X-Git-Url: http://git.imager.perl.org/imager.git/blobdiff_plain/a659442a40580d9c53e6ee52e9941560b53fb709..07d3b409edb813475ece1599b4d722a541a96ec2:/quant.c

diff --git a/quant.c b/quant.c
index 51524cd5..14b97fa7 100644
--- a/quant.c
+++ b/quant.c
@@ -2,10 +2,16 @@
    currently only used by gif.c, but maybe we'll support producing 
    8-bit (or bigger indexed) png files at some point
 */
-#include "image.h"
+#include "imager.h"
+#include "imageri.h"
 
+static void makemap_webmap(i_quantize *);
 static void makemap_addi(i_quantize *, i_img **imgs, int count);
 static void makemap_mediancut(i_quantize *, i_img **imgs, int count);
+static void makemap_mono(i_quantize *);
+static void makemap_gray(i_quantize *, int step);
+
+static int makemap_palette(i_quantize *, i_img **imgs, int count);
 
 static
 void
@@ -26,8 +32,20 @@ setcol(i_color *cl,unsigned char r,unsigned char g,unsigned char b,unsigned char
    handle multiple colour maps.
 */
 
+/*
+=item i_quant_makemap(C<quant>, C<imgs>, C<count>)
+
+=category Image quantization
+
+Analyzes the C<count> images in C<imgs> according to the rules in
+C<quant> to build a color map (optimal or not depending on
+C<< quant->make_colors >>).
+
+=cut
+*/
+
 void
-quant_makemap(i_quantize *quant, i_img **imgs, int count) {
+i_quant_makemap(i_quantize *quant, i_img **imgs, int count) {
 
   if (quant->translate == pt_giflib) {
     /* giflib does it's own color table generation */
@@ -44,21 +62,29 @@ quant_makemap(i_quantize *quant, i_img **imgs, int count) {
     /* use user's specified map */
     break;
   case mc_web_map:
-    {
-      int r, g, b;
-      int i = 0;
-      for (r = 0; r < 256; r+=0x33)
-	for (g = 0; g < 256; g+=0x33)
-	  for (b = 0; b < 256; b += 0x33)
-	    setcol(quant->mc_colors+i++, r, g, b, 255);
-      quant->mc_count = i;
-    }
+    makemap_webmap(quant);
     break;
 
   case mc_median_cut:
     makemap_mediancut(quant, imgs, count);
     break;
 
+  case mc_mono:
+    makemap_mono(quant);
+    break;
+
+  case mc_gray:
+    makemap_gray(quant, 1);
+    break;
+
+  case mc_gray4:
+    makemap_gray(quant, 85);
+    break;
+
+  case mc_gray16:
+    makemap_gray(quant, 17);
+    break;
+
   case mc_addi:
   default:
     makemap_addi(quant, imgs, count);
@@ -70,13 +96,29 @@ static void translate_closest(i_quantize *, i_img *, i_palidx *);
 static void translate_errdiff(i_quantize *, i_img *, i_palidx *);
 static void translate_addi(i_quantize *, i_img *, i_palidx *);
 
-/* Quantize the image given the palette in quant.
+/*
+=item i_quant_translate(C<quant>, C<img>)
+
+=category Image quantization
+
+Quantize the image given the palette in C<quant>.
+
+On success returns a pointer to a memory block of C<< img->xsize *
+img->ysize >> C<i_palidx> entries.
 
-   The giflib quantizer ignores the palette.
+On failure returns NULL.
+
+You should call myfree() on the returned block when you're done with
+it.
+
+This function will fail if the supplied palette contains no colors.
+
+=cut
 */
-i_palidx *quant_translate(i_quantize *quant, i_img *img) {
+i_palidx *
+i_quant_translate(i_quantize *quant, i_img *img) {
   i_palidx *result;
-  int bytes;
+  size_t bytes;
 
   mm_log((1, "quant_translate(quant %p, img %p)\n", quant, img));
 
@@ -189,9 +231,12 @@ eucl_d_ch(cvec* cv,i_sample_t *chans) {
     + PWR2(cv->b - chans[2]);
 }
 
-static
-int
-ceucl_d(i_color *c1, i_color *c2) { return PWR2(c1->channel[0]-c2->channel[0])+PWR2(c1->channel[1]-c2->channel[1])+PWR2(c1->channel[2]-c2->channel[2]); }
+static int
+ceucl_d(i_color *c1, i_color *c2) {
+return PWR2(c1->channel[0]-c2->channel[0])
+  +PWR2(c1->channel[1]-c2->channel[1])
+  +PWR2(c1->channel[2]-c2->channel[2]);
+}
 
 static const int
 gray_samples[] = { 0, 0, 0 };
@@ -251,17 +296,21 @@ for each side of the cube, but this will require even more memory.
 static void
 makemap_addi(i_quantize *quant, i_img **imgs, int count) {
   cvec *clr;
-  int cnum, i, x, y, bst_idx=0, ld, cd, iter, currhb, img_num;
+  int cnum, i, bst_idx=0, ld, cd, iter, currhb, img_num;
+  i_img_dim x, y;
   i_sample_t *val;
   float dlt, accerr;
   hashbox *hb;
   i_mempool mp;
-  int maxwidth = 0;
+  i_img_dim maxwidth = 0;
   i_sample_t *line;
   const int *sample_indices;
 
   mm_log((1, "makemap_addi(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", 
           quant, quant->mc_count, quant->mc_colors, imgs, count));
+
+  if (makemap_palette(quant, imgs, count))
+    return;
          
   i_mempool_init(&mp);
 
@@ -409,6 +458,8 @@ makemap_addi(i_quantize *quant, i_img **imgs, int count) {
 #endif
 
   i_mempool_destroy(&mp);
+
+  mm_log((1, "makemap_addi() - %d colors\n", quant->mc_count));
 }
 
 typedef struct {
@@ -434,7 +485,7 @@ typedef struct {
   i_sample_t max[3]; /* maximum for each channel */
   i_sample_t width[3]; /* width for each channel */
   int start, size;   /* beginning and size of the partition */
-  int pixels; /* number of pixels represented by this partition */
+  i_img_dim pixels; /* number of pixels represented by this partition */
 } medcut_partition;
 
 /*
@@ -500,11 +551,11 @@ static void
 makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
   quant_color_entry *colors;
   i_mempool mp;
-  int imgn, x, y, i, ch;
-  int max_width;
+  int imgn, i, ch;
+  i_img_dim x, y, max_width;
   i_color *line;
   int color_count;
-  int total_pixels;
+  i_img_dim total_pixels;
   medcut_partition *parts;
   int part_num;
   int in, out;
@@ -512,7 +563,11 @@ makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
      this isn't terribly efficient, but it should work */
   int chan_count; 
 
-  /*printf("images %d  pal size %d\n", count, quant->mc_size);*/
+  mm_log((1, "makemap_mediancut(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", 
+          quant, quant->mc_count, quant->mc_colors, imgs, count));
+
+  if (makemap_palette(quant, imgs, count))
+    return;
 
   i_mempool_init(&mp);
 
@@ -588,7 +643,8 @@ makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
     color_count = 1;
     
     while (color_count < quant->mc_size) {
-      int max_index, max_ch; /* index/channel with biggest spread */
+      /* initialized to avoid compiler warnings */
+      int max_index = 0, max_ch = 0; /* index/channel with biggest spread */
       int max_size;
       medcut_partition *workpart;
       int cum_total;
@@ -666,6 +722,140 @@ makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
   }
   /*printf("out %d colors\n", quant->mc_count);*/
   i_mempool_destroy(&mp);
+
+  mm_log((1, "makemap_mediancut() - %d colors\n", quant->mc_count));
+}
+
+static void
+makemap_mono(i_quantize *quant) {
+  quant->mc_colors[0].rgba.r = 0;
+  quant->mc_colors[0].rgba.g = 0;
+  quant->mc_colors[0].rgba.b = 0;
+  quant->mc_colors[0].rgba.a = 255;
+  quant->mc_colors[1].rgba.r = 255;
+  quant->mc_colors[1].rgba.g = 255;
+  quant->mc_colors[1].rgba.b = 255;
+  quant->mc_colors[1].rgba.a = 255;
+  quant->mc_count = 2;
+}
+
+static void
+makemap_gray(i_quantize *quant, int step) {
+  int gray = 0;
+  int i = 0;
+
+  while (gray < 256) {
+    setcol(quant->mc_colors+i, gray, gray, gray, 255);
+    ++i;
+    gray += step;
+  }
+  quant->mc_count = i;
+}
+
+static void
+makemap_webmap(i_quantize *quant) {
+  int r, g, b;
+
+  int i = 0;
+  for (r = 0; r < 256; r+=0x33)
+    for (g = 0; g < 256; g+=0x33)
+      for (b = 0; b < 256; b += 0x33)
+	setcol(quant->mc_colors+i++, r, g, b, 255);
+  quant->mc_count = i;
+}
+
+static int 
+in_palette(i_color *c, i_quantize *quant, int size) {
+  int i;
+
+  for (i = 0; i < size; ++i) {
+    if (c->channel[0] == quant->mc_colors[i].channel[0]
+        && c->channel[1] == quant->mc_colors[i].channel[1]
+        && c->channel[2] == quant->mc_colors[i].channel[2]) {
+      return i;
+    }
+  }
+
+  return -1;
+}
+
+/*
+=item makemap_palette(quant, imgs, count)
+
+Tests if all the given images are paletted and have a common palette,
+if they do it builds that palette.
+
+A possible improvement might be to eliminate unused colors in the
+images palettes.
+
+=cut
+*/
+
+static int
+makemap_palette(i_quantize *quant, i_img **imgs, int count) {
+  int size = quant->mc_count;
+  int i;
+  int imgn;
+  char used[256];
+  int col_count;
+
+  mm_log((1, "makemap_palette(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n", 
+          quant, quant->mc_count, quant->mc_colors, imgs, count));
+  /* we try to build a common palette here, if we can manage that, then
+     that's the palette we use */
+  for (imgn = 0; imgn < count; ++imgn) {
+    int eliminate_unused;
+    if (imgs[imgn]->type != i_palette_type) {
+      mm_log((1, "makemap_palette() -> 0 (non-palette image)\n"));
+      return 0;
+    }
+
+    if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0, 
+                        &eliminate_unused)) {
+      eliminate_unused = 1;
+    }
+
+    if (eliminate_unused) {
+      i_palidx *line = mymalloc(sizeof(i_palidx) * imgs[imgn]->xsize);
+      i_img_dim x, y;
+      memset(used, 0, sizeof(used));
+
+      for (y = 0; y < imgs[imgn]->ysize; ++y) {
+        i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line);
+        for (x = 0; x < imgs[imgn]->xsize; ++x)
+          used[line[x]] = 1;
+      }
+
+      myfree(line);
+    }
+    else {
+      /* assume all are in use */
+      memset(used, 1, sizeof(used));
+    }
+
+    col_count = i_colorcount(imgs[imgn]);
+    for (i = 0; i < col_count; ++i) {
+      i_color c;
+      
+      i_getcolors(imgs[imgn], i, &c, 1);
+      if (used[i]) {
+        if (in_palette(&c, quant, size) < 0) {
+          if (size < quant->mc_size) {
+            quant->mc_colors[size++] = c;
+          }
+          else {
+	    mm_log((1, "makemap_palette() -> 0 (too many colors)\n"));
+            return 0;
+          }
+        }
+      }
+    }
+  }
+
+  mm_log((1, "makemap_palette() -> 1 (%d total colors)\n", size));
+  quant->mc_count = size;
+
+  return 1;
 }
 
 #define pboxjump 32
@@ -707,6 +897,23 @@ makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
 /*#define IM_CFRAND2DIST*/
 #endif
 
+/* return true if the color map contains only grays */
+static int
+is_gray_map(const i_quantize *quant) {
+  int i;
+
+  for (i = 0; i < quant->mc_count; ++i) {
+    if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g
+	|| quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) {
+      mm_log((1, "  not a gray map\n"));
+      return 0;
+    }
+  }
+
+  mm_log((1, "  is a gray map\n"));
+  return 1;
+}
+
 #ifdef IM_CFHASHBOX
 
 /* The original version I wrote for this used the sort.
@@ -1059,7 +1266,8 @@ static int rand2dist_find(i_color val, i_quantize *quant, i_dists *dists, int in
 #endif
 
 static void translate_addi(i_quantize *quant, i_img *img, i_palidx *out) {
-  int x, y, i, k, bst_idx;
+  i_img_dim x, y, k;
+  int i, bst_idx = 0;
   i_color val;
   int pixdev = quant->perturb;
   CF_VARS;
@@ -1153,10 +1361,11 @@ translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
   int mapw, maph, mapo;
   int i;
   errdiff_t *err;
-  int errw;
+  i_img_dim errw;
   int difftotal;
-  int x, y, dx, dy;
-  int bst_idx;
+  i_img_dim x, y, dx, dy;
+  int bst_idx = 0;
+  int is_gray = is_gray_map(quant);
   CF_VARS;
 
   if ((quant->errdiff & ed_mask) == ed_custom) {
@@ -1195,12 +1404,15 @@ translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
   for (y = 0; y < img->ysize; ++y) {
     for (x = 0; x < img->xsize; ++x) {
       i_color val;
-      long ld, cd;
       errdiff_t perr;
       i_gpix(img, x, y, &val);
       if (img->channels < 3) {
         val.channel[1] = val.channel[2] = val.channel[0];
       }
+      else if (is_gray) {
+	int gray = 0.5 + color_to_grey(&val);
+	val.channel[0] = val.channel[1] = val.channel[2] = gray;
+      }
       perr = err[x+mapo];
       perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal;
       perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal;
@@ -1238,7 +1450,8 @@ translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
 
 
 static void prescan(i_img **imgs,int count, int cnum, cvec *clr, i_sample_t *line) {
-  int i,k,j,x,y;
+  int i,k,j;
+  i_img_dim x,y;
   i_sample_t *val;
   const int *chans;
 
@@ -1438,7 +1651,21 @@ static void transparent_threshold(i_quantize *, i_palidx *, i_img *, i_palidx);
 static void transparent_errdiff(i_quantize *, i_palidx *, i_img *, i_palidx);
 static void transparent_ordered(i_quantize *, i_palidx *, i_img *, i_palidx);
 
-void quant_transparent(i_quantize *quant, i_palidx *data, i_img *img,
+/*
+=item i_quant_transparent(C<quant>, C<data>, C<img>, C<trans_index>)
+
+=category Image quantization
+
+Dither the alpha channel on C<img> into the palette indexes in
+C<data>.  Pixels to be transparent are replaced with C<trans_pixel>.
+
+The method used depends on the tr_* members of C<quant>.
+
+=cut
+*/
+
+void 
+i_quant_transparent(i_quantize *quant, i_palidx *data, i_img *img,
 		       i_palidx trans_index)
 {
   switch (quant->transp) {
@@ -1466,7 +1693,7 @@ static void
 transparent_threshold(i_quantize *quant, i_palidx *data, i_img *img,
 		      i_palidx trans_index)
 {
-  int x, y;
+  i_img_dim x, y;
   i_sample_t *line = mymalloc(img->xsize * sizeof(i_sample_t));
   int trans_chan = img->channels > 2 ? 3 : 1;
   
@@ -1489,7 +1716,8 @@ transparent_errdiff(i_quantize *quant, i_palidx *data, i_img *img,
   int mapw, maph, mapo;
   int errw, *err, *errp;
   int difftotal, out, error;
-  int x, y, dx, dy, i;
+  i_img_dim x, y, dx, dy;
+  int i;
   i_sample_t *line;
   int trans_chan = img->channels > 2 ? 3 : 1;
 
@@ -1648,7 +1876,7 @@ transparent_ordered(i_quantize *quant, i_palidx *data, i_img *img,
 		    i_palidx trans_index)
 {
   unsigned char *spot;
-  int x, y;
+  i_img_dim x, y;
   i_sample_t *line;
   int trans_chan = img->channels > 2 ? 3 : 1;
   if (quant->tr_orddith == od_custom)