[Pixman] [PATCH 3/3] Add an iterator that can fetch bilinearly scaled images

[Søren Sandmann Pedersen]

This new iterator works in a separable way; that is, for a destination
scaline, it scales the two involved source scanlines and then caches
them so that they can be reused for the next destination scanlines.

This scheme saves a substantial amount of arithmetic for larger
scalings; the time-per-pixel as reported by scaling-bench (running
with PIXMAN_DISABLE="sse2 mmx") is graphed here:

	http://people.freedesktop.org/~sandmann/scaling-graph.png

where the blue graph is the times before this patch, and the red graph
is after.

As the graph shows, this patch is a slowdown for scaling ratios below
0.6, but not a big one, and large downscalings with the bilinear
filter is not an important usecase anyway since the results are ugly.

The graph is also available here:

    	http://i.imgur.com/Nibcyes.png

The data used to generate the graph is available here:

	http://people.freedesktop.org/~sandmann/before
	http://people.freedesktop.org/~sandmann/after
---
 pixman/pixman-fast-path.c |  192 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 192 insertions(+), 0 deletions(-)

diff --git a/pixman/pixman-fast-path.c b/pixman/pixman-fast-path.c
index 3982dce..0c2ca72 100644
--- a/pixman/pixman-fast-path.c
+++ b/pixman/pixman-fast-path.c
@@ -2261,6 +2261,188 @@ fast_write_back_r5g6b5 (pixman_iter_t *iter)
     }
 }
 
