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 53 int top() const { return fTop; } 54 int bottom() const { return fBottom; } 55 bool forceRLE() const { return fForceRLE; } 56 int count(int y) const { this->checkY(y); return fCounts[y]; } 57 bool sorted(int y) const { this->checkY(y); return fSorted[y]; } 58 59 SK_ALWAYS_INLINE void addDelta(int x, int y, SkFixed delta) { this->push_back(y, {x, delta}); } 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 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 75 const SkAntiRect& getAntiRect() const { return fAntiRect; } 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 92 void checkY(int y) const { SkASSERT(y >= fTop && y < fBottom); } 93 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 129 int top() const { return fBounds.fTop; } 130 int bottom() const { return fBounds.fBottom; } 131 SkAlpha* getMask() { return fMask; } 132 const SkIRect& getBounds() const { return fBounds; } 133 134 SK_ALWAYS_INLINE void addDelta (int x, int y, SkFixed delta) { this->delta(x, y) += delta; } 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 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 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 165 SK_ALWAYS_INLINE int index(int x, int y) const { return y * fExpandedWidth + x; } 166 167 void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); } 168 void checkX(int x) const { 169 SkASSERT(x >= fBounds.fLeft - PADDING && x < fBounds.fRight + PADDING); 170 } 171 }; 172 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 template<typename T> 186 static SK_ALWAYS_INLINE T CoverageToAlpha(const T& coverage, bool isEvenOdd, bool isInverse) { 187 T t0(0), t255(255); 188 T result; 189 if (isEvenOdd) { 190 T mod17 = coverage & 0x1ffff; 191 T mod16 = coverage & 0xffff; 192 result = ((mod16 << 1) - mod17).abs() >> 8; 193 } else { 194 result = coverage.abs() >> 8;; 195 } 196 result = T::Min(result, t255); 197 result = T::Max(result, t0); 198 return isInverse ? 255 - result : result; 199 } 200 201 // For convex paths (including inverse mode), the coverage is guaranteed to be 202 // between [-SK_Fixed1, SK_Fixed1] so we can skip isEvenOdd and SkTPin. 203 static SK_ALWAYS_INLINE SkAlpha ConvexCoverageToAlpha(SkFixed coverage, bool isInverse) { 204 SkASSERT(coverage >= -SK_Fixed1 && coverage <= SK_Fixed1); 205 int result = SkAbs32(coverage) >> 8; 206 result -= (result >> 8); // 256 to 255 207 return isInverse ? 255 - result : result; 208 } 209 210 template<typename T> 211 static SK_ALWAYS_INLINE T ConvexCoverageToAlpha(const T& coverage, bool isInverse) { 212 // allTrue is not implemented 213 // SkASSERT((coverage >= 0).allTrue() && (coverage <= SK_Fixed1).allTrue()); 214 T result = coverage.abs() >> 8; 215 result -= (result >> 8); // 256 to 255 216 return isInverse ? 255 - result : result; 217 } 218 219 #endif 220