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