home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / compresn / jpegv3sr / jwrgif.c < prev    next >
C/C++ Source or Header  |  1992-03-04  |  14KB  |  482 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.   (void) JFWRITE(dcinfo->output_file, "GIF87a", 6);
  322.   /* Write the Logical Screen Descriptor */
  323.   put_word((UINT16) dcinfo->image_width);
  324.   put_word((UINT16) dcinfo->image_height);
  325.   FlagByte = 0x80;        /* Yes, there is a global color table */
  326.   FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */
  327.   FlagByte |= (BitsPerPixel-1);    /* size of global color table */
  328.   putc(FlagByte, dcinfo->output_file);
  329.   putc(0, dcinfo->output_file);    /* Background color index */
  330.   putc(0, dcinfo->output_file);    /* Reserved in GIF87 (aspect ratio in GIF89) */
  331.   /* Write the Global Color Map */
  332.   /* If the color map is more than 8 bits precision, */
  333.   /* we reduce it to 8 bits by shifting */
  334.   for (i=0; i < ColorMapSize; i++) {
  335.     if (i < num_colors) {
  336.       if (colormap != NULL) {
  337.     if (dcinfo->out_color_space == CS_RGB) {
  338.       /* Normal case: RGB color map */
  339.       putc(GETJSAMPLE(colormap[0][i]) >> cshift, dcinfo->output_file);
  340.       putc(GETJSAMPLE(colormap[1][i]) >> cshift, dcinfo->output_file);
  341.       putc(GETJSAMPLE(colormap[2][i]) >> cshift, dcinfo->output_file);
  342.     } else {
  343.       /* Grayscale "color map": possible if quantizing grayscale image */
  344.       put_3bytes(GETJSAMPLE(colormap[0][i]) >> cshift);
  345.     }
  346.       } else {
  347.     /* Create a gray-scale map of num_colors values, range 0..255 */
  348.     put_3bytes((i * 255 + (num_colors-1)/2) / (num_colors-1));
  349.       }
  350.     } else {
  351.       /* fill out the map to a power of 2 */
  352.       put_3bytes(0);
  353.     }
  354.   }
  355.   /* Write image separator and Image Descriptor */
  356.   putc(',', dcinfo->output_file); /* separator */
  357.   put_word((UINT16) 0);        /* left/top offset */
  358.   put_word((UINT16) 0);
  359.   put_word((UINT16) dcinfo->image_width); /* image size */
  360.   put_word((UINT16) dcinfo->image_height);
  361.   /* flag byte: not interlaced, no local color map */
  362.   putc(0x00, dcinfo->output_file);
  363.   /* Write Initial Code Size byte */
  364.   putc(InitCodeSize, dcinfo->output_file);
  365.  
  366.   /* Initialize for LZW compression of image data */
  367.   compress_init(InitCodeSize+1);
  368. }
  369.  
  370.  
  371.  
  372. /*
  373.  * Initialize for GIF output.
  374.  */
  375.  
  376. METHODDEF void
  377. output_init (decompress_info_ptr cinfo)
  378. {
  379.   dcinfo = cinfo;        /* save for use by local routines */
  380.   if (cinfo->final_out_comps != 1) /* safety check */
  381.     ERREXIT(cinfo->emethods, "GIF output got confused");
  382.   /* Allocate space for hash table */
  383.   hash_code = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  384.                 (HSIZE * SIZEOF(code_int));
  385.   hash_prefix = (code_int FAR *) (*cinfo->emethods->alloc_medium)
  386.                 (HSIZE * SIZEOF(code_int));
  387.   hash_suffix = (UINT8 FAR *) (*cinfo->emethods->alloc_medium)
  388.                 (HSIZE * SIZEOF(UINT8));
  389.   /*
  390.    * If we aren't quantizing, put_color_map won't be called,
  391.    * so emit the header now.  This only happens with gray scale output.
  392.    * (If we are quantizing, wait for the color map to be provided.)
  393.    */
  394.   if (! cinfo->quantize_colors)
  395.     emit_header(256, (JSAMPARRAY) NULL);
  396. }
  397.  
  398.  
  399. /*
  400.  * Write the color map.
  401.  */
  402.  
  403. METHODDEF void
  404. put_color_map (decompress_info_ptr cinfo, int num_colors, JSAMPARRAY colormap)
  405. {
  406.   emit_header(num_colors, colormap);
  407. }
  408.  
  409.  
  410. /*
  411.  * Write some pixel data.
  412.  */
  413.  
  414. METHODDEF void
  415. put_pixel_rows (decompress_info_ptr cinfo, int num_rows,
  416.         JSAMPIMAGE pixel_data)
  417. {
  418.   register JSAMPROW ptr;
  419.   register long col;
  420.   register long width = cinfo->image_width;
  421.   register int row;
  422.   
  423.   for (row = 0; row < num_rows; row++) {
  424.     ptr = pixel_data[0][row];
  425.     for (col = width; col > 0; col--) {
  426.       compress_byte(GETJSAMPLE(*ptr));
  427.       ptr++;
  428.     }
  429.   }
  430. }
  431.  
  432.  
  433. /*
  434.  * Finish up at the end of the file.
  435.  */
  436.  
  437. METHODDEF void
  438. output_term (decompress_info_ptr cinfo)
  439. {
  440.   /* Flush LZW mechanism */
  441.   compress_term();
  442.   /* Write a zero-length data block to end the series */
  443.   putc(0, cinfo->output_file);
  444.   /* Write the GIF terminator mark */
  445.   putc(';', cinfo->output_file);
  446.   /* Make sure we wrote the output file OK */
  447.   fflush(cinfo->output_file);
  448.   if (ferror(cinfo->output_file))
  449.     ERREXIT(cinfo->emethods, "Output file write error");
  450.   /* Free space */
  451.   /* no work (we let free_all release the workspace) */
  452. }
  453.  
  454.  
  455. /*
  456.  * The method selection routine for GIF format output.
  457.  * This should be called from d_ui_method_selection if GIF output is wanted.
  458.  */
  459.  
  460. GLOBAL void
  461. jselwgif (decompress_info_ptr cinfo)
  462. {
  463.   cinfo->methods->output_init = output_init;
  464.   cinfo->methods->put_color_map = put_color_map;
  465.   cinfo->methods->put_pixel_rows = put_pixel_rows;
  466.   cinfo->methods->output_term = output_term;
  467.  
  468.   if (cinfo->out_color_space != CS_GRAYSCALE &&
  469.       cinfo->out_color_space != CS_RGB)
  470.     ERREXIT(cinfo->emethods, "GIF output must be grayscale or RGB");
  471.  
  472.   /* Force quantization if color or if > 8 bits input */
  473.   if (cinfo->out_color_space == CS_RGB || cinfo->data_precision > 8) {
  474.     /* Force quantization to at most 256 colors */
  475.     cinfo->quantize_colors = TRUE;
  476.     if (cinfo->desired_number_of_colors > 256)
  477.       cinfo->desired_number_of_colors = 256;
  478.   }
  479. }
  480.  
  481. #endif /* GIF_SUPPORTED */
  482.