1 /* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkScaledImageCache.h" 9 #include "SkMipMap.h" 10 #include "SkPixelRef.h" 11 #include "SkRect.h" 12 13 #ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT 14 #define SK_DEFAULT_IMAGE_CACHE_LIMIT (2 * 1024 * 1024) 15 #endif 16 17 18 // Implemented from en.wikipedia.org/wiki/MurmurHash. 19 static uint32_t compute_hash(const uint32_t data[], int count) { 20 uint32_t hash = 0; 21 22 for (int i = 0; i < count; ++i) { 23 uint32_t k = data[i]; 24 k *= 0xcc9e2d51; 25 k = (k << 15) | (k >> 17); 26 k *= 0x1b873593; 27 28 hash ^= k; 29 hash = (hash << 13) | (hash >> 19); 30 hash *= 5; 31 hash += 0xe6546b64; 32 } 33 34 // hash ^= size; 35 hash ^= hash >> 16; 36 hash *= 0x85ebca6b; 37 hash ^= hash >> 13; 38 hash *= 0xc2b2ae35; 39 hash ^= hash >> 16; 40 41 return hash; 42 } 43 44 struct Key { 45 bool init(const SkBitmap& bm, SkScalar scaleX, SkScalar scaleY) { 46 SkPixelRef* pr = bm.pixelRef(); 47 if (!pr) { 48 return false; 49 } 50 51 size_t offset = bm.pixelRefOffset(); 52 size_t rowBytes = bm.rowBytes(); 53 int x = (offset % rowBytes) >> 2; 54 int y = offset / rowBytes; 55 56 fGenID = pr->getGenerationID(); 57 fBounds.set(x, y, x + bm.width(), y + bm.height()); 58 fScaleX = scaleX; 59 fScaleY = scaleY; 60 61 fHash = compute_hash(&fGenID, 7); 62 return true; 63 } 64 65 bool operator<(const Key& other) const { 66 const uint32_t* a = &fGenID; 67 const uint32_t* b = &other.fGenID; 68 for (int i = 0; i < 7; ++i) { 69 if (a[i] < b[i]) { 70 return true; 71 } 72 if (a[i] > b[i]) { 73 return false; 74 } 75 } 76 return false; 77 } 78 79 bool operator==(const Key& other) const { 80 const uint32_t* a = &fHash; 81 const uint32_t* b = &other.fHash; 82 for (int i = 0; i < 8; ++i) { 83 if (a[i] != b[i]) { 84 return false; 85 } 86 } 87 return true; 88 } 89 90 uint32_t fHash; 91 uint32_t fGenID; 92 float fScaleX; 93 float fScaleY; 94 SkIRect fBounds; 95 }; 96 97 struct SkScaledImageCache::Rec { 98 Rec(const Key& key, const SkBitmap& bm) : fKey(key), fBitmap(bm) { 99 fLockCount = 1; 100 fMip = NULL; 101 } 102 103 Rec(const Key& key, const SkMipMap* mip) : fKey(key) { 104 fLockCount = 1; 105 fMip = mip; 106 mip->ref(); 107 } 108 109 ~Rec() { 110 SkSafeUnref(fMip); 111 } 112 113 size_t bytesUsed() const { 114 return fMip ? fMip->getSize() : fBitmap.getSize(); 115 } 116 117 Rec* fNext; 118 Rec* fPrev; 119 120 // this guy wants to be 64bit aligned 121 Key fKey; 122 123 int32_t fLockCount; 124 125 // we use either fBitmap or fMip, but not both 126 SkBitmap fBitmap; 127 const SkMipMap* fMip; 128 }; 129 130 #include "SkTDynamicHash.h" 131 132 namespace { // can't use static functions w/ template parameters 133 const Key& key_from_rec(const SkScaledImageCache::Rec& rec) { 134 return rec.fKey; 135 } 136 137 uint32_t hash_from_key(const Key& key) { 138 return key.fHash; 139 } 140 141 bool eq_rec_key(const SkScaledImageCache::Rec& rec, const Key& key) { 142 return rec.fKey == key; 143 } 144 } 145 146 class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec, 147 Key, key_from_rec, hash_from_key, 148 eq_rec_key> {}; 149 150 /////////////////////////////////////////////////////////////////////////////// 151 152 // experimental hash to speed things up 153 #define USE_HASH 154 155 SkScaledImageCache::SkScaledImageCache(size_t byteLimit) { 156 fHead = NULL; 157 fTail = NULL; 158 #ifdef USE_HASH 159 fHash = new Hash; 160 #else 161 fHash = NULL; 162 #endif 163 fBytesUsed = 0; 164 fByteLimit = byteLimit; 165 fCount = 0; 166 } 167 168 SkScaledImageCache::~SkScaledImageCache() { 169 Rec* rec = fHead; 170 while (rec) { 171 Rec* next = rec->fNext; 172 SkDELETE(rec); 173 rec = next; 174 } 175 delete fHash; 176 } 177 178 SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig, 179 SkScalar scaleX, 180 SkScalar scaleY) { 181 Key key; 182 if (!key.init(orig, scaleX, scaleY)) { 183 return NULL; 184 } 185 186 #ifdef USE_HASH 187 Rec* rec = fHash->find(key); 188 #else 189 Rec* rec = fHead; 190 while (rec != NULL) { 191 if (rec->fKey == key) { 192 break; 193 } 194 rec = rec->fNext; 195 } 196 #endif 197 198 if (rec) { 199 this->moveToHead(rec); // for our LRU 200 rec->fLockCount += 1; 201 } 202 return rec; 203 } 204 205 SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig, 206 SkScalar scaleX, 207 SkScalar scaleY, 208 SkBitmap* scaled) { 209 if (0 == scaleX || 0 == scaleY) { 210 // degenerate, and the key we use for mipmaps 211 return NULL; 212 } 213 214 Rec* rec = this->findAndLock(orig, scaleX, scaleY); 215 if (rec) { 216 SkASSERT(NULL == rec->fMip); 217 SkASSERT(rec->fBitmap.pixelRef()); 218 *scaled = rec->fBitmap; 219 } 220 return (ID*)rec; 221 } 222 223 SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig, 224 SkMipMap const ** mip) { 225 Rec* rec = this->findAndLock(orig, 0, 0); 226 if (rec) { 227 SkASSERT(rec->fMip); 228 SkASSERT(NULL == rec->fBitmap.pixelRef()); 229 *mip = rec->fMip; 230 } 231 return (ID*)rec; 232 } 233 234 SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig, 235 SkScalar scaleX, 236 SkScalar scaleY, 237 const SkBitmap& scaled) { 238 if (0 == scaleX || 0 == scaleY) { 239 // degenerate, and the key we use for mipmaps 240 return NULL; 241 } 242 243 Key key; 244 if (!key.init(orig, scaleX, scaleY)) { 245 return NULL; 246 } 247 248 Rec* rec = SkNEW_ARGS(Rec, (key, scaled)); 249 this->addToHead(rec); 250 SkASSERT(1 == rec->fLockCount); 251 252 #ifdef USE_HASH 253 fHash->add(rec); 254 #endif 255 256 // We may (now) be overbudget, so see if we need to purge something. 257 this->purgeAsNeeded(); 258 return (ID*)rec; 259 } 260 261 SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig, 262 const SkMipMap* mip) { 263 Key key; 264 if (!key.init(orig, 0, 0)) { 265 return NULL; 266 } 267 268 Rec* rec = SkNEW_ARGS(Rec, (key, mip)); 269 this->addToHead(rec); 270 SkASSERT(1 == rec->fLockCount); 271 272 #ifdef USE_HASH 273 fHash->add(rec); 274 #endif 275 276 // We may (now) be overbudget, so see if we need to purge something. 277 this->purgeAsNeeded(); 278 return (ID*)rec; 279 } 280 281 void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) { 282 SkASSERT(id); 283 284 #ifdef SK_DEBUG 285 { 286 bool found = false; 287 Rec* rec = fHead; 288 while (rec != NULL) { 289 if ((ID*)rec == id) { 290 found = true; 291 break; 292 } 293 rec = rec->fNext; 294 } 295 SkASSERT(found); 296 } 297 #endif 298 Rec* rec = (Rec*)id; 299 SkASSERT(rec->fLockCount > 0); 300 rec->fLockCount -= 1; 301 302 // we may have been over-budget, but now have released something, so check 303 // if we should purge. 304 if (0 == rec->fLockCount) { 305 this->purgeAsNeeded(); 306 } 307 } 308 309 void SkScaledImageCache::purgeAsNeeded() { 310 size_t byteLimit = fByteLimit; 311 size_t bytesUsed = fBytesUsed; 312 313 Rec* rec = fTail; 314 while (rec) { 315 if (bytesUsed < byteLimit) { 316 break; 317 } 318 Rec* prev = rec->fPrev; 319 if (0 == rec->fLockCount) { 320 size_t used = rec->bytesUsed(); 321 SkASSERT(used <= bytesUsed); 322 bytesUsed -= used; 323 this->detach(rec); 324 #ifdef USE_HASH 325 fHash->remove(rec->fKey); 326 #endif 327 328 SkDELETE(rec); 329 fCount -= 1; 330 } 331 rec = prev; 332 } 333 fBytesUsed = bytesUsed; 334 } 335 336 size_t SkScaledImageCache::setByteLimit(size_t newLimit) { 337 size_t prevLimit = fByteLimit; 338 fByteLimit = newLimit; 339 if (newLimit < prevLimit) { 340 this->purgeAsNeeded(); 341 } 342 return prevLimit; 343 } 344 345 /////////////////////////////////////////////////////////////////////////////// 346 347 void SkScaledImageCache::detach(Rec* rec) { 348 Rec* prev = rec->fPrev; 349 Rec* next = rec->fNext; 350 351 if (!prev) { 352 SkASSERT(fHead == rec); 353 fHead = next; 354 } else { 355 prev->fNext = next; 356 } 357 358 if (!next) { 359 fTail = prev; 360 } else { 361 next->fPrev = prev; 362 } 363 364 rec->fNext = rec->fPrev = NULL; 365 } 366 367 void SkScaledImageCache::moveToHead(Rec* rec) { 368 if (fHead == rec) { 369 return; 370 } 371 372 SkASSERT(fHead); 373 SkASSERT(fTail); 374 375 this->validate(); 376 377 this->detach(rec); 378 379 fHead->fPrev = rec; 380 rec->fNext = fHead; 381 fHead = rec; 382 383 this->validate(); 384 } 385 386 void SkScaledImageCache::addToHead(Rec* rec) { 387 this->validate(); 388 389 rec->fPrev = NULL; 390 rec->fNext = fHead; 391 if (fHead) { 392 fHead->fPrev = rec; 393 } 394 fHead = rec; 395 if (!fTail) { 396 fTail = rec; 397 } 398 fBytesUsed += rec->bytesUsed(); 399 fCount += 1; 400 401 this->validate(); 402 } 403 404 #ifdef SK_DEBUG 405 void SkScaledImageCache::validate() const { 406 if (NULL == fHead) { 407 SkASSERT(NULL == fTail); 408 SkASSERT(0 == fBytesUsed); 409 return; 410 } 411 412 if (fHead == fTail) { 413 SkASSERT(NULL == fHead->fPrev); 414 SkASSERT(NULL == fHead->fNext); 415 SkASSERT(fHead->bytesUsed() == fBytesUsed); 416 return; 417 } 418 419 SkASSERT(NULL == fHead->fPrev); 420 SkASSERT(NULL != fHead->fNext); 421 SkASSERT(NULL == fTail->fNext); 422 SkASSERT(NULL != fTail->fPrev); 423 424 size_t used = 0; 425 int count = 0; 426 const Rec* rec = fHead; 427 while (rec) { 428 count += 1; 429 used += rec->bytesUsed(); 430 SkASSERT(used <= fBytesUsed); 431 rec = rec->fNext; 432 } 433 SkASSERT(fCount == count); 434 435 rec = fTail; 436 while (rec) { 437 SkASSERT(count > 0); 438 count -= 1; 439 SkASSERT(used >= rec->bytesUsed()); 440 used -= rec->bytesUsed(); 441 rec = rec->fPrev; 442 } 443 444 SkASSERT(0 == count); 445 SkASSERT(0 == used); 446 } 447 #endif 448 449 /////////////////////////////////////////////////////////////////////////////// 450 451 #include "SkThread.h" 452 453 SK_DECLARE_STATIC_MUTEX(gMutex); 454 455 static SkScaledImageCache* get_cache() { 456 static SkScaledImageCache* gCache; 457 if (!gCache) { 458 gCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT)); 459 } 460 return gCache; 461 } 462 463 SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(const SkBitmap& orig, 464 SkScalar scaleX, 465 SkScalar scaleY, 466 SkBitmap* scaled) { 467 SkAutoMutexAcquire am(gMutex); 468 return get_cache()->findAndLock(orig, scaleX, scaleY, scaled); 469 } 470 471 SkScaledImageCache::ID* SkScaledImageCache::FindAndLockMip(const SkBitmap& orig, 472 SkMipMap const ** mip) { 473 SkAutoMutexAcquire am(gMutex); 474 return get_cache()->findAndLockMip(orig, mip); 475 } 476 477 SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(const SkBitmap& orig, 478 SkScalar scaleX, 479 SkScalar scaleY, 480 const SkBitmap& scaled) { 481 SkAutoMutexAcquire am(gMutex); 482 return get_cache()->addAndLock(orig, scaleX, scaleY, scaled); 483 } 484 485 SkScaledImageCache::ID* SkScaledImageCache::AddAndLockMip(const SkBitmap& orig, 486 const SkMipMap* mip) { 487 SkAutoMutexAcquire am(gMutex); 488 return get_cache()->addAndLockMip(orig, mip); 489 } 490 491 void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) { 492 SkAutoMutexAcquire am(gMutex); 493 return get_cache()->unlock(id); 494 } 495 496 size_t SkScaledImageCache::GetBytesUsed() { 497 SkAutoMutexAcquire am(gMutex); 498 return get_cache()->getBytesUsed(); 499 } 500 501 size_t SkScaledImageCache::GetByteLimit() { 502 SkAutoMutexAcquire am(gMutex); 503 return get_cache()->getByteLimit(); 504 } 505 506 size_t SkScaledImageCache::SetByteLimit(size_t newLimit) { 507 SkAutoMutexAcquire am(gMutex); 508 return get_cache()->setByteLimit(newLimit); 509 } 510 511 /////////////////////////////////////////////////////////////////////////////// 512 513 #include "SkGraphics.h" 514 515 size_t SkGraphics::GetImageCacheBytesUsed() { 516 return SkScaledImageCache::GetBytesUsed(); 517 } 518 519 size_t SkGraphics::GetImageCacheByteLimit() { 520 return SkScaledImageCache::GetByteLimit(); 521 } 522 523 size_t SkGraphics::SetImageCacheByteLimit(size_t newLimit) { 524 return SkScaledImageCache::SetByteLimit(newLimit); 525 } 526