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