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 {
00016 u_int16_t left;
00017 u_int16_t top;
00018 u_int16_t width;
00019 u_int16_t height;
00020 u_int32_t size;
00021 byte disposal;
00022 int transparent;
00023 byte *needed_colors;
00024 u_int16_t required_color_count;
00025 int32_t active_penalty;
00026 int32_t global_penalty;
00027 int32_t colormap_penalty;
00028 Gif_Image *new_gfi;
00029 } Gif_OptData;
00030
00031
00032 static int screen_width;
00033 static int screen_height;
00034
00035
00036 static Gif_Colormap *all_colormap;
00037
00038
00039 static Gif_Colormap *in_global_map;
00040
00041
00042 static Gif_Colormap *out_global_map;
00043
00044 #define TRANSP (0)
00045 static u_int16_t background;
00046 #define NOT_IN_OUT_GLOBAL (256)
00047 static u_int16_t *last_data;
00048 static u_int16_t *this_data;
00049 static u_int16_t *next_data;
00050 static int image_index;
00051
00052 static int gif_color_count;
00053
00054
00055
00056
00057
00058
00059
00060 Gif_OptData *
00061 new_opt_data(void)
00062 {
00063 Gif_OptData *od = Gif_New(Gif_OptData);
00064 od->needed_colors = 0;
00065 od->global_penalty = 1;
00066 return od;
00067 }
00068
00069 void
00070 delete_opt_data(Gif_OptData *od)
00071 {
00072 if (!od) return;
00073 Gif_DeleteArray(od->needed_colors);
00074 Gif_Delete(od);
00075 }
00076
00077
00078
00079
00080
00081
00082
00083 void
00084 colormap_combine(Gif_Colormap *dst, Gif_Colormap *src)
00085 {
00086 Gif_Color *src_col, *dst_col;
00087 int i, j;
00088
00089
00090 if (dst->ncol + src->ncol >= dst->capacity) {
00091 dst->capacity *= 2;
00092 Gif_ReArray(dst->col, Gif_Color, dst->capacity);
00093 }
00094
00095 src_col = src->col;
00096 dst_col = dst->col;
00097 for (i = 0; i < src->ncol; i++, src_col++) {
00098 for (j = 1; j < dst->ncol; j++) {
00099 if (GIF_COLOREQ(src_col, &dst_col[j]))
00100 goto found;
00101 }
00102 dst_col[j] = *src_col;
00103 dst_col[j].pixel = 0;
00104 dst->ncol++;
00105 found:
00106 src_col->pixel = j;
00107 }
00108 }
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119 static int32_t *permuting_sort_values;
00120
00121 static int
00122 permuting_sorter_up(const void *v1, const void *v2)
00123 {
00124 const u_int16_t *n1 = (const u_int16_t *)v1;
00125 const u_int16_t *n2 = (const u_int16_t *)v2;
00126 return (permuting_sort_values[*n1] - permuting_sort_values[*n2]);
00127 }
00128
00129 static int
00130 permuting_sorter_down(const void *v1, const void *v2)
00131 {
00132 const u_int16_t *n1 = (const u_int16_t *)v1;
00133 const u_int16_t *n2 = (const u_int16_t *)v2;
00134 return (permuting_sort_values[*n2] - permuting_sort_values[*n1]);
00135 }
00136
00137 static u_int16_t *
00138 sort_permutation(u_int16_t *perm, int size, int32_t *values, int is_down)
00139 {
00140 permuting_sort_values = values;
00141 if (is_down)
00142 qsort(perm, size, sizeof(u_int16_t), permuting_sorter_down);
00143 else
00144 qsort(perm, size, sizeof(u_int16_t), permuting_sorter_up);
00145 permuting_sort_values = 0;
00146 return perm;
00147 }
00148
00149
00150
00151
00152
00153
00154 static void
00155 copy_data_area(u_int16_t *dst, u_int16_t *src, Gif_Image *area)
00156 {
00157 int y, width, height;
00158 if (!area) return;
00159 width = area->width;
00160 height = area->height;
00161 dst += area->top * screen_width + area->left;
00162 src += area->top * screen_width + area->left;
00163 for (y = 0; y < height; y++) {
00164 memcpy(dst, src, sizeof(u_int16_t) * width);
00165 dst += screen_width;
00166 src += screen_width;
00167 }
00168 }
00169
00170 static void
00171 copy_data_area_subimage(u_int16_t *dst, u_int16_t *src, Gif_OptData *area)
00172 {
00173 Gif_Image img;
00174 img.left = area->left;
00175 img.top = area->top;
00176 img.width = area->width;
00177 img.height = area->height;
00178 copy_data_area(dst, src, &img);
00179 }
00180
00181 static void
00182 fill_data_area(u_int16_t *dst, u_int16_t value, Gif_Image *area)
00183 {
00184 int x, y;
00185 int width = area->width;
00186 int height = area->height;
00187 dst += area->top * screen_width + area->left;
00188 for (y = 0; y < height; y++) {
00189 for (x = 0; x < width; x++)
00190 dst[x] = value;
00191 dst += screen_width;
00192 }
00193 }
00194
00195 static void
00196 fill_data_area_subimage(u_int16_t *dst, u_int16_t value, Gif_OptData *area)
00197 {
00198 Gif_Image img;
00199 img.left = area->left;
00200 img.top = area->top;
00201 img.width = area->width;
00202 img.height = area->height;
00203 fill_data_area(dst, value, &img);
00204 }
00205
00206 static void
00207 erase_screen(u_int16_t *dst)
00208 {
00209 u_int32_t i;
00210 u_int32_t screen_size = screen_width * screen_height;
00211 for (i = 0; i < screen_size; i++)
00212 *dst++ = background;
00213 }
00214
00215
00216
00217
00218
00219 static void
00220 apply_frame(u_int16_t *dst, Gif_Image *gfi, int replace)
00221 {
00222 int i, y;
00223 u_int16_t map[256];
00224 Gif_Colormap *colormap = gfi->local ? gfi->local : in_global_map;
00225
00226
00227 for (i = 0; i < colormap->ncol; i++)
00228 map[i] = colormap->col[i].pixel;
00229
00230 for (i = colormap->ncol; i < 256; i++)
00231 map[i] = colormap->col[0].pixel;
00232 if (gfi->transparent >= 0 && gfi->transparent < 256)
00233 map[gfi->transparent] = TRANSP;
00234 else
00235 replace = 1;
00236
00237
00238 dst += gfi->left + gfi->top * screen_width;
00239 for (y = 0; y < gfi->height; y++) {
00240 byte *gfi_pointer = gfi->img[y];
00241 int x;
00242
00243 if (replace)
00244 for (x = 0; x < gfi->width; x++)
00245 dst[x] = map[gfi_pointer[x]];
00246 else
00247 for (x = 0; x < gfi->width; x++) {
00248 u_int16_t new_pixel = map[gfi_pointer[x]];
00249 if (new_pixel != TRANSP) dst[x] = new_pixel;
00250 }
00251
00252 dst += screen_width;
00253 }
00254 }
00255
00256 static void
00257 apply_frame_disposal(u_int16_t *into_data, u_int16_t *from_data,
00258 Gif_Image *gfi)
00259 {
00260 if (gfi->disposal == GIF_DISPOSAL_NONE
00261 || gfi->disposal == GIF_DISPOSAL_ASIS)
00262 copy_data_area(into_data, from_data, gfi);
00263
00264 else if (gfi->disposal == GIF_DISPOSAL_BACKGROUND)
00265 fill_data_area(into_data, background, gfi);
00266 }
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276 static void
00277 find_difference_bounds(Gif_OptData *bounds, Gif_Image *gfi, Gif_Image *last)
00278 {
00279 int lf, rt, lf_min, rt_max, tp, bt, x, y;
00280
00281
00282
00283 if (!last || last->disposal == GIF_DISPOSAL_NONE
00284 || last->disposal == GIF_DISPOSAL_ASIS) {
00285 lf_min = gfi->left;
00286 rt_max = gfi->left + gfi->width - 1;
00287 tp = gfi->top;
00288 bt = gfi->top + gfi->height - 1;
00289 } else {
00290 lf_min = 0;
00291 rt_max = screen_width - 1;
00292 tp = 0;
00293 bt = screen_height - 1;
00294 }
00295
00296 for (; tp < screen_height; tp++)
00297 if (memcmp(last_data + screen_width * tp, this_data + screen_width * tp,
00298 screen_width * sizeof(u_int16_t)) != 0)
00299 break;
00300 for (; bt >= tp; bt--)
00301 if (memcmp(last_data + screen_width * bt, this_data + screen_width * bt,
00302 screen_width * sizeof(u_int16_t)) != 0)
00303 break;
00304
00305 lf = screen_width;
00306 rt = 0;
00307 for (y = tp; y <= bt; y++) {
00308 u_int16_t *ld = last_data + screen_width * y;
00309 u_int16_t *td = this_data + screen_width * y;
00310 for (x = lf_min; x < lf; x++)
00311 if (ld[x] != td[x])
00312 break;
00313 lf = x;
00314
00315 for (x = rt_max; x > rt; x--)
00316 if (ld[x] != td[x])
00317 break;
00318 rt = x;
00319 }
00320
00321
00322 if (tp > bt)
00323 tp = bt = lf = rt = 0;
00324
00325 bounds->left = lf;
00326 bounds->top = tp;
00327 bounds->width = rt + 1 - lf;
00328 bounds->height = bt + 1 - tp;
00329 }
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340 static void
00341 expand_difference_bounds(Gif_OptData *bounds, Gif_Image *this_bounds)
00342 {
00343 int x, y;
00344
00345 int lf = bounds->left, tp = bounds->top;
00346 int rt = lf + bounds->width - 1, bt = tp + bounds->height - 1;
00347
00348 int tlf = this_bounds->left, ttp = this_bounds->top;
00349 int trt = tlf + this_bounds->width - 1, tbt = ttp + this_bounds->height - 1;
00350
00351 if (lf > rt || tp > bt)
00352 lf = 0, tp = 0, rt = screen_width - 1, bt = screen_height - 1;
00353
00354 for (y = ttp; y < tp; y++) {
00355 u_int16_t *now = this_data + screen_width * y;
00356 u_int16_t *next = next_data + screen_width * y;
00357 for (x = tlf; x <= trt; x++)
00358 if (now[x] != TRANSP && next[x] == TRANSP)
00359 goto found_top;
00360 }
00361 found_top:
00362 tp = y;
00363
00364 for (y = tbt; y > bt; y--) {
00365 u_int16_t *now = this_data + screen_width * y;
00366 u_int16_t *next = next_data + screen_width * y;
00367 for (x = tlf; x <= trt; x++)
00368 if (now[x] != TRANSP && next[x] == TRANSP)
00369 goto found_bottom;
00370 }
00371 found_bottom:
00372 bt = y;
00373
00374 for (x = tlf; x < lf; x++) {
00375 u_int16_t *now = this_data + x;
00376 u_int16_t *next = next_data + x;
00377 for (y = tp; y <= bt; y++)
00378 if (now[y*screen_width] != TRANSP && next[y*screen_width] == TRANSP)
00379 goto found_left;
00380 }
00381 found_left:
00382 lf = x;
00383
00384 for (x = trt; x > rt; x--) {
00385 u_int16_t *now = this_data + x;
00386 u_int16_t *next = next_data + x;
00387 for (y = tp; y <= bt; y++)
00388 if (now[y*screen_width] != TRANSP && next[y*screen_width] == TRANSP)
00389 goto found_right;
00390 }
00391 found_right:
00392 rt = x;
00393
00394 bounds->left = lf;
00395 bounds->top = tp;
00396 bounds->width = rt + 1 - lf;
00397 bounds->height = bt + 1 - tp;
00398 }
00399
00400
00401
00402
00403 static void
00404 fix_difference_bounds(Gif_OptData *bounds)
00405 {
00406 if (bounds->width == 0 || bounds->height == 0) {
00407 bounds->top = 0;
00408 bounds->left = 0;
00409 bounds->width = 1;
00410 bounds->height = 1;
00411 }
00412
00413 assert(bounds->top < screen_height && bounds->left < screen_width
00414 && bounds->top + bounds->height - 1 < screen_height
00415 && bounds->left + bounds->width - 1 < screen_width);
00416 }
00417
00418
00419
00420
00421
00422
00423 #define REQUIRED 2
00424 #define REPLACE_TRANSP 1
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436 static void
00437 get_used_colors(Gif_OptData *bounds, int use_transparency)
00438 {
00439 int top = bounds->top, width = bounds->width, height = bounds->height;
00440 int i, x, y;
00441 int all_ncol = all_colormap->ncol;
00442 byte *need = Gif_NewArray(byte, all_ncol);
00443
00444 for (i = 0; i < all_ncol; i++)
00445 need[i] = 0;
00446
00447
00448
00449
00450 for (y = top; y < top + height; y++) {
00451 u_int16_t *data = this_data + screen_width * y + bounds->left;
00452 u_int16_t *last = last_data + screen_width * y + bounds->left;
00453 for (x = 0; x < width; x++) {
00454 if (data[x] != last[x])
00455 need[data[x]] = REQUIRED;
00456 else if (need[data[x]] == 0)
00457 need[data[x]] = REPLACE_TRANSP;
00458 }
00459 }
00460 if (need[TRANSP])
00461 need[TRANSP] = REQUIRED;
00462
00463
00464 {
00465 int count[3];
00466
00467 count[0] = count[1] = count[2] = 0;
00468 for (i = 0; i < all_ncol; i++)
00469 count[need[i]]++;
00470
00471 if (use_transparency > 1 && !need[TRANSP] && count[REQUIRED] < 256) {
00472 need[TRANSP] = REQUIRED;
00473 count[REQUIRED]++;
00474 }
00475
00476 if (count[REPLACE_TRANSP] + count[REQUIRED] > 256)
00477 use_transparency = 1;
00478
00479 if (count[REPLACE_TRANSP] > 0 && use_transparency && !need[TRANSP]) {
00480 need[TRANSP] = REQUIRED;
00481 count[REQUIRED]++;
00482 }
00483
00484
00485 if (!use_transparency) {
00486 for (i = 0; i < all_ncol; i++)
00487 if (need[i] == REPLACE_TRANSP) need[i] = REQUIRED;
00488 count[REQUIRED] += count[REPLACE_TRANSP];
00489 }
00490
00491 if (count[REQUIRED] > 256)
00492 fatal_error("more than 256 colors required in a frame", count[REQUIRED]);
00493
00494
00495 if (count[REQUIRED] < 256 && use_transparency && !need[TRANSP]) {
00496 need[TRANSP] = REQUIRED;
00497 count[REQUIRED]++;
00498 }
00499 bounds->required_color_count = count[REQUIRED];
00500 }
00501
00502 bounds->needed_colors = need;
00503 }
00504
00505
00506
00507
00508
00509
00510 static void
00511 create_subimages(Gif_Stream *gfs, int optimize_level)
00512 {
00513 int screen_size;
00514 Gif_Image *last_gfi;
00515 int next_data_valid;
00516 u_int16_t *previous_data = 0;
00517
00518 screen_size = screen_width * screen_height;
00519
00520 next_data = Gif_NewArray(u_int16_t, screen_size);
00521 next_data_valid = 0;
00522
00523
00524 erase_screen(last_data);
00525 erase_screen(this_data);
00526 last_gfi = 0;
00527
00528
00529
00530
00531 for (image_index = 0; image_index < gfs->nimages; image_index++) {
00532 Gif_Image *gfi = gfs->images[image_index];
00533 Gif_OptData *subimage = new_opt_data();
00534
00535 if (!gfi->img) Gif_UncompressImage(gfi);
00536 Gif_ReleaseCompressedImage(gfi);
00537
00538
00539 if (gfi->disposal == GIF_DISPOSAL_PREVIOUS) {
00540 previous_data = Gif_NewArray(u_int16_t, screen_size);
00541 copy_data_area(previous_data, this_data, gfi);
00542 }
00543
00544
00545 if (next_data_valid) {
00546 u_int16_t *temp = this_data;
00547 this_data = next_data;
00548 next_data = temp;
00549 next_data_valid = 0;
00550 } else
00551 apply_frame(this_data, gfi, 0);
00552
00553
00554 subimage->disposal = GIF_DISPOSAL_ASIS;
00555 if (image_index > 0)
00556 find_difference_bounds(subimage, gfi, last_gfi);
00557 else {
00558 subimage->left = gfi->left;
00559 subimage->top = gfi->top;
00560 subimage->width = gfi->width;
00561 subimage->height = gfi->height;
00562 }
00563
00564
00565
00566 if (gfi->disposal == GIF_DISPOSAL_BACKGROUND
00567 && background == TRANSP
00568 && image_index < gfs->nimages - 1) {
00569
00570 Gif_Image *next_gfi = gfs->images[image_index + 1];
00571 memcpy(next_data, this_data, screen_size * sizeof(u_int16_t));
00572 apply_frame_disposal(next_data, this_data, gfi);
00573 apply_frame(next_data, next_gfi, 0);
00574 next_data_valid = 1;
00575
00576 expand_difference_bounds(subimage, gfi);
00577 subimage->disposal = GIF_DISPOSAL_BACKGROUND;
00578 }
00579
00580 fix_difference_bounds(subimage);
00581
00582
00583 {
00584 int use_transparency = optimize_level > 1 && image_index > 0;
00585 if (image_index == 0 && background == TRANSP)
00586 use_transparency = 2;
00587 get_used_colors(subimage, use_transparency);
00588 }
00589
00590 gfi->user_data = subimage;
00591 last_gfi = gfi;
00592
00593
00594
00595
00596
00597
00598
00599 if (subimage->disposal == GIF_DISPOSAL_BACKGROUND)
00600 fill_data_area_subimage(last_data, background, subimage);
00601 else
00602 copy_data_area_subimage(last_data, this_data, subimage);
00603
00604 if (last_gfi->disposal == GIF_DISPOSAL_BACKGROUND)
00605 fill_data_area(this_data, background, last_gfi);
00606 else if (last_gfi->disposal == GIF_DISPOSAL_PREVIOUS) {
00607 copy_data_area(this_data, previous_data, last_gfi);
00608 Gif_DeleteArray(previous_data);
00609 }
00610 }
00611
00612 Gif_DeleteArray(next_data);
00613 }
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635 static void
00636 increment_penalties(Gif_OptData *opt, int32_t *penalty, int32_t delta)
00637 {
00638 int i;
00639 int all_ncol = all_colormap->ncol;
00640 byte *need = opt->needed_colors;
00641 for (i = 1; i < all_ncol; i++)
00642 if (need[i] == REQUIRED)
00643 penalty[i] += delta;
00644 }
00645
00646 static void
00647 create_out_global_map(Gif_Stream *gfs)
00648 {
00649 int all_ncol = all_colormap->ncol;
00650 int32_t *penalty = Gif_NewArray(int32_t, all_ncol);
00651 u_int16_t *permute = Gif_NewArray(u_int16_t, all_ncol);
00652 u_int16_t *ordering = Gif_NewArray(u_int16_t, all_ncol);
00653 int cur_ncol, i, imagei;
00654 int nglobal_all = (all_ncol <= 257 ? all_ncol - 1 : 256);
00655 int permutation_changed;
00656
00657
00658 for (i = 0; i < all_ncol - 1; i++)
00659 permute[i] = i + 1;
00660
00661
00662 for (imagei = 0; imagei < gfs->nimages; imagei++) {
00663 Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data;
00664 opt->global_penalty = opt->colormap_penalty = 1;
00665 for (i = 2; i < opt->required_color_count; i *= 2)
00666 opt->colormap_penalty *= 3;
00667 opt->active_penalty =
00668 (all_ncol > 257 ? opt->colormap_penalty : opt->global_penalty);
00669 }
00670
00671
00672 for (i = 1; i < all_ncol; i++)
00673 penalty[i] = 0;
00674 for (imagei = 0; imagei < gfs->nimages; imagei++) {
00675 Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data;
00676 increment_penalties(opt, penalty, opt->active_penalty);
00677 }
00678 permutation_changed = 1;
00679
00680
00681 for (cur_ncol = all_ncol - 1; cur_ncol; cur_ncol--) {
00682 u_int16_t removed;
00683
00684
00685 if (permutation_changed)
00686 sort_permutation(permute, cur_ncol, penalty, 1);
00687 permutation_changed = 0;
00688
00689
00690 removed = permute[cur_ncol - 1];
00691 ordering[removed] = cur_ncol - 1;
00692
00693
00694 for (imagei = 0; imagei < gfs->nimages; imagei++) {
00695 Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data;
00696 byte *need = opt->needed_colors;
00697 if (opt->global_penalty > 0 && need[removed] == REQUIRED) {
00698 increment_penalties(opt, penalty, -opt->active_penalty);
00699 opt->global_penalty = 0;
00700 opt->colormap_penalty = (cur_ncol > 256 ? -1 : 0);
00701 permutation_changed = 1;
00702 }
00703 }
00704
00705
00706 if (cur_ncol == 257) {
00707 for (i = 0; i < all_ncol; i++)
00708 penalty[i] = 0;
00709 for (imagei = 0; imagei < gfs->nimages; imagei++) {
00710 Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data;
00711 opt->active_penalty = opt->global_penalty;
00712 increment_penalties(opt, penalty, opt->global_penalty);
00713 }
00714 permutation_changed = 1;
00715 }
00716 }
00717
00718
00719 if (background != TRANSP && ordering[background] >= 256) {
00720 u_int16_t other = permute[255];
00721 ordering[other] = ordering[background];
00722 ordering[background] = 255;
00723 }
00724
00725
00726 out_global_map = Gif_NewFullColormap(nglobal_all, 256);
00727
00728 for (i = 1; i < all_ncol; i++)
00729 if (ordering[i] < 256) {
00730 out_global_map->col[ordering[i]] = all_colormap->col[i];
00731 all_colormap->col[i].pixel = ordering[i];
00732 } else
00733 all_colormap->col[i].pixel = NOT_IN_OUT_GLOBAL;
00734
00735
00736 if (background != TRANSP)
00737 gfs->background = ordering[background];
00738
00739
00740 Gif_DeleteArray(penalty);
00741 Gif_DeleteArray(permute);
00742 Gif_DeleteArray(ordering);
00743 }
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756 static byte *
00757 prepare_colormap_map(Gif_Image *gfi, Gif_Colormap *into, byte *need)
00758 {
00759 int i;
00760 int is_global = (into == out_global_map);
00761
00762 int all_ncol = all_colormap->ncol;
00763 Gif_Color *all_col = all_colormap->col;
00764
00765 int ncol = into->ncol;
00766 Gif_Color *col = into->col;
00767
00768 byte *map = Gif_NewArray(byte, all_ncol);
00769 byte into_used[256];
00770
00771
00772
00773 for (i = 0; i < 256; i++)
00774 into_used[i] = 0;
00775
00776
00777
00778 for (i = 1; i < all_ncol; i++) {
00779 int val;
00780 if (need[i] != REQUIRED)
00781 continue;
00782
00783
00784 if (is_global) {
00785 val = all_col[i].pixel;
00786 if (val >= ncol) goto error;
00787 } else {
00788
00789 if (ncol == 256) goto error;
00790 val = ncol;
00791 col[val] = all_col[i];
00792 ncol++;
00793 }
00794
00795 map[i] = val;
00796 into_used[val] = 1;
00797 }
00798
00799
00800 gfi->transparent = -1;
00801 if (need[TRANSP]) {
00802 int transparent = -1;
00803
00804
00805
00806
00807 for (i = 0; i < ncol; i++)
00808 if (!into_used[i]) {
00809 transparent = i;
00810 break;
00811 }
00812
00813
00814
00815
00816
00817 if (transparent < 0) {
00818 if (ncol < 256) {
00819 transparent = ncol;
00820
00821 col[ncol] = all_col[TRANSP];
00822 } else
00823 goto error;
00824 }
00825
00826
00827 map[TRANSP] = transparent;
00828 for (i = 1; i < all_ncol; i++)
00829 if (need[i] == REPLACE_TRANSP)
00830 map[i] = transparent;
00831
00832 gfi->transparent = transparent;
00833 }
00834
00835
00836
00837 into->ncol = ncol;
00838 return map;
00839
00840 error:
00841
00842 Gif_DeleteArray(map);
00843 return 0;
00844 }
00845
00846
00847
00848
00849
00850 static int
00851 colormap_rgb_permutation_sorter(const void *v1, const void *v2)
00852 {
00853 const Gif_Color *col1 = (const Gif_Color *)v1;
00854 const Gif_Color *col2 = (const Gif_Color *)v2;
00855 int value1 = (col1->red << 16) | (col1->green << 8) | col1->blue;
00856 int value2 = (col2->red << 16) | (col2->green << 8) | col2->blue;
00857 return value1 - value2;
00858 }
00859
00860
00861
00862
00863
00864
00865 static byte *
00866 prepare_colormap(Gif_Image *gfi, byte *need)
00867 {
00868 byte *map;
00869
00870
00871 Gif_DeleteColormap(gfi->local);
00872 gfi->local = 0;
00873 map = prepare_colormap_map(gfi, out_global_map, need);
00874
00875 if (!map) {
00876
00877 byte permutation[256];
00878 Gif_Color *local_col;
00879 int i;
00880
00881 gfi->local = Gif_NewFullColormap(0, 256);
00882 map = prepare_colormap_map(gfi, gfi->local, need);
00883
00884
00885
00886 local_col = gfi->local->col;
00887 for (i = 0; i < gfi->local->ncol; i++)
00888 local_col[i].pixel = i;
00889
00890 qsort(local_col, gfi->local->ncol, sizeof(Gif_Color),
00891 colormap_rgb_permutation_sorter);
00892
00893 for (i = 0; i < gfi->local->ncol; i++)
00894 permutation[local_col[i].pixel] = i;
00895
00896 if (gfi->transparent >= gfi->local->ncol)
00897 permutation[gfi->transparent] = gfi->transparent;
00898
00899 for (i = 0; i < all_colormap->ncol; i++)
00900 map[i] = permutation[map[i]];
00901
00902 if (gfi->transparent >= 0)
00903 gfi->transparent = map[TRANSP];
00904 }
00905
00906 return map;
00907 }
00908
00909
00910
00911
00912
00913
00914
00915
00916
00917 static void
00918 simple_frame_data(Gif_Image *gfi, byte *map)
00919 {
00920 int top = gfi->top, width = gfi->width, height = gfi->height;
00921 int x, y;
00922
00923 for (y = 0; y < height; y++) {
00924 u_int16_t *from = this_data + screen_width * (y+top) + gfi->left;
00925 byte *into = gfi->image_data + y * width;
00926 for (x = 0; x < width; x++)
00927 *into++ = map[*from++];
00928 }
00929 }
00930
00931
00932
00933
00934
00935 static void
00936 transp_frame_data(Gif_Stream *gfs, Gif_Image *gfi, byte *map)
00937 {
00938 int top = gfi->top, width = gfi->width, height = gfi->height;
00939 int x, y;
00940 int transparent = gfi->transparent;
00941 u_int16_t *last = 0;
00942 u_int16_t *cur = 0;
00943 byte *data;
00944 int transparentizing;
00945 int run_length;
00946 int run_pixel_value = 0;
00947
00948
00949
00950 simple_frame_data(gfi, map);
00951 Gif_FullCompressImage(gfs, gfi, gif_write_flags);
00952
00953
00954
00955
00956
00957
00958
00959
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986
00987
00988 x = width;
00989 y = -1;
00990 data = gfi->image_data;
00991 transparentizing = 0;
00992 run_length = 0;
00993
00994 while (y < height) {
00995
00996 if (!transparentizing) {
00997
00998 while (x < width && !transparentizing) {
00999 *data = map[*cur];
01000
01001
01002 if (map[*cur] == transparent)
01003 transparentizing = 1;
01004 else if (*cur == *last) {
01005 if (*cur == run_pixel_value)
01006
01007 run_length++;
01008 else if (run_length > 0)
01009
01010 transparentizing = 1;
01011 else {
01012
01013 run_pixel_value = *cur;
01014 run_length = 1;
01015 }
01016 } else
01017 run_length = 0;
01018
01019 data++, last++, cur++, x++;
01020 }
01021
01022 if (transparentizing)
01023 memset(data - run_length - 1, transparent, run_length + 1);
01024
01025 } else
01026
01027 while (x < width && transparentizing) {
01028 if (*last == *cur || map[*cur] == transparent) {
01029 *data = transparent;
01030 data++, last++, cur++, x++;
01031 } else
01032
01033
01034 transparentizing = 0;
01035 }
01036
01037
01038 if (x >= width) {
01039 x = 0;
01040 y++;
01041 last = last_data + screen_width * (y+top) + gfi->left;
01042 cur = this_data + screen_width * (y+top) + gfi->left;
01043 }
01044 }
01045
01046
01047
01048 {
01049 byte *old_compressed = gfi->compressed;
01050 void (*old_free_compressed)(void *) = gfi->free_compressed;
01051 u_int32_t old_compressed_len = gfi->compressed_len;
01052 gfi->compressed = 0;
01053 Gif_FullCompressImage(gfs, gfi, gif_write_flags);
01054 if (gfi->compressed_len > old_compressed_len) {
01055 Gif_ReleaseCompressedImage(gfi);
01056 gfi->compressed = old_compressed;
01057 gfi->free_compressed = old_free_compressed;
01058 gfi->compressed_len = old_compressed_len;
01059 } else
01060 (*old_free_compressed)(old_compressed);
01061 Gif_ReleaseUncompressedImage(gfi);
01062 }
01063 }
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078
01079 static void
01080 create_new_image_data(Gif_Stream *gfs, int optimize_level)
01081 {
01082 Gif_Image cur_unopt_gfi;
01083
01084
01085 int screen_size = screen_width * screen_height;
01086 u_int16_t *previous_data = 0;
01087
01088 gfs->global = out_global_map;
01089
01090
01091 erase_screen(last_data);
01092 erase_screen(this_data);
01093
01094 for (image_index = 0; image_index < gfs->nimages; image_index++) {
01095 Gif_Image *cur_gfi = gfs->images[image_index];
01096 Gif_OptData *opt = (Gif_OptData *)cur_gfi->user_data;
01097
01098
01099 if (cur_gfi->disposal == GIF_DISPOSAL_PREVIOUS) {
01100 previous_data = Gif_NewArray(u_int16_t, screen_size);
01101 copy_data_area(previous_data, this_data, cur_gfi);
01102 }
01103
01104
01105 apply_frame(this_data, cur_gfi, 0);
01106
01107
01108
01109 cur_unopt_gfi = *cur_gfi;
01110
01111
01112 Gif_ReleaseUncompressedImage(cur_gfi);
01113 cur_gfi->left = opt->left;
01114 cur_gfi->top = opt->top;
01115 cur_gfi->width = opt->width;
01116 cur_gfi->height = opt->height;
01117 cur_gfi->disposal = opt->disposal;
01118 if (image_index > 0) cur_gfi->interlace = 0;
01119
01120
01121 {
01122 byte *map = prepare_colormap(cur_gfi, opt->needed_colors);
01123 byte *data = Gif_NewArray(byte, cur_gfi->width * cur_gfi->height);
01124 Gif_SetUncompressedImage(cur_gfi, data, Gif_DeleteArrayFunc, 0);
01125
01126
01127 if (optimize_level > 1 && image_index > 0)
01128 transp_frame_data(gfs, cur_gfi, map);
01129 else
01130 simple_frame_data(cur_gfi, map);
01131
01132 Gif_DeleteArray(map);
01133 }
01134
01135 delete_opt_data(opt);
01136 cur_gfi->user_data = 0;
01137
01138
01139
01140 if (cur_gfi->disposal == GIF_DISPOSAL_NONE
01141 || cur_gfi->disposal == GIF_DISPOSAL_ASIS)
01142 copy_data_area(last_data, this_data, cur_gfi);
01143 else if (cur_gfi->disposal == GIF_DISPOSAL_BACKGROUND)
01144 fill_data_area(last_data, background, cur_gfi);
01145 else
01146 assert(0 && "optimized frame has strange disposal");
01147
01148 if (cur_unopt_gfi.disposal == GIF_DISPOSAL_BACKGROUND)
01149 fill_data_area(this_data, background, &cur_unopt_gfi);
01150 else if (cur_unopt_gfi.disposal == GIF_DISPOSAL_PREVIOUS) {
01151 copy_data_area(this_data, previous_data, &cur_unopt_gfi);
01152 Gif_DeleteArray(previous_data);
01153 }
01154 }
01155 }
01156
01157
01158
01159
01160
01161
01162 static int
01163 initialize_optimizer(Gif_Stream *gfs, int optimize_level)
01164 {
01165 int i, screen_size;
01166
01167 if (gfs->nimages < 1)
01168 return 0;
01169
01170
01171 all_colormap = Gif_NewFullColormap(1, 384);
01172 all_colormap->col[0].red = 255;
01173 all_colormap->col[0].green = 255;
01174 all_colormap->col[0].blue = 255;
01175
01176 in_global_map = gfs->global;
01177 if (!in_global_map) {
01178 Gif_Color *col;
01179 in_global_map = Gif_NewFullColormap(256, 256);
01180 col = in_global_map->col;
01181 for (i = 0; i < 256; i++, col++)
01182 col->red = col->green = col->blue = i;
01183 }
01184
01185 {
01186 int any_globals = 0;
01187 int first_transparent = -1;
01188 for (i = 0; i < gfs->nimages; i++) {
01189 Gif_Image *gfi = gfs->images[i];
01190 if (gfi->local)
01191 colormap_combine(all_colormap, gfi->local);
01192 else
01193 any_globals = 1;
01194 if (gfi->transparent >= 0 && first_transparent < 0)
01195 first_transparent = i;
01196 }
01197 if (any_globals)
01198 colormap_combine(all_colormap, in_global_map);
01199
01200
01201 if (first_transparent >= 0) {
01202 Gif_Image *gfi = gfs->images[first_transparent];
01203 Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
01204 all_colormap->col[TRANSP] = gfcm->col[gfi->transparent];
01205 }
01206 }
01207
01208
01209 Gif_CalculateScreenSize(gfs, 0);
01210 screen_width = gfs->screen_width;
01211 screen_height = gfs->screen_height;
01212 for (i = 0; i < gfs->nimages; i++)
01213 Gif_ClipImage(gfs->images[i], 0, 0, screen_width, screen_height);
01214
01215
01216 screen_size = screen_width * screen_height;
01217 last_data = Gif_NewArray(u_int16_t, screen_size);
01218 this_data = Gif_NewArray(u_int16_t, screen_size);
01219
01220
01221 gif_color_count = 2;
01222 while (gif_color_count < gfs->global->ncol && gif_color_count < 256)
01223 gif_color_count *= 2;
01224
01225
01226 if (gfs->images[0]->transparent < 0
01227 && gfs->background < in_global_map->ncol)
01228 background = in_global_map->col[gfs->background].pixel;
01229 else
01230 background = TRANSP;
01231
01232 return 1;
01233 }
01234
01235 static void
01236 finalize_optimizer(Gif_Stream *gfs)
01237 {
01238 int i;
01239
01240 if (background == TRANSP)
01241 gfs->background = (byte)gfs->images[0]->transparent;
01242
01243
01244
01245
01246
01247 for (i = 0; i < gfs->nimages; i++)
01248 if (gfs->images[i]->disposal == GIF_DISPOSAL_ASIS
01249 && gfs->images[i]->delay == 0
01250 && gfs->images[i]->transparent < 0)
01251 gfs->images[i]->disposal = GIF_DISPOSAL_NONE;
01252
01253 Gif_DeleteColormap(in_global_map);
01254 Gif_DeleteColormap(all_colormap);
01255
01256 Gif_DeleteArray(last_data);
01257 Gif_DeleteArray(this_data);
01258 }
01259
01260
01261
01262
01263 void
01264 optimize_fragments(Gif_Stream *gfs, int optimize_level)
01265 {
01266 if (!initialize_optimizer(gfs, optimize_level))
01267 return;
01268
01269 create_subimages(gfs, optimize_level);
01270 create_out_global_map(gfs);
01271 create_new_image_data(gfs, optimize_level);
01272
01273 finalize_optimizer(gfs);
01274 }