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

[Oded Gabbay]

On Fri, Sep 4, 2015 at 5:09 AM, Ben Avison <bavison at riscosopen.org> wrote:
> 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)
Shouldn't the above two lines be with '+' ?
i.e:
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
>
> _______________________________________________
> Pixman mailing list
> Pixman at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/pixman

Unfortunately, I don't understand 90% of what this patch talks about,
so I hope someone else will review this as well.

         Oded