home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume17 / zoo2 / part04 / lzd.c < prev    next >
C/C++ Source or Header  |  1989-02-01  |  8KB  |  267 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. #include "options.h"
  6. /*
  7. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  8. code.  The contents of this file are hereby released to the public domain.
  9.                                  -- Rahul Dhesi 1986/11/14
  10. */
  11.  
  12. #include "zoo.h"
  13. #include "zooio.h"
  14. #include "various.h"
  15. #include "zoofns.h"           /* function definitions */
  16. /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
  17. #include "zoomem.h"
  18. #include "debug.h"
  19. #include "assert.h"
  20. /* lzconst.h contains constants for lzd() and lzc() */
  21. #include "lzconst.h"
  22.  
  23. #define  STACKSIZE   4000
  24.  
  25. struct tabentry {
  26.    unsigned next;
  27.    char z_ch;
  28. };
  29.  
  30.  
  31. #ifdef LINT_ARGS
  32. void init_dtab(NOTHING);
  33. unsigned rd_dcode(NOTHING);
  34. void wr_dchar (char);
  35. void ad_dcode(NOTHING);
  36. #else
  37. void init_dtab();
  38. unsigned rd_dcode();
  39. void wr_dchar();
  40. void ad_dcode();
  41. #endif
  42.  
  43. #ifdef FILTER
  44. /* to send data back to zoofilt */
  45. extern unsigned int filt_lzd_word;
  46. #endif /* FILTER */
  47.  
  48.  
  49. static unsigned stack_pointer = 0;
  50. static unsigned *stack;
  51.  
  52. #define  push(x)  {  \
  53.                      stack[stack_pointer++] = (x);                   \
  54.                      if (stack_pointer >= STACKSIZE)                 \
  55.                         prterror ('f', "Stack overflow in lzd().\n");\
  56.                   }
  57. #define  pop()    (stack[--stack_pointer])
  58.  
  59. extern char *out_buf_adr;        /* output buffer */
  60. extern char *in_buf_adr;         /* input buffer */
  61.  
  62. char memflag = 0;                /* memory allocated? flag */
  63. extern struct tabentry *table;   /* hash table from lzc.c */
  64. static unsigned cur_code;
  65. static unsigned old_code;
  66. static unsigned in_code;
  67.  
  68. static unsigned free_code;
  69. static int nbits;
  70. static unsigned max_code;
  71.  
  72. static char fin_char;
  73. static char k;
  74. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  75.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  76. static unsigned bit_offset;
  77. static unsigned output_offset;
  78.  
  79. #ifdef UNBUF_IO
  80. #define        BLOCKFILE        int
  81. #define        BLOCKREAD        read
  82. #define        BLOCKWRITE        blockwrite
  83. int read PARMS ((int, VOIDPTR, unsigned));
  84. int write PARMS ((int, VOIDPTR, unsigned));
  85. #else
  86. #define        BLOCKFILE        ZOOFILE
  87. #define        BLOCKREAD        zooread
  88. #define        BLOCKWRITE        zoowrite
  89. #endif /* UNBUF_IO */
  90.  
  91. static BLOCKFILE in_f, out_f; 
  92.  
  93. int lzd(input_f, output_f)
  94. BLOCKFILE input_f, output_f;          /* input & output file handles */
  95. {
  96.    in_f = input_f;                 /* make it avail to other fns */
  97.    out_f = output_f;               /* ditto */
  98.    nbits = 9;
  99.    max_code = 512;
  100.    free_code = FIRST_FREE;
  101.    stack_pointer = 0;
  102.    bit_offset = 0;
  103.    output_offset = 0;
  104.  
  105.    if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
  106.       return(IOERR);
  107.    if (memflag == 0) {
  108.      table = (struct tabentry *) emalloc((MAXMAX+10) * sizeof(struct tabentry));
  109.      stack = (unsigned *) emalloc (sizeof (unsigned) * STACKSIZE + 20);
  110.      memflag++;
  111.    }
  112.  
  113.    init_dtab();             /* initialize table */
  114.  
  115. loop:
  116.    cur_code = rd_dcode();
  117. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  118.    if (cur_code == Z_EOF) {
  119.       debug((printf ("lzd: Z_EOF\n")))
  120.       if (output_offset != 0) {
  121.          if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  122.             prterror ('f', "Output error in lzd().\n");
  123.          addbfcrc(out_buf_adr, output_offset);
  124.       }
  125. #ifdef FILTER
  126.         /* get next two bytes and put them where zoofilt can find them */
  127.         /* nbits known to be in range 9..13 */
  128.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  129.         filt_lzd_word = rd_dcode();
  130.         filt_lzd_word |= (rd_dcode() << nbits);
  131.         filt_lzd_word &= 0xffff;
  132. #endif
  133.       return (0);
  134.    }
  135.  
  136.    assert(nbits >= 9 && nbits <= 13);
  137.  
  138.    if (cur_code == CLEAR) {
  139.       debug((printf ("lzd: CLEAR\n")))
  140.       init_dtab();
  141.       fin_char = k = old_code = cur_code = rd_dcode();
  142.         if (cur_code == Z_EOF)        /* special case for 0-length files */
  143.             goto goteof;
  144.       wr_dchar(k);
  145.       goto loop;
  146.    }
  147.  
  148.    in_code = cur_code;
  149.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  150.       cur_code = old_code;             /* previous code becomes current */
  151.       push(fin_char);
  152.    }
  153.  
  154.    while (cur_code > 255) {               /* if code, not character */
  155.       push(table[cur_code].z_ch);         /* push suffix char */
  156.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  157.    }
  158.  
  159.    assert(nbits >= 9 && nbits <= 13);
  160.  
  161.    k = fin_char = cur_code;
  162.    push(k);
  163.    while (stack_pointer != 0) {
  164.       wr_dchar(pop());
  165.    }
  166.    assert(nbits >= 9 && nbits <= 13);
  167.    ad_dcode();
  168.    old_code = in_code;
  169.  
  170.    assert(nbits >= 9 && nbits <= 13);
  171.  
  172.    goto loop;
  173. } /* lzd() */
  174.  
  175. /* rd_dcode() reads a code from the input (compressed) file and returns
  176. its value. */
  177. unsigned rd_dcode()
  178. {
  179.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  180.    unsigned word;                     /* first 16 bits in buffer */
  181.    unsigned byte_offset;
  182.    char nextch;                           /* next 8 bits in buffer */
  183.    unsigned ofs_inbyte;               /* offset within byte */
  184.  
  185.    ofs_inbyte = bit_offset % 8;
  186.    byte_offset = bit_offset / 8;
  187.    bit_offset = bit_offset + nbits;
  188.  
  189.    assert(nbits >= 9 && nbits <= 13);
  190.  
  191.    if (byte_offset >= INBUFSIZ - 5) {
  192.       int space_left;
  193.  
  194.       assert(byte_offset >= INBUFSIZ - 5);
  195.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  196.  
  197.       bit_offset = ofs_inbyte + nbits;
  198.       space_left = INBUFSIZ - byte_offset;
  199.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  200.       ptra = in_buf_adr;
  201.       /* we now move the remaining characters down buffer beginning */
  202.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  203.       while (space_left > 0) {
  204.          *ptra++ = *ptrb++;
  205.          space_left--;
  206.       }
  207.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  208.       assert(space_left == 0);
  209.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  210.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  211.       byte_offset = 0;
  212.    }
  213.    ptra = byte_offset + in_buf_adr;
  214.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  215.    word = (unsigned char) *ptra; ptra++;
  216.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  217.  
  218.    nextch = *ptra;
  219.    if (ofs_inbyte != 0) {
  220.       /* shift nextch right by ofs_inbyte bits */
  221.       /* and shift those bits right into word; */
  222.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  223.    }
  224.    return (word & masks[nbits]); 
  225. } /* rd_dcode() */
  226.  
  227. void init_dtab()
  228. {
  229.    nbits = 9;
  230.    max_code = 512;
  231.    free_code = FIRST_FREE;
  232. }
  233.  
  234. void wr_dchar (ch)
  235. char ch;
  236. {
  237.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  238.       if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  239.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  240.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  241.       output_offset = 0;                  /* restore empty buffer */
  242.    }
  243.    assert(output_offset < OUTBUFSIZ);
  244.    out_buf_adr[output_offset++] = ch;        /* store character */
  245. } /* wr_dchar() */
  246.  
  247. /* adds a code to table */
  248. void ad_dcode()
  249. {
  250.    assert(nbits >= 9 && nbits <= 13);
  251.    assert(free_code <= MAXMAX+1);
  252.    table[free_code].z_ch = k;                /* save suffix char */
  253.    table[free_code].next = old_code;         /* save prefix code */
  254.    free_code++;
  255.    assert(nbits >= 9 && nbits <= 13);
  256.    if (free_code >= max_code) {
  257.       if (nbits < MAXBITS) {
  258.          debug((printf("lzd: nbits was %d\n", nbits)))
  259.          nbits++;
  260.          assert(nbits >= 9 && nbits <= 13);
  261.          debug((printf("lzd: nbits now %d\n", nbits)))
  262.          max_code = max_code << 1;        /* double max_code */
  263.          debug((printf("lzd: max_code now %d\n", max_code)))
  264.       }
  265.    }
  266. }
  267.