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