add special matrixprocs when the matrix is at most translate. These are faster

(somewhat) than their scale counterparts, but are also numerically exact for
any size bitmaps. The scale versions, because they operate in a scaled 65535
space, are not always exact for large images (due to SK_Fixed1 / width) loss of
bits



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

4 files changed, 333 insertions, 86 deletions

diff --git a/src/core/SkBitmapProcShader.cpp b/src/core/SkBitmapProcShader.cpp
index b396c68d5c..44af0cc586 100644
--- a/src/core/SkBitmapProcShader.cpp
+++ b/src/core/SkBitmapProcShader.cpp
@@ -140,7 +140,7 @@ void SkBitmapProcShader::shadeSpan(int x, int y, SkPMColor dstC[], int count) {
         return;
     }
 
-    uint32_t buffer[BUF_MAX];
+    uint32_t buffer[BUF_MAX + 1];
     SkBitmapProcState::MatrixProc   mproc = state.fMatrixProc;
     SkBitmapProcState::SampleProc32 sproc = state.fSampleProc32;
     int max = fState.fDoFilter ? (BUF_MAX >> 1) : BUF_MAX;
diff --git a/src/core/SkBitmapProcState.cpp b/src/core/SkBitmapProcState.cpp
index 3c5833dd25..b999a0c9f5 100644
--- a/src/core/SkBitmapProcState.cpp
+++ b/src/core/SkBitmapProcState.cpp
@@ -5,14 +5,6 @@
 #include "SkPaint.h"
 #include "SkShader.h"   // for tilemodes
 
