1/* infback.c -- inflate using a call-back interface
2 * Copyright (C) 1995-2016 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 This code is largely copied from inflate.c. Normally either infback.o or
8 inflate.o would be linked into an application--not both. The interface
9 with inffast.c is retained so that optimized assembler-coded versions of
10 inflate_fast() can be used with either inflate.c or infback.c.
11 */
12
13#include "zbuild.h"
14#include "zutil.h"
15#include "inftrees.h"
16#include "inflate.h"
17#include "inffast.h"
18#include "inflate_p.h"
19#include "functable.h"
20
21/*
22 strm provides memory allocation functions in zalloc and zfree, or
23 NULL to use the library memory allocation functions.
24
25 windowBits is in the range 8..15, and window is a user-supplied
26 window and output buffer that is 2**windowBits bytes.
27 */
28int32_t Z_EXPORT PREFIX(inflateBackInit_)(PREFIX3(stream) *strm, int32_t windowBits, uint8_t *window,
29 const char *version, int32_t stream_size) {
30 struct inflate_state *state;
31
32 if (version == NULL || version[0] != PREFIX2(VERSION)[0] || stream_size != (int)(sizeof(PREFIX3(stream))))
33 return Z_VERSION_ERROR;
34 if (strm == NULL || window == NULL || windowBits < 8 || windowBits > 15)
35 return Z_STREAM_ERROR;
36 strm->msg = NULL; /* in case we return an error */
37 if (strm->zalloc == NULL) {
38 strm->zalloc = zng_calloc;
39 strm->opaque = NULL;
40 }
41 if (strm->zfree == NULL)
42 strm->zfree = zng_cfree;
43 state = (struct inflate_state *) ZALLOC(strm, 1, sizeof(struct inflate_state));
44 if (state == NULL)
45 return Z_MEM_ERROR;
46 Tracev((stderr, "inflate: allocated\n"));
47 strm->state = (struct internal_state *)state;
48 state->dmax = 32768U;
49 state->wbits = (unsigned int)windowBits;
50 state->wsize = 1U << windowBits;
51 state->window = window;
52 state->wnext = 0;
53 state->whave = 0;
54 state->chunksize = functable.chunksize();
55 return Z_OK;
56}
57
58/*
59 Private macros for inflateBack()
60 Look in inflate_p.h for macros shared with inflate()
61*/
62
63/* Assure that some input is available. If input is requested, but denied,
64 then return a Z_BUF_ERROR from inflateBack(). */
65#define PULL() \
66 do { \
67 if (have == 0) { \
68 have = in(in_desc, &next); \
69 if (have == 0) { \
70 next = NULL; \
71 ret = Z_BUF_ERROR; \
72 goto inf_leave; \
73 } \
74 } \
75 } while (0)
76
77/* Get a byte of input into the bit accumulator, or return from inflateBack()
78 with an error if there is no input available. */
79#define PULLBYTE() \
80 do { \
81 PULL(); \
82 have--; \
83 hold += ((unsigned)(*next++) << bits); \
84 bits += 8; \
85 } while (0)
86
87/* Assure that some output space is available, by writing out the window
88 if it's full. If the write fails, return from inflateBack() with a
89 Z_BUF_ERROR. */
90#define ROOM() \
91 do { \
92 if (left == 0) { \
93 put = state->window; \
94 left = state->wsize; \
95 state->whave = left; \
96 if (out(out_desc, put, left)) { \
97 ret = Z_BUF_ERROR; \
98 goto inf_leave; \
99 } \
100 } \
101 } while (0)
102
103/*
104 strm provides the memory allocation functions and window buffer on input,
105 and provides information on the unused input on return. For Z_DATA_ERROR
106 returns, strm will also provide an error message.
107
108 in() and out() are the call-back input and output functions. When
109 inflateBack() needs more input, it calls in(). When inflateBack() has
110 filled the window with output, or when it completes with data in the
111 window, it calls out() to write out the data. The application must not
112 change the provided input until in() is called again or inflateBack()
113 returns. The application must not change the window/output buffer until
114 inflateBack() returns.
115
116 in() and out() are called with a descriptor parameter provided in the
117 inflateBack() call. This parameter can be a structure that provides the
118 information required to do the read or write, as well as accumulated
119 information on the input and output such as totals and check values.
120
121 in() should return zero on failure. out() should return non-zero on
122 failure. If either in() or out() fails, than inflateBack() returns a
123 Z_BUF_ERROR. strm->next_in can be checked for NULL to see whether it
124 was in() or out() that caused in the error. Otherwise, inflateBack()
125 returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
126 error, or Z_MEM_ERROR if it could not allocate memory for the state.
127 inflateBack() can also return Z_STREAM_ERROR if the input parameters
128 are not correct, i.e. strm is NULL or the state was not initialized.
129 */
130int32_t Z_EXPORT PREFIX(inflateBack)(PREFIX3(stream) *strm, in_func in, void *in_desc, out_func out, void *out_desc) {
131 struct inflate_state *state;
132 z_const unsigned char *next; /* next input */
133 unsigned char *put; /* next output */
134 unsigned have, left; /* available input and output */
135 uint32_t hold; /* bit buffer */
136 unsigned bits; /* bits in bit buffer */
137 unsigned copy; /* number of stored or match bytes to copy */
138 unsigned char *from; /* where to copy match bytes from */
139 code here; /* current decoding table entry */
140 code last; /* parent table entry */
141 unsigned len; /* length to copy for repeats, bits to drop */
142 int32_t ret; /* return code */
143 static const uint16_t order[19] = /* permutation of code lengths */
144 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
145
146 /* Check that the strm exists and that the state was initialized */
147 if (strm == NULL || strm->state == NULL)
148 return Z_STREAM_ERROR;
149 state = (struct inflate_state *)strm->state;
150
151 /* Reset the state */
152 strm->msg = NULL;
153 state->mode = TYPE;
154 state->last = 0;
155 state->whave = 0;
156 next = strm->next_in;
157 have = next != NULL ? strm->avail_in : 0;
158 hold = 0;
159 bits = 0;
160 put = state->window;
161 left = state->wsize;
162
163 /* Inflate until end of block marked as last */
164 for (;;)
165 switch (state->mode) {
166 case TYPE:
167 /* determine and dispatch block type */
168 if (state->last) {
169 BYTEBITS();
170 state->mode = DONE;
171 break;
172 }
173 NEEDBITS(3);
174 state->last = BITS(1);
175 DROPBITS(1);
176 switch (BITS(2)) {
177 case 0: /* stored block */
178 Tracev((stderr, "inflate: stored block%s\n", state->last ? " (last)" : ""));
179 state->mode = STORED;
180 break;
181 case 1: /* fixed block */
182 fixedtables(state);
183 Tracev((stderr, "inflate: fixed codes block%s\n", state->last ? " (last)" : ""));
184 state->mode = LEN; /* decode codes */
185 break;
186 case 2: /* dynamic block */
187 Tracev((stderr, "inflate: dynamic codes block%s\n", state->last ? " (last)" : ""));
188 state->mode = TABLE;
189 break;
190 case 3:
191 SET_BAD("invalid block type");
192 }
193 DROPBITS(2);
194 break;
195
196 case STORED:
197 /* get and verify stored block length */
198 BYTEBITS(); /* go to byte boundary */
199 NEEDBITS(32);
200 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
201 SET_BAD("invalid stored block lengths");
202 break;
203 }
204 state->length = (uint16_t)hold;
205 Tracev((stderr, "inflate: stored length %u\n", state->length));
206 INITBITS();
207
208 /* copy stored block from input to output */
209 while (state->length != 0) {
210 copy = state->length;
211 PULL();
212 ROOM();
213 if (copy > have) copy = have;
214 if (copy > left) copy = left;
215 memcpy(dest: put, src: next, n: copy);
216 have -= copy;
217 next += copy;
218 left -= copy;
219 put += copy;
220 state->length -= copy;
221 }
222 Tracev((stderr, "inflate: stored end\n"));
223 state->mode = TYPE;
224 break;
225
226 case TABLE:
227 /* get dynamic table entries descriptor */
228 NEEDBITS(14);
229 state->nlen = BITS(5) + 257;
230 DROPBITS(5);
231 state->ndist = BITS(5) + 1;
232 DROPBITS(5);
233 state->ncode = BITS(4) + 4;
234 DROPBITS(4);
235#ifndef PKZIP_BUG_WORKAROUND
236 if (state->nlen > 286 || state->ndist > 30) {
237 SET_BAD("too many length or distance symbols");
238 break;
239 }
240#endif
241 Tracev((stderr, "inflate: table sizes ok\n"));
242 state->have = 0;
243
244 /* get code length code lengths (not a typo) */
245 while (state->have < state->ncode) {
246 NEEDBITS(3);
247 state->lens[order[state->have++]] = (uint16_t)BITS(3);
248 DROPBITS(3);
249 }
250 while (state->have < 19)
251 state->lens[order[state->have++]] = 0;
252 state->next = state->codes;
253 state->lencode = (const code *)(state->next);
254 state->lenbits = 7;
255 ret = zng_inflate_table(type: CODES, lens: state->lens, codes: 19, table: &(state->next), bits: &(state->lenbits), work: state->work);
256 if (ret) {
257 SET_BAD("invalid code lengths set");
258 break;
259 }
260 Tracev((stderr, "inflate: code lengths ok\n"));
261 state->have = 0;
262
263 /* get length and distance code code lengths */
264 while (state->have < state->nlen + state->ndist) {
265 for (;;) {
266 here = state->lencode[BITS(state->lenbits)];
267 if (here.bits <= bits) break;
268 PULLBYTE();
269 }
270 if (here.val < 16) {
271 DROPBITS(here.bits);
272 state->lens[state->have++] = here.val;
273 } else {
274 if (here.val == 16) {
275 NEEDBITS(here.bits + 2);
276 DROPBITS(here.bits);
277 if (state->have == 0) {
278 SET_BAD("invalid bit length repeat");
279 break;
280 }
281 len = state->lens[state->have - 1];
282 copy = 3 + BITS(2);
283 DROPBITS(2);
284 } else if (here.val == 17) {
285 NEEDBITS(here.bits + 3);
286 DROPBITS(here.bits);
287 len = 0;
288 copy = 3 + BITS(3);
289 DROPBITS(3);
290 } else {
291 NEEDBITS(here.bits + 7);
292 DROPBITS(here.bits);
293 len = 0;
294 copy = 11 + BITS(7);
295 DROPBITS(7);
296 }
297 if (state->have + copy > state->nlen + state->ndist) {
298 SET_BAD("invalid bit length repeat");
299 break;
300 }
301 while (copy) {
302 --copy;
303 state->lens[state->have++] = (uint16_t)len;
304 }
305 }
306 }
307
308 /* handle error breaks in while */
309 if (state->mode == BAD)
310 break;
311
312 /* check for end-of-block code (better have one) */
313 if (state->lens[256] == 0) {
314 SET_BAD("invalid code -- missing end-of-block");
315 break;
316 }
317
318 /* build code tables -- note: do not change the lenbits or distbits
319 values here (9 and 6) without reading the comments in inftrees.h
320 concerning the ENOUGH constants, which depend on those values */
321 state->next = state->codes;
322 state->lencode = (const code *)(state->next);
323 state->lenbits = 9;
324 ret = zng_inflate_table(type: LENS, lens: state->lens, codes: state->nlen, table: &(state->next), bits: &(state->lenbits), work: state->work);
325 if (ret) {
326 SET_BAD("invalid literal/lengths set");
327 break;
328 }
329 state->distcode = (const code *)(state->next);
330 state->distbits = 6;
331 ret = zng_inflate_table(type: DISTS, lens: state->lens + state->nlen, codes: state->ndist,
332 table: &(state->next), bits: &(state->distbits), work: state->work);
333 if (ret) {
334 SET_BAD("invalid distances set");
335 break;
336 }
337 Tracev((stderr, "inflate: codes ok\n"));
338 state->mode = LEN;
339
340 case LEN:
341 /* use inflate_fast() if we have enough input and output */
342 if (have >= INFLATE_FAST_MIN_HAVE &&
343 left >= INFLATE_FAST_MIN_LEFT) {
344 RESTORE();
345 if (state->whave < state->wsize)
346 state->whave = state->wsize - left;
347 zng_inflate_fast(strm, start: state->wsize);
348 LOAD();
349 break;
350 }
351
352 /* get a literal, length, or end-of-block code */
353 for (;;) {
354 here = state->lencode[BITS(state->lenbits)];
355 if (here.bits <= bits)
356 break;
357 PULLBYTE();
358 }
359 if (here.op && (here.op & 0xf0) == 0) {
360 last = here;
361 for (;;) {
362 here = state->lencode[last.val + (BITS(last.bits + last.op) >> last.bits)];
363 if ((unsigned)last.bits + (unsigned)here.bits <= bits)
364 break;
365 PULLBYTE();
366 }
367 DROPBITS(last.bits);
368 }
369 DROPBITS(here.bits);
370 state->length = here.val;
371
372 /* process literal */
373 if ((int)(here.op) == 0) {
374 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
375 "inflate: literal '%c'\n" :
376 "inflate: literal 0x%02x\n", here.val));
377 ROOM();
378 *put++ = (unsigned char)(state->length);
379 left--;
380 state->mode = LEN;
381 break;
382 }
383
384 /* process end of block */
385 if (here.op & 32) {
386 Tracevv((stderr, "inflate: end of block\n"));
387 state->mode = TYPE;
388 break;
389 }
390
391 /* invalid code */
392 if (here.op & 64) {
393 SET_BAD("invalid literal/length code");
394 break;
395 }
396
397 /* length code -- get extra bits, if any */
398 state->extra = (here.op & 15);
399 if (state->extra) {
400 NEEDBITS(state->extra);
401 state->length += BITS(state->extra);
402 DROPBITS(state->extra);
403 }
404 Tracevv((stderr, "inflate: length %u\n", state->length));
405
406 /* get distance code */
407 for (;;) {
408 here = state->distcode[BITS(state->distbits)];
409 if (here.bits <= bits)
410 break;
411 PULLBYTE();
412 }
413 if ((here.op & 0xf0) == 0) {
414 last = here;
415 for (;;) {
416 here = state->distcode[last.val + (BITS(last.bits + last.op) >> last.bits)];
417 if ((unsigned)last.bits + (unsigned)here.bits <= bits)
418 break;
419 PULLBYTE();
420 }
421 DROPBITS(last.bits);
422 }
423 DROPBITS(here.bits);
424 if (here.op & 64) {
425 SET_BAD("invalid distance code");
426 break;
427 }
428 state->offset = here.val;
429 state->extra = (here.op & 15);
430
431 /* get distance extra bits, if any */
432 if (state->extra) {
433 NEEDBITS(state->extra);
434 state->offset += BITS(state->extra);
435 DROPBITS(state->extra);
436 }
437#ifdef INFLATE_STRICT
438 if (state->offset > state->wsize - (state->whave < state->wsize ? left : 0)) {
439 SET_BAD("invalid distance too far back");
440 break;
441 }
442#endif
443 Tracevv((stderr, "inflate: distance %u\n", state->offset));
444
445 /* copy match from window to output */
446 do {
447 ROOM();
448 copy = state->wsize - state->offset;
449 if (copy < left) {
450 from = put + copy;
451 copy = left - copy;
452 } else {
453 from = put - state->offset;
454 copy = left;
455 }
456 if (copy > state->length)
457 copy = state->length;
458 state->length -= copy;
459 left -= copy;
460 do {
461 *put++ = *from++;
462 } while (--copy);
463 } while (state->length != 0);
464 break;
465
466 case DONE:
467 /* inflate stream terminated properly -- write leftover output */
468 ret = Z_STREAM_END;
469 if (left < state->wsize) {
470 if (out(out_desc, state->window, state->wsize - left))
471 ret = Z_BUF_ERROR;
472 }
473 goto inf_leave;
474
475 case BAD:
476 ret = Z_DATA_ERROR;
477 goto inf_leave;
478
479 default: /* can't happen, but makes compilers happy */
480 ret = Z_STREAM_ERROR;
481 goto inf_leave;
482 }
483
484 /* Return unused input */
485 inf_leave:
486 strm->next_in = next;
487 strm->avail_in = have;
488 return ret;
489}
490
491int32_t Z_EXPORT PREFIX(inflateBackEnd)(PREFIX3(stream) *strm) {
492 if (strm == NULL || strm->state == NULL || strm->zfree == NULL)
493 return Z_STREAM_ERROR;
494 ZFREE(strm, strm->state);
495 strm->state = NULL;
496 Tracev((stderr, "inflate: end\n"));
497 return Z_OK;
498}
499