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