SkAAClip.cpp revision 47ac84edafc6f26e2146ab10363e2043c5af0e62
1 2/* 3 * Copyright 2011 Google Inc. 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#include "SkAAClip.h" 10#include "SkBlitter.h" 11#include "SkPath.h" 12#include "SkScan.h" 13#include "SkThread.h" 14 15static inline bool x_in_rect(int x, const SkIRect& rect) { 16 return (unsigned)(x - rect.fLeft) < (unsigned)rect.width(); 17} 18 19static inline bool y_in_rect(int y, const SkIRect& rect) { 20 return (unsigned)(y - rect.fTop) < (unsigned)rect.height(); 21} 22 23/* 24 * Data runs are packed [count, alpha] 25 */ 26 27struct SkAAClip::YOffset { 28 int32_t fY; 29 uint32_t fOffset; 30}; 31 32struct SkAAClip::RunHead { 33 int32_t fRefCnt; 34 int32_t fRowCount; 35 int32_t fDataSize; 36 37 YOffset* yoffsets() { 38 return (YOffset*)((char*)this + sizeof(RunHead)); 39 } 40 const YOffset* yoffsets() const { 41 return (const YOffset*)((const char*)this + sizeof(RunHead)); 42 } 43 uint8_t* data() { 44 return (uint8_t*)(this->yoffsets() + fRowCount); 45 } 46 const uint8_t* data() const { 47 return (const uint8_t*)(this->yoffsets() + fRowCount); 48 } 49 50 static RunHead* Alloc(int rowCount, size_t dataSize) { 51 size_t size = sizeof(RunHead) + rowCount * sizeof(YOffset) + dataSize; 52 RunHead* head = (RunHead*)sk_malloc_throw(size); 53 head->fRefCnt = 1; 54 head->fRowCount = rowCount; 55 head->fDataSize = dataSize; 56 return head; 57 } 58}; 59 60class SkAAClip::Iter { 61public: 62 Iter(const SkAAClip&); 63 64 bool done() const { return fDone; } 65 int top() const { SkASSERT(!fDone); return fTop; } 66 int bottom() const { SkASSERT(!fDone); return fBottom; } 67 const uint8_t* data() const { SkASSERT(!fDone); return fData; } 68 void next(); 69 70private: 71 const YOffset* fCurrYOff; 72 const YOffset* fStopYOff; 73 const uint8_t* fData; 74 75 int fTop, fBottom; 76 bool fDone; 77}; 78 79SkAAClip::Iter::Iter(const SkAAClip& clip) { 80 if (clip.isEmpty()) { 81 fDone = true; 82 return; 83 } 84 85 const RunHead* head = clip.fRunHead; 86 fCurrYOff = head->yoffsets(); 87 fStopYOff = fCurrYOff + head->fRowCount; 88 fData = head->data() + fCurrYOff->fOffset; 89 90 // setup first value 91 fTop = clip.fBounds.fTop; 92 fBottom = clip.fBounds.fTop + fCurrYOff->fY + 1; 93 fDone = false; 94} 95 96void SkAAClip::Iter::next() { 97 SkASSERT(!fDone); 98 99 const YOffset* prev = fCurrYOff; 100 const YOffset* curr = prev + 1; 101 102 if (curr >= fStopYOff) { 103 fDone = true; 104 } else { 105 fTop = fBottom; 106 fBottom += curr->fY - prev->fY; 107 fData += curr->fOffset - prev->fOffset; 108 fCurrYOff = curr; 109 } 110} 111 112/////////////////////////////////////////////////////////////////////////////// 113 114void SkAAClip::freeRuns() { 115 if (fRunHead) { 116 SkASSERT(fRunHead->fRefCnt >= 1); 117 if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) { 118 sk_free(fRunHead); 119 } 120 } 121} 122 123SkAAClip::SkAAClip() { 124 fBounds.setEmpty(); 125 fRunHead = NULL; 126} 127 128SkAAClip::SkAAClip(const SkAAClip& src) { 129 fRunHead = NULL; 130 *this = src; 131} 132 133SkAAClip::~SkAAClip() { 134 this->freeRuns(); 135} 136 137SkAAClip& SkAAClip::operator=(const SkAAClip& src) { 138 if (this != &src) { 139 this->freeRuns(); 140 fBounds = src.fBounds; 141 fRunHead = src.fRunHead; 142 if (fRunHead) { 143 sk_atomic_inc(&fRunHead->fRefCnt); 144 } 145 } 146 return *this; 147} 148 149bool operator==(const SkAAClip& a, const SkAAClip& b) { 150 if (&a == &b) { 151 return true; 152 } 153 if (a.fBounds != b.fBounds) { 154 return false; 155 } 156 157 const SkAAClip::RunHead* ah = a.fRunHead; 158 const SkAAClip::RunHead* bh = b.fRunHead; 159 160 // this catches empties and rects being equal 161 if (ah == bh) { 162 return true; 163 } 164 165 // now we insist that both are complex (but different ptrs) 166 if (!a.fRunHead || !b.fRunHead) { 167 return false; 168 } 169 170 return ah->fRowCount == bh->fRowCount && 171 ah->fDataSize == bh->fDataSize && 172 !memcmp(ah->data(), bh->data(), ah->fDataSize); 173} 174 175void SkAAClip::swap(SkAAClip& other) { 176 SkTSwap(fBounds, other.fBounds); 177 SkTSwap(fRunHead, other.fRunHead); 178} 179 180bool SkAAClip::set(const SkAAClip& src) { 181 *this = src; 182 return !this->isEmpty(); 183} 184 185bool SkAAClip::setEmpty() { 186 this->freeRuns(); 187 fBounds.setEmpty(); 188 fRunHead = NULL; 189 return false; 190} 191 192bool SkAAClip::setRect(const SkIRect& bounds) { 193 if (bounds.isEmpty()) { 194 return this->setEmpty(); 195 } 196 197 // TODO: special case this 198 199 SkRect r; 200 r.set(bounds); 201 SkPath path; 202 path.addRect(r); 203 return this->setPath(path); 204} 205 206bool SkAAClip::setRect(const SkRect& r) { 207 if (r.isEmpty()) { 208 return this->setEmpty(); 209 } 210 211 SkPath path; 212 path.addRect(r); 213 return this->setPath(path); 214} 215 216/////////////////////////////////////////////////////////////////////////////// 217 218const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const { 219 SkASSERT(fRunHead); 220 221 if (!y_in_rect(y, fBounds)) { 222 return NULL; 223 } 224 y -= fBounds.y(); // our yoffs values are relative to the top 225 226 const YOffset* yoff = fRunHead->yoffsets(); 227 while (yoff->fY < y) { 228 yoff += 1; 229 SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount); 230 } 231 232 if (lastYForRow) { 233 *lastYForRow = yoff->fY; 234 } 235 return fRunHead->data() + yoff->fOffset; 236} 237 238const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const { 239 SkASSERT(x_in_rect(x, fBounds)); 240 x -= fBounds.x(); 241 242 // first skip up to X 243 for (;;) { 244 int n = data[0]; 245 if (x < n) { 246 *initialCount = n - x; 247 break; 248 } 249 data += 2; 250 x -= n; 251 } 252 return data; 253} 254 255bool SkAAClip::quickContains(int left, int top, int right, int bottom) const { 256 if (this->isEmpty()) { 257 return false; 258 } 259 if (!fBounds.contains(left, top, right, bottom)) { 260 return false; 261 } 262#if 0 263 if (this->isRect()) { 264 return true; 265 } 266#endif 267 268 int lastY; 269 const uint8_t* row = this->findRow(top, &lastY); 270 if (lastY < bottom) { 271 return false; 272 } 273 // now just need to check in X 274 int initialCount; 275 row = this->findX(row, left, &initialCount); 276 return initialCount >= (right - left) && 0xFF == row[1]; 277} 278 279/////////////////////////////////////////////////////////////////////////////// 280 281class SkAAClip::Builder { 282 SkIRect fBounds; 283 struct Row { 284 int fY; 285 int fWidth; 286 SkTDArray<uint8_t>* fData; 287 }; 288 SkTDArray<Row> fRows; 289 Row* fCurrRow; 290 int fPrevY; 291 int fWidth; 292 293public: 294 Builder(const SkIRect& bounds) : fBounds(bounds) { 295 fPrevY = -1; 296 fWidth = bounds.width(); 297 fCurrRow = NULL; 298 } 299 300 ~Builder() { 301 Row* row = fRows.begin(); 302 Row* stop = fRows.end(); 303 while (row < stop) { 304 delete row->fData; 305 row += 1; 306 } 307 } 308 309 const SkIRect& getBounds() const { return fBounds; } 310 311 void addRun(int x, int y, U8CPU alpha, int count) { 312 SkASSERT(count > 0); 313 SkASSERT(fBounds.contains(x, y)); 314 SkASSERT(fBounds.contains(x + count - 1, y)); 315 316 x -= fBounds.left(); 317 y -= fBounds.top(); 318 319 Row* row = fCurrRow; 320 if (y != fPrevY) { 321 SkASSERT(y > fPrevY); 322 fPrevY = y; 323 row = this->flushRow(true); 324 row->fY = y; 325 row->fWidth = 0; 326 SkASSERT(row->fData); 327 SkASSERT(0 == row->fData->count()); 328 fCurrRow = row; 329 } 330 331 SkASSERT(row->fWidth <= x); 332 SkASSERT(row->fWidth < fBounds.width()); 333 334 SkTDArray<uint8_t>& data = *row->fData; 335 336 int gap = x - row->fWidth; 337 if (gap) { 338 AppendRun(data, 0, gap); 339 row->fWidth += gap; 340 SkASSERT(row->fWidth < fBounds.width()); 341 } 342 343 AppendRun(data, alpha, count); 344 row->fWidth += count; 345 SkASSERT(row->fWidth <= fBounds.width()); 346 } 347 348 RunHead* finish() { 349 this->flushRow(false); 350 351 const Row* row = fRows.begin(); 352 const Row* stop = fRows.end(); 353 354 size_t dataSize = 0; 355 while (row < stop) { 356 dataSize += row->fData->count(); 357 row += 1; 358 } 359 360 RunHead* head = RunHead::Alloc(fRows.count(), dataSize); 361 YOffset* yoffset = head->yoffsets(); 362 uint8_t* data = head->data(); 363 uint8_t* baseData = data; 364 365 row = fRows.begin(); 366 while (row < stop) { 367 yoffset->fY = row->fY; 368 yoffset->fOffset = data - baseData; 369 yoffset += 1; 370 371 size_t n = row->fData->count(); 372 memcpy(data, row->fData->begin(), n); 373 data += n; 374 375 row += 1; 376 } 377 378 return head; 379 } 380 381 void dump() { 382 this->validate(); 383 int y; 384 for (y = 0; y < fRows.count(); ++y) { 385 const Row& row = fRows[y]; 386 SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth); 387 const SkTDArray<uint8_t>& data = *row.fData; 388 int count = data.count(); 389 SkASSERT(!(count & 1)); 390 const uint8_t* ptr = data.begin(); 391 for (int x = 0; x < count; x += 2) { 392 SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]); 393 ptr += 2; 394 } 395 SkDebugf("\n"); 396 } 397 398#if 1 399 int prevY = -1; 400 for (y = 0; y < fRows.count(); ++y) { 401 const Row& row = fRows[y]; 402 const SkTDArray<uint8_t>& data = *row.fData; 403 int count = data.count(); 404 for (int n = prevY; n < row.fY; ++n) { 405 const uint8_t* ptr = data.begin(); 406 for (int x = 0; x < count; x += 2) { 407 for (int i = 0; i < ptr[0]; ++i) { 408 SkDebugf("%02X", ptr[1]); 409 } 410 ptr += 2; 411 } 412 SkDebugf("\n"); 413 } 414 prevY = row.fY; 415 } 416#endif 417 } 418 419 void validate() { 420#ifdef SK_DEBUG 421 int prevY = -1; 422 for (int i = 0; i < fRows.count(); ++i) { 423 const Row& row = fRows[i]; 424 SkASSERT(prevY < row.fY); 425 SkASSERT(fWidth == row.fWidth); 426 int count = row.fData->count(); 427 const uint8_t* ptr = row.fData->begin(); 428 SkASSERT(!(count & 1)); 429 int w = 0; 430 for (int x = 0; x < count; x += 2) { 431 w += ptr[0]; 432 SkASSERT(w <= fWidth); 433 ptr += 2; 434 } 435 SkASSERT(w == fWidth); 436 prevY = row.fY; 437 } 438#endif 439 } 440 441private: 442 Row* flushRow(bool readyForAnother) { 443 Row* next = NULL; 444 int count = fRows.count(); 445 if (count > 0) { 446 // flush current row if needed 447 Row* curr = &fRows[count - 1]; 448 if (curr->fWidth < fWidth) { 449 AppendRun(*curr->fData, 0, fWidth - curr->fWidth); 450 } 451 } 452 if (count > 1) { 453 // are our last two runs the same? 454 Row* prev = &fRows[count - 2]; 455 Row* curr = &fRows[count - 1]; 456 SkASSERT(prev->fWidth == fWidth); 457 SkASSERT(curr->fWidth == fWidth); 458 if (*prev->fData == *curr->fData) { 459 prev->fY = curr->fY; 460 if (readyForAnother) { 461 curr->fData->rewind(); 462 next = curr; 463 } else { 464 delete curr->fData; 465 fRows.removeShuffle(count - 1); 466 } 467 } else { 468 if (readyForAnother) { 469 next = fRows.append(); 470 next->fData = new SkTDArray<uint8_t>; 471 } 472 } 473 } else { 474 if (readyForAnother) { 475 next = fRows.append(); 476 next->fData = new SkTDArray<uint8_t>; 477 } 478 } 479 return next; 480 } 481 482 static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) { 483 do { 484 int n = count; 485 if (n > 255) { 486 n = 255; 487 } 488 uint8_t* ptr = data.append(2); 489 ptr[0] = n; 490 ptr[1] = alpha; 491 count -= n; 492 } while (count > 0); 493 } 494}; 495 496class SkAAClip::BuilderBlitter : public SkBlitter { 497public: 498 BuilderBlitter(Builder* builder) { 499 fBuilder = builder; 500 } 501 502 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE 503 { unexpected(); } 504 virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE 505 { unexpected(); } 506 virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE 507 { unexpected(); } 508 509 virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE { 510 return false; 511 } 512 513 virtual void blitH(int x, int y, int width) SK_OVERRIDE { 514 fBuilder->addRun(x, y, 0xFF, width); 515 } 516 517 virtual void blitAntiH(int x, int y, const SkAlpha alpha[], 518 const int16_t runs[]) SK_OVERRIDE { 519 for (;;) { 520 int count = *runs; 521 if (count <= 0) { 522 return; 523 } 524 fBuilder->addRun(x, y, *alpha, count); 525 runs += count; 526 alpha += count; 527 x += count; 528 } 529 } 530 531private: 532 Builder* fBuilder; 533 534 void unexpected() { 535 SkDebugf("---- did not expect to get called here"); 536 sk_throw(); 537 } 538}; 539 540bool SkAAClip::setPath(const SkPath& path, const SkRegion* clip) { 541 if (clip && clip->isEmpty()) { 542 return this->setEmpty(); 543 } 544 545 SkIRect ibounds; 546 path.getBounds().roundOut(&ibounds); 547 548 SkRegion tmpClip; 549 if (NULL == clip) { 550 tmpClip.setRect(ibounds); 551 clip = &tmpClip; 552 } 553 554 if (!path.isInverseFillType()) { 555 if (ibounds.isEmpty() || !ibounds.intersect(clip->getBounds())) { 556 return this->setEmpty(); 557 } 558 } 559 560 Builder builder(ibounds); 561 BuilderBlitter blitter(&builder); 562 563 SkScan::AntiFillPath(path, *clip, &blitter, true); 564 565 this->freeRuns(); 566 fBounds = ibounds; 567 fRunHead = builder.finish(); 568 569 builder.dump(); 570} 571 572/////////////////////////////////////////////////////////////////////////////// 573 574typedef void (*RowProc)(SkAAClip::Builder&, int bottom, 575 const uint8_t* rowA, const SkIRect& rectA, 576 const uint8_t* rowB, const SkIRect& rectB); 577 578static void sectRowProc(SkAAClip::Builder& builder, int bottom, 579 const uint8_t* rowA, const SkIRect& rectA, 580 const uint8_t* rowB, const SkIRect& rectB) { 581 582} 583 584typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB); 585 586static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) { 587 // Multiply 588 return SkMulDiv255Round(alphaA, alphaB); 589} 590 591static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) { 592 // SrcOver 593 return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB); 594} 595 596static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) { 597 // SrcOut 598 return SkMulDiv255Round(alphaA, 0xFF - alphaB); 599} 600 601static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) { 602 // XOR 603 return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB); 604} 605 606static AlphaProc find_alpha_proc(SkRegion::Op op) { 607 switch (op) { 608 case SkRegion::kIntersect_Op: 609 return sectAlphaProc; 610 case SkRegion::kDifference_Op: 611 return diffAlphaProc; 612 case SkRegion::kUnion_Op: 613 return unionAlphaProc; 614 case SkRegion::kXOR_Op: 615 return xorAlphaProc; 616 default: 617 SkASSERT(!"unexpected region op"); 618 return sectAlphaProc; 619 } 620} 621 622static const uint8_t gEmptyRow[] = { 623 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 624 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 625 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 626 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 627 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 628 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 629 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 630 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 631}; 632 633class RowIter { 634public: 635 RowIter(const uint8_t* row, const SkIRect& bounds) { 636 fRow = row; 637 fLeft = bounds.fLeft; 638 fRight = bounds.fLeft + row[0]; 639 fBoundsRight = bounds.fRight; 640 SkASSERT(fRight <= fBoundsRight); 641 fDone = false; 642 } 643 644 bool done() const { return fDone; } 645 int left() const { SkASSERT(!done()); return fLeft; } 646 int right() const { SkASSERT(!done()); return fRight; } 647 U8CPU alpha() const { SkASSERT(!done()); return fRow[1]; } 648 void next() { 649 SkASSERT(!done()); 650 if (fRight == fBoundsRight) { 651 fDone = true; 652 } else { 653 fRow += 2; 654 fLeft = fRight; 655 fRight += fRow[0]; 656 SkASSERT(fRight <= fBoundsRight); 657 } 658 } 659 660private: 661 const uint8_t* fRow; 662 int fLeft; 663 int fRight; 664 int fBoundsRight; 665 bool fDone; 666}; 667 668static void adjust_row(RowIter& iter, int& leftA, int& riteA, 669 int left, int rite) { 670 if (leftA == left) { 671 leftA = rite; 672 if (leftA == riteA) { 673 if (iter.done()) { 674 leftA = 0x7FFFFFFF; 675 riteA = 0x7FFFFFFF; 676 } else { 677 iter.next(); 678 leftA = iter.left(); 679 riteA = iter.right(); 680 } 681 } 682 } 683} 684 685static void operatorX(SkAAClip::Builder& builder, int lastY, 686 RowIter& iterA, RowIter& iterB, 687 AlphaProc proc, const SkIRect& bounds) { 688 SkASSERT(!iterA.done()); 689 int leftA = iterA.left(); 690 int riteA = iterA.right(); 691 SkASSERT(!iterB.done()); 692 int leftB = iterB.left(); 693 int riteB = iterB.right(); 694 695 for (;;) { 696 U8CPU alphaA = 0; 697 U8CPU alphaB = 0; 698 699 int left, rite; 700 if (riteA <= leftB) { // all A 701 left = leftA; 702 rite = riteA; 703 alphaA = iterA.alpha(); 704 } else if (riteB <= leftA) { // all B 705 left = leftB; 706 rite = riteB; 707 alphaB = iterB.alpha(); 708 } else { 709 // some overlap 710 alphaA = iterA.alpha(); 711 alphaB = iterB.alpha(); 712 if (leftA <= leftB) { 713 left = leftA; 714 if (leftA == leftB) { 715 rite = SkMin32(riteA, riteB); 716 } else{ 717 rite = leftB; 718 } 719 } else { // leftB < leftA 720 left = leftB; 721 rite = leftA; 722 } 723 } 724 725 if (left >= bounds.fRight) { 726 break; 727 } 728 729 SkASSERT(rite <= bounds.fRight); 730 if (left >= bounds.fLeft) { 731 builder.addRun(left, lastY, proc(alphaA, alphaB), rite - left); 732 } else { 733 SkASSERT(rite <= bounds.fLeft); 734 } 735 736 if (rite == bounds.fRight) { 737 break; 738 } 739 740 adjust_row(iterA, leftA, riteA, left, rite); 741 adjust_row(iterB, leftB, riteB, left, rite); 742 } 743} 744 745static void adjust_iter(SkAAClip::Iter& iter, int& topA, int& botA, 746 int top, int bot) { 747 if (topA == top) { 748 topA = bot; 749 if (topA == botA) { 750 if (iter.done()) { 751 topA = 0x7FFFFFFF; 752 botA = 0x7FFFFFFF; 753 } else { 754 iter.next(); 755 topA = iter.top(); 756 botA = iter.bottom(); 757 } 758 } 759 } 760} 761 762static void operateY(SkAAClip::Builder& builder, const SkAAClip& A, 763 const SkAAClip& B, SkRegion::Op op) { 764 AlphaProc proc = find_alpha_proc(op); 765 const SkIRect& bounds = builder.getBounds(); 766 767 SkAAClip::Iter iterA(A); 768 SkAAClip::Iter iterB(B); 769 770 SkASSERT(!iterA.done()); 771 int topA = iterA.top(); 772 int botA = iterA.bottom(); 773 SkASSERT(!iterB.done()); 774 int topB = iterB.top(); 775 int botB = iterB.bottom(); 776 777 for (;;) { 778 SkASSERT(topA < botA); 779 SkASSERT(topB < botB); 780 781 const uint8_t* rowA = gEmptyRow; 782 const uint8_t* rowB = gEmptyRow; 783 784 // find the vertical 785 int top, bot; 786 if (botA <= topB) { // all A 787 top = topA; 788 bot = botA; 789 rowA = iterA.data(); 790 } else if (botB <= topA) { // all B 791 top = topB; 792 bot = botB; 793 rowB = iterB.data(); 794 } else { 795 // some overlap 796 rowA = iterA.data(); 797 rowB = iterB.data(); 798 if (topA <= topB) { 799 top = topA; 800 if (topA == topB) { 801 bot = SkMin32(botA, botB); 802 } else{ 803 bot = topB; 804 } 805 } else { // topB < topA 806 top = topB; 807 bot = topA; 808 } 809 } 810 811 if (top >= bounds.fBottom) { 812 break; 813 } 814 815 SkASSERT(bot <= bounds.fBottom); 816 if (top >= bounds.fTop) { 817 RowIter rowIterA(rowA, A.getBounds()); 818 RowIter rowIterB(rowB, B.getBounds()); 819 operatorX(builder, bot - 1, rowIterA, rowIterB, proc, bounds); 820 } else { 821 SkASSERT(bot <= bounds.fTop); 822 } 823 824 if (bot == bounds.fBottom) { 825 break; 826 } 827 828 adjust_iter(iterA, topA, botA, top, bot); 829 adjust_iter(iterB, topB, botB, top, bot); 830 } 831 832} 833 834bool SkAAClip::op(const SkAAClip& clipAOrig, const SkAAClip& clipBOrig, 835 SkRegion::Op op) { 836 if (SkRegion::kReplace_Op == op) { 837 return this->set(clipBOrig); 838 } 839 840 const SkAAClip* clipA = &clipAOrig; 841 const SkAAClip* clipB = &clipBOrig; 842 843 if (SkRegion::kReverseDifference_Op == op) { 844 SkTSwap(clipA, clipB); 845 op = SkRegion::kDifference_Op; 846 } 847 848 bool a_empty = clipA->isEmpty(); 849 bool b_empty = clipB->isEmpty(); 850 851 SkIRect bounds; 852 switch (op) { 853 case SkRegion::kDifference_Op: 854 if (a_empty) { 855 return this->setEmpty(); 856 } 857 if (b_empty || !SkIRect::Intersects(clipA->fBounds, clipB->fBounds)) { 858 return this->set(*clipA); 859 } 860 bounds = clipA->fBounds; 861 break; 862 863 case SkRegion::kIntersect_Op: 864 if ((a_empty | b_empty) || !bounds.intersect(clipA->fBounds, 865 clipB->fBounds)) { 866 return this->setEmpty(); 867 } 868 break; 869 870 case SkRegion::kUnion_Op: 871 case SkRegion::kXOR_Op: 872 if (a_empty) { 873 return this->set(*clipB); 874 } 875 if (b_empty) { 876 return this->set(*clipA); 877 } 878 bounds = clipA->fBounds; 879 bounds.join(clipB->fBounds); 880 break; 881 882 default: 883 SkASSERT(!"unknown region op"); 884 return !this->isEmpty(); 885 } 886 887 SkASSERT(SkIRect::Intersects(clipA->fBounds, clipB->fBounds)); 888 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 889 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 890 891 Builder builder(bounds); 892 operateY(builder, *clipA, *clipB, op); 893 // don't free us until now, since we might be clipA or clipB 894 this->freeRuns(); 895 fBounds = bounds; 896 fRunHead = builder.finish(); 897 898 return !this->isEmpty(); 899} 900 901bool SkAAClip::op(const SkIRect& r, SkRegion::Op op) { 902 SkAAClip clip; 903 clip.setRect(r); 904 return this->op(*this, clip, op); 905} 906 907bool SkAAClip::op(const SkRect& r, SkRegion::Op op) { 908 SkAAClip clip; 909 clip.setRect(r); 910 return this->op(*this, clip, op); 911} 912 913bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) { 914 return this->op(*this, clip, op); 915} 916 917/////////////////////////////////////////////////////////////////////////////// 918/////////////////////////////////////////////////////////////////////////////// 919 920static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width, 921 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) { 922 // we don't read our initial n from data, since the caller may have had to 923 // clip it, hence the initialCount parameter. 924 int n = initialCount; 925 for (;;) { 926 if (n > width) { 927 n = width; 928 } 929 SkASSERT(n > 0); 930 runs[0] = n; 931 runs += n; 932 933 aa[0] = data[1]; 934 aa += n; 935 936 data += 2; 937 width -= n; 938 if (0 == width) { 939 break; 940 } 941 // load the next count 942 n = data[0]; 943 } 944 runs[0] = 0; // sentinel 945} 946 947SkAAClipBlitter::~SkAAClipBlitter() { 948 sk_free(fRuns); 949} 950 951void SkAAClipBlitter::ensureRunsAndAA() { 952 if (NULL == fRuns) { 953 // add 1 so we can store the terminating run count of 0 954 int count = fAAClipBounds.width() + 1; 955 fRuns = (int16_t*)sk_malloc_throw(count * sizeof(int16_t) + 956 count * sizeof(SkAlpha)); 957 fAA = (SkAlpha*)(fRuns + count); 958 } 959} 960 961void SkAAClipBlitter::blitH(int x, int y, int width) { 962 SkASSERT(width > 0); 963 SkASSERT(fAAClipBounds.contains(x, y)); 964 SkASSERT(fAAClipBounds.contains(x + width - 1, y)); 965 966 int lastY; 967 const uint8_t* row = fAAClip->findRow(y, &lastY); 968 int initialCount; 969 row = fAAClip->findX(row, x, &initialCount); 970 971 if (initialCount >= width) { 972 SkAlpha alpha = row[1]; 973 if (0 == alpha) { 974 return; 975 } 976 if (0xFF == alpha) { 977 fBlitter->blitH(x, y, width); 978 return; 979 } 980 } 981 982 this->ensureRunsAndAA(); 983 expandToRuns(row, initialCount, width, fRuns, fAA); 984 985 fBlitter->blitAntiH(x, y, fAA, fRuns); 986} 987 988static void merge(const uint8_t* SK_RESTRICT row, int rowN, 989 const SkAlpha* SK_RESTRICT srcAA, 990 const int16_t* SK_RESTRICT srcRuns, 991 SkAlpha* SK_RESTRICT dstAA, 992 int16_t* SK_RESTRICT dstRuns, 993 int width) { 994 SkDEBUGCODE(int accumulated = 0;) 995 int srcN = srcRuns[0]; 996 for (;;) { 997 if (0 == srcN) { 998 break; 999 } 1000 SkASSERT(rowN > 0); 1001 SkASSERT(srcN > 0); 1002 1003 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]); 1004 int minN = SkMin32(srcN, rowN); 1005 dstRuns[0] = minN; 1006 dstRuns += minN; 1007 dstAA[0] = newAlpha; 1008 dstAA += minN; 1009 1010 if (0 == (srcN -= minN)) { 1011 srcN = srcRuns[0]; // refresh 1012 srcRuns += srcN; 1013 srcAA += srcN; 1014 srcN = srcRuns[0]; // reload 1015 } 1016 if (0 == (rowN -= minN)) { 1017 row += 2; 1018 rowN = row[0]; // reload 1019 } 1020 1021 SkDEBUGCODE(accumulated += minN;) 1022 SkASSERT(accumulated <= width); 1023 } 1024} 1025 1026void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[], 1027 const int16_t runs[]) { 1028 int lastY; 1029 const uint8_t* row = fAAClip->findRow(y, &lastY); 1030 int initialCount; 1031 row = fAAClip->findX(row, x, &initialCount); 1032 1033 this->ensureRunsAndAA(); 1034 1035 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width()); 1036 fBlitter->blitAntiH(x, y, fAA, fRuns); 1037} 1038 1039void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) { 1040 if (fAAClip->quickContains(x, y, x + 1, y + height)) { 1041 fBlitter->blitV(x, y, height, alpha); 1042 return; 1043 } 1044 1045 int stopY = y + height; 1046 do { 1047 int lastY; 1048 const uint8_t* row = fAAClip->findRow(y, &lastY); 1049 int initialCount; 1050 row = fAAClip->findX(row, x, &initialCount); 1051 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]); 1052 if (newAlpha) { 1053 fBlitter->blitV(x, y, lastY - y + 1, newAlpha); 1054 } 1055 y = lastY + 1; 1056 } while (y < stopY); 1057} 1058 1059void SkAAClipBlitter::blitRect(int x, int y, int width, int height) { 1060 if (fAAClip->quickContains(x, y, x + width, y + height)) { 1061 fBlitter->blitRect(x, y, width, height); 1062 return; 1063 } 1064 1065 while (--height >= 0) { 1066 this->blitH(x, y, width); 1067 y += 1; 1068 } 1069} 1070 1071void SkAAClipBlitter::blitMask(const SkMask& mask, const SkIRect& clip) { 1072 fBlitter->blitMask(mask, clip); 1073} 1074 1075const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) { 1076 return NULL; 1077} 1078 1079/////////////////////////////////////////////////////////////////////////////// 1080 1081static void expand_row_to_mask(uint8_t* SK_RESTRICT mask, 1082 const uint8_t* SK_RESTRICT row, 1083 int width) { 1084 while (width > 0) { 1085 int n = row[0]; 1086 SkASSERT(width >= n); 1087 memset(mask, row[1], n); 1088 mask += n; 1089 row += 2; 1090 width -= n; 1091 } 1092} 1093 1094void SkAAClip::copyToMask(SkMask* mask) const { 1095 mask->fFormat = SkMask::kA8_Format; 1096 if (this->isEmpty()) { 1097 mask->fBounds.setEmpty(); 1098 mask->fImage = NULL; 1099 mask->fRowBytes = 0; 1100 return; 1101 } 1102 1103 mask->fBounds = fBounds; 1104 mask->fRowBytes = fBounds.width(); 1105 size_t size = mask->computeImageSize(); 1106 mask->fImage = SkMask::AllocImage(size); 1107 1108 Iter iter(*this); 1109 uint8_t* dst = mask->fImage; 1110 const int width = fBounds.width(); 1111 1112 int y = fBounds.fTop; 1113 while (!iter.done()) { 1114 do { 1115 expand_row_to_mask(dst, iter.data(), width); 1116 dst += mask->fRowBytes; 1117 } while (++y < iter.bottom()); 1118 iter.next(); 1119 } 1120} 1121 1122