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