• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 
2 /*
3  * Copyright 2011 The Android Open Source Project
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 
10 #include "SkScan.h"
11 #include "SkBlitter.h"
12 #include "SkColorPriv.h"
13 #include "SkLineClipper.h"
14 #include "SkRasterClip.h"
15 #include "SkFDot6.h"
16 
17 /*  Our attempt to compute the worst case "bounds" for the horizontal and
18     vertical cases has some numerical bug in it, and we sometimes undervalue
19     our extends. The bug is that when this happens, we will set the clip to
20     NULL (for speed), and thus draw outside of the clip by a pixel, which might
21     only look bad, but it might also access memory outside of the valid range
22     allcoated for the device bitmap.
23 
24     This define enables our fix to outset our "bounds" by 1, thus avoiding the
25     chance of the bug, but at the cost of sometimes taking the rectblitter
26     case (i.e. not setting the clip to NULL) when we might not actually need
27     to. If we can improve/fix the actual calculations, then we can remove this
28     step.
29  */
30 #define OUTSET_BEFORE_CLIP_TEST     true
31 
32 #define HLINE_STACK_BUFFER      100
33 
SmallDot6Scale(int value,int dot6)34 static inline int SmallDot6Scale(int value, int dot6) {
35     SkASSERT((int16_t)value == value);
36     SkASSERT((unsigned)dot6 <= 64);
37     return SkMulS16(value, dot6) >> 6;
38 }
39 
40 //#define TEST_GAMMA
41 
42 #ifdef TEST_GAMMA
43     static uint8_t gGammaTable[256];
44     #define ApplyGamma(table, alpha)    (table)[alpha]
45 
build_gamma_table()46     static void build_gamma_table() {
47         static bool gInit = false;
48 
49         if (gInit == false) {
50             for (int i = 0; i < 256; i++) {
51                 SkFixed n = i * 257;
52                 n += n >> 15;
53                 SkASSERT(n >= 0 && n <= SK_Fixed1);
54                 n = SkFixedSqrt(n);
55                 n = n * 255 >> 16;
56             //  SkDebugf("morph %d -> %d\n", i, n);
57                 gGammaTable[i] = SkToU8(n);
58             }
59             gInit = true;
60         }
61     }
62 #else
63     #define ApplyGamma(table, alpha)    SkToU8(alpha)
64 #endif
65 
66 ///////////////////////////////////////////////////////////////////////////////
67 
call_hline_blitter(SkBlitter * blitter,int x,int y,int count,U8CPU alpha)68 static void call_hline_blitter(SkBlitter* blitter, int x, int y, int count,
69                                U8CPU alpha) {
70     SkASSERT(count > 0);
71 
72     int16_t runs[HLINE_STACK_BUFFER + 1];
73     uint8_t  aa[HLINE_STACK_BUFFER];
74 
75     aa[0] = ApplyGamma(gGammaTable, alpha);
76     do {
77         int n = count;
78         if (n > HLINE_STACK_BUFFER) {
79             n = HLINE_STACK_BUFFER;
80         }
81         runs[0] = SkToS16(n);
82         runs[n] = 0;
83         blitter->blitAntiH(x, y, aa, runs);
84         x += n;
85         count -= n;
86     } while (count > 0);
87 }
88 
89 class SkAntiHairBlitter {
90 public:
SkAntiHairBlitter()91     SkAntiHairBlitter() : fBlitter(NULL) {}
~SkAntiHairBlitter()92     virtual ~SkAntiHairBlitter() {}
93 
getBlitter() const94     SkBlitter* getBlitter() const { return fBlitter; }
95 
setup(SkBlitter * blitter)96     void setup(SkBlitter* blitter) {
97         fBlitter = blitter;
98     }
99 
100     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed slope, int mod64) = 0;
101     virtual SkFixed drawLine(int x, int stopx, SkFixed fy, SkFixed slope) = 0;
102 
103 private:
104     SkBlitter*  fBlitter;
105 };
106 
107 class HLine_SkAntiHairBlitter : public SkAntiHairBlitter {
108 public:
drawCap(int x,SkFixed fy,SkFixed slope,int mod64)109     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed slope, int mod64) SK_OVERRIDE {
110         fy += SK_Fixed1/2;
111 
112         int y = fy >> 16;
113         uint8_t  a = (uint8_t)(fy >> 8);
114 
115         // lower line
116         unsigned ma = SmallDot6Scale(a, mod64);
117         if (ma) {
118             call_hline_blitter(this->getBlitter(), x, y, 1, ma);
119         }
120 
121         // upper line
122         ma = SmallDot6Scale(255 - a, mod64);
123         if (ma) {
124             call_hline_blitter(this->getBlitter(), x, y - 1, 1, ma);
125         }
126 
127         return fy - SK_Fixed1/2;
128     }
129 
drawLine(int x,int stopx,SkFixed fy,SkFixed slope)130     virtual SkFixed drawLine(int x, int stopx, SkFixed fy,
131                              SkFixed slope) SK_OVERRIDE {
132         SkASSERT(x < stopx);
133         int count = stopx - x;
134         fy += SK_Fixed1/2;
135 
136         int y = fy >> 16;
137         uint8_t  a = (uint8_t)(fy >> 8);
138 
139         // lower line
140         if (a) {
141             call_hline_blitter(this->getBlitter(), x, y, count, a);
142         }
143 
144         // upper line
145         a = 255 - a;
146         if (a) {
147             call_hline_blitter(this->getBlitter(), x, y - 1, count, a);
148         }
149 
150         return fy - SK_Fixed1/2;
151     }
152 };
153 
154 class Horish_SkAntiHairBlitter : public SkAntiHairBlitter {
155 public:
drawCap(int x,SkFixed fy,SkFixed dy,int mod64)156     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed dy, int mod64) SK_OVERRIDE {
157         int16_t runs[2];
158         uint8_t  aa[1];
159 
160         runs[0] = 1;
161         runs[1] = 0;
162 
163         fy += SK_Fixed1/2;
164         SkBlitter* blitter = this->getBlitter();
165 
166         int lower_y = fy >> 16;
167         uint8_t  a = (uint8_t)(fy >> 8);
168         unsigned ma = SmallDot6Scale(a, mod64);
169         if (ma) {
170             aa[0] = ApplyGamma(gamma, ma);
171             blitter->blitAntiH(x, lower_y, aa, runs);
172             // the clipping blitters might edit runs, but should not affect us
173             SkASSERT(runs[0] == 1);
174             SkASSERT(runs[1] == 0);
175         }
176         ma = SmallDot6Scale(255 - a, mod64);
177         if (ma) {
178             aa[0] = ApplyGamma(gamma, ma);
179             blitter->blitAntiH(x, lower_y - 1, aa, runs);
180             // the clipping blitters might edit runs, but should not affect us
181             SkASSERT(runs[0] == 1);
182             SkASSERT(runs[1] == 0);
183         }
184         fy += dy;
185 
186         return fy - SK_Fixed1/2;
187     }
188 
drawLine(int x,int stopx,SkFixed fy,SkFixed dy)189     virtual SkFixed drawLine(int x, int stopx, SkFixed fy, SkFixed dy) SK_OVERRIDE {
190         SkASSERT(x < stopx);
191 
192         int16_t runs[2];
193         uint8_t  aa[1];
194 
195         runs[0] = 1;
196         runs[1] = 0;
197 
198         fy += SK_Fixed1/2;
199         SkBlitter* blitter = this->getBlitter();
200         do {
201             int lower_y = fy >> 16;
202             uint8_t  a = (uint8_t)(fy >> 8);
203             if (a) {
204                 aa[0] = a;
205                 blitter->blitAntiH(x, lower_y, aa, runs);
206                 // the clipping blitters might edit runs, but should not affect us
207                 SkASSERT(runs[0] == 1);
208                 SkASSERT(runs[1] == 0);
209             }
210             a = 255 - a;
211             if (a) {
212                 aa[0] = a;
213                 blitter->blitAntiH(x, lower_y - 1, aa, runs);
214                 // the clipping blitters might edit runs, but should not affect us
215                 SkASSERT(runs[0] == 1);
216                 SkASSERT(runs[1] == 0);
217             }
218             fy += dy;
219         } while (++x < stopx);
220 
221         return fy - SK_Fixed1/2;
222     }
223 };
224 
225 class VLine_SkAntiHairBlitter : public SkAntiHairBlitter {
226 public:
drawCap(int y,SkFixed fx,SkFixed dx,int mod64)227     virtual SkFixed drawCap(int y, SkFixed fx, SkFixed dx, int mod64) SK_OVERRIDE {
228         SkASSERT(0 == dx);
229         fx += SK_Fixed1/2;
230 
231         int x = fx >> 16;
232         int a = (uint8_t)(fx >> 8);
233 
234         unsigned ma = SmallDot6Scale(a, mod64);
235         if (ma) {
236             this->getBlitter()->blitV(x, y, 1, ma);
237         }
238         ma = SmallDot6Scale(255 - a, mod64);
239         if (ma) {
240             this->getBlitter()->blitV(x - 1, y, 1, ma);
241         }
242 
243         return fx - SK_Fixed1/2;
244     }
245 
drawLine(int y,int stopy,SkFixed fx,SkFixed dx)246     virtual SkFixed drawLine(int y, int stopy, SkFixed fx, SkFixed dx) SK_OVERRIDE {
247         SkASSERT(y < stopy);
248         SkASSERT(0 == dx);
249         fx += SK_Fixed1/2;
250 
251         int x = fx >> 16;
252         int a = (uint8_t)(fx >> 8);
253 
254         if (a) {
255             this->getBlitter()->blitV(x, y, stopy - y, a);
256         }
257         a = 255 - a;
258         if (a) {
259             this->getBlitter()->blitV(x - 1, y, stopy - y, a);
260         }
261 
262         return fx - SK_Fixed1/2;
263     }
264 };
265 
266 class Vertish_SkAntiHairBlitter : public SkAntiHairBlitter {
267 public:
drawCap(int y,SkFixed fx,SkFixed dx,int mod64)268     virtual SkFixed drawCap(int y, SkFixed fx, SkFixed dx, int mod64) SK_OVERRIDE {
269         int16_t runs[3];
270         uint8_t  aa[2];
271 
272         runs[0] = 1;
273         runs[2] = 0;
274 
275         fx += SK_Fixed1/2;
276         int x = fx >> 16;
277         uint8_t  a = (uint8_t)(fx >> 8);
278 
279         aa[0] = SmallDot6Scale(255 - a, mod64);
280         aa[1] = SmallDot6Scale(a, mod64);
281         // the clippng blitters might overwrite this guy, so we have to reset it each time
282         runs[1] = 1;
283         this->getBlitter()->blitAntiH(x - 1, y, aa, runs);
284         // the clipping blitters might edit runs, but should not affect us
285         SkASSERT(runs[0] == 1);
286         SkASSERT(runs[2] == 0);
287         fx += dx;
288 
289         return fx - SK_Fixed1/2;
290     }
291 
drawLine(int y,int stopy,SkFixed fx,SkFixed dx)292     virtual SkFixed drawLine(int y, int stopy, SkFixed fx, SkFixed dx) SK_OVERRIDE {
293         SkASSERT(y < stopy);
294         int16_t runs[3];
295         uint8_t  aa[2];
296 
297         runs[0] = 1;
298         runs[2] = 0;
299 
300         fx += SK_Fixed1/2;
301         do {
302             int x = fx >> 16;
303             uint8_t  a = (uint8_t)(fx >> 8);
304 
305             aa[0] = 255 - a;
306             aa[1] = a;
307             // the clippng blitters might overwrite this guy, so we have to reset it each time
308             runs[1] = 1;
309             this->getBlitter()->blitAntiH(x - 1, y, aa, runs);
310             // the clipping blitters might edit runs, but should not affect us
311             SkASSERT(runs[0] == 1);
312             SkASSERT(runs[2] == 0);
313             fx += dx;
314         } while (++y < stopy);
315 
316         return fx - SK_Fixed1/2;
317     }
318 };
319 
fastfixdiv(SkFDot6 a,SkFDot6 b)320 static inline SkFixed fastfixdiv(SkFDot6 a, SkFDot6 b) {
321     SkASSERT((a << 16 >> 16) == a);
322     SkASSERT(b != 0);
323     return (a << 16) / b;
324 }
325 
326 #define SkBITCOUNT(x)   (sizeof(x) << 3)
327 
328 #if 1
329 // returns high-bit set iff x==0x8000...
bad_int(int x)330 static inline int bad_int(int x) {
331     return x & -x;
332 }
333 
any_bad_ints(int a,int b,int c,int d)334 static int any_bad_ints(int a, int b, int c, int d) {
335     return (bad_int(a) | bad_int(b) | bad_int(c) | bad_int(d)) >> (SkBITCOUNT(int) - 1);
336 }
337 #else
good_int(int x)338 static inline int good_int(int x) {
339     return x ^ (1 << (SkBITCOUNT(x) - 1));
340 }
341 
any_bad_ints(int a,int b,int c,int d)342 static int any_bad_ints(int a, int b, int c, int d) {
343     return !(good_int(a) & good_int(b) & good_int(c) & good_int(d));
344 }
345 #endif
346 
347 #ifdef SK_DEBUG
canConvertFDot6ToFixed(SkFDot6 x)348 static bool canConvertFDot6ToFixed(SkFDot6 x) {
349     const int maxDot6 = SK_MaxS32 >> (16 - 6);
350     return SkAbs32(x) <= maxDot6;
351 }
352 #endif
353 
354 /*
355  *  We want the fractional part of ordinate, but we want multiples of 64 to
356  *  return 64, not 0, so we can't just say (ordinate & 63).
357  *  We basically want to compute those bits, and if they're 0, return 64.
358  *  We can do that w/o a branch with an extra sub and add.
359  */
contribution_64(SkFDot6 ordinate)360 static int contribution_64(SkFDot6 ordinate) {
361 #if 0
362     int result = ordinate & 63;
363     if (0 == result) {
364         result = 64;
365     }
366 #else
367     int result = ((ordinate - 1) & 63) + 1;
368 #endif
369     SkASSERT(result > 0 && result <= 64);
370     return result;
371 }
372 
do_anti_hairline(SkFDot6 x0,SkFDot6 y0,SkFDot6 x1,SkFDot6 y1,const SkIRect * clip,SkBlitter * blitter)373 static void do_anti_hairline(SkFDot6 x0, SkFDot6 y0, SkFDot6 x1, SkFDot6 y1,
374                              const SkIRect* clip, SkBlitter* blitter) {
375     // check for integer NaN (0x80000000) which we can't handle (can't negate it)
376     // It appears typically from a huge float (inf or nan) being converted to int.
377     // If we see it, just don't draw.
378     if (any_bad_ints(x0, y0, x1, y1)) {
379         return;
380     }
381 
382     // The caller must clip the line to [-32767.0 ... 32767.0] ahead of time
383     // (in dot6 format)
384     SkASSERT(canConvertFDot6ToFixed(x0));
385     SkASSERT(canConvertFDot6ToFixed(y0));
386     SkASSERT(canConvertFDot6ToFixed(x1));
387     SkASSERT(canConvertFDot6ToFixed(y1));
388 
389     if (SkAbs32(x1 - x0) > SkIntToFDot6(511) || SkAbs32(y1 - y0) > SkIntToFDot6(511)) {
390         /*  instead of (x0 + x1) >> 1, we shift each separately. This is less
391             precise, but avoids overflowing the intermediate result if the
392             values are huge. A better fix might be to clip the original pts
393             directly (i.e. do the divide), so we don't spend time subdividing
394             huge lines at all.
395          */
396         int hx = (x0 >> 1) + (x1 >> 1);
397         int hy = (y0 >> 1) + (y1 >> 1);
398         do_anti_hairline(x0, y0, hx, hy, clip, blitter);
399         do_anti_hairline(hx, hy, x1, y1, clip, blitter);
400         return;
401     }
402 
403     int         scaleStart, scaleStop;
404     int         istart, istop;
405     SkFixed     fstart, slope;
406 
407     HLine_SkAntiHairBlitter     hline_blitter;
408     Horish_SkAntiHairBlitter    horish_blitter;
409     VLine_SkAntiHairBlitter     vline_blitter;
410     Vertish_SkAntiHairBlitter   vertish_blitter;
411     SkAntiHairBlitter*          hairBlitter = NULL;
412 
413     if (SkAbs32(x1 - x0) > SkAbs32(y1 - y0)) {   // mostly horizontal
414         if (x0 > x1) {    // we want to go left-to-right
415             SkTSwap<SkFDot6>(x0, x1);
416             SkTSwap<SkFDot6>(y0, y1);
417         }
418 
419         istart = SkFDot6Floor(x0);
420         istop = SkFDot6Ceil(x1);
421         fstart = SkFDot6ToFixed(y0);
422         if (y0 == y1) {   // completely horizontal, take fast case
423             slope = 0;
424             hairBlitter = &hline_blitter;
425         } else {
426             slope = fastfixdiv(y1 - y0, x1 - x0);
427             SkASSERT(slope >= -SK_Fixed1 && slope <= SK_Fixed1);
428             fstart += (slope * (32 - (x0 & 63)) + 32) >> 6;
429             hairBlitter = &horish_blitter;
430         }
431 
432         SkASSERT(istop > istart);
433         if (istop - istart == 1) {
434             // we are within a single pixel
435             scaleStart = x1 - x0;
436             SkASSERT(scaleStart >= 0 && scaleStart <= 64);
437             scaleStop = 0;
438         } else {
439             scaleStart = 64 - (x0 & 63);
440             scaleStop = x1 & 63;
441         }
442 
443         if (clip){
444             if (istart >= clip->fRight || istop <= clip->fLeft) {
445                 return;
446             }
447             if (istart < clip->fLeft) {
448                 fstart += slope * (clip->fLeft - istart);
449                 istart = clip->fLeft;
450                 scaleStart = 64;
451                 if (istop - istart == 1) {
452                     // we are within a single pixel
453                     scaleStart = contribution_64(x1);
454                     scaleStop = 0;
455                 }
456             }
457             if (istop > clip->fRight) {
458                 istop = clip->fRight;
459                 scaleStop = 0;  // so we don't draw this last column
460             }
461 
462             SkASSERT(istart <= istop);
463             if (istart == istop) {
464                 return;
465             }
466             // now test if our Y values are completely inside the clip
467             int top, bottom;
468             if (slope >= 0) { // T2B
469                 top = SkFixedFloorToInt(fstart - SK_FixedHalf);
470                 bottom = SkFixedCeilToInt(fstart + (istop - istart - 1) * slope + SK_FixedHalf);
471             } else {           // B2T
472                 bottom = SkFixedCeilToInt(fstart + SK_FixedHalf);
473                 top = SkFixedFloorToInt(fstart + (istop - istart - 1) * slope - SK_FixedHalf);
474             }
475 #ifdef OUTSET_BEFORE_CLIP_TEST
476             top -= 1;
477             bottom += 1;
478 #endif
479             if (top >= clip->fBottom || bottom <= clip->fTop) {
480                 return;
481             }
482             if (clip->fTop <= top && clip->fBottom >= bottom) {
483                 clip = NULL;
484             }
485         }
486     } else {   // mostly vertical
487         if (y0 > y1) {  // we want to go top-to-bottom
488             SkTSwap<SkFDot6>(x0, x1);
489             SkTSwap<SkFDot6>(y0, y1);
490         }
491 
492         istart = SkFDot6Floor(y0);
493         istop = SkFDot6Ceil(y1);
494         fstart = SkFDot6ToFixed(x0);
495         if (x0 == x1) {
496             if (y0 == y1) { // are we zero length?
497                 return;     // nothing to do
498             }
499             slope = 0;
500             hairBlitter = &vline_blitter;
501         } else {
502             slope = fastfixdiv(x1 - x0, y1 - y0);
503             SkASSERT(slope <= SK_Fixed1 && slope >= -SK_Fixed1);
504             fstart += (slope * (32 - (y0 & 63)) + 32) >> 6;
505             hairBlitter = &vertish_blitter;
506         }
507 
508         SkASSERT(istop > istart);
509         if (istop - istart == 1) {
510             // we are within a single pixel
511             scaleStart = y1 - y0;
512             SkASSERT(scaleStart >= 0 && scaleStart <= 64);
513             scaleStop = 0;
514         } else {
515             scaleStart = 64 - (y0 & 63);
516             scaleStop = y1 & 63;
517         }
518 
519         if (clip) {
520             if (istart >= clip->fBottom || istop <= clip->fTop) {
521                 return;
522             }
523             if (istart < clip->fTop) {
524                 fstart += slope * (clip->fTop - istart);
525                 istart = clip->fTop;
526                 scaleStart = 64;
527                 if (istop - istart == 1) {
528                     // we are within a single pixel
529                     scaleStart = contribution_64(y1);
530                     scaleStop = 0;
531                 }
532             }
533             if (istop > clip->fBottom) {
534                 istop = clip->fBottom;
535                 scaleStop = 0;  // so we don't draw this last row
536             }
537 
538             SkASSERT(istart <= istop);
539             if (istart == istop)
540                 return;
541 
542             // now test if our X values are completely inside the clip
543             int left, right;
544             if (slope >= 0) { // L2R
545                 left = SkFixedFloorToInt(fstart - SK_FixedHalf);
546                 right = SkFixedCeilToInt(fstart + (istop - istart - 1) * slope + SK_FixedHalf);
547             } else {           // R2L
548                 right = SkFixedCeilToInt(fstart + SK_FixedHalf);
549                 left = SkFixedFloorToInt(fstart + (istop - istart - 1) * slope - SK_FixedHalf);
550             }
551 #ifdef OUTSET_BEFORE_CLIP_TEST
552             left -= 1;
553             right += 1;
554 #endif
555             if (left >= clip->fRight || right <= clip->fLeft) {
556                 return;
557             }
558             if (clip->fLeft <= left && clip->fRight >= right) {
559                 clip = NULL;
560             }
561         }
562     }
563 
564     SkRectClipBlitter   rectClipper;
565     if (clip) {
566         rectClipper.init(blitter, *clip);
567         blitter = &rectClipper;
568     }
569 
570     SkASSERT(hairBlitter);
571     hairBlitter->setup(blitter);
572 
573 #ifdef SK_DEBUG
574     if (scaleStart > 0 && scaleStop > 0) {
575         // be sure we don't draw twice in the same pixel
576         SkASSERT(istart < istop - 1);
577     }
578 #endif
579 
580     fstart = hairBlitter->drawCap(istart, fstart, slope, scaleStart);
581     istart += 1;
582     int fullSpans = istop - istart - (scaleStop > 0);
583     if (fullSpans > 0) {
584         fstart = hairBlitter->drawLine(istart, istart + fullSpans, fstart, slope);
585     }
586     if (scaleStop > 0) {
587         hairBlitter->drawCap(istop - 1, fstart, slope, scaleStop);
588     }
589 }
590 
AntiHairLineRgn(const SkPoint & pt0,const SkPoint & pt1,const SkRegion * clip,SkBlitter * blitter)591 void SkScan::AntiHairLineRgn(const SkPoint& pt0, const SkPoint& pt1,
592                              const SkRegion* clip, SkBlitter* blitter) {
593     if (clip && clip->isEmpty()) {
594         return;
595     }
596 
597     SkASSERT(clip == NULL || !clip->getBounds().isEmpty());
598 
599 #ifdef TEST_GAMMA
600     build_gamma_table();
601 #endif
602 
603     SkPoint pts[2] = { pt0, pt1 };
604 
605     // We have to pre-clip the line to fit in a SkFixed, so we just chop
606     // the line. TODO find a way to actually draw beyond that range.
607     {
608         SkRect fixedBounds;
609         const SkScalar max = SkIntToScalar(32767);
610         fixedBounds.set(-max, -max, max, max);
611         if (!SkLineClipper::IntersectLine(pts, fixedBounds, pts)) {
612             return;
613         }
614     }
615 
616     if (clip) {
617         SkRect clipBounds;
618         clipBounds.set(clip->getBounds());
619         /*  We perform integral clipping later on, but we do a scalar clip first
620             to ensure that our coordinates are expressible in fixed/integers.
621 
622             antialiased hairlines can draw up to 1/2 of a pixel outside of
623             their bounds, so we need to outset the clip before calling the
624             clipper. To make the numerics safer, we outset by a whole pixel,
625             since the 1/2 pixel boundary is important to the antihair blitter,
626             we don't want to risk numerical fate by chopping on that edge.
627          */
628         clipBounds.inset(-SK_Scalar1, -SK_Scalar1);
629 
630         if (!SkLineClipper::IntersectLine(pts, clipBounds, pts)) {
631             return;
632         }
633     }
634 
635     SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
636     SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
637     SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
638     SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
639 
640     if (clip) {
641         SkFDot6 left = SkMin32(x0, x1);
642         SkFDot6 top = SkMin32(y0, y1);
643         SkFDot6 right = SkMax32(x0, x1);
644         SkFDot6 bottom = SkMax32(y0, y1);
645         SkIRect ir;
646 
647         ir.set( SkFDot6Floor(left) - 1,
648                 SkFDot6Floor(top) - 1,
649                 SkFDot6Ceil(right) + 1,
650                 SkFDot6Ceil(bottom) + 1);
651 
652         if (clip->quickReject(ir)) {
653             return;
654         }
655         if (!clip->quickContains(ir)) {
656             SkRegion::Cliperator iter(*clip, ir);
657             const SkIRect*       r = &iter.rect();
658 
659             while (!iter.done()) {
660                 do_anti_hairline(x0, y0, x1, y1, r, blitter);
661                 iter.next();
662             }
663             return;
664         }
665         // fall through to no-clip case
666     }
667     do_anti_hairline(x0, y0, x1, y1, NULL, blitter);
668 }
669 
AntiHairRect(const SkRect & rect,const SkRasterClip & clip,SkBlitter * blitter)670 void SkScan::AntiHairRect(const SkRect& rect, const SkRasterClip& clip,
671                           SkBlitter* blitter) {
672     SkPoint p0, p1;
673 
674     p0.set(rect.fLeft, rect.fTop);
675     p1.set(rect.fRight, rect.fTop);
676     SkScan::AntiHairLine(p0, p1, clip, blitter);
677     p0.set(rect.fRight, rect.fBottom);
678     SkScan::AntiHairLine(p0, p1, clip, blitter);
679     p1.set(rect.fLeft, rect.fBottom);
680     SkScan::AntiHairLine(p0, p1, clip, blitter);
681     p0.set(rect.fLeft, rect.fTop);
682     SkScan::AntiHairLine(p0, p1, clip, blitter);
683 }
684 
685 ///////////////////////////////////////////////////////////////////////////////
686 
687 typedef int FDot8;  // 24.8 integer fixed point
688 
SkFixedToFDot8(SkFixed x)689 static inline FDot8 SkFixedToFDot8(SkFixed x) {
690     return (x + 0x80) >> 8;
691 }
692 
do_scanline(FDot8 L,int top,FDot8 R,U8CPU alpha,SkBlitter * blitter)693 static void do_scanline(FDot8 L, int top, FDot8 R, U8CPU alpha,
694                         SkBlitter* blitter) {
695     SkASSERT(L < R);
696 
697     if ((L >> 8) == ((R - 1) >> 8)) {  // 1x1 pixel
698         blitter->blitV(L >> 8, top, 1, SkAlphaMul(alpha, R - L));
699         return;
700     }
701 
702     int left = L >> 8;
703 
704     if (L & 0xFF) {
705         blitter->blitV(left, top, 1, SkAlphaMul(alpha, 256 - (L & 0xFF)));
706         left += 1;
707     }
708 
709     int rite = R >> 8;
710     int width = rite - left;
711     if (width > 0) {
712         call_hline_blitter(blitter, left, top, width, alpha);
713     }
714     if (R & 0xFF) {
715         blitter->blitV(rite, top, 1, SkAlphaMul(alpha, R & 0xFF));
716     }
717 }
718 
antifilldot8(FDot8 L,FDot8 T,FDot8 R,FDot8 B,SkBlitter * blitter,bool fillInner)719 static void antifilldot8(FDot8 L, FDot8 T, FDot8 R, FDot8 B, SkBlitter* blitter,
720                          bool fillInner) {
721     // check for empty now that we're in our reduced precision space
722     if (L >= R || T >= B) {
723         return;
724     }
725     int top = T >> 8;
726     if (top == ((B - 1) >> 8)) {   // just one scanline high
727         do_scanline(L, top, R, B - T - 1, blitter);
728         return;
729     }
730 
731     if (T & 0xFF) {
732         do_scanline(L, top, R, 256 - (T & 0xFF), blitter);
733         top += 1;
734     }
735 
736     int bot = B >> 8;
737     int height = bot - top;
738     if (height > 0) {
739         int left = L >> 8;
740         if (left == ((R - 1) >> 8)) {   // just 1-pixel wide
741             blitter->blitV(left, top, height, R - L - 1);
742         } else {
743             if (L & 0xFF) {
744                 blitter->blitV(left, top, height, 256 - (L & 0xFF));
745                 left += 1;
746             }
747             int rite = R >> 8;
748             int width = rite - left;
749             if (width > 0 && fillInner) {
750                 blitter->blitRect(left, top, width, height);
751             }
752             if (R & 0xFF) {
753                 blitter->blitV(rite, top, height, R & 0xFF);
754             }
755         }
756     }
757 
758     if (B & 0xFF) {
759         do_scanline(L, bot, R, B & 0xFF, blitter);
760     }
761 }
762 
antifillrect(const SkXRect & xr,SkBlitter * blitter)763 static void antifillrect(const SkXRect& xr, SkBlitter* blitter) {
764     antifilldot8(SkFixedToFDot8(xr.fLeft), SkFixedToFDot8(xr.fTop),
765                  SkFixedToFDot8(xr.fRight), SkFixedToFDot8(xr.fBottom),
766                  blitter, true);
767 }
768 
769 ///////////////////////////////////////////////////////////////////////////////
770 
AntiFillXRect(const SkXRect & xr,const SkRegion * clip,SkBlitter * blitter)771 void SkScan::AntiFillXRect(const SkXRect& xr, const SkRegion* clip,
772                           SkBlitter* blitter) {
773     if (NULL == clip) {
774         antifillrect(xr, blitter);
775     } else {
776         SkIRect outerBounds;
777         XRect_roundOut(xr, &outerBounds);
778 
779         if (clip->isRect()) {
780             const SkIRect& clipBounds = clip->getBounds();
781 
782             if (clipBounds.contains(outerBounds)) {
783                 antifillrect(xr, blitter);
784             } else {
785                 SkXRect tmpR;
786                 // this keeps our original edges fractional
787                 XRect_set(&tmpR, clipBounds);
788                 if (tmpR.intersect(xr)) {
789                     antifillrect(tmpR, blitter);
790                 }
791             }
792         } else {
793             SkRegion::Cliperator clipper(*clip, outerBounds);
794             const SkIRect&       rr = clipper.rect();
795 
796             while (!clipper.done()) {
797                 SkXRect  tmpR;
798 
799                 // this keeps our original edges fractional
800                 XRect_set(&tmpR, rr);
801                 if (tmpR.intersect(xr)) {
802                     antifillrect(tmpR, blitter);
803                 }
804                 clipper.next();
805             }
806         }
807     }
808 }
809 
AntiFillXRect(const SkXRect & xr,const SkRasterClip & clip,SkBlitter * blitter)810 void SkScan::AntiFillXRect(const SkXRect& xr, const SkRasterClip& clip,
811                            SkBlitter* blitter) {
812     if (clip.isBW()) {
813         AntiFillXRect(xr, &clip.bwRgn(), blitter);
814     } else {
815         SkIRect outerBounds;
816         XRect_roundOut(xr, &outerBounds);
817 
818         if (clip.quickContains(outerBounds)) {
819             AntiFillXRect(xr, NULL, blitter);
820         } else {
821             SkAAClipBlitterWrapper wrapper(clip, blitter);
822             blitter = wrapper.getBlitter();
823 
824             AntiFillXRect(xr, &wrapper.getRgn(), wrapper.getBlitter());
825         }
826     }
827 }
828 
829 /*  This guy takes a float-rect, but with the key improvement that it has
830     already been clipped, so we know that it is safe to convert it into a
831     XRect (fixedpoint), as it won't overflow.
832 */
antifillrect(const SkRect & r,SkBlitter * blitter)833 static void antifillrect(const SkRect& r, SkBlitter* blitter) {
834     SkXRect xr;
835 
836     XRect_set(&xr, r);
837     antifillrect(xr, blitter);
838 }
839 
840 /*  We repeat the clipping logic of AntiFillXRect because the float rect might
841     overflow if we blindly converted it to an XRect. This sucks that we have to
842     repeat the clipping logic, but I don't see how to share the code/logic.
843 
844     We clip r (as needed) into one or more (smaller) float rects, and then pass
845     those to our version of antifillrect, which converts it into an XRect and
846     then calls the blit.
847 */
AntiFillRect(const SkRect & origR,const SkRegion * clip,SkBlitter * blitter)848 void SkScan::AntiFillRect(const SkRect& origR, const SkRegion* clip,
849                           SkBlitter* blitter) {
850     if (clip) {
851         SkRect newR;
852         newR.set(clip->getBounds());
853         if (!newR.intersect(origR)) {
854             return;
855         }
856 
857         SkIRect outerBounds;
858         newR.roundOut(&outerBounds);
859 
860         if (clip->isRect()) {
861             antifillrect(newR, blitter);
862         } else {
863             SkRegion::Cliperator clipper(*clip, outerBounds);
864             while (!clipper.done()) {
865                 newR.set(clipper.rect());
866                 if (newR.intersect(origR)) {
867                     antifillrect(newR, blitter);
868                 }
869                 clipper.next();
870             }
871         }
872     } else {
873         antifillrect(origR, blitter);
874     }
875 }
876 
AntiFillRect(const SkRect & r,const SkRasterClip & clip,SkBlitter * blitter)877 void SkScan::AntiFillRect(const SkRect& r, const SkRasterClip& clip,
878                           SkBlitter* blitter) {
879     if (clip.isBW()) {
880         AntiFillRect(r, &clip.bwRgn(), blitter);
881     } else {
882         SkAAClipBlitterWrapper wrap(clip, blitter);
883         AntiFillRect(r, &wrap.getRgn(), wrap.getBlitter());
884     }
885 }
886 
887 ///////////////////////////////////////////////////////////////////////////////
888 
889 #define SkAlphaMulRound(a, b)   SkMulDiv255Round(a, b)
890 
891 // calls blitRect() if the rectangle is non-empty
fillcheckrect(int L,int T,int R,int B,SkBlitter * blitter)892 static void fillcheckrect(int L, int T, int R, int B, SkBlitter* blitter) {
893     if (L < R && T < B) {
894         blitter->blitRect(L, T, R - L, B - T);
895     }
896 }
897 
SkScalarToFDot8(SkScalar x)898 static inline FDot8 SkScalarToFDot8(SkScalar x) {
899     return (int)(x * 256);
900 }
901 
FDot8Floor(FDot8 x)902 static inline int FDot8Floor(FDot8 x) {
903     return x >> 8;
904 }
905 
FDot8Ceil(FDot8 x)906 static inline int FDot8Ceil(FDot8 x) {
907     return (x + 0xFF) >> 8;
908 }
909 
910 // 1 - (1 - a)*(1 - b)
InvAlphaMul(U8CPU a,U8CPU b)911 static inline U8CPU InvAlphaMul(U8CPU a, U8CPU b) {
912     // need precise rounding (not just SkAlphaMul) so that values like
913     // a=228, b=252 don't overflow the result
914     return SkToU8(a + b - SkAlphaMulRound(a, b));
915 }
916 
inner_scanline(FDot8 L,int top,FDot8 R,U8CPU alpha,SkBlitter * blitter)917 static void inner_scanline(FDot8 L, int top, FDot8 R, U8CPU alpha,
918                            SkBlitter* blitter) {
919     SkASSERT(L < R);
920 
921     if ((L >> 8) == ((R - 1) >> 8)) {  // 1x1 pixel
922         blitter->blitV(L >> 8, top, 1, InvAlphaMul(alpha, R - L));
923         return;
924     }
925 
926     int left = L >> 8;
927     if (L & 0xFF) {
928         blitter->blitV(left, top, 1, InvAlphaMul(alpha, L & 0xFF));
929         left += 1;
930     }
931 
932     int rite = R >> 8;
933     int width = rite - left;
934     if (width > 0) {
935         call_hline_blitter(blitter, left, top, width, alpha);
936     }
937 
938     if (R & 0xFF) {
939         blitter->blitV(rite, top, 1, InvAlphaMul(alpha, ~R & 0xFF));
940     }
941 }
942 
innerstrokedot8(FDot8 L,FDot8 T,FDot8 R,FDot8 B,SkBlitter * blitter)943 static void innerstrokedot8(FDot8 L, FDot8 T, FDot8 R, FDot8 B,
944                             SkBlitter* blitter) {
945     SkASSERT(L < R && T < B);
946 
947     int top = T >> 8;
948     if (top == ((B - 1) >> 8)) {   // just one scanline high
949         // We want the inverse of B-T, since we're the inner-stroke
950         int alpha = 256 - (B - T);
951         if (alpha) {
952             inner_scanline(L, top, R, alpha, blitter);
953         }
954         return;
955     }
956 
957     if (T & 0xFF) {
958         inner_scanline(L, top, R, T & 0xFF, blitter);
959         top += 1;
960     }
961 
962     int bot = B >> 8;
963     int height = bot - top;
964     if (height > 0) {
965         if (L & 0xFF) {
966             blitter->blitV(L >> 8, top, height, L & 0xFF);
967         }
968         if (R & 0xFF) {
969             blitter->blitV(R >> 8, top, height, ~R & 0xFF);
970         }
971     }
972 
973     if (B & 0xFF) {
974         inner_scanline(L, bot, R, ~B & 0xFF, blitter);
975     }
976 }
977 
AntiFrameRect(const SkRect & r,const SkPoint & strokeSize,const SkRegion * clip,SkBlitter * blitter)978 void SkScan::AntiFrameRect(const SkRect& r, const SkPoint& strokeSize,
979                            const SkRegion* clip, SkBlitter* blitter) {
980     SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
981 
982     SkScalar rx = SkScalarHalf(strokeSize.fX);
983     SkScalar ry = SkScalarHalf(strokeSize.fY);
984 
985     // outset by the radius
986     FDot8 L = SkScalarToFDot8(r.fLeft - rx);
987     FDot8 T = SkScalarToFDot8(r.fTop - ry);
988     FDot8 R = SkScalarToFDot8(r.fRight + rx);
989     FDot8 B = SkScalarToFDot8(r.fBottom + ry);
990 
991     SkIRect outer;
992     // set outer to the outer rect of the outer section
993     outer.set(FDot8Floor(L), FDot8Floor(T), FDot8Ceil(R), FDot8Ceil(B));
994 
995     SkBlitterClipper clipper;
996     if (clip) {
997         if (clip->quickReject(outer)) {
998             return;
999         }
1000         if (!clip->contains(outer)) {
1001             blitter = clipper.apply(blitter, clip, &outer);
1002         }
1003         // now we can ignore clip for the rest of the function
1004     }
1005 
1006     // stroke the outer hull
1007     antifilldot8(L, T, R, B, blitter, false);
1008 
1009     // set outer to the outer rect of the middle section
1010     outer.set(FDot8Ceil(L), FDot8Ceil(T), FDot8Floor(R), FDot8Floor(B));
1011 
1012     // in case we lost a bit with diameter/2
1013     rx = strokeSize.fX - rx;
1014     ry = strokeSize.fY - ry;
1015     // inset by the radius
1016     L = SkScalarToFDot8(r.fLeft + rx);
1017     T = SkScalarToFDot8(r.fTop + ry);
1018     R = SkScalarToFDot8(r.fRight - rx);
1019     B = SkScalarToFDot8(r.fBottom - ry);
1020 
1021     if (L >= R || T >= B) {
1022         fillcheckrect(outer.fLeft, outer.fTop, outer.fRight, outer.fBottom,
1023                       blitter);
1024     } else {
1025         SkIRect inner;
1026         // set inner to the inner rect of the middle section
1027         inner.set(FDot8Floor(L), FDot8Floor(T), FDot8Ceil(R), FDot8Ceil(B));
1028 
1029         // draw the frame in 4 pieces
1030         fillcheckrect(outer.fLeft, outer.fTop, outer.fRight, inner.fTop,
1031                       blitter);
1032         fillcheckrect(outer.fLeft, inner.fTop, inner.fLeft, inner.fBottom,
1033                       blitter);
1034         fillcheckrect(inner.fRight, inner.fTop, outer.fRight, inner.fBottom,
1035                       blitter);
1036         fillcheckrect(outer.fLeft, inner.fBottom, outer.fRight, outer.fBottom,
1037                       blitter);
1038 
1039         // now stroke the inner rect, which is similar to antifilldot8() except that
1040         // it treats the fractional coordinates with the inverse bias (since its
1041         // inner).
1042         innerstrokedot8(L, T, R, B, blitter);
1043     }
1044 }
1045 
AntiFrameRect(const SkRect & r,const SkPoint & strokeSize,const SkRasterClip & clip,SkBlitter * blitter)1046 void SkScan::AntiFrameRect(const SkRect& r, const SkPoint& strokeSize,
1047                            const SkRasterClip& clip, SkBlitter* blitter) {
1048     if (clip.isBW()) {
1049         AntiFrameRect(r, strokeSize, &clip.bwRgn(), blitter);
1050     } else {
1051         SkAAClipBlitterWrapper wrap(clip, blitter);
1052         AntiFrameRect(r, strokeSize, &wrap.getRgn(), wrap.getBlitter());
1053     }
1054 }
1055