Line data Source code
1 : /*
2 : * Copyright 2016 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 : #include "SkAnalyticEdge.h"
9 : #include "SkAntiRun.h"
10 : #include "SkAutoMalloc.h"
11 : #include "SkBlitter.h"
12 : #include "SkEdge.h"
13 : #include "SkEdgeBuilder.h"
14 : #include "SkGeometry.h"
15 : #include "SkPath.h"
16 : #include "SkQuadClipper.h"
17 : #include "SkRasterClip.h"
18 : #include "SkRegion.h"
19 : #include "SkScan.h"
20 : #include "SkScanPriv.h"
21 : #include "SkTSort.h"
22 : #include "SkTemplates.h"
23 : #include "SkUtils.h"
24 :
25 : #include "mozilla/Assertions.h"
26 :
27 : ///////////////////////////////////////////////////////////////////////////////
28 :
29 : /*
30 :
31 : The following is a high-level overview of our analytic anti-aliasing
32 : algorithm. We consider a path as a collection of line segments, as
33 : quadratic/cubic curves are converted to small line segments. Without loss of
34 : generality, let's assume that the draw region is [0, W] x [0, H].
35 :
36 : Our algorithm is based on horizontal scan lines (y = c_i) as the previous
37 : sampling-based algorithm did. However, our algorithm uses non-equal-spaced
38 : scan lines, while the previous method always uses equal-spaced scan lines,
39 : such as (y = 1/2 + 0, 1/2 + 1, 1/2 + 2, ...) in the previous non-AA algorithm,
40 : and (y = 1/8 + 1/4, 1/8 + 2/4, 1/8 + 3/4, ...) in the previous
41 : 16-supersampling AA algorithm.
42 :
43 : Our algorithm contains scan lines y = c_i for c_i that is either:
44 :
45 : 1. an integer between [0, H]
46 :
47 : 2. the y value of a line segment endpoint
48 :
49 : 3. the y value of an intersection of two line segments
50 :
51 : For two consecutive scan lines y = c_i, y = c_{i+1}, we analytically computes
52 : the coverage of this horizontal strip of our path on each pixel. This can be
53 : done very efficiently because the strip of our path now only consists of
54 : trapezoids whose top and bottom edges are y = c_i, y = c_{i+1} (this includes
55 : rectangles and triangles as special cases).
56 :
57 : We now describe how the coverage of single pixel is computed against such a
58 : trapezoid. That coverage is essentially the intersection area of a rectangle
59 : (e.g., [0, 1] x [c_i, c_{i+1}]) and our trapezoid. However, that intersection
60 : could be complicated, as shown in the example region A below:
61 :
62 : +-----------\----+
63 : | \ C|
64 : | \ |
65 : \ \ |
66 : |\ A \|
67 : | \ \
68 : | \ |
69 : | B \ |
70 : +----\-----------+
71 :
72 : However, we don't have to compute the area of A directly. Instead, we can
73 : compute the excluded area, which are B and C, quite easily, because they're
74 : just triangles. In fact, we can prove that an excluded region (take B as an
75 : example) is either itself a simple trapezoid (including rectangles, triangles,
76 : and empty regions), or its opposite (the opposite of B is A + C) is a simple
77 : trapezoid. In any case, we can compute its area efficiently.
78 :
79 : In summary, our algorithm has a higher quality because it generates ground-
80 : truth coverages analytically. It is also faster because it has much fewer
81 : unnessasary horizontal scan lines. For example, given a triangle path, the
82 : number of scan lines in our algorithm is only about 3 + H while the
83 : 16-supersampling algorithm has about 4H scan lines.
84 :
85 : */
86 :
87 : ///////////////////////////////////////////////////////////////////////////////
88 :
89 342 : static inline void addAlpha(SkAlpha* alpha, SkAlpha delta) {
90 342 : SkASSERT(*alpha + (int)delta <= 256);
91 342 : *alpha = SkAlphaRuns::CatchOverflow(*alpha + (int)delta);
92 342 : }
93 :
94 4806 : static inline void safelyAddAlpha(SkAlpha* alpha, SkAlpha delta) {
95 4806 : *alpha = SkTMin(0xFF, *alpha + (int)delta);
96 4806 : }
97 :
98 184 : class AdditiveBlitter : public SkBlitter {
99 : public:
100 184 : ~AdditiveBlitter() override {}
101 :
102 : virtual SkBlitter* getRealBlitter(bool forceRealBlitter = false) = 0;
103 :
104 : virtual void blitAntiH(int x, int y, const SkAlpha antialias[], int len) = 0;
105 : virtual void blitAntiH(int x, int y, const SkAlpha alpha) = 0;
106 : virtual void blitAntiH(int x, int y, int width, const SkAlpha alpha) = 0;
107 :
108 0 : void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
109 0 : SkDEBUGFAIL("Please call real blitter's blitAntiH instead.");
110 0 : }
111 :
112 0 : void blitV(int x, int y, int height, SkAlpha alpha) override {
113 0 : SkDEBUGFAIL("Please call real blitter's blitV instead.");
114 0 : }
115 :
116 0 : void blitH(int x, int y, int width) override {
117 0 : SkDEBUGFAIL("Please call real blitter's blitH instead.");
118 0 : }
119 :
120 0 : void blitRect(int x, int y, int width, int height) override {
121 0 : SkDEBUGFAIL("Please call real blitter's blitRect instead.");
122 0 : }
123 :
124 0 : void blitAntiRect(int x, int y, int width, int height,
125 : SkAlpha leftAlpha, SkAlpha rightAlpha) override {
126 0 : SkDEBUGFAIL("Please call real blitter's blitAntiRect instead.");
127 0 : }
128 :
129 : virtual int getWidth() = 0;
130 :
131 : // Flush the additive alpha cache if floor(y) and floor(nextY) is different
132 : // (i.e., we'll start working on a new pixel row).
133 : virtual void flush_if_y_changed(SkFixed y, SkFixed nextY) = 0;
134 : };
135 :
136 : // We need this mask blitter because it significantly accelerates small path filling.
137 : class MaskAdditiveBlitter : public AdditiveBlitter {
138 : public:
139 : MaskAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip,
140 : bool isInverse);
141 6 : ~MaskAdditiveBlitter() override {
142 3 : fRealBlitter->blitMask(fMask, fClipRect);
143 3 : }
144 :
145 : // Most of the time, we still consider this mask blitter as the real blitter
146 : // so we can accelerate blitRect and others. But sometimes we want to return
147 : // the absolute real blitter (e.g., when we fall back to the old code path).
148 3 : SkBlitter* getRealBlitter(bool forceRealBlitter) override {
149 3 : return forceRealBlitter ? fRealBlitter : this;
150 : }
151 :
152 : // Virtual function is slow. So don't use this. Directly add alpha to the mask instead.
153 : void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
154 :
155 : // Allowing following methods are used to blit rectangles during aaa_walk_convex_edges
156 : // Since there aren't many rectangles, we can still bear the slow speed of virtual functions.
157 : void blitAntiH(int x, int y, const SkAlpha alpha) override;
158 : void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
159 : void blitV(int x, int y, int height, SkAlpha alpha) override;
160 : void blitRect(int x, int y, int width, int height) override;
161 : void blitAntiRect(int x, int y, int width, int height,
162 : SkAlpha leftAlpha, SkAlpha rightAlpha) override;
163 :
164 : // The flush is only needed for RLE (RunBasedAdditiveBlitter)
165 0 : void flush_if_y_changed(SkFixed y, SkFixed nextY) override {}
166 :
167 0 : int getWidth() override { return fClipRect.width(); }
168 :
169 187 : static bool canHandleRect(const SkIRect& bounds) {
170 187 : int width = bounds.width();
171 187 : if (width > MaskAdditiveBlitter::kMAX_WIDTH) {
172 169 : return false;
173 : }
174 18 : int64_t rb = SkAlign4(width);
175 : // use 64bits to detect overflow
176 18 : int64_t storage = rb * bounds.height();
177 :
178 18 : return (width <= MaskAdditiveBlitter::kMAX_WIDTH) &&
179 18 : (storage <= MaskAdditiveBlitter::kMAX_STORAGE);
180 : }
181 :
182 : // Return a pointer where pointer[x] corresonds to the alpha of (x, y)
183 3 : inline uint8_t* getRow(int y) {
184 3 : if (y != fY) {
185 3 : fY = y;
186 3 : fRow = fMask.fImage + (y - fMask.fBounds.fTop) * fMask.fRowBytes - fMask.fBounds.fLeft;
187 : }
188 3 : return fRow;
189 : }
190 :
191 : private:
192 : // so we don't try to do very wide things, where the RLE blitter would be faster
193 : static const int kMAX_WIDTH = 32;
194 : static const int kMAX_STORAGE = 1024;
195 :
196 : SkBlitter* fRealBlitter;
197 : SkMask fMask;
198 : SkIRect fClipRect;
199 : // we add 2 because we can write 1 extra byte at either end due to precision error
200 : uint32_t fStorage[(kMAX_STORAGE >> 2) + 2];
201 :
202 : uint8_t* fRow;
203 : int fY;
204 : };
205 :
206 3 : MaskAdditiveBlitter::MaskAdditiveBlitter(
207 3 : SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, bool isInverse) {
208 3 : SkASSERT(canHandleRect(ir));
209 3 : SkASSERT(!isInverse);
210 :
211 3 : fRealBlitter = realBlitter;
212 :
213 3 : fMask.fImage = (uint8_t*)fStorage + 1; // There's 1 extra byte at either end of fStorage
214 3 : fMask.fBounds = ir;
215 3 : fMask.fRowBytes = ir.width();
216 3 : fMask.fFormat = SkMask::kA8_Format;
217 :
218 3 : fY = ir.fTop - 1;
219 3 : fRow = nullptr;
220 :
221 3 : fClipRect = ir;
222 3 : if (!fClipRect.intersect(clip.getBounds())) {
223 0 : SkASSERT(0);
224 0 : fClipRect.setEmpty();
225 : }
226 :
227 3 : memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 2);
228 3 : }
229 :
230 0 : void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
231 0 : SkFAIL("Don't use this; directly add alphas to the mask.");
232 0 : }
233 :
234 0 : void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
235 0 : SkASSERT(x >= fMask.fBounds.fLeft -1);
236 0 : addAlpha(&this->getRow(y)[x], alpha);
237 0 : }
238 :
239 0 : void MaskAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
240 0 : SkASSERT(x >= fMask.fBounds.fLeft -1);
241 0 : uint8_t* row = this->getRow(y);
242 0 : for (int i = 0; i < width; ++i) {
243 0 : addAlpha(&row[x + i], alpha);
244 : }
245 0 : }
246 :
247 6 : void MaskAdditiveBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
248 6 : if (alpha == 0) {
249 6 : return;
250 : }
251 0 : SkASSERT(x >= fMask.fBounds.fLeft -1);
252 : // This must be called as if this is a real blitter.
253 : // So we directly set alpha rather than adding it.
254 0 : uint8_t* row = this->getRow(y);
255 0 : for (int i = 0; i < height; ++i) {
256 0 : row[x] = alpha;
257 0 : row += fMask.fRowBytes;
258 : }
259 : }
260 :
261 3 : void MaskAdditiveBlitter::blitRect(int x, int y, int width, int height) {
262 3 : SkASSERT(x >= fMask.fBounds.fLeft -1);
263 : // This must be called as if this is a real blitter.
264 : // So we directly set alpha rather than adding it.
265 3 : uint8_t* row = this->getRow(y);
266 114 : for (int i = 0; i < height; ++i) {
267 111 : memset(row + x, 0xFF, width);
268 111 : row += fMask.fRowBytes;
269 : }
270 3 : }
271 :
272 3 : void MaskAdditiveBlitter::blitAntiRect(int x, int y, int width, int height,
273 : SkAlpha leftAlpha, SkAlpha rightAlpha) {
274 3 : blitV(x, y, height, leftAlpha);
275 3 : blitV(x + 1 + width, y, height, rightAlpha);
276 3 : blitRect(x + 1, y, width, height);
277 3 : }
278 :
279 : class RunBasedAdditiveBlitter : public AdditiveBlitter {
280 : public:
281 : RunBasedAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip,
282 : bool isInverse);
283 : ~RunBasedAdditiveBlitter() override;
284 :
285 : SkBlitter* getRealBlitter(bool forceRealBlitter) override;
286 :
287 : void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
288 : void blitAntiH(int x, int y, const SkAlpha alpha) override;
289 : void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
290 :
291 : int getWidth() override;
292 :
293 2703 : void flush_if_y_changed(SkFixed y, SkFixed nextY) override {
294 2703 : if (SkFixedFloorToInt(y) != SkFixedFloorToInt(nextY)) {
295 2275 : this->flush();
296 : }
297 2703 : }
298 :
299 : protected:
300 : SkBlitter* fRealBlitter;
301 :
302 : /// Current y coordinate
303 : int fCurrY;
304 : /// Widest row of region to be blitted
305 : int fWidth;
306 : /// Leftmost x coordinate in any row
307 : int fLeft;
308 : /// Initial y coordinate (top of bounds).
309 : int fTop;
310 :
311 : // The next three variables are used to track a circular buffer that
312 : // contains the values used in SkAlphaRuns. These variables should only
313 : // ever be updated in advanceRuns(), and fRuns should always point to
314 : // a valid SkAlphaRuns...
315 : int fRunsToBuffer;
316 : void* fRunsBuffer;
317 : int fCurrentRun;
318 : SkAlphaRuns fRuns;
319 :
320 : int fOffsetX;
321 :
322 5681 : inline bool check(int x, int width) const {
323 : #ifdef SK_DEBUG
324 5681 : if (x < 0 || x + width > fWidth) {
325 : // SkDebugf("Ignore x = %d, width = %d\n", x, width);
326 : }
327 : #endif
328 5681 : return (x >= 0 && x + width <= fWidth);
329 : }
330 :
331 : // extra one to store the zero at the end
332 2160 : inline int getRunsSz() const { return (fWidth + 1 + (fWidth + 2)/2) * sizeof(int16_t); }
333 :
334 : // This function updates the fRuns variable to point to the next buffer space
335 : // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun
336 : // and resets fRuns to point to an empty scanline.
337 1979 : inline void advanceRuns() {
338 1979 : const size_t kRunsSz = this->getRunsSz();
339 1979 : fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer;
340 1979 : fRuns.fRuns = reinterpret_cast<int16_t*>(
341 1979 : reinterpret_cast<uint8_t*>(fRunsBuffer) + fCurrentRun * kRunsSz);
342 1979 : fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1);
343 1979 : fRuns.reset(fWidth);
344 1979 : }
345 :
346 : // Blitting 0xFF and 0 is much faster so we snap alphas close to them
347 5856 : inline SkAlpha snapAlpha(SkAlpha alpha) {
348 5856 : return alpha > 247 ? 0xFF : alpha < 8 ? 0 : alpha;
349 : }
350 :
351 4254 : inline void flush() {
352 4254 : if (fCurrY >= fTop) {
353 1798 : SkASSERT(fCurrentRun < fRunsToBuffer);
354 7654 : for (int x = 0; fRuns.fRuns[x]; x += fRuns.fRuns[x]) {
355 : // It seems that blitting 255 or 0 is much faster than blitting 254 or 1
356 5856 : fRuns.fAlpha[x] = snapAlpha(fRuns.fAlpha[x]);
357 : }
358 1798 : if (!fRuns.empty()) {
359 : // SkDEBUGCODE(fRuns.dump();)
360 1798 : fRealBlitter->blitAntiH(fLeft, fCurrY, fRuns.fAlpha, fRuns.fRuns);
361 1798 : this->advanceRuns();
362 1798 : fOffsetX = 0;
363 : }
364 1798 : fCurrY = fTop - 1;
365 : }
366 4254 : }
367 :
368 5681 : inline void checkY(int y) {
369 5681 : if (y != fCurrY) {
370 1798 : this->flush();
371 1798 : fCurrY = y;
372 : }
373 5681 : }
374 : };
375 :
376 181 : RunBasedAdditiveBlitter::RunBasedAdditiveBlitter(
377 181 : SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip, bool isInverse) {
378 181 : fRealBlitter = realBlitter;
379 :
380 : SkIRect sectBounds;
381 181 : if (isInverse) {
382 : // We use the clip bounds instead of the ir, since we may be asked to
383 : //draw outside of the rect when we're a inverse filltype
384 0 : sectBounds = clip.getBounds();
385 : } else {
386 181 : if (!sectBounds.intersect(ir, clip.getBounds())) {
387 0 : sectBounds.setEmpty();
388 : }
389 : }
390 :
391 181 : const int left = sectBounds.left();
392 181 : const int right = sectBounds.right();
393 :
394 181 : fLeft = left;
395 181 : fWidth = right - left;
396 181 : fTop = sectBounds.top();
397 181 : fCurrY = fTop - 1;
398 :
399 181 : fRunsToBuffer = realBlitter->requestRowsPreserved();
400 181 : fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz());
401 181 : fCurrentRun = -1;
402 :
403 181 : this->advanceRuns();
404 :
405 181 : fOffsetX = 0;
406 181 : }
407 :
408 362 : RunBasedAdditiveBlitter::~RunBasedAdditiveBlitter() {
409 181 : this->flush();
410 181 : }
411 :
412 1678 : SkBlitter* RunBasedAdditiveBlitter::getRealBlitter(bool forceRealBlitter) {
413 1678 : return fRealBlitter;
414 : }
415 :
416 98 : void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
417 98 : checkY(y);
418 98 : x -= fLeft;
419 :
420 98 : if (x < 0) {
421 0 : len += x;
422 0 : antialias -= x;
423 0 : x = 0;
424 : }
425 98 : len = SkTMin(len, fWidth - x);
426 98 : SkASSERT(check(x, len));
427 :
428 98 : if (x < fOffsetX) {
429 28 : fOffsetX = 0;
430 : }
431 :
432 196 : fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run
433 440 : for (int i = 0; i < len; i += fRuns.fRuns[x + i]) {
434 528 : for (int j = 1; j < fRuns.fRuns[x + i]; j++) {
435 186 : fRuns.fRuns[x + i + j] = 1;
436 186 : fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i];
437 : }
438 342 : fRuns.fRuns[x + i] = 1;
439 : }
440 440 : for (int i = 0; i < len; ++i) {
441 342 : addAlpha(&fRuns.fAlpha[x + i], antialias[i]);
442 : }
443 98 : }
444 672 : void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
445 672 : checkY(y);
446 672 : x -= fLeft;
447 :
448 672 : if (x < fOffsetX) {
449 122 : fOffsetX = 0;
450 : }
451 :
452 672 : if (this->check(x, 1)) {
453 1344 : fOffsetX = fRuns.add(x, 0, 1, 0, alpha, fOffsetX);
454 : }
455 672 : }
456 :
457 318 : void RunBasedAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
458 318 : checkY(y);
459 318 : x -= fLeft;
460 :
461 318 : if (x < fOffsetX) {
462 26 : fOffsetX = 0;
463 : }
464 :
465 318 : if (this->check(x, width)) {
466 636 : fOffsetX = fRuns.add(x, 0, width, 0, alpha, fOffsetX);
467 : }
468 318 : }
469 :
470 0 : int RunBasedAdditiveBlitter::getWidth() { return fWidth; }
471 :
472 : // This exists specifically for concave path filling.
473 : // In those cases, we can easily accumulate alpha greater than 0xFF.
474 39 : class SafeRLEAdditiveBlitter : public RunBasedAdditiveBlitter {
475 : public:
476 39 : SafeRLEAdditiveBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkRegion& clip,
477 39 : bool isInverse) : RunBasedAdditiveBlitter(realBlitter, ir, clip, isInverse) {}
478 :
479 : void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
480 : void blitAntiH(int x, int y, const SkAlpha alpha) override;
481 : void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
482 : };
483 :
484 16 : void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
485 16 : checkY(y);
486 16 : x -= fLeft;
487 :
488 16 : if (x < 0) {
489 0 : len += x;
490 0 : antialias -= x;
491 0 : x = 0;
492 : }
493 16 : len = SkTMin(len, fWidth - x);
494 16 : SkASSERT(check(x, len));
495 :
496 16 : if (x < fOffsetX) {
497 4 : fOffsetX = 0;
498 : }
499 :
500 32 : fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run
501 74 : for (int i = 0; i < len; i += fRuns.fRuns[x + i]) {
502 93 : for (int j = 1; j < fRuns.fRuns[x + i]; j++) {
503 35 : fRuns.fRuns[x + i + j] = 1;
504 35 : fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i];
505 : }
506 58 : fRuns.fRuns[x + i] = 1;
507 : }
508 74 : for (int i = 0; i < len; ++i) {
509 58 : safelyAddAlpha(&fRuns.fAlpha[x + i], antialias[i]);
510 : }
511 16 : }
512 :
513 1486 : void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
514 1486 : checkY(y);
515 1486 : x -= fLeft;
516 :
517 1486 : if (x < fOffsetX) {
518 181 : fOffsetX = 0;
519 : }
520 :
521 1486 : if (check(x, 1)) {
522 : // Break the run
523 2972 : fOffsetX = fRuns.add(x, 0, 1, 0, 0, fOffsetX);
524 1486 : safelyAddAlpha(&fRuns.fAlpha[x], alpha);
525 : }
526 1486 : }
527 :
528 3091 : void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
529 3091 : checkY(y);
530 3091 : x -= fLeft;
531 :
532 3091 : if (x < fOffsetX) {
533 131 : fOffsetX = 0;
534 : }
535 :
536 3091 : if (check(x, width)) {
537 : // Break the run
538 6182 : fOffsetX = fRuns.add(x, 0, width, 0, 0, fOffsetX);
539 6353 : for(int i = x; i < x + width; i += fRuns.fRuns[i]) {
540 3262 : safelyAddAlpha(&fRuns.fAlpha[i], alpha);
541 : }
542 : }
543 3091 : }
544 :
545 : ///////////////////////////////////////////////////////////////////////////////
546 :
547 : // Return the alpha of a trapezoid whose height is 1
548 1496 : static inline SkAlpha trapezoidToAlpha(SkFixed l1, SkFixed l2) {
549 1496 : SkASSERT(l1 >= 0 && l2 >= 0);
550 1496 : return (l1 + l2) >> 9;
551 : }
552 :
553 : // The alpha of right-triangle (a, a*b), in 16 bits
554 1776 : static inline SkFixed partialTriangleToAlpha16(SkFixed a, SkFixed b) {
555 1776 : SkASSERT(a <= SK_Fixed1);
556 : // SkFixedMul(SkFixedMul(a, a), b) >> 1
557 : // return ((((a >> 8) * (a >> 8)) >> 8) * (b >> 8)) >> 1;
558 1776 : return (a >> 11) * (a >> 11) * (b >> 11);
559 : }
560 :
561 : // The alpha of right-triangle (a, a*b)
562 1776 : static inline SkAlpha partialTriangleToAlpha(SkFixed a, SkFixed b) {
563 1776 : return partialTriangleToAlpha16(a, b) >> 8;
564 : }
565 :
566 3310 : static inline SkAlpha getPartialAlpha(SkAlpha alpha, SkFixed partialHeight) {
567 3310 : return SkToU8(SkFixedRoundToInt(alpha * partialHeight));
568 : }
569 :
570 1132 : static inline SkAlpha getPartialAlpha(SkAlpha alpha, SkAlpha fullAlpha) {
571 1132 : return ((uint16_t)alpha * fullAlpha) >> 8;
572 : }
573 :
574 : // For SkFixed that's close to SK_Fixed1, we can't convert it to alpha by just shifting right.
575 : // For example, when f = SK_Fixed1, right shifting 8 will get 256, but we need 255.
576 : // This is rarely the problem so we'll only use this for blitting rectangles.
577 2842 : static inline SkAlpha f2a(SkFixed f) {
578 2842 : SkASSERT(f <= SK_Fixed1);
579 2842 : return getPartialAlpha(0xFF, f);
580 : }
581 :
582 : // Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1),
583 : // approximate (very coarsely) the x coordinate of the intersection.
584 0 : static inline SkFixed approximateIntersection(SkFixed l1, SkFixed r1, SkFixed l2, SkFixed r2) {
585 0 : if (l1 > r1) { SkTSwap(l1, r1); }
586 0 : if (l2 > r2) { SkTSwap(l2, r2); }
587 0 : return (SkTMax(l1, l2) + SkTMin(r1, r2)) >> 1;
588 : }
589 :
590 : // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0]
591 162 : static inline void computeAlphaAboveLine(SkAlpha* alphas, SkFixed l, SkFixed r,
592 : SkFixed dY, SkAlpha fullAlpha) {
593 162 : SkASSERT(l <= r);
594 162 : SkASSERT(l >> 16 == 0);
595 162 : int R = SkFixedCeilToInt(r);
596 162 : if (R == 0) {
597 73 : return;
598 89 : } else if (R == 1) {
599 0 : alphas[0] = getPartialAlpha(((R << 17) - l - r) >> 9, fullAlpha);
600 : } else {
601 89 : SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle
602 89 : SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle
603 89 : SkFixed firstH = SkFixedMul(first, dY); // vertical edge of the left-most triangle
604 89 : alphas[0] = SkFixedMul(first, firstH) >> 9; // triangle alpha
605 89 : SkFixed alpha16 = firstH + (dY >> 1); // rectangle plus triangle
606 209 : for (int i = 1; i < R - 1; ++i) {
607 120 : alphas[i] = alpha16 >> 8;
608 120 : alpha16 += dY;
609 : }
610 89 : alphas[R - 1] = fullAlpha - partialTriangleToAlpha(last, dY);
611 : }
612 : }
613 :
614 : // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0]
615 162 : static inline void computeAlphaBelowLine(
616 : SkAlpha* alphas, SkFixed l, SkFixed r, SkFixed dY, SkAlpha fullAlpha) {
617 162 : SkASSERT(l <= r);
618 162 : SkASSERT(l >> 16 == 0);
619 162 : int R = SkFixedCeilToInt(r);
620 162 : if (R == 0) {
621 89 : return;
622 73 : } else if (R == 1) {
623 0 : alphas[0] = getPartialAlpha(trapezoidToAlpha(l, r), fullAlpha);
624 : } else {
625 73 : SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle
626 73 : SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle
627 73 : SkFixed lastH = SkFixedMul(last, dY); // vertical edge of the right-most triangle
628 73 : alphas[R-1] = SkFixedMul(last, lastH) >> 9; // triangle alpha
629 73 : SkFixed alpha16 = lastH + (dY >> 1); // rectangle plus triangle
630 175 : for (int i = R - 2; i > 0; i--) {
631 102 : alphas[i] = alpha16 >> 8;
632 102 : alpha16 += dY;
633 : }
634 73 : alphas[0] = fullAlpha - partialTriangleToAlpha(first, dY);
635 : }
636 : }
637 :
638 : // Note that if fullAlpha != 0xFF, we'll multiply alpha by fullAlpha
639 : static SK_ALWAYS_INLINE void blit_single_alpha(AdditiveBlitter* blitter, int y, int x,
640 : SkAlpha alpha, SkAlpha fullAlpha, SkAlpha* maskRow,
641 : bool isUsingMask, bool noRealBlitter, bool needSafeCheck) {
642 1496 : if (isUsingMask) {
643 0 : if (fullAlpha == 0xFF && !noRealBlitter) { // noRealBlitter is needed for concave paths
644 0 : maskRow[x] = alpha;
645 0 : } else if (needSafeCheck) {
646 0 : safelyAddAlpha(&maskRow[x], getPartialAlpha(alpha, fullAlpha));
647 : } else {
648 0 : addAlpha(&maskRow[x], getPartialAlpha(alpha, fullAlpha));
649 : }
650 : } else {
651 1496 : if (fullAlpha == 0xFF && !noRealBlitter) {
652 364 : blitter->getRealBlitter()->blitV(x, y, 1, alpha);
653 : } else {
654 1132 : blitter->blitAntiH(x, y, getPartialAlpha(alpha, fullAlpha));
655 : }
656 : }
657 : }
658 :
659 : static SK_ALWAYS_INLINE void blit_two_alphas(AdditiveBlitter* blitter, int y, int x,
660 : SkAlpha a1, SkAlpha a2, SkAlpha fullAlpha, SkAlpha* maskRow,
661 : bool isUsingMask, bool noRealBlitter, bool needSafeCheck) {
662 807 : if (isUsingMask) {
663 0 : if (needSafeCheck) {
664 0 : safelyAddAlpha(&maskRow[x], a1);
665 0 : safelyAddAlpha(&maskRow[x + 1], a2);
666 : } else {
667 0 : addAlpha(&maskRow[x], a1);
668 0 : addAlpha(&maskRow[x + 1], a2);
669 : }
670 : } else {
671 807 : if (fullAlpha == 0xFF && !noRealBlitter) {
672 294 : blitter->getRealBlitter()->blitAntiH2(x, y, a1, a2);
673 : } else {
674 513 : blitter->blitAntiH(x, y, a1);
675 513 : blitter->blitAntiH(x + 1, y, a2);
676 : }
677 : }
678 : }
679 :
680 : // It's important that this is inline. Otherwise it'll be much slower.
681 : static SK_ALWAYS_INLINE void blit_full_alpha(AdditiveBlitter* blitter, int y, int x, int len,
682 : SkAlpha fullAlpha, SkAlpha* maskRow, bool isUsingMask,
683 : bool noRealBlitter, bool needSafeCheck) {
684 4239 : if (isUsingMask) {
685 0 : for (int i = 0; i < len; ++i) {
686 0 : if (needSafeCheck) {
687 0 : safelyAddAlpha(&maskRow[x + i], fullAlpha);
688 : } else {
689 0 : addAlpha(&maskRow[x + i], fullAlpha);
690 : }
691 : }
692 : } else {
693 4239 : if (fullAlpha == 0xFF && !noRealBlitter) {
694 842 : blitter->getRealBlitter()->blitH(x, y, len);
695 : } else {
696 3397 : blitter->blitAntiH(x, y, len, fullAlpha);
697 : }
698 : }
699 : }
700 :
701 162 : static void blit_aaa_trapezoid_row(AdditiveBlitter* blitter, int y,
702 : SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr,
703 : SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha, SkAlpha* maskRow,
704 : bool isUsingMask, bool noRealBlitter, bool needSafeCheck) {
705 162 : int L = SkFixedFloorToInt(ul), R = SkFixedCeilToInt(lr);
706 162 : int len = R - L;
707 :
708 162 : if (len == 1) {
709 0 : SkAlpha alpha = trapezoidToAlpha(ur - ul, lr - ll);
710 0 : blit_single_alpha(blitter, y, L, alpha, fullAlpha, maskRow, isUsingMask, noRealBlitter,
711 : needSafeCheck);
712 0 : return;
713 : }
714 :
715 : // SkDebugf("y = %d, len = %d, ul = %f, ur = %f, ll = %f, lr = %f\n", y, len,
716 : // SkFixedToFloat(ul), SkFixedToFloat(ur), SkFixedToFloat(ll), SkFixedToFloat(lr));
717 :
718 162 : const int kQuickLen = 31;
719 : // This is faster than SkAutoSMalloc<1024>
720 : char quickMemory[(sizeof(SkAlpha) * 2 + sizeof(int16_t)) * (kQuickLen + 1)];
721 : SkAlpha* alphas;
722 :
723 162 : if (len <= kQuickLen) {
724 162 : alphas = (SkAlpha*)quickMemory;
725 : } else {
726 0 : alphas = new SkAlpha[(len + 1) * (sizeof(SkAlpha) * 2 + sizeof(int16_t))];
727 : }
728 :
729 162 : SkAlpha* tempAlphas = alphas + len + 1;
730 162 : int16_t* runs = (int16_t*)(alphas + (len + 1) * 2);
731 :
732 708 : for (int i = 0; i < len; ++i) {
733 546 : runs[i] = 1;
734 546 : alphas[i] = fullAlpha;
735 : }
736 162 : runs[len] = 0;
737 :
738 162 : int uL = SkFixedFloorToInt(ul);
739 162 : int lL = SkFixedCeilToInt(ll);
740 162 : if (uL + 2 == lL) { // We only need to compute two triangles, accelerate this special case
741 0 : SkFixed first = SkIntToFixed(uL) + SK_Fixed1 - ul;
742 0 : SkFixed second = ll - ul - first;
743 0 : SkAlpha a1 = fullAlpha - partialTriangleToAlpha(first, lDY);
744 0 : SkAlpha a2 = partialTriangleToAlpha(second, lDY);
745 0 : alphas[0] = alphas[0] > a1 ? alphas[0] - a1 : 0;
746 0 : alphas[1] = alphas[1] > a2 ? alphas[1] - a2 : 0;
747 : } else {
748 162 : computeAlphaBelowLine(tempAlphas + uL - L, ul - SkIntToFixed(uL), ll - SkIntToFixed(uL),
749 162 : lDY, fullAlpha);
750 410 : for (int i = uL; i < lL; ++i) {
751 248 : if (alphas[i - L] > tempAlphas[i - L]) {
752 217 : alphas[i - L] -= tempAlphas[i - L];
753 : } else {
754 31 : alphas[i - L] = 0;
755 : }
756 : }
757 : }
758 :
759 162 : int uR = SkFixedFloorToInt(ur);
760 162 : int lR = SkFixedCeilToInt(lr);
761 162 : if (uR + 2 == lR) { // We only need to compute two triangles, accelerate this special case
762 0 : SkFixed first = SkIntToFixed(uR) + SK_Fixed1 - ur;
763 0 : SkFixed second = lr - ur - first;
764 0 : SkAlpha a1 = partialTriangleToAlpha(first, rDY);
765 0 : SkAlpha a2 = fullAlpha - partialTriangleToAlpha(second, rDY);
766 0 : alphas[len-2] = alphas[len-2] > a1 ? alphas[len-2] - a1 : 0;
767 0 : alphas[len-1] = alphas[len-1] > a2 ? alphas[len-1] - a2 : 0;
768 : } else {
769 162 : computeAlphaAboveLine(tempAlphas + uR - L, ur - SkIntToFixed(uR), lr - SkIntToFixed(uR),
770 162 : rDY, fullAlpha);
771 460 : for (int i = uR; i < lR; ++i) {
772 298 : if (alphas[i - L] > tempAlphas[i - L]) {
773 265 : alphas[i - L] -= tempAlphas[i - L];
774 : } else {
775 33 : alphas[i - L] = 0;
776 : }
777 : }
778 : }
779 :
780 162 : if (isUsingMask) {
781 0 : for (int i = 0; i < len; ++i) {
782 0 : if (needSafeCheck) {
783 0 : safelyAddAlpha(&maskRow[L + i], alphas[i]);
784 : } else {
785 0 : addAlpha(&maskRow[L + i], alphas[i]);
786 : }
787 : }
788 : } else {
789 162 : if (fullAlpha == 0xFF && !noRealBlitter) {
790 : // Real blitter is faster than RunBasedAdditiveBlitter
791 48 : blitter->getRealBlitter()->blitAntiH(L, y, alphas, runs);
792 : } else {
793 114 : blitter->blitAntiH(L, y, alphas, len);
794 : }
795 : }
796 :
797 162 : if (len > kQuickLen) {
798 0 : delete [] alphas;
799 : }
800 : }
801 :
802 : static SK_ALWAYS_INLINE void blit_trapezoid_row(AdditiveBlitter* blitter, int y,
803 : SkFixed ul, SkFixed ur, SkFixed ll, SkFixed lr,
804 : SkFixed lDY, SkFixed rDY, SkAlpha fullAlpha,
805 : SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter = false,
806 : bool needSafeCheck = false) {
807 4272 : SkASSERT(lDY >= 0 && rDY >= 0); // We should only send in the absolte value
808 :
809 4272 : if (ul > ur) {
810 : #ifdef SK_DEBUG
811 : // SkDebugf("ul = %f > ur = %f!\n", SkFixedToFloat(ul), SkFixedToFloat(ur));
812 : #endif
813 : return;
814 : }
815 :
816 : // Edge crosses. Approximate it. This should only happend due to precision limit,
817 : // so the approximation could be very coarse.
818 4272 : if (ll > lr) {
819 : #ifdef SK_DEBUG
820 : // SkDebugf("approximate intersection: %d %f %f\n", y,
821 : // SkFixedToFloat(ll), SkFixedToFloat(lr));
822 : #endif
823 0 : ll = lr = approximateIntersection(ul, ll, ur, lr);
824 : }
825 :
826 4272 : if (ul == ur && ll == lr) {
827 : return; // empty trapzoid
828 : }
829 :
830 : // We're going to use the left line ul-ll and the rite line ur-lr
831 : // to exclude the area that's not covered by the path.
832 : // Swapping (ul, ll) or (ur, lr) won't affect that exclusion
833 : // so we'll do that for simplicity.
834 4272 : if (ul > ll) { SkTSwap(ul, ll); }
835 4272 : if (ur > lr) { SkTSwap(ur, lr); }
836 :
837 4272 : SkFixed joinLeft = SkFixedCeilToFixed(ll);
838 4272 : SkFixed joinRite = SkFixedFloorToFixed(ur);
839 4272 : if (joinLeft <= joinRite) { // There's a rect from joinLeft to joinRite that we can blit
840 4272 : if (ul < joinLeft) {
841 1139 : int len = SkFixedCeilToInt(joinLeft - ul);
842 1139 : if (len == 1) {
843 702 : SkAlpha alpha = trapezoidToAlpha(joinLeft - ul, joinLeft - ll);
844 702 : blit_single_alpha(blitter, y, ul >> 16, alpha, fullAlpha, maskRow, isUsingMask,
845 : noRealBlitter, needSafeCheck);
846 437 : } else if (len == 2) {
847 364 : SkFixed first = joinLeft - SK_Fixed1 - ul;
848 364 : SkFixed second = ll - ul - first;
849 364 : SkAlpha a1 = partialTriangleToAlpha(first, lDY);
850 364 : SkAlpha a2 = fullAlpha - partialTriangleToAlpha(second, lDY);
851 364 : blit_two_alphas(blitter, y, ul >> 16, a1, a2, fullAlpha, maskRow, isUsingMask,
852 : noRealBlitter, needSafeCheck);
853 : } else {
854 73 : blit_aaa_trapezoid_row(blitter, y, ul, joinLeft, ll, joinLeft, lDY, SK_MaxS32,
855 : fullAlpha, maskRow, isUsingMask, noRealBlitter,
856 73 : needSafeCheck);
857 : }
858 : }
859 : // SkAAClip requires that we blit from left to right.
860 : // Hence we must blit [ul, joinLeft] before blitting [joinLeft, joinRite]
861 4272 : if (joinLeft < joinRite) {
862 8478 : blit_full_alpha(blitter, y, SkFixedFloorToInt(joinLeft),
863 4239 : SkFixedFloorToInt(joinRite - joinLeft),
864 : fullAlpha, maskRow, isUsingMask, noRealBlitter, needSafeCheck);
865 : }
866 4272 : if (lr > joinRite) {
867 1326 : int len = SkFixedCeilToInt(lr - joinRite);
868 1326 : if (len == 1) {
869 794 : SkAlpha alpha = trapezoidToAlpha(ur - joinRite, lr - joinRite);
870 794 : blit_single_alpha(blitter, y, joinRite >> 16, alpha, fullAlpha, maskRow,
871 : isUsingMask, noRealBlitter, needSafeCheck);
872 532 : } else if (len == 2) {
873 443 : SkFixed first = joinRite + SK_Fixed1 - ur;
874 443 : SkFixed second = lr - ur - first;
875 443 : SkAlpha a1 = fullAlpha - partialTriangleToAlpha(first, rDY);
876 443 : SkAlpha a2 = partialTriangleToAlpha(second, rDY);
877 443 : blit_two_alphas(blitter, y, joinRite >> 16, a1, a2, fullAlpha, maskRow,
878 : isUsingMask, noRealBlitter, needSafeCheck);
879 : } else {
880 89 : blit_aaa_trapezoid_row(blitter, y, joinRite, ur, joinRite, lr, SK_MaxS32, rDY,
881 : fullAlpha, maskRow, isUsingMask, noRealBlitter,
882 89 : needSafeCheck);
883 : }
884 : }
885 : } else {
886 0 : blit_aaa_trapezoid_row(blitter, y, ul, ur, ll, lr, lDY, rDY, fullAlpha, maskRow,
887 0 : isUsingMask, noRealBlitter, needSafeCheck);
888 : }
889 : }
890 :
891 : ///////////////////////////////////////////////////////////////////////////////
892 :
893 1036 : static bool operator<(const SkAnalyticEdge& a, const SkAnalyticEdge& b) {
894 1036 : int valuea = a.fUpperY;
895 1036 : int valueb = b.fUpperY;
896 :
897 1036 : if (valuea == valueb) {
898 489 : valuea = a.fX;
899 489 : valueb = b.fX;
900 : }
901 :
902 1036 : if (valuea == valueb) {
903 13 : valuea = a.fDX;
904 13 : valueb = b.fDX;
905 : }
906 :
907 1036 : return valuea < valueb;
908 : }
909 :
910 177 : static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) {
911 177 : SkTQSort(list, list + count - 1);
912 :
913 : // now make the edges linked in sorted order
914 596 : for (int i = 1; i < count; ++i) {
915 419 : list[i - 1]->fNext = list[i];
916 419 : list[i]->fPrev = list[i - 1];
917 : }
918 :
919 177 : *last = list[count - 1];
920 177 : return list[0];
921 : }
922 :
923 : #ifdef SK_DEBUG
924 145 : static void validate_sort(const SkAnalyticEdge* edge) {
925 145 : SkFixed y = SkIntToFixed(-32768);
926 :
927 845 : while (edge->fUpperY != SK_MaxS32) {
928 350 : edge->validate();
929 350 : SkASSERT(y <= edge->fUpperY);
930 :
931 350 : y = edge->fUpperY;
932 350 : edge = (SkAnalyticEdge*)edge->fNext;
933 : }
934 145 : }
935 : #else
936 : #define validate_sort(edge)
937 : #endif
938 :
939 : // return true if we're done with this edge
940 731 : static bool update_edge(SkAnalyticEdge* edge, SkFixed last_y) {
941 731 : if (last_y >= edge->fLowerY) {
942 731 : if (edge->fCurveCount < 0) {
943 526 : if (static_cast<SkAnalyticCubicEdge*>(edge)->updateCubic()) {
944 526 : return false;
945 : }
946 205 : } else if (edge->fCurveCount > 0) {
947 0 : if (static_cast<SkAnalyticQuadraticEdge*>(edge)->updateQuadratic()) {
948 0 : return false;
949 : }
950 : }
951 205 : return true;
952 : }
953 0 : SkASSERT(false);
954 0 : return false;
955 : }
956 :
957 : // For an edge, we consider it smooth if the Dx doesn't change much, and Dy is large enough
958 : // For curves that are updating, the Dx is not changing much if fQDx/fCDx and fQDy/fCDy are
959 : // relatively large compared to fQDDx/QCDDx and fQDDy/fCDDy
960 277 : static inline bool isSmoothEnough(SkAnalyticEdge* thisEdge, SkAnalyticEdge* nextEdge, int stop_y) {
961 277 : if (thisEdge->fCurveCount < 0) {
962 225 : const SkCubicEdge& cEdge = static_cast<SkAnalyticCubicEdge*>(thisEdge)->fCEdge;
963 225 : int ddshift = cEdge.fCurveShift;
964 406 : return SkAbs32(cEdge.fCDx) >> 1 >= SkAbs32(cEdge.fCDDx) >> ddshift &&
965 398 : SkAbs32(cEdge.fCDy) >> 1 >= SkAbs32(cEdge.fCDDy) >> ddshift &&
966 : // current Dy is (fCDy - (fCDDy >> ddshift)) >> dshift
967 398 : (cEdge.fCDy - (cEdge.fCDDy >> ddshift)) >> cEdge.fCubicDShift >= SK_Fixed1;
968 52 : } else if (thisEdge->fCurveCount > 0) {
969 0 : const SkQuadraticEdge& qEdge = static_cast<SkAnalyticQuadraticEdge*>(thisEdge)->fQEdge;
970 0 : return SkAbs32(qEdge.fQDx) >> 1 >= SkAbs32(qEdge.fQDDx) &&
971 0 : SkAbs32(qEdge.fQDy) >> 1 >= SkAbs32(qEdge.fQDDy) &&
972 : // current Dy is (fQDy - fQDDy) >> shift
973 0 : (qEdge.fQDy - qEdge.fQDDy) >> qEdge.fCurveShift
974 0 : >= SK_Fixed1;
975 : }
976 98 : return SkAbs32(nextEdge->fDX - thisEdge->fDX) <= SK_Fixed1 && // DDx should be small
977 98 : nextEdge->fLowerY - nextEdge->fUpperY >= SK_Fixed1; // Dy should be large
978 : }
979 :
980 : // Check if the leftE and riteE are changing smoothly in terms of fDX.
981 : // If yes, we can later skip the fractional y and directly jump to integer y.
982 483 : static inline bool isSmoothEnough(SkAnalyticEdge* leftE, SkAnalyticEdge* riteE,
983 : SkAnalyticEdge* currE, int stop_y) {
984 483 : if (currE->fUpperY >= stop_y << 16) {
985 274 : return false; // We're at the end so we won't skip anything
986 : }
987 209 : if (leftE->fLowerY + SK_Fixed1 < riteE->fLowerY) {
988 9 : return isSmoothEnough(leftE, currE, stop_y); // Only leftE is changing
989 200 : } else if (leftE->fLowerY > riteE->fLowerY + SK_Fixed1) {
990 64 : return isSmoothEnough(riteE, currE, stop_y); // Only riteE is changing
991 : }
992 :
993 : // Now both edges are changing, find the second next edge
994 136 : SkAnalyticEdge* nextCurrE = currE->fNext;
995 136 : if (nextCurrE->fUpperY >= stop_y << 16) { // Check if we're at the end
996 0 : return false;
997 : }
998 136 : if (*nextCurrE < *currE) {
999 0 : SkTSwap(currE, nextCurrE);
1000 : }
1001 136 : return isSmoothEnough(leftE, currE, stop_y) && isSmoothEnough(riteE, nextCurrE, stop_y);
1002 : }
1003 :
1004 145 : static inline void aaa_walk_convex_edges(SkAnalyticEdge* prevHead,
1005 : AdditiveBlitter* blitter, int start_y, int stop_y, SkFixed leftBound, SkFixed riteBound,
1006 : bool isUsingMask) {
1007 145 : validate_sort((SkAnalyticEdge*)prevHead->fNext);
1008 :
1009 145 : SkAnalyticEdge* leftE = (SkAnalyticEdge*) prevHead->fNext;
1010 145 : SkAnalyticEdge* riteE = (SkAnalyticEdge*) leftE->fNext;
1011 145 : SkAnalyticEdge* currE = (SkAnalyticEdge*) riteE->fNext;
1012 :
1013 145 : bool currENullInit = !currE, currEChanged = false;
1014 :
1015 145 : SkFixed y = SkTMax(leftE->fUpperY, riteE->fUpperY);
1016 :
1017 : #ifdef SK_DEBUG
1018 145 : int frac_y_cnt = 0;
1019 145 : int total_y_cnt = 0;
1020 : #endif
1021 :
1022 : for (;;) {
1023 : // We have to check fLowerY first because some edges might be alone (e.g., there's only
1024 : // a left edge but no right edge in a given y scan line) due to precision limit.
1025 1148 : while (leftE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges
1026 405 : if (update_edge(leftE, y)) {
1027 175 : if (!currE) {
1028 0 : MOZ_RELEASE_ASSERT((!currENullInit || currEChanged) || (stop_y < SkFixedFloorToInt(SK_MaxS32)), "Please help us! Use crash reporter to report me and comment what site you were viewing when this happened.");
1029 0 : MOZ_RELEASE_ASSERT(!currENullInit || currEChanged, "Please help us! Use crash reporter to report me and comment what site you were viewing when this happened.");
1030 0 : MOZ_RELEASE_ASSERT(stop_y < SkFixedFloorToInt(SK_MaxS32), "Please help us! Use crash reporter to report me and comment what site you were viewing when this happened.");
1031 : }
1032 175 : if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
1033 145 : goto END_WALK;
1034 : }
1035 30 : leftE = currE;
1036 30 : currE = (SkAnalyticEdge*)currE->fNext;
1037 30 : currEChanged = true;
1038 : }
1039 : }
1040 1135 : while (riteE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges
1041 326 : if (update_edge(riteE, y)) {
1042 30 : if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
1043 0 : goto END_WALK;
1044 : }
1045 30 : riteE = currE;
1046 30 : currE = (SkAnalyticEdge*)currE->fNext;
1047 30 : currEChanged = true;
1048 : }
1049 : }
1050 :
1051 483 : SkASSERT(leftE);
1052 483 : SkASSERT(riteE);
1053 :
1054 : // check our bottom clip
1055 483 : if (SkFixedFloorToInt(y) >= stop_y) {
1056 0 : break;
1057 : }
1058 :
1059 483 : SkASSERT(SkFixedFloorToInt(leftE->fUpperY) <= stop_y);
1060 483 : SkASSERT(SkFixedFloorToInt(riteE->fUpperY) <= stop_y);
1061 :
1062 483 : leftE->goY(y);
1063 483 : riteE->goY(y);
1064 :
1065 501 : if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX &&
1066 18 : leftE->fDX > riteE->fDX)) {
1067 4 : SkTSwap(leftE, riteE);
1068 : }
1069 :
1070 483 : SkFixed local_bot_fixed = SkMin32(leftE->fLowerY, riteE->fLowerY);
1071 483 : if (isSmoothEnough(leftE, riteE, currE, stop_y)) {
1072 117 : local_bot_fixed = SkFixedCeilToFixed(local_bot_fixed);
1073 : }
1074 483 : local_bot_fixed = SkMin32(local_bot_fixed, SkIntToFixed(stop_y));
1075 :
1076 483 : SkFixed left = SkTMax(leftBound, leftE->fX);
1077 483 : SkFixed dLeft = leftE->fDX;
1078 483 : SkFixed rite = SkTMin(riteBound, riteE->fX);
1079 483 : SkFixed dRite = riteE->fDX;
1080 483 : if (0 == (dLeft | dRite)) {
1081 139 : int fullLeft = SkFixedCeilToInt(left);
1082 139 : int fullRite = SkFixedFloorToInt(rite);
1083 139 : SkFixed partialLeft = SkIntToFixed(fullLeft) - left;
1084 139 : SkFixed partialRite = rite - SkIntToFixed(fullRite);
1085 139 : int fullTop = SkFixedCeilToInt(y);
1086 139 : int fullBot = SkFixedFloorToInt(local_bot_fixed);
1087 139 : SkFixed partialTop = SkIntToFixed(fullTop) - y;
1088 139 : SkFixed partialBot = local_bot_fixed - SkIntToFixed(fullBot);
1089 139 : if (fullTop > fullBot) { // The rectangle is within one pixel height...
1090 0 : partialTop -= (SK_Fixed1 - partialBot);
1091 0 : partialBot = 0;
1092 : }
1093 :
1094 139 : if (fullRite >= fullLeft) {
1095 139 : if (partialTop > 0) { // blit first partial row
1096 5 : if (partialLeft > 0) {
1097 0 : blitter->blitAntiH(fullLeft - 1, fullTop - 1,
1098 0 : f2a(SkFixedMul(partialTop, partialLeft)));
1099 : }
1100 5 : blitter->blitAntiH(fullLeft, fullTop - 1, fullRite - fullLeft,
1101 10 : f2a(partialTop));
1102 5 : if (partialRite > 0) {
1103 0 : blitter->blitAntiH(fullRite, fullTop - 1,
1104 0 : f2a(SkFixedMul(partialTop, partialRite)));
1105 : }
1106 5 : blitter->flush_if_y_changed(y, y + partialTop);
1107 : }
1108 :
1109 : // Blit all full-height rows from fullTop to fullBot
1110 272 : if (fullBot > fullTop &&
1111 : // SkAAClip cannot handle the empty rect so check the non-emptiness here
1112 : // (bug chromium:662800)
1113 4 : (fullRite > fullLeft || f2a(partialLeft) > 0 || f2a(partialRite) > 0)) {
1114 399 : blitter->getRealBlitter()->blitAntiRect(fullLeft - 1, fullTop,
1115 : fullRite - fullLeft, fullBot - fullTop,
1116 399 : f2a(partialLeft), f2a(partialRite));
1117 : }
1118 :
1119 139 : if (partialBot > 0) { // blit last partial row
1120 7 : if (partialLeft > 0) {
1121 0 : blitter->blitAntiH(fullLeft - 1, fullBot,
1122 0 : f2a(SkFixedMul(partialBot, partialLeft)));
1123 : }
1124 7 : blitter->blitAntiH(fullLeft, fullBot, fullRite - fullLeft, f2a(partialBot));
1125 7 : if (partialRite > 0) {
1126 0 : blitter->blitAntiH(fullRite, fullBot,
1127 0 : f2a(SkFixedMul(partialBot, partialRite)));
1128 : }
1129 : }
1130 : } else { // left and rite are within the same pixel
1131 0 : if (partialTop > 0) {
1132 0 : blitter->blitAntiH(fullLeft - 1, fullTop - 1, 1,
1133 0 : f2a(SkFixedMul(partialTop, rite - left)));
1134 0 : blitter->flush_if_y_changed(y, y + partialTop);
1135 : }
1136 0 : if (fullBot > fullTop) {
1137 0 : blitter->getRealBlitter()->blitV(fullLeft - 1, fullTop, fullBot - fullTop,
1138 0 : f2a(rite - left));
1139 : }
1140 0 : if (partialBot > 0) {
1141 0 : blitter->blitAntiH(fullLeft - 1, fullBot, 1,
1142 0 : f2a(SkFixedMul(partialBot, rite - left)));
1143 : }
1144 : }
1145 :
1146 139 : y = local_bot_fixed;
1147 : } else {
1148 : // The following constant are used to snap X
1149 : // We snap X mainly for speedup (no tiny triangle) and
1150 : // avoiding edge cases caused by precision errors
1151 344 : const SkFixed kSnapDigit = SK_Fixed1 >> 4;
1152 344 : const SkFixed kSnapHalf = kSnapDigit >> 1;
1153 344 : const SkFixed kSnapMask = (-1 ^ (kSnapDigit - 1));
1154 344 : left += kSnapHalf; rite += kSnapHalf; // For fast rounding
1155 :
1156 : // Number of blit_trapezoid_row calls we'll have
1157 344 : int count = SkFixedCeilToInt(local_bot_fixed) - SkFixedFloorToInt(y);
1158 : #ifdef SK_DEBUG
1159 344 : total_y_cnt += count;
1160 344 : frac_y_cnt += ((int)(y & 0xFFFF0000) != y);
1161 344 : if ((int)(y & 0xFFFF0000) != y) {
1162 : // SkDebugf("frac_y = %f\n", SkFixedToFloat(y));
1163 : }
1164 : #endif
1165 :
1166 : // If we're using mask blitter, we advance the mask row in this function
1167 : // to save some "if" condition checks.
1168 344 : SkAlpha* maskRow = nullptr;
1169 344 : if (isUsingMask) {
1170 0 : maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
1171 : }
1172 :
1173 : // Instead of writing one loop that handles both partial-row blit_trapezoid_row
1174 : // and full-row trapezoid_row together, we use the following 3-stage flow to
1175 : // handle partial-row blit and full-row blit separately. It will save us much time
1176 : // on changing y, left, and rite.
1177 344 : if (count > 1) {
1178 242 : if ((int)(y & 0xFFFF0000) != y) { // There's a partial-row on the top
1179 124 : count--;
1180 124 : SkFixed nextY = SkFixedCeilToFixed(y + 1);
1181 124 : SkFixed dY = nextY - y;
1182 124 : SkFixed nextLeft = left + SkFixedMul(dLeft, dY);
1183 124 : SkFixed nextRite = rite + SkFixedMul(dRite, dY);
1184 124 : SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
1185 : (nextLeft & kSnapMask) >= leftBound &&
1186 : (nextRite & kSnapMask) <= riteBound);
1187 248 : blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask,
1188 : nextLeft & kSnapMask, nextRite & kSnapMask, leftE->fDY, riteE->fDY,
1189 124 : getPartialAlpha(0xFF, dY), maskRow, isUsingMask);
1190 124 : blitter->flush_if_y_changed(y, nextY);
1191 124 : left = nextLeft; rite = nextRite; y = nextY;
1192 : }
1193 :
1194 814 : while (count > 1) { // Full rows in the middle
1195 286 : count--;
1196 286 : if (isUsingMask) {
1197 0 : maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
1198 : }
1199 286 : SkFixed nextY = y + SK_Fixed1, nextLeft = left + dLeft, nextRite = rite + dRite;
1200 286 : SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
1201 : (nextLeft & kSnapMask) >= leftBound &&
1202 : (nextRite & kSnapMask) <= riteBound);
1203 286 : blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask,
1204 : nextLeft & kSnapMask, nextRite & kSnapMask,
1205 : leftE->fDY, riteE->fDY, 0xFF, maskRow, isUsingMask);
1206 286 : blitter->flush_if_y_changed(y, nextY);
1207 286 : left = nextLeft; rite = nextRite; y = nextY;
1208 : }
1209 : }
1210 :
1211 344 : if (isUsingMask) {
1212 0 : maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
1213 : }
1214 :
1215 344 : SkFixed dY = local_bot_fixed - y; // partial-row on the bottom
1216 344 : SkASSERT(dY <= SK_Fixed1);
1217 : // Smooth jumping to integer y may make the last nextLeft/nextRite out of bound.
1218 : // Take them back into the bound here.
1219 : // Note that we substract kSnapHalf later so we have to add them to leftBound/riteBound
1220 344 : SkFixed nextLeft = SkTMax(left + SkFixedMul(dLeft, dY), leftBound + kSnapHalf);
1221 344 : SkFixed nextRite = SkTMin(rite + SkFixedMul(dRite, dY), riteBound + kSnapHalf);
1222 344 : SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
1223 : (nextLeft & kSnapMask) >= leftBound && (nextRite & kSnapMask) <= riteBound);
1224 688 : blit_trapezoid_row(blitter, y >> 16, left & kSnapMask, rite & kSnapMask,
1225 : nextLeft & kSnapMask, nextRite & kSnapMask, leftE->fDY, riteE->fDY,
1226 344 : getPartialAlpha(0xFF, dY), maskRow, isUsingMask);
1227 344 : blitter->flush_if_y_changed(y, local_bot_fixed);
1228 344 : left = nextLeft; rite = nextRite; y = local_bot_fixed;
1229 344 : left -= kSnapHalf; rite -= kSnapHalf;
1230 : }
1231 :
1232 483 : leftE->fX = left;
1233 483 : riteE->fX = rite;
1234 483 : leftE->fY = riteE->fY = y;
1235 483 : }
1236 :
1237 : END_WALK:
1238 : ;
1239 : #ifdef SK_DEBUG
1240 : // SkDebugf("frac_y_cnt = %d, total_y_cnt = %d\n", frac_y_cnt, total_y_cnt);
1241 : #endif
1242 145 : }
1243 :
1244 : ///////////////////////////////////////////////////////////////////////////////
1245 :
1246 8712 : static inline void updateNextNextY(SkFixed y, SkFixed nextY, SkFixed* nextNextY) {
1247 8712 : *nextNextY = y > nextY && y < *nextNextY ? y : *nextNextY;
1248 8712 : }
1249 :
1250 6107 : static inline void checkIntersection(const SkAnalyticEdge* edge, SkFixed nextY, SkFixed* nextNextY)
1251 : {
1252 6107 : if (edge->fPrev->fPrev && edge->fPrev->fX + edge->fPrev->fDX > edge->fX + edge->fDX) {
1253 0 : *nextNextY = nextY + (SK_Fixed1 >> SkAnalyticEdge::kDefaultAccuracy);
1254 : }
1255 6107 : }
1256 :
1257 2524 : static void insert_new_edges(SkAnalyticEdge* newEdge, SkFixed y, SkFixed* nextNextY) {
1258 2524 : if (newEdge->fUpperY > y) {
1259 2450 : updateNextNextY(newEdge->fUpperY, y, nextNextY);
1260 2450 : return;
1261 : }
1262 74 : SkAnalyticEdge* prev = newEdge->fPrev;
1263 74 : if (prev->fX <= newEdge->fX) {
1264 423 : while (newEdge->fUpperY <= y) {
1265 179 : checkIntersection(newEdge, y, nextNextY);
1266 179 : updateNextNextY(newEdge->fLowerY, y, nextNextY);
1267 179 : newEdge = newEdge->fNext;
1268 : }
1269 65 : updateNextNextY(newEdge->fUpperY, y, nextNextY);
1270 65 : return;
1271 : }
1272 : // find first x pos to insert
1273 9 : SkAnalyticEdge* start = backward_insert_start(prev, newEdge->fX);
1274 : //insert the lot, fixing up the links as we go
1275 9 : do {
1276 18 : SkAnalyticEdge* next = newEdge->fNext;
1277 : do {
1278 18 : if (start->fNext == newEdge) {
1279 0 : goto nextEdge;
1280 : }
1281 18 : SkAnalyticEdge* after = start->fNext;
1282 18 : if (after->fX >= newEdge->fX) {
1283 18 : break;
1284 : }
1285 0 : SkASSERT(start != after);
1286 0 : start = after;
1287 : } while (true);
1288 18 : remove_edge(newEdge);
1289 18 : insert_edge_after(newEdge, start);
1290 : nextEdge:
1291 18 : checkIntersection(newEdge, y, nextNextY);
1292 18 : updateNextNextY(newEdge->fLowerY, y, nextNextY);
1293 18 : start = newEdge;
1294 18 : newEdge = next;
1295 18 : } while (newEdge->fUpperY <= y);
1296 9 : updateNextNextY(newEdge->fUpperY, y, nextNextY);
1297 : }
1298 :
1299 8712 : static void validate_edges_for_y(const SkAnalyticEdge* edge, SkFixed y) {
1300 : #ifdef SK_DEBUG
1301 14868 : while (edge->fUpperY <= y) {
1302 6156 : SkASSERT(edge->fPrev && edge->fNext);
1303 6156 : SkASSERT(edge->fPrev->fNext == edge);
1304 6156 : SkASSERT(edge->fNext->fPrev == edge);
1305 6156 : SkASSERT(edge->fUpperY <= edge->fLowerY);
1306 6156 : SkASSERT(edge->fPrev->fPrev == nullptr || edge->fPrev->fX <= edge->fX);
1307 6156 : edge = edge->fNext;
1308 : }
1309 : #endif
1310 2556 : }
1311 :
1312 : // Return true if prev->fX, next->fX are too close in the current pixel row.
1313 424 : static inline bool edges_too_close(SkAnalyticEdge* prev, SkAnalyticEdge* next, SkFixed lowerY) {
1314 : // Note that even if the following test failed, the edges might still be very close to each
1315 : // other at some point within the current pixel row because of prev->fDX and next->fDX.
1316 : // However, to handle that case, we have to sacrafice more performance.
1317 : // I think the current quality is good enough (mainly by looking at Nebraska-StateSeal.svg)
1318 : // so I'll ignore fDX for performance tradeoff.
1319 424 : return next && prev && next->fUpperY < lowerY && prev->fX >= next->fX - SkAbs32(next->fDX);
1320 : // The following is more accurate but also slower.
1321 : // return (prev && prev->fPrev && next && next->fNext != nullptr && next->fUpperY < lowerY &&
1322 : // prev->fX + SkAbs32(prev->fDX) >= next->fX - SkAbs32(next->fDX));
1323 : }
1324 :
1325 : // This function exists for the case where the previous rite edge is removed because
1326 : // its fLowerY <= nextY
1327 416 : static inline bool edges_too_close(int prevRite, SkFixed ul, SkFixed ll) {
1328 416 : return prevRite > SkFixedFloorToInt(ul) || prevRite > SkFixedFloorToInt(ll);
1329 : }
1330 :
1331 0 : static inline void blit_saved_trapezoid(SkAnalyticEdge* leftE, SkFixed lowerY,
1332 : SkFixed lowerLeft, SkFixed lowerRite,
1333 : AdditiveBlitter* blitter, SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter,
1334 : SkFixed leftClip, SkFixed rightClip) {
1335 0 : SkAnalyticEdge* riteE = leftE->fRiteE;
1336 0 : SkASSERT(riteE);
1337 0 : SkASSERT(riteE->fNext == nullptr || leftE->fSavedY == riteE->fSavedY);
1338 0 : SkASSERT(SkFixedFloorToInt(lowerY - 1) == SkFixedFloorToInt(leftE->fSavedY));
1339 0 : int y = SkFixedFloorToInt(leftE->fSavedY);
1340 : // Instead of using f2a(lowerY - leftE->fSavedY), we use the following fullAlpha
1341 : // to elimiate cumulative error: if there are many fractional y scan lines within the
1342 : // same row, the former may accumulate the rounding error while the later won't.
1343 0 : SkAlpha fullAlpha = f2a(lowerY - SkIntToFixed(y)) - f2a(leftE->fSavedY - SkIntToFixed(y));
1344 : // We need fSavedDY because the (quad or cubic) edge might be updated
1345 0 : blit_trapezoid_row(blitter, y,
1346 0 : SkTMax(leftE->fSavedX, leftClip), SkTMin(riteE->fSavedX, rightClip),
1347 0 : SkTMax(lowerLeft, leftClip), SkTMin(lowerRite, rightClip),
1348 : leftE->fSavedDY, riteE->fSavedDY, fullAlpha, maskRow, isUsingMask,
1349 0 : noRealBlitter ||
1350 0 : (fullAlpha == 0xFF && (edges_too_close(leftE->fPrev, leftE, lowerY)
1351 0 : || edges_too_close(riteE, riteE->fNext, lowerY))),
1352 : true);
1353 0 : leftE->fRiteE = nullptr;
1354 0 : }
1355 :
1356 0 : static inline void deferred_blit(SkAnalyticEdge* leftE, SkAnalyticEdge* riteE,
1357 : SkFixed left, SkFixed leftDY, // don't save leftE->fX/fDY as they may have been updated
1358 : SkFixed y, SkFixed nextY, bool isIntegralNextY, bool leftEnds, bool riteEnds,
1359 : AdditiveBlitter* blitter, SkAlpha* maskRow, bool isUsingMask, bool noRealBlitter,
1360 : SkFixed leftClip, SkFixed rightClip, int yShift) {
1361 0 : if (leftE->fRiteE && leftE->fRiteE != riteE) {
1362 : // leftE's right edge changed. Blit the saved trapezoid.
1363 0 : SkASSERT(leftE->fRiteE->fNext == nullptr || leftE->fRiteE->fY == y);
1364 0 : blit_saved_trapezoid(leftE, y, left, leftE->fRiteE->fX,
1365 0 : blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip);
1366 : }
1367 0 : if (!leftE->fRiteE) {
1368 : // Save and defer blitting the trapezoid
1369 0 : SkASSERT(riteE->fRiteE == nullptr);
1370 0 : SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY);
1371 0 : SkASSERT(riteE->fNext == nullptr || riteE->fY == y);
1372 0 : leftE->saveXY(left, y, leftDY);
1373 0 : riteE->saveXY(riteE->fX, y, riteE->fDY);
1374 0 : leftE->fRiteE = riteE;
1375 : }
1376 0 : SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY);
1377 0 : riteE->goY(nextY, yShift);
1378 : // Always blit when edges end or nextY is integral
1379 0 : if (isIntegralNextY || leftEnds || riteEnds) {
1380 0 : blit_saved_trapezoid(leftE, nextY, leftE->fX, riteE->fX,
1381 0 : blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip);
1382 : }
1383 0 : }
1384 :
1385 32 : static void aaa_walk_edges(SkAnalyticEdge* prevHead, SkAnalyticEdge* nextTail,
1386 : SkPath::FillType fillType, AdditiveBlitter* blitter, int start_y, int stop_y,
1387 : SkFixed leftClip, SkFixed rightClip, bool isUsingMask, bool forceRLE, bool useDeferred,
1388 : bool skipIntersect) {
1389 32 : prevHead->fX = prevHead->fUpperX = leftClip;
1390 32 : nextTail->fX = nextTail->fUpperX = rightClip;
1391 32 : SkFixed y = SkTMax(prevHead->fNext->fUpperY, SkIntToFixed(start_y));
1392 32 : SkFixed nextNextY = SK_MaxS32;
1393 :
1394 : {
1395 : SkAnalyticEdge* edge;
1396 81 : for(edge = prevHead->fNext; edge->fUpperY <= y; edge = edge->fNext) {
1397 49 : edge->goY(y);
1398 49 : updateNextNextY(edge->fLowerY, y, &nextNextY);
1399 : }
1400 32 : updateNextNextY(edge->fUpperY, y, &nextNextY);
1401 : }
1402 :
1403 : // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
1404 32 : int windingMask = (fillType & 1) ? 1 : -1;
1405 :
1406 32 : bool isInverse = SkPath::IsInverseFillType(fillType);
1407 :
1408 32 : if (isInverse && SkIntToFixed(start_y) != y) {
1409 0 : int width = SkFixedFloorToInt(rightClip - leftClip);
1410 0 : if (SkFixedFloorToInt(y) != start_y) {
1411 0 : blitter->getRealBlitter()->blitRect(SkFixedFloorToInt(leftClip), start_y,
1412 0 : width, SkFixedFloorToInt(y) - start_y);
1413 0 : start_y = SkFixedFloorToInt(y);
1414 : }
1415 0 : SkAlpha* maskRow = isUsingMask ? static_cast<MaskAdditiveBlitter*>(blitter)->getRow(start_y)
1416 0 : : nullptr;
1417 0 : blit_full_alpha(blitter, start_y, SkFixedFloorToInt(leftClip), width,
1418 0 : f2a(y - SkIntToFixed(start_y)), maskRow, isUsingMask, false, false);
1419 : }
1420 :
1421 : while (true) {
1422 2556 : int w = 0;
1423 2556 : bool in_interval = isInverse;
1424 2556 : SkFixed prevX = prevHead->fX;
1425 2556 : SkFixed nextY = SkTMin(nextNextY, SkFixedCeilToFixed(y + 1));
1426 2556 : bool isIntegralNextY = (nextY & (SK_Fixed1 - 1)) == 0;
1427 2556 : SkAnalyticEdge* currE = prevHead->fNext;
1428 2556 : SkAnalyticEdge* leftE = prevHead;
1429 2556 : SkFixed left = leftClip;
1430 2556 : SkFixed leftDY = 0;
1431 2556 : bool leftEnds = false;
1432 2556 : int prevRite = SkFixedFloorToInt(leftClip);
1433 :
1434 2556 : nextNextY = SK_MaxS32;
1435 :
1436 2556 : SkASSERT((nextY & ((SK_Fixed1 >> 2) - 1)) == 0);
1437 2556 : int yShift = 0;
1438 2556 : if ((nextY - y) & (SK_Fixed1 >> 2)) {
1439 288 : yShift = 2;
1440 288 : nextY = y + (SK_Fixed1 >> 2);
1441 2268 : } else if ((nextY - y) & (SK_Fixed1 >> 1)) {
1442 200 : yShift = 1;
1443 200 : SkASSERT(nextY == y + (SK_Fixed1 >> 1));
1444 : }
1445 :
1446 2556 : SkAlpha fullAlpha = f2a(nextY - y);
1447 :
1448 : // If we're using mask blitter, we advance the mask row in this function
1449 : // to save some "if" condition checks.
1450 2556 : SkAlpha* maskRow = nullptr;
1451 2556 : if (isUsingMask) {
1452 0 : maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(SkFixedFloorToInt(y));
1453 : }
1454 :
1455 2556 : SkASSERT(currE->fPrev == prevHead);
1456 2556 : validate_edges_for_y(currE, y);
1457 :
1458 : // Even if next - y == SK_Fixed1, we can still break the left-to-right order requirement
1459 : // of the SKAAClip: |\| (two trapezoids with overlapping middle wedges)
1460 2556 : bool noRealBlitter = forceRLE; // forceRLE && (nextY - y != SK_Fixed1);
1461 :
1462 14868 : while (currE->fUpperY <= y) {
1463 6156 : SkASSERT(currE->fLowerY >= nextY);
1464 6156 : SkASSERT(currE->fY == y);
1465 :
1466 6156 : w += currE->fWinding;
1467 6156 : bool prev_in_interval = in_interval;
1468 6156 : in_interval = !(w & windingMask) == isInverse;
1469 :
1470 6156 : bool isLeft = in_interval && !prev_in_interval;
1471 6156 : bool isRite = !in_interval && prev_in_interval;
1472 6156 : bool currEnds = currE->fLowerY == nextY;
1473 :
1474 6156 : if (useDeferred) {
1475 0 : if (currE->fRiteE && !isLeft) {
1476 : // currE is a left edge previously, but now it's not.
1477 : // Blit the trapezoid between fSavedY and y.
1478 0 : SkASSERT(currE->fRiteE->fY == y);
1479 0 : blit_saved_trapezoid(currE, y, currE->fX, currE->fRiteE->fX,
1480 0 : blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip);
1481 : }
1482 0 : if (leftE->fRiteE == currE && !isRite) {
1483 : // currE is a right edge previously, but now it's not.
1484 : // Moreover, its corresponding leftE doesn't change (otherwise we'll handle it
1485 : // in the previous if clause). Hence we blit the trapezoid.
1486 0 : blit_saved_trapezoid(leftE, y, left, currE->fX,
1487 0 : blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip);
1488 : }
1489 : }
1490 :
1491 6156 : if (isRite) {
1492 2638 : if (useDeferred) {
1493 0 : deferred_blit(leftE, currE, left, leftDY, y, nextY, isIntegralNextY,
1494 : leftEnds, currEnds, blitter, maskRow, isUsingMask, noRealBlitter,
1495 0 : leftClip, rightClip, yShift);
1496 : } else {
1497 2638 : SkFixed rite = currE->fX;
1498 2638 : currE->goY(nextY, yShift);
1499 2638 : leftE->fX = SkTMax(leftClip, leftE->fX);
1500 2638 : rite = SkTMin(rightClip, rite);
1501 2638 : currE->fX = SkTMin(rightClip, currE->fX);
1502 5276 : blit_trapezoid_row(blitter, y >> 16, left, rite, leftE->fX, currE->fX,
1503 : leftDY, currE->fDY, fullAlpha, maskRow, isUsingMask,
1504 5132 : noRealBlitter || (fullAlpha == 0xFF && (
1505 832 : edges_too_close(prevRite, left, leftE->fX) ||
1506 416 : edges_too_close(currE, currE->fNext, nextY)
1507 : )),
1508 2638 : true);
1509 2638 : prevRite = SkFixedCeilToInt(SkTMax(rite, currE->fX));
1510 : }
1511 : } else {
1512 3518 : if (isLeft) {
1513 3518 : left = SkTMax(currE->fX, leftClip);
1514 3518 : leftDY = currE->fDY;
1515 3518 : leftE = currE;
1516 3518 : leftEnds = leftE->fLowerY == nextY;
1517 : }
1518 3518 : currE->goY(nextY, yShift);
1519 : }
1520 :
1521 :
1522 6156 : SkAnalyticEdge* next = currE->fNext;
1523 : SkFixed newX;
1524 :
1525 6920 : while (currE->fLowerY <= nextY) {
1526 628 : if (currE->fCurveCount < 0) {
1527 384 : SkAnalyticCubicEdge* cubicEdge = (SkAnalyticCubicEdge*)currE;
1528 384 : cubicEdge->keepContinuous();
1529 384 : if (!cubicEdge->updateCubic()) {
1530 2 : break;
1531 : }
1532 244 : } else if (currE->fCurveCount > 0) {
1533 0 : SkAnalyticQuadraticEdge* quadEdge = (SkAnalyticQuadraticEdge*)currE;
1534 0 : quadEdge->keepContinuous();
1535 0 : if (!quadEdge->updateQuadratic()) {
1536 0 : break;
1537 : }
1538 : } else {
1539 244 : break;
1540 : }
1541 : }
1542 6156 : SkASSERT(currE->fY == nextY);
1543 :
1544 6156 : if (currE->fLowerY <= nextY) {
1545 246 : remove_edge(currE);
1546 : } else {
1547 5910 : updateNextNextY(currE->fLowerY, nextY, &nextNextY);
1548 5910 : newX = currE->fX;
1549 5910 : SkASSERT(currE->fLowerY > nextY);
1550 5910 : if (newX < prevX) { // ripple currE backwards until it is x-sorted
1551 : // If the crossing edge is a right edge, blit the saved trapezoid.
1552 0 : if (leftE->fRiteE == currE && useDeferred) {
1553 0 : SkASSERT(leftE->fY == nextY && currE->fY == nextY);
1554 0 : blit_saved_trapezoid(leftE, nextY, leftE->fX, currE->fX,
1555 0 : blitter, maskRow, isUsingMask, noRealBlitter, leftClip, rightClip);
1556 : }
1557 0 : backward_insert_edge_based_on_x(currE);
1558 : } else {
1559 5910 : prevX = newX;
1560 : }
1561 5910 : if (!skipIntersect) {
1562 5910 : checkIntersection(currE, nextY, &nextNextY);
1563 : }
1564 : }
1565 :
1566 6156 : currE = next;
1567 6156 : SkASSERT(currE);
1568 : }
1569 :
1570 : // was our right-edge culled away?
1571 2556 : if (in_interval) {
1572 880 : if (useDeferred) {
1573 0 : deferred_blit(leftE, nextTail, left, leftDY, y, nextY, isIntegralNextY,
1574 : leftEnds, false, blitter, maskRow, isUsingMask, noRealBlitter,
1575 0 : leftClip, rightClip, yShift);
1576 : } else {
1577 2640 : blit_trapezoid_row(blitter, y >> 16,
1578 : left, rightClip,
1579 880 : SkTMax(leftClip, leftE->fX), rightClip,
1580 : leftDY, 0, fullAlpha, maskRow, isUsingMask,
1581 1760 : noRealBlitter ||
1582 8 : (fullAlpha == 0xFF && edges_too_close(leftE->fPrev, leftE, nextY)),
1583 1760 : true);
1584 : }
1585 : }
1586 :
1587 2556 : if (forceRLE) {
1588 1944 : ((RunBasedAdditiveBlitter*)blitter)->flush_if_y_changed(y, nextY);
1589 : }
1590 :
1591 2556 : y = nextY;
1592 2556 : if (y >= SkIntToFixed(stop_y)) {
1593 32 : break;
1594 : }
1595 :
1596 : // now currE points to the first edge with a fUpperY larger than the previous y
1597 2524 : insert_new_edges(currE, y, &nextNextY);
1598 2524 : }
1599 32 : }
1600 :
1601 : static SK_ALWAYS_INLINE void aaa_fill_path(const SkPath& path, const SkIRect& clipRect,
1602 : AdditiveBlitter* blitter, int start_y, int stop_y, bool pathContainedInClip,
1603 : bool isUsingMask, bool forceRLE) { // forceRLE implies that SkAAClip is calling us
1604 184 : SkASSERT(blitter);
1605 :
1606 184 : SkEdgeBuilder builder;
1607 :
1608 : // If we're convex, then we need both edges, even the right edge is past the clip
1609 184 : const bool canCullToTheRight = !path.isConvex();
1610 :
1611 184 : SkASSERT(gSkUseAnalyticAA.load());
1612 184 : const SkIRect* builderClip = pathContainedInClip ? nullptr : &clipRect;
1613 184 : int count = builder.build(path, builderClip, 0, canCullToTheRight, true);
1614 184 : SkASSERT(count >= 0);
1615 :
1616 184 : SkAnalyticEdge** list = (SkAnalyticEdge**)builder.analyticEdgeList();
1617 :
1618 184 : SkIRect rect = clipRect;
1619 184 : if (0 == count) {
1620 7 : if (path.isInverseFillType()) {
1621 : /*
1622 : * Since we are in inverse-fill, our caller has already drawn above
1623 : * our top (start_y) and will draw below our bottom (stop_y). Thus
1624 : * we need to restrict our drawing to the intersection of the clip
1625 : * and those two limits.
1626 : */
1627 0 : if (rect.fTop < start_y) {
1628 0 : rect.fTop = start_y;
1629 : }
1630 0 : if (rect.fBottom > stop_y) {
1631 0 : rect.fBottom = stop_y;
1632 : }
1633 0 : if (!rect.isEmpty()) {
1634 0 : blitter->getRealBlitter()->blitRect(rect.fLeft, rect.fTop,
1635 0 : rect.width(), rect.height());
1636 : }
1637 : }
1638 : return;
1639 : }
1640 :
1641 : SkAnalyticEdge headEdge, tailEdge, *last;
1642 : // this returns the first and last edge after they're sorted into a dlink list
1643 177 : SkAnalyticEdge* edge = sort_edges(list, count, &last);
1644 :
1645 177 : headEdge.fRiteE = nullptr;
1646 177 : headEdge.fPrev = nullptr;
1647 177 : headEdge.fNext = edge;
1648 177 : headEdge.fUpperY = headEdge.fLowerY = SK_MinS32;
1649 177 : headEdge.fX = SK_MinS32;
1650 177 : headEdge.fDX = 0;
1651 177 : headEdge.fDY = SK_MaxS32;
1652 177 : headEdge.fUpperX = SK_MinS32;
1653 177 : edge->fPrev = &headEdge;
1654 :
1655 177 : tailEdge.fRiteE = nullptr;
1656 177 : tailEdge.fPrev = last;
1657 177 : tailEdge.fNext = nullptr;
1658 177 : tailEdge.fUpperY = tailEdge.fLowerY = SK_MaxS32;
1659 177 : tailEdge.fX = SK_MaxS32;
1660 177 : tailEdge.fDX = 0;
1661 177 : tailEdge.fDY = SK_MaxS32;
1662 177 : tailEdge.fUpperX = SK_MaxS32;
1663 177 : last->fNext = &tailEdge;
1664 :
1665 : // now edge is the head of the sorted linklist
1666 :
1667 177 : if (!pathContainedInClip && start_y < clipRect.fTop) {
1668 9 : start_y = clipRect.fTop;
1669 : }
1670 177 : if (!pathContainedInClip && stop_y > clipRect.fBottom) {
1671 18 : stop_y = clipRect.fBottom;
1672 : }
1673 :
1674 177 : SkFixed leftBound = SkIntToFixed(rect.fLeft);
1675 177 : SkFixed rightBound = SkIntToFixed(rect.fRight);
1676 177 : if (isUsingMask) {
1677 : // If we're using mask, then we have to limit the bound within the path bounds.
1678 : // Otherwise, the edge drift may access an invalid address inside the mask.
1679 : SkIRect ir;
1680 3 : path.getBounds().roundOut(&ir);
1681 3 : leftBound = SkTMax(leftBound, SkIntToFixed(ir.fLeft));
1682 3 : rightBound = SkTMin(rightBound, SkIntToFixed(ir.fRight));
1683 : }
1684 :
1685 177 : if (!path.isInverseFillType() && path.isConvex() && count >= 2) {
1686 145 : SkASSERT(count >= 2); // convex walker does not handle missing right edges
1687 145 : aaa_walk_convex_edges(&headEdge, blitter, start_y, stop_y,
1688 145 : leftBound, rightBound, isUsingMask);
1689 : } else {
1690 : // Only use deferred blitting if there are many edges.
1691 : bool useDeferred = count >
1692 32 : (SkFixedFloorToInt(tailEdge.fPrev->fLowerY - headEdge.fNext->fUpperY) + 1) * 4;
1693 :
1694 : // We skip intersection computation if there are many points which probably already
1695 : // give us enough fractional scan lines.
1696 32 : bool skipIntersect = path.countPoints() > (stop_y - start_y) * 2;
1697 :
1698 64 : aaa_walk_edges(&headEdge, &tailEdge, path.getFillType(), blitter, start_y, stop_y,
1699 64 : leftBound, rightBound, isUsingMask, forceRLE, useDeferred, skipIntersect);
1700 : }
1701 : }
1702 :
1703 : ///////////////////////////////////////////////////////////////////////////////
1704 :
1705 1472 : static int overflows_short_shift(int value, int shift) {
1706 1472 : const int s = 16 + shift;
1707 1472 : return (SkLeftShift(value, s) >> s) - value;
1708 : }
1709 :
1710 : /**
1711 : Would any of the coordinates of this rectangle not fit in a short,
1712 : when left-shifted by shift?
1713 : */
1714 184 : static int rect_overflows_short_shift(SkIRect rect, int shift) {
1715 184 : SkASSERT(!overflows_short_shift(8191, 2));
1716 184 : SkASSERT(overflows_short_shift(8192, 2));
1717 184 : SkASSERT(!overflows_short_shift(32767, 0));
1718 184 : SkASSERT(overflows_short_shift(32768, 0));
1719 :
1720 : // Since we expect these to succeed, we bit-or together
1721 : // for a tiny extra bit of speed.
1722 368 : return overflows_short_shift(rect.fLeft, 2) |
1723 368 : overflows_short_shift(rect.fRight, 2) |
1724 184 : overflows_short_shift(rect.fTop, 2) |
1725 184 : overflows_short_shift(rect.fBottom, 2);
1726 : }
1727 :
1728 184 : static bool fitsInsideLimit(const SkRect& r, SkScalar max) {
1729 184 : const SkScalar min = -max;
1730 552 : return r.fLeft > min && r.fTop > min &&
1731 552 : r.fRight < max && r.fBottom < max;
1732 : }
1733 :
1734 184 : static bool safeRoundOut(const SkRect& src, SkIRect* dst, int32_t maxInt) {
1735 184 : const SkScalar maxScalar = SkIntToScalar(maxInt);
1736 :
1737 184 : if (fitsInsideLimit(src, maxScalar)) {
1738 184 : src.roundOut(dst);
1739 184 : return true;
1740 : }
1741 0 : return false;
1742 : }
1743 :
1744 184 : void SkScan::AAAFillPath(const SkPath& path, const SkRegion& origClip, SkBlitter* blitter,
1745 : bool forceRLE) {
1746 184 : if (origClip.isEmpty()) {
1747 0 : return;
1748 : }
1749 :
1750 184 : const bool isInverse = path.isInverseFillType();
1751 : SkIRect ir;
1752 184 : if (!safeRoundOut(path.getBounds(), &ir, SK_MaxS32 >> 2)) {
1753 0 : return;
1754 : }
1755 184 : if (ir.isEmpty()) {
1756 0 : if (isInverse) {
1757 0 : blitter->blitRegion(origClip);
1758 : }
1759 0 : return;
1760 : }
1761 :
1762 : SkIRect clippedIR;
1763 184 : if (isInverse) {
1764 : // If the path is an inverse fill, it's going to fill the entire
1765 : // clip, and we care whether the entire clip exceeds our limits.
1766 0 : clippedIR = origClip.getBounds();
1767 : } else {
1768 184 : if (!clippedIR.intersect(ir, origClip.getBounds())) {
1769 0 : return;
1770 : }
1771 : }
1772 : // If the intersection of the path bounds and the clip bounds
1773 : // will overflow 32767 when << by 2, our SkFixed will overflow,
1774 : // so draw without antialiasing.
1775 184 : if (rect_overflows_short_shift(clippedIR, 2)) {
1776 0 : SkScan::FillPath(path, origClip, blitter);
1777 0 : return;
1778 : }
1779 :
1780 : // Our antialiasing can't handle a clip larger than 32767, so we restrict
1781 : // the clip to that limit here. (the runs[] uses int16_t for its index).
1782 : //
1783 : // A more general solution (one that could also eliminate the need to
1784 : // disable aa based on ir bounds (see overflows_short_shift) would be
1785 : // to tile the clip/target...
1786 368 : SkRegion tmpClipStorage;
1787 184 : const SkRegion* clipRgn = &origClip;
1788 : {
1789 : static const int32_t kMaxClipCoord = 32767;
1790 184 : const SkIRect& bounds = origClip.getBounds();
1791 184 : if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) {
1792 0 : SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord };
1793 0 : tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op);
1794 0 : clipRgn = &tmpClipStorage;
1795 : }
1796 : }
1797 : // for here down, use clipRgn, not origClip
1798 :
1799 368 : SkScanClipper clipper(blitter, clipRgn, ir);
1800 184 : const SkIRect* clipRect = clipper.getClipRect();
1801 :
1802 184 : if (clipper.getBlitter() == nullptr) { // clipped out
1803 0 : if (isInverse) {
1804 0 : blitter->blitRegion(*clipRgn);
1805 : }
1806 0 : return;
1807 : }
1808 :
1809 : // now use the (possibly wrapped) blitter
1810 184 : blitter = clipper.getBlitter();
1811 :
1812 184 : if (isInverse) {
1813 0 : sk_blit_above(blitter, ir, *clipRgn);
1814 : }
1815 :
1816 184 : SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
1817 :
1818 184 : if (MaskAdditiveBlitter::canHandleRect(ir) && !isInverse && !forceRLE) {
1819 6 : MaskAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse);
1820 3 : aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom,
1821 : clipRect == nullptr, true, forceRLE);
1822 181 : } else if (!isInverse && path.isConvex()) {
1823 284 : RunBasedAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse);
1824 142 : aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom,
1825 : clipRect == nullptr, false, forceRLE);
1826 : } else {
1827 78 : SafeRLEAdditiveBlitter additiveBlitter(blitter, ir, *clipRgn, isInverse);
1828 39 : aaa_fill_path(path, clipRgn->getBounds(), &additiveBlitter, ir.fTop, ir.fBottom,
1829 : clipRect == nullptr, false, forceRLE);
1830 : }
1831 :
1832 184 : if (isInverse) {
1833 0 : sk_blit_below(blitter, ir, *clipRgn);
1834 : }
1835 : }
1836 :
1837 : // This almost copies SkScan::AntiFillPath
1838 34 : void SkScan::AAAFillPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
1839 34 : if (clip.isEmpty()) {
1840 0 : return;
1841 : }
1842 :
1843 34 : if (clip.isBW()) {
1844 23 : AAAFillPath(path, clip.bwRgn(), blitter);
1845 : } else {
1846 22 : SkRegion tmp;
1847 22 : SkAAClipBlitter aaBlitter;
1848 :
1849 11 : tmp.setRect(clip.getBounds());
1850 11 : aaBlitter.init(blitter, &clip.aaRgn());
1851 11 : AAAFillPath(path, tmp, &aaBlitter, true);
1852 : }
1853 : }
|
