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