src/core/SkAAClip.cpp

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