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

[Pekka Paalanen]

On Wed, 9 Sep 2015 09:39:07 +0300
Oded Gabbay <oded.gabbay at gmail.com> wrote:

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

Hi,

I'm not sure if these two paragraphs about bilinear are really
necessary here. The essence is that we remove the extra margins from
both NEAREST (not 8*eps, but 7*eps and 9*eps, see below) and BILINEAR
(8*eps), without changing them in any other way.

The subsequent patches are still under discussion, and we have to see
how they work out.

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

Right.

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

Indeed, but I think the talk about omitting the loading of the
zero-weight pixel does not belong in this patch. Before and after
this patch we still do assume that bilinear fetchers unconditionally
read the pixel at x2.

However, this is a good explanation on why exactly does -0.5 / +0.5
adjustment allow bilinear fetchers to load x2 unconditionally. This is
the rationale for not changing anything else for COVER_CLIP_BILINEAR.

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

No, this is how coordinate rounding for NEAREST works. Pixel index i
maps from coordinates (i, i+1.0], IOW coordinates from i+eps to i+1.0,
inclusive. Perhaps surprisingly, coordinate i+0.0 is defined to map to
index i-1, which is what the -eps before truncation towards -Inf does.
(Pixel centers are at i+0.5.)

We want to ensure, that the pixel indices all fall into the valid image
pixels which are x in [0, width) and y in [0, height).

If we compare this new code to the old, we realize that the extra
margins were not a uniform 8*eps in all directions. They were 7*eps to
the left and up, and 9*eps to the right and down, for NEAREST.

BILINEAR, which does not have this eps offset thing like NEAREST does,
did have 8*eps extra margins in all directions.

> >         {
> >             *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[])
> >      }

I think affine-bench is missing a comment saying that it specifically
targets the COVER paths.

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

This comment is a bit confusing, since it does not explain what
retiring COVER_CLIP_BILINEAR means. I think it would be better to
rephrase as: "The upper limits can be reduced to the following if
bilinear fetchers are guaranteed to not access the pixel beyond the row
end with zero weight:" or something like that.

> > +     * 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

All the above otherwise looks good to me, but there is one more place
that has 8*eps, analyze_extent() in pixman.c has:

    /* Check we don't overflow when the destination extents are expanded by one.
     * This ensures that compositing functions can simply walk the source space
     * using 16.16 variables without worrying about overflow.
     */
    exp_extents = *extents;
    exp_extents.x1 -= 1;
    exp_extents.y1 -= 1;
    exp_extents.x2 += 1;
    exp_extents.y2 += 1;

    if (!compute_transformed_extents (transform, &exp_extents, &transformed))
	return FALSE;
    
    if (!IS_16_16 (transformed.x1 + x_off - 8 * pixman_fixed_e)	||
	!IS_16_16 (transformed.y1 + y_off - 8 * pixman_fixed_e)	||
	!IS_16_16 (transformed.x2 + x_off + 8 * pixman_fixed_e + width)	||
	!IS_16_16 (transformed.y2 + y_off + 8 * pixman_fixed_e + height))
    {
	return FALSE;
    }

Should we be removing these 8*eps too?


Siarhei, does this one patch do everything you expect from it?
For reference, below are some questions from Ben I haven't seen an
answer for.


On Thu, 27 Aug 2015 11:45:22 +0100
"Ben Avison" <bavison at riscosopen.org> wrote:

> On Thu, 27 Aug 2015 03:55:07 +0100, Siarhei Siamashka <siarhei.siamashka at gmail.com> wrote:
> > I believe that neither of FAST_PATH_SAMPLES_COVER_CLIP_NEAREST and
> > FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR flags matters for projective
> > transformations, but this can be additionally checked just in case.
> 
> I did survey all the existing fast paths and fetchers and discovered that
> both the cover flags were only being used for affine transforms when I
> was trying to work out what the 8 * pixman_fixed_e rounding might have
> been referring to.
> 
> By check, do you mean we should ensure that the flags are not set for
> projective transforms? If so, I see that compute_image_info() is called
> before analyze_extent() so it could be achieved by adding an extra test
> in analyze_extent() that FAST_PATH_AFFINE_TRANSFORM is set before setting
> the cover flags.


On Fri, 04 Sep 2015 03:03:57 +0100
"Ben Avison" <bavison at riscosopen.org> wrote:

> On Thu, 03 Sep 2015 16:22:05 +0100, Siarhei Siamashka <siarhei.siamashka at gmail.com> wrote:
> 
> > The cover-test is useful, but it is only able to demonstrate that the
> > code is incorrect when it fails (like, for example, the first revision
> > of Ben's patches). Still the test does not prove anything if it passes.
> 
> I'm not sure if you're asking for something here? It's hard to think of a
> test that proves that if the limits were any tighter that there *would*
> be bounds violations, at least not without adding some API to adjust the
> thresholds at runtime. The criticism that it can only demonstrate that
> the code is incorrect is equally true of any of the other fuzz testers
> in the test suite.


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/20150909/dd52e7c1/attachment-0001.sig>