home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / formats / gif / amiga / amigif.arc / expand.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-06-16  |  4.8 KB  |  234 lines
  1. /***********************************************************
  2.  * Copyright (c) 1987                                      *
  3.  * by CompuServe Inc, Columbus, Ohio.  All Rights Reserved *
  4.  ***********************************************************/
  5.  
  6. /*
  7.  * ABSTRACT:
  8.  *    Please see COMPRESS.C
  9.  *
  10.  * AUTHOR: Steve Wilhite
  11.  *
  12.  * REVISION HISTORY:
  13.  *
  14.  */
  15.  
  16. #include <setjmp.h>
  17.  
  18. extern char *malloc();            /* standard GetMem */
  19.  
  20. #define null_ptr    0L
  21. #define largest_code    4095
  22.  
  23. jmp_buf recover;
  24.  
  25. struct code_entry
  26.     {
  27.     short prefix;            /* prefix code */
  28.     char suffix;            /* suffix character */
  29.     char stack;
  30.     };
  31.  
  32. static short code_size;
  33. static short clear_code;
  34. static short eof_code;
  35. static short first_free;
  36. static short bit_offset;
  37. static short byte_offset, bits_left;
  38. static short max_code;
  39. static short free_code;
  40. static short old_code;
  41. static short input_code;
  42. static short code;
  43. static short suffix_char;
  44. static short final_char;
  45. static short bytes_unread;
  46. static unsigned char code_buffer[64];
  47. static struct code_entry *code_table;
  48. static short (*get_byte)();
  49. static short (*put_byte)();
  50.  
  51. static short mask[12] =
  52.     {0x001, 0x003, 0x007, 0x00F,
  53.      0x01F, 0x03F, 0x07F, 0x0FF,
  54.      0x1FF, 0x3FF, 0x7FF, 0xFFF};
  55.  
  56.  
  57. static init_table(min_code_size)
  58.     short min_code_size;
  59.     {
  60.     code_size = min_code_size + 1;
  61.     clear_code = 1 << min_code_size;
  62.     eof_code = clear_code + 1;
  63.     first_free = clear_code + 2;
  64.     free_code = first_free;
  65.     max_code = 1 << code_size;
  66.     }
  67. /*$page*/
  68.  
  69. static read_code()
  70.     {
  71.     short bytes_to_move, i, ch;
  72.     long temp;
  73.  
  74.     byte_offset = bit_offset >> 3;
  75.     bits_left = bit_offset & 7;
  76.  
  77.     if (byte_offset >= 61)
  78.     {
  79.     bytes_to_move = 64 - byte_offset;
  80.  
  81.     for (i = 0; i < bytes_to_move; i++)
  82.         code_buffer[i] = code_buffer[byte_offset + i];
  83.  
  84.     while (i < 64)
  85.         {
  86.         if (bytes_unread == 0)
  87.         {
  88.         /* Get the length of the next record. A zero-length record
  89.          * denotes "end of data".
  90.          */
  91.  
  92.         bytes_unread = (*get_byte)();
  93.  
  94.         if (bytes_unread < 1)
  95.             if (bytes_unread == 0)    /* end of data */
  96.             break;
  97.             else
  98.             longjmp(recover, bytes_unread);
  99.         }
  100.  
  101.         ch = (*get_byte)();
  102.  
  103.         if (ch < 0)
  104.         longjmp(recover, ch);
  105.  
  106.         code_buffer[i++] = ch;
  107.         bytes_unread--;
  108.         }
  109.  
  110.     bit_offset = bits_left;
  111.     byte_offset = 0;
  112.     }
  113.  
  114.     bit_offset += code_size;
  115.     temp = (long) code_buffer[byte_offset]
  116.     | (long) code_buffer[byte_offset + 1] << 8
  117.     | (long) code_buffer[byte_offset + 2] << 16;
  118.  
  119.     if (bits_left > 0)
  120.     temp >>= bits_left;
  121.  
  122.     return temp & mask[code_size - 1];
  123.     }
  124. /*$page*/
  125.  
  126. short Expand_Data(get_byte_routine, put_byte_routine)
  127. /*
  128.  * Function:
  129.  *    Decompress a LZW compressed data stream.
  130.  *
  131.  * Inputs:
  132.  *    get_byte_routine - address of the caller's "get_byte" routine.
  133.  *    put_byte_routine - address of the caller's "put_byte" routine.
  134.  *
  135.  * Returns:
  136.  *    0    OK
  137.  *    -1    expected end-of-file
  138.  *    -2    cannot allocate memory
  139.  *    -3    bad "min_code_size"
  140.  *    < -3    error status from the get_byte or put_byte routine
  141.  */
  142.     short (*get_byte_routine)();
  143.     short (*put_byte_routine)();
  144.     {
  145.     short i;
  146.     short sp;                /* stack ptr */
  147.     short status;
  148.     short min_code_size;
  149.  
  150.     get_byte = get_byte_routine;
  151.     put_byte = put_byte_routine;
  152.  
  153.     code_table = (struct code_entry *)
  154.     malloc(sizeof(struct code_entry)*(largest_code + 1));
  155.  
  156.     if (code_table == null_ptr)
  157.     return -2;
  158.  
  159.     status = setjmp(recover);
  160.  
  161.     if (status != 0)
  162.     {
  163.     free((char *) code_table);
  164.     return status;
  165.     }
  166.  
  167.     /* Get the minimum code size (2 to 9) */
  168.  
  169.     min_code_size = (*get_byte)();
  170.  
  171.     if (min_code_size < 0)
  172.     longjmp(recover, min_code_size);
  173.     else if (min_code_size < 2 || min_code_size > 9)
  174.     longjmp(recover, -3);
  175.  
  176.     init_table(min_code_size);
  177.     sp = 0;
  178.     bit_offset = 64*8;            /* force "read_code" to start a new */
  179.     bytes_unread = 0;            /* record */
  180.  
  181.     while ((code = read_code()) != eof_code)
  182.     {
  183.     if (code == clear_code)
  184.         {
  185.         init_table(min_code_size);
  186.         code = read_code();
  187.         old_code = code;
  188.         suffix_char = code;
  189.         final_char = code;
  190.         if ((status = (*put_byte)(suffix_char)) != 0)
  191.         longjmp(recover, status);
  192.         }
  193.     else
  194.         {
  195.         input_code = code;
  196.  
  197.         if (code >= free_code)
  198.         {
  199.         code = old_code;
  200.             code_table[sp++].stack = final_char;
  201.         }
  202.  
  203.         while (code >= first_free)
  204.         {
  205.         code_table[sp++].stack = code_table[code].suffix;
  206.         code = code_table[code].prefix;
  207.         }
  208.  
  209.         final_char = code;
  210.         suffix_char = code;
  211.         code_table[sp++].stack = final_char;
  212.  
  213.         while (sp > 0)
  214.         if ((status = (*put_byte)(code_table[--sp].stack)) != 0)
  215.             longjmp(recover, status);
  216.  
  217.         code_table[free_code].suffix = suffix_char;
  218.         code_table[free_code].prefix = old_code;
  219.         free_code++;
  220.         old_code = input_code;
  221.  
  222.         if (free_code >= max_code)
  223.         if (code_size < 12)
  224.             {
  225.             code_size++;
  226.             max_code <<= 1;
  227.             }
  228.         }
  229.     }
  230.  
  231.     free((char *) code_table);
  232.     return 0;
  233.     }
  234.