00001 /* optimize.c - Functions to optimize animated GIFs.
00002    Copyright (C) 1997-9 Eddie Kohler, eddietwo@lcs.mit.edu
00003    This file is part of gifsicle.
00004 
00005    Gifsicle is free software. It is distributed under the GNU Public License,
00006    version 2 or later; you can copy, distribute, or alter it at will, as long
00007    as this notice is kept intact and this source code is made available. There
00008    is no warranty, express or implied. */
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 /* Screen width and height */
00032 static int screen_width;
00033 static int screen_height;
00034 
00035 /* Colormap containing all colors in the image. May have >256 colors */
00036 static Gif_Colormap *all_colormap;
00037 
00038 /* The old global colormap, or a fake one we created if necessary */
00039 static Gif_Colormap *in_global_map;
00040 
00041 /* The new global colormap */
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  * SIMPLE HELPERS
00057  * new and delete optimize data; and colormap_combine; and sorting permutations
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 /* colormap_combine: Ensure that each color in `src' is represented in `dst'.
00079    For each color `i' in `src', src->col[i].pixel == some j so that
00080    GIF_COLOREQ(&src->col[i], &dst->col[j]). dst->col[0] is reserved for
00081    transparency; no source color will be mapped to it. */
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   /* expand dst->col if necessary. This might change dst->col */
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 /* sort_permutation: sorts a given permutation `perm' according to the
00112    corresponding values in `values'. Thus, in the output, the sequence
00113    `[ values[perm[i]] | i <- 0..size-1 ]' will be monotonic, either up or
00114    (if is_down != 0) down. */
00115 
00116 /* 9.Dec.1998 - Dumb idiot, it's time you stopped using C. The optimizer was
00117    broken because I switched to u_int32_t's for the sorting values without
00118    considering the consequences; and the consequences were bad. */
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  * MANIPULATING IMAGE AREAS
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  * APPLY A GIF FRAME OR DISPOSAL TO AN IMAGE DESTINATION
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   /* make sure transparency maps to TRANSP */
00227   for (i = 0; i < colormap->ncol; i++)
00228     map[i] = colormap->col[i].pixel;
00229   /* out-of-bounds colors map to 0, for the sake of argument */
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   /* map the image */
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  * FIND THE SMALLEST BOUNDING RECTANGLE ENCLOSING ALL CHANGES
00271  **/
00272 
00273 /* find_difference_bounds: Find the smallest rectangular area containing all
00274    the changes and store it in `bounds'. */
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   /* 1.Aug.99 - use current bounds if possible, since this function is a speed
00282      bottleneck */
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   /* 19.Aug.1999 - handle case when there's no difference between frames */
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 /* expand_difference_bounds: If the current image has background disposal and
00333    the background is transparent, we must expand the difference bounds to
00334    include any blanked (newly transparent) pixels that are still transparent
00335    in the next image. This function does that by comparing this_data and
00336    next_data. The new bounds are passed and stored in `bounds'; the image's
00337    old bounds, which are also the maximum bounds, are passed in
00338    `this_bounds'. */
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 /* fix_difference_bounds: make sure the image isn't 0x0. */
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   /* assert that image lies completely within screen */
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  * DETERMINE WHICH COLORS ARE USED
00421  **/
00422 
00423 #define REQUIRED        2
00424 #define REPLACE_TRANSP  1
00425 
00426 /* get_used_colors: mark which colors are needed by a given image. Returns a
00427    need array so that need[j] == REQUIRED if the output colormap must
00428    include all_color j; REPLACE_TRANSP if it should be replaced by
00429    transparency; and 0 if it's not in the image at all.
00430    
00431    If use_transparency > 0, then a pixel which was the same in the last frame
00432    may be replaced with transparency. If use_transparency == 2, transparency
00433    MUST be set. (This happens on the first image if the background should be
00434    transparent.) */
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   /* set elements that are in the image. need == 2 means the color
00448      must be in the map; need == 1 means the color may be replaced by
00449      transparency. */
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   /* check for too many colors; also force transparency if needed */
00464   {
00465     int count[3];
00466     /* Count distinct pixels in each category */
00467     count[0] = count[1] = count[2] = 0;
00468     for (i = 0; i < all_ncol; i++)
00469       count[need[i]]++;
00470     /* If use_transparency is large and there's room, add transparency */
00471     if (use_transparency > 1 && !need[TRANSP] && count[REQUIRED] < 256) {
00472       need[TRANSP] = REQUIRED;
00473       count[REQUIRED]++;
00474     }
00475     /* If too many "potentially transparent" pixels, force transparency */
00476     if (count[REPLACE_TRANSP] + count[REQUIRED] > 256)
00477       use_transparency = 1;
00478     /* Make sure transparency is marked necessary if we use it */
00479     if (count[REPLACE_TRANSP] > 0 && use_transparency && !need[TRANSP]) {
00480       need[TRANSP] = REQUIRED;
00481       count[REQUIRED]++;
00482     }
00483     /* If not using transparency, change "potentially transparent" pixels to
00484        "actually used" pixels */
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     /* If too many "actually used" pixels, fail miserably */
00491     if (count[REQUIRED] > 256)
00492       fatal_error("more than 256 colors required in a frame", count[REQUIRED]);
00493     /* If we can afford to have transparency, and we want to use it, then
00494        include it */
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  * FIND SUBIMAGES AND COLORS USED
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   /* do first image. Remember to uncompress it if necessary */
00524   erase_screen(last_data);
00525   erase_screen(this_data);
00526   last_gfi = 0;
00527   
00528   /* PRECONDITION: last_data -- garbage
00529      this_data -- equal to image data for previous image
00530      next_data -- equal to image data for next image if next_image_valid */
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     /* save previous data if necessary */
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     /* set this_data equal to the current image */
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     /* find minimum area of difference between this image and last image */
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     /* might need to expand difference border if transparent background &
00565        background disposal */
00566     if (gfi->disposal == GIF_DISPOSAL_BACKGROUND
00567         && background == TRANSP
00568         && image_index < gfs->nimages - 1) {
00569       /* set up next_data */
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       /* expand border as necessary */
00576       expand_difference_bounds(subimage, gfi);
00577       subimage->disposal = GIF_DISPOSAL_BACKGROUND;
00578     }
00579     
00580     fix_difference_bounds(subimage);
00581     
00582     /* set map of used colors */
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     /* Apply optimized disposal to last_data and unoptimized disposal to
00594        this_data. Before 9.Dec.1998 I applied unoptimized disposal uniformly
00595        to both. This led to subtle bugs. After all, to determine bounds, we
00596        want to compare the current image (only obtainable through unoptimized
00597        disposal) with what WILL be left after the previous OPTIMIZED image's
00598        disposal. This fix is repeated in create_new_image_data */
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  * CALCULATE OUTPUT GLOBAL COLORMAP
00618  **/
00619 
00620 /* create_out_global_map: The interface function to this pass. It creates
00621    out_global_map and sets pixel values on all_colormap appropriately.
00622    Specifically:
00623    
00624    all_colormap->col[P].pixel >= 256 ==> P is not in the global colormap.
00625    
00626    Otherwise, all_colormap->col[P].pixel == the J so that
00627    GIF_COLOREQ(&all_colormap->col[P], &out_global_map->col[J]).
00628 
00629    On return, the `colormap_penalty' component of an image's Gif_OptData
00630    structure is <0 iff that image will need a local colormap.
00631 
00632    20.Aug.1999 - updated to new version that arranges the entire colormap, not
00633    just the stuff above 256 colors. */
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   /* initial permutation is null */
00658   for (i = 0; i < all_ncol - 1; i++)
00659     permute[i] = i + 1;
00660   
00661   /* choose appropriate penalties for each image */
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   /* set initial penalties for each color */
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   /* Loop, removing one color at a time. */
00681   for (cur_ncol = all_ncol - 1; cur_ncol; cur_ncol--) {
00682     u_int16_t removed;
00683     
00684     /* sort permutation based on penalty */
00685     if (permutation_changed)
00686       sort_permutation(permute, cur_ncol, penalty, 1);
00687     permutation_changed = 0;
00688     
00689     /* update reverse permutation */
00690     removed = permute[cur_ncol - 1];
00691     ordering[removed] = cur_ncol - 1;
00692     
00693     /* decrement penalties for colors that are out of the running */
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     /* change colormap penalties if we're no longer working w/globalmap */
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   /* make sure background is in the global colormap */
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   /* assign out_global_map based on permutation */
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   /* set the stream's background color */
00736   if (background != TRANSP)
00737     gfs->background = ordering[background];
00738 
00739   /* cleanup */
00740   Gif_DeleteArray(penalty);
00741   Gif_DeleteArray(permute);
00742   Gif_DeleteArray(ordering);
00743 }
00744 
00745 
00746 /*****
00747  * CREATE COLOR MAPPING FOR A PARTICULAR IMAGE
00748  **/
00749 
00750 /* prepare_colormap_map: Create and return an array of bytes mapping from
00751    global pixel values to pixel values for this image. It may add colormap
00752    cells to `into'; if there isn't enough room in `into', it will return 0. It
00753    sets the `transparent' field of `gfi->optdata', but otherwise doesn't
00754    change or read it at all. */
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   /* keep track of which pixel indices in `into' have been used; initially,
00772      all unused */
00773   for (i = 0; i < 256; i++)
00774     into_used[i] = 0;
00775   
00776   /* go over all non-transparent global pixels which MUST appear
00777      (need[P]==REQUIRED) and place them in `into' */
00778   for (i = 1; i < all_ncol; i++) {
00779     int val;
00780     if (need[i] != REQUIRED)
00781       continue;
00782     
00783     /* fail if a needed pixel isn't in the global map */
00784     if (is_global) {
00785       val = all_col[i].pixel;
00786       if (val >= ncol) goto error;
00787     } else {
00788       /* always place colors in a local colormap */
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   /* now check for transparency */
00800   gfi->transparent = -1;
00801   if (need[TRANSP]) {
00802     int transparent = -1;
00803     
00804     /* first, look for an unused index in `into'. Pick the lowest one: the
00805        lower transparent index we get, the more likely we can shave a bit off
00806        min_code_bits later, thus saving space */
00807     for (i = 0; i < ncol; i++)
00808       if (!into_used[i]) {
00809         transparent = i;
00810         break;
00811       }
00812     
00813     /* otherwise, [1.Aug.1999] use a fake slot for the purely transparent
00814        color. Don't actually enter the transparent color into the colormap --
00815        we might be able to output a smaller colormap! If there's no room for
00816        it, give up */
00817     if (transparent < 0) {
00818       if (ncol < 256) {
00819         transparent = ncol;
00820         /* 1.Aug.1999 - don't increase ncol */
00821         col[ncol] = all_col[TRANSP];
00822       } else
00823         goto error;
00824     }
00825     
00826     /* change mapping */
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   /* If we get here, it worked! Commit state changes (the number of color
00836      cells in `into') and return the map. */
00837   into->ncol = ncol;
00838   return map;
00839   
00840  error:
00841   /* If we get here, it failed! Return 0 and don't change global state. */
00842   Gif_DeleteArray(map);
00843   return 0;
00844 }
00845 
00846 
00847 /* sort_colormap_permutation_rgb: for canonicalizing local colormaps by
00848    arranging them in RGB order */
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 /* prepare_colormap: make a colormap up from the image data by fitting any
00862    used colors into a colormap. Returns a map from global color index to index
00863    in this image's colormap. May set a local colormap on `gfi'. */
00864 
00865 static byte *
00866 prepare_colormap(Gif_Image *gfi, byte *need)
00867 {
00868   byte *map;
00869   
00870   /* try to map pixel values into the global colormap */
00871   Gif_DeleteColormap(gfi->local);
00872   gfi->local = 0;
00873   map = prepare_colormap_map(gfi, out_global_map, need);
00874   
00875   if (!map) {
00876     /* that didn't work; add a local colormap. */
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     /* The global colormap has already been canonicalized; we should
00885        canonicalize the local colormaps as well. Do that here */
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     /* 1.Aug.1999 - we might not have added space for gfi->transparent */
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  * CREATE OUTPUT FRAME DATA
00912  **/
00913 
00914 /* simple_frame_data: just copy the data from the image into the frame data.
00915    No funkiness, no transparency, nothing */
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 /* transp_frame_data: copy the frame data into the actual image, using
00933    transparency occasionally according to a heuristic described below */
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   /* First, try w/o transparency. Compare this to the result using
00949      transparency and pick the better of the two. */
00950   simple_frame_data(gfi, map);
00951   Gif_FullCompressImage(gfs, gfi, gif_write_flags);
00952   
00953   /* Actually copy data to frame.
00954     
00955     Use transparency if possible to shrink the size of the written GIF.
00956     
00957     The written GIF will be small if patterns (sequences of pixel values)
00958     recur in the image.
00959     We could conceivably use transparency to produce THE OPTIMAL image,
00960     with the most recurring patterns of the best kinds; but this would
00961     be very hard (wouldn't it?). Instead, we settle for a heuristic:
00962     we try and create RUNS. (Since we *try* to create them, they will
00963     presumably recur!) A RUN is a series of adjacent pixels all with the
00964     same value.
00965     
00966     By & large, we just use the regular image's values. However, we might
00967     create a transparent run *not in* the regular image, if TWO OR MORE
00968     adjacent runs OF DIFFERENT COLORS *could* be made transparent.
00969     
00970     (An area can be made transparent if the corresponding area in the previous
00971     frame had the same colors as the area does now.)
00972     
00973     Why? If only one run (say of color C) could be transparent, we get no
00974     large immediate advantage from making it transparent (it'll be a run of
00975     the same length regardless). Also, we might LOSE: what if the run was
00976     adjacent to some more of color C, which couldn't be made transparent? If
00977     we use color C (instead of the transparent color), then we get a longer
00978     run.
00979     
00980     This simple heuristic does a little better than Gifwizard's (6/97)
00981     on some images, but does *worse than nothing at all* on others.
00982     
00983     However, it DOES do better than the complicated, greedy algorithm I
00984     commented out above; and now we pick either the transparency-optimized
00985     version or the normal version, whichever compresses smaller, for the best
00986     of both worlds. (9/98) */
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       /* In an area that can't be made transparent */
00998       while (x < width && !transparentizing) {
00999         *data = map[*cur];
01000         
01001         /* If this pixel could be transparent... */
01002         if (map[*cur] == transparent)
01003           transparentizing = 1;
01004         else if (*cur == *last) {
01005           if (*cur == run_pixel_value)
01006             /* within a transparent run */
01007             run_length++;
01008           else if (run_length > 0)
01009             /* Ooo!! adjacent transparent runs -- combine them */
01010             transparentizing = 1;
01011           else {
01012             /* starting a new transparent run */
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       /* Make a sequence of pixels transparent */
01027       while (x < width && transparentizing) {
01028         if (*last == *cur || map[*cur] == transparent) {
01029           *data = transparent;
01030           data++, last++, cur++, x++;
01031         } else
01032           /* If this pixel can't be made transparent, just go back to
01033              copying normal runs. */
01034           transparentizing = 0;
01035       }
01036     
01037     /* Move to the next row */
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   /* Now, try compressed transparent version and pick the better of the two. */
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;        /* prevent freeing old_compressed */
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  * CREATE NEW IMAGE DATA
01068  **/
01069 
01070 /* last == what last image ended up looking like
01071    this == what new image should look like
01072    
01073    last = apply O1 + dispose O1 + ... + apply On-1 + dispose On-1
01074    this = apply U1 + dispose U1 + ... + apply Un-1 + dispose Un-1 + apply Un
01075    
01076    invariant: apply O1 + dispose O1 + ... + apply Ok
01077    === apply U1 + dispose U1 + ... + apply Uk */
01078 
01079 static void
01080 create_new_image_data(Gif_Stream *gfs, int optimize_level)
01081 {
01082   Gif_Image cur_unopt_gfi;      /* placehoder; maintains pre-optimization
01083                                    image size so we can apply background
01084                                    disposal */
01085   int screen_size = screen_width * screen_height;
01086   u_int16_t *previous_data = 0;
01087   
01088   gfs->global = out_global_map;
01089   
01090   /* do first image. Remember to uncompress it if necessary */
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     /* save previous data if necessary */
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     /* set up this_data to be equal to the current image */
01105     apply_frame(this_data, cur_gfi, 0);
01106     
01107     /* save actual bounds and disposal from unoptimized version so we can
01108        apply the disposal correctly next time through */
01109     cur_unopt_gfi = *cur_gfi;
01110     
01111     /* set bounds and disposal from optdata */
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     /* find the new image's colormap and then make new data */
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       /* don't use transparency on first frame */
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     /* Set up last_data and this_data. last_data must contain this_data + new
01139        disposal. this_data must contain this_data + old disposal. */
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  * INITIALIZATION AND FINALIZATION
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   /* combine colormaps */
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     /* try and maintain transparency's pixel value */
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   /* find screen_width and screen_height, and clip all images to screen */
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   /* create data arrays */
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   /* set up colormaps */
01221   gif_color_count = 2;
01222   while (gif_color_count < gfs->global->ncol && gif_color_count < 256)
01223     gif_color_count *= 2;
01224   
01225   /* choose background */
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   /* 10.Dec.1998 - prefer GIF_DISPOSAL_NONE to GIF_DISPOSAL_ASIS. This is
01244      semantically "wrong" -- it's better to set the disposal explicitly than
01245      rely on default behavior -- but will result in smaller GIF files, since
01246      the graphic control extension can be left off in many cases. */
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 /* the interface function! */
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 }