Re: [Pixman] [PATCH v14 16/22] pixman-filter: distribute normalization error over filter

[Bill Spitzak]

On Fri, Mar 18, 2016 at 6:54 PM, Søren Sandmann 
wrote:

> On Sun, Mar 6, 2016 at 8:06 PM,  wrote:
>
>> From: Bill Spitzak 
>>
>> This removes a high-frequency spike in the middle of some filters that is
>> caused by math errors all being in the same direction.
>>
>> Signed-off-by: Bill Spitzak 
>> ---
>>  pixman/pixman-filter.c | 12 +++-
>>  1 file changed, 11 insertions(+), 1 deletion(-)
>>
>> diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
>> index 36dd811..ab62e0a 100644
>> --- a/pixman/pixman-filter.c
>> +++ b/pixman/pixman-filter.c
>> @@ -282,8 +282,18 @@ create_1d_filter (int  width,
>> p[x] = t;
>> }
>>
>> +   /* Distribute any remaining error over all samples */
>> if (new_total != pixman_fixed_1)
>> -   p[width / 2] += (pixman_fixed_1 - new_total);
>> +   {
>> +   pixman_fixed_t delta = new_total - pixman_fixed_1;
>> +   pixman_fixed_t t = 0;
>> +   for (x = 0; x < width; ++x)
>> +   {
>> +   pixman_fixed_t new_t = delta * (x + 1) / width;
>> +   p[x] += new_t - t;
>> +   t = new_t;
>> +   }
>> +   }
>>
>
> I think there is a sign error in this code: delta is new_total - 1, which
> is positive when new_total is bigger than 1. But this positive delta is
> then added to the samples, making the total even bigger.
>

Yes I believe you are right. Looks like my mistake there, and you can see
the other line that this replaces is in the correct direction so I'm not
sure how I managed to do this. This incorrect version still hid the
artifact in the filter (a small dip/spike in the middle of large ones for
sync filters), so I guess I concluded I got it right.

Also, I would write the code like this:
>
> pixman_fixed_t error = pixman_fixed_1 - new_total;
> for (x = 0; x < width; ++x)
> {
> pixman_fixed_t d = error * (x + 1) / width;
> p[x] += d;
> error -= d;
> }
>
> to get rid of the temporary and to make it more obvious that there is an
> error that is being distributed.
>

That will not distribute the error evenly. I could just add
error*(x+1)/width-error*x/width and avoid the temporary entirely, though I
guess there has to be a warning comment that doing the obvious-looking
optimization will make it not work.

>
> Another possibility is to do error diffusion in the /* Normalize */ loop.
>

I don't think that will work because it needs to take into account the
rounding to pixman_fixed_t after the division.

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

Re: [Pixman] [PATCH v14 16/22] pixman-filter: distribute normalization error over filter

[Søren Sandmann]

> Also, I would write the code like this:
>
> pixman_fixed_t error = pixman_fixed_1 - new_total;
> for (x = 0; x < width; ++x)
> {
> pixman_fixed_t d = error * (x + 1) / width;
> p[x] += d;
> error -= d;
> }
>
> to get rid of the temporary and to make it more obvious that there is an
> error that is being distributed.
>

I meant

...
pixman_fixed_t d = error / (width - x);
...

of course, but I guess the rounding-towards-zero behavior of division in C
makes this less desirable since it tends to put all the rounding error
towards one side of the kernel. Rounding-to-nearest would make it similar
to your code:

...
pixman_fixed_t d = DIV(error + (width - x - 1) / 2, width - x)
...

but then it would be slightly cleaner to make the loop count down:

for (x = width; x > 0; --x)
{
pixman_fixed_t d = DIV(error + (x - 1) / 2, x)
p[x] += d;
error -= d;
}


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

Re: [Pixman] [PATCH v14 16/22] pixman-filter: distribute normalization error over filter

[Søren Sandmann]

On Fri, Mar 18, 2016 at 9:54 PM, Søren Sandmann 
wrote:

