1
2/*
3 * Copyright 2006 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10#include "SkGlyphCache.h"
11#include "SkGraphics.h"
12#include "SkPaint.h"
13#include "SkTemplates.h"
14
15//#define SPEW_PURGE_STATUS
16//#define USE_CACHE_HASH
17//#define RECORD_HASH_EFFICIENCY
18
19bool gSkSuppressFontCachePurgeSpew;
20
21///////////////////////////////////////////////////////////////////////////////
22
23#ifdef RECORD_HASH_EFFICIENCY
24    static uint32_t gHashSuccess;
25    static uint32_t gHashCollision;
26
27    static void RecordHashSuccess() {
28        gHashSuccess += 1;
29    }
30
31    static void RecordHashCollisionIf(bool pred) {
32        if (pred) {
33            gHashCollision += 1;
34
35            uint32_t total = gHashSuccess + gHashCollision;
36            SkDebugf("Font Cache Hash success rate: %d%%\n",
37                     100 * gHashSuccess / total);
38        }
39    }
40#else
41    #define RecordHashSuccess() (void)0
42    #define RecordHashCollisionIf(pred) (void)0
43#endif
44#define RecordHashCollision() RecordHashCollisionIf(true)
45
46///////////////////////////////////////////////////////////////////////////////
47
48#define kMinGlphAlloc       (sizeof(SkGlyph) * 64)
49#define kMinImageAlloc      (24 * 64)   // should be pointsize-dependent
50
51#define METRICS_RESERVE_COUNT  128  // so we don't grow this array a lot
52
53SkGlyphCache::SkGlyphCache(const SkDescriptor* desc)
54        : fGlyphAlloc(kMinGlphAlloc), fImageAlloc(kMinImageAlloc) {
55    fPrev = fNext = NULL;
56
57    fDesc = desc->copy();
58    fScalerContext = SkScalerContext::Create(desc);
59    fScalerContext->getFontMetrics(NULL, &fFontMetricsY);
60
61    // init to 0 so that all of the pointers will be null
62    memset(fGlyphHash, 0, sizeof(fGlyphHash));
63    // init with 0xFF so that the charCode field will be -1, which is invalid
64    memset(fCharToGlyphHash, 0xFF, sizeof(fCharToGlyphHash));
65
66    fMemoryUsed = sizeof(*this) + kMinGlphAlloc + kMinImageAlloc;
67
68    fGlyphArray.setReserve(METRICS_RESERVE_COUNT);
69
70    fMetricsCount = 0;
71    fAdvanceCount = 0;
72    fAuxProcList = NULL;
73}
74
75SkGlyphCache::~SkGlyphCache() {
76    SkGlyph**   gptr = fGlyphArray.begin();
77    SkGlyph**   stop = fGlyphArray.end();
78    while (gptr < stop) {
79        SkPath* path = (*gptr)->fPath;
80        if (path) {
81            SkDELETE(path);
82        }
83        gptr += 1;
84    }
85    SkDescriptor::Free(fDesc);
86    SkDELETE(fScalerContext);
87    this->invokeAndRemoveAuxProcs();
88}
89
90///////////////////////////////////////////////////////////////////////////////
91
92#ifdef SK_DEBUG
93#define VALIDATE()  AutoValidate av(this)
94#else
95#define VALIDATE()
96#endif
97
98uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
99    VALIDATE();
100    uint32_t id = SkGlyph::MakeID(charCode);
101    const CharGlyphRec& rec = fCharToGlyphHash[ID2HashIndex(id)];
102
103    if (rec.fID == id) {
104        return rec.fGlyph->getGlyphID();
105    } else {
106        return fScalerContext->charToGlyphID(charCode);
107    }
108}
109
110SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
111    return fScalerContext->glyphIDToChar(glyphID);
112}
113
114unsigned SkGlyphCache::getGlyphCount() {
115    return fScalerContext->getGlyphCount();
116}
117
118///////////////////////////////////////////////////////////////////////////////
119
120const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
121    VALIDATE();
122    uint32_t id = SkGlyph::MakeID(charCode);
123    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
124
125    if (rec->fID != id) {
126        // this ID is based on the UniChar
127        rec->fID = id;
128        // this ID is based on the glyph index
129        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
130        rec->fGlyph = this->lookupMetrics(id, kJustAdvance_MetricsType);
131    }
132    return *rec->fGlyph;
133}
134
135const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
136    VALIDATE();
137    uint32_t id = SkGlyph::MakeID(glyphID);
138    unsigned index = ID2HashIndex(id);
139    SkGlyph* glyph = fGlyphHash[index];
140
141    if (NULL == glyph || glyph->fID != id) {
142        glyph = this->lookupMetrics(glyphID, kJustAdvance_MetricsType);
143        fGlyphHash[index] = glyph;
144    }
145    return *glyph;
146}
147
148///////////////////////////////////////////////////////////////////////////////
149
150const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
151    VALIDATE();
152    uint32_t id = SkGlyph::MakeID(charCode);
153    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
154
155    if (rec->fID != id) {
156        RecordHashCollisionIf(rec->fGlyph != NULL);
157        // this ID is based on the UniChar
158        rec->fID = id;
159        // this ID is based on the glyph index
160        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
161        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
162    } else {
163        RecordHashSuccess();
164        if (rec->fGlyph->isJustAdvance()) {
165            fScalerContext->getMetrics(rec->fGlyph);
166        }
167    }
168    SkASSERT(rec->fGlyph->isFullMetrics());
169    return *rec->fGlyph;
170}
171
172const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
173                                               SkFixed x, SkFixed y) {
174    VALIDATE();
175    uint32_t id = SkGlyph::MakeID(charCode, x, y);
176    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
177
178    if (rec->fID != id) {
179        RecordHashCollisionIf(rec->fGlyph != NULL);
180        // this ID is based on the UniChar
181        rec->fID = id;
182        // this ID is based on the glyph index
183        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
184        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
185    } else {
186        RecordHashSuccess();
187        if (rec->fGlyph->isJustAdvance()) {
188            fScalerContext->getMetrics(rec->fGlyph);
189        }
190    }
191    SkASSERT(rec->fGlyph->isFullMetrics());
192    return *rec->fGlyph;
193}
194
195const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
196    VALIDATE();
197    uint32_t id = SkGlyph::MakeID(glyphID);
198    unsigned index = ID2HashIndex(id);
199    SkGlyph* glyph = fGlyphHash[index];
200
201    if (NULL == glyph || glyph->fID != id) {
202        RecordHashCollisionIf(glyph != NULL);
203        glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
204        fGlyphHash[index] = glyph;
205    } else {
206        RecordHashSuccess();
207        if (glyph->isJustAdvance()) {
208            fScalerContext->getMetrics(glyph);
209        }
210    }
211    SkASSERT(glyph->isFullMetrics());
212    return *glyph;
213}
214
215const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID,
216                                               SkFixed x, SkFixed y) {
217    VALIDATE();
218    uint32_t id = SkGlyph::MakeID(glyphID, x, y);
219    unsigned index = ID2HashIndex(id);
220    SkGlyph* glyph = fGlyphHash[index];
221
222    if (NULL == glyph || glyph->fID != id) {
223        RecordHashCollisionIf(glyph != NULL);
224        glyph = this->lookupMetrics(id, kFull_MetricsType);
225        fGlyphHash[index] = glyph;
226    } else {
227        RecordHashSuccess();
228        if (glyph->isJustAdvance()) {
229            fScalerContext->getMetrics(glyph);
230        }
231    }
232    SkASSERT(glyph->isFullMetrics());
233    return *glyph;
234}
235
236SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
237    SkGlyph* glyph;
238
239    int     hi = 0;
240    int     count = fGlyphArray.count();
241
242    if (count) {
243        SkGlyph**   gptr = fGlyphArray.begin();
244        int     lo = 0;
245
246        hi = count - 1;
247        while (lo < hi) {
248            int mid = (hi + lo) >> 1;
249            if (gptr[mid]->fID < id) {
250                lo = mid + 1;
251            } else {
252                hi = mid;
253            }
254        }
255        glyph = gptr[hi];
256        if (glyph->fID == id) {
257            if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
258                fScalerContext->getMetrics(glyph);
259            }
260            return glyph;
261        }
262
263        // check if we need to bump hi before falling though to the allocator
264        if (glyph->fID < id) {
265            hi += 1;
266        }
267    }
268
269    // not found, but hi tells us where to inser the new glyph
270    fMemoryUsed += sizeof(SkGlyph);
271
272    glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
273                                        SkChunkAlloc::kThrow_AllocFailType);
274    glyph->init(id);
275    *fGlyphArray.insert(hi) = glyph;
276
277    if (kJustAdvance_MetricsType == mtype) {
278        fScalerContext->getAdvance(glyph);
279        fAdvanceCount += 1;
280    } else {
281        SkASSERT(kFull_MetricsType == mtype);
282        fScalerContext->getMetrics(glyph);
283        fMetricsCount += 1;
284    }
285
286    return glyph;
287}
288
289const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
290    if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
291        if (glyph.fImage == NULL) {
292            size_t  size = glyph.computeImageSize();
293            const_cast<SkGlyph&>(glyph).fImage = fImageAlloc.alloc(size,
294                                        SkChunkAlloc::kReturnNil_AllocFailType);
295            // check that alloc() actually succeeded
296            if (glyph.fImage) {
297                fScalerContext->getImage(glyph);
298                // TODO: the scaler may have changed the maskformat during
299                // getImage (e.g. from AA or LCD to BW) which means we may have
300                // overallocated the buffer. Check if the new computedImageSize
301                // is smaller, and if so, strink the alloc size in fImageAlloc.
302                fMemoryUsed += size;
303            }
304        }
305    }
306    return glyph.fImage;
307}
308
309const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
310    if (glyph.fWidth) {
311        if (glyph.fPath == NULL) {
312            const_cast<SkGlyph&>(glyph).fPath = SkNEW(SkPath);
313            fScalerContext->getPath(glyph, glyph.fPath);
314            fMemoryUsed += sizeof(SkPath) +
315                    glyph.fPath->getPoints(NULL, 0x7FFFFFFF) * sizeof(SkPoint);
316        }
317    }
318    return glyph.fPath;
319}
320
321///////////////////////////////////////////////////////////////////////////////
322
323bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
324    const AuxProcRec* rec = fAuxProcList;
325    while (rec) {
326        if (rec->fProc == proc) {
327            if (dataPtr) {
328                *dataPtr = rec->fData;
329            }
330            return true;
331        }
332        rec = rec->fNext;
333    }
334    return false;
335}
336
337void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) {
338    if (proc == NULL) {
339        return;
340    }
341
342    AuxProcRec* rec = fAuxProcList;
343    while (rec) {
344        if (rec->fProc == proc) {
345            rec->fData = data;
346            return;
347        }
348        rec = rec->fNext;
349    }
350    // not found, create a new rec
351    rec = SkNEW(AuxProcRec);
352    rec->fProc = proc;
353    rec->fData = data;
354    rec->fNext = fAuxProcList;
355    fAuxProcList = rec;
356}
357
358void SkGlyphCache::removeAuxProc(void (*proc)(void*)) {
359    AuxProcRec* rec = fAuxProcList;
360    AuxProcRec* prev = NULL;
361    while (rec) {
362        AuxProcRec* next = rec->fNext;
363        if (rec->fProc == proc) {
364            if (prev) {
365                prev->fNext = next;
366            } else {
367                fAuxProcList = next;
368            }
369            SkDELETE(rec);
370            return;
371        }
372        prev = rec;
373        rec = next;
374    }
375}
376
377void SkGlyphCache::invokeAndRemoveAuxProcs() {
378    AuxProcRec* rec = fAuxProcList;
379    while (rec) {
380        rec->fProc(rec->fData);
381        AuxProcRec* next = rec->fNext;
382        SkDELETE(rec);
383        rec = next;
384    }
385}
386
387///////////////////////////////////////////////////////////////////////////////
388///////////////////////////////////////////////////////////////////////////////
389
390#ifdef USE_CACHE_HASH
391    #define HASH_BITCOUNT   6
392    #define HASH_COUNT      (1 << HASH_BITCOUNT)
393    #define HASH_MASK       (HASH_COUNT - 1)
394
395    static unsigned desc_to_hashindex(const SkDescriptor* desc)
396    {
397        SkASSERT(HASH_MASK < 256);  // since our munging reduces to 8 bits
398
399        uint32_t n = *(const uint32_t*)desc;    //desc->getChecksum();
400        SkASSERT(n == desc->getChecksum());
401
402        // don't trust that the low bits of checksum vary enough, so...
403        n ^= (n >> 24) ^ (n >> 16) ^ (n >> 8) ^ (n >> 30);
404
405        return n & HASH_MASK;
406    }
407#endif
408
409#include "SkThread.h"
410
411class SkGlyphCache_Globals {
412public:
413    SkGlyphCache_Globals() {
414        fHead = NULL;
415        fTotalMemoryUsed = 0;
416#ifdef USE_CACHE_HASH
417        sk_bzero(fHash, sizeof(fHash));
418#endif
419    }
420
421    SkMutex         fMutex;
422    SkGlyphCache*   fHead;
423    size_t          fTotalMemoryUsed;
424#ifdef USE_CACHE_HASH
425    SkGlyphCache*   fHash[HASH_COUNT];
426#endif
427
428#ifdef SK_DEBUG
429    void validate() const;
430#else
431    void validate() const {}
432#endif
433};
434
435static SkGlyphCache_Globals& getGlobals() {
436    // we leak this, so we don't incur any shutdown cost of the destructor
437    static SkGlyphCache_Globals* gGlobals = new SkGlyphCache_Globals;
438    return *gGlobals;
439}
440
441void SkGlyphCache::VisitAllCaches(bool (*proc)(SkGlyphCache*, void*),
442                                  void* context) {
443    SkGlyphCache_Globals& globals = getGlobals();
444    SkAutoMutexAcquire    ac(globals.fMutex);
445    SkGlyphCache*         cache;
446
447    globals.validate();
448
449    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
450        if (proc(cache, context)) {
451            break;
452        }
453    }
454
455    globals.validate();
456}
457
458/*  This guy calls the visitor from within the mutext lock, so the visitor
459    cannot:
460    - take too much time
461    - try to acquire the mutext again
462    - call a fontscaler (which might call into the cache)
463*/
464SkGlyphCache* SkGlyphCache::VisitCache(const SkDescriptor* desc,
465                              bool (*proc)(const SkGlyphCache*, void*),
466                              void* context) {
467    SkASSERT(desc);
468
469    SkGlyphCache_Globals& globals = getGlobals();
470    SkAutoMutexAcquire    ac(globals.fMutex);
471    SkGlyphCache*         cache;
472    bool                  insideMutex = true;
473
474    globals.validate();
475
476#ifdef USE_CACHE_HASH
477    SkGlyphCache** hash = globals.fHash;
478    unsigned index = desc_to_hashindex(desc);
479    cache = hash[index];
480    if (cache && *cache->fDesc == *desc) {
481        cache->detach(&globals.fHead);
482        goto FOUND_IT;
483    }
484#endif
485
486    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
487        if (cache->fDesc->equals(*desc)) {
488            cache->detach(&globals.fHead);
489            goto FOUND_IT;
490        }
491    }
492
493    /* Release the mutex now, before we create a new entry (which might have
494        side-effects like trying to access the cache/mutex (yikes!)
495    */
496    ac.release();           // release the mutex now
497    insideMutex = false;    // can't use globals anymore
498
499    cache = SkNEW_ARGS(SkGlyphCache, (desc));
500
501FOUND_IT:
502
503    AutoValidate av(cache);
504
505    if (proc(cache, context)) {   // stay detached
506        if (insideMutex) {
507            SkASSERT(globals.fTotalMemoryUsed >= cache->fMemoryUsed);
508            globals.fTotalMemoryUsed -= cache->fMemoryUsed;
509#ifdef USE_CACHE_HASH
510            hash[index] = NULL;
511#endif
512        }
513    } else {                        // reattach
514        if (insideMutex) {
515            cache->attachToHead(&globals.fHead);
516#ifdef USE_CACHE_HASH
517            hash[index] = cache;
518#endif
519        } else {
520            AttachCache(cache);
521        }
522        cache = NULL;
523    }
524    return cache;
525}
526
527void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
528    SkASSERT(cache);
529    SkASSERT(cache->fNext == NULL);
530
531    SkGlyphCache_Globals& globals = getGlobals();
532    SkAutoMutexAcquire    ac(globals.fMutex);
533
534    globals.validate();
535    cache->validate();
536
537    // if we have a fixed budget for our cache, do a purge here
538    {
539        size_t allocated = globals.fTotalMemoryUsed + cache->fMemoryUsed;
540        size_t budgeted = SkGraphics::GetFontCacheLimit();
541        if (allocated > budgeted) {
542            (void)InternalFreeCache(&globals, allocated - budgeted);
543        }
544    }
545
546    cache->attachToHead(&globals.fHead);
547    globals.fTotalMemoryUsed += cache->fMemoryUsed;
548
549#ifdef USE_CACHE_HASH
550    unsigned index = desc_to_hashindex(cache->fDesc);
551    SkASSERT(globals.fHash[index] != cache);
552    globals.fHash[index] = cache;
553#endif
554
555    globals.validate();
556}
557
558size_t SkGlyphCache::GetCacheUsed() {
559    SkGlyphCache_Globals& globals = getGlobals();
560    SkAutoMutexAcquire  ac(globals.fMutex);
561
562    return SkGlyphCache::ComputeMemoryUsed(globals.fHead);
563}
564
565bool SkGlyphCache::SetCacheUsed(size_t bytesUsed) {
566    size_t curr = SkGlyphCache::GetCacheUsed();
567
568    if (curr > bytesUsed) {
569        SkGlyphCache_Globals& globals = getGlobals();
570        SkAutoMutexAcquire  ac(globals.fMutex);
571
572        return InternalFreeCache(&globals, curr - bytesUsed) > 0;
573    }
574    return false;
575}
576
577///////////////////////////////////////////////////////////////////////////////
578
579SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
580    if (cache) {
581        while (cache->fNext) {
582            cache = cache->fNext;
583        }
584    }
585    return cache;
586}
587
588size_t SkGlyphCache::ComputeMemoryUsed(const SkGlyphCache* head) {
589    size_t size = 0;
590
591    while (head != NULL) {
592        size += head->fMemoryUsed;
593        head = head->fNext;
594    }
595    return size;
596}
597
598#ifdef SK_DEBUG
599void SkGlyphCache_Globals::validate() const {
600    size_t computed = SkGlyphCache::ComputeMemoryUsed(fHead);
601    if (fTotalMemoryUsed != computed) {
602        printf("total %d, computed %d\n", (int)fTotalMemoryUsed, (int)computed);
603    }
604    SkASSERT(fTotalMemoryUsed == computed);
605}
606#endif
607
608size_t SkGlyphCache::InternalFreeCache(SkGlyphCache_Globals* globals,
609                                       size_t bytesNeeded) {
610    globals->validate();
611
612    size_t  bytesFreed = 0;
613    int     count = 0;
614
615    // don't do any "small" purges
616    size_t minToPurge = globals->fTotalMemoryUsed >> 2;
617    if (bytesNeeded < minToPurge)
618        bytesNeeded = minToPurge;
619
620    SkGlyphCache* cache = FindTail(globals->fHead);
621    while (cache != NULL && bytesFreed < bytesNeeded) {
622        SkGlyphCache* prev = cache->fPrev;
623        bytesFreed += cache->fMemoryUsed;
624
625#ifdef USE_CACHE_HASH
626        unsigned index = desc_to_hashindex(cache->fDesc);
627        if (cache == globals->fHash[index]) {
628            globals->fHash[index] = NULL;
629        }
630#endif
631
632        cache->detach(&globals->fHead);
633        SkDELETE(cache);
634        cache = prev;
635        count += 1;
636    }
637
638    SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
639    globals->fTotalMemoryUsed -= bytesFreed;
640    globals->validate();
641
642#ifdef SPEW_PURGE_STATUS
643    if (count && !gSkSuppressFontCachePurgeSpew) {
644        SkDebugf("purging %dK from font cache [%d entries]\n",
645                 (int)(bytesFreed >> 10), count);
646    }
647#endif
648
649    return bytesFreed;
650}
651
652///////////////////////////////////////////////////////////////////////////////
653#ifdef SK_DEBUG
654
655void SkGlyphCache::validate() const {
656    int count = fGlyphArray.count();
657    for (int i = 0; i < count; i++) {
658        const SkGlyph* glyph = fGlyphArray[i];
659        SkASSERT(glyph);
660        SkASSERT(fGlyphAlloc.contains(glyph));
661        if (glyph->fImage) {
662            SkASSERT(fImageAlloc.contains(glyph->fImage));
663        }
664    }
665}
666
667#endif
668