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 #ifndef SkRegionPriv_DEFINED
11 #define SkRegionPriv_DEFINED
12
13 #include "SkRegion.h"
14 #include "SkAtomics.h"
15
16 #define assert_sentinel(value, isSentinel) \
17 SkASSERT(((value) == SkRegion::kRunTypeSentinel) == isSentinel)
18
19 //SkDEBUGCODE(extern int32_t gRgnAllocCounter;)
20
21 #ifdef SK_DEBUG
22 // Given the first interval (just past the interval-count), compute the
23 // interval count, by search for the x-sentinel
24 //
compute_intervalcount(const SkRegion::RunType runs[])25 static int compute_intervalcount(const SkRegion::RunType runs[]) {
26 const SkRegion::RunType* curr = runs;
27 while (*curr < SkRegion::kRunTypeSentinel) {
28 SkASSERT(curr[0] < curr[1]);
29 SkASSERT(curr[1] < SkRegion::kRunTypeSentinel);
30 curr += 2;
31 }
32 return SkToInt((curr - runs) >> 1);
33 }
34 #endif
35
36 struct SkRegion::RunHead {
37 private:
38
39 public:
40 int32_t fRefCnt;
41 int32_t fRunCount;
42
43 /**
44 * Number of spans with different Y values. This does not count the initial
45 * Top value, nor does it count the final Y-Sentinel value. In the logical
46 * case of a rectangle, this would return 1, and an empty region would
47 * return 0.
48 */
getYSpanCountRunHead49 int getYSpanCount() const {
50 return fYSpanCount;
51 }
52
53 /**
54 * Number of intervals in the entire region. This equals the number of
55 * rects that would be returned by the Iterator. In the logical case of
56 * a rect, this would return 1, and an empty region would return 0.
57 */
getIntervalCountRunHead58 int getIntervalCount() const {
59 return fIntervalCount;
60 }
61
AllocRunHead62 static RunHead* Alloc(int count) {
63 //SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
64 //SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
65
66 SkASSERT(count >= SkRegion::kRectRegionRuns);
67
68 const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead);
69 if (count < 0 || !sk_64_isS32(size)) { SK_ABORT("Invalid Size"); }
70
71 RunHead* head = (RunHead*)sk_malloc_throw(size);
72 head->fRefCnt = 1;
73 head->fRunCount = count;
74 // these must be filled in later, otherwise we will be invalid
75 head->fYSpanCount = 0;
76 head->fIntervalCount = 0;
77 return head;
78 }
79
AllocRunHead80 static RunHead* Alloc(int count, int yspancount, int intervalCount) {
81 SkASSERT(yspancount > 0);
82 SkASSERT(intervalCount > 1);
83
84 RunHead* head = Alloc(count);
85 head->fYSpanCount = yspancount;
86 head->fIntervalCount = intervalCount;
87 return head;
88 }
89
writable_runsRunHead90 SkRegion::RunType* writable_runs() {
91 SkASSERT(fRefCnt == 1);
92 return (SkRegion::RunType*)(this + 1);
93 }
94
readonly_runsRunHead95 const SkRegion::RunType* readonly_runs() const {
96 return (const SkRegion::RunType*)(this + 1);
97 }
98
ensureWritableRunHead99 RunHead* ensureWritable() {
100 RunHead* writable = this;
101 if (fRefCnt > 1) {
102 // We need to alloc & copy the current region before we call
103 // sk_atomic_dec because it could be freed in the meantime,
104 // otherwise.
105 writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
106 memcpy(writable->writable_runs(), this->readonly_runs(),
107 fRunCount * sizeof(RunType));
108
109 // fRefCount might have changed since we last checked.
110 // If we own the last reference at this point, we need to
111 // free the memory.
112 if (sk_atomic_dec(&fRefCnt) == 1) {
113 sk_free(this);
114 }
115 }
116 return writable;
117 }
118
119 /**
120 * Given a scanline (including its Bottom value at runs[0]), return the next
121 * scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
122 */
SkipEntireScanlineRunHead123 static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
124 // we are not the Y Sentinel
125 SkASSERT(runs[0] < SkRegion::kRunTypeSentinel);
126
127 const int intervals = runs[1];
128 SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel);
129 #ifdef SK_DEBUG
130 {
131 int n = compute_intervalcount(&runs[2]);
132 SkASSERT(n == intervals);
133 }
134 #endif
135
136 // skip the entire line [B N [L R] S]
137 runs += 1 + 1 + intervals * 2 + 1;
138 return const_cast<SkRegion::RunType*>(runs);
139 }
140
141
142 /**
143 * Return the scanline that contains the Y value. This requires that the Y
144 * value is already known to be contained within the bounds of the region,
145 * and so this routine never returns nullptr.
146 *
147 * It returns the beginning of the scanline, starting with its Bottom value.
148 */
findScanlineRunHead149 SkRegion::RunType* findScanline(int y) const {
150 const RunType* runs = this->readonly_runs();
151
152 // if the top-check fails, we didn't do a quick check on the bounds
153 SkASSERT(y >= runs[0]);
154
155 runs += 1; // skip top-Y
156 for (;;) {
157 int bottom = runs[0];
158 // If we hit this, we've walked off the region, and our bounds check
159 // failed.
160 SkASSERT(bottom < SkRegion::kRunTypeSentinel);
161 if (y < bottom) {
162 break;
163 }
164 runs = SkipEntireScanline(runs);
165 }
166 return const_cast<SkRegion::RunType*>(runs);
167 }
168
169 // Copy src runs into us, computing interval counts and bounds along the way
computeRunBoundsRunHead170 void computeRunBounds(SkIRect* bounds) {
171 RunType* runs = this->writable_runs();
172 bounds->fTop = *runs++;
173
174 int bot;
175 int ySpanCount = 0;
176 int intervalCount = 0;
177 int left = SK_MaxS32;
178 int rite = SK_MinS32;
179
180 do {
181 bot = *runs++;
182 SkASSERT(bot < SkRegion::kRunTypeSentinel);
183 ySpanCount += 1;
184
185 const int intervals = *runs++;
186 SkASSERT(intervals >= 0);
187 SkASSERT(intervals < SkRegion::kRunTypeSentinel);
188
189 if (intervals > 0) {
190 #ifdef SK_DEBUG
191 {
192 int n = compute_intervalcount(runs);
193 SkASSERT(n == intervals);
194 }
195 #endif
196 RunType L = runs[0];
197 SkASSERT(L < SkRegion::kRunTypeSentinel);
198 if (left > L) {
199 left = L;
200 }
201
202 runs += intervals * 2;
203 RunType R = runs[-1];
204 SkASSERT(R < SkRegion::kRunTypeSentinel);
205 if (rite < R) {
206 rite = R;
207 }
208
209 intervalCount += intervals;
210 }
211 SkASSERT(SkRegion::kRunTypeSentinel == *runs);
212 runs += 1; // skip x-sentinel
213
214 // test Y-sentinel
215 } while (SkRegion::kRunTypeSentinel > *runs);
216
217 #ifdef SK_DEBUG
218 // +1 to skip the last Y-sentinel
219 int runCount = SkToInt(runs - this->writable_runs() + 1);
220 SkASSERT(runCount == fRunCount);
221 #endif
222
223 fYSpanCount = ySpanCount;
224 fIntervalCount = intervalCount;
225
226 bounds->fLeft = left;
227 bounds->fRight = rite;
228 bounds->fBottom = bot;
229 }
230
231 private:
232 int32_t fYSpanCount;
233 int32_t fIntervalCount;
234 };
235
236 #endif
237