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