New 'blitAntiRect' entry point for blitters, specialized in supersampling

code to avoid quarter-scanline-at-a-time building of large rectangular
clips.

Speeds up aa_clip_build_path_AA benchmark 2x, aa_clip_build_rect_AA benchmark
10x or more. This is a sufficient performance gain to let Chromium reenable
WebKit's soft clipping code. Rolling into Chromium will require ~18
rebaselines.



git-svn-id: http://skia.googlecode.com/svn/trunk@2924 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 173 insertions, 36 deletions

diff --git a/src/core/SkAAClip.cpp b/src/core/SkAAClip.cpp
index cb49178e35..39eadbf243 100644
--- a/src/core/SkAAClip.cpp
+++ b/src/core/SkAAClip.cpp
@@ -926,6 +926,16 @@ public:
         SkASSERT(row->fWidth <= fBounds.width());
     }
 
+    void addColumn(int x, int y, U8CPU alpha, int height) {
+        SkASSERT(fBounds.contains(x, y + height - 1));
+
+        this->addRun(x, y, alpha, 1);
+        this->flushRowH(fCurrRow);
+        y -= fBounds.fTop;
+        SkASSERT(y == fCurrRow->fY);
+        fCurrRow->fY = y + height - 1;
+    }
+ 
     void addRectRun(int x, int y, int width, int height) {
         SkASSERT(fBounds.contains(x + width - 1, y + height - 1));
         this->addRun(x, y, 0xFF, width);
@@ -939,6 +949,39 @@ public:
         fCurrRow->fY = y + height - 1;
     }
 
+    void addAntiRectRun(int x, int y, int width, int height,
+                        SkAlpha leftAlpha, SkAlpha rightAlpha) {
+        SkASSERT(fBounds.contains(x + width - 1 +
+                 (leftAlpha > 0 ? 1 : 0) + (rightAlpha > 0 ? 1 : 0),
+                 y + height - 1));
+        SkASSERT(width >= 0);
+
+        // Conceptually we're always adding 3 runs, but we should
+        // merge or omit them if possible.
+        if (leftAlpha == 0xFF) {
+            width++;
+        } else if (leftAlpha > 0) {
+          this->addRun(x++, y, leftAlpha, 1);
+        }
+        if (rightAlpha == 0xFF) {
+            width++;
+        }
+        if (width > 0) {
+            this->addRun(x, y, 0xFF, width);
+        }
+        if (rightAlpha > 0 && rightAlpha < 255) {
+            this->addRun(x + width, y, rightAlpha, 1);
+        }
+
+        // we assume the rect must be all we'll see for these scanlines
+        // so we ensure our row goes all the way to our right
+        this->flushRowH(fCurrRow);
+
+        y -= fBounds.fTop;
+        SkASSERT(y == fCurrRow->fY);
+        fCurrRow->fY = y + height - 1;
+    }
+
     bool finish(SkAAClip* target) {
         this->flushRow(false);
 
@@ -1113,14 +1156,29 @@ public:
         }
     }
 
-    virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE
-        { unexpected(); }
+    /**
+       Must evaluate clips in scan-line order, so don't want to allow blitV(),
+       but an AAClip can be clipped down to a single pixel wide, so we
+       must support it (given AntiRect semantics: minimum width is 2).
+       Instead we'll rely on the runtime asserts to guarantee Y monotonicity;
+       any failure cases that misses may have minor artifacts.
+    */
+    virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE {
+        this->recordMinY(y);
+        fBuilder->addColumn(x, y, alpha, height);
+    }
 
     virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE {
         this->recordMinY(y);
         fBuilder->addRectRun(x, y, width, height);
     }
 
+    virtual void blitAntiRect(int x, int y, int width, int height,
+                     SkAlpha leftAlpha, SkAlpha rightAlpha) SK_OVERRIDE {
+        this->recordMinY(y);
+        fBuilder->addAntiRectRun(x, y, width, height, leftAlpha, rightAlpha);
+    }
+
     virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE
         { unexpected(); }
 
diff --git a/src/core/SkBlitter.cpp b/src/core/SkBlitter.cpp
index 307d51b340..8e93ef1303 100644
--- a/src/core/SkBlitter.cpp
+++ b/src/core/SkBlitter.cpp
@@ -52,6 +52,16 @@ void SkBlitter::blitRect(int x, int y, int width, int height) {
     }
 }
 
+/// Default implementation doesn't check for any easy optimizations
+/// such as alpha == 0 or 255; also uses blitV(), which some subclasses
+/// may not support.
+void SkBlitter::blitAntiRect(int x, int y, int width, int height,
+                             SkAlpha leftAlpha, SkAlpha rightAlpha) {
+    this->blitV(x, y, height, leftAlpha);
+    this->blitRect(x + 1, y, width, height);
+    this->blitV(x + width + 1, y, height, rightAlpha);
+}
+
 //////////////////////////////////////////////////////////////////////////////
 
 static inline void bits_to_runs(SkBlitter* blitter, int x, int y,
@@ -335,6 +345,37 @@ void SkRectClipBlitter::blitRect(int left, int y, int width, int height) {
     }
 }
 
