/* optimize.c - Functions to optimize animated GIFs. Copyright (C) 1997-9 Eddie Kohler, eddietwo@lcs.mit.edu This file is part of gifsicle. Gifsicle is free software. It is distributed under the GNU Public License, version 2 or later; you can copy, distribute, or alter it at will, as long as this notice is kept intact and this source code is made available. There is no warranty, express or implied. */ #include "config.h" #include "gifsicle.h" #include #include typedef struct { u_int16_t left; u_int16_t top; u_int16_t width; u_int16_t height; u_int32_t size; byte disposal; int transparent; byte *needed_colors; u_int16_t required_color_count; int32_t active_penalty; int32_t global_penalty; int32_t colormap_penalty; Gif_Image *new_gfi; } Gif_OptData; /* Screen width and height */ static int screen_width; static int screen_height; /* Colormap containing all colors in the image. May have >256 colors */ static Gif_Colormap *all_colormap; /* The old global colormap, or a fake one we created if necessary */ static Gif_Colormap *in_global_map; /* The new global colormap */ static Gif_Colormap *out_global_map; #define TRANSP (0) static u_int16_t background; #define NOT_IN_OUT_GLOBAL (256) static u_int16_t *last_data; static u_int16_t *this_data; static u_int16_t *next_data; static int image_index; static int gif_color_count; /***** * SIMPLE HELPERS * new and delete optimize data; and colormap_combine; and sorting permutations **/ Gif_OptData * new_opt_data(void) { Gif_OptData *od = Gif_New(Gif_OptData); od->needed_colors = 0; od->global_penalty = 1; return od; } void delete_opt_data(Gif_OptData *od) { if (!od) return; Gif_DeleteArray(od->needed_colors); Gif_Delete(od); } /* colormap_combine: Ensure that each color in `src' is represented in `dst'. For each color `i' in `src', src->col[i].pixel == some j so that GIF_COLOREQ(&src->col[i], &dst->col[j]). dst->col[0] is reserved for transparency; no source color will be mapped to it. */ void colormap_combine(Gif_Colormap *dst, Gif_Colormap *src) { Gif_Color *src_col, *dst_col; int i, j; /* expand dst->col if necessary. This might change dst->col */ if (dst->ncol + src->ncol >= dst->capacity) { dst->capacity *= 2; Gif_ReArray(dst->col, Gif_Color, dst->capacity); } src_col = src->col; dst_col = dst->col; for (i = 0; i < src->ncol; i++, src_col++) { for (j = 1; j < dst->ncol; j++) { if (GIF_COLOREQ(src_col, &dst_col[j])) goto found; } dst_col[j] = *src_col; dst_col[j].pixel = 0; dst->ncol++; found: src_col->pixel = j; } } /* sort_permutation: sorts a given permutation `perm' according to the corresponding values in `values'. Thus, in the output, the sequence `[ values[perm[i]] | i <- 0..size-1 ]' will be monotonic, either up or (if is_down != 0) down. */ /* 9.Dec.1998 - Dumb idiot, it's time you stopped using C. The optimizer was broken because I switched to u_int32_t's for the sorting values without considering the consequences; and the consequences were bad. */ static int32_t *permuting_sort_values; static int permuting_sorter_up(const void *v1, const void *v2) { const u_int16_t *n1 = (const u_int16_t *)v1; const u_int16_t *n2 = (const u_int16_t *)v2; return (permuting_sort_values[*n1] - permuting_sort_values[*n2]); } static int permuting_sorter_down(const void *v1, const void *v2) { const u_int16_t *n1 = (const u_int16_t *)v1; const u_int16_t *n2 = (const u_int16_t *)v2; return (permuting_sort_values[*n2] - permuting_sort_values[*n1]); } static u_int16_t * sort_permutation(u_int16_t *perm, int size, int32_t *values, int is_down) { permuting_sort_values = values; if (is_down) qsort(perm, size, sizeof(u_int16_t), permuting_sorter_down); else qsort(perm, size, sizeof(u_int16_t), permuting_sorter_up); permuting_sort_values = 0; return perm; } /***** * MANIPULATING IMAGE AREAS **/ static void copy_data_area(u_int16_t *dst, u_int16_t *src, Gif_Image *area) { int y, width, height; if (!area) return; width = area->width; height = area->height; dst += area->top * screen_width + area->left; src += area->top * screen_width + area->left; for (y = 0; y < height; y++) { memcpy(dst, src, sizeof(u_int16_t) * width); dst += screen_width; src += screen_width; } } static void copy_data_area_subimage(u_int16_t *dst, u_int16_t *src, Gif_OptData *area) { Gif_Image img; img.left = area->left; img.top = area->top; img.width = area->width; img.height = area->height; copy_data_area(dst, src, &img); } static void fill_data_area(u_int16_t *dst, u_int16_t value, Gif_Image *area) { int x, y; int width = area->width; int height = area->height; dst += area->top * screen_width + area->left; for (y = 0; y < height; y++) { for (x = 0; x < width; x++) dst[x] = value; dst += screen_width; } } static void fill_data_area_subimage(u_int16_t *dst, u_int16_t value, Gif_OptData *area) { Gif_Image img; img.left = area->left; img.top = area->top; img.width = area->width; img.height = area->height; fill_data_area(dst, value, &img); } static void erase_screen(u_int16_t *dst) { u_int32_t i; u_int32_t screen_size = screen_width * screen_height; for (i = 0; i < screen_size; i++) *dst++ = background; } /***** * APPLY A GIF FRAME OR DISPOSAL TO AN IMAGE DESTINATION **/ static void apply_frame(u_int16_t *dst, Gif_Image *gfi, int replace) { int i, y; u_int16_t map[256]; Gif_Colormap *colormap = gfi->local ? gfi->local : in_global_map; /* make sure transparency maps to TRANSP */ for (i = 0; i < colormap->ncol; i++) map[i] = colormap->col[i].pixel; /* out-of-bounds colors map to 0, for the sake of argument */ for (i = colormap->ncol; i < 256; i++) map[i] = colormap->col[0].pixel; if (gfi->transparent >= 0 && gfi->transparent < 256) map[gfi->transparent] = TRANSP; else replace = 1; /* map the image */ dst += gfi->left + gfi->top * screen_width; for (y = 0; y < gfi->height; y++) { byte *gfi_pointer = gfi->img[y]; int x; if (replace) for (x = 0; x < gfi->width; x++) dst[x] = map[gfi_pointer[x]]; else for (x = 0; x < gfi->width; x++) { u_int16_t new_pixel = map[gfi_pointer[x]]; if (new_pixel != TRANSP) dst[x] = new_pixel; } dst += screen_width; } } static void apply_frame_disposal(u_int16_t *into_data, u_int16_t *from_data, Gif_Image *gfi) { if (gfi->disposal == GIF_DISPOSAL_NONE || gfi->disposal == GIF_DISPOSAL_ASIS) copy_data_area(into_data, from_data, gfi); else if (gfi->disposal == GIF_DISPOSAL_BACKGROUND) fill_data_area(into_data, background, gfi); } /***** * FIND THE SMALLEST BOUNDING RECTANGLE ENCLOSING ALL CHANGES **/ /* find_difference_bounds: Find the smallest rectangular area containing all the changes and store it in `bounds'. */ static void find_difference_bounds(Gif_OptData *bounds, Gif_Image *gfi, Gif_Image *last) { int lf, rt, lf_min, rt_max, tp, bt, x, y; /* 1.Aug.99 - use current bounds if possible, since this function is a speed bottleneck */ if (!last || last->disposal == GIF_DISPOSAL_NONE || last->disposal == GIF_DISPOSAL_ASIS) { lf_min = gfi->left; rt_max = gfi->left + gfi->width - 1; tp = gfi->top; bt = gfi->top + gfi->height - 1; } else { lf_min = 0; rt_max = screen_width - 1; tp = 0; bt = screen_height - 1; } for (; tp < screen_height; tp++) if (memcmp(last_data + screen_width * tp, this_data + screen_width * tp, screen_width * sizeof(u_int16_t)) != 0) break; for (; bt >= tp; bt--) if (memcmp(last_data + screen_width * bt, this_data + screen_width * bt, screen_width * sizeof(u_int16_t)) != 0) break; lf = screen_width; rt = 0; for (y = tp; y <= bt; y++) { u_int16_t *ld = last_data + screen_width * y; u_int16_t *td = this_data + screen_width * y; for (x = lf_min; x < lf; x++) if (ld[x] != td[x]) break; lf = x; for (x = rt_max; x > rt; x--) if (ld[x] != td[x]) break; rt = x; } /* 19.Aug.1999 - handle case when there's no difference between frames */ if (tp > bt) tp = bt = lf = rt = 0; bounds->left = lf; bounds->top = tp; bounds->width = rt + 1 - lf; bounds->height = bt + 1 - tp; } /* expand_difference_bounds: If the current image has background disposal and the background is transparent, we must expand the difference bounds to include any blanked (newly transparent) pixels that are still transparent in the next image. This function does that by comparing this_data and next_data. The new bounds are passed and stored in `bounds'; the image's old bounds, which are also the maximum bounds, are passed in `this_bounds'. */ static void expand_difference_bounds(Gif_OptData *bounds, Gif_Image *this_bounds) { int x, y; int lf = bounds->left, tp = bounds->top; int rt = lf + bounds->width - 1, bt = tp + bounds->height - 1; int tlf = this_bounds->left, ttp = this_bounds->top; int trt = tlf + this_bounds->width - 1, tbt = ttp + this_bounds->height - 1; if (lf > rt || tp > bt) lf = 0, tp = 0, rt = screen_width - 1, bt = screen_height - 1; for (y = ttp; y < tp; y++) { u_int16_t *now = this_data + screen_width * y; u_int16_t *next = next_data + screen_width * y; for (x = tlf; x <= trt; x++) if (now[x] != TRANSP && next[x] == TRANSP) goto found_top; } found_top: tp = y; for (y = tbt; y > bt; y--) { u_int16_t *now = this_data + screen_width * y; u_int16_t *next = next_data + screen_width * y; for (x = tlf; x <= trt; x++) if (now[x] != TRANSP && next[x] == TRANSP) goto found_bottom; } found_bottom: bt = y; for (x = tlf; x < lf; x++) { u_int16_t *now = this_data + x; u_int16_t *next = next_data + x; for (y = tp; y <= bt; y++) if (now[y*screen_width] != TRANSP && next[y*screen_width] == TRANSP) goto found_left; } found_left: lf = x; for (x = trt; x > rt; x--) { u_int16_t *now = this_data + x; u_int16_t *next = next_data + x; for (y = tp; y <= bt; y++) if (now[y*screen_width] != TRANSP && next[y*screen_width] == TRANSP) goto found_right; } found_right: rt = x; bounds->left = lf; bounds->top = tp; bounds->width = rt + 1 - lf; bounds->height = bt + 1 - tp; } /* fix_difference_bounds: make sure the image isn't 0x0. */ static void fix_difference_bounds(Gif_OptData *bounds) { if (bounds->width == 0 || bounds->height == 0) { bounds->top = 0; bounds->left = 0; bounds->width = 1; bounds->height = 1; } /* assert that image lies completely within screen */ assert(bounds->top < screen_height && bounds->left < screen_width && bounds->top + bounds->height - 1 < screen_height && bounds->left + bounds->width - 1 < screen_width); } /***** * DETERMINE WHICH COLORS ARE USED **/ #define REQUIRED 2 #define REPLACE_TRANSP 1 /* get_used_colors: mark which colors are needed by a given image. Returns a need array so that need[j] == REQUIRED if the output colormap must include all_color j; REPLACE_TRANSP if it should be replaced by transparency; and 0 if it's not in the image at all. If use_transparency > 0, then a pixel which was the same in the last frame may be replaced with transparency. If use_transparency == 2, transparency MUST be set. (This happens on the first image if the background should be transparent.) */ static void get_used_colors(Gif_OptData *bounds, int use_transparency) { int top = bounds->top, width = bounds->width, height = bounds->height; int i, x, y; int all_ncol = all_colormap->ncol; byte *need = Gif_NewArray(byte, all_ncol); for (i = 0; i < all_ncol; i++) need[i] = 0; /* set elements that are in the image. need == 2 means the color must be in the map; need == 1 means the color may be replaced by transparency. */ for (y = top; y < top + height; y++) { u_int16_t *data = this_data + screen_width * y + bounds->left; u_int16_t *last = last_data + screen_width * y + bounds->left; for (x = 0; x < width; x++) { if (data[x] != last[x]) need[data[x]] = REQUIRED; else if (need[data[x]] == 0) need[data[x]] = REPLACE_TRANSP; } } if (need[TRANSP]) need[TRANSP] = REQUIRED; /* check for too many colors; also force transparency if needed */ { int count[3]; /* Count distinct pixels in each category */ count[0] = count[1] = count[2] = 0; for (i = 0; i < all_ncol; i++) count[need[i]]++; /* If use_transparency is large and there's room, add transparency */ if (use_transparency > 1 && !need[TRANSP] && count[REQUIRED] < 256) { need[TRANSP] = REQUIRED; count[REQUIRED]++; } /* If too many "potentially transparent" pixels, force transparency */ if (count[REPLACE_TRANSP] + count[REQUIRED] > 256) use_transparency = 1; /* Make sure transparency is marked necessary if we use it */ if (count[REPLACE_TRANSP] > 0 && use_transparency && !need[TRANSP]) { need[TRANSP] = REQUIRED; count[REQUIRED]++; } /* If not using transparency, change "potentially transparent" pixels to "actually used" pixels */ if (!use_transparency) { for (i = 0; i < all_ncol; i++) if (need[i] == REPLACE_TRANSP) need[i] = REQUIRED; count[REQUIRED] += count[REPLACE_TRANSP]; } /* If too many "actually used" pixels, fail miserably */ if (count[REQUIRED] > 256) fatal_error("more than 256 colors required in a frame", count[REQUIRED]); /* If we can afford to have transparency, and we want to use it, then include it */ if (count[REQUIRED] < 256 && use_transparency && !need[TRANSP]) { need[TRANSP] = REQUIRED; count[REQUIRED]++; } bounds->required_color_count = count[REQUIRED]; } bounds->needed_colors = need; } /***** * FIND SUBIMAGES AND COLORS USED **/ static void create_subimages(Gif_Stream *gfs, int optimize_level) { int screen_size; Gif_Image *last_gfi; int next_data_valid; u_int16_t *previous_data = 0; screen_size = screen_width * screen_height; next_data = Gif_NewArray(u_int16_t, screen_size); next_data_valid = 0; /* do first image. Remember to uncompress it if necessary */ erase_screen(last_data); erase_screen(this_data); last_gfi = 0; /* PRECONDITION: last_data -- garbage this_data -- equal to image data for previous image next_data -- equal to image data for next image if next_image_valid */ for (image_index = 0; image_index < gfs->nimages; image_index++) { Gif_Image *gfi = gfs->images[image_index]; Gif_OptData *subimage = new_opt_data(); if (!gfi->img) Gif_UncompressImage(gfi); Gif_ReleaseCompressedImage(gfi); /* save previous data if necessary */ if (gfi->disposal == GIF_DISPOSAL_PREVIOUS) { previous_data = Gif_NewArray(u_int16_t, screen_size); copy_data_area(previous_data, this_data, gfi); } /* set this_data equal to the current image */ if (next_data_valid) { u_int16_t *temp = this_data; this_data = next_data; next_data = temp; next_data_valid = 0; } else apply_frame(this_data, gfi, 0); /* find minimum area of difference between this image and last image */ subimage->disposal = GIF_DISPOSAL_ASIS; if (image_index > 0) find_difference_bounds(subimage, gfi, last_gfi); else { subimage->left = gfi->left; subimage->top = gfi->top; subimage->width = gfi->width; subimage->height = gfi->height; } /* might need to expand difference border if transparent background & background disposal */ if (gfi->disposal == GIF_DISPOSAL_BACKGROUND && background == TRANSP && image_index < gfs->nimages - 1) { /* set up next_data */ Gif_Image *next_gfi = gfs->images[image_index + 1]; memcpy(next_data, this_data, screen_size * sizeof(u_int16_t)); apply_frame_disposal(next_data, this_data, gfi); apply_frame(next_data, next_gfi, 0); next_data_valid = 1; /* expand border as necessary */ expand_difference_bounds(subimage, gfi); subimage->disposal = GIF_DISPOSAL_BACKGROUND; } fix_difference_bounds(subimage); /* set map of used colors */ { int use_transparency = optimize_level > 1 && image_index > 0; if (image_index == 0 && background == TRANSP) use_transparency = 2; get_used_colors(subimage, use_transparency); } gfi->user_data = subimage; last_gfi = gfi; /* Apply optimized disposal to last_data and unoptimized disposal to this_data. Before 9.Dec.1998 I applied unoptimized disposal uniformly to both. This led to subtle bugs. After all, to determine bounds, we want to compare the current image (only obtainable through unoptimized disposal) with what WILL be left after the previous OPTIMIZED image's disposal. This fix is repeated in create_new_image_data */ if (subimage->disposal == GIF_DISPOSAL_BACKGROUND) fill_data_area_subimage(last_data, background, subimage); else copy_data_area_subimage(last_data, this_data, subimage); if (last_gfi->disposal == GIF_DISPOSAL_BACKGROUND) fill_data_area(this_data, background, last_gfi); else if (last_gfi->disposal == GIF_DISPOSAL_PREVIOUS) { copy_data_area(this_data, previous_data, last_gfi); Gif_DeleteArray(previous_data); } } Gif_DeleteArray(next_data); } /***** * CALCULATE OUTPUT GLOBAL COLORMAP **/ /* create_out_global_map: The interface function to this pass. It creates out_global_map and sets pixel values on all_colormap appropriately. Specifically: all_colormap->col[P].pixel >= 256 ==> P is not in the global colormap. Otherwise, all_colormap->col[P].pixel == the J so that GIF_COLOREQ(&all_colormap->col[P], &out_global_map->col[J]). On return, the `colormap_penalty' component of an image's Gif_OptData structure is <0 iff that image will need a local colormap. 20.Aug.1999 - updated to new version that arranges the entire colormap, not just the stuff above 256 colors. */ static void increment_penalties(Gif_OptData *opt, int32_t *penalty, int32_t delta) { int i; int all_ncol = all_colormap->ncol; byte *need = opt->needed_colors; for (i = 1; i < all_ncol; i++) if (need[i] == REQUIRED) penalty[i] += delta; } static void create_out_global_map(Gif_Stream *gfs) { int all_ncol = all_colormap->ncol; int32_t *penalty = Gif_NewArray(int32_t, all_ncol); u_int16_t *permute = Gif_NewArray(u_int16_t, all_ncol); u_int16_t *ordering = Gif_NewArray(u_int16_t, all_ncol); int cur_ncol, i, imagei; int nglobal_all = (all_ncol <= 257 ? all_ncol - 1 : 256); int permutation_changed; /* initial permutation is null */ for (i = 0; i < all_ncol - 1; i++) permute[i] = i + 1; /* choose appropriate penalties for each image */ for (imagei = 0; imagei < gfs->nimages; imagei++) { Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data; opt->global_penalty = opt->colormap_penalty = 1; for (i = 2; i < opt->required_color_count; i *= 2) opt->colormap_penalty *= 3; opt->active_penalty = (all_ncol > 257 ? opt->colormap_penalty : opt->global_penalty); } /* set initial penalties for each color */ for (i = 1; i < all_ncol; i++) penalty[i] = 0; for (imagei = 0; imagei < gfs->nimages; imagei++) { Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data; increment_penalties(opt, penalty, opt->active_penalty); } permutation_changed = 1; /* Loop, removing one color at a time. */ for (cur_ncol = all_ncol - 1; cur_ncol; cur_ncol--) { u_int16_t removed; /* sort permutation based on penalty */ if (permutation_changed) sort_permutation(permute, cur_ncol, penalty, 1); permutation_changed = 0; /* update reverse permutation */ removed = permute[cur_ncol - 1]; ordering[removed] = cur_ncol - 1; /* decrement penalties for colors that are out of the running */ for (imagei = 0; imagei < gfs->nimages; imagei++) { Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data; byte *need = opt->needed_colors; if (opt->global_penalty > 0 && need[removed] == REQUIRED) { increment_penalties(opt, penalty, -opt->active_penalty); opt->global_penalty = 0; opt->colormap_penalty = (cur_ncol > 256 ? -1 : 0); permutation_changed = 1; } } /* change colormap penalties if we're no longer working w/globalmap */ if (cur_ncol == 257) { for (i = 0; i < all_ncol; i++) penalty[i] = 0; for (imagei = 0; imagei < gfs->nimages; imagei++) { Gif_OptData *opt = (Gif_OptData *)gfs->images[imagei]->user_data; opt->active_penalty = opt->global_penalty; increment_penalties(opt, penalty, opt->global_penalty); } permutation_changed = 1; } } /* make sure background is in the global colormap */ if (background != TRANSP && ordering[background] >= 256) { u_int16_t other = permute[255]; ordering[other] = ordering[background]; ordering[background] = 255; } /* assign out_global_map based on permutation */ out_global_map = Gif_NewFullColormap(nglobal_all, 256); for (i = 1; i < all_ncol; i++) if (ordering[i] < 256) { out_global_map->col[ordering[i]] = all_colormap->col[i]; all_colormap->col[i].pixel = ordering[i]; } else all_colormap->col[i].pixel = NOT_IN_OUT_GLOBAL; /* set the stream's background color */ if (background != TRANSP) gfs->background = ordering[background]; /* cleanup */ Gif_DeleteArray(penalty); Gif_DeleteArray(permute); Gif_DeleteArray(ordering); } /***** * CREATE COLOR MAPPING FOR A PARTICULAR IMAGE **/ /* prepare_colormap_map: Create and return an array of bytes mapping from global pixel values to pixel values for this image. It may add colormap cells to `into'; if there isn't enough room in `into', it will return 0. It sets the `transparent' field of `gfi->optdata', but otherwise doesn't change or read it at all. */ static byte * prepare_colormap_map(Gif_Image *gfi, Gif_Colormap *into, byte *need) { int i; int is_global = (into == out_global_map); int all_ncol = all_colormap->ncol; Gif_Color *all_col = all_colormap->col; int ncol = into->ncol; Gif_Color *col = into->col; byte *map = Gif_NewArray(byte, all_ncol); byte into_used[256]; /* keep track of which pixel indices in `into' have been used; initially, all unused */ for (i = 0; i < 256; i++) into_used[i] = 0; /* go over all non-transparent global pixels which MUST appear (need[P]==REQUIRED) and place them in `into' */ for (i = 1; i < all_ncol; i++) { int val; if (need[i] != REQUIRED) continue; /* fail if a needed pixel isn't in the global map */ if (is_global) { val = all_col[i].pixel; if (val >= ncol) goto error; } else { /* always place colors in a local colormap */ if (ncol == 256) goto error; val = ncol; col[val] = all_col[i]; ncol++; } map[i] = val; into_used[val] = 1; } /* now check for transparency */ gfi->transparent = -1; if (need[TRANSP]) { int transparent = -1; /* first, look for an unused index in `into'. Pick the lowest one: the lower transparent index we get, the more likely we can shave a bit off min_code_bits later, thus saving space */ for (i = 0; i < ncol; i++) if (!into_used[i]) { transparent = i; break; } /* otherwise, [1.Aug.1999] use a fake slot for the purely transparent color. Don't actually enter the transparent color into the colormap -- we might be able to output a smaller colormap! If there's no room for it, give up */ if (transparent < 0) { if (ncol < 256) { transparent = ncol; /* 1.Aug.1999 - don't increase ncol */ col[ncol] = all_col[TRANSP]; } else goto error; } /* change mapping */ map[TRANSP] = transparent; for (i = 1; i < all_ncol; i++) if (need[i] == REPLACE_TRANSP) map[i] = transparent; gfi->transparent = transparent; } /* If we get here, it worked! Commit state changes (the number of color cells in `into') and return the map. */ into->ncol = ncol; return map; error: /* If we get here, it failed! Return 0 and don't change global state. */ Gif_DeleteArray(map); return 0; } /* sort_colormap_permutation_rgb: for canonicalizing local colormaps by arranging them in RGB order */ static int colormap_rgb_permutation_sorter(const void *v1, const void *v2) { const Gif_Color *col1 = (const Gif_Color *)v1; const Gif_Color *col2 = (const Gif_Color *)v2; int value1 = (col1->red << 16) | (col1->green << 8) | col1->blue; int value2 = (col2->red << 16) | (col2->green << 8) | col2->blue; return value1 - value2; } /* prepare_colormap: make a colormap up from the image data by fitting any used colors into a colormap. Returns a map from global color index to index in this image's colormap. May set a local colormap on `gfi'. */ static byte * prepare_colormap(Gif_Image *gfi, byte *need) { byte *map; /* try to map pixel values into the global colormap */ Gif_DeleteColormap(gfi->local); gfi->local = 0; map = prepare_colormap_map(gfi, out_global_map, need); if (!map) { /* that didn't work; add a local colormap. */ byte permutation[256]; Gif_Color *local_col; int i; gfi->local = Gif_NewFullColormap(0, 256); map = prepare_colormap_map(gfi, gfi->local, need); /* The global colormap has already been canonicalized; we should canonicalize the local colormaps as well. Do that here */ local_col = gfi->local->col; for (i = 0; i < gfi->local->ncol; i++) local_col[i].pixel = i; qsort(local_col, gfi->local->ncol, sizeof(Gif_Color), colormap_rgb_permutation_sorter); for (i = 0; i < gfi->local->ncol; i++) permutation[local_col[i].pixel] = i; /* 1.Aug.1999 - we might not have added space for gfi->transparent */ if (gfi->transparent >= gfi->local->ncol) permutation[gfi->transparent] = gfi->transparent; for (i = 0; i < all_colormap->ncol; i++) map[i] = permutation[map[i]]; if (gfi->transparent >= 0) gfi->transparent = map[TRANSP]; } return map; } /***** * CREATE OUTPUT FRAME DATA **/ /* simple_frame_data: just copy the data from the image into the frame data. No funkiness, no transparency, nothing */ static void simple_frame_data(Gif_Image *gfi, byte *map) { int top = gfi->top, width = gfi->width, height = gfi->height; int x, y; for (y = 0; y < height; y++) { u_int16_t *from = this_data + screen_width * (y+top) + gfi->left; byte *into = gfi->image_data + y * width; for (x = 0; x < width; x++) *into++ = map[*from++]; } } /* transp_frame_data: copy the frame data into the actual image, using transparency occasionally according to a heuristic described below */ static void transp_frame_data(Gif_Stream *gfs, Gif_Image *gfi, byte *map) { int top = gfi->top, width = gfi->width, height = gfi->height; int x, y; int transparent = gfi->transparent; u_int16_t *last = 0; u_int16_t *cur = 0; byte *data; int transparentizing; int run_length; int run_pixel_value = 0; /* First, try w/o transparency. Compare this to the result using transparency and pick the better of the two. */ simple_frame_data(gfi, map); Gif_FullCompressImage(gfs, gfi, gif_write_flags); /* Actually copy data to frame. Use transparency if possible to shrink the size of the written GIF. The written GIF will be small if patterns (sequences of pixel values) recur in the image. We could conceivably use transparency to produce THE OPTIMAL image, with the most recurring patterns of the best kinds; but this would be very hard (wouldn't it?). Instead, we settle for a heuristic: we try and create RUNS. (Since we *try* to create them, they will presumably recur!) A RUN is a series of adjacent pixels all with the same value. By & large, we just use the regular image's values. However, we might create a transparent run *not in* the regular image, if TWO OR MORE adjacent runs OF DIFFERENT COLORS *could* be made transparent. (An area can be made transparent if the corresponding area in the previous frame had the same colors as the area does now.) Why? If only one run (say of color C) could be transparent, we get no large immediate advantage from making it transparent (it'll be a run of the same length regardless). Also, we might LOSE: what if the run was adjacent to some more of color C, which couldn't be made transparent? If we use color C (instead of the transparent color), then we get a longer run. This simple heuristic does a little better than Gifwizard's (6/97) on some images, but does *worse than nothing at all* on others. However, it DOES do better than the complicated, greedy algorithm I commented out above; and now we pick either the transparency-optimized version or the normal version, whichever compresses smaller, for the best of both worlds. (9/98) */ x = width; y = -1; data = gfi->image_data; transparentizing = 0; run_length = 0; while (y < height) { if (!transparentizing) { /* In an area that can't be made transparent */ while (x < width && !transparentizing) { *data = map[*cur]; /* If this pixel could be transparent... */ if (map[*cur] == transparent) transparentizing = 1; else if (*cur == *last) { if (*cur == run_pixel_value) /* within a transparent run */ run_length++; else if (run_length > 0) /* Ooo!! adjacent transparent runs -- combine them */ transparentizing = 1; else { /* starting a new transparent run */ run_pixel_value = *cur; run_length = 1; } } else run_length = 0; data++, last++, cur++, x++; } if (transparentizing) memset(data - run_length - 1, transparent, run_length + 1); } else /* Make a sequence of pixels transparent */ while (x < width && transparentizing) { if (*last == *cur || map[*cur] == transparent) { *data = transparent; data++, last++, cur++, x++; } else /* If this pixel can't be made transparent, just go back to copying normal runs. */ transparentizing = 0; } /* Move to the next row */ if (x >= width) { x = 0; y++; last = last_data + screen_width * (y+top) + gfi->left; cur = this_data + screen_width * (y+top) + gfi->left; } } /* Now, try compressed transparent version and pick the better of the two. */ { byte *old_compressed = gfi->compressed; void (*old_free_compressed)(void *) = gfi->free_compressed; u_int32_t old_compressed_len = gfi->compressed_len; gfi->compressed = 0; /* prevent freeing old_compressed */ Gif_FullCompressImage(gfs, gfi, gif_write_flags); if (gfi->compressed_len > old_compressed_len) { Gif_ReleaseCompressedImage(gfi); gfi->compressed = old_compressed; gfi->free_compressed = old_free_compressed; gfi->compressed_len = old_compressed_len; } else (*old_free_compressed)(old_compressed); Gif_ReleaseUncompressedImage(gfi); } } /***** * CREATE NEW IMAGE DATA **/ /* last == what last image ended up looking like this == what new image should look like last = apply O1 + dispose O1 + ... + apply On-1 + dispose On-1 this = apply U1 + dispose U1 + ... + apply Un-1 + dispose Un-1 + apply Un invariant: apply O1 + dispose O1 + ... + apply Ok === apply U1 + dispose U1 + ... + apply Uk */ static void create_new_image_data(Gif_Stream *gfs, int optimize_level) { Gif_Image cur_unopt_gfi; /* placehoder; maintains pre-optimization image size so we can apply background disposal */ int screen_size = screen_width * screen_height; u_int16_t *previous_data = 0; gfs->global = out_global_map; /* do first image. Remember to uncompress it if necessary */ erase_screen(last_data); erase_screen(this_data); for (image_index = 0; image_index < gfs->nimages; image_index++) { Gif_Image *cur_gfi = gfs->images[image_index]; Gif_OptData *opt = (Gif_OptData *)cur_gfi->user_data; /* save previous data if necessary */ if (cur_gfi->disposal == GIF_DISPOSAL_PREVIOUS) { previous_data = Gif_NewArray(u_int16_t, screen_size); copy_data_area(previous_data, this_data, cur_gfi); } /* set up this_data to be equal to the current image */ apply_frame(this_data, cur_gfi, 0); /* save actual bounds and disposal from unoptimized version so we can apply the disposal correctly next time through */ cur_unopt_gfi = *cur_gfi; /* set bounds and disposal from optdata */ Gif_ReleaseUncompressedImage(cur_gfi); cur_gfi->left = opt->left; cur_gfi->top = opt->top; cur_gfi->width = opt->width; cur_gfi->height = opt->height; cur_gfi->disposal = opt->disposal; if (image_index > 0) cur_gfi->interlace = 0; /* find the new image's colormap and then make new data */ { byte *map = prepare_colormap(cur_gfi, opt->needed_colors); byte *data = Gif_NewArray(byte, cur_gfi->width * cur_gfi->height); Gif_SetUncompressedImage(cur_gfi, data, Gif_DeleteArrayFunc, 0); /* don't use transparency on first frame */ if (optimize_level > 1 && image_index > 0) transp_frame_data(gfs, cur_gfi, map); else simple_frame_data(cur_gfi, map); Gif_DeleteArray(map); } delete_opt_data(opt); cur_gfi->user_data = 0; /* Set up last_data and this_data. last_data must contain this_data + new disposal. this_data must contain this_data + old disposal. */ if (cur_gfi->disposal == GIF_DISPOSAL_NONE || cur_gfi->disposal == GIF_DISPOSAL_ASIS) copy_data_area(last_data, this_data, cur_gfi); else if (cur_gfi->disposal == GIF_DISPOSAL_BACKGROUND) fill_data_area(last_data, background, cur_gfi); else assert(0 && "optimized frame has strange disposal"); if (cur_unopt_gfi.disposal == GIF_DISPOSAL_BACKGROUND) fill_data_area(this_data, background, &cur_unopt_gfi); else if (cur_unopt_gfi.disposal == GIF_DISPOSAL_PREVIOUS) { copy_data_area(this_data, previous_data, &cur_unopt_gfi); Gif_DeleteArray(previous_data); } } } /***** * INITIALIZATION AND FINALIZATION **/ static int initialize_optimizer(Gif_Stream *gfs, int optimize_level) { int i, screen_size; if (gfs->nimages < 1) return 0; /* combine colormaps */ all_colormap = Gif_NewFullColormap(1, 384); all_colormap->col[0].red = 255; all_colormap->col[0].green = 255; all_colormap->col[0].blue = 255; in_global_map = gfs->global; if (!in_global_map) { Gif_Color *col; in_global_map = Gif_NewFullColormap(256, 256); col = in_global_map->col; for (i = 0; i < 256; i++, col++) col->red = col->green = col->blue = i; } { int any_globals = 0; int first_transparent = -1; for (i = 0; i < gfs->nimages; i++) { Gif_Image *gfi = gfs->images[i]; if (gfi->local) colormap_combine(all_colormap, gfi->local); else any_globals = 1; if (gfi->transparent >= 0 && first_transparent < 0) first_transparent = i; } if (any_globals) colormap_combine(all_colormap, in_global_map); /* try and maintain transparency's pixel value */ if (first_transparent >= 0) { Gif_Image *gfi = gfs->images[first_transparent]; Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global; all_colormap->col[TRANSP] = gfcm->col[gfi->transparent]; } } /* find screen_width and screen_height, and clip all images to screen */ Gif_CalculateScreenSize(gfs, 0); screen_width = gfs->screen_width; screen_height = gfs->screen_height; for (i = 0; i < gfs->nimages; i++) Gif_ClipImage(gfs->images[i], 0, 0, screen_width, screen_height); /* create data arrays */ screen_size = screen_width * screen_height; last_data = Gif_NewArray(u_int16_t, screen_size); this_data = Gif_NewArray(u_int16_t, screen_size); /* set up colormaps */ gif_color_count = 2; while (gif_color_count < gfs->global->ncol && gif_color_count < 256) gif_color_count *= 2; /* choose background */ if (gfs->images[0]->transparent < 0 && gfs->background < in_global_map->ncol) background = in_global_map->col[gfs->background].pixel; else background = TRANSP; return 1; } static void finalize_optimizer(Gif_Stream *gfs) { int i; if (background == TRANSP) gfs->background = (byte)gfs->images[0]->transparent; /* 10.Dec.1998 - prefer GIF_DISPOSAL_NONE to GIF_DISPOSAL_ASIS. This is semantically "wrong" -- it's better to set the disposal explicitly than rely on default behavior -- but will result in smaller GIF files, since the graphic control extension can be left off in many cases. */ for (i = 0; i < gfs->nimages; i++) if (gfs->images[i]->disposal == GIF_DISPOSAL_ASIS && gfs->images[i]->delay == 0 && gfs->images[i]->transparent < 0) gfs->images[i]->disposal = GIF_DISPOSAL_NONE; Gif_DeleteColormap(in_global_map); Gif_DeleteColormap(all_colormap); Gif_DeleteArray(last_data); Gif_DeleteArray(this_data); } /* the interface function! */ void optimize_fragments(Gif_Stream *gfs, int optimize_level) { if (!initialize_optimizer(gfs, optimize_level)) return; create_subimages(gfs, optimize_level); create_out_global_map(gfs); create_new_image_data(gfs, optimize_level); finalize_optimizer(gfs); }