• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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, int top, int bottom, bool forceRLE);
52 
top()53     int  top() const { return fTop; }
bottom()54     int  bottom() const { return fBottom; }
forceRLE()55     bool forceRLE() const { return fForceRLE; }
count(int y)56     int  count(int y) const { this->checkY(y); return fCounts[y]; }
sorted(int y)57     bool sorted(int y) const { this->checkY(y); return fSorted[y]; }
58 
addDelta(int x,int y,SkFixed delta)59     SK_ALWAYS_INLINE void addDelta(int x, int y, SkFixed delta) { this->push_back(y, {x, delta}); }
getDelta(int y,int i)60     SK_ALWAYS_INLINE const SkCoverageDelta& getDelta(int y, int i) const {
61         this->checkY(y);
62         SkASSERT(i < fCounts[y]);
63         return fRows[y][i];
64     }
65 
66     // It might be better to sort right before blitting to make the memory hot
sort(int y)67     void sort(int y) {
68         this->checkY(y);
69         if (!fSorted[y]) {
70             SkTQSort(fRows[y], fRows[y] + fCounts[y] - 1);
71             fSorted[y] = true;
72         }
73     }
74 
getAntiRect()75     const SkAntiRect& getAntiRect() const { return fAntiRect; }
setAntiRect(int x,int y,int width,int height,SkAlpha leftAlpha,SkAlpha rightAlpha)76     void setAntiRect(int x, int y, int width, int height,
77             SkAlpha leftAlpha, SkAlpha rightAlpha) {
78         fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
79     }
80 
81 private:
82     SkArenaAlloc*               fAlloc;
83     SkCoverageDelta**           fRows;
84     bool*                       fSorted;
85     int*                        fCounts;
86     int*                        fMaxCounts;
87     int                         fTop;
88     int                         fBottom;
89     SkAntiRect                  fAntiRect;
90     bool                        fForceRLE;
91 
checkY(int y)92     void checkY(int y) const { SkASSERT(y >= fTop && y < fBottom); }
93 
push_back(int y,const SkCoverageDelta & delta)94     SK_ALWAYS_INLINE void push_back(int y, const SkCoverageDelta& delta) {
95         this->checkY(y);
96         if (fCounts[y] == fMaxCounts[y]) {
97             fMaxCounts[y] *= 4;
98             SkCoverageDelta* newRow = fAlloc->makeArrayDefault<SkCoverageDelta>(fMaxCounts[y]);
99             memcpy(newRow, fRows[y], sizeof(SkCoverageDelta) * fCounts[y]);
100             fRows[y] = newRow;
101         }
102         SkASSERT(fCounts[y] < fMaxCounts[y]);
103         fRows[y][fCounts[y]++] = delta;
104         fSorted[y] = fSorted[y] && (fCounts[y] == 1 || delta.fX >= fRows[y][fCounts[y] - 2].fX);
105     }
106 };
107 
108 class SkCoverageDeltaMask {
109 public:
110     // 1 for precision error, 1 for boundary delta (e.g., -SK_Fixed1 at fBounds.fRight + 1)
111     static constexpr int PADDING        = 2;
112 
113     static constexpr int SIMD_WIDTH     = 8;
114     static constexpr int SUITABLE_WIDTH = 32;
115 #ifdef SK_BUILD_FOR_GOOGLE3
116     static constexpr int MAX_MASK_SIZE  = 1024; // G3 has 16k stack limit based on -fstack-usage
117 #else
118     static constexpr int MAX_MASK_SIZE  = 2048;
119 #endif
120     static constexpr int MAX_SIZE       = MAX_MASK_SIZE * (sizeof(SkFixed) + sizeof(SkAlpha));
121 
122     // Expand PADDING on both sides, and make it a multiple of SIMD_WIDTH
123     static int  ExpandWidth(int width);
124     static bool CanHandle(const SkIRect& bounds);   // whether bounds fits into MAX_MASK_SIZE
125     static bool Suitable(const SkIRect& bounds);    // CanHandle(bounds) && width <= SUITABLE_WIDTH
126 
127     SkCoverageDeltaMask(SkArenaAlloc* alloc, const SkIRect& bounds);
128 
top()129     int              top()       const { return fBounds.fTop; }
bottom()130     int              bottom()    const { return fBounds.fBottom; }
getMask()131     SkAlpha*         getMask()         { return fMask; }
getBounds()132     const SkIRect&   getBounds() const { return fBounds; }
133 
addDelta(int x,int y,SkFixed delta)134     SK_ALWAYS_INLINE void addDelta (int x, int y, SkFixed delta) { this->delta(x, y) += delta; }
delta(int x,int y)135     SK_ALWAYS_INLINE SkFixed& delta (int x, int y) {
136         this->checkX(x);
137         this->checkY(y);
138         return fDeltas[this->index(x, y)];
139     }
140 
setAntiRect(int x,int y,int width,int height,SkAlpha leftAlpha,SkAlpha rightAlpha)141     void setAntiRect(int x, int y, int width, int height,
142                             SkAlpha leftAlpha, SkAlpha rightAlpha) {
143         fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
144     }
145 
prepareSkMask()146     SkMask prepareSkMask() {
147         SkMask mask;
148         mask.fImage     = fMask;
149         mask.fBounds    = fBounds;
150         mask.fRowBytes  = fBounds.width();
151         mask.fFormat    = SkMask::kA8_Format;
152         return mask;
153     }
154 
155     void convertCoverageToAlpha(bool isEvenOdd, bool isInverse, bool isConvex);
156 
157 private:
158     SkIRect     fBounds;
159     SkFixed*    fDeltaStorage;
160     SkFixed*    fDeltas;
161     SkAlpha*    fMask;
162     int         fExpandedWidth;
163     SkAntiRect  fAntiRect;
164 
index(int x,int y)165     SK_ALWAYS_INLINE int index(int x, int y) const { return y * fExpandedWidth + x; }
166 
checkY(int y)167     void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); }
checkX(int x)168     void checkX(int x) const {
169         SkASSERT(x >= fBounds.fLeft - PADDING && x < fBounds.fRight + PADDING);
170     }
171 };
172 
CoverageToAlpha(SkFixed coverage,bool isEvenOdd,bool isInverse)173 static SK_ALWAYS_INLINE SkAlpha CoverageToAlpha(SkFixed coverage, bool isEvenOdd, bool isInverse) {
174     SkAlpha result;
175     if (isEvenOdd) {
176         SkFixed mod17 = coverage & 0x1ffff;
177         SkFixed mod16 = coverage & 0xffff;
178         result = SkTPin(SkAbs32((mod16 << 1) - mod17) >> 8, 0, 255);
179     } else {
180         result = SkTPin(SkAbs32(coverage) >> 8, 0, 255);
181     }
182     return isInverse ? 255 - result : result;
183 }
184 
185 struct SkDAARecord {
186     enum class Type {
187         kToBeComputed,
188         kMask,
189         kList
190     } fType;
191 
192     SkMask               fMask;
193     SkCoverageDeltaList* fList;
194     SkArenaAlloc*        fAlloc;
195 
SkDAARecordSkDAARecord196     SkDAARecord(SkArenaAlloc* alloc) : fType(Type::kToBeComputed), fAlloc(alloc) {}
197 };
198 
199 template<typename T>
CoverageToAlpha(const T & coverage,bool isEvenOdd,bool isInverse)200 static SK_ALWAYS_INLINE T CoverageToAlpha(const T&  coverage, bool isEvenOdd, bool isInverse) {
201     T t0(0), t255(255);
202     T result;
203     if (isEvenOdd) {
204         T mod17 = coverage & 0x1ffff;
205         T mod16 = coverage & 0xffff;
206         result = ((mod16 << 1) - mod17).abs() >> 8;
207     } else {
208         result = coverage.abs() >> 8;;
209     }
210     result = T::Min(result, t255);
211     result = T::Max(result, t0);
212     return isInverse ? 255 - result : result;
213 }
214 
215 // For convex paths (including inverse mode), the coverage is guaranteed to be
216 // between [-SK_Fixed1, SK_Fixed1] so we can skip isEvenOdd and SkTPin.
ConvexCoverageToAlpha(SkFixed coverage,bool isInverse)217 static SK_ALWAYS_INLINE SkAlpha ConvexCoverageToAlpha(SkFixed coverage, bool isInverse) {
218     SkASSERT(coverage >= -SK_Fixed1 && coverage <= SK_Fixed1);
219     int result = SkAbs32(coverage) >> 8;
220     result -= (result >> 8); // 256 to 255
221     return isInverse ? 255 - result : result;
222 }
223 
224 template<typename T>
ConvexCoverageToAlpha(const T & coverage,bool isInverse)225 static SK_ALWAYS_INLINE T ConvexCoverageToAlpha(const T& coverage, bool isInverse) {
226     // allTrue is not implemented
227     // SkASSERT((coverage >= 0).allTrue() && (coverage <= SK_Fixed1).allTrue());
228     T result = coverage.abs() >> 8;
229     result -= (result >> 8); // 256 to 255
230     return isInverse ? 255 - result : result;
231 }
232 
233 #endif
234