SkAAClip.cpp revision 562a2ac95b8cd8b359574f8c4d6300b0475938db
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 this->validate(); 464 465 const int width = fBounds.width(); 466 RunHead* head = fRunHead; 467 YOffset* yoff = head->yoffsets(); 468 YOffset* stop = yoff + head->fRowCount; 469 const uint8_t* base = head->data(); 470 471 // Look to trim away empty rows from the top. 472 // 473 int skip = 0; 474 while (yoff < stop) { 475 const uint8_t* data = base + yoff->fOffset; 476 if (!row_is_all_zeros(data, width)) { 477 break; 478 } 479 skip += 1; 480 yoff += 1; 481 } 482 SkASSERT(skip <= head->fRowCount); 483 if (skip == head->fRowCount) { 484 return this->setEmpty(); 485 } 486 if (skip > 0) { 487 // adjust fRowCount and fBounds.fTop, and slide all the data up 488 // as we remove [skip] number of YOffset entries 489 yoff = head->yoffsets(); 490 int dy = yoff[skip - 1].fY + 1; 491 for (int i = skip; i < head->fRowCount; ++i) { 492 SkASSERT(yoff[i].fY >= dy); 493 yoff[i].fY -= dy; 494 } 495 YOffset* dst = head->yoffsets(); 496 size_t size = head->fRowCount * sizeof(YOffset) + head->fDataSize; 497 memmove(dst, dst + skip, size - skip * sizeof(YOffset)); 498 499 fBounds.fTop += dy; 500 SkASSERT(!fBounds.isEmpty()); 501 head->fRowCount -= skip; 502 SkASSERT(head->fRowCount > 0); 503 504 this->validate(); 505 // need to reset this after the memmove 506 base = head->data(); 507 } 508 509 // Look to trim away empty rows from the bottom. 510 // We know that we have at least one non-zero row, so we can just walk 511 // backwards without checking for running past the start. 512 // 513 stop = yoff = head->yoffsets() + head->fRowCount; 514 do { 515 yoff -= 1; 516 } while (row_is_all_zeros(base + yoff->fOffset, width)); 517 skip = stop - yoff - 1; 518 SkASSERT(skip >= 0 && skip < head->fRowCount); 519 if (skip > 0) { 520 // removing from the bottom is easier than from the top, as we don't 521 // have to adjust any of the Y values, we just have to trim the array 522 memmove(stop - skip, stop, head->fDataSize); 523 524 fBounds.fBottom = fBounds.fTop + yoff->fY + 1; 525 SkASSERT(!fBounds.isEmpty()); 526 head->fRowCount -= skip; 527 SkASSERT(head->fRowCount > 0); 528 } 529 this->validate(); 530 531 return true; 532} 533 534// can't validate before we're done, since trimming is part of the process of 535// making us valid after the Builder. Since we build from top to bottom, its 536// possible our fBounds.fBottom is bigger than our last scanline of data, so 537// we trim fBounds.fBottom back up. 538// 539// TODO: check for duplicates in X and Y to further compress our data 540// 541bool SkAAClip::trimBounds() { 542 if (this->isEmpty()) { 543 return false; 544 } 545 546 const RunHead* head = fRunHead; 547 const YOffset* yoff = head->yoffsets(); 548 549 SkASSERT(head->fRowCount > 0); 550 const YOffset& lastY = yoff[head->fRowCount - 1]; 551 SkASSERT(lastY.fY + 1 <= fBounds.height()); 552 fBounds.fBottom = fBounds.fTop + lastY.fY + 1; 553 SkASSERT(lastY.fY + 1 == fBounds.height()); 554 SkASSERT(!fBounds.isEmpty()); 555 556 return this->trimTopBottom() && this->trimLeftRight(); 557} 558 559/////////////////////////////////////////////////////////////////////////////// 560 561void SkAAClip::freeRuns() { 562 if (fRunHead) { 563 SkASSERT(fRunHead->fRefCnt >= 1); 564 if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) { 565 sk_free(fRunHead); 566 } 567 } 568} 569 570SkAAClip::SkAAClip() { 571 fBounds.setEmpty(); 572 fRunHead = NULL; 573} 574 575SkAAClip::SkAAClip(const SkAAClip& src) { 576 SkDEBUGCODE(fBounds.setEmpty();) // need this for validate 577 fRunHead = NULL; 578 *this = src; 579} 580 581SkAAClip::~SkAAClip() { 582 this->freeRuns(); 583} 584 585SkAAClip& SkAAClip::operator=(const SkAAClip& src) { 586 AUTO_AACLIP_VALIDATE(*this); 587 src.validate(); 588 589 if (this != &src) { 590 this->freeRuns(); 591 fBounds = src.fBounds; 592 fRunHead = src.fRunHead; 593 if (fRunHead) { 594 sk_atomic_inc(&fRunHead->fRefCnt); 595 } 596 } 597 return *this; 598} 599 600bool operator==(const SkAAClip& a, const SkAAClip& b) { 601 a.validate(); 602 b.validate(); 603 604 if (&a == &b) { 605 return true; 606 } 607 if (a.fBounds != b.fBounds) { 608 return false; 609 } 610 611 const SkAAClip::RunHead* ah = a.fRunHead; 612 const SkAAClip::RunHead* bh = b.fRunHead; 613 614 // this catches empties and rects being equal 615 if (ah == bh) { 616 return true; 617 } 618 619 // now we insist that both are complex (but different ptrs) 620 if (!a.fRunHead || !b.fRunHead) { 621 return false; 622 } 623 624 return ah->fRowCount == bh->fRowCount && 625 ah->fDataSize == bh->fDataSize && 626 !memcmp(ah->data(), bh->data(), ah->fDataSize); 627} 628 629void SkAAClip::swap(SkAAClip& other) { 630 AUTO_AACLIP_VALIDATE(*this); 631 other.validate(); 632 633 SkTSwap(fBounds, other.fBounds); 634 SkTSwap(fRunHead, other.fRunHead); 635} 636 637bool SkAAClip::set(const SkAAClip& src) { 638 *this = src; 639 return !this->isEmpty(); 640} 641 642bool SkAAClip::setEmpty() { 643 this->freeRuns(); 644 fBounds.setEmpty(); 645 fRunHead = NULL; 646 return false; 647} 648 649bool SkAAClip::setRect(const SkIRect& bounds) { 650 if (bounds.isEmpty()) { 651 return this->setEmpty(); 652 } 653 654 AUTO_AACLIP_VALIDATE(*this); 655 656#if 0 657 SkRect r; 658 r.set(bounds); 659 SkPath path; 660 path.addRect(r); 661 return this->setPath(path); 662#else 663 this->freeRuns(); 664 fBounds = bounds; 665 fRunHead = RunHead::AllocRect(bounds); 666 SkASSERT(!this->isEmpty()); 667 return true; 668#endif 669} 670 671bool SkAAClip::setRect(const SkRect& r, bool doAA) { 672 if (r.isEmpty()) { 673 return this->setEmpty(); 674 } 675 676 AUTO_AACLIP_VALIDATE(*this); 677 678 // TODO: special case this 679 680 SkPath path; 681 path.addRect(r); 682 return this->setPath(path, NULL, doAA); 683} 684 685bool SkAAClip::setRegion(const SkRegion& rgn) { 686 if (rgn.isEmpty()) { 687 return this->setEmpty(); 688 } 689 if (rgn.isRect()) { 690 return this->setRect(rgn.getBounds()); 691 } 692 693 SkAAClip clip; 694 SkRegion::Iterator iter(rgn); 695 for (; !iter.done(); iter.next()) { 696 clip.op(iter.rect(), SkRegion::kUnion_Op); 697 } 698 this->swap(clip); 699 return !this->isEmpty(); 700} 701 702/////////////////////////////////////////////////////////////////////////////// 703 704const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const { 705 SkASSERT(fRunHead); 706 707 if (!y_in_rect(y, fBounds)) { 708 return NULL; 709 } 710 y -= fBounds.y(); // our yoffs values are relative to the top 711 712 const YOffset* yoff = fRunHead->yoffsets(); 713 while (yoff->fY < y) { 714 yoff += 1; 715 SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount); 716 } 717 718 if (lastYForRow) { 719 *lastYForRow = fBounds.y() + yoff->fY; 720 } 721 return fRunHead->data() + yoff->fOffset; 722} 723 724const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const { 725 SkASSERT(x_in_rect(x, fBounds)); 726 x -= fBounds.x(); 727 728 // first skip up to X 729 for (;;) { 730 int n = data[0]; 731 if (x < n) { 732 *initialCount = n - x; 733 break; 734 } 735 data += 2; 736 x -= n; 737 } 738 return data; 739} 740 741bool SkAAClip::quickContains(int left, int top, int right, int bottom) const { 742 if (this->isEmpty()) { 743 return false; 744 } 745 if (!fBounds.contains(left, top, right, bottom)) { 746 return false; 747 } 748#if 0 749 if (this->isRect()) { 750 return true; 751 } 752#endif 753 754 int lastY; 755 const uint8_t* row = this->findRow(top, &lastY); 756 if (lastY < bottom) { 757 return false; 758 } 759 // now just need to check in X 760 int count; 761 row = this->findX(row, left, &count); 762#if 0 763 return count >= (right - left) && 0xFF == row[1]; 764#else 765 int rectWidth = right - left; 766 while (0xFF == row[1]) { 767 if (count >= rectWidth) { 768 return true; 769 } 770 rectWidth -= count; 771 row += 2; 772 count = row[0]; 773 } 774 return false; 775#endif 776} 777 778/////////////////////////////////////////////////////////////////////////////// 779 780class SkAAClip::Builder { 781 SkIRect fBounds; 782 struct Row { 783 int fY; 784 int fWidth; 785 SkTDArray<uint8_t>* fData; 786 }; 787 SkTDArray<Row> fRows; 788 Row* fCurrRow; 789 int fPrevY; 790 int fWidth; 791 int fMinY; 792 793public: 794 Builder(const SkIRect& bounds) : fBounds(bounds) { 795 fPrevY = -1; 796 fWidth = bounds.width(); 797 fCurrRow = NULL; 798 fMinY = bounds.fTop; 799 } 800 801 ~Builder() { 802 Row* row = fRows.begin(); 803 Row* stop = fRows.end(); 804 while (row < stop) { 805 delete row->fData; 806 row += 1; 807 } 808 } 809 810 const SkIRect& getBounds() const { return fBounds; } 811 812 void addRun(int x, int y, U8CPU alpha, int count) { 813 SkASSERT(count > 0); 814 SkASSERT(fBounds.contains(x, y)); 815 SkASSERT(fBounds.contains(x + count - 1, y)); 816 817 x -= fBounds.left(); 818 y -= fBounds.top(); 819 820 Row* row = fCurrRow; 821 if (y != fPrevY) { 822 SkASSERT(y > fPrevY); 823 fPrevY = y; 824 row = this->flushRow(true); 825 row->fY = y; 826 row->fWidth = 0; 827 SkASSERT(row->fData); 828 SkASSERT(0 == row->fData->count()); 829 fCurrRow = row; 830 } 831 832 SkASSERT(row->fWidth <= x); 833 SkASSERT(row->fWidth < fBounds.width()); 834 835 SkTDArray<uint8_t>& data = *row->fData; 836 837 int gap = x - row->fWidth; 838 if (gap) { 839 AppendRun(data, 0, gap); 840 row->fWidth += gap; 841 SkASSERT(row->fWidth < fBounds.width()); 842 } 843 844 AppendRun(data, alpha, count); 845 row->fWidth += count; 846 SkASSERT(row->fWidth <= fBounds.width()); 847 } 848 849 bool finish(SkAAClip* target) { 850 this->flushRow(false); 851 852 const Row* row = fRows.begin(); 853 const Row* stop = fRows.end(); 854 855 size_t dataSize = 0; 856 while (row < stop) { 857 dataSize += row->fData->count(); 858 row += 1; 859 } 860 861 if (0 == dataSize) { 862 return target->setEmpty(); 863 } 864 865 SkASSERT(fMinY >= fBounds.fTop); 866 SkASSERT(fMinY < fBounds.fBottom); 867 int adjustY = fMinY - fBounds.fTop; 868 fBounds.fTop = fMinY; 869 870 RunHead* head = RunHead::Alloc(fRows.count(), dataSize); 871 YOffset* yoffset = head->yoffsets(); 872 uint8_t* data = head->data(); 873 uint8_t* baseData = data; 874 875 row = fRows.begin(); 876 SkDEBUGCODE(int prevY = row->fY - 1;) 877 while (row < stop) { 878 SkASSERT(prevY < row->fY); // must be monotonic 879 SkDEBUGCODE(prevY = row->fY); 880 881 yoffset->fY = row->fY - adjustY; 882 yoffset->fOffset = data - baseData; 883 yoffset += 1; 884 885 size_t n = row->fData->count(); 886 memcpy(data, row->fData->begin(), n); 887#ifdef SK_DEBUG 888 int bytesNeeded = compute_row_length(data, fBounds.width()); 889 SkASSERT(bytesNeeded == n); 890#endif 891 data += n; 892 893 row += 1; 894 } 895 896 target->freeRuns(); 897 target->fBounds = fBounds; 898 target->fRunHead = head; 899 return target->trimBounds(); 900 } 901 902 void dump() { 903 this->validate(); 904 int y; 905 for (y = 0; y < fRows.count(); ++y) { 906 const Row& row = fRows[y]; 907 SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth); 908 const SkTDArray<uint8_t>& data = *row.fData; 909 int count = data.count(); 910 SkASSERT(!(count & 1)); 911 const uint8_t* ptr = data.begin(); 912 for (int x = 0; x < count; x += 2) { 913 SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]); 914 ptr += 2; 915 } 916 SkDebugf("\n"); 917 } 918 } 919 920 void validate() { 921#ifdef SK_DEBUG 922 int prevY = -1; 923 for (int i = 0; i < fRows.count(); ++i) { 924 const Row& row = fRows[i]; 925 SkASSERT(prevY < row.fY); 926 SkASSERT(fWidth == row.fWidth); 927 int count = row.fData->count(); 928 const uint8_t* ptr = row.fData->begin(); 929 SkASSERT(!(count & 1)); 930 int w = 0; 931 for (int x = 0; x < count; x += 2) { 932 int n = ptr[0]; 933 SkASSERT(n > 0); 934 w += n; 935 SkASSERT(w <= fWidth); 936 ptr += 2; 937 } 938 SkASSERT(w == fWidth); 939 prevY = row.fY; 940 } 941#endif 942 } 943 944 // only called by BuilderBlitter 945 void setMinY(int y) { 946 fMinY = y; 947 } 948 949private: 950 951 Row* flushRow(bool readyForAnother) { 952 Row* next = NULL; 953 int count = fRows.count(); 954 if (count > 0) { 955 // flush current row if needed 956 Row* curr = &fRows[count - 1]; 957 if (curr->fWidth < fWidth) { 958 AppendRun(*curr->fData, 0, fWidth - curr->fWidth); 959 curr->fWidth = fWidth; 960 } 961 } 962 if (count > 1) { 963 // are our last two runs the same? 964 Row* prev = &fRows[count - 2]; 965 Row* curr = &fRows[count - 1]; 966 SkASSERT(prev->fWidth == fWidth); 967 SkASSERT(curr->fWidth == fWidth); 968 if (*prev->fData == *curr->fData) { 969 prev->fY = curr->fY; 970 if (readyForAnother) { 971 curr->fData->rewind(); 972 next = curr; 973 } else { 974 delete curr->fData; 975 fRows.removeShuffle(count - 1); 976 } 977 } else { 978 if (readyForAnother) { 979 next = fRows.append(); 980 next->fData = new SkTDArray<uint8_t>; 981 } 982 } 983 } else { 984 if (readyForAnother) { 985 next = fRows.append(); 986 next->fData = new SkTDArray<uint8_t>; 987 } 988 } 989 return next; 990 } 991 992 static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) { 993 do { 994 int n = count; 995 if (n > 255) { 996 n = 255; 997 } 998 uint8_t* ptr = data.append(2); 999 ptr[0] = n; 1000 ptr[1] = alpha; 1001 count -= n; 1002 } while (count > 0); 1003 } 1004}; 1005 1006class SkAAClip::BuilderBlitter : public SkBlitter { 1007public: 1008 BuilderBlitter(Builder* builder) { 1009 fBuilder = builder; 1010 fLeft = builder->getBounds().fLeft; 1011 fRight = builder->getBounds().fRight; 1012 fMinY = SK_MaxS32; 1013 } 1014 1015 void finish() { 1016 if (fMinY < SK_MaxS32) { 1017 fBuilder->setMinY(fMinY); 1018 } 1019 } 1020 1021 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE 1022 { unexpected(); } 1023 1024 virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE { 1025// SkDebugf("blitRect Y:%d H:%d\n", y, height); 1026 while (--height >= 0) { 1027 this->blitH(x, y++, width); 1028 } 1029 } 1030 1031 virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE 1032 { unexpected(); } 1033 1034 virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE { 1035 return NULL; 1036 } 1037 1038 virtual void blitH(int x, int y, int width) SK_OVERRIDE { 1039 this->recordMinY(y); 1040 fBuilder->addRun(x, y, 0xFF, width); 1041 } 1042 1043 virtual void blitAntiH(int x, int y, const SkAlpha alpha[], 1044 const int16_t runs[]) SK_OVERRIDE { 1045 this->recordMinY(y); 1046 for (;;) { 1047 int count = *runs; 1048 if (count <= 0) { 1049 return; 1050 } 1051 1052 // The supersampler's buffer can be the width of the device, so 1053 // we may have to trim the run to our bounds. If so, we assert that 1054 // the extra spans are always alpha==0 1055 int localX = x; 1056 int localCount = count; 1057 if (x < fLeft) { 1058 SkASSERT(0 == *alpha); 1059 int gap = fLeft - x; 1060 SkASSERT(gap <= count); 1061 localX += gap; 1062 localCount -= gap; 1063 } 1064 int right = x + count; 1065 if (right > fRight) { 1066 SkASSERT(0 == *alpha); 1067 localCount -= right - fRight; 1068 SkASSERT(localCount >= 0); 1069 } 1070 1071 if (localCount) { 1072 fBuilder->addRun(localX, y, *alpha, localCount); 1073 } 1074 // Next run 1075 runs += count; 1076 alpha += count; 1077 x += count; 1078 } 1079 } 1080 1081private: 1082 Builder* fBuilder; 1083 int fLeft; // cache of builder's bounds' left edge 1084 int fRight; 1085 int fMinY; 1086 1087 /* 1088 * We track this, in case the scan converter skipped some number of 1089 * scanlines at the (relative to the bounds it was given). This allows 1090 * the builder, during its finish, to trip its bounds down to the "real" 1091 * top. 1092 */ 1093 void recordMinY(int y) { 1094 if (y < fMinY) { 1095 fMinY = y; 1096 } 1097 } 1098 1099 void unexpected() { 1100 SkDebugf("---- did not expect to get called here"); 1101 sk_throw(); 1102 } 1103}; 1104 1105bool SkAAClip::setPath(const SkPath& path, const SkRegion* clip, bool doAA) { 1106 AUTO_AACLIP_VALIDATE(*this); 1107 1108 if (clip && clip->isEmpty()) { 1109 return this->setEmpty(); 1110 } 1111 1112 SkIRect ibounds; 1113 path.getBounds().roundOut(&ibounds); 1114 1115 SkRegion tmpClip; 1116 if (NULL == clip) { 1117 tmpClip.setRect(ibounds); 1118 clip = &tmpClip; 1119 } 1120 1121 if (path.isInverseFillType()) { 1122 ibounds = clip->getBounds(); 1123 } else { 1124 if (ibounds.isEmpty() || !ibounds.intersect(clip->getBounds())) { 1125 return this->setEmpty(); 1126 } 1127 } 1128 1129 Builder builder(ibounds); 1130 BuilderBlitter blitter(&builder); 1131 1132 if (doAA) { 1133 SkScan::AntiFillPath(path, *clip, &blitter, true); 1134 } else { 1135 SkScan::FillPath(path, *clip, &blitter); 1136 } 1137 1138 blitter.finish(); 1139 return builder.finish(this); 1140} 1141 1142/////////////////////////////////////////////////////////////////////////////// 1143 1144typedef void (*RowProc)(SkAAClip::Builder&, int bottom, 1145 const uint8_t* rowA, const SkIRect& rectA, 1146 const uint8_t* rowB, const SkIRect& rectB); 1147 1148static void sectRowProc(SkAAClip::Builder& builder, int bottom, 1149 const uint8_t* rowA, const SkIRect& rectA, 1150 const uint8_t* rowB, const SkIRect& rectB) { 1151 1152} 1153 1154typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB); 1155 1156static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1157 // Multiply 1158 return SkMulDiv255Round(alphaA, alphaB); 1159} 1160 1161static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1162 // SrcOver 1163 return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB); 1164} 1165 1166static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1167 // SrcOut 1168 return SkMulDiv255Round(alphaA, 0xFF - alphaB); 1169} 1170 1171static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) { 1172 // XOR 1173 return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB); 1174} 1175 1176static AlphaProc find_alpha_proc(SkRegion::Op op) { 1177 switch (op) { 1178 case SkRegion::kIntersect_Op: 1179 return sectAlphaProc; 1180 case SkRegion::kDifference_Op: 1181 return diffAlphaProc; 1182 case SkRegion::kUnion_Op: 1183 return unionAlphaProc; 1184 case SkRegion::kXOR_Op: 1185 return xorAlphaProc; 1186 default: 1187 SkASSERT(!"unexpected region op"); 1188 return sectAlphaProc; 1189 } 1190} 1191 1192static const uint8_t gEmptyRow[] = { 1193 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1194 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1195 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1196 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1197 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1198 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1199 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1200 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0, 1201}; 1202 1203class RowIter { 1204public: 1205 RowIter(const uint8_t* row, const SkIRect& bounds) { 1206 fRow = row; 1207 fLeft = bounds.fLeft; 1208 fBoundsRight = bounds.fRight; 1209 if (row) { 1210 fRight = bounds.fLeft + row[0]; 1211 SkASSERT(fRight <= fBoundsRight); 1212 fAlpha = row[1]; 1213 fDone = false; 1214 } else { 1215 fDone = true; 1216 fRight = kMaxInt32; 1217 fAlpha = 0; 1218 } 1219 } 1220 1221 bool done() const { return fDone; } 1222 int left() const { return fLeft; } 1223 int right() const { return fRight; } 1224 U8CPU alpha() const { return fAlpha; } 1225 void next() { 1226 if (!fDone) { 1227 fLeft = fRight; 1228 if (fRight == fBoundsRight) { 1229 fDone = true; 1230 fRight = kMaxInt32; 1231 fAlpha = 0; 1232 } else { 1233 fRow += 2; 1234 fRight += fRow[0]; 1235 fAlpha = fRow[1]; 1236 SkASSERT(fRight <= fBoundsRight); 1237 } 1238 } 1239 } 1240 1241private: 1242 const uint8_t* fRow; 1243 int fLeft; 1244 int fRight; 1245 int fBoundsRight; 1246 bool fDone; 1247 uint8_t fAlpha; 1248}; 1249 1250static void adjust_row(RowIter& iter, int& leftA, int& riteA, int rite) { 1251 if (rite == riteA) { 1252 iter.next(); 1253 leftA = iter.left(); 1254 riteA = iter.right(); 1255 } 1256} 1257 1258static bool intersect(int& min, int& max, int boundsMin, int boundsMax) { 1259 SkASSERT(min < max); 1260 SkASSERT(boundsMin < boundsMax); 1261 if (min >= boundsMax || max <= boundsMin) { 1262 return false; 1263 } 1264 if (min < boundsMin) { 1265 min = boundsMin; 1266 } 1267 if (max > boundsMax) { 1268 max = boundsMax; 1269 } 1270 return true; 1271} 1272 1273static void operatorX(SkAAClip::Builder& builder, int lastY, 1274 RowIter& iterA, RowIter& iterB, 1275 AlphaProc proc, const SkIRect& bounds) { 1276 int leftA = iterA.left(); 1277 int riteA = iterA.right(); 1278 int leftB = iterB.left(); 1279 int riteB = iterB.right(); 1280 1281 int prevRite = bounds.fLeft; 1282 1283 do { 1284 U8CPU alphaA = 0; 1285 U8CPU alphaB = 0; 1286 int left, rite; 1287 1288 if (leftA < leftB) { 1289 left = leftA; 1290 alphaA = iterA.alpha(); 1291 if (riteA <= leftB) { 1292 rite = riteA; 1293 } else { 1294 rite = leftA = leftB; 1295 } 1296 } else if (leftB < leftA) { 1297 left = leftB; 1298 alphaB = iterB.alpha(); 1299 if (riteB <= leftA) { 1300 rite = riteB; 1301 } else { 1302 rite = leftB = leftA; 1303 } 1304 } else { 1305 left = leftA; // or leftB, since leftA == leftB 1306 rite = leftA = leftB = SkMin32(riteA, riteB); 1307 alphaA = iterA.alpha(); 1308 alphaB = iterB.alpha(); 1309 } 1310 1311 if (left >= bounds.fRight) { 1312 break; 1313 } 1314 if (rite > bounds.fRight) { 1315 rite = bounds.fRight; 1316 } 1317 1318 if (left >= bounds.fLeft) { 1319 SkASSERT(rite > left); 1320 builder.addRun(left, lastY, proc(alphaA, alphaB), rite - left); 1321 prevRite = rite; 1322 } 1323 1324 adjust_row(iterA, leftA, riteA, rite); 1325 adjust_row(iterB, leftB, riteB, rite); 1326 } while (!iterA.done() || !iterB.done()); 1327 1328 if (prevRite < bounds.fRight) { 1329 builder.addRun(prevRite, lastY, 0, bounds.fRight - prevRite); 1330 } 1331} 1332 1333static void adjust_iter(SkAAClip::Iter& iter, int& topA, int& botA, int bot) { 1334 if (bot == botA) { 1335 iter.next(); 1336 topA = botA; 1337 SkASSERT(botA == iter.top()); 1338 botA = iter.bottom(); 1339 } 1340} 1341 1342static void operateY(SkAAClip::Builder& builder, const SkAAClip& A, 1343 const SkAAClip& B, SkRegion::Op op) { 1344 AlphaProc proc = find_alpha_proc(op); 1345 const SkIRect& bounds = builder.getBounds(); 1346 1347 SkAAClip::Iter iterA(A); 1348 SkAAClip::Iter iterB(B); 1349 1350 SkASSERT(!iterA.done()); 1351 int topA = iterA.top(); 1352 int botA = iterA.bottom(); 1353 SkASSERT(!iterB.done()); 1354 int topB = iterB.top(); 1355 int botB = iterB.bottom(); 1356 1357 do { 1358 const uint8_t* rowA = NULL; 1359 const uint8_t* rowB = NULL; 1360 int top, bot; 1361 1362 if (topA < topB) { 1363 top = topA; 1364 rowA = iterA.data(); 1365 if (botA <= topB) { 1366 bot = botA; 1367 } else { 1368 bot = topA = topB; 1369 } 1370 1371 } else if (topB < topA) { 1372 top = topB; 1373 rowB = iterB.data(); 1374 if (botB <= topA) { 1375 bot = botB; 1376 } else { 1377 bot = topB = topA; 1378 } 1379 } else { 1380 top = topA; // or topB, since topA == topB 1381 bot = topA = topB = SkMin32(botA, botB); 1382 rowA = iterA.data(); 1383 rowB = iterB.data(); 1384 } 1385 1386 if (top >= bounds.fBottom) { 1387 break; 1388 } 1389 1390 if (bot > bounds.fBottom) { 1391 bot = bounds.fBottom; 1392 } 1393 SkASSERT(top < bot); 1394 1395 if (!rowA && !rowB) { 1396 builder.addRun(bounds.fLeft, bot - 1, 0, bounds.width()); 1397 } else if (top >= bounds.fTop) { 1398 SkASSERT(bot <= bounds.fBottom); 1399 RowIter rowIterA(rowA, rowA ? A.getBounds() : bounds); 1400 RowIter rowIterB(rowB, rowB ? B.getBounds() : bounds); 1401 operatorX(builder, bot - 1, rowIterA, rowIterB, proc, bounds); 1402 } 1403 1404 adjust_iter(iterA, topA, botA, bot); 1405 adjust_iter(iterB, topB, botB, bot); 1406 } while (!iterA.done() || !iterB.done()); 1407} 1408 1409bool SkAAClip::op(const SkAAClip& clipAOrig, const SkAAClip& clipBOrig, 1410 SkRegion::Op op) { 1411 AUTO_AACLIP_VALIDATE(*this); 1412 1413 if (SkRegion::kReplace_Op == op) { 1414 return this->set(clipBOrig); 1415 } 1416 1417 const SkAAClip* clipA = &clipAOrig; 1418 const SkAAClip* clipB = &clipBOrig; 1419 1420 if (SkRegion::kReverseDifference_Op == op) { 1421 SkTSwap(clipA, clipB); 1422 op = SkRegion::kDifference_Op; 1423 } 1424 1425 bool a_empty = clipA->isEmpty(); 1426 bool b_empty = clipB->isEmpty(); 1427 1428 SkIRect bounds; 1429 switch (op) { 1430 case SkRegion::kDifference_Op: 1431 if (a_empty) { 1432 return this->setEmpty(); 1433 } 1434 if (b_empty || !SkIRect::Intersects(clipA->fBounds, clipB->fBounds)) { 1435 return this->set(*clipA); 1436 } 1437 bounds = clipA->fBounds; 1438 break; 1439 1440 case SkRegion::kIntersect_Op: 1441 if ((a_empty | b_empty) || !bounds.intersect(clipA->fBounds, 1442 clipB->fBounds)) { 1443 return this->setEmpty(); 1444 } 1445 break; 1446 1447 case SkRegion::kUnion_Op: 1448 case SkRegion::kXOR_Op: 1449 if (a_empty) { 1450 return this->set(*clipB); 1451 } 1452 if (b_empty) { 1453 return this->set(*clipA); 1454 } 1455 bounds = clipA->fBounds; 1456 bounds.join(clipB->fBounds); 1457 break; 1458 1459 default: 1460 SkASSERT(!"unknown region op"); 1461 return !this->isEmpty(); 1462 } 1463 1464 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 1465 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds)); 1466 1467 Builder builder(bounds); 1468 operateY(builder, *clipA, *clipB, op); 1469 1470 return builder.finish(this); 1471} 1472 1473/* 1474 * It can be expensive to build a local aaclip before applying the op, so 1475 * we first see if we can restrict the bounds of new rect to our current 1476 * bounds, or note that the new rect subsumes our current clip. 1477 */ 1478 1479bool SkAAClip::op(const SkIRect& rOrig, SkRegion::Op op) { 1480 SkIRect rStorage; 1481 const SkIRect* r = &rOrig; 1482 1483 switch (op) { 1484 case SkRegion::kIntersect_Op: 1485 if (!rStorage.intersect(rOrig, fBounds)) { 1486 // no overlap, so we're empty 1487 return this->setEmpty(); 1488 } 1489 if (rStorage == fBounds) { 1490 // we were wholly inside the rect, no change 1491 return !this->isEmpty(); 1492 } 1493 if (this->quickContains(rStorage)) { 1494 // the intersection is wholly inside us, we're a rect 1495 return this->setRect(rStorage); 1496 } 1497 r = &rStorage; // use the intersected bounds 1498 break; 1499 case SkRegion::kDifference_Op: 1500 break; 1501 case SkRegion::kUnion_Op: 1502 if (rOrig.contains(fBounds)) { 1503 return this->setRect(rOrig); 1504 } 1505 break; 1506 default: 1507 break; 1508 } 1509 1510 SkAAClip clip; 1511 clip.setRect(*r); 1512 return this->op(*this, clip, op); 1513} 1514 1515bool SkAAClip::op(const SkRect& rOrig, SkRegion::Op op, bool doAA) { 1516 SkRect rStorage, boundsStorage; 1517 const SkRect* r = &rOrig; 1518 1519 boundsStorage.set(fBounds); 1520 switch (op) { 1521 case SkRegion::kIntersect_Op: 1522 case SkRegion::kDifference_Op: 1523 if (!rStorage.intersect(rOrig, boundsStorage)) { 1524 return this->setEmpty(); 1525 } 1526 r = &rStorage; // use the intersected bounds 1527 break; 1528 case SkRegion::kUnion_Op: 1529 if (rOrig.contains(boundsStorage)) { 1530 return this->setRect(rOrig); 1531 } 1532 break; 1533 default: 1534 break; 1535 } 1536 1537 SkAAClip clip; 1538 clip.setRect(*r, doAA); 1539 return this->op(*this, clip, op); 1540} 1541 1542bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) { 1543 return this->op(*this, clip, op); 1544} 1545 1546/////////////////////////////////////////////////////////////////////////////// 1547 1548bool SkAAClip::translate(int dx, int dy, SkAAClip* dst) const { 1549 if (NULL == dst) { 1550 return !this->isEmpty(); 1551 } 1552 1553 if (this->isEmpty()) { 1554 return dst->setEmpty(); 1555 } 1556 1557 if (this != dst) { 1558 sk_atomic_inc(&fRunHead->fRefCnt); 1559 dst->fRunHead = fRunHead; 1560 dst->fBounds = fBounds; 1561 } 1562 dst->fBounds.offset(dx, dy); 1563 return true; 1564} 1565 1566static void expand_row_to_mask(uint8_t* SK_RESTRICT mask, 1567 const uint8_t* SK_RESTRICT row, 1568 int width) { 1569 while (width > 0) { 1570 int n = row[0]; 1571 SkASSERT(width >= n); 1572 memset(mask, row[1], n); 1573 mask += n; 1574 row += 2; 1575 width -= n; 1576 } 1577} 1578 1579void SkAAClip::copyToMask(SkMask* mask) const { 1580 mask->fFormat = SkMask::kA8_Format; 1581 if (this->isEmpty()) { 1582 mask->fBounds.setEmpty(); 1583 mask->fImage = NULL; 1584 mask->fRowBytes = 0; 1585 return; 1586 } 1587 1588 mask->fBounds = fBounds; 1589 mask->fRowBytes = fBounds.width(); 1590 size_t size = mask->computeImageSize(); 1591 mask->fImage = SkMask::AllocImage(size); 1592 1593 Iter iter(*this); 1594 uint8_t* dst = mask->fImage; 1595 const int width = fBounds.width(); 1596 1597 int y = fBounds.fTop; 1598 while (!iter.done()) { 1599 do { 1600 expand_row_to_mask(dst, iter.data(), width); 1601 dst += mask->fRowBytes; 1602 } while (++y < iter.bottom()); 1603 iter.next(); 1604 } 1605} 1606 1607/////////////////////////////////////////////////////////////////////////////// 1608/////////////////////////////////////////////////////////////////////////////// 1609 1610static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width, 1611 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) { 1612 // we don't read our initial n from data, since the caller may have had to 1613 // clip it, hence the initialCount parameter. 1614 int n = initialCount; 1615 for (;;) { 1616 if (n > width) { 1617 n = width; 1618 } 1619 SkASSERT(n > 0); 1620 runs[0] = n; 1621 runs += n; 1622 1623 aa[0] = data[1]; 1624 aa += n; 1625 1626 data += 2; 1627 width -= n; 1628 if (0 == width) { 1629 break; 1630 } 1631 // load the next count 1632 n = data[0]; 1633 } 1634 runs[0] = 0; // sentinel 1635} 1636 1637SkAAClipBlitter::~SkAAClipBlitter() { 1638 sk_free(fScanlineScratch); 1639} 1640 1641void SkAAClipBlitter::ensureRunsAndAA() { 1642 if (NULL == fScanlineScratch) { 1643 // add 1 so we can store the terminating run count of 0 1644 int count = fAAClipBounds.width() + 1; 1645 // we use this either for fRuns + fAA, or a scaline of a mask 1646 // which may be as deep as 32bits 1647 fScanlineScratch = sk_malloc_throw(count * sizeof(SkPMColor)); 1648 fRuns = (int16_t*)fScanlineScratch; 1649 fAA = (SkAlpha*)(fRuns + count); 1650 } 1651} 1652 1653void SkAAClipBlitter::blitH(int x, int y, int width) { 1654 SkASSERT(width > 0); 1655 SkASSERT(fAAClipBounds.contains(x, y)); 1656 SkASSERT(fAAClipBounds.contains(x + width - 1, y)); 1657 1658 int lastY; 1659 const uint8_t* row = fAAClip->findRow(y, &lastY); 1660 int initialCount; 1661 row = fAAClip->findX(row, x, &initialCount); 1662 1663 if (initialCount >= width) { 1664 SkAlpha alpha = row[1]; 1665 if (0 == alpha) { 1666 return; 1667 } 1668 if (0xFF == alpha) { 1669 fBlitter->blitH(x, y, width); 1670 return; 1671 } 1672 } 1673 1674 this->ensureRunsAndAA(); 1675 expandToRuns(row, initialCount, width, fRuns, fAA); 1676 1677 fBlitter->blitAntiH(x, y, fAA, fRuns); 1678} 1679 1680static void merge(const uint8_t* SK_RESTRICT row, int rowN, 1681 const SkAlpha* SK_RESTRICT srcAA, 1682 const int16_t* SK_RESTRICT srcRuns, 1683 SkAlpha* SK_RESTRICT dstAA, 1684 int16_t* SK_RESTRICT dstRuns, 1685 int width) { 1686 SkDEBUGCODE(int accumulated = 0;) 1687 int srcN = srcRuns[0]; 1688 // do we need this check? 1689 if (0 == srcN) { 1690 return; 1691 } 1692 1693 for (;;) { 1694 SkASSERT(rowN > 0); 1695 SkASSERT(srcN > 0); 1696 1697 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]); 1698 int minN = SkMin32(srcN, rowN); 1699 dstRuns[0] = minN; 1700 dstRuns += minN; 1701 dstAA[0] = newAlpha; 1702 dstAA += minN; 1703 1704 if (0 == (srcN -= minN)) { 1705 srcN = srcRuns[0]; // refresh 1706 srcRuns += srcN; 1707 srcAA += srcN; 1708 srcN = srcRuns[0]; // reload 1709 if (0 == srcN) { 1710 break; 1711 } 1712 } 1713 if (0 == (rowN -= minN)) { 1714 row += 2; 1715 rowN = row[0]; // reload 1716 } 1717 1718 SkDEBUGCODE(accumulated += minN;) 1719 SkASSERT(accumulated <= width); 1720 } 1721 dstRuns[0] = 0; 1722} 1723 1724void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[], 1725 const int16_t runs[]) { 1726 int lastY; 1727 const uint8_t* row = fAAClip->findRow(y, &lastY); 1728 int initialCount; 1729 row = fAAClip->findX(row, x, &initialCount); 1730 1731 this->ensureRunsAndAA(); 1732 1733 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width()); 1734 fBlitter->blitAntiH(x, y, fAA, fRuns); 1735} 1736 1737void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) { 1738 if (fAAClip->quickContains(x, y, x + 1, y + height)) { 1739 fBlitter->blitV(x, y, height, alpha); 1740 return; 1741 } 1742 1743 for (;;) { 1744 int lastY; 1745 const uint8_t* row = fAAClip->findRow(y, &lastY); 1746 int dy = lastY - y + 1; 1747 if (dy > height) { 1748 dy = height; 1749 } 1750 height -= dy; 1751 1752 int initialCount; 1753 row = fAAClip->findX(row, x, &initialCount); 1754 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]); 1755 if (newAlpha) { 1756 fBlitter->blitV(x, y, dy, newAlpha); 1757 } 1758 SkASSERT(height >= 0); 1759 if (height <= 0) { 1760 break; 1761 } 1762 y = lastY + 1; 1763 } 1764} 1765 1766void SkAAClipBlitter::blitRect(int x, int y, int width, int height) { 1767 if (fAAClip->quickContains(x, y, x + width, y + height)) { 1768 fBlitter->blitRect(x, y, width, height); 1769 return; 1770 } 1771 1772 while (--height >= 0) { 1773 this->blitH(x, y, width); 1774 y += 1; 1775 } 1776} 1777 1778typedef void (*MergeAAProc)(const void* src, int width, const uint8_t* row, 1779 int initialRowCount, void* dst); 1780 1781static void small_memcpy(void* dst, const void* src, size_t n) { 1782 memcpy(dst, src, n); 1783} 1784 1785static void small_bzero(void* dst, size_t n) { 1786 sk_bzero(dst, n); 1787} 1788 1789static inline uint8_t mergeOne(uint8_t value, unsigned alpha) { 1790 return SkMulDiv255Round(value, alpha); 1791} 1792static inline uint16_t mergeOne(uint16_t value, unsigned alpha) { 1793 unsigned r = SkGetPackedR16(value); 1794 unsigned g = SkGetPackedG16(value); 1795 unsigned b = SkGetPackedB16(value); 1796 return SkPackRGB16(SkMulDiv255Round(r, alpha), 1797 SkMulDiv255Round(r, alpha), 1798 SkMulDiv255Round(r, alpha)); 1799} 1800static inline SkPMColor mergeOne(SkPMColor value, unsigned alpha) { 1801 unsigned a = SkGetPackedA32(value); 1802 unsigned r = SkGetPackedR32(value); 1803 unsigned g = SkGetPackedG32(value); 1804 unsigned b = SkGetPackedB32(value); 1805 return SkPackARGB32(SkMulDiv255Round(a, alpha), 1806 SkMulDiv255Round(r, alpha), 1807 SkMulDiv255Round(g, alpha), 1808 SkMulDiv255Round(b, alpha)); 1809} 1810 1811template <typename T> void mergeT(const T* SK_RESTRICT src, int srcN, 1812 const uint8_t* SK_RESTRICT row, int rowN, 1813 T* SK_RESTRICT dst) { 1814 SkDEBUGCODE(int accumulated = 0;) 1815 for (;;) { 1816 SkASSERT(rowN > 0); 1817 SkASSERT(srcN > 0); 1818 1819 int n = SkMin32(rowN, srcN); 1820 unsigned rowA = row[1]; 1821 if (0xFF == rowA) { 1822 small_memcpy(dst, src, n * sizeof(T)); 1823 } else if (0 == rowA) { 1824 small_bzero(dst, n * sizeof(T)); 1825 } else { 1826 for (int i = 0; i < n; ++i) { 1827 dst[i] = mergeOne(src[i], rowA); 1828 } 1829 } 1830 1831 if (0 == (srcN -= n)) { 1832 break; 1833 } 1834 1835 src += n; 1836 dst += n; 1837 1838 SkASSERT(rowN == n); 1839 row += 2; 1840 rowN = row[0]; 1841 } 1842} 1843 1844static MergeAAProc find_merge_aa_proc(SkMask::Format format) { 1845 switch (format) { 1846 case SkMask::kBW_Format: 1847 SkASSERT(!"unsupported"); 1848 return NULL; 1849 case SkMask::kA8_Format: 1850 case SkMask::k3D_Format: { 1851 void (*proc8)(const uint8_t*, int, const uint8_t*, int, uint8_t*) = mergeT; 1852 return (MergeAAProc)proc8; 1853 } 1854 case SkMask::kLCD16_Format: { 1855 void (*proc16)(const uint16_t*, int, const uint8_t*, int, uint16_t*) = mergeT; 1856 return (MergeAAProc)proc16; 1857 } 1858 case SkMask::kLCD32_Format: { 1859 void (*proc32)(const SkPMColor*, int, const uint8_t*, int, SkPMColor*) = mergeT; 1860 return (MergeAAProc)proc32; 1861 } 1862 default: 1863 SkASSERT(!"unsupported"); 1864 return NULL; 1865 } 1866} 1867 1868static U8CPU bit2byte(int bitInAByte) { 1869 SkASSERT(bitInAByte <= 0xFF); 1870 // negation turns any non-zero into 0xFFFFFF??, so we just shift down 1871 // some value >= 8 to get a full FF value 1872 return -bitInAByte >> 8; 1873} 1874 1875static void upscaleBW2A8(SkMask* dstMask, const SkMask& srcMask) { 1876 SkASSERT(SkMask::kBW_Format == srcMask.fFormat); 1877 SkASSERT(SkMask::kA8_Format == dstMask->fFormat); 1878 1879 const int width = srcMask.fBounds.width(); 1880 const int height = srcMask.fBounds.height(); 1881 1882 const uint8_t* SK_RESTRICT src = (const uint8_t*)srcMask.fImage; 1883 const size_t srcRB = srcMask.fRowBytes; 1884 uint8_t* SK_RESTRICT dst = (uint8_t*)dstMask->fImage; 1885 const size_t dstRB = dstMask->fRowBytes; 1886 1887 const int wholeBytes = width >> 3; 1888 const int leftOverBits = width & 7; 1889 1890 for (int y = 0; y < height; ++y) { 1891 uint8_t* SK_RESTRICT d = dst; 1892 for (int i = 0; i < wholeBytes; ++i) { 1893 int srcByte = src[i]; 1894 d[0] = bit2byte(srcByte & (1 << 7)); 1895 d[1] = bit2byte(srcByte & (1 << 6)); 1896 d[2] = bit2byte(srcByte & (1 << 5)); 1897 d[3] = bit2byte(srcByte & (1 << 4)); 1898 d[4] = bit2byte(srcByte & (1 << 3)); 1899 d[5] = bit2byte(srcByte & (1 << 2)); 1900 d[6] = bit2byte(srcByte & (1 << 1)); 1901 d[7] = bit2byte(srcByte & (1 << 0)); 1902 d += 8; 1903 } 1904 if (leftOverBits) { 1905 int srcByte = src[wholeBytes]; 1906 for (int x = 0; x < leftOverBits; ++x) { 1907 *d++ = bit2byte(srcByte & 0x80); 1908 srcByte <<= 1; 1909 } 1910 } 1911 src += srcRB; 1912 dst += dstRB; 1913 } 1914} 1915 1916void SkAAClipBlitter::blitMask(const SkMask& origMask, const SkIRect& clip) { 1917 SkASSERT(fAAClip->getBounds().contains(clip)); 1918 1919 if (fAAClip->quickContains(clip)) { 1920 fBlitter->blitMask(origMask, clip); 1921 return; 1922 } 1923 1924 const SkMask* mask = &origMask; 1925 1926 // if we're BW, we need to upscale to A8 (ugh) 1927 SkMask grayMask; 1928 grayMask.fImage = NULL; 1929 if (SkMask::kBW_Format == origMask.fFormat) { 1930 grayMask.fFormat = SkMask::kA8_Format; 1931 grayMask.fBounds = origMask.fBounds; 1932 grayMask.fRowBytes = origMask.fBounds.width(); 1933 size_t size = grayMask.computeImageSize(); 1934 grayMask.fImage = (uint8_t*)fGrayMaskScratch.reset(size, 1935 SkAutoMalloc::kReuse_OnShrink); 1936 1937 upscaleBW2A8(&grayMask, origMask); 1938 mask = &grayMask; 1939 } 1940 1941 this->ensureRunsAndAA(); 1942 1943 // HACK -- we are devolving 3D into A8, need to copy the rest of the 3D 1944 // data into a temp block to support it better (ugh) 1945 1946 const void* src = mask->getAddr(clip.fLeft, clip.fTop); 1947 const size_t srcRB = mask->fRowBytes; 1948 const int width = clip.width(); 1949 MergeAAProc mergeProc = find_merge_aa_proc(mask->fFormat); 1950 1951 SkMask rowMask; 1952 rowMask.fFormat = SkMask::k3D_Format == mask->fFormat ? SkMask::kA8_Format : mask->fFormat; 1953 rowMask.fBounds.fLeft = clip.fLeft; 1954 rowMask.fBounds.fRight = clip.fRight; 1955 rowMask.fRowBytes = mask->fRowBytes; // doesn't matter, since our height==1 1956 rowMask.fImage = (uint8_t*)fScanlineScratch; 1957 1958 int y = clip.fTop; 1959 const int stopY = y + clip.height(); 1960 1961 do { 1962 int localStopY; 1963 const uint8_t* row = fAAClip->findRow(y, &localStopY); 1964 // findRow returns last Y, not stop, so we add 1 1965 localStopY = SkMin32(localStopY + 1, stopY); 1966 1967 int initialCount; 1968 row = fAAClip->findX(row, clip.fLeft, &initialCount); 1969 do { 1970 mergeProc(src, width, row, initialCount, rowMask.fImage); 1971 rowMask.fBounds.fTop = y; 1972 rowMask.fBounds.fBottom = y + 1; 1973 fBlitter->blitMask(rowMask, rowMask.fBounds); 1974 src = (const void*)((const char*)src + srcRB); 1975 } while (++y < localStopY); 1976 } while (y < stopY); 1977} 1978 1979const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) { 1980 return NULL; 1981} 1982 1983