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 | |
herb | b906daf | 2015-09-29 09:37:59 -0700 | [diff] [blame] | 9 | #include "SkAtomics.h" |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 10 | #include "SkRegionPriv.h" |
| 11 | #include "SkTemplates.h" |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 12 | #include "SkUtils.h" |
| 13 | |
| 14 | /* Region Layout |
| 15 | * |
| 16 | * TOP |
| 17 | * |
| 18 | * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ] |
| 19 | * ... |
| 20 | * |
| 21 | * Y-Sentinel |
| 22 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 23 | |
| 24 | SkDEBUGCODE(int32_t gRgnAllocCounter;) |
| 25 | |
| 26 | ///////////////////////////////////////////////////////////////////////////////////////////////// |
| 27 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 28 | /* Pass in the beginning with the intervals. |
| 29 | * We back up 1 to read the interval-count. |
| 30 | * Return the beginning of the next scanline (i.e. the next Y-value) |
| 31 | */ |
| 32 | static SkRegion::RunType* skip_intervals(const SkRegion::RunType runs[]) { |
| 33 | int intervals = runs[-1]; |
| 34 | #ifdef SK_DEBUG |
| 35 | if (intervals > 0) { |
| 36 | SkASSERT(runs[0] < runs[1]); |
| 37 | SkASSERT(runs[1] < SkRegion::kRunTypeSentinel); |
| 38 | } else { |
| 39 | SkASSERT(0 == intervals); |
| 40 | SkASSERT(SkRegion::kRunTypeSentinel == runs[0]); |
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 | #endif |
| 43 | runs += intervals * 2 + 1; |
| 44 | return const_cast<SkRegion::RunType*>(runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 45 | } |
| 46 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 47 | bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count, |
| 48 | SkIRect* bounds) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 49 | assert_sentinel(runs[0], false); // top |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 50 | SkASSERT(count >= kRectRegionRuns); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 51 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 52 | if (count == kRectRegionRuns) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 53 | assert_sentinel(runs[1], false); // bottom |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 54 | SkASSERT(1 == runs[2]); |
| 55 | assert_sentinel(runs[3], false); // left |
| 56 | assert_sentinel(runs[4], false); // right |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 57 | assert_sentinel(runs[5], true); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 58 | assert_sentinel(runs[6], true); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 59 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 60 | SkASSERT(runs[0] < runs[1]); // valid height |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 61 | SkASSERT(runs[3] < runs[4]); // valid width |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 62 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 63 | bounds->set(runs[3], runs[0], runs[4], runs[1]); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 64 | return true; |
| 65 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 66 | return false; |
| 67 | } |
| 68 | |
| 69 | ////////////////////////////////////////////////////////////////////////// |
| 70 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 71 | SkRegion::SkRegion() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 72 | fBounds.set(0, 0, 0, 0); |
| 73 | fRunHead = SkRegion_gEmptyRunHeadPtr; |
| 74 | } |
| 75 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 76 | SkRegion::SkRegion(const SkRegion& src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 77 | fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) |
| 78 | this->setRegion(src); |
| 79 | } |
| 80 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 81 | SkRegion::SkRegion(const SkIRect& rect) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 82 | fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) |
| 83 | this->setRect(rect); |
| 84 | } |
| 85 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 86 | SkRegion::~SkRegion() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 87 | this->freeRuns(); |
| 88 | } |
| 89 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 90 | void SkRegion::freeRuns() { |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 91 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 92 | SkASSERT(fRunHead->fRefCnt >= 1); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 93 | if (sk_atomic_dec(&fRunHead->fRefCnt) == 1) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 94 | //SkASSERT(gRgnAllocCounter > 0); |
| 95 | //SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter)); |
| 96 | //SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter)); |
| 97 | sk_free(fRunHead); |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 102 | void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) { |
| 103 | fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount); |
| 104 | } |
| 105 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 106 | void SkRegion::allocateRuns(int count) { |
| 107 | fRunHead = RunHead::Alloc(count); |
| 108 | } |
| 109 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 110 | void SkRegion::allocateRuns(const RunHead& head) { |
| 111 | fRunHead = RunHead::Alloc(head.fRunCount, |
| 112 | head.getYSpanCount(), |
| 113 | head.getIntervalCount()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 114 | } |
| 115 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 116 | SkRegion& SkRegion::operator=(const SkRegion& src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 117 | (void)this->setRegion(src); |
| 118 | return *this; |
| 119 | } |
| 120 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 121 | void SkRegion::swap(SkRegion& other) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 122 | SkTSwap<SkIRect>(fBounds, other.fBounds); |
| 123 | SkTSwap<RunHead*>(fRunHead, other.fRunHead); |
| 124 | } |
| 125 | |
commit-bot@chromium.org | 5dd567c | 2013-07-17 21:39:28 +0000 | [diff] [blame] | 126 | int SkRegion::computeRegionComplexity() const { |
| 127 | if (this->isEmpty()) { |
| 128 | return 0; |
| 129 | } else if (this->isRect()) { |
| 130 | return 1; |
| 131 | } |
| 132 | return fRunHead->getIntervalCount(); |
| 133 | } |
skia.committer@gmail.com | f7d01ce | 2013-07-18 07:00:56 +0000 | [diff] [blame] | 134 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 135 | bool SkRegion::setEmpty() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 136 | this->freeRuns(); |
| 137 | fBounds.set(0, 0, 0, 0); |
| 138 | fRunHead = SkRegion_gEmptyRunHeadPtr; |
| 139 | return false; |
| 140 | } |
| 141 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 142 | bool SkRegion::setRect(int32_t left, int32_t top, |
| 143 | int32_t right, int32_t bottom) { |
| 144 | if (left >= right || top >= bottom) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 145 | return this->setEmpty(); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 146 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 147 | this->freeRuns(); |
| 148 | fBounds.set(left, top, right, bottom); |
| 149 | fRunHead = SkRegion_gRectRunHeadPtr; |
| 150 | return true; |
| 151 | } |
| 152 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 153 | bool SkRegion::setRect(const SkIRect& r) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 154 | return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom); |
| 155 | } |
| 156 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 157 | bool SkRegion::setRegion(const SkRegion& src) { |
| 158 | if (this != &src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 159 | this->freeRuns(); |
| 160 | |
| 161 | fBounds = src.fBounds; |
| 162 | fRunHead = src.fRunHead; |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 163 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 164 | sk_atomic_inc(&fRunHead->fRefCnt); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 165 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 166 | } |
| 167 | return fRunHead != SkRegion_gEmptyRunHeadPtr; |
| 168 | } |
| 169 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 170 | bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 171 | SkRegion tmp(rect); |
| 172 | |
| 173 | return this->op(tmp, rgn, op); |
| 174 | } |
| 175 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 176 | bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 177 | SkRegion tmp(rect); |
| 178 | |
| 179 | return this->op(rgn, tmp, op); |
| 180 | } |
| 181 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 182 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 183 | |
djsollen@google.com | 56c6977 | 2011-11-08 19:00:26 +0000 | [diff] [blame] | 184 | #ifdef SK_BUILD_FOR_ANDROID |
bungeman@google.com | 2c8e9d4 | 2013-10-11 19:23:56 +0000 | [diff] [blame] | 185 | #include <stdio.h> |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 186 | char* SkRegion::toString() { |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 187 | Iterator iter(*this); |
| 188 | int count = 0; |
| 189 | while (!iter.done()) { |
| 190 | count++; |
| 191 | iter.next(); |
| 192 | } |
| 193 | // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0' |
| 194 | const int max = (count*((11*4)+5))+11+1; |
mtklein | 002c2ce | 2015-08-26 05:43:22 -0700 | [diff] [blame] | 195 | char* result = (char*)sk_malloc_throw(max); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 196 | if (result == nullptr) { |
| 197 | return nullptr; |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 198 | } |
caryclark | 8f18643 | 2016-10-06 11:46:25 -0700 | [diff] [blame] | 199 | count = snprintf(result, max, "SkRegion("); |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 200 | iter.reset(*this); |
| 201 | while (!iter.done()) { |
| 202 | const SkIRect& r = iter.rect(); |
caryclark | 8f18643 | 2016-10-06 11:46:25 -0700 | [diff] [blame] | 203 | count += snprintf(result+count, max - count, |
| 204 | "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom); |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 205 | iter.next(); |
| 206 | } |
caryclark | 8f18643 | 2016-10-06 11:46:25 -0700 | [diff] [blame] | 207 | count += snprintf(result+count, max - count, ")"); |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 208 | return result; |
| 209 | } |
| 210 | #endif |
| 211 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 212 | /////////////////////////////////////////////////////////////////////////////// |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 213 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 214 | int SkRegion::count_runtype_values(int* itop, int* ibot) const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 215 | int maxT; |
| 216 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 217 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 218 | maxT = 2; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 219 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 220 | SkASSERT(this->isComplex()); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 221 | maxT = fRunHead->getIntervalCount() * 2; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 222 | } |
| 223 | *itop = fBounds.fTop; |
| 224 | *ibot = fBounds.fBottom; |
| 225 | return maxT; |
| 226 | } |
| 227 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 228 | static bool isRunCountEmpty(int count) { |
| 229 | return count <= 2; |
| 230 | } |
| 231 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 232 | bool SkRegion::setRuns(RunType runs[], int count) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 233 | SkDEBUGCODE(this->validate();) |
| 234 | SkASSERT(count > 0); |
| 235 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 236 | if (isRunCountEmpty(count)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 237 | // SkDEBUGF(("setRuns: empty\n")); |
| 238 | assert_sentinel(runs[count-1], true); |
| 239 | return this->setEmpty(); |
| 240 | } |
| 241 | |
| 242 | // trim off any empty spans from the top and bottom |
| 243 | // weird I should need this, perhaps op() could be smarter... |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 244 | if (count > kRectRegionRuns) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 245 | RunType* stop = runs + count; |
| 246 | assert_sentinel(runs[0], false); // top |
| 247 | assert_sentinel(runs[1], false); // bottom |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 248 | // runs[2] is uncomputed intervalCount |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 249 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 250 | if (runs[3] == SkRegion::kRunTypeSentinel) { // should be first left... |
| 251 | runs += 3; // skip empty initial span |
| 252 | runs[0] = runs[-2]; // set new top to prev bottom |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 253 | assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 254 | assert_sentinel(runs[2], false); // intervalcount |
| 255 | assert_sentinel(runs[3], false); // left |
| 256 | assert_sentinel(runs[4], false); // right |
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 | assert_sentinel(stop[-1], true); |
| 260 | assert_sentinel(stop[-2], true); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 261 | |
| 262 | // now check for a trailing empty span |
| 263 | if (stop[-5] == SkRegion::kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs |
| 264 | stop[-4] = SkRegion::kRunTypeSentinel; // kill empty last span |
| 265 | stop -= 3; |
| 266 | assert_sentinel(stop[-1], true); // last y-sentinel |
| 267 | assert_sentinel(stop[-2], true); // last x-sentinel |
| 268 | assert_sentinel(stop[-3], false); // last right |
| 269 | assert_sentinel(stop[-4], false); // last left |
| 270 | assert_sentinel(stop[-5], false); // last interval-count |
| 271 | assert_sentinel(stop[-6], false); // last bottom |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 272 | } |
| 273 | count = (int)(stop - runs); |
| 274 | } |
| 275 | |
| 276 | SkASSERT(count >= kRectRegionRuns); |
| 277 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 278 | if (SkRegion::RunsAreARect(runs, count, &fBounds)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 279 | return this->setRect(fBounds); |
| 280 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 281 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 282 | // if we get here, we need to become a complex region |
| 283 | |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 284 | if (!this->isComplex() || fRunHead->fRunCount != count) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 285 | this->freeRuns(); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 286 | this->allocateRuns(count); |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 287 | SkASSERT(this->isComplex()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 288 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 289 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 290 | // must call this before we can write directly into runs() |
| 291 | // in case we are sharing the buffer with another region (copy on write) |
| 292 | fRunHead = fRunHead->ensureWritable(); |
| 293 | memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType)); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 294 | fRunHead->computeRunBounds(&fBounds); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 295 | |
| 296 | SkDEBUGCODE(this->validate();) |
| 297 | |
| 298 | return true; |
| 299 | } |
| 300 | |
| 301 | void SkRegion::BuildRectRuns(const SkIRect& bounds, |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 302 | RunType runs[kRectRegionRuns]) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 303 | runs[0] = bounds.fTop; |
| 304 | runs[1] = bounds.fBottom; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 305 | runs[2] = 1; // 1 interval for this scanline |
| 306 | runs[3] = bounds.fLeft; |
| 307 | runs[4] = bounds.fRight; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 308 | runs[5] = kRunTypeSentinel; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 309 | runs[6] = kRunTypeSentinel; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 310 | } |
| 311 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 312 | bool SkRegion::contains(int32_t x, int32_t y) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 313 | SkDEBUGCODE(this->validate();) |
| 314 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 315 | if (!fBounds.contains(x, y)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 316 | return false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 317 | } |
| 318 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 319 | return true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 320 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 321 | SkASSERT(this->isComplex()); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 322 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 323 | const RunType* runs = fRunHead->findScanline(y); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 324 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 325 | // Skip the Bottom and IntervalCount |
| 326 | runs += 2; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 327 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 328 | // Just walk this scanline, checking each interval. The X-sentinel will |
| 329 | // appear as a left-inteval (runs[0]) and should abort the search. |
| 330 | // |
| 331 | // We could do a bsearch, using interval-count (runs[1]), but need to time |
| 332 | // when that would be worthwhile. |
| 333 | // |
| 334 | for (;;) { |
| 335 | if (x < runs[0]) { |
| 336 | break; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 337 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 338 | if (x < runs[1]) { |
| 339 | return true; |
| 340 | } |
| 341 | runs += 2; |
| 342 | } |
| 343 | return false; |
| 344 | } |
| 345 | |
mike@reedtribe.org | 796a175 | 2012-11-07 03:39:46 +0000 | [diff] [blame] | 346 | static SkRegion::RunType scanline_bottom(const SkRegion::RunType runs[]) { |
| 347 | return runs[0]; |
| 348 | } |
| 349 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 350 | static const SkRegion::RunType* scanline_next(const SkRegion::RunType runs[]) { |
| 351 | // skip [B N [L R]... S] |
| 352 | return runs + 2 + runs[1] * 2 + 1; |
| 353 | } |
| 354 | |
| 355 | static bool scanline_contains(const SkRegion::RunType runs[], |
| 356 | SkRegion::RunType L, SkRegion::RunType R) { |
| 357 | runs += 2; // skip Bottom and IntervalCount |
| 358 | for (;;) { |
| 359 | if (L < runs[0]) { |
| 360 | break; |
| 361 | } |
| 362 | if (R <= runs[1]) { |
| 363 | return true; |
| 364 | } |
| 365 | runs += 2; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 366 | } |
| 367 | return false; |
| 368 | } |
| 369 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 370 | bool SkRegion::contains(const SkIRect& r) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 371 | SkDEBUGCODE(this->validate();) |
| 372 | |
| 373 | if (!fBounds.contains(r)) { |
| 374 | return false; |
| 375 | } |
| 376 | if (this->isRect()) { |
| 377 | return true; |
| 378 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 379 | SkASSERT(this->isComplex()); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 380 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 381 | const RunType* scanline = fRunHead->findScanline(r.fTop); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 382 | for (;;) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 383 | if (!scanline_contains(scanline, r.fLeft, r.fRight)) { |
| 384 | return false; |
| 385 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 386 | if (r.fBottom <= scanline_bottom(scanline)) { |
| 387 | break; |
| 388 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 389 | scanline = scanline_next(scanline); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 390 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 391 | return true; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 392 | } |
| 393 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 394 | bool SkRegion::contains(const SkRegion& rgn) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 395 | SkDEBUGCODE(this->validate();) |
| 396 | SkDEBUGCODE(rgn.validate();) |
| 397 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 398 | if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 399 | return false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 400 | } |
| 401 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 402 | return true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 403 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 404 | if (rgn.isRect()) { |
| 405 | return this->contains(rgn.getBounds()); |
| 406 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 407 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 408 | /* |
| 409 | * A contains B is equivalent to |
| 410 | * B - A == 0 |
| 411 | */ |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 412 | return !Oper(rgn, *this, kDifference_Op, nullptr); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 413 | } |
| 414 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 415 | const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 416 | int* intervals) const { |
| 417 | SkASSERT(tmpStorage && intervals); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 418 | const RunType* runs = tmpStorage; |
| 419 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 420 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 421 | tmpStorage[0] = kRunTypeSentinel; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 422 | *intervals = 0; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 423 | } else if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 424 | BuildRectRuns(fBounds, tmpStorage); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 425 | *intervals = 1; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 426 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 427 | runs = fRunHead->readonly_runs(); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 428 | *intervals = fRunHead->getIntervalCount(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 429 | } |
| 430 | return runs; |
| 431 | } |
| 432 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 433 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 434 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 435 | static bool scanline_intersects(const SkRegion::RunType runs[], |
| 436 | SkRegion::RunType L, SkRegion::RunType R) { |
| 437 | runs += 2; // skip Bottom and IntervalCount |
| 438 | for (;;) { |
| 439 | if (R <= runs[0]) { |
| 440 | break; |
| 441 | } |
| 442 | if (L < runs[1]) { |
| 443 | return true; |
| 444 | } |
| 445 | runs += 2; |
| 446 | } |
| 447 | return false; |
| 448 | } |
| 449 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 450 | bool SkRegion::intersects(const SkIRect& r) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 451 | SkDEBUGCODE(this->validate();) |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 452 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 453 | if (this->isEmpty() || r.isEmpty()) { |
| 454 | return false; |
| 455 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 456 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 457 | SkIRect sect; |
| 458 | if (!sect.intersect(fBounds, r)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 459 | return false; |
| 460 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 461 | if (this->isRect()) { |
| 462 | return true; |
| 463 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 464 | SkASSERT(this->isComplex()); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 465 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 466 | const RunType* scanline = fRunHead->findScanline(sect.fTop); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 467 | for (;;) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 468 | if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) { |
| 469 | return true; |
| 470 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 471 | if (sect.fBottom <= scanline_bottom(scanline)) { |
| 472 | break; |
| 473 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 474 | scanline = scanline_next(scanline); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 475 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 476 | return false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 477 | } |
| 478 | |
| 479 | bool SkRegion::intersects(const SkRegion& rgn) const { |
| 480 | if (this->isEmpty() || rgn.isEmpty()) { |
| 481 | return false; |
| 482 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 483 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 484 | if (!SkIRect::Intersects(fBounds, rgn.fBounds)) { |
| 485 | return false; |
| 486 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 487 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 488 | bool weAreARect = this->isRect(); |
| 489 | bool theyAreARect = rgn.isRect(); |
| 490 | |
| 491 | if (weAreARect && theyAreARect) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 492 | return true; |
| 493 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 494 | if (weAreARect) { |
| 495 | return rgn.intersects(this->getBounds()); |
| 496 | } |
| 497 | if (theyAreARect) { |
| 498 | return this->intersects(rgn.getBounds()); |
| 499 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 500 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 501 | // both of us are complex |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 502 | return Oper(*this, rgn, kIntersect_Op, nullptr); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 503 | } |
| 504 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 505 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 506 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 507 | bool SkRegion::operator==(const SkRegion& b) const { |
| 508 | SkDEBUGCODE(validate();) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 509 | SkDEBUGCODE(b.validate();) |
| 510 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 511 | if (this == &b) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 512 | return true; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 513 | } |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 514 | if (fBounds != b.fBounds) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 515 | return false; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 516 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 517 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 518 | const SkRegion::RunHead* ah = fRunHead; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 519 | const SkRegion::RunHead* bh = b.fRunHead; |
| 520 | |
| 521 | // this catches empties and rects being equal |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 522 | if (ah == bh) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 523 | return true; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 524 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 525 | // now we insist that both are complex (but different ptrs) |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 526 | if (!this->isComplex() || !b.isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 527 | return false; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 528 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 529 | return ah->fRunCount == bh->fRunCount && |
| 530 | !memcmp(ah->readonly_runs(), bh->readonly_runs(), |
| 531 | ah->fRunCount * sizeof(SkRegion::RunType)); |
| 532 | } |
| 533 | |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 534 | void SkRegion::translate(int dx, int dy, SkRegion* dst) const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 535 | SkDEBUGCODE(this->validate();) |
| 536 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 537 | if (nullptr == dst) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 538 | return; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 539 | } |
| 540 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 541 | dst->setEmpty(); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 542 | } else if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 543 | dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy, |
| 544 | fBounds.fRight + dx, fBounds.fBottom + dy); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 545 | } else { |
| 546 | if (this == dst) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 547 | dst->fRunHead = dst->fRunHead->ensureWritable(); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 548 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 549 | SkRegion tmp; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 550 | tmp.allocateRuns(*fRunHead); |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 551 | SkASSERT(tmp.isComplex()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 552 | tmp.fBounds = fBounds; |
| 553 | dst->swap(tmp); |
| 554 | } |
| 555 | |
| 556 | dst->fBounds.offset(dx, dy); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 557 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 558 | const RunType* sruns = fRunHead->readonly_runs(); |
| 559 | RunType* druns = dst->fRunHead->writable_runs(); |
| 560 | |
| 561 | *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 562 | for (;;) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 563 | int bottom = *sruns++; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 564 | if (bottom == kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 565 | break; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 566 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 567 | *druns++ = (SkRegion::RunType)(bottom + dy); // bottom; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 568 | *druns++ = *sruns++; // copy intervalCount; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 569 | for (;;) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 570 | int x = *sruns++; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 571 | if (x == kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 572 | break; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 573 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 574 | *druns++ = (SkRegion::RunType)(x + dx); |
| 575 | *druns++ = (SkRegion::RunType)(*sruns++ + dx); |
| 576 | } |
| 577 | *druns++ = kRunTypeSentinel; // x sentinel |
| 578 | } |
| 579 | *druns++ = kRunTypeSentinel; // y sentinel |
| 580 | |
| 581 | SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount); |
| 582 | SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount); |
| 583 | } |
| 584 | |
| 585 | SkDEBUGCODE(this->validate();) |
| 586 | } |
| 587 | |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 588 | /////////////////////////////////////////////////////////////////////////////// |
| 589 | |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 590 | bool SkRegion::setRects(const SkIRect rects[], int count) { |
| 591 | if (0 == count) { |
reed@android.com | cb34235 | 2010-07-22 18:27:53 +0000 | [diff] [blame] | 592 | this->setEmpty(); |
| 593 | } else { |
| 594 | this->setRect(rects[0]); |
| 595 | for (int i = 1; i < count; i++) { |
| 596 | this->op(rects[i], kUnion_Op); |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 597 | } |
| 598 | } |
reed@android.com | cb34235 | 2010-07-22 18:27:53 +0000 | [diff] [blame] | 599 | return !this->isEmpty(); |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 600 | } |
| 601 | |
| 602 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 603 | |
bungeman | d7dc76f | 2016-03-10 11:14:40 -0800 | [diff] [blame] | 604 | #if defined _WIN32 // disable warning : local variable used without having been initialized |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 605 | #pragma warning ( push ) |
| 606 | #pragma warning ( disable : 4701 ) |
| 607 | #endif |
| 608 | |
| 609 | #ifdef SK_DEBUG |
| 610 | static void assert_valid_pair(int left, int rite) |
| 611 | { |
| 612 | SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite); |
| 613 | } |
| 614 | #else |
| 615 | #define assert_valid_pair(left, rite) |
| 616 | #endif |
| 617 | |
| 618 | struct spanRec { |
| 619 | const SkRegion::RunType* fA_runs; |
| 620 | const SkRegion::RunType* fB_runs; |
| 621 | int fA_left, fA_rite, fB_left, fB_rite; |
| 622 | int fLeft, fRite, fInside; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 623 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 624 | void init(const SkRegion::RunType a_runs[], |
| 625 | const SkRegion::RunType b_runs[]) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 626 | fA_left = *a_runs++; |
| 627 | fA_rite = *a_runs++; |
| 628 | fB_left = *b_runs++; |
| 629 | fB_rite = *b_runs++; |
| 630 | |
| 631 | fA_runs = a_runs; |
| 632 | fB_runs = b_runs; |
| 633 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 634 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 635 | bool done() const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 636 | SkASSERT(fA_left <= SkRegion::kRunTypeSentinel); |
| 637 | SkASSERT(fB_left <= SkRegion::kRunTypeSentinel); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 638 | return fA_left == SkRegion::kRunTypeSentinel && |
| 639 | fB_left == SkRegion::kRunTypeSentinel; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 640 | } |
| 641 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 642 | void next() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 643 | assert_valid_pair(fA_left, fA_rite); |
| 644 | assert_valid_pair(fB_left, fB_rite); |
| 645 | |
| 646 | int inside, left, rite SK_INIT_TO_AVOID_WARNING; |
| 647 | bool a_flush = false; |
| 648 | bool b_flush = false; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 649 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 650 | int a_left = fA_left; |
| 651 | int a_rite = fA_rite; |
| 652 | int b_left = fB_left; |
| 653 | int b_rite = fB_rite; |
| 654 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 655 | if (a_left < b_left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 656 | inside = 1; |
| 657 | left = a_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 658 | if (a_rite <= b_left) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 659 | rite = a_rite; |
| 660 | a_flush = true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 661 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 662 | rite = a_left = b_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 663 | } |
| 664 | } else if (b_left < a_left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 665 | inside = 2; |
| 666 | left = b_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 667 | if (b_rite <= a_left) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 668 | rite = b_rite; |
| 669 | b_flush = true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 670 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 671 | rite = b_left = a_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 672 | } |
| 673 | } else { // a_left == b_left |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 674 | inside = 3; |
| 675 | left = a_left; // or b_left |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 676 | if (a_rite <= b_rite) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 677 | rite = b_left = a_rite; |
| 678 | a_flush = true; |
| 679 | } |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 680 | if (b_rite <= a_rite) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 681 | rite = a_left = b_rite; |
| 682 | b_flush = true; |
| 683 | } |
| 684 | } |
| 685 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 686 | if (a_flush) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 687 | a_left = *fA_runs++; |
| 688 | a_rite = *fA_runs++; |
| 689 | } |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 690 | if (b_flush) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 691 | b_left = *fB_runs++; |
| 692 | b_rite = *fB_runs++; |
| 693 | } |
| 694 | |
| 695 | SkASSERT(left <= rite); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 696 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 697 | // now update our state |
| 698 | fA_left = a_left; |
| 699 | fA_rite = a_rite; |
| 700 | fB_left = b_left; |
| 701 | fB_rite = b_rite; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 702 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 703 | fLeft = left; |
| 704 | fRite = rite; |
| 705 | fInside = inside; |
| 706 | } |
| 707 | }; |
| 708 | |
| 709 | static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[], |
| 710 | const SkRegion::RunType b_runs[], |
| 711 | SkRegion::RunType dst[], |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 712 | int min, int max) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 713 | spanRec rec; |
| 714 | bool firstInterval = true; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 715 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 716 | rec.init(a_runs, b_runs); |
| 717 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 718 | while (!rec.done()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 719 | rec.next(); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 720 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 721 | int left = rec.fLeft; |
| 722 | int rite = rec.fRite; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 723 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 724 | // add left,rite to our dst buffer (checking for coincidence |
| 725 | if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) && |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 726 | left < rite) { // skip if equal |
| 727 | if (firstInterval || dst[-1] < left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 728 | *dst++ = (SkRegion::RunType)(left); |
| 729 | *dst++ = (SkRegion::RunType)(rite); |
| 730 | firstInterval = false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 731 | } else { |
| 732 | // update the right edge |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 733 | dst[-1] = (SkRegion::RunType)(rite); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 734 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 735 | } |
| 736 | } |
| 737 | |
| 738 | *dst++ = SkRegion::kRunTypeSentinel; |
| 739 | return dst; |
| 740 | } |
| 741 | |
bungeman | d7dc76f | 2016-03-10 11:14:40 -0800 | [diff] [blame] | 742 | #if defined _WIN32 |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 743 | #pragma warning ( pop ) |
| 744 | #endif |
| 745 | |
| 746 | static const struct { |
| 747 | uint8_t fMin; |
| 748 | uint8_t fMax; |
| 749 | } gOpMinMax[] = { |
| 750 | { 1, 1 }, // Difference |
| 751 | { 3, 3 }, // Intersection |
| 752 | { 1, 3 }, // Union |
| 753 | { 1, 2 } // XOR |
| 754 | }; |
| 755 | |
| 756 | class RgnOper { |
| 757 | public: |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 758 | RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 759 | // need to ensure that the op enum lines up with our minmax array |
| 760 | SkASSERT(SkRegion::kDifference_Op == 0); |
| 761 | SkASSERT(SkRegion::kIntersect_Op == 1); |
| 762 | SkASSERT(SkRegion::kUnion_Op == 2); |
| 763 | SkASSERT(SkRegion::kXOR_Op == 3); |
| 764 | SkASSERT((unsigned)op <= 3); |
| 765 | |
| 766 | fStartDst = dst; |
| 767 | fPrevDst = dst + 1; |
| 768 | fPrevLen = 0; // will never match a length from operate_on_span |
| 769 | fTop = (SkRegion::RunType)(top); // just a first guess, we might update this |
| 770 | |
| 771 | fMin = gOpMinMax[op].fMin; |
| 772 | fMax = gOpMinMax[op].fMax; |
| 773 | } |
| 774 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 775 | void addSpan(int bottom, const SkRegion::RunType a_runs[], |
| 776 | const SkRegion::RunType b_runs[]) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 777 | // skip X values and slots for the next Y+intervalCount |
| 778 | SkRegion::RunType* start = fPrevDst + fPrevLen + 2; |
| 779 | // start points to beginning of dst interval |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 780 | SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax); |
| 781 | size_t len = stop - start; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 782 | SkASSERT(len >= 1 && (len & 1) == 1); |
| 783 | SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 784 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 785 | if (fPrevLen == len && |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 786 | (1 == len || !memcmp(fPrevDst, start, |
| 787 | (len - 1) * sizeof(SkRegion::RunType)))) { |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 788 | // update Y value |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 789 | fPrevDst[-2] = (SkRegion::RunType)(bottom); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 790 | } else { // accept the new span |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 791 | if (len == 1 && fPrevLen == 0) { |
| 792 | fTop = (SkRegion::RunType)(bottom); // just update our bottom |
| 793 | } else { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 794 | start[-2] = (SkRegion::RunType)(bottom); |
commit-bot@chromium.org | f117781 | 2014-04-23 19:19:44 +0000 | [diff] [blame] | 795 | start[-1] = SkToS32(len >> 1); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 796 | fPrevDst = start; |
| 797 | fPrevLen = len; |
| 798 | } |
| 799 | } |
| 800 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 801 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 802 | int flush() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 803 | fStartDst[0] = fTop; |
| 804 | fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel; |
| 805 | return (int)(fPrevDst - fStartDst + fPrevLen + 1); |
| 806 | } |
| 807 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 808 | bool isEmpty() const { return 0 == fPrevLen; } |
| 809 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 810 | uint8_t fMin, fMax; |
| 811 | |
| 812 | private: |
| 813 | SkRegion::RunType* fStartDst; |
| 814 | SkRegion::RunType* fPrevDst; |
| 815 | size_t fPrevLen; |
| 816 | SkRegion::RunType fTop; |
| 817 | }; |
| 818 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 819 | // want a unique value to signal that we exited due to quickExit |
| 820 | #define QUICK_EXIT_TRUE_COUNT (-1) |
| 821 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 822 | static int operate(const SkRegion::RunType a_runs[], |
| 823 | const SkRegion::RunType b_runs[], |
| 824 | SkRegion::RunType dst[], |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 825 | SkRegion::Op op, |
| 826 | bool quickExit) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 827 | const SkRegion::RunType gEmptyScanline[] = { |
| 828 | 0, // dummy bottom value |
| 829 | 0, // zero intervals |
reed@google.com | 5f7c8a5 | 2012-05-03 16:17:38 +0000 | [diff] [blame] | 830 | SkRegion::kRunTypeSentinel, |
| 831 | // just need a 2nd value, since spanRec.init() reads 2 values, even |
| 832 | // though if the first value is the sentinel, it ignores the 2nd value. |
| 833 | // w/o the 2nd value here, we might read uninitialized memory. |
| 834 | // This happens when we are using gSentinel, which is pointing at |
| 835 | // our sentinel value. |
| 836 | 0 |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 837 | }; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 838 | const SkRegion::RunType* const gSentinel = &gEmptyScanline[2]; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 839 | |
| 840 | int a_top = *a_runs++; |
| 841 | int a_bot = *a_runs++; |
| 842 | int b_top = *b_runs++; |
| 843 | int b_bot = *b_runs++; |
| 844 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 845 | a_runs += 1; // skip the intervalCount; |
| 846 | b_runs += 1; // skip the intervalCount; |
| 847 | |
| 848 | // Now a_runs and b_runs to their intervals (or sentinel) |
| 849 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 850 | assert_sentinel(a_top, false); |
| 851 | assert_sentinel(a_bot, false); |
| 852 | assert_sentinel(b_top, false); |
| 853 | assert_sentinel(b_bot, false); |
| 854 | |
| 855 | RgnOper oper(SkMin32(a_top, b_top), dst, op); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 856 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 857 | int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 858 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 859 | while (a_bot < SkRegion::kRunTypeSentinel || |
| 860 | b_bot < SkRegion::kRunTypeSentinel) { |
| 861 | int top, bot SK_INIT_TO_AVOID_WARNING; |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 862 | const SkRegion::RunType* run0 = gSentinel; |
| 863 | const SkRegion::RunType* run1 = gSentinel; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 864 | bool a_flush = false; |
| 865 | bool b_flush = false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 866 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 867 | if (a_top < b_top) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 868 | top = a_top; |
| 869 | run0 = a_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 870 | if (a_bot <= b_top) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 871 | bot = a_bot; |
| 872 | a_flush = true; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 873 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 874 | bot = a_top = b_top; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 875 | } |
| 876 | } else if (b_top < a_top) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 877 | top = b_top; |
| 878 | run1 = b_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 879 | if (b_bot <= a_top) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 880 | bot = b_bot; |
| 881 | b_flush = true; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 882 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 883 | bot = b_top = a_top; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 884 | } |
| 885 | } else { // a_top == b_top |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 886 | top = a_top; // or b_top |
| 887 | run0 = a_runs; |
| 888 | run1 = b_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 889 | if (a_bot <= b_bot) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 890 | bot = b_top = a_bot; |
| 891 | a_flush = true; |
| 892 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 893 | if (b_bot <= a_bot) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 894 | bot = a_top = b_bot; |
| 895 | b_flush = true; |
| 896 | } |
| 897 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 898 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 899 | if (top > prevBot) { |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 900 | oper.addSpan(top, gSentinel, gSentinel); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 901 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 902 | oper.addSpan(bot, run0, run1); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 903 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 904 | if (quickExit && !oper.isEmpty()) { |
| 905 | return QUICK_EXIT_TRUE_COUNT; |
| 906 | } |
| 907 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 908 | if (a_flush) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 909 | a_runs = skip_intervals(a_runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 910 | a_top = a_bot; |
| 911 | a_bot = *a_runs++; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 912 | a_runs += 1; // skip uninitialized intervalCount |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 913 | if (a_bot == SkRegion::kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 914 | a_top = a_bot; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 915 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 916 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 917 | if (b_flush) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 918 | b_runs = skip_intervals(b_runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 919 | b_top = b_bot; |
| 920 | b_bot = *b_runs++; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 921 | b_runs += 1; // skip uninitialized intervalCount |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 922 | if (b_bot == SkRegion::kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 923 | b_top = b_bot; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 924 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 925 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 926 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 927 | prevBot = bot; |
| 928 | } |
| 929 | return oper.flush(); |
| 930 | } |
| 931 | |
| 932 | /////////////////////////////////////////////////////////////////////////////// |
| 933 | |
| 934 | /* Given count RunTypes in a complex region, return the worst case number of |
| 935 | logical intervals that represents (i.e. number of rects that would be |
| 936 | returned from the iterator). |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 937 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 938 | We could just return count/2, since there must be at least 2 values per |
| 939 | interval, but we can first trim off the const overhead of the initial TOP |
| 940 | value, plus the final BOTTOM + 2 sentinels. |
| 941 | */ |
caryclark@google.com | 803eceb | 2012-06-06 12:09:34 +0000 | [diff] [blame] | 942 | #if 0 // UNUSED |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 943 | static int count_to_intervals(int count) { |
| 944 | SkASSERT(count >= 6); // a single rect is 6 values |
| 945 | return (count - 4) >> 1; |
| 946 | } |
caryclark@google.com | 803eceb | 2012-06-06 12:09:34 +0000 | [diff] [blame] | 947 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 948 | |
| 949 | /* Given a number of intervals, what is the worst case representation of that |
| 950 | many intervals? |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 951 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 952 | Worst case (from a storage perspective), is a vertical stack of single |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 953 | intervals: TOP + N * (BOTTOM INTERVALCOUNT LEFT RIGHT SENTINEL) + SENTINEL |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 954 | */ |
| 955 | static int intervals_to_count(int intervals) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 956 | return 1 + intervals * 5 + 1; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 957 | } |
| 958 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 959 | /* Given the intervalCounts of RunTypes in two regions, return the worst-case number |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 960 | of RunTypes need to store the result after a region-op. |
| 961 | */ |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 962 | static int compute_worst_case_count(int a_intervals, int b_intervals) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 963 | // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1) |
| 964 | int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals; |
| 965 | // convert back to number of RunType values |
| 966 | return intervals_to_count(intervals); |
| 967 | } |
| 968 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 969 | static bool setEmptyCheck(SkRegion* result) { |
| 970 | return result ? result->setEmpty() : false; |
| 971 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 972 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 973 | static bool setRectCheck(SkRegion* result, const SkIRect& rect) { |
| 974 | return result ? result->setRect(rect) : !rect.isEmpty(); |
| 975 | } |
| 976 | |
| 977 | static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) { |
| 978 | return result ? result->setRegion(rgn) : !rgn.isEmpty(); |
| 979 | } |
| 980 | |
| 981 | bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op, |
| 982 | SkRegion* result) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 983 | SkASSERT((unsigned)op < kOpCount); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 984 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 985 | if (kReplace_Op == op) { |
| 986 | return setRegionCheck(result, rgnbOrig); |
| 987 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 988 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 989 | // swith to using pointers, so we can swap them as needed |
| 990 | const SkRegion* rgna = &rgnaOrig; |
| 991 | const SkRegion* rgnb = &rgnbOrig; |
| 992 | // after this point, do not refer to rgnaOrig or rgnbOrig!!! |
| 993 | |
| 994 | // collaps difference and reverse-difference into just difference |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 995 | if (kReverseDifference_Op == op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 996 | SkTSwap<const SkRegion*>(rgna, rgnb); |
| 997 | op = kDifference_Op; |
| 998 | } |
| 999 | |
| 1000 | SkIRect bounds; |
| 1001 | bool a_empty = rgna->isEmpty(); |
| 1002 | bool b_empty = rgnb->isEmpty(); |
| 1003 | bool a_rect = rgna->isRect(); |
| 1004 | bool b_rect = rgnb->isRect(); |
| 1005 | |
| 1006 | switch (op) { |
| 1007 | case kDifference_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1008 | if (a_empty) { |
| 1009 | return setEmptyCheck(result); |
| 1010 | } |
reed@google.com | 0d10280 | 2012-05-31 18:28:59 +0000 | [diff] [blame] | 1011 | if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds, |
| 1012 | rgnb->fBounds)) { |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1013 | return setRegionCheck(result, *rgna); |
| 1014 | } |
reed@google.com | 0d10280 | 2012-05-31 18:28:59 +0000 | [diff] [blame] | 1015 | if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) { |
| 1016 | return setEmptyCheck(result); |
| 1017 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1018 | break; |
| 1019 | |
| 1020 | case kIntersect_Op: |
| 1021 | if ((a_empty | b_empty) |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1022 | || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) { |
| 1023 | return setEmptyCheck(result); |
| 1024 | } |
| 1025 | if (a_rect & b_rect) { |
| 1026 | return setRectCheck(result, bounds); |
| 1027 | } |
reed@google.com | 633c32b | 2013-01-31 15:24:24 +0000 | [diff] [blame] | 1028 | if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { |
| 1029 | return setRegionCheck(result, *rgnb); |
| 1030 | } |
| 1031 | if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { |
| 1032 | return setRegionCheck(result, *rgna); |
| 1033 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1034 | break; |
| 1035 | |
| 1036 | case kUnion_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1037 | if (a_empty) { |
| 1038 | return setRegionCheck(result, *rgnb); |
| 1039 | } |
| 1040 | if (b_empty) { |
| 1041 | return setRegionCheck(result, *rgna); |
| 1042 | } |
| 1043 | if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { |
| 1044 | return setRegionCheck(result, *rgna); |
| 1045 | } |
| 1046 | if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { |
| 1047 | return setRegionCheck(result, *rgnb); |
| 1048 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1049 | break; |
| 1050 | |
| 1051 | case kXOR_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1052 | if (a_empty) { |
| 1053 | return setRegionCheck(result, *rgnb); |
| 1054 | } |
| 1055 | if (b_empty) { |
| 1056 | return setRegionCheck(result, *rgna); |
| 1057 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1058 | break; |
| 1059 | default: |
tomhudson@google.com | 0c00f21 | 2011-12-28 14:59:50 +0000 | [diff] [blame] | 1060 | SkDEBUGFAIL("unknown region op"); |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1061 | return false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1062 | } |
| 1063 | |
| 1064 | RunType tmpA[kRectRegionRuns]; |
| 1065 | RunType tmpB[kRectRegionRuns]; |
| 1066 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1067 | int a_intervals, b_intervals; |
| 1068 | const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals); |
| 1069 | const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1070 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1071 | int dstCount = compute_worst_case_count(a_intervals, b_intervals); |
| 1072 | SkAutoSTMalloc<256, RunType> array(dstCount); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1073 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1074 | #ifdef SK_DEBUG |
| 1075 | // Sometimes helpful to seed everything with a known value when debugging |
| 1076 | // sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount); |
| 1077 | #endif |
| 1078 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1079 | int count = operate(a_runs, b_runs, array.get(), op, nullptr == result); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1080 | SkASSERT(count <= dstCount); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1081 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1082 | if (result) { |
| 1083 | SkASSERT(count >= 0); |
| 1084 | return result->setRuns(array.get(), count); |
| 1085 | } else { |
| 1086 | return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count); |
| 1087 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1088 | } |
| 1089 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1090 | bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) { |
| 1091 | SkDEBUGCODE(this->validate();) |
| 1092 | return SkRegion::Oper(rgna, rgnb, op, this); |
| 1093 | } |
| 1094 | |
| 1095 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1096 | |
| 1097 | #include "SkBuffer.h" |
| 1098 | |
commit-bot@chromium.org | 4faa869 | 2013-11-05 15:46:56 +0000 | [diff] [blame] | 1099 | size_t SkRegion::writeToMemory(void* storage) const { |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1100 | if (nullptr == storage) { |
commit-bot@chromium.org | 4faa869 | 2013-11-05 15:46:56 +0000 | [diff] [blame] | 1101 | size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1102 | if (!this->isEmpty()) { |
| 1103 | size += sizeof(fBounds); |
| 1104 | if (this->isComplex()) { |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1105 | size += 2 * sizeof(int32_t); // ySpanCount + intervalCount |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1106 | size += fRunHead->fRunCount * sizeof(RunType); |
| 1107 | } |
| 1108 | } |
| 1109 | return size; |
| 1110 | } |
| 1111 | |
| 1112 | SkWBuffer buffer(storage); |
| 1113 | |
| 1114 | if (this->isEmpty()) { |
| 1115 | buffer.write32(-1); |
| 1116 | } else { |
| 1117 | bool isRect = this->isRect(); |
| 1118 | |
| 1119 | buffer.write32(isRect ? 0 : fRunHead->fRunCount); |
| 1120 | buffer.write(&fBounds, sizeof(fBounds)); |
| 1121 | |
| 1122 | if (!isRect) { |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1123 | buffer.write32(fRunHead->getYSpanCount()); |
| 1124 | buffer.write32(fRunHead->getIntervalCount()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1125 | buffer.write(fRunHead->readonly_runs(), |
| 1126 | fRunHead->fRunCount * sizeof(RunType)); |
| 1127 | } |
| 1128 | } |
| 1129 | return buffer.pos(); |
| 1130 | } |
| 1131 | |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1132 | // Validate that a memory sequence is a valid region. |
| 1133 | // Try to check all possible errors. |
| 1134 | // never read beyond &runs[runCount-1]. |
| 1135 | static bool validate_run(const int32_t* runs, |
| 1136 | int runCount, |
| 1137 | const SkIRect& givenBounds, |
| 1138 | int32_t ySpanCount, |
| 1139 | int32_t intervalCount) { |
| 1140 | // Region Layout: |
| 1141 | // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel |
| 1142 | if (ySpanCount < 1 || intervalCount < 2 || runCount != 2 + 3 * ySpanCount + 2 * intervalCount) { |
| 1143 | return false; |
| 1144 | } |
| 1145 | SkASSERT(runCount >= 7); // 7==SkRegion::kRectRegionRuns |
| 1146 | // quick sanity check: |
| 1147 | if (runs[runCount - 1] != SkRegion::kRunTypeSentinel || |
| 1148 | runs[runCount - 2] != SkRegion::kRunTypeSentinel) { |
| 1149 | return false; |
| 1150 | } |
| 1151 | const int32_t* const end = runs + runCount; |
| 1152 | SkIRect bounds = {0, 0, 0 ,0}; // calulated bounds |
| 1153 | SkIRect rect = {0, 0, 0, 0}; // current rect |
| 1154 | rect.fTop = *runs++; |
| 1155 | if (rect.fTop == SkRegion::kRunTypeSentinel) { |
| 1156 | return false; // no rect can contain SkRegion::kRunTypeSentinel |
| 1157 | } |
Hal Canary | f975b3e | 2017-06-22 11:21:57 +0000 | [diff] [blame] | 1158 | if (rect.fTop != givenBounds.fTop) { |
| 1159 | return false; // Must not begin with empty span that does not contribute to bounds. |
| 1160 | } |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1161 | do { |
| 1162 | --ySpanCount; |
| 1163 | if (ySpanCount < 0) { |
| 1164 | return false; // too many yspans |
| 1165 | } |
| 1166 | rect.fBottom = *runs++; |
| 1167 | if (rect.fBottom == SkRegion::kRunTypeSentinel) { |
| 1168 | return false; |
| 1169 | } |
Hal Canary | f975b3e | 2017-06-22 11:21:57 +0000 | [diff] [blame] | 1170 | if (rect.fBottom > givenBounds.fBottom) { |
| 1171 | return false; // Must not end with empty span that does not contribute to bounds. |
| 1172 | } |
| 1173 | if (rect.fBottom <= rect.fTop) { |
| 1174 | return false; // y-intervals must be ordered; rects must be non-empty. |
| 1175 | } |
| 1176 | |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1177 | int32_t xIntervals = *runs++; |
| 1178 | SkASSERT(runs < end); |
| 1179 | if (xIntervals < 0 || runs + 1 + 2 * xIntervals > end) { |
| 1180 | return false; |
| 1181 | } |
| 1182 | intervalCount -= xIntervals; |
| 1183 | if (intervalCount < 0) { |
| 1184 | return false; // too many intervals |
| 1185 | } |
Hal Canary | f975b3e | 2017-06-22 11:21:57 +0000 | [diff] [blame] | 1186 | bool firstInterval = true; |
| 1187 | int32_t lastRight; // check that x-intervals are distinct and ordered. |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1188 | while (xIntervals-- > 0) { |
| 1189 | rect.fLeft = *runs++; |
| 1190 | rect.fRight = *runs++; |
| 1191 | if (rect.fLeft == SkRegion::kRunTypeSentinel || |
Hal Canary | f975b3e | 2017-06-22 11:21:57 +0000 | [diff] [blame] | 1192 | rect.fRight == SkRegion::kRunTypeSentinel || |
| 1193 | rect.fLeft >= rect.fRight || // check non-empty rect |
| 1194 | (!firstInterval && rect.fLeft <= lastRight)) { |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1195 | return false; |
| 1196 | } |
Hal Canary | f975b3e | 2017-06-22 11:21:57 +0000 | [diff] [blame] | 1197 | lastRight = rect.fRight; |
| 1198 | firstInterval = false; |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1199 | bounds.join(rect); |
| 1200 | } |
| 1201 | if (*runs++ != SkRegion::kRunTypeSentinel) { |
| 1202 | return false; // required check sentinal. |
| 1203 | } |
| 1204 | rect.fTop = rect.fBottom; |
| 1205 | SkASSERT(runs < end); |
| 1206 | } while (*runs != SkRegion::kRunTypeSentinel); |
| 1207 | ++runs; |
| 1208 | if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) { |
| 1209 | return false; |
| 1210 | } |
| 1211 | SkASSERT(runs == end); // if ySpanCount && intervalCount are right, must be correct length. |
| 1212 | return true; |
| 1213 | } |
commit-bot@chromium.org | 4faa869 | 2013-11-05 15:46:56 +0000 | [diff] [blame] | 1214 | size_t SkRegion::readFromMemory(const void* storage, size_t length) { |
Mike Reed | 1026ccf | 2017-01-08 14:35:29 -0500 | [diff] [blame] | 1215 | SkRBuffer buffer(storage, length); |
| 1216 | SkRegion tmp; |
| 1217 | int32_t count; |
skia.committer@gmail.com | 382fde3 | 2013-11-06 07:02:11 +0000 | [diff] [blame] | 1218 | |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1219 | // Serialized Region Format: |
| 1220 | // Empty: |
| 1221 | // -1 |
| 1222 | // Simple Rect: |
| 1223 | // 0 LEFT TOP RIGHT BOTTOM |
| 1224 | // Complex Region: |
| 1225 | // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT [RUNS....] |
| 1226 | if (!buffer.readS32(&count) || count < -1) { |
| 1227 | return 0; |
| 1228 | } |
| 1229 | if (count >= 0) { |
| 1230 | if (!buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)) || tmp.fBounds.isEmpty()) { |
| 1231 | return 0; // Short buffer or bad bounds for non-empty region; report failure. |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 1232 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1233 | if (count == 0) { |
| 1234 | tmp.fRunHead = SkRegion_gRectRunHeadPtr; |
| 1235 | } else { |
commit-bot@chromium.org | 8f457e3 | 2013-11-08 19:22:57 +0000 | [diff] [blame] | 1236 | int32_t ySpanCount, intervalCount; |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1237 | if (!buffer.readS32(&ySpanCount) || |
| 1238 | !buffer.readS32(&intervalCount) || |
| 1239 | buffer.available() < count * sizeof(int32_t)) { |
| 1240 | return 0; |
commit-bot@chromium.org | 4faa869 | 2013-11-05 15:46:56 +0000 | [diff] [blame] | 1241 | } |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1242 | if (!validate_run((const int32_t*)((const char*)storage + buffer.pos()), count, |
| 1243 | tmp.fBounds, ySpanCount, intervalCount)) { |
| 1244 | return 0; // invalid runs, don't even allocate |
| 1245 | } |
| 1246 | tmp.allocateRuns(count, ySpanCount, intervalCount); |
| 1247 | SkASSERT(tmp.isComplex()); |
| 1248 | SkAssertResult(buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(int32_t))); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1249 | } |
| 1250 | } |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1251 | SkASSERT(tmp.isValid()); |
| 1252 | SkASSERT(buffer.isValid()); |
| 1253 | this->swap(tmp); |
| 1254 | return buffer.pos(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1255 | } |
| 1256 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 1257 | /////////////////////////////////////////////////////////////////////////////// |
| 1258 | |
| 1259 | const SkRegion& SkRegion::GetEmptyRegion() { |
| 1260 | static SkRegion gEmpty; |
| 1261 | return gEmpty; |
| 1262 | } |
| 1263 | |
| 1264 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1265 | |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 1266 | bool SkRegion::isValid() const { |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1267 | if (this->isEmpty()) { |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 1268 | return fBounds == SkIRect{0, 0, 0, 0}; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1269 | } |
Hal Canary | 58a1ea8 | 2017-02-19 22:16:10 -0500 | [diff] [blame] | 1270 | if (fBounds.isEmpty()) { |
| 1271 | return false; |
| 1272 | } |
| 1273 | if (this->isRect()) { |
| 1274 | return true; |
| 1275 | } |
| 1276 | return fRunHead && fRunHead->fRefCnt > 0 && |
| 1277 | validate_run(fRunHead->readonly_runs(), fRunHead->fRunCount, fBounds, |
| 1278 | fRunHead->getYSpanCount(), fRunHead->getIntervalCount()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1279 | } |
| 1280 | |
Hal Canary | 251bf3e | 2017-02-16 12:42:24 -0500 | [diff] [blame] | 1281 | #ifdef SK_DEBUG |
| 1282 | void SkRegion::validate() const { SkASSERT(this->isValid()); } |
| 1283 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1284 | void SkRegion::dump() const { |
| 1285 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1286 | SkDebugf(" rgn: empty\n"); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1287 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1288 | SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1289 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1290 | const RunType* runs = fRunHead->readonly_runs(); |
| 1291 | for (int i = 0; i < fRunHead->fRunCount; i++) |
| 1292 | SkDebugf(" %d", runs[i]); |
| 1293 | } |
| 1294 | SkDebugf("\n"); |
| 1295 | } |
| 1296 | } |
| 1297 | |
| 1298 | #endif |
| 1299 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1300 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1301 | |
| 1302 | SkRegion::Iterator::Iterator(const SkRegion& rgn) { |
| 1303 | this->reset(rgn); |
| 1304 | } |
| 1305 | |
| 1306 | bool SkRegion::Iterator::rewind() { |
| 1307 | if (fRgn) { |
| 1308 | this->reset(*fRgn); |
| 1309 | return true; |
| 1310 | } |
| 1311 | return false; |
| 1312 | } |
| 1313 | |
| 1314 | void SkRegion::Iterator::reset(const SkRegion& rgn) { |
| 1315 | fRgn = &rgn; |
| 1316 | if (rgn.isEmpty()) { |
| 1317 | fDone = true; |
| 1318 | } else { |
| 1319 | fDone = false; |
| 1320 | if (rgn.isRect()) { |
| 1321 | fRect = rgn.fBounds; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1322 | fRuns = nullptr; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1323 | } else { |
| 1324 | fRuns = rgn.fRunHead->readonly_runs(); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1325 | fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]); |
| 1326 | fRuns += 5; |
| 1327 | // Now fRuns points to the 2nd interval (or x-sentinel) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1328 | } |
| 1329 | } |
| 1330 | } |
| 1331 | |
| 1332 | void SkRegion::Iterator::next() { |
| 1333 | if (fDone) { |
| 1334 | return; |
| 1335 | } |
| 1336 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1337 | if (fRuns == nullptr) { // rect case |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1338 | fDone = true; |
| 1339 | return; |
| 1340 | } |
| 1341 | |
| 1342 | const RunType* runs = fRuns; |
| 1343 | |
| 1344 | if (runs[0] < kRunTypeSentinel) { // valid X value |
| 1345 | fRect.fLeft = runs[0]; |
| 1346 | fRect.fRight = runs[1]; |
| 1347 | runs += 2; |
| 1348 | } else { // we're at the end of a line |
| 1349 | runs += 1; |
| 1350 | if (runs[0] < kRunTypeSentinel) { // valid Y value |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1351 | int intervals = runs[1]; |
| 1352 | if (0 == intervals) { // empty line |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1353 | fRect.fTop = runs[0]; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1354 | runs += 3; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1355 | } else { |
| 1356 | fRect.fTop = fRect.fBottom; |
| 1357 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1358 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1359 | fRect.fBottom = runs[0]; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1360 | assert_sentinel(runs[2], false); |
| 1361 | assert_sentinel(runs[3], false); |
| 1362 | fRect.fLeft = runs[2]; |
| 1363 | fRect.fRight = runs[3]; |
| 1364 | runs += 4; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1365 | } else { // end of rgn |
| 1366 | fDone = true; |
| 1367 | } |
| 1368 | } |
| 1369 | fRuns = runs; |
| 1370 | } |
| 1371 | |
| 1372 | SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip) |
| 1373 | : fIter(rgn), fClip(clip), fDone(true) { |
| 1374 | const SkIRect& r = fIter.rect(); |
| 1375 | |
| 1376 | while (!fIter.done()) { |
| 1377 | if (r.fTop >= clip.fBottom) { |
| 1378 | break; |
| 1379 | } |
| 1380 | if (fRect.intersect(clip, r)) { |
| 1381 | fDone = false; |
| 1382 | break; |
| 1383 | } |
| 1384 | fIter.next(); |
| 1385 | } |
| 1386 | } |
| 1387 | |
| 1388 | void SkRegion::Cliperator::next() { |
| 1389 | if (fDone) { |
| 1390 | return; |
| 1391 | } |
| 1392 | |
| 1393 | const SkIRect& r = fIter.rect(); |
| 1394 | |
| 1395 | fDone = true; |
| 1396 | fIter.next(); |
| 1397 | while (!fIter.done()) { |
| 1398 | if (r.fTop >= fClip.fBottom) { |
| 1399 | break; |
| 1400 | } |
| 1401 | if (fRect.intersect(fClip, r)) { |
| 1402 | fDone = false; |
| 1403 | break; |
| 1404 | } |
| 1405 | fIter.next(); |
| 1406 | } |
| 1407 | } |
| 1408 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1409 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1410 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1411 | SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, |
| 1412 | int right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1413 | SkDEBUGCODE(rgn.validate();) |
| 1414 | |
| 1415 | const SkIRect& r = rgn.getBounds(); |
| 1416 | |
| 1417 | fDone = true; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1418 | if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && |
| 1419 | right > r.fLeft && left < r.fRight) { |
| 1420 | if (rgn.isRect()) { |
| 1421 | if (left < r.fLeft) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1422 | left = r.fLeft; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1423 | } |
| 1424 | if (right > r.fRight) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1425 | right = r.fRight; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1426 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1427 | fLeft = left; |
| 1428 | fRight = right; |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1429 | fRuns = nullptr; // means we're a rect, not a rgn |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1430 | fDone = false; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1431 | } else { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1432 | const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y); |
| 1433 | runs += 2; // skip Bottom and IntervalCount |
| 1434 | for (;;) { |
| 1435 | // runs[0..1] is to the right of the span, so we're done |
| 1436 | if (runs[0] >= right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1437 | break; |
| 1438 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1439 | // runs[0..1] is to the left of the span, so continue |
| 1440 | if (runs[1] <= left) { |
| 1441 | runs += 2; |
| 1442 | continue; |
| 1443 | } |
| 1444 | // runs[0..1] intersects the span |
| 1445 | fRuns = runs; |
| 1446 | fLeft = left; |
| 1447 | fRight = right; |
| 1448 | fDone = false; |
| 1449 | break; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1450 | } |
| 1451 | } |
| 1452 | } |
| 1453 | } |
| 1454 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1455 | bool SkRegion::Spanerator::next(int* left, int* right) { |
| 1456 | if (fDone) { |
| 1457 | return false; |
| 1458 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1459 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 1460 | if (fRuns == nullptr) { // we're a rect |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1461 | fDone = true; // ok, now we're done |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1462 | if (left) { |
| 1463 | *left = fLeft; |
| 1464 | } |
| 1465 | if (right) { |
| 1466 | *right = fRight; |
| 1467 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1468 | return true; // this interval is legal |
| 1469 | } |
| 1470 | |
| 1471 | const SkRegion::RunType* runs = fRuns; |
| 1472 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1473 | if (runs[0] >= fRight) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1474 | fDone = true; |
| 1475 | return false; |
| 1476 | } |
| 1477 | |
| 1478 | SkASSERT(runs[1] > fLeft); |
| 1479 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1480 | if (left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1481 | *left = SkMax32(fLeft, runs[0]); |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1482 | } |
| 1483 | if (right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1484 | *right = SkMin32(fRight, runs[1]); |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1485 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1486 | fRuns = runs + 2; |
| 1487 | return true; |
| 1488 | } |
| 1489 | |
| 1490 | /////////////////////////////////////////////////////////////////////////////// |
| 1491 | |
| 1492 | #ifdef SK_DEBUG |
| 1493 | |
| 1494 | bool SkRegion::debugSetRuns(const RunType runs[], int count) { |
| 1495 | // we need to make a copy, since the real method may modify the array, and |
| 1496 | // so it cannot be const. |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1497 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1498 | SkAutoTArray<RunType> storage(count); |
| 1499 | memcpy(storage.get(), runs, count * sizeof(RunType)); |
| 1500 | return this->setRuns(storage.get(), count); |
| 1501 | } |
| 1502 | |
| 1503 | #endif |