[Pixman] [PATCH 1/4] Change conditions for setting FAST_PATH_SAMPLES_COVER_CLIP flags

[Ben Avison]

As discussed in
http://lists.freedesktop.org/archives/pixman/2015-August/003905.html

the 8 * pixman_fixed_e adjustment which was applied to the transformed
coordinates is a legacy of rounding errors which used to occur in old
versions of Pixman, but which no longer apply. For any affine transform,
you are now guaranteed to get the same result by transforming the upper
coordinate as though you transform the lower coordinate and add (size-1)
steps of the increment in source coordinate space. No projective
transform routines use the COVER_CLIP flags, so they cannot be affected.

However, removing the 8 * pixman_fixed_e border exposes a bug in the
calculation of the COVER_CLIP_NEAREST flag. Because the half-way cases
round down, an adjustment by pixman_fixed_e is needed. This patch
applies this adjustment.

Many bilinear fast paths currently assume that COVER_CLIP_BILINEAR is
not set when the transformed upper coordinate corresponds exactly to the
last row/pixel in source space. This is due to a detail of many current
implementations - they assume they can always load the pixel after the one
you get by dividing the coordinate by 2^16 with rounding to -infinity.

To avoid causing these implementations to exceed array bounds in these
cases, the COVER_CLIP_BILINEAR flag retains this feature in this patch.
Subsequent patches deal with removing this assumption, to enable cover
fast paths to be used in the maximum number of cases.

Proof:

All implementations must give the same numerical results as
bits_image_fetch_pixel_nearest() / bits_image_fetch_pixel_bilinear().

The former does
    int x0 = pixman_fixed_to_int (x - pixman_fixed_e);
which maps directly to the new test for the nearest flag, when you consider
that x0 must fall in the interval [0,width).

The latter does
    x1 = x - pixman_fixed_1 / 2;
    x1 = pixman_fixed_to_int (x1);
    x2 = x1 + 1;
but then x2 is brought back in range by the repeat() function, so it can't
stray beyond the end of the source line. When you write a cover path, you
are effectively omitting the repeat() function. The weight applied to the
pixel at offset x2 will be zero, so if you skip the load and leave the
pixel value undefined, the numerical result is unaffected, but you have
avoided a memory access that could potentially cause a page fault. If
however, we assume that the implementation loads from offset x2
unconditionally, then we need
    x1 >= 0
    x2 < width
so
    x - pixman_fixed_1 / 2 >= 0
    x - pixman_fixed_1 / 2 + pixman_fixed_1 < width * pixman_fixed_1
so
    pixman_fixed_to_int (x - pixman_fixed_1 / 2) >= 0
    pixman_fixed_to_int (x + pixman_fixed_1 / 2) < width
which matches the source code lines for the bilinear case, once you delete
the lines that apply the 8 * pixman_fixed_e border.
---
 pixman/pixman.c     |   17 ++++-------------
 test/affine-bench.c |   16 ++++++++++------
 2 files changed, 14 insertions(+), 19 deletions(-)

diff --git a/pixman/pixman.c b/pixman/pixman.c
index a07c577..f932eac 100644
--- a/pixman/pixman.c
+++ b/pixman/pixman.c
@@ -497,21 +497,12 @@ 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;
 	}
diff --git a/test/affine-bench.c b/test/affine-bench.c
index 9e0121e..697684b 100644
--- a/test/affine-bench.c
+++ b/test/affine-bench.c
@@ -396,13 +396,17 @@ main (int argc, char *argv[])
     }
 
     compute_transformed_extents (&binfo.transform, &dest_box, &transformed);
-    /* The source area is expanded by a tiny bit (8/65536th pixel)
-     * to match the calculation of the COVER_CLIP flags in analyze_extent()
+    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);
+    ymax = pixman_fixed_to_int (transformed.y2 + pixman_fixed_1 / 2);
+    /* Note: when FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR is retired, the upper
+     * limits can be reduced to:
+     * 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);
+     * This is equivalent to subtracting 0.5 and rounding up, rather than
+     * subtracting 0.5, rounding down and adding 1.
      */
-    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);
     binfo.src_x = -xmin;
     binfo.src_y = -ymin;
 
-- 
1.7.5.4