[Pixman] [PATCH 1/2] Remove the 8e extra safety margin in COVER_CLIP analysis
Siarhei Siamashka
siarhei.siamashka at gmail.com
Mon Sep 21 19:39:50 PDT 2015
On Mon, 21 Sep 2015 12:59:18 +0300
Pekka Paalanen <ppaalanen at gmail.com> wrote:
> On Mon, 21 Sep 2015 08:32:48 +0300
> Siarhei Siamashka <siarhei.siamashka at gmail.com> wrote:
>
> > On Fri, 11 Sep 2015 14:30:23 +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.
> >
> > That's actually what I wanted too see proven.
>
> Hi Siarhei, Ben,
>
> starting here...
>
> > 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 = | 0 |
> > | 0 |
>
> (with the correction you made in a follow-up)
>
> >
> > 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.
>
> ...and ending here. Shall I just take that piece of text and put it in
> the commit message?
I'm fine with this.
> Btw. thanks for trying cover-test on the old code.
>
> > Since we are trying to justify the 8e extra safety margin removal in
> > the context of this patch, this is what I wanted to see explained in
> > the commit message. But maybe I'm just bad at math and it was perfectly
> > obvious to everyone else without any special proof.
>
> No, I think we took your word for it. Well, I did.
OK. What I mean is that it's safer to provide some explanations now. So
that in the future nobody can claim that we had been clueless and it
only happens to work by pure luck :-)
> > > No projective transform routines use the COVER_CLIP flags, so they
> > > cannot be affected.
> > >
> > > 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;
> > > but then x2 is brought back in range by the repeat() function, so it can't
> > > stray beyond the end of the source line.
> >
> > The wording does not look very good here. It seems to imply that the
> > repeat() function has some special use in the latter (BILINEAR) case.
> > But the repeat handling is exactly the same for NEAREST and BILINEAR.
> > Also for NONE repeat and fetching pixels from the outside of the source
> > image bounds, we are not bringing the coordinate back into range but
> > interpreting the pixel value as zero.
>
> Ok, how about this:
>
> 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... and so on.
Looks good to me.
> > > When you write a COVER path, you are effectively omitting the repeat()
> > > function.
> > >
> > > 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.
> >
> > Thanks for explaining this. It was not the part that I was worried
> > about, but it is still good to have it nonetheless.
> >
> > > Signed-off-by: Ben Avison <bavison at riscosopen.org>
> > > [Pekka: adjusted commit message, left affine-bench changes for another patch]
> > > Signed-off-by: Pekka Paalanen <pekka.paalanen at collabora.co.uk>
> > >
> > > ---
> > >
> > > This is v2 part 1/2 of the patch "Change conditions for setting
> > > FAST_PATH_SAMPLES_COVER_CLIP flags".
> > > ---
> > > pixman/pixman.c | 17 ++++-------------
> > > 1 file changed, 4 insertions(+), 13 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;
> > > }
> >
> > Acked-by: Siarhei Siamashka <siarhei.siamashka at gmail.com>
> >
> > It's up to you whether to update the commit message or not. Maybe the
> > already existing reference to the mailing list archive is already
> > sufficient.
>
> Siarhei, how far is this from getting a Reviewed-by from you?
>
> It seems you have already invested a good deal of time looking at this,
> would be a shame to leave it at Acked-by level now. :-)
You are right. Looks like the Acked-by tag is not very useful, at least
based on the description in
http://wiki.x.org/wiki/Development/Documentation/SubmittingPatches
> I'm happy to send another revision, if it helps turning the Ack to R-b.
I will start using the Reviewed-by tag from now on. And all my older
Acked-by tags were in fact intended to be Reviewed-by.
--
Best regards,
Siarhei Siamashka
More information about the Pixman
mailing list