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