+void SkRectClipBlitter::blitAntiRect(int left, int y, int width, int height,
+                                     SkAlpha leftAlpha, SkAlpha rightAlpha) {
+    SkIRect    r;
+
+    // The *true* width of the rectangle blitted is width+2:
+    r.set(left, y, left + width + 2, y + height);
+    if (r.intersect(fClipRect)) {
+        if (r.fLeft != left) {
+            SkASSERT(r.fLeft > left);
+            leftAlpha = 255;
+        }
+        if (r.fRight != left + width + 2) {
+            SkASSERT(r.fRight < left + width + 2);
+            rightAlpha = 255;
+        }
+        if (255 == leftAlpha && 255 == rightAlpha) {
+            fBlitter->blitRect(r.fLeft, r.fTop, r.width(), r.height());
+        } else if (1 == r.width()) {
+            if (r.fLeft == left) {
+                fBlitter->blitV(r.fLeft, r.fTop, r.height(), leftAlpha);
+            } else {
+                SkASSERT(r.fLeft == left + width + 1);
+                fBlitter->blitV(r.fLeft, r.fTop, r.height(), rightAlpha);
+            }
+        } else {
+            fBlitter->blitAntiRect(r.fLeft, r.fTop, r.width() - 2, r.height(),
+                                   leftAlpha, rightAlpha);
+        }
+    }
+}
+
 void SkRectClipBlitter::blitMask(const SkMask& mask, const SkIRect& clip) {
     SkASSERT(mask.fBounds.contains(clip));
 
@@ -430,6 +471,44 @@ void SkRgnClipBlitter::blitRect(int x, int y, int width, int height) {
     }
 }
 
