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.