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