[Pixman] [PATCH 2/3] Optimize BILINEAR filter to NEAREST for identity transforms

[Siarhei Siamashka]

On Tue, May 24, 2011 at 7:47 PM, Soeren Sandmann <sandmann at cs.au.dk> wrote:
> Siarhei Siamashka <siarhei.siamashka at gmail.com> writes:
>
>> From: Siarhei Siamashka <siarhei.siamashka at nokia.com>
>>
>> When doing non-transformed composite operations with the source images
>> having BILINEAR filter set, standard fast paths should be still
>> perfectly usable just like for the NEAREST filter case.
>>
>> But because BILINEAR filter samples 2x2 pixel block in the source image
>> for each corresponding destination pixel, FAST_PATH_SAMPLES_COVER_CLIP
>> flag may not be set if the composite operation covers the whole source
>> image including the last pixel in the scanline (the rightmost pixels of
>> the last 2x2 block are considered to be outside of the source image
>> bounds even though they have zero weight for interpolation).
>
> To summarize the issue here, the problematic case is when an image
>
> - has a bilinear filter set
>
> - has a transformation that makes that filter reduce to nearest. (Most
>  importantly, this happens with identity transformations)
>
> - and the area sampled from the image is equal to the image bounds
>
> In this case the standard fast paths would work perfectly well, but we
> can't use them because the analyze_extents() code decides that because
> of the bilinear filter, it won't set the SAMPLES_COVER_CLIP flag.
>
> The problem for the analyze_extents() code is that if it chooses to
> provide the COVER flag, then some code might read common.filter and try
> to read outside the image to do bilinear filtering. But without COVER,
> the standard fast paths won't run.
>
> It seems to me that the cause of the problem is that the meaning of
> COVER depends on what the filter is: it means "there is enough space
> around the sample area for the chosen filter", which then becomes wrong
> when doing filter reductions.

The meaning of COVER flag does not become wrong after doing filter
reduction, it's the "common.filter" variable which gets kind of wrong.
This "common.filter" value means "a filter value set by the user
application via pixman_image_set_filter() call". When no filter
reductions are done, it is also happens to be valid in any part of
code. But no matter what is the name of this filter variable, it needs
to be backed up somewhere just to prevent the following problem:
1. The user sets bilinear filter
2. the user sets identity transform
3. Bilinear filter is optimized to nearest
4. The user tries to set some other transform where the filter does
matter (for example scaling), but we already forgot that the filter
was originally bilinear

Initially I tried to add a new "common.original_filter" variable for
keeping this filter information backup. But after looking at the code
a bit more, just decided that the flags already contain most of the
filter related information and could be perfectly used without
expanding pixman_image_t structure size even by a single bit. So my
proposed patch:
1. Adds only one extra branch just in "compute_image_info" function,
which if i understand it correctly, is lazily called only when
something was updated in the image. So potentially this function may
be called less often than "pixman_image_composite". Additionally this
extra branch is only executed when the filter is originally set to
bilinear (so no overhead for nearest filter at all).
2. Changes "switch" code to "if/else/else" block on a common path. But
at least instead of checking for three possible values like
PIXMAN_FILTER_BILINEAR/PIXMAN_FILTER_GOOD/PIXMAN_FILTER_BEST, just
testing a single bit flag is enough there, which might (or might not)
make the code even faster. So this does not look like a bad
replacement.

A subjective advantage is that it also gets rid of a somewhat
illogical NO_CONVOLUTION_FILTER flag. This flag does not cause any
problems itself, but just distracts attention when looking at the
printout of fast path flags.

Regarding the potential risk of using "common.filter" accidentally in
a wrong way, I think that this variable can be just renamed and get an
unattractive discouraging name, maybe something like
"common.filter_before_optimization". Also for additional safety and
debugging purposes, maybe even valgrind client requests could be used
to mark this variable as unaccessible at the wrong time in a special
debug configuration, but that could be an overkill.

> So maybe a solution would be to provide two separate flags:
>
>        COVER_NEAREST:  "there is enough space for a nearest filter"
>        COVER_BILINEAR: "there is enough space for a bilinear filter"
>
> These are unambiguous and because either there is enough space for a
> bilinear filter, or there isn't, they can be set independently of what
> the filter actually is.

Sure, it's one of the multiple possible options. But I think that
evaluating and potentially setting both of these flags may introduce a
bit more overhead on the common code path. Also it still may be a good
idea to divide responsibilities between different parts of the
library, optimize the filter early enough and let the rest of code not
to deal with extra flags and just forget that this filter reduction
optimization even happened. After all, cairo already does filter
reduction optimization itself, and nobody complained about the
original filter information not reaching pixman fast path functions ;)

> Code that currently depends on COVER generally also depends on filter,
> at least implicitly, so there shouldn't be any problem picking the
> correct version of COVER for existing fast paths.
>
> This would solve the problem because in the problematic case, the flags
> FILTER_NEAREST | COVER_NEAREST could be set, and the standard fast paths
> would run, but at the same time, bilinear/cover paths wouldn't be
> triggered because they would require FILTER_BILINEAR | COVER_BILINEAR.
>
> As a side effect, this also means we can drop the code that worries
> about what covering means when there is a convolution filter.

Do you mean this code?
    http://cgit.freedesktop.org/pixman/tree/pixman/pixman.c?id=pixman-0.22.0#n593
I think we can freely drop it with or without such change, and nothing
bad would really happen if FAST_PATH_SAMPLES_COVER_CLIP would not be
set when convolution filter is in use. Except that the interpretation
of flags may be changed a bit.

-- 
Best regards,
Siarhei Siamashka