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