diff options
Diffstat (limited to 'jpeg/wrgif.c')
| -rw-r--r-- | jpeg/wrgif.c | 334 |
1 files changed, 250 insertions, 84 deletions
diff --git a/jpeg/wrgif.c b/jpeg/wrgif.c index 843a1036..9d472de1 100644 --- a/jpeg/wrgif.c +++ b/jpeg/wrgif.c @@ -1,19 +1,13 @@ /* * wrgif.c * - * Copyright (C) 1991-1997, Thomas G. Lane. - * Modified 2015-2017 by Guido Vollbeding. + * Copyright (C) 1991-1996, Thomas G. Lane. + * Modified 2015-2019 by Guido Vollbeding. * This file is part of the Independent JPEG Group's software. * For conditions of distribution and use, see the accompanying README file. * * This file contains routines to write output images in GIF format. * - ************************************************************************** - * NOTE: to avoid entanglements with Unisys' patent on LZW compression, * - * this code has been modified to output "uncompressed GIF" files. * - * There is no trace of the LZW algorithm in this file. * - ************************************************************************** - * * These routines may need modification for non-Unix environments or * specialized applications. As they stand, they assume output to * an ordinary stdio stream. @@ -31,11 +25,6 @@ * copyright notice and this permission notice appear in supporting * documentation. This software is provided "as is" without express or * implied warranty. - * - * We are also required to state that - * "The Graphics Interchange Format(c) is the Copyright property of - * CompuServe Incorporated. GIF(sm) is a Service Mark property of - * CompuServe Incorporated." */ #include "cdjpeg.h" /* Common decls for cjpeg/djpeg applications */ @@ -43,6 +32,40 @@ #ifdef GIF_SUPPORTED +#define MAX_LZW_BITS 12 /* maximum LZW code size (4096 symbols) */ + +typedef INT16 code_int; /* must hold -1 .. 2**MAX_LZW_BITS */ + +#define LZW_TABLE_SIZE ((code_int) 1 << MAX_LZW_BITS) + +#define HSIZE 5003 /* hash table size for 80% occupancy */ + +typedef int hash_int; /* must hold -2*HSIZE..2*HSIZE */ + +#define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1) + + +/* + * The LZW hash table consists of two parallel arrays: + * hash_code[i] code of symbol in slot i, or 0 if empty slot + * hash_value[i] symbol's value; undefined if empty slot + * where slot values (i) range from 0 to HSIZE-1. The symbol value is + * its prefix symbol's code concatenated with its suffix character. + * + * Algorithm: use open addressing double hashing (no chaining) on the + * prefix code / suffix character combination. We do a variant of Knuth's + * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime + * secondary probe. + * + * The hash_value[] table is allocated from FAR heap space since it would + * use up rather a lot of the near data space in a PC. + */ + +typedef INT32 hash_entry; /* must hold (code_int<<8) | byte */ + +#define HASH_ENTRY(prefix, suffix) ((((hash_entry) (prefix)) << 8) | (suffix)) + + /* Private version of data destination object */ typedef struct { @@ -52,14 +75,24 @@ typedef struct { /* State for packing variable-width codes into a bitstream */ int n_bits; /* current number of bits/code */ - int maxcode; /* maximum code, given n_bits */ + code_int maxcode; /* maximum code, given n_bits */ + int init_bits; /* initial n_bits ... restored after clear */ INT32 cur_accum; /* holds bits not yet output */ int cur_bits; /* # of bits in cur_accum */ + /* LZW string construction */ + code_int waiting_code; /* symbol not yet output; may be extendable */ + boolean first_byte; /* if TRUE, waiting_code is not valid */ + /* State for GIF code assignment */ - int ClearCode; /* clear code (doesn't change) */ - int EOFCode; /* EOF code (ditto) */ - int code_counter; /* counts output symbols */ + code_int ClearCode; /* clear code (doesn't change) */ + code_int EOFCode; /* EOF code (ditto) */ + code_int free_code; /* LZW: first not-yet-used symbol code */ + code_int code_counter; /* not LZW: counts output symbols */ + + /* LZW hash table */ + code_int *hash_code; /* => hash table of symbol codes */ + hash_entry FAR *hash_value; /* => hash table of symbol values */ /* GIF data packet construction buffer */ int bytesinpkt; /* # of bytes in current packet */ @@ -69,9 +102,6 @@ typedef struct { typedef gif_dest_struct * gif_dest_ptr; -/* Largest value that will fit in N bits */ -#define MAXCODE(n_bits) ((1 << (n_bits)) - 1) - /* * Routines to package finished data bytes into GIF data blocks. @@ -93,7 +123,7 @@ flush_packet (gif_dest_ptr dinfo) /* Add a character to current packet; flush to disk if necessary */ -#define CHAR_OUT(dinfo,c) \ +#define CHAR_OUT(dinfo, c) \ { (dinfo)->packetbuf[++(dinfo)->bytesinpkt] = (char) (c); \ if ((dinfo)->bytesinpkt >= 255) \ flush_packet(dinfo); \ @@ -103,7 +133,7 @@ flush_packet (gif_dest_ptr dinfo) /* Routine to convert variable-width codes into a byte stream */ LOCAL(void) -output (gif_dest_ptr dinfo, int code) +output (gif_dest_ptr dinfo, code_int code) /* Emit a code of n_bits bits */ /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */ { @@ -115,74 +145,76 @@ output (gif_dest_ptr dinfo, int code) dinfo->cur_accum >>= 8; dinfo->cur_bits -= 8; } + + /* + * If the next entry is going to be too big for the code size, + * then increase it, if possible. We do this here to ensure + * that it's done in sync with the decoder's codesize increases. + */ + if (dinfo->free_code > dinfo->maxcode) { + dinfo->n_bits++; + if (dinfo->n_bits == MAX_LZW_BITS) + dinfo->maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */ + else + dinfo->maxcode = MAXCODE(dinfo->n_bits); + } } -/* The pseudo-compression algorithm. - * - * In this module we simply output each pixel value as a separate symbol; - * thus, no compression occurs. In fact, there is expansion of one bit per - * pixel, because we use a symbol width one bit wider than the pixel width. - * - * GIF ordinarily uses variable-width symbols, and the decoder will expect - * to ratchet up the symbol width after a fixed number of symbols. - * To simplify the logic and keep the expansion penalty down, we emit a - * GIF Clear code to reset the decoder just before the width would ratchet up. - * Thus, all the symbols in the output file will have the same bit width. - * Note that emitting the Clear codes at the right times is a mere matter of - * counting output symbols and is in no way dependent on the LZW patent. - * - * With a small basic pixel width (low color count), Clear codes will be - * needed very frequently, causing the file to expand even more. So this - * simplistic approach wouldn't work too well on bilevel images, for example. - * But for output of JPEG conversions the pixel width will usually be 8 bits - * (129 to 256 colors), so the overhead added by Clear symbols is only about - * one symbol in every 256. - */ +/* Compression initialization & termination */ + + +LOCAL(void) +clear_hash (gif_dest_ptr dinfo) +/* Fill the hash table with empty entries */ +{ + /* It's sufficient to zero hash_code[] */ + MEMZERO(dinfo->hash_code, HSIZE * SIZEOF(code_int)); +} + + +LOCAL(void) +clear_block (gif_dest_ptr dinfo) +/* Reset compressor and issue a Clear code */ +{ + clear_hash(dinfo); /* delete all the symbols */ + dinfo->free_code = dinfo->ClearCode + 2; + output(dinfo, dinfo->ClearCode); /* inform decoder */ + dinfo->n_bits = dinfo->init_bits; /* reset code size */ + dinfo->maxcode = MAXCODE(dinfo->n_bits); +} + LOCAL(void) compress_init (gif_dest_ptr dinfo, int i_bits) -/* Initialize pseudo-compressor */ +/* Initialize compressor */ { /* init all the state variables */ - dinfo->n_bits = i_bits; + dinfo->n_bits = dinfo->init_bits = i_bits; dinfo->maxcode = MAXCODE(dinfo->n_bits); - dinfo->ClearCode = (1 << (i_bits - 1)); + dinfo->ClearCode = ((code_int) 1 << (i_bits - 1)); dinfo->EOFCode = dinfo->ClearCode + 1; - dinfo->code_counter = dinfo->ClearCode + 2; + dinfo->code_counter = dinfo->free_code = dinfo->ClearCode + 2; + dinfo->first_byte = TRUE; /* no waiting symbol yet */ /* init output buffering vars */ dinfo->bytesinpkt = 0; dinfo->cur_accum = 0; dinfo->cur_bits = 0; + /* clear hash table */ + if (dinfo->hash_code != NULL) + clear_hash(dinfo); /* GIF specifies an initial Clear code */ output(dinfo, dinfo->ClearCode); } LOCAL(void) -compress_pixel (gif_dest_ptr dinfo, int c) -/* Accept and "compress" one pixel value. - * The given value must be less than n_bits wide. - */ -{ - /* Output the given pixel value as a symbol. */ - output(dinfo, c); - /* Issue Clear codes often enough to keep the reader from ratcheting up - * its symbol size. - */ - if (dinfo->code_counter < dinfo->maxcode) { - dinfo->code_counter++; - } else { - output(dinfo, dinfo->ClearCode); - dinfo->code_counter = dinfo->ClearCode + 2; /* reset the counter */ - } -} - - -LOCAL(void) compress_term (gif_dest_ptr dinfo) /* Clean up at end */ { + /* Flush out the buffered LZW code */ + if (! dinfo->first_byte) + output(dinfo, dinfo->waiting_code); /* Send an EOF code */ output(dinfo, dinfo->EOFCode); /* Flush the bit-packing buffer */ @@ -219,7 +251,7 @@ put_3bytes (gif_dest_ptr dinfo, int val) LOCAL(void) emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap) /* Output the GIF file header, including color map */ -/* If colormap==NULL, synthesize a grayscale colormap */ +/* If colormap == NULL, synthesize a grayscale colormap */ { int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte; int cshift = dinfo->cinfo->data_precision - 8; @@ -250,15 +282,15 @@ emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap) put_word(dinfo, (unsigned int) dinfo->cinfo->output_width); put_word(dinfo, (unsigned int) dinfo->cinfo->output_height); FlagByte = 0x80; /* Yes, there is a global color table */ - FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */ - FlagByte |= (BitsPerPixel-1); /* size of global color table */ + FlagByte |= (BitsPerPixel - 1) << 4; /* color resolution */ + FlagByte |= (BitsPerPixel - 1); /* size of global color table */ putc(FlagByte, dinfo->pub.output_file); putc(0, dinfo->pub.output_file); /* Background color index */ putc(0, dinfo->pub.output_file); /* Reserved (aspect ratio in GIF89) */ /* Write the Global Color Map */ /* If the color map is more than 8 bits precision, */ /* we reduce it to 8 bits by shifting */ - for (i=0; i < ColorMapSize; i++) { + for (i = 0; i < ColorMapSize; i++) { if (i < num_colors) { if (colormap != NULL) { if (dinfo->cinfo->out_color_space == JCS_RGB) { @@ -272,11 +304,11 @@ emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap) } } else { /* Create a grayscale map of num_colors values, range 0..255 */ - put_3bytes(dinfo, (i * 255 + (num_colors-1)/2) / (num_colors-1)); + put_3bytes(dinfo, (i * 255 + (num_colors - 1) / 2) / (num_colors - 1)); } } else { /* fill out the map to a power of 2 */ - put_3bytes(dinfo, 0); + put_3bytes(dinfo, CENTERJSAMPLE >> cshift); } } /* Write image separator and Image Descriptor */ @@ -290,8 +322,8 @@ emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap) /* Write Initial Code Size byte */ putc(InitCodeSize, dinfo->pub.output_file); - /* Initialize for "compression" of image data */ - compress_init(dinfo, InitCodeSize+1); + /* Initialize for compression of image data */ + compress_init(dinfo, InitCodeSize + 1); } @@ -316,17 +348,139 @@ start_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo) * In this module rows_supplied will always be 1. */ + +/* + * The LZW algorithm proper + */ + +METHODDEF(void) +put_LZW_pixel_rows (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo, + JDIMENSION rows_supplied) +{ + gif_dest_ptr dest = (gif_dest_ptr) dinfo; + register JSAMPROW ptr; + register JDIMENSION col; + code_int c; + register hash_int i; + register hash_int disp; + register hash_entry probe_value; + + ptr = dest->pub.buffer[0]; + for (col = cinfo->output_width; col > 0; col--) { + /* Accept and compress one 8-bit byte */ + c = (code_int) GETJSAMPLE(*ptr++); + + if (dest->first_byte) { /* need to initialize waiting_code */ + dest->waiting_code = c; + dest->first_byte = FALSE; + continue; + } + + /* Probe hash table to see if a symbol exists for + * waiting_code followed by c. + * If so, replace waiting_code by that symbol and continue. + */ + i = ((hash_int) c << (MAX_LZW_BITS-8)) + dest->waiting_code; + /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */ + if (i >= HSIZE) + i -= HSIZE; + + probe_value = HASH_ENTRY(dest->waiting_code, c); + + if (dest->hash_code[i] == 0) { + /* hit empty slot; desired symbol not in table */ + output(dest, dest->waiting_code); + if (dest->free_code < LZW_TABLE_SIZE) { + dest->hash_code[i] = dest->free_code++; /* add symbol to hashtable */ + dest->hash_value[i] = probe_value; + } else + clear_block(dest); + dest->waiting_code = c; + continue; + } + if (dest->hash_value[i] == probe_value) { + dest->waiting_code = dest->hash_code[i]; + continue; + } + + if (i == 0) /* secondary hash (after G. Knott) */ + disp = 1; + else + disp = HSIZE - i; + for (;;) { + i -= disp; + if (i < 0) + i += HSIZE; + if (dest->hash_code[i] == 0) { + /* hit empty slot; desired symbol not in table */ + output(dest, dest->waiting_code); + if (dest->free_code < LZW_TABLE_SIZE) { + dest->hash_code[i] = dest->free_code++; /* add symbol to hashtable */ + dest->hash_value[i] = probe_value; + } else + clear_block(dest); + dest->waiting_code = c; + break; + } + if (dest->hash_value[i] == probe_value) { + dest->waiting_code = dest->hash_code[i]; + break; + } + } + } +} + + +/* + * The pseudo-compression algorithm. + * + * In this version we simply output each pixel value as a separate symbol; + * thus, no compression occurs. In fact, there is expansion of one bit per + * pixel, because we use a symbol width one bit wider than the pixel width. + * + * GIF ordinarily uses variable-width symbols, and the decoder will expect + * to ratchet up the symbol width after a fixed number of symbols. + * To simplify the logic and keep the expansion penalty down, we emit a + * GIF Clear code to reset the decoder just before the width would ratchet up. + * Thus, all the symbols in the output file will have the same bit width. + * Note that emitting the Clear codes at the right times is a mere matter of + * counting output symbols and is in no way dependent on the LZW algorithm. + * + * With a small basic pixel width (low color count), Clear codes will be + * needed very frequently, causing the file to expand even more. So this + * simplistic approach wouldn't work too well on bilevel images, for example. + * But for output of JPEG conversions the pixel width will usually be 8 bits + * (129 to 256 colors), so the overhead added by Clear symbols is only about + * one symbol in every 256. + */ + METHODDEF(void) -put_pixel_rows (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo, - JDIMENSION rows_supplied) +put_raw_pixel_rows (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo, + JDIMENSION rows_supplied) { gif_dest_ptr dest = (gif_dest_ptr) dinfo; register JSAMPROW ptr; register JDIMENSION col; + code_int c; ptr = dest->pub.buffer[0]; for (col = cinfo->output_width; col > 0; col--) { - compress_pixel(dest, GETJSAMPLE(*ptr++)); + c = (code_int) GETJSAMPLE(*ptr++); + /* Accept and output one pixel value. + * The given value must be less than n_bits wide. + */ + + /* Output the given pixel value as a symbol. */ + output(dest, c); + /* Issue Clear codes often enough to keep the reader from ratcheting up + * its symbol size. + */ + if (dest->code_counter < dest->maxcode) { + dest->code_counter++; + } else { + output(dest, dest->ClearCode); + dest->code_counter = dest->ClearCode + 2; /* reset the counter */ + } } } @@ -340,7 +494,7 @@ finish_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo) { gif_dest_ptr dest = (gif_dest_ptr) dinfo; - /* Flush "compression" mechanism */ + /* Flush compression mechanism */ compress_term(dest); /* Write a zero-length data block to end the series */ putc(0, dest->pub.output_file); @@ -358,17 +512,15 @@ finish_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo) */ GLOBAL(djpeg_dest_ptr) -jinit_write_gif (j_decompress_ptr cinfo) +jinit_write_gif (j_decompress_ptr cinfo, boolean is_lzw) { gif_dest_ptr dest; /* Create module interface object, fill in method pointers */ - dest = (gif_dest_ptr) - (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, - SIZEOF(gif_dest_struct)); + dest = (gif_dest_ptr) (*cinfo->mem->alloc_small) + ((j_common_ptr) cinfo, JPOOL_IMAGE, SIZEOF(gif_dest_struct)); dest->cinfo = cinfo; /* make back link for subroutines */ dest->pub.start_output = start_output_gif; - dest->pub.put_pixel_rows = put_pixel_rows; dest->pub.finish_output = finish_output_gif; if (cinfo->out_color_space != JCS_GRAYSCALE && @@ -394,6 +546,20 @@ jinit_write_gif (j_decompress_ptr cinfo) ((j_common_ptr) cinfo, JPOOL_IMAGE, cinfo->output_width, (JDIMENSION) 1); dest->pub.buffer_height = 1; + if (is_lzw) { + dest->pub.put_pixel_rows = put_LZW_pixel_rows; + /* Allocate space for hash table */ + dest->hash_code = (code_int *) (*cinfo->mem->alloc_small) + ((j_common_ptr) cinfo, JPOOL_IMAGE, HSIZE * SIZEOF(code_int)); + dest->hash_value = (hash_entry FAR *) (*cinfo->mem->alloc_large) + ((j_common_ptr) cinfo, JPOOL_IMAGE, HSIZE * SIZEOF(hash_entry)); + } else { + dest->pub.put_pixel_rows = put_raw_pixel_rows; + /* Mark tables unused */ + dest->hash_code = NULL; + dest->hash_value = NULL; + } + return &dest->pub; } |