Re: Concerns about using filters for downscaling

From 8b8fd5ebc9899ff4985ff50c48ee2bf1ab75feea Mon Sep 17 00:00:00 2001
From: "Owen W. Taylor" <[email protected]>
Date: Mon, 24 Mar 2014 16:02:28 -0400
Subject: [PATCH] Add a SSE2 fast path for separable convolutions

Take the fast-path code for separable convolutions, and port it to
use SSE2 floating point math. A special case is added for when
the convolution is reading entirely within the un-repeated bounds
of the source image, and the per-source-pixel checks for 0
filter values are removed because they slowed down filters with
mostly non-zero values significantly.

The SSE2 conversion by itself only gave minimal speedups, because
the arithmetic was hidden by the rest of the complexity, but with
the tight inner loop, the overall speedup is a doubling.
---
 pixman/pixman-sse2.c | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 306 insertions(+), 2 deletions(-)

diff --git a/pixman/pixman-sse2.c b/pixman/pixman-sse2.c
index a6e7808..cbc16f5 100644
--- a/pixman/pixman-sse2.c
+++ b/pixman/pixman-sse2.c
@@ -6460,12 +6460,282 @@ sse2_fetch_a8 (pixman_iter_t *iter, const uint32_t *mask)
     return iter->buffer;
 }
 
