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