1 /*
2 * wrgif.c
3 *
4 * This file was part of the Independent JPEG Group's software:
5 * Copyright (C) 1991-1997, Thomas G. Lane.
6 * Modified 2015-2019 by Guido Vollbeding.
7 * libjpeg-turbo Modifications:
8 * Copyright (C) 2015, 2017, D. R. Commander.
9 * For conditions of distribution and use, see the accompanying README.ijg
10 * file.
11 *
12 * This file contains routines to write output images in GIF format.
13 *
14 * These routines may need modification for non-Unix environments or
15 * specialized applications. As they stand, they assume output to
16 * an ordinary stdio stream.
17 */
18
19 /*
20 * This code is loosely based on ppmtogif from the PBMPLUS distribution
21 * of Feb. 1991. That file contains the following copyright notice:
22 * Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
23 * Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
24 * Copyright (C) 1989 by Jef Poskanzer.
25 * Permission to use, copy, modify, and distribute this software and its
26 * documentation for any purpose and without fee is hereby granted, provided
27 * that the above copyright notice appear in all copies and that both that
28 * copyright notice and this permission notice appear in supporting
29 * documentation. This software is provided "as is" without express or
30 * implied warranty.
31 */
32
33 #include "cdjpeg.h" /* Common decls for cjpeg/djpeg applications */
34
35 #ifdef GIF_SUPPORTED
36
37
38 #define MAX_LZW_BITS 12 /* maximum LZW code size (4096 symbols) */
39
40 typedef INT16 code_int; /* must hold -1 .. 2**MAX_LZW_BITS */
41
42 #define LZW_TABLE_SIZE ((code_int)1 << MAX_LZW_BITS)
43
44 #define HSIZE 5003 /* hash table size for 80% occupancy */
45
46 typedef int hash_int; /* must hold -2*HSIZE..2*HSIZE */
47
48 #define MAXCODE(n_bits) (((code_int)1 << (n_bits)) - 1)
49
50
51 /*
52 * The LZW hash table consists of two parallel arrays:
53 * hash_code[i] code of symbol in slot i, or 0 if empty slot
54 * hash_value[i] symbol's value; undefined if empty slot
55 * where slot values (i) range from 0 to HSIZE-1. The symbol value is
56 * its prefix symbol's code concatenated with its suffix character.
57 *
58 * Algorithm: use open addressing double hashing (no chaining) on the
59 * prefix code / suffix character combination. We do a variant of Knuth's
60 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
61 * secondary probe.
62 */
63
64 typedef int hash_entry; /* must hold (code_int << 8) | byte */
65
66 #define HASH_ENTRY(prefix, suffix) ((((hash_entry)(prefix)) << 8) | (suffix))
67
68
69 /* Private version of data destination object */
70
71 typedef struct {
72 struct djpeg_dest_struct pub; /* public fields */
73
74 j_decompress_ptr cinfo; /* back link saves passing separate parm */
75
76 /* State for packing variable-width codes into a bitstream */
77 int n_bits; /* current number of bits/code */
78 code_int maxcode; /* maximum code, given n_bits */
79 int init_bits; /* initial n_bits ... restored after clear */
80 int cur_accum; /* holds bits not yet output */
81 int cur_bits; /* # of bits in cur_accum */
82
83 /* LZW string construction */
84 code_int waiting_code; /* symbol not yet output; may be extendable */
85 boolean first_byte; /* if TRUE, waiting_code is not valid */
86
87 /* State for GIF code assignment */
88 code_int ClearCode; /* clear code (doesn't change) */
89 code_int EOFCode; /* EOF code (ditto) */
90 code_int free_code; /* LZW: first not-yet-used symbol code */
91 code_int code_counter; /* not LZW: counts output symbols */
92
93 /* LZW hash table */
94 code_int *hash_code; /* => hash table of symbol codes */
95 hash_entry *hash_value; /* => hash table of symbol values */
96
97 /* GIF data packet construction buffer */
98 int bytesinpkt; /* # of bytes in current packet */
99 char packetbuf[256]; /* workspace for accumulating packet */
100
101 } gif_dest_struct;
102
103 typedef gif_dest_struct *gif_dest_ptr;
104
105
106 /*
107 * Routines to package finished data bytes into GIF data blocks.
108 * A data block consists of a count byte (1..255) and that many data bytes.
109 */
110
111 LOCAL(void)
flush_packet(gif_dest_ptr dinfo)112 flush_packet(gif_dest_ptr dinfo)
113 /* flush any accumulated data */
114 {
115 if (dinfo->bytesinpkt > 0) { /* never write zero-length packet */
116 dinfo->packetbuf[0] = (char)dinfo->bytesinpkt++;
117 if (JFWRITE(dinfo->pub.output_file, dinfo->packetbuf, dinfo->bytesinpkt) !=
118 (size_t)dinfo->bytesinpkt)
119 ERREXIT(dinfo->cinfo, JERR_FILE_WRITE);
120 dinfo->bytesinpkt = 0;
121 }
122 }
123
124
125 /* Add a character to current packet; flush to disk if necessary */
126 #define CHAR_OUT(dinfo, c) { \
127 (dinfo)->packetbuf[++(dinfo)->bytesinpkt] = (char)(c); \
128 if ((dinfo)->bytesinpkt >= 255) \
129 flush_packet(dinfo); \
130 }
131
132
133 /* Routine to convert variable-width codes into a byte stream */
134
135 LOCAL(void)
output(gif_dest_ptr dinfo,code_int code)136 output(gif_dest_ptr dinfo, code_int code)
137 /* Emit a code of n_bits bits */
138 /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
139 {
140 dinfo->cur_accum |= ((long)code) << dinfo->cur_bits;
141 dinfo->cur_bits += dinfo->n_bits;
142
143 while (dinfo->cur_bits >= 8) {
144 CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
145 dinfo->cur_accum >>= 8;
146 dinfo->cur_bits -= 8;
147 }
148
149 /*
150 * If the next entry is going to be too big for the code size,
151 * then increase it, if possible. We do this here to ensure
152 * that it's done in sync with the decoder's codesize increases.
153 */
154 if (dinfo->free_code > dinfo->maxcode) {
155 dinfo->n_bits++;
156 if (dinfo->n_bits == MAX_LZW_BITS)
157 dinfo->maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */
158 else
159 dinfo->maxcode = MAXCODE(dinfo->n_bits);
160 }
161 }
162
163
164 /* Compression initialization & termination */
165
166
167 LOCAL(void)
clear_hash(gif_dest_ptr dinfo)168 clear_hash(gif_dest_ptr dinfo)
169 /* Fill the hash table with empty entries */
170 {
171 /* It's sufficient to zero hash_code[] */
172 MEMZERO(dinfo->hash_code, HSIZE * sizeof(code_int));
173 }
174
175
176 LOCAL(void)
clear_block(gif_dest_ptr dinfo)177 clear_block(gif_dest_ptr dinfo)
178 /* Reset compressor and issue a Clear code */
179 {
180 clear_hash(dinfo); /* delete all the symbols */
181 dinfo->free_code = dinfo->ClearCode + 2;
182 output(dinfo, dinfo->ClearCode); /* inform decoder */
183 dinfo->n_bits = dinfo->init_bits; /* reset code size */
184 dinfo->maxcode = MAXCODE(dinfo->n_bits);
185 }
186
187
188 LOCAL(void)
compress_init(gif_dest_ptr dinfo,int i_bits)189 compress_init(gif_dest_ptr dinfo, int i_bits)
190 /* Initialize compressor */
191 {
192 /* init all the state variables */
193 dinfo->n_bits = dinfo->init_bits = i_bits;
194 dinfo->maxcode = MAXCODE(dinfo->n_bits);
195 dinfo->ClearCode = ((code_int) 1 << (i_bits - 1));
196 dinfo->EOFCode = dinfo->ClearCode + 1;
197 dinfo->code_counter = dinfo->free_code = dinfo->ClearCode + 2;
198 dinfo->first_byte = TRUE; /* no waiting symbol yet */
199 /* init output buffering vars */
200 dinfo->bytesinpkt = 0;
201 dinfo->cur_accum = 0;
202 dinfo->cur_bits = 0;
203 /* clear hash table */
204 if (dinfo->hash_code != NULL)
205 clear_hash(dinfo);
206 /* GIF specifies an initial Clear code */
207 output(dinfo, dinfo->ClearCode);
208 }
209
210
211 LOCAL(void)
compress_term(gif_dest_ptr dinfo)212 compress_term(gif_dest_ptr dinfo)
213 /* Clean up at end */
214 {
215 /* Flush out the buffered LZW code */
216 if (!dinfo->first_byte)
217 output(dinfo, dinfo->waiting_code);
218 /* Send an EOF code */
219 output(dinfo, dinfo->EOFCode);
220 /* Flush the bit-packing buffer */
221 if (dinfo->cur_bits > 0) {
222 CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
223 }
224 /* Flush the packet buffer */
225 flush_packet(dinfo);
226 }
227
228
229 /* GIF header construction */
230
231
232 LOCAL(void)
put_word(gif_dest_ptr dinfo,unsigned int w)233 put_word(gif_dest_ptr dinfo, unsigned int w)
234 /* Emit a 16-bit word, LSB first */
235 {
236 putc(w & 0xFF, dinfo->pub.output_file);
237 putc((w >> 8) & 0xFF, dinfo->pub.output_file);
238 }
239
240
241 LOCAL(void)
put_3bytes(gif_dest_ptr dinfo,int val)242 put_3bytes(gif_dest_ptr dinfo, int val)
243 /* Emit 3 copies of same byte value --- handy subr for colormap construction */
244 {
245 putc(val, dinfo->pub.output_file);
246 putc(val, dinfo->pub.output_file);
247 putc(val, dinfo->pub.output_file);
248 }
249
250
251 LOCAL(void)
emit_header(gif_dest_ptr dinfo,int num_colors,JSAMPARRAY colormap)252 emit_header(gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap)
253 /* Output the GIF file header, including color map */
254 /* If colormap == NULL, synthesize a grayscale colormap */
255 {
256 int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte;
257 int cshift = dinfo->cinfo->data_precision - 8;
258 int i;
259
260 if (num_colors > 256)
261 ERREXIT1(dinfo->cinfo, JERR_TOO_MANY_COLORS, num_colors);
262 /* Compute bits/pixel and related values */
263 BitsPerPixel = 1;
264 while (num_colors > (1 << BitsPerPixel))
265 BitsPerPixel++;
266 ColorMapSize = 1 << BitsPerPixel;
267 if (BitsPerPixel <= 1)
268 InitCodeSize = 2;
269 else
270 InitCodeSize = BitsPerPixel;
271 /*
272 * Write the GIF header.
273 * Note that we generate a plain GIF87 header for maximum compatibility.
274 */
275 putc('G', dinfo->pub.output_file);
276 putc('I', dinfo->pub.output_file);
277 putc('F', dinfo->pub.output_file);
278 putc('8', dinfo->pub.output_file);
279 putc('7', dinfo->pub.output_file);
280 putc('a', dinfo->pub.output_file);
281 /* Write the Logical Screen Descriptor */
282 put_word(dinfo, (unsigned int)dinfo->cinfo->output_width);
283 put_word(dinfo, (unsigned int)dinfo->cinfo->output_height);
284 FlagByte = 0x80; /* Yes, there is a global color table */
285 FlagByte |= (BitsPerPixel - 1) << 4; /* color resolution */
286 FlagByte |= (BitsPerPixel - 1); /* size of global color table */
287 putc(FlagByte, dinfo->pub.output_file);
288 putc(0, dinfo->pub.output_file); /* Background color index */
289 putc(0, dinfo->pub.output_file); /* Reserved (aspect ratio in GIF89) */
290 /* Write the Global Color Map */
291 /* If the color map is more than 8 bits precision, */
292 /* we reduce it to 8 bits by shifting */
293 for (i = 0; i < ColorMapSize; i++) {
294 if (i < num_colors) {
295 if (colormap != NULL) {
296 if (dinfo->cinfo->out_color_space == JCS_RGB) {
297 /* Normal case: RGB color map */
298 putc(colormap[0][i] >> cshift, dinfo->pub.output_file);
299 putc(colormap[1][i] >> cshift, dinfo->pub.output_file);
300 putc(colormap[2][i] >> cshift, dinfo->pub.output_file);
301 } else {
302 /* Grayscale "color map": possible if quantizing grayscale image */
303 put_3bytes(dinfo, colormap[0][i] >> cshift);
304 }
305 } else {
306 /* Create a grayscale map of num_colors values, range 0..255 */
307 put_3bytes(dinfo, (i * 255 + (num_colors - 1) / 2) / (num_colors - 1));
308 }
309 } else {
310 /* fill out the map to a power of 2 */
311 put_3bytes(dinfo, CENTERJSAMPLE >> cshift);
312 }
313 }
314 /* Write image separator and Image Descriptor */
315 putc(',', dinfo->pub.output_file); /* separator */
316 put_word(dinfo, 0); /* left/top offset */
317 put_word(dinfo, 0);
318 put_word(dinfo, (unsigned int)dinfo->cinfo->output_width); /* image size */
319 put_word(dinfo, (unsigned int)dinfo->cinfo->output_height);
320 /* flag byte: not interlaced, no local color map */
321 putc(0x00, dinfo->pub.output_file);
322 /* Write Initial Code Size byte */
323 putc(InitCodeSize, dinfo->pub.output_file);
324
325 /* Initialize for compression of image data */
326 compress_init(dinfo, InitCodeSize + 1);
327 }
328
329
330 /*
331 * Startup: write the file header.
332 */
333
334 METHODDEF(void)
start_output_gif(j_decompress_ptr cinfo,djpeg_dest_ptr dinfo)335 start_output_gif(j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
336 {
337 gif_dest_ptr dest = (gif_dest_ptr)dinfo;
338
339 if (cinfo->quantize_colors)
340 emit_header(dest, cinfo->actual_number_of_colors, cinfo->colormap);
341 else
342 emit_header(dest, 256, (JSAMPARRAY)NULL);
343 }
344
345
346 /*
347 * Write some pixel data.
348 * In this module rows_supplied will always be 1.
349 */
350
351
352 /*
353 * The LZW algorithm proper
354 */
355
356 METHODDEF(void)
put_LZW_pixel_rows(j_decompress_ptr cinfo,djpeg_dest_ptr dinfo,JDIMENSION rows_supplied)357 put_LZW_pixel_rows(j_decompress_ptr cinfo, djpeg_dest_ptr dinfo,
358 JDIMENSION rows_supplied)
359 {
360 gif_dest_ptr dest = (gif_dest_ptr)dinfo;
361 register JSAMPROW ptr;
362 register JDIMENSION col;
363 code_int c;
364 register hash_int i;
365 register hash_int disp;
366 register hash_entry probe_value;
367
368 ptr = dest->pub.buffer[0];
369 for (col = cinfo->output_width; col > 0; col--) {
370 /* Accept and compress one 8-bit byte */
371 c = (code_int)(*ptr++);
372
373 if (dest->first_byte) { /* need to initialize waiting_code */
374 dest->waiting_code = c;
375 dest->first_byte = FALSE;
376 continue;
377 }
378
379 /* Probe hash table to see if a symbol exists for
380 * waiting_code followed by c.
381 * If so, replace waiting_code by that symbol and continue.
382 */
383 i = ((hash_int)c << (MAX_LZW_BITS - 8)) + dest->waiting_code;
384 /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
385 if (i >= HSIZE)
386 i -= HSIZE;
387
388 probe_value = HASH_ENTRY(dest->waiting_code, c);
389
390 if (dest->hash_code[i] == 0) {
391 /* hit empty slot; desired symbol not in table */
392 output(dest, dest->waiting_code);
393 if (dest->free_code < LZW_TABLE_SIZE) {
394 dest->hash_code[i] = dest->free_code++; /* add symbol to hashtable */
395 dest->hash_value[i] = probe_value;
396 } else
397 clear_block(dest);
398 dest->waiting_code = c;
399 continue;
400 }
401 if (dest->hash_value[i] == probe_value) {
402 dest->waiting_code = dest->hash_code[i];
403 continue;
404 }
405
406 if (i == 0) /* secondary hash (after G. Knott) */
407 disp = 1;
408 else
409 disp = HSIZE - i;
410 for (;;) {
411 i -= disp;
412 if (i < 0)
413 i += HSIZE;
414 if (dest->hash_code[i] == 0) {
415 /* hit empty slot; desired symbol not in table */
416 output(dest, dest->waiting_code);
417 if (dest->free_code < LZW_TABLE_SIZE) {
418 dest->hash_code[i] = dest->free_code++; /* add symbol to hashtable */
419 dest->hash_value[i] = probe_value;
420 } else
421 clear_block(dest);
422 dest->waiting_code = c;
423 break;
424 }
425 if (dest->hash_value[i] == probe_value) {
426 dest->waiting_code = dest->hash_code[i];
427 break;
428 }
429 }
430 }
431 }
432
433
434 /*
435 * The pseudo-compression algorithm.
436 *
437 * In this version we simply output each pixel value as a separate symbol;
438 * thus, no compression occurs. In fact, there is expansion of one bit per
439 * pixel, because we use a symbol width one bit wider than the pixel width.
440 *
441 * GIF ordinarily uses variable-width symbols, and the decoder will expect
442 * to ratchet up the symbol width after a fixed number of symbols.
443 * To simplify the logic and keep the expansion penalty down, we emit a
444 * GIF Clear code to reset the decoder just before the width would ratchet up.
445 * Thus, all the symbols in the output file will have the same bit width.
446 * Note that emitting the Clear codes at the right times is a mere matter of
447 * counting output symbols and is in no way dependent on the LZW algorithm.
448 *
449 * With a small basic pixel width (low color count), Clear codes will be
450 * needed very frequently, causing the file to expand even more. So this
451 * simplistic approach wouldn't work too well on bilevel images, for example.
452 * But for output of JPEG conversions the pixel width will usually be 8 bits
453 * (129 to 256 colors), so the overhead added by Clear symbols is only about
454 * one symbol in every 256.
455 */
456
457 METHODDEF(void)
put_raw_pixel_rows(j_decompress_ptr cinfo,djpeg_dest_ptr dinfo,JDIMENSION rows_supplied)458 put_raw_pixel_rows(j_decompress_ptr cinfo, djpeg_dest_ptr dinfo,
459 JDIMENSION rows_supplied)
460 {
461 gif_dest_ptr dest = (gif_dest_ptr)dinfo;
462 register JSAMPROW ptr;
463 register JDIMENSION col;
464 code_int c;
465
466 ptr = dest->pub.buffer[0];
467 for (col = cinfo->output_width; col > 0; col--) {
468 c = (code_int)(*ptr++);
469 /* Accept and output one pixel value.
470 * The given value must be less than n_bits wide.
471 */
472
473 /* Output the given pixel value as a symbol. */
474 output(dest, c);
475 /* Issue Clear codes often enough to keep the reader from ratcheting up
476 * its symbol size.
477 */
478 if (dest->code_counter < dest->maxcode) {
479 dest->code_counter++;
480 } else {
481 output(dest, dest->ClearCode);
482 dest->code_counter = dest->ClearCode + 2; /* reset the counter */
483 }
484 }
485 }
486
487
488 /*
489 * Finish up at the end of the file.
490 */
491
492 METHODDEF(void)
finish_output_gif(j_decompress_ptr cinfo,djpeg_dest_ptr dinfo)493 finish_output_gif(j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
494 {
495 gif_dest_ptr dest = (gif_dest_ptr)dinfo;
496
497 /* Flush compression mechanism */
498 compress_term(dest);
499 /* Write a zero-length data block to end the series */
500 putc(0, dest->pub.output_file);
501 /* Write the GIF terminator mark */
502 putc(';', dest->pub.output_file);
503 /* Make sure we wrote the output file OK */
504 fflush(dest->pub.output_file);
505 if (ferror(dest->pub.output_file))
506 ERREXIT(cinfo, JERR_FILE_WRITE);
507 }
508
509
510 /*
511 * Re-calculate buffer dimensions based on output dimensions.
512 */
513
514 METHODDEF(void)
calc_buffer_dimensions_gif(j_decompress_ptr cinfo,djpeg_dest_ptr dinfo)515 calc_buffer_dimensions_gif(j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
516 {
517 }
518
519
520 /*
521 * The module selection routine for GIF format output.
522 */
523
524 GLOBAL(djpeg_dest_ptr)
jinit_write_gif(j_decompress_ptr cinfo,boolean is_lzw)525 jinit_write_gif(j_decompress_ptr cinfo, boolean is_lzw)
526 {
527 gif_dest_ptr dest;
528
529 /* Create module interface object, fill in method pointers */
530 dest = (gif_dest_ptr)
531 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
532 sizeof(gif_dest_struct));
533 dest->cinfo = cinfo; /* make back link for subroutines */
534 dest->pub.start_output = start_output_gif;
535 dest->pub.finish_output = finish_output_gif;
536 dest->pub.calc_buffer_dimensions = calc_buffer_dimensions_gif;
537
538 if (cinfo->out_color_space != JCS_GRAYSCALE &&
539 cinfo->out_color_space != JCS_RGB)
540 ERREXIT(cinfo, JERR_GIF_COLORSPACE);
541
542 /* Force quantization if color or if > 8 bits input */
543 if (cinfo->out_color_space != JCS_GRAYSCALE || cinfo->data_precision > 8) {
544 /* Force quantization to at most 256 colors */
545 cinfo->quantize_colors = TRUE;
546 if (cinfo->desired_number_of_colors > 256)
547 cinfo->desired_number_of_colors = 256;
548 }
549
550 /* Calculate output image dimensions so we can allocate space */
551 jpeg_calc_output_dimensions(cinfo);
552
553 if (cinfo->output_components != 1) /* safety check: just one component? */
554 ERREXIT(cinfo, JERR_GIF_BUG);
555
556 /* Create decompressor output buffer. */
557 dest->pub.buffer = (*cinfo->mem->alloc_sarray)
558 ((j_common_ptr)cinfo, JPOOL_IMAGE, cinfo->output_width, (JDIMENSION)1);
559 dest->pub.buffer_height = 1;
560
561 if (is_lzw) {
562 dest->pub.put_pixel_rows = put_LZW_pixel_rows;
563 /* Allocate space for hash table */
564 dest->hash_code = (code_int *)
565 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
566 HSIZE * sizeof(code_int));
567 dest->hash_value = (hash_entry *)
568 (*cinfo->mem->alloc_large) ((j_common_ptr)cinfo, JPOOL_IMAGE,
569 HSIZE * sizeof(hash_entry));
570 } else {
571 dest->pub.put_pixel_rows = put_raw_pixel_rows;
572 /* Mark tables unused */
573 dest->hash_code = NULL;
574 dest->hash_value = NULL;
575 }
576
577 return (djpeg_dest_ptr)dest;
578 }
579
580 #endif /* GIF_SUPPORTED */
581