> On Sun, Mar 6, 2016 at 8:06 PM,  wrote:
>
>> From: Bill Spitzak 
>>
>> This removes a high-frequency spike in the middle of some filters that is
>> caused by math errors all being in the same direction.
>>
>> Signed-off-by: Bill Spitzak 
>> ---
>>  pixman/pixman-filter.c | 12 +++-
>>  1 file changed, 11 insertions(+), 1 deletion(-)
>>
>> diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
>> index 36dd811..ab62e0a 100644
>> --- a/pixman/pixman-filter.c
>> +++ b/pixman/pixman-filter.c
>> @@ -282,8 +282,18 @@ create_1d_filter (int  width,
>> p[x] = t;
>> }
>>
>> +   /* Distribute any remaining error over all samples */
>> if (new_total != pixman_fixed_1)
>> -   p[width / 2] += (pixman_fixed_1 - new_total);
>> +   {
>> +   pixman_fixed_t delta = new_total - pixman_fixed_1;
>> +   pixman_fixed_t t = 0;
>> +   for (x = 0; x < width; ++x)
>> +   {
>> +   pixman_fixed_t new_t = delta * (x + 1) / width;
>> +   p[x] += new_t - t;
>> +   t = new_t;
>> +   }
>> +   }
>>
>
> I think there is a sign error in this code: delta is new_total - 1, which
> is positive when new_total is bigger than 1. But this positive delta is
> then added to the samples, making the total even bigger.
>
> Also, I would write the code like this:
>
> pixman_fixed_t error = pixman_fixed_1 - new_total;
> for (x = 0; x < width; ++x)
> {
> pixman_fixed_t d = error * (x + 1) / width;
> p[x] += d;
> error -= d;
> }
>
> to get rid of the temporary and to make it more obvious that there is an
> error that is being distributed.
>
> Another possibility is to do error diffusion in the /* Normalize */ loop.
>

Also, a test that generates a bunch of filters and verifies that all the
phases sum to 1 would be useful.


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

Re: [Pixman] [PATCH v14 16/22] pixman-filter: distribute normalization error over filter

[Søren Sandmann]

On Sun, Mar 6, 2016 at 8:06 PM,  wrote:

> From: Bill Spitzak 
>
> This removes a high-frequency spike in the middle of some filters that is
> caused by math errors all being in the same direction.
>
> Signed-off-by: Bill Spitzak 
> ---
>  pixman/pixman-filter.c | 12 +++-
>  1 file changed, 11 insertions(+), 1 deletion(-)
>
> diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
> index 36dd811..ab62e0a 100644
> --- a/pixman/pixman-filter.c
> +++ b/pixman/pixman-filter.c
> @@ -282,8 +282,18 @@ create_1d_filter (int  width,
> p[x] = t;
> }
>
> +   /* Distribute any remaining error over all samples */
> if (new_total != pixman_fixed_1)
> -   p[width / 2] += (pixman_fixed_1 - new_total);
> +   {
> +   pixman_fixed_t delta = new_total - pixman_fixed_1;
> +   pixman_fixed_t t = 0;
> +   for (x = 0; x < width; ++x)
> +   {
> +   pixman_fixed_t new_t = delta * (x + 1) / width;
> +   p[x] += new_t - t;
> +   t = new_t;
> +   }
> +   }
>

I think there is a sign error in this code: delta is new_total - 1, which
is positive when new_total is bigger than 1. But this positive delta is
then added to the samples, making the total even bigger.

Also, I would write the code like this:

pixman_fixed_t error = pixman_fixed_1 - new_total;
for (x = 0; x < width; ++x)
{
pixman_fixed_t d = error * (x + 1) / width;
p[x] += d;
error -= d;
}

to get rid of the temporary and to make it more obvious that there is an
error that is being distributed.

Another possibility is to do error diffusion in the /* Normalize */ loop.


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

[Pixman] [PATCH v14 16/22] pixman-filter: distribute normalization error over filter

[spitzak]

From: Bill Spitzak 

This removes a high-frequency spike in the middle of some filters that is
caused by math errors all being in the same direction.

Signed-off-by: Bill Spitzak 
---
 pixman/pixman-filter.c | 12 +++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
index 36dd811..ab62e0a 100644
--- a/pixman/pixman-filter.c
+++ b/pixman/pixman-filter.c
@@ -282,8 +282,18 @@ create_1d_filter (int  width,
p[x] = t;
}
 
+   /* Distribute any remaining error over all samples */
if (new_total != pixman_fixed_1)
-   p[width / 2] += (pixman_fixed_1 - new_total);
+   {
+   pixman_fixed_t delta = new_total - pixman_fixed_1;
+   pixman_fixed_t t = 0;
+   for (x = 0; x < width; ++x)
+   {
+   pixman_fixed_t new_t = delta * (x + 1) / width;
+   p[x] += new_t - t;
+   t = new_t;
+   }
+   }
 
p += width;
 }
-- 
1.9.1

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