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