home *** CD-ROM | disk | FTP | other *** search
/ Power Utilities / Power Utilities.iso / utility / pro200 / expander.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-15  |  7.5 KB  |  289 lines
  1. /*----------------------------------------------------------------------*/
  2. /* Copyright (c) 1987                            */
  3. /* by CompuServe Inc., Columbus, Ohio.  All Rights Reserved        */
  4. /* EXPANDER.C can be copied and distributed freely for any        */
  5. /* non-commercial purposes. EXPANDER.C can only be incorporated        */
  6. /* into commercial software with the permission of CompuServe Inc.    */
  7. /*----------------------------------------------------------------------*/
  8.  
  9. /*
  10.  * ABSTRACT:
  11.  *    The compression algorithm builds a string translation table that maps
  12.  *    substrings from the input string into fixed-length codes.  These codes
  13.  *    are used by the expansion algorithm to rebuild the compressor's table
  14.  *    and reconstruct the original data stream.  In it's simplest form, the
  15.  *    algorithm can be stated as:
  16.  *
  17.  *        "if <w>k is in the table, then <w> is in the table"
  18.  *
  19.  *    <w> is a code which represents a string in the table.  When a new
  20.  *    character k is read in, the table is searched for <w>k.  If this
  21.  *    combination is found, <w> is set to the code for that combination
  22.  *    and the next character is read in.  Otherwise, this combination is
  23.  *    added to the table, the code <w> is written to the output stream and
  24.  *    <w> is set to k.
  25.  *
  26.  *    The expansion algorithm builds an identical table by parsing each
  27.  *    received code into a prefix string and suffix character.  The suffix
  28.  *    character is pushed onto the stack and the prefix string translated
  29.  *    again until it is a single character.  This completes the expansion.
  30.  *    The expanded code is then output by popping the stack and a new entry
  31.  *    is made in the table.
  32.  *
  33.  *    The algorithm used here has one additional feature.  The output codes
  34.  *    are variable length.  They start at a specified number of bits.  Once
  35.  *    the number of codes exceeds the current code size, the number of bits
  36.  *    in the code is incremented.  When the table is completely full, a
  37.  *    clear code is transmitted for the expander and the table is reset.
  38.  *    This program uses a maximum code size of 12 bits for a total of 4096
  39.  *    codes.
  40.  *
  41.  *    The expander realizes that the code size is changing when it's table
  42.  *    size reaches the maximum for the current code size.  At this point,
  43.  *    the code size in increased.  Remember that the expander's table is
  44.  *    identical to the compressor's table at any point in the original data
  45.  *    stream.
  46.  *
  47.  *    The compressed data stream is structured as follows:
  48.  *        first byte denoting the minimum code size
  49.  *        one or more counted byte strings. The first byte contains the
  50.  *        length of the string. A null string denotes "end of data"
  51.  *
  52.  *    This format permits a compressed data stream to be embedded within a
  53.  *    non-compressed context.
  54.  *
  55.  * AUTHOR: Steve Wilhite
  56.  *
  57.  * REVISION HISTORY:
  58.  *
  59.  */
  60.  
  61. #include <malloc.h>
  62. #include <setjmp.h>
  63.  
  64. #include "expander.h"
  65.  
  66. /* Function prototypes: */
  67.  
  68. void init_table( short    min_code_size );
  69.  
  70. short read_code(void);
  71.  
  72. #define null_ptr    0
  73. #define largest_code    4095
  74.  
  75. jmp_buf recover;
  76.  
  77. struct code_entry
  78.     {
  79.     short prefix;            /* prefix code */
  80.     char suffix;            /* suffix character */
  81.     char stack;
  82.     };
  83.  
  84. static short code_size;
  85. static short clear_code;
  86. static short eof_code;
  87. static short first_free;
  88. static short bit_offset;
  89. static short byte_offset, bits_left;
  90. static short max_code;
  91. static short free_code;
  92. static short old_code;
  93. static short input_code;
  94. static short code;
  95. static short suffix_char;
  96. static short final_char;
  97. static short bytes_unread;
  98. static unsigned char code_buffer[64];
  99. static struct code_entry *code_table;
  100. static short (*get_byte)(void);
  101. static short (*put_byte)(short);
  102.  
  103. static short mask[12] =
  104.     {0x001, 0x003, 0x007, 0x00F,
  105.      0x01F, 0x03F, 0x07F, 0x0FF,
  106.      0x1FF, 0x3FF, 0x7FF, 0xFFF};
  107.  
  108.  
  109. void init_table( short    min_code_size )
  110.     {
  111.     code_size = min_code_size + 1;
  112.     clear_code = 1 << min_code_size;
  113.     eof_code = clear_code + 1;
  114.     first_free = clear_code + 2;
  115.     free_code = first_free;
  116.     max_code = 1 << code_size;
  117.     }
  118. /*$page*/
  119.  
  120. short read_code(void)
  121.     {
  122.     short
  123.     bytes_to_move,
  124.     i,
  125.     ch;
  126.     long
  127.     temp;
  128.  
  129.     byte_offset = bit_offset >> 3;
  130.     bits_left = bit_offset & 7;
  131.  
  132.     if (byte_offset >= 61)
  133.     {
  134.     bytes_to_move = 64 - byte_offset;
  135.  
  136.     for (i = 0; i < bytes_to_move; i++)
  137.         code_buffer[i] = code_buffer[byte_offset + i];
  138.  
  139.     while (i < 64)
  140.         {
  141.         if (bytes_unread == 0)
  142.         {
  143.         /* Get the length of the next record. A zero-length record
  144.          * denotes "end of data".
  145.          */
  146.  
  147.         bytes_unread = (*get_byte)();
  148.  
  149.         if (bytes_unread < 1)
  150.             if (bytes_unread == 0)    /* end of data */
  151.             break;
  152.             else
  153.             longjmp(recover, bytes_unread);
  154.         }
  155.  
  156.         ch = (*get_byte)();
  157.  
  158.         if (ch < 0)
  159.         longjmp(recover, ch);
  160.  
  161.         code_buffer[i++] = (unsigned char)(ch);
  162.         bytes_unread--;
  163.         }
  164.  
  165.     bit_offset = bits_left;
  166.     byte_offset = 0;
  167.     }
  168.  
  169.     bit_offset += code_size;
  170.     temp = (long) code_buffer[byte_offset]
  171.     | (long) code_buffer[byte_offset + 1] << 8
  172.     | (long) code_buffer[byte_offset + 2] << 16;
  173.  
  174.     if (bits_left > 0)
  175.     temp >>= (long) bits_left;
  176.  
  177.     return (short)(temp) & mask[code_size - 1];
  178.     }
  179. /*$page*/
  180.  
  181. short Expand_Data(
  182.           short (*get_byte_routine)(void),
  183.           short (*put_byte_routine)(short)
  184.          )
  185. /*
  186.  * Function:
  187.  *    Decompress a LZW compressed data stream.
  188.  *
  189.  * Inputs:
  190.  *    get_byte_routine - address of the caller's "get_byte" routine.
  191.  *    put_byte_routine - address of the caller's "put_byte" routine.
  192.  *
  193.  * Returns:
  194.  *    0    OK
  195.  *    -1    expected end-of-file
  196.  *    -2    cannot allocate memory
  197.  *    -3    bad "min_code_size"
  198.  *    < -3    error status from the get_byte or put_byte routine
  199.  */
  200.     {
  201.     short sp;                /* stack ptr */
  202.     short status;
  203.     short min_code_size;
  204.  
  205.     get_byte = get_byte_routine;
  206.     put_byte = put_byte_routine;
  207.  
  208.     code_table = (struct code_entry *)
  209.     malloc(sizeof(struct code_entry)*(largest_code + 1));
  210.  
  211.     if (code_table == null_ptr)
  212.     return -2;
  213.  
  214.     status = setjmp(recover);
  215.  
  216.     if (status != 0)
  217.     {
  218.     free((char *) code_table);
  219.     return status;
  220.     }
  221.  
  222.     /* Get the minimum code size (2 to 9) */
  223.  
  224.     min_code_size = (*get_byte)();
  225.  
  226.     if (min_code_size < 0)
  227.     longjmp(recover, min_code_size);
  228.     else if (min_code_size < 2 || min_code_size > 9)
  229.     longjmp(recover, -3);
  230.  
  231.     init_table(min_code_size);
  232.     sp = 0;
  233.     bit_offset = 64*8;            /* force "read_code" to start a new */
  234.     bytes_unread = 0;            /* record */
  235.  
  236.     while ((code = read_code()) != eof_code)
  237.     {
  238.     if (code == clear_code)
  239.         {
  240.         init_table(min_code_size);
  241.         code = read_code();
  242.         old_code = code;
  243.         suffix_char = code;
  244.         final_char = code;
  245.         if ((status = (*put_byte)(suffix_char)) != 0)
  246.         longjmp(recover, status);
  247.         }
  248.     else
  249.         {
  250.         input_code = code;
  251.  
  252.         if (code >= free_code)
  253.         {
  254.         code = old_code;
  255.             code_table[sp++].stack = (char) final_char;
  256.         }
  257.  
  258.         while (code >= first_free)
  259.         {
  260.         code_table[sp++].stack = code_table[code].suffix;
  261.         code = code_table[code].prefix;
  262.         }
  263.  
  264.         final_char = code;
  265.         suffix_char = code;
  266.         code_table[sp++].stack = (char) final_char;
  267.  
  268.         while (sp > 0)
  269.         if ((status = (*put_byte)(code_table[--sp].stack)) != 0)
  270.             longjmp(recover, status);
  271.  
  272.         code_table[free_code].suffix = (char) suffix_char;
  273.         code_table[free_code].prefix = old_code;
  274.         free_code++;
  275.         old_code = input_code;
  276.  
  277.         if (free_code >= max_code)
  278.         if (code_size < 12)
  279.             {
  280.             code_size++;
  281.             max_code <<= 1;
  282.             }
  283.         }
  284.     }
  285.  
  286.     free((char *) code_table);
  287.     return 0;
  288.     }
  289.