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