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 }

00219 {
00220   int i;
00221   for (i = 1; i < nhist; i++)
00222     assert(hist[i].haspixel != 255);
00223 }

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 }

00518 {
00519   return colormap_diversity(hist, nhist, adapt_size, 1);
00520 }

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 }

00524 {
00525   return colormap_diversity(hist, nhist, adapt_size, 0);
00526 }

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 }

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 }

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 }

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 }

00042 {
00043   Gif_DeleteArray(hist->c);
00044 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }