michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #include "SkScan.h"
michael@0: #include "SkBlitter.h"
michael@0: #include "SkColorPriv.h"
michael@0: #include "SkLineClipper.h"
michael@0: #include "SkRasterClip.h"
michael@0: #include "SkFDot6.h"
michael@0: 
michael@0: /*  Our attempt to compute the worst case "bounds" for the horizontal and
michael@0:     vertical cases has some numerical bug in it, and we sometimes undervalue
michael@0:     our extends. The bug is that when this happens, we will set the clip to
michael@0:     NULL (for speed), and thus draw outside of the clip by a pixel, which might
michael@0:     only look bad, but it might also access memory outside of the valid range
michael@0:     allcoated for the device bitmap.
michael@0: 
michael@0:     This define enables our fix to outset our "bounds" by 1, thus avoiding the
michael@0:     chance of the bug, but at the cost of sometimes taking the rectblitter
michael@0:     case (i.e. not setting the clip to NULL) when we might not actually need
michael@0:     to. If we can improve/fix the actual calculations, then we can remove this
michael@0:     step.
michael@0:  */
michael@0: #define OUTSET_BEFORE_CLIP_TEST     true
michael@0: 
michael@0: #define HLINE_STACK_BUFFER      100
michael@0: 
michael@0: static inline int SmallDot6Scale(int value, int dot6) {
michael@0:     SkASSERT((int16_t)value == value);
michael@0:     SkASSERT((unsigned)dot6 <= 64);
michael@0:     return SkMulS16(value, dot6) >> 6;
michael@0: }
michael@0: 
michael@0: //#define TEST_GAMMA
michael@0: 
michael@0: #ifdef TEST_GAMMA
michael@0:     static uint8_t gGammaTable[256];
michael@0:     #define ApplyGamma(table, alpha)    (table)[alpha]
michael@0: 
michael@0:     static void build_gamma_table() {
michael@0:         static bool gInit = false;
michael@0: 
michael@0:         if (gInit == false) {
michael@0:             for (int i = 0; i < 256; i++) {
michael@0:                 SkFixed n = i * 257;
michael@0:                 n += n >> 15;
michael@0:                 SkASSERT(n >= 0 && n <= SK_Fixed1);
michael@0:                 n = SkFixedSqrt(n);
michael@0:                 n = n * 255 >> 16;
michael@0:             //  SkDebugf("morph %d -> %d\n", i, n);
michael@0:                 gGammaTable[i] = SkToU8(n);
michael@0:             }
michael@0:             gInit = true;
michael@0:         }
michael@0:     }
michael@0: #else
michael@0:     #define ApplyGamma(table, alpha)    SkToU8(alpha)
michael@0: #endif
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static void call_hline_blitter(SkBlitter* blitter, int x, int y, int count,
michael@0:                                U8CPU alpha) {
michael@0:     SkASSERT(count > 0);
michael@0: 
michael@0:     int16_t runs[HLINE_STACK_BUFFER + 1];
michael@0:     uint8_t  aa[HLINE_STACK_BUFFER];
michael@0: 
michael@0:     aa[0] = ApplyGamma(gGammaTable, alpha);
michael@0:     do {
michael@0:         int n = count;
michael@0:         if (n > HLINE_STACK_BUFFER) {
michael@0:             n = HLINE_STACK_BUFFER;
michael@0:         }
michael@0:         runs[0] = SkToS16(n);
michael@0:         runs[n] = 0;
michael@0:         blitter->blitAntiH(x, y, aa, runs);
michael@0:         x += n;
michael@0:         count -= n;
michael@0:     } while (count > 0);
michael@0: }
michael@0: 
michael@0: class SkAntiHairBlitter {
michael@0: public:
michael@0:     SkAntiHairBlitter() : fBlitter(NULL) {}
michael@0:     virtual ~SkAntiHairBlitter() {}
michael@0: 
michael@0:     SkBlitter* getBlitter() const { return fBlitter; }
michael@0: 
michael@0:     void setup(SkBlitter* blitter) {
michael@0:         fBlitter = blitter;
michael@0:     }
michael@0: 
michael@0:     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed slope, int mod64) = 0;
michael@0:     virtual SkFixed drawLine(int x, int stopx, SkFixed fy, SkFixed slope) = 0;
michael@0: 
michael@0: private:
michael@0:     SkBlitter*  fBlitter;
michael@0: };
michael@0: 
michael@0: class HLine_SkAntiHairBlitter : public SkAntiHairBlitter {
michael@0: public:
michael@0:     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed slope, int mod64) SK_OVERRIDE {
michael@0:         fy += SK_Fixed1/2;
michael@0: 
michael@0:         int y = fy >> 16;
michael@0:         uint8_t  a = (uint8_t)(fy >> 8);
michael@0: 
michael@0:         // lower line
michael@0:         unsigned ma = SmallDot6Scale(a, mod64);
michael@0:         if (ma) {
michael@0:             call_hline_blitter(this->getBlitter(), x, y, 1, ma);
michael@0:         }
michael@0: 
michael@0:         // upper line
michael@0:         ma = SmallDot6Scale(255 - a, mod64);
michael@0:         if (ma) {
michael@0:             call_hline_blitter(this->getBlitter(), x, y - 1, 1, ma);
michael@0:         }
michael@0: 
michael@0:         return fy - SK_Fixed1/2;
michael@0:     }
michael@0: 
michael@0:     virtual SkFixed drawLine(int x, int stopx, SkFixed fy,
michael@0:                              SkFixed slope) SK_OVERRIDE {
michael@0:         SkASSERT(x < stopx);
michael@0:         int count = stopx - x;
michael@0:         fy += SK_Fixed1/2;
michael@0: 
michael@0:         int y = fy >> 16;
michael@0:         uint8_t  a = (uint8_t)(fy >> 8);
michael@0: 
michael@0:         // lower line
michael@0:         if (a) {
michael@0:             call_hline_blitter(this->getBlitter(), x, y, count, a);
michael@0:         }
michael@0: 
michael@0:         // upper line
michael@0:         a = 255 - a;
michael@0:         if (a) {
michael@0:             call_hline_blitter(this->getBlitter(), x, y - 1, count, a);
michael@0:         }
michael@0: 
michael@0:         return fy - SK_Fixed1/2;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class Horish_SkAntiHairBlitter : public SkAntiHairBlitter {
michael@0: public:
michael@0:     virtual SkFixed drawCap(int x, SkFixed fy, SkFixed dy, int mod64) SK_OVERRIDE {
michael@0:         int16_t runs[2];
michael@0:         uint8_t  aa[1];
michael@0: 
michael@0:         runs[0] = 1;
michael@0:         runs[1] = 0;
michael@0: 
michael@0:         fy += SK_Fixed1/2;
michael@0:         SkBlitter* blitter = this->getBlitter();
michael@0: 
michael@0:         int lower_y = fy >> 16;
michael@0:         uint8_t  a = (uint8_t)(fy >> 8);
michael@0:         unsigned ma = SmallDot6Scale(a, mod64);
michael@0:         if (ma) {
michael@0:             aa[0] = ApplyGamma(gamma, ma);
michael@0:             blitter->blitAntiH(x, lower_y, aa, runs);
michael@0:             // the clipping blitters might edit runs, but should not affect us
michael@0:             SkASSERT(runs[0] == 1);
michael@0:             SkASSERT(runs[1] == 0);
michael@0:         }
michael@0:         ma = SmallDot6Scale(255 - a, mod64);
michael@0:         if (ma) {
michael@0:             aa[0] = ApplyGamma(gamma, ma);
michael@0:             blitter->blitAntiH(x, lower_y - 1, aa, runs);
michael@0:             // the clipping blitters might edit runs, but should not affect us
michael@0:             SkASSERT(runs[0] == 1);
michael@0:             SkASSERT(runs[1] == 0);
michael@0:         }
michael@0:         fy += dy;
michael@0: 
michael@0:         return fy - SK_Fixed1/2;
michael@0:     }
michael@0: 
michael@0:     virtual SkFixed drawLine(int x, int stopx, SkFixed fy, SkFixed dy) SK_OVERRIDE {
michael@0:         SkASSERT(x < stopx);
michael@0: 
michael@0:         int16_t runs[2];
michael@0:         uint8_t  aa[1];
michael@0: 
michael@0:         runs[0] = 1;
michael@0:         runs[1] = 0;
michael@0: 
michael@0:         fy += SK_Fixed1/2;
michael@0:         SkBlitter* blitter = this->getBlitter();
michael@0:         do {
michael@0:             int lower_y = fy >> 16;
michael@0:             uint8_t  a = (uint8_t)(fy >> 8);
michael@0:             if (a) {
michael@0:                 aa[0] = a;
michael@0:                 blitter->blitAntiH(x, lower_y, aa, runs);
michael@0:                 // the clipping blitters might edit runs, but should not affect us
michael@0:                 SkASSERT(runs[0] == 1);
michael@0:                 SkASSERT(runs[1] == 0);
michael@0:             }
michael@0:             a = 255 - a;
michael@0:             if (a) {
michael@0:                 aa[0] = a;
michael@0:                 blitter->blitAntiH(x, lower_y - 1, aa, runs);
michael@0:                 // the clipping blitters might edit runs, but should not affect us
michael@0:                 SkASSERT(runs[0] == 1);
michael@0:                 SkASSERT(runs[1] == 0);
michael@0:             }
michael@0:             fy += dy;
michael@0:         } while (++x < stopx);
michael@0: 
michael@0:         return fy - SK_Fixed1/2;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class VLine_SkAntiHairBlitter : public SkAntiHairBlitter {
michael@0: public:
michael@0:     virtual SkFixed drawCap(int y, SkFixed fx, SkFixed dx, int mod64) SK_OVERRIDE {
michael@0:         SkASSERT(0 == dx);
michael@0:         fx += SK_Fixed1/2;
michael@0: 
michael@0:         int x = fx >> 16;
michael@0:         int a = (uint8_t)(fx >> 8);
michael@0: 
michael@0:         unsigned ma = SmallDot6Scale(a, mod64);
michael@0:         if (ma) {
michael@0:             this->getBlitter()->blitV(x, y, 1, ma);
michael@0:         }
michael@0:         ma = SmallDot6Scale(255 - a, mod64);
michael@0:         if (ma) {
michael@0:             this->getBlitter()->blitV(x - 1, y, 1, ma);
michael@0:         }
michael@0: 
michael@0:         return fx - SK_Fixed1/2;
michael@0:     }
michael@0: 
michael@0:     virtual SkFixed drawLine(int y, int stopy, SkFixed fx, SkFixed dx) SK_OVERRIDE {
michael@0:         SkASSERT(y < stopy);
michael@0:         SkASSERT(0 == dx);
michael@0:         fx += SK_Fixed1/2;
michael@0: 
michael@0:         int x = fx >> 16;
michael@0:         int a = (uint8_t)(fx >> 8);
michael@0: 
michael@0:         if (a) {
michael@0:             this->getBlitter()->blitV(x, y, stopy - y, a);
michael@0:         }
michael@0:         a = 255 - a;
michael@0:         if (a) {
michael@0:             this->getBlitter()->blitV(x - 1, y, stopy - y, a);
michael@0:         }
michael@0: 
michael@0:         return fx - SK_Fixed1/2;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class Vertish_SkAntiHairBlitter : public SkAntiHairBlitter {
michael@0: public:
michael@0:     virtual SkFixed drawCap(int y, SkFixed fx, SkFixed dx, int mod64) SK_OVERRIDE {
michael@0:         int16_t runs[3];
michael@0:         uint8_t  aa[2];
michael@0: 
michael@0:         runs[0] = 1;
michael@0:         runs[2] = 0;
michael@0: 
michael@0:         fx += SK_Fixed1/2;
michael@0:         int x = fx >> 16;
michael@0:         uint8_t  a = (uint8_t)(fx >> 8);
michael@0: 
michael@0:         aa[0] = SmallDot6Scale(255 - a, mod64);
michael@0:         aa[1] = SmallDot6Scale(a, mod64);
michael@0:         // the clippng blitters might overwrite this guy, so we have to reset it each time
michael@0:         runs[1] = 1;
michael@0:         this->getBlitter()->blitAntiH(x - 1, y, aa, runs);
michael@0:         // the clipping blitters might edit runs, but should not affect us
michael@0:         SkASSERT(runs[0] == 1);
michael@0:         SkASSERT(runs[2] == 0);
michael@0:         fx += dx;
michael@0: 
michael@0:         return fx - SK_Fixed1/2;
michael@0:     }
michael@0: 
michael@0:     virtual SkFixed drawLine(int y, int stopy, SkFixed fx, SkFixed dx) SK_OVERRIDE {
michael@0:         SkASSERT(y < stopy);
michael@0:         int16_t runs[3];
michael@0:         uint8_t  aa[2];
michael@0: 
michael@0:         runs[0] = 1;
michael@0:         runs[2] = 0;
michael@0: 
michael@0:         fx += SK_Fixed1/2;
michael@0:         do {
michael@0:             int x = fx >> 16;
michael@0:             uint8_t  a = (uint8_t)(fx >> 8);
michael@0: 
michael@0:             aa[0] = 255 - a;
michael@0:             aa[1] = a;
michael@0:             // the clippng blitters might overwrite this guy, so we have to reset it each time
michael@0:             runs[1] = 1;
michael@0:             this->getBlitter()->blitAntiH(x - 1, y, aa, runs);
michael@0:             // the clipping blitters might edit runs, but should not affect us
michael@0:             SkASSERT(runs[0] == 1);
michael@0:             SkASSERT(runs[2] == 0);
michael@0:             fx += dx;
michael@0:         } while (++y < stopy);
michael@0: 
michael@0:         return fx - SK_Fixed1/2;
michael@0:     }
michael@0: };
michael@0: 
michael@0: static inline SkFixed fastfixdiv(SkFDot6 a, SkFDot6 b) {
michael@0:     SkASSERT((a << 16 >> 16) == a);
michael@0:     SkASSERT(b != 0);
michael@0:     return (a << 16) / b;
michael@0: }
michael@0: 
michael@0: #define SkBITCOUNT(x)   (sizeof(x) << 3)
michael@0: 
michael@0: #if 1
michael@0: // returns high-bit set iff x==0x8000...
michael@0: static inline int bad_int(int x) {
michael@0:     return x & -x;
michael@0: }
michael@0: 
michael@0: static int any_bad_ints(int a, int b, int c, int d) {
michael@0:     return (bad_int(a) | bad_int(b) | bad_int(c) | bad_int(d)) >> (SkBITCOUNT(int) - 1);
michael@0: }
michael@0: #else
michael@0: static inline int good_int(int x) {
michael@0:     return x ^ (1 << (SkBITCOUNT(x) - 1));
michael@0: }
michael@0: 
michael@0: static int any_bad_ints(int a, int b, int c, int d) {
michael@0:     return !(good_int(a) & good_int(b) & good_int(c) & good_int(d));
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: static bool canConvertFDot6ToFixed(SkFDot6 x) {
michael@0:     const int maxDot6 = SK_MaxS32 >> (16 - 6);
michael@0:     return SkAbs32(x) <= maxDot6;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  *  We want the fractional part of ordinate, but we want multiples of 64 to
michael@0:  *  return 64, not 0, so we can't just say (ordinate & 63).
michael@0:  *  We basically want to compute those bits, and if they're 0, return 64.
michael@0:  *  We can do that w/o a branch with an extra sub and add.
michael@0:  */
michael@0: static int contribution_64(SkFDot6 ordinate) {
michael@0: #if 0
michael@0:     int result = ordinate & 63;
michael@0:     if (0 == result) {
michael@0:         result = 64;
michael@0:     }
michael@0: #else
michael@0:     int result = ((ordinate - 1) & 63) + 1;
michael@0: #endif
michael@0:     SkASSERT(result > 0 && result <= 64);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: static void do_anti_hairline(SkFDot6 x0, SkFDot6 y0, SkFDot6 x1, SkFDot6 y1,
michael@0:                              const SkIRect* clip, SkBlitter* blitter) {
michael@0:     // check for integer NaN (0x80000000) which we can't handle (can't negate it)
michael@0:     // It appears typically from a huge float (inf or nan) being converted to int.
michael@0:     // If we see it, just don't draw.
michael@0:     if (any_bad_ints(x0, y0, x1, y1)) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // The caller must clip the line to [-32767.0 ... 32767.0] ahead of time
michael@0:     // (in dot6 format)
michael@0:     SkASSERT(canConvertFDot6ToFixed(x0));
michael@0:     SkASSERT(canConvertFDot6ToFixed(y0));
michael@0:     SkASSERT(canConvertFDot6ToFixed(x1));
michael@0:     SkASSERT(canConvertFDot6ToFixed(y1));
michael@0: 
michael@0:     if (SkAbs32(x1 - x0) > SkIntToFDot6(511) || SkAbs32(y1 - y0) > SkIntToFDot6(511)) {
michael@0:         /*  instead of (x0 + x1) >> 1, we shift each separately. This is less
michael@0:             precise, but avoids overflowing the intermediate result if the
michael@0:             values are huge. A better fix might be to clip the original pts
michael@0:             directly (i.e. do the divide), so we don't spend time subdividing
michael@0:             huge lines at all.
michael@0:          */
michael@0:         int hx = (x0 >> 1) + (x1 >> 1);
michael@0:         int hy = (y0 >> 1) + (y1 >> 1);
michael@0:         do_anti_hairline(x0, y0, hx, hy, clip, blitter);
michael@0:         do_anti_hairline(hx, hy, x1, y1, clip, blitter);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     int         scaleStart, scaleStop;
michael@0:     int         istart, istop;
michael@0:     SkFixed     fstart, slope;
michael@0: 
michael@0:     HLine_SkAntiHairBlitter     hline_blitter;
michael@0:     Horish_SkAntiHairBlitter    horish_blitter;
michael@0:     VLine_SkAntiHairBlitter     vline_blitter;
michael@0:     Vertish_SkAntiHairBlitter   vertish_blitter;
michael@0:     SkAntiHairBlitter*          hairBlitter = NULL;
michael@0: 
michael@0:     if (SkAbs32(x1 - x0) > SkAbs32(y1 - y0)) {   // mostly horizontal
michael@0:         if (x0 > x1) {    // we want to go left-to-right
michael@0:             SkTSwap<SkFDot6>(x0, x1);
michael@0:             SkTSwap<SkFDot6>(y0, y1);
michael@0:         }
michael@0: 
michael@0:         istart = SkFDot6Floor(x0);
michael@0:         istop = SkFDot6Ceil(x1);
michael@0:         fstart = SkFDot6ToFixed(y0);
michael@0:         if (y0 == y1) {   // completely horizontal, take fast case
michael@0:             slope = 0;
michael@0:             hairBlitter = &hline_blitter;
michael@0:         } else {
michael@0:             slope = fastfixdiv(y1 - y0, x1 - x0);
michael@0:             SkASSERT(slope >= -SK_Fixed1 && slope <= SK_Fixed1);
michael@0:             fstart += (slope * (32 - (x0 & 63)) + 32) >> 6;
michael@0:             hairBlitter = &horish_blitter;
michael@0:         }
michael@0: 
michael@0:         SkASSERT(istop > istart);
michael@0:         if (istop - istart == 1) {
michael@0:             // we are within a single pixel
michael@0:             scaleStart = x1 - x0;
michael@0:             SkASSERT(scaleStart >= 0 && scaleStart <= 64);
michael@0:             scaleStop = 0;
michael@0:         } else {
michael@0:             scaleStart = 64 - (x0 & 63);
michael@0:             scaleStop = x1 & 63;
michael@0:         }
michael@0: 
michael@0:         if (clip){
michael@0:             if (istart >= clip->fRight || istop <= clip->fLeft) {
michael@0:                 return;
michael@0:             }
michael@0:             if (istart < clip->fLeft) {
michael@0:                 fstart += slope * (clip->fLeft - istart);
michael@0:                 istart = clip->fLeft;
michael@0:                 scaleStart = 64;
michael@0:                 if (istop - istart == 1) {
michael@0:                     // we are within a single pixel
michael@0:                     scaleStart = contribution_64(x1);
michael@0:                     scaleStop = 0;
michael@0:                 }
michael@0:             }
michael@0:             if (istop > clip->fRight) {
michael@0:                 istop = clip->fRight;
michael@0:                 scaleStop = 0;  // so we don't draw this last column
michael@0:             }
michael@0: 
michael@0:             SkASSERT(istart <= istop);
michael@0:             if (istart == istop) {
michael@0:                 return;
michael@0:             }
michael@0:             // now test if our Y values are completely inside the clip
michael@0:             int top, bottom;
michael@0:             if (slope >= 0) { // T2B
michael@0:                 top = SkFixedFloorToInt(fstart - SK_FixedHalf);
michael@0:                 bottom = SkFixedCeilToInt(fstart + (istop - istart - 1) * slope + SK_FixedHalf);
michael@0:             } else {           // B2T
michael@0:                 bottom = SkFixedCeilToInt(fstart + SK_FixedHalf);
michael@0:                 top = SkFixedFloorToInt(fstart + (istop - istart - 1) * slope - SK_FixedHalf);
michael@0:             }
michael@0: #ifdef OUTSET_BEFORE_CLIP_TEST
michael@0:             top -= 1;
michael@0:             bottom += 1;
michael@0: #endif
michael@0:             if (top >= clip->fBottom || bottom <= clip->fTop) {
michael@0:                 return;
michael@0:             }
michael@0:             if (clip->fTop <= top && clip->fBottom >= bottom) {
michael@0:                 clip = NULL;
michael@0:             }
michael@0:         }
michael@0:     } else {   // mostly vertical
michael@0:         if (y0 > y1) {  // we want to go top-to-bottom
michael@0:             SkTSwap<SkFDot6>(x0, x1);
michael@0:             SkTSwap<SkFDot6>(y0, y1);
michael@0:         }
michael@0: 
michael@0:         istart = SkFDot6Floor(y0);
michael@0:         istop = SkFDot6Ceil(y1);
michael@0:         fstart = SkFDot6ToFixed(x0);
michael@0:         if (x0 == x1) {
michael@0:             if (y0 == y1) { // are we zero length?
michael@0:                 return;     // nothing to do
michael@0:             }
michael@0:             slope = 0;
michael@0:             hairBlitter = &vline_blitter;
michael@0:         } else {
michael@0:             slope = fastfixdiv(x1 - x0, y1 - y0);
michael@0:             SkASSERT(slope <= SK_Fixed1 && slope >= -SK_Fixed1);
michael@0:             fstart += (slope * (32 - (y0 & 63)) + 32) >> 6;
michael@0:             hairBlitter = &vertish_blitter;
michael@0:         }
michael@0: 
michael@0:         SkASSERT(istop > istart);
michael@0:         if (istop - istart == 1) {
michael@0:             // we are within a single pixel
michael@0:             scaleStart = y1 - y0;
michael@0:             SkASSERT(scaleStart >= 0 && scaleStart <= 64);
michael@0:             scaleStop = 0;
michael@0:         } else {
michael@0:             scaleStart = 64 - (y0 & 63);
michael@0:             scaleStop = y1 & 63;
michael@0:         }
michael@0: 
michael@0:         if (clip) {
michael@0:             if (istart >= clip->fBottom || istop <= clip->fTop) {
michael@0:                 return;
michael@0:             }
michael@0:             if (istart < clip->fTop) {
michael@0:                 fstart += slope * (clip->fTop - istart);
michael@0:                 istart = clip->fTop;
michael@0:                 scaleStart = 64;
michael@0:                 if (istop - istart == 1) {
michael@0:                     // we are within a single pixel
michael@0:                     scaleStart = contribution_64(y1);
michael@0:                     scaleStop = 0;
michael@0:                 }
michael@0:             }
michael@0:             if (istop > clip->fBottom) {
michael@0:                 istop = clip->fBottom;
michael@0:                 scaleStop = 0;  // so we don't draw this last row
michael@0:             }
michael@0: 
michael@0:             SkASSERT(istart <= istop);
michael@0:             if (istart == istop)
michael@0:                 return;
michael@0: 
michael@0:             // now test if our X values are completely inside the clip
michael@0:             int left, right;
michael@0:             if (slope >= 0) { // L2R
michael@0:                 left = SkFixedFloorToInt(fstart - SK_FixedHalf);
michael@0:                 right = SkFixedCeilToInt(fstart + (istop - istart - 1) * slope + SK_FixedHalf);
michael@0:             } else {           // R2L
michael@0:                 right = SkFixedCeilToInt(fstart + SK_FixedHalf);
michael@0:                 left = SkFixedFloorToInt(fstart + (istop - istart - 1) * slope - SK_FixedHalf);
michael@0:             }
michael@0: #ifdef OUTSET_BEFORE_CLIP_TEST
michael@0:             left -= 1;
michael@0:             right += 1;
michael@0: #endif
michael@0:             if (left >= clip->fRight || right <= clip->fLeft) {
michael@0:                 return;
michael@0:             }
michael@0:             if (clip->fLeft <= left && clip->fRight >= right) {
michael@0:                 clip = NULL;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkRectClipBlitter   rectClipper;
michael@0:     if (clip) {
michael@0:         rectClipper.init(blitter, *clip);
michael@0:         blitter = &rectClipper;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(hairBlitter);
michael@0:     hairBlitter->setup(blitter);
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     if (scaleStart > 0 && scaleStop > 0) {
michael@0:         // be sure we don't draw twice in the same pixel
michael@0:         SkASSERT(istart < istop - 1);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     fstart = hairBlitter->drawCap(istart, fstart, slope, scaleStart);
michael@0:     istart += 1;
michael@0:     int fullSpans = istop - istart - (scaleStop > 0);
michael@0:     if (fullSpans > 0) {
michael@0:         fstart = hairBlitter->drawLine(istart, istart + fullSpans, fstart, slope);
michael@0:     }
michael@0:     if (scaleStop > 0) {
michael@0:         hairBlitter->drawCap(istop - 1, fstart, slope, scaleStop);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiHairLineRgn(const SkPoint& pt0, const SkPoint& pt1,
michael@0:                              const SkRegion* clip, SkBlitter* blitter) {
michael@0:     if (clip && clip->isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(clip == NULL || !clip->getBounds().isEmpty());
michael@0: 
michael@0: #ifdef TEST_GAMMA
michael@0:     build_gamma_table();
michael@0: #endif
michael@0: 
michael@0:     SkPoint pts[2] = { pt0, pt1 };
michael@0: 
michael@0:     // We have to pre-clip the line to fit in a SkFixed, so we just chop
michael@0:     // the line. TODO find a way to actually draw beyond that range.
michael@0:     {
michael@0:         SkRect fixedBounds;
michael@0:         const SkScalar max = SkIntToScalar(32767);
michael@0:         fixedBounds.set(-max, -max, max, max);
michael@0:         if (!SkLineClipper::IntersectLine(pts, fixedBounds, pts)) {
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (clip) {
michael@0:         SkRect clipBounds;
michael@0:         clipBounds.set(clip->getBounds());
michael@0:         /*  We perform integral clipping later on, but we do a scalar clip first
michael@0:             to ensure that our coordinates are expressible in fixed/integers.
michael@0: 
michael@0:             antialiased hairlines can draw up to 1/2 of a pixel outside of
michael@0:             their bounds, so we need to outset the clip before calling the
michael@0:             clipper. To make the numerics safer, we outset by a whole pixel,
michael@0:             since the 1/2 pixel boundary is important to the antihair blitter,
michael@0:             we don't want to risk numerical fate by chopping on that edge.
michael@0:          */
michael@0:         clipBounds.inset(-SK_Scalar1, -SK_Scalar1);
michael@0: 
michael@0:         if (!SkLineClipper::IntersectLine(pts, clipBounds, pts)) {
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkFDot6 x0 = SkScalarToFDot6(pts[0].fX);
michael@0:     SkFDot6 y0 = SkScalarToFDot6(pts[0].fY);
michael@0:     SkFDot6 x1 = SkScalarToFDot6(pts[1].fX);
michael@0:     SkFDot6 y1 = SkScalarToFDot6(pts[1].fY);
michael@0: 
michael@0:     if (clip) {
michael@0:         SkFDot6 left = SkMin32(x0, x1);
michael@0:         SkFDot6 top = SkMin32(y0, y1);
michael@0:         SkFDot6 right = SkMax32(x0, x1);
michael@0:         SkFDot6 bottom = SkMax32(y0, y1);
michael@0:         SkIRect ir;
michael@0: 
michael@0:         ir.set( SkFDot6Floor(left) - 1,
michael@0:                 SkFDot6Floor(top) - 1,
michael@0:                 SkFDot6Ceil(right) + 1,
michael@0:                 SkFDot6Ceil(bottom) + 1);
michael@0: 
michael@0:         if (clip->quickReject(ir)) {
michael@0:             return;
michael@0:         }
michael@0:         if (!clip->quickContains(ir)) {
michael@0:             SkRegion::Cliperator iter(*clip, ir);
michael@0:             const SkIRect*       r = &iter.rect();
michael@0: 
michael@0:             while (!iter.done()) {
michael@0:                 do_anti_hairline(x0, y0, x1, y1, r, blitter);
michael@0:                 iter.next();
michael@0:             }
michael@0:             return;
michael@0:         }
michael@0:         // fall through to no-clip case
michael@0:     }
michael@0:     do_anti_hairline(x0, y0, x1, y1, NULL, blitter);
michael@0: }
michael@0: 
michael@0: void SkScan::AntiHairRect(const SkRect& rect, const SkRasterClip& clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     SkPoint p0, p1;
michael@0: 
michael@0:     p0.set(rect.fLeft, rect.fTop);
michael@0:     p1.set(rect.fRight, rect.fTop);
michael@0:     SkScan::AntiHairLine(p0, p1, clip, blitter);
michael@0:     p0.set(rect.fRight, rect.fBottom);
michael@0:     SkScan::AntiHairLine(p0, p1, clip, blitter);
michael@0:     p1.set(rect.fLeft, rect.fBottom);
michael@0:     SkScan::AntiHairLine(p0, p1, clip, blitter);
michael@0:     p0.set(rect.fLeft, rect.fTop);
michael@0:     SkScan::AntiHairLine(p0, p1, clip, blitter);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: typedef int FDot8;  // 24.8 integer fixed point
michael@0: 
michael@0: static inline FDot8 SkFixedToFDot8(SkFixed x) {
michael@0:     return (x + 0x80) >> 8;
michael@0: }
michael@0: 
michael@0: static void do_scanline(FDot8 L, int top, FDot8 R, U8CPU alpha,
michael@0:                         SkBlitter* blitter) {
michael@0:     SkASSERT(L < R);
michael@0: 
michael@0:     if ((L >> 8) == ((R - 1) >> 8)) {  // 1x1 pixel
michael@0:         blitter->blitV(L >> 8, top, 1, SkAlphaMul(alpha, R - L));
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     int left = L >> 8;
michael@0: 
michael@0:     if (L & 0xFF) {
michael@0:         blitter->blitV(left, top, 1, SkAlphaMul(alpha, 256 - (L & 0xFF)));
michael@0:         left += 1;
michael@0:     }
michael@0: 
michael@0:     int rite = R >> 8;
michael@0:     int width = rite - left;
michael@0:     if (width > 0) {
michael@0:         call_hline_blitter(blitter, left, top, width, alpha);
michael@0:     }
michael@0:     if (R & 0xFF) {
michael@0:         blitter->blitV(rite, top, 1, SkAlphaMul(alpha, R & 0xFF));
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void antifilldot8(FDot8 L, FDot8 T, FDot8 R, FDot8 B, SkBlitter* blitter,
michael@0:                          bool fillInner) {
michael@0:     // check for empty now that we're in our reduced precision space
michael@0:     if (L >= R || T >= B) {
michael@0:         return;
michael@0:     }
michael@0:     int top = T >> 8;
michael@0:     if (top == ((B - 1) >> 8)) {   // just one scanline high
michael@0:         do_scanline(L, top, R, B - T - 1, blitter);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (T & 0xFF) {
michael@0:         do_scanline(L, top, R, 256 - (T & 0xFF), blitter);
michael@0:         top += 1;
michael@0:     }
michael@0: 
michael@0:     int bot = B >> 8;
michael@0:     int height = bot - top;
michael@0:     if (height > 0) {
michael@0:         int left = L >> 8;
michael@0:         if (left == ((R - 1) >> 8)) {   // just 1-pixel wide
michael@0:             blitter->blitV(left, top, height, R - L - 1);
michael@0:         } else {
michael@0:             if (L & 0xFF) {
michael@0:                 blitter->blitV(left, top, height, 256 - (L & 0xFF));
michael@0:                 left += 1;
michael@0:             }
michael@0:             int rite = R >> 8;
michael@0:             int width = rite - left;
michael@0:             if (width > 0 && fillInner) {
michael@0:                 blitter->blitRect(left, top, width, height);
michael@0:             }
michael@0:             if (R & 0xFF) {
michael@0:                 blitter->blitV(rite, top, height, R & 0xFF);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (B & 0xFF) {
michael@0:         do_scanline(L, bot, R, B & 0xFF, blitter);
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void antifillrect(const SkXRect& xr, SkBlitter* blitter) {
michael@0:     antifilldot8(SkFixedToFDot8(xr.fLeft), SkFixedToFDot8(xr.fTop),
michael@0:                  SkFixedToFDot8(xr.fRight), SkFixedToFDot8(xr.fBottom),
michael@0:                  blitter, true);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkScan::AntiFillXRect(const SkXRect& xr, const SkRegion* clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (NULL == clip) {
michael@0:         antifillrect(xr, blitter);
michael@0:     } else {
michael@0:         SkIRect outerBounds;
michael@0:         XRect_roundOut(xr, &outerBounds);
michael@0: 
michael@0:         if (clip->isRect()) {
michael@0:             const SkIRect& clipBounds = clip->getBounds();
michael@0: 
michael@0:             if (clipBounds.contains(outerBounds)) {
michael@0:                 antifillrect(xr, blitter);
michael@0:             } else {
michael@0:                 SkXRect tmpR;
michael@0:                 // this keeps our original edges fractional
michael@0:                 XRect_set(&tmpR, clipBounds);
michael@0:                 if (tmpR.intersect(xr)) {
michael@0:                     antifillrect(tmpR, blitter);
michael@0:                 }
michael@0:             }
michael@0:         } else {
michael@0:             SkRegion::Cliperator clipper(*clip, outerBounds);
michael@0:             const SkIRect&       rr = clipper.rect();
michael@0: 
michael@0:             while (!clipper.done()) {
michael@0:                 SkXRect  tmpR;
michael@0: 
michael@0:                 // this keeps our original edges fractional
michael@0:                 XRect_set(&tmpR, rr);
michael@0:                 if (tmpR.intersect(xr)) {
michael@0:                     antifillrect(tmpR, blitter);
michael@0:                 }
michael@0:                 clipper.next();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFillXRect(const SkXRect& xr, const SkRasterClip& clip,
michael@0:                            SkBlitter* blitter) {
michael@0:     if (clip.isBW()) {
michael@0:         AntiFillXRect(xr, &clip.bwRgn(), blitter);
michael@0:     } else {
michael@0:         SkIRect outerBounds;
michael@0:         XRect_roundOut(xr, &outerBounds);
michael@0: 
michael@0:         if (clip.quickContains(outerBounds)) {
michael@0:             AntiFillXRect(xr, NULL, blitter);
michael@0:         } else {
michael@0:             SkAAClipBlitterWrapper wrapper(clip, blitter);
michael@0:             blitter = wrapper.getBlitter();
michael@0: 
michael@0:             AntiFillXRect(xr, &wrapper.getRgn(), wrapper.getBlitter());
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*  This guy takes a float-rect, but with the key improvement that it has
michael@0:     already been clipped, so we know that it is safe to convert it into a
michael@0:     XRect (fixedpoint), as it won't overflow.
michael@0: */
michael@0: static void antifillrect(const SkRect& r, SkBlitter* blitter) {
michael@0:     SkXRect xr;
michael@0: 
michael@0:     XRect_set(&xr, r);
michael@0:     antifillrect(xr, blitter);
michael@0: }
michael@0: 
michael@0: /*  We repeat the clipping logic of AntiFillXRect because the float rect might
michael@0:     overflow if we blindly converted it to an XRect. This sucks that we have to
michael@0:     repeat the clipping logic, but I don't see how to share the code/logic.
michael@0: 
michael@0:     We clip r (as needed) into one or more (smaller) float rects, and then pass
michael@0:     those to our version of antifillrect, which converts it into an XRect and
michael@0:     then calls the blit.
michael@0: */
michael@0: void SkScan::AntiFillRect(const SkRect& origR, const SkRegion* clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (clip) {
michael@0:         SkRect newR;
michael@0:         newR.set(clip->getBounds());
michael@0:         if (!newR.intersect(origR)) {
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         SkIRect outerBounds;
michael@0:         newR.roundOut(&outerBounds);
michael@0: 
michael@0:         if (clip->isRect()) {
michael@0:             antifillrect(newR, blitter);
michael@0:         } else {
michael@0:             SkRegion::Cliperator clipper(*clip, outerBounds);
michael@0:             while (!clipper.done()) {
michael@0:                 newR.set(clipper.rect());
michael@0:                 if (newR.intersect(origR)) {
michael@0:                     antifillrect(newR, blitter);
michael@0:                 }
michael@0:                 clipper.next();
michael@0:             }
michael@0:         }
michael@0:     } else {
michael@0:         antifillrect(origR, blitter);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFillRect(const SkRect& r, const SkRasterClip& clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (clip.isBW()) {
michael@0:         AntiFillRect(r, &clip.bwRgn(), blitter);
michael@0:     } else {
michael@0:         SkAAClipBlitterWrapper wrap(clip, blitter);
michael@0:         AntiFillRect(r, &wrap.getRgn(), wrap.getBlitter());
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #define SkAlphaMulRound(a, b)   SkMulDiv255Round(a, b)
michael@0: 
michael@0: // calls blitRect() if the rectangle is non-empty
michael@0: static void fillcheckrect(int L, int T, int R, int B, SkBlitter* blitter) {
michael@0:     if (L < R && T < B) {
michael@0:         blitter->blitRect(L, T, R - L, B - T);
michael@0:     }
michael@0: }
michael@0: 
michael@0: static inline FDot8 SkScalarToFDot8(SkScalar x) {
michael@0:     return (int)(x * 256);
michael@0: }
michael@0: 
michael@0: static inline int FDot8Floor(FDot8 x) {
michael@0:     return x >> 8;
michael@0: }
michael@0: 
michael@0: static inline int FDot8Ceil(FDot8 x) {
michael@0:     return (x + 0xFF) >> 8;
michael@0: }
michael@0: 
michael@0: // 1 - (1 - a)*(1 - b)
michael@0: static inline U8CPU InvAlphaMul(U8CPU a, U8CPU b) {
michael@0:     // need precise rounding (not just SkAlphaMul) so that values like
michael@0:     // a=228, b=252 don't overflow the result
michael@0:     return SkToU8(a + b - SkAlphaMulRound(a, b));
michael@0: }
michael@0: 
michael@0: static void inner_scanline(FDot8 L, int top, FDot8 R, U8CPU alpha,
michael@0:                            SkBlitter* blitter) {
michael@0:     SkASSERT(L < R);
michael@0: 
michael@0:     if ((L >> 8) == ((R - 1) >> 8)) {  // 1x1 pixel
michael@0:         blitter->blitV(L >> 8, top, 1, InvAlphaMul(alpha, R - L));
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     int left = L >> 8;
michael@0:     if (L & 0xFF) {
michael@0:         blitter->blitV(left, top, 1, InvAlphaMul(alpha, L & 0xFF));
michael@0:         left += 1;
michael@0:     }
michael@0: 
michael@0:     int rite = R >> 8;
michael@0:     int width = rite - left;
michael@0:     if (width > 0) {
michael@0:         call_hline_blitter(blitter, left, top, width, alpha);
michael@0:     }
michael@0: 
michael@0:     if (R & 0xFF) {
michael@0:         blitter->blitV(rite, top, 1, InvAlphaMul(alpha, ~R & 0xFF));
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void innerstrokedot8(FDot8 L, FDot8 T, FDot8 R, FDot8 B,
michael@0:                             SkBlitter* blitter) {
michael@0:     SkASSERT(L < R && T < B);
michael@0: 
michael@0:     int top = T >> 8;
michael@0:     if (top == ((B - 1) >> 8)) {   // just one scanline high
michael@0:         // We want the inverse of B-T, since we're the inner-stroke
michael@0:         int alpha = 256 - (B - T);
michael@0:         if (alpha) {
michael@0:             inner_scanline(L, top, R, alpha, blitter);
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (T & 0xFF) {
michael@0:         inner_scanline(L, top, R, T & 0xFF, blitter);
michael@0:         top += 1;
michael@0:     }
michael@0: 
michael@0:     int bot = B >> 8;
michael@0:     int height = bot - top;
michael@0:     if (height > 0) {
michael@0:         if (L & 0xFF) {
michael@0:             blitter->blitV(L >> 8, top, height, L & 0xFF);
michael@0:         }
michael@0:         if (R & 0xFF) {
michael@0:             blitter->blitV(R >> 8, top, height, ~R & 0xFF);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (B & 0xFF) {
michael@0:         inner_scanline(L, bot, R, ~B & 0xFF, blitter);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFrameRect(const SkRect& r, const SkPoint& strokeSize,
michael@0:                            const SkRegion* clip, SkBlitter* blitter) {
michael@0:     SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0);
michael@0: 
michael@0:     SkScalar rx = SkScalarHalf(strokeSize.fX);
michael@0:     SkScalar ry = SkScalarHalf(strokeSize.fY);
michael@0: 
michael@0:     // outset by the radius
michael@0:     FDot8 L = SkScalarToFDot8(r.fLeft - rx);
michael@0:     FDot8 T = SkScalarToFDot8(r.fTop - ry);
michael@0:     FDot8 R = SkScalarToFDot8(r.fRight + rx);
michael@0:     FDot8 B = SkScalarToFDot8(r.fBottom + ry);
michael@0: 
michael@0:     SkIRect outer;
michael@0:     // set outer to the outer rect of the outer section
michael@0:     outer.set(FDot8Floor(L), FDot8Floor(T), FDot8Ceil(R), FDot8Ceil(B));
michael@0: 
michael@0:     SkBlitterClipper clipper;
michael@0:     if (clip) {
michael@0:         if (clip->quickReject(outer)) {
michael@0:             return;
michael@0:         }
michael@0:         if (!clip->contains(outer)) {
michael@0:             blitter = clipper.apply(blitter, clip, &outer);
michael@0:         }
michael@0:         // now we can ignore clip for the rest of the function
michael@0:     }
michael@0: 
michael@0:     // stroke the outer hull
michael@0:     antifilldot8(L, T, R, B, blitter, false);
michael@0: 
michael@0:     // set outer to the outer rect of the middle section
michael@0:     outer.set(FDot8Ceil(L), FDot8Ceil(T), FDot8Floor(R), FDot8Floor(B));
michael@0: 
michael@0:     // in case we lost a bit with diameter/2
michael@0:     rx = strokeSize.fX - rx;
michael@0:     ry = strokeSize.fY - ry;
michael@0:     // inset by the radius
michael@0:     L = SkScalarToFDot8(r.fLeft + rx);
michael@0:     T = SkScalarToFDot8(r.fTop + ry);
michael@0:     R = SkScalarToFDot8(r.fRight - rx);
michael@0:     B = SkScalarToFDot8(r.fBottom - ry);
michael@0: 
michael@0:     if (L >= R || T >= B) {
michael@0:         fillcheckrect(outer.fLeft, outer.fTop, outer.fRight, outer.fBottom,
michael@0:                       blitter);
michael@0:     } else {
michael@0:         SkIRect inner;
michael@0:         // set inner to the inner rect of the middle section
michael@0:         inner.set(FDot8Floor(L), FDot8Floor(T), FDot8Ceil(R), FDot8Ceil(B));
michael@0: 
michael@0:         // draw the frame in 4 pieces
michael@0:         fillcheckrect(outer.fLeft, outer.fTop, outer.fRight, inner.fTop,
michael@0:                       blitter);
michael@0:         fillcheckrect(outer.fLeft, inner.fTop, inner.fLeft, inner.fBottom,
michael@0:                       blitter);
michael@0:         fillcheckrect(inner.fRight, inner.fTop, outer.fRight, inner.fBottom,
michael@0:                       blitter);
michael@0:         fillcheckrect(outer.fLeft, inner.fBottom, outer.fRight, outer.fBottom,
michael@0:                       blitter);
michael@0: 
michael@0:         // now stroke the inner rect, which is similar to antifilldot8() except that
michael@0:         // it treats the fractional coordinates with the inverse bias (since its
michael@0:         // inner).
michael@0:         innerstrokedot8(L, T, R, B, blitter);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFrameRect(const SkRect& r, const SkPoint& strokeSize,
michael@0:                            const SkRasterClip& clip, SkBlitter* blitter) {
michael@0:     if (clip.isBW()) {
michael@0:         AntiFrameRect(r, strokeSize, &clip.bwRgn(), blitter);
michael@0:     } else {
michael@0:         SkAAClipBlitterWrapper wrap(clip, blitter);
michael@0:         AntiFrameRect(r, strokeSize, &wrap.getRgn(), wrap.getBlitter());
michael@0:     }
michael@0: }