michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 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 "SkScanPriv.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkMatrix.h"
michael@0: #include "SkBlitter.h"
michael@0: #include "SkRegion.h"
michael@0: #include "SkAntiRun.h"
michael@0: 
michael@0: #define SHIFT   2
michael@0: #define SCALE   (1 << SHIFT)
michael@0: #define MASK    (SCALE - 1)
michael@0: 
michael@0: /** @file
michael@0:     We have two techniques for capturing the output of the supersampler:
michael@0:     - SUPERMASK, which records a large mask-bitmap
michael@0:         this is often faster for small, complex objects
michael@0:     - RLE, which records a rle-encoded scanline
michael@0:         this is often faster for large objects with big spans
michael@0: 
michael@0:     These blitters use two coordinate systems:
michael@0:     - destination coordinates, scale equal to the output - often
michael@0:         abbreviated with 'i' or 'I' in variable names
michael@0:     - supersampled coordinates, scale equal to the output * SCALE
michael@0: 
michael@0:     Enabling SK_USE_LEGACY_AA_COVERAGE keeps the aa coverage calculations as
michael@0:     they were before the fix that unified the output of the RLE and MASK
michael@0:     supersamplers.
michael@0:  */
michael@0: 
michael@0: //#define FORCE_SUPERMASK
michael@0: //#define FORCE_RLE
michael@0: //#define SK_USE_LEGACY_AA_COVERAGE
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /// Base class for a single-pass supersampled blitter.
michael@0: class BaseSuperBlitter : public SkBlitter {
michael@0: public:
michael@0:     BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                      const SkRegion& clip);
michael@0: 
michael@0:     /// Must be explicitly defined on subclasses.
michael@0:     virtual void blitAntiH(int x, int y, const SkAlpha antialias[],
michael@0:                            const int16_t runs[]) SK_OVERRIDE {
michael@0:         SkDEBUGFAIL("How did I get here?");
michael@0:     }
michael@0:     /// May not be called on BaseSuperBlitter because it blits out of order.
michael@0:     virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE {
michael@0:         SkDEBUGFAIL("How did I get here?");
michael@0:     }
michael@0: 
michael@0: protected:
michael@0:     SkBlitter*  fRealBlitter;
michael@0:     /// Current y coordinate, in destination coordinates.
michael@0:     int         fCurrIY;
michael@0:     /// Widest row of region to be blitted, in destination coordinates.
michael@0:     int         fWidth;
michael@0:     /// Leftmost x coordinate in any row, in destination coordinates.
michael@0:     int         fLeft;
michael@0:     /// Leftmost x coordinate in any row, in supersampled coordinates.
michael@0:     int         fSuperLeft;
michael@0: 
michael@0:     SkDEBUGCODE(int fCurrX;)
michael@0:     /// Current y coordinate in supersampled coordinates.
michael@0:     int fCurrY;
michael@0:     /// Initial y coordinate (top of bounds).
michael@0:     int fTop;
michael@0: };
michael@0: 
michael@0: BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                                    const SkRegion& clip) {
michael@0:     fRealBlitter = realBlitter;
michael@0: 
michael@0:     /*
michael@0:      *  We use the clip bounds instead of the ir, since we may be asked to
michael@0:      *  draw outside of the rect if we're a inverse filltype
michael@0:      */
michael@0:     const int left = clip.getBounds().fLeft;
michael@0:     const int right = clip.getBounds().fRight;
michael@0: 
michael@0:     fLeft = left;
michael@0:     fSuperLeft = left << SHIFT;
michael@0:     fWidth = right - left;
michael@0: #if 0
michael@0:     fCurrIY = -1;
michael@0:     fCurrY = -1;
michael@0: #else
michael@0:     fTop = ir.fTop;
michael@0:     fCurrIY = ir.fTop - 1;
michael@0:     fCurrY = (ir.fTop << SHIFT) - 1;
michael@0: #endif
michael@0:     SkDEBUGCODE(fCurrX = -1;)
michael@0: }
michael@0: 
michael@0: /// Run-length-encoded supersampling antialiased blitter.
michael@0: class SuperBlitter : public BaseSuperBlitter {
michael@0: public:
michael@0:     SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                  const SkRegion& clip);
michael@0: 
michael@0:     virtual ~SuperBlitter() {
michael@0:         this->flush();
michael@0:         sk_free(fRuns.fRuns);
michael@0:     }
michael@0: 
michael@0:     /// Once fRuns contains a complete supersampled row, flush() blits
michael@0:     /// it out through the wrapped blitter.
michael@0:     void flush();
michael@0: 
michael@0:     /// Blits a row of pixels, with location and width specified
michael@0:     /// in supersampled coordinates.
michael@0:     virtual void blitH(int x, int y, int width) SK_OVERRIDE;
michael@0:     /// Blits a rectangle of pixels, with location and size specified
michael@0:     /// in supersampled coordinates.
michael@0:     virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE;
michael@0: 
michael@0: private:
michael@0:     SkAlphaRuns fRuns;
michael@0:     int         fOffsetX;
michael@0: };
michael@0: 
michael@0: SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                            const SkRegion& clip)
michael@0:         : BaseSuperBlitter(realBlitter, ir, clip) {
michael@0:     const int width = fWidth;
michael@0: 
michael@0:     // extra one to store the zero at the end
michael@0:     fRuns.fRuns = (int16_t*)sk_malloc_throw((width + 1 + (width + 2)/2) * sizeof(int16_t));
michael@0:     fRuns.fAlpha = (uint8_t*)(fRuns.fRuns + width + 1);
michael@0:     fRuns.reset(width);
michael@0: 
michael@0:     fOffsetX = 0;
michael@0: }
michael@0: 
michael@0: void SuperBlitter::flush() {
michael@0:     if (fCurrIY >= fTop) {
michael@0:         if (!fRuns.empty()) {
michael@0:         //  SkDEBUGCODE(fRuns.dump();)
michael@0:             fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns);
michael@0:             fRuns.reset(fWidth);
michael@0:             fOffsetX = 0;
michael@0:         }
michael@0:         fCurrIY = fTop - 1;
michael@0:         SkDEBUGCODE(fCurrX = -1;)
michael@0:     }
michael@0: }
michael@0: 
michael@0: /** coverage_to_partial_alpha() is being used by SkAlphaRuns, which
michael@0:     *accumulates* SCALE pixels worth of "alpha" in [0,(256/SCALE)]
michael@0:     to produce a final value in [0, 255] and handles clamping 256->255
michael@0:     itself, with the same (alpha - (alpha >> 8)) correction as
michael@0:     coverage_to_exact_alpha().
michael@0: */
michael@0: static inline int coverage_to_partial_alpha(int aa) {
michael@0:     aa <<= 8 - 2*SHIFT;
michael@0: #ifdef SK_USE_LEGACY_AA_COVERAGE
michael@0:     aa -= aa >> (8 - SHIFT - 1);
michael@0: #endif
michael@0:     return aa;
michael@0: }
michael@0: 
michael@0: /** coverage_to_exact_alpha() is being used by our blitter, which wants
michael@0:     a final value in [0, 255].
michael@0: */
michael@0: static inline int coverage_to_exact_alpha(int aa) {
michael@0:     int alpha = (256 >> SHIFT) * aa;
michael@0:     // clamp 256->255
michael@0:     return alpha - (alpha >> 8);
michael@0: }
michael@0: 
michael@0: void SuperBlitter::blitH(int x, int y, int width) {
michael@0:     SkASSERT(width > 0);
michael@0: 
michael@0:     int iy = y >> SHIFT;
michael@0:     SkASSERT(iy >= fCurrIY);
michael@0: 
michael@0:     x -= fSuperLeft;
michael@0:     // hack, until I figure out why my cubics (I think) go beyond the bounds
michael@0:     if (x < 0) {
michael@0:         width += x;
michael@0:         x = 0;
michael@0:     }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     SkASSERT(y != fCurrY || x >= fCurrX);
michael@0: #endif
michael@0:     SkASSERT(y >= fCurrY);
michael@0:     if (fCurrY != y) {
michael@0:         fOffsetX = 0;
michael@0:         fCurrY = y;
michael@0:     }
michael@0: 
michael@0:     if (iy != fCurrIY) {  // new scanline
michael@0:         this->flush();
michael@0:         fCurrIY = iy;
michael@0:     }
michael@0: 
michael@0:     int start = x;
michael@0:     int stop = x + width;
michael@0: 
michael@0:     SkASSERT(start >= 0 && stop > start);
michael@0:     // integer-pixel-aligned ends of blit, rounded out
michael@0:     int fb = start & MASK;
michael@0:     int fe = stop & MASK;
michael@0:     int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
michael@0: 
michael@0:     if (n < 0) {
michael@0:         fb = fe - fb;
michael@0:         n = 0;
michael@0:         fe = 0;
michael@0:     } else {
michael@0:         if (fb == 0) {
michael@0:             n += 1;
michael@0:         } else {
michael@0:             fb = SCALE - fb;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     fOffsetX = fRuns.add(x >> SHIFT, coverage_to_partial_alpha(fb),
michael@0:                          n, coverage_to_partial_alpha(fe),
michael@0:                          (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT),
michael@0:                          fOffsetX);
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     fRuns.assertValid(y & MASK, (1 << (8 - SHIFT)));
michael@0:     fCurrX = x + width;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #if 0 // UNUSED
michael@0: static void set_left_rite_runs(SkAlphaRuns& runs, int ileft, U8CPU leftA,
michael@0:                                int n, U8CPU riteA) {
michael@0:     SkASSERT(leftA <= 0xFF);
michael@0:     SkASSERT(riteA <= 0xFF);
michael@0: 
michael@0:     int16_t* run = runs.fRuns;
michael@0:     uint8_t* aa = runs.fAlpha;
michael@0: 
michael@0:     if (ileft > 0) {
michael@0:         run[0] = ileft;
michael@0:         aa[0] = 0;
michael@0:         run += ileft;
michael@0:         aa += ileft;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(leftA < 0xFF);
michael@0:     if (leftA > 0) {
michael@0:         *run++ = 1;
michael@0:         *aa++ = leftA;
michael@0:     }
michael@0: 
michael@0:     if (n > 0) {
michael@0:         run[0] = n;
michael@0:         aa[0] = 0xFF;
michael@0:         run += n;
michael@0:         aa += n;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(riteA < 0xFF);
michael@0:     if (riteA > 0) {
michael@0:         *run++ = 1;
michael@0:         *aa++ = riteA;
michael@0:     }
michael@0:     run[0] = 0;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: void SuperBlitter::blitRect(int x, int y, int width, int height) {
michael@0:     SkASSERT(width > 0);
michael@0:     SkASSERT(height > 0);
michael@0: 
michael@0:     // blit leading rows
michael@0:     while ((y & MASK)) {
michael@0:         this->blitH(x, y++, width);
michael@0:         if (--height <= 0) {
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(height > 0);
michael@0: 
michael@0:     // Since this is a rect, instead of blitting supersampled rows one at a
michael@0:     // time and then resolving to the destination canvas, we can blit
michael@0:     // directly to the destintion canvas one row per SCALE supersampled rows.
michael@0:     int start_y = y >> SHIFT;
michael@0:     int stop_y = (y + height) >> SHIFT;
michael@0:     int count = stop_y - start_y;
michael@0:     if (count > 0) {
michael@0:         y += count << SHIFT;
michael@0:         height -= count << SHIFT;
michael@0: 
michael@0:         // save original X for our tail blitH() loop at the bottom
michael@0:         int origX = x;
michael@0: 
michael@0:         x -= fSuperLeft;
michael@0:         // hack, until I figure out why my cubics (I think) go beyond the bounds
michael@0:         if (x < 0) {
michael@0:             width += x;
michael@0:             x = 0;
michael@0:         }
michael@0: 
michael@0:         // There is always a left column, a middle, and a right column.
michael@0:         // ileft is the destination x of the first pixel of the entire rect.
michael@0:         // xleft is (SCALE - # of covered supersampled pixels) in that
michael@0:         // destination pixel.
michael@0:         int ileft = x >> SHIFT;
michael@0:         int xleft = x & MASK;
michael@0:         // irite is the destination x of the last pixel of the OPAQUE section.
michael@0:         // xrite is the number of supersampled pixels extending beyond irite;
michael@0:         // xrite/SCALE should give us alpha.
michael@0:         int irite = (x + width) >> SHIFT;
michael@0:         int xrite = (x + width) & MASK;
michael@0:         if (!xrite) {
michael@0:             xrite = SCALE;
michael@0:             irite--;
michael@0:         }
michael@0: 
michael@0:         // Need to call flush() to clean up pending draws before we
michael@0:         // even consider blitV(), since otherwise it can look nonmonotonic.
michael@0:         SkASSERT(start_y > fCurrIY);
michael@0:         this->flush();
michael@0: 
michael@0:         int n = irite - ileft - 1;
michael@0:         if (n < 0) {
michael@0:             // If n < 0, we'll only have a single partially-transparent column
michael@0:             // of pixels to render.
michael@0:             xleft = xrite - xleft;
michael@0:             SkASSERT(xleft <= SCALE);
michael@0:             SkASSERT(xleft > 0);
michael@0:             xrite = 0;
michael@0:             fRealBlitter->blitV(ileft + fLeft, start_y, count,
michael@0:                 coverage_to_exact_alpha(xleft));
michael@0:         } else {
michael@0:             // With n = 0, we have two possibly-transparent columns of pixels
michael@0:             // to render; with n > 0, we have opaque columns between them.
michael@0: 
michael@0:             xleft = SCALE - xleft;
michael@0: 
michael@0:             // Using coverage_to_exact_alpha is not consistent with blitH()
michael@0:             const int coverageL = coverage_to_exact_alpha(xleft);
michael@0:             const int coverageR = coverage_to_exact_alpha(xrite);
michael@0: 
michael@0:             SkASSERT(coverageL > 0 || n > 0 || coverageR > 0);
michael@0:             SkASSERT((coverageL != 0) + n + (coverageR != 0) <= fWidth);
michael@0: 
michael@0:             fRealBlitter->blitAntiRect(ileft + fLeft, start_y, n, count,
michael@0:                                        coverageL, coverageR);
michael@0:         }
michael@0: 
michael@0:         // preamble for our next call to blitH()
michael@0:         fCurrIY = stop_y - 1;
michael@0:         fOffsetX = 0;
michael@0:         fCurrY = y - 1;
michael@0:         fRuns.reset(fWidth);
michael@0:         x = origX;
michael@0:     }
michael@0: 
michael@0:     // catch any remaining few rows
michael@0:     SkASSERT(height <= MASK);
michael@0:     while (--height >= 0) {
michael@0:         this->blitH(x, y++, width);
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /// Masked supersampling antialiased blitter.
michael@0: class MaskSuperBlitter : public BaseSuperBlitter {
michael@0: public:
michael@0:     MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                      const SkRegion& clip);
michael@0:     virtual ~MaskSuperBlitter() {
michael@0:         fRealBlitter->blitMask(fMask, fClipRect);
michael@0:     }
michael@0: 
michael@0:     virtual void blitH(int x, int y, int width) SK_OVERRIDE;
michael@0: 
michael@0:     static bool CanHandleRect(const SkIRect& bounds) {
michael@0: #ifdef FORCE_RLE
michael@0:         return false;
michael@0: #endif
michael@0:         int width = bounds.width();
michael@0:         int64_t rb = SkAlign4(width);
michael@0:         // use 64bits to detect overflow
michael@0:         int64_t storage = rb * bounds.height();
michael@0: 
michael@0:         return (width <= MaskSuperBlitter::kMAX_WIDTH) &&
michael@0:                (storage <= MaskSuperBlitter::kMAX_STORAGE);
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     enum {
michael@0: #ifdef FORCE_SUPERMASK
michael@0:         kMAX_WIDTH = 2048,
michael@0:         kMAX_STORAGE = 1024 * 1024 * 2
michael@0: #else
michael@0:         kMAX_WIDTH = 32,    // so we don't try to do very wide things, where the RLE blitter would be faster
michael@0:         kMAX_STORAGE = 1024
michael@0: #endif
michael@0:     };
michael@0: 
michael@0:     SkMask      fMask;
michael@0:     SkIRect     fClipRect;
michael@0:     // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than
michael@0:     // perform a test to see if stopAlpha != 0
michael@0:     uint32_t    fStorage[(kMAX_STORAGE >> 2) + 1];
michael@0: };
michael@0: 
michael@0: MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
michael@0:                                    const SkRegion& clip)
michael@0:         : BaseSuperBlitter(realBlitter, ir, clip) {
michael@0:     SkASSERT(CanHandleRect(ir));
michael@0: 
michael@0:     fMask.fImage    = (uint8_t*)fStorage;
michael@0:     fMask.fBounds   = ir;
michael@0:     fMask.fRowBytes = ir.width();
michael@0:     fMask.fFormat   = SkMask::kA8_Format;
michael@0: 
michael@0:     fClipRect = ir;
michael@0:     fClipRect.intersect(clip.getBounds());
michael@0: 
michael@0:     // For valgrind, write 1 extra byte at the end so we don't read
michael@0:     // uninitialized memory. See comment in add_aa_span and fStorage[].
michael@0:     memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1);
michael@0: }
michael@0: 
michael@0: static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) {
michael@0:     /*  I should be able to just add alpha[x] + startAlpha.
michael@0:         However, if the trailing edge of the previous span and the leading
michael@0:         edge of the current span round to the same super-sampled x value,
michael@0:         I might overflow to 256 with this add, hence the funny subtract.
michael@0:     */
michael@0:     unsigned tmp = *alpha + startAlpha;
michael@0:     SkASSERT(tmp <= 256);
michael@0:     *alpha = SkToU8(tmp - (tmp >> 8));
michael@0: }
michael@0: 
michael@0: static inline uint32_t quadplicate_byte(U8CPU value) {
michael@0:     uint32_t pair = (value << 8) | value;
michael@0:     return (pair << 16) | pair;
michael@0: }
michael@0: 
michael@0: // Perform this tricky subtract, to avoid overflowing to 256. Our caller should
michael@0: // only ever call us with at most enough to hit 256 (never larger), so it is
michael@0: // enough to just subtract the high-bit. Actually clamping with a branch would
michael@0: // be slower (e.g. if (tmp > 255) tmp = 255;)
michael@0: //
michael@0: static inline void saturated_add(uint8_t* ptr, U8CPU add) {
michael@0:     unsigned tmp = *ptr + add;
michael@0:     SkASSERT(tmp <= 256);
michael@0:     *ptr = SkToU8(tmp - (tmp >> 8));
michael@0: }
michael@0: 
michael@0: // minimum count before we want to setup an inner loop, adding 4-at-a-time
michael@0: #define MIN_COUNT_FOR_QUAD_LOOP  16
michael@0: 
michael@0: static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount,
michael@0:                         U8CPU stopAlpha, U8CPU maxValue) {
michael@0:     SkASSERT(middleCount >= 0);
michael@0: 
michael@0:     saturated_add(alpha, startAlpha);
michael@0:     alpha += 1;
michael@0: 
michael@0:     if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) {
michael@0:         // loop until we're quad-byte aligned
michael@0:         while (SkTCast<intptr_t>(alpha) & 0x3) {
michael@0:             alpha[0] = SkToU8(alpha[0] + maxValue);
michael@0:             alpha += 1;
michael@0:             middleCount -= 1;
michael@0:         }
michael@0: 
michael@0:         int bigCount = middleCount >> 2;
michael@0:         uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha);
michael@0:         uint32_t qval = quadplicate_byte(maxValue);
michael@0:         do {
michael@0:             *qptr++ += qval;
michael@0:         } while (--bigCount > 0);
michael@0: 
michael@0:         middleCount &= 3;
michael@0:         alpha = reinterpret_cast<uint8_t*> (qptr);
michael@0:         // fall through to the following while-loop
michael@0:     }
michael@0: 
michael@0:     while (--middleCount >= 0) {
michael@0:         alpha[0] = SkToU8(alpha[0] + maxValue);
michael@0:         alpha += 1;
michael@0:     }
michael@0: 
michael@0:     // potentially this can be off the end of our "legal" alpha values, but that
michael@0:     // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0
michael@0:     // every time (slow), we just do it, and ensure that we've allocated extra space
michael@0:     // (see the + 1 comment in fStorage[]
michael@0:     saturated_add(alpha, stopAlpha);
michael@0: }
michael@0: 
michael@0: void MaskSuperBlitter::blitH(int x, int y, int width) {
michael@0:     int iy = (y >> SHIFT);
michael@0: 
michael@0:     SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom);
michael@0:     iy -= fMask.fBounds.fTop;   // make it relative to 0
michael@0: 
michael@0:     // This should never happen, but it does.  Until the true cause is
michael@0:     // discovered, let's skip this span instead of crashing.
michael@0:     // See http://crbug.com/17569.
michael@0:     if (iy < 0) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     {
michael@0:         int ix = x >> SHIFT;
michael@0:         SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     x -= (fMask.fBounds.fLeft << SHIFT);
michael@0: 
michael@0:     // hack, until I figure out why my cubics (I think) go beyond the bounds
michael@0:     if (x < 0) {
michael@0:         width += x;
michael@0:         x = 0;
michael@0:     }
michael@0: 
michael@0:     uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT);
michael@0: 
michael@0:     int start = x;
michael@0:     int stop = x + width;
michael@0: 
michael@0:     SkASSERT(start >= 0 && stop > start);
michael@0:     int fb = start & MASK;
michael@0:     int fe = stop & MASK;
michael@0:     int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
michael@0: 
michael@0: 
michael@0:     if (n < 0) {
michael@0:         SkASSERT(row >= fMask.fImage);
michael@0:         SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1);
michael@0:         add_aa_span(row, coverage_to_partial_alpha(fe - fb));
michael@0:     } else {
michael@0:         fb = SCALE - fb;
michael@0:         SkASSERT(row >= fMask.fImage);
michael@0:         SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1);
michael@0:         add_aa_span(row,  coverage_to_partial_alpha(fb),
michael@0:                     n, coverage_to_partial_alpha(fe),
michael@0:                     (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT));
michael@0:     }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     fCurrX = x + width;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static bool fitsInsideLimit(const SkRect& r, SkScalar max) {
michael@0:     const SkScalar min = -max;
michael@0:     return  r.fLeft > min && r.fTop > min &&
michael@0:             r.fRight < max && r.fBottom < max;
michael@0: }
michael@0: 
michael@0: static int overflows_short_shift(int value, int shift) {
michael@0:     const int s = 16 + shift;
michael@0:     return (value << s >> s) - value;
michael@0: }
michael@0: 
michael@0: /**
michael@0:   Would any of the coordinates of this rectangle not fit in a short,
michael@0:   when left-shifted by shift?
michael@0: */
michael@0: static int rect_overflows_short_shift(SkIRect rect, int shift) {
michael@0:     SkASSERT(!overflows_short_shift(8191, SHIFT));
michael@0:     SkASSERT(overflows_short_shift(8192, SHIFT));
michael@0:     SkASSERT(!overflows_short_shift(32767, 0));
michael@0:     SkASSERT(overflows_short_shift(32768, 0));
michael@0: 
michael@0:     // Since we expect these to succeed, we bit-or together
michael@0:     // for a tiny extra bit of speed.
michael@0:     return overflows_short_shift(rect.fLeft, SHIFT) |
michael@0:            overflows_short_shift(rect.fRight, SHIFT) |
michael@0:            overflows_short_shift(rect.fTop, SHIFT) |
michael@0:            overflows_short_shift(rect.fBottom, SHIFT);
michael@0: }
michael@0: 
michael@0: static bool safeRoundOut(const SkRect& src, SkIRect* dst, int32_t maxInt) {
michael@0:     const SkScalar maxScalar = SkIntToScalar(maxInt);
michael@0: 
michael@0:     if (fitsInsideLimit(src, maxScalar)) {
michael@0:         src.roundOut(dst);
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFillPath(const SkPath& path, const SkRegion& origClip,
michael@0:                           SkBlitter* blitter, bool forceRLE) {
michael@0:     if (origClip.isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     SkIRect ir;
michael@0: 
michael@0:     if (!safeRoundOut(path.getBounds(), &ir, SK_MaxS32 >> SHIFT)) {
michael@0: #if 0
michael@0:         const SkRect& r = path.getBounds();
michael@0:         SkDebugf("--- bounds can't fit in SkIRect\n", r.fLeft, r.fTop, r.fRight, r.fBottom);
michael@0: #endif
michael@0:         return;
michael@0:     }
michael@0:     if (ir.isEmpty()) {
michael@0:         if (path.isInverseFillType()) {
michael@0:             blitter->blitRegion(origClip);
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // If the intersection of the path bounds and the clip bounds
michael@0:     // will overflow 32767 when << by SHIFT, we can't supersample,
michael@0:     // so draw without antialiasing.
michael@0:     SkIRect clippedIR;
michael@0:     if (path.isInverseFillType()) {
michael@0:        // If the path is an inverse fill, it's going to fill the entire
michael@0:        // clip, and we care whether the entire clip exceeds our limits.
michael@0:        clippedIR = origClip.getBounds();
michael@0:     } else {
michael@0:        if (!clippedIR.intersect(ir, origClip.getBounds())) {
michael@0:            return;
michael@0:        }
michael@0:     }
michael@0:     if (rect_overflows_short_shift(clippedIR, SHIFT)) {
michael@0:         SkScan::FillPath(path, origClip, blitter);
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Our antialiasing can't handle a clip larger than 32767, so we restrict
michael@0:     // the clip to that limit here. (the runs[] uses int16_t for its index).
michael@0:     //
michael@0:     // A more general solution (one that could also eliminate the need to
michael@0:     // disable aa based on ir bounds (see overflows_short_shift) would be
michael@0:     // to tile the clip/target...
michael@0:     SkRegion tmpClipStorage;
michael@0:     const SkRegion* clipRgn = &origClip;
michael@0:     {
michael@0:         static const int32_t kMaxClipCoord = 32767;
michael@0:         const SkIRect& bounds = origClip.getBounds();
michael@0:         if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) {
michael@0:             SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord };
michael@0:             tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op);
michael@0:             clipRgn = &tmpClipStorage;
michael@0:         }
michael@0:     }
michael@0:     // for here down, use clipRgn, not origClip
michael@0: 
michael@0:     SkScanClipper   clipper(blitter, clipRgn, ir);
michael@0:     const SkIRect*  clipRect = clipper.getClipRect();
michael@0: 
michael@0:     if (clipper.getBlitter() == NULL) { // clipped out
michael@0:         if (path.isInverseFillType()) {
michael@0:             blitter->blitRegion(*clipRgn);
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // now use the (possibly wrapped) blitter
michael@0:     blitter = clipper.getBlitter();
michael@0: 
michael@0:     if (path.isInverseFillType()) {
michael@0:         sk_blit_above(blitter, ir, *clipRgn);
michael@0:     }
michael@0: 
michael@0:     SkIRect superRect, *superClipRect = NULL;
michael@0: 
michael@0:     if (clipRect) {
michael@0:         superRect.set(  clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT,
michael@0:                         clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT);
michael@0:         superClipRect = &superRect;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
michael@0: 
michael@0:     // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it
michael@0:     // if we're an inverse filltype
michael@0:     if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) {
michael@0:         MaskSuperBlitter    superBlit(blitter, ir, *clipRgn);
michael@0:         SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
michael@0:         sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, *clipRgn);
michael@0:     } else {
michael@0:         SuperBlitter    superBlit(blitter, ir, *clipRgn);
michael@0:         sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, *clipRgn);
michael@0:     }
michael@0: 
michael@0:     if (path.isInverseFillType()) {
michael@0:         sk_blit_below(blitter, ir, *clipRgn);
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #include "SkRasterClip.h"
michael@0: 
michael@0: void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (clip.isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (clip.isBW()) {
michael@0:         FillPath(path, clip.bwRgn(), blitter);
michael@0:     } else {
michael@0:         SkRegion        tmp;
michael@0:         SkAAClipBlitter aaBlitter;
michael@0: 
michael@0:         tmp.setRect(clip.getBounds());
michael@0:         aaBlitter.init(blitter, &clip.aaRgn());
michael@0:         SkScan::FillPath(path, tmp, &aaBlitter);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip,
michael@0:                           SkBlitter* blitter) {
michael@0:     if (clip.isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (clip.isBW()) {
michael@0:         AntiFillPath(path, clip.bwRgn(), blitter);
michael@0:     } else {
michael@0:         SkRegion        tmp;
michael@0:         SkAAClipBlitter aaBlitter;
michael@0: 
michael@0:         tmp.setRect(clip.getBounds());
michael@0:         aaBlitter.init(blitter, &clip.aaRgn());
michael@0:         SkScan::AntiFillPath(path, tmp, &aaBlitter, true);
michael@0:     }
michael@0: }