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