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