1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkScaledImageCache.h"
9#include "SkMipMap.h"
10#include "SkPixelRef.h"
11#include "SkRect.h"
12
13#ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
14    #define SK_DEFAULT_IMAGE_CACHE_LIMIT     (2 * 1024 * 1024)
15#endif
16
17
18 // Implemented from en.wikipedia.org/wiki/MurmurHash.
19static uint32_t compute_hash(const uint32_t data[], int count) {
20    uint32_t hash = 0;
21
22    for (int i = 0; i < count; ++i) {
23        uint32_t k = data[i];
24        k *= 0xcc9e2d51;
25        k = (k << 15) | (k >> 17);
26        k *= 0x1b873593;
27
28        hash ^= k;
29        hash = (hash << 13) | (hash >> 19);
30        hash *= 5;
31        hash += 0xe6546b64;
32    }
33
34    //    hash ^= size;
35    hash ^= hash >> 16;
36    hash *= 0x85ebca6b;
37    hash ^= hash >> 13;
38    hash *= 0xc2b2ae35;
39    hash ^= hash >> 16;
40
41    return hash;
42}
43
44struct Key {
45    bool init(const SkBitmap& bm, SkScalar scaleX, SkScalar scaleY) {
46        SkPixelRef* pr = bm.pixelRef();
47        if (!pr) {
48            return false;
49        }
50
51        size_t offset = bm.pixelRefOffset();
52        size_t rowBytes = bm.rowBytes();
53        int x = (offset % rowBytes) >> 2;
54        int y = offset / rowBytes;
55
56        fGenID = pr->getGenerationID();
57        fBounds.set(x, y, x + bm.width(), y + bm.height());
58        fScaleX = scaleX;
59        fScaleY = scaleY;
60
61        fHash = compute_hash(&fGenID, 7);
62        return true;
63    }
64
65    bool operator<(const Key& other) const {
66        const uint32_t* a = &fGenID;
67        const uint32_t* b = &other.fGenID;
68        for (int i = 0; i < 7; ++i) {
69            if (a[i] < b[i]) {
70                return true;
71            }
72            if (a[i] > b[i]) {
73                return false;
74            }
75        }
76        return false;
77    }
78
79    bool operator==(const Key& other) const {
80        const uint32_t* a = &fHash;
81        const uint32_t* b = &other.fHash;
82        for (int i = 0; i < 8; ++i) {
83            if (a[i] != b[i]) {
84                return false;
85            }
86        }
87        return true;
88    }
89
90    uint32_t    fHash;
91    uint32_t    fGenID;
92    float       fScaleX;
93    float       fScaleY;
94    SkIRect     fBounds;
95};
96
97struct SkScaledImageCache::Rec {
98    Rec(const Key& key, const SkBitmap& bm) : fKey(key), fBitmap(bm) {
99        fLockCount = 1;
100        fMip = NULL;
101    }
102
103    Rec(const Key& key, const SkMipMap* mip) : fKey(key) {
104        fLockCount = 1;
105        fMip = mip;
106        mip->ref();
107    }
108
109    ~Rec() {
110        SkSafeUnref(fMip);
111    }
112
113    size_t bytesUsed() const {
114        return fMip ? fMip->getSize() : fBitmap.getSize();
115    }
116
117    Rec*    fNext;
118    Rec*    fPrev;
119
120    // this guy wants to be 64bit aligned
121    Key     fKey;
122
123    int32_t fLockCount;
124
125    // we use either fBitmap or fMip, but not both
126    SkBitmap fBitmap;
127    const SkMipMap* fMip;
128};
129
130#include "SkTDynamicHash.h"
131
132namespace { // can't use static functions w/ template parameters
133const Key& key_from_rec(const SkScaledImageCache::Rec& rec) {
134    return rec.fKey;
135}
136
137uint32_t hash_from_key(const Key& key) {
138    return key.fHash;
139}
140
141bool eq_rec_key(const SkScaledImageCache::Rec& rec, const Key& key) {
142    return rec.fKey == key;
143}
144}
145
146class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec,
147                                   Key, key_from_rec, hash_from_key,
148                                   eq_rec_key> {};
149
150///////////////////////////////////////////////////////////////////////////////
151
152// experimental hash to speed things up
153#define USE_HASH
154
155SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
156    fHead = NULL;
157    fTail = NULL;
158#ifdef USE_HASH
159    fHash = new Hash;
160#else
161    fHash = NULL;
162#endif
163    fBytesUsed = 0;
164    fByteLimit = byteLimit;
165    fCount = 0;
166}
167
168SkScaledImageCache::~SkScaledImageCache() {
169    Rec* rec = fHead;
170    while (rec) {
171        Rec* next = rec->fNext;
172        SkDELETE(rec);
173        rec = next;
174    }
175    delete fHash;
176}
177
178SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig,
179                                                        SkScalar scaleX,
180                                                        SkScalar scaleY) {
181    Key key;
182    if (!key.init(orig, scaleX, scaleY)) {
183        return NULL;
184    }
185
186#ifdef USE_HASH
187    Rec* rec = fHash->find(key);
188#else
189    Rec* rec = fHead;
190    while (rec != NULL) {
191        if (rec->fKey == key) {
192            break;
193        }
194        rec = rec->fNext;
195    }
196#endif
197
198    if (rec) {
199        this->moveToHead(rec);  // for our LRU
200        rec->fLockCount += 1;
201    }
202    return rec;
203}
204
205SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
206                                                        SkScalar scaleX,
207                                                        SkScalar scaleY,
208                                                        SkBitmap* scaled) {
209    if (0 == scaleX || 0 == scaleY) {
210        // degenerate, and the key we use for mipmaps
211        return NULL;
212    }
213
214    Rec* rec = this->findAndLock(orig, scaleX, scaleY);
215    if (rec) {
216        SkASSERT(NULL == rec->fMip);
217        SkASSERT(rec->fBitmap.pixelRef());
218        *scaled = rec->fBitmap;
219    }
220    return (ID*)rec;
221}
222
223SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig,
224                                                           SkMipMap const ** mip) {
225    Rec* rec = this->findAndLock(orig, 0, 0);
226    if (rec) {
227        SkASSERT(rec->fMip);
228        SkASSERT(NULL == rec->fBitmap.pixelRef());
229        *mip = rec->fMip;
230    }
231    return (ID*)rec;
232}
233
234SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig,
235                                                       SkScalar scaleX,
236                                                       SkScalar scaleY,
237                                                       const SkBitmap& scaled) {
238    if (0 == scaleX || 0 == scaleY) {
239        // degenerate, and the key we use for mipmaps
240        return NULL;
241    }
242
243    Key key;
244    if (!key.init(orig, scaleX, scaleY)) {
245        return NULL;
246    }
247
248    Rec* rec = SkNEW_ARGS(Rec, (key, scaled));
249    this->addToHead(rec);
250    SkASSERT(1 == rec->fLockCount);
251
252#ifdef USE_HASH
253    fHash->add(rec);
254#endif
255
256    // We may (now) be overbudget, so see if we need to purge something.
257    this->purgeAsNeeded();
258    return (ID*)rec;
259}
260
261SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig,
262                                                          const SkMipMap* mip) {
263    Key key;
264    if (!key.init(orig, 0, 0)) {
265        return NULL;
266    }
267
268    Rec* rec = SkNEW_ARGS(Rec, (key, mip));
269    this->addToHead(rec);
270    SkASSERT(1 == rec->fLockCount);
271
272#ifdef USE_HASH
273    fHash->add(rec);
274#endif
275
276    // We may (now) be overbudget, so see if we need to purge something.
277    this->purgeAsNeeded();
278    return (ID*)rec;
279}
280
281void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
282    SkASSERT(id);
283
284#ifdef SK_DEBUG
285    {
286        bool found = false;
287        Rec* rec = fHead;
288        while (rec != NULL) {
289            if ((ID*)rec == id) {
290                found = true;
291                break;
292            }
293            rec = rec->fNext;
294        }
295        SkASSERT(found);
296    }
297#endif
298    Rec* rec = (Rec*)id;
299    SkASSERT(rec->fLockCount > 0);
300    rec->fLockCount -= 1;
301
302    // we may have been over-budget, but now have released something, so check
303    // if we should purge.
304    if (0 == rec->fLockCount) {
305        this->purgeAsNeeded();
306    }
307}
308
309void SkScaledImageCache::purgeAsNeeded() {
310    size_t byteLimit = fByteLimit;
311    size_t bytesUsed = fBytesUsed;
312
313    Rec* rec = fTail;
314    while (rec) {
315        if (bytesUsed < byteLimit) {
316            break;
317        }
318        Rec* prev = rec->fPrev;
319        if (0 == rec->fLockCount) {
320            size_t used = rec->bytesUsed();
321            SkASSERT(used <= bytesUsed);
322            bytesUsed -= used;
323            this->detach(rec);
324#ifdef USE_HASH
325            fHash->remove(rec->fKey);
326#endif
327
328            SkDELETE(rec);
329            fCount -= 1;
330        }
331        rec = prev;
332    }
333    fBytesUsed = bytesUsed;
334}
335
336size_t SkScaledImageCache::setByteLimit(size_t newLimit) {
337    size_t prevLimit = fByteLimit;
338    fByteLimit = newLimit;
339    if (newLimit < prevLimit) {
340        this->purgeAsNeeded();
341    }
342    return prevLimit;
343}
344
345///////////////////////////////////////////////////////////////////////////////
346
347void SkScaledImageCache::detach(Rec* rec) {
348    Rec* prev = rec->fPrev;
349    Rec* next = rec->fNext;
350
351    if (!prev) {
352        SkASSERT(fHead == rec);
353        fHead = next;
354    } else {
355        prev->fNext = next;
356    }
357
358    if (!next) {
359        fTail = prev;
360    } else {
361        next->fPrev = prev;
362    }
363
364    rec->fNext = rec->fPrev = NULL;
365}
366
367void SkScaledImageCache::moveToHead(Rec* rec) {
368    if (fHead == rec) {
369        return;
370    }
371
372    SkASSERT(fHead);
373    SkASSERT(fTail);
374
375    this->validate();
376
377    this->detach(rec);
378
379    fHead->fPrev = rec;
380    rec->fNext = fHead;
381    fHead = rec;
382
383    this->validate();
384}
385
386void SkScaledImageCache::addToHead(Rec* rec) {
387    this->validate();
388
389    rec->fPrev = NULL;
390    rec->fNext = fHead;
391    if (fHead) {
392        fHead->fPrev = rec;
393    }
394    fHead = rec;
395    if (!fTail) {
396        fTail = rec;
397    }
398    fBytesUsed += rec->bytesUsed();
399    fCount += 1;
400
401    this->validate();
402}
403
404#ifdef SK_DEBUG
405void SkScaledImageCache::validate() const {
406    if (NULL == fHead) {
407        SkASSERT(NULL == fTail);
408        SkASSERT(0 == fBytesUsed);
409        return;
410    }
411
412    if (fHead == fTail) {
413        SkASSERT(NULL == fHead->fPrev);
414        SkASSERT(NULL == fHead->fNext);
415        SkASSERT(fHead->bytesUsed() == fBytesUsed);
416        return;
417    }
418
419    SkASSERT(NULL == fHead->fPrev);
420    SkASSERT(NULL != fHead->fNext);
421    SkASSERT(NULL == fTail->fNext);
422    SkASSERT(NULL != fTail->fPrev);
423
424    size_t used = 0;
425    int count = 0;
426    const Rec* rec = fHead;
427    while (rec) {
428        count += 1;
429        used += rec->bytesUsed();
430        SkASSERT(used <= fBytesUsed);
431        rec = rec->fNext;
432    }
433    SkASSERT(fCount == count);
434
435    rec = fTail;
436    while (rec) {
437        SkASSERT(count > 0);
438        count -= 1;
439        SkASSERT(used >= rec->bytesUsed());
440        used -= rec->bytesUsed();
441        rec = rec->fPrev;
442    }
443
444    SkASSERT(0 == count);
445    SkASSERT(0 == used);
446}
447#endif
448
449///////////////////////////////////////////////////////////////////////////////
450
451#include "SkThread.h"
452
453SK_DECLARE_STATIC_MUTEX(gMutex);
454
455static SkScaledImageCache* get_cache() {
456    static SkScaledImageCache* gCache;
457    if (!gCache) {
458        gCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT));
459    }
460    return gCache;
461}
462
463SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(const SkBitmap& orig,
464                                                        SkScalar scaleX,
465                                                        SkScalar scaleY,
466                                                        SkBitmap* scaled) {
467    SkAutoMutexAcquire am(gMutex);
468    return get_cache()->findAndLock(orig, scaleX, scaleY, scaled);
469}
470
471SkScaledImageCache::ID* SkScaledImageCache::FindAndLockMip(const SkBitmap& orig,
472                                                       SkMipMap const ** mip) {
473    SkAutoMutexAcquire am(gMutex);
474    return get_cache()->findAndLockMip(orig, mip);
475}
476
477SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(const SkBitmap& orig,
478                                                       SkScalar scaleX,
479                                                       SkScalar scaleY,
480                                                       const SkBitmap& scaled) {
481    SkAutoMutexAcquire am(gMutex);
482    return get_cache()->addAndLock(orig, scaleX, scaleY, scaled);
483}
484
485SkScaledImageCache::ID* SkScaledImageCache::AddAndLockMip(const SkBitmap& orig,
486                                                          const SkMipMap* mip) {
487    SkAutoMutexAcquire am(gMutex);
488    return get_cache()->addAndLockMip(orig, mip);
489}
490
491void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) {
492    SkAutoMutexAcquire am(gMutex);
493    return get_cache()->unlock(id);
494}
495
496size_t SkScaledImageCache::GetBytesUsed() {
497    SkAutoMutexAcquire am(gMutex);
498    return get_cache()->getBytesUsed();
499}
500
501size_t SkScaledImageCache::GetByteLimit() {
502    SkAutoMutexAcquire am(gMutex);
503    return get_cache()->getByteLimit();
504}
505
506size_t SkScaledImageCache::SetByteLimit(size_t newLimit) {
507    SkAutoMutexAcquire am(gMutex);
508    return get_cache()->setByteLimit(newLimit);
509}
510
511///////////////////////////////////////////////////////////////////////////////
512
513#include "SkGraphics.h"
514
515size_t SkGraphics::GetImageCacheBytesUsed() {
516    return SkScaledImageCache::GetBytesUsed();
517}
518
519size_t SkGraphics::GetImageCacheByteLimit() {
520    return SkScaledImageCache::GetByteLimit();
521}
522
523size_t SkGraphics::SetImageCacheByteLimit(size_t newLimit) {
524    return SkScaledImageCache::SetByteLimit(newLimit);
525}
526