1/* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2016 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zbuild.h"
7#include "zutil.h"
8#include "inftrees.h"
9#include "inflate.h"
10#include "inffast.h"
11#include "inflate_p.h"
12#include "inffixed.h"
13#include "memcopy.h"
14#include "functable.h"
15
16/* Architecture-specific hooks. */
17#ifdef S390_DFLTCC_INFLATE
18# include "arch/s390/dfltcc_inflate.h"
19#else
20/* Memory management for the inflate state. Useful for allocating arch-specific extension blocks. */
21# define ZALLOC_STATE(strm, items, size) ZALLOC(strm, items, size)
22# define ZFREE_STATE(strm, addr) ZFREE(strm, addr)
23# define ZCOPY_STATE(dst, src, size) memcpy(dst, src, size)
24/* Memory management for the window. Useful for allocation the aligned window. */
25# define ZALLOC_WINDOW(strm, items, size) ZALLOC(strm, items, size)
26# define ZFREE_WINDOW(strm, addr) ZFREE(strm, addr)
27/* Invoked at the end of inflateResetKeep(). Useful for initializing arch-specific extension blocks. */
28# define INFLATE_RESET_KEEP_HOOK(strm) do {} while (0)
29/* Invoked at the beginning of inflatePrime(). Useful for updating arch-specific buffers. */
30# define INFLATE_PRIME_HOOK(strm, bits, value) do {} while (0)
31/* Invoked at the beginning of each block. Useful for plugging arch-specific inflation code. */
32# define INFLATE_TYPEDO_HOOK(strm, flush) do {} while (0)
33/* Returns whether zlib-ng should compute a checksum. Set to 0 if arch-specific inflation code already does that. */
34# define INFLATE_NEED_CHECKSUM(strm) 1
35/* Returns whether zlib-ng should update a window. Set to 0 if arch-specific inflation code already does that. */
36# define INFLATE_NEED_UPDATEWINDOW(strm) 1
37/* Invoked at the beginning of inflateMark(). Useful for updating arch-specific pointers and offsets. */
38# define INFLATE_MARK_HOOK(strm) do {} while (0)
39#endif
40
41/* function prototypes */
42static int inflateStateCheck(PREFIX3(stream) *strm);
43static int updatewindow(PREFIX3(stream) *strm, const unsigned char *end, uint32_t copy);
44static uint32_t syncsearch(uint32_t *have, const unsigned char *buf, uint32_t len);
45
46static int inflateStateCheck(PREFIX3(stream) *strm) {
47 struct inflate_state *state;
48 if (strm == NULL || strm->zalloc == NULL || strm->zfree == NULL)
49 return 1;
50 state = (struct inflate_state *)strm->state;
51 if (state == NULL || state->strm != strm || state->mode < HEAD || state->mode > SYNC)
52 return 1;
53 return 0;
54}
55
56int ZEXPORT PREFIX(inflateResetKeep)(PREFIX3(stream) *strm) {
57 struct inflate_state *state;
58
59 if (inflateStateCheck(strm))
60 return Z_STREAM_ERROR;
61 state = (struct inflate_state *)strm->state;
62 strm->total_in = strm->total_out = state->total = 0;
63 strm->msg = NULL;
64 if (state->wrap) /* to support ill-conceived Java test suite */
65 strm->adler = state->wrap & 1;
66 state->mode = HEAD;
67 state->check = functable.adler32(0L, NULL, 0);
68 state->last = 0;
69 state->havedict = 0;
70 state->flags = -1;
71 state->dmax = 32768U;
72 state->head = NULL;
73 state->hold = 0;
74 state->bits = 0;
75 state->lencode = state->distcode = state->next = state->codes;
76 state->sane = 1;
77 state->back = -1;
78 INFLATE_RESET_KEEP_HOOK(strm); /* hook for IBM Z DFLTCC */
79 Tracev((stderr, "inflate: reset\n"));
80 return Z_OK;
81}
82
83int ZEXPORT PREFIX(inflateReset)(PREFIX3(stream) *strm) {
84 struct inflate_state *state;
85
86 if (inflateStateCheck(strm))
87 return Z_STREAM_ERROR;
88 state = (struct inflate_state *)strm->state;
89 state->wsize = 0;
90 state->whave = 0;
91 state->wnext = 0;
92 return PREFIX(inflateResetKeep)(strm);
93}
94
95int ZEXPORT PREFIX(inflateReset2)(PREFIX3(stream) *strm, int windowBits) {
96 int wrap;
97 struct inflate_state *state;
98
99 /* get the state */
100 if (inflateStateCheck(strm))
101 return Z_STREAM_ERROR;
102 state = (struct inflate_state *)strm->state;
103
104 /* extract wrap request from windowBits parameter */
105 if (windowBits < 0) {
106 wrap = 0;
107 windowBits = -windowBits;
108 } else {
109 wrap = (windowBits >> 4) + 5;
110#ifdef GUNZIP
111 if (windowBits < 48)
112 windowBits &= 15;
113#endif
114 }
115
116 /* set number of window bits, free window if different */
117 if (windowBits && (windowBits < 8 || windowBits > 15))
118 return Z_STREAM_ERROR;
119 if (state->window != NULL && state->wbits != (unsigned)windowBits) {
120 ZFREE_WINDOW(strm, state->window);
121 state->window = NULL;
122 }
123
124 /* update state and reset the rest of it */
125 state->wrap = wrap;
126 state->wbits = (unsigned)windowBits;
127 return PREFIX(inflateReset)(strm);
128}
129
130int ZEXPORT PREFIX(inflateInit2_)(PREFIX3(stream) *strm, int windowBits, const char *version, int stream_size) {
131 int ret;
132 struct inflate_state *state;
133
134 if (version == NULL || version[0] != PREFIX2(VERSION)[0] || stream_size != (int)(sizeof(PREFIX3(stream))))
135 return Z_VERSION_ERROR;
136 if (strm == NULL)
137 return Z_STREAM_ERROR;
138 strm->msg = NULL; /* in case we return an error */
139 if (strm->zalloc == NULL) {
140 strm->zalloc = zng_calloc;
141 strm->opaque = NULL;
142 }
143 if (strm->zfree == NULL)
144 strm->zfree = zng_cfree;
145 state = (struct inflate_state *) ZALLOC_STATE(strm, 1, sizeof(struct inflate_state));
146 if (state == NULL)
147 return Z_MEM_ERROR;
148 Tracev((stderr, "inflate: allocated\n"));
149 strm->state = (struct internal_state *)state;
150 state->strm = strm;
151 state->window = NULL;
152 state->mode = HEAD; /* to pass state test in inflateReset2() */
153 ret = PREFIX(inflateReset2)(strm, windowBits);
154 if (ret != Z_OK) {
155 ZFREE_STATE(strm, state);
156 strm->state = NULL;
157 }
158 return ret;
159}
160
161int ZEXPORT PREFIX(inflateInit_)(PREFIX3(stream) *strm, const char *version, int stream_size) {
162 return PREFIX(inflateInit2_)(strm, DEF_WBITS, version, stream_size);
163}
164
165int ZEXPORT PREFIX(inflatePrime)(PREFIX3(stream) *strm, int bits, int value) {
166 struct inflate_state *state;
167
168 if (inflateStateCheck(strm))
169 return Z_STREAM_ERROR;
170 INFLATE_PRIME_HOOK(strm, bits, value); /* hook for IBM Z DFLTCC */
171 state = (struct inflate_state *)strm->state;
172 if (bits < 0) {
173 state->hold = 0;
174 state->bits = 0;
175 return Z_OK;
176 }
177 if (bits > 16 || state->bits + (unsigned int)bits > 32)
178 return Z_STREAM_ERROR;
179 value &= (1L << bits) - 1;
180 state->hold += (unsigned)value << state->bits;
181 state->bits += (unsigned int)bits;
182 return Z_OK;
183}
184
185/*
186 Return state with length and distance decoding tables and index sizes set to
187 fixed code decoding. This returns fixed tables from inffixed.h.
188 */
189
190void ZLIB_INTERNAL fixedtables(struct inflate_state *state) {
191 state->lencode = lenfix;
192 state->lenbits = 9;
193 state->distcode = distfix;
194 state->distbits = 5;
195}
196
197int ZLIB_INTERNAL inflate_ensure_window(struct inflate_state *state)
198{
199 /* if it hasn't been done already, allocate space for the window */
200 if (state->window == NULL) {
201#ifdef INFFAST_CHUNKSIZE
202 unsigned wsize = 1U << state->wbits;
203 state->window = (unsigned char *) ZALLOC_WINDOW(state->strm, wsize + INFFAST_CHUNKSIZE, sizeof(unsigned char));
204 if (state->window == Z_NULL)
205 return 1;
206 memset(state->window + wsize, 0, INFFAST_CHUNKSIZE);
207#else
208 state->window = (unsigned char *) ZALLOC_WINDOW(state->strm, 1U << state->wbits, sizeof(unsigned char));
209 if (state->window == NULL)
210 return 1;
211#endif
212 }
213
214 /* if window not in use yet, initialize */
215 if (state->wsize == 0) {
216 state->wsize = 1U << state->wbits;
217 state->wnext = 0;
218 state->whave = 0;
219 }
220
221 return 0;
222}
223
224/*
225 Update the window with the last wsize (normally 32K) bytes written before
226 returning. If window does not exist yet, create it. This is only called
227 when a window is already in use, or when output has been written during this
228 inflate call, but the end of the deflate stream has not been reached yet.
229 It is also called to create a window for dictionary data when a dictionary
230 is loaded.
231
232 Providing output buffers larger than 32K to inflate() should provide a speed
233 advantage, since only the last 32K of output is copied to the sliding window
234 upon return from inflate(), and since all distances after the first 32K of
235 output will fall in the output data, making match copies simpler and faster.
236 The advantage may be dependent on the size of the processor's data caches.
237 */
238static int updatewindow(PREFIX3(stream) *strm, const unsigned char *end, uint32_t copy) {
239 struct inflate_state *state;
240 uint32_t dist;
241
242 state = (struct inflate_state *)strm->state;
243
244 if (inflate_ensure_window(state)) return 1;
245
246 /* copy state->wsize or less output bytes into the circular window */
247 if (copy >= state->wsize) {
248 memcpy(state->window, end - state->wsize, state->wsize);
249 state->wnext = 0;
250 state->whave = state->wsize;
251 } else {
252 dist = state->wsize - state->wnext;
253 if (dist > copy)
254 dist = copy;
255 memcpy(state->window + state->wnext, end - copy, dist);
256 copy -= dist;
257 if (copy) {
258 memcpy(state->window, end - copy, copy);
259 state->wnext = copy;
260 state->whave = state->wsize;
261 } else {
262 state->wnext += dist;
263 if (state->wnext == state->wsize)
264 state->wnext = 0;
265 if (state->whave < state->wsize)
266 state->whave += dist;
267 }
268 }
269 return 0;
270}
271
272
273/*
274 Private macros for inflate()
275 Look in inflate_p.h for macros shared with inflateBack()
276*/
277
278/* Get a byte of input into the bit accumulator, or return from inflate() if there is no input available. */
279#define PULLBYTE() \
280 do { \
281 if (have == 0) goto inf_leave; \
282 have--; \
283 hold += ((unsigned)(*next++) << bits); \
284 bits += 8; \
285 } while (0)
286
287/*
288 inflate() uses a state machine to process as much input data and generate as
289 much output data as possible before returning. The state machine is
290 structured roughly as follows:
291
292 for (;;) switch (state) {
293 ...
294 case STATEn:
295 if (not enough input data or output space to make progress)
296 return;
297 ... make progress ...
298 state = STATEm;
299 break;
300 ...
301 }
302
303 so when inflate() is called again, the same case is attempted again, and
304 if the appropriate resources are provided, the machine proceeds to the
305 next state. The NEEDBITS() macro is usually the way the state evaluates
306 whether it can proceed or should return. NEEDBITS() does the return if
307 the requested bits are not available. The typical use of the BITS macros
308 is:
309
310 NEEDBITS(n);
311 ... do something with BITS(n) ...
312 DROPBITS(n);
313
314 where NEEDBITS(n) either returns from inflate() if there isn't enough
315 input left to load n bits into the accumulator, or it continues. BITS(n)
316 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
317 the low n bits off the accumulator. INITBITS() clears the accumulator
318 and sets the number of available bits to zero. BYTEBITS() discards just
319 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
320 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
321
322 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
323 if there is no input available. The decoding of variable length codes uses
324 PULLBYTE() directly in order to pull just enough bytes to decode the next
325 code, and no more.
326
327 Some states loop until they get enough input, making sure that enough
328 state information is maintained to continue the loop where it left off
329 if NEEDBITS() returns in the loop. For example, want, need, and keep
330 would all have to actually be part of the saved state in case NEEDBITS()
331 returns:
332
333 case STATEw:
334 while (want < need) {
335 NEEDBITS(n);
336 keep[want++] = BITS(n);
337 DROPBITS(n);
338 }
339 state = STATEx;
340 case STATEx:
341
342 As shown above, if the next state is also the next case, then the break
343 is omitted.
344
345 A state may also return if there is not enough output space available to
346 complete that state. Those states are copying stored data, writing a
347 literal byte, and copying a matching string.
348
349 When returning, a "goto inf_leave" is used to update the total counters,
350 update the check value, and determine whether any progress has been made
351 during that inflate() call in order to return the proper return code.
352 Progress is defined as a change in either strm->avail_in or strm->avail_out.
353 When there is a window, goto inf_leave will update the window with the last
354 output written. If a goto inf_leave occurs in the middle of decompression
355 and there is no window currently, goto inf_leave will create one and copy
356 output to the window for the next call of inflate().
357
358 In this implementation, the flush parameter of inflate() only affects the
359 return code (per zlib.h). inflate() always writes as much as possible to
360 strm->next_out, given the space available and the provided input--the effect
361 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
362 the allocation of and copying into a sliding window until necessary, which
363 provides the effect documented in zlib.h for Z_FINISH when the entire input
364 stream available. So the only thing the flush parameter actually does is:
365 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
366 will return Z_BUF_ERROR if it has not reached the end of the stream.
367 */
368
369int ZEXPORT PREFIX(inflate)(PREFIX3(stream) *strm, int flush) {
370 struct inflate_state *state;
371 const unsigned char *next; /* next input */
372 unsigned char *put; /* next output */
373 unsigned have, left; /* available input and output */
374 uint32_t hold; /* bit buffer */
375 unsigned bits; /* bits in bit buffer */
376 uint32_t in, out; /* save starting available input and output */
377 unsigned copy; /* number of stored or match bytes to copy */
378 unsigned char *from; /* where to copy match bytes from */
379 code here; /* current decoding table entry */
380 code last; /* parent table entry */
381 unsigned len; /* length to copy for repeats, bits to drop */
382 int ret; /* return code */
383#ifdef GUNZIP
384 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
385#endif
386 static const uint16_t order[19] = /* permutation of code lengths */
387 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
388
389 if (inflateStateCheck(strm) || strm->next_out == NULL ||
390 (strm->next_in == NULL && strm->avail_in != 0))
391 return Z_STREAM_ERROR;
392
393 state = (struct inflate_state *)strm->state;
394 if (state->mode == TYPE) /* skip check */
395 state->mode = TYPEDO;
396 LOAD();
397 in = have;
398 out = left;
399 ret = Z_OK;
400 for (;;)
401 switch (state->mode) {
402 case HEAD:
403 if (state->wrap == 0) {
404 state->mode = TYPEDO;
405 break;
406 }
407 NEEDBITS(16);
408#ifdef GUNZIP
409 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
410 if (state->wbits == 0)
411 state->wbits = 15;
412 state->check = PREFIX(crc32)(0L, NULL, 0);
413 CRC2(state->check, hold);
414 INITBITS();
415 state->mode = FLAGS;
416 break;
417 }
418 if (state->head != NULL)
419 state->head->done = -1;
420 if (!(state->wrap & 1) || /* check if zlib header allowed */
421#else
422 if (
423#endif
424 ((BITS(8) << 8) + (hold >> 8)) % 31) {
425 strm->msg = (char *)"incorrect header check";
426 state->mode = BAD;
427 break;
428 }
429 if (BITS(4) != Z_DEFLATED) {
430 strm->msg = (char *)"unknown compression method";
431 state->mode = BAD;
432 break;
433 }
434 DROPBITS(4);
435 len = BITS(4) + 8;
436 if (state->wbits == 0)
437 state->wbits = len;
438 if (len > 15 || len > state->wbits) {
439 strm->msg = (char *)"invalid window size";
440 state->mode = BAD;
441 break;
442 }
443 state->dmax = 1U << len;
444 state->flags = 0; /* indicate zlib header */
445 Tracev((stderr, "inflate: zlib header ok\n"));
446 strm->adler = state->check = functable.adler32(0L, NULL, 0);
447 state->mode = hold & 0x200 ? DICTID : TYPE;
448 INITBITS();
449 break;
450#ifdef GUNZIP
451
452 case FLAGS:
453 NEEDBITS(16);
454 state->flags = (int)(hold);
455 if ((state->flags & 0xff) != Z_DEFLATED) {
456 strm->msg = (char *)"unknown compression method";
457 state->mode = BAD;
458 break;
459 }
460 if (state->flags & 0xe000) {
461 strm->msg = (char *)"unknown header flags set";
462 state->mode = BAD;
463 break;
464 }
465 if (state->head != NULL)
466 state->head->text = (int)((hold >> 8) & 1);
467 if ((state->flags & 0x0200) && (state->wrap & 4))
468 CRC2(state->check, hold);
469 INITBITS();
470 state->mode = TIME;
471
472 case TIME:
473 NEEDBITS(32);
474 if (state->head != NULL)
475 state->head->time = hold;
476 if ((state->flags & 0x0200) && (state->wrap & 4))
477 CRC4(state->check, hold);
478 INITBITS();
479 state->mode = OS;
480
481 case OS:
482 NEEDBITS(16);
483 if (state->head != NULL) {
484 state->head->xflags = (int)(hold & 0xff);
485 state->head->os = (int)(hold >> 8);
486 }
487 if ((state->flags & 0x0200) && (state->wrap & 4))
488 CRC2(state->check, hold);
489 INITBITS();
490 state->mode = EXLEN;
491
492 case EXLEN:
493 if (state->flags & 0x0400) {
494 NEEDBITS(16);
495 state->length = (uint16_t)hold;
496 if (state->head != NULL)
497 state->head->extra_len = (uint16_t)hold;
498 if ((state->flags & 0x0200) && (state->wrap & 4))
499 CRC2(state->check, hold);
500 INITBITS();
501 } else if (state->head != NULL) {
502 state->head->extra = NULL;
503 }
504 state->mode = EXTRA;
505
506 case EXTRA:
507 if (state->flags & 0x0400) {
508 copy = state->length;
509 if (copy > have)
510 copy = have;
511 if (copy) {
512 if (state->head != NULL &&
513 state->head->extra != NULL) {
514 len = state->head->extra_len - state->length;
515 memcpy(state->head->extra + len, next,
516 len + copy > state->head->extra_max ?
517 state->head->extra_max - len : copy);
518 }
519 if ((state->flags & 0x0200) && (state->wrap & 4))
520 state->check = PREFIX(crc32)(state->check, next, copy);
521 have -= copy;
522 next += copy;
523 state->length -= copy;
524 }
525 if (state->length)
526 goto inf_leave;
527 }
528 state->length = 0;
529 state->mode = NAME;
530
531 case NAME:
532 if (state->flags & 0x0800) {
533 if (have == 0) goto inf_leave;
534 copy = 0;
535 do {
536 len = (unsigned)(next[copy++]);
537 if (state->head != NULL && state->head->name != NULL && state->length < state->head->name_max)
538 state->head->name[state->length++] = (unsigned char)len;
539 } while (len && copy < have);
540 if ((state->flags & 0x0200) && (state->wrap & 4))
541 state->check = PREFIX(crc32)(state->check, next, copy);
542 have -= copy;
543 next += copy;
544 if (len)
545 goto inf_leave;
546 } else if (state->head != NULL) {
547 state->head->name = NULL;
548 }
549 state->length = 0;
550 state->mode = COMMENT;
551
552 case COMMENT:
553 if (state->flags & 0x1000) {
554 if (have == 0) goto inf_leave;
555 copy = 0;
556 do {
557 len = (unsigned)(next[copy++]);
558 if (state->head != NULL && state->head->comment != NULL
559 && state->length < state->head->comm_max)
560 state->head->comment[state->length++] = (unsigned char)len;
561 } while (len && copy < have);
562 if ((state->flags & 0x0200) && (state->wrap & 4))
563 state->check = PREFIX(crc32)(state->check, next, copy);
564 have -= copy;
565 next += copy;
566 if (len)
567 goto inf_leave;
568 } else if (state->head != NULL) {
569 state->head->comment = NULL;
570 }
571 state->mode = HCRC;
572
573 case HCRC:
574 if (state->flags & 0x0200) {
575 NEEDBITS(16);
576 if ((state->wrap & 4) && hold != (state->check & 0xffff)) {
577 strm->msg = (char *)"header crc mismatch";
578 state->mode = BAD;
579 break;
580 }
581 INITBITS();
582 }
583 if (state->head != NULL) {
584 state->head->hcrc = (int)((state->flags >> 9) & 1);
585 state->head->done = 1;
586 }
587 strm->adler = state->check = PREFIX(crc32)(0L, NULL, 0);
588 state->mode = TYPE;
589 break;
590#endif
591 case DICTID:
592 NEEDBITS(32);
593 strm->adler = state->check = ZSWAP32(hold);
594 INITBITS();
595 state->mode = DICT;
596
597 case DICT:
598 if (state->havedict == 0) {
599 RESTORE();
600 return Z_NEED_DICT;
601 }
602 strm->adler = state->check = functable.adler32(0L, NULL, 0);
603 state->mode = TYPE;
604
605 case TYPE:
606 if (flush == Z_BLOCK || flush == Z_TREES)
607 goto inf_leave;
608
609 case TYPEDO:
610 /* determine and dispatch block type */
611 INFLATE_TYPEDO_HOOK(strm, flush); /* hook for IBM Z DFLTCC */
612 if (state->last) {
613 BYTEBITS();
614 state->mode = CHECK;
615 break;
616 }
617 NEEDBITS(3);
618 state->last = BITS(1);
619 DROPBITS(1);
620 switch (BITS(2)) {
621 case 0: /* stored block */
622 Tracev((stderr, "inflate: stored block%s\n", state->last ? " (last)" : ""));
623 state->mode = STORED;
624 break;
625 case 1: /* fixed block */
626 fixedtables(state);
627 Tracev((stderr, "inflate: fixed codes block%s\n", state->last ? " (last)" : ""));
628 state->mode = LEN_; /* decode codes */
629 if (flush == Z_TREES) {
630 DROPBITS(2);
631 goto inf_leave;
632 }
633 break;
634 case 2: /* dynamic block */
635 Tracev((stderr, "inflate: dynamic codes block%s\n", state->last ? " (last)" : ""));
636 state->mode = TABLE;
637 break;
638 case 3:
639 strm->msg = (char *)"invalid block type";
640 state->mode = BAD;
641 }
642 DROPBITS(2);
643 break;
644
645 case STORED:
646 /* get and verify stored block length */
647 BYTEBITS(); /* go to byte boundary */
648 NEEDBITS(32);
649 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
650 strm->msg = (char *)"invalid stored block lengths";
651 state->mode = BAD;
652 break;
653 }
654 state->length = (uint16_t)hold;
655 Tracev((stderr, "inflate: stored length %u\n", state->length));
656 INITBITS();
657 state->mode = COPY_;
658 if (flush == Z_TREES)
659 goto inf_leave;
660
661 case COPY_:
662 state->mode = COPY;
663
664 case COPY:
665 /* copy stored block from input to output */
666 copy = state->length;
667 if (copy) {
668 if (copy > have) copy = have;
669 if (copy > left) copy = left;
670 if (copy == 0) goto inf_leave;
671 memcpy(put, next, copy);
672 have -= copy;
673 next += copy;
674 left -= copy;
675 put += copy;
676 state->length -= copy;
677 break;
678 }
679 Tracev((stderr, "inflate: stored end\n"));
680 state->mode = TYPE;
681 break;
682
683 case TABLE:
684 /* get dynamic table entries descriptor */
685 NEEDBITS(14);
686 state->nlen = BITS(5) + 257;
687 DROPBITS(5);
688 state->ndist = BITS(5) + 1;
689 DROPBITS(5);
690 state->ncode = BITS(4) + 4;
691 DROPBITS(4);
692#ifndef PKZIP_BUG_WORKAROUND
693 if (state->nlen > 286 || state->ndist > 30) {
694 strm->msg = (char *)"too many length or distance symbols";
695 state->mode = BAD;
696 break;
697 }
698#endif
699 Tracev((stderr, "inflate: table sizes ok\n"));
700 state->have = 0;
701 state->mode = LENLENS;
702
703 case LENLENS:
704 /* get code length code lengths (not a typo) */
705 while (state->have < state->ncode) {
706 NEEDBITS(3);
707 state->lens[order[state->have++]] = (uint16_t)BITS(3);
708 DROPBITS(3);
709 }
710 while (state->have < 19)
711 state->lens[order[state->have++]] = 0;
712 state->next = state->codes;
713 state->lencode = (const code *)(state->next);
714 state->lenbits = 7;
715 ret = zng_inflate_table(CODES, state->lens, 19, &(state->next), &(state->lenbits), state->work);
716 if (ret) {
717 strm->msg = (char *)"invalid code lengths set";
718 state->mode = BAD;
719 break;
720 }
721 Tracev((stderr, "inflate: code lengths ok\n"));
722 state->have = 0;
723 state->mode = CODELENS;
724
725 case CODELENS:
726 /* get length and distance code code lengths */
727 while (state->have < state->nlen + state->ndist) {
728 for (;;) {
729 here = state->lencode[BITS(state->lenbits)];
730 if (here.bits <= bits) break;
731 PULLBYTE();
732 }
733 if (here.val < 16) {
734 DROPBITS(here.bits);
735 state->lens[state->have++] = here.val;
736 } else {
737 if (here.val == 16) {
738 NEEDBITS(here.bits + 2);
739 DROPBITS(here.bits);
740 if (state->have == 0) {
741 strm->msg = (char *)"invalid bit length repeat";
742 state->mode = BAD;
743 break;
744 }
745 len = state->lens[state->have - 1];
746 copy = 3 + BITS(2);
747 DROPBITS(2);
748 } else if (here.val == 17) {
749 NEEDBITS(here.bits + 3);
750 DROPBITS(here.bits);
751 len = 0;
752 copy = 3 + BITS(3);
753 DROPBITS(3);
754 } else {
755 NEEDBITS(here.bits + 7);
756 DROPBITS(here.bits);
757 len = 0;
758 copy = 11 + BITS(7);
759 DROPBITS(7);
760 }
761 if (state->have + copy > state->nlen + state->ndist) {
762 strm->msg = (char *)"invalid bit length repeat";
763 state->mode = BAD;
764 break;
765 }
766 while (copy) {
767 --copy;
768 state->lens[state->have++] = (uint16_t)len;
769 }
770 }
771 }
772
773 /* handle error breaks in while */
774 if (state->mode == BAD)
775 break;
776
777 /* check for end-of-block code (better have one) */
778 if (state->lens[256] == 0) {
779 strm->msg = (char *)"invalid code -- missing end-of-block";
780 state->mode = BAD;
781 break;
782 }
783
784 /* build code tables -- note: do not change the lenbits or distbits
785 values here (9 and 6) without reading the comments in inftrees.h
786 concerning the ENOUGH constants, which depend on those values */
787 state->next = state->codes;
788 state->lencode = (const code *)(state->next);
789 state->lenbits = 9;
790 ret = zng_inflate_table(LENS, state->lens, state->nlen, &(state->next), &(state->lenbits), state->work);
791 if (ret) {
792 strm->msg = (char *)"invalid literal/lengths set";
793 state->mode = BAD;
794 break;
795 }
796 state->distcode = (const code *)(state->next);
797 state->distbits = 6;
798 ret = zng_inflate_table(DISTS, state->lens + state->nlen, state->ndist,
799 &(state->next), &(state->distbits), state->work);
800 if (ret) {
801 strm->msg = (char *)"invalid distances set";
802 state->mode = BAD;
803 break;
804 }
805 Tracev((stderr, "inflate: codes ok\n"));
806 state->mode = LEN_;
807 if (flush == Z_TREES)
808 goto inf_leave;
809
810 case LEN_:
811 state->mode = LEN;
812
813 case LEN:
814 /* use inflate_fast() if we have enough input and output */
815 if (have >= INFLATE_FAST_MIN_HAVE &&
816 left >= INFLATE_FAST_MIN_LEFT) {
817 RESTORE();
818 zng_inflate_fast(strm, out);
819 LOAD();
820 if (state->mode == TYPE)
821 state->back = -1;
822 break;
823 }
824 state->back = 0;
825
826 /* get a literal, length, or end-of-block code */
827 for (;;) {
828 here = state->lencode[BITS(state->lenbits)];
829 if (here.bits <= bits)
830 break;
831 PULLBYTE();
832 }
833 if (here.op && (here.op & 0xf0) == 0) {
834 last = here;
835 for (;;) {
836 here = state->lencode[last.val + (BITS(last.bits + last.op) >> last.bits)];
837 if ((unsigned)last.bits + (unsigned)here.bits <= bits)
838 break;
839 PULLBYTE();
840 }
841 DROPBITS(last.bits);
842 state->back += last.bits;
843 }
844 DROPBITS(here.bits);
845 state->back += here.bits;
846 state->length = here.val;
847
848 /* process literal */
849 if ((int)(here.op) == 0) {
850 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
851 "inflate: literal '%c'\n" :
852 "inflate: literal 0x%02x\n", here.val));
853 state->mode = LIT;
854 break;
855 }
856
857 /* process end of block */
858 if (here.op & 32) {
859 Tracevv((stderr, "inflate: end of block\n"));
860 state->back = -1;
861 state->mode = TYPE;
862 break;
863 }
864
865 /* invalid code */
866 if (here.op & 64) {
867 strm->msg = (char *)"invalid literal/length code";
868 state->mode = BAD;
869 break;
870 }
871
872 /* length code */
873 state->extra = (here.op & 15);
874 state->mode = LENEXT;
875
876 case LENEXT:
877 /* get extra bits, if any */
878 if (state->extra) {
879 NEEDBITS(state->extra);
880 state->length += BITS(state->extra);
881 DROPBITS(state->extra);
882 state->back += state->extra;
883 }
884 Tracevv((stderr, "inflate: length %u\n", state->length));
885 state->was = state->length;
886 state->mode = DIST;
887
888 case DIST:
889 /* get distance code */
890 for (;;) {
891 here = state->distcode[BITS(state->distbits)];
892 if (here.bits <= bits)
893 break;
894 PULLBYTE();
895 }
896 if ((here.op & 0xf0) == 0) {
897 last = here;
898 for (;;) {
899 here = state->distcode[last.val + (BITS(last.bits + last.op) >> last.bits)];
900 if ((unsigned)last.bits + (unsigned)here.bits <= bits)
901 break;
902 PULLBYTE();
903 }
904 DROPBITS(last.bits);
905 state->back += last.bits;
906 }
907 DROPBITS(here.bits);
908 state->back += here.bits;
909 if (here.op & 64) {
910 strm->msg = (char *)"invalid distance code";
911 state->mode = BAD;
912 break;
913 }
914 state->offset = here.val;
915 state->extra = (here.op & 15);
916 state->mode = DISTEXT;
917
918 case DISTEXT:
919 /* get distance extra bits, if any */
920 if (state->extra) {
921 NEEDBITS(state->extra);
922 state->offset += BITS(state->extra);
923 DROPBITS(state->extra);
924 state->back += state->extra;
925 }
926#ifdef INFLATE_STRICT
927 if (state->offset > state->dmax) {
928 strm->msg = (char *)"invalid distance too far back";
929 state->mode = BAD;
930 break;
931 }
932#endif
933 Tracevv((stderr, "inflate: distance %u\n", state->offset));
934 state->mode = MATCH;
935
936 case MATCH:
937 /* copy match from window to output */
938 if (left == 0) goto inf_leave;
939 copy = out - left;
940 if (state->offset > copy) { /* copy from window */
941 copy = state->offset - copy;
942 if (copy > state->whave) {
943 if (state->sane) {
944 strm->msg = (char *)"invalid distance too far back";
945 state->mode = BAD;
946 break;
947 }
948#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
949 Trace((stderr, "inflate.c too far\n"));
950 copy -= state->whave;
951 if (copy > state->length)
952 copy = state->length;
953 if (copy > left)
954 copy = left;
955 left -= copy;
956 state->length -= copy;
957 do {
958 *put++ = 0;
959 } while (--copy);
960 if (state->length == 0)
961 state->mode = LEN;
962 break;
963#endif
964 }
965 if (copy > state->wnext) {
966 copy -= state->wnext;
967 from = state->window + (state->wsize - copy);
968 } else {
969 from = state->window + (state->wnext - copy);
970 }
971 if (copy > state->length)
972 copy = state->length;
973 if (copy > left)
974 copy = left;
975#if defined(INFFAST_CHUNKSIZE)
976 put = chunkcopysafe(put, from, copy, put + left);
977#else
978 if (copy >= sizeof(uint64_t))
979 put = chunk_memcpy(put, from, copy);
980 else
981 put = copy_bytes(put, from, copy);
982#endif
983 } else { /* copy from output */
984 copy = state->length;
985 if (copy > left)
986 copy = left;
987#if defined(INFFAST_CHUNKSIZE)
988 put = chunkmemsetsafe(put, state->offset, copy, left);
989#else
990 if (copy >= sizeof(uint64_t))
991 put = chunk_memset(put, put - state->offset, state->offset, copy);
992 else
993 put = set_bytes(put, put - state->offset, state->offset, copy);
994#endif
995 }
996 left -= copy;
997 state->length -= copy;
998 if (state->length == 0)
999 state->mode = LEN;
1000 break;
1001
1002 case LIT:
1003 if (left == 0)
1004 goto inf_leave;
1005 *put++ = (unsigned char)(state->length);
1006 left--;
1007 state->mode = LEN;
1008 break;
1009
1010 case CHECK:
1011 if (state->wrap) {
1012 NEEDBITS(32);
1013 out -= left;
1014 strm->total_out += out;
1015 state->total += out;
1016 if (INFLATE_NEED_CHECKSUM(strm) && (state->wrap & 4) && out)
1017 strm->adler = state->check = UPDATE(state->check, put - out, out);
1018 out = left;
1019 if ((state->wrap & 4) && (
1020#ifdef GUNZIP
1021 state->flags ? hold :
1022#endif
1023 ZSWAP32(hold)) != state->check) {
1024 strm->msg = (char *)"incorrect data check";
1025 state->mode = BAD;
1026 break;
1027 }
1028 INITBITS();
1029 Tracev((stderr, "inflate: check matches trailer\n"));
1030 }
1031#ifdef GUNZIP
1032 state->mode = LENGTH;
1033
1034 case LENGTH:
1035 if (state->wrap && state->flags) {
1036 NEEDBITS(32);
1037 if ((state->wrap & 4) && hold != (state->total & 0xffffffff)) {
1038 strm->msg = (char *)"incorrect length check";
1039 state->mode = BAD;
1040 break;
1041 }
1042 INITBITS();
1043 Tracev((stderr, "inflate: length matches trailer\n"));
1044 }
1045#endif
1046 state->mode = DONE;
1047
1048 case DONE:
1049 /* inflate stream terminated properly */
1050 ret = Z_STREAM_END;
1051 goto inf_leave;
1052
1053 case BAD:
1054 ret = Z_DATA_ERROR;
1055 goto inf_leave;
1056
1057 case MEM:
1058 return Z_MEM_ERROR;
1059
1060 case SYNC:
1061
1062 default: /* can't happen, but makes compilers happy */
1063 return Z_STREAM_ERROR;
1064 }
1065
1066 /*
1067 Return from inflate(), updating the total counts and the check value.
1068 If there was no progress during the inflate() call, return a buffer
1069 error. Call updatewindow() to create and/or update the window state.
1070 Note: a memory error from inflate() is non-recoverable.
1071 */
1072 inf_leave:
1073 RESTORE();
1074 if (INFLATE_NEED_UPDATEWINDOW(strm) &&
1075 (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1076 (state->mode < CHECK || flush != Z_FINISH)))) {
1077 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1078 state->mode = MEM;
1079 return Z_MEM_ERROR;
1080 }
1081 }
1082 in -= strm->avail_in;
1083 out -= strm->avail_out;
1084 strm->total_in += in;
1085 strm->total_out += out;
1086 state->total += out;
1087 if (INFLATE_NEED_CHECKSUM(strm) && (state->wrap & 4) && out)
1088 strm->adler = state->check = UPDATE(state->check, strm->next_out - out, out);
1089 strm->data_type = (int)state->bits + (state->last ? 64 : 0) +
1090 (state->mode == TYPE ? 128 : 0) + (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1091 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1092 ret = Z_BUF_ERROR;
1093 return ret;
1094}
1095
1096int ZEXPORT PREFIX(inflateEnd)(PREFIX3(stream) *strm) {
1097 struct inflate_state *state;
1098 if (inflateStateCheck(strm))
1099 return Z_STREAM_ERROR;
1100 state = (struct inflate_state *)strm->state;
1101 if (state->window != NULL)
1102 ZFREE_WINDOW(strm, state->window);
1103 ZFREE_STATE(strm, strm->state);
1104 strm->state = NULL;
1105 Tracev((stderr, "inflate: end\n"));
1106 return Z_OK;
1107}
1108
1109int ZEXPORT PREFIX(inflateGetDictionary)(PREFIX3(stream) *strm, unsigned char *dictionary, unsigned int *dictLength) {
1110 struct inflate_state *state;
1111
1112 /* check state */
1113 if (inflateStateCheck(strm))
1114 return Z_STREAM_ERROR;
1115 state = (struct inflate_state *)strm->state;
1116
1117 /* copy dictionary */
1118 if (state->whave && dictionary != NULL) {
1119 memcpy(dictionary, state->window + state->wnext, state->whave - state->wnext);
1120 memcpy(dictionary + state->whave - state->wnext, state->window, state->wnext);
1121 }
1122 if (dictLength != NULL)
1123 *dictLength = state->whave;
1124 return Z_OK;
1125}
1126
1127int ZEXPORT PREFIX(inflateSetDictionary)(PREFIX3(stream) *strm, const unsigned char *dictionary, unsigned int dictLength) {
1128 struct inflate_state *state;
1129 unsigned long dictid;
1130 int ret;
1131
1132 /* check state */
1133 if (inflateStateCheck(strm))
1134 return Z_STREAM_ERROR;
1135 state = (struct inflate_state *)strm->state;
1136 if (state->wrap != 0 && state->mode != DICT)
1137 return Z_STREAM_ERROR;
1138
1139 /* check for correct dictionary identifier */
1140 if (state->mode == DICT) {
1141 dictid = functable.adler32(0L, NULL, 0);
1142 dictid = functable.adler32(dictid, dictionary, dictLength);
1143 if (dictid != state->check)
1144 return Z_DATA_ERROR;
1145 }
1146
1147 /* copy dictionary to window using updatewindow(), which will amend the
1148 existing dictionary if appropriate */
1149 ret = updatewindow(strm, dictionary + dictLength, dictLength);
1150 if (ret) {
1151 state->mode = MEM;
1152 return Z_MEM_ERROR;
1153 }
1154 state->havedict = 1;
1155 Tracev((stderr, "inflate: dictionary set\n"));
1156 return Z_OK;
1157}
1158
1159int ZEXPORT PREFIX(inflateGetHeader)(PREFIX3(stream) *strm, PREFIX(gz_headerp) head) {
1160 struct inflate_state *state;
1161
1162 /* check state */
1163 if (inflateStateCheck(strm))
1164 return Z_STREAM_ERROR;
1165 state = (struct inflate_state *)strm->state;
1166 if ((state->wrap & 2) == 0)
1167 return Z_STREAM_ERROR;
1168
1169 /* save header structure */
1170 state->head = head;
1171 head->done = 0;
1172 return Z_OK;
1173}
1174
1175/*
1176 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1177 or when out of input. When called, *have is the number of pattern bytes
1178 found in order so far, in 0..3. On return *have is updated to the new
1179 state. If on return *have equals four, then the pattern was found and the
1180 return value is how many bytes were read including the last byte of the
1181 pattern. If *have is less than four, then the pattern has not been found
1182 yet and the return value is len. In the latter case, syncsearch() can be
1183 called again with more data and the *have state. *have is initialized to
1184 zero for the first call.
1185 */
1186static uint32_t syncsearch(uint32_t *have, const unsigned char *buf, uint32_t len) {
1187 uint32_t got;
1188 uint32_t next;
1189
1190 got = *have;
1191 next = 0;
1192 while (next < len && got < 4) {
1193 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1194 got++;
1195 else if (buf[next])
1196 got = 0;
1197 else
1198 got = 4 - got;
1199 next++;
1200 }
1201 *have = got;
1202 return next;
1203}
1204
1205int ZEXPORT PREFIX(inflateSync)(PREFIX3(stream) *strm) {
1206 unsigned len; /* number of bytes to look at or looked at */
1207 int flags; /* temporary to save header status */
1208 size_t in, out; /* temporary to save total_in and total_out */
1209 unsigned char buf[4]; /* to restore bit buffer to byte string */
1210 struct inflate_state *state;
1211
1212 /* check parameters */
1213 if (inflateStateCheck(strm))
1214 return Z_STREAM_ERROR;
1215 state = (struct inflate_state *)strm->state;
1216 if (strm->avail_in == 0 && state->bits < 8)
1217 return Z_BUF_ERROR;
1218
1219 /* if first time, start search in bit buffer */
1220 if (state->mode != SYNC) {
1221 state->mode = SYNC;
1222 state->hold <<= state->bits & 7;
1223 state->bits -= state->bits & 7;
1224 len = 0;
1225 while (state->bits >= 8) {
1226 buf[len++] = (unsigned char)(state->hold);
1227 state->hold >>= 8;
1228 state->bits -= 8;
1229 }
1230 state->have = 0;
1231 syncsearch(&(state->have), buf, len);
1232 }
1233
1234 /* search available input */
1235 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1236 strm->avail_in -= len;
1237 strm->next_in += len;
1238 strm->total_in += len;
1239
1240 /* return no joy or set up to restart inflate() on a new block */
1241 if (state->have != 4)
1242 return Z_DATA_ERROR;
1243 if (state->flags == -1)
1244 state->wrap = 0; /* if no header yet, treat as raw */
1245 else
1246 state->wrap &= ~4; /* no point in computing a check value now */
1247 flags = state->flags;
1248 in = strm->total_in;
1249 out = strm->total_out;
1250 PREFIX(inflateReset)(strm);
1251 strm->total_in = in;
1252 strm->total_out = out;
1253 state->flags = flags;
1254 state->mode = TYPE;
1255 return Z_OK;
1256}
1257
1258/*
1259 Returns true if inflate is currently at the end of a block generated by
1260 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1261 implementation to provide an additional safety check. PPP uses
1262 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1263 block. When decompressing, PPP checks that at the end of input packet,
1264 inflate is waiting for these length bytes.
1265 */
1266int ZEXPORT PREFIX(inflateSyncPoint)(PREFIX3(stream) *strm) {
1267 struct inflate_state *state;
1268
1269 if (inflateStateCheck(strm))
1270 return Z_STREAM_ERROR;
1271 state = (struct inflate_state *)strm->state;
1272 return state->mode == STORED && state->bits == 0;
1273}
1274
1275int ZEXPORT PREFIX(inflateCopy)(PREFIX3(stream) *dest, PREFIX3(stream) *source) {
1276 struct inflate_state *state;
1277 struct inflate_state *copy;
1278 unsigned char *window;
1279 unsigned wsize;
1280
1281 /* check input */
1282 if (inflateStateCheck(source) || dest == NULL)
1283 return Z_STREAM_ERROR;
1284 state = (struct inflate_state *)source->state;
1285
1286 /* allocate space */
1287 copy = (struct inflate_state *)
1288 ZALLOC_STATE(source, 1, sizeof(struct inflate_state));
1289 if (copy == NULL)
1290 return Z_MEM_ERROR;
1291 window = NULL;
1292 if (state->window != NULL) {
1293 window = (unsigned char *) ZALLOC_WINDOW(source, 1U << state->wbits, sizeof(unsigned char));
1294 if (window == NULL) {
1295 ZFREE_STATE(source, copy);
1296 return Z_MEM_ERROR;
1297 }
1298 }
1299
1300 /* copy state */
1301 memcpy((void *)dest, (void *)source, sizeof(PREFIX3(stream)));
1302 ZCOPY_STATE((void *)copy, (void *)state, sizeof(struct inflate_state));
1303 copy->strm = dest;
1304 if (state->lencode >= state->codes && state->lencode <= state->codes + ENOUGH - 1) {
1305 copy->lencode = copy->codes + (state->lencode - state->codes);
1306 copy->distcode = copy->codes + (state->distcode - state->codes);
1307 }
1308 copy->next = copy->codes + (state->next - state->codes);
1309 if (window != NULL) {
1310 wsize = 1U << state->wbits;
1311 memcpy(window, state->window, wsize);
1312 }
1313 copy->window = window;
1314 dest->state = (struct internal_state *)copy;
1315 return Z_OK;
1316}
1317
1318int ZEXPORT PREFIX(inflateUndermine)(PREFIX3(stream) *strm, int subvert) {
1319 struct inflate_state *state;
1320
1321 if (inflateStateCheck(strm))
1322 return Z_STREAM_ERROR;
1323 state = (struct inflate_state *)strm->state;
1324#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1325 state->sane = !subvert;
1326 return Z_OK;
1327#else
1328 (void)subvert;
1329 state->sane = 1;
1330 return Z_DATA_ERROR;
1331#endif
1332}
1333
1334int ZEXPORT PREFIX(inflateValidate)(PREFIX3(stream) *strm, int check) {
1335 struct inflate_state *state;
1336
1337 if (inflateStateCheck(strm))
1338 return Z_STREAM_ERROR;
1339 state = (struct inflate_state *)strm->state;
1340 if (check && state->wrap)
1341 state->wrap |= 4;
1342 else
1343 state->wrap &= ~4;
1344 return Z_OK;
1345}
1346
1347long ZEXPORT PREFIX(inflateMark)(PREFIX3(stream) *strm) {
1348 struct inflate_state *state;
1349
1350 if (inflateStateCheck(strm))
1351 return -65536;
1352 INFLATE_MARK_HOOK(strm); /* hook for IBM Z DFLTCC */
1353 state = (struct inflate_state *)strm->state;
1354 return ((long)(state->back) << 16) + (state->mode == COPY ? state->length :
1355 (state->mode == MATCH ? state->was - state->length : 0));
1356}
1357
1358unsigned long ZEXPORT PREFIX(inflateCodesUsed)(PREFIX3(stream) *strm) {
1359 struct inflate_state *state;
1360 if (strm == NULL || strm->state == NULL)
1361 return (unsigned long)-1;
1362 state = (struct inflate_state *)strm->state;
1363 return (unsigned long)(state->next - state->codes);
1364}
1365