-#ifdef SK_CPU_BENDIAN
-    #define UNPACK_PRIMARY_SHORT(packed)    ((uint32_t)(packed) >> 16)
-    #define UNPACK_SECONDARY_SHORT(packed)  ((packed) & 0xFFFF)
-#else
-    #define UNPACK_PRIMARY_SHORT(packed)    ((packed) & 0xFFFF)
-    #define UNPACK_SECONDARY_SHORT(packed)  ((uint32_t)(packed) >> 16)
-#endif
-
 // returns expanded * 5bits
 static inline uint32_t Filter_565_Expanded(unsigned x, unsigned y,
                                            uint32_t a00, uint32_t a01,
@@ -334,20 +326,20 @@ bool SkBitmapProcState::chooseProcs(const SkMatrix& inv, const SkPaint& paint) {
     if (fOrigBitmap.width() == 0 || fOrigBitmap.height() == 0) {
         return false;
     }
+
     const SkMatrix* m;
-    bool clamp_clamp;
+    bool trivial_matrix = (inv.getType() & ~SkMatrix::kTranslate_Mask) == 0;
+    bool clamp_clamp = SkShader::kClamp_TileMode == fTileModeX &&
+                       SkShader::kClamp_TileMode == fTileModeY;
 
-    if (SkShader::kClamp_TileMode == fTileModeX &&
-            SkShader::kClamp_TileMode == fTileModeY) {
+    if (clamp_clamp || trivial_matrix) {
         m = &inv;
-        clamp_clamp = true;
     } else {
         fUnitInvMatrix = inv;
         fUnitInvMatrix.postIDiv(fOrigBitmap.width(), fOrigBitmap.height());
         m = &fUnitInvMatrix;
-        clamp_clamp = false;
     }
-    
+
     fBitmap = &fOrigBitmap;
     if (fOrigBitmap.hasMipMap()) {
         int shift = fOrigBitmap.extractMipLevel(&fMipBitmap,
@@ -390,7 +382,7 @@ bool SkBitmapProcState::chooseProcs(const SkMatrix& inv, const SkPaint& paint) {
     fSampleProc32 = NULL;
     fSampleProc16 = NULL;
 
-    fMatrixProc = this->chooseMatrixProc();
+    fMatrixProc = this->chooseMatrixProc(trivial_matrix);
     if (NULL == fMatrixProc) {
         return false;
     }
diff --git a/src/core/SkBitmapProcState.h b/src/core/SkBitmapProcState.h
index 796257995c..2790a6c26a 100644
--- a/src/core/SkBitmapProcState.h
+++ b/src/core/SkBitmapProcState.h
@@ -46,6 +46,7 @@ struct SkBitmapProcState {
                                  uint16_t colors[]);
     
     typedef U16CPU (*FixedTileProc)(SkFixed);   // returns 0..0xFFFF
+    typedef U16CPU (*IntTileProc)(int value, int count);   // returns 0..count-1
 
     // If a shader proc is present, then the corresponding matrix/sample procs
     // are ignored
@@ -62,6 +63,7 @@ struct SkBitmapProcState {
 
     FixedTileProc       fTileProcX;         // chooseProcs
     FixedTileProc       fTileProcY;         // chooseProcs
+    IntTileProc         fIntTileProcY;      // chooseProcs
     SkFixed             fFilterOneX;
     SkFixed             fFilterOneY;
 
@@ -96,8 +98,32 @@ private:
     SkBitmap            fOrigBitmap;        // CONSTRUCTOR
     SkBitmap            fMipBitmap;
 
-    MatrixProc chooseMatrixProc();
+    MatrixProc chooseMatrixProc(bool trivial_matrix);
     bool chooseProcs(const SkMatrix& inv, const SkPaint&);
 };
 
+/*  Macros for packing and unpacking pairs of 16bit values in a 32bit uint.
+    Used to allow access to a stream of uint16_t either one at a time, or
+    2 at a time by unpacking a uint32_t
+ */
+#ifdef SK_CPU_BENDIAN
+    #define PACK_TWO_SHORTS(pri, sec) ((pri) << 16 | (sec))
+    #define UNPACK_PRIMARY_SHORT(packed)    ((uint32_t)(packed) >> 16)
+    #define UNPACK_SECONDARY_SHORT(packed)  ((packed) & 0xFFFF)
+#else
+    #define PACK_TWO_SHORTS(pri, sec) ((pri) | ((sec) << 16))
+    #define UNPACK_PRIMARY_SHORT(packed)    ((packed) & 0xFFFF)
+    #define UNPACK_SECONDARY_SHORT(packed)  ((uint32_t)(packed) >> 16)
+#endif
+
+#ifdef SK_DEBUG
+    static inline uint32_t pack_two_shorts(U16CPU pri, U16CPU sec) {
+        SkASSERT((uint16_t)pri == pri);
+        SkASSERT((uint16_t)sec == sec);
+        return PACK_TWO_SHORTS(pri, sec);
+    }
+#else
+    #define pack_two_shorts(pri, sec)   PACK_TWO_SHORTS(pri, sec)
+#endif
+
 #endif
diff --git a/src/core/SkBitmapProcState_matrixProcs.cpp b/src/core/SkBitmapProcState_matrixProcs.cpp
index beb21c8ef7..cf32d9b451 100644
--- a/src/core/SkBitmapProcState_matrixProcs.cpp
+++ b/src/core/SkBitmapProcState_matrixProcs.cpp
@@ -1,27 +1,30 @@
 #include "SkBitmapProcState.h"
 #include "SkPerspIter.h"
 #include "SkShader.h"
+#include "SkUtils.h"
+
+/*  returns 0...(n-1) given any x (positive or negative).
+    
+    As an example, if n (which is always positive) is 5...
+ 
+          x: -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8
+    returns:  2  3  4  0  1  2  3  4  0  1  2  3  4  0  1  2  3
+ */
+static inline int sk_int_mod(int x, int n) {
+    SkASSERT(n > 0);
+    if ((unsigned)x >= (unsigned)n) {
+        if (x < 0) {
+            x = n + ~(~x % n);
+        } else {
+            x = x % n;
+        }
+    }
+    return x;
+}
 
 void decal_nofilter_scale(uint32_t dst[], SkFixed fx, SkFixed dx, int count);
 void decal_filter_scale(uint32_t dst[], SkFixed fx, SkFixed dx, int count);
 
-#ifdef SK_CPU_BENDIAN
-    #define PACK_TWO_SHORTS(pri, sec) ((pri) << 16 | (sec))
-#else
-    #define PACK_TWO_SHORTS(pri, sec) ((pri) | ((sec) << 16))
-#endif
-
-#ifdef SK_DEBUG
-    static uint32_t pack_two_shorts(U16CPU pri, U16CPU sec)
-    {
-        SkASSERT((uint16_t)pri == pri);
-        SkASSERT((uint16_t)sec == sec);
-        return PACK_TWO_SHORTS(pri, sec);
-    }
-#else
-    #define pack_two_shorts(pri, sec)   PACK_TWO_SHORTS(pri, sec)
-#endif
-
 #define MAKENAME(suffix)        ClampX_ClampY ## suffix
 #define TILEX_PROCF(fx, max)    SkClampMax((fx) >> 16, max)
 #define TILEY_PROCF(fy, max)    SkClampMax((fy) >> 16, max)
@@ -91,39 +94,51 @@ static SkBitmapProcState::FixedTileProc choose_tile_proc(unsigned m)
     return fixed_mirror;
 }
 
-SkBitmapProcState::MatrixProc SkBitmapProcState::chooseMatrixProc()
-{
-    int index = 0;
-    if (fDoFilter)
-        index = 1;
-    if (fInvType & SkMatrix::kPerspective_Mask)
-        index |= 4;
-    else if (fInvType & SkMatrix::kAffine_Mask)
-        index |= 2;
+static inline U16CPU int_clamp(int x, int n) {
+#ifdef SK_CPU_HAS_CONDITIONAL_INSTR
+    if (x >= n)
+        x = n - 1;
+    if (x < 0)
+        x = 0;
+#else
+    if ((unsigned)x >= (unsigned)n) {
+        if (x < 0) {
+            x = 0;
+        } else {
+            x = n - 1;
+        }
+    }
+#endif
+    return x;
+}
 
-    if (SkShader::kClamp_TileMode == fTileModeX &&
-        SkShader::kClamp_TileMode == fTileModeY)
-    {
-        // clamp gets special version of filterOne
-        fFilterOneX = SK_Fixed1;
-        fFilterOneY = SK_Fixed1;
-        return ClampX_ClampY_Procs[index];
+static inline U16CPU int_repeat(int x, int n) {
+    return sk_int_mod(x, n);
+}
+
+static inline U16CPU int_mirror(int x, int n) {
+    x = sk_int_mod(x, 2 * n);
+    if (x >= n) {
+        x = n + ~(x - n);
     }
-    
-    // all remaining procs use this form for filterOne
-    fFilterOneX = SK_Fixed1 / fBitmap->width();
-    fFilterOneY = SK_Fixed1 / fBitmap->height();
+    return x;
+}
 
-    if (SkShader::kRepeat_TileMode == fTileModeX &&
-        SkShader::kRepeat_TileMode == fTileModeY)
-    {
-        return RepeatX_RepeatY_Procs[index];
+#if 0
+static void test_int_tileprocs() {
+    for (int i = -8; i <= 8; i++) {
+        SkDebugf(" int_mirror(%2d, 3) = %d\n", i, int_mirror(i, 3));
     }
+}
+#endif
 
-    // only general needs these procs
-    fTileProcX = choose_tile_proc(fTileModeX);
-    fTileProcY = choose_tile_proc(fTileModeY);
-    return GeneralXY_Procs[index];
+static SkBitmapProcState::IntTileProc choose_int_tile_proc(unsigned tm) {
+    if (SkShader::kClamp_TileMode == tm)
+        return int_clamp;
+    if (SkShader::kRepeat_TileMode == tm)
+        return int_repeat;
+    SkASSERT(SkShader::kMirror_TileMode == tm);
+    return int_mirror;
 }
 
 //////////////////////////////////////////////////////////////////////////////
@@ -166,34 +181,248 @@ void decal_filter_scale(uint32_t dst[], SkFixed fx, SkFixed dx, int count)
     }
 }
 
-///////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+// stores the same as SCALE, but is cheaper to compute. Also since there is no
+// scale, we don't need/have a FILTER version
 
-void repeat_nofilter_identity(uint32_t dst[], int x, int width, int count)
-{
-    if (x >= width)
-        x %= width;
+static void fill_sequential(uint16_t xptr[], int start, int count) {
+#if 1
+    if (reinterpret_cast<intptr_t>(xptr) & 0x2) {
+        *xptr++ = start++;
+        count -= 1;
+    }
+    if (count > 3) {
+        uint32_t* xxptr = reinterpret_cast<uint32_t*>(xptr);
+        uint32_t pattern0 = PACK_TWO_SHORTS(start + 0, start + 1);
+        uint32_t pattern1 = PACK_TWO_SHORTS(start + 2, start + 3);
+        start += count & ~3;
+        int qcount = count >> 2;
+        do {
+            *xxptr++ = pattern0;
+            pattern0 += 0x40004;
+            *xxptr++ = pattern1;
+            pattern1 += 0x40004;
+        } while (--qcount >= 0);
+        xptr = reinterpret_cast<uint16_t*>(xxptr);
+        count &= 3;
+    }
+    while (--count >= 0) {
+        *xptr++ = start++;
+    }
+#else
+    for (int i = 0; i < count; i++) {
+        *xptr++ = start++;
+    }
+#endif
+}
 
-    int i;
-    uint16_t* xx = (uint16_t*)dst;
+static int nofilter_trans_preamble(const SkBitmapProcState& s, uint32_t** xy,
+                                   int x, int y) {
+    SkPoint pt;
+    s.fInvProc(*s.fInvMatrix, SkIntToScalar(x) + SK_ScalarHalf,
+               SkIntToScalar(y) + SK_ScalarHalf, &pt);
+    **xy = s.fIntTileProcY(SkScalarToFixed(pt.fY) >> 16,
+                           s.fBitmap->height());
+    *xy += 1;   // bump the ptr
+    // return our starting X position
+    return SkScalarToFixed(pt.fX) >> 16;
+}
 
-    // do the first partial run
-    int n = width - x;
-    if (n > count)
-        n = count;
+static void clampx_nofilter_trans(const SkBitmapProcState& s,
+                                  uint32_t xy[], int count, int x, int y) {
+    SkASSERT((s.fInvType & ~SkMatrix::kTranslate_Mask) == 0);
+
+    int xpos = nofilter_trans_preamble(s, &xy, x, y);
+    const int width = s.fBitmap->width();    
+    if (1 == width) {
+        // all of the following X values must be 0
+        memset(xy, 0, count * sizeof(uint16_t));
+        return;
+    }
     
+    uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
+    int n;
+
+    // fill before 0 as needed
+    if (xpos < 0) {
+        n = -xpos;
+        if (n > count) {
+            n = count;
+        }
+        memset(xptr, 0, n * sizeof(uint16_t));
+        count -= n;
+        if (0 == count) {
+            return;
+        }
+        xptr += n;
+        xpos = 0;
+    }
+
+    // fill in 0..width-1 if needed
+    if (xpos < width) {
+        n = width - xpos;
+        if (n > count) {
+            n = count;
+        }
+        fill_sequential(xptr, xpos, n);
+        count -= n;
+        if (0 == count) {
+            return;
+        }
+        xptr += n;
+    }
+
+    // fill the remaining with the max value
+    sk_memset16(xptr, width - 1, count * sizeof(uint16_t));
+}
+
+static void repeatx_nofilter_trans(const SkBitmapProcState& s,
+                                   uint32_t xy[], int count, int x, int y) {
+    SkASSERT((s.fInvType & ~SkMatrix::kTranslate_Mask) == 0);
+
+    int xpos = nofilter_trans_preamble(s, &xy, x, y);
+    const int width = s.fBitmap->width();    
+    if (1 == width) {
+        // all of the following X values must be 0
+        memset(xy, 0, count * sizeof(uint16_t));
+        return;
+    }
+
+    uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
+    int start = sk_int_mod(xpos, width);
+    int n = width - start;
+    if (n > count) {
+        n = count;
+    }
+    fill_sequential(xptr, start, n);
+    xptr += n;
+    count -= n;
+
+    while (count >= width) {
+        fill_sequential(xptr, 0, width);
+        xptr += width;
+        count -= width;
+    }
+
+    if (count > 0) {
+        fill_sequential(xptr, 0, count);
+    }
+}
+
+static void fill_backwards(uint16_t xptr[], int pos, int count) {
+    for (int i = 0; i < count; i++) {
+        SkASSERT(pos >= 0);
+        xptr[i] = pos--;
+    }
+}
+
+static void mirrorx_nofilter_trans(const SkBitmapProcState& s,
+                                   uint32_t xy[], int count, int x, int y) {
+    SkASSERT((s.fInvType & ~SkMatrix::kTranslate_Mask) == 0);
+
+    int xpos = nofilter_trans_preamble(s, &xy, x, y);
+    const int width = s.fBitmap->width();    
+    if (1 == width) {
+        // all of the following X values must be 0
+        memset(xy, 0, count * sizeof(uint16_t));
+        return;
+    }
+
+    uint16_t* xptr = reinterpret_cast<uint16_t*>(xy);
+    // need to know our start, and our initial phase (forward or backward)
+    bool forward;
+    int n;
+    int start = sk_int_mod(xpos, 2 * width);
+    if (start >= width) {
+        start = width + ~(start - width);
+        forward = false;
+        n = start + 1;  // [start .. 0]
+    } else {
+        forward = true;
+        n = width - start;  // [start .. width)
+    }
+    if (n > count) {
+        n = count;
+    }
+    if (forward) {
+        fill_sequential(xptr, start, n);
+    } else {
+        fill_backwards(xptr, start, n);
+    }
+    forward = !forward;
+    xptr += n;
     count -= n;
-    n += x;
-    for (i = x; i < n; i++)
-        *xx++ = SkToU16(i);
-
-    // do all the full-width runs
-    while ((count -= width) >= 0)
-        for (i = 0; i < width; i++)
-            *xx++ = SkToU16(i);
-
-    // final cleanup run
-    count += width;
-    for (i = 0; i < count; i++)
-        *xx++ = SkToU16(i);
+    
+    while (count >= width) {
+        if (forward) {
+            fill_sequential(xptr, 0, width);
+        } else {
+            fill_backwards(xptr, width - 1, width);
+        }
+        forward = !forward;
+        xptr += width;
+        count -= width;
+    }
+    
+    if (count > 0) {
+        if (forward) {
+            fill_sequential(xptr, 0, count);
+        } else {
+            fill_backwards(xptr, width - 1, count);
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+SkBitmapProcState::MatrixProc
+SkBitmapProcState::chooseMatrixProc(bool trivial_matrix) {
+//    test_int_tileprocs();
+    // check for our special case when there is no scale/affine/perspective
+    if (trivial_matrix) {
+        SkASSERT(!fDoFilter);
+        fIntTileProcY = choose_int_tile_proc(fTileModeY);
+        switch (fTileModeX) {
+            case SkShader::kClamp_TileMode:
+                return clampx_nofilter_trans;
+            case SkShader::kRepeat_TileMode:
+                return repeatx_nofilter_trans;
+            case SkShader::kMirror_TileMode:
+                return mirrorx_nofilter_trans;
+        }
+    }
+    
+    int index = 0;
+    if (fDoFilter) {
+        index = 1;
+    }
+    if (fInvType & SkMatrix::kPerspective_Mask) {
+        index += 4;
+    } else if (fInvType & SkMatrix::kAffine_Mask) {
+        index += 4;
+    }
+    
+    if (SkShader::kClamp_TileMode == fTileModeX &&
+        SkShader::kClamp_TileMode == fTileModeY)
+    {
+        // clamp gets special version of filterOne
+        fFilterOneX = SK_Fixed1;
+        fFilterOneY = SK_Fixed1;
+        return ClampX_ClampY_Procs[index];
+    }
+    
+    // all remaining procs use this form for filterOne
+    fFilterOneX = SK_Fixed1 / fBitmap->width();
+    fFilterOneY = SK_Fixed1 / fBitmap->height();
+    
+    if (SkShader::kRepeat_TileMode == fTileModeX &&
+        SkShader::kRepeat_TileMode == fTileModeY)
+    {
+        return RepeatX_RepeatY_Procs[index];
+    }
+    
+    fTileProcX = choose_tile_proc(fTileModeX);
+    fTileProcY = choose_tile_proc(fTileModeY);
+    return GeneralXY_Procs[index];
 }