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