[babl] palette: optimize rgb(a) -> palette index computation

[Ãyvind KolÃs <ok src gnome org>]

commit 3246212471a8841e2c9de2ea50904749727f3dbc
Author: Ãyvind KolÃs <pippin gimp org>
Date:   Mon Mar 19 02:55:32 2012 +0000

    palette: optimize rgb(a) -> palette index computation

 babl/babl-palette.c |  261 +++++++++++++++++++++++++++++++++++++++++----------
 1 files changed, 210 insertions(+), 51 deletions(-)
---
diff --git a/babl/babl-palette.c b/babl/babl-palette.c
index 48f0192..961e52a 100644
--- a/babl/babl-palette.c
+++ b/babl/babl-palette.c
@@ -19,26 +19,107 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
+#include <values.h>
 #include <assert.h>
 #include "babl.h"
 #include "babl-memory.h"
 
+#define HASH_TABLE_SIZE 1111
+
 void babl_sanity (void);
 
+/* A default palette, containing standard ANSI / EGA colors
+ *
+ */
+static unsigned char defpal_data[4*16] = 
+{  
+0  ,0  ,0  ,255,
+127,0  ,0  ,255,
+0  ,127,0  ,255,
+127,127,0  ,255,
+0  ,0  ,127,255,
+127,0  ,127,255,
+0  ,127,127,255,
+127,127,127,255,
+63 ,63 ,63 ,255,
+255,0  ,0  ,255,
+0  ,255,0  ,255,
+255,255,0  ,255,
+0  ,0  ,255,255,
+255,0  ,255,255,
+0  ,255,255,255,
+255,255,255,255,
+};
+static double defpal_double[4*8*16];
+
+
 typedef struct BablPalette
 {
   int         count; /* number of palette entries */
   const Babl *format;/* the pixel format the palette is stored in */
-  void       *data;  /* one linear segment of all the pixels representing the palette, in   order */
-  void       *data_double;
-  void       *data_u8;
+  unsigned char *data;  /* one linear segment of all the pixels representing the palette, in   order */
+  double        *data_double;
+  unsigned char *data_u8;
+  int          hash[HASH_TABLE_SIZE];
+  unsigned int hashpx[HASH_TABLE_SIZE];
 } BablPalette;
 
+static void
+babl_palette_reset_hash (BablPalette *pal)
+{
+  int i;
+  for (i = 0; i < HASH_TABLE_SIZE; i++)
+    {
+      pal->hashpx[i] = ((255 << 16) | (255 << 8) | 255) + 11; /* non existant pixel */
+      pal->hash[i] = -1;
+    }
+}
+
+static int
+babl_palette_lookup (BablPalette *pal, int r, int g, int b, int a)
+{
+  unsigned int pixel      = (r << 16) | (g << 8) | b;
+  int          hash_index = pixel % HASH_TABLE_SIZE;
+  int          idx = pal->hash[hash_index];
+  
+  if (idx >= 0 &&
+      pal->hashpx[hash_index] == pixel)
+    {
+      return idx;
+    }
+  else
+    {
+      int best_idx = 0;
+      int best_diff = MAXINT;
+
+      for (idx = 0; idx < pal->count; idx++)
+        {
+          unsigned char *palpx = pal->data_u8 + idx * 4;
+          int pr = palpx[0];
+          int pg = palpx[1];
+          int pb = palpx[2];
+
+          int diff = (r - pr) * (r - pr) +
+                     (g - pg) * (g - pg) +
+                     (b - pb) * (b - pb);
+          if (diff < best_diff)
+            {
+              best_diff = diff;
+              best_idx  = idx;
+            }
+        }
+      pal->hash[hash_index] = best_idx;
+      pal->hashpx[hash_index] = pixel;
+      return best_idx;
+    }
+  return 0;
+}
 
 static BablPalette *make_pal (const Babl *format, const void *data, int count)
 {
   BablPalette *pal = NULL;
   int bpp = babl_format_get_bytes_per_pixel (format);
+
   pal = babl_malloc (sizeof (BablPalette));
   pal->count = count;
   pal->format = format;
@@ -46,10 +127,14 @@ static BablPalette *make_pal (const Babl *format, const void *data, int count)
   pal->data_double = babl_malloc (4 * sizeof(double) * count);
   pal->data_u8 = babl_malloc (4 * sizeof(char) * count);
   memcpy (pal->data, data, bpp * count);
+
   babl_process (babl_fish (format, babl_format ("RGBA double")),
-                pal->data, pal->data_double, count);
+                data, pal->data_double, count);
   babl_process (babl_fish (format, babl_format ("RGBA u8")),
-                pal->data, pal->data_u8, count);
+                data, pal->data_u8, count);
+
+  babl_palette_reset_hash (pal);
+
   return pal;
 }
 
@@ -61,36 +146,13 @@ static void babl_palette_free (BablPalette *pal)
   babl_free (pal);
 }
 
