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. */
rd_dcode()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
init_dtab()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 */
xwr_dchar(ch)206 void xwr_dchar (ch)
207 char 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
cb9fill()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[2] >> 2) | ((f[3] & 7) << 6);
236 t[3] = (f[3] >> 3) | ((f[4] & 15) << 5);
237 t[4] = (f[4] >> 4) | ((f[5] & 31) << 4);
238 t[5] = (f[5] >> 5) | ((f[6] & 63) << 3);
239 t[6] = (f[6] >> 6) | ((f[7] & 127) << 2);
240 t[7] = (f[7] >> 7) | ((f[8] ) << 1);
241 }
242
cb10fill()243 static void cb10fill ()
244 {
245 t[0] = (f[0] ) | ((f[1] & 3) << 8);
246 t[1] = (f[1] >> 2) | ((f[2] & 15) << 6);
247 t[2] = (f[2] >> 4) | ((f[3] & 63) << 4);
248 t[3] = (f[3] >> 6) | ((f[4] ) << 2);
249 t[4] = (f[5] ) | ((f[6] & 3) << 8);
250 t[5] = (f[6] >> 2) | ((f[7] & 15) << 6);
251 t[6] = (f[7] >> 4) | ((f[8] & 63) << 4);
252 t[7] = (f[8] >> 6) | ((f[9] ) << 2);
253 }
254
cb11fill()255 static void cb11fill ()
256 {
257 t[0] = (f[0] ) | ((f[1] & 7) << 8);
258 t[1] = (f[1] >> 3) | ((f[2] & 63) << 5);
259 t[2] = (f[2] >> 6) | (f[3] << 2) | ((f[4] & 1) << 10);
260 t[3] = (f[4] >> 1) | ((f[5] & 15) << 7);
261 t[4] = (f[5] >> 4) | ((f[6] & 127) << 4);
262 t[5] = (f[6] >> 7) | (f[7] << 1) | ((f[8] & 3) << 9);
263 t[6] = (f[8] >> 2) | ((f[9] & 31) << 6);
264 t[7] = (f[9] >> 5) | ((f[10] ) << 3);
265 }
266
cb12fill()267 static void cb12fill ()
268 {
269 t[0] = (f[0] ) | ((f[1] & 15) << 8);
270 t[1] = (f[1] >> 4) | ((f[2] ) << 4);
271 t[2] = (f[3] ) | ((f[4] & 15) << 8);
272 t[3] = (f[4] >> 4) | ((f[5] ) << 4);
273 t[4] = (f[6] ) | ((f[7] & 15) << 8);
274 t[5] = (f[7] >> 4) | ((f[8] ) << 4);
275 t[6] = (f[9] ) | ((f[10] & 15) << 8);
276 t[7] = (f[10] >> 4) | ((f[11] ) << 4);
277 }
278
cb13fill()279 static void cb13fill ()
280 {
281 t[0] = (f[0] ) | ((f[1] & 31) << 8);
282 t[1] = (f[1] >> 5) | (f[2] << 3) | ((f[3] & 3) << 11);
283 t[2] = (f[3] >> 2) | ((f[4] & 127) << 6);
284 t[3] = (f[4] >> 7) | (f[5] << 1) | ((f[6] & 15) << 9);
285 t[4] = (f[6] >> 4) | (f[7] << 4) | ((f[8] & 1) << 12);
286 t[5] = (f[8] >> 1) | ((f[9] & 63) << 7);
287 t[6] = (f[9] >> 6) | (f[10] << 2) | ((f[11] & 7) << 10);
288 t[7] = (f[11] >> 3) | (f[12] << 5);
289 }
290
291 /* vector of code buffer fill routines
292 */
293 void (*cbfillvec[]) PARMS ((void)) = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
294 cb9fill, cb10fill, cb11fill, cb12fill, cb13fill };
295
296 /* cbfill -- main code buffer fill routine
297 **
298 ** moves data from inbuf[] to f[]
299 ** then calls via vector to unpack to t[]
300 ** then moves from t[] to codebuf[]
301 ** A lot of moving around, but still faster than a lot of shifting and
302 ** masking via variables (at least on a micro -- don't know about VAXen)
303 ** Uses memcpy() for block move
304 */
305
cbfill()306 static void cbfill ()
307 {
308 char *inbp;
309 inbp = in_buf_adr + bit_offset / 8;
310 codebufp = codebuf;
311 while ( codebufp < codebuflim ) {
312 memcpy((VOIDPTR) f, inbp, nbits);
313 (*cbfillvec[nbits])();
314 memcpy((VOIDPTR) codebufp, (VOIDPTR) t, 8 * sizeof(unsigned int));
315 inbp += nbits;
316 codebufp += 8;
317 }
318 bit_offset += nbits * CODEBUF_SIZE;
319 }
320
321 /* The following is used in the KwKwK case because it's a pretty rare
322 ** case, and doing it this way avoids the overhead of remembering the
323 ** "finchar" (first input character) of every string
324 */
firstchar(code)325 static int firstchar(code) /* find first character of a code */
326 int code;
327 {
328 while ( code > 255 )
329 code = head[code];
330 return code;
331 }
332
lzd(input_f,output_f)333 int lzd(input_f, output_f)
334 BLOCKFILE input_f, output_f; /* input & output files */
335 {
336 in_f = input_f; /* make it avail to other fns */
337 out_f = output_f; /* ditto */
338 nbits = 9;
339 max_code = 512;
340 free_code = FIRST_FREE;
341 bit_offset = 0;
342 outbuflim = out_buf_adr + OUTBUFSIZ; /* setup out buffer limit */
343 outbufguard = outbuflim - 12; /* for checking avail. room in outbuf */
344 /* note must allow for as many characters as we special-case (8) */
345 /* used 12 for extra fudge factor (Rahul does it, so I can too) */
346 outbufp = out_buf_adr; /* setup output buffer ptr */
347 codebufp = codebuflim = &codebuf[CODEBUF_SIZE]; /* code buf ptr & limit */
348 *codebuflim = CLEAR; /* phony CLEAR sentinel past end of code buffer */
349
350 if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1) /* fill input buffer */
351 return(IOERR);
352 if (memflag == 0) {
353 head = (int *) ealloc((MAXMAX+10) * sizeof(int));
354 tail = (char *) ealloc((MAXMAX+10) * sizeof(char));
355 stack = (char *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
356 memflag++;
357 }
358
359 stack_pointer = stack_lim = stack + STACKSIZE; /* setup stack ptr, limit*/
360 init_dtab(); /* initialize table */
361
362 loop:
363 cur_code = *codebufp++; /* get code from code buffer */
364
365 goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
366 if (cur_code == Z_EOF) {
367 debug((printf ("lzd: Z_EOF\n")))
368
369 if (outbufp != out_buf_adr) {
370 if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
371 != outbufp - out_buf_adr)
372 prterror ('f', "Output error in lzd().\n");
373 addbfcrc(out_buf_adr, outbufp - out_buf_adr);
374
375 }
376 #ifdef FILTER
377 /* get next two bytes and put them where zoofilt can find them */
378 /* nbits known to be in range 9..13 */
379 bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
380 filt_lzd_word = rd_dcode();
381 filt_lzd_word |= (rd_dcode() << nbits);
382 filt_lzd_word &= 0xffff;
383 #endif
384 return (0);
385 }
386
387 assert(nbits >= 9 && nbits <= 13);
388
389 if (cur_code == CLEAR) { /* was it sentinel or real CLEAR ? */
390 if ( codebufp > codebuflim ) { /* it was the sentinel */
391 if ( bit_offset % 8 == 0 && /* if we're on byte boundary and */
392 /* codesize won't change before codebuf is filled and */
393 /* codebuf can be filled without running out of inbuf */
394 free_code + CODEBUF_SIZE < max_code &&
395 bit_offset / 8 + (CODEBUF_SIZE * 13 / 8) < INBUFSIZ - 10 ) {
396 codebufoffset = bit_offset; /* remember where we were when */
397 cbfill(); /* we filled the code buffer */
398 codebufp = codebuf; /* setup code buffer pointer */
399 goto loop; /* now go get codes from code buffer */
400 } /* otherwise, use rd_dcode to get code */
401 codebufp = codebuflim; /* reset codebuf ptr to sentinel */
402 cur_code = rd_dcode(); /* get code via rd_dcode() */
403 if ( cur_code != CLEAR ) /* if it's not CLEAR */
404 goto got_code; /* then go handle it */
405 } else { /* else it's really a CLEAR code, not sentinel */
406 /* reset bit_offset to get next code in input buf after CLEAR code */
407 bit_offset = codebufoffset + (codebufp - codebuf) * nbits;
408 }
409 codebufp = codebuflim; /* set code buf ptr to sentinel */
410 debug((printf ("lzd: CLEAR\n")))
411 init_dtab(); /* init decompression table, etc. */
412 old_code = cur_code = rd_dcode(); /* get next code after CLEAR */
413 if (cur_code == Z_EOF) /* special case for 0-length files */
414 goto goteof;
415 wr_dchar(cur_code); /* write it out */
416 goto loop; /* and get next code */
417 }
418
419 got_code: /* we got a code and it's not a CLEAR */
420
421 if (cur_code == Z_EOF) {
422 debug((printf ("lzd: Z_EOF\n")))
423 if (outbufp != out_buf_adr) {
424 if (BLOCKWRITE (out_f, out_buf_adr, outbufp - out_buf_adr)
425 != outbufp - out_buf_adr)
426 prterror ('f', "Output error in lzd().\n");
427 addbfcrc(out_buf_adr, outbufp - out_buf_adr);
428 }
429 return (0);
430 }
431
432 in_code = cur_code; /* save original code */
433 if (cur_code >= free_code) { /* if code not in table (k<w>k<w>k) */
434 cur_code = old_code; /* previous code becomes current */
435 /* push first character of old code */
436 *--stack_pointer = firstchar(old_code);
437 goto unwind; /* and go "unwind" the current code */
438 } /* (use general unwind because the stack isn't empty now) */
439
440 /* Unwind a code. The basic idea is to use a sort of loop-unrolling
441 ** approach to really speed up the processing by treating the codes
442 ** which represent short strings (the vast majority of codes) as
443 ** special cases. Avoid a lot of stack overflow checking safely.
444 */
445
446 if (cur_code > 255) { /* if cur_code is not atomic */
447 *--stack_pointer = tail[cur_code]; /* push its tail code */
448 cur_code = head[cur_code]; /* and replace with its head code */
449 } else { /* else 1-byte string */
450 if ( outbufp > outbufguard ) /* if outbuf near end, */
451 goto write_stack; /* write via general routine */
452 *outbufp++ = cur_code; /* we got space, put char out */
453 goto add_code; /* add code to table */
454 }
455
456 if (cur_code > 255) { /* if cur_code is not atomic */
457 *--stack_pointer = tail[cur_code]; /* push its tail code */
458 cur_code = head[cur_code]; /* and replace with its head code */
459 } else { /* else 2-byte string */
460 if ( outbufp > outbufguard ) /* if outbuf near end, */
461 goto write_stack; /* write via general routine */
462 *outbufp++ = cur_code; /* we got space, put char out, and */
463 goto move_1_char; /* go move rest of stack to outbuf */
464 }
465 if (cur_code > 255) { /* if cur_code is not atomic */
466 *--stack_pointer = tail[cur_code]; /* push its tail code */
467 cur_code = head[cur_code]; /* and replace with its head code */
468 } else { /* else 3-byte string */
469 if ( outbufp > outbufguard ) /* if outbuf near end, */
470 goto write_stack; /* write via general routine */
471 *outbufp++ = cur_code; /* we got space, put char out, and */
472 goto move_2_char; /* go move rest of stack to outbuf */
473 }
474
475 /* we handle codes representing strings of 4 thru 8 bytes similarly */
476
477 if (cur_code > 255) {
478 *--stack_pointer = tail[cur_code];
479 cur_code = head[cur_code];
480 } else { /* 4-byte string */
481 if ( outbufp > outbufguard )
482 goto write_stack;
483 *outbufp++ = cur_code;
484 goto move_3_char;
485 }
486 if (cur_code > 255) {
487 *--stack_pointer = tail[cur_code];
488 cur_code = head[cur_code];
489 } else { /* 5-byte string */
490 if ( outbufp > outbufguard )
491 goto write_stack;
492 *outbufp++ = cur_code;
493 goto move_4_char;
494 }
495 if (cur_code > 255) {
496 *--stack_pointer = tail[cur_code];
497 cur_code = head[cur_code];
498 } else { /* 6-byte string */
499 if ( outbufp > outbufguard )
500 goto write_stack;
501 *outbufp++ = cur_code;
502 goto move_5_char;
503 }
504 if (cur_code > 255) {
505 *--stack_pointer = tail[cur_code];
506 cur_code = head[cur_code];
507 } else { /* 7-byte string */
508 if ( outbufp > outbufguard )
509 goto write_stack;
510 *outbufp++ = cur_code;
511 goto move_6_char;
512 }
513 if (cur_code > 255) {
514 *--stack_pointer = tail[cur_code];
515 cur_code = head[cur_code];
516 } else { /* 8-byte string */
517 if ( outbufp > outbufguard )
518 goto write_stack;
519 *outbufp++ = cur_code;
520 goto move_7_char;
521 }
522
523 /* Here for KwKwK case and strings longer than 8 bytes */
524 /* Note we have to check stack here, but not elsewhere */
525
526 unwind:
527 while (cur_code > 255) { /* if code, not character */
528 *--stack_pointer = tail[cur_code]; /* push suffix char */
529 if (stack_pointer < stack+12)
530 prterror ('f', "Stack overflow in lzd().\n");
531 cur_code = head[cur_code]; /* head of code is new code */
532 }
533
534 /* General routine to write stack with check for output buffer full */
535
536 write_stack:
537 assert(nbits >= 9 && nbits <= 13);
538 wr_dchar(cur_code); /* write this code, don't need to stack it first */
539 while ( stack_pointer < stack_lim ) {
540 wr_dchar(*stack_pointer++);
541 }
542 goto add_code; /* now go add code to table */
543
544 /* Here to move strings from stack to output buffer */
545 /* only if we know we have enough room in output buffer */
546 /* because (outbufp <= outbufguard) */
547
548 move_7_char:
549 *outbufp++ = *stack_pointer++;
550 move_6_char:
551 *outbufp++ = *stack_pointer++;
552 move_5_char:
553 *outbufp++ = *stack_pointer++;
554 move_4_char:
555 *outbufp++ = *stack_pointer++;
556 move_3_char:
557 *outbufp++ = *stack_pointer++;
558 move_2_char:
559 *outbufp++ = *stack_pointer++;
560 move_1_char:
561 *outbufp++ = *stack_pointer++;
562
563 assert(stack_pointer == stack_lim); /* I haven't tested this! rdg */
564
565 /* add_code is now inline to avoid overhead of function call on */
566 /* each code processed */
567
568 add_code:
569 assert(nbits >= 9 && nbits <= 13);
570 assert(free_code <= MAXMAX+1);
571 tail[free_code] = cur_code; /* save suffix char */
572 head[free_code] = old_code; /* save prefix code */
573 free_code++;
574 assert(nbits >= 9 && nbits <= 13);
575 if (free_code >= max_code) {
576 if (nbits < MAXBITS) {
577 debug((printf("lzd: nbits was %d\n", nbits)))
578 nbits++;
579 assert(nbits >= 9 && nbits <= 13);
580 debug((printf("lzd: nbits now %d\n", nbits)))
581 max_code = max_code << 1; /* double max_code */
582 debug((printf("lzd: max_code now %d\n", max_code)))
583 }
584 }
585 old_code = in_code;
586
587 assert(nbits >= 9 && nbits <= 13);
588
589 goto loop;
590 } /* lzd() */
591
592 #else /* SLOW_LZD defined, so use following instead */
593
594 /*********************************************************************/
595 /* Original slower lzd(). */
596 /*********************************************************************/
597
598 /*
599 Lempel-Ziv decompression. Mostly based on Tom Pfau's assembly language
600 code. The contents of this file are hereby released to the public domain.
601 -- Rahul Dhesi 1986/11/14
602 */
603
604 #define STACKSIZE 4000
605
606 struct tabentry {
607 unsigned next;
608 char z_ch;
609 };
610
611 void init_dtab PARMS((void));
612 unsigned rd_dcode PARMS((void));
613 void wr_dchar PARMS((int));
614 void ad_dcode PARMS((void));
615
616 #ifdef FILTER
617 /* to send data back to zoofilt */
618 extern unsigned int filt_lzd_word;
619 #endif /* FILTER */
620
621
622 static unsigned stack_pointer = 0;
623 static unsigned *stack;
624
625 #define push(x) { \
626 stack[stack_pointer++] = (x); \
627 if (stack_pointer >= STACKSIZE) \
628 prterror ('f', "Stack overflow in lzd().\n");\
629 }
630 #define pop() (stack[--stack_pointer])
631
632 extern char *out_buf_adr; /* output buffer */
633 extern char *in_buf_adr; /* input buffer */
634
635 char memflag = 0; /* memory allocated? flag */
636 extern struct tabentry *table; /* hash table from lzc.c */
637 static unsigned cur_code;
638 static unsigned old_code;
639 static unsigned in_code;
640
641 static unsigned free_code;
642 static int nbits;
643 static unsigned max_code;
644
645 static char fin_char;
646 static char k;
647 static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
648 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
649 static unsigned bit_offset;
650 static unsigned output_offset;
651
652 #ifdef UNBUF_IO
653 #define BLOCKFILE int
654 #define BLOCKREAD read
655 #define BLOCKWRITE blockwrite
656 int read PARMS ((int, VOIDPTR, unsigned));
657 int write PARMS ((int, VOIDPTR, unsigned));
658 #else
659 #define BLOCKFILE ZOOFILE
660 #define BLOCKREAD zooread
661 #define BLOCKWRITE zoowrite
662 #endif /* UNBUF_IO */
663
664 static BLOCKFILE in_f, out_f;
665
lzd(input_f,output_f)666 int lzd(input_f, output_f)
667 BLOCKFILE input_f, output_f; /* input & output file handles */
668 {
669 in_f = input_f; /* make it avail to other fns */
670 out_f = output_f; /* ditto */
671 nbits = 9;
672 max_code = 512;
673 free_code = FIRST_FREE;
674 stack_pointer = 0;
675 bit_offset = 0;
676 output_offset = 0;
677
678 if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
679 return(IOERR);
680 if (memflag == 0) {
681 table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
682 stack = (unsigned *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
683 memflag++;
684 }
685
686 init_dtab(); /* initialize table */
687
688 loop:
689 cur_code = rd_dcode();
690 goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
691 if (cur_code == Z_EOF) {
692 debug((printf ("lzd: Z_EOF\n")))
693 if (output_offset != 0) {
694 if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
695 prterror ('f', "Output error in lzd().\n");
696 addbfcrc(out_buf_adr, output_offset);
697 }
698 #ifdef FILTER
699 /* get next two bytes and put them where zoofilt can find them */
700 /* nbits known to be in range 9..13 */
701 bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
702 filt_lzd_word = rd_dcode();
703 filt_lzd_word |= (rd_dcode() << nbits);
704 filt_lzd_word &= 0xffff;
705 #endif
706 return (0);
707 }
708
709 assert(nbits >= 9 && nbits <= 13);
710
711 if (cur_code == CLEAR) {
712 debug((printf ("lzd: CLEAR\n")))
713 init_dtab();
714 fin_char = k = old_code = cur_code = rd_dcode();
715 if (cur_code == Z_EOF) /* special case for 0-length files */
716 goto goteof;
717 wr_dchar(k);
718 goto loop;
719 }
720
721 in_code = cur_code;
722 if (cur_code >= free_code) { /* if code not in table (k<w>k<w>k) */
723 cur_code = old_code; /* previous code becomes current */
724 push(fin_char);
725 }
726
727 while (cur_code > 255) { /* if code, not character */
728 push(table[cur_code].z_ch); /* push suffix char */
729 cur_code = table[cur_code].next; /* <w> := <w>.code */
730 }
731
732 assert(nbits >= 9 && nbits <= 13);
733
734 k = fin_char = cur_code;
735 push(k);
736 while (stack_pointer != 0) {
737 wr_dchar(pop());
738 }
739 assert(nbits >= 9 && nbits <= 13);
740 ad_dcode();
741 old_code = in_code;
742
743 assert(nbits >= 9 && nbits <= 13);
744
745 goto loop;
746 } /* lzd() */
747
748 /* rd_dcode() reads a code from the input (compressed) file and returns
749 its value. */
rd_dcode()750 unsigned rd_dcode()
751 {
752 register char *ptra, *ptrb; /* miscellaneous pointers */
753 unsigned word; /* first 16 bits in buffer */
754 unsigned byte_offset;
755 char nextch; /* next 8 bits in buffer */
756 unsigned ofs_inbyte; /* offset within byte */
757
758 ofs_inbyte = bit_offset % 8;
759 byte_offset = bit_offset / 8;
760 bit_offset = bit_offset + nbits;
761
762 assert(nbits >= 9 && nbits <= 13);
763
764 if (byte_offset >= INBUFSIZ - 5) {
765 int space_left;
766
767 #ifdef CHECK_BREAK
768 check_break();
769 #endif
770
771 assert(byte_offset >= INBUFSIZ - 5);
772 debug((printf ("lzd: byte_offset near end of buffer\n")))
773
774 bit_offset = ofs_inbyte + nbits;
775 space_left = INBUFSIZ - byte_offset;
776 ptrb = byte_offset + in_buf_adr; /* point to char */
777 ptra = in_buf_adr;
778 /* we now move the remaining characters down buffer beginning */
779 debug((printf ("rd_dcode: space_left = %d\n", space_left)))
780 while (space_left > 0) {
781 *ptra++ = *ptrb++;
782 space_left--;
783 }
784 assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
785 assert(space_left == 0);
786 if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
787 prterror ('f', "I/O error in lzd:rd_dcode.\n");
788 byte_offset = 0;
789 }
790 ptra = byte_offset + in_buf_adr;
791 /* NOTE: "word = *((int *) ptra)" would not be independent of byte order. */
792 word = (unsigned char) *ptra; ptra++;
793 word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
794
795 nextch = *ptra;
796 if (ofs_inbyte != 0) {
797 /* shift nextch right by ofs_inbyte bits */
798 /* and shift those bits right into word; */
799 word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
800 }
801 return (word & masks[nbits]);
802 } /* rd_dcode() */
803
init_dtab()804 void init_dtab()
805 {
806 nbits = 9;
807 max_code = 512;
808 free_code = FIRST_FREE;
809 }
810
wr_dchar(ch)811 void wr_dchar (ch)
812 int ch;
813 {
814 if (output_offset >= OUTBUFSIZ) { /* if buffer full */
815 #ifdef CHECK_BREAK
816 check_break();
817 #endif
818 if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
819 prterror ('f', "Write error in lzd:wr_dchar.\n");
820 addbfcrc(out_buf_adr, output_offset); /* update CRC */
821 output_offset = 0; /* restore empty buffer */
822 }
823 assert(output_offset < OUTBUFSIZ);
824 out_buf_adr[output_offset++] = ch; /* store character */
825 } /* wr_dchar() */
826
827 /* adds a code to table */
ad_dcode()828 void ad_dcode()
829 {
830 assert(nbits >= 9 && nbits <= 13);
831 assert(free_code <= MAXMAX+1);
832 table[free_code].z_ch = k; /* save suffix char */
833 table[free_code].next = old_code; /* save prefix code */
834 free_code++;
835 assert(nbits >= 9 && nbits <= 13);
836 if (free_code >= max_code) {
837 if (nbits < MAXBITS) {
838 debug((printf("lzd: nbits was %d\n", nbits)))
839 nbits++;
840 assert(nbits >= 9 && nbits <= 13);
841 debug((printf("lzd: nbits now %d\n", nbits)))
842 max_code = max_code << 1; /* double max_code */
843 debug((printf("lzd: max_code now %d\n", max_code)))
844 }
845 }
846 }
847 #endif /* ! SLOW_LZD */
848