"Fossies" - the Fresh Open Source Software Archive

Member "gifsicle-1.92/src/optimize.c" (18 Apr 2019, 13030 Bytes) of package /linux/misc/gifsicle-1.92.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "optimize.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.91_vs_1.92.

    1 /* optimize.c - Functions to optimize animated GIFs.
    2    Copyright (C) 1997-2019 Eddie Kohler, ekohler@gmail.com
    3    This file is part of gifsicle.
    4 
    5    Gifsicle is free software. It is distributed under the GNU Public License,
    6    version 2; you can copy, distribute, or alter it at will, as long
    7    as this notice is kept intact and this source code is made available. There
    8    is no warranty, express or implied. */
    9 
   10 #include <config.h>
   11 #include "gifsicle.h"
   12 #include "kcolor.h"
   13 #include <assert.h>
   14 #include <string.h>
   15 
   16 typedef int32_t penalty_type;
   17 
   18 typedef struct {
   19   int left;
   20   int top;
   21   int width;
   22   int height;
   23 } Gif_OptBounds;
   24 
   25 typedef struct {
   26   uint16_t left;
   27   uint16_t top;
   28   uint16_t width;
   29   uint16_t height;
   30   uint32_t size;
   31   uint8_t disposal;
   32   int transparent;
   33   uint8_t *needed_colors;
   34   unsigned required_color_count;
   35   int32_t active_penalty;
   36   int32_t global_penalty;
   37   int32_t colormap_penalty;
   38   Gif_Image *new_gfi;
   39 } Gif_OptData;
   40 
   41 /* Screen width and height */
   42 static int screen_width;
   43 static int screen_height;
   44 
   45 /* Colormap containing all colors in the image. May have >256 colors */
   46 static Gif_Colormap *all_colormap;
   47 /* Histogram so we can find colors quickly */
   48 static kchist all_colormap_hist;
   49 
   50 /* The old global colormap, or a fake one we created if necessary */
   51 static Gif_Colormap *in_global_map;
   52 
   53 /* The new global colormap */
   54 static Gif_Colormap *out_global_map;
   55 
   56 #define TRANSP (0)
   57 #define NOT_IN_OUT_GLOBAL (256)
   58 static unsigned background;
   59 static int image_index;
   60 
   61 static penalty_type *permuting_sort_values;
   62 
   63 #define REQUIRED        2
   64 #define REPLACE_TRANSP  1
   65 
   66 
   67 /*****
   68  * SIMPLE HELPERS
   69  * new and delete optimize data; and colormap_combine; and sorting permutations
   70  **/
   71 
   72 Gif_OptData *
   73 new_opt_data(void)
   74 {
   75   Gif_OptData *od = Gif_New(Gif_OptData);
   76   od->needed_colors = 0;
   77   od->global_penalty = 1;
   78   return od;
   79 }
   80 
   81 void
   82 delete_opt_data(Gif_OptData *od)
   83 {
   84   if (!od) return;
   85   Gif_DeleteArray(od->needed_colors);
   86   Gif_Delete(od);
   87 }
   88 
   89 
   90 /* all_colormap_add: Ensure that each color in 'src' is represented in
   91    'all_colormap'. For each color 'i' in 'src', src->col[i].pixel == some j
   92    so that GIF_COLOREQ(&src->col[i], &all_colormap->col[j]).
   93    all_colormap->col[0] is reserved for transparency; no source color will
   94    be mapped to it. */
   95 
   96 static void all_colormap_add(const Gif_Colormap* src) {
   97     int i;
   98 
   99     /* expand dst->col if necessary. This might change dst->col */
  100     if (all_colormap->ncol + src->ncol >= all_colormap->capacity) {
  101         all_colormap->capacity *= 2;
  102         Gif_ReArray(all_colormap->col, Gif_Color, all_colormap->capacity);
  103     }
  104 
  105     for (i = 0; i < src->ncol; ++i) {
  106         kchistitem* khi = kchist_add(&all_colormap_hist,
  107                                      kc_makegfcng(&src->col[i]), 0);
  108         if (!khi->count) {
  109             all_colormap->col[all_colormap->ncol] = src->col[i];
  110             all_colormap->col[all_colormap->ncol].pixel = 0;
  111             khi->count = all_colormap->ncol;
  112             ++all_colormap->ncol;
  113         }
  114         src->col[i].pixel = khi->count;
  115     }
  116 }
  117 
  118 
  119 /*****
  120  * MANIPULATING IMAGE AREAS
  121  **/
  122 
  123 static Gif_OptBounds
  124 safe_bounds(Gif_Image *area)
  125 {
  126   /* Returns bounds constrained to lie within the screen. */
  127   Gif_OptBounds b;
  128   b.left = constrain(0, area->left, screen_width);
  129   b.top = constrain(0, area->top, screen_height);
  130   b.width = constrain(0, area->left + area->width, screen_width) - b.left;
  131   b.height = constrain(0, area->top + area->height, screen_height) - b.top;
  132   return b;
  133 }
  134 
  135 
  136 /*****
  137  * FIND THE SMALLEST BOUNDING RECTANGLE ENCLOSING ALL CHANGES
  138  **/
  139 
  140 /* fix_difference_bounds: make sure the image isn't 0x0. */
  141 
  142 static void
  143 fix_difference_bounds(Gif_OptData *bounds)
  144 {
  145   if (bounds->width == 0 || bounds->height == 0) {
  146     bounds->top = 0;
  147     bounds->left = 0;
  148     bounds->width = 1;
  149     bounds->height = 1;
  150   }
  151   /* assert that image lies completely within screen */
  152   assert(bounds->top < screen_height && bounds->left < screen_width
  153          && bounds->top + bounds->height <= screen_height
  154          && bounds->left + bounds->width <= screen_width);
  155 }
  156 
  157 
  158 /*****
  159  * CALCULATE OUTPUT GLOBAL COLORMAP
  160  **/
  161 
  162 static void
  163 increment_penalties(Gif_OptData *opt, penalty_type *penalty, int32_t delta)
  164 {
  165   int i;
  166   int all_ncol = all_colormap->ncol;
  167   uint8_t *need = opt->needed_colors;
  168   for (i = 1; i < all_ncol; i++)
  169     if (need[i] == REQUIRED)
  170       penalty[i] += delta;
  171 }
  172 
  173 
  174 /*****
  175  * CREATE COLOR MAPPING FOR A PARTICULAR IMAGE
  176  **/
  177 
  178 /* sort_colormap_permutation_rgb: for canonicalizing local colormaps by
  179    arranging them in RGB order */
  180 
  181 static int
  182 colormap_rgb_permutation_sorter(const void *v1, const void *v2)
  183 {
  184   const Gif_Color *col1 = (const Gif_Color *)v1;
  185   const Gif_Color *col2 = (const Gif_Color *)v2;
  186   int value1 = (col1->gfc_red << 16) | (col1->gfc_green << 8) | col1->gfc_blue;
  187   int value2 = (col2->gfc_red << 16) | (col2->gfc_green << 8) | col2->gfc_blue;
  188   return value1 - value2;
  189 }
  190 
  191 
  192 /* prepare_colormap_map: Create and return an array of bytes mapping from
  193    global pixel values to pixel values for this image. It may add colormap
  194    cells to 'into'; if there isn't enough room in 'into', it will return 0. It
  195    sets the 'transparent' field of 'gfi->optdata', but otherwise doesn't
  196    change or read it at all. */
  197 
  198 static uint8_t *
  199 prepare_colormap_map(Gif_Image *gfi, Gif_Colormap *into, uint8_t *need)
  200 {
  201   int i;
  202   int is_global = (into == out_global_map);
  203 
  204   int all_ncol = all_colormap->ncol;
  205   Gif_Color *all_col = all_colormap->col;
  206 
  207   int ncol = into->ncol;
  208   Gif_Color *col = into->col;
  209 
  210   uint8_t *map = Gif_NewArray(uint8_t, all_ncol);
  211   uint8_t into_used[256];
  212 
  213   /* keep track of which pixel indices in 'into' have been used; initially,
  214      all unused */
  215   for (i = 0; i < 256; i++)
  216     into_used[i] = 0;
  217 
  218   /* go over all non-transparent global pixels which MUST appear
  219      (need[P]==REQUIRED) and place them in 'into' */
  220   for (i = 1; i < all_ncol; i++) {
  221     int val;
  222     if (need[i] != REQUIRED)
  223       continue;
  224 
  225     /* fail if a needed pixel isn't in the global map */
  226     if (is_global) {
  227       val = all_col[i].pixel;
  228       if (val >= ncol)
  229         goto error;
  230     } else {
  231       /* always place colors in a local colormap */
  232       if (ncol == 256)
  233         goto error;
  234       val = ncol;
  235       col[val] = all_col[i];
  236       col[val].pixel = i;
  237       ncol++;
  238     }
  239 
  240     map[i] = val;
  241     into_used[val] = 1;
  242   }
  243 
  244   if (!is_global) {
  245     qsort(col, ncol, sizeof(Gif_Color), colormap_rgb_permutation_sorter);
  246     for (i = 0; i < ncol; ++i)
  247       map[col[i].pixel] = i;
  248   }
  249 
  250   /* now check for transparency */
  251   gfi->transparent = -1;
  252   if (need[TRANSP]) {
  253     int transparent = -1;
  254 
  255     /* first, look for an unused index in 'into'. Pick the lowest one: the
  256        lower transparent index we get, the more likely we can shave a bit off
  257        min_code_bits later, thus saving space */
  258     for (i = 0; i < ncol; i++)
  259       if (!into_used[i]) {
  260         transparent = i;
  261         break;
  262       }
  263 
  264     /* otherwise, [1.Aug.1999] use a fake slot for the purely transparent
  265        color. Don't actually enter the transparent color into the colormap --
  266        we might be able to output a smaller colormap! If there's no room for
  267        it, give up */
  268     if (transparent < 0) {
  269       if (ncol < 256) {
  270         transparent = ncol;
  271         /* 1.Aug.1999 - don't increase ncol */
  272         col[ncol] = all_col[TRANSP];
  273       } else
  274         goto error;
  275     }
  276 
  277     /* change mapping */
  278     map[TRANSP] = transparent;
  279     for (i = 1; i < all_ncol; i++)
  280       if (need[i] == REPLACE_TRANSP)
  281         map[i] = transparent;
  282 
  283     gfi->transparent = transparent;
  284   }
  285 
  286   /* If we get here, it worked! Commit state changes (the number of color
  287      cells in 'into') and return the map. */
  288   into->ncol = ncol;
  289   return map;
  290 
  291  error:
  292   /* If we get here, it failed! Return 0 and don't change global state. */
  293   Gif_DeleteArray(map);
  294   return 0;
  295 }
  296 
  297 
  298 /* prepare_colormap: make a colormap up from the image data by fitting any
  299    used colors into a colormap. Returns a map from global color index to index
  300    in this image's colormap. May set a local colormap on 'gfi'. */
  301 
  302 static uint8_t *
  303 prepare_colormap(Gif_Image *gfi, uint8_t *need)
  304 {
  305   uint8_t *map;
  306 
  307   /* try to map pixel values into the global colormap */
  308   Gif_DeleteColormap(gfi->local);
  309   gfi->local = 0;
  310   map = prepare_colormap_map(gfi, out_global_map, need);
  311 
  312   if (!map) {
  313     /* that didn't work; add a local colormap. */
  314     gfi->local = Gif_NewFullColormap(0, 256);
  315     map = prepare_colormap_map(gfi, gfi->local, need);
  316   }
  317 
  318   return map;
  319 }
  320 
  321 
  322 /*****
  323  * INITIALIZATION AND FINALIZATION
  324  **/
  325 
  326 static int
  327 initialize_optimizer(Gif_Stream *gfs)
  328 {
  329   int i;
  330 
  331   if (gfs->nimages < 1)
  332     return 0;
  333 
  334   /* combine colormaps */
  335   all_colormap = Gif_NewFullColormap(1, 384);
  336   all_colormap->col[0].gfc_red = 255;
  337   all_colormap->col[0].gfc_green = 255;
  338   all_colormap->col[0].gfc_blue = 255;
  339 
  340   in_global_map = gfs->global;
  341   if (!in_global_map) {
  342     Gif_Color *col;
  343     in_global_map = Gif_NewFullColormap(256, 256);
  344     col = in_global_map->col;
  345     for (i = 0; i < 256; i++, col++)
  346       col->gfc_red = col->gfc_green = col->gfc_blue = i;
  347   }
  348 
  349   {
  350     int any_globals = 0;
  351     int first_transparent = -1;
  352 
  353     kchist_init(&all_colormap_hist);
  354     for (i = 0; i < gfs->nimages; i++) {
  355       Gif_Image *gfi = gfs->images[i];
  356       if (gfi->local)
  357         all_colormap_add(gfi->local);
  358       else
  359         any_globals = 1;
  360       if (gfi->transparent >= 0 && first_transparent < 0)
  361         first_transparent = i;
  362     }
  363     if (any_globals)
  364       all_colormap_add(in_global_map);
  365     kchist_cleanup(&all_colormap_hist);
  366 
  367     /* try and maintain transparency's pixel value */
  368     if (first_transparent >= 0) {
  369       Gif_Image *gfi = gfs->images[first_transparent];
  370       Gif_Colormap *gfcm = gfi->local ? gfi->local : gfs->global;
  371       all_colormap->col[TRANSP] = gfcm->col[gfi->transparent];
  372     }
  373   }
  374 
  375   /* find screen_width and screen_height, and clip all images to screen */
  376   Gif_CalculateScreenSize(gfs, 0);
  377   screen_width = gfs->screen_width;
  378   screen_height = gfs->screen_height;
  379   for (i = 0; i < gfs->nimages; i++)
  380     Gif_ClipImage(gfs->images[i], 0, 0, screen_width, screen_height);
  381 
  382   /* choose background */
  383   if (gfs->images[0]->transparent < 0
  384       && gfs->global && gfs->background < in_global_map->ncol)
  385     background = in_global_map->col[gfs->background].pixel;
  386   else
  387     background = TRANSP;
  388 
  389   return 1;
  390 }
  391 
  392 static void
  393 finalize_optimizer(Gif_Stream *gfs, int optimize_flags)
  394 {
  395   int i;
  396 
  397   if (background == TRANSP)
  398     gfs->background = (uint8_t)gfs->images[0]->transparent;
  399 
  400   /* 11.Mar.2010 - remove entirely transparent frames. */
  401   for (i = 1; i < gfs->nimages && !(optimize_flags & GT_OPT_KEEPEMPTY); ++i) {
  402     Gif_Image *gfi = gfs->images[i];
  403     if (gfi->width == 1 && gfi->height == 1 && gfi->transparent >= 0
  404         && !gfi->identifier && !gfi->comment
  405         && (gfi->disposal == GIF_DISPOSAL_ASIS
  406             || gfi->disposal == GIF_DISPOSAL_NONE
  407             || gfi->disposal == GIF_DISPOSAL_PREVIOUS)
  408         && gfi->delay && gfs->images[i-1]->delay) {
  409       Gif_UncompressImage(gfs, gfi);
  410       if (gfi->img[0][0] == gfi->transparent
  411           && (gfs->images[i-1]->disposal == GIF_DISPOSAL_ASIS
  412               || gfs->images[i-1]->disposal == GIF_DISPOSAL_NONE)) {
  413         gfs->images[i-1]->delay += gfi->delay;
  414         Gif_DeleteImage(gfi);
  415         memmove(&gfs->images[i], &gfs->images[i+1], sizeof(Gif_Image *) * (gfs->nimages - i - 1));
  416         --gfs->nimages;
  417         --i;
  418       }
  419     }
  420   }
  421 
  422   /* 10.Dec.1998 - prefer GIF_DISPOSAL_NONE to GIF_DISPOSAL_ASIS. This is
  423      semantically "wrong" -- it's better to set the disposal explicitly than
  424      rely on default behavior -- but will result in smaller GIF files, since
  425      the graphic control extension can be left off in many cases. */
  426   for (i = 0; i < gfs->nimages; i++)
  427     if (gfs->images[i]->disposal == GIF_DISPOSAL_ASIS
  428         && gfs->images[i]->delay == 0
  429         && gfs->images[i]->transparent < 0)
  430       gfs->images[i]->disposal = GIF_DISPOSAL_NONE;
  431 
  432   Gif_DeleteColormap(in_global_map);
  433   Gif_DeleteColormap(all_colormap);
  434 }
  435 
  436 
  437 /* two versions of the optimization template */
  438 #define palindex_type uint16_t
  439 #define X(t) t ## 16
  440 #include "opttemplate.c"
  441 #undef palindex_type
  442 #undef X
  443 
  444 #define palindex_type uint32_t
  445 #define X(t) t ## 32
  446 #include "opttemplate.c"
  447 
  448 /* the interface function! */
  449 
  450 void
  451 optimize_fragments(Gif_Stream *gfs, int optimize_flags, int huge_stream)
  452 {
  453     if (!initialize_optimizer(gfs))
  454         return;
  455     if ((unsigned) all_colormap->ncol >= 0xFFFF) {
  456         create_subimages32(gfs, optimize_flags, !huge_stream);
  457         create_out_global_map32(gfs);
  458         create_new_image_data32(gfs, optimize_flags);
  459         finalize_optimizer_data32();
  460     } else {
  461         create_subimages16(gfs, optimize_flags, !huge_stream);
  462         create_out_global_map16(gfs);
  463         create_new_image_data16(gfs, optimize_flags);
  464         finalize_optimizer_data16();
  465     }
  466     finalize_optimizer(gfs, optimize_flags);
  467 }