SkRegion.cpp revision cb34235f46b6259b612e72c416e850e26803250a
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(int32_t x, int32_t 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 558bool SkRegion::setRects(const SkIRect rects[], int count) { 559 if (0 == count) { 560 this->setEmpty(); 561 } else { 562 this->setRect(rects[0]); 563 for (int i = 1; i < count; i++) { 564 this->op(rects[i], kUnion_Op); 565 } 566 } 567 return !this->isEmpty(); 568} 569 570/////////////////////////////////////////////////////////////////////////////// 571 572#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized 573#pragma warning ( push ) 574#pragma warning ( disable : 4701 ) 575#endif 576 577#ifdef SK_DEBUG 578static void assert_valid_pair(int left, int rite) 579{ 580 SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite); 581} 582#else 583 #define assert_valid_pair(left, rite) 584#endif 585 586struct spanRec { 587 const SkRegion::RunType* fA_runs; 588 const SkRegion::RunType* fB_runs; 589 int fA_left, fA_rite, fB_left, fB_rite; 590 int fLeft, fRite, fInside; 591 592 void init(const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[]) 593 { 594 fA_left = *a_runs++; 595 fA_rite = *a_runs++; 596 fB_left = *b_runs++; 597 fB_rite = *b_runs++; 598 599 fA_runs = a_runs; 600 fB_runs = b_runs; 601 } 602 603 bool done() const 604 { 605 SkASSERT(fA_left <= SkRegion::kRunTypeSentinel); 606 SkASSERT(fB_left <= SkRegion::kRunTypeSentinel); 607 return fA_left == SkRegion::kRunTypeSentinel && fB_left == SkRegion::kRunTypeSentinel; 608 } 609 610 void next() 611 { 612 assert_valid_pair(fA_left, fA_rite); 613 assert_valid_pair(fB_left, fB_rite); 614 615 int inside, left, rite SK_INIT_TO_AVOID_WARNING; 616 bool a_flush = false; 617 bool b_flush = false; 618 619 int a_left = fA_left; 620 int a_rite = fA_rite; 621 int b_left = fB_left; 622 int b_rite = fB_rite; 623 624 if (a_left < b_left) 625 { 626 inside = 1; 627 left = a_left; 628 if (a_rite <= b_left) // [...] <...> 629 { 630 rite = a_rite; 631 a_flush = true; 632 } 633 else // [...<..]...> or [...<...>...] 634 rite = a_left = b_left; 635 } 636 else if (b_left < a_left) 637 { 638 inside = 2; 639 left = b_left; 640 if (b_rite <= a_left) // [...] <...> 641 { 642 rite = b_rite; 643 b_flush = true; 644 } 645 else // [...<..]...> or [...<...>...] 646 rite = b_left = a_left; 647 } 648 else // a_left == b_left 649 { 650 inside = 3; 651 left = a_left; // or b_left 652 if (a_rite <= b_rite) 653 { 654 rite = b_left = a_rite; 655 a_flush = true; 656 } 657 if (b_rite <= a_rite) 658 { 659 rite = a_left = b_rite; 660 b_flush = true; 661 } 662 } 663 664 if (a_flush) 665 { 666 a_left = *fA_runs++; 667 a_rite = *fA_runs++; 668 } 669 if (b_flush) 670 { 671 b_left = *fB_runs++; 672 b_rite = *fB_runs++; 673 } 674 675 SkASSERT(left <= rite); 676 677 // now update our state 678 fA_left = a_left; 679 fA_rite = a_rite; 680 fB_left = b_left; 681 fB_rite = b_rite; 682 683 fLeft = left; 684 fRite = rite; 685 fInside = inside; 686 } 687}; 688 689static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[], 690 const SkRegion::RunType b_runs[], 691 SkRegion::RunType dst[], 692 int min, int max) 693{ 694 spanRec rec; 695 bool firstInterval = true; 696 697 rec.init(a_runs, b_runs); 698 699 while (!rec.done()) 700 { 701 rec.next(); 702 703 int left = rec.fLeft; 704 int rite = rec.fRite; 705 706 // add left,rite to our dst buffer (checking for coincidence 707 if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) && 708 left < rite) // skip if equal 709 { 710 if (firstInterval || dst[-1] < left) 711 { 712 *dst++ = (SkRegion::RunType)(left); 713 *dst++ = (SkRegion::RunType)(rite); 714 firstInterval = false; 715 } 716 else // update the right edge 717 dst[-1] = (SkRegion::RunType)(rite); 718 } 719 } 720 721 *dst++ = SkRegion::kRunTypeSentinel; 722 return dst; 723} 724 725#if defined _WIN32 && _MSC_VER >= 1300 726#pragma warning ( pop ) 727#endif 728 729static const struct { 730 uint8_t fMin; 731 uint8_t fMax; 732} gOpMinMax[] = { 733 { 1, 1 }, // Difference 734 { 3, 3 }, // Intersection 735 { 1, 3 }, // Union 736 { 1, 2 } // XOR 737}; 738 739class RgnOper { 740public: 741 RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) 742 { 743 // need to ensure that the op enum lines up with our minmax array 744 SkASSERT(SkRegion::kDifference_Op == 0); 745 SkASSERT(SkRegion::kIntersect_Op == 1); 746 SkASSERT(SkRegion::kUnion_Op == 2); 747 SkASSERT(SkRegion::kXOR_Op == 3); 748 SkASSERT((unsigned)op <= 3); 749 750 fStartDst = dst; 751 fPrevDst = dst + 1; 752 fPrevLen = 0; // will never match a length from operate_on_span 753 fTop = (SkRegion::RunType)(top); // just a first guess, we might update this 754 755 fMin = gOpMinMax[op].fMin; 756 fMax = gOpMinMax[op].fMax; 757 } 758 759 void addSpan(int bottom, const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[]) 760 { 761 SkRegion::RunType* start = fPrevDst + fPrevLen + 1; // skip X values and slot for the next Y 762 SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax); 763 size_t len = stop - start; 764 765 if (fPrevLen == len && !memcmp(fPrevDst, start, len * sizeof(SkRegion::RunType))) // update Y value 766 fPrevDst[-1] = (SkRegion::RunType)(bottom); 767 else // accept the new span 768 { 769 if (len == 1 && fPrevLen == 0) { 770 fTop = (SkRegion::RunType)(bottom); // just update our bottom 771 } else { 772 start[-1] = (SkRegion::RunType)(bottom); 773 fPrevDst = start; 774 fPrevLen = len; 775 } 776 } 777 } 778 779 int flush() 780 { 781 fStartDst[0] = fTop; 782 fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel; 783 return (int)(fPrevDst - fStartDst + fPrevLen + 1); 784 } 785 786 uint8_t fMin, fMax; 787 788private: 789 SkRegion::RunType* fStartDst; 790 SkRegion::RunType* fPrevDst; 791 size_t fPrevLen; 792 SkRegion::RunType fTop; 793}; 794 795static int operate( const SkRegion::RunType a_runs[], 796 const SkRegion::RunType b_runs[], 797 SkRegion::RunType dst[], 798 SkRegion::Op op) 799{ 800 const SkRegion::RunType gSentinel[] = { 801 SkRegion::kRunTypeSentinel, 802 // just need a 2nd value, since spanRec.init() reads 2 values, even 803 // though if the first value is the sentinel, it ignores the 2nd value. 804 // w/o the 2nd value here, we might read uninitialized memory. 805 0, 806 }; 807 808 int a_top = *a_runs++; 809 int a_bot = *a_runs++; 810 int b_top = *b_runs++; 811 int b_bot = *b_runs++; 812 813 assert_sentinel(a_top, false); 814 assert_sentinel(a_bot, false); 815 assert_sentinel(b_top, false); 816 assert_sentinel(b_bot, false); 817 818 RgnOper oper(SkMin32(a_top, b_top), dst, op); 819 820 bool firstInterval = true; 821 int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test 822 823 while (a_bot < SkRegion::kRunTypeSentinel || b_bot < SkRegion::kRunTypeSentinel) 824 { 825 int top, bot SK_INIT_TO_AVOID_WARNING; 826 const SkRegion::RunType* run0 = gSentinel; 827 const SkRegion::RunType* run1 = gSentinel; 828 bool a_flush = false; 829 bool b_flush = false; 830 int inside; 831 832 if (a_top < b_top) 833 { 834 inside = 1; 835 top = a_top; 836 run0 = a_runs; 837 if (a_bot <= b_top) // [...] <...> 838 { 839 bot = a_bot; 840 a_flush = true; 841 } 842 else // [...<..]...> or [...<...>...] 843 bot = a_top = b_top; 844 } 845 else if (b_top < a_top) 846 { 847 inside = 2; 848 top = b_top; 849 run1 = b_runs; 850 if (b_bot <= a_top) // [...] <...> 851 { 852 bot = b_bot; 853 b_flush = true; 854 } 855 else // [...<..]...> or [...<...>...] 856 bot = b_top = a_top; 857 } 858 else // a_top == b_top 859 { 860 inside = 3; 861 top = a_top; // or b_top 862 run0 = a_runs; 863 run1 = b_runs; 864 if (a_bot <= b_bot) 865 { 866 bot = b_top = a_bot; 867 a_flush = true; 868 } 869 if (b_bot <= a_bot) 870 { 871 bot = a_top = b_bot; 872 b_flush = true; 873 } 874 } 875 876 if (top > prevBot) 877 oper.addSpan(top, gSentinel, gSentinel); 878 879// if ((unsigned)(inside - oper.fMin) <= (unsigned)(oper.fMax - oper.fMin)) 880 { 881 oper.addSpan(bot, run0, run1); 882 firstInterval = false; 883 } 884 885 if (a_flush) 886 { 887 a_runs = skip_scanline(a_runs); 888 a_top = a_bot; 889 a_bot = *a_runs++; 890 if (a_bot == SkRegion::kRunTypeSentinel) 891 a_top = a_bot; 892 } 893 if (b_flush) 894 { 895 b_runs = skip_scanline(b_runs); 896 b_top = b_bot; 897 b_bot = *b_runs++; 898 if (b_bot == SkRegion::kRunTypeSentinel) 899 b_top = b_bot; 900 } 901 902 prevBot = bot; 903 } 904 return oper.flush(); 905} 906 907/////////////////////////////////////////////////////////////////////////////// 908 909/* Given count RunTypes in a complex region, return the worst case number of 910 logical intervals that represents (i.e. number of rects that would be 911 returned from the iterator). 912 913 We could just return count/2, since there must be at least 2 values per 914 interval, but we can first trim off the const overhead of the initial TOP 915 value, plus the final BOTTOM + 2 sentinels. 916 */ 917static int count_to_intervals(int count) { 918 SkASSERT(count >= 6); // a single rect is 6 values 919 return (count - 4) >> 1; 920} 921 922/* Given a number of intervals, what is the worst case representation of that 923 many intervals? 924 925 Worst case (from a storage perspective), is a vertical stack of single 926 intervals: TOP + N * (BOTTOM LEFT RIGHT SENTINEL) + SENTINEL 927 */ 928static int intervals_to_count(int intervals) { 929 return 1 + intervals * 4 + 1; 930} 931 932/* Given the counts of RunTypes in two regions, return the worst-case number 933 of RunTypes need to store the result after a region-op. 934 */ 935static int compute_worst_case_count(int a_count, int b_count) { 936 int a_intervals = count_to_intervals(a_count); 937 int b_intervals = count_to_intervals(b_count); 938 // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1) 939 int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals; 940 // convert back to number of RunType values 941 return intervals_to_count(intervals); 942} 943 944bool SkRegion::op(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op) 945{ 946 SkDEBUGCODE(this->validate();) 947 948 SkASSERT((unsigned)op < kOpCount); 949 950 if (kReplace_Op == op) 951 return this->set(rgnbOrig); 952 953 // swith to using pointers, so we can swap them as needed 954 const SkRegion* rgna = &rgnaOrig; 955 const SkRegion* rgnb = &rgnbOrig; 956 // after this point, do not refer to rgnaOrig or rgnbOrig!!! 957 958 // collaps difference and reverse-difference into just difference 959 if (kReverseDifference_Op == op) 960 { 961 SkTSwap<const SkRegion*>(rgna, rgnb); 962 op = kDifference_Op; 963 } 964 965 SkIRect bounds; 966 bool a_empty = rgna->isEmpty(); 967 bool b_empty = rgnb->isEmpty(); 968 bool a_rect = rgna->isRect(); 969 bool b_rect = rgnb->isRect(); 970 971 switch (op) { 972 case kDifference_Op: 973 if (a_empty) 974 return this->setEmpty(); 975 if (b_empty || !SkIRect::Intersects(rgna->fBounds, rgnb->fBounds)) 976 return this->setRegion(*rgna); 977 break; 978 979 case kIntersect_Op: 980 if ((a_empty | b_empty) 981 || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) 982 return this->setEmpty(); 983 if (a_rect & b_rect) 984 return this->setRect(bounds); 985 break; 986 987 case kUnion_Op: 988 if (a_empty) 989 return this->setRegion(*rgnb); 990 if (b_empty) 991 return this->setRegion(*rgna); 992 if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) 993 return this->setRegion(*rgna); 994 if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) 995 return this->setRegion(*rgnb); 996 break; 997 998 case kXOR_Op: 999 if (a_empty) 1000 return this->setRegion(*rgnb); 1001 if (b_empty) 1002 return this->setRegion(*rgna); 1003 break; 1004 default: 1005 SkASSERT(!"unknown region op"); 1006 return !this->isEmpty(); 1007 } 1008 1009 RunType tmpA[kRectRegionRuns]; 1010 RunType tmpB[kRectRegionRuns]; 1011 1012 int a_count, b_count; 1013 const RunType* a_runs = rgna->getRuns(tmpA, &a_count); 1014 const RunType* b_runs = rgnb->getRuns(tmpB, &b_count); 1015 1016 int dstCount = compute_worst_case_count(a_count, b_count); 1017 SkAutoSTMalloc<32, RunType> array(dstCount); 1018 1019 int count = operate(a_runs, b_runs, array.get(), op); 1020 SkASSERT(count <= dstCount); 1021 return this->setRuns(array.get(), count); 1022} 1023 1024////////////////////////////////////////////////////////////////////////////////////////////////////////// 1025 1026#include "SkBuffer.h" 1027 1028uint32_t SkRegion::flatten(void* storage) const { 1029 if (NULL == storage) { 1030 uint32_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount 1031 if (!this->isEmpty()) { 1032 size += sizeof(fBounds); 1033 if (this->isComplex()) { 1034 size += fRunHead->fRunCount * sizeof(RunType); 1035 } 1036 } 1037 return size; 1038 } 1039 1040 SkWBuffer buffer(storage); 1041 1042 if (this->isEmpty()) { 1043 buffer.write32(-1); 1044 } else { 1045 bool isRect = this->isRect(); 1046 1047 buffer.write32(isRect ? 0 : fRunHead->fRunCount); 1048 buffer.write(&fBounds, sizeof(fBounds)); 1049 1050 if (!isRect) { 1051 buffer.write(fRunHead->readonly_runs(), 1052 fRunHead->fRunCount * sizeof(RunType)); 1053 } 1054 } 1055 return buffer.pos(); 1056} 1057 1058uint32_t SkRegion::unflatten(const void* storage) { 1059 SkRBuffer buffer(storage); 1060 SkRegion tmp; 1061 int32_t count; 1062 1063 count = buffer.readS32(); 1064 if (count >= 0) { 1065 buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)); 1066 if (count == 0) { 1067 tmp.fRunHead = SkRegion_gRectRunHeadPtr; 1068 } else { 1069 tmp.allocateRuns(count); 1070 buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType)); 1071 } 1072 } 1073 this->swap(tmp); 1074 return buffer.pos(); 1075} 1076 1077////////////////////////////////////////////////////////////////////////////////////////////////////////// 1078 1079#ifdef SK_DEBUG 1080 1081static const SkRegion::RunType* validate_line(const SkRegion::RunType run[], const SkIRect& bounds) 1082{ 1083 // *run is the bottom of the current span 1084 SkASSERT(*run > bounds.fTop); 1085 SkASSERT(*run <= bounds.fBottom); 1086 run += 1; 1087 1088 // check for empty span 1089 if (*run != SkRegion::kRunTypeSentinel) 1090 { 1091 int prevRite = bounds.fLeft - 1; 1092 do { 1093 int left = *run++; 1094 int rite = *run++; 1095 SkASSERT(left < rite); 1096 SkASSERT(left > prevRite); 1097 SkASSERT(rite <= bounds.fRight); 1098 prevRite = rite; 1099 } while (*run < SkRegion::kRunTypeSentinel); 1100 } 1101 return run + 1; // skip sentinel 1102} 1103 1104void SkRegion::validate() const 1105{ 1106 if (this->isEmpty()) 1107 { 1108 // check for explicit empty (the zero rect), so we can compare rects to know when 1109 // two regions are equal (i.e. emptyRectA == emptyRectB) 1110 // this is stricter than just asserting fBounds.isEmpty() 1111 SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0); 1112 } 1113 else 1114 { 1115 SkASSERT(!fBounds.isEmpty()); 1116 if (!this->isRect()) 1117 { 1118 SkASSERT(fRunHead->fRefCnt >= 1); 1119 SkASSERT(fRunHead->fRunCount >= kRectRegionRuns); 1120 1121 const RunType* run = fRunHead->readonly_runs(); 1122 const RunType* stop = run + fRunHead->fRunCount; 1123 1124 // check that our bounds match our runs 1125 { 1126 SkIRect bounds; 1127 bool isARect = ComputeRunBounds(run, stop - run, &bounds); 1128 SkASSERT(!isARect); 1129 SkASSERT(bounds == fBounds); 1130 } 1131 1132 SkASSERT(*run == fBounds.fTop); 1133 run++; 1134 do { 1135 run = validate_line(run, fBounds); 1136 } while (*run < kRunTypeSentinel); 1137 SkASSERT(run + 1 == stop); 1138 } 1139 } 1140} 1141 1142void SkRegion::dump() const 1143{ 1144 if (this->isEmpty()) 1145 SkDebugf(" rgn: empty\n"); 1146 else 1147 { 1148 SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1149 if (this->isComplex()) 1150 { 1151 const RunType* runs = fRunHead->readonly_runs(); 1152 for (int i = 0; i < fRunHead->fRunCount; i++) 1153 SkDebugf(" %d", runs[i]); 1154 } 1155 SkDebugf("\n"); 1156 } 1157} 1158 1159#endif 1160 1161///////////////////////////////////////////////////////////////////////////////////// 1162 1163SkRegion::Iterator::Iterator(const SkRegion& rgn) { 1164 this->reset(rgn); 1165} 1166 1167bool SkRegion::Iterator::rewind() { 1168 if (fRgn) { 1169 this->reset(*fRgn); 1170 return true; 1171 } 1172 return false; 1173} 1174 1175void SkRegion::Iterator::reset(const SkRegion& rgn) { 1176 fRgn = &rgn; 1177 if (rgn.isEmpty()) { 1178 fDone = true; 1179 } else { 1180 fDone = false; 1181 if (rgn.isRect()) { 1182 fRect = rgn.fBounds; 1183 fRuns = NULL; 1184 } else { 1185 fRuns = rgn.fRunHead->readonly_runs(); 1186 fRect.set(fRuns[2], fRuns[0], fRuns[3], fRuns[1]); 1187 fRuns += 4; 1188 } 1189 } 1190} 1191 1192void SkRegion::Iterator::next() { 1193 if (fDone) { 1194 return; 1195 } 1196 1197 if (fRuns == NULL) { // rect case 1198 fDone = true; 1199 return; 1200 } 1201 1202 const RunType* runs = fRuns; 1203 1204 if (runs[0] < kRunTypeSentinel) { // valid X value 1205 fRect.fLeft = runs[0]; 1206 fRect.fRight = runs[1]; 1207 runs += 2; 1208 } else { // we're at the end of a line 1209 runs += 1; 1210 if (runs[0] < kRunTypeSentinel) { // valid Y value 1211 if (runs[1] == kRunTypeSentinel) { // empty line 1212 fRect.fTop = runs[0]; 1213 runs += 2; 1214 } else { 1215 fRect.fTop = fRect.fBottom; 1216 } 1217 1218 fRect.fBottom = runs[0]; 1219 assert_sentinel(runs[1], false); 1220 fRect.fLeft = runs[1]; 1221 fRect.fRight = runs[2]; 1222 runs += 3; 1223 } else { // end of rgn 1224 fDone = true; 1225 } 1226 } 1227 fRuns = runs; 1228} 1229 1230SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip) 1231 : fIter(rgn), fClip(clip), fDone(true) { 1232 const SkIRect& r = fIter.rect(); 1233 1234 while (!fIter.done()) { 1235 if (r.fTop >= clip.fBottom) { 1236 break; 1237 } 1238 if (fRect.intersect(clip, r)) { 1239 fDone = false; 1240 break; 1241 } 1242 fIter.next(); 1243 } 1244} 1245 1246void SkRegion::Cliperator::next() { 1247 if (fDone) { 1248 return; 1249 } 1250 1251 const SkIRect& r = fIter.rect(); 1252 1253 fDone = true; 1254 fIter.next(); 1255 while (!fIter.done()) { 1256 if (r.fTop >= fClip.fBottom) { 1257 break; 1258 } 1259 if (fRect.intersect(fClip, r)) { 1260 fDone = false; 1261 break; 1262 } 1263 fIter.next(); 1264 } 1265} 1266 1267////////////////////////////////////////////////////////////////////// 1268 1269SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, int right) 1270{ 1271 SkDEBUGCODE(rgn.validate();) 1272 1273 const SkIRect& r = rgn.getBounds(); 1274 1275 fDone = true; 1276 if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && right > r.fLeft && left < r.fRight) 1277 { 1278 if (rgn.isRect()) 1279 { 1280 if (left < r.fLeft) 1281 left = r.fLeft; 1282 if (right > r.fRight) 1283 right = r.fRight; 1284 1285 fLeft = left; 1286 fRight = right; 1287 fRuns = NULL; // means we're a rect, not a rgn 1288 fDone = false; 1289 } 1290 else 1291 { 1292 const SkRegion::RunType* runs = find_y(rgn.fRunHead->readonly_runs(), y); 1293 if (runs) 1294 { 1295 for (;;) 1296 { 1297 if (runs[0] >= right) // runs[0..1] is to the right of the span, so we're done 1298 break; 1299 if (runs[1] <= left) // runs[0..1] is to the left of the span, so continue 1300 { 1301 runs += 2; 1302 continue; 1303 } 1304 // runs[0..1] intersects the span 1305 fRuns = runs; 1306 fLeft = left; 1307 fRight = right; 1308 fDone = false; 1309 break; 1310 } 1311 } 1312 } 1313 } 1314} 1315 1316bool SkRegion::Spanerator::next(int* left, int* right) 1317{ 1318 if (fDone) return false; 1319 1320 if (fRuns == NULL) // we're a rect 1321 { 1322 fDone = true; // ok, now we're done 1323 if (left) *left = fLeft; 1324 if (right) *right = fRight; 1325 return true; // this interval is legal 1326 } 1327 1328 const SkRegion::RunType* runs = fRuns; 1329 1330 if (runs[0] >= fRight) 1331 { 1332 fDone = true; 1333 return false; 1334 } 1335 1336 SkASSERT(runs[1] > fLeft); 1337 1338 if (left) 1339 *left = SkMax32(fLeft, runs[0]); 1340 if (right) 1341 *right = SkMin32(fRight, runs[1]); 1342 fRuns = runs + 2; 1343 return true; 1344} 1345 1346/////////////////////////////////////////////////////////////////////////////// 1347 1348#ifdef SK_DEBUG 1349 1350bool SkRegion::debugSetRuns(const RunType runs[], int count) { 1351 // we need to make a copy, since the real method may modify the array, and 1352 // so it cannot be const. 1353 1354 SkAutoTArray<RunType> storage(count); 1355 memcpy(storage.get(), runs, count * sizeof(RunType)); 1356 return this->setRuns(storage.get(), count); 1357} 1358 1359#endif 1360