1 2 /* 3 * Copyright 2012 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 9 #ifndef SkPathRef_DEFINED 10 #define SkPathRef_DEFINED 11 12 #include "SkRefCnt.h" 13 #include <stddef.h> // ptrdiff_t 14 15 /** 16 * Holds the path verbs and points. It is versioned by a generation ID. None of its public methods 17 * modify the contents. To modify or append to the verbs/points wrap the SkPathRef in an 18 * SkPathRef::Editor object. Installing the editor resets the generation ID. It also performs 19 * copy-on-write if the SkPathRef is shared by multipls SkPaths. The caller passes the Editor's 20 * constructor a SkAutoTUnref, which may be updated to point to a new SkPathRef after the editor's 21 * constructor returns. 22 * 23 * The points and verbs are stored in a single allocation. The points are at the begining of the 24 * allocation while the verbs are stored at end of the allocation, in reverse order. Thus the points 25 * and verbs both grow into the middle of the allocation until the meet. To access verb i in the 26 * verb array use ref.verbs()[~i] (because verbs() returns a pointer just beyond the first 27 * logical verb or the last verb in memory). 28 */ 29 30 class SkPathRef; 31 32 class SkPathRef : public ::SkRefCnt { 33 public: 34 SK_DECLARE_INST_COUNT(SkPathRef); 35 36 class Editor { 37 public: 38 Editor(SkAutoTUnref<SkPathRef>* pathRef, 39 int incReserveVerbs = 0, 40 int incReservePoints = 0) 41 { 42 if ((*pathRef)->unique()) { 43 (*pathRef)->incReserve(incReserveVerbs, incReservePoints); 44 } else { 45 SkPathRef* copy = SkNEW(SkPathRef); 46 copy->copy(**pathRef, incReserveVerbs, incReservePoints); 47 pathRef->reset(copy); 48 } 49 fPathRef = *pathRef; 50 fPathRef->fGenerationID = 0; 51 SkDEBUGCODE(sk_atomic_inc(&fPathRef->fEditorsAttached);) 52 } 53 54 ~Editor() { SkDEBUGCODE(sk_atomic_dec(&fPathRef->fEditorsAttached);) } 55 56 /** 57 * Returns the array of points. 58 */ 59 SkPoint* points() { return fPathRef->fPoints; } 60 61 /** 62 * Gets the ith point. Shortcut for this->points() + i 63 */ 64 SkPoint* atPoint(int i) { 65 SkASSERT((unsigned) i < (unsigned) fPathRef->fPointCnt); 66 return this->points() + i; 67 }; 68 69 /** 70 * Adds the verb and allocates space for the number of points indicated by the verb. The 71 * return value is a pointer to where the points for the verb should be written. 72 */ 73 SkPoint* growForVerb(SkPath::Verb verb) { 74 fPathRef->validate(); 75 return fPathRef->growForVerb(verb); 76 } 77 78 SkPoint* growForConic(SkScalar w) { 79 fPathRef->validate(); 80 SkPoint* pts = fPathRef->growForVerb(SkPath::kConic_Verb); 81 *fPathRef->fConicWeights.append() = w; 82 return pts; 83 } 84 85 /** 86 * Allocates space for additional verbs and points and returns pointers to the new verbs and 87 * points. verbs will point one beyond the first new verb (index it using [~<i>]). pts points 88 * at the first new point (indexed normally [<i>]). 89 */ 90 void grow(int newVerbs, int newPts, uint8_t** verbs, SkPoint** pts) { 91 SkASSERT(NULL != verbs); 92 SkASSERT(NULL != pts); 93 fPathRef->validate(); 94 int oldVerbCnt = fPathRef->fVerbCnt; 95 int oldPointCnt = fPathRef->fPointCnt; 96 SkASSERT(verbs && pts); 97 fPathRef->grow(newVerbs, newPts); 98 *verbs = fPathRef->fVerbs - oldVerbCnt; 99 *pts = fPathRef->fPoints + oldPointCnt; 100 fPathRef->validate(); 101 } 102 103 /** 104 * Resets the path ref to a new verb and point count. The new verbs and points are 105 * uninitialized. 106 */ 107 void resetToSize(int newVerbCnt, int newPointCnt, int newConicCount) { 108 fPathRef->resetToSize(newVerbCnt, newPointCnt, newConicCount); 109 } 110 /** 111 * Gets the path ref that is wrapped in the Editor. 112 */ 113 SkPathRef* pathRef() { return fPathRef; } 114 115 private: 116 SkPathRef* fPathRef; 117 }; 118 119 public: 120 /** 121 * Gets a path ref with no verbs or points. 122 */ 123 static SkPathRef* CreateEmpty() { 124 static SkPathRef* gEmptyPathRef; 125 if (!gEmptyPathRef) { 126 gEmptyPathRef = SkNEW(SkPathRef); // leak! 127 } 128 return SkRef(gEmptyPathRef); 129 } 130 131 /** 132 * Transforms a path ref by a matrix, allocating a new one only if necessary. 133 */ 134 static void CreateTransformedCopy(SkAutoTUnref<SkPathRef>* dst, 135 const SkPathRef& src, 136 const SkMatrix& matrix) { 137 src.validate(); 138 if (matrix.isIdentity()) { 139 if (*dst != &src) { 140 src.ref(); 141 dst->reset(const_cast<SkPathRef*>(&src)); 142 (*dst)->validate(); 143 } 144 return; 145 } 146 bool dstUnique = (*dst)->unique(); 147 if (&src == *dst && dstUnique) { 148 matrix.mapPoints((*dst)->fPoints, (*dst)->fPointCnt); 149 return; 150 } else if (!dstUnique) { 151 dst->reset(SkNEW(SkPathRef)); 152 } 153 (*dst)->resetToSize(src.fVerbCnt, src.fPointCnt, src.fConicWeights.count()); 154 memcpy((*dst)->verbsMemWritable(), src.verbsMemBegin(), src.fVerbCnt * sizeof(uint8_t)); 155 matrix.mapPoints((*dst)->fPoints, src.points(), src.fPointCnt); 156 (*dst)->fConicWeights = src.fConicWeights; 157 (*dst)->validate(); 158 } 159 160 static SkPathRef* CreateFromBuffer(SkRBuffer* buffer) { 161 SkPathRef* ref = SkNEW(SkPathRef); 162 ref->fGenerationID = buffer->readU32(); 163 int32_t verbCount = buffer->readS32(); 164 int32_t pointCount = buffer->readS32(); 165 int32_t conicCount = buffer->readS32(); 166 ref->resetToSize(verbCount, pointCount, conicCount); 167 168 SkASSERT(verbCount == ref->countVerbs()); 169 SkASSERT(pointCount == ref->countPoints()); 170 SkASSERT(conicCount == ref->fConicWeights.count()); 171 buffer->read(ref->verbsMemWritable(), verbCount * sizeof(uint8_t)); 172 buffer->read(ref->fPoints, pointCount * sizeof(SkPoint)); 173 buffer->read(ref->fConicWeights.begin(), conicCount * sizeof(SkScalar)); 174 return ref; 175 } 176 177 /** 178 * Rollsback a path ref to zero verbs and points with the assumption that the path ref will be 179 * repopulated with approximately the same number of verbs and points. A new path ref is created 180 * only if necessary. 181 */ 182 static void Rewind(SkAutoTUnref<SkPathRef>* pathRef) { 183 if ((*pathRef)->unique()) { 184 (*pathRef)->validate(); 185 (*pathRef)->fVerbCnt = 0; 186 (*pathRef)->fPointCnt = 0; 187 (*pathRef)->fFreeSpace = (*pathRef)->currSize(); 188 (*pathRef)->fGenerationID = 0; 189 (*pathRef)->fConicWeights.rewind(); 190 (*pathRef)->validate(); 191 } else { 192 int oldVCnt = (*pathRef)->countVerbs(); 193 int oldPCnt = (*pathRef)->countPoints(); 194 pathRef->reset(SkNEW(SkPathRef)); 195 (*pathRef)->resetToSize(0, 0, 0, oldVCnt, oldPCnt); 196 } 197 } 198 199 virtual ~SkPathRef() { 200 this->validate(); 201 sk_free(fPoints); 202 203 SkDEBUGCODE(fPoints = NULL;) 204 SkDEBUGCODE(fVerbs = NULL;) 205 SkDEBUGCODE(fVerbCnt = 0x9999999;) 206 SkDEBUGCODE(fPointCnt = 0xAAAAAAA;) 207 SkDEBUGCODE(fPointCnt = 0xBBBBBBB;) 208 SkDEBUGCODE(fGenerationID = 0xEEEEEEEE;) 209 SkDEBUGCODE(fEditorsAttached = 0x7777777;) 210 } 211 212 int countPoints() const { this->validate(); return fPointCnt; } 213 int countVerbs() const { this->validate(); return fVerbCnt; } 214 215 /** 216 * Returns a pointer one beyond the first logical verb (last verb in memory order). 217 */ 218 const uint8_t* verbs() const { this->validate(); return fVerbs; } 219 220 /** 221 * Returns a const pointer to the first verb in memory (which is the last logical verb). 222 */ 223 const uint8_t* verbsMemBegin() const { return this->verbs() - fVerbCnt; } 224 225 /** 226 * Returns a const pointer to the first point. 227 */ 228 const SkPoint* points() const { this->validate(); return fPoints; } 229 230 /** 231 * Shortcut for this->points() + this->countPoints() 232 */ 233 const SkPoint* pointsEnd() const { return this->points() + this->countPoints(); } 234 235 const SkScalar* conicWeights() const { this->validate(); return fConicWeights.begin(); } 236 const SkScalar* conicWeightsEnd() const { this->validate(); return fConicWeights.end(); } 237 238 /** 239 * Convenience methods for getting to a verb or point by index. 240 */ 241 uint8_t atVerb(int index) { 242 SkASSERT((unsigned) index < (unsigned) fVerbCnt); 243 return this->verbs()[~index]; 244 } 245 const SkPoint& atPoint(int index) const { 246 SkASSERT((unsigned) index < (unsigned) fPointCnt); 247 return this->points()[index]; 248 } 249 250 bool operator== (const SkPathRef& ref) const { 251 this->validate(); 252 ref.validate(); 253 bool genIDMatch = fGenerationID && fGenerationID == ref.fGenerationID; 254 #ifdef SK_RELEASE 255 if (genIDMatch) { 256 return true; 257 } 258 #endif 259 if (fPointCnt != ref.fPointCnt || 260 fVerbCnt != ref.fVerbCnt) { 261 SkASSERT(!genIDMatch); 262 return false; 263 } 264 if (0 != memcmp(this->verbsMemBegin(), 265 ref.verbsMemBegin(), 266 ref.fVerbCnt * sizeof(uint8_t))) { 267 SkASSERT(!genIDMatch); 268 return false; 269 } 270 if (0 != memcmp(this->points(), 271 ref.points(), 272 ref.fPointCnt * sizeof(SkPoint))) { 273 SkASSERT(!genIDMatch); 274 return false; 275 } 276 if (fConicWeights != ref.fConicWeights) { 277 SkASSERT(!genIDMatch); 278 return false; 279 } 280 // We've done the work to determine that these are equal. If either has a zero genID, copy 281 // the other's. If both are 0 then genID() will compute the next ID. 282 if (0 == fGenerationID) { 283 fGenerationID = ref.genID(); 284 } else if (0 == ref.fGenerationID) { 285 ref.fGenerationID = this->genID(); 286 } 287 return true; 288 } 289 290 /** 291 * Writes the path points and verbs to a buffer. 292 */ 293 void writeToBuffer(SkWBuffer* buffer) { 294 this->validate(); 295 SkDEBUGCODE(size_t beforePos = buffer->pos();) 296 297 // TODO: write gen ID here. Problem: We don't know if we're cross process or not from 298 // SkWBuffer. Until this is fixed we write 0. 299 buffer->write32(0); 300 buffer->write32(fVerbCnt); 301 buffer->write32(fPointCnt); 302 buffer->write32(fConicWeights.count()); 303 buffer->write(verbsMemBegin(), fVerbCnt * sizeof(uint8_t)); 304 buffer->write(fPoints, fPointCnt * sizeof(SkPoint)); 305 buffer->write(fConicWeights.begin(), fConicWeights.bytes()); 306 307 SkASSERT(buffer->pos() - beforePos == (size_t) this->writeSize()); 308 } 309 310 /** 311 * Gets the number of bytes that would be written in writeBuffer() 312 */ 313 uint32_t writeSize() { 314 return 4 * sizeof(uint32_t) + 315 fVerbCnt * sizeof(uint8_t) + 316 fPointCnt * sizeof(SkPoint) + 317 fConicWeights.bytes(); 318 } 319 320 private: 321 SkPathRef() { 322 fPointCnt = 0; 323 fVerbCnt = 0; 324 fVerbs = NULL; 325 fPoints = NULL; 326 fFreeSpace = 0; 327 fGenerationID = kEmptyGenID; 328 SkDEBUGCODE(fEditorsAttached = 0;) 329 this->validate(); 330 } 331 332 void copy(const SkPathRef& ref, int additionalReserveVerbs, int additionalReservePoints) { 333 this->validate(); 334 this->resetToSize(ref.fVerbCnt, ref.fPointCnt, ref.fConicWeights.count(), 335 additionalReserveVerbs, additionalReservePoints); 336 memcpy(this->verbsMemWritable(), ref.verbsMemBegin(), ref.fVerbCnt * sizeof(uint8_t)); 337 memcpy(this->fPoints, ref.fPoints, ref.fPointCnt * sizeof(SkPoint)); 338 fConicWeights = ref.fConicWeights; 339 // We could call genID() here to force a real ID (instead of 0). However, if we're making 340 // a copy then presumably we intend to make a modification immediately afterwards. 341 fGenerationID = ref.fGenerationID; 342 this->validate(); 343 } 344 345 /** Makes additional room but does not change the counts or change the genID */ 346 void incReserve(int additionalVerbs, int additionalPoints) { 347 this->validate(); 348 size_t space = additionalVerbs * sizeof(uint8_t) + additionalPoints * sizeof (SkPoint); 349 this->makeSpace(space); 350 this->validate(); 351 } 352 353 /** Resets the path ref with verbCount verbs and pointCount points, all unitialized. Also 354 * allocates space for reserveVerb additional verbs and reservePoints additional points.*/ 355 void resetToSize(int verbCount, int pointCount, int conicCount, 356 int reserveVerbs = 0, int reservePoints = 0) { 357 this->validate(); 358 fGenerationID = 0; 359 360 size_t newSize = sizeof(uint8_t) * verbCount + sizeof(SkPoint) * pointCount; 361 size_t newReserve = sizeof(uint8_t) * reserveVerbs + sizeof(SkPoint) * reservePoints; 362 size_t minSize = newSize + newReserve; 363 364 ptrdiff_t sizeDelta = this->currSize() - minSize; 365 366 if (sizeDelta < 0 || static_cast<size_t>(sizeDelta) >= 3 * minSize) { 367 sk_free(fPoints); 368 fPoints = NULL; 369 fVerbs = NULL; 370 fFreeSpace = 0; 371 fVerbCnt = 0; 372 fPointCnt = 0; 373 this->makeSpace(minSize); 374 fVerbCnt = verbCount; 375 fPointCnt = pointCount; 376 fFreeSpace -= newSize; 377 } else { 378 fPointCnt = pointCount; 379 fVerbCnt = verbCount; 380 fFreeSpace = this->currSize() - minSize; 381 } 382 fConicWeights.setCount(conicCount); 383 this->validate(); 384 } 385 386 /** 387 * Increases the verb count by newVerbs and the point count be newPoints. New verbs and points 388 * are uninitialized. 389 */ 390 void grow(int newVerbs, int newPoints) { 391 this->validate(); 392 size_t space = newVerbs * sizeof(uint8_t) + newPoints * sizeof (SkPoint); 393 this->makeSpace(space); 394 fVerbCnt += newVerbs; 395 fPointCnt += newPoints; 396 fFreeSpace -= space; 397 this->validate(); 398 } 399 400 /** 401 * Increases the verb count 1, records the new verb, and creates room for the requisite number 402 * of additional points. A pointer to the first point is returned. Any new points are 403 * uninitialized. 404 */ 405 SkPoint* growForVerb(SkPath::Verb verb) { 406 this->validate(); 407 int pCnt; 408 switch (verb) { 409 case SkPath::kMove_Verb: 410 pCnt = 1; 411 break; 412 case SkPath::kLine_Verb: 413 pCnt = 1; 414 break; 415 case SkPath::kQuad_Verb: 416 // fall through 417 case SkPath::kConic_Verb: 418 pCnt = 2; 419 break; 420 case SkPath::kCubic_Verb: 421 pCnt = 3; 422 break; 423 case SkPath::kClose_Verb: 424 pCnt = 0; 425 break; 426 case SkPath::kDone_Verb: 427 SkASSERT(!"growForVerb called for kDone"); 428 // fall through 429 default: 430 SkASSERT(!"default is not reached"); 431 pCnt = 0; 432 } 433 size_t space = sizeof(uint8_t) + pCnt * sizeof (SkPoint); 434 this->makeSpace(space); 435 this->fVerbs[~fVerbCnt] = verb; 436 SkPoint* ret = fPoints + fPointCnt; 437 fVerbCnt += 1; 438 fPointCnt += pCnt; 439 fFreeSpace -= space; 440 this->validate(); 441 return ret; 442 } 443 444 /** 445 * Ensures that the free space available in the path ref is >= size. The verb and point counts 446 * are not changed. 447 */ 448 void makeSpace(size_t size) { 449 this->validate(); 450 ptrdiff_t growSize = size - fFreeSpace; 451 if (growSize <= 0) { 452 return; 453 } 454 size_t oldSize = this->currSize(); 455 // round to next multiple of 8 bytes 456 growSize = (growSize + 7) & ~static_cast<size_t>(7); 457 // we always at least double the allocation 458 if (static_cast<size_t>(growSize) < oldSize) { 459 growSize = oldSize; 460 } 461 if (growSize < kMinSize) { 462 growSize = kMinSize; 463 } 464 size_t newSize = oldSize + growSize; 465 // Note that realloc could memcpy more than we need. It seems to be a win anyway. TODO: 466 // encapsulate this. 467 fPoints = reinterpret_cast<SkPoint*>(sk_realloc_throw(fPoints, newSize)); 468 size_t oldVerbSize = fVerbCnt * sizeof(uint8_t); 469 void* newVerbsDst = reinterpret_cast<void*>( 470 reinterpret_cast<intptr_t>(fPoints) + newSize - oldVerbSize); 471 void* oldVerbsSrc = reinterpret_cast<void*>( 472 reinterpret_cast<intptr_t>(fPoints) + oldSize - oldVerbSize); 473 memmove(newVerbsDst, oldVerbsSrc, oldVerbSize); 474 fVerbs = reinterpret_cast<uint8_t*>(reinterpret_cast<intptr_t>(fPoints) + newSize); 475 fFreeSpace += growSize; 476 this->validate(); 477 } 478 479 /** 480 * Private, non-const-ptr version of the public function verbsMemBegin(). 481 */ 482 uint8_t* verbsMemWritable() { 483 this->validate(); 484 return fVerbs - fVerbCnt; 485 } 486 487 /** 488 * Gets the total amount of space allocated for verbs, points, and reserve. 489 */ 490 size_t currSize() const { 491 return reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints); 492 } 493 494 /** 495 * Gets an ID that uniquely identifies the contents of the path ref. If two path refs have the 496 * same ID then they have the same verbs and points. However, two path refs may have the same 497 * contents but different genIDs. Zero is reserved and means an ID has not yet been determined 498 * for the path ref. 499 */ 500 int32_t genID() const { 501 SkASSERT(!fEditorsAttached); 502 if (!fGenerationID) { 503 if (0 == fPointCnt && 0 == fVerbCnt) { 504 fGenerationID = kEmptyGenID; 505 } else { 506 static int32_t gPathRefGenerationID; 507 // do a loop in case our global wraps around, as we never want to return a 0 or the 508 // empty ID 509 do { 510 fGenerationID = sk_atomic_inc(&gPathRefGenerationID) + 1; 511 } while (fGenerationID <= kEmptyGenID); 512 } 513 } 514 return fGenerationID; 515 } 516 517 void validate() const { 518 SkASSERT(static_cast<ptrdiff_t>(fFreeSpace) >= 0); 519 SkASSERT(reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints) >= 0); 520 SkASSERT((NULL == fPoints) == (NULL == fVerbs)); 521 SkASSERT(!(NULL == fPoints && 0 != fFreeSpace)); 522 SkASSERT(!(NULL == fPoints && 0 != fFreeSpace)); 523 SkASSERT(!(NULL == fPoints && fPointCnt)); 524 SkASSERT(!(NULL == fVerbs && fVerbCnt)); 525 SkASSERT(this->currSize() == 526 fFreeSpace + sizeof(SkPoint) * fPointCnt + sizeof(uint8_t) * fVerbCnt); 527 } 528 529 enum { 530 kMinSize = 256, 531 }; 532 533 SkPoint* fPoints; // points to begining of the allocation 534 uint8_t* fVerbs; // points just past the end of the allocation (verbs grow backwards) 535 int fVerbCnt; 536 int fPointCnt; 537 size_t fFreeSpace; // redundant but saves computation 538 SkTDArray<SkScalar> fConicWeights; 539 540 enum { 541 kEmptyGenID = 1, // GenID reserved for path ref with zero points and zero verbs. 542 }; 543 mutable int32_t fGenerationID; 544 SkDEBUGCODE(int32_t fEditorsAttached;) // assert that only one editor in use at any time. 545 546 typedef SkRefCnt INHERITED; 547 }; 548 549 SK_DEFINE_INST_COUNT(SkPathRef); 550 551 #endif 552