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