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