1 /* 2 * Copyright 2006 The Android Open Source Project 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 "SkRegion.h" 9 10 #include "SkMacros.h" 11 #include "SkRegionPriv.h" 12 #include "SkSafeMath.h" 13 #include "SkTemplates.h" 14 #include "SkTo.h" 15 #include "SkUTF.h" 16 17 #include <utility> 18 19 /* Region Layout 20 * 21 * TOP 22 * 23 * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ] 24 * ... 25 * 26 * Y-Sentinel 27 */ 28 29 ///////////////////////////////////////////////////////////////////////////////////////////////// 30 31 #define SkRegion_gEmptyRunHeadPtr ((SkRegionPriv::RunHead*)-1) 32 #define SkRegion_gRectRunHeadPtr nullptr 33 34 constexpr int kRunArrayStackCount = 256; 35 36 // This is a simple data structure which is like a SkSTArray<N,T,true>, except that: 37 // - It does not initialize memory. 38 // - It does not distinguish between reserved space and initialized space. 39 // - resizeToAtLeast() instead of resize() 40 // - Uses sk_realloc_throw() 41 // - Can never be made smaller. 42 // Measurement: for the `region_union_16` benchmark, this is 6% faster. 43 class RunArray { 44 public: 45 RunArray() { fPtr = fStack; } 46 #ifdef SK_DEBUG 47 int count() const { return fCount; } 48 #endif 49 SkRegionPriv::RunType& operator[](int i) { 50 SkASSERT((unsigned)i < (unsigned)fCount); 51 return fPtr[i]; 52 } 53 /** Resize the array to a size greater-than-or-equal-to count. */ 54 void resizeToAtLeast(int count) { 55 if (count > fCount) { 56 // leave at least 50% extra space for future growth. 57 count += count >> 1; 58 fMalloc.realloc(count); 59 if (fPtr == fStack) { 60 memcpy(fMalloc.get(), fStack, fCount * sizeof(SkRegionPriv::RunType)); 61 } 62 fPtr = fMalloc.get(); 63 fCount = count; 64 } 65 } 66 private: 67 SkRegionPriv::RunType fStack[kRunArrayStackCount]; 68 SkAutoTMalloc<SkRegionPriv::RunType> fMalloc; 69 int fCount = kRunArrayStackCount; 70 SkRegionPriv::RunType* fPtr; // non-owning pointer 71 }; 72 73 /* Pass in the beginning with the intervals. 74 * We back up 1 to read the interval-count. 75 * Return the beginning of the next scanline (i.e. the next Y-value) 76 */ 77 static SkRegionPriv::RunType* skip_intervals(const SkRegionPriv::RunType runs[]) { 78 int intervals = runs[-1]; 79 #ifdef SK_DEBUG 80 if (intervals > 0) { 81 SkASSERT(runs[0] < runs[1]); 82 SkASSERT(runs[1] < SkRegion_kRunTypeSentinel); 83 } else { 84 SkASSERT(0 == intervals); 85 SkASSERT(SkRegion_kRunTypeSentinel == runs[0]); 86 } 87 #endif 88 runs += intervals * 2 + 1; 89 return const_cast<SkRegionPriv::RunType*>(runs); 90 } 91 92 bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count, 93 SkIRect* bounds) { 94 assert_sentinel(runs[0], false); // top 95 SkASSERT(count >= kRectRegionRuns); 96 97 if (count == kRectRegionRuns) { 98 assert_sentinel(runs[1], false); // bottom 99 SkASSERT(1 == runs[2]); 100 assert_sentinel(runs[3], false); // left 101 assert_sentinel(runs[4], false); // right 102 assert_sentinel(runs[5], true); 103 assert_sentinel(runs[6], true); 104 105 SkASSERT(runs[0] < runs[1]); // valid height 106 SkASSERT(runs[3] < runs[4]); // valid width 107 108 bounds->set(runs[3], runs[0], runs[4], runs[1]); 109 return true; 110 } 111 return false; 112 } 113 114 ////////////////////////////////////////////////////////////////////////// 115 116 SkRegion::SkRegion() { 117 fBounds.set(0, 0, 0, 0); 118 fRunHead = SkRegion_gEmptyRunHeadPtr; 119 } 120 121 SkRegion::SkRegion(const SkRegion& src) { 122 fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) 123 this->setRegion(src); 124 } 125 126 SkRegion::SkRegion(const SkIRect& rect) { 127 fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) 128 this->setRect(rect); 129 } 130 131 SkRegion::~SkRegion() { 132 this->freeRuns(); 133 } 134 135 void SkRegion::freeRuns() { 136 if (this->isComplex()) { 137 SkASSERT(fRunHead->fRefCnt >= 1); 138 if (--fRunHead->fRefCnt == 0) { 139 sk_free(fRunHead); 140 } 141 } 142 } 143 144 void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) { 145 fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount); 146 } 147 148 void SkRegion::allocateRuns(int count) { 149 fRunHead = RunHead::Alloc(count); 150 } 151 152 void SkRegion::allocateRuns(const RunHead& head) { 153 fRunHead = RunHead::Alloc(head.fRunCount, 154 head.getYSpanCount(), 155 head.getIntervalCount()); 156 } 157 158 SkRegion& SkRegion::operator=(const SkRegion& src) { 159 (void)this->setRegion(src); 160 return *this; 161 } 162 163 void SkRegion::swap(SkRegion& other) { 164 using std::swap; 165 swap(fBounds, other.fBounds); 166 swap(fRunHead, other.fRunHead); 167 } 168 169 int SkRegion::computeRegionComplexity() const { 170 if (this->isEmpty()) { 171 return 0; 172 } else if (this->isRect()) { 173 return 1; 174 } 175 return fRunHead->getIntervalCount(); 176 } 177 178 bool SkRegion::setEmpty() { 179 this->freeRuns(); 180 fBounds.set(0, 0, 0, 0); 181 fRunHead = SkRegion_gEmptyRunHeadPtr; 182 return false; 183 } 184 185 bool SkRegion::setRect(const SkIRect& r) { 186 if (r.isEmpty() || 187 SkRegion_kRunTypeSentinel == r.right() || 188 SkRegion_kRunTypeSentinel == r.bottom()) { 189 return this->setEmpty(); 190 } 191 this->freeRuns(); 192 fBounds = r; 193 fRunHead = SkRegion_gRectRunHeadPtr; 194 return true; 195 } 196 197 bool SkRegion::setRegion(const SkRegion& src) { 198 if (this != &src) { 199 this->freeRuns(); 200 201 fBounds = src.fBounds; 202 fRunHead = src.fRunHead; 203 if (this->isComplex()) { 204 fRunHead->fRefCnt++; 205 } 206 } 207 return fRunHead != SkRegion_gEmptyRunHeadPtr; 208 } 209 210 bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) { 211 SkRegion tmp(rect); 212 213 return this->op(tmp, rgn, op); 214 } 215 216 bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) { 217 SkRegion tmp(rect); 218 219 return this->op(rgn, tmp, op); 220 } 221 222 /////////////////////////////////////////////////////////////////////////////// 223 224 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK 225 #include <stdio.h> 226 char* SkRegion::toString() { 227 Iterator iter(*this); 228 int count = 0; 229 while (!iter.done()) { 230 count++; 231 iter.next(); 232 } 233 // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0' 234 const int max = (count*((11*4)+5))+11+1; 235 char* result = (char*)sk_malloc_throw(max); 236 if (result == nullptr) { 237 return nullptr; 238 } 239 count = snprintf(result, max, "SkRegion("); 240 iter.reset(*this); 241 while (!iter.done()) { 242 const SkIRect& r = iter.rect(); 243 count += snprintf(result+count, max - count, 244 "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom); 245 iter.next(); 246 } 247 count += snprintf(result+count, max - count, ")"); 248 return result; 249 } 250 #endif 251 252 /////////////////////////////////////////////////////////////////////////////// 253 254 int SkRegion::count_runtype_values(int* itop, int* ibot) const { 255 int maxT; 256 257 if (this->isRect()) { 258 maxT = 2; 259 } else { 260 SkASSERT(this->isComplex()); 261 maxT = fRunHead->getIntervalCount() * 2; 262 } 263 *itop = fBounds.fTop; 264 *ibot = fBounds.fBottom; 265 return maxT; 266 } 267 268 static bool isRunCountEmpty(int count) { 269 return count <= 2; 270 } 271 272 bool SkRegion::setRuns(RunType runs[], int count) { 273 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 274 SkASSERT(count > 0); 275 276 if (isRunCountEmpty(count)) { 277 // SkDEBUGF("setRuns: empty\n"); 278 assert_sentinel(runs[count-1], true); 279 return this->setEmpty(); 280 } 281 282 // trim off any empty spans from the top and bottom 283 // weird I should need this, perhaps op() could be smarter... 284 if (count > kRectRegionRuns) { 285 RunType* stop = runs + count; 286 assert_sentinel(runs[0], false); // top 287 assert_sentinel(runs[1], false); // bottom 288 // runs[2] is uncomputed intervalCount 289 290 if (runs[3] == SkRegion_kRunTypeSentinel) { // should be first left... 291 runs += 3; // skip empty initial span 292 runs[0] = runs[-2]; // set new top to prev bottom 293 assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row 294 assert_sentinel(runs[2], false); // intervalcount 295 assert_sentinel(runs[3], false); // left 296 assert_sentinel(runs[4], false); // right 297 } 298 299 assert_sentinel(stop[-1], true); 300 assert_sentinel(stop[-2], true); 301 302 // now check for a trailing empty span 303 if (stop[-5] == SkRegion_kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs 304 stop[-4] = SkRegion_kRunTypeSentinel; // kill empty last span 305 stop -= 3; 306 assert_sentinel(stop[-1], true); // last y-sentinel 307 assert_sentinel(stop[-2], true); // last x-sentinel 308 assert_sentinel(stop[-3], false); // last right 309 assert_sentinel(stop[-4], false); // last left 310 assert_sentinel(stop[-5], false); // last interval-count 311 assert_sentinel(stop[-6], false); // last bottom 312 } 313 count = (int)(stop - runs); 314 } 315 316 SkASSERT(count >= kRectRegionRuns); 317 318 if (SkRegion::RunsAreARect(runs, count, &fBounds)) { 319 return this->setRect(fBounds); 320 } 321 322 // if we get here, we need to become a complex region 323 324 if (!this->isComplex() || fRunHead->fRunCount != count) { 325 this->freeRuns(); 326 this->allocateRuns(count); 327 SkASSERT(this->isComplex()); 328 } 329 330 // must call this before we can write directly into runs() 331 // in case we are sharing the buffer with another region (copy on write) 332 fRunHead = fRunHead->ensureWritable(); 333 memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType)); 334 fRunHead->computeRunBounds(&fBounds); 335 336 // Our computed bounds might be too large, so we have to check here. 337 if (fBounds.isEmpty()) { 338 return this->setEmpty(); 339 } 340 341 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 342 343 return true; 344 } 345 346 void SkRegion::BuildRectRuns(const SkIRect& bounds, 347 RunType runs[kRectRegionRuns]) { 348 runs[0] = bounds.fTop; 349 runs[1] = bounds.fBottom; 350 runs[2] = 1; // 1 interval for this scanline 351 runs[3] = bounds.fLeft; 352 runs[4] = bounds.fRight; 353 runs[5] = SkRegion_kRunTypeSentinel; 354 runs[6] = SkRegion_kRunTypeSentinel; 355 } 356 357 bool SkRegion::contains(int32_t x, int32_t y) const { 358 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 359 360 if (!fBounds.contains(x, y)) { 361 return false; 362 } 363 if (this->isRect()) { 364 return true; 365 } 366 SkASSERT(this->isComplex()); 367 368 const RunType* runs = fRunHead->findScanline(y); 369 370 // Skip the Bottom and IntervalCount 371 runs += 2; 372 373 // Just walk this scanline, checking each interval. The X-sentinel will 374 // appear as a left-inteval (runs[0]) and should abort the search. 375 // 376 // We could do a bsearch, using interval-count (runs[1]), but need to time 377 // when that would be worthwhile. 378 // 379 for (;;) { 380 if (x < runs[0]) { 381 break; 382 } 383 if (x < runs[1]) { 384 return true; 385 } 386 runs += 2; 387 } 388 return false; 389 } 390 391 static SkRegionPriv::RunType scanline_bottom(const SkRegionPriv::RunType runs[]) { 392 return runs[0]; 393 } 394 395 static const SkRegionPriv::RunType* scanline_next(const SkRegionPriv::RunType runs[]) { 396 // skip [B N [L R]... S] 397 return runs + 2 + runs[1] * 2 + 1; 398 } 399 400 static bool scanline_contains(const SkRegionPriv::RunType runs[], 401 SkRegionPriv::RunType L, SkRegionPriv::RunType R) { 402 runs += 2; // skip Bottom and IntervalCount 403 for (;;) { 404 if (L < runs[0]) { 405 break; 406 } 407 if (R <= runs[1]) { 408 return true; 409 } 410 runs += 2; 411 } 412 return false; 413 } 414 415 bool SkRegion::contains(const SkIRect& r) const { 416 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 417 418 if (!fBounds.contains(r)) { 419 return false; 420 } 421 if (this->isRect()) { 422 return true; 423 } 424 SkASSERT(this->isComplex()); 425 426 const RunType* scanline = fRunHead->findScanline(r.fTop); 427 for (;;) { 428 if (!scanline_contains(scanline, r.fLeft, r.fRight)) { 429 return false; 430 } 431 if (r.fBottom <= scanline_bottom(scanline)) { 432 break; 433 } 434 scanline = scanline_next(scanline); 435 } 436 return true; 437 } 438 439 bool SkRegion::contains(const SkRegion& rgn) const { 440 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 441 SkDEBUGCODE(SkRegionPriv::Validate(rgn)); 442 443 if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) { 444 return false; 445 } 446 if (this->isRect()) { 447 return true; 448 } 449 if (rgn.isRect()) { 450 return this->contains(rgn.getBounds()); 451 } 452 453 /* 454 * A contains B is equivalent to 455 * B - A == 0 456 */ 457 return !Oper(rgn, *this, kDifference_Op, nullptr); 458 } 459 460 const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], 461 int* intervals) const { 462 SkASSERT(tmpStorage && intervals); 463 const RunType* runs = tmpStorage; 464 465 if (this->isEmpty()) { 466 tmpStorage[0] = SkRegion_kRunTypeSentinel; 467 *intervals = 0; 468 } else if (this->isRect()) { 469 BuildRectRuns(fBounds, tmpStorage); 470 *intervals = 1; 471 } else { 472 runs = fRunHead->readonly_runs(); 473 *intervals = fRunHead->getIntervalCount(); 474 } 475 return runs; 476 } 477 478 /////////////////////////////////////////////////////////////////////////////// 479 480 static bool scanline_intersects(const SkRegionPriv::RunType runs[], 481 SkRegionPriv::RunType L, SkRegionPriv::RunType R) { 482 runs += 2; // skip Bottom and IntervalCount 483 for (;;) { 484 if (R <= runs[0]) { 485 break; 486 } 487 if (L < runs[1]) { 488 return true; 489 } 490 runs += 2; 491 } 492 return false; 493 } 494 495 bool SkRegion::intersects(const SkIRect& r) const { 496 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 497 498 if (this->isEmpty() || r.isEmpty()) { 499 return false; 500 } 501 502 SkIRect sect; 503 if (!sect.intersect(fBounds, r)) { 504 return false; 505 } 506 if (this->isRect()) { 507 return true; 508 } 509 SkASSERT(this->isComplex()); 510 511 const RunType* scanline = fRunHead->findScanline(sect.fTop); 512 for (;;) { 513 if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) { 514 return true; 515 } 516 if (sect.fBottom <= scanline_bottom(scanline)) { 517 break; 518 } 519 scanline = scanline_next(scanline); 520 } 521 return false; 522 } 523 524 bool SkRegion::intersects(const SkRegion& rgn) const { 525 if (this->isEmpty() || rgn.isEmpty()) { 526 return false; 527 } 528 529 if (!SkIRect::Intersects(fBounds, rgn.fBounds)) { 530 return false; 531 } 532 533 bool weAreARect = this->isRect(); 534 bool theyAreARect = rgn.isRect(); 535 536 if (weAreARect && theyAreARect) { 537 return true; 538 } 539 if (weAreARect) { 540 return rgn.intersects(this->getBounds()); 541 } 542 if (theyAreARect) { 543 return this->intersects(rgn.getBounds()); 544 } 545 546 // both of us are complex 547 return Oper(*this, rgn, kIntersect_Op, nullptr); 548 } 549 550 /////////////////////////////////////////////////////////////////////////////// 551 552 bool SkRegion::operator==(const SkRegion& b) const { 553 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 554 SkDEBUGCODE(SkRegionPriv::Validate(b)); 555 556 if (this == &b) { 557 return true; 558 } 559 if (fBounds != b.fBounds) { 560 return false; 561 } 562 563 const SkRegion::RunHead* ah = fRunHead; 564 const SkRegion::RunHead* bh = b.fRunHead; 565 566 // this catches empties and rects being equal 567 if (ah == bh) { 568 return true; 569 } 570 // now we insist that both are complex (but different ptrs) 571 if (!this->isComplex() || !b.isComplex()) { 572 return false; 573 } 574 return ah->fRunCount == bh->fRunCount && 575 !memcmp(ah->readonly_runs(), bh->readonly_runs(), 576 ah->fRunCount * sizeof(SkRegion::RunType)); 577 } 578 579 // Return a (new) offset such that when applied (+=) to min and max, we don't overflow/underflow 580 static int32_t pin_offset_s32(int32_t min, int32_t max, int32_t offset) { 581 SkASSERT(min <= max); 582 const int32_t lo = -SK_MaxS32-1, 583 hi = +SK_MaxS32; 584 if ((int64_t)min + offset < lo) { offset = lo - min; } 585 if ((int64_t)max + offset > hi) { offset = hi - max; } 586 return offset; 587 } 588 589 void SkRegion::translate(int dx, int dy, SkRegion* dst) const { 590 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 591 592 if (nullptr == dst) { 593 return; 594 } 595 if (this->isEmpty()) { 596 dst->setEmpty(); 597 return; 598 } 599 // pin dx and dy so we don't overflow our existing bounds 600 dx = pin_offset_s32(fBounds.fLeft, fBounds.fRight, dx); 601 dy = pin_offset_s32(fBounds.fTop, fBounds.fBottom, dy); 602 603 if (this->isRect()) { 604 dst->setRect(fBounds.makeOffset(dx, dy)); 605 } else { 606 if (this == dst) { 607 dst->fRunHead = dst->fRunHead->ensureWritable(); 608 } else { 609 SkRegion tmp; 610 tmp.allocateRuns(*fRunHead); 611 SkASSERT(tmp.isComplex()); 612 tmp.fBounds = fBounds; 613 dst->swap(tmp); 614 } 615 616 dst->fBounds.offset(dx, dy); 617 618 const RunType* sruns = fRunHead->readonly_runs(); 619 RunType* druns = dst->fRunHead->writable_runs(); 620 621 *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top 622 for (;;) { 623 int bottom = *sruns++; 624 if (bottom == SkRegion_kRunTypeSentinel) { 625 break; 626 } 627 *druns++ = (SkRegion::RunType)(bottom + dy); // bottom; 628 *druns++ = *sruns++; // copy intervalCount; 629 for (;;) { 630 int x = *sruns++; 631 if (x == SkRegion_kRunTypeSentinel) { 632 break; 633 } 634 *druns++ = (SkRegion::RunType)(x + dx); 635 *druns++ = (SkRegion::RunType)(*sruns++ + dx); 636 } 637 *druns++ = SkRegion_kRunTypeSentinel; // x sentinel 638 } 639 *druns++ = SkRegion_kRunTypeSentinel; // y sentinel 640 641 SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount); 642 SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount); 643 } 644 645 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 646 } 647 648 /////////////////////////////////////////////////////////////////////////////// 649 650 bool SkRegion::setRects(const SkIRect rects[], int count) { 651 if (0 == count) { 652 this->setEmpty(); 653 } else { 654 this->setRect(rects[0]); 655 for (int i = 1; i < count; i++) { 656 this->op(rects[i], kUnion_Op); 657 } 658 } 659 return !this->isEmpty(); 660 } 661 662 /////////////////////////////////////////////////////////////////////////////// 663 664 #if defined _WIN32 // disable warning : local variable used without having been initialized 665 #pragma warning ( push ) 666 #pragma warning ( disable : 4701 ) 667 #endif 668 669 #ifdef SK_DEBUG 670 static void assert_valid_pair(int left, int rite) 671 { 672 SkASSERT(left == SkRegion_kRunTypeSentinel || left < rite); 673 } 674 #else 675 #define assert_valid_pair(left, rite) 676 #endif 677 678 struct spanRec { 679 const SkRegionPriv::RunType* fA_runs; 680 const SkRegionPriv::RunType* fB_runs; 681 int fA_left, fA_rite, fB_left, fB_rite; 682 int fLeft, fRite, fInside; 683 684 void init(const SkRegionPriv::RunType a_runs[], 685 const SkRegionPriv::RunType b_runs[]) { 686 fA_left = *a_runs++; 687 fA_rite = *a_runs++; 688 fB_left = *b_runs++; 689 fB_rite = *b_runs++; 690 691 fA_runs = a_runs; 692 fB_runs = b_runs; 693 } 694 695 bool done() const { 696 SkASSERT(fA_left <= SkRegion_kRunTypeSentinel); 697 SkASSERT(fB_left <= SkRegion_kRunTypeSentinel); 698 return fA_left == SkRegion_kRunTypeSentinel && 699 fB_left == SkRegion_kRunTypeSentinel; 700 } 701 702 void next() { 703 assert_valid_pair(fA_left, fA_rite); 704 assert_valid_pair(fB_left, fB_rite); 705 706 int inside, left, rite SK_INIT_TO_AVOID_WARNING; 707 bool a_flush = false; 708 bool b_flush = false; 709 710 int a_left = fA_left; 711 int a_rite = fA_rite; 712 int b_left = fB_left; 713 int b_rite = fB_rite; 714 715 if (a_left < b_left) { 716 inside = 1; 717 left = a_left; 718 if (a_rite <= b_left) { // [...] <...> 719 rite = a_rite; 720 a_flush = true; 721 } else { // [...<..]...> or [...<...>...] 722 rite = a_left = b_left; 723 } 724 } else if (b_left < a_left) { 725 inside = 2; 726 left = b_left; 727 if (b_rite <= a_left) { // [...] <...> 728 rite = b_rite; 729 b_flush = true; 730 } else { // [...<..]...> or [...<...>...] 731 rite = b_left = a_left; 732 } 733 } else { // a_left == b_left 734 inside = 3; 735 left = a_left; // or b_left 736 if (a_rite <= b_rite) { 737 rite = b_left = a_rite; 738 a_flush = true; 739 } 740 if (b_rite <= a_rite) { 741 rite = a_left = b_rite; 742 b_flush = true; 743 } 744 } 745 746 if (a_flush) { 747 a_left = *fA_runs++; 748 a_rite = *fA_runs++; 749 } 750 if (b_flush) { 751 b_left = *fB_runs++; 752 b_rite = *fB_runs++; 753 } 754 755 SkASSERT(left <= rite); 756 757 // now update our state 758 fA_left = a_left; 759 fA_rite = a_rite; 760 fB_left = b_left; 761 fB_rite = b_rite; 762 763 fLeft = left; 764 fRite = rite; 765 fInside = inside; 766 } 767 }; 768 769 static int distance_to_sentinel(const SkRegionPriv::RunType* runs) { 770 const SkRegionPriv::RunType* ptr = runs; 771 while (*ptr != SkRegion_kRunTypeSentinel) { ptr += 2; } 772 return ptr - runs; 773 } 774 775 static int operate_on_span(const SkRegionPriv::RunType a_runs[], 776 const SkRegionPriv::RunType b_runs[], 777 RunArray* array, int dstOffset, 778 int min, int max) { 779 // This is a worst-case for this span plus two for TWO terminating sentinels. 780 array->resizeToAtLeast( 781 dstOffset + distance_to_sentinel(a_runs) + distance_to_sentinel(b_runs) + 2); 782 SkRegionPriv::RunType* dst = &(*array)[dstOffset]; // get pointer AFTER resizing. 783 784 spanRec rec; 785 bool firstInterval = true; 786 787 rec.init(a_runs, b_runs); 788 789 while (!rec.done()) { 790 rec.next(); 791 792 int left = rec.fLeft; 793 int rite = rec.fRite; 794 795 // add left,rite to our dst buffer (checking for coincidence 796 if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) && 797 left < rite) { // skip if equal 798 if (firstInterval || *(dst - 1) < left) { 799 *dst++ = (SkRegionPriv::RunType)(left); 800 *dst++ = (SkRegionPriv::RunType)(rite); 801 firstInterval = false; 802 } else { 803 // update the right edge 804 *(dst - 1) = (SkRegionPriv::RunType)(rite); 805 } 806 } 807 } 808 SkASSERT(dst < &(*array)[array->count() - 1]); 809 *dst++ = SkRegion_kRunTypeSentinel; 810 return dst - &(*array)[0]; 811 } 812 813 #if defined _WIN32 814 #pragma warning ( pop ) 815 #endif 816 817 static const struct { 818 uint8_t fMin; 819 uint8_t fMax; 820 } gOpMinMax[] = { 821 { 1, 1 }, // Difference 822 { 3, 3 }, // Intersection 823 { 1, 3 }, // Union 824 { 1, 2 } // XOR 825 }; 826 // need to ensure that the op enum lines up with our minmax array 827 static_assert(0 == SkRegion::kDifference_Op, ""); 828 static_assert(1 == SkRegion::kIntersect_Op, ""); 829 static_assert(2 == SkRegion::kUnion_Op, ""); 830 static_assert(3 == SkRegion::kXOR_Op, ""); 831 832 class RgnOper { 833 public: 834 RgnOper(int top, RunArray* array, SkRegion::Op op) 835 : fMin(gOpMinMax[op].fMin) 836 , fMax(gOpMinMax[op].fMax) 837 , fArray(array) 838 , fTop((SkRegionPriv::RunType)top) // just a first guess, we might update this 839 { SkASSERT((unsigned)op <= 3); } 840 841 void addSpan(int bottom, const SkRegionPriv::RunType a_runs[], 842 const SkRegionPriv::RunType b_runs[]) { 843 // skip X values and slots for the next Y+intervalCount 844 int start = fPrevDst + fPrevLen + 2; 845 // start points to beginning of dst interval 846 int stop = operate_on_span(a_runs, b_runs, fArray, start, fMin, fMax); 847 size_t len = SkToSizeT(stop - start); 848 SkASSERT(len >= 1 && (len & 1) == 1); 849 SkASSERT(SkRegion_kRunTypeSentinel == (*fArray)[stop - 1]); 850 851 // Assert memcmp won't exceed fArray->count(). 852 SkASSERT(fArray->count() >= SkToInt(start + len - 1)); 853 if (fPrevLen == len && 854 (1 == len || !memcmp(&(*fArray)[fPrevDst], 855 &(*fArray)[start], 856 (len - 1) * sizeof(SkRegionPriv::RunType)))) { 857 // update Y value 858 (*fArray)[fPrevDst - 2] = (SkRegionPriv::RunType)bottom; 859 } else { // accept the new span 860 if (len == 1 && fPrevLen == 0) { 861 fTop = (SkRegionPriv::RunType)bottom; // just update our bottom 862 } else { 863 (*fArray)[start - 2] = (SkRegionPriv::RunType)bottom; 864 (*fArray)[start - 1] = SkToS32(len >> 1); 865 fPrevDst = start; 866 fPrevLen = len; 867 } 868 } 869 } 870 871 int flush() { 872 (*fArray)[fStartDst] = fTop; 873 // Previously reserved enough for TWO sentinals. 874 SkASSERT(fArray->count() > SkToInt(fPrevDst + fPrevLen)); 875 (*fArray)[fPrevDst + fPrevLen] = SkRegion_kRunTypeSentinel; 876 return (int)(fPrevDst - fStartDst + fPrevLen + 1); 877 } 878 879 bool isEmpty() const { return 0 == fPrevLen; } 880 881 uint8_t fMin, fMax; 882 883 private: 884 RunArray* fArray; 885 int fStartDst = 0; 886 int fPrevDst = 1; 887 size_t fPrevLen = 0; // will never match a length from operate_on_span 888 SkRegionPriv::RunType fTop; 889 }; 890 891 // want a unique value to signal that we exited due to quickExit 892 #define QUICK_EXIT_TRUE_COUNT (-1) 893 894 static int operate(const SkRegionPriv::RunType a_runs[], 895 const SkRegionPriv::RunType b_runs[], 896 RunArray* dst, 897 SkRegion::Op op, 898 bool quickExit) { 899 const SkRegionPriv::RunType gEmptyScanline[] = { 900 0, // dummy bottom value 901 0, // zero intervals 902 SkRegion_kRunTypeSentinel, 903 // just need a 2nd value, since spanRec.init() reads 2 values, even 904 // though if the first value is the sentinel, it ignores the 2nd value. 905 // w/o the 2nd value here, we might read uninitialized memory. 906 // This happens when we are using gSentinel, which is pointing at 907 // our sentinel value. 908 0 909 }; 910 const SkRegionPriv::RunType* const gSentinel = &gEmptyScanline[2]; 911 912 int a_top = *a_runs++; 913 int a_bot = *a_runs++; 914 int b_top = *b_runs++; 915 int b_bot = *b_runs++; 916 917 a_runs += 1; // skip the intervalCount; 918 b_runs += 1; // skip the intervalCount; 919 920 // Now a_runs and b_runs to their intervals (or sentinel) 921 922 assert_sentinel(a_top, false); 923 assert_sentinel(a_bot, false); 924 assert_sentinel(b_top, false); 925 assert_sentinel(b_bot, false); 926 927 RgnOper oper(SkMin32(a_top, b_top), dst, op); 928 929 int prevBot = SkRegion_kRunTypeSentinel; // so we fail the first test 930 931 while (a_bot < SkRegion_kRunTypeSentinel || 932 b_bot < SkRegion_kRunTypeSentinel) { 933 int top, bot SK_INIT_TO_AVOID_WARNING; 934 const SkRegionPriv::RunType* run0 = gSentinel; 935 const SkRegionPriv::RunType* run1 = gSentinel; 936 bool a_flush = false; 937 bool b_flush = false; 938 939 if (a_top < b_top) { 940 top = a_top; 941 run0 = a_runs; 942 if (a_bot <= b_top) { // [...] <...> 943 bot = a_bot; 944 a_flush = true; 945 } else { // [...<..]...> or [...<...>...] 946 bot = a_top = b_top; 947 } 948 } else if (b_top < a_top) { 949 top = b_top; 950 run1 = b_runs; 951 if (b_bot <= a_top) { // [...] <...> 952 bot = b_bot; 953 b_flush = true; 954 } else { // [...<..]...> or [...<...>...] 955 bot = b_top = a_top; 956 } 957 } else { // a_top == b_top 958 top = a_top; // or b_top 959 run0 = a_runs; 960 run1 = b_runs; 961 if (a_bot <= b_bot) { 962 bot = b_top = a_bot; 963 a_flush = true; 964 } 965 if (b_bot <= a_bot) { 966 bot = a_top = b_bot; 967 b_flush = true; 968 } 969 } 970 971 if (top > prevBot) { 972 oper.addSpan(top, gSentinel, gSentinel); 973 } 974 oper.addSpan(bot, run0, run1); 975 976 if (quickExit && !oper.isEmpty()) { 977 return QUICK_EXIT_TRUE_COUNT; 978 } 979 980 if (a_flush) { 981 a_runs = skip_intervals(a_runs); 982 a_top = a_bot; 983 a_bot = *a_runs++; 984 a_runs += 1; // skip uninitialized intervalCount 985 if (a_bot == SkRegion_kRunTypeSentinel) { 986 a_top = a_bot; 987 } 988 } 989 if (b_flush) { 990 b_runs = skip_intervals(b_runs); 991 b_top = b_bot; 992 b_bot = *b_runs++; 993 b_runs += 1; // skip uninitialized intervalCount 994 if (b_bot == SkRegion_kRunTypeSentinel) { 995 b_top = b_bot; 996 } 997 } 998 999 prevBot = bot; 1000 } 1001 return oper.flush(); 1002 } 1003 1004 /////////////////////////////////////////////////////////////////////////////// 1005 1006 /* Given count RunTypes in a complex region, return the worst case number of 1007 logical intervals that represents (i.e. number of rects that would be 1008 returned from the iterator). 1009 1010 We could just return count/2, since there must be at least 2 values per 1011 interval, but we can first trim off the const overhead of the initial TOP 1012 value, plus the final BOTTOM + 2 sentinels. 1013 */ 1014 #if 0 // UNUSED 1015 static int count_to_intervals(int count) { 1016 SkASSERT(count >= 6); // a single rect is 6 values 1017 return (count - 4) >> 1; 1018 } 1019 #endif 1020 1021 static bool setEmptyCheck(SkRegion* result) { 1022 return result ? result->setEmpty() : false; 1023 } 1024 1025 static bool setRectCheck(SkRegion* result, const SkIRect& rect) { 1026 return result ? result->setRect(rect) : !rect.isEmpty(); 1027 } 1028 1029 static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) { 1030 return result ? result->setRegion(rgn) : !rgn.isEmpty(); 1031 } 1032 1033 bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op, 1034 SkRegion* result) { 1035 SkASSERT((unsigned)op < kOpCount); 1036 1037 if (kReplace_Op == op) { 1038 return setRegionCheck(result, rgnbOrig); 1039 } 1040 1041 // swith to using pointers, so we can swap them as needed 1042 const SkRegion* rgna = &rgnaOrig; 1043 const SkRegion* rgnb = &rgnbOrig; 1044 // after this point, do not refer to rgnaOrig or rgnbOrig!!! 1045 1046 // collaps difference and reverse-difference into just difference 1047 if (kReverseDifference_Op == op) { 1048 using std::swap; 1049 swap(rgna, rgnb); 1050 op = kDifference_Op; 1051 } 1052 1053 SkIRect bounds; 1054 bool a_empty = rgna->isEmpty(); 1055 bool b_empty = rgnb->isEmpty(); 1056 bool a_rect = rgna->isRect(); 1057 bool b_rect = rgnb->isRect(); 1058 1059 switch (op) { 1060 case kDifference_Op: 1061 if (a_empty) { 1062 return setEmptyCheck(result); 1063 } 1064 if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds, 1065 rgnb->fBounds)) { 1066 return setRegionCheck(result, *rgna); 1067 } 1068 if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) { 1069 return setEmptyCheck(result); 1070 } 1071 break; 1072 1073 case kIntersect_Op: 1074 if ((a_empty | b_empty) 1075 || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) { 1076 return setEmptyCheck(result); 1077 } 1078 if (a_rect & b_rect) { 1079 return setRectCheck(result, bounds); 1080 } 1081 if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { 1082 return setRegionCheck(result, *rgnb); 1083 } 1084 if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { 1085 return setRegionCheck(result, *rgna); 1086 } 1087 break; 1088 1089 case kUnion_Op: 1090 if (a_empty) { 1091 return setRegionCheck(result, *rgnb); 1092 } 1093 if (b_empty) { 1094 return setRegionCheck(result, *rgna); 1095 } 1096 if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { 1097 return setRegionCheck(result, *rgna); 1098 } 1099 if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { 1100 return setRegionCheck(result, *rgnb); 1101 } 1102 break; 1103 1104 case kXOR_Op: 1105 if (a_empty) { 1106 return setRegionCheck(result, *rgnb); 1107 } 1108 if (b_empty) { 1109 return setRegionCheck(result, *rgna); 1110 } 1111 break; 1112 default: 1113 SkDEBUGFAIL("unknown region op"); 1114 return false; 1115 } 1116 1117 RunType tmpA[kRectRegionRuns]; 1118 RunType tmpB[kRectRegionRuns]; 1119 1120 int a_intervals, b_intervals; 1121 const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals); 1122 const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals); 1123 1124 RunArray array; 1125 int count = operate(a_runs, b_runs, &array, op, nullptr == result); 1126 SkASSERT(count <= array.count()); 1127 1128 if (result) { 1129 SkASSERT(count >= 0); 1130 return result->setRuns(&array[0], count); 1131 } else { 1132 return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count); 1133 } 1134 } 1135 1136 bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) { 1137 SkDEBUGCODE(SkRegionPriv::Validate(*this)); 1138 return SkRegion::Oper(rgna, rgnb, op, this); 1139 } 1140 1141 /////////////////////////////////////////////////////////////////////////////// 1142 1143 #include "SkBuffer.h" 1144 1145 size_t SkRegion::writeToMemory(void* storage) const { 1146 if (nullptr == storage) { 1147 size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount 1148 if (!this->isEmpty()) { 1149 size += sizeof(fBounds); 1150 if (this->isComplex()) { 1151 size += 2 * sizeof(int32_t); // ySpanCount + intervalCount 1152 size += fRunHead->fRunCount * sizeof(RunType); 1153 } 1154 } 1155 return size; 1156 } 1157 1158 SkWBuffer buffer(storage); 1159 1160 if (this->isEmpty()) { 1161 buffer.write32(-1); 1162 } else { 1163 bool isRect = this->isRect(); 1164 1165 buffer.write32(isRect ? 0 : fRunHead->fRunCount); 1166 buffer.write(&fBounds, sizeof(fBounds)); 1167 1168 if (!isRect) { 1169 buffer.write32(fRunHead->getYSpanCount()); 1170 buffer.write32(fRunHead->getIntervalCount()); 1171 buffer.write(fRunHead->readonly_runs(), 1172 fRunHead->fRunCount * sizeof(RunType)); 1173 } 1174 } 1175 return buffer.pos(); 1176 } 1177 1178 static bool validate_run_count(int ySpanCount, int intervalCount, int runCount) { 1179 // return 2 + 3 * ySpanCount + 2 * intervalCount; 1180 if (ySpanCount < 1 || intervalCount < 2) { 1181 return false; 1182 } 1183 SkSafeMath safeMath; 1184 int sum = 2; 1185 sum = safeMath.addInt(sum, ySpanCount); 1186 sum = safeMath.addInt(sum, ySpanCount); 1187 sum = safeMath.addInt(sum, ySpanCount); 1188 sum = safeMath.addInt(sum, intervalCount); 1189 sum = safeMath.addInt(sum, intervalCount); 1190 return safeMath && sum == runCount; 1191 } 1192 1193 // Validate that a memory sequence is a valid region. 1194 // Try to check all possible errors. 1195 // never read beyond &runs[runCount-1]. 1196 static bool validate_run(const int32_t* runs, 1197 int runCount, 1198 const SkIRect& givenBounds, 1199 int32_t ySpanCount, 1200 int32_t intervalCount) { 1201 // Region Layout: 1202 // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel 1203 if (!validate_run_count(SkToInt(ySpanCount), SkToInt(intervalCount), runCount)) { 1204 return false; 1205 } 1206 SkASSERT(runCount >= 7); // 7==SkRegion::kRectRegionRuns 1207 // quick sanity check: 1208 if (runs[runCount - 1] != SkRegion_kRunTypeSentinel || 1209 runs[runCount - 2] != SkRegion_kRunTypeSentinel) { 1210 return false; 1211 } 1212 const int32_t* const end = runs + runCount; 1213 SkIRect bounds = {0, 0, 0 ,0}; // calulated bounds 1214 SkIRect rect = {0, 0, 0, 0}; // current rect 1215 rect.fTop = *runs++; 1216 if (rect.fTop == SkRegion_kRunTypeSentinel) { 1217 return false; // no rect can contain SkRegion_kRunTypeSentinel 1218 } 1219 if (rect.fTop != givenBounds.fTop) { 1220 return false; // Must not begin with empty span that does not contribute to bounds. 1221 } 1222 do { 1223 --ySpanCount; 1224 if (ySpanCount < 0) { 1225 return false; // too many yspans 1226 } 1227 rect.fBottom = *runs++; 1228 if (rect.fBottom == SkRegion_kRunTypeSentinel) { 1229 return false; 1230 } 1231 if (rect.fBottom > givenBounds.fBottom) { 1232 return false; // Must not end with empty span that does not contribute to bounds. 1233 } 1234 if (rect.fBottom <= rect.fTop) { 1235 return false; // y-intervals must be ordered; rects must be non-empty. 1236 } 1237 1238 int32_t xIntervals = *runs++; 1239 SkASSERT(runs < end); 1240 if (xIntervals < 0 || xIntervals > intervalCount || runs + 1 + 2 * xIntervals > end) { 1241 return false; 1242 } 1243 intervalCount -= xIntervals; 1244 bool firstInterval = true; 1245 int32_t lastRight = 0; // check that x-intervals are distinct and ordered. 1246 while (xIntervals-- > 0) { 1247 rect.fLeft = *runs++; 1248 rect.fRight = *runs++; 1249 if (rect.fLeft == SkRegion_kRunTypeSentinel || 1250 rect.fRight == SkRegion_kRunTypeSentinel || 1251 rect.fLeft >= rect.fRight || // check non-empty rect 1252 (!firstInterval && rect.fLeft <= lastRight)) { 1253 return false; 1254 } 1255 lastRight = rect.fRight; 1256 firstInterval = false; 1257 bounds.join(rect); 1258 } 1259 if (*runs++ != SkRegion_kRunTypeSentinel) { 1260 return false; // required check sentinal. 1261 } 1262 rect.fTop = rect.fBottom; 1263 SkASSERT(runs < end); 1264 } while (*runs != SkRegion_kRunTypeSentinel); 1265 ++runs; 1266 if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) { 1267 return false; 1268 } 1269 SkASSERT(runs == end); // if ySpanCount && intervalCount are right, must be correct length. 1270 return true; 1271 } 1272 size_t SkRegion::readFromMemory(const void* storage, size_t length) { 1273 SkRBuffer buffer(storage, length); 1274 SkRegion tmp; 1275 int32_t count; 1276 1277 // Serialized Region Format: 1278 // Empty: 1279 // -1 1280 // Simple Rect: 1281 // 0 LEFT TOP RIGHT BOTTOM 1282 // Complex Region: 1283 // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT [RUNS....] 1284 if (!buffer.readS32(&count) || count < -1) { 1285 return 0; 1286 } 1287 if (count >= 0) { 1288 if (!buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)) || tmp.fBounds.isEmpty()) { 1289 return 0; // Short buffer or bad bounds for non-empty region; report failure. 1290 } 1291 if (count == 0) { 1292 tmp.fRunHead = SkRegion_gRectRunHeadPtr; 1293 } else { 1294 int32_t ySpanCount, intervalCount; 1295 if (!buffer.readS32(&ySpanCount) || 1296 !buffer.readS32(&intervalCount) || 1297 buffer.available() < count * sizeof(int32_t)) { 1298 return 0; 1299 } 1300 if (!validate_run((const int32_t*)((const char*)storage + buffer.pos()), count, 1301 tmp.fBounds, ySpanCount, intervalCount)) { 1302 return 0; // invalid runs, don't even allocate 1303 } 1304 tmp.allocateRuns(count, ySpanCount, intervalCount); 1305 SkASSERT(tmp.isComplex()); 1306 SkAssertResult(buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(int32_t))); 1307 } 1308 } 1309 SkASSERT(tmp.isValid()); 1310 SkASSERT(buffer.isValid()); 1311 this->swap(tmp); 1312 return buffer.pos(); 1313 } 1314 1315 /////////////////////////////////////////////////////////////////////////////// 1316 1317 bool SkRegion::isValid() const { 1318 if (this->isEmpty()) { 1319 return fBounds == SkIRect{0, 0, 0, 0}; 1320 } 1321 if (fBounds.isEmpty()) { 1322 return false; 1323 } 1324 if (this->isRect()) { 1325 return true; 1326 } 1327 return fRunHead && fRunHead->fRefCnt > 0 && 1328 validate_run(fRunHead->readonly_runs(), fRunHead->fRunCount, fBounds, 1329 fRunHead->getYSpanCount(), fRunHead->getIntervalCount()); 1330 } 1331 1332 #ifdef SK_DEBUG 1333 void SkRegionPriv::Validate(const SkRegion& rgn) { SkASSERT(rgn.isValid()); } 1334 1335 void SkRegion::dump() const { 1336 if (this->isEmpty()) { 1337 SkDebugf(" rgn: empty\n"); 1338 } else { 1339 SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1340 if (this->isComplex()) { 1341 const RunType* runs = fRunHead->readonly_runs(); 1342 for (int i = 0; i < fRunHead->fRunCount; i++) 1343 SkDebugf(" %d", runs[i]); 1344 } 1345 SkDebugf("\n"); 1346 } 1347 } 1348 1349 #endif 1350 1351 /////////////////////////////////////////////////////////////////////////////// 1352 1353 SkRegion::Iterator::Iterator(const SkRegion& rgn) { 1354 this->reset(rgn); 1355 } 1356 1357 bool SkRegion::Iterator::rewind() { 1358 if (fRgn) { 1359 this->reset(*fRgn); 1360 return true; 1361 } 1362 return false; 1363 } 1364 1365 void SkRegion::Iterator::reset(const SkRegion& rgn) { 1366 fRgn = &rgn; 1367 if (rgn.isEmpty()) { 1368 fDone = true; 1369 } else { 1370 fDone = false; 1371 if (rgn.isRect()) { 1372 fRect = rgn.fBounds; 1373 fRuns = nullptr; 1374 } else { 1375 fRuns = rgn.fRunHead->readonly_runs(); 1376 fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]); 1377 fRuns += 5; 1378 // Now fRuns points to the 2nd interval (or x-sentinel) 1379 } 1380 } 1381 } 1382 1383 void SkRegion::Iterator::next() { 1384 if (fDone) { 1385 return; 1386 } 1387 1388 if (fRuns == nullptr) { // rect case 1389 fDone = true; 1390 return; 1391 } 1392 1393 const RunType* runs = fRuns; 1394 1395 if (runs[0] < SkRegion_kRunTypeSentinel) { // valid X value 1396 fRect.fLeft = runs[0]; 1397 fRect.fRight = runs[1]; 1398 runs += 2; 1399 } else { // we're at the end of a line 1400 runs += 1; 1401 if (runs[0] < SkRegion_kRunTypeSentinel) { // valid Y value 1402 int intervals = runs[1]; 1403 if (0 == intervals) { // empty line 1404 fRect.fTop = runs[0]; 1405 runs += 3; 1406 } else { 1407 fRect.fTop = fRect.fBottom; 1408 } 1409 1410 fRect.fBottom = runs[0]; 1411 assert_sentinel(runs[2], false); 1412 assert_sentinel(runs[3], false); 1413 fRect.fLeft = runs[2]; 1414 fRect.fRight = runs[3]; 1415 runs += 4; 1416 } else { // end of rgn 1417 fDone = true; 1418 } 1419 } 1420 fRuns = runs; 1421 } 1422 1423 SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip) 1424 : fIter(rgn), fClip(clip), fDone(true) { 1425 const SkIRect& r = fIter.rect(); 1426 1427 while (!fIter.done()) { 1428 if (r.fTop >= clip.fBottom) { 1429 break; 1430 } 1431 if (fRect.intersect(clip, r)) { 1432 fDone = false; 1433 break; 1434 } 1435 fIter.next(); 1436 } 1437 } 1438 1439 void SkRegion::Cliperator::next() { 1440 if (fDone) { 1441 return; 1442 } 1443 1444 const SkIRect& r = fIter.rect(); 1445 1446 fDone = true; 1447 fIter.next(); 1448 while (!fIter.done()) { 1449 if (r.fTop >= fClip.fBottom) { 1450 break; 1451 } 1452 if (fRect.intersect(fClip, r)) { 1453 fDone = false; 1454 break; 1455 } 1456 fIter.next(); 1457 } 1458 } 1459 1460 /////////////////////////////////////////////////////////////////////////////// 1461 1462 SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, 1463 int right) { 1464 SkDEBUGCODE(SkRegionPriv::Validate(rgn)); 1465 1466 const SkIRect& r = rgn.getBounds(); 1467 1468 fDone = true; 1469 if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && 1470 right > r.fLeft && left < r.fRight) { 1471 if (rgn.isRect()) { 1472 if (left < r.fLeft) { 1473 left = r.fLeft; 1474 } 1475 if (right > r.fRight) { 1476 right = r.fRight; 1477 } 1478 fLeft = left; 1479 fRight = right; 1480 fRuns = nullptr; // means we're a rect, not a rgn 1481 fDone = false; 1482 } else { 1483 const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y); 1484 runs += 2; // skip Bottom and IntervalCount 1485 for (;;) { 1486 // runs[0..1] is to the right of the span, so we're done 1487 if (runs[0] >= right) { 1488 break; 1489 } 1490 // runs[0..1] is to the left of the span, so continue 1491 if (runs[1] <= left) { 1492 runs += 2; 1493 continue; 1494 } 1495 // runs[0..1] intersects the span 1496 fRuns = runs; 1497 fLeft = left; 1498 fRight = right; 1499 fDone = false; 1500 break; 1501 } 1502 } 1503 } 1504 } 1505 1506 bool SkRegion::Spanerator::next(int* left, int* right) { 1507 if (fDone) { 1508 return false; 1509 } 1510 1511 if (fRuns == nullptr) { // we're a rect 1512 fDone = true; // ok, now we're done 1513 if (left) { 1514 *left = fLeft; 1515 } 1516 if (right) { 1517 *right = fRight; 1518 } 1519 return true; // this interval is legal 1520 } 1521 1522 const SkRegion::RunType* runs = fRuns; 1523 1524 if (runs[0] >= fRight) { 1525 fDone = true; 1526 return false; 1527 } 1528 1529 SkASSERT(runs[1] > fLeft); 1530 1531 if (left) { 1532 *left = SkMax32(fLeft, runs[0]); 1533 } 1534 if (right) { 1535 *right = SkMin32(fRight, runs[1]); 1536 } 1537 fRuns = runs + 2; 1538 return true; 1539 } 1540 1541 /////////////////////////////////////////////////////////////////////////////////////////////////// 1542 1543 static void visit_pairs(int pairCount, int y, const int32_t pairs[], 1544 const std::function<void(const SkIRect&)>& visitor) { 1545 for (int i = 0; i < pairCount; ++i) { 1546 visitor({ pairs[0], y, pairs[1], y + 1 }); 1547 pairs += 2; 1548 } 1549 } 1550 1551 void SkRegionPriv::VisitSpans(const SkRegion& rgn, 1552 const std::function<void(const SkIRect&)>& visitor) { 1553 if (rgn.isEmpty()) { 1554 return; 1555 } 1556 if (rgn.isRect()) { 1557 visitor(rgn.getBounds()); 1558 } else { 1559 const int32_t* p = rgn.fRunHead->readonly_runs(); 1560 int32_t top = *p++; 1561 int32_t bot = *p++; 1562 do { 1563 int pairCount = *p++; 1564 if (pairCount == 1) { 1565 visitor({ p[0], top, p[1], bot }); 1566 p += 2; 1567 } else if (pairCount > 1) { 1568 // we have to loop repeated in Y, sending each interval in Y -> X order 1569 for (int y = top; y < bot; ++y) { 1570 visit_pairs(pairCount, y, p, visitor); 1571 } 1572 p += pairCount * 2; 1573 } 1574 assert_sentinel(*p, true); 1575 p += 1; // skip sentinel 1576 1577 // read next bottom or sentinel 1578 top = bot; 1579 bot = *p++; 1580 } while (!SkRegionValueIsSentinel(bot)); 1581 } 1582 } 1583 1584