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 "include/core/SkColor.h"
9 #include "include/core/SkMatrix.h"
10 #include "include/core/SkPath.h"
11 #include "include/core/SkRect.h"
12 #include "include/core/SkRegion.h"
13 #include "include/core/SkScalar.h"
14 #include "include/core/SkTypes.h"
15 #include "include/private/base/SkDebug.h"
16 #include "include/private/base/SkMalloc.h"
17 #include "include/private/base/SkMath.h"
18 #include "include/private/base/SkPoint_impl.h"
19 #include "include/private/base/SkTDArray.h"
20 #include "include/private/base/SkTFitsIn.h"
21 #include "include/private/base/SkTo.h"
22 #include "src/base/SkSafeMath.h"
23 #include "src/base/SkTSort.h"
24 #include "src/core/SkBlitter.h"
25 #include "src/core/SkRegionPriv.h"
26 #include "src/core/SkScan.h"
27
28 #include <algorithm>
29 #include <cstdint>
30 #include <cstring>
31 #include <iterator>
32
33 // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
34 // 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)35 static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
36 for (int i = 0; i < count; ++i) {
37 if (a[i] != b[i]) {
38 return false;
39 }
40 }
41 return true;
42 }
43
44 class SkRgnBuilder : public SkBlitter {
45 public:
46 SkRgnBuilder();
47 ~SkRgnBuilder() override;
48
49 // returns true if it could allocate the working storage needed
50 bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
51
done()52 void done() {
53 if (fCurrScanline != nullptr) {
54 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
55 if (!this->collapsWithPrev()) { // flush the last line
56 fCurrScanline = fCurrScanline->nextScanline();
57 }
58 }
59 }
60
61 int computeRunCount() const;
62 void copyToRect(SkIRect*) const;
63 void copyToRgn(SkRegion::RunType runs[]) const;
64
65 void blitH(int x, int y, int width) override;
blitAntiH(int x,int y,const SkAlpha antialias[],const int16_t runs[])66 void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
67 SkDEBUGFAIL("blitAntiH not implemented");
68 }
69
70 #ifdef SK_DEBUG
dump() const71 void dump() const {
72 SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
73 Scanline* line = (Scanline*)fStorage;
74 while (line < fCurrScanline) {
75 SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
76 for (int i = 0; i < line->fXCount; i++) {
77 SkDebugf(" %d", line->firstX()[i]);
78 }
79 SkDebugf("\n");
80
81 line = line->nextScanline();
82 }
83 }
84 #endif
85 private:
86 /*
87 * Scanline mimics a row in the region, nearly. A row in a region is:
88 * [Bottom IntervalCount [L R]... Sentinel]
89 * while a Scanline is
90 * [LastY XCount [L R]... uninitialized]
91 * The two are the same length (which is good), but we have to transmute
92 * the scanline a little when we convert it to a region-row.
93 *
94 * Potentially we could recode this to exactly match the row format, in
95 * which case copyToRgn() could be a single memcpy. Not sure that is worth
96 * the effort.
97 */
98 struct Scanline {
99 SkRegion::RunType fLastY;
100 SkRegion::RunType fXCount;
101
firstXSkRgnBuilder::Scanline102 SkRegion::RunType* firstX() { return (SkRegion::RunType*)(this + 1); }
nextScanlineSkRgnBuilder::Scanline103 Scanline* nextScanline() {
104 // add final +1 for the x-sentinel
105 return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
106 }
107 };
108 SkRegion::RunType* fStorage;
109 Scanline* fCurrScanline;
110 Scanline* fPrevScanline;
111 // points at next avialable x[] in fCurrScanline
112 SkRegion::RunType* fCurrXPtr;
113 SkRegion::RunType fTop; // first Y value
114
115 int fStorageCount;
116
collapsWithPrev()117 bool collapsWithPrev() {
118 if (fPrevScanline != nullptr &&
119 fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
120 fPrevScanline->fXCount == fCurrScanline->fXCount &&
121 sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
122 {
123 // update the height of fPrevScanline
124 fPrevScanline->fLastY = fCurrScanline->fLastY;
125 return true;
126 }
127 return false;
128 }
129 };
130
SkRgnBuilder()131 SkRgnBuilder::SkRgnBuilder()
132 : fStorage(nullptr) {
133 }
134
~SkRgnBuilder()135 SkRgnBuilder::~SkRgnBuilder() {
136 sk_free(fStorage);
137 }
138
init(int maxHeight,int maxTransitions,bool pathIsInverse)139 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
140 if ((maxHeight | maxTransitions) < 0) {
141 return false;
142 }
143
144 SkSafeMath safe;
145
146 if (pathIsInverse) {
147 // allow for additional X transitions to "invert" each scanline
148 // [ L' ... normal transitions ... R' ]
149 //
150 maxTransitions = safe.addInt(maxTransitions, 2);
151 }
152
153 // compute the count with +1 and +3 slop for the working buffer
154 size_t count = safe.mul(safe.addInt(maxHeight, 1), safe.addInt(3, maxTransitions));
155
156 if (pathIsInverse) {
157 // allow for two "empty" rows for the top and bottom
158 // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
159 count = safe.add(count, 10);
160 }
161
162 if (!safe || !SkTFitsIn<int32_t>(count)) {
163 return false;
164 }
165 fStorageCount = SkToS32(count);
166
167 fStorage = (SkRegion::RunType*)sk_malloc_canfail(fStorageCount, sizeof(SkRegion::RunType));
168 if (nullptr == fStorage) {
169 return false;
170 }
171
172 fCurrScanline = nullptr; // signal empty collection
173 fPrevScanline = nullptr; // signal first scanline
174 return true;
175 }
176
blitH(int x,int y,int width)177 void SkRgnBuilder::blitH(int x, int y, int width) {
178 if (fCurrScanline == nullptr) { // first time
179 fTop = (SkRegion::RunType)(y);
180 fCurrScanline = (Scanline*)fStorage;
181 fCurrScanline->fLastY = (SkRegion::RunType)(y);
182 fCurrXPtr = fCurrScanline->firstX();
183 } else {
184 SkASSERT(y >= fCurrScanline->fLastY);
185
186 if (y > fCurrScanline->fLastY) {
187 // if we get here, we're done with fCurrScanline
188 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
189
190 int prevLastY = fCurrScanline->fLastY;
191 if (!this->collapsWithPrev()) {
192 fPrevScanline = fCurrScanline;
193 fCurrScanline = fCurrScanline->nextScanline();
194
195 }
196 if (y - 1 > prevLastY) { // insert empty run
197 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
198 fCurrScanline->fXCount = 0;
199 fCurrScanline = fCurrScanline->nextScanline();
200 }
201 // setup for the new curr line
202 fCurrScanline->fLastY = (SkRegion::RunType)(y);
203 fCurrXPtr = fCurrScanline->firstX();
204 }
205 }
206 // check if we should extend the current run, or add a new one
207 if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
208 fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
209 } else {
210 fCurrXPtr[0] = (SkRegion::RunType)(x);
211 fCurrXPtr[1] = (SkRegion::RunType)(x + width);
212 fCurrXPtr += 2;
213 }
214 SkASSERT(fCurrXPtr - fStorage < fStorageCount);
215 }
216
computeRunCount() const217 int SkRgnBuilder::computeRunCount() const {
218 if (fCurrScanline == nullptr) {
219 return 0;
220 }
221
222 const SkRegion::RunType* line = fStorage;
223 const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
224
225 return 2 + (int)(stop - line);
226 }
227
copyToRect(SkIRect * r) const228 void SkRgnBuilder::copyToRect(SkIRect* r) const {
229 SkASSERT(fCurrScanline != nullptr);
230 // A rect's scanline is [bottom intervals left right sentinel] == 5
231 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
232
233 Scanline* line = (Scanline*)fStorage;
234 SkASSERT(line->fXCount == 2);
235
236 r->setLTRB(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
237 }
238
copyToRgn(SkRegion::RunType runs[]) const239 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
240 SkASSERT(fCurrScanline != nullptr);
241 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
242
243 Scanline* line = (Scanline*)fStorage;
244 const Scanline* stop = fCurrScanline;
245
246 *runs++ = fTop;
247 do {
248 *runs++ = (SkRegion::RunType)(line->fLastY + 1);
249 int count = line->fXCount;
250 *runs++ = count >> 1; // intervalCount
251 if (count) {
252 memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
253 runs += count;
254 }
255 *runs++ = SkRegion_kRunTypeSentinel;
256 line = line->nextScanline();
257 } while (line < stop);
258 SkASSERT(line == stop);
259 *runs = SkRegion_kRunTypeSentinel;
260 }
261
verb_to_initial_last_index(unsigned verb)262 static unsigned verb_to_initial_last_index(unsigned verb) {
263 static const uint8_t gPathVerbToInitialLastIndex[] = {
264 0, // kMove_Verb
265 1, // kLine_Verb
266 2, // kQuad_Verb
267 2, // kConic_Verb
268 3, // kCubic_Verb
269 0, // kClose_Verb
270 0 // kDone_Verb
271 };
272 SkASSERT((unsigned)verb < std::size(gPathVerbToInitialLastIndex));
273 return gPathVerbToInitialLastIndex[verb];
274 }
275
verb_to_max_edges(unsigned verb)276 static unsigned verb_to_max_edges(unsigned verb) {
277 static const uint8_t gPathVerbToMaxEdges[] = {
278 0, // kMove_Verb
279 1, // kLine_Verb
280 2, // kQuad_VerbB
281 2, // kConic_VerbB
282 3, // kCubic_Verb
283 0, // kClose_Verb
284 0 // kDone_Verb
285 };
286 SkASSERT((unsigned)verb < std::size(gPathVerbToMaxEdges));
287 return gPathVerbToMaxEdges[verb];
288 }
289
290 // If returns 0, ignore itop and ibot
count_path_runtype_values(const SkPath & path,int * itop,int * ibot)291 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
292 SkPath::Iter iter(path, true);
293 SkPoint pts[4];
294 SkPath::Verb verb;
295
296 int maxEdges = 0;
297 SkScalar top = SkIntToScalar(SK_MaxS16);
298 SkScalar bot = SkIntToScalar(SK_MinS16);
299
300 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
301 maxEdges += verb_to_max_edges(verb);
302
303 int lastIndex = verb_to_initial_last_index(verb);
304 if (lastIndex > 0) {
305 for (int i = 1; i <= lastIndex; i++) {
306 if (top > pts[i].fY) {
307 top = pts[i].fY;
308 } else if (bot < pts[i].fY) {
309 bot = pts[i].fY;
310 }
311 }
312 } else if (SkPath::kMove_Verb == verb) {
313 if (top > pts[0].fY) {
314 top = pts[0].fY;
315 } else if (bot < pts[0].fY) {
316 bot = pts[0].fY;
317 }
318 }
319 }
320 if (0 == maxEdges) {
321 return 0; // we have only moves+closes
322 }
323
324 SkASSERT(top <= bot);
325 *itop = SkScalarRoundToInt(top);
326 *ibot = SkScalarRoundToInt(bot);
327 return maxEdges;
328 }
329
check_inverse_on_empty_return(SkRegion * dst,const SkPath & path,const SkRegion & clip)330 static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) {
331 if (path.isInverseFillType()) {
332 return dst->set(clip);
333 } else {
334 return dst->setEmpty();
335 }
336 }
337
setPath(const SkPath & path,const SkRegion & clip)338 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
339 SkDEBUGCODE(SkRegionPriv::Validate(*this));
340
341 if (clip.isEmpty() || !path.isFinite() || path.isEmpty()) {
342 // This treats non-finite paths as empty as well, so this returns empty or 'clip' if
343 // it's inverse-filled. If clip is also empty, path's fill type doesn't really matter
344 // and this region ends up empty.
345 return check_inverse_on_empty_return(this, path, clip);
346 }
347
348 // Our builder is very fragile, and can't be called with spans/rects out of Y->X order.
349 // To ensure this, we only "fill" clipped to a rect (the clip's bounds), and if the
350 // clip is more complex than that, we just post-intersect the result with the clip.
351 const SkIRect clipBounds = clip.getBounds();
352 if (clip.isComplex()) {
353 if (!this->setPath(path, SkRegion(clipBounds))) {
354 return false;
355 }
356 return this->op(clip, kIntersect_Op);
357 }
358
359 // SkScan::FillPath has limits on the coordinate range of the clipping SkRegion. If it's too
360 // big, tile the clip bounds and union the pieces back together.
361 if (SkScan::PathRequiresTiling(clipBounds)) {
362 static constexpr int kTileSize = 32767 >> 1; // Limit so coords can fit into SkFixed (16.16)
363 const SkIRect pathBounds = path.getBounds().roundOut();
364
365 this->setEmpty();
366
367 // Note: With large integers some intermediate calculations can overflow, but the
368 // end results will still be in integer range. Using int64_t for the intermediate
369 // values will handle this situation.
370 for (int64_t top = clipBounds.fTop; top < clipBounds.fBottom; top += kTileSize) {
371 int64_t bot = std::min(top + kTileSize, (int64_t)clipBounds.fBottom);
372 for (int64_t left = clipBounds.fLeft; left < clipBounds.fRight; left += kTileSize) {
373 int64_t right = std::min(left + kTileSize, (int64_t)clipBounds.fRight);
374
375 SkIRect tileClipBounds = {(int)left, (int)top, (int)right, (int)bot};
376 if (!SkIRect::Intersects(pathBounds, tileClipBounds)) {
377 continue;
378 }
379
380 // Shift coordinates so the top left is (0,0) during scan conversion and then
381 // translate the SkRegion afterwards.
382 tileClipBounds.offset(-left, -top);
383 SkASSERT(!SkScan::PathRequiresTiling(tileClipBounds));
384 SkRegion tile;
385 tile.setPath(path.makeTransform(SkMatrix::Translate(-left, -top)),
386 SkRegion(tileClipBounds));
387 tile.translate(left, top);
388 this->op(tile, kUnion_Op);
389 }
390 }
391 // During tiling we only applied the bounds of the tile, now that we have a full SkRegion,
392 // apply the original clip.
393 return this->op(clip, kIntersect_Op);
394 }
395
396 // compute worst-case rgn-size for the path
397 int pathTop, pathBot;
398 int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
399 if (0 == pathTransitions) {
400 return check_inverse_on_empty_return(this, path, clip);
401 }
402
403 int clipTop, clipBot;
404 int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
405
406 int top = std::max(pathTop, clipTop);
407 int bot = std::min(pathBot, clipBot);
408 if (top >= bot) {
409 return check_inverse_on_empty_return(this, path, clip);
410 }
411
412 SkRgnBuilder builder;
413
414 if (!builder.init(bot - top,
415 std::max(pathTransitions, clipTransitions),
416 path.isInverseFillType())) {
417 // can't allocate working space, so return false
418 return this->setEmpty();
419 }
420
421 SkScan::FillPath(path, clip, &builder);
422 builder.done();
423
424 int count = builder.computeRunCount();
425 if (count == 0) {
426 return this->setEmpty();
427 } else if (count == kRectRegionRuns) {
428 builder.copyToRect(&fBounds);
429 this->setRect(fBounds);
430 } else {
431 SkRegion tmp;
432
433 tmp.fRunHead = RunHead::Alloc(count);
434 builder.copyToRgn(tmp.fRunHead->writable_runs());
435 tmp.fRunHead->computeRunBounds(&tmp.fBounds);
436 this->swap(tmp);
437 }
438 SkDEBUGCODE(SkRegionPriv::Validate(*this));
439 return true;
440 }
441
442 /////////////////////////////////////////////////////////////////////////////////////////////////
443 /////////////////////////////////////////////////////////////////////////////////////////////////
444
445 struct Edge {
446 enum {
447 kY0Link = 0x01,
448 kY1Link = 0x02,
449
450 kCompleteLink = (kY0Link | kY1Link)
451 };
452
453 SkRegionPriv::RunType fX;
454 SkRegionPriv::RunType fY0, fY1;
455 uint8_t fFlags;
456 Edge* fNext;
457
setEdge458 void set(int x, int y0, int y1) {
459 SkASSERT(y0 != y1);
460
461 fX = (SkRegionPriv::RunType)(x);
462 fY0 = (SkRegionPriv::RunType)(y0);
463 fY1 = (SkRegionPriv::RunType)(y1);
464 fFlags = 0;
465 SkDEBUGCODE(fNext = nullptr;)
466 }
467
topEdge468 int top() const {
469 return std::min(fY0, fY1);
470 }
471 };
472
find_link(Edge * base,Edge * stop)473 static void find_link(Edge* base, Edge* stop) {
474 SkASSERT(base < stop);
475
476 if (base->fFlags == Edge::kCompleteLink) {
477 SkASSERT(base->fNext);
478 return;
479 }
480
481 SkASSERT(base + 1 < stop);
482
483 int y0 = base->fY0;
484 int y1 = base->fY1;
485
486 Edge* e = base;
487 if ((base->fFlags & Edge::kY0Link) == 0) {
488 for (;;) {
489 e += 1;
490 if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
491 SkASSERT(nullptr == e->fNext);
492 e->fNext = base;
493 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
494 break;
495 }
496 }
497 }
498
499 e = base;
500 if ((base->fFlags & Edge::kY1Link) == 0) {
501 for (;;) {
502 e += 1;
503 if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
504 SkASSERT(nullptr == base->fNext);
505 base->fNext = e;
506 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
507 break;
508 }
509 }
510 }
511
512 base->fFlags = Edge::kCompleteLink;
513 }
514
extract_path(Edge * edge,Edge * stop,SkPath * path)515 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
516 while (0 == edge->fFlags) {
517 edge++; // skip over "used" edges
518 }
519
520 SkASSERT(edge < stop);
521
522 Edge* base = edge;
523 Edge* prev = edge;
524 edge = edge->fNext;
525 SkASSERT(edge != base);
526
527 int count = 1;
528 path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
529 prev->fFlags = 0;
530 do {
531 if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
532 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
533 path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
534 }
535 prev = edge;
536 edge = edge->fNext;
537 count += 1;
538 prev->fFlags = 0;
539 } while (edge != base);
540 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
541 path->close();
542 return count;
543 }
544
545 struct EdgeLT {
operator ()EdgeLT546 bool operator()(const Edge& a, const Edge& b) const {
547 return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
548 }
549 };
550
getBoundaryPath(SkPath * path) const551 bool SkRegion::getBoundaryPath(SkPath* path) const {
552 // path could safely be nullptr if we're empty, but the caller shouldn't
553 // *know* that
554 SkASSERT(path);
555
556 if (this->isEmpty()) {
557 return false;
558 }
559
560 const SkIRect& bounds = this->getBounds();
561
562 if (this->isRect()) {
563 SkRect r;
564 r.set(bounds); // this converts the ints to scalars
565 path->addRect(r);
566 return true;
567 }
568
569 SkRegion::Iterator iter(*this);
570 SkTDArray<Edge> edges;
571
572 for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
573 Edge* edge = edges.append(2);
574 edge[0].set(r.fLeft, r.fBottom, r.fTop);
575 edge[1].set(r.fRight, r.fTop, r.fBottom);
576 }
577
578 int count = edges.size();
579 Edge* start = edges.begin();
580 Edge* stop = start + count;
581 SkTQSort<Edge>(start, stop, EdgeLT());
582
583 Edge* e;
584 for (e = start; e != stop; e++) {
585 find_link(e, stop);
586 }
587
588 #ifdef SK_DEBUG
589 for (e = start; e != stop; e++) {
590 SkASSERT(e->fNext != nullptr);
591 SkASSERT(e->fFlags == Edge::kCompleteLink);
592 }
593 #endif
594
595 path->incReserve(count << 1);
596 do {
597 SkASSERT(count > 1);
598 count -= extract_path(start, stop, path);
599 } while (count > 0);
600
601 return true;
602 }
603