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//
25static 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
36struct SkRegion::RunHead {
37private:
38
39public:
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
228private:
229    int32_t fYSpanCount;
230    int32_t fIntervalCount;
231};
232
233#endif
234