[PATCH 3/3] winex11: Use TINN algorithm to speed up colour lookups.

[Vitaliy Margolen]

Vitaly Budovski wrote:
> Make use of the Triangle Inequality Nearest Neighbour algorithm to find the
> nearest colour more efficiently than a simple linear search. The improvements
> are most noticeable with a palette of 256 colours. Testing shows approximately
> 3-4x performance increase for 256 colours.
> ---

Overall idea looks good, however the big problem with it is use of float
point numbers. Fortunately you can get rid of them and use integers
instead. Because you never use the distance in the calculations, but
only to compare against other distances, you can skip "sqrt" and just
compare squares, as the original code does. That will give you even more
 speed improvements.

Few more nitpicks about this and other patches in the series:
> +static int compare_distance(const void *left, const void *right)
> +{
> +    const struct tinn *l = left;
> +    const struct tinn *r = right;

Please don't use void pointers. Use typed pointers, especially that you
cast them to a hard-coded type.

> +const void *init_tinn(struct tinn *dest, const void *buf, size_t num,
> +    size_t size, float (*distance)(const void *, const void *))
> +{
> +    size_t i;
> +    size_t ref = rand() % num;
I'm not so sure using random reference point really necessary.

> +static struct tinn tinnPalette[256];
> +

This won't work well with multi-threaded apps. You probably should make
it on the stack for each X11DRV_DIB_SetImageBits_* function. Especially
that some need only 2 elements. Btw, how big of the gain/loss whill
there be for 1-bit and 4-bit DIBs?

> +                    q.rgbRed = srcval.peRed;
> +                    q.rgbGreen = srcval.peGreen;
> +                    q.rgbBlue = srcval.peBlue;

Looks much better, if written as:
q = srcval;

> -                                      ((srcval >>  7) & 0xf8) | /* r */
> -                                      ((srcval >> 12) & 0x07),
> -                                      ((srcval >>  2) & 0xf8) | /* g */
> -                                      ((srcval >>  7) & 0x07),
> -                                      ((srcval <<  3) & 0xf8) | /* b */
> -                                      ((srcval >>  2) & 0x07) ) << (7-(x&7)) );
> +
> +                            q.rgbRed = ((srcval >>  7) & 0xf8) |
> +                                ((srcval >> 12) & 0x07);
> +                            q.rgbGreen = ((srcval >>  2) & 0xf8) |
> +                                ((srcval >>  7) & 0x07);
> +                            q.rgbBlue = ((srcval <<  3) & 0xf8) |
> +                                ((srcval >>  2) & 0x07);
What happened to the comments and alignment?

Vitaliy Margolen.