1 /* quantize.c - Histograms and quantization for gifsicle.
2 Copyright (C) 1997-9 Eddie Kohler, eddietwo@lcs.mit.edu
3 This file is part of gifsicle.
4
5 Gifsicle is free software. It is distributed under the GNU Public License,
6 version 2 or later; you can copy, distribute, or alter it at will, as long
7 as this notice is kept intact and this source code is made available. There
8 is no warranty, express or implied. */
9
10 #include "config.h"
11 #include "gifsicle.h"
12 #include <assert.h>
13 #include <string.h>
14
15 typedef struct Gif_Histogram {
16 Gif_Color *c;
17 int n;
18 int cap;
19 } Gif_Histogram;
20
21 static void add_histogram_color(Gif_Color *, Gif_Histogram *, unsigned long);
22
23 static void
init_histogram(Gif_Histogram * new_hist,Gif_Histogram * old_hist)24 init_histogram(Gif_Histogram *new_hist, Gif_Histogram *old_hist)
25 {
26 int new_cap = (old_hist ? old_hist->cap * 2 : 1024);
27 Gif_Color *nc = Gif_NewArray(Gif_Color, new_cap);
28 int i;
29 new_hist->c = nc;
30 new_hist->n = 0;
31 new_hist->cap = new_cap;
32 for (i = 0; i < new_cap; i++)
33 new_hist->c[i].haspixel = 0;
34 if (old_hist)
35 for (i = 0; i < old_hist->cap; i++)
36 if (old_hist->c[i].haspixel)
37 add_histogram_color(&old_hist->c[i], new_hist, old_hist->c[i].pixel);
38 }
39
40 static void
delete_histogram(Gif_Histogram * hist)41 delete_histogram(Gif_Histogram *hist)
42 {
43 Gif_DeleteArray(hist->c);
44 }
45
46 static void
add_histogram_color(Gif_Color * color,Gif_Histogram * hist,unsigned long count)47 add_histogram_color(Gif_Color *color, Gif_Histogram *hist, unsigned long count)
48 {
49 Gif_Color *hc = hist->c;
50 int hcap = hist->cap - 1;
51 int i = (((color->red & 0xF0) << 4) | (color->green & 0xF0)
52 | (color->blue >> 4)) & hcap;
53 int hash2 = ((((color->red & 0x0F) << 8) | ((color->green & 0x0F) << 4)
54 | (color->blue & 0x0F)) & hcap) | 1;
55
56 for (; hc[i].haspixel; i = (i + hash2) & hcap)
57 if (hc[i].red == color->red && hc[i].green == color->green
58 && hc[i].blue == color->blue) {
59 hc[i].pixel += count;
60 color->haspixel = 1;
61 color->pixel = i;
62 return;
63 }
64
65 if (hist->n > ((hist->cap * 7) >> 3)) {
66 Gif_Histogram new_hist;
67 init_histogram(&new_hist, hist);
68 delete_histogram(hist);
69 *hist = new_hist;
70 hc = hist->c; /* 31.Aug.1999 - bug fix from Steven Marthouse
71 <comments@vrml3d.com> */
72 }
73
74 hist->n++;
75 hc[i] = *color;
76 hc[i].haspixel = 1;
77 hc[i].pixel = count;
78 color->haspixel = 1;
79 color->pixel = i;
80 }
81
82 static int
popularity_sort_compare(const void * va,const void * vb)83 popularity_sort_compare(const void *va, const void *vb)
84 {
85 const Gif_Color *a = (const Gif_Color *)va;
86 const Gif_Color *b = (const Gif_Color *)vb;
87 return b->pixel - a->pixel;
88 }
89
90 static int
pixel_sort_compare(const void * va,const void * vb)91 pixel_sort_compare(const void *va, const void *vb)
92 {
93 const Gif_Color *a = (const Gif_Color *)va;
94 const Gif_Color *b = (const Gif_Color *)vb;
95 return a->pixel - b->pixel;
96 }
97
98
99 Gif_Color *
histogram(Gif_Stream * gfs,int * nhist_store)100 histogram(Gif_Stream *gfs, int *nhist_store)
101 {
102 Gif_Histogram hist;
103 Gif_Color *linear;
104 Gif_Color transparent_color;
105 unsigned long ntransparent = 0;
106 unsigned long nbackground = 0;
107 int x, y, i;
108
109 unmark_colors(gfs->global);
110 for (i = 0; i < gfs->nimages; i++)
111 unmark_colors(gfs->images[i]->local);
112
113 init_histogram(&hist, 0);
114
115 /* Count pixels. Be careful about values which are outside the range of the
116 colormap. */
117 for (i = 0; i < gfs->nimages; i++) {
118 Gif_Image *gfi = gfs->images[i];
119 Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
120 u_int32_t count[256];
121 Gif_Color *col;
122 int ncol;
123 int transparent = gfi->transparent;
124 if (!gfcm) continue;
125
126 /* sweep over the image data, counting pixels */
127 for (x = 0; x < 256; x++)
128 count[x] = 0;
129 for (y = 0; y < gfi->height; y++) {
130 byte *data = gfi->img[y];
131 for (x = 0; x < gfi->width; x++, data++)
132 count[*data]++;
133 }
134
135 /* add counted colors to global histogram */
136 col = gfcm->col;
137 ncol = gfcm->ncol;
138 for (x = 0; x < ncol; x++)
139 if (count[x] && x != transparent) {
140 if (col[x].haspixel)
141 hist.c[ col[x].pixel ].pixel += count[x];
142 else
143 add_histogram_color(&col[x], &hist, count[x]);
144 }
145 if (transparent >= 0) {
146 if (ntransparent == 0) transparent_color = col[transparent];
147 ntransparent += count[transparent];
148 }
149
150 /* if this image has background disposal, count its size towards the
151 background's pixel count */
152 if (gfi->disposal == GIF_DISPOSAL_BACKGROUND)
153 nbackground += gfi->width * gfi->height;
154 }
155
156 /* account for background by adding it to `ntransparent' or the histogram */
157 if (gfs->images[0]->transparent < 0 && gfs->global
158 && gfs->background < gfs->global->ncol)
159 add_histogram_color(&gfs->global->col[gfs->background], &hist, nbackground);
160 else
161 ntransparent += nbackground;
162
163 /* now, make the linear histogram from the hashed histogram */
164 linear = Gif_NewArray(Gif_Color, hist.n + 1);
165 i = 0;
166
167 /* Put all transparent pixels in histogram slot 0. Transparent pixels are
168 marked by haspixel == 255. */
169 if (ntransparent) {
170 linear[0] = transparent_color;
171 linear[0].haspixel = 255;
172 linear[0].pixel = ntransparent;
173 i++;
174 }
175
176 /* put hash histogram colors into linear histogram */
177 for (x = 0; x < hist.cap; x++)
178 if (hist.c[x].haspixel)
179 linear[i++] = hist.c[x];
180
181 delete_histogram(&hist);
182 *nhist_store = i;
183 return linear;
184 }
185
186
187 #undef min
188 #undef max
189 #define min(a, b) ((a) < (b) ? (a) : (b))
190 #define max(a, b) ((a) > (b) ? (a) : (b))
191
192 static int
red_sort_compare(const void * va,const void * vb)193 red_sort_compare(const void *va, const void *vb)
194 {
195 const Gif_Color *a = (const Gif_Color *)va;
196 const Gif_Color *b = (const Gif_Color *)vb;
197 return a->red - b->red;
198 }
199
200 static int
green_sort_compare(const void * va,const void * vb)201 green_sort_compare(const void *va, const void *vb)
202 {
203 const Gif_Color *a = (const Gif_Color *)va;
204 const Gif_Color *b = (const Gif_Color *)vb;
205 return a->green - b->green;
206 }
207
208 static int
blue_sort_compare(const void * va,const void * vb)209 blue_sort_compare(const void *va, const void *vb)
210 {
211 const Gif_Color *a = (const Gif_Color *)va;
212 const Gif_Color *b = (const Gif_Color *)vb;
213 return a->blue - b->blue;
214 }
215
216
217 static void
assert_hist_transparency(Gif_Color * hist,int nhist)218 assert_hist_transparency(Gif_Color *hist, int nhist)
219 {
220 int i;
221 for (i = 1; i < nhist; i++)
222 assert(hist[i].haspixel != 255);
223 }
224
225
226 /* COLORMAP FUNCTIONS return a palette (a vector of Gif_Colors). The
227 pixel fields are undefined; the haspixel fields are all 0. */
228
229 typedef struct {
230 int first;
231 int count;
232 u_int32_t pixel;
233 } adaptive_slot;
234
235 Gif_Colormap *
colormap_median_cut(Gif_Color * hist,int nhist,int adapt_size)236 colormap_median_cut(Gif_Color *hist, int nhist, int adapt_size)
237 {
238 adaptive_slot *slots = Gif_NewArray(adaptive_slot, adapt_size);
239 Gif_Colormap *gfcm = Gif_NewFullColormap(adapt_size, 256);
240 Gif_Color *adapt = gfcm->col;
241 int nadapt;
242 int i, j;
243
244 /* This code was written with reference to ppmquant by Jef Poskanzer, part
245 of the pbmplus package. */
246
247 if (adapt_size < 2 || adapt_size > 256)
248 fatal_error("adaptive palette size must be between 2 and 256");
249 if (adapt_size >= nhist) {
250 warning("trivial adaptive palette (only %d colors in source)", nhist);
251 adapt_size = nhist;
252 }
253
254 /* 0. remove any transparent color from consideration; reduce adaptive
255 palette size to accommodate transparency if it looks like that'll be
256 necessary */
257 assert_hist_transparency(hist, nhist);
258 if (adapt_size > 2 && adapt_size < nhist && hist[0].haspixel == 255
259 && nhist <= 265)
260 adapt_size--;
261 if (hist[0].haspixel == 255) {
262 hist[0] = hist[nhist - 1];
263 nhist--;
264 }
265
266 /* 1. set up the first slot, containing all pixels. */
267 {
268 u_int32_t total = 0;
269 for (i = 0; i < nhist; i++)
270 total += hist[i].pixel;
271 slots[0].first = 0;
272 slots[0].count = nhist;
273 slots[0].pixel = total;
274 qsort(hist, nhist, sizeof(Gif_Color), pixel_sort_compare);
275 }
276
277 /* 2. split slots until we have enough. */
278 for (nadapt = 1; nadapt < adapt_size; nadapt++) {
279 adaptive_slot *split = 0;
280 Gif_Color minc, maxc, *slice;
281
282 /* 2.1. pick the slot to split. */
283 {
284 u_int32_t split_pixel = 0;
285 for (i = 0; i < nadapt; i++)
286 if (slots[i].count >= 2 && slots[i].pixel > split_pixel) {
287 split = &slots[i];
288 split_pixel = slots[i].pixel;
289 }
290 if (!split)
291 break;
292 }
293 slice = &hist[split->first];
294
295 /* 2.2. find its extent. */
296 {
297 Gif_Color *trav = slice;
298 minc = maxc = *trav;
299 for (i = 1, trav++; i < split->count; i++, trav++) {
300 minc.red = min(minc.red, trav->red);
301 maxc.red = max(maxc.red, trav->red);
302 minc.green = min(minc.green, trav->green);
303 maxc.green = max(maxc.green, trav->green);
304 minc.blue = min(minc.blue, trav->blue);
305 maxc.blue = max(maxc.blue, trav->blue);
306 }
307 }
308
309 /* 2.3. decide how to split it. use the luminance method. also sort the
310 colors. */
311 {
312 double red_diff = 0.299 * (maxc.red - minc.red);
313 double green_diff = 0.587 * (maxc.green - minc.green);
314 double blue_diff = 0.114 * (maxc.blue - minc.blue);
315 if (red_diff >= green_diff && red_diff >= blue_diff)
316 qsort(slice, split->count, sizeof(Gif_Color), red_sort_compare);
317 else if (green_diff >= blue_diff)
318 qsort(slice, split->count, sizeof(Gif_Color), green_sort_compare);
319 else
320 qsort(slice, split->count, sizeof(Gif_Color), blue_sort_compare);
321 }
322
323 /* 2.4. decide where to split the slot and split it there. */
324 {
325 u_int32_t half_pixels = split->pixel / 2;
326 u_int32_t pixel_accum = slice[0].pixel;
327 u_int32_t diff1, diff2;
328 for (i = 1; i < split->count - 1 && pixel_accum < half_pixels; i++)
329 pixel_accum += slice[i].pixel;
330
331 /* We know the area before the split has more pixels than the area
332 after, possibly by a large margin (bad news). If it would shrink the
333 margin, change the split. */
334 diff1 = 2*pixel_accum - split->pixel;
335 diff2 = split->pixel - 2*(pixel_accum - slice[i-1].pixel);
336 if (diff2 < diff1 && i > 1) {
337 i--;
338 pixel_accum -= slice[i].pixel;
339 }
340
341 slots[nadapt].first = split->first + i;
342 slots[nadapt].count = split->count - i;
343 slots[nadapt].pixel = split->pixel - pixel_accum;
344 split->count = i;
345 split->pixel = pixel_accum;
346 }
347 }
348
349 /* 3. make the new palette by choosing one color from each slot. */
350 for (i = 0; i < nadapt; i++) {
351 double red_total = 0, green_total = 0, blue_total = 0;
352 Gif_Color *slice = &hist[ slots[i].first ];
353 for (j = 0; j < slots[i].count; j++) {
354 red_total += slice[j].red * slice[j].pixel;
355 green_total += slice[j].green * slice[j].pixel;
356 blue_total += slice[j].blue * slice[j].pixel;
357 }
358 adapt[i].red = (byte)(red_total / slots[i].pixel);
359 adapt[i].green = (byte)(green_total / slots[i].pixel);
360 adapt[i].blue = (byte)(blue_total / slots[i].pixel);
361 adapt[i].haspixel = 0;
362 }
363
364 Gif_DeleteArray(slots);
365 gfcm->ncol = nadapt;
366 return gfcm;
367 }
368
369
370
371 static Gif_Colormap *
colormap_diversity(Gif_Color * hist,int nhist,int adapt_size,int blend)372 colormap_diversity(Gif_Color *hist, int nhist, int adapt_size, int blend)
373 {
374 u_int32_t *min_dist = Gif_NewArray(u_int32_t, nhist);
375 int *closest = Gif_NewArray(int, nhist);
376 Gif_Colormap *gfcm = Gif_NewFullColormap(adapt_size, 256);
377 Gif_Color *adapt = gfcm->col;
378 int nadapt = 0;
379 int i, j, match = 0;
380
381 /* This code was uses XV's modified diversity algorithm, and was written
382 with reference to XV's implementation of that algorithm by John Bradley
383 <bradley@cis.upenn.edu> and Tom Lane <Tom.Lane@g.gp.cs.cmu.edu>. */
384
385 if (adapt_size < 2 || adapt_size > 256)
386 fatal_error("adaptive palette size must be between 2 and 256");
387 if (adapt_size > nhist) {
388 warning("trivial adaptive palette (only %d colors in source)", nhist);
389 adapt_size = nhist;
390 }
391
392 /* 0. remove any transparent color from consideration; reduce adaptive
393 palette size to accommodate transparency if it looks like that'll be
394 necessary */
395 assert_hist_transparency(hist, nhist);
396 /* It will be necessary to accommodate transparency if (1) there is
397 transparency in the image; (2) the adaptive palette isn't trivial; and
398 (3) there are a small number of colors in the image (arbitrary constant:
399 <= 265), so it's likely that most images will use most of the slots, so
400 it's likely there won't be unused slots. */
401 if (adapt_size > 2 && adapt_size < nhist && hist[0].haspixel == 255
402 && nhist <= 265)
403 adapt_size--;
404 if (hist[0].haspixel == 255) {
405 hist[0] = hist[nhist - 1];
406 nhist--;
407 }
408
409 /* blending has bad effects when there are very few colors */
410 if (adapt_size < 4)
411 blend = 0;
412
413 /* 1. initialize min_dist and sort the colors in order of popularity. */
414 for (i = 0; i < nhist; i++)
415 min_dist[i] = 0x7FFFFFFF;
416
417 qsort(hist, nhist, sizeof(Gif_Color), popularity_sort_compare);
418
419 /* 2. choose colors one at a time */
420 for (nadapt = 0; nadapt < adapt_size; nadapt++) {
421 int chosen = 0;
422
423 /* 2.1. choose the color to be added */
424 if (nadapt == 0 || (nadapt >= 10 && nadapt % 2 == 0)) {
425 /* 2.1a. choose based on popularity from unchosen colors; we've sorted
426 them on popularity, so just choose the first in the list */
427 for (; chosen < nhist; chosen++)
428 if (min_dist[chosen])
429 break;
430
431 } else {
432 /* 2.1b. choose based on diversity from unchosen colors */
433 u_int32_t chosen_dist = 0;
434 for (i = 0; i < nhist; i++)
435 if (min_dist[i] > chosen_dist) {
436 chosen = i;
437 chosen_dist = min_dist[i];
438 }
439 }
440
441 /* 2.2. add the color */
442 min_dist[chosen] = 0;
443 closest[chosen] = nadapt;
444
445 /* 2.3. adjust the min_dist array */
446 {
447 int red = hist[chosen].red, green = hist[chosen].green,
448 blue = hist[chosen].blue;
449 Gif_Color *h = hist;
450 for (i = 0; i < nhist; i++, h++)
451 if (min_dist[i]) {
452 u_int32_t dist = (h->red - red) * (h->red - red)
453 + (h->green - green) * (h->green - green)
454 + (h->blue - blue) * (h->blue - blue);
455 if (dist < min_dist[i]) {
456 min_dist[i] = dist;
457 closest[i] = nadapt;
458 }
459 }
460 }
461 }
462
463 /* 3. make the new palette by choosing one color from each slot. */
464 if (!blend) {
465 for (i = 0; i < nadapt; i++) {
466 for (j = 0; j < nhist; j++)
467 if (closest[j] == i && !min_dist[j])
468 match = j;
469 adapt[i] = hist[match];
470 adapt[i].haspixel = 0;
471 }
472
473 } else {
474 for (i = 0; i < nadapt; i++) {
475 double red_total = 0, green_total = 0, blue_total = 0;
476 u_int32_t pixel_total = 0, mismatch_pixel_total = 0;
477 for (j = 0; j < nhist; j++)
478 if (closest[j] == i) {
479 u_int32_t pixel = hist[j].pixel;
480 red_total += hist[j].red * pixel;
481 green_total += hist[j].green * pixel;
482 blue_total += hist[j].blue * pixel;
483 pixel_total += pixel;
484 if (min_dist[j])
485 mismatch_pixel_total += pixel;
486 else
487 match = j;
488 }
489 /* Only blend if total number of mismatched pixels exceeds total number
490 of matched pixels by a large margin. */
491 if (3 * mismatch_pixel_total <= 2 * pixel_total)
492 adapt[i] = hist[match];
493 else {
494 /* Favor, by a smallish amount, the color the plain diversity
495 algorithm would pick. */
496 u_int32_t pixel = hist[match].pixel * 2;
497 red_total += hist[match].red * pixel;
498 green_total += hist[match].green * pixel;
499 blue_total += hist[match].blue * pixel;
500 pixel_total += pixel;
501 adapt[i].red = (byte)(red_total / pixel_total);
502 adapt[i].green = (byte)(green_total / pixel_total);
503 adapt[i].blue = (byte)(blue_total / pixel_total);
504 }
505 adapt[i].haspixel = 0;
506 }
507 }
508
509 Gif_DeleteArray(min_dist);
510 Gif_DeleteArray(closest);
511 gfcm->ncol = nadapt;
512 return gfcm;
513 }
514
515
516 Gif_Colormap *
colormap_blend_diversity(Gif_Color * hist,int nhist,int adapt_size)517 colormap_blend_diversity(Gif_Color *hist, int nhist, int adapt_size)
518 {
519 return colormap_diversity(hist, nhist, adapt_size, 1);
520 }
521
522 Gif_Colormap *
colormap_flat_diversity(Gif_Color * hist,int nhist,int adapt_size)523 colormap_flat_diversity(Gif_Color *hist, int nhist, int adapt_size)
524 {
525 return colormap_diversity(hist, nhist, adapt_size, 0);
526 }
527
528
529 struct color_hash_item {
530 byte red;
531 byte green;
532 byte blue;
533 u_int32_t pixel;
534 color_hash_item *next;
535 };
536 #define COLOR_HASH_SIZE 20023
537 #define COLOR_HASH_CODE(r, g, b) ((u_int32_t)(r * 33023 + g * 30013 + b * 27011) % COLOR_HASH_SIZE)
538
539
540 /*****
541 * color_hash_item allocation and deallocation
542 **/
543
544 static color_hash_item *hash_item_alloc_list;
545 static int hash_item_alloc_left;
546 #define HASH_ITEM_ALLOC_AMOUNT 512
547
548 static color_hash_item **
new_color_hash(void)549 new_color_hash(void)
550 {
551 int i;
552 color_hash_item **hash = Gif_NewArray(color_hash_item *, COLOR_HASH_SIZE);
553 for (i = 0; i < COLOR_HASH_SIZE; i++)
554 hash[i] = 0;
555 return hash;
556 }
557
558
559 static color_hash_item *
new_color_hash_item(byte red,byte green,byte blue)560 new_color_hash_item(byte red, byte green, byte blue)
561 {
562 color_hash_item *chi;
563 if (hash_item_alloc_left <= 0) {
564 color_hash_item *new_alloc =
565 Gif_NewArray(color_hash_item, HASH_ITEM_ALLOC_AMOUNT);
566 new_alloc[HASH_ITEM_ALLOC_AMOUNT-1].next = hash_item_alloc_list;
567 hash_item_alloc_list = new_alloc;
568 hash_item_alloc_left = HASH_ITEM_ALLOC_AMOUNT - 1;
569 }
570
571 --hash_item_alloc_left;
572 chi = &hash_item_alloc_list[hash_item_alloc_left];
573 chi->red = red;
574 chi->green = green;
575 chi->blue = blue;
576 chi->next = 0;
577 return chi;
578 }
579
580 static void
free_all_color_hash_items(void)581 free_all_color_hash_items(void)
582 {
583 while (hash_item_alloc_list) {
584 color_hash_item *next =
585 hash_item_alloc_list[HASH_ITEM_ALLOC_AMOUNT - 1].next;
586 Gif_DeleteArray(hash_item_alloc_list);
587 hash_item_alloc_list = next;
588 }
589 hash_item_alloc_left = 0;
590 }
591
592
593 static int
hash_color(int red,int green,int blue,color_hash_item ** hash,Gif_Colormap * new_cm)594 hash_color(int red, int green, int blue,
595 color_hash_item **hash, Gif_Colormap *new_cm)
596 {
597 u_int32_t hash_code = COLOR_HASH_CODE(red, green, blue);
598 color_hash_item *prev = 0, *trav;
599
600 /* Is new_cm grayscale? We cache the answer here. */
601 static Gif_Colormap *cached_new_cm;
602 static int new_cm_grayscale;
603
604 for (trav = hash[hash_code]; trav; prev = trav, trav = trav->next)
605 if (trav->red == red && trav->green == green && trav->blue == blue)
606 return trav->pixel;
607
608 trav = new_color_hash_item(red, green, blue);
609 if (prev)
610 prev->next = trav;
611 else
612 hash[hash_code] = trav;
613
614 /* calculate whether new_cm is grayscale */
615 if (new_cm != cached_new_cm) {
616 int i;
617 Gif_Color *col = new_cm->col;
618 cached_new_cm = new_cm;
619 new_cm_grayscale = 1;
620 for (i = 0; i < new_cm->ncol && new_cm_grayscale; i++)
621 if (col[i].red != col[i].green || col[i].green != col[i].blue
622 || col[i].blue != col[i].red)
623 new_cm_grayscale = 0;
624 }
625
626 /* find the closest color in the new colormap */
627 {
628 Gif_Color *col = new_cm->col;
629 int ncol = new_cm->ncol, i, found;
630 u_int32_t min_dist = 0xFFFFFFFFU;
631
632 if (new_cm_grayscale) {
633 /* If the new colormap is 100% grayscale, then use distance in luminance
634 space instead of distance in RGB space. The weights for the R,G,B
635 components in luminance space are 0.299,0.587,0.114. We calculate a
636 gray value for the input color first and compare that against the
637 available grays in the colormap. Thanks to Christian Kumpf,
638 <kumpf@igd.fhg.de>, for providing a patch.
639
640 Note on the calculation of `gray': Using the factors 306, 601, and
641 117 (proportional to 0.299,0.587,0.114) we get a scaled gray value
642 between 0 and 255 * 1024. */
643 int gray = 306 * red + 601 * green + 117 * blue;
644 for (i = 0; i < ncol; i++)
645 if (col[i].haspixel != 255) {
646 int in_gray = 1024 * col[i].red;
647 u_int32_t dist = abs(gray - in_gray);
648 if (dist < min_dist) {
649 min_dist = dist;
650 found = i;
651 }
652 }
653
654 } else {
655 /* Use straight-line Euclidean distance in RGB space */
656 for (i = 0; i < ncol; i++)
657 if (col[i].haspixel != 255) {
658 u_int32_t dist = (red - col[i].red) * (red - col[i].red)
659 + (green - col[i].green) * (green - col[i].green)
660 + (blue - col[i].blue) * (blue - col[i].blue);
661 if (dist < min_dist) {
662 min_dist = dist;
663 found = i;
664 }
665 }
666 }
667
668 trav->pixel = found;
669 return found;
670 }
671 }
672
673
674 void
colormap_image_posterize(Gif_Image * gfi,byte * new_data,Gif_Colormap * old_cm,Gif_Colormap * new_cm,color_hash_item ** hash,u_int32_t * histogram)675 colormap_image_posterize(Gif_Image *gfi, byte *new_data,
676 Gif_Colormap *old_cm, Gif_Colormap *new_cm,
677 color_hash_item **hash, u_int32_t *histogram)
678 {
679 int ncol = old_cm->ncol;
680 Gif_Color *col = old_cm->col;
681 int map[256];
682 int i, j;
683 int transparent = gfi->transparent;
684
685 /* find closest colors in new colormap */
686 for (i = 0; i < ncol; i++)
687 if (col[i].haspixel)
688 map[i] = col[i].pixel;
689 else {
690 map[i] = col[i].pixel =
691 hash_color(col[i].red, col[i].green, col[i].blue, hash, new_cm);
692 col[i].haspixel = 1;
693 }
694
695 /* map image */
696 for (j = 0; j < gfi->height; j++) {
697 byte *data = gfi->img[j];
698 for (i = 0; i < gfi->width; i++, data++, new_data++)
699 if (*data != transparent) {
700 *new_data = map[*data];
701 histogram[*new_data]++;
702 }
703 }
704 }
705
706
707 #define DITHER_SCALE 1024
708 #define DITHER_SCALE_M1 (DITHER_SCALE-1)
709 #define N_RANDOM_VALUES 512
710
711 void
colormap_image_floyd_steinberg(Gif_Image * gfi,byte * all_new_data,Gif_Colormap * old_cm,Gif_Colormap * new_cm,color_hash_item ** hash,u_int32_t * histogram)712 colormap_image_floyd_steinberg(Gif_Image *gfi, byte *all_new_data,
713 Gif_Colormap *old_cm, Gif_Colormap *new_cm,
714 color_hash_item **hash, u_int32_t *histogram)
715 {
716 static int32_t *random_values = 0;
717
718 int width = gfi->width;
719 int dither_direction = 0;
720 int transparent = gfi->transparent;
721 int i, j;
722 int32_t *r_err, *g_err, *b_err, *r_err1, *g_err1, *b_err1;
723 Gif_Color *col = old_cm->col;
724 Gif_Color *new_col = new_cm->col;
725
726 /* This code was written with reference to ppmquant by Jef Poskanzer, part
727 of the pbmplus package. */
728
729 /* Initialize Floyd-Steinberg error vectors to small random values, so we
730 don't get artifacts on the top row */
731 r_err = Gif_NewArray(int32_t, width + 2);
732 g_err = Gif_NewArray(int32_t, width + 2);
733 b_err = Gif_NewArray(int32_t, width + 2);
734 r_err1 = Gif_NewArray(int32_t, width + 2);
735 g_err1 = Gif_NewArray(int32_t, width + 2);
736 b_err1 = Gif_NewArray(int32_t, width + 2);
737 /* Use the same random values on each call in an attempt to minimize
738 "jumping dithering" effects on animations */
739 if (!random_values) {
740 random_values = Gif_NewArray(int32_t, N_RANDOM_VALUES);
741 for (i = 0; i < N_RANDOM_VALUES; i++)
742 random_values[i] = RANDOM() % (DITHER_SCALE_M1 * 2) - DITHER_SCALE_M1;
743 }
744 for (i = 0; i < gfi->width + 2; i++) {
745 int j = (i + gfi->left) * 3;
746 r_err[i] = random_values[ (j + 0) % N_RANDOM_VALUES ];
747 g_err[i] = random_values[ (j + 1) % N_RANDOM_VALUES ];
748 b_err[i] = random_values[ (j + 2) % N_RANDOM_VALUES ];
749 }
750 /* *_err1 initialized below */
751
752 /* Do the image! */
753 for (j = 0; j < gfi->height; j++) {
754 int d0, d1, d2, d3; /* used for error diffusion */
755 byte *data, *new_data;
756 int x;
757
758 if (dither_direction) {
759 x = width - 1;
760 d0 = 0, d1 = 2, d2 = 1, d3 = 0;
761 } else {
762 x = 0;
763 d0 = 2, d1 = 0, d2 = 1, d3 = 2;
764 }
765 data = &gfi->img[j][x];
766 new_data = all_new_data + j * width + x;
767
768 for (i = 0; i < width + 2; i++)
769 r_err1[i] = g_err1[i] = b_err1[i] = 0;
770
771 /* Do a single row */
772 while (x >= 0 && x < width) {
773 int e, use_r, use_g, use_b;
774
775 /* the transparent color never gets adjusted */
776 if (*data == transparent)
777 goto next;
778
779 /* use Floyd-Steinberg errors to adjust actual color */
780 use_r = col[*data].red + r_err[x+1] / DITHER_SCALE;
781 use_g = col[*data].green + g_err[x+1] / DITHER_SCALE;
782 use_b = col[*data].blue + b_err[x+1] / DITHER_SCALE;
783 use_r = max(use_r, 0); use_r = min(use_r, 255);
784 use_g = max(use_g, 0); use_g = min(use_g, 255);
785 use_b = max(use_b, 0); use_b = min(use_b, 255);
786
787 *new_data = hash_color(use_r, use_g, use_b, hash, new_cm);
788 histogram[*new_data]++;
789
790 /* calculate and propagate the error between desired and selected color.
791 Assume that, with a large scale (1024), we don't need to worry about
792 image artifacts caused by error accumulation (the fact that the
793 error terms might not sum to the error). */
794 e = (use_r - new_col[*new_data].red) * DITHER_SCALE;
795 if (e) {
796 r_err [x+d0] += (e * 7) / 16;
797 r_err1[x+d1] += (e * 3) / 16;
798 r_err1[x+d2] += (e * 5) / 16;
799 r_err1[x+d3] += e / 16;
800 }
801
802 e = (use_g - new_col[*new_data].green) * DITHER_SCALE;
803 if (e) {
804 g_err [x+d0] += (e * 7) / 16;
805 g_err1[x+d1] += (e * 3) / 16;
806 g_err1[x+d2] += (e * 5) / 16;
807 g_err1[x+d3] += e / 16;
808 }
809
810 e = (use_b - new_col[*new_data].blue) * DITHER_SCALE;
811 if (e) {
812 b_err [x+d0] += (e * 7) / 16;
813 b_err1[x+d1] += (e * 3) / 16;
814 b_err1[x+d2] += (e * 5) / 16;
815 b_err1[x+d3] += e / 16;
816 }
817
818 next:
819 if (dither_direction)
820 x--, data--, new_data--;
821 else
822 x++, data++, new_data++;
823 }
824 /* Did a single row */
825
826 /* change dithering directions */
827 {
828 int32_t *temp;
829 temp = r_err; r_err = r_err1; r_err1 = temp;
830 temp = g_err; g_err = g_err1; g_err1 = temp;
831 temp = b_err; b_err = b_err1; b_err1 = temp;
832 dither_direction = !dither_direction;
833 }
834 }
835
836 /* delete temporary storage */
837 Gif_DeleteArray(r_err);
838 Gif_DeleteArray(g_err);
839 Gif_DeleteArray(b_err);
840 Gif_DeleteArray(r_err1);
841 Gif_DeleteArray(g_err1);
842 Gif_DeleteArray(b_err1);
843 }
844
845
846 /* return value 1 means run the image_changer again */
847 static int
try_assign_transparency(Gif_Image * gfi,Gif_Colormap * old_cm,byte * new_data,Gif_Colormap * new_cm,int * new_ncol,u_int32_t * histogram)848 try_assign_transparency(Gif_Image *gfi, Gif_Colormap *old_cm, byte *new_data,
849 Gif_Colormap *new_cm, int *new_ncol,
850 u_int32_t *histogram)
851 {
852 u_int32_t min_used;
853 int i, j;
854 int transparent = gfi->transparent;
855 int new_transparent = -1;
856 Gif_Color transp_value;
857
858 if (transparent < 0)
859 return 0;
860
861 if (old_cm)
862 transp_value = old_cm->col[transparent];
863
864 /* look for an unused pixel in the existing colormap; prefer the same color
865 we had */
866 for (i = 0; i < *new_ncol; i++)
867 if (histogram[i] == 0 && GIF_COLOREQ(&transp_value, &new_cm->col[i])) {
868 new_transparent = i;
869 goto found;
870 }
871 for (i = 0; i < *new_ncol; i++)
872 if (histogram[i] == 0) {
873 new_transparent = i;
874 goto found;
875 }
876
877 /* try to expand the colormap */
878 if (*new_ncol < 256) {
879 assert(*new_ncol < new_cm->capacity);
880 new_transparent = *new_ncol;
881 new_cm->col[new_transparent] = transp_value;
882 (*new_ncol)++;
883 goto found;
884 }
885
886 /* not found: mark the least-frequently-used color as the new transparent
887 color and return 1 (meaning `dither again') */
888 assert(*new_ncol == 256);
889 min_used = 0xFFFFFFFFU;
890 for (i = 0; i < 256; i++)
891 if (histogram[i] < min_used) {
892 new_transparent = i;
893 min_used = histogram[i];
894 }
895 new_cm->col[new_transparent].haspixel = 255; /* mark it unusable */
896 return 1;
897
898 found:
899 for (j = 0; j < gfi->height; j++) {
900 byte *data = gfi->img[j];
901 for (i = 0; i < gfi->width; i++, data++, new_data++)
902 if (*data == transparent)
903 *new_data = new_transparent;
904 }
905
906 gfi->transparent = new_transparent;
907 return 0;
908 }
909
910 void
colormap_stream(Gif_Stream * gfs,Gif_Colormap * new_cm,colormap_image_func image_changer)911 colormap_stream(Gif_Stream *gfs, Gif_Colormap *new_cm,
912 colormap_image_func image_changer)
913 {
914 color_hash_item **hash = new_color_hash();
915 int background_transparent = gfs->images[0]->transparent >= 0;
916 Gif_Color *new_col = new_cm->col;
917 int new_ncol = new_cm->ncol;
918 int imagei, j;
919 int compress_new_cm = 1;
920
921 /* make sure colormap has enough space */
922 if (new_cm->capacity < 256) {
923 Gif_Color *x = Gif_NewArray(Gif_Color, 256);
924 memcpy(x, new_col, sizeof(Gif_Color) * new_ncol);
925 Gif_DeleteArray(new_col);
926 new_cm->col = new_col = x;
927 new_cm->capacity = 256;
928 }
929 assert(new_cm->capacity >= 256);
930
931 /* new_col[j].pixel == number of pixels with color j in the new image. */
932 for (j = 0; j < 256; j++)
933 new_col[j].pixel = 0;
934
935 for (imagei = 0; imagei < gfs->nimages; imagei++) {
936 Gif_Image *gfi = gfs->images[imagei];
937 Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
938
939 if (gfcm) {
940 /* If there was an old colormap, change the image data */
941 byte *new_data = Gif_NewArray(byte, gfi->width * gfi->height);
942 u_int32_t histogram[256];
943 unmark_colors(new_cm);
944 unmark_colors(gfcm);
945
946 do {
947 for (j = 0; j < 256; j++) histogram[j] = 0;
948 image_changer(gfi, new_data, gfcm, new_cm, hash, histogram);
949 } while (try_assign_transparency(gfi, gfcm, new_data, new_cm, &new_ncol,
950 histogram));
951
952 Gif_ReleaseUncompressedImage(gfi);
953 Gif_SetUncompressedImage(gfi, new_data, Gif_DeleteArrayFunc, 0);
954
955 /* update count of used colors */
956 for (j = 0; j < 256; j++)
957 new_col[j].pixel += histogram[j];
958 if (gfi->transparent >= 0)
959 /* we don't have data on the number of used colors for transparency
960 so fudge it. */
961 new_col[gfi->transparent].pixel += gfi->width * gfi->height / 8;
962
963 } else {
964 /* Can't compress new_cm afterwards if we didn't actively change colors
965 over */
966 compress_new_cm = 0;
967 }
968
969 if (gfi->local) {
970 Gif_DeleteColormap(gfi->local);
971 gfi->local = 0;
972 }
973 }
974
975 /* Set new_cm->ncol from new_ncol. We didn't update new_cm->ncol before so
976 the closest-color algorithms wouldn't see any new transparent colors.
977 That way added transparent colors were only used for transparency. */
978 new_cm->ncol = new_ncol;
979
980 /* change the background. I hate the background by now */
981 if (background_transparent)
982 gfs->background = gfs->images[0]->transparent;
983 else if (gfs->global && gfs->background < gfs->global->ncol) {
984 Gif_Color *c = &gfs->global->col[ gfs->background ];
985 gfs->background = hash_color(c->red, c->green, c->blue, hash, new_cm);
986 new_col[gfs->background].pixel++;
987 }
988
989 Gif_DeleteColormap(gfs->global);
990
991 /* We may have used only a subset of the colors in new_cm. We try to store
992 only that subset, just as if we'd piped the output of `gifsicle
993 --use-colormap=X' through `gifsicle' another time. */
994 gfs->global = Gif_CopyColormap(new_cm);
995 if (compress_new_cm) {
996 /* only bother to recompress if we'll get anything out of it */
997 compress_new_cm = 0;
998 for (j = 0; j < new_cm->ncol - 1; j++)
999 if (new_col[j].pixel == 0 || new_col[j].pixel < new_col[j+1].pixel) {
1000 compress_new_cm = 1;
1001 break;
1002 }
1003 }
1004
1005 if (compress_new_cm) {
1006 int map[256];
1007
1008 /* Gif_CopyColormap copies the `pixel' values as well */
1009 new_col = gfs->global->col;
1010 for (j = 0; j < new_cm->ncol; j++)
1011 new_col[j].haspixel = j;
1012
1013 /* sort based on popularity */
1014 qsort(new_col, new_cm->ncol, sizeof(Gif_Color), popularity_sort_compare);
1015
1016 /* set up the map and reduce the number of colors */
1017 for (j = 0; j < new_cm->ncol; j++)
1018 map[ new_col[j].haspixel ] = j;
1019 for (j = 0; j < new_cm->ncol; j++)
1020 if (!new_col[j].pixel) {
1021 gfs->global->ncol = j;
1022 break;
1023 }
1024
1025 /* map the image data, transparencies, and background */
1026 gfs->background = map[gfs->background];
1027 for (imagei = 0; imagei < gfs->nimages; imagei++) {
1028 Gif_Image *gfi = gfs->images[imagei];
1029 u_int32_t size;
1030 byte *data = gfi->image_data;
1031 for (size = gfi->width * gfi->height; size > 0; size--, data++)
1032 *data = map[*data];
1033 if (gfi->transparent >= 0)
1034 gfi->transparent = map[gfi->transparent];
1035 }
1036 }
1037
1038 /* free storage */
1039 free_all_color_hash_items();
1040 Gif_DeleteArray(hash);
1041 }
1042