home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c019 / 1.ddi / BOOZ20 / LZD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-10  |  6.1 KB  |  225 lines
  1. /*
  2. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  3. code.
  4.  
  5. This file is public domain.
  6.  
  7.                                     -- Rahul Dhesi 1991/07/07
  8. */
  9.  
  10. #include "booz.h"
  11. #include <stdio.h>
  12.  
  13. /* must fit in MEM_BLOCK_SIZE */
  14. #define  OUT_BUF_SIZE    4096
  15. #define  IN_BUF_SIZE    4096
  16.  
  17. #define  STACKSIZE   2000
  18. #define  INBUFSIZ    (IN_BUF_SIZE - SPARE)
  19. #define  OUTBUFSIZ   (OUT_BUF_SIZE - SPARE)
  20. #define  MEMERR      2
  21. #define  IOERR       1
  22. #define  MAXBITS     13
  23. #define  CLEAR       256         /* clear code */
  24. #define  Z_EOF       257         /* end of file marker */
  25. #define  FIRST_FREE  258         /* first free code */
  26. #define  MAXMAX      8192        /* max code + 1 */
  27. #define  SPARE       4
  28.  
  29. char out_buf_adr[MEM_BLOCK_SIZE];
  30. #define in_buf_adr   (&out_buf_adr[OUT_BUF_SIZE])
  31.  
  32. struct tabentry {
  33.    unsigned next;
  34.    char z_ch;
  35. };
  36.  
  37. static struct tabentry *table;
  38. static int gotmem = 0;
  39.  
  40. static int init_dtab();
  41. static unsigned rd_dcode();
  42. static int wr_dchar();
  43. static int ad_dcode();
  44.  
  45. static unsigned lzd_sp = 0;
  46. static unsigned lzd_stack[STACKSIZE + SPARE];
  47.  
  48. static int push(ch)
  49. int ch;
  50. {
  51.    lzd_stack[lzd_sp++] = ch;
  52.    if (lzd_sp >= STACKSIZE)
  53.       prterror ('f', "Stack overflow in lzd()\n", (char *) 0, (char *) 0);
  54. }
  55.    
  56. #define  pop()    (lzd_stack[--lzd_sp])
  57.  
  58. unsigned cur_code;
  59. unsigned old_code;
  60. unsigned in_code;
  61.  
  62. unsigned free_code;
  63. int nbits;
  64. unsigned max_code;
  65.  
  66. char fin_char;
  67. char k;
  68. unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  69.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  70. unsigned bit_offset;
  71. unsigned output_offset;
  72. static FILE *in_file;
  73. static FILE *out_file; 
  74.  
  75. int lzd(input_file, output_file)
  76. FILE *input_file, *output_file;          /* input & output file handles */
  77. {
  78.    in_file = input_file;                 /* make it avail to other fns */
  79.    out_file = output_file;               /* ditto */
  80.    nbits = 9;
  81.    max_code = 512;
  82.    free_code = FIRST_FREE;
  83.    lzd_sp = 0;
  84.    bit_offset = 0;
  85.    output_offset = 0;
  86.  
  87.    if (gotmem == 0) {
  88.       table = (struct tabentry *) 
  89.          malloc (MAXMAX * sizeof (struct tabentry) + SPARE);
  90.       gotmem++;
  91.    }
  92.    if (table == (struct tabentry *) 0)
  93.       memerr();
  94.  
  95.    fread(in_buf_adr, 1, INBUFSIZ, in_file);
  96.    if (ferror(in_file))
  97.       return(IOERR);
  98.  
  99.    init_dtab();             /* initialize table */
  100.  
  101. loop:
  102.    cur_code = rd_dcode();
  103.    if (cur_code == Z_EOF) {
  104.       if (output_offset != 0) {
  105.          if (out_file != NULL) {
  106.        if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
  107.               prterror ('f', "Output error in lzd()\n", 
  108.                         (char *) 0, (char *) 0);
  109.          }
  110.          addbfcrc(out_buf_adr, output_offset);
  111.       }
  112.       return (0);
  113.    }
  114.  
  115.    if (cur_code == CLEAR) {
  116.       init_dtab();
  117.       fin_char = k = old_code = cur_code = rd_dcode();
  118.       wr_dchar((int) k);
  119.       goto loop;
  120.    }
  121.  
  122.    in_code = cur_code;
  123.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  124.       cur_code = old_code;             /* previous code becomes current */
  125.       push(fin_char);
  126.    }
  127.  
  128.    while (cur_code > 255) {               /* if code, not character */
  129.       push(table[cur_code].z_ch);         /* push suffix char */
  130.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  131.    }
  132.  
  133.    k = fin_char = cur_code;
  134.    push(k);
  135.    while (lzd_sp != 0) {
  136.       wr_dchar((int) pop());
  137.    }
  138.    ad_dcode();
  139.    old_code = in_code;
  140.  
  141.    goto loop;
  142. } /* lzd() */
  143.  
  144. /* rd_dcode() reads a code from the input (compressed) file and returns
  145. its value. */
  146. static unsigned rd_dcode()
  147. {
  148.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  149.    unsigned word;                     /* first 16 bits in buffer */
  150.    unsigned byte_offset;
  151.    char nextch;                           /* next 8 bits in buffer */
  152.    unsigned ofs_inbyte;               /* offset within byte */
  153.  
  154.    ofs_inbyte = bit_offset % 8;
  155.    byte_offset = bit_offset / 8;
  156.    bit_offset = bit_offset + nbits;
  157.  
  158.    if (byte_offset >= INBUFSIZ - 5) {
  159.       int space_left;
  160.  
  161.       bit_offset = ofs_inbyte + nbits;
  162.       space_left = INBUFSIZ - byte_offset;
  163.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  164.       ptra = in_buf_adr;
  165.       /* we now move the remaining characters down buffer beginning */
  166.       while (space_left > 0) {
  167.          *ptra++ = *ptrb++;
  168.          space_left--;
  169.       }
  170.       fread(ptra, 1, byte_offset, in_file);
  171.       if (ferror(in_file))
  172.          prterror ('f', "Input error in lzd:rd_dcode\n", 
  173.                 (char *) 0, (char *) 0);
  174.       byte_offset = 0;
  175.    }
  176.    ptra = byte_offset + in_buf_adr;
  177.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  178.    word = (unsigned char) *ptra; ptra++;
  179.    word = word | ((unsigned char) *ptra) << 8; ptra++;
  180.  
  181.    nextch = *ptra;
  182.    if (ofs_inbyte != 0) {
  183.       /* shift nextch right by ofs_inbyte bits */
  184.       /* and shift those bits right into word; */
  185.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  186.    }
  187.    return (word & masks[nbits]); 
  188. } /* rd_dcode() */
  189.  
  190. static int init_dtab()
  191. {
  192.    nbits = 9;
  193.    max_code = 512;
  194.    free_code = FIRST_FREE;
  195. }
  196.  
  197. static int wr_dchar (ch)
  198. int ch;
  199. {
  200.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  201.       if (out_file != NULL) {
  202.          if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
  203.             prterror ('f', "Write error in lzd:wr_dchar\n", 
  204.                     (char *) 0, (char *) 0);
  205.       }
  206.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  207.       output_offset = 0;                  /* restore empty buffer */
  208.    }
  209.    out_buf_adr[output_offset++] = ch;        /* store character */
  210. } /* wr_dchar() */
  211.  
  212. /* adds a code to table */
  213. static int ad_dcode()
  214. {
  215.    table[free_code].z_ch = k;                /* save suffix char */
  216.    table[free_code].next = old_code;         /* save prefix code */
  217.    free_code++;
  218.    if (free_code >= max_code) {
  219.       if (nbits < MAXBITS) {
  220.          nbits++;
  221.          max_code = max_code << 1;        /* double max_code */
  222.       }
  223.    }
  224. }
  225.