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