home *** CD-ROM | disk | FTP | other *** search
/ Hall of Fame / HallofFameCDROM.cdr / proglc / zoo141_c.lzh / LZD.C < prev    next >
C/C++ Source or Header  |  1987-02-07  |  7KB  |  233 lines
  1. #include "options.h"
  2. /*
  3. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  4. code.  The contents of this file are hereby released to the public domain.
  5.                                  -- Rahul Dhesi 1986/11/14
  6. */
  7.  
  8. #include <stdio.h>            /* just to define NULL */
  9. #include "various.h"
  10. #include "zoofns.h"           /* function definitions */
  11. /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
  12. #include "zoomem.h"
  13. #include "debug.h"
  14. #include "assert.h"
  15. /* lzconst.h contains constants for lzd() and lzc() */
  16. #include "lzconst.h"
  17.  
  18. #define  STACKSIZE   4000
  19.  
  20. struct tabentry {
  21.    unsigned next;
  22.    char z_ch;
  23. };
  24.  
  25. void init_dtab();
  26. unsigned rd_dcode();
  27.  
  28. #ifdef LINT_ARGS
  29. void wr_dchar (char);
  30. #else
  31. void wr_dchar();
  32. #endif
  33.  
  34. void ad_dcode();
  35.  
  36. static unsigned stack_pointer = 0;
  37. static unsigned stack[STACKSIZE + 20];    /* fudge factor -- avoid obo errors */
  38.  
  39. #define  push(x)  {  \
  40.                      stack[stack_pointer++] = (x);                   \
  41.                      if (stack_pointer >= STACKSIZE)                 \
  42.                         prterror ('f', "Stack overflow in lzd().\n");\
  43.                   }
  44. #define  pop()    (stack[--stack_pointer])
  45.  
  46. extern char *out_buf_adr;        /* output buffer */
  47. extern char *in_buf_adr;         /* input buffer */
  48.  
  49. char memflag = 0;                /* memory allocated? flag */
  50. extern struct tabentry *table;   /* hash table from lzc.c */
  51. static unsigned cur_code;
  52. static unsigned old_code;
  53. static unsigned in_code;
  54.  
  55. static unsigned free_code;
  56. static int nbits;
  57. static unsigned max_code;
  58.  
  59. static char fin_char;
  60. static char k;
  61. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  62.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  63. static unsigned bit_offset;
  64. static unsigned output_offset;
  65. static int in_han, out_han; 
  66.  
  67. int lzd(input_handle, output_handle)
  68. int input_handle, output_handle;          /* input & output file handles */
  69. {
  70.    in_han = input_handle;                 /* make it avail to other fns */
  71.    out_han = output_handle;               /* ditto */
  72.    nbits = 9;
  73.    max_code = 512;
  74.    free_code = FIRST_FREE;
  75.    stack_pointer = 0;
  76.    bit_offset = 0;
  77.    output_offset = 0;
  78.  
  79.    if (read(in_han, in_buf_adr, INBUFSIZ) == -1)
  80.       return(IOERR);
  81.    if (memflag == 0) {
  82.      table = (struct tabentry *) emalloc((MAXMAX+10) * sizeof(struct tabentry));
  83.      memflag++;
  84.    }
  85.  
  86.    init_dtab();             /* initialize table */
  87.  
  88. loop:
  89.    cur_code = rd_dcode();
  90.    if (cur_code == Z_EOF) {
  91.       debug((printf ("lzd: Z_EOF\n")))
  92.       if (output_offset != 0) {
  93.          if (out_han != -2) {
  94.             if (write(out_han, out_buf_adr, output_offset) != output_offset)
  95.                prterror ('f', "Output error in lzd().\n");
  96.          }
  97.          addbfcrc(out_buf_adr, output_offset);
  98.       }
  99.       return (0);
  100.    }
  101.  
  102.    assert(nbits >= 9 && nbits <= 13);
  103.  
  104.    if (cur_code == CLEAR) {
  105.       debug((printf ("lzd: CLEAR\n")))
  106.       init_dtab();
  107.       fin_char = k = old_code = cur_code = rd_dcode();
  108.       wr_dchar(k);
  109.       goto loop;
  110.    }
  111.  
  112.    in_code = cur_code;
  113.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  114.       cur_code = old_code;             /* previous code becomes current */
  115.       push(fin_char);
  116.    }
  117.  
  118.    while (cur_code > 255) {               /* if code, not character */
  119.       push(table[cur_code].z_ch);         /* push suffix char */
  120.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  121.    }
  122.  
  123.    assert(nbits >= 9 && nbits <= 13);
  124.  
  125.    k = fin_char = cur_code;
  126.    push(k);
  127.    while (stack_pointer != 0) {
  128.       wr_dchar(pop());
  129.    }
  130.    assert(nbits >= 9 && nbits <= 13);
  131.    ad_dcode();
  132.    old_code = in_code;
  133.  
  134.    assert(nbits >= 9 && nbits <= 13);
  135.  
  136.    goto loop;
  137. } /* lzd() */
  138.  
  139. /* rd_dcode() reads a code from the input (compressed) file and returns
  140. its value. */
  141. unsigned rd_dcode()
  142. {
  143.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  144.    unsigned word;                     /* first 16 bits in buffer */
  145.    unsigned byte_offset;
  146.    char nextch;                           /* next 8 bits in buffer */
  147.    unsigned ofs_inbyte;               /* offset within byte */
  148.  
  149.    ofs_inbyte = bit_offset % 8;
  150.    byte_offset = bit_offset / 8;
  151.    bit_offset = bit_offset + nbits;
  152.  
  153.    assert(nbits >= 9 && nbits <= 13);
  154.  
  155.    if (byte_offset >= INBUFSIZ - 5) {
  156.       int space_left;
  157.  
  158.       assert(byte_offset >= INBUFSIZ - 5);
  159.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  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.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  167.       while (space_left > 0) {
  168.          *ptra++ = *ptrb++;
  169.          space_left--;
  170.       }
  171.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  172.       assert(space_left == 0);
  173.       if (read(in_han, ptra, byte_offset) == -1)
  174.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  175.       byte_offset = 0;
  176.    }
  177.    ptra = byte_offset + in_buf_adr;
  178.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  179.    word = (unsigned char) *ptra; ptra++;
  180.    word = word | ((unsigned char) *ptra) << 8; ptra++;
  181.  
  182.    nextch = *ptra;
  183.    if (ofs_inbyte != 0) {
  184.       /* shift nextch right by ofs_inbyte bits */
  185.       /* and shift those bits right into word; */
  186.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  187.    }
  188.    return (word & masks[nbits]); 
  189. } /* rd_dcode() */
  190.  
  191. void init_dtab()
  192. {
  193.    nbits = 9;
  194.    max_code = 512;
  195.    free_code = FIRST_FREE;
  196. }
  197.  
  198. void wr_dchar (ch)
  199. char ch;
  200. {
  201.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  202.       if (out_han != -2) {
  203.          if (write(out_han, out_buf_adr, output_offset) != output_offset)
  204.             prterror ('f', "Write error in lzd:wr_dchar.\n");
  205.       }
  206.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  207.       output_offset = 0;                  /* restore empty buffer */
  208.    }
  209.    assert(output_offset < OUTBUFSIZ);
  210.    out_buf_adr[output_offset++] = ch;        /* store character */
  211. } /* wr_dchar() */
  212.  
  213. /* adds a code to table */
  214. void ad_dcode()
  215. {
  216.    assert(nbits >= 9 && nbits <= 13);
  217.    assert(free_code <= MAXMAX+1);
  218.    table[free_code].z_ch = k;                /* save suffix char */
  219.    table[free_code].next = old_code;         /* save prefix code */
  220.    free_code++;
  221.    assert(nbits >= 9 && nbits <= 13);
  222.    if (free_code >= max_code) {
  223.       if (nbits < MAXBITS) {
  224.          debug((printf("lzd: nbits was %d\n", nbits)))
  225.          nbits++;
  226.          assert(nbits >= 9 && nbits <= 13);
  227.          debug((printf("lzd: nbits now %d\n", nbits)))
  228.          max_code = max_code << 1;        /* double max_code */
  229.          debug((printf("lzd: max_code now %d\n", max_code)))
  230.       }
  231.    }
  232. }
  233.