home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / fbm / src / flgifc.c < prev    next >
C/C++ Source or Header  |  1990-06-24  |  13KB  |  464 lines
  1. /*****************************************************************
  2.  * flgifc.c: FBM Release 1.0 25-Feb-90 Michael Mauldin
  3.  *
  4.  * Modifications to GIFENCODE are Copyright (C) 1989,1990 by
  5.  * Michael Mauldin.  Permission is granted to use this file in whole
  6.  * or in part for any purpose, educational, recreational or commercial,
  7.  * provided that this copyright notice is retained unchanged.
  8.  * This software is available to all free of charge by anonymous
  9.  * FTP and in the UUNET archives.
  10.  *
  11.  * CONTENTS
  12.  *    compress( init_bits, outfile, ReadValue )
  13.  *
  14.  * EDITLOG
  15.  *    LastEditDate = Mon Jun 25 00:09:49 1990 - Michael Mauldin
  16.  *    LastFileName = /usr2/mlm/src/misc/fbm/flgifc.c
  17.  *
  18.  * HISTORY
  19.  * 25-Jun-90  Michael Mauldin (mlm@cs.cmu.edu) Carnegie Mellon
  20.  *    Package for Release 1.0
  21.  *
  22.  * 07-Mar-89  Michael Mauldin (mlm) at Carnegie Mellon University
  23.  *    Beta release (version 0.9) mlm@cs.cmu.edu
  24.  *
  25.  * 21-Feb-89  Michael Mauldin (mlm) at Carnegie Mellon University
  26.  *    Removed two unused variables found by Lint.
  27.  *
  28.  * 19-Feb-89  Michael Mauldin (mlm) at Carnegie Mellon University
  29.  *    Adapted to FBM package.
  30.  *
  31.  * 13-Feb-89  David Rowley (mgardi@watdcsu.waterloo.edu)
  32.  *    GIF encoding modifications (sent by mail on 2/13/89)
  33.  *    original name: GIFENCODE.C - GIF Image compression interface
  34.  *
  35.  *    Based on: compress.c - File compression ala IEEE Computer, June 1984.
  36.  *
  37.  *    Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  38.  *    Jim McKie               (decvax!mcvax!jim)
  39.  *    Steve Davies            (decvax!vax135!petsd!peora!srd)
  40.  *    Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  41.  *    James A. Woods          (decvax!ihnp4!ames!jaw)
  42.  *    Joe Orost               (decvax!vax135!petsd!joe)
  43.  *
  44.  *****************************************************************/
  45.  
  46. /*
  47.  * General DEFINEs
  48.  */
  49. #define min(a,b)        ((a>b) ? b : a)
  50.  
  51. #define BITS    12
  52. #define MSDOS    1
  53.  
  54. #define HSIZE  5003            /* 80% occupancy */
  55.  
  56. /*
  57.  * Pointer to function returning an int
  58.  */
  59. typedef int (* ifunptr)();
  60.  
  61. /*
  62.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  63.  */
  64. typedef int             code_int;
  65.  
  66. #ifdef SIGNED_COMPARE_SLOW
  67. typedef unsigned long int count_int;
  68. typedef unsigned short int count_short;
  69. #else
  70. typedef long int          count_int;
  71. #endif
  72.  
  73. #ifdef NO_UCHAR
  74.  typedef char   char_type;
  75. #else
  76.  typedef        unsigned char   char_type;
  77. #endif /* UCHAR */
  78.  
  79. /*
  80.  *
  81.  * GIF Image compression - modified 'compress'
  82.  *
  83.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  84.  *
  85.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  86.  *              Jim McKie               (decvax!mcvax!jim)
  87.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  88.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  89.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  90.  *              Joe Orost               (decvax!vax135!petsd!joe)
  91.  *
  92.  */
  93. #include <stdio.h>
  94. #include <ctype.h>
  95. #include <signal.h>
  96.  
  97. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  98.  
  99. static int n_bits;                        /* number of bits/code */
  100. static int maxbits = BITS;                /* user settable max # bits/code */
  101. static code_int maxcode;                  /* maximum code, given n_bits */
  102. static code_int maxmaxcode = (code_int)1 << BITS; /* should NEVER generate this code */
  103. #ifdef COMPATIBLE               /* But wrong! */
  104. # define MAXCODE(n_bits)        ((code_int) 1 << (n_bits) - 1)
  105. #else
  106. # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
  107. #endif /* COMPATIBLE */
  108.  
  109. static count_int htab [HSIZE];
  110. static unsigned short codetab [HSIZE];
  111. #define HashTabOf(i)       htab[i]
  112. #define CodeTabOf(i)    codetab[i]
  113.  
  114. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  115.  
  116. /*
  117.  * To save much memory, we overlay the table used by compress() with those
  118.  * used by decompress().  The tab_prefix table is the same size and type
  119.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  120.  * get this from the beginning of htab.  The output stack uses the rest
  121.  * of htab, and contains characters.  There is plenty of room for any
  122.  * possible stack (stack used to be 8000 characters).
  123.  */
  124.  
  125. #define tab_prefixof(i) CodeTabOf(i)
  126. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  127. #define de_stack               ((char_type *)&tab_suffixof((code_int)1<<BITS))
  128.  
  129. static code_int free_ent = 0;                  /* first unused entry */
  130.  
  131. /*
  132.  * block compression parameters -- after all codes are used up,
  133.  * and compression rate changes, start over.
  134.  */
  135. static int clear_flg = 0;
  136.  
  137. static long int in_count = 1;            /* length of input */
  138. static long int out_count = 0;           /* # of codes output (for debugging) */
  139.  
  140. /*
  141.  * compress stdin to stdout
  142.  *
  143.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  144.  * prefix code / next character combination.  We do a variant of Knuth's
  145.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  146.  * secondary probe.  Here, the modular division first probe is gives way
  147.  * to a faster exclusive-or manipulation.  Also do block compression with
  148.  * an adaptive reset, whereby the code table is cleared when the compression
  149.  * ratio decreases, but after the table fills.  The variable-length output
  150.  * codes are re-sized at this point, and a special CLEAR code is generated
  151.  * for the decompressor.  Late addition:  construct the table according to
  152.  * file size for noticeable speed improvement on small files.  Please direct
  153.  * questions about this implementation to ames!jaw.
  154.  */
  155.  
  156. static int g_init_bits;
  157. static FILE *g_outfile;
  158.  
  159. static int ClearCode;
  160. static int EOFCode;
  161.  
  162. static    output(), cl_block(), cl_hash(), writeerr(), char_init(), char_out(),
  163.     flush_char();
  164.  
  165. #ifndef lint
  166. static char *fbmid =
  167. "$FBM flgifc.c <1.0> 25-Jun-90  (C) 1989,1990 by Michael Mauldin, source \
  168. code available free from MLM@CS.CMU.EDU and from UUNET archives$";
  169. #endif
  170.  
  171. compress( init_bits, outfile, ReadValue )
  172. int init_bits;
  173. FILE *outfile;
  174. ifunptr ReadValue;
  175. {
  176.     register long fcode;
  177.     register code_int i = 0;
  178.     register int c;
  179.     register code_int ent;
  180.     register code_int disp;
  181.     register code_int hsize_reg;
  182.     register int hshift;
  183.  
  184.     /*
  185.      * Set up the globals:  g_init_bits - initial number of bits
  186.      *                      g_outfile   - pointer to output file
  187.      */
  188.     g_init_bits = init_bits;
  189.     g_outfile = outfile;
  190.  
  191.     /*
  192.      * Set up the necessary values
  193.      */
  194.     out_count = 0;
  195.     clear_flg = 0;
  196.     in_count = 1;
  197.     maxcode = MAXCODE(n_bits = g_init_bits);
  198.  
  199.     ClearCode = (1 << (init_bits - 1));
  200.     EOFCode = ClearCode + 1;
  201.     free_ent = ClearCode + 2;
  202.  
  203.     char_init();
  204.     
  205.     ent = GIFNextPixel( ReadValue );
  206.  
  207.     hshift = 0;
  208.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  209.         hshift++;
  210.     hshift = 8 - hshift;                /* set hash code range bound */
  211.  
  212.     hsize_reg = hsize;
  213.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  214.  
  215.     output( (code_int)ClearCode );
  216.     
  217. #ifdef SIGNED_COMPARE_SLOW
  218.     while ( (c = GIFNextPixel( ReadValue )) != (unsigned) EOF ) {
  219. #else
  220.     while ( (c = GIFNextPixel( ReadValue )) != EOF ) {
  221. #endif
  222.  
  223.         in_count++;
  224.  
  225.         fcode = (long) (((long) c << maxbits) + ent);
  226.         i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  227.  
  228.         if ( HashTabOf (i) == fcode ) {
  229.             ent = CodeTabOf (i);
  230.             continue;
  231.         } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  232.             goto nomatch;
  233.         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  234.         if ( i == 0 )
  235.             disp = 1;
  236. probe:
  237.         if ( (i -= disp) < 0 )
  238.             i += hsize_reg;
  239.  
  240.         if ( HashTabOf (i) == fcode ) {
  241.             ent = CodeTabOf (i);
  242.             continue;
  243.         }
  244.         if ( (long)HashTabOf (i) > 0 ) 
  245.             goto probe;
  246. nomatch:
  247.         output ( (code_int) ent );
  248.         out_count++;
  249.         ent = c;
  250. #ifdef SIGNED_COMPARE_SLOW
  251.         if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  252. #else
  253.         if ( free_ent < maxmaxcode ) {
  254. #endif
  255.             CodeTabOf (i) = free_ent++; /* code -> hashtable */
  256.             HashTabOf (i) = fcode;
  257.         } else
  258.         cl_block();
  259.     }
  260.     /*
  261.      * Put out the final code.
  262.      */
  263.     output( (code_int)ent );
  264.     out_count++;
  265.     output( (code_int) EOFCode );
  266.  
  267.     return;
  268. }
  269.  
  270. /*****************************************************************
  271.  * TAG( output )
  272.  *
  273.  * Output the given code.
  274.  * Inputs:
  275.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  276.  *              that n_bits =< (long)wordsize - 1.
  277.  * Outputs:
  278.  *      Outputs code to the file.
  279.  * Assumptions:
  280.  *      Chars are 8 bits long.
  281.  * Algorithm:
  282.  *      Maintain a BITS character long buffer (so that 8 codes will
  283.  * fit in it exactly).  Use the VAX insv instruction to insert each
  284.  * code in turn.  When the buffer fills up empty it and start over.
  285.  */
  286.  
  287. static unsigned long cur_accum = 0;
  288. static int  cur_bits = 0;
  289.  
  290. static
  291. unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  292.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  293.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  294.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  295.  
  296. static
  297. output( code )
  298. code_int  code;
  299. {
  300.     cur_accum &= masks[ cur_bits ];
  301.  
  302.     if( cur_bits > 0 )
  303.         cur_accum |= ((long)code << cur_bits);
  304.     else
  305.         cur_accum = code;
  306.     
  307.     cur_bits += n_bits;
  308.  
  309.     while( cur_bits >= 8 ) {
  310.         char_out( (unsigned int)(cur_accum & 0xff) );
  311.     cur_accum >>= 8;
  312.     cur_bits -= 8;
  313.     }
  314.  
  315.     /*
  316.      * If the next entry is going to be too big for the code size,
  317.      * then increase it, if possible.
  318.      */
  319.    if ( free_ent > maxcode || clear_flg ) {
  320.  
  321.             if( clear_flg ) {
  322.         
  323.                 maxcode = MAXCODE (n_bits = g_init_bits);
  324.                 clear_flg = 0;
  325.         
  326.             } else {
  327.         
  328.                 n_bits++;
  329.                 if ( n_bits == maxbits )
  330.                     maxcode = maxmaxcode;
  331.                 else
  332.                     maxcode = MAXCODE(n_bits);
  333.             }
  334.         }
  335.     
  336.     if( code == EOFCode ) {
  337.         /*
  338.          * At EOF, write the rest of the buffer.
  339.          */
  340.         while( cur_bits > 0 ) {
  341.                 char_out( (unsigned int)(cur_accum & 0xff) );
  342.             cur_accum >>= 8;
  343.             cur_bits -= 8;
  344.         }
  345.  
  346.     flush_char();
  347.     
  348.         fflush( g_outfile );
  349.  
  350.     if( ferror( g_outfile ) )
  351.                 writeerr();
  352.     }
  353. }
  354.  
  355. /*
  356.  * Clear out the hash table
  357.  */
  358. static
  359. cl_block ()             /* table clear for block compress */
  360. {
  361.  
  362.         cl_hash ( (count_int) hsize );
  363.         free_ent = ClearCode + 2;
  364.         clear_flg = 1;
  365.  
  366.         output( (code_int)ClearCode );
  367. }
  368.  
  369. static
  370. cl_hash(hsize)          /* reset code table */
  371. register count_int hsize;
  372. {
  373.  
  374.         register count_int *htab_p = htab+hsize;
  375.  
  376.         register long i;
  377.         register long m1 = -1;
  378.  
  379.         i = hsize - 16;
  380.         do {                            /* might use Sys V memset(3) here */
  381.                 *(htab_p-16) = m1;
  382.                 *(htab_p-15) = m1;
  383.                 *(htab_p-14) = m1;
  384.                 *(htab_p-13) = m1;
  385.                 *(htab_p-12) = m1;
  386.                 *(htab_p-11) = m1;
  387.                 *(htab_p-10) = m1;
  388.                 *(htab_p-9) = m1;
  389.                 *(htab_p-8) = m1;
  390.                 *(htab_p-7) = m1;
  391.                 *(htab_p-6) = m1;
  392.                 *(htab_p-5) = m1;
  393.                 *(htab_p-4) = m1;
  394.                 *(htab_p-3) = m1;
  395.                 *(htab_p-2) = m1;
  396.                 *(htab_p-1) = m1;
  397.                 htab_p -= 16;
  398.         } while ((i -= 16) >= 0);
  399.  
  400.     for ( i += 16; i > 0; i-- )
  401.                 *--htab_p = m1;
  402. }
  403.  
  404. static
  405. writeerr()
  406. {
  407.     printf( "error writing output file\n" );
  408.     exit(1);
  409. }
  410.  
  411. /******************************************************************************
  412.  *
  413.  * GIF Specific routines
  414.  *
  415.  ******************************************************************************/
  416.  
  417. /*
  418.  * Number of characters so far in this 'packet'
  419.  */
  420. static int a_count;
  421.  
  422. /*
  423.  * Set up the 'byte output' routine
  424.  */
  425. static
  426. char_init()
  427. {
  428.     a_count = 0;
  429. }
  430.  
  431. /*
  432.  * Define the storage for the packet accumulator
  433.  */
  434. static char accum[ 256 ];
  435.  
  436. /*
  437.  * Add a character to the end of the current packet, and if it is 254
  438.  * characters, flush the packet to disk.
  439.  */
  440. static
  441. char_out( c )
  442. int c;
  443. {
  444.     accum[ a_count++ ] = c;
  445.     if( a_count >= 254 ) 
  446.         flush_char();
  447. }
  448.  
  449. /*
  450.  * Flush the packet to disk, and reset the accumulator
  451.  */
  452. static
  453. flush_char()
  454. {
  455.     if( a_count > 0 ) {
  456.         fputc( a_count, g_outfile );
  457.         fwrite( accum, 1, a_count, g_outfile );
  458.         a_count = 0;
  459.     }
  460. }    
  461.  
  462. /* The End */
  463.  
  464.