home *** CD-ROM | disk | FTP | other *** search
/ Amiga ACS 1998 #6 / amigaacscoverdisc1998-061998.iso / games / descent / source / pslib / lzw.c < prev    next >
Text File  |  1998-06-08  |  9KB  |  313 lines
  1. /*
  2. THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
  3. SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
  4. END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
  5. ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
  6. IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
  7. SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
  8. FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  9. CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10. AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.  
  11. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12. */
  13. /*
  14.  * $Source: f:/miner/source/pslib/rcs/lzw.c $
  15.  * $Revision: 1.8 $
  16.  * $Author: john $
  17.  * $Date: 1994/02/01 13:23:51 $
  18.  *
  19.  * Based on lzw15v.c from Data Compression book.
  20.  * CompressFile and Expandfile have been replaced by cfread and cfwrite.
  21.  *
  22.  * $Log: lzw.c $
  23.  * Revision 1.8  1994/02/01  13:23:51  john
  24.  * *** empty log message ***
  25.  * 
  26.  * Revision 1.7  1993/10/22  17:50:43  yuan
  27.  * Fixed the hard to track down bug
  28.  * 
  29.  * Revision 1.6  1993/10/18  18:00:13  yuan
  30.  * Fixed memory alloc errors.
  31.  * 
  32.  * Revision 1.5  1993/09/21  17:22:24  yuan
  33.  * *** empty log message ***
  34.  * 
  35.  * Revision 1.4  1993/09/21  17:16:25  yuan
  36.  * cleaning up
  37.  * 
  38.  * Revision 1.3  1993/09/14  13:11:57  yuan
  39.  * cfread and cfwrite have been changed into lzw_expand and lzw_compress.
  40.  * the new cfread and cfwrite functions are now in library.c
  41.  * lzw_compress returns the compressed buffer and a parameter *size.
  42.  * 
  43.  * Revision 1.2  1993/09/09  17:45:56  yuan
  44.  * tab added to ERROR messages
  45.  * 
  46.  * Revision 1.1  1993/09/08  16:15:03  yuan
  47.  * Initial revision
  48.  * 
  49.  * Revision 1.3  1993/07/24  19:05:22  yuan
  50.  * *** empty log message ***
  51.  * 
  52.  * Revision 1.2  1993/07/22  11:27:29  yuan
  53.  * No change
  54.  * 
  55.  * Revision 1.1  1993/07/21  15:28:48  matt
  56.  * Initial revision
  57.  * 
  58.  *
  59.  */
  60.  
  61. #pragma off (unreferenced)
  62. static char rcsid[] = "$Id: lzw.c 1.8 1994/02/01 13:23:51 john Exp $";
  63. #pragma on (unreferenced)
  64.  
  65. #include <stdio.h>
  66. #include <stdlib.h>
  67. #include <string.h>
  68.  
  69. #include "library.h"
  70. #include "mem.h"
  71.  
  72. //#define DEBUG_ON 1
  73. //#include "error.h"
  74.  
  75. #define BITS                       15
  76. #define MAX_CODE                   ( ( 1 << BITS ) - 1 )
  77. #define TABLE_SIZE                 35023L
  78. #define END_OF_STREAM              256
  79. #define BUMP_CODE                  257
  80. #define FLUSH_CODE                 258
  81. #define FIRST_CODE                 259
  82. #define UNUSED                     -1
  83.  
  84. unsigned int find_child_node( int parent_code, int child_character );
  85. unsigned int decode_string( unsigned int offset, unsigned int code );
  86.  
  87. char *CompressionName = "LZW 15 Bit Variable Rate Encoder";
  88. char *Usage           = "in-file out-file";
  89.  
  90. typedef struct {
  91.     int code_value;
  92.     int parent_code;
  93.     char character;
  94. } DICTIONARY;
  95.  
  96. DICTIONARY * dict;
  97.  
  98. char * decode_stack;
  99. unsigned int next_code;
  100. int current_code_bits;
  101. unsigned int next_bump_code;
  102.  
  103. void InitializeDictionary()
  104. {
  105.     unsigned int i;
  106.  
  107.     for ( i = 0 ; i < TABLE_SIZE ; i++ )
  108.         dict[i].code_value = UNUSED;
  109.  
  110.     next_code = FIRST_CODE;
  111.     current_code_bits = 9;
  112.     next_bump_code = 511;
  113. }
  114.  
  115. void InitializeStorage()
  116. {
  117.     //MALLOC( dict, DICTIONARY, TABLE_SIZE );//won't compile, hack below -KRB
  118.     //MALLOC( decode_stack, char, TABLE_SIZE );
  119.     dict = (DICTIONARY *)malloc(TABLE_SIZE*sizeof(DICTIONARY));
  120.     decode_stack = (char *)malloc(TABLE_SIZE*sizeof(char));
  121. }
  122.  
  123.  
  124. void FreeStorage()
  125. {
  126.     free(dict);
  127.     free(decode_stack);
  128. }
  129.  
  130. ubyte *lzw_compress( ubyte *inputbuf, ubyte *outputbuf, int input_size, int *output_size ) {
  131.     BIT_BUF *output;
  132.     int character;
  133.     int string_code;
  134.     unsigned int index;
  135.     int i;
  136.  
  137.     output = OpenOutputBitBuf();
  138.     if ( outputbuf == NULL ) {
  139.         //MALLOC( output->buf, ubyte, input_size); //Another compile hack -KRB
  140.         output->buf = (ubyte *)malloc(input_size*sizeof(ubyte));
  141.         if (output->buf == NULL) {
  142.             printf("    ERROR : OpenOutputBitBuf - Not enough memory to read buffer.\n");
  143.             exit(1);
  144.         }
  145.         outputbuf = output->buf;
  146.     } else output->buf = outputbuf;
  147.  
  148.     InitializeStorage();
  149.     InitializeDictionary();
  150.     string_code = ( *inputbuf++ );
  151.     for ( i=0 ; i<input_size ; i++ ) {
  152.  
  153.         if (output->current_byte+4 >= input_size) {
  154.             CloseOutputBitBuf( output );
  155.             FreeStorage();
  156.             free( outputbuf );
  157.             *output_size = -1;
  158.             return NULL;
  159.         }
  160.         character = ( *inputbuf++ );
  161.         index = find_child_node( string_code, character );
  162.         if ( dict[ index ].code_value != - 1 )
  163.             string_code = dict[ index ].code_value;
  164.         else {
  165.             dict[ index ].code_value = next_code++;
  166.             dict[ index ].parent_code = string_code;
  167.             dict[ index ].character = (char) character;
  168.             OutputBits( output,
  169.                         (unsigned long) string_code, current_code_bits );
  170.             string_code = character;
  171.             if ( next_code > MAX_CODE ) {
  172.                 OutputBits( output,
  173.                             (unsigned long) FLUSH_CODE, current_code_bits );
  174.                 InitializeDictionary();
  175.             } else if ( next_code > next_bump_code ) {
  176.                 OutputBits( output,
  177.                             (unsigned long) BUMP_CODE, current_code_bits );
  178.                 current_code_bits++;
  179.                 next_bump_code <<= 1;
  180.                 next_bump_code |= 1;
  181.             }
  182.         }
  183.     }
  184.     OutputBits( output, (unsigned long) string_code, current_code_bits );
  185.     OutputBits( output, (unsigned long) END_OF_STREAM, current_code_bits);
  186.     *output_size = output->current_byte+1;
  187.     //printf("Outputsize %d\n", *output_size);
  188.     CloseOutputBitBuf( output );
  189.     FreeStorage();
  190.  
  191.     //mem_validate_heap();
  192.  
  193.  
  194.     return outputbuf;
  195. }
  196.  
  197.  
  198. ubyte *lzw_expand( ubyte *inputbuf, ubyte *outputbuf, int length ) {
  199.     BIT_BUF *input;
  200.     unsigned int new_code;
  201.     unsigned int old_code;
  202.     int character;
  203.     unsigned int count;
  204.     int counter;
  205.  
  206.     //printf("Input Size %d\n", length);
  207.  
  208.  
  209.     input = OpenInputBitBuf( inputbuf );
  210.     if ( outputbuf == NULL )
  211.         //MALLOC(outputbuf, ubyte, length);//Another hack for compiling -KRB
  212.         outputbuf = (ubyte *)malloc(length*sizeof(ubyte));
  213.     InitializeStorage();
  214.     counter = 0;
  215.     for ( ; ; ) {
  216.  
  217.         //mem_validate_heap();
  218.  
  219.         InitializeDictionary();
  220.         old_code = (unsigned int) InputBits( input, current_code_bits );
  221.         if ( old_code == END_OF_STREAM ) {
  222.             CloseInputBitBuf( input );
  223.             return outputbuf;
  224.         }
  225.         character = old_code;
  226.  
  227.         if (counter<length) {
  228.             outputbuf[counter++] = ( ubyte ) old_code;
  229.         } else {
  230.             printf( "ERROR:Tried to write %d\n", old_code );
  231.             exit(1);
  232.         }
  233.  
  234.         for ( ; ; ) {
  235.  
  236.             //mem_validate_heap();
  237.  
  238.             new_code = (unsigned int) InputBits( input, current_code_bits );
  239.             if ( new_code == END_OF_STREAM ) {
  240.                 //printf("\nEND OF STREAM at %d bytes\n", counter);
  241.                 CloseInputBitBuf( input );
  242.                 FreeStorage();
  243.                 return outputbuf;
  244.             }
  245.             if ( new_code == FLUSH_CODE )
  246.                 break;
  247.             if ( new_code == BUMP_CODE ) {
  248.                 current_code_bits++;
  249.                 continue;
  250.             }
  251.             if ( new_code >= next_code ) {
  252.                 decode_stack[ 0 ] = (char) character;
  253.                 count = decode_string( 1, old_code );
  254.             }
  255.             else    {
  256.                 count = decode_string( 0, new_code );
  257.             }
  258.             character = decode_stack[ count - 1 ];
  259.             while ( count > 0 ) {
  260.                 // This lets the case counter==length pass through.
  261.                 // This is a hack.
  262.                 if (counter<length) {
  263.                     outputbuf[counter++] = ( ubyte ) decode_stack[ --count ];
  264.                 } else if (counter>length) {
  265.                     printf( "ERROR:Tried to write %d\n", decode_stack[ --count ] );
  266.                     exit(1);
  267.                 } else
  268.                     count--;
  269.             }
  270.             dict[ next_code ].parent_code = old_code;
  271.             dict[ next_code ].character = (char) character;
  272.             next_code++;
  273.             old_code = new_code;
  274.         }
  275.     }
  276. }
  277.  
  278.  
  279. unsigned int find_child_node( int parent_code, int child_character ) {
  280.     unsigned int index;
  281.     int offset;
  282.  
  283.     index = ( child_character << ( BITS - 8 ) ) ^ parent_code;
  284.     if ( index == 0 )
  285.         offset = 1;
  286.     else
  287.         offset = TABLE_SIZE - index;
  288.     for ( ; ; ) {
  289.         if ( dict[ index ].code_value == UNUSED )
  290.             return( (unsigned int) index );
  291.         if ( dict[ index ].parent_code == parent_code &&
  292.              dict[ index ].character == (char) child_character )
  293.             return( index );
  294.         if ( (int) index >= offset )
  295.             index -= offset;
  296.         else
  297.             index += TABLE_SIZE - offset;
  298.     }
  299. }
  300.  
  301.  
  302. unsigned int decode_string( unsigned int count, unsigned int code ) {
  303.     while ( code > 255 ) {
  304.         decode_stack[ count++ ] = dict[ code ].character;
  305.         code = dict[ code ].parent_code;
  306.     }
  307.     decode_stack[ count++ ] = (char) code;
  308.     return( count );
  309. }
  310.  
  311.  
  312. 
  313.