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 *
new_opt_data(void)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
delete_opt_data(Gif_OptData * od)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
all_colormap_add(const Gif_Colormap * src)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
safe_bounds(Gif_Image * area)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
fix_difference_bounds(Gif_OptData * bounds)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
increment_penalties(Gif_OptData * opt,penalty_type * penalty,int32_t delta)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
colormap_rgb_permutation_sorter(const void * v1,const void * v2)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 *
prepare_colormap_map(Gif_Image * gfi,Gif_Colormap * into,uint8_t * need)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 *
prepare_colormap(Gif_Image * gfi,uint8_t * need)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
initialize_optimizer(Gif_Stream * gfs)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
finalize_optimizer(Gif_Stream * gfs,int optimize_flags)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
optimize_fragments(Gif_Stream * gfs,int optimize_flags,int huge_stream)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 }
468