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