[Pixman] [PATCH v3 1/2] Remove the 8e extra safety margin in COVER_CLIP analysis
siarhei.siamashka at gmail.com
Thu Sep 24 21:38:34 PDT 2015
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
> 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
> 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 |
> ((a * (x_dst + 0x10000) + b * y_dst + 0x8000) / 0x10000 + c)
> ((a * x_dst + b * y_dst + 0x8000) / 0x10000 + c)
> 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)
> 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
> 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()"
> 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
> 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
> 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.
> 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
> x1 >= 0
> x2 < width
> x - pixman_fixed_1 / 2 >= 0
> x - pixman_fixed_1 / 2 + pixman_fixed_1 < width * pixman_fixed_1
> 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>
More information about the Pixman