[Pixman] [PATCH 37/37] More accurate FAST_PATH_SAMPLES_COVER_CLIP_NEAREST|BILINEAR

[Ben Avison]

A number of fast paths exist which only support "cover" type plots. These
are operations where once we transform the complete set of destination
pixels required for the plot into the source image's coordinate space, all
the required source pixels fall within the source's array bounds. This
means that there is no need for bounds checking in the inner loop, and the
selected repeat type (none, normal (aka tiled), pad, or reflect) has no
impact upon the result.

Without the needs for bounds checking, a "cover" fast path will always be
faster than an equivalent fast path which uses one of the four repeat types,
so it is unfortunate that the previous tests in analyze_extent() for
setting the two cover flags were too strict, resulting in the "cover" fast
paths being passed over in some cases where they could have been used
instead of the matching "repeat" fast path. The penalty is even higher
where there is no equivalent "repeat" fast path, as is the case with recent
ARMv6 scaled fast paths.

A worked example helps to illustrate the point. Consider a source image of
size 2,1 being plotted at the 3 pixels at the top-left of the destination
image using transformation matrix

    / 0.5 0   0.25 \
T = | 0   1   0    |
    \ 0   0   1    /

In source and destination, x and y, Pixman considers the sample at array
index i to represent the colour at the centre of the pixel with coordinates
[i, i+1). So the top three destination pixels correspond to coordinates
(0.5, 0.5), (1.5, 0.5), (2.5, 0.5). If we write these as

    / 0.5 1.5 2.5 \
D = | 0.5 0.5 0.5 |
    \ 1   1   1   /

then under the transformation, we get the equivalent source coordinates

        / 0.5 1   1.5 \
T . D = | 0.5 0.5 0.5 |
        \ 1   1   1   /

Thus output pixel 0 corresponds exactly to input pixel 0, output pixel 2
corresponds exactly to input pixel 1, and output pixel 1 depends upon the
filter type: for bilinear it's the average of the two input pixels and for
nearest it rounds half-way coordinates to -infinity, so chooses input pixel
0.

Either way, we have remained within the bounds of the source image for all
pixels, but the old code incorrectly deduced that source index -1 for both
x and y, and source index 2 for x, were required for bilinear plots and
thus wouldn't choose a "cover" fast path.

There was a similar fault for nearest-neighbour scaling, where for example
doing a two-row plot of the same source image under the transformation

    / 0.5 0   0.25 \
T = | 0   0.5 0.25 |
    \ 0   0   1    /

wrongly deduced that source index 1 for y was required when generating the
second row.

There was a section of code where the post-transformation coordinates were
enlarged by 8*pixman_fixed_e, which was largely to blame for these. The
correct way to handle rounding depends on whether we're calculating the
cover flag for nearest or bilinear scaling, and since coordinates are
handled in fixed point throughout, there is a precise correct amount to
adjust each by, rather than an arbitrary fudge factor.

Running fuzzer-find-diff.pl on scaling-test for a number of hours has not
been able to identify any cases where the results of this new version are
incorrect.
---
 pixman/pixman.c     |   25 ++++++++-----------------
 test/affine-bench.c |    8 ++++----
 2 files changed, 12 insertions(+), 21 deletions(-)

diff --git a/pixman/pixman.c b/pixman/pixman.c
index 9555cea..792573c 100644
--- a/pixman/pixman.c
+++ b/pixman/pixman.c
@@ -495,29 +495,20 @@ analyze_extent (pixman_image_t       *image,
     if (!compute_transformed_extents (transform, extents, &transformed))
 	return FALSE;
 
-    /* Expand the source area by a tiny bit so account of different rounding that
-     * may happen during sampling. Note that (8 * pixman_fixed_e) is very far from
-     * 0.5 so this won't cause the area computed to be overly pessimistic.
-     */
-    transformed.x1 -= 8 * pixman_fixed_e;
-    transformed.y1 -= 8 * pixman_fixed_e;
-    transformed.x2 += 8 * pixman_fixed_e;
-    transformed.y2 += 8 * pixman_fixed_e;
-
     if (image->common.type == BITS)
     {
-	if (pixman_fixed_to_int (transformed.x1) >= 0			&&
-	    pixman_fixed_to_int (transformed.y1) >= 0			&&
-	    pixman_fixed_to_int (transformed.x2) < image->bits.width	&&
-	    pixman_fixed_to_int (transformed.y2) < image->bits.height)
+        if (pixman_fixed_to_int (transformed.x1 - pixman_fixed_e) >= 0                   &&
+            pixman_fixed_to_int (transformed.y1 - pixman_fixed_e) >= 0                   &&
+            pixman_fixed_to_int (transformed.x2 - pixman_fixed_e) < image->bits.width    &&
+            pixman_fixed_to_int (transformed.y2 - pixman_fixed_e) < image->bits.height)
 	{
 	    *flags |= FAST_PATH_SAMPLES_COVER_CLIP_NEAREST;
 	}
 
-	if (pixman_fixed_to_int (transformed.x1 - pixman_fixed_1 / 2) >= 0		  &&
-	    pixman_fixed_to_int (transformed.y1 - pixman_fixed_1 / 2) >= 0		  &&
-	    pixman_fixed_to_int (transformed.x2 + pixman_fixed_1 / 2) < image->bits.width &&
-	    pixman_fixed_to_int (transformed.y2 + pixman_fixed_1 / 2) < image->bits.height)
+        if (pixman_fixed_to_int (transformed.x1 - pixman_fixed_1 / 2) >= 0                                 &&
+            pixman_fixed_to_int (transformed.y1 - pixman_fixed_1 / 2) >= 0                                 &&
+            pixman_fixed_to_int (transformed.x2 + pixman_fixed_1 / 2 - pixman_fixed_e) < image->bits.width &&
+            pixman_fixed_to_int (transformed.y2 + pixman_fixed_1 / 2 - pixman_fixed_e) < image->bits.height)
 	{
 	    *flags |= FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR;
 	}
diff --git a/test/affine-bench.c b/test/affine-bench.c
index 6eff5ab..25704ef 100644
--- a/test/affine-bench.c
+++ b/test/affine-bench.c
@@ -385,10 +385,10 @@ main (int argc, char *argv[])
     }
 
     compute_transformed_extents (&t, &dest_box, &transformed);
-    xmin = pixman_fixed_to_int (transformed.x1 - 8 * pixman_fixed_e - pixman_fixed_1 / 2);
-    ymin = pixman_fixed_to_int (transformed.y1 - 8 * pixman_fixed_e - pixman_fixed_1 / 2);
-    xmax = pixman_fixed_to_int (transformed.x2 + 8 * pixman_fixed_e + pixman_fixed_1 / 2);
-    ymax = pixman_fixed_to_int (transformed.y2 + 8 * pixman_fixed_e + pixman_fixed_1 / 2);
+    xmin = pixman_fixed_to_int (transformed.x1 - pixman_fixed_1 / 2);
+    ymin = pixman_fixed_to_int (transformed.y1 - pixman_fixed_1 / 2);
+    xmax = pixman_fixed_to_int (transformed.x2 + pixman_fixed_1 / 2 - pixman_fixed_e);
+    ymax = pixman_fixed_to_int (transformed.y2 + pixman_fixed_1 / 2 - pixman_fixed_e);
     src_x = -xmin;
     src_y = -ymin;
 
-- 
1.7.5.4