diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/core/SkScaledImageCache.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gfx/skia/trunk/src/core/SkScaledImageCache.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,798 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "SkScaledImageCache.h" +#include "SkMipMap.h" +#include "SkOnce.h" +#include "SkPixelRef.h" +#include "SkRect.h" + +// This can be defined by the caller's build system +//#define SK_USE_DISCARDABLE_SCALEDIMAGECACHE + +#ifndef SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT +# define SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT 1024 +#endif + +#ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT + #define SK_DEFAULT_IMAGE_CACHE_LIMIT (2 * 1024 * 1024) +#endif + +static inline SkScaledImageCache::ID* rec_to_id(SkScaledImageCache::Rec* rec) { + return reinterpret_cast(rec); +} + +static inline SkScaledImageCache::Rec* id_to_rec(SkScaledImageCache::ID* id) { + return reinterpret_cast(id); +} + + // Implemented from en.wikipedia.org/wiki/MurmurHash. +static uint32_t compute_hash(const uint32_t data[], int count) { + uint32_t hash = 0; + + for (int i = 0; i < count; ++i) { + uint32_t k = data[i]; + k *= 0xcc9e2d51; + k = (k << 15) | (k >> 17); + k *= 0x1b873593; + + hash ^= k; + hash = (hash << 13) | (hash >> 19); + hash *= 5; + hash += 0xe6546b64; + } + + // hash ^= size; + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + + return hash; +} + +struct SkScaledImageCache::Key { + Key(uint32_t genID, + SkScalar scaleX, + SkScalar scaleY, + SkIRect bounds) + : fGenID(genID) + , fScaleX(scaleX) + , fScaleY(scaleY) + , fBounds(bounds) { + fHash = compute_hash(&fGenID, 7); + } + + bool operator<(const Key& other) const { + const uint32_t* a = &fGenID; + const uint32_t* b = &other.fGenID; + for (int i = 0; i < 7; ++i) { + if (a[i] < b[i]) { + return true; + } + if (a[i] > b[i]) { + return false; + } + } + return false; + } + + bool operator==(const Key& other) const { + const uint32_t* a = &fHash; + const uint32_t* b = &other.fHash; + for (int i = 0; i < 8; ++i) { + if (a[i] != b[i]) { + return false; + } + } + return true; + } + + uint32_t fHash; + uint32_t fGenID; + float fScaleX; + float fScaleY; + SkIRect fBounds; +}; + +struct SkScaledImageCache::Rec { + Rec(const Key& key, const SkBitmap& bm) : fKey(key), fBitmap(bm) { + fLockCount = 1; + fMip = NULL; + } + + Rec(const Key& key, const SkMipMap* mip) : fKey(key) { + fLockCount = 1; + fMip = mip; + mip->ref(); + } + + ~Rec() { + SkSafeUnref(fMip); + } + + size_t bytesUsed() const { + return fMip ? fMip->getSize() : fBitmap.getSize(); + } + + Rec* fNext; + Rec* fPrev; + + // this guy wants to be 64bit aligned + Key fKey; + + int32_t fLockCount; + + // we use either fBitmap or fMip, but not both + SkBitmap fBitmap; + const SkMipMap* fMip; +}; + +#include "SkTDynamicHash.h" + +namespace { // can't use static functions w/ template parameters +const SkScaledImageCache::Key& key_from_rec(const SkScaledImageCache::Rec& rec) { + return rec.fKey; +} + +uint32_t hash_from_key(const SkScaledImageCache::Key& key) { + return key.fHash; +} + +bool eq_rec_key(const SkScaledImageCache::Rec& rec, const SkScaledImageCache::Key& key) { + return rec.fKey == key; +} +} + +class SkScaledImageCache::Hash : public SkTDynamicHash {}; + +/////////////////////////////////////////////////////////////////////////////// + +// experimental hash to speed things up +#define USE_HASH + +#if !defined(USE_HASH) +static inline SkScaledImageCache::Rec* find_rec_in_list( + SkScaledImageCache::Rec* head, const Key & key) { + SkScaledImageCache::Rec* rec = head; + while ((rec != NULL) && (rec->fKey != key)) { + rec = rec->fNext; + } + return rec; +} +#endif + +void SkScaledImageCache::init() { + fHead = NULL; + fTail = NULL; +#ifdef USE_HASH + fHash = new Hash; +#else + fHash = NULL; +#endif + fBytesUsed = 0; + fCount = 0; + fAllocator = NULL; + + // One of these should be explicit set by the caller after we return. + fByteLimit = 0; + fDiscardableFactory = NULL; +} + +#include "SkDiscardableMemory.h" + +class SkOneShotDiscardablePixelRef : public SkPixelRef { +public: + SK_DECLARE_INST_COUNT(SkOneShotDiscardablePixelRef) + // Ownership of the discardablememory is transfered to the pixelref + SkOneShotDiscardablePixelRef(const SkImageInfo&, SkDiscardableMemory*, size_t rowBytes); + ~SkOneShotDiscardablePixelRef(); + + SK_DECLARE_UNFLATTENABLE_OBJECT() + +protected: + virtual bool onNewLockPixels(LockRec*) SK_OVERRIDE; + virtual void onUnlockPixels() SK_OVERRIDE; + virtual size_t getAllocatedSizeInBytes() const SK_OVERRIDE; + +private: + SkDiscardableMemory* fDM; + size_t fRB; + bool fFirstTime; + + typedef SkPixelRef INHERITED; +}; + +SkOneShotDiscardablePixelRef::SkOneShotDiscardablePixelRef(const SkImageInfo& info, + SkDiscardableMemory* dm, + size_t rowBytes) + : INHERITED(info) + , fDM(dm) + , fRB(rowBytes) +{ + SkASSERT(dm->data()); + fFirstTime = true; +} + +SkOneShotDiscardablePixelRef::~SkOneShotDiscardablePixelRef() { + SkDELETE(fDM); +} + +bool SkOneShotDiscardablePixelRef::onNewLockPixels(LockRec* rec) { + if (fFirstTime) { + // we're already locked + SkASSERT(fDM->data()); + fFirstTime = false; + goto SUCCESS; + } + + // A previous call to onUnlock may have deleted our DM, so check for that + if (NULL == fDM) { + return false; + } + + if (!fDM->lock()) { + // since it failed, we delete it now, to free-up the resource + delete fDM; + fDM = NULL; + return false; + } + +SUCCESS: + rec->fPixels = fDM->data(); + rec->fColorTable = NULL; + rec->fRowBytes = fRB; + return true; +} + +void SkOneShotDiscardablePixelRef::onUnlockPixels() { + SkASSERT(!fFirstTime); + fDM->unlock(); +} + +size_t SkOneShotDiscardablePixelRef::getAllocatedSizeInBytes() const { + return this->info().getSafeSize(fRB); +} + +class SkScaledImageCacheDiscardableAllocator : public SkBitmap::Allocator { +public: + SkScaledImageCacheDiscardableAllocator( + SkScaledImageCache::DiscardableFactory factory) { + SkASSERT(factory); + fFactory = factory; + } + + virtual bool allocPixelRef(SkBitmap*, SkColorTable*) SK_OVERRIDE; + +private: + SkScaledImageCache::DiscardableFactory fFactory; +}; + +bool SkScaledImageCacheDiscardableAllocator::allocPixelRef(SkBitmap* bitmap, + SkColorTable* ctable) { + size_t size = bitmap->getSize(); + if (0 == size) { + return false; + } + + SkDiscardableMemory* dm = fFactory(size); + if (NULL == dm) { + return false; + } + + // can we relax this? + if (kPMColor_SkColorType != bitmap->colorType()) { + return false; + } + + SkImageInfo info = bitmap->info(); + bitmap->setPixelRef(SkNEW_ARGS(SkOneShotDiscardablePixelRef, + (info, dm, bitmap->rowBytes())))->unref(); + bitmap->lockPixels(); + return bitmap->readyToDraw(); +} + +SkScaledImageCache::SkScaledImageCache(DiscardableFactory factory) { + this->init(); + fDiscardableFactory = factory; + + fAllocator = SkNEW_ARGS(SkScaledImageCacheDiscardableAllocator, (factory)); +} + +SkScaledImageCache::SkScaledImageCache(size_t byteLimit) { + this->init(); + fByteLimit = byteLimit; +} + +SkScaledImageCache::~SkScaledImageCache() { + SkSafeUnref(fAllocator); + + Rec* rec = fHead; + while (rec) { + Rec* next = rec->fNext; + SkDELETE(rec); + rec = next; + } + delete fHash; +} + +//////////////////////////////////////////////////////////////////////////////// + + +SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(uint32_t genID, + SkScalar scaleX, + SkScalar scaleY, + const SkIRect& bounds) { + const Key key(genID, scaleX, scaleY, bounds); + return this->findAndLock(key); +} + +/** + This private method is the fully general record finder. All other + record finders should call this function or the one above. */ +SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkScaledImageCache::Key& key) { + if (key.fBounds.isEmpty()) { + return NULL; + } +#ifdef USE_HASH + Rec* rec = fHash->find(key); +#else + Rec* rec = find_rec_in_list(fHead, key); +#endif + if (rec) { + this->moveToHead(rec); // for our LRU + rec->fLockCount += 1; + } + return rec; +} + +/** + This function finds the bounds of the bitmap *within its pixelRef*. + If the bitmap lacks a pixelRef, it will return an empty rect, since + that doesn't make sense. This may be a useful enough function that + it should be somewhere else (in SkBitmap?). */ +static SkIRect get_bounds_from_bitmap(const SkBitmap& bm) { + if (!(bm.pixelRef())) { + return SkIRect::MakeEmpty(); + } + SkIPoint origin = bm.pixelRefOrigin(); + return SkIRect::MakeXYWH(origin.fX, origin.fY, bm.width(), bm.height()); +} + + +SkScaledImageCache::ID* SkScaledImageCache::findAndLock(uint32_t genID, + int32_t width, + int32_t height, + SkBitmap* bitmap) { + Rec* rec = this->findAndLock(genID, SK_Scalar1, SK_Scalar1, + SkIRect::MakeWH(width, height)); + if (rec) { + SkASSERT(NULL == rec->fMip); + SkASSERT(rec->fBitmap.pixelRef()); + *bitmap = rec->fBitmap; + } + return rec_to_id(rec); +} + +SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig, + SkScalar scaleX, + SkScalar scaleY, + SkBitmap* scaled) { + if (0 == scaleX || 0 == scaleY) { + // degenerate, and the key we use for mipmaps + return NULL; + } + Rec* rec = this->findAndLock(orig.getGenerationID(), scaleX, + scaleY, get_bounds_from_bitmap(orig)); + if (rec) { + SkASSERT(NULL == rec->fMip); + SkASSERT(rec->fBitmap.pixelRef()); + *scaled = rec->fBitmap; + } + return rec_to_id(rec); +} + +SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig, + SkMipMap const ** mip) { + Rec* rec = this->findAndLock(orig.getGenerationID(), 0, 0, + get_bounds_from_bitmap(orig)); + if (rec) { + SkASSERT(rec->fMip); + SkASSERT(NULL == rec->fBitmap.pixelRef()); + *mip = rec->fMip; + } + return rec_to_id(rec); +} + + +//////////////////////////////////////////////////////////////////////////////// +/** + This private method is the fully general record adder. All other + record adders should call this funtion. */ +SkScaledImageCache::ID* SkScaledImageCache::addAndLock(SkScaledImageCache::Rec* rec) { + SkASSERT(rec); + // See if we already have this key (racy inserts, etc.) + Rec* existing = this->findAndLock(rec->fKey); + if (NULL != existing) { + // Since we already have a matching entry, just delete the new one and return. + // Call sites cannot assume the passed in object will live past this call. + existing->fBitmap = rec->fBitmap; + SkDELETE(rec); + return rec_to_id(existing); + } + + this->addToHead(rec); + SkASSERT(1 == rec->fLockCount); +#ifdef USE_HASH + SkASSERT(fHash); + fHash->add(rec); +#endif + // We may (now) be overbudget, so see if we need to purge something. + this->purgeAsNeeded(); + return rec_to_id(rec); +} + +SkScaledImageCache::ID* SkScaledImageCache::addAndLock(uint32_t genID, + int32_t width, + int32_t height, + const SkBitmap& bitmap) { + Key key(genID, SK_Scalar1, SK_Scalar1, SkIRect::MakeWH(width, height)); + Rec* rec = SkNEW_ARGS(Rec, (key, bitmap)); + return this->addAndLock(rec); +} + +SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig, + SkScalar scaleX, + SkScalar scaleY, + const SkBitmap& scaled) { + if (0 == scaleX || 0 == scaleY) { + // degenerate, and the key we use for mipmaps + return NULL; + } + SkIRect bounds = get_bounds_from_bitmap(orig); + if (bounds.isEmpty()) { + return NULL; + } + Key key(orig.getGenerationID(), scaleX, scaleY, bounds); + Rec* rec = SkNEW_ARGS(Rec, (key, scaled)); + return this->addAndLock(rec); +} + +SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig, + const SkMipMap* mip) { + SkIRect bounds = get_bounds_from_bitmap(orig); + if (bounds.isEmpty()) { + return NULL; + } + Key key(orig.getGenerationID(), 0, 0, bounds); + Rec* rec = SkNEW_ARGS(Rec, (key, mip)); + return this->addAndLock(rec); +} + +void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) { + SkASSERT(id); + +#ifdef SK_DEBUG + { + bool found = false; + Rec* rec = fHead; + while (rec != NULL) { + if (rec == id_to_rec(id)) { + found = true; + break; + } + rec = rec->fNext; + } + SkASSERT(found); + } +#endif + Rec* rec = id_to_rec(id); + SkASSERT(rec->fLockCount > 0); + rec->fLockCount -= 1; + + // we may have been over-budget, but now have released something, so check + // if we should purge. + if (0 == rec->fLockCount) { + this->purgeAsNeeded(); + } +} + +void SkScaledImageCache::purgeAsNeeded() { + size_t byteLimit; + int countLimit; + + if (fDiscardableFactory) { + countLimit = SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT; + byteLimit = SK_MaxU32; // no limit based on bytes + } else { + countLimit = SK_MaxS32; // no limit based on count + byteLimit = fByteLimit; + } + + size_t bytesUsed = fBytesUsed; + int countUsed = fCount; + + Rec* rec = fTail; + while (rec) { + if (bytesUsed < byteLimit && countUsed < countLimit) { + break; + } + + Rec* prev = rec->fPrev; + if (0 == rec->fLockCount) { + size_t used = rec->bytesUsed(); + SkASSERT(used <= bytesUsed); + this->detach(rec); +#ifdef USE_HASH + fHash->remove(rec->fKey); +#endif + + SkDELETE(rec); + + bytesUsed -= used; + countUsed -= 1; + } + rec = prev; + } + + fBytesUsed = bytesUsed; + fCount = countUsed; +} + +size_t SkScaledImageCache::setByteLimit(size_t newLimit) { + size_t prevLimit = fByteLimit; + fByteLimit = newLimit; + if (newLimit < prevLimit) { + this->purgeAsNeeded(); + } + return prevLimit; +} + +/////////////////////////////////////////////////////////////////////////////// + +void SkScaledImageCache::detach(Rec* rec) { + Rec* prev = rec->fPrev; + Rec* next = rec->fNext; + + if (!prev) { + SkASSERT(fHead == rec); + fHead = next; + } else { + prev->fNext = next; + } + + if (!next) { + fTail = prev; + } else { + next->fPrev = prev; + } + + rec->fNext = rec->fPrev = NULL; +} + +void SkScaledImageCache::moveToHead(Rec* rec) { + if (fHead == rec) { + return; + } + + SkASSERT(fHead); + SkASSERT(fTail); + + this->validate(); + + this->detach(rec); + + fHead->fPrev = rec; + rec->fNext = fHead; + fHead = rec; + + this->validate(); +} + +void SkScaledImageCache::addToHead(Rec* rec) { + this->validate(); + + rec->fPrev = NULL; + rec->fNext = fHead; + if (fHead) { + fHead->fPrev = rec; + } + fHead = rec; + if (!fTail) { + fTail = rec; + } + fBytesUsed += rec->bytesUsed(); + fCount += 1; + + this->validate(); +} + +/////////////////////////////////////////////////////////////////////////////// + +#ifdef SK_DEBUG +void SkScaledImageCache::validate() const { + if (NULL == fHead) { + SkASSERT(NULL == fTail); + SkASSERT(0 == fBytesUsed); + return; + } + + if (fHead == fTail) { + SkASSERT(NULL == fHead->fPrev); + SkASSERT(NULL == fHead->fNext); + SkASSERT(fHead->bytesUsed() == fBytesUsed); + return; + } + + SkASSERT(NULL == fHead->fPrev); + SkASSERT(NULL != fHead->fNext); + SkASSERT(NULL == fTail->fNext); + SkASSERT(NULL != fTail->fPrev); + + size_t used = 0; + int count = 0; + const Rec* rec = fHead; + while (rec) { + count += 1; + used += rec->bytesUsed(); + SkASSERT(used <= fBytesUsed); + rec = rec->fNext; + } + SkASSERT(fCount == count); + + rec = fTail; + while (rec) { + SkASSERT(count > 0); + count -= 1; + SkASSERT(used >= rec->bytesUsed()); + used -= rec->bytesUsed(); + rec = rec->fPrev; + } + + SkASSERT(0 == count); + SkASSERT(0 == used); +} +#endif + +void SkScaledImageCache::dump() const { + this->validate(); + + const Rec* rec = fHead; + int locked = 0; + while (rec) { + locked += rec->fLockCount > 0; + rec = rec->fNext; + } + + SkDebugf("SkScaledImageCache: count=%d bytes=%d locked=%d %s\n", + fCount, fBytesUsed, locked, + fDiscardableFactory ? "discardable" : "malloc"); +} + +/////////////////////////////////////////////////////////////////////////////// + +#include "SkThread.h" + +SK_DECLARE_STATIC_MUTEX(gMutex); +static SkScaledImageCache* gScaledImageCache = NULL; +static void cleanup_gScaledImageCache() { SkDELETE(gScaledImageCache); } + +static void create_cache(int) { +#ifdef SK_USE_DISCARDABLE_SCALEDIMAGECACHE + gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SkDiscardableMemory::Create)); +#else + gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT)); +#endif +} + +static SkScaledImageCache* get_cache() { + SK_DECLARE_STATIC_ONCE(once); + SkOnce(&once, create_cache, 0, cleanup_gScaledImageCache); + SkASSERT(NULL != gScaledImageCache); + return gScaledImageCache; +} + + +SkScaledImageCache::ID* SkScaledImageCache::FindAndLock( + uint32_t pixelGenerationID, + int32_t width, + int32_t height, + SkBitmap* scaled) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->findAndLock(pixelGenerationID, width, height, scaled); +} + +SkScaledImageCache::ID* SkScaledImageCache::AddAndLock( + uint32_t pixelGenerationID, + int32_t width, + int32_t height, + const SkBitmap& scaled) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->addAndLock(pixelGenerationID, width, height, scaled); +} + + +SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(const SkBitmap& orig, + SkScalar scaleX, + SkScalar scaleY, + SkBitmap* scaled) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->findAndLock(orig, scaleX, scaleY, scaled); +} + +SkScaledImageCache::ID* SkScaledImageCache::FindAndLockMip(const SkBitmap& orig, + SkMipMap const ** mip) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->findAndLockMip(orig, mip); +} + +SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(const SkBitmap& orig, + SkScalar scaleX, + SkScalar scaleY, + const SkBitmap& scaled) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->addAndLock(orig, scaleX, scaleY, scaled); +} + +SkScaledImageCache::ID* SkScaledImageCache::AddAndLockMip(const SkBitmap& orig, + const SkMipMap* mip) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->addAndLockMip(orig, mip); +} + +void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) { + SkAutoMutexAcquire am(gMutex); + get_cache()->unlock(id); + +// get_cache()->dump(); +} + +size_t SkScaledImageCache::GetBytesUsed() { + SkAutoMutexAcquire am(gMutex); + return get_cache()->getBytesUsed(); +} + +size_t SkScaledImageCache::GetByteLimit() { + SkAutoMutexAcquire am(gMutex); + return get_cache()->getByteLimit(); +} + +size_t SkScaledImageCache::SetByteLimit(size_t newLimit) { + SkAutoMutexAcquire am(gMutex); + return get_cache()->setByteLimit(newLimit); +} + +SkBitmap::Allocator* SkScaledImageCache::GetAllocator() { + SkAutoMutexAcquire am(gMutex); + return get_cache()->allocator(); +} + +void SkScaledImageCache::Dump() { + SkAutoMutexAcquire am(gMutex); + get_cache()->dump(); +} + +/////////////////////////////////////////////////////////////////////////////// + +#include "SkGraphics.h" + +size_t SkGraphics::GetImageCacheBytesUsed() { + return SkScaledImageCache::GetBytesUsed(); +} + +size_t SkGraphics::GetImageCacheByteLimit() { + return SkScaledImageCache::GetByteLimit(); +} + +size_t SkGraphics::SetImageCacheByteLimit(size_t newLimit) { + return SkScaledImageCache::SetByteLimit(newLimit); +}