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