pixman: Branch 'master' - 2 commits
Pekka Paalanen
pq at kemper.freedesktop.org
Fri Sep 25 04:38:02 PDT 2015
pixman/pixman.c | 17 ++++-------------
test/affine-bench.c | 24 ++++++++++++++++++------
2 files changed, 22 insertions(+), 19 deletions(-)
New commits:
commit 2876d8d3dd6a71cb9eb3ac93e5b9c18b71a452da
Author: Ben Avison <bavison at riscosopen.org>
Date: Fri Sep 4 03:09:20 2015 +0100
affine-bench: remove 8e margin from COVER area
Patch "Remove the 8e extra safety margin in COVER_CLIP analysis" reduced
the required image area for setting the COVER flags in
pixman.c:analyze_extent(). Do the same reduction in affine-bench.
Leaving the old calculations in place would be very confusing for anyone
reading the code.
Also add a comment that explains how affine-bench wants to hit the COVER
paths. This explains why the intricate extent calculations are copied
from pixman.c.
[Pekka: split patch, change comments, write commit message]
Signed-off-by: Pekka Paalanen <pekka.paalanen at collabora.co.uk>
Reviewed-by: Ben Avison <bavison at riscosopen.org>
diff --git a/test/affine-bench.c b/test/affine-bench.c
index 9e0121e..86bf46e 100644
--- a/test/affine-bench.c
+++ b/test/affine-bench.c
@@ -395,14 +395,26 @@ main (int argc, char *argv[])
return EXIT_FAILURE;
}
+ /* Compute required extents for source and mask image so they qualify
+ * for COVER fast paths and get the flags in pixman.c:analyze_extent().
+ * These computations are for FAST_PATH_SAMPLES_COVER_CLIP_BILINEAR,
+ * but at the same time they also allow COVER_CLIP_NEAREST.
+ */
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:
+ * The upper limits can be reduced to the following when fetchers
+ * are guaranteed to not access pixels with zero weight. This concerns
+ * particularly all bilinear samplers.
+ *
+ * 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;
commit 0e2e9751282b19280c92be4a80c5ae476bae0ce4
Author: Ben Avison <bavison at riscosopen.org>
Date: Fri Sep 4 03:09:20 2015 +0100
Remove the 8e extra safety margin in COVER_CLIP analysis
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. 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
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 = | d |
| 0 |
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.
** 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
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;
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
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.
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>
Reviewed-by: Siarhei Siamashka <siarhei.siamashka at gmail.com>
Reviewed-by: Ben Avison <bavison at riscosopen.org>
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;
}
More information about the xorg-commit
mailing list