SkAAClip.cpp revision c5507bfe2d54e411ef6eb83452b8cbfbae009610
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 "SkColorPriv.h" 12#include "SkPath.h" 13#include "SkScan.h" 14#include "SkThread.h" 15#include "SkUtils.h" 16 17class AutoAAClipValidate { 18public: 19 AutoAAClipValidate(const SkAAClip& clip) : fClip(clip) { 20 fClip.validate(); 21 } 22 ~AutoAAClipValidate() { 23 fClip.validate(); 24 } 25private: 26 const SkAAClip& fClip; 27}; 28 29#ifdef SK_DEBUG 30 #define AUTO_AACLIP_VALIDATE(clip) AutoAAClipValidate acv(clip) 31#else 32 #define AUTO_AACLIP_VALIDATE(clip) 33#endif 34 35/////////////////////////////////////////////////////////////////////////////// 36 37#define kMaxInt32 0x7FFFFFFF 38 39static inline bool x_in_rect(int x, const SkIRect& rect) { 40 return (unsigned)(x - rect.fLeft) < (unsigned)rect.width(); 41} 42 43static inline bool y_in_rect(int y, const SkIRect& rect) { 44 return (unsigned)(y - rect.fTop) < (unsigned)rect.height(); 45} 46 47/* 48 * Data runs are packed [count, alpha] 49 */ 50 51struct SkAAClip::YOffset { 52 int32_t fY; 53 uint32_t fOffset; 54}; 55 56struct SkAAClip::RunHead { 57 int32_t fRefCnt; 58 int32_t fRowCount; 59 int32_t fDataSize; 60 61 YOffset* yoffsets() { 62 return (YOffset*)((char*)this + sizeof(RunHead)); 63 } 64 const YOffset* yoffsets() const { 65 return (const YOffset*)((const char*)this + sizeof(RunHead)); 66 } 67 uint8_t* data() { 68 return (uint8_t*)(this->yoffsets() + fRowCount); 69 } 70 const uint8_t* data() const { 71 return (const uint8_t*)(this->yoffsets() + fRowCount); 72 } 73 74 static RunHead* Alloc(int rowCount, size_t dataSize) { 75 size_t size = sizeof(RunHead) + rowCount * sizeof(YOffset) + dataSize; 76 RunHead* head = (RunHead*)sk_malloc_throw(size); 77 head->fRefCnt = 1; 78 head->fRowCount = rowCount; 79 head->fDataSize = dataSize; 80 return head; 81 } 82 83 static int ComputeRowSizeForWidth(int width) { 84 // 2 bytes per segment, where each segment can store up to 255 for count 85 int segments = 0; 86 while (width > 0) { 87 segments += 1; 88 int n = SkMin32(width, 255); 89 width -= n; 90 } 91 return segments * 2; // each segment is row[0] + row[1] (n + alpha) 92 } 93 94 static RunHead* AllocRect(const SkIRect& bounds) { 95 SkASSERT(!bounds.isEmpty()); 96 int width = bounds.width(); 97 size_t rowSize = ComputeRowSizeForWidth(width); 98 RunHead* head = RunHead::Alloc(1, rowSize); 99 YOffset* yoff = head->yoffsets(); 100 yoff->fY = bounds.height() - 1; 101 yoff->fOffset = 0; 102 uint8_t* row = head->data(); 103 while (width > 0) { 104 int n = SkMin32(width, 255); 105 row[0] = n; 106 row[1] = 0xFF; 107 width -= n; 108 row += 2; 109 } 110 return head; 111 } 112}; 113 114class SkAAClip::Iter { 115public: 116 Iter(const SkAAClip&); 117 118 bool done() const { return fDone; } 119 int top() const { return fTop; } 120 int bottom() const { return fBottom; } 121 const uint8_t* data() const { return fData; } 122 void next(); 123 124private: 125 const YOffset* fCurrYOff; 126 const YOffset* fStopYOff; 127 const uint8_t* fData; 128 129 int fTop, fBottom; 130 bool fDone; 131}; 132 133SkAAClip::Iter::Iter(const SkAAClip& clip) { 134 if (clip.isEmpty()) { 135 fDone = true; 136 fTop = fBottom = clip.fBounds.fBottom; 137 fData = NULL; 138 return; 139 } 140 141 const RunHead* head = clip.fRunHead; 142 fCurrYOff = head->yoffsets(); 143 fStopYOff = fCurrYOff + head->fRowCount; 144 fData = head->data() + fCurrYOff->fOffset; 145 146 // setup first value 147 fTop = clip.fBounds.fTop; 148 fBottom = clip.fBounds.fTop + fCurrYOff->fY + 1; 149 fDone = false; 150} 151 152void SkAAClip::Iter::next() { 153 if (!fDone) { 154 const YOffset* prev = fCurrYOff; 155 const YOffset* curr = prev + 1; 156 SkASSERT(curr <= fStopYOff); 157 158 fTop = fBottom; 159 if (curr >= fStopYOff) { 160 fDone = true; 161 fBottom = kMaxInt32; 162 fData = NULL; 163 } else { 164 fBottom += curr->fY - prev->fY; 165 fData += curr->fOffset - prev->fOffset; 166 fCurrYOff = curr; 167 } 168 } 169} 170 171#ifdef SK_DEBUG 172// assert we're exactly width-wide, and then return the number of bytes used 173static size_t compute_row_length(const uint8_t row[], int width) { 174 const uint8_t* origRow = row; 175 while (width > 0) { 176 int n = row[0]; 177 SkASSERT(n > 0); 178 SkASSERT(n <= width); 179 row += 2; 180 width -= n; 181 } 182 SkASSERT(0 == width); 183 return row - origRow; 184} 185 186void SkAAClip::validate() const { 187 if (NULL == fRunHead) { 188 SkASSERT(fBounds.isEmpty()); 189 return; 190 } 191 192 const RunHead* head = fRunHead; 193 SkASSERT(head->fRefCnt > 0); 194 SkASSERT(head->fRowCount > 0); 195 SkASSERT(head->fDataSize > 0); 196 197 const YOffset* yoff = head->yoffsets(); 198 const YOffset* ystop = yoff + head->fRowCount; 199 const int lastY = fBounds.height() - 1; 200 201 // Y and offset must be monotonic 202 int prevY = -1; 203 int32_t prevOffset = -1; 204 while (yoff < ystop) { 205 SkASSERT(prevY < yoff->fY); 206 SkASSERT(yoff->fY <= lastY); 207 prevY = yoff->fY; 208 SkASSERT(prevOffset < (int32_t)yoff->fOffset); 209 prevOffset = yoff->fOffset; 210 const uint8_t* row = head->data() + yoff->fOffset; 211 size_t rowLength = compute_row_length(row, fBounds.width()); 212 SkASSERT(yoff->fOffset + rowLength <= head->fDataSize); 213 yoff += 1; 214 } 215 // check the last entry; 216 --yoff; 217 SkASSERT(yoff->fY == lastY); 218} 219#endif 220 221/////////////////////////////////////////////////////////////////////////////// 222 223static void count_left_right_zeros(const uint8_t* row, int width, 224 int* leftZ, int* riteZ) { 225 int zeros = 0; 226 do { 227 if (row[1]) { 228 break; 229 } 230 int n = row[0]; 231 SkASSERT(n > 0); 232 SkASSERT(n <= width); 233 zeros += n; 234 row += 2; 235 width -= n; 236 } while (width > 0); 237 *leftZ = zeros; 238 239 zeros = 0; 240 while (width > 0) { 241 int n = row[0]; 242 SkASSERT(n > 0); 243 if (0 == row[1]) { 244 zeros += n; 245 } else { 246 zeros = 0; 247 } 248 row += 2; 249 width -= n; 250 } 251 *riteZ = zeros; 252} 253 254#ifdef SK_DEBUG 255static void test_count_left_right_zeros() { 256 static bool gOnce; 257 if (gOnce) { 258 return; 259 } 260 gOnce = true; 261 262 const uint8_t data0[] = { 0, 0, 10, 0xFF }; 263 const uint8_t data1[] = { 0, 0, 5, 0xFF, 2, 0, 3, 0xFF }; 264 const uint8_t data2[] = { 7, 0, 5, 0, 2, 0, 3, 0xFF }; 265 const uint8_t data3[] = { 0, 5, 5, 0xFF, 2, 0, 3, 0 }; 266 const uint8_t data4[] = { 2, 3, 2, 0, 5, 0xFF, 3, 0 }; 267 const uint8_t data5[] = { 10, 0, 10, 0 }; 268 const uint8_t data6[] = { 2, 2, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 269 270 const uint8_t* array[] = { 271 data0, data1, data2, data3, data4, data5, data6 272 }; 273 274 for (size_t i = 0; i < SK_ARRAY_COUNT(array); ++i) { 275 const uint8_t* data = array[i]; 276 const int expectedL = *data++; 277 const int expectedR = *data++; 278 int L = 12345, R = 12345; 279 count_left_right_zeros(data, 10, &L, &R); 280 SkASSERT(expectedL == L); 281 SkASSERT(expectedR == R); 282 } 283} 284#endif 285 286// modify row in place, trimming off (zeros) from the left and right sides. 287// return the number of bytes that were completely eliminated from the left 288static int trim_row_left_right(uint8_t* row, int width, int leftZ, int riteZ) { 289 int trim = 0; 290 while (leftZ > 0) { 291 SkASSERT(0 == row[1]); 292 int n = row[0]; 293 SkASSERT(n > 0); 294 SkASSERT(n <= width); 295 width -= n; 296 row += 2; 297 if (n > leftZ) { 298 row[-2] = n - leftZ; 299 break; 300 } 301 trim += 2; 302 leftZ -= n; 303 SkASSERT(leftZ >= 0); 304 } 305 306 if (riteZ) { 307 // walk row to the end, and then we'll back up to trim riteZ 308 while (width > 0) { 309 int n = row[0]; 310 SkASSERT(n <= width); 311 width -= n; 312 row += 2; 313 } 314 // now skip whole runs of zeros 315 do { 316 row -= 2; 317 SkASSERT(0 == row[1]); 318 int n = row[0]; 319 SkASSERT(n > 0); 320 if (n > riteZ) { 321 row[0] = n - riteZ; 322 break; 323 } 324 riteZ -= n; 325 SkASSERT(riteZ >= 0); 326 } while (riteZ > 0); 327 } 328 329 return trim; 330} 331 332#ifdef SK_DEBUG 333// assert that this row is exactly this width 334static void assert_row_width(const uint8_t* row, int width) { 335 while (width > 0) { 336 int n = row[0]; 337 SkASSERT(n > 0); 338 SkASSERT(n <= width); 339 width -= n; 340 row += 2; 341 } 342 SkASSERT(0 == width); 343} 344 345static void test_trim_row_left_right() { 346 static bool gOnce; 347 if (gOnce) { 348 return; 349 } 350 gOnce = true; 351 352 uint8_t data0[] = { 0, 0, 0, 10, 10, 0xFF }; 353 uint8_t data1[] = { 2, 0, 0, 10, 5, 0, 2, 0, 3, 0xFF }; 354 uint8_t data2[] = { 5, 0, 2, 10, 5, 0, 2, 0, 3, 0xFF }; 355 uint8_t data3[] = { 6, 0, 2, 10, 5, 0, 2, 0, 3, 0xFF }; 356 uint8_t data4[] = { 0, 0, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 357 uint8_t data5[] = { 1, 0, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 358 uint8_t data6[] = { 0, 1, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 359 uint8_t data7[] = { 1, 1, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 360 uint8_t data8[] = { 2, 2, 2, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 }; 361 uint8_t data9[] = { 5, 2, 4, 10, 2, 0, 2, 0, 2, 0, 2, 0xFF, 2, 0 }; 362 uint8_t data10[] ={ 74, 0, 4, 150, 9, 0, 65, 0, 76, 0xFF }; 363 364 uint8_t* array[] = { 365 data0, data1, data2, data3, data4, 366 data5, data6, data7, data8, data9, 367 data10 368 }; 369 370 for (size_t i = 0; i < SK_ARRAY_COUNT(array); ++i) { 371 uint8_t* data = array[i]; 372 const int trimL = *data++; 373 const int trimR = *data++; 374 const int expectedSkip = *data++; 375 const int origWidth = *data++; 376 assert_row_width(data, origWidth); 377 int skip = trim_row_left_right(data, origWidth, trimL, trimR); 378 SkASSERT(expectedSkip == skip); 379 int expectedWidth = origWidth - trimL - trimR; 380 assert_row_width(data + skip, expectedWidth); 381 } 382} 383#endif 384 385bool SkAAClip::trimLeftRight() { 386 SkDEBUGCODE(test_trim_row_left_right();) 387 388 if (this->isEmpty()) { 389 return false; 390 } 391 392 AUTO_AACLIP_VALIDATE(*this); 393 394 const int width = fBounds.width(); 395 RunHead* head = fRunHead; 396 YOffset* yoff = head->yoffsets(); 397 YOffset* stop = yoff + head->fRowCount; 398 uint8_t* base = head->data(); 399 400 int leftZeros = width; 401 int riteZeros = width; 402 while (yoff < stop) { 403 int L, R; 404 count_left_right_zeros(base + yoff->fOffset, width, &L, &R); 405 if (L < leftZeros) { 406 leftZeros = L; 407 } 408 if (R < riteZeros) { 409 riteZeros = R; 410 } 411 if (0 == (leftZeros | riteZeros)) { 412 // no trimming to do 413 return true; 414 } 415 yoff += 1; 416 } 417 418 SkASSERT(leftZeros || riteZeros); 419 if (width == (leftZeros + riteZeros)) { 420 return this->setEmpty(); 421 } 422 423 this->validate(); 424 425 fBounds.fLeft += leftZeros; 426 fBounds.fRight -= riteZeros; 427 SkASSERT(!fBounds.isEmpty()); 428 429 // For now we don't realloc the storage (for time), we just shrink in place 430 // This means we don't have to do any memmoves either, since we can just 431 // play tricks with the yoff->fOffset for each row 432 yoff = head->yoffsets(); 433 while (yoff < stop) { 434 uint8_t* row = base + yoff->fOffset; 435 SkDEBUGCODE((void)compute_row_length(row, width);) 436 yoff->fOffset += trim_row_left_right(row, width, leftZeros, riteZeros); 437 SkDEBUGCODE((void)compute_row_length(base + yoff->fOffset, width - leftZeros - riteZeros);) 438 yoff += 1; 439 } 440 return true; 441} 442 443static bool row_is_all_zeros(const uint8_t* row, int width) { 444 SkASSERT(width > 0); 445 do { 446 if (row[1]) { 447 return false; 448 } 449 int n = row[0]; 450 SkASSERT(n <= width); 451 width -= n; 452 row += 2; 453 } while (width > 0); 454 SkASSERT(0 == width); 455 return true; 456} 457 458bool SkAAClip::trimTopBottom() { 459 if (this->isEmpty()) { 460 return false; 461 } 462 463 const int width = fBounds.width(); 464 RunHead* head = fRunHead; 465 YOffset* yoff = head->yoffsets(); 466 YOffset* stop = yoff + head->fRowCount; 467 const uint8_t* base = head->data(); 468 469 // Look to trim away empty rows from the top. 470 // 471 int skip = 0; 472 while (yoff < stop) { 473 const uint8_t* data = base + yoff->fOffset; 474 if (!row_is_all_zeros(data, width)) { 475 break; 476 } 477 skip += 1; 478 yoff += 1; 479 } 480 SkASSERT(skip <= head->fRowCount); 481 if (skip == head->fRowCount) { 482 return this->setEmpty(); 483 } 484 if (skip > 0) { 485 // adjust fRowCount and fBounds.fTop, and slide all the data up 486 // as we remove [skip] number of YOffset entries 487 yoff = head->yoffsets(); 488 int dy = yoff[skip - 1].fY + 1; 489 for (int i = skip; i < head->fRowCount; ++i) { 490 SkASSERT(yoff[i].fY >= dy); 491 yoff[i].fY -= dy; 492 } 493 YOffset* dst = head->yoffsets(); 494 size_t size = head->fRowCount * sizeof(YOffset) + head->fDataSize; 495 memmove(dst, dst + skip, size - skip * sizeof(YOffset)); 496 497 fBounds.fTop += dy; 498 SkASSERT(!fBounds.isEmpty()); 499 head->fRowCount -= skip; 500 SkASSERT(head->fRowCount > 0); 501 } 502 503 // Look to trim away empty rows from the bottom. 504 // We know that we have at least one non-zero row, so we can just walk 505 // backwards without checking for running past the start. 506 // 507 stop = yoff = head->yoffsets() + head->fRowCount; 508 do { 509 yoff -= 1; 510 } while (row_is_all_zeros(base + yoff->fOffset, width)); 511 skip = stop - yoff - 1; 512 SkASSERT(skip >= 0 && skip < head->fRowCount); 513 if (skip > 0) { 514 // removing from the bottom is easier than from the top, as we don't 515 // have to adjust any of the Y values, we just have to trim the array 516 memmove(stop - skip, stop, head->fDataSize); 517 518 fBounds.fBottom = fBounds.fTop + yoff->fY + 1; 519 SkASSERT(!fBounds.isEmpty()); 520 head->fRowCount -= skip; 521 SkASSERT(head->fRowCount > 0); 522 } 523 524 return true; 525} 526 527// can't validate before we're done, since trimming is part of the process of 528// making us valid after the Builder. Since we build from top to bottom, its 529// possible our fBounds.fBottom is bigger than our last scanline of data, so 530// we trim fBounds.fBottom back up. 531// 532// TODO: check for duplicates in X and Y to further compress our data 533// 534bool SkAAClip::trimBounds() { 535 if (this->isEmpty()) { 536 return false; 537 } 538 539 const RunHead* head = fRunHead; 540 const YOffset* yoff = head->yoffsets(); 541 542 SkASSERT(head->fRowCount > 0); 543 const YOffset& lastY = yoff[head->fRowCount - 1]; 544 SkASSERT(lastY.fY + 1 <= fBounds.height()); 545 fBounds.fBottom = fBounds.fTop + lastY.fY + 1; 546 SkASSERT(lastY.fY + 1 == fBounds.height()); 547 SkASSERT(!fBounds.isEmpty()); 548 549 return this->trimTopBottom() && this->trimLeftRight(); 550} 551 552/////////////////////////////////////////////////////////////////////////////// 553 554void SkAAClip::freeRuns() { 555 if (fRunHead) { 556 SkASSERT(fRunHead->fRefCnt >= 1); 557 if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) { 558 sk_free(fRunHead); 559 } 560 } 561} 562 563SkAAClip::SkAAClip() { 564 fBounds.setEmpty(); 565 fRunHead = NULL; 566} 567 568SkAAClip::SkAAClip(const SkAAClip& src) { 569 SkDEBUGCODE(fBounds.setEmpty();) // need this for validate 570 fRunHead = NULL; 571 *this = src; 572} 573 574SkAAClip::~SkAAClip() { 575 this->freeRuns(); 576} 577 578SkAAClip& SkAAClip::operator=(const SkAAClip& src) { 579 AUTO_AACLIP_VALIDATE(*this); 580 src.validate(); 581 582 if (this != &src) { 583 this->freeRuns(); 584 fBounds = src.fBounds; 585 fRunHead = src.fRunHead; 586 if (fRunHead) { 587 sk_atomic_inc(&fRunHead->fRefCnt); 588 } 589 } 590 return *this; 591} 592 593bool operator==(const SkAAClip& a, const SkAAClip& b) { 594 a.validate(); 595 b.validate(); 596 597 if (&a == &b) { 598 return true; 599 } 600 if (a.fBounds != b.fBounds) { 601 return false; 602 } 603 604 const SkAAClip::RunHead* ah = a.fRunHead; 605 const SkAAClip::RunHead* bh = b.fRunHead; 606 607 // this catches empties and rects being equal 608 if (ah == bh) { 609 return true; 610 } 611 612 // now we insist that both are complex (but different ptrs) 613 if (!a.fRunHead || !b.fRunHead) { 614 return false; 615 } 616 617 return ah->fRowCount == bh->fRowCount && 618 ah->fDataSize == bh->fDataSize && 619 !memcmp(ah->data(), bh->data(), ah->fDataSize); 620} 621 622void SkAAClip::swap(SkAAClip& other) { 623 AUTO_AACLIP_VALIDATE(*this); 624 other.validate(); 625 626 SkTSwap(fBounds, other.fBounds); 627 SkTSwap(fRunHead, other.fRunHead); 628} 629 630bool SkAAClip::set(const SkAAClip& src) { 631 *this = src; 632 return !this->isEmpty(); 633} 634 635bool SkAAClip::setEmpty() { 636 this->freeRuns(); 637 fBounds.setEmpty(); 638 fRunHead = NULL; 639 return false; 640} 641 642bool SkAAClip::setRect(const SkIRect& bounds) { 643 if (bounds.isEmpty()) { 644 return this->setEmpty(); 645 } 646 647 AUTO_AACLIP_VALIDATE(*this); 648 649#if 0 650 SkRect r; 651 r.set(bounds); 652 SkPath path; 653 path.addRect(r); 654 return this->setPath(path); 655#else 656 this->freeRuns(); 657 fBounds = bounds; 658 fRunHead = RunHead::AllocRect(bounds); 659 SkASSERT(!this->isEmpty()); 660 return true; 661#endif 662} 663 664bool SkAAClip::setRect(const SkRect& r, bool doAA) { 665 if (r.isEmpty()) { 666 return this->setEmpty(); 667 } 668 669 AUTO_AACLIP_VALIDATE(*this); 670 671 // TODO: special case this 672 673 SkPath path; 674 path.addRect(r); 675 return this->setPath(path, NULL, doAA); 676} 677 678bool SkAAClip::setRegion(const SkRegion& rgn) { 679 if (rgn.isEmpty()) { 680 return this->setEmpty(); 681 } 682 if (rgn.isRect()) { 683 return this->setRect(rgn.getBounds()); 684 } 685 686 SkAAClip clip; 687 SkRegion::Iterator iter(rgn); 688 for (; !iter.done(); iter.next()) { 689 clip.op(iter.rect(), SkRegion::kUnion_Op); 690 } 691 this->swap(clip); 692 return !this->isEmpty(); 693} 694 695/////////////////////////////////////////////////////////////////////////////// 696 697const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const { 698 SkASSERT(fRunHead); 699 700 if (!y_in_rect(y, fBounds)) { 701 return NULL; 702 } 703 y -= fBounds.y(); // our yoffs values are relative to the top 704 705 const YOffset* yoff = fRunHead->yoffsets(); 706 while (yoff->fY < y) { 707 yoff += 1; 708 SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount); 709 } 710 711 if (lastYForRow) { 712 *lastYForRow = fBounds.y() + yoff->fY; 713 } 714 return fRunHead->data() + yoff->fOffset; 715} 716 717const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const { 718 SkASSERT(x_in_rect(x, fBounds)); 719 x -= fBounds.x(); 720 721 // first skip up to X 722 for (;;) { 723 int n = data[0]; 724 if (x < n) { 725 *initialCount = n - x; 726 break; 727 } 728 data += 2; 729 x -= n; 730 } 731 return data; 732} 733 734bool SkAAClip::quickContains(int left, int top, int right, int bottom) const { 735 if (this->isEmpty()) { 736 return false; 737 } 738 if (!fBounds.contains(left, top, right, bottom)) { 739 return false; 740 } 741#if 0 742 if (this->isRect()) { 743 return true; 744 } 745#endif 746 747 int lastY; 748 const uint8_t* row = this->findRow(top, &lastY); 749 if (lastY < bottom) { 750 return false; 751 } 752 // now just need to check in X 753 int count; 754 row = this->findX(row, left, &count); 755#if 0 756 return count >= (right - left) && 0xFF == row[1]; 757#else 758 int rectWidth = right - left; 759 while (0xFF == row[1]) { 760 if (count >= rectWidth) { 761 return true; 762 } 763 rectWidth -= count; 764 row += 2; 765 count = row[0]; 766 } 767 return false; 768#endif 769} 770 771/////////////////////////////////////////////////////////////////////////////// 772 773class SkAAClip::Builder { 774 SkIRect fBounds; 775 struct Row { 776 int fY; 777 int fWidth; 778 SkTDArray<uint8_t>* fData; 779 }; 780 SkTDArray<Row> fRows; 781 Row* fCurrRow; 782 int fPrevY; 783 int fWidth; 784 int fMinY; 785 786public: 787 Builder(const SkIRect& bounds) : fBounds(bounds) { 788 fPrevY = -1; 789 fWidth = bounds.width(); 790 fCurrRow = NULL; 791 fMinY = bounds.fTop; 792 } 793 794 ~Builder() { 795 Row* row = fRows.begin(); 796 Row* stop = fRows.end(); 797 while (row < stop) { 798 delete row->fData; 799 row += 1; 800 } 801 } 802 803 const SkIRect& getBounds() const { return fBounds; } 804 805 void addRun(int x, int y, U8CPU alpha, int count) { 806 SkASSERT(count > 0); 807 SkASSERT(fBounds.contains(x, y)); 808 SkASSERT(fBounds.contains(x + count - 1, y)); 809 810 x -= fBounds.left(); 811 y -= fBounds.top(); 812 813 Row* row = fCurrRow; 814 if (y != fPrevY) { 815 SkASSERT(y > fPrevY); 816 fPrevY = y; 817 row = this->flushRow(true); 818 row->fY = y; 819 row->fWidth = 0; 820 SkASSERT(row->fData); 821 SkASSERT(0 == row->fData->count()); 822 fCurrRow = row; 823 } 824 825 SkASSERT(row->fWidth <= x); 826 SkASSERT(row->fWidth < fBounds.width()); 827 828 SkTDArray<uint8_t>& data = *row->fData; 829 830 int gap = x - row->fWidth; 831 if (gap) { 832 AppendRun(data, 0, gap); 833 row->fWidth += gap; 834 SkASSERT(row->fWidth < fBounds.width()); 835 } 836 837 AppendRun(data, alpha, count); 838 row->fWidth += count; 839 SkASSERT(row->fWidth <= fBounds.width()); 840 } 841 842 bool finish(SkAAClip* target) { 843 this->flushRow(false); 844 845 const Row* row = fRows.begin(); 846 const Row* stop = fRows.end(); 847 848 size_t dataSize = 0; 849 while (row < stop) { 850 dataSize += row->fData->count(); 851 row += 1; 852 } 853 854 if (0 == dataSize) { 855 return target->setEmpty(); 856 } 857 858 SkASSERT(fMinY >= fBounds.fTop); 859 SkASSERT(fMinY < fBounds.fBottom); 860 int adjustY = fMinY - fBounds.fTop; 861 fBounds.fTop = fMinY; 862 863 RunHead* head = RunHead::Alloc(fRows.count(), dataSize); 864 YOffset* yoffset = head->yoffsets(); 865 uint8_t* data = head->data(); 866 uint8_t* baseData = data; 867 868 row = fRows.begin(); 869 SkDEBUGCODE(int prevY = row->fY - 1;) 870 while (row < stop) { 871 SkASSERT(prevY < row->fY); // must be monotonic 872 SkDEBUGCODE(prevY = row->fY); 873 874 yoffset->fY = row->fY - adjustY; 875 yoffset->fOffset = data - baseData; 876 yoffset += 1; 877 878 size_t n = row->fData->count(); 879 memcpy(data, row->fData->begin(), n); 880#ifdef SK_DEBUG 881 int bytesNeeded = compute_row_length(data, fBounds.width()); 882 SkASSERT(bytesNeeded == n); 883#endif 884 data += n; 885 886 row += 1; 887 } 888 889 target->freeRuns(); 890 target->fBounds = fBounds; 891 target->fRunHead = head; 892 return target->trimBounds(); 893 } 894 895 void dump() { 896 this->validate(); 897 int y; 898 for (y = 0; y < fRows.count(); ++y) { 899 const Row& row = fRows[y]; 900 SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth); 901 const SkTDArray<uint8_t>& data = *row.fData; 902 int count = data.count(); 903 SkASSERT(!(count & 1)); 904 const uint8_t* ptr = data.begin(); 905 for (int x = 0; x < count; x += 2) { 906 SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]); 907 ptr += 2; 908 } 909 SkDebugf("\n"); 910 } 911 } 912 913 void validate() { 914#ifdef SK_DEBUG 915 int prevY = -1; 916 for (int i = 0; i < fRows.count(); ++i) { 917 const Row& row = fRows[i]; 918 SkASSERT(prevY < row.fY); 919 SkASSERT(fWidth == row.fWidth); 920 int count = row.fData->count(); 921 const uint8_t* ptr = row.fData->begin(); 922 SkASSERT(!(count & 1)); 923 int w = 0; 924 for (int x = 0; x < count; x += 2) { 925 w += ptr[0]; 926 SkASSERT(w <= fWidth); 927 ptr += 2; 928 } 929 SkASSERT(w == fWidth); 930 prevY = row.fY; 931 } 932#endif 933 } 934 935 // only called by BuilderBlitter 936 void setMinY(int y) { 937 fMinY = y; 938 } 939 940private: 941 942 Row* flushRow(bool readyForAnother) { 943 Row* next = NULL; 944 int count = fRows.count(); 945 if (count > 0) { 946 // flush current row if needed 947 Row* curr = &fRows[count - 1]; 948 if (curr->fWidth < fWidth) { 949 AppendRun(*curr->fData, 0, fWidth - curr->fWidth); 950 curr->fWidth = fWidth; 951 } 952 } 953 if (count > 1) { 954 // are our last two runs the same? 955 Row* prev = &fRows[count - 2]; 956 Row* curr = &fRows[count - 1]; 957 SkASSERT(prev->fWidth == fWidth); 958 SkASSERT(curr->fWidth == fWidth); 959 if (*prev->fData == *curr->fData) { 960 prev->fY = curr->fY; 961 if (readyForAnother) { 962 curr->fData->rewind(); 963 next = curr; 964 } else { 965 delete curr->fData; 966 fRows.removeShuffle(count - 1); 967 } 968 } else { 969 if (readyForAnother) { 970 next = fRows.append(); 971 next->fData = new SkTDArray<uint8_t>; 972 } 973 } 974 } else { 975 if (readyForAnother) { 976 next = fRows.append(); 977 next->fData = new SkTDArray<uint8_t>; 978 } 979 } 980 return next; 981 } 982 983 static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) { 984 do { 985 int n = count; 986 if (n > 255) { 987 n = 255; 988 } 989 uint8_t* ptr = data.append(2); 990 ptr[0] = n; 991 ptr[1] = alpha; 992 count -= n; 993 } while (count > 0); 994 } 995}; 996 997class SkAAClip::BuilderBlitter : public SkBlitter { 998public: 999 BuilderBlitter(Builder* builder) { 1000 fBuilder = builder; 1001 fLeft = builder->getBounds().fLeft; 1002 fRight = builder->getBounds().fRight; 1003 fMinY = SK_MaxS32; 1004 } 1005 1006 void finish() { 1007 if (fMinY < SK_MaxS32) { 1008 fBuilder->setMinY(fMinY); 1009 } 1010 } 1011 1012 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE 1013 { unexpected(); } 1014 1015 // let the default impl call blitH 1016// virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE 1017 1018 virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE 1019 { unexpected(); } 1020 1021 virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE { 1022 return NULL; 1023 } 1024 1025 virtual void blitH(int x, int y, int width) SK_OVERRIDE { 1026 this->recordMinY(y); 1027 fBuilder->addRun(x, y, 0xFF, width); 1028 } 1029 1030 virtual void blitAntiH(int x, int y, const SkAlpha alpha[], 1031 const int16_t runs[]) SK_OVERRIDE { 1032 this->recordMinY(y); 1033 for (;;) { 1034 int count = *runs; 1035 if (count <= 0) { 1036 return; 1037 } 1038 1039 // The supersampler's buffer can be the width of the device, so 1040 // we may have to trim the run to our bounds. If so, we assert that 1041 // the extra spans are always alpha==0 1042 int localX = x; 1043 int localCount = count; 1044 if (x < fLeft) { 1045 SkASSERT(0 == *alpha); 1046 int gap = fLeft - x; 1047 SkASSERT(gap <= count); 1048 localX += gap; 1049 localCount -= gap; 1050 } 1051 int right = x + count; 1052 if (right > fRight) { 1053 SkASSERT(0 == *alpha); 1054 localCount -= right - fRight; 1055 SkASSERT(localCount >= 0); 1056 } 1057 1058 if (localCount) { 1059 fBuilder->addRun(localX, y, *alpha, localCount); 1060 } 1061 // Next run 1062 runs += count; 1063 alpha += count; 1064 x += count; 1065 } 1066 } 1067 1068private: 1069 Builder* fBuilder; 1070 int fLeft; // cache of builder's bounds' left edge 1071 int fRight; 1072 int fMinY; 1073 1074 /* 1075 * We track this, in case the scan converter skipped some number of 1076 * scanlines at the (relative to the bounds it was given). This allows 1077 * the builder, during its finish, to trip its bounds down to the "real" 1078 * top. 1079 */ 1080 void recordMinY(int y) { 1081 if (y < fMinY) { 1082 fMinY = y; 1083 } 1084 } 1085 1086 void unexpected() { 1087 SkDebugf("---- did not expect to get called here"); 1088 sk_throw(); 1089 } 1090}; 1091 1092bool SkAAClip::setPath(const SkPath& path, const SkRegion* clip, bool doAA) { 1093 AUTO_AACLIP_VALIDATE(*this); 1094 1095 if (clip && clip->isEmpty()) { 1096 return this->setEmpty(); 1097 } 1098 1099 SkIRect ibounds; 1100 path.getBounds().roundOut(&ibounds); 1101 1102 SkRegion tmpClip; 1103 if (NULL == clip) { 1104 tmpClip.setRect(ibounds); 1105 clip = &tmpClip; 1106 } 1107 1108 if (path.isInverseFillType()) { 1109 ibounds = clip->getBounds(); 1110 } else { 1111 if (ibounds.isEmpty() || !ibounds.intersect(clip->getBounds())) { 1112 return this->setEmpty(); 1113 } 1114 } 1115 1116 Builder builder(ibounds); 1117 BuilderBlitter blitter(&builder); 1118 1119 if (doAA) { 1120 SkScan::AntiFillPath(path, *clip, &blitter, true); 1121 } else { 1122 SkScan::FillPath(path, *clip, &blitter); 1123 } 1124 1125 blitter.finish(); 1126 return builder.finish(this); 1127} 1128 1129/////////////////////////////////////////////////////////////////////////////// 1130 1131typedef void (*RowProc)(SkAAClip::Builder&, int bottom, 1132 const uint8_t* rowA, const SkIRect& rectA, 1133 const uint8_t* rowB, const SkIRect& rectB); 1134 1135static void sectRowProc(SkAAClip::Builder& builder, int bottom, 1136 const uint8_t* rowA, const SkIRect& rectA, 1137 const uint8_t* rowB, const SkIRect& rectB) { 1138 1139} 1140 1141typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB); 1142 1143static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1144 // Multiply 1145 return SkMulDiv255Round(alphaA, alphaB); 1146} 1147 1148static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1149 // SrcOver 1150 return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB); 1151} 1152 1153static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1154 // SrcOut 1155 return SkMulDiv255Round(alphaA, 0xFF - alphaB); 1156} 1157 1158static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1159 // XOR 1160 return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB); 1161} 1162 1163static AlphaProc find_alpha_proc(SkRegion::Op op) { 1164 switch (op) { 1165 case SkRegion::kIntersect_Op: 1166 return sectAlphaProc; 1167 case SkRegion::kDifference_Op: 1168 return diffAlphaProc; 1169 case SkRegion::kUnion_Op: 1170 return unionAlphaProc; 1171 case SkRegion::kXOR_Op: 1172 return xorAlphaProc; 1173 default: 1174 SkASSERT(!"unexpected region op"); 1175 return sectAlphaProc; 1176 } 1177} 1178 1179static const uint8_t gEmptyRow[] = { 1180 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1181 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1182 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1183 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1184 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1185 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1186 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1187 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1188}; 1189 1190class RowIter { 1191public: 1192 RowIter(const uint8_t* row, const SkIRect& bounds) { 1193 fRow = row; 1194 fLeft = bounds.fLeft; 1195 fBoundsRight = bounds.fRight; 1196 if (row) { 1197 fRight = bounds.fLeft + row[0]; 1198 SkASSERT(fRight <= fBoundsRight); 1199 fAlpha = row[1]; 1200 fDone = false; 1201 } else { 1202 fDone = true; 1203 fRight = kMaxInt32; 1204 fAlpha = 0; 1205 } 1206 } 1207 1208 bool done() const { return fDone; } 1209 int left() const { return fLeft; } 1210 int right() const { return fRight; } 1211 U8CPU alpha() const { return fAlpha; } 1212 void next() { 1213 if (!fDone) { 1214 fLeft = fRight; 1215 if (fRight == fBoundsRight) { 1216 fDone = true; 1217 fRight = kMaxInt32; 1218 fAlpha = 0; 1219 } else { 1220 fRow += 2; 1221 fRight += fRow[0]; 1222 fAlpha = fRow[1]; 1223 SkASSERT(fRight <= fBoundsRight); 1224 } 1225 } 1226 } 1227 1228private: 1229 const uint8_t* fRow; 1230 int fLeft; 1231 int fRight; 1232 int fBoundsRight; 1233 bool fDone; 1234 uint8_t fAlpha; 1235}; 1236 1237static void adjust_row(RowIter& iter, int& leftA, int& riteA, int rite) { 1238 if (rite == riteA) { 1239 iter.next(); 1240 leftA = iter.left(); 1241 riteA = iter.right(); 1242 } 1243} 1244 1245static bool intersect(int& min, int& max, int boundsMin, int boundsMax) { 1246 SkASSERT(min < max); 1247 SkASSERT(boundsMin < boundsMax); 1248 if (min >= boundsMax || max <= boundsMin) { 1249 return false; 1250 } 1251 if (min < boundsMin) { 1252 min = boundsMin; 1253 } 1254 if (max > boundsMax) { 1255 max = boundsMax; 1256 } 1257 return true; 1258} 1259 1260static void operatorX(SkAAClip::Builder& builder, int lastY, 1261 RowIter& iterA, RowIter& iterB, 1262 AlphaProc proc, const SkIRect& bounds) { 1263 int leftA = iterA.left(); 1264 int riteA = iterA.right(); 1265 int leftB = iterB.left(); 1266 int riteB = iterB.right(); 1267 1268 int prevRite = bounds.fLeft; 1269 1270 do { 1271 U8CPU alphaA = 0; 1272 U8CPU alphaB = 0; 1273 int left, rite; 1274 1275 if (leftA < leftB) { 1276 left = leftA; 1277 alphaA = iterA.alpha(); 1278 if (riteA <= leftB) { 1279 rite = riteA; 1280 } else { 1281 rite = leftA = leftB; 1282 } 1283 } else if (leftB < leftA) { 1284 left = leftB; 1285 alphaB = iterB.alpha(); 1286 if (riteB <= leftA) { 1287 rite = riteB; 1288 } else { 1289 rite = leftB = leftA; 1290 } 1291 } else { 1292 left = leftA; // or leftB, since leftA == leftB 1293 rite = leftA = leftB = SkMin32(riteA, riteB); 1294 alphaA = iterA.alpha(); 1295 alphaB = iterB.alpha(); 1296 } 1297 1298 if (left >= bounds.fRight) { 1299 break; 1300 } 1301 if (rite > bounds.fRight) { 1302 rite = bounds.fRight; 1303 } 1304 1305 if (left >= bounds.fLeft) { 1306 SkASSERT(rite > left); 1307 builder.addRun(left, lastY, proc(alphaA, alphaB), rite - left); 1308 prevRite = rite; 1309 } 1310 1311 adjust_row(iterA, leftA, riteA, rite); 1312 adjust_row(iterB, leftB, riteB, rite); 1313 } while (!iterA.done() || !iterB.done()); 1314 1315 if (prevRite < bounds.fRight) { 1316 builder.addRun(prevRite, lastY, 0, bounds.fRight - prevRite); 1317 } 1318} 1319 1320static void adjust_iter(SkAAClip::Iter& iter, int& topA, int& botA, int bot) { 1321 if (bot == botA) { 1322 iter.next(); 1323 topA = botA; 1324 SkASSERT(botA == iter.top()); 1325 botA = iter.bottom(); 1326 } 1327} 1328 1329static void operateY(SkAAClip::Builder& builder, const SkAAClip& A, 1330 const SkAAClip& B, SkRegion::Op op) { 1331 AlphaProc proc = find_alpha_proc(op); 1332 const SkIRect& bounds = builder.getBounds(); 1333 1334 SkAAClip::Iter iterA(A); 1335 SkAAClip::Iter iterB(B); 1336 1337 SkASSERT(!iterA.done()); 1338 int topA = iterA.top(); 1339 int botA = iterA.bottom(); 1340 SkASSERT(!iterB.done()); 1341 int topB = iterB.top(); 1342 int botB = iterB.bottom(); 1343 1344 do { 1345 const uint8_t* rowA = NULL; 1346 const uint8_t* rowB = NULL; 1347 int top, bot; 1348 1349 if (topA < topB) { 1350 top = topA; 1351 rowA = iterA.data(); 1352 if (botA <= topB) { 1353 bot = botA; 1354 } else { 1355 bot = topA = topB; 1356 } 1357 1358 } else if (topB < topA) { 1359 top = topB; 1360 rowB = iterB.data(); 1361 if (botB <= topA) { 1362 bot = botB; 1363 } else { 1364 bot = topB = topA; 1365 } 1366 } else { 1367 top = topA; // or topB, since topA == topB 1368 bot = topA = topB = SkMin32(botA, botB); 1369 rowA = iterA.data(); 1370 rowB = iterB.data(); 1371 } 1372 1373 if (top >= bounds.fBottom) { 1374 break; 1375 } 1376 1377 if (bot > bounds.fBottom) { 1378 bot = bounds.fBottom; 1379 } 1380 SkASSERT(top < bot); 1381 1382 if (!rowA && !rowB) { 1383 builder.addRun(bounds.fLeft, bot - 1, 0, bounds.width()); 1384 } else if (top >= bounds.fTop) { 1385 SkASSERT(bot <= bounds.fBottom); 1386 RowIter rowIterA(rowA, rowA ? A.getBounds() : bounds); 1387 RowIter rowIterB(rowB, rowB ? B.getBounds() : bounds); 1388 operatorX(builder, bot - 1, rowIterA, rowIterB, proc, bounds); 1389 } 1390 1391 adjust_iter(iterA, topA, botA, bot); 1392 adjust_iter(iterB, topB, botB, bot); 1393 } while (!iterA.done() || !iterB.done()); 1394} 1395 1396bool SkAAClip::op(const SkAAClip& clipAOrig, const SkAAClip& clipBOrig, 1397 SkRegion::Op op) { 1398 AUTO_AACLIP_VALIDATE(*this); 1399 1400 if (SkRegion::kReplace_Op == op) { 1401 return this->set(clipBOrig); 1402 } 1403 1404 const SkAAClip* clipA = &clipAOrig; 1405 const SkAAClip* clipB = &clipBOrig; 1406 1407 if (SkRegion::kReverseDifference_Op == op) { 1408 SkTSwap(clipA, clipB); 1409 op = SkRegion::kDifference_Op; 1410 } 1411 1412 bool a_empty = clipA->isEmpty(); 1413 bool b_empty = clipB->isEmpty(); 1414 1415 SkIRect bounds; 1416 switch (op) { 1417 case SkRegion::kDifference_Op: 1418 if (a_empty) { 1419 return this->setEmpty(); 1420 } 1421 if (b_empty || !SkIRect::Intersects(clipA->fBounds, clipB->fBounds)) { 1422 return this->set(*clipA); 1423 } 1424 bounds = clipA->fBounds; 1425 break; 1426 1427 case SkRegion::kIntersect_Op: 1428 if ((a_empty | b_empty) || !bounds.intersect(clipA->fBounds, 1429 clipB->fBounds)) { 1430 return this->setEmpty(); 1431 } 1432 break; 1433 1434 case SkRegion::kUnion_Op: 1435 case SkRegion::kXOR_Op: 1436 if (a_empty) { 1437 return this->set(*clipB); 1438 } 1439 if (b_empty) { 1440 return this->set(*clipA); 1441 } 1442 bounds = clipA->fBounds; 1443 bounds.join(clipB->fBounds); 1444 break; 1445 1446 default: 1447 SkASSERT(!"unknown region op"); 1448 return !this->isEmpty(); 1449 } 1450 1451 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 1452 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 1453 1454 Builder builder(bounds); 1455 operateY(builder, *clipA, *clipB, op); 1456 1457 return builder.finish(this); 1458} 1459 1460/* 1461 * It can be expensive to build a local aaclip before applying the op, so 1462 * we first see if we can restrict the bounds of new rect to our current 1463 * bounds, or note that the new rect subsumes our current clip. 1464 */ 1465 1466bool SkAAClip::op(const SkIRect& rOrig, SkRegion::Op op) { 1467 SkIRect rStorage; 1468 const SkIRect* r = &rOrig; 1469 1470 switch (op) { 1471 case SkRegion::kIntersect_Op: 1472 if (!rStorage.intersect(rOrig, fBounds)) { 1473 // no overlap, so we're empty 1474 return this->setEmpty(); 1475 } 1476 if (rStorage == fBounds) { 1477 // we were wholly inside the rect, no change 1478 return !this->isEmpty(); 1479 } 1480 if (this->quickContains(rStorage)) { 1481 // the intersection is wholly inside us, we're a rect 1482 return this->setRect(rStorage); 1483 } 1484 r = &rStorage; // use the intersected bounds 1485 break; 1486 case SkRegion::kDifference_Op: 1487 break; 1488 case SkRegion::kUnion_Op: 1489 if (rOrig.contains(fBounds)) { 1490 return this->setRect(rOrig); 1491 } 1492 break; 1493 default: 1494 break; 1495 } 1496 1497 SkAAClip clip; 1498 clip.setRect(*r); 1499 return this->op(*this, clip, op); 1500} 1501 1502bool SkAAClip::op(const SkRect& rOrig, SkRegion::Op op, bool doAA) { 1503 SkRect rStorage, boundsStorage; 1504 const SkRect* r = &rOrig; 1505 1506 boundsStorage.set(fBounds); 1507 switch (op) { 1508 case SkRegion::kIntersect_Op: 1509 case SkRegion::kDifference_Op: 1510 if (!rStorage.intersect(rOrig, boundsStorage)) { 1511 return this->setEmpty(); 1512 } 1513 r = &rStorage; // use the intersected bounds 1514 break; 1515 case SkRegion::kUnion_Op: 1516 if (rOrig.contains(boundsStorage)) { 1517 return this->setRect(rOrig); 1518 } 1519 break; 1520 default: 1521 break; 1522 } 1523 1524 SkAAClip clip; 1525 clip.setRect(*r, doAA); 1526 return this->op(*this, clip, op); 1527} 1528 1529bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) { 1530 return this->op(*this, clip, op); 1531} 1532 1533/////////////////////////////////////////////////////////////////////////////// 1534 1535bool SkAAClip::translate(int dx, int dy, SkAAClip* dst) const { 1536 if (NULL == dst) { 1537 return !this->isEmpty(); 1538 } 1539 1540 if (this->isEmpty()) { 1541 return dst->setEmpty(); 1542 } 1543 1544 if (this != dst) { 1545 sk_atomic_inc(&fRunHead->fRefCnt); 1546 dst->fRunHead = fRunHead; 1547 dst->fBounds = fBounds; 1548 } 1549 dst->fBounds.offset(dx, dy); 1550 return true; 1551} 1552 1553static void expand_row_to_mask(uint8_t* SK_RESTRICT mask, 1554 const uint8_t* SK_RESTRICT row, 1555 int width) { 1556 while (width > 0) { 1557 int n = row[0]; 1558 SkASSERT(width >= n); 1559 memset(mask, row[1], n); 1560 mask += n; 1561 row += 2; 1562 width -= n; 1563 } 1564} 1565 1566void SkAAClip::copyToMask(SkMask* mask) const { 1567 mask->fFormat = SkMask::kA8_Format; 1568 if (this->isEmpty()) { 1569 mask->fBounds.setEmpty(); 1570 mask->fImage = NULL; 1571 mask->fRowBytes = 0; 1572 return; 1573 } 1574 1575 mask->fBounds = fBounds; 1576 mask->fRowBytes = fBounds.width(); 1577 size_t size = mask->computeImageSize(); 1578 mask->fImage = SkMask::AllocImage(size); 1579 1580 Iter iter(*this); 1581 uint8_t* dst = mask->fImage; 1582 const int width = fBounds.width(); 1583 1584 int y = fBounds.fTop; 1585 while (!iter.done()) { 1586 do { 1587 expand_row_to_mask(dst, iter.data(), width); 1588 dst += mask->fRowBytes; 1589 } while (++y < iter.bottom()); 1590 iter.next(); 1591 } 1592} 1593 1594/////////////////////////////////////////////////////////////////////////////// 1595/////////////////////////////////////////////////////////////////////////////// 1596 1597static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width, 1598 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) { 1599 // we don't read our initial n from data, since the caller may have had to 1600 // clip it, hence the initialCount parameter. 1601 int n = initialCount; 1602 for (;;) { 1603 if (n > width) { 1604 n = width; 1605 } 1606 SkASSERT(n > 0); 1607 runs[0] = n; 1608 runs += n; 1609 1610 aa[0] = data[1]; 1611 aa += n; 1612 1613 data += 2; 1614 width -= n; 1615 if (0 == width) { 1616 break; 1617 } 1618 // load the next count 1619 n = data[0]; 1620 } 1621 runs[0] = 0; // sentinel 1622} 1623 1624SkAAClipBlitter::~SkAAClipBlitter() { 1625 sk_free(fScanlineScratch); 1626} 1627 1628void SkAAClipBlitter::ensureRunsAndAA() { 1629 if (NULL == fScanlineScratch) { 1630 // add 1 so we can store the terminating run count of 0 1631 int count = fAAClipBounds.width() + 1; 1632 // we use this either for fRuns + fAA, or a scaline of a mask 1633 // which may be as deep as 32bits 1634 fScanlineScratch = sk_malloc_throw(count * sizeof(SkPMColor)); 1635 fRuns = (int16_t*)fScanlineScratch; 1636 fAA = (SkAlpha*)(fRuns + count); 1637 } 1638} 1639 1640void SkAAClipBlitter::blitH(int x, int y, int width) { 1641 SkASSERT(width > 0); 1642 SkASSERT(fAAClipBounds.contains(x, y)); 1643 SkASSERT(fAAClipBounds.contains(x + width - 1, y)); 1644 1645 int lastY; 1646 const uint8_t* row = fAAClip->findRow(y, &lastY); 1647 int initialCount; 1648 row = fAAClip->findX(row, x, &initialCount); 1649 1650 if (initialCount >= width) { 1651 SkAlpha alpha = row[1]; 1652 if (0 == alpha) { 1653 return; 1654 } 1655 if (0xFF == alpha) { 1656 fBlitter->blitH(x, y, width); 1657 return; 1658 } 1659 } 1660 1661 this->ensureRunsAndAA(); 1662 expandToRuns(row, initialCount, width, fRuns, fAA); 1663 1664 fBlitter->blitAntiH(x, y, fAA, fRuns); 1665} 1666 1667static void merge(const uint8_t* SK_RESTRICT row, int rowN, 1668 const SkAlpha* SK_RESTRICT srcAA, 1669 const int16_t* SK_RESTRICT srcRuns, 1670 SkAlpha* SK_RESTRICT dstAA, 1671 int16_t* SK_RESTRICT dstRuns, 1672 int width) { 1673 SkDEBUGCODE(int accumulated = 0;) 1674 int srcN = srcRuns[0]; 1675 // do we need this check? 1676 if (0 == srcN) { 1677 return; 1678 } 1679 1680 for (;;) { 1681 SkASSERT(rowN > 0); 1682 SkASSERT(srcN > 0); 1683 1684 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]); 1685 int minN = SkMin32(srcN, rowN); 1686 dstRuns[0] = minN; 1687 dstRuns += minN; 1688 dstAA[0] = newAlpha; 1689 dstAA += minN; 1690 1691 if (0 == (srcN -= minN)) { 1692 srcN = srcRuns[0]; // refresh 1693 srcRuns += srcN; 1694 srcAA += srcN; 1695 srcN = srcRuns[0]; // reload 1696 if (0 == srcN) { 1697 break; 1698 } 1699 } 1700 if (0 == (rowN -= minN)) { 1701 row += 2; 1702 rowN = row[0]; // reload 1703 } 1704 1705 SkDEBUGCODE(accumulated += minN;) 1706 SkASSERT(accumulated <= width); 1707 } 1708 dstRuns[0] = 0; 1709} 1710 1711void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[], 1712 const int16_t runs[]) { 1713 int lastY; 1714 const uint8_t* row = fAAClip->findRow(y, &lastY); 1715 int initialCount; 1716 row = fAAClip->findX(row, x, &initialCount); 1717 1718 this->ensureRunsAndAA(); 1719 1720 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width()); 1721 fBlitter->blitAntiH(x, y, fAA, fRuns); 1722} 1723 1724void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) { 1725 if (fAAClip->quickContains(x, y, x + 1, y + height)) { 1726 fBlitter->blitV(x, y, height, alpha); 1727 return; 1728 } 1729 1730 for (;;) { 1731 int lastY; 1732 const uint8_t* row = fAAClip->findRow(y, &lastY); 1733 int dy = lastY - y + 1; 1734 if (dy > height) { 1735 dy = height; 1736 } 1737 height -= dy; 1738 1739 int initialCount; 1740 row = fAAClip->findX(row, x, &initialCount); 1741 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]); 1742 if (newAlpha) { 1743 fBlitter->blitV(x, y, dy, newAlpha); 1744 } 1745 SkASSERT(height >= 0); 1746 if (height <= 0) { 1747 break; 1748 } 1749 y = lastY + 1; 1750 } 1751} 1752 1753void SkAAClipBlitter::blitRect(int x, int y, int width, int height) { 1754 if (fAAClip->quickContains(x, y, x + width, y + height)) { 1755 fBlitter->blitRect(x, y, width, height); 1756 return; 1757 } 1758 1759 while (--height >= 0) { 1760 this->blitH(x, y, width); 1761 y += 1; 1762 } 1763} 1764 1765typedef void (*MergeAAProc)(const void* src, int width, const uint8_t* row, 1766 int initialRowCount, void* dst); 1767 1768static void small_memcpy(void* dst, const void* src, size_t n) { 1769 memcpy(dst, src, n); 1770} 1771 1772static void small_bzero(void* dst, size_t n) { 1773 sk_bzero(dst, n); 1774} 1775 1776static inline uint8_t mergeOne(uint8_t value, unsigned alpha) { 1777 return SkMulDiv255Round(value, alpha); 1778} 1779static inline uint16_t mergeOne(uint16_t value, unsigned alpha) { 1780 unsigned r = SkGetPackedR16(value); 1781 unsigned g = SkGetPackedG16(value); 1782 unsigned b = SkGetPackedB16(value); 1783 return SkPackRGB16(SkMulDiv255Round(r, alpha), 1784 SkMulDiv255Round(r, alpha), 1785 SkMulDiv255Round(r, alpha)); 1786} 1787static inline SkPMColor mergeOne(SkPMColor value, unsigned alpha) { 1788 unsigned a = SkGetPackedA32(value); 1789 unsigned r = SkGetPackedR32(value); 1790 unsigned g = SkGetPackedG32(value); 1791 unsigned b = SkGetPackedB32(value); 1792 return SkPackARGB32(SkMulDiv255Round(a, alpha), 1793 SkMulDiv255Round(r, alpha), 1794 SkMulDiv255Round(g, alpha), 1795 SkMulDiv255Round(b, alpha)); 1796} 1797 1798template <typename T> void mergeT(const T* SK_RESTRICT src, int srcN, 1799 const uint8_t* SK_RESTRICT row, int rowN, 1800 T* SK_RESTRICT dst) { 1801 SkDEBUGCODE(int accumulated = 0;) 1802 for (;;) { 1803 SkASSERT(rowN > 0); 1804 SkASSERT(srcN > 0); 1805 1806 int n = SkMin32(rowN, srcN); 1807 unsigned rowA = row[1]; 1808 if (0xFF == rowA) { 1809 small_memcpy(dst, src, n * sizeof(T)); 1810 } else if (0 == rowA) { 1811 small_bzero(dst, n * sizeof(T)); 1812 } else { 1813 for (int i = 0; i < n; ++i) { 1814 dst[i] = mergeOne(src[i], rowA); 1815 } 1816 } 1817 1818 if (0 == (srcN -= n)) { 1819 break; 1820 } 1821 1822 src += n; 1823 dst += n; 1824 1825 SkASSERT(rowN == n); 1826 row += 2; 1827 rowN = row[0]; 1828 } 1829} 1830 1831static MergeAAProc find_merge_aa_proc(SkMask::Format format) { 1832 switch (format) { 1833 case SkMask::kBW_Format: 1834 SkASSERT(!"unsupported"); 1835 return NULL; 1836 case SkMask::kA8_Format: 1837 case SkMask::k3D_Format: { 1838 void (*proc8)(const uint8_t*, int, const uint8_t*, int, uint8_t*) = mergeT; 1839 return (MergeAAProc)proc8; 1840 } 1841 case SkMask::kLCD16_Format: { 1842 void (*proc16)(const uint16_t*, int, const uint8_t*, int, uint16_t*) = mergeT; 1843 return (MergeAAProc)proc16; 1844 } 1845 case SkMask::kLCD32_Format: { 1846 void (*proc32)(const SkPMColor*, int, const uint8_t*, int, SkPMColor*) = mergeT; 1847 return (MergeAAProc)proc32; 1848 } 1849 default: 1850 SkASSERT(!"unsupported"); 1851 return NULL; 1852 } 1853} 1854 1855static U8CPU bit2byte(int bitInAByte) { 1856 SkASSERT(bitInAByte <= 0xFF); 1857 // negation turns any non-zero into 0xFFFFFF??, so we just shift down 1858 // some value >= 8 to get a full FF value 1859 return -bitInAByte >> 8; 1860} 1861 1862static void upscaleBW2A8(SkMask* dstMask, const SkMask& srcMask) { 1863 SkASSERT(SkMask::kBW_Format == srcMask.fFormat); 1864 SkASSERT(SkMask::kA8_Format == dstMask->fFormat); 1865 1866 const int width = srcMask.fBounds.width(); 1867 const int height = srcMask.fBounds.height(); 1868 1869 const uint8_t* SK_RESTRICT src = (const uint8_t*)srcMask.fImage; 1870 const size_t srcRB = srcMask.fRowBytes; 1871 uint8_t* SK_RESTRICT dst = (uint8_t*)dstMask->fImage; 1872 const size_t dstRB = dstMask->fRowBytes; 1873 1874 const int wholeBytes = width >> 3; 1875 const int leftOverBits = width & 7; 1876 1877 for (int y = 0; y < height; ++y) { 1878 uint8_t* SK_RESTRICT d = dst; 1879 for (int i = 0; i < wholeBytes; ++i) { 1880 int srcByte = src[i]; 1881 d[0] = bit2byte(srcByte & (1 << 7)); 1882 d[1] = bit2byte(srcByte & (1 << 6)); 1883 d[2] = bit2byte(srcByte & (1 << 5)); 1884 d[3] = bit2byte(srcByte & (1 << 4)); 1885 d[4] = bit2byte(srcByte & (1 << 3)); 1886 d[5] = bit2byte(srcByte & (1 << 2)); 1887 d[6] = bit2byte(srcByte & (1 << 1)); 1888 d[7] = bit2byte(srcByte & (1 << 0)); 1889 d += 8; 1890 } 1891 if (leftOverBits) { 1892 int srcByte = src[wholeBytes]; 1893 for (int x = 0; x < leftOverBits; ++x) { 1894 *d++ = bit2byte(srcByte & 0x80); 1895 srcByte <<= 1; 1896 } 1897 } 1898 src += srcRB; 1899 dst += dstRB; 1900 } 1901} 1902 1903void SkAAClipBlitter::blitMask(const SkMask& origMask, const SkIRect& clip) { 1904 SkASSERT(fAAClip->getBounds().contains(clip)); 1905 1906 if (fAAClip->quickContains(clip)) { 1907 fBlitter->blitMask(origMask, clip); 1908 return; 1909 } 1910 1911 const SkMask* mask = &origMask; 1912 1913 // if we're BW, we need to upscale to A8 (ugh) 1914 SkMask grayMask; 1915 grayMask.fImage = NULL; 1916 if (SkMask::kBW_Format == origMask.fFormat) { 1917 grayMask.fFormat = SkMask::kA8_Format; 1918 grayMask.fBounds = origMask.fBounds; 1919 grayMask.fRowBytes = origMask.fBounds.width(); 1920 size_t size = grayMask.computeImageSize(); 1921 grayMask.fImage = (uint8_t*)fGrayMaskScratch.reset(size, 1922 SkAutoMalloc::kReuse_OnShrink); 1923 1924 upscaleBW2A8(&grayMask, origMask); 1925 mask = &grayMask; 1926 } 1927 1928 this->ensureRunsAndAA(); 1929 1930 // HACK -- we are devolving 3D into A8, need to copy the rest of the 3D 1931 // data into a temp block to support it better (ugh) 1932 1933 const void* src = mask->getAddr(clip.fLeft, clip.fTop); 1934 const size_t srcRB = mask->fRowBytes; 1935 const int width = clip.width(); 1936 MergeAAProc mergeProc = find_merge_aa_proc(mask->fFormat); 1937 1938 SkMask rowMask; 1939 rowMask.fFormat = SkMask::k3D_Format == mask->fFormat ? SkMask::kA8_Format : mask->fFormat; 1940 rowMask.fBounds.fLeft = clip.fLeft; 1941 rowMask.fBounds.fRight = clip.fRight; 1942 rowMask.fRowBytes = mask->fRowBytes; // doesn't matter, since our height==1 1943 rowMask.fImage = (uint8_t*)fScanlineScratch; 1944 1945 int y = clip.fTop; 1946 const int stopY = y + clip.height(); 1947 1948 do { 1949 int localStopY; 1950 const uint8_t* row = fAAClip->findRow(y, &localStopY); 1951 // findRow returns last Y, not stop, so we add 1 1952 localStopY = SkMin32(localStopY + 1, stopY); 1953 1954 int initialCount; 1955 row = fAAClip->findX(row, clip.fLeft, &initialCount); 1956 do { 1957 mergeProc(src, width, row, initialCount, rowMask.fImage); 1958 rowMask.fBounds.fTop = y; 1959 rowMask.fBounds.fBottom = y + 1; 1960 fBlitter->blitMask(rowMask, rowMask.fBounds); 1961 src = (const void*)((const char*)src + srcRB); 1962 } while (++y < localStopY); 1963 } while (y < stopY); 1964} 1965 1966const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) { 1967 return NULL; 1968} 1969 1970