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