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