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