00001 /* quantize.c - Histograms and quantization for gifsicle.
00002    Copyright (C) 1997-9 Eddie Kohler, eddietwo@lcs.mit.edu
00003    This file is part of gifsicle.
00004 
00005    Gifsicle is free software. It is distributed under the GNU Public License,
00006    version 2 or later; you can copy, distribute, or alter it at will, as long
00007    as this notice is kept intact and this source code is made available. There
00008    is no warranty, express or implied. */
00009 
00010 #include "config.h"
00011 #include "gifsicle.h"
00012 #include <assert.h>
00013 #include <string.h>
00014 
00015 typedef struct Gif_Histogram {
00016   Gif_Color *c;
00017   int n;
00018   int cap;
00019 } Gif_Histogram;
00020 
00021 static void add_histogram_color(Gif_Color *, Gif_Histogram *, unsigned long);
00022 
00023 static void
00024 init_histogram(Gif_Histogram *new_hist, Gif_Histogram *old_hist)
00025 {
00026   int new_cap = (old_hist ? old_hist->cap * 2 : 1024);
00027   Gif_Color *nc = Gif_NewArray(Gif_Color, new_cap);
00028   int i;
00029   new_hist->c = nc;
00030   new_hist->n = 0;
00031   new_hist->cap = new_cap;
00032   for (i = 0; i < new_cap; i++)
00033     new_hist->c[i].haspixel = 0;
00034   if (old_hist)
00035     for (i = 0; i < old_hist->cap; i++)
00036       if (old_hist->c[i].haspixel)
00037         add_histogram_color(&old_hist->c[i], new_hist, old_hist->c[i].pixel);
00038 }
00039 
00040 static void
00041 delete_histogram(Gif_Histogram *hist)
00042 {
00043   Gif_DeleteArray(hist->c);
00044 }
00045 
00046 static void
00047 add_histogram_color(Gif_Color *color, Gif_Histogram *hist, unsigned long count)
00048 {
00049   Gif_Color *hc = hist->c;
00050   int hcap = hist->cap - 1;
00051   int i = (((color->red & 0xF0) << 4) | (color->green & 0xF0)
00052            | (color->blue >> 4)) & hcap;
00053   int hash2 = ((((color->red & 0x0F) << 8) | ((color->green & 0x0F) << 4)
00054                 | (color->blue & 0x0F)) & hcap) | 1;
00055   
00056   for (; hc[i].haspixel; i = (i + hash2) & hcap)
00057     if (hc[i].red == color->red && hc[i].green == color->green
00058         && hc[i].blue == color->blue) {
00059       hc[i].pixel += count;
00060       color->haspixel = 1;
00061       color->pixel = i;
00062       return;
00063     }
00064 
00065   if (hist->n > ((hist->cap * 7) >> 3)) {
00066     Gif_Histogram new_hist;
00067     init_histogram(&new_hist, hist);
00068     delete_histogram(hist);
00069     *hist = new_hist;
00070     hc = hist->c;               /* 31.Aug.1999 - bug fix from Steven Marthouse
00071                                    <comments@vrml3d.com> */
00072   }
00073 
00074   hist->n++;
00075   hc[i] = *color;
00076   hc[i].haspixel = 1;
00077   hc[i].pixel = count;
00078   color->haspixel = 1;
00079   color->pixel = i;
00080 }
00081 
00082 static int
00083 popularity_sort_compare(const void *va, const void *vb)
00084 {
00085   const Gif_Color *a = (const Gif_Color *)va;
00086   const Gif_Color *b = (const Gif_Color *)vb;
00087   return b->pixel - a->pixel;
00088 }
00089 
00090 static int
00091 pixel_sort_compare(const void *va, const void *vb)
00092 {
00093   const Gif_Color *a = (const Gif_Color *)va;
00094   const Gif_Color *b = (const Gif_Color *)vb;
00095   return a->pixel - b->pixel;
00096 }
00097 
00098 
00099 Gif_Color *
00100 histogram(Gif_Stream *gfs, int *nhist_store)
00101 {
00102   Gif_Histogram hist;
00103   Gif_Color *linear;
00104   Gif_Color transparent_color;
00105   unsigned long ntransparent = 0;
00106   unsigned long nbackground = 0;
00107   int x, y, i;
00108   
00109   unmark_colors(gfs->global);
00110   for (i = 0; i < gfs->nimages; i++)
00111     unmark_colors(gfs->images[i]->local);
00112 
00113   init_histogram(&hist, 0);
00114   
00115   /* Count pixels. Be careful about values which are outside the range of the
00116      colormap. */
00117   for (i = 0; i < gfs->nimages; i++) {
00118     Gif_Image *gfi = gfs->images[i];
00119     Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
00120     u_int32_t count[256];
00121     Gif_Color *col;
00122     int ncol;
00123     int transparent = gfi->transparent;
00124     if (!gfcm) continue;
00125     
00126     /* sweep over the image data, counting pixels */
00127     for (x = 0; x < 256; x++)
00128       count[x] = 0;
00129     for (y = 0; y < gfi->height; y++) {
00130       byte *data = gfi->img[y];
00131       for (x = 0; x < gfi->width; x++, data++)
00132         count[*data]++;
00133     }
00134     
00135     /* add counted colors to global histogram */
00136     col = gfcm->col;
00137     ncol = gfcm->ncol;
00138     for (x = 0; x < ncol; x++)
00139       if (count[x] && x != transparent) {
00140         if (col[x].haspixel)
00141           hist.c[ col[x].pixel ].pixel += count[x];
00142         else
00143           add_histogram_color(&col[x], &hist, count[x]);
00144       }
00145     if (transparent >= 0) {
00146       if (ntransparent == 0) transparent_color = col[transparent];
00147       ntransparent += count[transparent];
00148     }
00149     
00150     /* if this image has background disposal, count its size towards the
00151        background's pixel count */
00152     if (gfi->disposal == GIF_DISPOSAL_BACKGROUND)
00153       nbackground += gfi->width * gfi->height;
00154   }
00155   
00156   /* account for background by adding it to `ntransparent' or the histogram */
00157   if (gfs->images[0]->transparent < 0 && gfs->global
00158       && gfs->background < gfs->global->ncol)
00159     add_histogram_color(&gfs->global->col[gfs->background], &hist, nbackground);
00160   else
00161     ntransparent += nbackground;
00162   
00163   /* now, make the linear histogram from the hashed histogram */
00164   linear = Gif_NewArray(Gif_Color, hist.n + 1);
00165   i = 0;
00166   
00167   /* Put all transparent pixels in histogram slot 0. Transparent pixels are
00168      marked by haspixel == 255. */
00169   if (ntransparent) {
00170     linear[0] = transparent_color;
00171     linear[0].haspixel = 255;
00172     linear[0].pixel = ntransparent;
00173     i++;
00174   }
00175   
00176   /* put hash histogram colors into linear histogram */
00177   for (x = 0; x < hist.cap; x++)
00178     if (hist.c[x].haspixel)
00179       linear[i++] = hist.c[x];
00180 
00181   delete_histogram(&hist);
00182   *nhist_store = i;
00183   return linear;
00184 }
00185 
00186 
00187 #undef min
00188 #undef max
00189 #define min(a, b)       ((a) < (b) ? (a) : (b))
00190 #define max(a, b)       ((a) > (b) ? (a) : (b))
00191 
00192 static int
00193 red_sort_compare(const void *va, const void *vb)
00194 {
00195   const Gif_Color *a = (const Gif_Color *)va;
00196   const Gif_Color *b = (const Gif_Color *)vb;
00197   return a->red - b->red;
00198 }
00199 
00200 static int
00201 green_sort_compare(const void *va, const void *vb)
00202 {
00203   const Gif_Color *a = (const Gif_Color *)va;
00204   const Gif_Color *b = (const Gif_Color *)vb;
00205   return a->green - b->green;
00206 }
00207 
00208 static int
00209 blue_sort_compare(const void *va, const void *vb)
00210 {
00211   const Gif_Color *a = (const Gif_Color *)va;
00212   const Gif_Color *b = (const Gif_Color *)vb;
00213   return a->blue - b->blue;
00214 }
00215 
00216 
00217 static void
00218 assert_hist_transparency(Gif_Color *hist, int nhist)
00219 {
00220   int i;
00221   for (i = 1; i < nhist; i++)
00222     assert(hist[i].haspixel != 255);
00223 }
00224 
00225 
00226 /* COLORMAP FUNCTIONS return a palette (a vector of Gif_Colors). The
00227    pixel fields are undefined; the haspixel fields are all 0. */
00228 
00229 typedef struct {
00230   int first;
00231   int count;
00232   u_int32_t pixel;
00233 } adaptive_slot;
00234 
00235 Gif_Colormap *
00236 colormap_median_cut(Gif_Color *hist, int nhist, int adapt_size)
00237 {
00238   adaptive_slot *slots = Gif_NewArray(adaptive_slot, adapt_size);
00239   Gif_Colormap *gfcm = Gif_NewFullColormap(adapt_size, 256);
00240   Gif_Color *adapt = gfcm->col;
00241   int nadapt;
00242   int i, j;
00243   
00244   /* This code was written with reference to ppmquant by Jef Poskanzer, part
00245      of the pbmplus package. */
00246   
00247   if (adapt_size < 2 || adapt_size > 256)
00248     fatal_error("adaptive palette size must be between 2 and 256");
00249   if (adapt_size >= nhist) {
00250     warning("trivial adaptive palette (only %d colors in source)", nhist);
00251     adapt_size = nhist;
00252   }
00253   
00254   /* 0. remove any transparent color from consideration; reduce adaptive
00255      palette size to accommodate transparency if it looks like that'll be
00256      necessary */
00257   assert_hist_transparency(hist, nhist);
00258   if (adapt_size > 2 && adapt_size < nhist && hist[0].haspixel == 255
00259       && nhist <= 265)
00260     adapt_size--;
00261   if (hist[0].haspixel == 255) {
00262     hist[0] = hist[nhist - 1];
00263     nhist--;
00264   }
00265   
00266   /* 1. set up the first slot, containing all pixels. */
00267   {
00268     u_int32_t total = 0;
00269     for (i = 0; i < nhist; i++)
00270       total += hist[i].pixel;
00271     slots[0].first = 0;
00272     slots[0].count = nhist;
00273     slots[0].pixel = total;
00274     qsort(hist, nhist, sizeof(Gif_Color), pixel_sort_compare);
00275   }
00276   
00277   /* 2. split slots until we have enough. */
00278   for (nadapt = 1; nadapt < adapt_size; nadapt++) {
00279     adaptive_slot *split = 0;
00280     Gif_Color minc, maxc, *slice;
00281     
00282     /* 2.1. pick the slot to split. */
00283     {
00284       u_int32_t split_pixel = 0;
00285       for (i = 0; i < nadapt; i++)
00286         if (slots[i].count >= 2 && slots[i].pixel > split_pixel) {
00287           split = &slots[i];
00288           split_pixel = slots[i].pixel;
00289         }
00290       if (!split)
00291         break;
00292     }
00293     slice = &hist[split->first];
00294     
00295     /* 2.2. find its extent. */
00296     {
00297       Gif_Color *trav = slice;
00298       minc = maxc = *trav;
00299       for (i = 1, trav++; i < split->count; i++, trav++) {
00300         minc.red = min(minc.red, trav->red);
00301         maxc.red = max(maxc.red, trav->red);
00302         minc.green = min(minc.green, trav->green);
00303         maxc.green = max(maxc.green, trav->green);
00304         minc.blue = min(minc.blue, trav->blue);
00305         maxc.blue = max(maxc.blue, trav->blue);
00306       }
00307     }
00308     
00309     /* 2.3. decide how to split it. use the luminance method. also sort the
00310        colors. */
00311     {
00312       double red_diff = 0.299 * (maxc.red - minc.red);
00313       double green_diff = 0.587 * (maxc.green - minc.green);
00314       double blue_diff = 0.114 * (maxc.blue - minc.blue);
00315       if (red_diff >= green_diff && red_diff >= blue_diff)
00316         qsort(slice, split->count, sizeof(Gif_Color), red_sort_compare);
00317       else if (green_diff >= blue_diff)
00318         qsort(slice, split->count, sizeof(Gif_Color), green_sort_compare);
00319       else
00320         qsort(slice, split->count, sizeof(Gif_Color), blue_sort_compare);
00321     }
00322     
00323     /* 2.4. decide where to split the slot and split it there. */
00324     {
00325       u_int32_t half_pixels = split->pixel / 2;
00326       u_int32_t pixel_accum = slice[0].pixel;
00327       u_int32_t diff1, diff2;
00328       for (i = 1; i < split->count - 1 && pixel_accum < half_pixels; i++)
00329         pixel_accum += slice[i].pixel;
00330 
00331       /* We know the area before the split has more pixels than the area
00332          after, possibly by a large margin (bad news). If it would shrink the
00333          margin, change the split. */
00334       diff1 = 2*pixel_accum - split->pixel;
00335       diff2 = split->pixel - 2*(pixel_accum - slice[i-1].pixel);
00336       if (diff2 < diff1 && i > 1) {
00337         i--;
00338         pixel_accum -= slice[i].pixel;
00339       }
00340       
00341       slots[nadapt].first = split->first + i;
00342       slots[nadapt].count = split->count - i;
00343       slots[nadapt].pixel = split->pixel - pixel_accum;
00344       split->count = i;
00345       split->pixel = pixel_accum;
00346     }
00347   }
00348   
00349   /* 3. make the new palette by choosing one color from each slot. */
00350   for (i = 0; i < nadapt; i++) {
00351     double red_total = 0, green_total = 0, blue_total = 0;
00352     Gif_Color *slice = &hist[ slots[i].first ];
00353     for (j = 0; j < slots[i].count; j++) {
00354       red_total += slice[j].red * slice[j].pixel;
00355       green_total += slice[j].green * slice[j].pixel;
00356       blue_total += slice[j].blue * slice[j].pixel;
00357     }
00358     adapt[i].red = (byte)(red_total / slots[i].pixel);
00359     adapt[i].green = (byte)(green_total / slots[i].pixel);
00360     adapt[i].blue = (byte)(blue_total / slots[i].pixel);
00361     adapt[i].haspixel = 0;
00362   }
00363   
00364   Gif_DeleteArray(slots);
00365   gfcm->ncol = nadapt;
00366   return gfcm;
00367 }
00368 
00369 
00370 
00371 static Gif_Colormap *
00372 colormap_diversity(Gif_Color *hist, int nhist, int adapt_size, int blend)
00373 {
00374   u_int32_t *min_dist = Gif_NewArray(u_int32_t, nhist);
00375   int *closest = Gif_NewArray(int, nhist);
00376   Gif_Colormap *gfcm = Gif_NewFullColormap(adapt_size, 256);
00377   Gif_Color *adapt = gfcm->col;
00378   int nadapt = 0;
00379   int i, j, match = 0;
00380   
00381   /* This code was uses XV's modified diversity algorithm, and was written
00382      with reference to XV's implementation of that algorithm by John Bradley
00383      <bradley@cis.upenn.edu> and Tom Lane <Tom.Lane@g.gp.cs.cmu.edu>. */
00384   
00385   if (adapt_size < 2 || adapt_size > 256)
00386     fatal_error("adaptive palette size must be between 2 and 256");
00387   if (adapt_size > nhist) {
00388     warning("trivial adaptive palette (only %d colors in source)", nhist);
00389     adapt_size = nhist;
00390   }
00391   
00392   /* 0. remove any transparent color from consideration; reduce adaptive
00393      palette size to accommodate transparency if it looks like that'll be
00394      necessary */
00395   assert_hist_transparency(hist, nhist);
00396   /* It will be necessary to accommodate transparency if (1) there is
00397      transparency in the image; (2) the adaptive palette isn't trivial; and
00398      (3) there are a small number of colors in the image (arbitrary constant:
00399      <= 265), so it's likely that most images will use most of the slots, so
00400      it's likely there won't be unused slots. */
00401   if (adapt_size > 2 && adapt_size < nhist && hist[0].haspixel == 255
00402       && nhist <= 265)
00403     adapt_size--;
00404   if (hist[0].haspixel == 255) {
00405     hist[0] = hist[nhist - 1];
00406     nhist--;
00407   }
00408   
00409   /* blending has bad effects when there are very few colors */
00410   if (adapt_size < 4)
00411     blend = 0;
00412   
00413   /* 1. initialize min_dist and sort the colors in order of popularity. */
00414   for (i = 0; i < nhist; i++)
00415     min_dist[i] = 0x7FFFFFFF;
00416   
00417   qsort(hist, nhist, sizeof(Gif_Color), popularity_sort_compare);
00418   
00419   /* 2. choose colors one at a time */
00420   for (nadapt = 0; nadapt < adapt_size; nadapt++) {
00421     int chosen = 0;
00422     
00423     /* 2.1. choose the color to be added */
00424     if (nadapt == 0 || (nadapt >= 10 && nadapt % 2 == 0)) {
00425       /* 2.1a. choose based on popularity from unchosen colors; we've sorted
00426          them on popularity, so just choose the first in the list */
00427       for (; chosen < nhist; chosen++)
00428         if (min_dist[chosen])
00429           break;
00430       
00431     } else {
00432       /* 2.1b. choose based on diversity from unchosen colors */
00433       u_int32_t chosen_dist = 0;
00434       for (i = 0; i < nhist; i++)
00435         if (min_dist[i] > chosen_dist) {
00436           chosen = i;
00437           chosen_dist = min_dist[i];
00438         }
00439     }
00440     
00441     /* 2.2. add the color */
00442     min_dist[chosen] = 0;
00443     closest[chosen] = nadapt;
00444     
00445     /* 2.3. adjust the min_dist array */
00446     {
00447       int red = hist[chosen].red, green = hist[chosen].green,
00448         blue = hist[chosen].blue;
00449       Gif_Color *h = hist;
00450       for (i = 0; i < nhist; i++, h++)
00451         if (min_dist[i]) {
00452           u_int32_t dist = (h->red - red) * (h->red - red)
00453             + (h->green - green) * (h->green - green)
00454             + (h->blue - blue) * (h->blue - blue);
00455           if (dist < min_dist[i]) {
00456             min_dist[i] = dist;
00457             closest[i] = nadapt;
00458           }
00459         }
00460     }
00461   }
00462   
00463   /* 3. make the new palette by choosing one color from each slot. */
00464   if (!blend) {
00465     for (i = 0; i < nadapt; i++) {
00466       for (j = 0; j < nhist; j++)
00467         if (closest[j] == i && !min_dist[j])
00468           match = j;
00469       adapt[i] = hist[match];
00470       adapt[i].haspixel = 0;
00471     }
00472     
00473   } else {
00474     for (i = 0; i < nadapt; i++) {
00475       double red_total = 0, green_total = 0, blue_total = 0;
00476       u_int32_t pixel_total = 0, mismatch_pixel_total = 0;
00477       for (j = 0; j < nhist; j++)
00478         if (closest[j] == i) {
00479           u_int32_t pixel = hist[j].pixel;
00480           red_total += hist[j].red * pixel;
00481           green_total += hist[j].green * pixel;
00482           blue_total += hist[j].blue * pixel;
00483           pixel_total += pixel;
00484           if (min_dist[j])
00485             mismatch_pixel_total += pixel;
00486           else
00487             match = j;
00488         }
00489       /* Only blend if total number of mismatched pixels exceeds total number
00490          of matched pixels by a large margin. */
00491       if (3 * mismatch_pixel_total <= 2 * pixel_total)
00492         adapt[i] = hist[match];
00493       else {
00494         /* Favor, by a smallish amount, the color the plain diversity
00495            algorithm would pick. */
00496         u_int32_t pixel = hist[match].pixel * 2;
00497         red_total += hist[match].red * pixel;
00498         green_total += hist[match].green * pixel;
00499         blue_total += hist[match].blue * pixel;
00500         pixel_total += pixel;
00501         adapt[i].red = (byte)(red_total / pixel_total);
00502         adapt[i].green = (byte)(green_total / pixel_total);
00503         adapt[i].blue = (byte)(blue_total / pixel_total);
00504       }
00505       adapt[i].haspixel = 0;
00506     }
00507   }
00508   
00509   Gif_DeleteArray(min_dist);
00510   Gif_DeleteArray(closest);
00511   gfcm->ncol = nadapt;
00512   return gfcm;
00513 }
00514 
00515 
00516 Gif_Colormap *
00517 colormap_blend_diversity(Gif_Color *hist, int nhist, int adapt_size)
00518 {
00519   return colormap_diversity(hist, nhist, adapt_size, 1);
00520 }
00521 
00522 Gif_Colormap *
00523 colormap_flat_diversity(Gif_Color *hist, int nhist, int adapt_size)
00524 {
00525   return colormap_diversity(hist, nhist, adapt_size, 0);
00526 }
00527 
00528 
00529 struct color_hash_item {
00530   byte red;
00531   byte green;
00532   byte blue;
00533   u_int32_t pixel;
00534   color_hash_item *next;
00535 };
00536 #define COLOR_HASH_SIZE 20023
00537 #define COLOR_HASH_CODE(r, g, b)        ((u_int32_t)(r * 33023 + g * 30013 + b * 27011) % COLOR_HASH_SIZE)
00538 
00539 
00540 /*****
00541  * color_hash_item allocation and deallocation
00542  **/
00543 
00544 static color_hash_item *hash_item_alloc_list;
00545 static int hash_item_alloc_left;
00546 #define HASH_ITEM_ALLOC_AMOUNT 512
00547 
00548 static color_hash_item **
00549 new_color_hash(void)
00550 {
00551   int i;
00552   color_hash_item **hash = Gif_NewArray(color_hash_item *, COLOR_HASH_SIZE);
00553   for (i = 0; i < COLOR_HASH_SIZE; i++)
00554     hash[i] = 0;
00555   return hash;
00556 }
00557 
00558 
00559 static color_hash_item *
00560 new_color_hash_item(byte red, byte green, byte blue)
00561 {
00562   color_hash_item *chi;
00563   if (hash_item_alloc_left <= 0) {
00564     color_hash_item *new_alloc =
00565       Gif_NewArray(color_hash_item, HASH_ITEM_ALLOC_AMOUNT);
00566     new_alloc[HASH_ITEM_ALLOC_AMOUNT-1].next = hash_item_alloc_list;
00567     hash_item_alloc_list = new_alloc;
00568     hash_item_alloc_left = HASH_ITEM_ALLOC_AMOUNT - 1;
00569   }
00570   
00571   --hash_item_alloc_left;
00572   chi = &hash_item_alloc_list[hash_item_alloc_left];
00573   chi->red = red;
00574   chi->green = green;
00575   chi->blue = blue;
00576   chi->next = 0;
00577   return chi;
00578 }
00579 
00580 static void
00581 free_all_color_hash_items(void)
00582 {
00583   while (hash_item_alloc_list) {
00584     color_hash_item *next =
00585       hash_item_alloc_list[HASH_ITEM_ALLOC_AMOUNT - 1].next;
00586     Gif_DeleteArray(hash_item_alloc_list);
00587     hash_item_alloc_list = next;
00588   }
00589   hash_item_alloc_left = 0;
00590 }
00591 
00592 
00593 static int
00594 hash_color(int red, int green, int blue,
00595            color_hash_item **hash, Gif_Colormap *new_cm)
00596 {
00597   u_int32_t hash_code = COLOR_HASH_CODE(red, green, blue);
00598   color_hash_item *prev = 0, *trav;
00599   
00600   /* Is new_cm grayscale? We cache the answer here. */
00601   static Gif_Colormap *cached_new_cm;
00602   static int new_cm_grayscale;
00603   
00604   for (trav = hash[hash_code]; trav; prev = trav, trav = trav->next)
00605     if (trav->red == red && trav->green == green && trav->blue == blue)
00606       return trav->pixel;
00607   
00608   trav = new_color_hash_item(red, green, blue);
00609   if (prev)
00610     prev->next = trav;
00611   else
00612     hash[hash_code] = trav;
00613   
00614   /* calculate whether new_cm is grayscale */
00615   if (new_cm != cached_new_cm) {
00616     int i;
00617     Gif_Color *col = new_cm->col;
00618     cached_new_cm = new_cm;
00619     new_cm_grayscale = 1;
00620     for (i = 0; i < new_cm->ncol && new_cm_grayscale; i++)
00621       if (col[i].red != col[i].green || col[i].green != col[i].blue
00622           || col[i].blue != col[i].red)
00623         new_cm_grayscale = 0;
00624   }
00625   
00626   /* find the closest color in the new colormap */
00627   {
00628     Gif_Color *col = new_cm->col;
00629     int ncol = new_cm->ncol, i, found;
00630     u_int32_t min_dist = 0xFFFFFFFFU;
00631     
00632     if (new_cm_grayscale) {
00633       /* If the new colormap is 100% grayscale, then use distance in luminance
00634          space instead of distance in RGB space. The weights for the R,G,B
00635          components in luminance space are 0.299,0.587,0.114. We calculate a
00636          gray value for the input color first and compare that against the
00637          available grays in the colormap. Thanks to Christian Kumpf,
00638          <kumpf@igd.fhg.de>, for providing a patch.
00639          
00640          Note on the calculation of `gray': Using the factors 306, 601, and
00641          117 (proportional to 0.299,0.587,0.114) we get a scaled gray value
00642          between 0 and 255 * 1024. */
00643       int gray = 306 * red + 601 * green + 117 * blue;
00644       for (i = 0; i < ncol; i++)
00645         if (col[i].haspixel != 255) {
00646           int in_gray = 1024 * col[i].red;
00647           u_int32_t dist = abs(gray - in_gray);
00648           if (dist < min_dist) {
00649             min_dist = dist;
00650             found = i;
00651           }
00652         }
00653       
00654     } else {
00655       /* Use straight-line Euclidean distance in RGB space */
00656       for (i = 0; i < ncol; i++)
00657         if (col[i].haspixel != 255) {
00658           u_int32_t dist = (red - col[i].red) * (red - col[i].red)
00659             + (green - col[i].green) * (green - col[i].green)
00660             + (blue - col[i].blue) * (blue - col[i].blue);
00661           if (dist < min_dist) {
00662             min_dist = dist;
00663             found = i;
00664           }
00665         }
00666     }
00667     
00668     trav->pixel = found;
00669     return found;
00670   }
00671 }
00672 
00673 
00674 void
00675 colormap_image_posterize(Gif_Image *gfi, byte *new_data,
00676                          Gif_Colormap *old_cm, Gif_Colormap *new_cm,
00677                          color_hash_item **hash, u_int32_t *histogram)
00678 {
00679   int ncol = old_cm->ncol;
00680   Gif_Color *col = old_cm->col;
00681   int map[256];
00682   int i, j;
00683   int transparent = gfi->transparent;
00684   
00685   /* find closest colors in new colormap */
00686   for (i = 0; i < ncol; i++)
00687     if (col[i].haspixel)
00688       map[i] = col[i].pixel;
00689     else {
00690       map[i] = col[i].pixel =
00691         hash_color(col[i].red, col[i].green, col[i].blue, hash, new_cm);
00692       col[i].haspixel = 1;
00693     }
00694   
00695   /* map image */
00696   for (j = 0; j < gfi->height; j++) {
00697     byte *data = gfi->img[j];
00698     for (i = 0; i < gfi->width; i++, data++, new_data++)
00699       if (*data != transparent) {
00700         *new_data = map[*data];
00701         histogram[*new_data]++;
00702       }
00703   }
00704 }
00705 
00706 
00707 #define DITHER_SCALE    1024
00708 #define DITHER_SCALE_M1 (DITHER_SCALE-1)
00709 #define N_RANDOM_VALUES 512
00710 
00711 void
00712 colormap_image_floyd_steinberg(Gif_Image *gfi, byte *all_new_data,
00713                                Gif_Colormap *old_cm, Gif_Colormap *new_cm,
00714                                color_hash_item **hash, u_int32_t *histogram)
00715 {
00716   static int32_t *random_values = 0;
00717   
00718   int width = gfi->width;
00719   int dither_direction = 0;
00720   int transparent = gfi->transparent;
00721   int i, j;
00722   int32_t *r_err, *g_err, *b_err, *r_err1, *g_err1, *b_err1;
00723   Gif_Color *col = old_cm->col;
00724   Gif_Color *new_col = new_cm->col;
00725   
00726   /* This code was written with reference to ppmquant by Jef Poskanzer, part
00727      of the pbmplus package. */
00728   
00729   /* Initialize Floyd-Steinberg error vectors to small random values, so we
00730      don't get artifacts on the top row */
00731   r_err = Gif_NewArray(int32_t, width + 2);
00732   g_err = Gif_NewArray(int32_t, width + 2);
00733   b_err = Gif_NewArray(int32_t, width + 2);
00734   r_err1 = Gif_NewArray(int32_t, width + 2);
00735   g_err1 = Gif_NewArray(int32_t, width + 2);
00736   b_err1 = Gif_NewArray(int32_t, width + 2);
00737   /* Use the same random values on each call in an attempt to minimize
00738      "jumping dithering" effects on animations */
00739   if (!random_values) {
00740     random_values = Gif_NewArray(int32_t, N_RANDOM_VALUES);
00741     for (i = 0; i < N_RANDOM_VALUES; i++)
00742       random_values[i] = RANDOM() % (DITHER_SCALE_M1 * 2) - DITHER_SCALE_M1;
00743   }
00744   for (i = 0; i < gfi->width + 2; i++) {
00745     int j = (i + gfi->left) * 3;
00746     r_err[i] = random_values[ (j + 0) % N_RANDOM_VALUES ];
00747     g_err[i] = random_values[ (j + 1) % N_RANDOM_VALUES ];
00748     b_err[i] = random_values[ (j + 2) % N_RANDOM_VALUES ];
00749   }
00750   /* *_err1 initialized below */
00751   
00752   /* Do the image! */
00753   for (j = 0; j < gfi->height; j++) {
00754     int d0, d1, d2, d3;         /* used for error diffusion */
00755     byte *data, *new_data;
00756     int x;
00757     
00758     if (dither_direction) {
00759       x = width - 1;
00760       d0 = 0, d1 = 2, d2 = 1, d3 = 0;
00761     } else {
00762       x = 0;
00763       d0 = 2, d1 = 0, d2 = 1, d3 = 2;
00764     }
00765     data = &gfi->img[j][x];
00766     new_data = all_new_data + j * width + x;
00767     
00768     for (i = 0; i < width + 2; i++)
00769       r_err1[i] = g_err1[i] = b_err1[i] = 0;
00770     
00771     /* Do a single row */
00772     while (x >= 0 && x < width) {
00773       int e, use_r, use_g, use_b;
00774       
00775       /* the transparent color never gets adjusted */
00776       if (*data == transparent)
00777         goto next;
00778       
00779       /* use Floyd-Steinberg errors to adjust actual color */
00780       use_r = col[*data].red + r_err[x+1] / DITHER_SCALE;
00781       use_g = col[*data].green + g_err[x+1] / DITHER_SCALE;
00782       use_b = col[*data].blue + b_err[x+1] / DITHER_SCALE;
00783       use_r = max(use_r, 0);  use_r = min(use_r, 255);
00784       use_g = max(use_g, 0);  use_g = min(use_g, 255);
00785       use_b = max(use_b, 0);  use_b = min(use_b, 255);
00786       
00787       *new_data = hash_color(use_r, use_g, use_b, hash, new_cm);
00788       histogram[*new_data]++;
00789       
00790       /* calculate and propagate the error between desired and selected color.
00791          Assume that, with a large scale (1024), we don't need to worry about
00792          image artifacts caused by error accumulation (the fact that the
00793          error terms might not sum to the error). */
00794       e = (use_r - new_col[*new_data].red) * DITHER_SCALE;
00795       if (e) {
00796         r_err [x+d0] += (e * 7) / 16;
00797         r_err1[x+d1] += (e * 3) / 16;
00798         r_err1[x+d2] += (e * 5) / 16;
00799         r_err1[x+d3] += e / 16;
00800       }
00801       
00802       e = (use_g - new_col[*new_data].green) * DITHER_SCALE;
00803       if (e) {
00804         g_err [x+d0] += (e * 7) / 16;
00805         g_err1[x+d1] += (e * 3) / 16;
00806         g_err1[x+d2] += (e * 5) / 16;
00807         g_err1[x+d3] += e / 16;
00808       }
00809       
00810       e = (use_b - new_col[*new_data].blue) * DITHER_SCALE;
00811       if (e) {
00812         b_err [x+d0] += (e * 7) / 16;
00813         b_err1[x+d1] += (e * 3) / 16;
00814         b_err1[x+d2] += (e * 5) / 16;
00815         b_err1[x+d3] += e / 16;
00816       }
00817       
00818      next:
00819       if (dither_direction)
00820         x--, data--, new_data--;
00821       else
00822         x++, data++, new_data++;
00823     }
00824     /* Did a single row */
00825     
00826     /* change dithering directions */
00827     {
00828       int32_t *temp;
00829       temp = r_err; r_err = r_err1; r_err1 = temp;
00830       temp = g_err; g_err = g_err1; g_err1 = temp;
00831       temp = b_err; b_err = b_err1; b_err1 = temp;
00832       dither_direction = !dither_direction;
00833     }
00834   }
00835   
00836   /* delete temporary storage */
00837   Gif_DeleteArray(r_err);
00838   Gif_DeleteArray(g_err);
00839   Gif_DeleteArray(b_err);
00840   Gif_DeleteArray(r_err1);
00841   Gif_DeleteArray(g_err1);
00842   Gif_DeleteArray(b_err1);
00843 }
00844 
00845 
00846 /* return value 1 means run the image_changer again */
00847 static int
00848 try_assign_transparency(Gif_Image *gfi, Gif_Colormap *old_cm, byte *new_data,
00849                         Gif_Colormap *new_cm, int *new_ncol,
00850                         u_int32_t *histogram)
00851 {
00852   u_int32_t min_used;
00853   int i, j;
00854   int transparent = gfi->transparent;
00855   int new_transparent = -1;
00856   Gif_Color transp_value;
00857   
00858   if (transparent < 0)
00859     return 0;
00860 
00861   if (old_cm)
00862     transp_value = old_cm->col[transparent];
00863   
00864   /* look for an unused pixel in the existing colormap; prefer the same color
00865      we had */
00866   for (i = 0; i < *new_ncol; i++)
00867     if (histogram[i] == 0 && GIF_COLOREQ(&transp_value, &new_cm->col[i])) {
00868       new_transparent = i;
00869       goto found;
00870     }
00871   for (i = 0; i < *new_ncol; i++)
00872     if (histogram[i] == 0) {
00873       new_transparent = i;
00874       goto found;
00875     }
00876   
00877   /* try to expand the colormap */
00878   if (*new_ncol < 256) {
00879     assert(*new_ncol < new_cm->capacity);
00880     new_transparent = *new_ncol;
00881     new_cm->col[new_transparent] = transp_value;
00882     (*new_ncol)++;
00883     goto found;
00884   }
00885   
00886   /* not found: mark the least-frequently-used color as the new transparent
00887      color and return 1 (meaning `dither again') */
00888   assert(*new_ncol == 256);
00889   min_used = 0xFFFFFFFFU;
00890   for (i = 0; i < 256; i++)
00891     if (histogram[i] < min_used) {
00892       new_transparent = i;
00893       min_used = histogram[i];
00894     }
00895   new_cm->col[new_transparent].haspixel = 255; /* mark it unusable */
00896   return 1;
00897   
00898  found:
00899   for (j = 0; j < gfi->height; j++) {
00900     byte *data = gfi->img[j];
00901     for (i = 0; i < gfi->width; i++, data++, new_data++)
00902       if (*data == transparent)
00903         *new_data = new_transparent;
00904   }
00905   
00906   gfi->transparent = new_transparent;
00907   return 0;
00908 }
00909 
00910 void
00911 colormap_stream(Gif_Stream *gfs, Gif_Colormap *new_cm,
00912                 colormap_image_func image_changer)
00913 { 
00914   color_hash_item **hash = new_color_hash();
00915   int background_transparent = gfs->images[0]->transparent >= 0;
00916   Gif_Color *new_col = new_cm->col;
00917   int new_ncol = new_cm->ncol;
00918   int imagei, j;
00919   int compress_new_cm = 1;
00920 
00921   /* make sure colormap has enough space */
00922   if (new_cm->capacity < 256) {
00923     Gif_Color *x = Gif_NewArray(Gif_Color, 256);
00924     memcpy(x, new_col, sizeof(Gif_Color) * new_ncol);
00925     Gif_DeleteArray(new_col);
00926     new_cm->col = new_col = x;
00927     new_cm->capacity = 256;
00928   }
00929   assert(new_cm->capacity >= 256);
00930   
00931   /* new_col[j].pixel == number of pixels with color j in the new image. */
00932   for (j = 0; j < 256; j++)
00933     new_col[j].pixel = 0;
00934   
00935   for (imagei = 0; imagei < gfs->nimages; imagei++) {
00936     Gif_Image *gfi = gfs->images[imagei];
00937     Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
00938 
00939     if (gfcm) {
00940       /* If there was an old colormap, change the image data */
00941       byte *new_data = Gif_NewArray(byte, gfi->width * gfi->height);
00942       u_int32_t histogram[256];
00943       unmark_colors(new_cm);
00944       unmark_colors(gfcm);
00945       
00946       do {
00947         for (j = 0; j < 256; j++) histogram[j] = 0;
00948         image_changer(gfi, new_data, gfcm, new_cm, hash, histogram);
00949       } while (try_assign_transparency(gfi, gfcm, new_data, new_cm, &new_ncol,
00950                                        histogram));
00951       
00952       Gif_ReleaseUncompressedImage(gfi);
00953       Gif_SetUncompressedImage(gfi, new_data, Gif_DeleteArrayFunc, 0);
00954       
00955       /* update count of used colors */
00956       for (j = 0; j < 256; j++)
00957         new_col[j].pixel += histogram[j];
00958       if (gfi->transparent >= 0)
00959         /* we don't have data on the number of used colors for transparency
00960            so fudge it. */
00961         new_col[gfi->transparent].pixel += gfi->width * gfi->height / 8;
00962       
00963     } else {
00964       /* Can't compress new_cm afterwards if we didn't actively change colors
00965          over */
00966       compress_new_cm = 0;
00967     }
00968     
00969     if (gfi->local) {
00970       Gif_DeleteColormap(gfi->local);
00971       gfi->local = 0;
00972     }
00973   }
00974 
00975   /* Set new_cm->ncol from new_ncol. We didn't update new_cm->ncol before so
00976      the closest-color algorithms wouldn't see any new transparent colors.
00977      That way added transparent colors were only used for transparency. */
00978   new_cm->ncol = new_ncol;
00979   
00980   /* change the background. I hate the background by now */
00981   if (background_transparent)
00982     gfs->background = gfs->images[0]->transparent;
00983   else if (gfs->global && gfs->background < gfs->global->ncol) {
00984     Gif_Color *c = &gfs->global->col[ gfs->background ];
00985     gfs->background = hash_color(c->red, c->green, c->blue, hash, new_cm);
00986     new_col[gfs->background].pixel++;
00987   }
00988   
00989   Gif_DeleteColormap(gfs->global);
00990   
00991   /* We may have used only a subset of the colors in new_cm. We try to store
00992      only that subset, just as if we'd piped the output of `gifsicle
00993      --use-colormap=X' through `gifsicle' another time. */
00994   gfs->global = Gif_CopyColormap(new_cm);
00995   if (compress_new_cm) {
00996     /* only bother to recompress if we'll get anything out of it */
00997     compress_new_cm = 0;
00998     for (j = 0; j < new_cm->ncol - 1; j++)
00999       if (new_col[j].pixel == 0 || new_col[j].pixel < new_col[j+1].pixel) {
01000         compress_new_cm = 1;
01001         break;
01002       }
01003   }
01004   
01005   if (compress_new_cm) {
01006     int map[256];
01007     
01008     /* Gif_CopyColormap copies the `pixel' values as well */
01009     new_col = gfs->global->col;
01010     for (j = 0; j < new_cm->ncol; j++)
01011       new_col[j].haspixel = j;
01012     
01013     /* sort based on popularity */
01014     qsort(new_col, new_cm->ncol, sizeof(Gif_Color), popularity_sort_compare);
01015     
01016     /* set up the map and reduce the number of colors */
01017     for (j = 0; j < new_cm->ncol; j++)
01018       map[ new_col[j].haspixel ] = j;
01019     for (j = 0; j < new_cm->ncol; j++)
01020       if (!new_col[j].pixel) {
01021         gfs->global->ncol = j;
01022         break;
01023       }
01024     
01025     /* map the image data, transparencies, and background */
01026     gfs->background = map[gfs->background];
01027     for (imagei = 0; imagei < gfs->nimages; imagei++) {
01028       Gif_Image *gfi = gfs->images[imagei];
01029       u_int32_t size;
01030       byte *data = gfi->image_data;
01031       for (size = gfi->width * gfi->height; size > 0; size--, data++)
01032         *data = map[*data];
01033       if (gfi->transparent >= 0)
01034         gfi->transparent = map[gfi->transparent];
01035     }
01036   }
01037   
01038   /* free storage */
01039   free_all_color_hash_items();
01040   Gif_DeleteArray(hash);
01041 }