1/*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkRegionPriv.h"
9#include "SkBlitter.h"
10#include "SkScan.h"
11#include "SkTDArray.h"
12#include "SkPath.h"
13
14// The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
15// we may not want to promote this to a "std" routine just yet.
16static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
17    for (int i = 0; i < count; ++i) {
18        if (a[i] != b[i]) {
19            return false;
20        }
21    }
22    return true;
23}
24
25class SkRgnBuilder : public SkBlitter {
26public:
27    SkRgnBuilder();
28    virtual ~SkRgnBuilder();
29
30    // returns true if it could allocate the working storage needed
31    bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
32
33    void done() {
34        if (fCurrScanline != NULL) {
35            fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
36            if (!this->collapsWithPrev()) { // flush the last line
37                fCurrScanline = fCurrScanline->nextScanline();
38            }
39        }
40    }
41
42    int     computeRunCount() const;
43    void    copyToRect(SkIRect*) const;
44    void    copyToRgn(SkRegion::RunType runs[]) const;
45
46    virtual void blitH(int x, int y, int width);
47
48#ifdef SK_DEBUG
49    void dump() const {
50        SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
51        const Scanline* line = (Scanline*)fStorage;
52        while (line < fCurrScanline) {
53            SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
54            for (int i = 0; i < line->fXCount; i++) {
55                SkDebugf(" %d", line->firstX()[i]);
56            }
57            SkDebugf("\n");
58
59            line = line->nextScanline();
60        }
61    }
62#endif
63private:
64    /*
65     *  Scanline mimics a row in the region, nearly. A row in a region is:
66     *      [Bottom IntervalCount [L R]... Sentinel]
67     *  while a Scanline is
68     *      [LastY XCount [L R]... uninitialized]
69     *  The two are the same length (which is good), but we have to transmute
70     *  the scanline a little when we convert it to a region-row.
71     *
72     *  Potentially we could recode this to exactly match the row format, in
73     *  which case copyToRgn() could be a single memcpy. Not sure that is worth
74     *  the effort.
75     */
76    struct Scanline {
77        SkRegion::RunType fLastY;
78        SkRegion::RunType fXCount;
79
80        SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
81        Scanline* nextScanline() const {
82            // add final +1 for the x-sentinel
83            return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
84        }
85    };
86    SkRegion::RunType*  fStorage;
87    Scanline*           fCurrScanline;
88    Scanline*           fPrevScanline;
89    //  points at next avialable x[] in fCurrScanline
90    SkRegion::RunType*  fCurrXPtr;
91    SkRegion::RunType   fTop;           // first Y value
92
93    int fStorageCount;
94
95    bool collapsWithPrev() {
96        if (fPrevScanline != NULL &&
97            fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
98            fPrevScanline->fXCount == fCurrScanline->fXCount &&
99            sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
100        {
101            // update the height of fPrevScanline
102            fPrevScanline->fLastY = fCurrScanline->fLastY;
103            return true;
104        }
105        return false;
106    }
107};
108
109SkRgnBuilder::SkRgnBuilder()
110    : fStorage(NULL) {
111}
112
113SkRgnBuilder::~SkRgnBuilder() {
114    sk_free(fStorage);
115}
116
117bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
118    if ((maxHeight | maxTransitions) < 0) {
119        return false;
120    }
121
122    if (pathIsInverse) {
123        // allow for additional X transitions to "invert" each scanline
124        // [ L' ... normal transitions ... R' ]
125        //
126        maxTransitions += 2;
127    }
128
129    // compute the count with +1 and +3 slop for the working buffer
130    int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);
131
132    if (pathIsInverse) {
133        // allow for two "empty" rows for the top and bottom
134        //      [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
135        count += 10;
136    }
137
138    if (count < 0 || !sk_64_isS32(count)) {
139        return false;
140    }
141    fStorageCount = sk_64_asS32(count);
142
143    int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
144    if (size < 0 || !sk_64_isS32(size)) {
145        return false;
146    }
147
148    fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
149    if (NULL == fStorage) {
150        return false;
151    }
152
153    fCurrScanline = NULL;    // signal empty collection
154    fPrevScanline = NULL;    // signal first scanline
155    return true;
156}
157
158void SkRgnBuilder::blitH(int x, int y, int width) {
159    if (fCurrScanline == NULL) {  // first time
160        fTop = (SkRegion::RunType)(y);
161        fCurrScanline = (Scanline*)fStorage;
162        fCurrScanline->fLastY = (SkRegion::RunType)(y);
163        fCurrXPtr = fCurrScanline->firstX();
164    } else {
165        SkASSERT(y >= fCurrScanline->fLastY);
166
167        if (y > fCurrScanline->fLastY) {
168            // if we get here, we're done with fCurrScanline
169            fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
170
171            int prevLastY = fCurrScanline->fLastY;
172            if (!this->collapsWithPrev()) {
173                fPrevScanline = fCurrScanline;
174                fCurrScanline = fCurrScanline->nextScanline();
175
176            }
177            if (y - 1 > prevLastY) {  // insert empty run
178                fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
179                fCurrScanline->fXCount = 0;
180                fCurrScanline = fCurrScanline->nextScanline();
181            }
182            // setup for the new curr line
183            fCurrScanline->fLastY = (SkRegion::RunType)(y);
184            fCurrXPtr = fCurrScanline->firstX();
185        }
186    }
187    //  check if we should extend the current run, or add a new one
188    if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
189        fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
190    } else {
191        fCurrXPtr[0] = (SkRegion::RunType)(x);
192        fCurrXPtr[1] = (SkRegion::RunType)(x + width);
193        fCurrXPtr += 2;
194    }
195    SkASSERT(fCurrXPtr - fStorage < fStorageCount);
196}
197
198int SkRgnBuilder::computeRunCount() const {
199    if (fCurrScanline == NULL) {
200        return 0;
201    }
202
203    const SkRegion::RunType*  line = fStorage;
204    const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;
205
206    return 2 + (int)(stop - line);
207}
208
209void SkRgnBuilder::copyToRect(SkIRect* r) const {
210    SkASSERT(fCurrScanline != NULL);
211    // A rect's scanline is [bottom intervals left right sentinel] == 5
212    SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
213
214    const Scanline* line = (const Scanline*)fStorage;
215    SkASSERT(line->fXCount == 2);
216
217    r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
218}
219
220void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
221    SkASSERT(fCurrScanline != NULL);
222    SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
223
224    const Scanline* line = (const Scanline*)fStorage;
225    const Scanline* stop = fCurrScanline;
226
227    *runs++ = fTop;
228    do {
229        *runs++ = (SkRegion::RunType)(line->fLastY + 1);
230        int count = line->fXCount;
231        *runs++ = count >> 1;   // intervalCount
232        if (count) {
233            memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
234            runs += count;
235        }
236        *runs++ = SkRegion::kRunTypeSentinel;
237        line = line->nextScanline();
238    } while (line < stop);
239    SkASSERT(line == stop);
240    *runs = SkRegion::kRunTypeSentinel;
241}
242
243static unsigned verb_to_initial_last_index(unsigned verb) {
244    static const uint8_t gPathVerbToInitialLastIndex[] = {
245        0,  //  kMove_Verb
246        1,  //  kLine_Verb
247        2,  //  kQuad_Verb
248        2,  //  kConic_Verb
249        3,  //  kCubic_Verb
250        0,  //  kClose_Verb
251        0   //  kDone_Verb
252    };
253    SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
254    return gPathVerbToInitialLastIndex[verb];
255}
256
257static unsigned verb_to_max_edges(unsigned verb) {
258    static const uint8_t gPathVerbToMaxEdges[] = {
259        0,  //  kMove_Verb
260        1,  //  kLine_Verb
261        2,  //  kQuad_VerbB
262        2,  //  kConic_VerbB
263        3,  //  kCubic_Verb
264        0,  //  kClose_Verb
265        0   //  kDone_Verb
266    };
267    SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
268    return gPathVerbToMaxEdges[verb];
269}
270
271
272static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
273    SkPath::Iter    iter(path, true);
274    SkPoint         pts[4];
275    SkPath::Verb    verb;
276
277    int maxEdges = 0;
278    SkScalar    top = SkIntToScalar(SK_MaxS16);
279    SkScalar    bot = SkIntToScalar(SK_MinS16);
280
281    while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
282        maxEdges += verb_to_max_edges(verb);
283
284        int lastIndex = verb_to_initial_last_index(verb);
285        if (lastIndex > 0) {
286            for (int i = 1; i <= lastIndex; i++) {
287                if (top > pts[i].fY) {
288                    top = pts[i].fY;
289                } else if (bot < pts[i].fY) {
290                    bot = pts[i].fY;
291                }
292            }
293        } else if (SkPath::kMove_Verb == verb) {
294            if (top > pts[0].fY) {
295                top = pts[0].fY;
296            } else if (bot < pts[0].fY) {
297                bot = pts[0].fY;
298            }
299        }
300    }
301    SkASSERT(top <= bot);
302
303    *itop = SkScalarRoundToInt(top);
304    *ibot = SkScalarRoundToInt(bot);
305    return maxEdges;
306}
307
308bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
309    SkDEBUGCODE(this->validate();)
310
311    if (clip.isEmpty()) {
312        return this->setEmpty();
313    }
314
315    if (path.isEmpty()) {
316        if (path.isInverseFillType()) {
317            return this->set(clip);
318        } else {
319            return this->setEmpty();
320        }
321    }
322
323    //  compute worst-case rgn-size for the path
324    int pathTop, pathBot;
325    int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
326    int clipTop, clipBot;
327    int clipTransitions;
328
329    clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
330
331    int top = SkMax32(pathTop, clipTop);
332    int bot = SkMin32(pathBot, clipBot);
333
334    if (top >= bot)
335        return this->setEmpty();
336
337    SkRgnBuilder builder;
338
339    if (!builder.init(bot - top,
340                      SkMax32(pathTransitions, clipTransitions),
341                      path.isInverseFillType())) {
342        // can't allocate working space, so return false
343        return this->setEmpty();
344    }
345
346    SkScan::FillPath(path, clip, &builder);
347    builder.done();
348
349    int count = builder.computeRunCount();
350    if (count == 0) {
351        return this->setEmpty();
352    } else if (count == kRectRegionRuns) {
353        builder.copyToRect(&fBounds);
354        this->setRect(fBounds);
355    } else {
356        SkRegion tmp;
357
358        tmp.fRunHead = RunHead::Alloc(count);
359        builder.copyToRgn(tmp.fRunHead->writable_runs());
360        tmp.fRunHead->computeRunBounds(&tmp.fBounds);
361        this->swap(tmp);
362    }
363    SkDEBUGCODE(this->validate();)
364    return true;
365}
366
367/////////////////////////////////////////////////////////////////////////////////////////////////
368/////////////////////////////////////////////////////////////////////////////////////////////////
369
370struct Edge {
371    enum {
372        kY0Link = 0x01,
373        kY1Link = 0x02,
374
375        kCompleteLink = (kY0Link | kY1Link)
376    };
377
378    SkRegion::RunType fX;
379    SkRegion::RunType fY0, fY1;
380    uint8_t fFlags;
381    Edge*   fNext;
382
383    void set(int x, int y0, int y1) {
384        SkASSERT(y0 != y1);
385
386        fX = (SkRegion::RunType)(x);
387        fY0 = (SkRegion::RunType)(y0);
388        fY1 = (SkRegion::RunType)(y1);
389        fFlags = 0;
390        SkDEBUGCODE(fNext = NULL;)
391    }
392
393    int top() const {
394        return SkFastMin32(fY0, fY1);
395    }
396};
397
398static void find_link(Edge* base, Edge* stop) {
399    SkASSERT(base < stop);
400
401    if (base->fFlags == Edge::kCompleteLink) {
402        SkASSERT(base->fNext);
403        return;
404    }
405
406    SkASSERT(base + 1 < stop);
407
408    int y0 = base->fY0;
409    int y1 = base->fY1;
410
411    Edge* e = base;
412    if ((base->fFlags & Edge::kY0Link) == 0) {
413        for (;;) {
414            e += 1;
415            if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
416                SkASSERT(NULL == e->fNext);
417                e->fNext = base;
418                e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
419                break;
420            }
421        }
422    }
423
424    e = base;
425    if ((base->fFlags & Edge::kY1Link) == 0) {
426        for (;;) {
427            e += 1;
428            if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
429                SkASSERT(NULL == base->fNext);
430                base->fNext = e;
431                e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
432                break;
433            }
434        }
435    }
436
437    base->fFlags = Edge::kCompleteLink;
438}
439
440static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
441    while (0 == edge->fFlags) {
442        edge++; // skip over "used" edges
443    }
444
445    SkASSERT(edge < stop);
446
447    Edge* base = edge;
448    Edge* prev = edge;
449    edge = edge->fNext;
450    SkASSERT(edge != base);
451
452    int count = 1;
453    path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
454    prev->fFlags = 0;
455    do {
456        if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
457            path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
458            path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
459        }
460        prev = edge;
461        edge = edge->fNext;
462        count += 1;
463        prev->fFlags = 0;
464    } while (edge != base);
465    path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
466    path->close();
467    return count;
468}
469
470#include "SkTSearch.h"
471
472static int EdgeProc(const Edge* a, const Edge* b) {
473    return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
474}
475
476bool SkRegion::getBoundaryPath(SkPath* path) const {
477    // path could safely be NULL if we're empty, but the caller shouldn't
478    // *know* that
479    SkASSERT(path);
480
481    if (this->isEmpty()) {
482        return false;
483    }
484
485    const SkIRect& bounds = this->getBounds();
486
487    if (this->isRect()) {
488        SkRect  r;
489        r.set(bounds);      // this converts the ints to scalars
490        path->addRect(r);
491        return true;
492    }
493
494    SkRegion::Iterator  iter(*this);
495    SkTDArray<Edge>     edges;
496
497    for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
498        Edge* edge = edges.append(2);
499        edge[0].set(r.fLeft, r.fBottom, r.fTop);
500        edge[1].set(r.fRight, r.fTop, r.fBottom);
501    }
502    qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));
503
504    int count = edges.count();
505    Edge* start = edges.begin();
506    Edge* stop = start + count;
507    Edge* e;
508
509    for (e = start; e != stop; e++) {
510        find_link(e, stop);
511    }
512
513#ifdef SK_DEBUG
514    for (e = start; e != stop; e++) {
515        SkASSERT(e->fNext != NULL);
516        SkASSERT(e->fFlags == Edge::kCompleteLink);
517    }
518#endif
519
520    path->incReserve(count << 1);
521    do {
522        SkASSERT(count > 1);
523        count -= extract_path(start, stop, path);
524    } while (count > 0);
525
526    return true;
527}
528