SkPictureFlat.h revision eab16dea1ce249dc8e4dc635cd76b6b1b7d0cc98
1 2/* 3 * Copyright 2011 Google Inc. 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#ifndef SkPictureFlat_DEFINED 9#define SkPictureFlat_DEFINED 10 11//#define SK_DEBUG_SIZE 12 13#include "SkChunkAlloc.h" 14#include "SkBitmap.h" 15#include "SkBitmapHeap.h" 16#include "SkOrderedReadBuffer.h" 17#include "SkOrderedWriteBuffer.h" 18#include "SkPicture.h" 19#include "SkPtrRecorder.h" 20#include "SkMatrix.h" 21#include "SkPaint.h" 22#include "SkPath.h" 23#include "SkRegion.h" 24#include "SkTRefArray.h" 25#include "SkTSearch.h" 26 27enum DrawType { 28 UNUSED, 29 CLIP_PATH, 30 CLIP_REGION, 31 CLIP_RECT, 32 CONCAT, 33 DRAW_BITMAP, 34 DRAW_BITMAP_MATRIX, 35 DRAW_BITMAP_NINE, 36 DRAW_BITMAP_RECT_TO_RECT, 37 DRAW_CLEAR, 38 DRAW_DATA, 39 DRAW_PAINT, 40 DRAW_PATH, 41 DRAW_PICTURE, 42 DRAW_POINTS, 43 DRAW_POS_TEXT, 44 DRAW_POS_TEXT_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT 45 DRAW_POS_TEXT_H, 46 DRAW_POS_TEXT_H_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT_H 47 DRAW_RECT, 48 DRAW_SPRITE, 49 DRAW_TEXT, 50 DRAW_TEXT_ON_PATH, 51 DRAW_TEXT_TOP_BOTTOM, // fast variant of DRAW_TEXT 52 DRAW_VERTICES, 53 RESTORE, 54 ROTATE, 55 SAVE, 56 SAVE_LAYER, 57 SCALE, 58 SET_MATRIX, 59 SKEW, 60 TRANSLATE, 61 62 LAST_DRAWTYPE_ENUM = TRANSLATE 63}; 64 65enum DrawVertexFlags { 66 DRAW_VERTICES_HAS_TEXS = 0x01, 67 DRAW_VERTICES_HAS_COLORS = 0x02, 68 DRAW_VERTICES_HAS_INDICES = 0x04 69}; 70 71/////////////////////////////////////////////////////////////////////////////// 72// clipparams are packed in 5 bits 73// doAA:1 | regionOp:4 74 75static inline uint32_t ClipParams_pack(SkRegion::Op op, bool doAA) { 76 unsigned doAABit = doAA ? 1 : 0; 77 return (doAABit << 4) | op; 78} 79 80static inline SkRegion::Op ClipParams_unpackRegionOp(uint32_t packed) { 81 return (SkRegion::Op)(packed & 0xF); 82} 83 84static inline bool ClipParams_unpackDoAA(uint32_t packed) { 85 return SkToBool((packed >> 4) & 1); 86} 87 88/////////////////////////////////////////////////////////////////////////////// 89 90class SkTypefacePlayback { 91public: 92 SkTypefacePlayback(); 93 virtual ~SkTypefacePlayback(); 94 95 int count() const { return fCount; } 96 97 void reset(const SkRefCntSet*); 98 99 void setCount(int count); 100 SkRefCnt* set(int index, SkRefCnt*); 101 102 void setupBuffer(SkOrderedReadBuffer& buffer) const { 103 buffer.setTypefaceArray((SkTypeface**)fArray, fCount); 104 } 105 106protected: 107 int fCount; 108 SkRefCnt** fArray; 109}; 110 111class SkFactoryPlayback { 112public: 113 SkFactoryPlayback(int count) : fCount(count) { 114 fArray = SkNEW_ARRAY(SkFlattenable::Factory, count); 115 } 116 117 ~SkFactoryPlayback() { 118 SkDELETE_ARRAY(fArray); 119 } 120 121 SkFlattenable::Factory* base() const { return fArray; } 122 123 void setupBuffer(SkOrderedReadBuffer& buffer) const { 124 buffer.setFactoryPlayback(fArray, fCount); 125 } 126 127private: 128 int fCount; 129 SkFlattenable::Factory* fArray; 130}; 131 132/////////////////////////////////////////////////////////////////////////////// 133// 134// 135// The following templated classes provide an efficient way to store and compare 136// objects that have been flattened (i.e. serialized in an ordered binary 137// format). 138// 139// SkFlatData: is a simple indexable container for the flattened data 140// which is agnostic to the type of data is is indexing. It is 141// also responsible for flattening/unflattening objects but 142// details of that operation are hidden in the provided procs 143// SkFlatDictionary: is an abstract templated dictionary that maintains a 144// searchable set of SkFlataData objects of type T. 145// SkFlatController: is an interface provided to SkFlatDictionary which handles 146// allocation and unallocation in some cases. It also holds 147// ref count recorders and the like. 148// 149// NOTE: any class that wishes to be used in conjunction with SkFlatDictionary 150// must subclass the dictionary and provide the necessary flattening procs. 151// The end of this header contains dictionary subclasses for some common classes 152// like SkBitmap, SkMatrix, SkPaint, and SkRegion. SkFlatController must also 153// be implemented, or SkChunkFlatController can be used to use an 154// SkChunkAllocator and never do replacements. 155// 156// 157/////////////////////////////////////////////////////////////////////////////// 158 159class SkFlatData; 160 161class SkFlatController : public SkRefCnt { 162public: 163 SK_DECLARE_INST_COUNT(SkFlatController) 164 165 SkFlatController(); 166 virtual ~SkFlatController(); 167 /** 168 * Provide a new block of memory for the SkFlatDictionary to use. 169 */ 170 virtual void* allocThrow(size_t bytes) = 0; 171 172 /** 173 * Unallocate a previously allocated block, returned by allocThrow. 174 * Implementation should at least perform an unallocation if passed the last 175 * pointer returned by allocThrow. If findAndReplace() is intended to be 176 * used, unalloc should also be able to unallocate the SkFlatData that is 177 * provided. 178 */ 179 virtual void unalloc(void* ptr) = 0; 180 181 /** 182 * Used during creation and unflattening of SkFlatData objects. If the 183 * objects being flattened contain bitmaps they are stored in this heap 184 * and the flattenable stores the index to the bitmap on the heap. 185 * This should be set by the protected setBitmapHeap. 186 */ 187 SkBitmapHeap* getBitmapHeap() { return fBitmapHeap; } 188 189 /** 190 * Used during creation of SkFlatData objects. If a typeface recorder is 191 * required to flatten the objects being flattened (i.e. for SkPaints), this 192 * should be set by the protected setTypefaceSet. 193 */ 194 SkRefCntSet* getTypefaceSet() { return fTypefaceSet; } 195 196 /** 197 * Used during unflattening of the SkFlatData objects in the 198 * SkFlatDictionary. Needs to be set by the protected setTypefacePlayback 199 * and needs to be reset to the SkRefCntSet passed to setTypefaceSet. 200 */ 201 SkTypefacePlayback* getTypefacePlayback() { return fTypefacePlayback; } 202 203 /** 204 * Optional factory recorder used during creation of SkFlatData objects. Set 205 * using the protected method setNamedFactorySet. 206 */ 207 SkNamedFactorySet* getNamedFactorySet() { return fFactorySet; } 208 209 /** 210 * Flags to use during creation of SkFlatData objects. Defaults to zero. 211 */ 212 uint32_t getWriteBufferFlags() { return fWriteBufferFlags; } 213 214protected: 215 /** 216 * Set an SkBitmapHeap to be used to store/read SkBitmaps. Ref counted. 217 */ 218 void setBitmapHeap(SkBitmapHeap*); 219 220 /** 221 * Set an SkRefCntSet to be used to store SkTypefaces during flattening. Ref 222 * counted. 223 */ 224 void setTypefaceSet(SkRefCntSet*); 225 226 /** 227 * Set an SkTypefacePlayback to be used to find references to SkTypefaces 228 * during unflattening. Should be reset to the set provided to 229 * setTypefaceSet. 230 */ 231 void setTypefacePlayback(SkTypefacePlayback*); 232 233 /** 234 * Set an SkNamedFactorySet to be used to store Factorys and their 235 * corresponding names during flattening. Ref counted. Returns the same 236 * set as a convenience. 237 */ 238 SkNamedFactorySet* setNamedFactorySet(SkNamedFactorySet*); 239 240 /** 241 * Set the flags to be used during flattening. 242 */ 243 void setWriteBufferFlags(uint32_t flags) { fWriteBufferFlags = flags; } 244 245private: 246 SkBitmapHeap* fBitmapHeap; 247 SkRefCntSet* fTypefaceSet; 248 SkTypefacePlayback* fTypefacePlayback; 249 SkNamedFactorySet* fFactorySet; 250 uint32_t fWriteBufferFlags; 251 252 typedef SkRefCnt INHERITED; 253}; 254 255class SkFlatData { 256public: 257 /** 258 * Compare two SkFlatData ptrs, returning -1, 0, 1 to allow them to be 259 * sorted. 260 * 261 * Note: this assumes that a and b have different sentinel values, either 262 * InCache or AsCandidate, otherwise the loop will go beyond the end of 263 * the buffers. 264 * 265 * dataToCompare() returns 2 fields before the flattened data: 266 * - checksum 267 * - size 268 * This ensures that if we see two blocks of different length, we will 269 * notice that right away, and not read any further. It also ensures that 270 * we see the checksum right away, so that most of the time it is enough 271 * to short-circuit our comparison. 272 */ 273 static int Compare(const SkFlatData* a, const SkFlatData* b) { 274 const uint32_t* stop = a->dataStop(); 275 const uint32_t* a_ptr = a->dataToCompare() - 1; 276 const uint32_t* b_ptr = b->dataToCompare() - 1; 277 // We use -1 above, so we can pre-increment our pointers in the loop 278 while (*++a_ptr == *++b_ptr) {} 279 280 if (a_ptr == stop) { // sentinel 281 SkASSERT(b->dataStop() == b_ptr); 282 return 0; 283 } 284 SkASSERT(a_ptr < a->dataStop()); 285 SkASSERT(b_ptr < b->dataStop()); 286 return (*a_ptr < *b_ptr) ? -1 : 1; 287 } 288 289 int index() const { return fIndex; } 290 const void* data() const { return (const char*)this + sizeof(*this); } 291 void* data() { return (char*)this + sizeof(*this); } 292 // Our data is always 32bit aligned, so we can offer this accessor 293 uint32_t* data32() { return (uint32_t*)this->data(); } 294 // Returns the size of the flattened data. 295 size_t flatSize() const { return fFlatSize; } 296 297 void setSentinelInCache() { 298 this->setSentinel(kInCache_Sentinel); 299 } 300 void setSentinelAsCandidate() { 301 this->setSentinel(kCandidate_Sentinel); 302 } 303 304 uint32_t checksum() const { return fChecksum; } 305 306#ifdef SK_DEBUG_SIZE 307 // returns the logical size of our data. Does not return any sentinel or 308 // padding we might have. 309 size_t size() const { 310 return sizeof(SkFlatData) + fFlatSize; 311 } 312#endif 313 314 static SkFlatData* Create(SkFlatController* controller, const void* obj, int index, 315 void (*flattenProc)(SkOrderedWriteBuffer&, const void*)); 316 317 void unflatten(void* result, 318 void (*unflattenProc)(SkOrderedReadBuffer&, void*), 319 SkBitmapHeap* bitmapHeap = NULL, 320 SkTypefacePlayback* facePlayback = NULL) const; 321 322 // When we purge an entry, we want to reuse an old index for the new entry, 323 // so we expose this setter. 324 void setIndex(int index) { fIndex = index; } 325 326 // for unittesting 327 friend bool operator==(const SkFlatData& a, const SkFlatData& b) { 328 size_t N = (const char*)a.dataStop() - (const char*)a.dataToCompare(); 329 return !memcmp(a.dataToCompare(), b.dataToCompare(), N); 330 } 331 332private: 333 int fIndex; 334 335 // From here down is the data we look at in the search/sort. We always begin 336 // with the checksum and then length. 337 uint32_t fChecksum; 338 int32_t fFlatSize; // size of flattened data 339 // uint32_t flattenedData[] 340 // uint32_t sentinelValue 341 342 const uint32_t* dataToCompare() const { 343 return (const uint32_t*)&fChecksum; 344 } 345 const uint32_t* dataStop() const { 346 SkASSERT(SkIsAlign4(fFlatSize)); 347 return (const uint32_t*)((const char*)this->data() + fFlatSize); 348 } 349 350 enum { 351 kInCache_Sentinel = 0, 352 kCandidate_Sentinel = ~0U, 353 }; 354 void setSentinel(uint32_t value) { 355 SkASSERT(SkIsAlign4(fFlatSize)); 356 this->data32()[fFlatSize >> 2] = value; 357 } 358}; 359 360template <class T> 361class SkFlatDictionary { 362public: 363 SkFlatDictionary(SkFlatController* controller) 364 : fController(controller) { 365 fFlattenProc = NULL; 366 fUnflattenProc = NULL; 367 SkASSERT(controller); 368 fController->ref(); 369 // set to 1 since returning a zero from find() indicates failure 370 fNextIndex = 1; 371 sk_bzero(fHash, sizeof(fHash)); 372 } 373 374 virtual ~SkFlatDictionary() { 375 fController->unref(); 376 } 377 378 int count() const { return fData.count(); } 379 380 const SkFlatData* operator[](int index) const { 381 SkASSERT(index >= 0 && index < fData.count()); 382 return fData[index]; 383 } 384 385 /** 386 * Clears the dictionary of all entries. However, it does NOT free the 387 * memory that was allocated for each entry. 388 */ 389 void reset() { 390 fData.reset(); 391 fNextIndex = 1; 392 sk_bzero(fHash, sizeof(fHash)); 393 } 394 395 /** 396 * Similar to find. Allows the caller to specify an SkFlatData to replace in 397 * the case of an add. Also tells the caller whether a new SkFlatData was 398 * added and whether the old one was replaced. The parameters added and 399 * replaced are required to be non-NULL. Rather than returning the index of 400 * the entry in the dictionary, it returns the actual SkFlatData. 401 */ 402 const SkFlatData* findAndReplace(const T& element, 403 const SkFlatData* toReplace, bool* added, 404 bool* replaced) { 405 SkASSERT(added != NULL && replaced != NULL); 406 int oldCount = fData.count(); 407 const SkFlatData* flat = this->findAndReturnFlat(element); 408 *added = fData.count() == oldCount + 1; 409 *replaced = false; 410 if (*added && toReplace != NULL) { 411 // First, find the index of the one to replace 412 int indexToReplace = fData.find(toReplace); 413 if (indexToReplace >= 0) { 414 // findAndReturnFlat set the index to fNextIndex and increased 415 // fNextIndex by one. Reuse the index from the one being 416 // replaced and reset fNextIndex to the proper value. 417 const_cast<SkFlatData*>(flat)->setIndex(toReplace->index()); 418 fNextIndex--; 419 // Remove from the array. 420 fData.remove(indexToReplace); 421 // Remove from the hash table. 422 int oldHash = ChecksumToHashIndex(toReplace->checksum()); 423 if (fHash[oldHash] == toReplace) { 424 fHash[oldHash] = NULL; 425 } 426 // Delete the actual object. 427 fController->unalloc((void*)toReplace); 428 *replaced = true; 429 } 430 } 431 return flat; 432 } 433 434 /** 435 * Given an element of type T return its 1-based index in the dictionary. If 436 * the element wasn't previously in the dictionary it is automatically 437 * added. 438 * 439 * To make the Compare function fast, we write a sentinel value at the end 440 * of each block. The blocks in our fData[] all have a 0 sentinel. The 441 * newly created block we're comparing against has a -1 in the sentinel. 442 * 443 * This trick allows Compare to always loop until failure. If it fails on 444 * the sentinal value, we know the blocks are equal. 445 */ 446 int find(const T& element) { 447 return this->findAndReturnFlat(element)->index(); 448 } 449 450 /** 451 * Given a pointer to an array of type T we allocate the array and fill it 452 * with the unflattened dictionary contents. The return value is the size of 453 * the allocated array. 454 */ 455 int unflattenDictionary(T*& array) const { 456 int elementCount = fData.count(); 457 if (elementCount > 0) { 458 array = SkNEW_ARRAY(T, elementCount); 459 this->unflattenIntoArray(array); 460 } 461 return elementCount; 462 } 463 464 /** 465 * Unflatten the objects and return them in SkTRefArray, or return NULL 466 * if there no objects (instead of an empty array). 467 */ 468 SkTRefArray<T>* unflattenToArray() const { 469 int count = fData.count(); 470 SkTRefArray<T>* array = NULL; 471 if (count > 0) { 472 array = SkTRefArray<T>::Create(count); 473 this->unflattenIntoArray(&array->writableAt(0)); 474 } 475 return array; 476 } 477 478protected: 479 void (*fFlattenProc)(SkOrderedWriteBuffer&, const void*); 480 void (*fUnflattenProc)(SkOrderedReadBuffer&, void*); 481 482private: 483 void unflattenIntoArray(T* array) const { 484 const int count = fData.count(); 485 const SkFlatData** iter = fData.begin(); 486 for (int i = 0; i < count; ++i) { 487 const SkFlatData* element = iter[i]; 488 int index = element->index() - 1; 489 SkASSERT((unsigned)index < (unsigned)count); 490 element->unflatten(&array[index], fUnflattenProc, 491 fController->getBitmapHeap(), 492 fController->getTypefacePlayback()); 493 } 494 } 495 496 497 SkFlatController * const fController; 498 int fNextIndex; 499 SkTDArray<const SkFlatData*> fData; 500 501 const SkFlatData* findAndReturnFlat(const T& element) { 502 SkFlatData* flat = SkFlatData::Create(fController, &element, fNextIndex, fFlattenProc); 503 504 int hashIndex = ChecksumToHashIndex(flat->checksum()); 505 const SkFlatData* candidate = fHash[hashIndex]; 506 if (candidate && !SkFlatData::Compare(flat, candidate)) { 507 fController->unalloc(flat); 508 return candidate; 509 } 510 511 int index = SkTSearch<SkFlatData>((const SkFlatData**) fData.begin(), 512 fData.count(), flat, sizeof(flat), 513 &SkFlatData::Compare); 514 if (index >= 0) { 515 fController->unalloc(flat); 516 fHash[hashIndex] = fData[index]; 517 return fData[index]; 518 } 519 520 index = ~index; 521 *fData.insert(index) = flat; 522 SkASSERT(fData.count() == fNextIndex); 523 fNextIndex++; 524 flat->setSentinelInCache(); 525 fHash[hashIndex] = flat; 526 return flat; 527 } 528 529 530 enum { 531 // Determined by trying diff values on picture-recording benchmarks 532 // (e.g. PictureRecordBench.cpp), choosing the smallest value that 533 // showed a big improvement. Even better would be to benchmark diff 534 // values on recording representative web-pages or other "real" content. 535 HASH_BITS = 7, 536 HASH_MASK = (1 << HASH_BITS) - 1, 537 HASH_COUNT = 1 << HASH_BITS 538 }; 539 const SkFlatData* fHash[HASH_COUNT]; 540 541 static int ChecksumToHashIndex(uint32_t checksum) { 542 int n = checksum; 543 if (HASH_BITS < 32) { 544 n ^= n >> 16; 545 } 546 if (HASH_BITS < 16) { 547 n ^= n >> 8; 548 } 549 if (HASH_BITS < 8) { 550 n ^= n >> 4; 551 } 552 return n & HASH_MASK; 553 } 554}; 555 556/////////////////////////////////////////////////////////////////////////////// 557// Some common dictionaries are defined here for both reference and convenience 558/////////////////////////////////////////////////////////////////////////////// 559 560template <class T> 561static void SkFlattenObjectProc(SkOrderedWriteBuffer& buffer, const void* obj) { 562 ((T*)obj)->flatten(buffer); 563} 564 565template <class T> 566static void SkUnflattenObjectProc(SkOrderedReadBuffer& buffer, void* obj) { 567 ((T*)obj)->unflatten(buffer); 568} 569 570class SkChunkFlatController : public SkFlatController { 571public: 572 SkChunkFlatController(size_t minSize) 573 : fHeap(minSize) 574 , fTypefaceSet(SkNEW(SkRefCntSet)) { 575 this->setTypefaceSet(fTypefaceSet); 576 this->setTypefacePlayback(&fTypefacePlayback); 577 } 578 579 ~SkChunkFlatController() { 580 fTypefaceSet->unref(); 581 } 582 583 virtual void* allocThrow(size_t bytes) SK_OVERRIDE { 584 return fHeap.allocThrow(bytes); 585 } 586 587 virtual void unalloc(void* ptr) SK_OVERRIDE { 588 (void) fHeap.unalloc(ptr); 589 } 590 591 void setupPlaybacks() const { 592 fTypefacePlayback.reset(fTypefaceSet); 593 } 594 595 void setBitmapStorage(SkBitmapHeap* heap) { 596 this->setBitmapHeap(heap); 597 } 598 599private: 600 SkChunkAlloc fHeap; 601 SkRefCntSet* fTypefaceSet; 602 mutable SkTypefacePlayback fTypefacePlayback; 603}; 604 605class SkBitmapDictionary : public SkFlatDictionary<SkBitmap> { 606public: 607 SkBitmapDictionary(SkFlatController* controller) 608 : SkFlatDictionary<SkBitmap>(controller) { 609 fFlattenProc = &SkFlattenObjectProc<SkBitmap>; 610 fUnflattenProc = &SkUnflattenObjectProc<SkBitmap>; 611 } 612}; 613 614class SkMatrixDictionary : public SkFlatDictionary<SkMatrix> { 615 public: 616 SkMatrixDictionary(SkFlatController* controller) 617 : SkFlatDictionary<SkMatrix>(controller) { 618 fFlattenProc = &flattenMatrix; 619 fUnflattenProc = &unflattenMatrix; 620 } 621 622 static void flattenMatrix(SkOrderedWriteBuffer& buffer, const void* obj) { 623 buffer.getWriter32()->writeMatrix(*(SkMatrix*)obj); 624 } 625 626 static void unflattenMatrix(SkOrderedReadBuffer& buffer, void* obj) { 627 buffer.getReader32()->readMatrix((SkMatrix*)obj); 628 } 629}; 630 631class SkPaintDictionary : public SkFlatDictionary<SkPaint> { 632 public: 633 SkPaintDictionary(SkFlatController* controller) 634 : SkFlatDictionary<SkPaint>(controller) { 635 fFlattenProc = &SkFlattenObjectProc<SkPaint>; 636 fUnflattenProc = &SkUnflattenObjectProc<SkPaint>; 637 } 638}; 639 640class SkRegionDictionary : public SkFlatDictionary<SkRegion> { 641 public: 642 SkRegionDictionary(SkFlatController* controller) 643 : SkFlatDictionary<SkRegion>(controller) { 644 fFlattenProc = &flattenRegion; 645 fUnflattenProc = &unflattenRegion; 646 } 647 648 static void flattenRegion(SkOrderedWriteBuffer& buffer, const void* obj) { 649 buffer.getWriter32()->writeRegion(*(SkRegion*)obj); 650 } 651 652 static void unflattenRegion(SkOrderedReadBuffer& buffer, void* obj) { 653 buffer.getReader32()->readRegion((SkRegion*)obj); 654 } 655}; 656 657#endif 658