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

[Pekka Paalanen]

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?

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.

> > 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.

> > 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. :-)

I'm happy to send another revision, if it helps turning the Ack to R-b.


Thanks,
pq
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 811 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freedesktop.org/archives/pixman/attachments/20150921/404ed3b1/attachment.sig>