+typedef struct
+{
+    int		y;
+    uint64_t *	buffer;
+} line_t;
+
+typedef struct
+{
+    line_t		line0;
+    line_t		line1;
+    pixman_fixed_t	y;
+    pixman_fixed_t	x;
+    uint64_t		data[1];
+} bilinear_info_t;
+
+static void
+fetch_horizontal (bits_image_t *image, line_t *line,
+		  int y, pixman_fixed_t x, pixman_fixed_t ux, int n)
+{
+    uint32_t *bits = image->bits + y * image->rowstride;
+    int i;
+
+    for (i = 0; i < n; ++i)
+    {
+	int x0 = pixman_fixed_to_int (x);
+	int x1 = x0 + 1;
+	int32_t dist_x;
+
+	uint32_t left = *(bits + x0);
+	uint32_t right = *(bits + x1);
+	uint32_t lag, rag;
+	uint32_t lrb, rrb;
+	uint64_t lagrb, ragrb;
+	uint64_t a, r, g, b;
+	uint64_t p;
+
+	dist_x = pixman_fixed_to_bilinear_weight (x);
+	dist_x <<= (8 - BILINEAR_INTERPOLATION_BITS);
+
+	lag = (left & 0xff00ff00);
+	lrb = (left & 0x00ff00ff);
+	rag = (right & 0xff00ff00);
+	rrb = (right & 0x00ff00ff);
+	lagrb = (((uint64_t)lag) << 24) | lrb;
+	ragrb = (((uint64_t)rag) << 24) | rrb;
+
+	p = (lagrb << 8) + dist_x * (ragrb - lagrb);
+
+	a = (p <<  0) & 0xffff000000000000ULL;
+	r = (p << 16) & 0x0000ffff00000000ULL;
+	g = (p >> 16) & 0x00000000ffff0000ULL;
+	b = (p >>  0) & 0x000000000000ffffULL;
+
+	line->buffer[i] = a | r | g | b;
+
+	x += ux;
+    }
+
+    line->y = y;
+}
+
+static uint32_t *
+fast_fetch_bilinear_cover (pixman_iter_t *iter, const uint32_t *mask)
+{
+    pixman_fixed_t fx, ux;
+    bilinear_info_t *info = iter->data;
+    line_t *line0, *line1;
+    int y0, y1;
+    int32_t dist_y;
+    int i;
+
+    fx = info->x;
+    ux = iter->image->common.transform->matrix[0][0];
+
+    y0 = pixman_fixed_to_int (info->y);
+    y1 = y0 + 1;
+    dist_y = pixman_fixed_to_bilinear_weight (info->y);
+    dist_y <<= (8 - BILINEAR_INTERPOLATION_BITS);
+
+    line0 = &info->line0;
+    line1 = &info->line1;
+
+    if (line0->y != y0 || line1->y != y1)
+    {
+	if (line0->y == y1 || line1->y == y0)
+	{
+	    line_t tmp = *line0;
+	    *line0 = *line1;
+	    *line1 = tmp;
+	}
+
+	if (line0->y != y0)
+	{
+	    fetch_horizontal (
+		&iter->image->bits, line0, y0, fx, ux, iter->width);
+	}
+
+	if (line1->y != y1)
+	{
+	    fetch_horizontal (
+		&iter->image->bits, line1, y1, fx, ux, iter->width);
+	}
+    }
+
+    for (i = 0; i < iter->width; ++i)
+    {
+	uint64_t top = line0->buffer[i];
+	uint64_t bot = line1->buffer[i];
+	uint64_t tag = (top & 0xffff0000ffff0000ULL) >> 16;
+	uint64_t bag = (bot & 0xffff0000ffff0000ULL) >> 16;
+	uint64_t trb = (top & 0x0000ffff0000ffffULL);
+	uint64_t brb = (bot & 0x0000ffff0000ffffULL);
+	uint64_t ag, rb;
+	uint64_t a, r, g, b;
+
+	ag = (tag << 8) + dist_y * (bag - tag);
+	rb = (trb << 8) + dist_y * (brb - trb);
+
+	a = ((ag >> 24) & 0xff000000);
+	r = ((rb >> 32) & 0x00ff0000);
+	g = ((ag >>  8) & 0x0000ff00);
+	b = ((rb >> 16) & 0x000000ff);
+
+	iter->buffer[i] = a | r | g | b;
+    }
+
+    info->y += iter->image->common.transform->matrix[1][1];
+
+    return iter->buffer;
+}
+
+static void
+bilinear_cover_iter_fini (pixman_iter_t *iter)
+{
+    free (iter->data);
+}
+
+static void
+fast_bilinear_cover_iter_init (pixman_iter_t *iter, const pixman_iter_info_t *iter_info)
+{
+    int width = iter->width;
+    bilinear_info_t *info;
+    pixman_vector_t v;
+
+    /* Reference point is the center of the pixel */
+    v.vector[0] = pixman_int_to_fixed (iter->x) + pixman_fixed_1 / 2;
+    v.vector[1] = pixman_int_to_fixed (iter->y) + pixman_fixed_1 / 2;
+    v.vector[2] = pixman_fixed_1;
+
+    if (!pixman_transform_point_3d (iter->image->common.transform, &v))
+	goto fail;
+
+    info = malloc (sizeof (*info) + (2 * width - 1) * sizeof (uint64_t));
+    if (!info)
+	goto fail;
+
+    info->x = v.vector[0] - pixman_fixed_1 / 2;
+    info->y = v.vector[1] - pixman_fixed_1 / 2;
+
+    /* It is safe to set the y coordinates to -1 initially
+     * because COVER_CLIP_BILINEAR ensures that we will only
+     * be asked to fetch lines in the [0, height) interval
+     */
+    info->line0.y = -1;
+    info->line0.buffer = &(info->data[0]);
+    info->line1.y = -1;
+    info->line1.buffer = &(info->data[width]);
+
+    iter->get_scanline = fast_fetch_bilinear_cover;
+    iter->fini = bilinear_cover_iter_fini;
+
+    iter->data = info;
+    return;
+
+fail:
+    /* Something went wrong, either a bad matrix or OOM; in such cases,
+     * we don't guarantee any particular rendering.
+     */
+    iter->get_scanline = _pixman_iter_get_scanline_noop;
+    iter->fini = bilinear_cover_iter_fini;
+}
+
 #define IMAGE_FLAGS							\
     (FAST_PATH_STANDARD_FLAGS | FAST_PATH_ID_TRANSFORM |		\
      FAST_PATH_BITS_IMAGE | FAST_PATH_SAMPLES_COVER_CLIP_NEAREST)
@@ -2280,6 +2462,16 @@ static const pixman_iter_info_t fast_iters[] =
       _pixman_iter_init_bits_stride,
       fast_dest_fetch_noop, fast_write_back_r5g6b5 },
 
+    { PIXMAN_a8r8g8b8,
+      (FAST_PATH_STANDARD_FLAGS			|
+       FAST_PATH_SCALE_TRANSFORM		|
+       FAST_PATH_BILINEAR_FILTER		|
+       FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR),
+      ITER_NARROW | ITER_SRC,
+      fast_bilinear_cover_iter_init,
+      NULL, NULL
+    },
+
     { PIXMAN_null },
 };
 
-- 
1.7.1