[Pixman] [PATCH v3 1/2] Remove the 8e extra safety margin in COVER_CLIP analysis

[Siarhei Siamashka]

On Wed, 23 Sep 2015 11:40:32 +0300
Pekka Paalanen <ppaalanen at gmail.com> wrote:

> From: Ben Avison <bavison at riscosopen.org>
> 
> As discussed in
> http://lists.freedesktop.org/archives/pixman/2015-August/003905.html
> 
> the 8 * pixman_fixed_e (8e) 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.
> 
> Proof by Siarhei Siamashka:
> 
> Let's take a look at the following affine transformation matrix (with 16.16
> fixed point values) and two vectors:
> 
>          | a   b     c    |
> M      = | d   e     f    |
>          | 0   0  0x10000 |
> 
>          |  x_dst  |
> P     =  |  y_dst  |
>          | 0x10000 |
> 
>          | 0x10000 |
> ONE_X  = |    0    |
>          |    0    |
> 
> The current matrix multiplication code does the following calculations:
> 
>              | (a * x_dst + b * y_dst + 0x8000) / 0x10000 + c |
>     M * P =  | (d * x_dst + e * y_dst + 0x8000) / 0x10000 + f |
>              |                   0x10000                      |
> 
> These calculations are not perfectly exact and we may get rounding
> because the integer coordinates are adjusted by 0.5 (or 0x8000 in the
> 16.16 fixed point format) before doing matrix multiplication. For
> example, if the 'a' coefficient is an odd number and 'b' is zero,
> then we are losing some of the least significant bits when dividing by
> 0x10000.
> 
> So we need to strictly prove that the following expression is always
> true even though we have to deal with rounding:
> 
>                                           | a |
>     M * (P + ONE_X) - M * P = M * ONE_X = | d |
>                                           | 0 |
> 
> or
> 
>    ((a * (x_dst + 0x10000) + b * y_dst + 0x8000) / 0x10000 + c)
>   -
>    ((a * x_dst             + b * y_dst + 0x8000) / 0x10000 + c)
>   =
>     a
> 
> It's easy to see that this is equivalent to
> 
>     a + ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c)
>       - ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c)
>   =
>     a
> 
> Which means that stepping exactly by one pixel horizontally in the
> destination image space (advancing 'x_dst' by 0x10000) is the same as
> changing the transformed 'x_src' coordinate in the source image space
> exactly by 'a'. The same applies to the vertical direction too.
> Repeating these steps, we can reach any pixel in the source image
> space and get exactly the same fixed point coordinates as doing
> matrix multiplications per each pixel.
> 
> By the way, the older matrix multiplication implementation, which was
> relying on less accurate calculations with three intermediate roundings
> "((a + 0x8000) >> 16) + ((b + 0x8000) >> 16) + ((c + 0x8000) >> 16)",
> also has the same properties. However reverting
>     http://cgit.freedesktop.org/pixman/commit/?id=ed39992564beefe6b12f81e842caba11aff98a9c
> and applying this "Remove the 8e extra safety margin in COVER_CLIP
> analysis" patch makes the cover test fail. The real reason why it fails
> is that the old pixman code was using "pixman_transform_point_3d()"
> function
>     http://cgit.freedesktop.org/pixman/tree/pixman/pixman-matrix.c?id=pixman-0.28.2#n49
> for getting the transformed coordinate of the top left corner pixel
> in the image scaling code, but at the same time using a different
> "pixman_transform_point()" function
>     http://cgit.freedesktop.org/pixman/tree/pixman/pixman-matrix.c?id=pixman-0.28.2#n82
> in the extents calculation code for setting the cover flag. And these
> functions did the intermediate rounding differently. That's why the 8e
> safety margin was needed.
> 
> ** proof ends
> 
> However, for COVER_CLIP_NEAREST, the actual margins added were not 8e.
> Because the half-way cases round down, that is, coordinate 0 hits pixel
> index -1 while coordinate e hits pixel index 0, the extra safety margins
> were actually 7e to the left and up, and 9e to the right and down. This
> patch removes the 7e and 9e margins and restores the -e adjustment
> required for NEAREST sampling in Pixman. For reference, see
> pixman/rounding.txt.
> 
> For COVER_CLIP_BILINEAR, the margins were exactly 8e as there are no
> additional offsets to be restored, so simply removing the 8e additions
> is enough.
> 
> 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;
> When you write a COVER path, you take advantage of the assumption that
> both x1 and x2 fall in the interval [0, width).
> 
> As samplers are allowed to fetch the pixel at x2 unconditionally, we
> require
>     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 add the 8e margin.
> 
> Cc: Siarhei Siamashka <siarhei.siamashka at gmail.com>
> Signed-off-by: Ben Avison <bavison at riscosopen.org>
> [Pekka: adjusted commit message, left affine-bench changes for another patch]
> [Pekka: add commit message parts from Siarhei]
> Signed-off-by: Pekka Paalanen <pekka.paalanen at collabora.co.uk>
> 
> ---
> 
> v2 is part 1/2 of the patch "Change conditions for setting
> FAST_PATH_SAMPLES_COVER_CLIP flags".
> 
> This is v3 with a yet more bikeshedded commit message.
> 
> Ben, Siarhei,
> 
> for the record, gentlemen, please give your reviewed-by's
> so I can just push these two out without any confusion. :-)

Yes, sure. Even the older commit message already included a
link to the mailing list archive, so I did not have any
problems with it. This final revision is also fine.

Reviewed-by: Siarhei Siamashka <siarhei.siamashka at gmail.com>

-- 
Best regards,
Siarhei Siamashka