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