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
39#ifdef SK_DEBUG
40static inline bool x_in_rect(int x, const SkIRect& rect) {
41    return (unsigned)(x - rect.fLeft) < (unsigned)rect.width();
42}
43#endif
44
45static 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
53struct SkAAClip::YOffset {
54    int32_t  fY;
55    uint32_t fOffset;
56};
57
58struct 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
116class SkAAClip::Iter {
117public:
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
126private:
127    const YOffset* fCurrYOff;
128    const YOffset* fStopYOff;
129    const uint8_t* fData;
130
131    int fTop, fBottom;
132    bool fDone;
133};
134
135SkAAClip::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
156void 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
177static 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
190void 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
223static 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
246void 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.
268static 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
306static 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
339static 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
385static 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
396static 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
436bool 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
499static 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
514bool 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//
597bool 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
617void 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
626SkAAClip::SkAAClip() {
627    fBounds.setEmpty();
628    fRunHead = NULL;
629}
630
631SkAAClip::SkAAClip(const SkAAClip& src) {
632    SkDEBUGCODE(fBounds.setEmpty();)    // need this for validate
633    fRunHead = NULL;
634    *this = src;
635}
636
637SkAAClip::~SkAAClip() {
638    this->freeRuns();
639}
640
641SkAAClip& 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
656bool 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
685void 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
693bool SkAAClip::set(const SkAAClip& src) {
694    *this = src;
695    return !this->isEmpty();
696}
697
698bool SkAAClip::setEmpty() {
699    this->freeRuns();
700    fBounds.setEmpty();
701    fRunHead = NULL;
702    return false;
703}
704
705bool 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
727bool 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
755bool 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
769static 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
783bool 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
868const 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
888const 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
907bool 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
946class 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
959public:
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
1174private:
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
1233class 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
1253public:
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) 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) 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) 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) override
1298        { unexpected(); }
1299
1300    const SkBitmap* justAnOpaqueColor(uint32_t*) override {
1301        return NULL;
1302    }
1303
1304    void blitH(int x, int y, int width) 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[]) 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
1349private:
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
1373bool 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
1412typedef void (*RowProc)(SkAAClip::Builder&, int bottom,
1413                        const uint8_t* rowA, const SkIRect& rectA,
1414                        const uint8_t* rowB, const SkIRect& rectB);
1415
1416typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB);
1417
1418static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1419    // Multiply
1420    return SkMulDiv255Round(alphaA, alphaB);
1421}
1422
1423static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1424    // SrcOver
1425    return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB);
1426}
1427
1428static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1429    // SrcOut
1430    return SkMulDiv255Round(alphaA, 0xFF - alphaB);
1431}
1432
1433static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1434    // XOR
1435    return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB);
1436}
1437
1438static 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
1454class RowIter {
1455public:
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
1492private:
1493    const uint8_t*  fRow;
1494    int             fLeft;
1495    int             fRight;
1496    int             fBoundsRight;
1497    bool            fDone;
1498    uint8_t         fAlpha;
1499};
1500
1501static 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
1510static 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
1526static 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
1586static 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
1595static 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
1662bool 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
1732bool 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
1768bool 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
1799bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) {
1800    return this->op(*this, clip, op);
1801}
1802
1803///////////////////////////////////////////////////////////////////////////////
1804
1805bool 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
1824static 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
1838void 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
1869static 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
1896SkAAClipBlitter::~SkAAClipBlitter() {
1897    sk_free(fScanlineScratch);
1898}
1899
1900void 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
1912void 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
1938static 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
1982void 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
1995void 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
2023void 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
2035typedef void (*MergeAAProc)(const void* src, int width, const uint8_t* row,
2036                            int initialRowCount, void* dst);
2037
2038static void small_memcpy(void* dst, const void* src, size_t n) {
2039    memcpy(dst, src, n);
2040}
2041
2042static void small_bzero(void* dst, size_t n) {
2043    sk_bzero(dst, n);
2044}
2045
2046static inline uint8_t mergeOne(uint8_t value, unsigned alpha) {
2047    return SkMulDiv255Round(value, alpha);
2048}
2049
2050static 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
2059template <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
2091static 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
2111static 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
2118static 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
2159void 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
2222const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) {
2223    return NULL;
2224}
2225