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