Implement the y-transpose optimization in image (RGBA) blurs. This gives ~38% performance improvem…

src/effects/SkBlurImageFilter.cpp

 /*
  * Copyright 2011 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkBitmap.h"
 #include "SkBlurImageFilter.h"
 #include "SkColorPriv.h"
@@ skipping 21 matching lines @@
     : INHERITED(input, cropRect), fSigma(SkSize::Make(sigmaX, sigmaY)) {
     SkASSERT(sigmaX >= 0 && sigmaY >= 0);
 }
 
 void SkBlurImageFilter::flatten(SkFlattenableWriteBuffer& buffer) const {
     this->INHERITED::flatten(buffer);
     buffer.writeScalar(fSigma.fWidth);
     buffer.writeScalar(fSigma.fHeight);
 }
 
-static void boxBlurX(const SkBitmap& src, SkBitmap* dst, int kernelSize,
-                     int leftOffset, int rightOffset, const SkIRect& bounds)
+enum BlurDirection {
+    kX, kY
+};
+

[mtklein, 2013/11/06 13:51:52]

Maybe add a nice big block comment here with some ASCII art?  Every time I look
at the mask blur code that does this my brain goes all inside out.  I sort of
always go through the same questions, "Wait, you can really walk in different
directions?", "how does it all line up?", etc.  It's somewhat surprising you can
do this at all.  (A link to an external description of this trick would be just
fine by me too... no need to rehash this if it's a commonly known trick.)

[Stephen White, 2013/11/06 15:09:59]

Done.

+template<BlurDirection srcDirection, BlurDirection dstDirection>
+static void boxBlur(const SkPMColor* src, int srcStride, SkPMColor* dst, int kernelSize,
+                    int leftOffset, int rightOffset, int width, int height)
 {
-    int width = bounds.width(), height = bounds.height();
     int rightBorder = SkMin32(rightOffset + 1, width);
+    int srcStrideX = srcDirection == kX ? 1 : srcStride;
+    int dstStrideX = dstDirection == kX ? 1 : height;
+    int srcStrideY = srcDirection == kX ? srcStride : 1;
+    int dstStrideY = dstDirection == kX ? width : 1;
 #ifndef SK_DISABLE_BLUR_DIVISION_OPTIMIZATION
     uint32_t scale = (1 << 24) / kernelSize;
     uint32_t half = 1 << 23;
 #endif
     for (int y = 0; y < height; ++y) {
         int sumA = 0, sumR = 0, sumG = 0, sumB = 0;
-        SkPMColor* p = src.getAddr32(bounds.fLeft, y + bounds.fTop);
+        const SkPMColor* p = src;
         for (int i = 0; i < rightBorder; ++i) {
             sumA += SkGetPackedA32(*p);
             sumR += SkGetPackedR32(*p);
             sumG += SkGetPackedG32(*p);
             sumB += SkGetPackedB32(*p);
-            p++;
+            p += srcStrideX;
         }
 
-        const SkColor* sptr = src.getAddr32(bounds.fLeft, bounds.fTop + y);
-        SkColor* dptr = dst->getAddr32(0, y);
+        const SkPMColor* sptr = src;
+        SkColor* dptr = dst;
         for (int x = 0; x < width; ++x) {
 #ifndef SK_DISABLE_BLUR_DIVISION_OPTIMIZATION
             *dptr = SkPackARGB32((sumA * scale + half) >> 24,
                                  (sumR * scale + half) >> 24,
                                  (sumG * scale + half) >> 24,
                                  (sumB * scale + half) >> 24);
 #else
             *dptr = SkPackARGB32(sumA / kernelSize,
                                  sumR / kernelSize,
                                  sumG / kernelSize,
                                  sumB / kernelSize);
 #endif
             if (x >= leftOffset) {
-                SkColor l = *(sptr - leftOffset);
+                SkColor l = *(sptr - leftOffset * srcStrideX);
                 sumA -= SkGetPackedA32(l);
                 sumR -= SkGetPackedR32(l);
                 sumG -= SkGetPackedG32(l);
                 sumB -= SkGetPackedB32(l);
             }
             if (x + rightOffset + 1 < width) {
-                SkColor r = *(sptr + rightOffset + 1);
+                SkColor r = *(sptr + (rightOffset + 1) * srcStrideX);
                 sumA += SkGetPackedA32(r);
                 sumR += SkGetPackedR32(r);
                 sumG += SkGetPackedG32(r);
                 sumB += SkGetPackedB32(r);
             }
-            sptr++;
-            dptr++;
+            sptr += srcStrideX;
+            if (srcDirection == kY) {

[mtklein, 2013/11/06 13:51:52]

Should be fine to remove this prefetch entirely now?  It'll only be triggered in
the old code paths.

[Stephen White, 2013/11/06 15:09:59]

Actually, it'll still be used in the Y-only path (when kernelSizeX is 0, below).
So I think we should leave it in.

Although another thing we could try is breaking out each of the if-tests above
into separate loops, as is done in the mask blurs. Then the hardware prefetchers
might work better.

+                SK_PREFETCH(sptr + (rightOffset + 1) * srcStrideX);
+            }
+            dptr += dstStrideX;
         }
+        src += srcStrideY;
+        dst += dstStrideY;
     }
 }
 
-static void boxBlurY(const SkBitmap& src, SkBitmap* dst, int kernelSize,
-                     int topOffset, int bottomOffset, const SkIRect& bounds)
+static void boxBlurX(const SkPMColor* src, int srcStride, SkPMColor* dst, int kernelSize,

[mtklein, 2013/11/06 13:51:52]

These are going to want to get renames, eh?  X seems a bit overloaded.  boxBlur
and boxBlurTransposed for XY?

[Stephen White, 2013/11/06 15:09:59]

We'll still need boxBlurY(), and boxBlurTransposed() makes it hard to line up
the parameters in all the calls below. :) How about boxBlurXX, boxBlurXY,
boxBlurYY?

(I'd also like to try reordering the Y-only passes into YX, XX, XY, for which
I'll need boxBlurYX).

[mtklein, 2013/11/06 15:18:56]

Maybe just get rid of these intermediates and call boxBlur<Src,Dst> directly?

+                     int leftOffset, int rightOffset, int width, int height)
 {
-    int width = bounds.width(), height = bounds.height();
-    int bottomBorder = SkMin32(bottomOffset + 1, height);
-    int srcStride = src.rowBytesAsPixels();
-    int dstStride = dst->rowBytesAsPixels();
+    boxBlur<kX, kX>(src, srcStride, dst, kernelSize, leftOffset, rightOffset, width, height);
+}
+
 #ifndef SK_DISABLE_BLUR_DIVISION_OPTIMIZATION
-    uint32_t scale = (1 << 24) / kernelSize;
-    uint32_t half = 1 << 23;
+static void boxBlurXY(const SkPMColor* src, int srcStride, SkPMColor* dst, int kernelSize,
+                              int leftOffset, int rightOffset, int width, int height)
+{
+    boxBlur<kX, kY>(src, srcStride, dst, kernelSize, leftOffset, rightOffset, width, height);
+}
 #endif
-    for (int x = 0; x < width; ++x) {
-        int sumA = 0, sumR = 0, sumG = 0, sumB = 0;
-        SkColor* p = src.getAddr32(bounds.fLeft + x, bounds.fTop);
-        for (int i = 0; i < bottomBorder; ++i) {
-            sumA += SkGetPackedA32(*p);
-            sumR += SkGetPackedR32(*p);
-            sumG += SkGetPackedG32(*p);
-            sumB += SkGetPackedB32(*p);
-            p += srcStride;
-        }
 
-        const SkColor* sptr = src.getAddr32(bounds.fLeft + x, bounds.fTop);
-        SkColor* dptr = dst->getAddr32(x, 0);
-        for (int y = 0; y < height; ++y) {
-#ifndef SK_DISABLE_BLUR_DIVISION_OPTIMIZATION
-            *dptr = SkPackARGB32((sumA * scale + half) >> 24,
-                                 (sumR * scale + half) >> 24,
-                                 (sumG * scale + half) >> 24,
-                                 (sumB * scale + half) >> 24);
-#else
-            *dptr = SkPackARGB32(sumA / kernelSize,
-                                 sumR / kernelSize,
-                                 sumG / kernelSize,
-                                 sumB / kernelSize);
-#endif
-            if (y >= topOffset) {
-                SkColor l = *(sptr - topOffset * srcStride);
-                sumA -= SkGetPackedA32(l);
-                sumR -= SkGetPackedR32(l);
-                sumG -= SkGetPackedG32(l);
-                sumB -= SkGetPackedB32(l);
-            }
-            if (y + bottomOffset + 1 < height) {
-                SkColor r = *(sptr + (bottomOffset + 1) * srcStride);
-                sumA += SkGetPackedA32(r);
-                sumR += SkGetPackedR32(r);
-                sumG += SkGetPackedG32(r);
-                sumB += SkGetPackedB32(r);
-            }
-            sptr += srcStride;
-            // The next leading pixel seems to be too hard to predict.  Hint the fetch.
-            SK_PREFETCH(sptr + (bottomOffset + 1) * srcStride);
-            dptr += dstStride;
-        }
-    }
+static void boxBlurY(const SkPMColor* src, int srcStride, SkPMColor* dst, int kernelSize,
+                     int topOffset, int bottomOffset, int width, int height)
+{
+    boxBlur<kY, kY>(src, srcStride, dst, kernelSize, topOffset, bottomOffset, width, height);
 }
 
 static void getBox3Params(SkScalar s, int *kernelSize, int* kernelSize3, int *lowOffset,
                           int *highOffset)
 {
     float pi = SkScalarToFloat(SK_ScalarPI);
     int d = static_cast<int>(floorf(SkScalarToFloat(s) * 3.0f * sqrtf(2.0f * pi) / 4.0f + 0.5f));
     *kernelSize = d;
     if (d % 2 == 1) {
         *lowOffset = *highOffset = (d - 1) / 2;
@@ skipping 44 matching lines @@
         src.copyTo(dst, dst->config());
         return true;
     }
 
     SkBitmap temp;
     temp.setConfig(dst->config(), dst->width(), dst->height());
     if (!temp.allocPixels()) {
         return false;
     }
 
+    const SkPMColor* s = src.getAddr32(srcBounds.left(), srcBounds.top());
+    SkPMColor* t = temp.getAddr32(0, 0);
+    SkPMColor* d = dst->getAddr32(0, 0);
+    int w = dstBounds.width(), h = dstBounds.height();
+    int sw = src.rowBytesAsPixels();
     if (kernelSizeX > 0 && kernelSizeY > 0) {
-        boxBlurX(src,  &temp, kernelSizeX,  lowOffsetX,  highOffsetX, srcBounds);
-        boxBlurY(temp, dst,   kernelSizeY,  lowOffsetY,  highOffsetY, dstBounds);
-        boxBlurX(*dst, &temp, kernelSizeX,  highOffsetX, lowOffsetX, dstBounds);
-        boxBlurY(temp, dst,   kernelSizeY,  highOffsetY, lowOffsetY, dstBounds);
-        boxBlurX(*dst, &temp, kernelSizeX3, highOffsetX, highOffsetX, dstBounds);
-        boxBlurY(temp, dst,   kernelSizeY3, highOffsetY, highOffsetY, dstBounds);
+#ifndef SK_DISABLE_BLUR_DIVISION_OPTIMIZATION
+        boxBlurX(s,  sw, t, kernelSizeX,  lowOffsetX,  highOffsetX, w, h);
+        boxBlurX(t,  w,  d, kernelSizeX,  highOffsetX, lowOffsetX,  w, h);
+        boxBlurXY(d, w,  t, kernelSizeX3, highOffsetX, highOffsetX, w, h);
+        boxBlurX(t,  h,  d, kernelSizeY,  lowOffsetY,  highOffsetY, h, w);
+        boxBlurX(d,  h,  t, kernelSizeY,  highOffsetY, lowOffsetY,  h, w);
+        boxBlurXY(t, h,  d, kernelSizeY3, highOffsetY, highOffsetY, h, w);
+#else
+        boxBlurX(s,  sw, t, kernelSizeX,  lowOffsetX,  highOffsetX, w, h);
+        boxBlurY(t,  w,  d, kernelSizeY,  lowOffsetY,  highOffsetY, h, w);
+        boxBlurX(d,  w,  t, kernelSizeX,  highOffsetX, lowOffsetX,  w, h);
+        boxBlurY(t,  w,  d, kernelSizeY,  highOffsetY, lowOffsetY,  h, w);
+        boxBlurX(d,  w,  t, kernelSizeX3, highOffsetX, highOffsetX, w, h);
+        boxBlurY(t,  w,  d, kernelSizeY3, highOffsetY, highOffsetY, h, w);
+#endif
     } else if (kernelSizeX > 0) {
-        boxBlurX(src,  dst,   kernelSizeX,  lowOffsetX,  highOffsetX, srcBounds);
-        boxBlurX(*dst, &temp, kernelSizeX,  highOffsetX, lowOffsetX, dstBounds);
-        boxBlurX(temp, dst,   kernelSizeX3, highOffsetX, highOffsetX, dstBounds);
+        boxBlurX(s,  sw, d, kernelSizeX,  lowOffsetX,  highOffsetX, w, h);
+        boxBlurX(d,  w,  t, kernelSizeX,  highOffsetX, lowOffsetX,  w, h);
+        boxBlurX(t,  w,  d, kernelSizeX3, highOffsetX, highOffsetX, w, h);
     } else if (kernelSizeY > 0) {
-        boxBlurY(src,  dst,   kernelSizeY,  lowOffsetY,  highOffsetY, srcBounds);
-        boxBlurY(*dst, &temp, kernelSizeY,  highOffsetY, lowOffsetY, dstBounds);
-        boxBlurY(temp, dst,   kernelSizeY3, highOffsetY, highOffsetY, dstBounds);
+        boxBlurY(s,  sw, d, kernelSizeY,  lowOffsetY,  highOffsetY, h, w);
+        boxBlurY(d,  w,  t, kernelSizeY,  highOffsetY, lowOffsetY,  h, w);
+        boxBlurY(t,  w,  d, kernelSizeY3, highOffsetY, highOffsetY, h, w);
     }
     offset->fX += srcBounds.fLeft;
     offset->fY += srcBounds.fTop;
     return true;
 }
 
 bool SkBlurImageFilter::filterImageGPU(Proxy* proxy, const SkBitmap& src, const SkMatrix& ctm,
                                        SkBitmap* result, SkIPoint* offset) {
 #if SK_SUPPORT_GPU
     SkBitmap input;
@@ skipping 14 matching lines @@
                                                              fSigma.width(),
                                                              fSigma.height()));
     offset->fX += rect.fLeft;
     offset->fY += rect.fTop;
     return SkImageFilterUtils::WrapTexture(tex, rect.width(), rect.height(), result);
 #else
     SkDEBUGFAIL("Should not call in GPU-less build");
     return false;
 #endif
 }