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 #ifndef SkRegionPriv_DEFINED
9 #define SkRegionPriv_DEFINED
10
11 #include "include/core/SkRegion.h"
12 #include "include/private/base/SkMath.h"
13 #include "include/private/base/SkMalloc.h"
14 #include "include/private/base/SkTo.h"
15
16 #include <atomic>
17 #include <functional>
18
19 class SkRegionPriv {
20 public:
21 inline static constexpr int kRunTypeSentinel = 0x7FFFFFFF;
22 typedef SkRegion::RunType RunType;
23 typedef SkRegion::RunHead RunHead;
24
25 // Call the function with each span, in Y -> X ascending order.
26 // We pass a rect, but we will still ensure the span Y->X ordering, so often the height
27 // of the rect may be 1. It should never be empty.
28 static void VisitSpans(const SkRegion& rgn, const std::function<void(const SkIRect&)>&);
29
30 #ifdef SK_DEBUG
31 static void Validate(const SkRegion& rgn);
32 #endif
33 };
34
35 static constexpr int SkRegion_kRunTypeSentinel = 0x7FFFFFFF;
36
SkRegionValueIsSentinel(int32_t value)37 inline bool SkRegionValueIsSentinel(int32_t value) {
38 return value == (int32_t)SkRegion_kRunTypeSentinel;
39 }
40
41 #define assert_sentinel(value, isSentinel) \
42 SkASSERT(SkRegionValueIsSentinel(value) == isSentinel)
43
44 #ifdef SK_DEBUG
45 // Given the first interval (just past the interval-count), compute the
46 // interval count, by search for the x-sentinel
47 //
compute_intervalcount(const SkRegionPriv::RunType runs[])48 static int compute_intervalcount(const SkRegionPriv::RunType runs[]) {
49 const SkRegionPriv::RunType* curr = runs;
50 while (*curr < SkRegion_kRunTypeSentinel) {
51 SkASSERT(curr[0] < curr[1]);
52 SkASSERT(curr[1] < SkRegion_kRunTypeSentinel);
53 curr += 2;
54 }
55 return SkToInt((curr - runs) >> 1);
56 }
57 #endif
58
59 struct SkRegion::RunHead {
60 private:
61
62 public:
63 std::atomic<int32_t> fRefCnt;
64 int32_t fRunCount;
65
66 /**
67 * Number of spans with different Y values. This does not count the initial
68 * Top value, nor does it count the final Y-Sentinel value. In the logical
69 * case of a rectangle, this would return 1, and an empty region would
70 * return 0.
71 */
getYSpanCountRunHead72 int getYSpanCount() const {
73 return fYSpanCount;
74 }
75
76 /**
77 * Number of intervals in the entire region. This equals the number of
78 * rects that would be returned by the Iterator. In the logical case of
79 * a rect, this would return 1, and an empty region would return 0.
80 */
getIntervalCountRunHead81 int getIntervalCount() const {
82 return fIntervalCount;
83 }
84
AllocRunHead85 static RunHead* Alloc(int count) {
86 if (count < SkRegion::kRectRegionRuns) {
87 return nullptr;
88 }
89
90 const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead);
91 if (count < 0 || !SkTFitsIn<int32_t>(size)) { SK_ABORT("Invalid Size"); }
92
93 RunHead* head = (RunHead*)sk_malloc_throw(size);
94 head->fRefCnt = 1;
95 head->fRunCount = count;
96 // these must be filled in later, otherwise we will be invalid
97 head->fYSpanCount = 0;
98 head->fIntervalCount = 0;
99 return head;
100 }
101
AllocRunHead102 static RunHead* Alloc(int count, int yspancount, int intervalCount) {
103 if (yspancount <= 0 || intervalCount <= 1) {
104 return nullptr;
105 }
106
107 RunHead* head = Alloc(count);
108 if (!head) {
109 return nullptr;
110 }
111 head->fYSpanCount = yspancount;
112 head->fIntervalCount = intervalCount;
113 return head;
114 }
115
writable_runsRunHead116 SkRegion::RunType* writable_runs() {
117 SkASSERT(fRefCnt == 1);
118 return (SkRegion::RunType*)(this + 1);
119 }
120
readonly_runsRunHead121 const SkRegion::RunType* readonly_runs() const {
122 return (const SkRegion::RunType*)(this + 1);
123 }
124
ensureWritableRunHead125 RunHead* ensureWritable() {
126 RunHead* writable = this;
127 if (fRefCnt > 1) {
128 // We need to alloc & copy the current region before decrease
129 // the refcount because it could be freed in the meantime.
130 writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
131 memcpy(writable->writable_runs(), this->readonly_runs(),
132 fRunCount * sizeof(RunType));
133
134 // fRefCount might have changed since we last checked.
135 // If we own the last reference at this point, we need to
136 // free the memory.
137 if (--fRefCnt == 0) {
138 sk_free(this);
139 }
140 }
141 return writable;
142 }
143
144 /**
145 * Given a scanline (including its Bottom value at runs[0]), return the next
146 * scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
147 */
SkipEntireScanlineRunHead148 static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
149 // we are not the Y Sentinel
150 SkASSERT(runs[0] < SkRegion_kRunTypeSentinel);
151
152 const int intervals = runs[1];
153 SkASSERT(runs[2 + intervals * 2] == SkRegion_kRunTypeSentinel);
154 #ifdef SK_DEBUG
155 {
156 int n = compute_intervalcount(&runs[2]);
157 SkASSERT(n == intervals);
158 }
159 #endif
160
161 // skip the entire line [B N [L R] S]
162 runs += 1 + 1 + intervals * 2 + 1;
163 return const_cast<SkRegion::RunType*>(runs);
164 }
165
166
167 /**
168 * Return the scanline that contains the Y value. This requires that the Y
169 * value is already known to be contained within the bounds of the region,
170 * and so this routine never returns nullptr.
171 *
172 * It returns the beginning of the scanline, starting with its Bottom value.
173 */
findScanlineRunHead174 SkRegion::RunType* findScanline(int y) const {
175 const RunType* runs = this->readonly_runs();
176
177 // if the top-check fails, we didn't do a quick check on the bounds
178 SkASSERT(y >= runs[0]);
179
180 runs += 1; // skip top-Y
181 for (;;) {
182 int bottom = runs[0];
183 // If we hit this, we've walked off the region, and our bounds check
184 // failed.
185 SkASSERT(bottom < SkRegion_kRunTypeSentinel);
186 if (y < bottom) {
187 break;
188 }
189 runs = SkipEntireScanline(runs);
190 }
191 return const_cast<SkRegion::RunType*>(runs);
192 }
193
194 // Copy src runs into us, computing interval counts and bounds along the way
computeRunBoundsRunHead195 void computeRunBounds(SkIRect* bounds) {
196 RunType* runs = this->writable_runs();
197 bounds->fTop = *runs++;
198
199 int bot;
200 int ySpanCount = 0;
201 int intervalCount = 0;
202 int left = SK_MaxS32;
203 int rite = SK_MinS32;
204
205 do {
206 bot = *runs++;
207 SkASSERT(bot < SkRegion_kRunTypeSentinel);
208 ySpanCount += 1;
209
210 const int intervals = *runs++;
211 SkASSERT(intervals >= 0);
212 SkASSERT(intervals < SkRegion_kRunTypeSentinel);
213
214 if (intervals > 0) {
215 #ifdef SK_DEBUG
216 {
217 int n = compute_intervalcount(runs);
218 SkASSERT(n == intervals);
219 }
220 #endif
221 RunType L = runs[0];
222 SkASSERT(L < SkRegion_kRunTypeSentinel);
223 if (left > L) {
224 left = L;
225 }
226
227 runs += intervals * 2;
228 RunType R = runs[-1];
229 SkASSERT(R < SkRegion_kRunTypeSentinel);
230 if (rite < R) {
231 rite = R;
232 }
233
234 intervalCount += intervals;
235 }
236 SkASSERT(SkRegion_kRunTypeSentinel == *runs);
237 runs += 1; // skip x-sentinel
238
239 // test Y-sentinel
240 } while (SkRegion_kRunTypeSentinel > *runs);
241
242 #ifdef SK_DEBUG
243 // +1 to skip the last Y-sentinel
244 int runCount = SkToInt(runs - this->writable_runs() + 1);
245 SkASSERT(runCount == fRunCount);
246 #endif
247
248 fYSpanCount = ySpanCount;
249 fIntervalCount = intervalCount;
250
251 bounds->fLeft = left;
252 bounds->fRight = rite;
253 bounds->fBottom = bot;
254 }
255
256 private:
257 int32_t fYSpanCount;
258 int32_t fIntervalCount;
259 };
260
261 #endif
262