00001 /* merge.c - Functions which actually combine and manipulate GIF image data.
00002    Copyright (C) 1997-9 Eddie Kohler, eddietwo@lcs.mit.edu
00003    This file is part of gifsicle.
00004 
00005    Gifsicle is free software; you can copy, distribute, or alter it at will, as
00006    long as this notice is kept intact and this source code is made available.
00007    Hypo(pa)thetical commerical developers are asked to write the author a note,
00008    which might make his day. There is no warranty, express or implied. */
00009 
00010 #include "config.h"
00011 #include "gifsicle.h"
00012 #include <assert.h>
00013 #include <stdio.h>
00014 #include <stdlib.h>
00015 #include <errno.h>
00016 #include <limits.h>
00017 #include <string.h>
00018 
00019 /* First merging stage: Mark the used colors in all colormaps. */
00020 
00021 void
00022 unmark_colors(Gif_Colormap *gfcm)
00023 {
00024   int i;
00025   if (gfcm)
00026     for (i = 0; i < gfcm->ncol; i++)
00027       gfcm->col[i].haspixel = 0;
00028 }
00029 
00030 void
00031 unmark_colors_2(Gif_Colormap *gfcm)
00032 {
00033   int i;
00034   for (i = 0; i < gfcm->ncol; i++)
00035     gfcm->col[i].pixel = 256;
00036 }
00037 
00038 
00039 static void
00040 mark_used_colors(Gif_Image *gfi, Gif_Colormap *gfcm)
00041 {
00042   Gif_Color *col = gfcm->col;
00043   int ncol = gfcm->ncol;
00044   byte have[256];
00045   int i, j, total;
00046   
00047   /* Only mark colors until we've seen all of them. The total variable keeps
00048      track of how many we've seen. have[i] is true if we've seen color i */
00049   for (i = 0; i < ncol; i++)
00050     have[i] = 0;
00051   for (i = ncol; i < 256; i++)
00052     have[i] = 1;
00053   total = 256 - ncol;
00054   
00055   /* Loop over every pixel (until we've seen all colors) */
00056   for (j = 0; j < gfi->height && total < 256; j++) {
00057     byte *data = gfi->img[j];
00058     for (i = 0; i < gfi->width; i++, data++)
00059       if (!have[*data]) {
00060         have[*data] = 1;
00061         total++;
00062       }
00063   }
00064   
00065   /* Mark the colors we've found */
00066   for (i = 0; i < ncol; i++)
00067     col[i].haspixel = have[i];
00068   
00069   /* Mark the transparent color specially */
00070   if (gfi->transparent >= 0 && gfi->transparent < ncol)
00071     col[gfi->transparent].haspixel = 2;
00072   /* 1.Aug.1999 - DO NOT clear transparent index if gfi->transparent isn't
00073      within bounds! Some smart GIF optimizers will write a small colormap, not
00074      including the transparent color. */
00075   /* 19.Aug.1999 - Don't need to set col[gfi->transparent].haspixel to 2 even
00076      if it's not within bounds! */
00077 }
00078 
00079 
00080 int
00081 find_color_index(Gif_Color *c, int nc, Gif_Color *color)
00082 {
00083   int index;
00084   for (index = 0; index < nc; index++)
00085     if (GIF_COLOREQ(&c[index], color))
00086       return index;
00087   return -1;
00088 }
00089 
00090 
00091 static int
00092 ensure_slot_255(Gif_Colormap *dest, int ncol)
00093 {
00094   Gif_Color *background = &dest->col[255];
00095   int i;
00096   for (i = 0; i < ncol; i++)
00097     if (GIF_COLOREQ(&dest->col[i], background))
00098       return ncol;
00099   return ncol + 1;
00100 }
00101 
00102 int
00103 merge_colormap_if_possible(Gif_Colormap *dest, Gif_Colormap *src)
00104 {
00105   Gif_Color *srccol = src->col;
00106   Gif_Color *destcol = dest->col;
00107   int ndestcol = dest->ncol;
00108   int dest_userflags = dest->userflags;
00109   int i, x;
00110   int trivial_map = 1;
00111   
00112   for (i = 0; i < src->ncol; i++) {
00113     if (srccol[i].haspixel == 1) {
00114       /* Store an image color cell's mapping to the global colormap in its
00115          `pixel' slot. This is useful caching: oftentimes many input frames
00116          will share a colormap */
00117       int mapto = srccol[i].pixel < 256 ? srccol[i].pixel : -1;
00118       
00119       if (mapto == -1)
00120         mapto = find_color_index(destcol, ndestcol, &srccol[i]);
00121       
00122       if (mapto == -1 && ndestcol == 255
00123           && (dest_userflags & COLORMAP_ENSURE_SLOT_255) != 0) {
00124         ndestcol = ensure_slot_255(dest, ndestcol);
00125         dest_userflags &= ~COLORMAP_ENSURE_SLOT_255;
00126         /* slot 255 might have been equal to `srccol[i]'! */
00127         if (ndestcol == 256 && GIF_COLOREQ(&destcol[255], &srccol[i]))
00128           mapto = 255;
00129       }
00130       
00131       if (mapto == -1 && ndestcol < 256) {
00132         /* add the color */
00133         mapto = ndestcol;
00134         destcol[mapto] = srccol[i];
00135         ndestcol++;
00136       }
00137       
00138       if (mapto == -1)
00139         /* check for a pure-transparent color */
00140         for (x = 0; x < ndestcol; x++)
00141           if (destcol[x].haspixel == 2) {
00142             mapto = x;
00143             destcol[mapto] = srccol[i];
00144             break;
00145           }
00146       
00147       if (mapto == -1)
00148         /* give up and require a local colormap */
00149         goto local_colormap_required;
00150       
00151       assert(mapto >= 0 && mapto < ndestcol);
00152       assert(GIF_COLOREQ(&destcol[mapto], &srccol[i]));
00153       
00154       srccol[i].pixel = mapto;
00155       destcol[mapto].haspixel = 1;
00156       if (mapto != i)
00157         trivial_map = 0;
00158       
00159     } else if (srccol[i].haspixel == 2)
00160       /* a dedicated transparent color; if trivial_map & at end of colormap
00161          insert it with haspixel == 2. (strictly not necessary; we do it to
00162          try to keep the map trivial.) */
00163       if (trivial_map && i == ndestcol) {
00164         destcol[ndestcol] = srccol[i];
00165         ndestcol++;
00166       }
00167   }
00168 
00169   /* success! save new number of colors */
00170   dest->ncol = ndestcol;
00171   dest->userflags = dest_userflags;
00172   return 1;
00173   
00174   /* failure: a local colormap is required */
00175  local_colormap_required:
00176   if (warn_local_colormaps == 1) {
00177     static int context = 0;
00178     warning("so many colors that local colormaps were required");
00179     if (!context)
00180       warncontext("(You may want to try `--colors 256'.)");
00181     warn_local_colormaps = 2;
00182     context = 1;
00183   }
00184   
00185   /* 9.Dec.1998 - This must have been a longstanding bug! We MUST clear
00186      the cached mappings of any pixels in the source colormap we
00187      assigned this time through, since we are throwing those colors
00188      away. We assigned it this time through if the cached mapping is >=
00189      dest->ncol. */
00190   for (x = 0; x < i; x++)
00191     if (srccol[x].haspixel == 1 && srccol[x].pixel >= dest->ncol)
00192       srccol[x].pixel = 256;
00193   
00194   return 0;
00195 }
00196 
00197 
00198 void
00199 merge_stream(Gif_Stream *dest, Gif_Stream *src, int no_comments)
00200 {
00201   int i;
00202   assert(dest->global);
00203   
00204   /* unmark colors in global and local colormaps -- 12/9 */
00205   if (src->global)
00206     unmark_colors_2(src->global);
00207   for (i = 0; i < src->nimages; i++)
00208     if (src->images[i]->local)
00209       unmark_colors_2(src->images[i]->local);
00210   
00211   if (dest->loopcount < 0)
00212     dest->loopcount = src->loopcount;
00213   
00214   if (src->comment && !no_comments) {
00215     if (!dest->comment) dest->comment = Gif_NewComment();
00216     merge_comments(dest->comment, src->comment);
00217   }
00218 }
00219 
00220 
00221 void
00222 merge_comments(Gif_Comment *destc, Gif_Comment *srcc)
00223 {
00224   int i;
00225   for (i = 0; i < srcc->count; i++)
00226     Gif_AddComment(destc, srcc->str[i], srcc->len[i]);
00227 }
00228 
00229 
00230 Gif_Image *
00231 merge_image(Gif_Stream *dest, Gif_Stream *src, Gif_Image *srci)
00232 {
00233   Gif_Colormap *imagecm;
00234   Gif_Color *imagecol;
00235   int islocal;
00236   int i;
00237   Gif_Colormap *localcm = 0;
00238   Gif_Colormap *destcm = dest->global;
00239   
00240   byte map[256];                /* map[input pixel value] == output pixval */
00241   int trivial_map = 1;          /* does the map take input pixval --> the same
00242                                    pixel value for all colors in the image? */
00243   byte used[256];               /* used[output pixval K] == 1 iff K was used
00244                                    in the image */
00245   
00246   Gif_Image *desti;
00247   
00248   /* mark colors that were actually used in this image */
00249   islocal = srci->local != 0;
00250   imagecm = islocal ? srci->local : src->global;
00251   if (!imagecm)
00252     fatal_error("no global or local colormap for source image");
00253   
00254   mark_used_colors(srci, imagecm);
00255   imagecol = imagecm->col;      /* may be changed by mark_used_colors */
00256   
00257   /* map[old_pixel_value] == new_pixel_value */
00258   for (i = 0; i < 256; i++)
00259     map[i] = used[i] = 0;
00260   
00261   /* Merge the colormap */
00262   if (merge_colormap_if_possible(dest->global, imagecm)) {
00263     /* Create `map' and `used' for global colormap. */
00264     for (i = 0; i < imagecm->ncol; i++)
00265       if (imagecol[i].haspixel == 1) {
00266         map[i] = imagecol[i].pixel;
00267         if (map[i] != i) trivial_map = 0;
00268         used[map[i]] = 1;
00269       }
00270     
00271   } else {
00272     /* Need a local colormap. */
00273     int ncol = 0;
00274     destcm = localcm = Gif_NewFullColormap(0, 256);
00275     for (i = 0; i < imagecm->ncol; i++)
00276       if (imagecol[i].haspixel) {
00277         map[i] = ncol;
00278         if (ncol != i) trivial_map = 0;
00279         /* 19.Aug.1999- BUGFIX! color is only used if it was opaque */
00280         if (imagecol[i].haspixel == 1)
00281           used[ncol] = 1;
00282         localcm->col[ ncol++ ] = imagecol[i];
00283       }
00284     localcm->ncol = ncol;
00285   }
00286   
00287   /* Decide on a transparent index */
00288   if (srci->transparent >= 0) {
00289     int found_transparent = -1;
00290     
00291     /* try to keep the map trivial -- prefer same transparent index */
00292     if (trivial_map && !used[srci->transparent])
00293       found_transparent = srci->transparent;
00294     else
00295       for (i = destcm->ncol - 1; i >= 0; i--)
00296         if (!used[i])
00297           found_transparent = i;
00298     
00299     /* 1.Aug.1999 - Allow for the case that the transparent index is bigger
00300        than the number of colors we've created thus far. */
00301     if (found_transparent < 0 || found_transparent >= destcm->ncol) {
00302       Gif_Color *c;
00303       found_transparent = destcm->ncol;
00304       /* 1.Aug.1999 - Don't update destcm->ncol -- we want the output colormap
00305          to be as small as possible. */
00306       c = &destcm->col[found_transparent];
00307       if (srci->transparent < imagecm->ncol)
00308         *c = imagecol[srci->transparent];
00309       else
00310         c->haspixel = 2;
00311       assert(c->haspixel == 2 && found_transparent < 256);
00312     }
00313     
00314     map[srci->transparent] = found_transparent;
00315     if (srci->transparent != found_transparent) trivial_map = 0;
00316   }
00317   
00318   assert(destcm->ncol <= 256);
00319   /* Make the new image. */
00320   desti = Gif_NewImage();
00321   
00322   desti->identifier = Gif_CopyString(srci->identifier);
00323   if (srci->transparent > -1)
00324     desti->transparent = map[srci->transparent];
00325   desti->delay = srci->delay;
00326   desti->disposal = srci->disposal;
00327   desti->left = srci->left;
00328   desti->top = srci->top;
00329   desti->interlace = srci->interlace;
00330   
00331   desti->width = srci->width;
00332   desti->height = srci->height;
00333   desti->local = localcm;
00334   
00335   if (srci->comment) {
00336     desti->comment = Gif_NewComment();
00337     merge_comments(desti->comment, srci->comment);
00338   }
00339   
00340   Gif_CreateUncompressedImage(desti);
00341   
00342   {
00343     int i, j;
00344     
00345     if (trivial_map)
00346       for (j = 0; j < desti->height; j++)
00347         memcpy(desti->img[j], srci->img[j], desti->width);
00348     
00349     else
00350       for (j = 0; j < desti->height; j++) {
00351         byte *srcdata = srci->img[j];
00352         byte *destdata = desti->img[j];
00353         for (i = 0; i < desti->width; i++, srcdata++, destdata++)
00354           *destdata = map[*srcdata];
00355       }
00356   }
00357   
00358   Gif_AddImage(dest, desti);
00359   return desti;  
00360 }