Re: [Pixman] [PATCH 2/2] More general BILINEAR=>NEAREST reduction

[Bill Spitzak]

Seems correct and gets more cases than my code did (I was assuming nobody
would use bilinear for scales less than 1/2 so I did not check for it).
Minor comments:

On Mon, Mar 14, 2016 at 11:19 PM, Søren Sandmann Pedersen <
soren.sandm...@gmail.com> wrote:

> Generalize and simplify the code that reduces BILINEAR to NEAREST so
> that all the reduction happens for all affine transformations where
> t00..t22 are integers and (t00 + t01) and (t10 + t11) are both
> odd. This is a sufficient condition for the resulting transformed
> coordinates being exactly at the center of a pixel so that BILINEAR
> becomes identical to NEAREST.
>

Actually the last row (t20, t21, t22) has to be 0,0,1 (or 0,0,w where you
then make a new matrix that divides everything by w and then it is 0,0,1).
This is already tested for by the test for AFFINE, but this comment is a
bit incorrect.


>
> Signed-off-by: Søren Sandmann 
> ---
>  pixman/pixman-image.c | 69
> ++-
>  1 file changed, 41 insertions(+), 28 deletions(-)
>
> diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
> index 1ff1a49..cff8a30 100644
> --- a/pixman/pixman-image.c
> +++ b/pixman/pixman-image.c
> @@ -335,37 +335,50 @@ compute_image_info (pixman_image_t *image)
> {
> flags |= FAST_PATH_NEAREST_FILTER;
> }
> -   else if (
> -   /* affine and integer translation components in matrix ... */
> -   ((flags & FAST_PATH_AFFINE_TRANSFORM) &&
> -!pixman_fixed_frac (image->common.transform->matrix[0][2] |
> -image->common.transform->matrix[1][2])) &&
> -   (
> -   /* ... combined with a simple rotation */
> -   (flags & (FAST_PATH_ROTATE_90_TRANSFORM |
> - FAST_PATH_ROTATE_180_TRANSFORM |
> - FAST_PATH_ROTATE_270_TRANSFORM)) ||
> -   /* ... or combined with a simple non-rotated translation */
> -   (image->common.transform->matrix[0][0] == pixman_fixed_1 &&
> -image->common.transform->matrix[1][1] == pixman_fixed_1 &&
> -image->common.transform->matrix[0][1] == 0 &&
> -image->common.transform->matrix[1][0] == 0)
> -   )
> -   )
> +   else if (flags & FAST_PATH_AFFINE_TRANSFORM)
> {
> -   /* FIXME: there are some affine-test failures, showing that
> -* handling of BILINEAR and NEAREST filter is not quite
> -* equivalent when getting close to 32K for the translation
> -* components of the matrix. That's likely some bug, but for
> -* now just skip BILINEAR->NEAREST optimization in this case.
> +   /* Suppose the transform is
> +*
> +*[ t00, t01, t02 ]
> +*[ t10, t11, t12 ]
> +*[ 120, t21, t22 ]
>

typo 120->t20. I would change the last row to just read [0,0,1] as you are
assuming this and not using these values in the following equation.


> +*
> +* and the destination coordinates are (n + 0.5, m + 0.5). Then
> +* the transformed x coordinate is:
> +*
> +* tx = t00 * (n + 0.5) + t01 * (m + 0.5) + t02
> +*= t00 * n + t01 * m + t02 + (t00 + t01) * 0.5
>

I would use u,v rather than tx,ty for the source coordinates. More complex
analysis of transforms gets very hard to read unless the variables are kept
to one letter.

+* which implies that if t00, t01 and t02 are all integers
> +* and (t00 + t01) is odd, then tx will be an integer plus 0.5,
> +* which means a BILINEAR filter will reduce to NEAREST. The
> same
> +* applies in the y direction
>  */
> -   pixman_fixed_t magic_limit = pixman_int_to_fixed (3);
> -   if (image->common.transform->matrix[0][2] <= magic_limit  &&
> -   image->common.transform->matrix[1][2] <= magic_limit  &&
> -   image->common.transform->matrix[0][2] >= -magic_limit &&
> -   image->common.transform->matrix[1][2] >= -magic_limit)
> +   pixman_fixed_t (*t)[3] = image->common.transform->matrix;
> +
> +   if (pixman_fixed_frac (t[0][0]) == 0
>  &&
> +   pixman_fixed_frac (t[0][1]) == 0
>  &&
> +   pixman_fixed_frac (t[0][2]) == 0
>  &&
> +   ((t[0][0] + t[0][1]) & pixman_fixed_1) == pixman_fixed_1
>  &&
> +   pixman_fixed_frac (t[1][0]) == 0
>  &&
> +   pixman_fixed_frac (t[1][1]) == 0
>  &&
> +   pixman_fixed_frac (t[1][2]) == 0
>  &&
> +   ((t[1][0] + t[1][1]) & pixman_fixed_1) == pixman_fixed_1)
>

You can or all the numbers together to test they are all integers in one
step.


> {
> -   flags |= FAST_PATH_NEAREST_FILTER;
> +   /* FIXME: there are some 

Re: [Pixman] [PATCH 1/2] Add new test of filter reduction from BILINEAR to NEAREST

[Bill Spitzak]

Great idea to test this.

On Mon, Mar 14, 2016 at 11:24 PM, Søren Sandmann 
wrote:

> diff --git a/test/filter-reduction-test.c b/test/filter-reduction-test.c
>
>> new file mode 100644
>> index 000..72b3142
>> --- /dev/null
>> +++ b/test/filter-reduction-test.c
>> @@ -0,0 +1,119 @@
>> +/*
>> + * Test program, which can detect some problems with nearest neighbour
>> + * and bilinear scaling in pixman. Testing is done by running lots
>> + * of random SRC and OVER compositing operations a8r8g8b8, x8a8r8g8b8
>> + * and r5g6b5 color formats.
>> + *
>> + * Script 'fuzzer-find-diff.pl' can be used to narrow down the problem
>> in
>> + * the case of test failure.
>> + */
>>
>
> This comment is of course a leftover due to starting from a copy of
> scaling-test.c.
>
>
> Søren
>
> ___
> Pixman mailing list
> Pixman@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/pixman
>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

Re: [Pixman] [PATCH 1/2] Add new test of filter reduction from BILINEAR to NEAREST

[Søren Sandmann]

diff --git a/test/filter-reduction-test.c b/test/filter-reduction-test.c

> new file mode 100644
> index 000..72b3142
> --- /dev/null
> +++ b/test/filter-reduction-test.c
> @@ -0,0 +1,119 @@
> +/*
> + * Test program, which can detect some problems with nearest neighbour
> + * and bilinear scaling in pixman. Testing is done by running lots
> + * of random SRC and OVER compositing operations a8r8g8b8, x8a8r8g8b8
> + * and r5g6b5 color formats.
> + *
> + * Script 'fuzzer-find-diff.pl' can be used to narrow down the problem in
> + * the case of test failure.
> + */
>

This comment is of course a leftover due to starting from a copy of
scaling-test.c.


Søren
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

[Pixman] [PATCH 1/2] Add new test of filter reduction from BILINEAR to NEAREST

[Søren Sandmann Pedersen]

This new test tests a bunch of bilinear downscalings, where many have
a transformation such that the BILINEAR filter can be reduced to
NEAREST (and many don't).

A CRC32 is computed for all the resulting images and compared to a
known-good value for both 4-bit and 7-bit interpolation.

Signed-off-by: Søren Sandmann 
---
 test/Makefile.sources|   1 +
 test/filter-reduction-test.c | 119 +++
 2 files changed, 120 insertions(+)
 create mode 100644 test/filter-reduction-test.c

diff --git a/test/Makefile.sources b/test/Makefile.sources
index 5d55e67..0a56231 100644
--- a/test/Makefile.sources
+++ b/test/Makefile.sources
@@ -21,6 +21,7 @@ TESTPROGRAMS =  \
gradient-crash-test   \
pixel-test\
matrix-test   \
+   filter-reduction-test \
composite-traps-test  \
region-contains-test  \
glyph-test\
diff --git a/test/filter-reduction-test.c b/test/filter-reduction-test.c
new file mode 100644
index 000..72b3142
--- /dev/null
+++ b/test/filter-reduction-test.c
@@ -0,0 +1,119 @@
+/*
+ * Test program, which can detect some problems with nearest neighbour
+ * and bilinear scaling in pixman. Testing is done by running lots
+ * of random SRC and OVER compositing operations a8r8g8b8, x8a8r8g8b8
+ * and r5g6b5 color formats.
+ *
+ * Script 'fuzzer-find-diff.pl' can be used to narrow down the problem in
+ * the case of test failure.
+ */
+#include 
+#include 
+#include "utils.h"
+
+static const pixman_fixed_t entries[] =
+{
+pixman_double_to_fixed (-1.0),
+pixman_double_to_fixed (-0.5),
+pixman_double_to_fixed (-1/3.0),
+pixman_double_to_fixed (0.0),
+pixman_double_to_fixed (0.5),
+pixman_double_to_fixed (1.0),
+pixman_double_to_fixed (1.5),
+pixman_double_to_fixed (2.0),
+pixman_double_to_fixed (3.0),
+};
+
+#define SIZE 12
+
+static uint32_t
+test_scale (const pixman_transform_t *xform, uint32_t crc)
+{
+uint32_t *srcbuf, *dstbuf;
+pixman_image_t *src, *dest;
+
+srcbuf = malloc (SIZE * SIZE * 4);
+prng_randmemset (srcbuf, SIZE * SIZE * 4, 0);
+src = pixman_image_create_bits (PIXMAN_a8r8g8b8, SIZE, SIZE, srcbuf, SIZE 
* 4);
+
+dstbuf = malloc (SIZE * SIZE * 4);
+prng_randmemset (dstbuf, SIZE * SIZE * 4, 0);
+dest = pixman_image_create_bits (PIXMAN_a8r8g8b8, SIZE, SIZE, dstbuf, SIZE 
* 4);
+
+pixman_image_set_transform (src, xform);
+pixman_image_set_repeat (src, PIXMAN_REPEAT_NORMAL);
+pixman_image_set_filter (src, PIXMAN_FILTER_BILINEAR, NULL, 0);
+
+image_endian_swap (src);
+image_endian_swap (dest);
+
+pixman_image_composite (PIXMAN_OP_SRC,
+   src, NULL, dest,
+   0, 0, 0, 0, 0, 0,
+   SIZE, SIZE);
+
+crc = compute_crc32_for_image (crc, dest);
+
+pixman_image_unref (src);
+pixman_image_unref (dest);
+
+free (srcbuf);
+free (dstbuf);
+
+return crc;
+}
+
+#if BILINEAR_INTERPOLATION_BITS == 7
+#define CHECKSUM 0x40BDEAC4
+#elif BILINEAR_INTERPOLATION_BITS == 4
+#define CHECKSUM 0xF8245E72
+#else
+#define CHECKSUM 0x
+#endif
+
+int
+main (int argc, const char *argv[])
+{
+const pixman_fixed_t *end = entries + ARRAY_LENGTH (entries);
+const pixman_fixed_t *t0, *t1, *t2, *t3, *t4, *t5;
+uint32_t crc = 0;
+
+prng_srand (0xcafebabe);
+
+for (t0 = entries; t0 < end; ++t0)
+{
+   for (t1 = entries; t1 < end; ++t1)
+   {
+   for (t2 = entries; t2 < end; ++t2)
+   {
+   for (t3 = entries; t3 < end; ++t3)
+   {
+   for (t4 = entries; t4 < end; ++t4)
+   {
+   for (t5 = entries; t5 < end; ++t5)
+   {
+   pixman_transform_t xform = {
+   { { *t0, *t1, *t2 },
+ { *t3, *t4, *t5 },
+ { 0, 0, pixman_fixed_1 } }
+   };
+
+   crc = test_scale (, crc);
+   }
+   }
+   }
+   }
+   }
+}
+
+if (crc != CHECKSUM)
+{
+   printf ("filter-reduction-test failed! (checksum=%08X, expected 
%08X)\n", crc, CHECKSUM);
+   return 1;
+}
+else
+{
+   printf ("filter-reduction-test passed (checksum=%08X)\n", crc);
+   return 0;
+}
+}
-- 
1.7.11.7

___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

[Pixman] More general BILINEAR to NEAREST reduction

[Søren Sandmann Pedersen]

The following two patches generalize the reduction of BILINEAR to
NEAREST based on the formula mentioned here:

  https://lists.freedesktop.org/archives/pixman/2010-August/000321.html


Søren

___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman