On Wed, 9 Sep 2015 09:39:07 +0300 Oded Gabbay <[email protected]> wrote:
> On Fri, Sep 4, 2015 at 5:09 AM, Ben Avison <[email protected]> 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" <[email protected]> wrote: > On Thu, 27 Aug 2015 03:55:07 +0100, Siarhei Siamashka > <[email protected]> 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" <[email protected]> wrote: > On Thu, 03 Sep 2015 16:22:05 +0100, Siarhei Siamashka > <[email protected]> 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
pgpFXidzcD8Uo.pgp
Description: OpenPGP digital signature
_______________________________________________ Pixman mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/pixman
