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