use triangle filter for odd dimensions in mip-levels

src/core/SkMipMap.cpp

Index: src/core/SkMipMap.cpp
diff --git a/src/core/SkMipMap.cpp b/src/core/SkMipMap.cpp
index 6e0aaed6973e174e0359d607e7305e299c3ed1cc..5fadb6e4e4d090c33da47d433d6a6ec6b0767150 100644
--- a/src/core/SkMipMap.cpp
+++ b/src/core/SkMipMap.cpp
@@ -9,6 +9,8 @@
 #include "SkBitmap.h"
 #include "SkColorPriv.h"
 
+#ifdef SK_SUPPORT_LEGACY_MIPLEVEL_BUILDER
+
 static void downsample32_nocheck(void* dst, int, int, const void* srcPtr, const SkPixmap& srcPM) {
     const uint32_t* p = static_cast<const uint32_t*>(srcPtr);
     const uint32_t* baseP = p;
@@ -132,7 +134,7 @@ static void downsample4444(void* dst, int x, int y, const void* srcPtr, const Sk
     }
     c += expand4444(*p);
 
-   *((uint16_t*)dst) = (uint16_t)collaps4444(c >> 2);
+    *((uint16_t*)dst) = (uint16_t)collaps4444(c >> 2);
 }
 
 static void downsample8_nocheck(void* dst, int, int, const void* srcPtr, const SkPixmap& srcPM) {
@@ -314,9 +316,308 @@ SkMipMap* SkMipMap::Build(const SkBitmap& src, SkDiscardableFactoryProc fact) {
         addr += height * rowBytes;
     }
     SkASSERT(addr == baseAddr + size);
+    
+    return mipmap;
+}
+
+#else   // new technique that handles odd dimensions better
+
+//
+// ColorTypeFilter is the "Type" we pass to some downsample template functions.
+// It controls how we expand a pixel into a large type, with space between each component,
+// so we can then perform our simple filter (either box or triangle) and store the intermediates
+// in the expanded type.
+//
+
+struct ColorTypeFilter_8888 {
+    typedef uint32_t Type;
+    static uint64_t Expand(uint32_t x) {
+        return (x & 0xFF00FF) | ((uint64_t)(x & 0xFF00FF00) << 24);
+    }
+    static uint32_t Compact(uint64_t x) {
+        return (uint32_t)((x & 0xFF00FF) | ((x >> 24) & 0xFF00FF00));
+    }
+};
+
+struct ColorTypeFilter_565 {
+    typedef uint16_t Type;
+    static uint32_t Expand(uint16_t x) {
+        return (x & ~SK_G16_MASK_IN_PLACE) | ((x & SK_G16_MASK_IN_PLACE) << 16);
+    }
+    static uint16_t Compact(uint32_t x) {
+        return (x & ~SK_G16_MASK_IN_PLACE) | ((x >> 16) & SK_G16_MASK_IN_PLACE);
+    }
+};
+
+struct ColorTypeFilter_4444 {
+    typedef uint16_t Type;
+    static uint32_t Expand(uint16_t x) {
+        return (x & 0xF0F) | ((x & ~0xF0F) << 12);
+    }
+    static uint16_t Compact(uint32_t x) {
+        return (x & 0xF0F) | ((x >> 12) & ~0xF0F);
+    }
+};
+
+struct ColorTypeFilter_8 {
+    typedef uint8_t Type;
+    static unsigned Expand(unsigned x) {
+        return x;
+    }
+    static uint8_t Compact(unsigned x) {
+        return (uint8_t)x;
+    }
+};
+
+template <typename T> T add_121(T a, T b, T c) {
+    return a + b + b + c;
+}
+
+//
+//  To produce each mip level, we need to filter down by 1/2 (e.g. 100x100 -> 50,50)
+//  If the starting dimension is odd, we floor the size of the lower level (e.g. 101 -> 50)
+//  In those (odd) cases, we use a triangle filter, with 1-pixel overlap between samplings,
+//  else for even cases, we just use a 2x box filter.
+//
+//  This produces 4 possible filters: 2x2 2x3 3x2 3x3 where WxH indicates the number of src pixels
+//  we need to sample in each dimension to produce 1 dst pixel.
+//
+
+template <typename F> void downsample_2x2(void* dst, const void* src, size_t srcRB) {
+    auto p0 = static_cast<const typename F::Type*>(src);
+    auto p1 = (const typename F::Type*)((const char*)p0 + srcRB);
+
+    auto c00 = F::Expand(p0[0]);
+    auto c10 = F::Expand(p0[1]);

[mtklein, 2016/01/15 20:11:22]

Is it just me or would these read more easily as

...
auto c01 = F::Expand(p0[1]);
auto c10 = F::Expand(p1[0]);
...

i.e. make cXY names match pX[Y] (in all 4 functions).

[reed1, 2016/01/15 20:58:16]

Done.

+    auto c01 = F::Expand(p1[0]);
+    auto c11 = F::Expand(p1[1]);
+
+    auto c = c00 + c10 + c01 + c11;
+    *(typename F::Type*)dst = F::Compact(c >> 2);
+}
+
+template <typename F> void downsample_3x2(void* dst, const void* src, size_t srcRB) {
+    auto p0 = static_cast<const typename F::Type*>(src);
+    auto p1 = (const typename F::Type*)((const char*)p0 + srcRB);
+
+    auto c00 = F::Expand(p0[0]);
+    auto c10 = F::Expand(p0[1]);
+    auto c20 = F::Expand(p0[2]);
+    auto c01 = F::Expand(p1[0]);
+    auto c11 = F::Expand(p1[1]);
+    auto c21 = F::Expand(p1[2]);
+
+    auto c = add_121(c00, c10, c20) + add_121(c01, c11, c21);
+    *(typename F::Type*)dst = F::Compact(c >> 3);
+}
+
+template <typename F> void downsample_2x3(void* dst, const void* src, size_t srcRB) {
+    auto p0 = static_cast<const typename F::Type*>(src);
+    auto p1 = (const typename F::Type*)((const char*)p0 + srcRB);
+    auto p2 = (const typename F::Type*)((const char*)p1 + srcRB);
+
+    auto c00 = F::Expand(p0[0]);
+    auto c10 = F::Expand(p0[1]);
+    auto c01 = F::Expand(p1[0]);
+    auto c11 = F::Expand(p1[1]);
+    auto c02 = F::Expand(p2[0]);
+    auto c12 = F::Expand(p2[1]);
+    auto c = add_121(c00, c01, c02) + add_121(c10, c11, c12);
+    *(uint32_t*)dst = F::Compact(c >> 3);

[mtklein, 2016/01/15 20:11:22]

typename F::Type*

[reed1, 2016/01/15 20:58:16]

Done.

+}
+
+template <typename F> void downsample_3x3(void* dst, const void* src, size_t srcRB) {
+    auto p0 = static_cast<const typename F::Type*>(src);
+    auto p1 = (const typename F::Type*)((const char*)p0 + srcRB);
+    auto p2 = (const typename F::Type*)((const char*)p1 + srcRB);
+
+    auto c00 = F::Expand(p0[0]);
+    auto c10 = F::Expand(p0[1]);
+    auto c20 = F::Expand(p0[2]);
+    auto c01 = F::Expand(p1[0]);
+    auto c11 = F::Expand(p1[1]);
+    auto c21 = F::Expand(p1[2]);
+    auto c02 = F::Expand(p2[0]);
+    auto c12 = F::Expand(p2[1]);
+    auto c22 = F::Expand(p2[2]);
+
+    auto c = add_121(c00, c10, c20) + (add_121(c01, c11, c21) << 1) + add_121(c02, c12, c22);
+    *(typename F::Type*)dst = F::Compact(c >> 4);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+size_t SkMipMap::AllocLevelsSize(int levelCount, size_t pixelSize) {
+    if (levelCount < 0) {
+        return 0;
+    }
+    int64_t size = sk_64_mul(levelCount + 1, sizeof(Level)) + pixelSize;
+    if (!sk_64_isS32(size)) {
+        return 0;
+    }
+    return sk_64_asS32(size);
+}
+
+typedef void SkDownSampleProc(void*, const void* srcPtr, size_t srcRB);
+
+SkMipMap* SkMipMap::Build(const SkBitmap& src, SkDiscardableFactoryProc fact) {
+    SkDownSampleProc* proc2x2 = nullptr;

[mtklein, 2016/01/15 20:11:22]

Can you just move your typedef inside the function and call it Proc?

[reed1, 2016/01/15 20:58:16]

Done.

+    SkDownSampleProc* proc2x3 = nullptr;
+    SkDownSampleProc* proc3x2 = nullptr;
+    SkDownSampleProc* proc3x3 = nullptr;
+
+    const SkColorType ct = src.colorType();
+    const SkAlphaType at = src.alphaType();
+    switch (ct) {
+        case kRGBA_8888_SkColorType:
+        case kBGRA_8888_SkColorType:
+            proc2x2 = downsample_2x2<ColorTypeFilter_8888>;

[mtklein, 2016/01/15 20:11:22]

This may seem anal, but I think this section of code would be easier to read if
the procs were named

  proc22
  proc23
  proc32
  proc33

the xs keep tripping me up when reading

[reed1, 2016/01/15 20:58:16]

Hmmm, not sure about this one. I guess its ok either way, but we'd lose the "x"
in both the variable and the function name.

    proc32 = downsample_32

Not sure that won't make someone think we're talking about 32bits as opposed to
3x2 as dimensions.

Will try proc_3_2

+            proc2x3 = downsample_2x3<ColorTypeFilter_8888>;
+            proc3x2 = downsample_3x2<ColorTypeFilter_8888>;
+            proc3x3 = downsample_3x3<ColorTypeFilter_8888>;
+            break;
+        case kRGB_565_SkColorType:
+            proc2x2 = downsample_2x2<ColorTypeFilter_565>;
+            proc2x3 = downsample_2x3<ColorTypeFilter_565>;
+            proc3x2 = downsample_3x2<ColorTypeFilter_565>;
+            proc3x3 = downsample_3x3<ColorTypeFilter_565>;
+            break;
+        case kARGB_4444_SkColorType:
+            proc2x2 = downsample_2x2<ColorTypeFilter_4444>;
+            proc2x3 = downsample_2x3<ColorTypeFilter_4444>;
+            proc3x2 = downsample_3x2<ColorTypeFilter_4444>;
+            proc3x3 = downsample_3x3<ColorTypeFilter_4444>;
+            break;
+        case kAlpha_8_SkColorType:
+        case kGray_8_SkColorType:
+            proc2x2 = downsample_2x2<ColorTypeFilter_8>;
+            proc2x3 = downsample_2x3<ColorTypeFilter_8>;
+            proc3x2 = downsample_3x2<ColorTypeFilter_8>;
+            proc3x3 = downsample_3x3<ColorTypeFilter_8>;
+            break;
+        default:
+            // TODO: We could build miplevels for kIndex8 if the levels were in 8888.
+            //       Means using more ram, but the quality would be fine.
+            return nullptr;
+    }
+
+    // whip through our loop to compute the exact size needed
+    size_t  size = 0;
+    int     countLevels = 0;
+    {
+        int width = src.width();
+        int height = src.height();
+        for (;;) {
+            width >>= 1;
+            height >>= 1;
+            if (0 == width || 0 == height) {
+                break;
+            }
+            size += SkColorTypeMinRowBytes(ct, width) * height;
+            countLevels += 1;
+        }
+    }
+    if (0 == countLevels) {
+        return nullptr;
+    }
+
+    size_t storageSize = SkMipMap::AllocLevelsSize(countLevels, size);
+    if (0 == storageSize) {
+        return nullptr;
+    }
+
+    SkAutoPixmapUnlock srcUnlocker;
+    if (!src.requestLock(&srcUnlocker)) {
+        return nullptr;
+    }
+    const SkPixmap& srcPixmap = srcUnlocker.pixmap();
+    // Try to catch where we might have returned nullptr for src crbug.com/492818
+    if (nullptr == srcPixmap.addr()) {
+        sk_throw();
+    }
+
+    SkMipMap* mipmap;
+    if (fact) {
+        SkDiscardableMemory* dm = fact(storageSize);
+        if (nullptr == dm) {
+            return nullptr;
+        }
+        mipmap = new SkMipMap(storageSize, dm);
+    } else {
+        mipmap = new SkMipMap(sk_malloc_throw(storageSize), storageSize);
+    }
+
+    // init
+    mipmap->fCount = countLevels;
+    mipmap->fLevels = (Level*)mipmap->writable_data();
+
+    Level* levels = mipmap->fLevels;
+    uint8_t*    baseAddr = (uint8_t*)&levels[countLevels];
+    uint8_t*    addr = baseAddr;
+    int         width = src.width();
+    int         height = src.height();
+    uint32_t    rowBytes;
+    SkPixmap    srcPM(srcPixmap);
+
+    int prevW = width;
+    int prevH = height;
+    for (int i = 0; i < countLevels; ++i) {
+        width >>= 1;
+        height >>= 1;
+        rowBytes = SkToU32(SkColorTypeMinRowBytes(ct, width));
+
+        levels[i].fPixels   = addr;
+        levels[i].fWidth    = width;
+        levels[i].fHeight   = height;
+        levels[i].fRowBytes = rowBytes;
+        levels[i].fScale    = (float)width / src.width();
+
+        SkPixmap dstPM(SkImageInfo::Make(width, height, ct, at), addr, rowBytes);
+
+        const size_t pixelSize = srcPM.info().bytesPerPixel();
+
+        const void* srcBasePtr = srcPM.addr();
+        void* dstBasePtr = dstPM.writable_addr();
+
+        SkDownSampleProc* proc;
+        if (prevH & 1) {        // src-height is 3
+            if (prevW & 1) {    // src-width is 3
+                proc = proc3x3;
+            } else {            // src-width is 2
+                proc = proc2x3;
+            }
+        } else {                // src-height is 2
+            if (prevW & 1) {    // src-width is 3
+                proc = proc3x2;
+            } else {            // src-width is 2
+                proc = proc2x2;
+            }
+        }
+
+        const size_t srcRB = srcPM.rowBytes();
+        for (int y = 0; y < height; y++) {
+            const void* srcPtr = srcBasePtr;
+            void* dstPtr = dstBasePtr;
+
+            for (int x = 0; x < width; x++) {
+                proc(dstPtr, srcPtr, srcRB);
+                srcPtr = (char*)srcPtr + pixelSize * 2;
+                dstPtr = (char*)dstPtr + pixelSize;
+            }
+
+            srcBasePtr = (char*)srcBasePtr + srcRB * 2; // jump two rows
+            dstBasePtr = (char*)dstBasePtr + dstPM.rowBytes();
+        }
+        srcPM = dstPM;
+        addr += height * rowBytes;
+        prevW = width;
+        prevH = height;
+    }
+    SkASSERT(addr == baseAddr + size);
 
     return mipmap;
 }
+#endif
 
 ///////////////////////////////////////////////////////////////////////////////