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