Line data Source code
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 :
9 : #include "SkAtomics.h"
10 : #include "SkRegionPriv.h"
11 : #include "SkTemplates.h"
12 : #include "SkUtils.h"
13 :
14 : /* Region Layout
15 : *
16 : * TOP
17 : *
18 : * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ]
19 : * ...
20 : *
21 : * Y-Sentinel
22 : */
23 :
24 : SkDEBUGCODE(int32_t gRgnAllocCounter;)
25 :
26 : /////////////////////////////////////////////////////////////////////////////////////////////////
27 :
28 : /* Pass in the beginning with the intervals.
29 : * We back up 1 to read the interval-count.
30 : * Return the beginning of the next scanline (i.e. the next Y-value)
31 : */
32 308 : static SkRegion::RunType* skip_intervals(const SkRegion::RunType runs[]) {
33 308 : int intervals = runs[-1];
34 : #ifdef SK_DEBUG
35 308 : if (intervals > 0) {
36 275 : SkASSERT(runs[0] < runs[1]);
37 275 : SkASSERT(runs[1] < SkRegion::kRunTypeSentinel);
38 : } else {
39 33 : SkASSERT(0 == intervals);
40 33 : SkASSERT(SkRegion::kRunTypeSentinel == runs[0]);
41 : }
42 : #endif
43 308 : runs += intervals * 2 + 1;
44 308 : return const_cast<SkRegion::RunType*>(runs);
45 : }
46 :
47 82 : bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count,
48 : SkIRect* bounds) {
49 82 : assert_sentinel(runs[0], false); // top
50 82 : SkASSERT(count >= kRectRegionRuns);
51 :
52 82 : if (count == kRectRegionRuns) {
53 9 : assert_sentinel(runs[1], false); // bottom
54 9 : SkASSERT(1 == runs[2]);
55 9 : assert_sentinel(runs[3], false); // left
56 9 : assert_sentinel(runs[4], false); // right
57 9 : assert_sentinel(runs[5], true);
58 9 : assert_sentinel(runs[6], true);
59 :
60 9 : SkASSERT(runs[0] < runs[1]); // valid height
61 9 : SkASSERT(runs[3] < runs[4]); // valid width
62 :
63 9 : bounds->set(runs[3], runs[0], runs[4], runs[1]);
64 9 : return true;
65 : }
66 73 : return false;
67 : }
68 :
69 : //////////////////////////////////////////////////////////////////////////
70 :
71 1653 : SkRegion::SkRegion() {
72 1653 : fBounds.set(0, 0, 0, 0);
73 1653 : fRunHead = SkRegion_gEmptyRunHeadPtr;
74 1653 : }
75 :
76 152 : SkRegion::SkRegion(const SkRegion& src) {
77 152 : fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
78 152 : this->setRegion(src);
79 152 : }
80 :
81 127 : SkRegion::SkRegion(const SkIRect& rect) {
82 127 : fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
83 127 : this->setRect(rect);
84 127 : }
85 :
86 3760 : SkRegion::~SkRegion() {
87 1880 : this->freeRuns();
88 1880 : }
89 :
90 3151 : void SkRegion::freeRuns() {
91 3151 : if (this->isComplex()) {
92 124 : SkASSERT(fRunHead->fRefCnt >= 1);
93 124 : if (sk_atomic_dec(&fRunHead->fRefCnt) == 1) {
94 : //SkASSERT(gRgnAllocCounter > 0);
95 : //SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter));
96 : //SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter));
97 73 : sk_free(fRunHead);
98 : }
99 : }
100 3151 : }
101 :
102 0 : void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) {
103 0 : fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount);
104 0 : }
105 :
106 73 : void SkRegion::allocateRuns(int count) {
107 73 : fRunHead = RunHead::Alloc(count);
108 73 : }
109 :
110 0 : void SkRegion::allocateRuns(const RunHead& head) {
111 0 : fRunHead = RunHead::Alloc(head.fRunCount,
112 : head.getYSpanCount(),
113 : head.getIntervalCount());
114 0 : }
115 :
116 473 : SkRegion& SkRegion::operator=(const SkRegion& src) {
117 473 : (void)this->setRegion(src);
118 473 : return *this;
119 : }
120 :
121 0 : void SkRegion::swap(SkRegion& other) {
122 0 : SkTSwap<SkIRect>(fBounds, other.fBounds);
123 0 : SkTSwap<RunHead*>(fRunHead, other.fRunHead);
124 0 : }
125 :
126 0 : int SkRegion::computeRegionComplexity() const {
127 0 : if (this->isEmpty()) {
128 0 : return 0;
129 0 : } else if (this->isRect()) {
130 0 : return 1;
131 : }
132 0 : return fRunHead->getIntervalCount();
133 : }
134 :
135 15 : bool SkRegion::setEmpty() {
136 15 : this->freeRuns();
137 15 : fBounds.set(0, 0, 0, 0);
138 15 : fRunHead = SkRegion_gEmptyRunHeadPtr;
139 15 : return false;
140 : }
141 :
142 522 : bool SkRegion::setRect(int32_t left, int32_t top,
143 : int32_t right, int32_t bottom) {
144 522 : if (left >= right || top >= bottom) {
145 0 : return this->setEmpty();
146 : }
147 522 : this->freeRuns();
148 522 : fBounds.set(left, top, right, bottom);
149 522 : fRunHead = SkRegion_gRectRunHeadPtr;
150 522 : return true;
151 : }
152 :
153 522 : bool SkRegion::setRect(const SkIRect& r) {
154 522 : return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom);
155 : }
156 :
157 692 : bool SkRegion::setRegion(const SkRegion& src) {
158 692 : if (this != &src) {
159 661 : this->freeRuns();
160 :
161 661 : fBounds = src.fBounds;
162 661 : fRunHead = src.fRunHead;
163 661 : if (this->isComplex()) {
164 51 : sk_atomic_inc(&fRunHead->fRefCnt);
165 : }
166 : }
167 692 : return fRunHead != SkRegion_gEmptyRunHeadPtr;
168 : }
169 :
170 0 : bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) {
171 0 : SkRegion tmp(rect);
172 :
173 0 : return this->op(tmp, rgn, op);
174 : }
175 :
176 127 : bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) {
177 254 : SkRegion tmp(rect);
178 :
179 254 : return this->op(rgn, tmp, op);
180 : }
181 :
182 : ///////////////////////////////////////////////////////////////////////////////
183 :
184 : #ifdef SK_BUILD_FOR_ANDROID
185 : #include <stdio.h>
186 : char* SkRegion::toString() {
187 : Iterator iter(*this);
188 : int count = 0;
189 : while (!iter.done()) {
190 : count++;
191 : iter.next();
192 : }
193 : // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0'
194 : const int max = (count*((11*4)+5))+11+1;
195 : char* result = (char*)sk_malloc_throw(max);
196 : if (result == nullptr) {
197 : return nullptr;
198 : }
199 : count = snprintf(result, max, "SkRegion(");
200 : iter.reset(*this);
201 : while (!iter.done()) {
202 : const SkIRect& r = iter.rect();
203 : count += snprintf(result+count, max - count,
204 : "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
205 : iter.next();
206 : }
207 : count += snprintf(result+count, max - count, ")");
208 : return result;
209 : }
210 : #endif
211 :
212 : ///////////////////////////////////////////////////////////////////////////////
213 :
214 0 : int SkRegion::count_runtype_values(int* itop, int* ibot) const {
215 : int maxT;
216 :
217 0 : if (this->isRect()) {
218 0 : maxT = 2;
219 : } else {
220 0 : SkASSERT(this->isComplex());
221 0 : maxT = fRunHead->getIntervalCount() * 2;
222 : }
223 0 : *itop = fBounds.fTop;
224 0 : *ibot = fBounds.fBottom;
225 0 : return maxT;
226 : }
227 :
228 82 : static bool isRunCountEmpty(int count) {
229 82 : return count <= 2;
230 : }
231 :
232 82 : bool SkRegion::setRuns(RunType runs[], int count) {
233 82 : SkDEBUGCODE(this->validate();)
234 82 : SkASSERT(count > 0);
235 :
236 82 : if (isRunCountEmpty(count)) {
237 : // SkDEBUGF(("setRuns: empty\n"));
238 0 : assert_sentinel(runs[count-1], true);
239 0 : return this->setEmpty();
240 : }
241 :
242 : // trim off any empty spans from the top and bottom
243 : // weird I should need this, perhaps op() could be smarter...
244 82 : if (count > kRectRegionRuns) {
245 81 : RunType* stop = runs + count;
246 81 : assert_sentinel(runs[0], false); // top
247 81 : assert_sentinel(runs[1], false); // bottom
248 : // runs[2] is uncomputed intervalCount
249 :
250 81 : if (runs[3] == SkRegion::kRunTypeSentinel) { // should be first left...
251 0 : runs += 3; // skip empty initial span
252 0 : runs[0] = runs[-2]; // set new top to prev bottom
253 0 : assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row
254 0 : assert_sentinel(runs[2], false); // intervalcount
255 0 : assert_sentinel(runs[3], false); // left
256 0 : assert_sentinel(runs[4], false); // right
257 : }
258 :
259 81 : assert_sentinel(stop[-1], true);
260 81 : assert_sentinel(stop[-2], true);
261 :
262 : // now check for a trailing empty span
263 81 : if (stop[-5] == SkRegion::kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs
264 17 : stop[-4] = SkRegion::kRunTypeSentinel; // kill empty last span
265 17 : stop -= 3;
266 17 : assert_sentinel(stop[-1], true); // last y-sentinel
267 17 : assert_sentinel(stop[-2], true); // last x-sentinel
268 17 : assert_sentinel(stop[-3], false); // last right
269 17 : assert_sentinel(stop[-4], false); // last left
270 17 : assert_sentinel(stop[-5], false); // last interval-count
271 17 : assert_sentinel(stop[-6], false); // last bottom
272 : }
273 81 : count = (int)(stop - runs);
274 : }
275 :
276 82 : SkASSERT(count >= kRectRegionRuns);
277 :
278 82 : if (SkRegion::RunsAreARect(runs, count, &fBounds)) {
279 9 : return this->setRect(fBounds);
280 : }
281 :
282 : // if we get here, we need to become a complex region
283 :
284 73 : if (!this->isComplex() || fRunHead->fRunCount != count) {
285 73 : this->freeRuns();
286 73 : this->allocateRuns(count);
287 73 : SkASSERT(this->isComplex());
288 : }
289 :
290 : // must call this before we can write directly into runs()
291 : // in case we are sharing the buffer with another region (copy on write)
292 73 : fRunHead = fRunHead->ensureWritable();
293 73 : memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
294 73 : fRunHead->computeRunBounds(&fBounds);
295 :
296 73 : SkDEBUGCODE(this->validate();)
297 :
298 73 : return true;
299 : }
300 :
301 106 : void SkRegion::BuildRectRuns(const SkIRect& bounds,
302 : RunType runs[kRectRegionRuns]) {
303 106 : runs[0] = bounds.fTop;
304 106 : runs[1] = bounds.fBottom;
305 106 : runs[2] = 1; // 1 interval for this scanline
306 106 : runs[3] = bounds.fLeft;
307 106 : runs[4] = bounds.fRight;
308 106 : runs[5] = kRunTypeSentinel;
309 106 : runs[6] = kRunTypeSentinel;
310 106 : }
311 :
312 0 : bool SkRegion::contains(int32_t x, int32_t y) const {
313 0 : SkDEBUGCODE(this->validate();)
314 :
315 0 : if (!fBounds.contains(x, y)) {
316 0 : return false;
317 : }
318 0 : if (this->isRect()) {
319 0 : return true;
320 : }
321 0 : SkASSERT(this->isComplex());
322 :
323 0 : const RunType* runs = fRunHead->findScanline(y);
324 :
325 : // Skip the Bottom and IntervalCount
326 0 : runs += 2;
327 :
328 : // Just walk this scanline, checking each interval. The X-sentinel will
329 : // appear as a left-inteval (runs[0]) and should abort the search.
330 : //
331 : // We could do a bsearch, using interval-count (runs[1]), but need to time
332 : // when that would be worthwhile.
333 : //
334 : for (;;) {
335 0 : if (x < runs[0]) {
336 0 : break;
337 : }
338 0 : if (x < runs[1]) {
339 0 : return true;
340 : }
341 0 : runs += 2;
342 : }
343 0 : return false;
344 : }
345 :
346 0 : static SkRegion::RunType scanline_bottom(const SkRegion::RunType runs[]) {
347 0 : return runs[0];
348 : }
349 :
350 0 : static const SkRegion::RunType* scanline_next(const SkRegion::RunType runs[]) {
351 : // skip [B N [L R]... S]
352 0 : return runs + 2 + runs[1] * 2 + 1;
353 : }
354 :
355 0 : static bool scanline_contains(const SkRegion::RunType runs[],
356 : SkRegion::RunType L, SkRegion::RunType R) {
357 0 : runs += 2; // skip Bottom and IntervalCount
358 : for (;;) {
359 0 : if (L < runs[0]) {
360 0 : break;
361 : }
362 0 : if (R <= runs[1]) {
363 0 : return true;
364 : }
365 0 : runs += 2;
366 : }
367 0 : return false;
368 : }
369 :
370 0 : bool SkRegion::contains(const SkIRect& r) const {
371 0 : SkDEBUGCODE(this->validate();)
372 :
373 0 : if (!fBounds.contains(r)) {
374 0 : return false;
375 : }
376 0 : if (this->isRect()) {
377 0 : return true;
378 : }
379 0 : SkASSERT(this->isComplex());
380 :
381 0 : const RunType* scanline = fRunHead->findScanline(r.fTop);
382 : for (;;) {
383 0 : if (!scanline_contains(scanline, r.fLeft, r.fRight)) {
384 0 : return false;
385 : }
386 0 : if (r.fBottom <= scanline_bottom(scanline)) {
387 0 : break;
388 : }
389 0 : scanline = scanline_next(scanline);
390 : }
391 0 : return true;
392 : }
393 :
394 0 : bool SkRegion::contains(const SkRegion& rgn) const {
395 0 : SkDEBUGCODE(this->validate();)
396 0 : SkDEBUGCODE(rgn.validate();)
397 :
398 0 : if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) {
399 0 : return false;
400 : }
401 0 : if (this->isRect()) {
402 0 : return true;
403 : }
404 0 : if (rgn.isRect()) {
405 0 : return this->contains(rgn.getBounds());
406 : }
407 :
408 : /*
409 : * A contains B is equivalent to
410 : * B - A == 0
411 : */
412 0 : return !Oper(rgn, *this, kDifference_Op, nullptr);
413 : }
414 :
415 164 : const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
416 : int* intervals) const {
417 164 : SkASSERT(tmpStorage && intervals);
418 164 : const RunType* runs = tmpStorage;
419 :
420 164 : if (this->isEmpty()) {
421 0 : tmpStorage[0] = kRunTypeSentinel;
422 0 : *intervals = 0;
423 164 : } else if (this->isRect()) {
424 106 : BuildRectRuns(fBounds, tmpStorage);
425 106 : *intervals = 1;
426 : } else {
427 58 : runs = fRunHead->readonly_runs();
428 58 : *intervals = fRunHead->getIntervalCount();
429 : }
430 164 : return runs;
431 : }
432 :
433 : ///////////////////////////////////////////////////////////////////////////////
434 :
435 0 : static bool scanline_intersects(const SkRegion::RunType runs[],
436 : SkRegion::RunType L, SkRegion::RunType R) {
437 0 : runs += 2; // skip Bottom and IntervalCount
438 : for (;;) {
439 0 : if (R <= runs[0]) {
440 0 : break;
441 : }
442 0 : if (L < runs[1]) {
443 0 : return true;
444 : }
445 0 : runs += 2;
446 : }
447 0 : return false;
448 : }
449 :
450 0 : bool SkRegion::intersects(const SkIRect& r) const {
451 0 : SkDEBUGCODE(this->validate();)
452 :
453 0 : if (this->isEmpty() || r.isEmpty()) {
454 0 : return false;
455 : }
456 :
457 : SkIRect sect;
458 0 : if (!sect.intersect(fBounds, r)) {
459 0 : return false;
460 : }
461 0 : if (this->isRect()) {
462 0 : return true;
463 : }
464 0 : SkASSERT(this->isComplex());
465 :
466 0 : const RunType* scanline = fRunHead->findScanline(sect.fTop);
467 : for (;;) {
468 0 : if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) {
469 0 : return true;
470 : }
471 0 : if (sect.fBottom <= scanline_bottom(scanline)) {
472 0 : break;
473 : }
474 0 : scanline = scanline_next(scanline);
475 : }
476 0 : return false;
477 : }
478 :
479 0 : bool SkRegion::intersects(const SkRegion& rgn) const {
480 0 : if (this->isEmpty() || rgn.isEmpty()) {
481 0 : return false;
482 : }
483 :
484 0 : if (!SkIRect::Intersects(fBounds, rgn.fBounds)) {
485 0 : return false;
486 : }
487 :
488 0 : bool weAreARect = this->isRect();
489 0 : bool theyAreARect = rgn.isRect();
490 :
491 0 : if (weAreARect && theyAreARect) {
492 0 : return true;
493 : }
494 0 : if (weAreARect) {
495 0 : return rgn.intersects(this->getBounds());
496 : }
497 0 : if (theyAreARect) {
498 0 : return this->intersects(rgn.getBounds());
499 : }
500 :
501 : // both of us are complex
502 0 : return Oper(*this, rgn, kIntersect_Op, nullptr);
503 : }
504 :
505 : ///////////////////////////////////////////////////////////////////////////////
506 :
507 0 : bool SkRegion::operator==(const SkRegion& b) const {
508 0 : SkDEBUGCODE(validate();)
509 0 : SkDEBUGCODE(b.validate();)
510 :
511 0 : if (this == &b) {
512 0 : return true;
513 : }
514 0 : if (fBounds != b.fBounds) {
515 0 : return false;
516 : }
517 :
518 0 : const SkRegion::RunHead* ah = fRunHead;
519 0 : const SkRegion::RunHead* bh = b.fRunHead;
520 :
521 : // this catches empties and rects being equal
522 0 : if (ah == bh) {
523 0 : return true;
524 : }
525 : // now we insist that both are complex (but different ptrs)
526 0 : if (!this->isComplex() || !b.isComplex()) {
527 0 : return false;
528 : }
529 0 : return ah->fRunCount == bh->fRunCount &&
530 0 : !memcmp(ah->readonly_runs(), bh->readonly_runs(),
531 0 : ah->fRunCount * sizeof(SkRegion::RunType));
532 : }
533 :
534 0 : void SkRegion::translate(int dx, int dy, SkRegion* dst) const {
535 0 : SkDEBUGCODE(this->validate();)
536 :
537 0 : if (nullptr == dst) {
538 0 : return;
539 : }
540 0 : if (this->isEmpty()) {
541 0 : dst->setEmpty();
542 0 : } else if (this->isRect()) {
543 0 : dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy,
544 0 : fBounds.fRight + dx, fBounds.fBottom + dy);
545 : } else {
546 0 : if (this == dst) {
547 0 : dst->fRunHead = dst->fRunHead->ensureWritable();
548 : } else {
549 0 : SkRegion tmp;
550 0 : tmp.allocateRuns(*fRunHead);
551 0 : SkASSERT(tmp.isComplex());
552 0 : tmp.fBounds = fBounds;
553 0 : dst->swap(tmp);
554 : }
555 :
556 0 : dst->fBounds.offset(dx, dy);
557 :
558 0 : const RunType* sruns = fRunHead->readonly_runs();
559 0 : RunType* druns = dst->fRunHead->writable_runs();
560 :
561 0 : *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top
562 : for (;;) {
563 0 : int bottom = *sruns++;
564 0 : if (bottom == kRunTypeSentinel) {
565 0 : break;
566 : }
567 0 : *druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
568 0 : *druns++ = *sruns++; // copy intervalCount;
569 : for (;;) {
570 0 : int x = *sruns++;
571 0 : if (x == kRunTypeSentinel) {
572 0 : break;
573 : }
574 0 : *druns++ = (SkRegion::RunType)(x + dx);
575 0 : *druns++ = (SkRegion::RunType)(*sruns++ + dx);
576 0 : }
577 0 : *druns++ = kRunTypeSentinel; // x sentinel
578 0 : }
579 0 : *druns++ = kRunTypeSentinel; // y sentinel
580 :
581 0 : SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
582 0 : SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
583 : }
584 :
585 0 : SkDEBUGCODE(this->validate();)
586 : }
587 :
588 : ///////////////////////////////////////////////////////////////////////////////
589 :
590 0 : bool SkRegion::setRects(const SkIRect rects[], int count) {
591 0 : if (0 == count) {
592 0 : this->setEmpty();
593 : } else {
594 0 : this->setRect(rects[0]);
595 0 : for (int i = 1; i < count; i++) {
596 0 : this->op(rects[i], kUnion_Op);
597 : }
598 : }
599 0 : return !this->isEmpty();
600 : }
601 :
602 : ///////////////////////////////////////////////////////////////////////////////
603 :
604 : #if defined _WIN32 // disable warning : local variable used without having been initialized
605 : #pragma warning ( push )
606 : #pragma warning ( disable : 4701 )
607 : #endif
608 :
609 : #ifdef SK_DEBUG
610 850 : static void assert_valid_pair(int left, int rite)
611 : {
612 850 : SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite);
613 850 : }
614 : #else
615 : #define assert_valid_pair(left, rite)
616 : #endif
617 :
618 : struct spanRec {
619 : const SkRegion::RunType* fA_runs;
620 : const SkRegion::RunType* fB_runs;
621 : int fA_left, fA_rite, fB_left, fB_rite;
622 : int fLeft, fRite, fInside;
623 :
624 325 : void init(const SkRegion::RunType a_runs[],
625 : const SkRegion::RunType b_runs[]) {
626 325 : fA_left = *a_runs++;
627 325 : fA_rite = *a_runs++;
628 325 : fB_left = *b_runs++;
629 325 : fB_rite = *b_runs++;
630 :
631 325 : fA_runs = a_runs;
632 325 : fB_runs = b_runs;
633 325 : }
634 :
635 750 : bool done() const {
636 : SkASSERT(fA_left <= SkRegion::kRunTypeSentinel);
637 : SkASSERT(fB_left <= SkRegion::kRunTypeSentinel);
638 1195 : return fA_left == SkRegion::kRunTypeSentinel &&
639 1195 : fB_left == SkRegion::kRunTypeSentinel;
640 : }
641 :
642 425 : void next() {
643 425 : assert_valid_pair(fA_left, fA_rite);
644 425 : assert_valid_pair(fB_left, fB_rite);
645 :
646 425 : int inside, left, rite SK_INIT_TO_AVOID_WARNING;
647 425 : bool a_flush = false;
648 425 : bool b_flush = false;
649 :
650 425 : int a_left = fA_left;
651 425 : int a_rite = fA_rite;
652 425 : int b_left = fB_left;
653 425 : int b_rite = fB_rite;
654 :
655 425 : if (a_left < b_left) {
656 256 : inside = 1;
657 256 : left = a_left;
658 256 : if (a_rite <= b_left) { // [...] <...>
659 229 : rite = a_rite;
660 229 : a_flush = true;
661 : } else { // [...<..]...> or [...<...>...]
662 27 : rite = a_left = b_left;
663 : }
664 169 : } else if (b_left < a_left) {
665 128 : inside = 2;
666 128 : left = b_left;
667 128 : if (b_rite <= a_left) { // [...] <...>
668 120 : rite = b_rite;
669 120 : b_flush = true;
670 : } else { // [...<..]...> or [...<...>...]
671 8 : rite = b_left = a_left;
672 : }
673 : } else { // a_left == b_left
674 41 : inside = 3;
675 41 : left = a_left; // or b_left
676 41 : if (a_rite <= b_rite) {
677 24 : rite = b_left = a_rite;
678 24 : a_flush = true;
679 : }
680 41 : if (b_rite <= a_rite) {
681 22 : rite = a_left = b_rite;
682 22 : b_flush = true;
683 : }
684 : }
685 :
686 425 : if (a_flush) {
687 253 : a_left = *fA_runs++;
688 253 : a_rite = *fA_runs++;
689 : }
690 425 : if (b_flush) {
691 142 : b_left = *fB_runs++;
692 142 : b_rite = *fB_runs++;
693 : }
694 :
695 425 : SkASSERT(left <= rite);
696 :
697 : // now update our state
698 425 : fA_left = a_left;
699 425 : fA_rite = a_rite;
700 425 : fB_left = b_left;
701 425 : fB_rite = b_rite;
702 :
703 425 : fLeft = left;
704 425 : fRite = rite;
705 425 : fInside = inside;
706 425 : }
707 : };
708 :
709 325 : static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
710 : const SkRegion::RunType b_runs[],
711 : SkRegion::RunType dst[],
712 : int min, int max) {
713 : spanRec rec;
714 325 : bool firstInterval = true;
715 :
716 325 : rec.init(a_runs, b_runs);
717 :
718 1175 : while (!rec.done()) {
719 425 : rec.next();
720 :
721 425 : int left = rec.fLeft;
722 425 : int rite = rec.fRite;
723 :
724 : // add left,rite to our dst buffer (checking for coincidence
725 425 : if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
726 : left < rite) { // skip if equal
727 285 : if (firstInterval || dst[-1] < left) {
728 285 : *dst++ = (SkRegion::RunType)(left);
729 285 : *dst++ = (SkRegion::RunType)(rite);
730 285 : firstInterval = false;
731 : } else {
732 : // update the right edge
733 0 : dst[-1] = (SkRegion::RunType)(rite);
734 : }
735 : }
736 : }
737 :
738 325 : *dst++ = SkRegion::kRunTypeSentinel;
739 325 : return dst;
740 : }
741 :
742 : #if defined _WIN32
743 : #pragma warning ( pop )
744 : #endif
745 :
746 : static const struct {
747 : uint8_t fMin;
748 : uint8_t fMax;
749 : } gOpMinMax[] = {
750 : { 1, 1 }, // Difference
751 : { 3, 3 }, // Intersection
752 : { 1, 3 }, // Union
753 : { 1, 2 } // XOR
754 : };
755 :
756 : class RgnOper {
757 : public:
758 82 : RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) {
759 : // need to ensure that the op enum lines up with our minmax array
760 : SkASSERT(SkRegion::kDifference_Op == 0);
761 : SkASSERT(SkRegion::kIntersect_Op == 1);
762 : SkASSERT(SkRegion::kUnion_Op == 2);
763 : SkASSERT(SkRegion::kXOR_Op == 3);
764 82 : SkASSERT((unsigned)op <= 3);
765 :
766 82 : fStartDst = dst;
767 82 : fPrevDst = dst + 1;
768 82 : fPrevLen = 0; // will never match a length from operate_on_span
769 82 : fTop = (SkRegion::RunType)(top); // just a first guess, we might update this
770 :
771 82 : fMin = gOpMinMax[op].fMin;
772 82 : fMax = gOpMinMax[op].fMax;
773 82 : }
774 :
775 325 : void addSpan(int bottom, const SkRegion::RunType a_runs[],
776 : const SkRegion::RunType b_runs[]) {
777 : // skip X values and slots for the next Y+intervalCount
778 325 : SkRegion::RunType* start = fPrevDst + fPrevLen + 2;
779 : // start points to beginning of dst interval
780 325 : SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax);
781 325 : size_t len = stop - start;
782 325 : SkASSERT(len >= 1 && (len & 1) == 1);
783 325 : SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]);
784 :
785 325 : if (fPrevLen == len &&
786 30 : (1 == len || !memcmp(fPrevDst, start,
787 : (len - 1) * sizeof(SkRegion::RunType)))) {
788 : // update Y value
789 26 : fPrevDst[-2] = (SkRegion::RunType)(bottom);
790 : } else { // accept the new span
791 299 : if (len == 1 && fPrevLen == 0) {
792 21 : fTop = (SkRegion::RunType)(bottom); // just update our bottom
793 : } else {
794 278 : start[-2] = (SkRegion::RunType)(bottom);
795 278 : start[-1] = SkToS32(len >> 1);
796 278 : fPrevDst = start;
797 278 : fPrevLen = len;
798 : }
799 : }
800 325 : }
801 :
802 82 : int flush() {
803 82 : fStartDst[0] = fTop;
804 82 : fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel;
805 82 : return (int)(fPrevDst - fStartDst + fPrevLen + 1);
806 : }
807 :
808 0 : bool isEmpty() const { return 0 == fPrevLen; }
809 :
810 : uint8_t fMin, fMax;
811 :
812 : private:
813 : SkRegion::RunType* fStartDst;
814 : SkRegion::RunType* fPrevDst;
815 : size_t fPrevLen;
816 : SkRegion::RunType fTop;
817 : };
818 :
819 : // want a unique value to signal that we exited due to quickExit
820 : #define QUICK_EXIT_TRUE_COUNT (-1)
821 :
822 82 : static int operate(const SkRegion::RunType a_runs[],
823 : const SkRegion::RunType b_runs[],
824 : SkRegion::RunType dst[],
825 : SkRegion::Op op,
826 : bool quickExit) {
827 : const SkRegion::RunType gEmptyScanline[] = {
828 : 0, // dummy bottom value
829 : 0, // zero intervals
830 : SkRegion::kRunTypeSentinel,
831 : // just need a 2nd value, since spanRec.init() reads 2 values, even
832 : // though if the first value is the sentinel, it ignores the 2nd value.
833 : // w/o the 2nd value here, we might read uninitialized memory.
834 : // This happens when we are using gSentinel, which is pointing at
835 : // our sentinel value.
836 : 0
837 82 : };
838 82 : const SkRegion::RunType* const gSentinel = &gEmptyScanline[2];
839 :
840 82 : int a_top = *a_runs++;
841 82 : int a_bot = *a_runs++;
842 82 : int b_top = *b_runs++;
843 82 : int b_bot = *b_runs++;
844 :
845 82 : a_runs += 1; // skip the intervalCount;
846 82 : b_runs += 1; // skip the intervalCount;
847 :
848 : // Now a_runs and b_runs to their intervals (or sentinel)
849 :
850 82 : assert_sentinel(a_top, false);
851 82 : assert_sentinel(a_bot, false);
852 82 : assert_sentinel(b_top, false);
853 82 : assert_sentinel(b_bot, false);
854 :
855 82 : RgnOper oper(SkMin32(a_top, b_top), dst, op);
856 :
857 82 : int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test
858 :
859 700 : while (a_bot < SkRegion::kRunTypeSentinel ||
860 : b_bot < SkRegion::kRunTypeSentinel) {
861 309 : int top, bot SK_INIT_TO_AVOID_WARNING;
862 309 : const SkRegion::RunType* run0 = gSentinel;
863 309 : const SkRegion::RunType* run1 = gSentinel;
864 309 : bool a_flush = false;
865 309 : bool b_flush = false;
866 :
867 309 : if (a_top < b_top) {
868 171 : top = a_top;
869 171 : run0 = a_runs;
870 171 : if (a_bot <= b_top) { // [...] <...>
871 158 : bot = a_bot;
872 158 : a_flush = true;
873 : } else { // [...<..]...> or [...<...>...]
874 13 : bot = a_top = b_top;
875 : }
876 138 : } else if (b_top < a_top) {
877 73 : top = b_top;
878 73 : run1 = b_runs;
879 73 : if (b_bot <= a_top) { // [...] <...>
880 68 : bot = b_bot;
881 68 : b_flush = true;
882 : } else { // [...<..]...> or [...<...>...]
883 5 : bot = b_top = a_top;
884 : }
885 : } else { // a_top == b_top
886 65 : top = a_top; // or b_top
887 65 : run0 = a_runs;
888 65 : run1 = b_runs;
889 65 : if (a_bot <= b_bot) {
890 36 : bot = b_top = a_bot;
891 36 : a_flush = true;
892 : }
893 65 : if (b_bot <= a_bot) {
894 46 : bot = a_top = b_bot;
895 46 : b_flush = true;
896 : }
897 : }
898 :
899 309 : if (top > prevBot) {
900 16 : oper.addSpan(top, gSentinel, gSentinel);
901 : }
902 309 : oper.addSpan(bot, run0, run1);
903 :
904 309 : if (quickExit && !oper.isEmpty()) {
905 0 : return QUICK_EXIT_TRUE_COUNT;
906 : }
907 :
908 309 : if (a_flush) {
909 194 : a_runs = skip_intervals(a_runs);
910 194 : a_top = a_bot;
911 194 : a_bot = *a_runs++;
912 194 : a_runs += 1; // skip uninitialized intervalCount
913 194 : if (a_bot == SkRegion::kRunTypeSentinel) {
914 82 : a_top = a_bot;
915 : }
916 : }
917 309 : if (b_flush) {
918 114 : b_runs = skip_intervals(b_runs);
919 114 : b_top = b_bot;
920 114 : b_bot = *b_runs++;
921 114 : b_runs += 1; // skip uninitialized intervalCount
922 114 : if (b_bot == SkRegion::kRunTypeSentinel) {
923 82 : b_top = b_bot;
924 : }
925 : }
926 :
927 309 : prevBot = bot;
928 : }
929 82 : return oper.flush();
930 : }
931 :
932 : ///////////////////////////////////////////////////////////////////////////////
933 :
934 : /* Given count RunTypes in a complex region, return the worst case number of
935 : logical intervals that represents (i.e. number of rects that would be
936 : returned from the iterator).
937 :
938 : We could just return count/2, since there must be at least 2 values per
939 : interval, but we can first trim off the const overhead of the initial TOP
940 : value, plus the final BOTTOM + 2 sentinels.
941 : */
942 : #if 0 // UNUSED
943 : static int count_to_intervals(int count) {
944 : SkASSERT(count >= 6); // a single rect is 6 values
945 : return (count - 4) >> 1;
946 : }
947 : #endif
948 :
949 : /* Given a number of intervals, what is the worst case representation of that
950 : many intervals?
951 :
952 : Worst case (from a storage perspective), is a vertical stack of single
953 : intervals: TOP + N * (BOTTOM INTERVALCOUNT LEFT RIGHT SENTINEL) + SENTINEL
954 : */
955 82 : static int intervals_to_count(int intervals) {
956 82 : return 1 + intervals * 5 + 1;
957 : }
958 :
959 : /* Given the intervalCounts of RunTypes in two regions, return the worst-case number
960 : of RunTypes need to store the result after a region-op.
961 : */
962 82 : static int compute_worst_case_count(int a_intervals, int b_intervals) {
963 : // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1)
964 82 : int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals;
965 : // convert back to number of RunType values
966 82 : return intervals_to_count(intervals);
967 : }
968 :
969 2 : static bool setEmptyCheck(SkRegion* result) {
970 2 : return result ? result->setEmpty() : false;
971 : }
972 :
973 0 : static bool setRectCheck(SkRegion* result, const SkIRect& rect) {
974 0 : return result ? result->setRect(rect) : !rect.isEmpty();
975 : }
976 :
977 67 : static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) {
978 67 : return result ? result->setRegion(rgn) : !rgn.isEmpty();
979 : }
980 :
981 151 : bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
982 : SkRegion* result) {
983 151 : SkASSERT((unsigned)op < kOpCount);
984 :
985 151 : if (kReplace_Op == op) {
986 0 : return setRegionCheck(result, rgnbOrig);
987 : }
988 :
989 : // swith to using pointers, so we can swap them as needed
990 151 : const SkRegion* rgna = &rgnaOrig;
991 151 : const SkRegion* rgnb = &rgnbOrig;
992 : // after this point, do not refer to rgnaOrig or rgnbOrig!!!
993 :
994 : // collaps difference and reverse-difference into just difference
995 151 : if (kReverseDifference_Op == op) {
996 0 : SkTSwap<const SkRegion*>(rgna, rgnb);
997 0 : op = kDifference_Op;
998 : }
999 :
1000 : SkIRect bounds;
1001 151 : bool a_empty = rgna->isEmpty();
1002 151 : bool b_empty = rgnb->isEmpty();
1003 151 : bool a_rect = rgna->isRect();
1004 151 : bool b_rect = rgnb->isRect();
1005 :
1006 151 : switch (op) {
1007 : case kDifference_Op:
1008 0 : if (a_empty) {
1009 0 : return setEmptyCheck(result);
1010 : }
1011 0 : if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds,
1012 0 : rgnb->fBounds)) {
1013 0 : return setRegionCheck(result, *rgna);
1014 : }
1015 0 : if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) {
1016 0 : return setEmptyCheck(result);
1017 : }
1018 0 : break;
1019 :
1020 : case kIntersect_Op:
1021 126 : if ((a_empty | b_empty)
1022 63 : || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) {
1023 2 : return setEmptyCheck(result);
1024 : }
1025 61 : if (a_rect & b_rect) {
1026 0 : return setRectCheck(result, bounds);
1027 : }
1028 61 : if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
1029 12 : return setRegionCheck(result, *rgnb);
1030 : }
1031 49 : if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
1032 31 : return setRegionCheck(result, *rgna);
1033 : }
1034 18 : break;
1035 :
1036 : case kUnion_Op:
1037 88 : if (a_empty) {
1038 24 : return setRegionCheck(result, *rgnb);
1039 : }
1040 64 : if (b_empty) {
1041 0 : return setRegionCheck(result, *rgna);
1042 : }
1043 64 : if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
1044 0 : return setRegionCheck(result, *rgna);
1045 : }
1046 64 : if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
1047 0 : return setRegionCheck(result, *rgnb);
1048 : }
1049 64 : break;
1050 :
1051 : case kXOR_Op:
1052 0 : if (a_empty) {
1053 0 : return setRegionCheck(result, *rgnb);
1054 : }
1055 0 : if (b_empty) {
1056 0 : return setRegionCheck(result, *rgna);
1057 : }
1058 0 : break;
1059 : default:
1060 0 : SkDEBUGFAIL("unknown region op");
1061 0 : return false;
1062 : }
1063 :
1064 : RunType tmpA[kRectRegionRuns];
1065 : RunType tmpB[kRectRegionRuns];
1066 :
1067 : int a_intervals, b_intervals;
1068 82 : const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals);
1069 82 : const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals);
1070 :
1071 82 : int dstCount = compute_worst_case_count(a_intervals, b_intervals);
1072 164 : SkAutoSTMalloc<256, RunType> array(dstCount);
1073 :
1074 : #ifdef SK_DEBUG
1075 : // Sometimes helpful to seed everything with a known value when debugging
1076 : // sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount);
1077 : #endif
1078 :
1079 82 : int count = operate(a_runs, b_runs, array.get(), op, nullptr == result);
1080 82 : SkASSERT(count <= dstCount);
1081 :
1082 82 : if (result) {
1083 82 : SkASSERT(count >= 0);
1084 82 : return result->setRuns(array.get(), count);
1085 : } else {
1086 0 : return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count);
1087 : }
1088 : }
1089 :
1090 151 : bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) {
1091 151 : SkDEBUGCODE(this->validate();)
1092 151 : return SkRegion::Oper(rgna, rgnb, op, this);
1093 : }
1094 :
1095 : ///////////////////////////////////////////////////////////////////////////////
1096 :
1097 : #include "SkBuffer.h"
1098 :
1099 0 : size_t SkRegion::writeToMemory(void* storage) const {
1100 0 : if (nullptr == storage) {
1101 0 : size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
1102 0 : if (!this->isEmpty()) {
1103 0 : size += sizeof(fBounds);
1104 0 : if (this->isComplex()) {
1105 0 : size += 2 * sizeof(int32_t); // ySpanCount + intervalCount
1106 0 : size += fRunHead->fRunCount * sizeof(RunType);
1107 : }
1108 : }
1109 0 : return size;
1110 : }
1111 :
1112 0 : SkWBuffer buffer(storage);
1113 :
1114 0 : if (this->isEmpty()) {
1115 0 : buffer.write32(-1);
1116 : } else {
1117 0 : bool isRect = this->isRect();
1118 :
1119 0 : buffer.write32(isRect ? 0 : fRunHead->fRunCount);
1120 0 : buffer.write(&fBounds, sizeof(fBounds));
1121 :
1122 0 : if (!isRect) {
1123 0 : buffer.write32(fRunHead->getYSpanCount());
1124 0 : buffer.write32(fRunHead->getIntervalCount());
1125 0 : buffer.write(fRunHead->readonly_runs(),
1126 0 : fRunHead->fRunCount * sizeof(RunType));
1127 : }
1128 : }
1129 0 : return buffer.pos();
1130 : }
1131 :
1132 : // Validate that a memory sequence is a valid region.
1133 : // Try to check all possible errors.
1134 : // never read beyond &runs[runCount-1].
1135 458 : static bool validate_run(const int32_t* runs,
1136 : int runCount,
1137 : const SkIRect& givenBounds,
1138 : int32_t ySpanCount,
1139 : int32_t intervalCount) {
1140 : // Region Layout:
1141 : // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel
1142 458 : if (ySpanCount < 1 || intervalCount < 2 || runCount != 2 + 3 * ySpanCount + 2 * intervalCount) {
1143 0 : return false;
1144 : }
1145 458 : SkASSERT(runCount >= 7); // 7==SkRegion::kRectRegionRuns
1146 : // quick sanity check:
1147 916 : if (runs[runCount - 1] != SkRegion::kRunTypeSentinel ||
1148 458 : runs[runCount - 2] != SkRegion::kRunTypeSentinel) {
1149 0 : return false;
1150 : }
1151 458 : const int32_t* const end = runs + runCount;
1152 458 : SkIRect bounds = {0, 0, 0 ,0}; // calulated bounds
1153 458 : SkIRect rect = {0, 0, 0, 0}; // current rect
1154 458 : rect.fTop = *runs++;
1155 458 : if (rect.fTop == SkRegion::kRunTypeSentinel) {
1156 0 : return false; // no rect can contain SkRegion::kRunTypeSentinel
1157 : }
1158 1224 : do {
1159 1682 : --ySpanCount;
1160 1682 : if (ySpanCount < 0) {
1161 0 : return false; // too many yspans
1162 : }
1163 1682 : rect.fBottom = *runs++;
1164 1682 : if (rect.fBottom == SkRegion::kRunTypeSentinel) {
1165 0 : return false;
1166 : }
1167 1682 : int32_t xIntervals = *runs++;
1168 1682 : SkASSERT(runs < end);
1169 1682 : if (xIntervals < 0 || runs + 1 + 2 * xIntervals > end) {
1170 0 : return false;
1171 : }
1172 1682 : intervalCount -= xIntervals;
1173 1682 : if (intervalCount < 0) {
1174 0 : return false; // too many intervals
1175 : }
1176 1771 : while (xIntervals-- > 0) {
1177 1771 : rect.fLeft = *runs++;
1178 1771 : rect.fRight = *runs++;
1179 5313 : if (rect.fLeft == SkRegion::kRunTypeSentinel ||
1180 3542 : rect.fRight == SkRegion::kRunTypeSentinel || rect.isEmpty()) {
1181 0 : return false;
1182 : }
1183 1771 : bounds.join(rect);
1184 : }
1185 1682 : if (*runs++ != SkRegion::kRunTypeSentinel) {
1186 0 : return false; // required check sentinal.
1187 : }
1188 1682 : rect.fTop = rect.fBottom;
1189 1682 : SkASSERT(runs < end);
1190 1682 : } while (*runs != SkRegion::kRunTypeSentinel);
1191 458 : ++runs;
1192 458 : if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) {
1193 0 : return false;
1194 : }
1195 458 : SkASSERT(runs == end); // if ySpanCount && intervalCount are right, must be correct length.
1196 458 : return true;
1197 : }
1198 0 : size_t SkRegion::readFromMemory(const void* storage, size_t length) {
1199 0 : SkRBuffer buffer(storage, length);
1200 0 : SkRegion tmp;
1201 : int32_t count;
1202 :
1203 : // Serialized Region Format:
1204 : // Empty:
1205 : // -1
1206 : // Simple Rect:
1207 : // 0 LEFT TOP RIGHT BOTTOM
1208 : // Complex Region:
1209 : // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT [RUNS....]
1210 0 : if (!buffer.readS32(&count) || count < -1) {
1211 0 : return 0;
1212 : }
1213 0 : if (count >= 0) {
1214 0 : if (!buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)) || tmp.fBounds.isEmpty()) {
1215 0 : return 0; // Short buffer or bad bounds for non-empty region; report failure.
1216 : }
1217 0 : if (count == 0) {
1218 0 : tmp.fRunHead = SkRegion_gRectRunHeadPtr;
1219 : } else {
1220 : int32_t ySpanCount, intervalCount;
1221 0 : if (!buffer.readS32(&ySpanCount) ||
1222 0 : !buffer.readS32(&intervalCount) ||
1223 0 : buffer.available() < count * sizeof(int32_t)) {
1224 0 : return 0;
1225 : }
1226 0 : if (!validate_run((const int32_t*)((const char*)storage + buffer.pos()), count,
1227 : tmp.fBounds, ySpanCount, intervalCount)) {
1228 0 : return 0; // invalid runs, don't even allocate
1229 : }
1230 0 : tmp.allocateRuns(count, ySpanCount, intervalCount);
1231 0 : SkASSERT(tmp.isComplex());
1232 0 : SkAssertResult(buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(int32_t)));
1233 : }
1234 : }
1235 0 : SkASSERT(tmp.isValid());
1236 0 : SkASSERT(buffer.isValid());
1237 0 : this->swap(tmp);
1238 0 : return buffer.pos();
1239 : }
1240 :
1241 : ///////////////////////////////////////////////////////////////////////////////
1242 :
1243 0 : const SkRegion& SkRegion::GetEmptyRegion() {
1244 0 : static SkRegion gEmpty;
1245 0 : return gEmpty;
1246 : }
1247 :
1248 : ///////////////////////////////////////////////////////////////////////////////
1249 :
1250 4980 : bool SkRegion::isValid() const {
1251 4980 : if (this->isEmpty()) {
1252 1452 : return fBounds == SkIRect{0, 0, 0, 0};
1253 : }
1254 3528 : if (fBounds.isEmpty()) {
1255 0 : return false;
1256 : }
1257 3528 : if (this->isRect()) {
1258 3070 : return true;
1259 : }
1260 916 : return fRunHead && fRunHead->fRefCnt > 0 &&
1261 916 : validate_run(fRunHead->readonly_runs(), fRunHead->fRunCount, fBounds,
1262 1374 : fRunHead->getYSpanCount(), fRunHead->getIntervalCount());
1263 : }
1264 :
1265 : #ifdef SK_DEBUG
1266 4980 : void SkRegion::validate() const { SkASSERT(this->isValid()); }
1267 :
1268 0 : void SkRegion::dump() const {
1269 0 : if (this->isEmpty()) {
1270 0 : SkDebugf(" rgn: empty\n");
1271 : } else {
1272 0 : SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
1273 0 : if (this->isComplex()) {
1274 0 : const RunType* runs = fRunHead->readonly_runs();
1275 0 : for (int i = 0; i < fRunHead->fRunCount; i++)
1276 0 : SkDebugf(" %d", runs[i]);
1277 : }
1278 0 : SkDebugf("\n");
1279 : }
1280 0 : }
1281 :
1282 : #endif
1283 :
1284 : ///////////////////////////////////////////////////////////////////////////////
1285 :
1286 39 : SkRegion::Iterator::Iterator(const SkRegion& rgn) {
1287 39 : this->reset(rgn);
1288 39 : }
1289 :
1290 0 : bool SkRegion::Iterator::rewind() {
1291 0 : if (fRgn) {
1292 0 : this->reset(*fRgn);
1293 0 : return true;
1294 : }
1295 0 : return false;
1296 : }
1297 :
1298 39 : void SkRegion::Iterator::reset(const SkRegion& rgn) {
1299 39 : fRgn = &rgn;
1300 39 : if (rgn.isEmpty()) {
1301 0 : fDone = true;
1302 : } else {
1303 39 : fDone = false;
1304 39 : if (rgn.isRect()) {
1305 21 : fRect = rgn.fBounds;
1306 21 : fRuns = nullptr;
1307 : } else {
1308 18 : fRuns = rgn.fRunHead->readonly_runs();
1309 18 : fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]);
1310 18 : fRuns += 5;
1311 : // Now fRuns points to the 2nd interval (or x-sentinel)
1312 : }
1313 : }
1314 39 : }
1315 :
1316 86 : void SkRegion::Iterator::next() {
1317 86 : if (fDone) {
1318 0 : return;
1319 : }
1320 :
1321 86 : if (fRuns == nullptr) { // rect case
1322 21 : fDone = true;
1323 21 : return;
1324 : }
1325 :
1326 65 : const RunType* runs = fRuns;
1327 :
1328 65 : if (runs[0] < kRunTypeSentinel) { // valid X value
1329 13 : fRect.fLeft = runs[0];
1330 13 : fRect.fRight = runs[1];
1331 13 : runs += 2;
1332 : } else { // we're at the end of a line
1333 52 : runs += 1;
1334 52 : if (runs[0] < kRunTypeSentinel) { // valid Y value
1335 37 : int intervals = runs[1];
1336 37 : if (0 == intervals) { // empty line
1337 12 : fRect.fTop = runs[0];
1338 12 : runs += 3;
1339 : } else {
1340 25 : fRect.fTop = fRect.fBottom;
1341 : }
1342 :
1343 37 : fRect.fBottom = runs[0];
1344 37 : assert_sentinel(runs[2], false);
1345 37 : assert_sentinel(runs[3], false);
1346 37 : fRect.fLeft = runs[2];
1347 37 : fRect.fRight = runs[3];
1348 37 : runs += 4;
1349 : } else { // end of rgn
1350 15 : fDone = true;
1351 : }
1352 : }
1353 65 : fRuns = runs;
1354 : }
1355 :
1356 22 : SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
1357 22 : : fIter(rgn), fClip(clip), fDone(true) {
1358 22 : const SkIRect& r = fIter.rect();
1359 :
1360 42 : while (!fIter.done()) {
1361 32 : if (r.fTop >= clip.fBottom) {
1362 0 : break;
1363 : }
1364 32 : if (fRect.intersect(clip, r)) {
1365 22 : fDone = false;
1366 22 : break;
1367 : }
1368 10 : fIter.next();
1369 : }
1370 22 : }
1371 :
1372 55 : void SkRegion::Cliperator::next() {
1373 55 : if (fDone) {
1374 0 : return;
1375 : }
1376 :
1377 55 : const SkIRect& r = fIter.rect();
1378 :
1379 55 : fDone = true;
1380 55 : fIter.next();
1381 63 : while (!fIter.done()) {
1382 40 : if (r.fTop >= fClip.fBottom) {
1383 3 : break;
1384 : }
1385 37 : if (fRect.intersect(fClip, r)) {
1386 33 : fDone = false;
1387 33 : break;
1388 : }
1389 4 : fIter.next();
1390 : }
1391 : }
1392 :
1393 : ///////////////////////////////////////////////////////////////////////////////
1394 :
1395 0 : SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
1396 0 : int right) {
1397 0 : SkDEBUGCODE(rgn.validate();)
1398 :
1399 0 : const SkIRect& r = rgn.getBounds();
1400 :
1401 0 : fDone = true;
1402 0 : if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom &&
1403 0 : right > r.fLeft && left < r.fRight) {
1404 0 : if (rgn.isRect()) {
1405 0 : if (left < r.fLeft) {
1406 0 : left = r.fLeft;
1407 : }
1408 0 : if (right > r.fRight) {
1409 0 : right = r.fRight;
1410 : }
1411 0 : fLeft = left;
1412 0 : fRight = right;
1413 0 : fRuns = nullptr; // means we're a rect, not a rgn
1414 0 : fDone = false;
1415 : } else {
1416 0 : const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y);
1417 0 : runs += 2; // skip Bottom and IntervalCount
1418 : for (;;) {
1419 : // runs[0..1] is to the right of the span, so we're done
1420 0 : if (runs[0] >= right) {
1421 0 : break;
1422 : }
1423 : // runs[0..1] is to the left of the span, so continue
1424 0 : if (runs[1] <= left) {
1425 0 : runs += 2;
1426 0 : continue;
1427 : }
1428 : // runs[0..1] intersects the span
1429 0 : fRuns = runs;
1430 0 : fLeft = left;
1431 0 : fRight = right;
1432 0 : fDone = false;
1433 0 : break;
1434 : }
1435 : }
1436 : }
1437 0 : }
1438 :
1439 0 : bool SkRegion::Spanerator::next(int* left, int* right) {
1440 0 : if (fDone) {
1441 0 : return false;
1442 : }
1443 :
1444 0 : if (fRuns == nullptr) { // we're a rect
1445 0 : fDone = true; // ok, now we're done
1446 0 : if (left) {
1447 0 : *left = fLeft;
1448 : }
1449 0 : if (right) {
1450 0 : *right = fRight;
1451 : }
1452 0 : return true; // this interval is legal
1453 : }
1454 :
1455 0 : const SkRegion::RunType* runs = fRuns;
1456 :
1457 0 : if (runs[0] >= fRight) {
1458 0 : fDone = true;
1459 0 : return false;
1460 : }
1461 :
1462 0 : SkASSERT(runs[1] > fLeft);
1463 :
1464 0 : if (left) {
1465 0 : *left = SkMax32(fLeft, runs[0]);
1466 : }
1467 0 : if (right) {
1468 0 : *right = SkMin32(fRight, runs[1]);
1469 : }
1470 0 : fRuns = runs + 2;
1471 0 : return true;
1472 : }
1473 :
1474 : ///////////////////////////////////////////////////////////////////////////////
1475 :
1476 : #ifdef SK_DEBUG
1477 :
1478 0 : bool SkRegion::debugSetRuns(const RunType runs[], int count) {
1479 : // we need to make a copy, since the real method may modify the array, and
1480 : // so it cannot be const.
1481 :
1482 0 : SkAutoTArray<RunType> storage(count);
1483 0 : memcpy(storage.get(), runs, count * sizeof(RunType));
1484 0 : return this->setRuns(storage.get(), count);
1485 : }
1486 :
1487 : #endif
|
