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 "SkThread.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 RunHead* head = (RunHead*)sk_malloc_throw(sizeof(RunHead) + count * sizeof(RunType)); 69 head->fRefCnt = 1; 70 head->fRunCount = count; 71 // these must be filled in later, otherwise we will be invalid 72 head->fYSpanCount = 0; 73 head->fIntervalCount = 0; 74 return head; 75 } 76 77 static RunHead* Alloc(int count, int yspancount, int intervalCount) { 78 SkASSERT(yspancount > 0); 79 SkASSERT(intervalCount > 1); 80 81 RunHead* head = Alloc(count); 82 head->fYSpanCount = yspancount; 83 head->fIntervalCount = intervalCount; 84 return head; 85 } 86 87 SkRegion::RunType* writable_runs() { 88 SkASSERT(fRefCnt == 1); 89 return (SkRegion::RunType*)(this + 1); 90 } 91 92 const SkRegion::RunType* readonly_runs() const { 93 return (const SkRegion::RunType*)(this + 1); 94 } 95 96 RunHead* ensureWritable() { 97 RunHead* writable = this; 98 if (fRefCnt > 1) { 99 // We need to alloc & copy the current region before we call 100 // sk_atomic_dec because it could be freed in the meantime, 101 // otherwise. 102 writable = Alloc(fRunCount, fYSpanCount, fIntervalCount); 103 memcpy(writable->writable_runs(), this->readonly_runs(), 104 fRunCount * sizeof(RunType)); 105 106 // fRefCount might have changed since we last checked. 107 // If we own the last reference at this point, we need to 108 // free the memory. 109 if (sk_atomic_dec(&fRefCnt) == 1) { 110 sk_free(this); 111 } 112 } 113 return writable; 114 } 115 116 /** 117 * Given a scanline (including its Bottom value at runs[0]), return the next 118 * scanline. Asserts that there is one (i.e. runs[0] < Sentinel) 119 */ 120 static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) { 121 // we are not the Y Sentinel 122 SkASSERT(runs[0] < SkRegion::kRunTypeSentinel); 123 124 const int intervals = runs[1]; 125 SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel); 126 #ifdef SK_DEBUG 127 { 128 int n = compute_intervalcount(&runs[2]); 129 SkASSERT(n == intervals); 130 } 131 #endif 132 133 // skip the entire line [B N [L R] S] 134 runs += 1 + 1 + intervals * 2 + 1; 135 return const_cast<SkRegion::RunType*>(runs); 136 } 137 138 139 /** 140 * Return the scanline that contains the Y value. This requires that the Y 141 * value is already known to be contained within the bounds of the region, 142 * and so this routine never returns NULL. 143 * 144 * It returns the beginning of the scanline, starting with its Bottom value. 145 */ 146 SkRegion::RunType* findScanline(int y) const { 147 const RunType* runs = this->readonly_runs(); 148 149 // if the top-check fails, we didn't do a quick check on the bounds 150 SkASSERT(y >= runs[0]); 151 152 runs += 1; // skip top-Y 153 for (;;) { 154 int bottom = runs[0]; 155 // If we hit this, we've walked off the region, and our bounds check 156 // failed. 157 SkASSERT(bottom < SkRegion::kRunTypeSentinel); 158 if (y < bottom) { 159 break; 160 } 161 runs = SkipEntireScanline(runs); 162 } 163 return const_cast<SkRegion::RunType*>(runs); 164 } 165 166 // Copy src runs into us, computing interval counts and bounds along the way 167 void computeRunBounds(SkIRect* bounds) { 168 RunType* runs = this->writable_runs(); 169 bounds->fTop = *runs++; 170 171 int bot; 172 int ySpanCount = 0; 173 int intervalCount = 0; 174 int left = SK_MaxS32; 175 int rite = SK_MinS32; 176 177 do { 178 bot = *runs++; 179 SkASSERT(bot < SkRegion::kRunTypeSentinel); 180 ySpanCount += 1; 181 182 const int intervals = *runs++; 183 SkASSERT(intervals >= 0); 184 SkASSERT(intervals < SkRegion::kRunTypeSentinel); 185 186 if (intervals > 0) { 187 #ifdef SK_DEBUG 188 { 189 int n = compute_intervalcount(runs); 190 SkASSERT(n == intervals); 191 } 192 #endif 193 RunType L = runs[0]; 194 SkASSERT(L < SkRegion::kRunTypeSentinel); 195 if (left > L) { 196 left = L; 197 } 198 199 runs += intervals * 2; 200 RunType R = runs[-1]; 201 SkASSERT(R < SkRegion::kRunTypeSentinel); 202 if (rite < R) { 203 rite = R; 204 } 205 206 intervalCount += intervals; 207 } 208 SkASSERT(SkRegion::kRunTypeSentinel == *runs); 209 runs += 1; // skip x-sentinel 210 211 // test Y-sentinel 212 } while (SkRegion::kRunTypeSentinel > *runs); 213 214 #ifdef SK_DEBUG 215 // +1 to skip the last Y-sentinel 216 int runCount = SkToInt(runs - this->writable_runs() + 1); 217 SkASSERT(runCount == fRunCount); 218 #endif 219 220 fYSpanCount = ySpanCount; 221 fIntervalCount = intervalCount; 222 223 bounds->fLeft = left; 224 bounds->fRight = rite; 225 bounds->fBottom = bot; 226 } 227 228 private: 229 int32_t fYSpanCount; 230 int32_t fIntervalCount; 231 }; 232 233 #endif 234
