1 /* $NetBSD: infback.c,v 1.2 2006/01/27 00:45:27 christos Exp $ */
2
3 /* infback.c -- inflate using a call-back interface
4 * Copyright (C) 1995-2005 Mark Adler
5 * For conditions of distribution and use, see copyright notice in zlib.h
6 */
7
8 /*
9 This code is largely copied from inflate.c. Normally either infback.o or
10 inflate.o would be linked into an application--not both. The interface
11 with inffast.c is retained so that optimized assembler-coded versions of
12 inflate_fast() can be used with either inflate.c or infback.c.
13 */
14
15 #include "zutil.h"
16 #include "inftrees.h"
17 #include "inflate.h"
18 #include "inffast.h"
19
20 /* function prototypes */
21 local void fixedtables OF((struct inflate_state FAR *state));
22
23 /*
24 strm provides memory allocation functions in zalloc and zfree, or
25 Z_NULL to use the library memory allocation functions.
26
27 windowBits is in the range 8..15, and window is a user-supplied
28 window and output buffer that is 2**windowBits bytes.
29 */
inflateBackInit_(strm,windowBits,window,version,stream_size)30 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
31 z_streamp strm;
32 int windowBits;
33 unsigned char FAR *window;
34 const char *version;
35 int stream_size;
36 {
37 struct inflate_state FAR *state;
38
39 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
40 stream_size != (int)(sizeof(z_stream)))
41 return Z_VERSION_ERROR;
42 if (strm == Z_NULL || window == Z_NULL ||
43 windowBits < 8 || windowBits > 15)
44 return Z_STREAM_ERROR;
45 strm->msg = Z_NULL; /* in case we return an error */
46 if (strm->zalloc == (alloc_func)0) {
47 strm->zalloc = zcalloc;
48 strm->opaque = (voidpf)0;
49 }
50 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
51 state = (struct inflate_state FAR *)ZALLOC(strm, 1,
52 sizeof(struct inflate_state));
53 if (state == Z_NULL) return Z_MEM_ERROR;
54 Tracev((stderr, "inflate: allocated\n"));
55 strm->state = (struct internal_state FAR *)state;
56 state->dmax = 32768U;
57 state->wbits = windowBits;
58 state->wsize = 1U << windowBits;
59 state->window = window;
60 state->write = 0;
61 state->whave = 0;
62 return Z_OK;
63 }
64
65 /*
66 Return state with length and distance decoding tables and index sizes set to
67 fixed code decoding. Normally this returns fixed tables from inffixed.h.
68 If BUILDFIXED is defined, then instead this routine builds the tables the
69 first time it's called, and returns those tables the first time and
70 thereafter. This reduces the size of the code by about 2K bytes, in
71 exchange for a little execution time. However, BUILDFIXED should not be
72 used for threaded applications, since the rewriting of the tables and virgin
73 may not be thread-safe.
74 */
fixedtables(state)75 local void fixedtables(state)
76 struct inflate_state FAR *state;
77 {
78 #ifdef BUILDFIXED
79 static int virgin = 1;
80 static code *lenfix, *distfix;
81 static code fixed[544];
82
83 /* build fixed huffman tables if first call (may not be thread safe) */
84 if (virgin) {
85 unsigned sym, bits;
86 static code *next;
87
88 /* literal/length table */
89 sym = 0;
90 while (sym < 144) state->lens[sym++] = 8;
91 while (sym < 256) state->lens[sym++] = 9;
92 while (sym < 280) state->lens[sym++] = 7;
93 while (sym < 288) state->lens[sym++] = 8;
94 next = fixed;
95 lenfix = next;
96 bits = 9;
97 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
98
99 /* distance table */
100 sym = 0;
101 while (sym < 32) state->lens[sym++] = 5;
102 distfix = next;
103 bits = 5;
104 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
105
106 /* do this just once */
107 virgin = 0;
108 }
109 #else /* !BUILDFIXED */
110 # include "inffixed.h"
111 #endif /* BUILDFIXED */
112 state->lencode = lenfix;
113 state->lenbits = 9;
114 state->distcode = distfix;
115 state->distbits = 5;
116 }
117
118 /* Macros for inflateBack(): */
119
120 /* Load returned state from inflate_fast() */
121 #define LOAD() \
122 do { \
123 put = strm->next_out; \
124 left = strm->avail_out; \
125 next = strm->next_in; \
126 have = strm->avail_in; \
127 hold = state->hold; \
128 bits = state->bits; \
129 } while (0)
130
131 /* Set state from registers for inflate_fast() */
132 #define RESTORE() \
133 do { \
134 strm->next_out = put; \
135 strm->avail_out = left; \
136 strm->next_in = next; \
137 strm->avail_in = have; \
138 state->hold = hold; \
139 state->bits = bits; \
140 } while (0)
141
142 /* Clear the input bit accumulator */
143 #define INITBITS() \
144 do { \
145 hold = 0; \
146 bits = 0; \
147 } while (0)
148
149 /* Assure that some input is available. If input is requested, but denied,
150 then return a Z_BUF_ERROR from inflateBack(). */
151 #define PULL() \
152 do { \
153 if (have == 0) { \
154 have = in(in_desc, &next); \
155 if (have == 0) { \
156 next = Z_NULL; \
157 ret = Z_BUF_ERROR; \
158 goto inf_leave; \
159 } \
160 } \
161 } while (0)
162
163 /* Get a byte of input into the bit accumulator, or return from inflateBack()
164 with an error if there is no input available. */
165 #define PULLBYTE() \
166 do { \
167 PULL(); \
168 have--; \
169 hold += (unsigned long)(*next++) << bits; \
170 bits += 8; \
171 } while (0)
172
173 /* Assure that there are at least n bits in the bit accumulator. If there is
174 not enough available input to do that, then return from inflateBack() with
175 an error. */
176 #define NEEDBITS(n) \
177 do { \
178 while (bits < (unsigned)(n)) \
179 PULLBYTE(); \
180 } while (0)
181
182 /* Return the low n bits of the bit accumulator (n < 16) */
183 #define BITS(n) \
184 ((unsigned)hold & ((1U << (n)) - 1))
185
186 /* Remove n bits from the bit accumulator */
187 #define DROPBITS(n) \
188 do { \
189 hold >>= (n); \
190 bits -= (unsigned)(n); \
191 } while (0)
192
193 /* Remove zero to seven bits as needed to go to a byte boundary */
194 #define BYTEBITS() \
195 do { \
196 hold >>= bits & 7; \
197 bits -= bits & 7; \
198 } while (0)
199
200 /* Assure that some output space is available, by writing out the window
201 if it's full. If the write fails, return from inflateBack() with a
202 Z_BUF_ERROR. */
203 #define ROOM() \
204 do { \
205 if (left == 0) { \
206 put = state->window; \
207 left = state->wsize; \
208 state->whave = left; \
209 if (out(out_desc, put, left)) { \
210 ret = Z_BUF_ERROR; \
211 goto inf_leave; \
212 } \
213 } \
214 } while (0)
215
216 /*
217 strm provides the memory allocation functions and window buffer on input,
218 and provides information on the unused input on return. For Z_DATA_ERROR
219 returns, strm will also provide an error message.
220
221 in() and out() are the call-back input and output functions. When
222 inflateBack() needs more input, it calls in(). When inflateBack() has
223 filled the window with output, or when it completes with data in the
224 window, it calls out() to write out the data. The application must not
225 change the provided input until in() is called again or inflateBack()
226 returns. The application must not change the window/output buffer until
227 inflateBack() returns.
228
229 in() and out() are called with a descriptor parameter provided in the
230 inflateBack() call. This parameter can be a structure that provides the
231 information required to do the read or write, as well as accumulated
232 information on the input and output such as totals and check values.
233
234 in() should return zero on failure. out() should return non-zero on
235 failure. If either in() or out() fails, than inflateBack() returns a
236 Z_BUF_ERROR. strm->next_in can be checked for Z_NULL to see whether it
237 was in() or out() that caused in the error. Otherwise, inflateBack()
238 returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
239 error, or Z_MEM_ERROR if it could not allocate memory for the state.
240 inflateBack() can also return Z_STREAM_ERROR if the input parameters
241 are not correct, i.e. strm is Z_NULL or the state was not initialized.
242 */
inflateBack(strm,in,in_desc,out,out_desc)243 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
244 z_streamp strm;
245 in_func in;
246 void FAR *in_desc;
247 out_func out;
248 void FAR *out_desc;
249 {
250 struct inflate_state FAR *state;
251 unsigned char FAR *next; /* next input */
252 unsigned char FAR *put; /* next output */
253 unsigned have, left; /* available input and output */
254 unsigned long hold; /* bit buffer */
255 unsigned bits; /* bits in bit buffer */
256 unsigned copy; /* number of stored or match bytes to copy */
257 unsigned char FAR *from; /* where to copy match bytes from */
258 code this; /* current decoding table entry */
259 code last; /* parent table entry */
260 unsigned len; /* length to copy for repeats, bits to drop */
261 int ret; /* return code */
262 static const unsigned short order[19] = /* permutation of code lengths */
263 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
264
265 /* Check that the strm exists and that the state was initialized */
266 if (strm == Z_NULL || strm->state == Z_NULL)
267 return Z_STREAM_ERROR;
268 state = (struct inflate_state FAR *)strm->state;
269
270 /* Reset the state */
271 strm->msg = Z_NULL;
272 state->mode = TYPE;
273 state->last = 0;
274 state->whave = 0;
275 next = strm->next_in;
276 have = next != Z_NULL ? strm->avail_in : 0;
277 hold = 0;
278 bits = 0;
279 put = state->window;
280 left = state->wsize;
281
282 /* Inflate until end of block marked as last */
283 for (;;)
284 switch (state->mode) {
285 case TYPE:
286 /* determine and dispatch block type */
287 if (state->last) {
288 BYTEBITS();
289 state->mode = DONE;
290 break;
291 }
292 NEEDBITS(3);
293 state->last = BITS(1);
294 DROPBITS(1);
295 switch (BITS(2)) {
296 case 0: /* stored block */
297 Tracev((stderr, "inflate: stored block%s\n",
298 state->last ? " (last)" : ""));
299 state->mode = STORED;
300 break;
301 case 1: /* fixed block */
302 fixedtables(state);
303 Tracev((stderr, "inflate: fixed codes block%s\n",
304 state->last ? " (last)" : ""));
305 state->mode = LEN; /* decode codes */
306 break;
307 case 2: /* dynamic block */
308 Tracev((stderr, "inflate: dynamic codes block%s\n",
309 state->last ? " (last)" : ""));
310 state->mode = TABLE;
311 break;
312 case 3:
313 strm->msg = __UNCONST("invalid block type");
314 state->mode = BAD;
315 }
316 DROPBITS(2);
317 break;
318
319 case STORED:
320 /* get and verify stored block length */
321 BYTEBITS(); /* go to byte boundary */
322 NEEDBITS(32);
323 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
324 strm->msg = __UNCONST("invalid stored block lengths");
325 state->mode = BAD;
326 break;
327 }
328 state->length = (unsigned)hold & 0xffff;
329 Tracev((stderr, "inflate: stored length %u\n",
330 state->length));
331 INITBITS();
332
333 /* copy stored block from input to output */
334 while (state->length != 0) {
335 copy = state->length;
336 PULL();
337 ROOM();
338 if (copy > have) copy = have;
339 if (copy > left) copy = left;
340 zmemcpy(put, next, copy);
341 have -= copy;
342 next += copy;
343 left -= copy;
344 put += copy;
345 state->length -= copy;
346 }
347 Tracev((stderr, "inflate: stored end\n"));
348 state->mode = TYPE;
349 break;
350
351 case TABLE:
352 /* get dynamic table entries descriptor */
353 NEEDBITS(14);
354 state->nlen = BITS(5) + 257;
355 DROPBITS(5);
356 state->ndist = BITS(5) + 1;
357 DROPBITS(5);
358 state->ncode = BITS(4) + 4;
359 DROPBITS(4);
360 #ifndef PKZIP_BUG_WORKAROUND
361 if (state->nlen > 286 || state->ndist > 30) {
362 strm->msg = __UNCONST("too many length or distance symbols");
363 state->mode = BAD;
364 break;
365 }
366 #endif
367 Tracev((stderr, "inflate: table sizes ok\n"));
368
369 /* get code length code lengths (not a typo) */
370 state->have = 0;
371 while (state->have < state->ncode) {
372 NEEDBITS(3);
373 state->lens[order[state->have++]] = (unsigned short)BITS(3);
374 DROPBITS(3);
375 }
376 while (state->have < 19)
377 state->lens[order[state->have++]] = 0;
378 state->next = state->codes;
379 state->lencode = (code const FAR *)(state->next);
380 state->lenbits = 7;
381 ret = inflate_table(CODES, state->lens, 19, &(state->next),
382 &(state->lenbits), state->work);
383 if (ret) {
384 strm->msg = __UNCONST("invalid code lengths set");
385 state->mode = BAD;
386 break;
387 }
388 Tracev((stderr, "inflate: code lengths ok\n"));
389
390 /* get length and distance code code lengths */
391 state->have = 0;
392 while (state->have < state->nlen + state->ndist) {
393 for (;;) {
394 this = state->lencode[BITS(state->lenbits)];
395 if ((unsigned)(this.bits) <= bits) break;
396 PULLBYTE();
397 }
398 if (this.val < 16) {
399 NEEDBITS(this.bits);
400 DROPBITS(this.bits);
401 state->lens[state->have++] = this.val;
402 }
403 else {
404 if (this.val == 16) {
405 NEEDBITS(this.bits + 2);
406 DROPBITS(this.bits);
407 if (state->have == 0) {
408 strm->msg = __UNCONST("invalid bit length repeat");
409 state->mode = BAD;
410 break;
411 }
412 len = (unsigned)(state->lens[state->have - 1]);
413 copy = 3 + BITS(2);
414 DROPBITS(2);
415 }
416 else if (this.val == 17) {
417 NEEDBITS(this.bits + 3);
418 DROPBITS(this.bits);
419 len = 0;
420 copy = 3 + BITS(3);
421 DROPBITS(3);
422 }
423 else {
424 NEEDBITS(this.bits + 7);
425 DROPBITS(this.bits);
426 len = 0;
427 copy = 11 + BITS(7);
428 DROPBITS(7);
429 }
430 if (state->have + copy > state->nlen + state->ndist) {
431 strm->msg = __UNCONST("invalid bit length repeat");
432 state->mode = BAD;
433 break;
434 }
435 while (copy--)
436 state->lens[state->have++] = (unsigned short)len;
437 }
438 }
439
440 /* handle error breaks in while */
441 if (state->mode == BAD) break;
442
443 /* build code tables */
444 state->next = state->codes;
445 state->lencode = (code const FAR *)(state->next);
446 state->lenbits = 9;
447 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
448 &(state->lenbits), state->work);
449 if (ret) {
450 strm->msg = __UNCONST("invalid literal/lengths set");
451 state->mode = BAD;
452 break;
453 }
454 state->distcode = (code const FAR *)(state->next);
455 state->distbits = 6;
456 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
457 &(state->next), &(state->distbits), state->work);
458 if (ret) {
459 strm->msg = __UNCONST("invalid distances set");
460 state->mode = BAD;
461 break;
462 }
463 Tracev((stderr, "inflate: codes ok\n"));
464 state->mode = LEN;
465
466 case LEN:
467 /* use inflate_fast() if we have enough input and output */
468 if (have >= 6 && left >= 258) {
469 RESTORE();
470 if (state->whave < state->wsize)
471 state->whave = state->wsize - left;
472 inflate_fast(strm, state->wsize);
473 LOAD();
474 break;
475 }
476
477 /* get a literal, length, or end-of-block code */
478 for (;;) {
479 this = state->lencode[BITS(state->lenbits)];
480 if ((unsigned)(this.bits) <= bits) break;
481 PULLBYTE();
482 }
483 if (this.op && (this.op & 0xf0) == 0) {
484 last = this;
485 for (;;) {
486 this = state->lencode[last.val +
487 (BITS(last.bits + last.op) >> last.bits)];
488 if ((unsigned)(last.bits + this.bits) <= bits) break;
489 PULLBYTE();
490 }
491 DROPBITS(last.bits);
492 }
493 DROPBITS(this.bits);
494 state->length = (unsigned)this.val;
495
496 /* process literal */
497 if (this.op == 0) {
498 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
499 "inflate: literal '%c'\n" :
500 "inflate: literal 0x%02x\n", this.val));
501 ROOM();
502 *put++ = (unsigned char)(state->length);
503 left--;
504 state->mode = LEN;
505 break;
506 }
507
508 /* process end of block */
509 if (this.op & 32) {
510 Tracevv((stderr, "inflate: end of block\n"));
511 state->mode = TYPE;
512 break;
513 }
514
515 /* invalid code */
516 if (this.op & 64) {
517 strm->msg = __UNCONST("invalid literal/length code");
518 state->mode = BAD;
519 break;
520 }
521
522 /* length code -- get extra bits, if any */
523 state->extra = (unsigned)(this.op) & 15;
524 if (state->extra != 0) {
525 NEEDBITS(state->extra);
526 state->length += BITS(state->extra);
527 DROPBITS(state->extra);
528 }
529 Tracevv((stderr, "inflate: length %u\n", state->length));
530
531 /* get distance code */
532 for (;;) {
533 this = state->distcode[BITS(state->distbits)];
534 if ((unsigned)(this.bits) <= bits) break;
535 PULLBYTE();
536 }
537 if ((this.op & 0xf0) == 0) {
538 last = this;
539 for (;;) {
540 this = state->distcode[last.val +
541 (BITS(last.bits + last.op) >> last.bits)];
542 if ((unsigned)(last.bits + this.bits) <= bits) break;
543 PULLBYTE();
544 }
545 DROPBITS(last.bits);
546 }
547 DROPBITS(this.bits);
548 if (this.op & 64) {
549 strm->msg = __UNCONST("invalid distance code");
550 state->mode = BAD;
551 break;
552 }
553 state->offset = (unsigned)this.val;
554
555 /* get distance extra bits, if any */
556 state->extra = (unsigned)(this.op) & 15;
557 if (state->extra != 0) {
558 NEEDBITS(state->extra);
559 state->offset += BITS(state->extra);
560 DROPBITS(state->extra);
561 }
562 if (state->offset > state->wsize - (state->whave < state->wsize ?
563 left : 0)) {
564 strm->msg = __UNCONST("invalid distance too far back");
565 state->mode = BAD;
566 break;
567 }
568 Tracevv((stderr, "inflate: distance %u\n", state->offset));
569
570 /* copy match from window to output */
571 do {
572 ROOM();
573 copy = state->wsize - state->offset;
574 if (copy < left) {
575 from = put + copy;
576 copy = left - copy;
577 }
578 else {
579 from = put - state->offset;
580 copy = left;
581 }
582 if (copy > state->length) copy = state->length;
583 state->length -= copy;
584 left -= copy;
585 do {
586 *put++ = *from++;
587 } while (--copy);
588 } while (state->length != 0);
589 break;
590
591 case DONE:
592 /* inflate stream terminated properly -- write leftover output */
593 ret = Z_STREAM_END;
594 if (left < state->wsize) {
595 if (out(out_desc, state->window, state->wsize - left))
596 ret = Z_BUF_ERROR;
597 }
598 goto inf_leave;
599
600 case BAD:
601 ret = Z_DATA_ERROR;
602 goto inf_leave;
603
604 default: /* can't happen, but makes compilers happy */
605 ret = Z_STREAM_ERROR;
606 goto inf_leave;
607 }
608
609 /* Return unused input */
610 inf_leave:
611 strm->next_in = next;
612 strm->avail_in = have;
613 return ret;
614 }
615
inflateBackEnd(strm)616 int ZEXPORT inflateBackEnd(strm)
617 z_streamp strm;
618 {
619 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
620 return Z_STREAM_ERROR;
621 ZFREE(strm, strm->state);
622 strm->state = Z_NULL;
623 Tracev((stderr, "inflate: end\n"));
624 return Z_OK;
625 }
626