wrgif.c

   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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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)
 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 */