src/core/SkScaledImageCache.cpp

/*
 * 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 "SkPixelRef.h"
#include "SkRect.h"

#ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
    #define SK_DEFAULT_IMAGE_CACHE_LIMIT     (2 * 1024 * 1024)
#endif


 // 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 Key {
    bool init(const SkBitmap& bm, SkScalar scaleX, SkScalar scaleY) {
        SkPixelRef* pr = bm.pixelRef();
        if (!pr) {
            return false;
        }

        size_t offset = bm.pixelRefOffset();
        size_t rowBytes = bm.rowBytes();
        int x = (offset % rowBytes) >> 2;
        int y = offset / rowBytes;

        fGenID = pr->getGenerationID();
        fBounds.set(x, y, x + bm.width(), y + bm.height());
        fScaleX = scaleX;
        fScaleY = scaleY;

        fHash = compute_hash(&fGenID, 7);
        return true;
    }

    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 Key& key_from_rec(const SkScaledImageCache::Rec& rec) {
    return rec.fKey;
}

uint32_t hash_from_key(const Key& key) {
    return key.fHash;
}

bool eq_rec_key(const SkScaledImageCache::Rec& rec, const Key& key) {
    return rec.fKey == key;
}
}

class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec,
                                   Key, key_from_rec, hash_from_key,
                                   eq_rec_key> {};

///////////////////////////////////////////////////////////////////////////////

// experimental hash to speed things up
#define USE_HASH

SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
    fHead = NULL;
    fTail = NULL;
#ifdef USE_HASH
    fHash = new Hash;
#else
    fHash = NULL;
#endif
    fBytesUsed = 0;
    fByteLimit = byteLimit;
    fCount = 0;
}

SkScaledImageCache::~SkScaledImageCache() {
    Rec* rec = fHead;
    while (rec) {
        Rec* next = rec->fNext;
        SkDELETE(rec);
        rec = next;
    }
    delete fHash;
}

SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig,
                                                        SkScalar scaleX,
                                                        SkScalar scaleY) {
    Key key;
    if (!key.init(orig, scaleX, scaleY)) {
        return NULL;
    }

#ifdef USE_HASH
    Rec* rec = fHash->find(key);
#else
    Rec* rec = fHead;
    while (rec != NULL) {
        if (rec->fKey == key) {
            break;
        }
        rec = rec->fNext;
    }
#endif

    if (rec) {
        this->moveToHead(rec);  // for our LRU
        rec->fLockCount += 1;
    }
    return 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, scaleX, scaleY);
    if (rec) {
        SkASSERT(NULL == rec->fMip);
        SkASSERT(rec->fBitmap.pixelRef());
        *scaled = rec->fBitmap;
    }
    return (ID*)rec;
}

SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig,
                                                           SkMipMap const ** mip) {
    Rec* rec = this->findAndLock(orig, 0, 0);
    if (rec) {
        SkASSERT(rec->fMip);
        SkASSERT(NULL == rec->fBitmap.pixelRef());
        *mip = rec->fMip;
    }
    return (ID*)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;
    }

    Key key;
    if (!key.init(orig, scaleX, scaleY)) {
        return NULL;
    }

    Rec* rec = SkNEW_ARGS(Rec, (key, scaled));
    this->addToHead(rec);
    SkASSERT(1 == rec->fLockCount);

#ifdef USE_HASH
    fHash->add(rec);
#endif

    // We may (now) be overbudget, so see if we need to purge something.
    this->purgeAsNeeded();
    return (ID*)rec;
}

SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig,
                                                          const SkMipMap* mip) {
    Key key;
    if (!key.init(orig, 0, 0)) {
        return NULL;
    }

    Rec* rec = SkNEW_ARGS(Rec, (key, mip));
    this->addToHead(rec);
    SkASSERT(1 == rec->fLockCount);

#ifdef USE_HASH
    fHash->add(rec);
#endif

    // We may (now) be overbudget, so see if we need to purge something.
    this->purgeAsNeeded();
    return (ID*)rec;
}

void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
    SkASSERT(id);

#ifdef SK_DEBUG
    {
        bool found = false;
        Rec* rec = fHead;
        while (rec != NULL) {
            if ((ID*)rec == id) {
                found = true;
                break;
            }
            rec = rec->fNext;
        }
        SkASSERT(found);
    }
#endif
    Rec* rec = (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 = fByteLimit;
    size_t bytesUsed = fBytesUsed;

    Rec* rec = fTail;
    while (rec) {
        if (bytesUsed < byteLimit) {
            break;
        }
        Rec* prev = rec->fPrev;
        if (0 == rec->fLockCount) {
            size_t used = rec->bytesUsed();
            SkASSERT(used <= bytesUsed);
            bytesUsed -= used;
            this->detach(rec);
#ifdef USE_HASH
            fHash->remove(rec->fKey);
#endif

            SkDELETE(rec);
            fCount -= 1;
        }
        rec = prev;
    }
    fBytesUsed = bytesUsed;
}

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

///////////////////////////////////////////////////////////////////////////////

#include "SkThread.h"

SK_DECLARE_STATIC_MUTEX(gMutex);

static SkScaledImageCache* get_cache() {
    static SkScaledImageCache* gCache;
    if (!gCache) {
        gCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT));
    }
    return gCache;
}

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);
    return get_cache()->unlock(id);
}

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);
}

///////////////////////////////////////////////////////////////////////////////

#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);
}