src/third_party/skia/src/core/SkRegionPriv.h

   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