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