00001
00002
00003
00004
00005
00006
00007
00008
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;
00071
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
00116
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
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
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
00151
00152 if (gfi->disposal == GIF_DISPOSAL_BACKGROUND)
00153 nbackground += gfi->width * gfi->height;
00154 }
00155
00156
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
00164 linear = Gif_NewArray(Gif_Color, hist.n + 1);
00165 i = 0;
00166
00167
00168
00169 if (ntransparent) {
00170 linear[0] = transparent_color;
00171 linear[0].haspixel = 255;
00172 linear[0].pixel = ntransparent;
00173 i++;
00174 }
00175
00176
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
00227
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
00245
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
00255
00256
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
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
00278 for (nadapt = 1; nadapt < adapt_size; nadapt++) {
00279 adaptive_slot *split = 0;
00280 Gif_Color minc, maxc, *slice;
00281
00282
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
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
00310
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
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
00332
00333
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
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
00382
00383
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
00393
00394
00395 assert_hist_transparency(hist, nhist);
00396
00397
00398
00399
00400
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
00410 if (adapt_size < 4)
00411 blend = 0;
00412
00413
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
00420 for (nadapt = 0; nadapt < adapt_size; nadapt++) {
00421 int chosen = 0;
00422
00423
00424 if (nadapt == 0 || (nadapt >= 10 && nadapt % 2 == 0)) {
00425
00426
00427 for (; chosen < nhist; chosen++)
00428 if (min_dist[chosen])
00429 break;
00430
00431 } else {
00432
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
00442 min_dist[chosen] = 0;
00443 closest[chosen] = nadapt;
00444
00445
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
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
00490
00491 if (3 * mismatch_pixel_total <= 2 * pixel_total)
00492 adapt[i] = hist[match];
00493 else {
00494
00495
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
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
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
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
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
00634
00635
00636
00637
00638
00639
00640
00641
00642
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
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
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
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
00727
00728
00729
00730
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
00738
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
00751
00752
00753 for (j = 0; j < gfi->height; j++) {
00754 int d0, d1, d2, d3;
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
00772 while (x >= 0 && x < width) {
00773 int e, use_r, use_g, use_b;
00774
00775
00776 if (*data == transparent)
00777 goto next;
00778
00779
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
00791
00792
00793
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
00825
00826
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
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
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
00865
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
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
00887
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;
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
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
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
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
00956 for (j = 0; j < 256; j++)
00957 new_col[j].pixel += histogram[j];
00958 if (gfi->transparent >= 0)
00959
00960
00961 new_col[gfi->transparent].pixel += gfi->width * gfi->height / 8;
00962
00963 } else {
00964
00965
00966 compress_new_cm = 0;
00967 }
00968
00969 if (gfi->local) {
00970 Gif_DeleteColormap(gfi->local);
00971 gfi->local = 0;
00972 }
00973 }
00974
00975
00976
00977
00978 new_cm->ncol = new_ncol;
00979
00980
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
00992
00993
00994 gfs->global = Gif_CopyColormap(new_cm);
00995 if (compress_new_cm) {
00996
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
01009 new_col = gfs->global->col;
01010 for (j = 0; j < new_cm->ncol; j++)
01011 new_col[j].haspixel = j;
01012
01013
01014 qsort(new_col, new_cm->ncol, sizeof(Gif_Color), popularity_sort_compare);
01015
01016
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
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
01039 free_all_color_hash_items();
01040 Gif_DeleteArray(hash);
01041 }