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