-/* A default palette, containing standard ANSI / EGA colors
- *
- */
-static unsigned char defpal_data[4*16] = 
-{  
-0  ,0  ,0  ,255,
-127,0  ,0  ,255,
-0  ,127,0  ,255,
-127,127,0  ,255,
-0  ,0  ,127,255,
-127,0  ,127,255,
-0  ,127,127,255,
-127,127,127,255,
-63 ,63 ,63 ,255,
-255,0  ,0  ,255,
-0  ,255,0  ,255,
-255,255,0  ,255,
-0  ,0  ,255,255,
-255,0  ,255,255,
-0  ,255,255,255,
-255,255,255,255,
-};
-static double defpal_double[4*8*16];
-
 static BablPalette *default_palette (void)
 {
   static BablPalette pal;
   static int inited = 0;
   if (inited)
     return &pal;
+  memset (&pal, 0, sizeof (pal));
   inited = 1;
   pal.count = 16;
   pal.format = babl_format ("RGBA u8"); /* dynamically generated, so
@@ -103,6 +165,8 @@ static BablPalette *default_palette (void)
 
   babl_process (babl_fish (pal.format, babl_format ("RGBA double")),
                 pal.data, pal.data_double, pal.count);
+
+  babl_palette_reset_hash (&pal);
   return &pal;
 }
 
@@ -220,6 +284,80 @@ pal_to_rgba (char *src,
 }
 
 static long
+pala_to_rgba (char *src,
+              char *dst,
+              long  n,
+              void *src_model_data)
+{
+  BablPalette **palptr = src_model_data;
+  BablPalette *pal = *palptr;
+
+  assert(pal);
+  while (n--)
+    {
+      int idx      = (((double *) src)[0]) * 255.5;
+      double alpha = (((double *) src)[1]);
+      double *palpx;
+
+      if (idx < 0) idx = 0;
+      if (idx >= pal->count) idx = pal->count-1;
+
+      palpx = ((double *)pal->data_double) + idx * 4;
+      memcpy (dst, palpx, sizeof(double)*4);
+
+      ((double *)dst)[3] *= alpha; 
+
+      src += sizeof (double) * 2;
+      dst += sizeof (double) * 4;
+    }
+  return n;
+}
+
+static long
+rgba_u8_to_pal (unsigned char *src,
+                unsigned char *dst,
+                long  n,
+                void *src_model_data)
+{
+  BablPalette **palptr = src_model_data;
+  BablPalette *pal;
+  assert (palptr);
+  pal = *palptr;
+  assert(pal);
+  while (n--)
+    {
+      dst[0] = babl_palette_lookup (pal, src[0], src[1], src[2], src[3]);
+
+      src += sizeof (char) * 4;
+      dst += sizeof (char) * 1;
+    }
+
+  return n;
+}
+
+static long
+rgba_u8_to_pal_a (char *src,
+                  char *dst,
+                  long  n,
+                  void *src_model_data)
+{
+  BablPalette **palptr = src_model_data;
+  BablPalette *pal;
+  assert (palptr);
+  pal = *palptr;
+  assert(pal);
+  while (n--)
+    {
+      dst[0] = babl_palette_lookup (pal, src[0], src[1], src[2], src[3]);
+      dst[1] = src[3];
+
+      src += sizeof (char) * 4;
+      dst += sizeof (char) * 2;
+    }
+  return n;
+}
+
+static long
 pal_u8_to_rgba_u8 (char *src,
                    char *dst,
                    long  n,
@@ -248,35 +386,35 @@ pal_u8_to_rgba_u8 (char *src,
 }
 
 static long
-pala_to_rgba (char *src,
-              char *dst,
-              long  n,
-              void *src_model_data)
+pala_u8_to_rgba_u8 (char *src,
+                    char *dst,
+                    long  n,
+                    void *src_model_data)
 {
   BablPalette **palptr = src_model_data;
-  BablPalette *pal = *palptr;
-
+  BablPalette *pal;
+  assert (palptr);
+  pal = *palptr;
   assert(pal);
   while (n--)
     {
-      int idx      = (((double *) src)[0]) * 255.5;
-      double alpha = (((double *) src)[1]);
-      double *palpx;
+      int idx = (((unsigned char *) src)[0]);
+      unsigned char *palpx;
 
       if (idx < 0) idx = 0;
       if (idx >= pal->count) idx = pal->count-1;
 
-      palpx = ((double *)pal->data_double) + idx * 4;
-      memcpy (dst, palpx, sizeof(double)*4);
-
-      ((double *)dst)[3] *= alpha; 
+      palpx = ((unsigned char*)pal->data_u8) + idx * 4;
+      memcpy (dst, palpx, sizeof(char)*4);
+      dst[3] = (dst[3] * src[1]) >> 8;
 
-      src += sizeof (double) * 2;
-      dst += sizeof (double) * 4;
+      src += sizeof (char) * 2;
+      dst += sizeof (char) * 4;
     }
   return n;
 }
 
+
 #include "base/util.h"
 
 static inline long
@@ -382,6 +520,13 @@ void babl_new_palette (const char *name, const Babl **format_u8,
      "data", palptr,
      NULL
   );
+  babl_conversion_new (
+     babl_model ("RGBA"),
+     model_no_alpha,
+     "linear", rgba_to_pal,
+     "data", palptr,
+     NULL
+  );
 
   babl_conversion_new (
      f_pal_u8,
@@ -397,13 +542,6 @@ void babl_new_palette (const char *name, const Babl **format_u8,
      NULL
   );
 
-  babl_conversion_new (
-     babl_model ("RGBA"),
-     model_no_alpha,
-     "linear", rgba_to_pal,
-     "data", palptr,
-     NULL
-  );
 
   babl_conversion_new (
      f_pal_u8,
@@ -412,6 +550,27 @@ void babl_new_palette (const char *name, const Babl **format_u8,
      "data", palptr,
      NULL);
 
+
+  babl_conversion_new (
+     f_pal_a_u8,
+     babl_format ("RGBA u8"),
+     "linear", pala_u8_to_rgba_u8,
+     "data", palptr,
+     NULL);
+
+  babl_conversion_new (
+     babl_format ("RGBA u8"),
+     f_pal_a_u8,
+     "linear", rgba_u8_to_pal_a,
+     "data", palptr,
+     NULL);
+  babl_conversion_new (
+     babl_format ("RGBA u8"),
+     f_pal_u8,
+     "linear", rgba_u8_to_pal,
+     "data", palptr,
+     NULL);
+
   babl_set_user_data (model, palptr);
   babl_set_user_data (model_no_alpha, palptr);