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