1 /*
2 * Copyright 2017 Google Inc.
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 SkCoverageDelta_DEFINED
9 #define SkCoverageDelta_DEFINED
10
11 #include "SkArenaAlloc.h"
12 #include "SkFixed.h"
13 #include "SkMask.h"
14 #include "SkTSort.h"
15 #include "SkUtils.h"
16
17 // Future todo: maybe we can make fX and fDelta 16-bit long to speed it up a little bit.
18 struct SkCoverageDelta {
19 int fX; // the y coordinate will be implied in SkCoverageDeltaList
20 SkFixed fDelta; // the amount that the alpha changed
21
22 // Sort according to fX
23 bool operator<(const SkCoverageDelta& other) const {
24 return fX < other.fX;
25 }
26 };
27
28 // All the arguments needed for SkBlitter::blitAntiRect
29 struct SkAntiRect {
30 int fX;
31 int fY;
32 int fWidth;
33 int fHeight;
34 SkAlpha fLeftAlpha;
35 SkAlpha fRightAlpha;
36 };
37
38 // A list of SkCoverageDelta with y from top() to bottom().
39 // For each row y, there are count(y) number of deltas.
40 // You can ask whether they are sorted or not by sorted(y), and you can sort them by sort(y).
41 // Once sorted, getDelta(y, i) should return the i-th leftmost delta on row y.
42 class SkCoverageDeltaList {
43 public:
44 // We can store INIT_ROW_SIZE deltas per row (i.e., per y-scanline) initially.
45 #ifdef SK_BUILD_FOR_GOOGLE3
46 static constexpr int INIT_ROW_SIZE = 8; // google3 has 16k stack limit; so we make it small
47 #else
48 static constexpr int INIT_ROW_SIZE = 32;
49 #endif
50
51 SkCoverageDeltaList(SkArenaAlloc* alloc, const SkIRect& bounds, bool forceRLE);
52
top()53 int top() const { return fBounds.fTop; }
bottom()54 int bottom() const { return fBounds.fBottom; }
left()55 int left() const { return fBounds.fLeft; }
right()56 int right() const { return fBounds.fRight; }
forceRLE()57 bool forceRLE() const { return fForceRLE; }
count(int y)58 int count(int y) const { this->checkY(y); return fCounts[y]; }
sorted(int y)59 bool sorted(int y) const { this->checkY(y); return fSorted[y]; }
60
addDelta(int x,int y,SkFixed delta)61 SK_ALWAYS_INLINE void addDelta(int x, int y, SkFixed delta) { this->push_back(y, {x, delta}); }
getDelta(int y,int i)62 SK_ALWAYS_INLINE const SkCoverageDelta& getDelta(int y, int i) const {
63 this->checkY(y);
64 SkASSERT(i < fCounts[y]);
65 return fRows[y][i];
66 }
67
68 // It might be better to sort right before blitting to make the memory hot
sort(int y)69 void sort(int y) {
70 this->checkY(y);
71 if (!fSorted[y]) {
72 SkTQSort(fRows[y], fRows[y] + fCounts[y] - 1);
73 fSorted[y] = true;
74 }
75 }
76
getAntiRect()77 const SkAntiRect& getAntiRect() const { return fAntiRect; }
setAntiRect(int x,int y,int width,int height,SkAlpha leftAlpha,SkAlpha rightAlpha)78 void setAntiRect(int x, int y, int width, int height,
79 SkAlpha leftAlpha, SkAlpha rightAlpha) {
80 fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
81 }
82
83 private:
84 SkArenaAlloc* fAlloc;
85 SkCoverageDelta** fRows;
86 bool* fSorted;
87 int* fCounts;
88 int* fMaxCounts;
89 SkIRect fBounds;
90 SkAntiRect fAntiRect;
91 bool fForceRLE;
92
checkY(int y)93 void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); }
94
push_back(int y,const SkCoverageDelta & delta)95 SK_ALWAYS_INLINE void push_back(int y, const SkCoverageDelta& delta) {
96 this->checkY(y);
97 if (fCounts[y] == fMaxCounts[y]) {
98 fMaxCounts[y] *= 4;
99 SkCoverageDelta* newRow = fAlloc->makeArrayDefault<SkCoverageDelta>(fMaxCounts[y]);
100 memcpy(newRow, fRows[y], sizeof(SkCoverageDelta) * fCounts[y]);
101 fRows[y] = newRow;
102 }
103 SkASSERT(fCounts[y] < fMaxCounts[y]);
104 fRows[y][fCounts[y]++] = delta;
105 fSorted[y] = fSorted[y] && (fCounts[y] == 1 || delta.fX >= fRows[y][fCounts[y] - 2].fX);
106 }
107 };
108
109 class SkCoverageDeltaMask {
110 public:
111 // 3 for precision error, 1 for boundary delta (e.g., -SK_Fixed1 at fBounds.fRight + 1)
112 static constexpr int PADDING = 4;
113
114 static constexpr int SIMD_WIDTH = 8;
115 static constexpr int SUITABLE_WIDTH = 32;
116 #ifdef SK_BUILD_FOR_GOOGLE3
117 static constexpr int MAX_MASK_SIZE = 1024; // G3 has 16k stack limit based on -fstack-usage
118 #else
119 static constexpr int MAX_MASK_SIZE = 2048;
120 #endif
121 static constexpr int MAX_SIZE = MAX_MASK_SIZE * (sizeof(SkFixed) + sizeof(SkAlpha));
122
123 // Expand PADDING on both sides, and make it a multiple of SIMD_WIDTH
124 static int ExpandWidth(int width);
125 static bool CanHandle(const SkIRect& bounds); // whether bounds fits into MAX_MASK_SIZE
126 static bool Suitable(const SkIRect& bounds); // CanHandle(bounds) && width <= SUITABLE_WIDTH
127
128 SkCoverageDeltaMask(SkArenaAlloc* alloc, const SkIRect& bounds);
129
top()130 int top() const { return fBounds.fTop; }
bottom()131 int bottom() const { return fBounds.fBottom; }
getMask()132 SkAlpha* getMask() { return fMask; }
getBounds()133 const SkIRect& getBounds() const { return fBounds; }
134
addDelta(int x,int y,SkFixed delta)135 SK_ALWAYS_INLINE void addDelta (int x, int y, SkFixed delta) { this->delta(x, y) += delta; }
delta(int x,int y)136 SK_ALWAYS_INLINE SkFixed& delta (int x, int y) {
137 this->checkX(x);
138 this->checkY(y);
139 return fDeltas[this->index(x, y)];
140 }
141
setAntiRect(int x,int y,int width,int height,SkAlpha leftAlpha,SkAlpha rightAlpha)142 void setAntiRect(int x, int y, int width, int height,
143 SkAlpha leftAlpha, SkAlpha rightAlpha) {
144 fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
145 }
146
prepareSkMask()147 SkMask prepareSkMask() {
148 SkMask mask;
149 mask.fImage = fMask;
150 mask.fBounds = fBounds;
151 mask.fRowBytes = fBounds.width();
152 mask.fFormat = SkMask::kA8_Format;
153 return mask;
154 }
155
156 void convertCoverageToAlpha(bool isEvenOdd, bool isInverse, bool isConvex);
157
158 private:
159 SkIRect fBounds;
160 SkFixed* fDeltaStorage;
161 SkFixed* fDeltas;
162 SkAlpha* fMask;
163 int fExpandedWidth;
164 SkAntiRect fAntiRect;
165
index(int x,int y)166 SK_ALWAYS_INLINE int index(int x, int y) const { return y * fExpandedWidth + x; }
167
checkY(int y)168 void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); }
checkX(int x)169 void checkX(int x) const {
170 SkASSERT(x >= fBounds.fLeft - PADDING && x < fBounds.fRight + PADDING);
171 }
172 };
173
CoverageToAlpha(SkFixed coverage,bool isEvenOdd,bool isInverse)174 static SK_ALWAYS_INLINE SkAlpha CoverageToAlpha(SkFixed coverage, bool isEvenOdd, bool isInverse) {
175 SkAlpha result;
176 if (isEvenOdd) {
177 SkFixed mod17 = coverage & 0x1ffff;
178 SkFixed mod16 = coverage & 0xffff;
179 result = SkTPin(SkAbs32((mod16 << 1) - mod17) >> 8, 0, 255);
180 } else {
181 result = SkTPin(SkAbs32(coverage) >> 8, 0, 255);
182 }
183 return isInverse ? 255 - result : result;
184 }
185
186 struct SkDAARecord {
187 enum class Type {
188 kToBeComputed,
189 kMask,
190 kList,
191 kEmpty
192 } fType;
193
194 SkMask fMask;
195 SkCoverageDeltaList* fList;
196 SkArenaAlloc* fAlloc;
197
SkDAARecordSkDAARecord198 SkDAARecord(SkArenaAlloc* alloc) : fType(Type::kToBeComputed), fAlloc(alloc) {}
199
200 // When the scan converter returns early (e.g., the path is completely out of the clip), we set
201 // the type to empty to signal that the record has been computed and it's empty. This is
202 // required only for DEBUG where we check that the type must not be kToBeComputed after
203 // init-once.
setEmptySkDAARecord204 void setEmpty() { fType = Type::kEmpty; }
SetEmptySkDAARecord205 static inline void SetEmpty(SkDAARecord* record) { // record may be nullptr
206 #ifdef SK_DEBUG
207 // If type != kToBeComputed, then we're in the draw phase and we shouldn't set it to empty
208 // because being empty in one tile does not imply emptiness in other tiles.
209 if (record && record->fType == Type::kToBeComputed) {
210 record->setEmpty();
211 }
212 #endif
213 }
214 };
215
216 template<typename T>
CoverageToAlpha(const T & coverage,bool isEvenOdd,bool isInverse)217 static SK_ALWAYS_INLINE T CoverageToAlpha(const T& coverage, bool isEvenOdd, bool isInverse) {
218 T t0(0), t255(255);
219 T result;
220 if (isEvenOdd) {
221 T mod17 = coverage & 0x1ffff;
222 T mod16 = coverage & 0xffff;
223 result = ((mod16 << 1) - mod17).abs() >> 8;
224 } else {
225 result = coverage.abs() >> 8;
226 }
227 result = T::Min(result, t255);
228 result = T::Max(result, t0);
229 return isInverse ? 255 - result : result;
230 }
231
232 // For convex paths (including inverse mode), the coverage is guaranteed to be
233 // between [-SK_Fixed1, SK_Fixed1] so we can skip isEvenOdd and SkTPin.
ConvexCoverageToAlpha(SkFixed coverage,bool isInverse)234 static SK_ALWAYS_INLINE SkAlpha ConvexCoverageToAlpha(SkFixed coverage, bool isInverse) {
235 SkASSERT(coverage >= -SK_Fixed1 && coverage <= SK_Fixed1);
236 int result = SkAbs32(coverage) >> 8;
237 result -= (result >> 8); // 256 to 255
238 return isInverse ? 255 - result : result;
239 }
240
241 template<typename T>
ConvexCoverageToAlpha(const T & coverage,bool isInverse)242 static SK_ALWAYS_INLINE T ConvexCoverageToAlpha(const T& coverage, bool isInverse) {
243 // allTrue is not implemented
244 // SkASSERT((coverage >= 0).allTrue() && (coverage <= SK_Fixed1).allTrue());
245 T result = coverage.abs() >> 8;
246 result -= (result >> 8); // 256 to 255
247 return isInverse ? 255 - result : result;
248 }
249
250 #endif
251