/* * Copyright 2006 The Android Open Source Project * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "SkGlyphCache.h" #include "SkGlyphCache_Globals.h" #include "SkGraphics.h" #include "SkLazyPtr.h" #include "SkPaint.h" #include "SkPath.h" #include "SkTemplates.h" #include "SkTLS.h" #include "SkTypeface.h" //#define SPEW_PURGE_STATUS namespace { SkGlyphCache_Globals* create_globals() { return SkNEW_ARGS(SkGlyphCache_Globals, (SkGlyphCache_Globals::kYes_UseMutex)); } } // namespace SK_DECLARE_STATIC_LAZY_PTR(SkGlyphCache_Globals, globals, create_globals); // Returns the shared globals static SkGlyphCache_Globals& getSharedGlobals() { return *globals.get(); } // Returns the TLS globals (if set), or the shared globals static SkGlyphCache_Globals& getGlobals() { SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS(); return tls ? *tls : getSharedGlobals(); } /////////////////////////////////////////////////////////////////////////////// #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS #define RecordHashSuccess() fHashHitCount += 1 #define RecordHashCollisionIf(pred) do { if (pred) fHashMissCount += 1; } while (0) #else #define RecordHashSuccess() (void)0 #define RecordHashCollisionIf(pred) (void)0 #endif #define RecordHashCollision() RecordHashCollisionIf(true) /////////////////////////////////////////////////////////////////////////////// // so we don't grow our arrays a lot #define kMinGlyphCount 16 #define kMinGlyphImageSize (16*2) #define kMinAllocAmount ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount) SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkScalerContext* ctx) : fScalerContext(ctx), fGlyphAlloc(kMinAllocAmount) { SkASSERT(typeface); SkASSERT(desc); SkASSERT(ctx); fPrev = fNext = NULL; fDesc = desc->copy(); fScalerContext->getFontMetrics(&fFontMetrics); // Create the sentinel SkGlyph. SkGlyph* sentinel = fGlyphArray.insert(0); sentinel->initGlyphFromCombinedID(SkGlyph::kImpossibleID); // Initialize all index to zero which points to the sentinel SkGlyph. memset(fGlyphHash, 0x00, sizeof(fGlyphHash)); fMemoryUsed = sizeof(*this); fGlyphArray.setReserve(kMinGlyphCount); fAuxProcList = NULL; #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS fHashHitCount = fHashMissCount = 0; #endif } SkGlyphCache::~SkGlyphCache() { #if 0 { size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*); size_t glyphAlloc = fGlyphAlloc.totalCapacity(); size_t glyphHashUsed = 0; size_t uniHashUsed = 0; for (int i = 0; i < kHashCount; ++i) { glyphHashUsed += fGlyphHash[i] ? sizeof(fGlyphHash[0]) : 0; uniHashUsed += fCharToGlyphHash[i].fID != 0xFFFFFFFF ? sizeof(fCharToGlyphHash[0]) : 0; } size_t glyphUsed = fGlyphArray.count() * sizeof(SkGlyph); size_t imageUsed = 0; for (int i = 0; i < fGlyphArray.count(); ++i) { const SkGlyph& g = *fGlyphArray[i]; if (g.fImage) { imageUsed += g.fHeight * g.rowBytes(); } } SkDebugf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n", ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(CharGlyphRec) * kHashCount, uniHashUsed); } #endif SkGlyph* gptr = fGlyphArray.begin(); SkGlyph* stop = fGlyphArray.end(); while (gptr < stop) { SkPath* path = gptr->fPath; if (path) { SkDELETE(path); } gptr += 1; } SkDescriptor::Free(fDesc); SkDELETE(fScalerContext); this->invokeAndRemoveAuxProcs(); } SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) { if (NULL == fCharToGlyphHash.get()) { // Allocate the array. fCharToGlyphHash.reset(kHashCount); // Initialize entries of fCharToGlyphHash to index the sentinel glyph and // an fID value that will not match any id. for (int i = 0; i <kHashCount; ++i) { fCharToGlyphHash[i].fID = SkGlyph::kImpossibleID; fCharToGlyphHash[i].fGlyphIndex = 0; } } return &fCharToGlyphHash[ID2HashIndex(id)]; } void SkGlyphCache::adjustCaches(int insertion_index) { for (int i = 0; i < kHashCount; ++i) { if (fGlyphHash[i] >= SkToU16(insertion_index)) { fGlyphHash[i] += 1; } } if (fCharToGlyphHash.get() != NULL) { for (int i = 0; i < kHashCount; ++i) { if (fCharToGlyphHash[i].fGlyphIndex >= SkToU16(insertion_index)) { fCharToGlyphHash[i].fGlyphIndex += 1; } } } } /////////////////////////////////////////////////////////////////////////////// #ifdef SK_DEBUG #define VALIDATE() AutoValidate av(this) #else #define VALIDATE() #endif uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) { VALIDATE(); uint32_t id = SkGlyph::MakeID(charCode); const CharGlyphRec& rec = *this->getCharGlyphRec(id); if (rec.fID == id) { return fGlyphArray[rec.fGlyphIndex].getGlyphID(); } else { return fScalerContext->charToGlyphID(charCode); } } SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) { return fScalerContext->glyphIDToChar(glyphID); } unsigned SkGlyphCache::getGlyphCount() { return fScalerContext->getGlyphCount(); } /////////////////////////////////////////////////////////////////////////////// const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) { VALIDATE(); return *this->lookupByChar(charCode, kJustAdvance_MetricsType); } const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) { VALIDATE(); uint32_t id = SkGlyph::MakeID(glyphID); return *this->lookupByCombinedID(id, kJustAdvance_MetricsType); } /////////////////////////////////////////////////////////////////////////////// const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) { VALIDATE(); return *this->lookupByChar(charCode, kFull_MetricsType); } const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) { VALIDATE(); return *this->lookupByChar(charCode, kFull_MetricsType, x, y); } const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) { VALIDATE(); uint32_t id = SkGlyph::MakeID(glyphID); return *this->lookupByCombinedID(id, kFull_MetricsType); } const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) { VALIDATE(); uint32_t id = SkGlyph::MakeID(glyphID, x, y); return *this->lookupByCombinedID(id, kFull_MetricsType); } SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) { uint32_t id = SkGlyph::MakeID(charCode, x, y); CharGlyphRec* rec = this->getCharGlyphRec(id); SkGlyph* glyph; if (rec->fID != id) { RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID); // this ID is based on the UniChar rec->fID = id; // this ID is based on the glyph index id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y); rec->fGlyphIndex = this->lookupMetrics(id, type); glyph = &fGlyphArray[rec->fGlyphIndex]; } else { RecordHashSuccess(); glyph = &fGlyphArray[rec->fGlyphIndex]; if (type == kFull_MetricsType && glyph->isJustAdvance()) { fScalerContext->getMetrics(glyph); } } return glyph; } SkGlyph* SkGlyphCache::lookupByCombinedID(uint32_t id, MetricsType type) { uint32_t hash_index = ID2HashIndex(id); uint16_t glyph_index = fGlyphHash[hash_index]; SkGlyph* glyph = &fGlyphArray[glyph_index]; if (glyph->fID != id) { RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID); glyph_index = this->lookupMetrics(id, type); fGlyphHash[hash_index] = glyph_index; glyph = &fGlyphArray[glyph_index]; } else { RecordHashSuccess(); if (type == kFull_MetricsType && glyph->isJustAdvance()) { fScalerContext->getMetrics(glyph); } } return glyph; } uint16_t SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) { SkASSERT(id != SkGlyph::kImpossibleID); // Count is always greater than 0 because of the sentinel. // The fGlyphArray cache is in descending order, so that the sentinel with a value of ~0 is // always at index 0. SkGlyph* gptr = fGlyphArray.begin(); int lo = 0; int hi = fGlyphArray.count() - 1; while (lo < hi) { int mid = (hi + lo) >> 1; if (gptr[mid].fID > id) { lo = mid + 1; } else { hi = mid; } } uint16_t glyph_index = hi; SkGlyph* glyph = &gptr[glyph_index]; if (glyph->fID == id) { if (kFull_MetricsType == mtype && glyph->isJustAdvance()) { fScalerContext->getMetrics(glyph); } SkASSERT(glyph->fID != SkGlyph::kImpossibleID); return glyph_index; } // check if we need to bump hi before falling though to the allocator if (glyph->fID > id) { glyph_index += 1; } // Not found, but hi contains the index of the insertion point of the new glyph. fMemoryUsed += sizeof(SkGlyph); this->adjustCaches(glyph_index); glyph = fGlyphArray.insert(glyph_index); glyph->initGlyphFromCombinedID(id); if (kJustAdvance_MetricsType == mtype) { fScalerContext->getAdvance(glyph); } else { SkASSERT(kFull_MetricsType == mtype); fScalerContext->getMetrics(glyph); } SkASSERT(glyph->fID != SkGlyph::kImpossibleID); return glyph_index; } const void* SkGlyphCache::findImage(const SkGlyph& glyph) { if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) { if (NULL == glyph.fImage) { size_t size = glyph.computeImageSize(); const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size, SkChunkAlloc::kReturnNil_AllocFailType); // check that alloc() actually succeeded if (glyph.fImage) { fScalerContext->getImage(glyph); // TODO: the scaler may have changed the maskformat during // getImage (e.g. from AA or LCD to BW) which means we may have // overallocated the buffer. Check if the new computedImageSize // is smaller, and if so, strink the alloc size in fImageAlloc. fMemoryUsed += size; } } } return glyph.fImage; } const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) { if (glyph.fWidth) { if (glyph.fPath == NULL) { const_cast<SkGlyph&>(glyph).fPath = SkNEW(SkPath); fScalerContext->getPath(glyph, glyph.fPath); fMemoryUsed += sizeof(SkPath) + glyph.fPath->countPoints() * sizeof(SkPoint); } } return glyph.fPath; } void SkGlyphCache::dump() const { const SkTypeface* face = fScalerContext->getTypeface(); const SkScalerContextRec& rec = fScalerContext->getRec(); SkMatrix matrix; rec.getSingleMatrix(&matrix); matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize)); SkString name; face->getFamilyName(&name); SkString msg; msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d", face->uniqueID(), name.c_str(), face->style(), rec.fTextSize, matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX], matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY], rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast, fGlyphArray.count()); #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS const int sum = SkTMax(fHashHitCount + fHashMissCount, 1); // avoid divide-by-zero msg.appendf(" hash:%2d\n", 100 * fHashHitCount / sum); #endif SkDebugf("%s\n", msg.c_str()); } /////////////////////////////////////////////////////////////////////////////// bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const { const AuxProcRec* rec = fAuxProcList; while (rec) { if (rec->fProc == proc) { if (dataPtr) { *dataPtr = rec->fData; } return true; } rec = rec->fNext; } return false; } void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) { if (proc == NULL) { return; } AuxProcRec* rec = fAuxProcList; while (rec) { if (rec->fProc == proc) { rec->fData = data; return; } rec = rec->fNext; } // not found, create a new rec rec = SkNEW(AuxProcRec); rec->fProc = proc; rec->fData = data; rec->fNext = fAuxProcList; fAuxProcList = rec; } void SkGlyphCache::invokeAndRemoveAuxProcs() { AuxProcRec* rec = fAuxProcList; while (rec) { rec->fProc(rec->fData); AuxProcRec* next = rec->fNext; SkDELETE(rec); rec = next; } } /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// #include "SkThread.h" size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) { static const size_t minLimit = 256 * 1024; if (newLimit < minLimit) { newLimit = minLimit; } SkAutoMutexAcquire ac(fMutex); size_t prevLimit = fCacheSizeLimit; fCacheSizeLimit = newLimit; this->internalPurge(); return prevLimit; } int SkGlyphCache_Globals::setCacheCountLimit(int newCount) { if (newCount < 0) { newCount = 0; } SkAutoMutexAcquire ac(fMutex); int prevCount = fCacheCountLimit; fCacheCountLimit = newCount; this->internalPurge(); return prevCount; } void SkGlyphCache_Globals::purgeAll() { SkAutoMutexAcquire ac(fMutex); this->internalPurge(fTotalMemoryUsed); } /* This guy calls the visitor from within the mutext lock, so the visitor cannot: - take too much time - try to acquire the mutext again - call a fontscaler (which might call into the cache) */ SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface, const SkDescriptor* desc, bool (*proc)(const SkGlyphCache*, void*), void* context) { if (!typeface) { typeface = SkTypeface::GetDefaultTypeface(); } SkASSERT(desc); SkGlyphCache_Globals& globals = getGlobals(); SkAutoMutexAcquire ac(globals.fMutex); SkGlyphCache* cache; bool insideMutex = true; globals.validate(); for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) { if (cache->fDesc->equals(*desc)) { globals.internalDetachCache(cache); goto FOUND_IT; } } /* Release the mutex now, before we create a new entry (which might have side-effects like trying to access the cache/mutex (yikes!) */ ac.release(); // release the mutex now insideMutex = false; // can't use globals anymore // Check if we can create a scaler-context before creating the glyphcache. // If not, we may have exhausted OS/font resources, so try purging the // cache once and try again. { // pass true the first time, to notice if the scalercontext failed, // so we can try the purge. SkScalerContext* ctx = typeface->createScalerContext(desc, true); if (!ctx) { getSharedGlobals().purgeAll(); ctx = typeface->createScalerContext(desc, false); SkASSERT(ctx); } cache = SkNEW_ARGS(SkGlyphCache, (typeface, desc, ctx)); } FOUND_IT: AutoValidate av(cache); if (!proc(cache, context)) { // need to reattach if (insideMutex) { globals.internalAttachCacheToHead(cache); } else { globals.attachCacheToHead(cache); } cache = NULL; } return cache; } void SkGlyphCache::AttachCache(SkGlyphCache* cache) { SkASSERT(cache); SkASSERT(cache->fNext == NULL); getGlobals().attachCacheToHead(cache); } void SkGlyphCache::Dump() { SkGlyphCache_Globals& globals = getGlobals(); SkAutoMutexAcquire ac(globals.fMutex); SkGlyphCache* cache; globals.validate(); SkDebugf("SkGlyphCache strikes:%d memory:%d\n", globals.getCacheCountUsed(), (int)globals.getTotalMemoryUsed()); #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS int hitCount = 0; int missCount = 0; #endif for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) { #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS hitCount += cache->fHashHitCount; missCount += cache->fHashMissCount; #endif cache->dump(); } #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS SkDebugf("Hash hit percent:%2d\n", 100 * hitCount / (hitCount + missCount)); #endif } /////////////////////////////////////////////////////////////////////////////// void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) { SkAutoMutexAcquire ac(fMutex); this->validate(); cache->validate(); this->internalAttachCacheToHead(cache); this->internalPurge(); } SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const { SkGlyphCache* cache = fHead; if (cache) { while (cache->fNext) { cache = cache->fNext; } } return cache; } size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) { this->validate(); size_t bytesNeeded = 0; if (fTotalMemoryUsed > fCacheSizeLimit) { bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit; } bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded); if (bytesNeeded) { // no small purges! bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2); } int countNeeded = 0; if (fCacheCount > fCacheCountLimit) { countNeeded = fCacheCount - fCacheCountLimit; // no small purges! countNeeded = SkMax32(countNeeded, fCacheCount >> 2); } // early exit if (!countNeeded && !bytesNeeded) { return 0; } size_t bytesFreed = 0; int countFreed = 0; // we start at the tail and proceed backwards, as the linklist is in LRU // order, with unimportant entries at the tail. SkGlyphCache* cache = this->internalGetTail(); while (cache != NULL && (bytesFreed < bytesNeeded || countFreed < countNeeded)) { SkGlyphCache* prev = cache->fPrev; bytesFreed += cache->fMemoryUsed; countFreed += 1; this->internalDetachCache(cache); SkDELETE(cache); cache = prev; } this->validate(); #ifdef SPEW_PURGE_STATUS if (countFreed) { SkDebugf("purging %dK from font cache [%d entries]\n", (int)(bytesFreed >> 10), countFreed); } #endif return bytesFreed; } void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) { SkASSERT(NULL == cache->fPrev && NULL == cache->fNext); if (fHead) { fHead->fPrev = cache; cache->fNext = fHead; } fHead = cache; fCacheCount += 1; fTotalMemoryUsed += cache->fMemoryUsed; } void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) { SkASSERT(fCacheCount > 0); fCacheCount -= 1; fTotalMemoryUsed -= cache->fMemoryUsed; if (cache->fPrev) { cache->fPrev->fNext = cache->fNext; } else { fHead = cache->fNext; } if (cache->fNext) { cache->fNext->fPrev = cache->fPrev; } cache->fPrev = cache->fNext = NULL; } /////////////////////////////////////////////////////////////////////////////// #ifdef SK_DEBUG void SkGlyphCache::validate() const { #ifdef SK_DEBUG_GLYPH_CACHE int count = fGlyphArray.count(); for (int i = 0; i < count; i++) { const SkGlyph* glyph = &fGlyphArray[i]; SkASSERT(glyph); if (glyph->fImage) { SkASSERT(fGlyphAlloc.contains(glyph->fImage)); } } #endif } void SkGlyphCache_Globals::validate() const { size_t computedBytes = 0; int computedCount = 0; const SkGlyphCache* head = fHead; while (head != NULL) { computedBytes += head->fMemoryUsed; computedCount += 1; head = head->fNext; } SkASSERT(fTotalMemoryUsed == computedBytes); SkASSERT(fCacheCount == computedCount); } #endif /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// #include "SkTypefaceCache.h" size_t SkGraphics::GetFontCacheLimit() { return getSharedGlobals().getCacheSizeLimit(); } size_t SkGraphics::SetFontCacheLimit(size_t bytes) { return getSharedGlobals().setCacheSizeLimit(bytes); } size_t SkGraphics::GetFontCacheUsed() { return getSharedGlobals().getTotalMemoryUsed(); } int SkGraphics::GetFontCacheCountLimit() { return getSharedGlobals().getCacheCountLimit(); } int SkGraphics::SetFontCacheCountLimit(int count) { return getSharedGlobals().setCacheCountLimit(count); } int SkGraphics::GetFontCacheCountUsed() { return getSharedGlobals().getCacheCountUsed(); } void SkGraphics::PurgeFontCache() { getSharedGlobals().purgeAll(); SkTypefaceCache::PurgeAll(); } size_t SkGraphics::GetTLSFontCacheLimit() { const SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS(); return tls ? tls->getCacheSizeLimit() : 0; } void SkGraphics::SetTLSFontCacheLimit(size_t bytes) { if (0 == bytes) { SkGlyphCache_Globals::DeleteTLS(); } else { SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes); } }