SkRegion.cpp revision b77b69f89f2551a4a14a30b1a44dd93ea5927bb1
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 (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 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 (this->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 (!this->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 SkASSERT(this->isComplex()); 317 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 SkRegion::RunType scanline_bottom(const SkRegion::RunType runs[]) { 342 return runs[0]; 343} 344 345static const SkRegion::RunType* scanline_next(const SkRegion::RunType runs[]) { 346 // skip [B N [L R]... S] 347 return runs + 2 + runs[1] * 2 + 1; 348} 349 350static bool scanline_contains(const SkRegion::RunType runs[], 351 SkRegion::RunType L, SkRegion::RunType R) { 352 runs += 2; // skip Bottom and IntervalCount 353 for (;;) { 354 if (L < runs[0]) { 355 break; 356 } 357 if (R <= runs[1]) { 358 return true; 359 } 360 runs += 2; 361 } 362 return false; 363} 364 365bool SkRegion::contains(const SkIRect& r) const { 366 SkDEBUGCODE(this->validate();) 367 368 if (!fBounds.contains(r)) { 369 return false; 370 } 371 if (this->isRect()) { 372 return true; 373 } 374 SkASSERT(this->isComplex()); 375 376 const RunType* scanline = fRunHead->findScanline(r.fTop); 377 for (;;) { 378 if (!scanline_contains(scanline, r.fLeft, r.fRight)) { 379 return false; 380 } 381 if (r.fBottom <= scanline_bottom(scanline)) { 382 break; 383 } 384 scanline = scanline_next(scanline); 385 } 386 return true; 387} 388 389bool SkRegion::contains(const SkRegion& rgn) const { 390 SkDEBUGCODE(this->validate();) 391 SkDEBUGCODE(rgn.validate();) 392 393 if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) { 394 return false; 395 } 396 if (this->isRect()) { 397 return true; 398 } 399 if (rgn.isRect()) { 400 return this->contains(rgn.getBounds()); 401 } 402 403 /* 404 * A contains B is equivalent to 405 * B - A == 0 406 */ 407 return !Oper(rgn, *this, kDifference_Op, NULL); 408} 409 410const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], 411 int* intervals) const { 412 SkASSERT(tmpStorage && intervals); 413 const RunType* runs = tmpStorage; 414 415 if (this->isEmpty()) { 416 tmpStorage[0] = kRunTypeSentinel; 417 *intervals = 0; 418 } else if (this->isRect()) { 419 BuildRectRuns(fBounds, tmpStorage); 420 *intervals = 1; 421 } else { 422 runs = fRunHead->readonly_runs(); 423 *intervals = fRunHead->getIntervalCount(); 424 } 425 return runs; 426} 427 428/////////////////////////////////////////////////////////////////////////////// 429 430static bool scanline_intersects(const SkRegion::RunType runs[], 431 SkRegion::RunType L, SkRegion::RunType R) { 432 runs += 2; // skip Bottom and IntervalCount 433 for (;;) { 434 if (R <= runs[0]) { 435 break; 436 } 437 if (L < runs[1]) { 438 return true; 439 } 440 runs += 2; 441 } 442 return false; 443} 444 445bool SkRegion::intersects(const SkIRect& r) const { 446 SkDEBUGCODE(this->validate();) 447 448 if (this->isEmpty() || r.isEmpty()) { 449 return false; 450 } 451 452 SkIRect sect; 453 if (!sect.intersect(fBounds, r)) { 454 return false; 455 } 456 if (this->isRect()) { 457 return true; 458 } 459 SkASSERT(this->isComplex()); 460 461 const RunType* scanline = fRunHead->findScanline(sect.fTop); 462 for (;;) { 463 if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) { 464 return true; 465 } 466 if (sect.fBottom <= scanline_bottom(scanline)) { 467 break; 468 } 469 scanline = scanline_next(scanline); 470 } 471 return false; 472} 473 474bool SkRegion::intersects(const SkRegion& rgn) const { 475 if (this->isEmpty() || rgn.isEmpty()) { 476 return false; 477 } 478 479 if (!SkIRect::Intersects(fBounds, rgn.fBounds)) { 480 return false; 481 } 482 483 bool weAreARect = this->isRect(); 484 bool theyAreARect = rgn.isRect(); 485 486 if (weAreARect && theyAreARect) { 487 return true; 488 } 489 if (weAreARect) { 490 return rgn.intersects(this->getBounds()); 491 } 492 if (theyAreARect) { 493 return this->intersects(rgn.getBounds()); 494 } 495 496 // both of us are complex 497 return Oper(*this, rgn, kIntersect_Op, NULL); 498} 499 500/////////////////////////////////////////////////////////////////////////////// 501 502bool SkRegion::operator==(const SkRegion& b) const { 503 SkDEBUGCODE(validate();) 504 SkDEBUGCODE(b.validate();) 505 506 if (this == &b) { 507 return true; 508 } 509 if (fBounds != b.fBounds) { 510 return false; 511 } 512 513 const SkRegion::RunHead* ah = fRunHead; 514 const SkRegion::RunHead* bh = b.fRunHead; 515 516 // this catches empties and rects being equal 517 if (ah == bh) { 518 return true; 519 } 520 // now we insist that both are complex (but different ptrs) 521 if (!this->isComplex() || !b.isComplex()) { 522 return false; 523 } 524 return ah->fRunCount == bh->fRunCount && 525 !memcmp(ah->readonly_runs(), bh->readonly_runs(), 526 ah->fRunCount * sizeof(SkRegion::RunType)); 527} 528 529void SkRegion::translate(int dx, int dy, SkRegion* dst) const { 530 SkDEBUGCODE(this->validate();) 531 532 if (NULL == dst) { 533 return; 534 } 535 if (this->isEmpty()) { 536 dst->setEmpty(); 537 } else if (this->isRect()) { 538 dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy, 539 fBounds.fRight + dx, fBounds.fBottom + dy); 540 } else { 541 if (this == dst) { 542 dst->fRunHead = dst->fRunHead->ensureWritable(); 543 } else { 544 SkRegion tmp; 545 tmp.allocateRuns(*fRunHead); 546 tmp.fBounds = fBounds; 547 dst->swap(tmp); 548 } 549 550 dst->fBounds.offset(dx, dy); 551 552 const RunType* sruns = fRunHead->readonly_runs(); 553 RunType* druns = dst->fRunHead->writable_runs(); 554 555 *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top 556 for (;;) { 557 int bottom = *sruns++; 558 if (bottom == kRunTypeSentinel) { 559 break; 560 } 561 *druns++ = (SkRegion::RunType)(bottom + dy); // bottom; 562 *druns++ = *sruns++; // copy intervalCount; 563 for (;;) { 564 int x = *sruns++; 565 if (x == kRunTypeSentinel) { 566 break; 567 } 568 *druns++ = (SkRegion::RunType)(x + dx); 569 *druns++ = (SkRegion::RunType)(*sruns++ + dx); 570 } 571 *druns++ = kRunTypeSentinel; // x sentinel 572 } 573 *druns++ = kRunTypeSentinel; // y sentinel 574 575 SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount); 576 SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount); 577 } 578 579 SkDEBUGCODE(this->validate();) 580} 581 582/////////////////////////////////////////////////////////////////////////////// 583 584bool SkRegion::setRects(const SkIRect rects[], int count) { 585 if (0 == count) { 586 this->setEmpty(); 587 } else { 588 this->setRect(rects[0]); 589 for (int i = 1; i < count; i++) { 590 this->op(rects[i], kUnion_Op); 591 } 592 } 593 return !this->isEmpty(); 594} 595 596/////////////////////////////////////////////////////////////////////////////// 597 598#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized 599#pragma warning ( push ) 600#pragma warning ( disable : 4701 ) 601#endif 602 603#ifdef SK_DEBUG 604static void assert_valid_pair(int left, int rite) 605{ 606 SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite); 607} 608#else 609 #define assert_valid_pair(left, rite) 610#endif 611 612struct spanRec { 613 const SkRegion::RunType* fA_runs; 614 const SkRegion::RunType* fB_runs; 615 int fA_left, fA_rite, fB_left, fB_rite; 616 int fLeft, fRite, fInside; 617 618 void init(const SkRegion::RunType a_runs[], 619 const SkRegion::RunType b_runs[]) { 620 fA_left = *a_runs++; 621 fA_rite = *a_runs++; 622 fB_left = *b_runs++; 623 fB_rite = *b_runs++; 624 625 fA_runs = a_runs; 626 fB_runs = b_runs; 627 } 628 629 bool done() const { 630 SkASSERT(fA_left <= SkRegion::kRunTypeSentinel); 631 SkASSERT(fB_left <= SkRegion::kRunTypeSentinel); 632 return fA_left == SkRegion::kRunTypeSentinel && 633 fB_left == SkRegion::kRunTypeSentinel; 634 } 635 636 void next() { 637 assert_valid_pair(fA_left, fA_rite); 638 assert_valid_pair(fB_left, fB_rite); 639 640 int inside, left, rite SK_INIT_TO_AVOID_WARNING; 641 bool a_flush = false; 642 bool b_flush = false; 643 644 int a_left = fA_left; 645 int a_rite = fA_rite; 646 int b_left = fB_left; 647 int b_rite = fB_rite; 648 649 if (a_left < b_left) { 650 inside = 1; 651 left = a_left; 652 if (a_rite <= b_left) { // [...] <...> 653 rite = a_rite; 654 a_flush = true; 655 } else { // [...<..]...> or [...<...>...] 656 rite = a_left = b_left; 657 } 658 } else if (b_left < a_left) { 659 inside = 2; 660 left = b_left; 661 if (b_rite <= a_left) { // [...] <...> 662 rite = b_rite; 663 b_flush = true; 664 } else { // [...<..]...> or [...<...>...] 665 rite = b_left = a_left; 666 } 667 } else { // a_left == b_left 668 inside = 3; 669 left = a_left; // or b_left 670 if (a_rite <= b_rite) { 671 rite = b_left = a_rite; 672 a_flush = true; 673 } 674 if (b_rite <= a_rite) { 675 rite = a_left = b_rite; 676 b_flush = true; 677 } 678 } 679 680 if (a_flush) { 681 a_left = *fA_runs++; 682 a_rite = *fA_runs++; 683 } 684 if (b_flush) { 685 b_left = *fB_runs++; 686 b_rite = *fB_runs++; 687 } 688 689 SkASSERT(left <= rite); 690 691 // now update our state 692 fA_left = a_left; 693 fA_rite = a_rite; 694 fB_left = b_left; 695 fB_rite = b_rite; 696 697 fLeft = left; 698 fRite = rite; 699 fInside = inside; 700 } 701}; 702 703static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[], 704 const SkRegion::RunType b_runs[], 705 SkRegion::RunType dst[], 706 int min, int max) { 707 spanRec rec; 708 bool firstInterval = true; 709 710 rec.init(a_runs, b_runs); 711 712 while (!rec.done()) { 713 rec.next(); 714 715 int left = rec.fLeft; 716 int rite = rec.fRite; 717 718 // add left,rite to our dst buffer (checking for coincidence 719 if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) && 720 left < rite) { // skip if equal 721 if (firstInterval || dst[-1] < left) { 722 *dst++ = (SkRegion::RunType)(left); 723 *dst++ = (SkRegion::RunType)(rite); 724 firstInterval = false; 725 } else { 726 // update the right edge 727 dst[-1] = (SkRegion::RunType)(rite); 728 } 729 } 730 } 731 732 *dst++ = SkRegion::kRunTypeSentinel; 733 return dst; 734} 735 736#if defined _WIN32 && _MSC_VER >= 1300 737#pragma warning ( pop ) 738#endif 739 740static const struct { 741 uint8_t fMin; 742 uint8_t fMax; 743} gOpMinMax[] = { 744 { 1, 1 }, // Difference 745 { 3, 3 }, // Intersection 746 { 1, 3 }, // Union 747 { 1, 2 } // XOR 748}; 749 750class RgnOper { 751public: 752 RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) { 753 // need to ensure that the op enum lines up with our minmax array 754 SkASSERT(SkRegion::kDifference_Op == 0); 755 SkASSERT(SkRegion::kIntersect_Op == 1); 756 SkASSERT(SkRegion::kUnion_Op == 2); 757 SkASSERT(SkRegion::kXOR_Op == 3); 758 SkASSERT((unsigned)op <= 3); 759 760 fStartDst = dst; 761 fPrevDst = dst + 1; 762 fPrevLen = 0; // will never match a length from operate_on_span 763 fTop = (SkRegion::RunType)(top); // just a first guess, we might update this 764 765 fMin = gOpMinMax[op].fMin; 766 fMax = gOpMinMax[op].fMax; 767 } 768 769 void addSpan(int bottom, const SkRegion::RunType a_runs[], 770 const SkRegion::RunType b_runs[]) { 771 // skip X values and slots for the next Y+intervalCount 772 SkRegion::RunType* start = fPrevDst + fPrevLen + 2; 773 // start points to beginning of dst interval 774 SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax); 775 size_t len = stop - start; 776 SkASSERT(len >= 1 && (len & 1) == 1); 777 SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]); 778 779 if (fPrevLen == len && 780 (1 == len || !memcmp(fPrevDst, start, 781 (len - 1) * sizeof(SkRegion::RunType)))) { 782 // update Y value 783 fPrevDst[-2] = (SkRegion::RunType)(bottom); 784 } else { // accept the new span 785 if (len == 1 && fPrevLen == 0) { 786 fTop = (SkRegion::RunType)(bottom); // just update our bottom 787 } else { 788 start[-2] = (SkRegion::RunType)(bottom); 789 start[-1] = len >> 1; 790 fPrevDst = start; 791 fPrevLen = len; 792 } 793 } 794 } 795 796 int flush() { 797 fStartDst[0] = fTop; 798 fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel; 799 return (int)(fPrevDst - fStartDst + fPrevLen + 1); 800 } 801 802 bool isEmpty() const { return 0 == fPrevLen; } 803 804 uint8_t fMin, fMax; 805 806private: 807 SkRegion::RunType* fStartDst; 808 SkRegion::RunType* fPrevDst; 809 size_t fPrevLen; 810 SkRegion::RunType fTop; 811}; 812 813// want a unique value to signal that we exited due to quickExit 814#define QUICK_EXIT_TRUE_COUNT (-1) 815 816static int operate(const SkRegion::RunType a_runs[], 817 const SkRegion::RunType b_runs[], 818 SkRegion::RunType dst[], 819 SkRegion::Op op, 820 bool quickExit) { 821 const SkRegion::RunType gEmptyScanline[] = { 822 0, // dummy bottom value 823 0, // zero intervals 824 SkRegion::kRunTypeSentinel, 825 // just need a 2nd value, since spanRec.init() reads 2 values, even 826 // though if the first value is the sentinel, it ignores the 2nd value. 827 // w/o the 2nd value here, we might read uninitialized memory. 828 // This happens when we are using gSentinel, which is pointing at 829 // our sentinel value. 830 0 831 }; 832 const SkRegion::RunType* const gSentinel = &gEmptyScanline[2]; 833 834 int a_top = *a_runs++; 835 int a_bot = *a_runs++; 836 int b_top = *b_runs++; 837 int b_bot = *b_runs++; 838 839 a_runs += 1; // skip the intervalCount; 840 b_runs += 1; // skip the intervalCount; 841 842 // Now a_runs and b_runs to their intervals (or sentinel) 843 844 assert_sentinel(a_top, false); 845 assert_sentinel(a_bot, false); 846 assert_sentinel(b_top, false); 847 assert_sentinel(b_bot, false); 848 849 RgnOper oper(SkMin32(a_top, b_top), dst, op); 850 851 bool firstInterval = true; 852 int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test 853 854 while (a_bot < SkRegion::kRunTypeSentinel || 855 b_bot < SkRegion::kRunTypeSentinel) { 856 int top, bot SK_INIT_TO_AVOID_WARNING; 857 const SkRegion::RunType* run0 = gSentinel; 858 const SkRegion::RunType* run1 = gSentinel; 859 bool a_flush = false; 860 bool b_flush = false; 861 862 if (a_top < b_top) { 863 top = a_top; 864 run0 = a_runs; 865 if (a_bot <= b_top) { // [...] <...> 866 bot = a_bot; 867 a_flush = true; 868 } else { // [...<..]...> or [...<...>...] 869 bot = a_top = b_top; 870 } 871 } else if (b_top < a_top) { 872 top = b_top; 873 run1 = b_runs; 874 if (b_bot <= a_top) { // [...] <...> 875 bot = b_bot; 876 b_flush = true; 877 } else { // [...<..]...> or [...<...>...] 878 bot = b_top = a_top; 879 } 880 } else { // a_top == b_top 881 top = a_top; // or b_top 882 run0 = a_runs; 883 run1 = b_runs; 884 if (a_bot <= b_bot) { 885 bot = b_top = a_bot; 886 a_flush = true; 887 } 888 if (b_bot <= a_bot) { 889 bot = a_top = b_bot; 890 b_flush = true; 891 } 892 } 893 894 if (top > prevBot) { 895 oper.addSpan(top, gSentinel, gSentinel); 896 } 897 oper.addSpan(bot, run0, run1); 898 firstInterval = false; 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 break; 1025 1026 case kUnion_Op: 1027 if (a_empty) { 1028 return setRegionCheck(result, *rgnb); 1029 } 1030 if (b_empty) { 1031 return setRegionCheck(result, *rgna); 1032 } 1033 if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { 1034 return setRegionCheck(result, *rgna); 1035 } 1036 if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { 1037 return setRegionCheck(result, *rgnb); 1038 } 1039 break; 1040 1041 case kXOR_Op: 1042 if (a_empty) { 1043 return setRegionCheck(result, *rgnb); 1044 } 1045 if (b_empty) { 1046 return setRegionCheck(result, *rgna); 1047 } 1048 break; 1049 default: 1050 SkDEBUGFAIL("unknown region op"); 1051 return false; 1052 } 1053 1054 RunType tmpA[kRectRegionRuns]; 1055 RunType tmpB[kRectRegionRuns]; 1056 1057 int a_intervals, b_intervals; 1058 const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals); 1059 const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals); 1060 1061 int dstCount = compute_worst_case_count(a_intervals, b_intervals); 1062 SkAutoSTMalloc<256, RunType> array(dstCount); 1063 1064#ifdef SK_DEBUG 1065// Sometimes helpful to seed everything with a known value when debugging 1066// sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount); 1067#endif 1068 1069 int count = operate(a_runs, b_runs, array.get(), op, NULL == result); 1070 SkASSERT(count <= dstCount); 1071 1072 if (result) { 1073 SkASSERT(count >= 0); 1074 return result->setRuns(array.get(), count); 1075 } else { 1076 return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count); 1077 } 1078} 1079 1080bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) { 1081 SkDEBUGCODE(this->validate();) 1082 return SkRegion::Oper(rgna, rgnb, op, this); 1083} 1084 1085/////////////////////////////////////////////////////////////////////////////// 1086 1087#include "SkBuffer.h" 1088 1089uint32_t SkRegion::writeToMemory(void* storage) const { 1090 if (NULL == storage) { 1091 uint32_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount 1092 if (!this->isEmpty()) { 1093 size += sizeof(fBounds); 1094 if (this->isComplex()) { 1095 size += 2 * sizeof(int32_t); // ySpanCount + intervalCount 1096 size += fRunHead->fRunCount * sizeof(RunType); 1097 } 1098 } 1099 return size; 1100 } 1101 1102 SkWBuffer buffer(storage); 1103 1104 if (this->isEmpty()) { 1105 buffer.write32(-1); 1106 } else { 1107 bool isRect = this->isRect(); 1108 1109 buffer.write32(isRect ? 0 : fRunHead->fRunCount); 1110 buffer.write(&fBounds, sizeof(fBounds)); 1111 1112 if (!isRect) { 1113 buffer.write32(fRunHead->getYSpanCount()); 1114 buffer.write32(fRunHead->getIntervalCount()); 1115 buffer.write(fRunHead->readonly_runs(), 1116 fRunHead->fRunCount * sizeof(RunType)); 1117 } 1118 } 1119 return buffer.pos(); 1120} 1121 1122uint32_t SkRegion::readFromMemory(const void* storage) { 1123 SkRBuffer buffer(storage); 1124 SkRegion tmp; 1125 int32_t count; 1126 1127 count = buffer.readS32(); 1128 if (count >= 0) { 1129 buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)); 1130 if (count == 0) { 1131 tmp.fRunHead = SkRegion_gRectRunHeadPtr; 1132 } else { 1133 int32_t ySpanCount = buffer.readS32(); 1134 int32_t intervalCount = buffer.readS32(); 1135 tmp.allocateRuns(count, ySpanCount, intervalCount); 1136 buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType)); 1137 } 1138 } 1139 this->swap(tmp); 1140 return buffer.pos(); 1141} 1142 1143/////////////////////////////////////////////////////////////////////////////// 1144 1145const SkRegion& SkRegion::GetEmptyRegion() { 1146 static SkRegion gEmpty; 1147 return gEmpty; 1148} 1149 1150/////////////////////////////////////////////////////////////////////////////// 1151 1152#ifdef SK_DEBUG 1153 1154// Starts with first X-interval, and returns a ptr to the X-sentinel 1155static const SkRegion::RunType* skip_intervals_slow(const SkRegion::RunType runs[]) { 1156 // want to track that our intevals are all disjoint, such that 1157 // prev-right < next-left. We rely on this optimization in places such as 1158 // contains(). 1159 // 1160 SkRegion::RunType prevR = -SkRegion::kRunTypeSentinel; 1161 1162 while (runs[0] < SkRegion::kRunTypeSentinel) { 1163 SkASSERT(prevR < runs[0]); 1164 SkASSERT(runs[0] < runs[1]); 1165 SkASSERT(runs[1] < SkRegion::kRunTypeSentinel); 1166 prevR = runs[1]; 1167 runs += 2; 1168 } 1169 return runs; 1170} 1171 1172static void compute_bounds(const SkRegion::RunType runs[], int count, 1173 SkIRect* bounds, int* ySpanCountPtr, 1174 int* intervalCountPtr) { 1175 assert_sentinel(runs[0], false); // top 1176 1177 int left = SK_MaxS32; 1178 int rite = SK_MinS32; 1179 int bot; 1180 int ySpanCount = 0; 1181 int intervalCount = 0; 1182 1183 bounds->fTop = *runs++; 1184 do { 1185 bot = *runs++; 1186 SkASSERT(SkRegion::kRunTypeSentinel > bot); 1187 1188 ySpanCount += 1; 1189 1190 runs += 1; // skip intervalCount for now 1191 if (*runs < SkRegion::kRunTypeSentinel) { 1192 if (left > *runs) { 1193 left = *runs; 1194 } 1195 1196 const SkRegion::RunType* prev = runs; 1197 runs = skip_intervals_slow(runs); 1198 int intervals = (runs - prev) >> 1; 1199 SkASSERT(prev[-1] == intervals); 1200 intervalCount += intervals; 1201 1202 if (rite < runs[-1]) { 1203 rite = runs[-1]; 1204 } 1205 } else { 1206 SkASSERT(0 == runs[-1]); // no intervals 1207 } 1208 SkASSERT(SkRegion::kRunTypeSentinel == *runs); 1209 runs += 1; 1210 } while (SkRegion::kRunTypeSentinel != *runs); 1211 1212 bounds->fLeft = left; 1213 bounds->fRight = rite; 1214 bounds->fBottom = bot; 1215 *ySpanCountPtr = ySpanCount; 1216 *intervalCountPtr = intervalCount; 1217} 1218 1219void SkRegion::validate() const { 1220 if (this->isEmpty()) { 1221 // check for explicit empty (the zero rect), so we can compare rects to know when 1222 // two regions are equal (i.e. emptyRectA == emptyRectB) 1223 // this is stricter than just asserting fBounds.isEmpty() 1224 SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0); 1225 } else { 1226 SkASSERT(!fBounds.isEmpty()); 1227 if (!this->isRect()) { 1228 SkASSERT(fRunHead->fRefCnt >= 1); 1229 SkASSERT(fRunHead->fRunCount > kRectRegionRuns); 1230 1231 const RunType* run = fRunHead->readonly_runs(); 1232 const RunType* stop = run + fRunHead->fRunCount; 1233 1234 // check that our bounds match our runs 1235 { 1236 SkIRect bounds; 1237 int ySpanCount, intervalCount; 1238 compute_bounds(run, stop - run, &bounds, &ySpanCount, &intervalCount); 1239 1240 SkASSERT(bounds == fBounds); 1241 SkASSERT(ySpanCount > 0); 1242 SkASSERT(fRunHead->getYSpanCount() == ySpanCount); 1243 // SkASSERT(intervalCount > 1); 1244 SkASSERT(fRunHead->getIntervalCount() == intervalCount); 1245 } 1246 } 1247 } 1248} 1249 1250void SkRegion::dump() const { 1251 if (this->isEmpty()) { 1252 SkDebugf(" rgn: empty\n"); 1253 } else { 1254 SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1255 if (this->isComplex()) { 1256 const RunType* runs = fRunHead->readonly_runs(); 1257 for (int i = 0; i < fRunHead->fRunCount; i++) 1258 SkDebugf(" %d", runs[i]); 1259 } 1260 SkDebugf("\n"); 1261 } 1262} 1263 1264#endif 1265 1266/////////////////////////////////////////////////////////////////////////////// 1267 1268SkRegion::Iterator::Iterator(const SkRegion& rgn) { 1269 this->reset(rgn); 1270} 1271 1272bool SkRegion::Iterator::rewind() { 1273 if (fRgn) { 1274 this->reset(*fRgn); 1275 return true; 1276 } 1277 return false; 1278} 1279 1280void SkRegion::Iterator::reset(const SkRegion& rgn) { 1281 fRgn = &rgn; 1282 if (rgn.isEmpty()) { 1283 fDone = true; 1284 } else { 1285 fDone = false; 1286 if (rgn.isRect()) { 1287 fRect = rgn.fBounds; 1288 fRuns = NULL; 1289 } else { 1290 fRuns = rgn.fRunHead->readonly_runs(); 1291 fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]); 1292 fRuns += 5; 1293 // Now fRuns points to the 2nd interval (or x-sentinel) 1294 } 1295 } 1296} 1297 1298void SkRegion::Iterator::next() { 1299 if (fDone) { 1300 return; 1301 } 1302 1303 if (fRuns == NULL) { // rect case 1304 fDone = true; 1305 return; 1306 } 1307 1308 const RunType* runs = fRuns; 1309 1310 if (runs[0] < kRunTypeSentinel) { // valid X value 1311 fRect.fLeft = runs[0]; 1312 fRect.fRight = runs[1]; 1313 runs += 2; 1314 } else { // we're at the end of a line 1315 runs += 1; 1316 if (runs[0] < kRunTypeSentinel) { // valid Y value 1317 int intervals = runs[1]; 1318 if (0 == intervals) { // empty line 1319 fRect.fTop = runs[0]; 1320 runs += 3; 1321 } else { 1322 fRect.fTop = fRect.fBottom; 1323 } 1324 1325 fRect.fBottom = runs[0]; 1326 assert_sentinel(runs[2], false); 1327 assert_sentinel(runs[3], false); 1328 fRect.fLeft = runs[2]; 1329 fRect.fRight = runs[3]; 1330 runs += 4; 1331 } else { // end of rgn 1332 fDone = true; 1333 } 1334 } 1335 fRuns = runs; 1336} 1337 1338SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip) 1339 : fIter(rgn), fClip(clip), fDone(true) { 1340 const SkIRect& r = fIter.rect(); 1341 1342 while (!fIter.done()) { 1343 if (r.fTop >= clip.fBottom) { 1344 break; 1345 } 1346 if (fRect.intersect(clip, r)) { 1347 fDone = false; 1348 break; 1349 } 1350 fIter.next(); 1351 } 1352} 1353 1354void SkRegion::Cliperator::next() { 1355 if (fDone) { 1356 return; 1357 } 1358 1359 const SkIRect& r = fIter.rect(); 1360 1361 fDone = true; 1362 fIter.next(); 1363 while (!fIter.done()) { 1364 if (r.fTop >= fClip.fBottom) { 1365 break; 1366 } 1367 if (fRect.intersect(fClip, r)) { 1368 fDone = false; 1369 break; 1370 } 1371 fIter.next(); 1372 } 1373} 1374 1375/////////////////////////////////////////////////////////////////////////////// 1376 1377SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, 1378 int right) { 1379 SkDEBUGCODE(rgn.validate();) 1380 1381 const SkIRect& r = rgn.getBounds(); 1382 1383 fDone = true; 1384 if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && 1385 right > r.fLeft && left < r.fRight) { 1386 if (rgn.isRect()) { 1387 if (left < r.fLeft) { 1388 left = r.fLeft; 1389 } 1390 if (right > r.fRight) { 1391 right = r.fRight; 1392 } 1393 fLeft = left; 1394 fRight = right; 1395 fRuns = NULL; // means we're a rect, not a rgn 1396 fDone = false; 1397 } else { 1398 const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y); 1399 runs += 2; // skip Bottom and IntervalCount 1400 for (;;) { 1401 // runs[0..1] is to the right of the span, so we're done 1402 if (runs[0] >= right) { 1403 break; 1404 } 1405 // runs[0..1] is to the left of the span, so continue 1406 if (runs[1] <= left) { 1407 runs += 2; 1408 continue; 1409 } 1410 // runs[0..1] intersects the span 1411 fRuns = runs; 1412 fLeft = left; 1413 fRight = right; 1414 fDone = false; 1415 break; 1416 } 1417 } 1418 } 1419} 1420 1421bool SkRegion::Spanerator::next(int* left, int* right) { 1422 if (fDone) { 1423 return false; 1424 } 1425 1426 if (fRuns == NULL) { // we're a rect 1427 fDone = true; // ok, now we're done 1428 if (left) { 1429 *left = fLeft; 1430 } 1431 if (right) { 1432 *right = fRight; 1433 } 1434 return true; // this interval is legal 1435 } 1436 1437 const SkRegion::RunType* runs = fRuns; 1438 1439 if (runs[0] >= fRight) { 1440 fDone = true; 1441 return false; 1442 } 1443 1444 SkASSERT(runs[1] > fLeft); 1445 1446 if (left) { 1447 *left = SkMax32(fLeft, runs[0]); 1448 } 1449 if (right) { 1450 *right = SkMin32(fRight, runs[1]); 1451 } 1452 fRuns = runs + 2; 1453 return true; 1454} 1455 1456/////////////////////////////////////////////////////////////////////////////// 1457 1458#ifdef SK_DEBUG 1459 1460bool SkRegion::debugSetRuns(const RunType runs[], int count) { 1461 // we need to make a copy, since the real method may modify the array, and 1462 // so it cannot be const. 1463 1464 SkAutoTArray<RunType> storage(count); 1465 memcpy(storage.get(), runs, count * sizeof(RunType)); 1466 return this->setRuns(storage.get(), count); 1467} 1468 1469#endif 1470