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