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