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