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