Line data Source code
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 :
17 955 : inline bool SkRegionValueIsSentinel(int32_t value) {
18 955 : 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 : //
30 210 : static int compute_intervalcount(const SkRegion::RunType runs[]) {
31 210 : const SkRegion::RunType* curr = runs;
32 758 : while (*curr < SkRegion::kRunTypeSentinel) {
33 274 : SkASSERT(curr[0] < curr[1]);
34 274 : SkASSERT(curr[1] < SkRegion::kRunTypeSentinel);
35 274 : curr += 2;
36 : }
37 210 : 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 : */
54 458 : int getYSpanCount() const {
55 458 : 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 : */
63 516 : int getIntervalCount() const {
64 516 : return fIntervalCount;
65 : }
66 :
67 73 : static RunHead* Alloc(int count) {
68 : //SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
69 : //SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
70 :
71 73 : if (count < SkRegion::kRectRegionRuns) {
72 0 : return nullptr;
73 : }
74 :
75 73 : const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead);
76 73 : if (count < 0 || !sk_64_isS32(size)) { SK_ABORT("Invalid Size"); }
77 :
78 73 : RunHead* head = (RunHead*)sk_malloc_throw(size);
79 73 : head->fRefCnt = 1;
80 73 : head->fRunCount = count;
81 : // these must be filled in later, otherwise we will be invalid
82 73 : head->fYSpanCount = 0;
83 73 : head->fIntervalCount = 0;
84 73 : return head;
85 : }
86 :
87 0 : static RunHead* Alloc(int count, int yspancount, int intervalCount) {
88 0 : if (yspancount <= 0 || intervalCount <= 1) {
89 0 : return nullptr;
90 : }
91 :
92 0 : RunHead* head = Alloc(count);
93 0 : if (!head) {
94 0 : return nullptr;
95 : }
96 0 : head->fYSpanCount = yspancount;
97 0 : head->fIntervalCount = intervalCount;
98 0 : return head;
99 : }
100 :
101 219 : SkRegion::RunType* writable_runs() {
102 219 : SkASSERT(fRefCnt == 1);
103 219 : return (SkRegion::RunType*)(this + 1);
104 : }
105 :
106 534 : const SkRegion::RunType* readonly_runs() const {
107 534 : return (const SkRegion::RunType*)(this + 1);
108 : }
109 :
110 73 : RunHead* ensureWritable() {
111 73 : RunHead* writable = this;
112 73 : 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 0 : writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
117 0 : memcpy(writable->writable_runs(), this->readonly_runs(),
118 0 : 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 0 : if (sk_atomic_dec(&fRefCnt) == 1) {
124 0 : sk_free(this);
125 : }
126 : }
127 73 : 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 : */
134 0 : static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
135 : // we are not the Y Sentinel
136 0 : SkASSERT(runs[0] < SkRegion::kRunTypeSentinel);
137 :
138 0 : const int intervals = runs[1];
139 0 : SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel);
140 : #ifdef SK_DEBUG
141 : {
142 0 : int n = compute_intervalcount(&runs[2]);
143 0 : SkASSERT(n == intervals);
144 : }
145 : #endif
146 :
147 : // skip the entire line [B N [L R] S]
148 0 : runs += 1 + 1 + intervals * 2 + 1;
149 0 : 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 : */
160 0 : SkRegion::RunType* findScanline(int y) const {
161 0 : const RunType* runs = this->readonly_runs();
162 :
163 : // if the top-check fails, we didn't do a quick check on the bounds
164 0 : SkASSERT(y >= runs[0]);
165 :
166 0 : runs += 1; // skip top-Y
167 : for (;;) {
168 0 : int bottom = runs[0];
169 : // If we hit this, we've walked off the region, and our bounds check
170 : // failed.
171 0 : SkASSERT(bottom < SkRegion::kRunTypeSentinel);
172 0 : if (y < bottom) {
173 0 : break;
174 : }
175 0 : runs = SkipEntireScanline(runs);
176 0 : }
177 0 : return const_cast<SkRegion::RunType*>(runs);
178 : }
179 :
180 : // Copy src runs into us, computing interval counts and bounds along the way
181 73 : void computeRunBounds(SkIRect* bounds) {
182 73 : RunType* runs = this->writable_runs();
183 73 : bounds->fTop = *runs++;
184 :
185 : int bot;
186 73 : int ySpanCount = 0;
187 73 : int intervalCount = 0;
188 73 : int left = SK_MaxS32;
189 73 : int rite = SK_MinS32;
190 :
191 179 : do {
192 252 : bot = *runs++;
193 252 : SkASSERT(bot < SkRegion::kRunTypeSentinel);
194 252 : ySpanCount += 1;
195 :
196 252 : const int intervals = *runs++;
197 252 : SkASSERT(intervals >= 0);
198 252 : SkASSERT(intervals < SkRegion::kRunTypeSentinel);
199 :
200 252 : if (intervals > 0) {
201 : #ifdef SK_DEBUG
202 : {
203 210 : int n = compute_intervalcount(runs);
204 210 : SkASSERT(n == intervals);
205 : }
206 : #endif
207 210 : RunType L = runs[0];
208 210 : SkASSERT(L < SkRegion::kRunTypeSentinel);
209 210 : if (left > L) {
210 118 : left = L;
211 : }
212 :
213 210 : runs += intervals * 2;
214 210 : RunType R = runs[-1];
215 210 : SkASSERT(R < SkRegion::kRunTypeSentinel);
216 210 : if (rite < R) {
217 126 : rite = R;
218 : }
219 :
220 210 : intervalCount += intervals;
221 : }
222 252 : SkASSERT(SkRegion::kRunTypeSentinel == *runs);
223 252 : runs += 1; // skip x-sentinel
224 :
225 : // test Y-sentinel
226 252 : } while (SkRegion::kRunTypeSentinel > *runs);
227 :
228 : #ifdef SK_DEBUG
229 : // +1 to skip the last Y-sentinel
230 73 : int runCount = SkToInt(runs - this->writable_runs() + 1);
231 73 : SkASSERT(runCount == fRunCount);
232 : #endif
233 :
234 73 : fYSpanCount = ySpanCount;
235 73 : fIntervalCount = intervalCount;
236 :
237 73 : bounds->fLeft = left;
238 73 : bounds->fRight = rite;
239 73 : bounds->fBottom = bot;
240 73 : }
241 :
242 : private:
243 : int32_t fYSpanCount;
244 : int32_t fIntervalCount;
245 : };
246 :
247 : #endif
|
