home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / formats / gif / gen_code / amiga / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-02  |  7.2 KB  |  279 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;εq∙ ª¡ä│Äû┼▒~(Ω╜▀U╘⌐#╢5    VeÜHfzIoYô½=├|⌐ÖΘ╧A3▀√_/ m■àwÄVåT╨ªÑÿ[÷3F≈≈₧h½Df    û╫iÆτî╜╔δ╞d*n<p.╦F1wî_4sI▐▓╘K¼,Å£9%«}¥╠ █ɼ╬Σqib▌ùÑ─A.Z-O
  142. ìûOj╢ô≡┴{)╗a²à╠r±╥±D½GτY■ñX╠D°░▓êâl/g╟╜
  143. ▌Öß═Båào~╫¢<rèµφ.áK⌐▀oóGσ[?Érv_Mñç╚`╛t~ûâÆi╓¬º¥ªÜ[▀F╥)gì°4í╓█óü_1½╚![│IK╛"j▐ó╤t£ég+gäk┐ù<⌠TY▄G╞ε╝pº╩j3å2╝ò█ #▀S║½ì{■$â~7╪L"╣▄"d,├√&A;Q≥mS┌w╕
  144. Ñ╙Rεä⌠▒Φ-ࢠΓAΣ
  145. ╥âáp║π╙═éRC┬ú≥∞¡2┌ùεαj╘<ΩΦ¼│5F≥»╩~S}»2▐╢=»¼¢≈Y?│┴/φY'╜#└BTW║@ê Ω>ú╦w╜êbαôß1:é╩· δ#oƒ╛∞5²│wµ▌WD?∞┴╤zîΓv{) d?Æτ)ⁿòCq6ó¡XpαƒÑó▀ñ∩]'⌐
  146.     byte_offset = 0;
  147.     }
  148.  
  149.     if (bits_left > 0)
  150.     {
  151.     temp = ((long) code << bits_left) | code_buffer[byte_offset];
  152.     code_buffer[byte_offset] = temp;
  153.     code_buffer[byte_offset + 1] = temp >> 8;
  154.     code_buffer[byte_offset + 2] = temp >> 16;
  155.     }
  156.     else
  157.     {
  158.     code_buffer[byte_offset] = code;
  159.     code_buffer[byte_offset + 1] = code >> 8;
  160.     }
  161.  
  162.     bit_offset += code_size;
  163.     }
  164.  
  165. /*$page*/
  166.  
  167. short Compress_Data(min_code_size, get_byte_routine, put_byte_routine)
  168. /*
  169.  * Function:
  170.  *    Compress a stream of data bytes using the LZW algorithm.
  171.  *
  172.  * Inputs:
  173.  *    min_code_size
  174.  *        the field size of an input value.  Should be in the range from
  175.  *        1 to 9.
  176.  *
  177.  *    get_byte_routine
  178.  *        address of the caller's "get_byte" routine:
  179.  *
  180.  *        status = get_byte();
  181.  *
  182.  *        where "status" is
  183.  *            0 .. 255    the byte just read
  184.  *            -1        logical end-of-file
  185.  *            < -3        error codes
  186.  *
  187.  *    put_byte_routine
  188.  *        address the the caller's "put_byte" routine:
  189.  *
  190.  *        status = put_byte(value)
  191.  *
  192.  *        where
  193.  *            value    the byte to write
  194.  *            status    0 = OK, else < -3 means some error code
  195.  *
  196.  * Returns:
  197.  *     0    normal completion
  198.  *    -1    (not used)
  199.  *    -2    insufficient dynamic memory
  200.  *    -3    bad "min_code_size"
  201.  *    < -3    error status from either the get_byte or put_byte routine
  202.  */
  203.     short (*get_byte_routine)();
  204.     short (*put_byte_routine)();
  205.     {
  206.     short status;
  207.  
  208.     get_byte = get_byte_routine;
  209.     put_byte = put_byte_routine;
  210.  
  211.     if (min_code_size < 2 || min_code_size > 9)
  212.     if (min_code_size == 1)
  213.         min_code_size = 2;
  214.     else
  215.         return -3;
  216.  
  217.     code_table = (struct code_entry *)
  218.     GetMem(sizeof(struct code_entry)*table_size);
  219.  
  220.     if (code_table == null_ptr)
  221.     return -2;
  222.  
  223.     status = setjmp(recover);
  224.  
  225.     if (status != 0)
  226.     {
  227.     FreeMem((char *) code_table);
  228.     return status;
  229.     }
  230.  
  231.     (*put_byte)(min_code_size);        /* record the minimum code size */
  232.     bit_offset = 0;
  233.     init_table(min_code_size);
  234.     write_code(clear_code);
  235.     suffix_char = (*get_byte)();
  236.  
  237.     if (suffix_char >= 0)
  238.     {
  239.     prefix_code = suffix_char;
  240.  
  241.     while ((suffix_char = (*get_byte)()) >= 0)
  242.         {
  243.         hx = (prefix_code ^ suffix_char << 5) % table_size;
  244.         d = 1;
  245.  
  246.         for (;;)
  247.         {
  248.         if (code_table[hx].code_id == 0)
  249.             {
  250.             write_code(prefix_code);
  251.  
  252.             d = free_code;
  253.  
  254.             if (free_code <= largest_code)
  255.             {
  256.             code_table[hx].prior_code = prefix_code;
  257.             code_table[hx].added_char = suffix_char;
  258.             code_table[hx].code_id = free_code;
  259.             free_code++;
  260.             }
  261.  
  262.             if (d == max_code)
  263.             if (code_size < 12)
  264.                 {
  265.                 code_size++;
  266.                 max_code <<= 1;
  267.                 }
  268.             else
  269.                 {
  270.                 write_code(clear_code);
  271.                 init_table(min_code_size);
  272.                 }
  273.  
  274.             prefix_code = suffix_char;
  275.             break;
  276.             }
  277.  
  278.         if (code_table[hx].prior_code == prefix_code &&
  279.             code_table[hx].added_char == suffix_char)
  280.             {
  281.             pr