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