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