+void SkRgnClipBlitter::blitAntiRect(int x, int y, int width, int height,
+                                    SkAlpha leftAlpha, SkAlpha rightAlpha) {
+    // The *true* width of the rectangle to blit is width + 2
+    SkIRect    bounds;
+    bounds.set(x, y, x + width + 2, y + height);
+
+    SkRegion::Cliperator    iter(*fRgn, bounds);
+
+    while (!iter.done()) {
+        const SkIRect& r = iter.rect();
+        SkASSERT(bounds.contains(r));
+        SkASSERT(r.fLeft >= x);
+        SkASSERT(r.fRight < x + width + 2);
+
+        SkAlpha effectiveLeftAlpha = (r.fLeft == x) ? leftAlpha : 255;
+        SkAlpha effectiveRightAlpha = (r.fRight == x + width + 2) ?
+                                      rightAlpha : 255;
+
+        if (255 == effectiveLeftAlpha && 255 == effectiveRightAlpha) {
+            fBlitter->blitRect(r.fLeft, r.fTop, r.width(), r.height());
+        } else if (1 == r.width()) {
+            if (r.fLeft == x) {
+                fBlitter->blitV(r.fLeft, r.fTop, r.height(), 
+                                effectiveLeftAlpha);
+            } else {
+                SkASSERT(r.fLeft == x + width + 1);
+                fBlitter->blitV(r.fLeft, r.fTop, r.height(),
+                                effectiveRightAlpha);
+            }
+        } else {
+            fBlitter->blitAntiRect(r.fLeft, r.fTop, r.width() - 2, r.height(),
+                                   effectiveLeftAlpha, effectiveRightAlpha);
+        }
+        iter.next();
+    }
+}
+
+
 void SkRgnClipBlitter::blitMask(const SkMask& mask, const SkIRect& clip) {
     SkASSERT(mask.fBounds.contains(clip));
 
diff --git a/src/core/SkScan_AntiPath.cpp b/src/core/SkScan_AntiPath.cpp
index 7b81716b6d..346b82a6be 100644
--- a/src/core/SkScan_AntiPath.cpp
+++ b/src/core/SkScan_AntiPath.cpp
@@ -156,6 +156,12 @@ static inline int coverage_to_alpha(int aa) {
     return aa;
 }
 
+static inline int coverage_to_exact_alpha(int aa) {
+    static int map [] = { 0, 64, 128, 192, 255 };
+    SkASSERT(SHIFT == 2);
+    return map[aa];
+}
+
 void SuperBlitter::blitH(int x, int y, int width) {
     SkASSERT(width > 0);
 
@@ -183,10 +189,6 @@ void SuperBlitter::blitH(int x, int y, int width) {
         fCurrIY = iy;
     }
 
-    // we sub 1 from maxValue 1 time for each block, so that we don't
-    // hit 256 as a summed max, but 255.
-//  int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT);
-
     int start = x;
     int stop = x + width;
 
@@ -204,10 +206,11 @@ void SuperBlitter::blitH(int x, int y, int width) {
         if (fb == 0) {
             n += 1;
         } else {
-            fb = (1 << SHIFT) - fb;
+            fb = SCALE - fb;
         }
     }
 
+    // TODO - should this be using coverage_to_exact_alpha?
     fOffsetX = fRuns.add(x >> SHIFT, coverage_to_alpha(fb),
                          n, coverage_to_alpha(fe),
                          (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT),
@@ -288,24 +291,35 @@ void SuperBlitter::blitRect(int x, int y, int width, int height) {
             x = 0;
         }
 
+        // There is always a left column, a middle, and a right column.
+        // ileft is the destination x of the first pixel of the entire rect.
+        // xleft is (SCALE - # of covered supersampled pixels) in that
+        // destination pixel.
         int ileft = x >> SHIFT;
         int xleft = x & MASK;
+        // irite is the destination x of the last pixel of the OPAQUE section.
+        // xrite is the number of supersampled pixels extending beyond irite;
+        // xrite/SCALE should give us alpha.
         int irite = (x + width) >> SHIFT;
         int xrite = (x + width) & MASK;
+        if (!xrite) {
+            xrite = SCALE;
+            irite--;
+        }
+
         int n = irite - ileft - 1;
         if (n < 0) {
-            // only one pixel, call blitV()?
             xleft = xrite - xleft;
-            n = 0;
+            SkASSERT(xleft <= SCALE);
+            SkASSERT(xleft > 0);
             xrite = 0;
+            fRealBlitter->blitV(ileft + fLeft, start_y, count,
+                coverage_to_exact_alpha(xleft));
         } else {
-            if (0 == xleft) {
-                n += 1;
-            } else {
-                xleft = (1 << SHIFT) - xleft;
-            }
+            xleft = SCALE - xleft;
         }
 
+
         // here we go
         SkASSERT(start_y > fCurrIY);
         this->flush();
@@ -314,23 +328,13 @@ void SuperBlitter::blitRect(int x, int y, int width, int height) {
         // values up. If we didn't care about that, we could be more precise
         // and compute these exactly (e.g. 2->128 instead of 2->124)
         //
-        const int coverageL = coverage_to_alpha(xleft) << SHIFT;
-        const int coverageR = coverage_to_alpha(xrite) << SHIFT;
+        const int coverageL = coverage_to_exact_alpha(xleft);
+        const int coverageR = coverage_to_exact_alpha(xrite);
         SkASSERT(n + (coverageR != 0) <= fWidth);
 
-        for (int i = start_y; i < stop_y; ++i) {
-            // note: we should only need to call set_left_rite once, but
-            // our clipping blitters sometimes modify runs/alpha in-place,
-            // so for now we reset fRuns each time :(
-            //
-            //  TODO:
-            //  - don't modify in-place, or at least tell us when you're going to
-            //  - pass height down to blitAntiH (blitAntiHV) so that aaclip and
-            //    other can take advantage of the vertical-repeat explicitly
-            //
-            set_left_rite_runs(fRuns, ileft, coverageL, n, coverageR);
-            fRealBlitter->blitAntiH(fLeft, i, fRuns.fAlpha, fRuns.fRuns);
-        }
+        SkASSERT(coverageL > 0 || n > 0 || coverageR > 0);
+        fRealBlitter->blitAntiRect(ileft + fLeft, start_y, n, count,
+                                   coverageL, coverageR);
 
         // preamble for our next call to blitH()
         fCurrIY = stop_y - 1;
@@ -340,7 +344,7 @@ void SuperBlitter::blitRect(int x, int y, int width, int height) {
         x = origX;
     }
 
-    // catch any remaining few
+    // catch any remaining few rows
     SkASSERT(height <= MASK);
     while (--height >= 0) {
         this->blitH(x, y++, width);
@@ -507,10 +511,6 @@ void MaskSuperBlitter::blitH(int x, int y, int width) {
         x = 0;
     }
 
-    // we sub 1 from maxValue 1 time for each block, so that we don't
-    // hit 256 as a summed max, but 255.
-//  int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT);
-
     uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT);
 
     int start = x;
@@ -531,10 +531,10 @@ void MaskSuperBlitter::blitH(int x, int y, int width) {
         if (0 == fb) {
             n += 1;
         } else {
-            fb = (1 << SHIFT) - fb;
+            fb = SCALE - fb;
         }
 #else
-        fb = (1 << SHIFT) - fb;
+        fb = SCALE - fb;
 #endif
         SkASSERT(row >= fMask.fImage);
         SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1);