home *** CD-ROM | disk | FTP | other *** search
/ FM Towns: Free Software Collection 3 / FREEWARE.BIN / towns_os / look / source / lzw.c < prev    next >
Text File  |  1980-01-02  |  4KB  |  185 lines
  1. /*----------------------------------------------------------------------*/
  2. /* Copyright (c) 1987                                                    */
  3. /* by CompuServe Inc., Columbus, Ohio.  All Rights Reserved                */
  4. /* 89.6.8    FM-TOWNS Model Convert By Ken                                */
  5. /*----------------------------------------------------------------------*/
  6. #include     <stdio.h>
  7. #include    <stdlib.h>
  8.  
  9. #define largest_code    4095
  10.  
  11. struct code_entry {
  12.     short prefix;            /* prefix code */
  13.     char suffix;            /* suffix character */
  14.     char stack;
  15. };
  16.  
  17. static short code_size;
  18. static short clear_code;
  19. static short eof_code;
  20. static short first_free;
  21. static short bit_offset;
  22. static short byte_offset, bits_left;
  23. static short max_code;
  24. static short free_code;
  25. static short old_code;
  26. static short input_code;
  27. static short code;
  28. static short suffix_char;
  29. static short final_char;
  30. static short bytes_unread;
  31. static short min_code_size;
  32. static unsigned char code_buffer[64];
  33. static struct code_entry *code_table;
  34. static char *dmy_buf=NULL;
  35. static short dmy_size,dmy_ptr,dmy_read;
  36.  
  37. static short mask[12] =
  38.     {0x001, 0x003, 0x007, 0x00F,
  39.      0x01F, 0x03F, 0x07F, 0x0FF,
  40.      0x1FF, 0x3FF, 0x7FF, 0xFFF};
  41.  
  42. static void dmy_putc(short ch)
  43. {
  44.     dmy_buf[dmy_ptr++] = ch;
  45.     dmy_ptr &= 4095;
  46.     dmy_size++;
  47. }
  48. static void init_table(short min_code_size)
  49. {
  50.     code_size = min_code_size + 1;
  51.     clear_code = 1 << min_code_size;
  52.     eof_code = clear_code + 1;
  53.     first_free = clear_code + 2;
  54.     free_code = first_free;
  55.     max_code = 1 << code_size;
  56. }
  57.  
  58. static long read_code(FILE *fp)
  59. {
  60.     short bytes_to_move, i, ch;
  61.     long temp;
  62.  
  63.     byte_offset = bit_offset >> 3;
  64.     bits_left = bit_offset & 7;
  65.  
  66.     if (byte_offset >= 61) {
  67.         bytes_to_move = 64 - byte_offset;
  68.         for (i = 0; i < bytes_to_move; i++)
  69.             code_buffer[i] = code_buffer[byte_offset + i];
  70.         while (i < 64) {
  71.             if (bytes_unread == 0) {
  72.                 if ( (bytes_unread = getc(fp)) == EOF )
  73.                     return EOF;
  74.                 if ( bytes_unread == 0 )    /* end of data */
  75.                     break;
  76.             }
  77.             if ( (ch = getc(fp)) == EOF )
  78.                 return EOF;
  79.             code_buffer[i++] = ch;
  80.             bytes_unread--;
  81.         }
  82.         bit_offset = bits_left;
  83.         byte_offset = 0;
  84.     }
  85.  
  86.     bit_offset += code_size;
  87.     temp = (long) code_buffer[byte_offset]
  88.          | (long) code_buffer[byte_offset + 1] << 8
  89.          | (long) code_buffer[byte_offset + 2] << 16;
  90.  
  91.     if (bits_left > 0)
  92.         temp >>= bits_left;
  93.  
  94.     return temp & mask[code_size - 1];
  95. }
  96.  
  97. static short Expand_init(FILE *fp)
  98. {
  99.     if ( (code_table = (struct code_entry *)
  100.             malloc(sizeof(struct code_entry)*(largest_code + 1))) == NULL )
  101.         return EOF;
  102.  
  103.     if ( (min_code_size = getc(fp)) < 0 )
  104.         return EOF;
  105.     else if ( min_code_size < 2 || min_code_size > 9 )
  106.         return EOF;
  107.  
  108.     init_table(min_code_size);
  109.     bit_offset = 64*8;            /* force "read_code" to start a new */
  110.     bytes_unread = 0;            /* record */
  111.     return 0;
  112. }
  113. static short Expand_Data(FILE *fp)
  114. {
  115.     short sp = 0;
  116.  
  117.     if ( (code = read_code(fp)) == eof_code )
  118.         return EOF;
  119.  
  120.     if ( code == clear_code ) {
  121.         init_table(min_code_size);
  122.         code = read_code(fp);
  123.         old_code = code;
  124.         suffix_char = code;
  125.         final_char = code;
  126.         dmy_putc(suffix_char);
  127.         return 0;
  128.     }
  129.  
  130.        input_code = code;
  131.     if ( code >= free_code ) {
  132.         code = old_code;
  133.         code_table[sp++].stack = final_char;
  134.     }
  135.     while (code >= first_free) {
  136.         code_table[sp++].stack = code_table[code].suffix;
  137.         code = code_table[code].prefix;
  138.     }
  139.  
  140.        final_char = code;
  141.        suffix_char = code;
  142.        code_table[sp++].stack = final_char;
  143.  
  144.        while (sp > 0)
  145.         dmy_putc(code_table[--sp].stack);
  146.  
  147.     code_table[free_code].suffix = suffix_char;
  148.     code_table[free_code].prefix = old_code;
  149.        free_code++;
  150.        old_code = input_code;
  151.  
  152.        if ( free_code >= max_code && code_size < 12 ) {
  153.         code_size++;
  154.         max_code <<= 1;
  155.     }
  156.     return 0;
  157. }
  158. void    dmy_close(void)
  159. {
  160.     if ( dmy_buf != NULL ) { free(dmy_buf); dmy_buf = NULL; }
  161.     if ( code_table != NULL ) { free(code_table); code_table = NULL; }
  162. }
  163. int        dmy_getc(FILE *fp)
  164. {
  165.     int        ch;
  166.  
  167.     if ( dmy_buf == NULL ) {
  168.         if ( Expand_init(fp) != 0 )
  169.             goto ERROR;
  170.         if ( (dmy_buf = malloc(4096)) == NULL )
  171.             goto ERROR;        
  172.         dmy_size = dmy_ptr = dmy_read = 0;
  173.     }
  174.     if ( dmy_size <= 0 && Expand_Data(fp) != 0 )
  175.         goto ERROR;
  176.     ch = (unsigned char)dmy_buf[dmy_read++];
  177.     dmy_read &= 4095;
  178.     dmy_size--;
  179.     return ch;
  180.  
  181. ERROR:
  182.     dmy_close();
  183.     return EOF;
  184. }
  185.