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