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