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