+typedef uint32_t (* convert_pixel_t) (const uint8_t *row, int x);
+
+static void
+sse2_iter_fini_separable_convolution (pixman_iter_t *iter)
+{
+    free (iter->data);
+}
+
+static void
+sse2_iter_init_separable_convolution (pixman_iter_t            *iter,
+                                      const pixman_iter_info_t *info)
+{
+    pixman_fixed_t *params = iter->image->common.filter_params;
+    int n_params = iter->image->common.n_filter_params;
+    float *filter;
+    int i;
+
+    iter->data = malloc (sizeof (float) * (n_params - 4));
+    if (iter->data == NULL)
+	goto fail;
+
+    filter = (float *)iter->data;
+
+    for (i = 0; i < (n_params - 4); i++)
+	filter[i] = (float)params[i + 4] / 65536.;
+
+    iter->fini = sse2_iter_fini_separable_convolution;
+
+    return;
+
+fail:
+    /* In case of OOM, we don't guarantee any particular rendering.
+     */
+    _pixman_log_error (
+	FUNC, "Allocation failure, skipping rendering\n");
+
+    iter->get_scanline = _pixman_iter_get_scanline_noop;
+    iter->fini = NULL;
+}
+
+/* Expands a pixel packed into a 32-bit integer into 4 32-bit floats */
+static force_inline __m128
+expand_pixel_ps (uint32_t pixel)
+{
+    __m128i pixel_wide = _mm_cvtsi32_si128 (pixel);
+    __m128i pixel_unpacked = _mm_unpacklo_epi16 (_mm_unpacklo_epi8 (pixel_wide, _mm_setzero_si128 ()),
+                                                 _mm_setzero_si128 ());
+    return  _mm_cvtepi32_ps (pixel_unpacked);
+}
+
+static force_inline void
+sse2_fetch_separable_convolution_affine (pixman_image_t * image,
+                                         float           *filter,
+                                         int              offset,
+                                         int              line,
+                                         int              width,
+                                         uint32_t *       buffer,
+                                         const uint32_t * mask,
+
+                                         convert_pixel_t	convert_pixel,
+                                         pixman_format_code_t	format,
+                                         pixman_repeat_t	repeat_mode)
+{
+    __m128 one_half = _mm_set1_ps (0.5f);
+    bits_image_t *bits = &image->bits;
+    pixman_fixed_t *params = image->common.filter_params;
+    int cwidth = pixman_fixed_to_int (params[0]);
+    int cheight = pixman_fixed_to_int (params[1]);
+    int x_off = ((cwidth << 16) - pixman_fixed_1) >> 1;
+    int y_off = ((cheight << 16) - pixman_fixed_1) >> 1;
+    int x_phase_bits = pixman_fixed_to_int (params[2]);
+    int y_phase_bits = pixman_fixed_to_int (params[3]);
+    int x_phase_shift = 16 - x_phase_bits;
+    int y_phase_shift = 16 - y_phase_bits;
+    pixman_fixed_t vx, vy;
+    pixman_fixed_t ux, uy;
+    pixman_vector_t v;
+    int k;
+
+    /* reference point is the center of the pixel */
+    v.vector[0] = pixman_int_to_fixed (offset) + pixman_fixed_1 / 2;
+    v.vector[1] = pixman_int_to_fixed (line) + pixman_fixed_1 / 2;
+    v.vector[2] = pixman_fixed_1;
+
+    if (!pixman_transform_point_3d (image->common.transform, &v))
+	return;
+
+    ux = image->common.transform->matrix[0][0];
+    uy = image->common.transform->matrix[1][0];
+
+    vx = v.vector[0];
+    vy = v.vector[1];
+
+    for (k = 0; k < width; ++k)
+    {
+	float *y_filter;
+	__m128 stot;
+        __m64 tot_integer, tot_packed;
+	pixman_fixed_t x, y;
+	int32_t x1, x2, y1, y2;
+	int32_t px, py;
+	int i, j;
+
+	if (mask && !mask[k])
+	    goto next;
+
+	/* Round x and y to the middle of the closest phase before continuing. This
+	 * ensures that the convolution matrix is aligned right, since it was
+	 * positioned relative to a particular phase (and not relative to whatever
+	 * exact fraction we happen to get here).
+	 */
+	x = ((vx >> x_phase_shift) << x_phase_shift) + ((1 << x_phase_shift) >> 1);
+	y = ((vy >> y_phase_shift) << y_phase_shift) + ((1 << y_phase_shift) >> 1);
+
+	px = (x & 0xffff) >> x_phase_shift;
+	py = (y & 0xffff) >> y_phase_shift;
+
+	x1 = pixman_fixed_to_int (x - pixman_fixed_e - x_off);
+	y1 = pixman_fixed_to_int (y - pixman_fixed_e - y_off);
+	x2 = x1 + cwidth;
+	y2 = y1 + cheight;
+
+	stot = _mm_setzero_ps();
+
+	y_filter = filter + (1 << x_phase_bits) * cwidth + py * cheight;
+
+        if (x1 >= 0 && y1 >= 0 && x2 <= bits->width && y2 <= bits->height)
+        {
+            for (i = y1; i < y2; ++i)
+            {
+                float fy = *y_filter++;
+                float *x_filter = filter + px * cwidth;
+
+		for (j = x1; j < x2; ++j)
+		{
+                    float fx = *x_filter++;
+		    int rx = j;
+		    int ry = i;
+
+                    __m128 f, pixel_ps;
+                    uint32_t pixel, mask;
+                    uint8_t *row;
+
+                    mask = PIXMAN_FORMAT_A (format)? 0 : 0xff000000;
+
+                    row = (uint8_t *)bits->bits + bits->rowstride * 4 * ry;
+                    pixel = convert_pixel (row, rx) | mask;
+
+                    f = _mm_set1_ps (fx * fy);
+                    pixel_ps = expand_pixel_ps (pixel);
+                    stot = _mm_add_ps(stot, _mm_mul_ps (pixel_ps, f));
+		}
+	    }
+        }
+        else
+        {
+            for (i = y1; i < y2; ++i)
+            {
+                float fy = *y_filter++;
+		float *x_filter = filter + px * cwidth;
+
+		for (j = x1; j < x2; ++j)
+		{
+                    float fx = *x_filter++;
+		    int rx = j;
+		    int ry = i;
+
+                    __m128 f, pixel_ps;
+                    uint32_t pixel, mask;
+                    uint8_t *row;
+
+                    mask = PIXMAN_FORMAT_A (format)? 0 : 0xff000000;
+
+                    if (repeat_mode != PIXMAN_REPEAT_NONE)
+                    {
+                        repeat (repeat_mode, &rx, bits->width);
+                        repeat (repeat_mode, &ry, bits->height);
+
+                        row = (uint8_t *)bits->bits + bits->rowstride * 4 * ry;
+                        pixel = convert_pixel (row, rx) | mask;
+                    }
+                    else
+                    {
+                        if (rx < 0 || ry < 0 || rx >= bits->width || ry >= bits->height)
+                        {
+                            pixel = 0;
+                        }
+                        else
+                        {
+                            row = (uint8_t *)bits->bits + bits->rowstride * 4 * ry;
+                            pixel = convert_pixel (row, rx) | mask;
+                        }
+                    }
+
+                    f = _mm_set1_ps (fx * fy);
+                    pixel_ps = expand_pixel_ps (pixel);
+                    stot = _mm_add_ps(stot, _mm_mul_ps (pixel_ps, f));
+		}
+	    }
+        }
+
+	tot_integer = _mm_cvtps_pi16 (_mm_add_ps (stot, one_half));
+	tot_packed = _mm_packs_pu16 (tot_integer, tot_integer);
+	buffer[k] = _mm_cvtsi64_si32 (tot_packed);
+
+    next:
+	vx += ux;
+	vy += uy;
+    }
+}
+
+static force_inline uint32_t
+convert_a8r8g8b8 (const uint8_t *row, int x)
+{
+    return *(((uint32_t *)row) + x);
+}
+
+static force_inline uint32_t
+convert_x8r8g8b8 (const uint8_t *row, int x)
+{
+    return *(((uint32_t *)row) + x);
+}
+
+static force_inline uint32_t
+convert_a8 (const uint8_t *row, int x)
+{
+    return *(row + x) << 24;
+}
+
+static force_inline uint32_t
+convert_r5g6b5 (const uint8_t *row, int x)
+{
+    return convert_0565_to_0888 (*((uint16_t *)row + x));
+}
+
+#define MAKE_SEPARABLE_CONVOLUTION_FETCHER(name, format, repeat_mode)  \
+    static uint32_t *							\
+    sse2_fetch_separable_convolution_affine_ ## name (pixman_iter_t   *iter, \
+                                                      const uint32_t * mask) \
+    {									\
+	sse2_fetch_separable_convolution_affine (                 	\
+	    iter->image,                                                \
+            (float *)iter->data,                                        \
+	    iter->x, iter->y++,                                         \
+	    iter->width,                                                \
+	    iter->buffer, mask,                                         \
+	    convert_ ## format,                                         \
+	    PIXMAN_ ## format,                                          \
+	    repeat_mode);                                               \
+									\
+	return iter->buffer;                                            \
+    }
+
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (pad_a8r8g8b8,     a8r8g8b8, PIXMAN_REPEAT_PAD)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (none_a8r8g8b8,    a8r8g8b8, PIXMAN_REPEAT_NONE)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (reflect_a8r8g8b8, a8r8g8b8, PIXMAN_REPEAT_REFLECT)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (normal_a8r8g8b8,  a8r8g8b8, PIXMAN_REPEAT_NORMAL)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (pad_x8r8g8b8,     x8r8g8b8, PIXMAN_REPEAT_PAD)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (none_x8r8g8b8,    x8r8g8b8, PIXMAN_REPEAT_NONE)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (reflect_x8r8g8b8, x8r8g8b8, PIXMAN_REPEAT_REFLECT)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (normal_x8r8g8b8,  x8r8g8b8, PIXMAN_REPEAT_NORMAL)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (pad_a8,           a8,       PIXMAN_REPEAT_PAD)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (none_a8,          a8,       PIXMAN_REPEAT_NONE)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (reflect_a8,	 a8,       PIXMAN_REPEAT_REFLECT)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (normal_a8,	 a8,       PIXMAN_REPEAT_NORMAL)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (pad_r5g6b5,       r5g6b5,   PIXMAN_REPEAT_PAD)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (none_r5g6b5,      r5g6b5,   PIXMAN_REPEAT_NONE)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (reflect_r5g6b5,   r5g6b5,   PIXMAN_REPEAT_REFLECT)
+MAKE_SEPARABLE_CONVOLUTION_FETCHER (normal_r5g6b5,    r5g6b5,   PIXMAN_REPEAT_NORMAL)
+
+static const pixman_iter_info_t sse2_iters[] = 
+{
 #define IMAGE_FLAGS							\
     (FAST_PATH_STANDARD_FLAGS | FAST_PATH_ID_TRANSFORM |		\
      FAST_PATH_BITS_IMAGE | FAST_PATH_SAMPLES_COVER_CLIP_NEAREST)
 
-static const pixman_iter_info_t sse2_iters[] = 
-{
     { PIXMAN_x8r8g8b8, IMAGE_FLAGS, ITER_NARROW,
       _pixman_iter_init_bits_stride, sse2_fetch_x8r8g8b8, NULL
     },
@@ -6475,6 +6745,40 @@ static const pixman_iter_info_t sse2_iters[] =
     { PIXMAN_a8, IMAGE_FLAGS, ITER_NARROW,
       _pixman_iter_init_bits_stride, sse2_fetch_a8, NULL
     },
+
+#define GENERAL_SEPARABLE_CONVOLUTION_FLAGS				\
+    (FAST_PATH_NO_ALPHA_MAP            |				\
+     FAST_PATH_NO_ACCESSORS            |				\
+     FAST_PATH_HAS_TRANSFORM           |				\
+     FAST_PATH_AFFINE_TRANSFORM        |				\
+     FAST_PATH_SEPARABLE_CONVOLUTION_FILTER)
+    
+#define SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH(name, format, repeat)   \
+    { PIXMAN_ ## format,						\
+      GENERAL_SEPARABLE_CONVOLUTION_FLAGS | FAST_PATH_ ## repeat ## _REPEAT, \
+      ITER_NARROW | ITER_SRC,						\
+      sse2_iter_init_separable_convolution,                             \
+      sse2_fetch_separable_convolution_affine_ ## name, \
+      NULL, \
+    },
+
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (pad_a8r8g8b8, a8r8g8b8, PAD)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (none_a8r8g8b8, a8r8g8b8, NONE)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (reflect_a8r8g8b8, a8r8g8b8, REFLECT)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (normal_a8r8g8b8, a8r8g8b8, NORMAL)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (pad_x8r8g8b8, x8r8g8b8, PAD)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (none_x8r8g8b8, x8r8g8b8, NONE)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (reflect_x8r8g8b8, x8r8g8b8, REFLECT)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (normal_x8r8g8b8, x8r8g8b8, NORMAL)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (pad_a8, a8, PAD)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (none_a8, a8, NONE)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (reflect_a8, a8, REFLECT)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (normal_a8, a8, NORMAL)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (pad_r5g6b5, r5g6b5, PAD)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (none_r5g6b5, r5g6b5, NONE)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (reflect_r5g6b5, r5g6b5, REFLECT)
+    SEPARABLE_CONVOLUTION_AFFINE_FAST_PATH (normal_r5g6b5, r5g6b5, NORMAL)
+
     { PIXMAN_null },
 };
 
-- 
1.8.5.3