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