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