aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkRegionPriv.h
blob: ce21e92960857b3f6de19fa6fd8b54a0da51116c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */


#ifndef SkRegionPriv_DEFINED
#define SkRegionPriv_DEFINED

#include "SkRegion.h"

#include "SkAtomics.h"
#include "SkMalloc.h"

inline bool SkRegionValueIsSentinel(int32_t value) {
    return value == (int32_t)SkRegion::kRunTypeSentinel;
}

#define assert_sentinel(value, isSentinel) \
    SkASSERT(SkRegionValueIsSentinel(value) == isSentinel)

//SkDEBUGCODE(extern int32_t gRgnAllocCounter;)

#ifdef SK_DEBUG
// Given the first interval (just past the interval-count), compute the
// interval count, by search for the x-sentinel
//
static int compute_intervalcount(const SkRegion::RunType runs[]) {
    const SkRegion::RunType* curr = runs;
    while (*curr < SkRegion::kRunTypeSentinel) {
        SkASSERT(curr[0] < curr[1]);
        SkASSERT(curr[1] < SkRegion::kRunTypeSentinel);
        curr += 2;
    }
    return SkToInt((curr - runs) >> 1);
}
#endif

struct SkRegion::RunHead {
private:

public:
    int32_t fRefCnt;
    int32_t fRunCount;

    /**
     *  Number of spans with different Y values. This does not count the initial
     *  Top value, nor does it count the final Y-Sentinel value. In the logical
     *  case of a rectangle, this would return 1, and an empty region would
     *  return 0.
     */
    int getYSpanCount() const {
        return fYSpanCount;
    }

    /**
     *  Number of intervals in the entire region. This equals the number of
     *  rects that would be returned by the Iterator. In the logical case of
     *  a rect, this would return 1, and an empty region would return 0.
     */
    int getIntervalCount() const {
        return fIntervalCount;
    }

    static RunHead* Alloc(int count) {
        //SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
        //SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));

        if (count < SkRegion::kRectRegionRuns) {
            return nullptr;
        }

        const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead);
        if (count < 0 || !sk_64_isS32(size)) { SK_ABORT("Invalid Size"); }

        RunHead* head = (RunHead*)sk_malloc_throw(size);
        head->fRefCnt = 1;
        head->fRunCount = count;
        // these must be filled in later, otherwise we will be invalid
        head->fYSpanCount = 0;
        head->fIntervalCount = 0;
        return head;
    }

    static RunHead* Alloc(int count, int yspancount, int intervalCount) {
        if (yspancount <= 0 || intervalCount <= 1) {
            return nullptr;
        }

        RunHead* head = Alloc(count);
        if (!head) {
            return nullptr;
        }
        head->fYSpanCount = yspancount;
        head->fIntervalCount = intervalCount;
        return head;
    }

    SkRegion::RunType* writable_runs() {
        SkASSERT(fRefCnt == 1);
        return (SkRegion::RunType*)(this + 1);
    }

    const SkRegion::RunType* readonly_runs() const {
        return (const SkRegion::RunType*)(this + 1);
    }

    RunHead* ensureWritable() {
        RunHead* writable = this;
        if (fRefCnt > 1) {
            // We need to alloc & copy the current region before we call
            // sk_atomic_dec because it could be freed in the meantime,
            // otherwise.
            writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
            memcpy(writable->writable_runs(), this->readonly_runs(),
                   fRunCount * sizeof(RunType));

            // fRefCount might have changed since we last checked.
            // If we own the last reference at this point, we need to
            // free the memory.
            if (sk_atomic_dec(&fRefCnt) == 1) {
                sk_free(this);
            }
        }
        return writable;
    }

    /**
     *  Given a scanline (including its Bottom value at runs[0]), return the next
     *  scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
     */
    static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
        // we are not the Y Sentinel
        SkASSERT(runs[0] < SkRegion::kRunTypeSentinel);

        const int intervals = runs[1];
        SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel);
#ifdef SK_DEBUG
        {
            int n = compute_intervalcount(&runs[2]);
            SkASSERT(n == intervals);
        }
#endif

        // skip the entire line [B N [L R] S]
        runs += 1 + 1 + intervals * 2 + 1;
        return const_cast<SkRegion::RunType*>(runs);
    }


    /**
     *  Return the scanline that contains the Y value. This requires that the Y
     *  value is already known to be contained within the bounds of the region,
     *  and so this routine never returns nullptr.
     *
     *  It returns the beginning of the scanline, starting with its Bottom value.
     */
    SkRegion::RunType* findScanline(int y) const {
        const RunType* runs = this->readonly_runs();

        // if the top-check fails, we didn't do a quick check on the bounds
        SkASSERT(y >= runs[0]);

        runs += 1;  // skip top-Y
        for (;;) {
            int bottom = runs[0];
            // If we hit this, we've walked off the region, and our bounds check
            // failed.
            SkASSERT(bottom < SkRegion::kRunTypeSentinel);
            if (y < bottom) {
                break;
            }
            runs = SkipEntireScanline(runs);
        }
        return const_cast<SkRegion::RunType*>(runs);
    }

    // Copy src runs into us, computing interval counts and bounds along the way
    void computeRunBounds(SkIRect* bounds) {
        RunType* runs = this->writable_runs();
        bounds->fTop = *runs++;

        int bot;
        int ySpanCount = 0;
        int intervalCount = 0;
        int left = SK_MaxS32;
        int rite = SK_MinS32;

        do {
            bot = *runs++;
            SkASSERT(bot < SkRegion::kRunTypeSentinel);
            ySpanCount += 1;

            const int intervals = *runs++;
            SkASSERT(intervals >= 0);
            SkASSERT(intervals < SkRegion::kRunTypeSentinel);

            if (intervals > 0) {
#ifdef SK_DEBUG
                {
                    int n = compute_intervalcount(runs);
                    SkASSERT(n == intervals);
                }
#endif
                RunType L = runs[0];
                SkASSERT(L < SkRegion::kRunTypeSentinel);
                if (left > L) {
                    left = L;
                }

                runs += intervals * 2;
                RunType R = runs[-1];
                SkASSERT(R < SkRegion::kRunTypeSentinel);
                if (rite < R) {
                    rite = R;
                }

                intervalCount += intervals;
            }
            SkASSERT(SkRegion::kRunTypeSentinel == *runs);
            runs += 1;  // skip x-sentinel

            // test Y-sentinel
        } while (SkRegion::kRunTypeSentinel > *runs);

#ifdef SK_DEBUG
        // +1 to skip the last Y-sentinel
        int runCount = SkToInt(runs - this->writable_runs() + 1);
        SkASSERT(runCount == fRunCount);
#endif

        fYSpanCount = ySpanCount;
        fIntervalCount = intervalCount;

        bounds->fLeft = left;
        bounds->fRight = rite;
        bounds->fBottom = bot;
    }

private:
    int32_t fYSpanCount;
    int32_t fIntervalCount;
};

#include <functional>

class SkRegionPriv {
public:
    // Call the function with each span, in Y -> X ascending order.
    // We pass a rect, but we will still ensure the span Y->X ordering, so often the height
    // of the rect may be 1. It should never be empty.
    static void VisitSpans(const SkRegion& rgn, const std::function<void(const SkIRect&)>&);
};

#endif