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