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 19 bool 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 53 SkGlyphCache::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 75 SkGlyphCache::~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 98 uint16_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 110 SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) { 111 return fScalerContext->glyphIDToChar(glyphID); 112 } 113 114 unsigned SkGlyphCache::getGlyphCount() { 115 return fScalerContext->getGlyphCount(); 116 } 117 118 /////////////////////////////////////////////////////////////////////////////// 119 120 const 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 135 const 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 150 const 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 172 const 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 195 const 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 215 const 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 236 SkGlyph* 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 289 const 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 309 const 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 323 bool 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 337 void 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 358 void 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 377 void 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 411 class SkGlyphCache_Globals { 412 public: 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 435 static 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 441 void 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 */ 464 SkGlyphCache* 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 501 FOUND_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 527 void 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 558 size_t SkGlyphCache::GetCacheUsed() { 559 SkGlyphCache_Globals& globals = getGlobals(); 560 SkAutoMutexAcquire ac(globals.fMutex); 561 562 return SkGlyphCache::ComputeMemoryUsed(globals.fHead); 563 } 564 565 bool 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 579 SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) { 580 if (cache) { 581 while (cache->fNext) { 582 cache = cache->fNext; 583 } 584 } 585 return cache; 586 } 587 588 size_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 599 void 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 608 size_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 655 void 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