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