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