SSE2 implementation of RGBA box blurs. This yields ~2X perf improvement on

src/opts/SkBlurImage_opts_SSE2.cpp

Index: src/opts/SkBlurImage_opts_SSE2.cpp
diff --git a/src/opts/SkBlurImage_opts_SSE2.cpp b/src/opts/SkBlurImage_opts_SSE2.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..ed335183c2ab352bdced77523f96420056c05da1
--- /dev/null
+++ b/src/opts/SkBlurImage_opts_SSE2.cpp
@@ -0,0 +1,88 @@
+/*
+ * Copyright 2013 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 "SkColorPriv.h"
+#include "SkBlurImage_opts_SSE2.h"
+#include "SkRect.h"
+
+#include <emmintrin.h>
+
+enum BlurDirection {

[mtklein, 2013/11/08 18:42:34]

namespace {} around the enum and template?

[Stephen White, 2013/11/08 20:20:49]

Done.

+    kX, kY
+};
+
+template<BlurDirection srcDirection, BlurDirection dstDirection>
+void SkBoxBlur_SSE2(const SkPMColor* src, int srcStride, SkPMColor* dst, int kernelSize,
+                         int leftOffset, int rightOffset, int width, int height)

[mtklein, 2013/11/08 18:42:34]

funky indent

[Stephen White, 2013/11/08 20:20:49]

Fixed.

+{
+    int rightBorder = SkMin32(rightOffset + 1, width);

[mtklein, 2013/11/08 18:42:34]

in the interest of readability, can you sprinkle const all over this wherever
possible?  there are enough variables to keep track of here that it's not always
obvious what's moving when reading.

[Stephen White, 2013/11/08 20:20:49]

I usually find it's just noise, but ok. Done.

+    int srcStrideX = srcDirection == kX ? 1 : srcStride;
+    int dstStrideX = dstDirection == kX ? 1 : height;
+    int srcStrideY = srcDirection == kX ? srcStride : 1;
+    int dstStrideY = dstDirection == kX ? width : 1;
+    __m128i scale = _mm_set1_epi32((1 << 24) / kernelSize);

[mtklein, 2013/11/08 18:42:34]

If I'm thinking right, this is the limiting factor in how many pixels we can
handle at a time.  An alternative is to load up two (or four) pixels at once and
use a divide, right?  Any sense of how that'd compare?  I'm guessing, speed
faster but code much grungier?

[Stephen White, 2013/11/08 20:20:49]

There is no integer divide in SSE2.

You're right that loading more than a pixel is usually a win (see SkBlitRow_SSE2
where I load 4 src pixels into an aligned SSE reg at a time). The problem here
is that the sums here are inter-pixel, and SSE2 has no horizontal adds. SSSE3 or
SSE4.1 does (can't remember which), but they're still not very fast. We'd also
have to do a lot of tricky setup and teardown code to handle the slop.

We could definitely look at it in a future patch, but I'd prefer to go with this
for now.

[mtklein, 2013/11/08 20:37:35]

Duh.  SGTM

+    __m128i half = _mm_set1_epi32(1 << 23);
+    __m128i zero = _mm_setzero_si128();
+    for (int y = 0; y < height; ++y) {
+        __m128i sum = zero;
+        const SkPMColor* p = src;
+        for (int i = 0; i < rightBorder; ++i) {
+            __m128i expanded = _mm_cvtsi32_si128(*p);
+            expanded = _mm_unpacklo_epi8(expanded, zero);

[mtklein, 2013/11/08 18:42:34]

Can you narrate a little for folks who don't speak SSE?  E.g, for this block,
something like  // 0000 0000 0000 ARGB  -> 000A 000R 000G 000B would be plenty. 
(Have I got that right?)  This (and its inverse) might make nice little inline
functions.

[Stephen White, 2013/11/08 20:20:49]

Done.

+            expanded = _mm_unpacklo_epi16(expanded, zero);
+            sum = _mm_add_epi32(sum, expanded);
+            p += srcStrideX;
+        }
+
+        const SkPMColor* sptr = src;
+        SkColor* dptr = dst;
+        for (int x = 0; x < width; ++x) {
+            __m128i tmp1 = _mm_mul_epu32(sum, scale);

[mtklein, 2013/11/08 18:42:34]

So, I'd following along right there with you if this said something like

// (sum * scale + half) >> 24 to do (sum / kernelSize) without a divide.
_m128i average = _mm_srli_epi32(_mm_add_epi32(_mm_mul_epu32(sum, scale), half),
24);

How do tmp2 and the shuffles figure into it?

[Stephen White, 2013/11/08 20:20:49]

Those 7 instructions are an unfortunate side-effect of the fact that SSE2 has no
equivalent of C-style overflowing multiply, only a 32-to-64-bit
(non-overflowing). I'll add a comment.

+            __m128i tmp2 = _mm_mul_epu32(_mm_srli_si128(sum, 4),
+                                         _mm_srli_si128(scale, 4));
+            __m128i result = _mm_unpacklo_epi32(_mm_shuffle_epi32(tmp1, _MM_SHUFFLE(0,0,2,0)),
+                                                _mm_shuffle_epi32(tmp2, _MM_SHUFFLE(0,0,2,0)));
+            result = _mm_add_epi32(result, half);
+            result = _mm_srli_epi32(result, 24);
+            result = _mm_packs_epi32(result, zero);

[mtklein, 2013/11/08 18:42:34]

These two lines are // 000A 000R 000G 000B -> 0000 0000 0000 ARGB, right?

[Stephen White, 2013/11/08 20:20:49]

Yep, comment added.

+            result = _mm_packus_epi16(result, zero);
+            *dptr = _mm_cvtsi128_si32(result);
+            if (x >= leftOffset) {
+                SkColor l = *(sptr - leftOffset * srcStrideX);
+                __m128i expanded = _mm_cvtsi32_si128(l);
+                expanded = _mm_unpacklo_epi8(expanded, zero);
+                expanded = _mm_unpacklo_epi16(expanded, zero);
+                sum = _mm_sub_epi32(sum, expanded);
+            }
+            if (x + rightOffset + 1 < width) {
+                SkColor r = *(sptr + (rightOffset + 1) * srcStrideX);
+                __m128i expanded = _mm_cvtsi32_si128(r);
+                expanded = _mm_unpacklo_epi8(expanded, zero);
+                expanded = _mm_unpacklo_epi16(expanded, zero);
+                sum = _mm_add_epi32(sum, expanded);
+            }
+            sptr += srcStrideX;
+            if (srcDirection == kY) {
+                _mm_prefetch(reinterpret_cast<const char*>(sptr + (rightOffset + 1) * srcStrideX), _MM_HINT_T0);

[mtklein, 2013/11/08 18:42:34]

linebreak after the ,?

[Stephen White, 2013/11/08 20:20:49]

Done.

+            }
+            dptr += dstStrideX;
+        }
+        src += srcStrideY;
+        dst += dstStrideY;
+    }
+}
+
+bool SkBoxBlurGetPlatformProcs_SSE2(SkBoxBlurProc* boxBlurX,
+                                    SkBoxBlurProc* boxBlurY,
+                                    SkBoxBlurProc* boxBlurXY) {
+    *boxBlurX = SkBoxBlur_SSE2<kX, kX>;
+    *boxBlurY = SkBoxBlur_SSE2<kY, kY>;
+    *boxBlurXY = SkBoxBlur_SSE2<kX, kY>;
+    return true;
+}