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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

00071 {
00072   if (!od) return;
00073   Gif_DeleteArray(od->needed_colors);
00074   Gif_Delete(od);
00075 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

00062 {
00063   Gif_OptData *od = Gif_New(Gif_OptData);
00064   od->needed_colors = 0;
00065   od->global_penalty = 1;
00066   return od;
00067 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }

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 }