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