home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 9 / FreshFishVol9-CD2.bin / bbs / util / zoo-2.1.lha / zoo / lzd.c < prev    next >
C/C++ Source or Header  |  1992-05-02  |  28KB  |  850 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.    If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.    --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.    I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>     /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define    STACKSIZE    4000    /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */      /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. void xwr_dchar PARMS ((int));
  63. static int firstchar PARMS ((int));
  64. static void cbfill PARMS ((void));
  65.  
  66. /* wr_dchar() is a macro for speed */
  67. #define wr_dchar(c) {                             \
  68.                                     if (outbufp<outbuflim) \
  69.                                         *outbufp++=(c);     \
  70.                                     else                          \
  71.                                         xwr_dchar(c);       \
  72.                           }
  73.  
  74. extern char *out_buf_adr;            /* output buffer */
  75. extern char *in_buf_adr;            /* input buffer */
  76.                              /* use pointers (not counters) for buffer (for speed) */
  77. static char *outbufp;                /* output buffer pointer */
  78. static char *outbuflim;             /* output buffer limit */
  79. static char *outbufguard;            /* output buffer "guard" */
  80.  
  81. char memflag = 0;                     /* memory allocated? flag */
  82. int *head;                                /* lzw prefix codes */
  83. char *tail;                             /* lzw suffix codes */
  84. static unsigned cur_code;
  85. static unsigned old_code;
  86. static unsigned in_code;
  87.  
  88. static unsigned free_code;
  89. static int nbits;
  90. static unsigned max_code;
  91.  
  92. /* We use a buffer of codes to avoid a function call to unpack each
  93. ** one as needed.  We allocate an extra slot past the end of the buffer
  94. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  95. ** fold the test for code buffer runout into the test for a clear code
  96. ** and avoid having an extra test on each code processed.  Also, we don't
  97. ** always use the code buffer.  We can only use it when the input buffer
  98. ** is at a byte boundary, and when we know that the codesize won't change
  99. ** before we fill the code buffer, and when we know we won't run out of
  100. ** bytes in the input buffer before filling the code buffer.  So we start
  101. ** with the code buffer pointer pointing to the sentinel, and we always
  102. ** have it pointing at the sentinel when we can't (for one reason or
  103. ** another) be getting our codes from the code buffer.  We check for this
  104. ** condition whenever we get a CLEAR code, and if so, we get the code
  105. ** via the good old rd_dcode() routine.
  106. **
  107. ** One other problem with the code buffer approach is that we might get
  108. ** a CLEAR code in the middle of the buffer.  This means that the next
  109. ** code is only 9 bits, but we have probably already unpacked a number of
  110. ** larger codes from the input into the buffer before we discover this.
  111. ** So we remember where (in the input buffer) the code buffer was filled
  112. ** from, and when a CLEAR code is encountered in the buffer (not the
  113. ** sentinel at the end) we back up the bit_offset pointer in the input
  114. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  115. */
  116.  
  117. #define CODEBUF_SIZE 64       /* must be multiple of 8, experiment for best */
  118. static unsigned codebuf[CODEBUF_SIZE+1];        /* code buffer */
  119. static unsigned *codebufp;         /* code buffer pointer */
  120. static unsigned *codebuflim;        /* code buffer limit */
  121.         /* bit offset within the input buffer of where the code buffer began */
  122. static unsigned codebufoffset;
  123.  
  124. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  125.                                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  126. static unsigned bit_offset;    /* note this only allows max 8K input buffer!!*/
  127.  
  128. #ifdef UNBUF_IO
  129. #define        BLOCKFILE        int
  130. #define        BLOCKREAD        read
  131. #define        BLOCKWRITE        blockwrite
  132. int read PARMS ((int, VOIDPTR, unsigned));
  133. int write PARMS ((int, VOIDPTR, unsigned));
  134. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  135. #else
  136. #define        BLOCKFILE        ZOOFILE
  137. #define        BLOCKREAD        zooread
  138. #define        BLOCKWRITE        zoowrite
  139. #endif /* UNBUF_IO */
  140.  
  141. static BLOCKFILE in_f, out_f;
  142.  
  143. /* rd_dcode() reads a code from the input (compressed) file and returns
  144. its value. */
  145. unsigned rd_dcode()
  146. {
  147.     register char *ptra, *ptrb;     /* miscellaneous pointers */
  148.     unsigned word;                           /* first 16 bits in buffer */
  149.     unsigned byte_offset;
  150.     char nextch;                                    /* next 8 bits in buffer */
  151.     unsigned ofs_inbyte;                   /* offset within byte */
  152.  
  153.     ofs_inbyte = bit_offset % 8;
  154.     byte_offset = bit_offset / 8;
  155.     bit_offset = bit_offset + nbits;
  156.  
  157.     assert(nbits >= 9 && nbits <= 13);
  158.  
  159.     if (byte_offset >= INBUFSIZ - 5) {
  160.         int space_left;
  161.  
  162.         assert(byte_offset >= INBUFSIZ - 5);
  163.         debug((printf ("lzd: byte_offset near end of buffer\n")))
  164.  
  165.         bit_offset = ofs_inbyte + nbits;
  166.         space_left = INBUFSIZ - byte_offset;
  167.         ptrb = byte_offset + in_buf_adr;             /* point to char */
  168.         ptra = in_buf_adr;
  169.         /* we now move the remaining characters down buffer beginning */
  170.         debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  171.         while (space_left > 0) {
  172.             *ptra++ = *ptrb++;
  173.             space_left--;
  174.         }
  175.         assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  176.         assert(space_left == 0);
  177.         if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  178.             prterror ('f', "I/O error in lzd:rd_dcode.\n");
  179.         byte_offset = 0;
  180.     }
  181.     ptra = byte_offset + in_buf_adr;
  182.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  183.     word = (unsigned char) *ptra; ptra++;
  184.     word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  185.  
  186.     nextch = *ptra;
  187.     if (ofs_inbyte != 0) {
  188.         /* shift nextch right by ofs_inbyte bits */
  189.         /* and shift those bits right into word; */
  190.         word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  191.     }
  192.     return (word & masks[nbits]);
  193. } /* rd_dcode() */
  194.  
  195. void init_dtab()
  196. {
  197.     nbits = 9;
  198.     max_code = 512;
  199.     free_code = FIRST_FREE;
  200. }
  201.  
  202. /* By making wr_dchar() a macro and calling this routine only on buffer
  203. ** full condition, we save a lot of function call overhead.
  204. ** We also use pointers instead of counters for efficiency (in the macro).
  205. */
  206. void xwr_dchar (ch)
  207. int ch;
  208. {
  209.     if (outbufp >= outbuflim) {      /* if buffer full */
  210.         if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
  211.                                                                 != outbufp - out_buf_adr)
  212.             prterror ('f', "Write error in lzd:wr_dchar.\n");
  213.         addbfcrc(out_buf_adr, outbufp - out_buf_adr);     /* update CRC */
  214.         outbufp = out_buf_adr;                         /* restore empty buffer */
  215.     }
  216.     assert(outbufp - out_buf_adr < OUTBUFSIZ);
  217.     *outbufp++ = ch;
  218. } /* wr_dchar() */
  219.  
  220.  
  221. /* Code buffer fill routines
  222. **
  223. ** We use a separate function for each code size.
  224. ** Each function unpacks 8 codes from a packed buffer (f)
  225. ** to an unpacked buffer (t)
  226. ** A lot of code space, but really speeds up bit picking.
  227. */
  228. static unsigned char f[13];    /* must be unsigned for right shifts */
  229. static unsigned t[8];
  230.  
  231. static void cb9fill ()
  232. {
  233.     t[0] = (f[0]     ) | ((f[1] &   1) << 8);
  234.     t[1] = (f[1] >> 1) | ((f[2] &   3) << 7);
  235.     t[2] = (f[