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