Add SSE optimization of Color32A_D565

src/opts/SkBlitRow_opts_SSE4.cpp

Index: src/opts/SkBlitRow_opts_SSE4.cpp
diff --git a/src/opts/SkBlitRow_opts_SSE4.cpp b/src/opts/SkBlitRow_opts_SSE4.cpp
index ae92a77eb2d234ba9bf5a7d816b860f469b022e9..bc9a6d394482372127f13b1f561302165c2b0b61 100644
--- a/src/opts/SkBlitRow_opts_SSE4.cpp
+++ b/src/opts/SkBlitRow_opts_SSE4.cpp
@@ -7,6 +7,10 @@ void S32A_Opaque_BlitRow32_SSE4(SkPMColor* SK_RESTRICT, const SkPMColor* SK_REST
     sk_throw();
 }
 
+void Color32A_D565_SSE4(uint16_t dst[], SkPMColor src, int count, int x, int y) {
+    sk_throw();
+}
+
 #else
 
 #include <emmintrin.h>  // SSE2:   Most _mm_foo() in this file.
@@ -64,4 +68,112 @@ void S32A_Opaque_BlitRow32_SSE4(SkPMColor* SK_RESTRICT dst,
     }
 }
 
+void Color32A_D565_SSE4(uint16_t dst[], SkPMColor src, int count, int x, int y) {
+    SkASSERT(count > 0);
+    // dst must be 2-byte aligned.
+    SkASSERT((((size_t)dst) & 0x01) == 0);

[mtklein, 2015/01/30 18:17:37]

Seems paranoid?  If we need to keep this, let's write it as

SkASSERT(SkIsAlign2((uintptr_t)dst));

[henrik.smiding, 2015/02/10 15:11:51]

I thought so too, but I actually found it in the new Color32A_D565_neon
function.
Will remove it.

+
+    uint32_t src_expand = (SkGetPackedG32(src) << 24) |
+                          (SkGetPackedR32(src) << 13) |
+                          (SkGetPackedB32(src) << 2);
+    unsigned scale = SkAlpha255To256(0xFF - SkGetPackedA32(src)) >> 3;
+
+    // Check if we have enough pixels to run SIMD, at all
+    if (count >= 8) {

[mtklein, 2015/01/30 18:17:37]

This logic seems complex, and I'm worried we're overfitting to the benchmarks or
machine we're using to test.

Why don't we start by stripping all the smarts away and just use unaligned
memory access?  We can watch perf.skia.org to see its performance impact across
a variety of machines, and then refine this if needed.

uint32_t src_expand = ...;
unsigned scale = ... ;

const __m128i src_expand_wide = ...;
const __m128i scale_wide = ...;
const __m128i mask_green = ...;

__m128i* dst_wide = (__m128i*)dst;
while (count >= 8) {
  __m128i pixels = _mm_loadu_si128(dst_wide);
  ...
  _mm_storeu_si128(dst_wide++, pixels);
}
while (count --> 0) {
  ...
}

[henrik.smiding, 2015/02/10 15:11:52]

I did this optimization based on reports that it was used heavily in Android WPS
Office application.

I actually added the unaligned loop at the last minute, to improve performance
of smaller widths (8-63 pixels).
I would prefer it if we kept the aligned loop, since aligned memory access is
still faster. Especially on Atom/Silvermont cores.

+        __m128i* dst_wide;
+        const __m128i src_expand_wide = _mm_set1_epi32(src_expand);
+        const __m128i scale_wide = _mm_set1_epi32(scale);
+        const __m128i mask_green = _mm_set1_epi32(SK_R16_MASK_IN_PLACE |
+                                                  SK_B16_MASK_IN_PLACE |
+                                                 (SK_G16_MASK_IN_PLACE << 16));
+
+        // Check if we should run the aligned SIMD loop
+        if ((count >= 64) || ((((size_t)dst) & 0x0F) == 0)) {

[mtklein, 2015/01/30 18:17:37]

How'd you pick 64?

[henrik.smiding, 2015/02/10 15:11:52]

I measured different widths with skia bench, using both aligned and unaligned
loops running on both aligned and unaligned start addresses. The sweet-spot for
the Silvermont core was somewhere between 64 and 96 pixels.
I will remove this 'magic number' in the next patch, along with the unaligned
loop.

+            // Align dst to an even 16 byte address (0-7 pixels)
+            while (((((size_t)dst) & 0x0F) != 0) && (count > 0)) {
+                uint32_t dst_expand = SkExpand_rgb_16(*dst) * scale;

[mtklein, 2015/01/30 18:17:37]

You've got a lot of repeated code here.  If it needs to stick around, which I
hope it doesn't, please factor the scalar and the 8x version out into their own
functions, e.g.

static void Color32A_D565_1x(uint16_t* dst, unsigned scale, uint32_t
src_expand);
static void Color32A_D565_8x(__m128i* dst, __m128i scale, __m128i src_expand);

I'm somewhat surprised we don't have that 1x variant extracted as its own method
in SkColorPriv.h already.  Might make sense to do so if we can peg down the
right name for it, then add the 8x variant to SkColor_opts_SSE2.h.

[henrik.smiding, 2015/02/10 15:11:51]

I'll re-factor the code a bit. When you're satisfied I'll check if it's possible
to move some of it to other files. Moving to header files as inline methods
should not affect performance at least.

+                *dst = SkCompact_rgb_16((src_expand + dst_expand) >> 5);
+                dst += 1;
+                count--;
+            }
+
+            dst_wide = reinterpret_cast<__m128i*>(dst);
+            do {
+                // Load 8 RGB565 pixels
+                __m128i pixels = _mm_load_si128(dst_wide);
+
+                // Duplicate and mask
+                __m128i pixels_high = _mm_unpackhi_epi16(pixels, pixels);
+                pixels_high = _mm_and_si128(mask_green, pixels_high);
+                pixels = _mm_unpacklo_epi16(pixels, pixels);
+                pixels = _mm_and_si128(mask_green, pixels);
+
+                // Scale with alpha
+                pixels_high = _mm_mullo_epi32(pixels_high, scale_wide);

[mtklein, 2015/01/30 18:17:37]

It doesn't seem like SSE4 is essential to the speed of this code.  Am I thinking
right it's just _mm_mullo_epi32 forcing us to do this in >=SSE4.1, and
_mm_hadd_epi16 forcing us to do it in >=SSSE3?  It seems like a shame to not
implement this as an _SSE2.cpp optimization instead, and then come back with an
SSSE3 or SSE4 variant only if they're really that much faster than the SSE2
code.  The bulk of our x86 users do have SSE2, but not SSSE3 or SSE4.

[henrik.smiding, 2015/02/10 15:11:51]

I added the _mm_hadd instruction at the last minute, replacing something like
seven instructions. It made the code shorter and clearer, but since hadd is
using micro-code, it didn't give that much on the performance side (on a
Silvermont that is).

_mm_mullo_epi32 is the only instruction that makes four 32-bit multiplications
in one go. 
The only other instruction that does 32-bit multiplications in SSE2, only does
two, requiring two calls to slow mul-instructions, and some shuffling/shifting
on top of that. Since the multiplication step is the only really 'heavy'
instruction in the loop, doubling it would impact performance. Also, not that
far from the C-code's 1 mul/pixel.

How do you know that most of your users only have SSE2? Do the majority of
people sit on 10+ year old computers? I recall that SSE4 is as old as the entire
ARMv7 architecture.

I'll push a new version of this patch, and then write and measure a SSE2-only
version. But I predict twice the code, and noticeable less performance (given
ideal memory pre-fetching). But if it's still faster than the C-code I'll push a
patch.

+                pixels = _mm_mullo_epi32(pixels, scale_wide);
+
+                // Add src_expand_wide and shift down again
+                pixels_high = _mm_add_epi32(pixels_high, src_expand_wide);
+                pixels_high = _mm_srli_epi32(pixels_high, 5);
+                pixels = _mm_add_epi32(pixels, src_expand_wide);
+                pixels = _mm_srli_epi32(pixels, 5);
+
+                // Mask
+                pixels_high = _mm_and_si128(mask_green, pixels_high);
+                pixels = _mm_and_si128(mask_green, pixels);
+
+                // Combine into RGB565 and store
+                pixels = _mm_hadd_epi16(pixels, pixels_high);
+                _mm_store_si128(dst_wide, pixels);
+                count -= 8;
+                dst_wide++;
+            } while (count >= 8);
+        }
+        else {  // Unaligned loop to handle medium widths
+            dst_wide = reinterpret_cast<__m128i*>(dst);
+
+            do {
+                // Load 8 RGB565 pixels
+                __m128i pixels = _mm_loadu_si128(dst_wide);
+
+                // Duplicate and mask
+                __m128i pixels_high = _mm_unpackhi_epi16(pixels, pixels);
+                pixels_high = _mm_and_si128(mask_green, pixels_high);
+                pixels = _mm_unpacklo_epi16(pixels, pixels);
+                pixels = _mm_and_si128(mask_green, pixels);
+
+                // Scale with alpha
+                pixels_high = _mm_mullo_epi32(pixels_high, scale_wide);
+                pixels = _mm_mullo_epi32(pixels, scale_wide);
+
+                // Add src_expand_wide and shift down again
+                pixels_high = _mm_add_epi32(pixels_high, src_expand_wide);
+                pixels_high = _mm_srli_epi32(pixels_high, 5);
+                pixels = _mm_add_epi32(pixels, src_expand_wide);
+                pixels = _mm_srli_epi32(pixels, 5);
+
+                // Mask
+                pixels_high = _mm_and_si128(mask_green, pixels_high);
+                pixels = _mm_and_si128(mask_green, pixels);
+
+                // Combine into RGB565 and store
+                pixels = _mm_hadd_epi16(pixels, pixels_high);
+                _mm_storeu_si128(dst_wide, pixels);
+                count -= 8;
+                dst_wide++;
+            } while (count >= 8);
+        }
+
+        dst = reinterpret_cast<uint16_t*>(dst_wide);
+    }
+
+    // Small loop to handle remaining 0-7 pixels.
+    while (count > 0) {
+        uint32_t dst_expand = SkExpand_rgb_16(*dst) * scale;
+        *dst = SkCompact_rgb_16((src_expand + dst_expand) >> 5);
+        dst += 1;
+        count--;
+    }
+}
+
 #endif