epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 8 | #ifndef SkRegionPriv_DEFINED |
| 9 | #define SkRegionPriv_DEFINED |
| 10 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 11 | #include "include/core/SkRegion.h" |
| 12 | #include "include/private/SkMalloc.h" |
| 13 | #include "include/private/SkTo.h" |
Mike Klein | de2244c | 2018-12-04 11:16:08 -0500 | [diff] [blame] | 14 | #include <atomic> |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 15 | #include <functional> |
| 16 | |
| 17 | class SkRegionPriv { |
| 18 | public: |
| 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 | |
| 33 | static constexpr int SkRegion_kRunTypeSentinel = 0x7FFFFFFF; |
| 34 | |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 35 | inline bool SkRegionValueIsSentinel(int32_t value) { |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 36 | return value == (int32_t)SkRegion_kRunTypeSentinel; |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 37 | } |
| 38 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 39 | #define assert_sentinel(value, isSentinel) \ |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 40 | SkASSERT(SkRegionValueIsSentinel(value) == isSentinel) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 41 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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 | // |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 46 | static int compute_intervalcount(const SkRegionPriv::RunType runs[]) { |
| 47 | const SkRegionPriv::RunType* curr = runs; |
| 48 | while (*curr < SkRegion_kRunTypeSentinel) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 49 | SkASSERT(curr[0] < curr[1]); |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 50 | SkASSERT(curr[1] < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 51 | curr += 2; |
| 52 | } |
commit-bot@chromium.org | f117781 | 2014-04-23 19:19:44 +0000 | [diff] [blame] | 53 | return SkToInt((curr - runs) >> 1); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 54 | } |
| 55 | #endif |
| 56 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 57 | struct SkRegion::RunHead { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 58 | private: |
| 59 | |
| 60 | public: |
Mike Reed | f80989f | 2018-04-27 12:06:44 -0400 | [diff] [blame] | 61 | std::atomic<int32_t> fRefCnt; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 62 | int32_t fRunCount; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 63 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 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 | |
reed@google.com | a95ea2c | 2012-04-30 16:35:25 +0000 | [diff] [blame] | 83 | static RunHead* Alloc(int count) { |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 84 | if (count < SkRegion::kRectRegionRuns) { |
| 85 | return nullptr; |
| 86 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 87 | |
djsollen | 38fd5fe | 2015-05-18 13:05:11 -0700 | [diff] [blame] | 88 | const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead); |
Herb Derby | c402b77 | 2017-09-20 11:56:00 -0400 | [diff] [blame] | 89 | if (count < 0 || !SkTFitsIn<int32_t>(size)) { SK_ABORT("Invalid Size"); } |
djsollen | 38fd5fe | 2015-05-18 13:05:11 -0700 | [diff] [blame] | 90 | |
| 91 | RunHead* head = (RunHead*)sk_malloc_throw(size); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 92 | head->fRefCnt = 1; |
| 93 | head->fRunCount = count; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 94 | // these must be filled in later, otherwise we will be invalid |
| 95 | head->fYSpanCount = 0; |
| 96 | head->fIntervalCount = 0; |
| 97 | return head; |
| 98 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 99 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 100 | static RunHead* Alloc(int count, int yspancount, int intervalCount) { |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 101 | if (yspancount <= 0 || intervalCount <= 1) { |
| 102 | return nullptr; |
| 103 | } |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 104 | |
| 105 | RunHead* head = Alloc(count); |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 106 | if (!head) { |
| 107 | return nullptr; |
| 108 | } |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 109 | head->fYSpanCount = yspancount; |
| 110 | head->fIntervalCount = intervalCount; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 111 | return head; |
| 112 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 113 | |
reed@google.com | a95ea2c | 2012-04-30 16:35:25 +0000 | [diff] [blame] | 114 | SkRegion::RunType* writable_runs() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 115 | SkASSERT(fRefCnt == 1); |
| 116 | return (SkRegion::RunType*)(this + 1); |
| 117 | } |
reed@google.com | a95ea2c | 2012-04-30 16:35:25 +0000 | [diff] [blame] | 118 | |
| 119 | const SkRegion::RunType* readonly_runs() const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 120 | return (const SkRegion::RunType*)(this + 1); |
| 121 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 122 | |
reed@google.com | a95ea2c | 2012-04-30 16:35:25 +0000 | [diff] [blame] | 123 | RunHead* ensureWritable() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 124 | RunHead* writable = this; |
reed@google.com | a95ea2c | 2012-04-30 16:35:25 +0000 | [diff] [blame] | 125 | if (fRefCnt > 1) { |
Mike Klein | de2244c | 2018-12-04 11:16:08 -0500 | [diff] [blame] | 126 | // We need to alloc & copy the current region before decrease |
| 127 | // the refcount because it could be freed in the meantime. |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 128 | writable = Alloc(fRunCount, fYSpanCount, fIntervalCount); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 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. |
Mike Reed | f80989f | 2018-04-27 12:06:44 -0400 | [diff] [blame] | 135 | if (--fRefCnt == 0) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 136 | sk_free(this); |
| 137 | } |
| 138 | } |
| 139 | return writable; |
| 140 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 141 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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 |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 148 | SkASSERT(runs[0] < SkRegion_kRunTypeSentinel); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 149 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 150 | const int intervals = runs[1]; |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 151 | SkASSERT(runs[2 + intervals * 2] == SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 163 | |
| 164 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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, |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 168 | * and so this routine never returns nullptr. |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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]); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 177 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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. |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 183 | SkASSERT(bottom < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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++; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 196 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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++; |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 205 | SkASSERT(bot < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 206 | ySpanCount += 1; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 207 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 208 | const int intervals = *runs++; |
| 209 | SkASSERT(intervals >= 0); |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 210 | SkASSERT(intervals < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 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]; |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 220 | SkASSERT(L < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 221 | if (left > L) { |
| 222 | left = L; |
| 223 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 224 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 225 | runs += intervals * 2; |
| 226 | RunType R = runs[-1]; |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 227 | SkASSERT(R < SkRegion_kRunTypeSentinel); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 228 | if (rite < R) { |
| 229 | rite = R; |
| 230 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 231 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 232 | intervalCount += intervals; |
| 233 | } |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 234 | SkASSERT(SkRegion_kRunTypeSentinel == *runs); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 235 | runs += 1; // skip x-sentinel |
| 236 | |
| 237 | // test Y-sentinel |
Cary Clark | 6943689 | 2018-07-28 10:14:27 -0400 | [diff] [blame] | 238 | } while (SkRegion_kRunTypeSentinel > *runs); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 239 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 240 | #ifdef SK_DEBUG |
| 241 | // +1 to skip the last Y-sentinel |
commit-bot@chromium.org | f117781 | 2014-04-23 19:19:44 +0000 | [diff] [blame] | 242 | int runCount = SkToInt(runs - this->writable_runs() + 1); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 243 | SkASSERT(runCount == fRunCount); |
| 244 | #endif |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 245 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 246 | fYSpanCount = ySpanCount; |
| 247 | fIntervalCount = intervalCount; |
| 248 | |
| 249 | bounds->fLeft = left; |
| 250 | bounds->fRight = rite; |
| 251 | bounds->fBottom = bot; |
| 252 | } |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 253 | |
| 254 | private: |
| 255 | int32_t fYSpanCount; |
| 256 | int32_t fIntervalCount; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 257 | }; |
| 258 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 259 | #endif |