Home | History | Annotate | Download | only in core
      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