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 SkAntiRun_DEFINED
11#define SkAntiRun_DEFINED
12
13#include "SkBlitter.h"
14
15/** Sparse array of run-length-encoded alpha (supersampling coverage) values.
16    Sparseness allows us to independently compose several paths into the
17    same SkAlphaRuns buffer.
18*/
19
20class SkAlphaRuns {
21public:
22    int16_t*    fRuns;
23    uint8_t*     fAlpha;
24
25    /// Returns true if the scanline contains only a single run,
26    /// of alpha value 0.
27    bool empty() const {
28        SkASSERT(fRuns[0] > 0);
29        return fAlpha[0] == 0 && fRuns[fRuns[0]] == 0;
30    }
31
32    /// Reinitialize for a new scanline.
33    void    reset(int width);
34
35    /**
36     *  Insert into the buffer a run starting at (x-offsetX):
37     *      if startAlpha > 0
38     *          one pixel with value += startAlpha,
39     *              max 255
40     *      if middleCount > 0
41     *          middleCount pixels with value += maxValue
42     *      if stopAlpha > 0
43     *          one pixel with value += stopAlpha
44     *  Returns the offsetX value that should be passed on the next call,
45     *  assuming we're on the same scanline. If the caller is switching
46     *  scanlines, then offsetX should be 0 when this is called.
47     */
48    SK_ALWAYS_INLINE int add(int x, U8CPU startAlpha, int middleCount, U8CPU stopAlpha,
49                             U8CPU maxValue, int offsetX) {
50        SkASSERT(middleCount >= 0);
51        SkASSERT(x >= 0 && x + (startAlpha != 0) + middleCount + (stopAlpha != 0) <= fWidth);
52
53        SkASSERT(fRuns[offsetX] >= 0);
54
55        int16_t*    runs = fRuns + offsetX;
56        uint8_t*    alpha = fAlpha + offsetX;
57        uint8_t*    lastAlpha = alpha;
58        x -= offsetX;
59
60        if (startAlpha) {
61            SkAlphaRuns::Break(runs, alpha, x, 1);
62            /*  I should be able to just add alpha[x] + startAlpha.
63                However, if the trailing edge of the previous span and the leading
64                edge of the current span round to the same super-sampled x value,
65                I might overflow to 256 with this add, hence the funny subtract (crud).
66            */
67            unsigned tmp = alpha[x] + startAlpha;
68            SkASSERT(tmp <= 256);
69            alpha[x] = SkToU8(tmp - (tmp >> 8));    // was (tmp >> 7), but that seems wrong if we're trying to catch 256
70
71            runs += x + 1;
72            alpha += x + 1;
73            x = 0;
74            lastAlpha += x; // we don't want the +1
75            SkDEBUGCODE(this->validate();)
76        }
77
78        if (middleCount) {
79            SkAlphaRuns::Break(runs, alpha, x, middleCount);
80            alpha += x;
81            runs += x;
82            x = 0;
83            do {
84                alpha[0] = SkToU8(alpha[0] + maxValue);
85                int n = runs[0];
86                SkASSERT(n <= middleCount);
87                alpha += n;
88                runs += n;
89                middleCount -= n;
90            } while (middleCount > 0);
91            SkDEBUGCODE(this->validate();)
92            lastAlpha = alpha;
93        }
94
95        if (stopAlpha) {
96            SkAlphaRuns::Break(runs, alpha, x, 1);
97            alpha += x;
98            alpha[0] = SkToU8(alpha[0] + stopAlpha);
99            SkDEBUGCODE(this->validate();)
100            lastAlpha = alpha;
101        }
102
103        return SkToS32(lastAlpha - fAlpha);  // new offsetX
104    }
105
106    SkDEBUGCODE(void assertValid(int y, int maxStep) const;)
107    SkDEBUGCODE(void dump() const;)
108
109    /**
110     * Break the runs in the buffer at offsets x and x+count, properly
111     * updating the runs to the right and left.
112     *   i.e. from the state AAAABBBB, run-length encoded as A4B4,
113     *   Break(..., 2, 5) would produce AAAABBBB rle as A2A2B3B1.
114     * Allows add() to sum another run to some of the new sub-runs.
115     *   i.e. adding ..CCCCC. would produce AADDEEEB, rle as A2D2E3B1.
116     */
117    static void Break(int16_t runs[], uint8_t alpha[], int x, int count) {
118        SkASSERT(count > 0 && x >= 0);
119
120        //  SkAlphaRuns::BreakAt(runs, alpha, x);
121        //  SkAlphaRuns::BreakAt(&runs[x], &alpha[x], count);
122
123        int16_t* next_runs = runs + x;
124        uint8_t*  next_alpha = alpha + x;
125
126        while (x > 0) {
127            int n = runs[0];
128            SkASSERT(n > 0);
129
130            if (x < n) {
131                alpha[x] = alpha[0];
132                runs[0] = SkToS16(x);
133                runs[x] = SkToS16(n - x);
134                break;
135            }
136            runs += n;
137            alpha += n;
138            x -= n;
139        }
140
141        runs = next_runs;
142        alpha = next_alpha;
143        x = count;
144
145        for (;;) {
146            int n = runs[0];
147            SkASSERT(n > 0);
148
149            if (x < n) {
150                alpha[x] = alpha[0];
151                runs[0] = SkToS16(x);
152                runs[x] = SkToS16(n - x);
153                break;
154            }
155            x -= n;
156            if (x <= 0) {
157                break;
158            }
159            runs += n;
160            alpha += n;
161        }
162    }
163
164    /**
165     * Cut (at offset x in the buffer) a run into two shorter runs with
166     * matching alpha values.
167     * Used by the RectClipBlitter to trim a RLE encoding to match the
168     * clipping rectangle.
169     */
170    static void BreakAt(int16_t runs[], uint8_t alpha[], int x) {
171        while (x > 0) {
172            int n = runs[0];
173            SkASSERT(n > 0);
174
175            if (x < n) {
176                alpha[x] = alpha[0];
177                runs[0] = SkToS16(x);
178                runs[x] = SkToS16(n - x);
179                break;
180            }
181            runs += n;
182            alpha += n;
183            x -= n;
184        }
185    }
186
187private:
188    SkDEBUGCODE(int fWidth;)
189    SkDEBUGCODE(void validate() const;)
190};
191
192#endif
193