1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2022 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
9 * 1.2.beta0 24 Nov 2002
10 * - First version -- complete rewrite of inflate to simplify code, avoid
11 * creation of window when not needed, minimize use of window when it is
12 * needed, make inffast.c even faster, implement gzip decoding, and to
13 * improve code readability and style over the previous zlib inflate code
15 * 1.2.beta1 25 Nov 2002
16 * - Use pointers for available input and output checking in inffast.c
17 * - Remove input and output counters in inffast.c
18 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
19 * - Remove unnecessary second byte pull from length extra in inffast.c
20 * - Unroll direct copy to three copies per loop in inffast.c
22 * 1.2.beta2 4 Dec 2002
23 * - Change external routine names to reduce potential conflicts
24 * - Correct filename to inffixed.h for fixed tables in inflate.c
25 * - Make hbuf[] unsigned char to match parameter type in inflate.c
26 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
27 * to avoid negation problem on Alphas (64 bit) in inflate.c
29 * 1.2.beta3 22 Dec 2002
30 * - Add comments on state->bits assertion in inffast.c
31 * - Add comments on op field in inftrees.h
32 * - Fix bug in reuse of allocated window after inflateReset()
33 * - Remove bit fields--back to byte structure for speed
34 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
35 * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
36 * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
37 * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
38 * - Use local copies of stream next and avail values, as well as local bit
39 * buffer and bit count in inflate()--for speed when inflate_fast() not used
41 * 1.2.beta4 1 Jan 2003
42 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43 * - Move a comment on output buffer sizes from inffast.c to inflate.c
44 * - Add comments in inffast.c to introduce the inflate_fast() routine
45 * - Rearrange window copies in inflate_fast() for speed and simplification
46 * - Unroll last copy for window match in inflate_fast()
47 * - Use local copies of window variables in inflate_fast() for speed
48 * - Pull out common wnext == 0 case for speed in inflate_fast()
49 * - Make op and len in inflate_fast() unsigned for consistency
50 * - Add FAR to lcode and dcode declarations in inflate_fast()
51 * - Simplified bad distance check in inflate_fast()
52 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53 * source file infback.c to provide a call-back interface to inflate for
54 * programs like gzip and unzip -- uses window as output buffer to avoid
57 * 1.2.beta5 1 Jan 2003
58 * - Improved inflateBack() interface to allow the caller to provide initial
60 * - Fixed stored blocks bug in inflateBack()
62 * 1.2.beta6 4 Jan 2003
63 * - Added comments in inffast.c on effectiveness of POSTINC
64 * - Typecasting all around to reduce compiler warnings
65 * - Changed loops from while (1) or do {} while (1) to for (;;), again to
66 * make compilers happy
67 * - Changed type of window in inflateBackInit() to unsigned char *
69 * 1.2.beta7 27 Jan 2003
70 * - Changed many types to unsigned or unsigned short to avoid warnings
71 * - Added inflateCopy() function
74 * - Changed inflateBack() interface to provide separate opaque descriptors
75 * for the in() and out() functions
76 * - Changed inflateBack() argument and in_func typedef to swap the length
77 * and buffer address return values for the input function
78 * - Check next_in and next_out for Z_NULL on entry to inflate()
80 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
94 /* function prototypes */
95 local int inflateStateCheck OF((z_streamp strm));
96 local void fixedtables OF((struct inflate_state FAR *state));
97 local int updatewindow OF((z_streamp strm, const unsigned char FAR *end,
100 void makefixed OF((void));
102 local unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf,
105 local int inflateStateCheck(strm)
108 struct inflate_state FAR *state;
109 if (strm == Z_NULL ||
110 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)
112 state = (struct inflate_state FAR *)strm->state;
113 if (state == Z_NULL || state->strm != strm ||
114 state->mode < HEAD || state->mode > SYNC)
119 int ZEXPORT inflateResetKeep(strm)
122 struct inflate_state FAR *state;
124 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
125 state = (struct inflate_state FAR *)strm->state;
126 strm->total_in = strm->total_out = state->total = 0;
128 if (state->wrap) /* to support ill-conceived Java test suite */
129 strm->adler = state->wrap & 1;
134 state->dmax = 32768U;
135 state->head = Z_NULL;
138 state->lencode = state->distcode = state->next = state->codes;
141 Tracev((stderr, "inflate: reset\n"));
145 int ZEXPORT inflateReset(strm)
148 struct inflate_state FAR *state;
150 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
151 state = (struct inflate_state FAR *)strm->state;
155 return inflateResetKeep(strm);
158 int ZEXPORT inflateReset2(strm, windowBits)
163 struct inflate_state FAR *state;
166 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
167 state = (struct inflate_state FAR *)strm->state;
169 /* extract wrap request from windowBits parameter */
170 if (windowBits < 0) {
172 windowBits = -windowBits;
175 wrap = (windowBits >> 4) + 5;
182 /* set number of window bits, free window if different */
183 if (windowBits && (windowBits < 8 || windowBits > 15))
184 return Z_STREAM_ERROR;
185 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
186 ZFREE(strm, state->window);
187 state->window = Z_NULL;
190 /* update state and reset the rest of it */
192 state->wbits = (unsigned)windowBits;
193 return inflateReset(strm);
196 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
203 struct inflate_state FAR *state;
205 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
206 stream_size != (int)(sizeof(z_stream)))
207 return Z_VERSION_ERROR;
208 if (strm == Z_NULL) return Z_STREAM_ERROR;
209 strm->msg = Z_NULL; /* in case we return an error */
210 if (strm->zalloc == (alloc_func)0) {
211 #if defined(Z_SOLO) && !defined(_KERNEL)
212 return Z_STREAM_ERROR;
214 strm->zalloc = zcalloc;
215 strm->opaque = (voidpf)0;
218 if (strm->zfree == (free_func)0)
219 #if defined(Z_SOLO) && !defined(_KERNEL)
220 return Z_STREAM_ERROR;
222 strm->zfree = zcfree;
224 state = (struct inflate_state FAR *)
225 ZALLOC(strm, 1, sizeof(struct inflate_state));
226 if (state == Z_NULL) return Z_MEM_ERROR;
227 Tracev((stderr, "inflate: allocated\n"));
228 strm->state = (struct internal_state FAR *)state;
230 state->window = Z_NULL;
231 state->mode = HEAD; /* to pass state test in inflateReset2() */
232 ret = inflateReset2(strm, windowBits);
235 strm->state = Z_NULL;
240 int ZEXPORT inflateInit_(strm, version, stream_size)
245 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
248 int ZEXPORT inflatePrime(strm, bits, value)
253 struct inflate_state FAR *state;
255 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
256 state = (struct inflate_state FAR *)strm->state;
262 if (bits > 16 || state->bits + (uInt)bits > 32) return Z_STREAM_ERROR;
263 value &= (1L << bits) - 1;
264 state->hold += (unsigned)value << state->bits;
265 state->bits += (uInt)bits;
270 Return state with length and distance decoding tables and index sizes set to
271 fixed code decoding. Normally this returns fixed tables from inffixed.h.
272 If BUILDFIXED is defined, then instead this routine builds the tables the
273 first time it's called, and returns those tables the first time and
274 thereafter. This reduces the size of the code by about 2K bytes, in
275 exchange for a little execution time. However, BUILDFIXED should not be
276 used for threaded applications, since the rewriting of the tables and virgin
277 may not be thread-safe.
279 local void fixedtables(state)
280 struct inflate_state FAR *state;
283 static int virgin = 1;
284 static code *lenfix, *distfix;
285 static code fixed[544];
287 /* build fixed huffman tables if first call (may not be thread safe) */
292 /* literal/length table */
294 while (sym < 144) state->lens[sym++] = 8;
295 while (sym < 256) state->lens[sym++] = 9;
296 while (sym < 280) state->lens[sym++] = 7;
297 while (sym < 288) state->lens[sym++] = 8;
301 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
305 while (sym < 32) state->lens[sym++] = 5;
308 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
310 /* do this just once */
313 #else /* !BUILDFIXED */
314 # include "inffixed.h"
315 #endif /* BUILDFIXED */
316 state->lencode = lenfix;
318 state->distcode = distfix;
326 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
327 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
328 those tables to stdout, which would be piped to inffixed.h. A small program
329 can simply call makefixed to do this:
331 void makefixed(void);
339 Then that can be linked with zlib built with MAKEFIXED defined and run:
346 struct inflate_state state;
349 puts(" /* inffixed.h -- table for decoding fixed codes");
350 puts(" * Generated automatically by makefixed().");
353 puts(" /* WARNING: this file should *not* be used by applications.");
354 puts(" It is part of the implementation of this library and is");
355 puts(" subject to change. Applications should only use zlib.h.");
359 printf(" static const code lenfix[%u] = {", size);
362 if ((low % 7) == 0) printf("\n ");
363 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
364 state.lencode[low].bits, state.lencode[low].val);
365 if (++low == size) break;
370 printf("\n static const code distfix[%u] = {", size);
373 if ((low % 6) == 0) printf("\n ");
374 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
375 state.distcode[low].val);
376 if (++low == size) break;
381 #endif /* MAKEFIXED */
384 Update the window with the last wsize (normally 32K) bytes written before
385 returning. If window does not exist yet, create it. This is only called
386 when a window is already in use, or when output has been written during this
387 inflate call, but the end of the deflate stream has not been reached yet.
388 It is also called to create a window for dictionary data when a dictionary
391 Providing output buffers larger than 32K to inflate() should provide a speed
392 advantage, since only the last 32K of output is copied to the sliding window
393 upon return from inflate(), and since all distances after the first 32K of
394 output will fall in the output data, making match copies simpler and faster.
395 The advantage may be dependent on the size of the processor's data caches.
397 local int updatewindow(strm, end, copy)
402 struct inflate_state FAR *state;
405 state = (struct inflate_state FAR *)strm->state;
407 /* if it hasn't been done already, allocate space for the window */
408 if (state->window == Z_NULL) {
409 state->window = (unsigned char FAR *)
410 ZALLOC(strm, 1U << state->wbits,
411 sizeof(unsigned char));
412 if (state->window == Z_NULL) return 1;
415 /* if window not in use yet, initialize */
416 if (state->wsize == 0) {
417 state->wsize = 1U << state->wbits;
422 /* copy state->wsize or less output bytes into the circular window */
423 if (copy >= state->wsize) {
424 zmemcpy(state->window, end - state->wsize, state->wsize);
426 state->whave = state->wsize;
429 dist = state->wsize - state->wnext;
430 if (dist > copy) dist = copy;
431 zmemcpy(state->window + state->wnext, end - copy, dist);
434 zmemcpy(state->window, end - copy, copy);
436 state->whave = state->wsize;
439 state->wnext += dist;
440 if (state->wnext == state->wsize) state->wnext = 0;
441 if (state->whave < state->wsize) state->whave += dist;
447 /* Macros for inflate(): */
449 /* check function to use adler32() for zlib or crc32() for gzip */
451 # define UPDATE_CHECK(check, buf, len) \
452 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
454 # define UPDATE_CHECK(check, buf, len) adler32(check, buf, len)
457 /* check macros for header crc */
459 # define CRC2(check, word) \
461 hbuf[0] = (unsigned char)(word); \
462 hbuf[1] = (unsigned char)((word) >> 8); \
463 check = crc32(check, hbuf, 2); \
466 # define CRC4(check, word) \
468 hbuf[0] = (unsigned char)(word); \
469 hbuf[1] = (unsigned char)((word) >> 8); \
470 hbuf[2] = (unsigned char)((word) >> 16); \
471 hbuf[3] = (unsigned char)((word) >> 24); \
472 check = crc32(check, hbuf, 4); \
476 /* Load registers with state in inflate() for speed */
479 put = strm->next_out; \
480 left = strm->avail_out; \
481 next = strm->next_in; \
482 have = strm->avail_in; \
483 hold = state->hold; \
484 bits = state->bits; \
487 /* Restore state from registers in inflate() */
490 strm->next_out = put; \
491 strm->avail_out = left; \
492 strm->next_in = next; \
493 strm->avail_in = have; \
494 state->hold = hold; \
495 state->bits = bits; \
498 /* Clear the input bit accumulator */
505 /* Get a byte of input into the bit accumulator, or return from inflate()
506 if there is no input available. */
509 if (have == 0) goto inf_leave; \
511 hold += (unsigned long)(*next++) << bits; \
515 /* Assure that there are at least n bits in the bit accumulator. If there is
516 not enough available input to do that, then return from inflate(). */
517 #define NEEDBITS(n) \
519 while (bits < (unsigned)(n)) \
523 /* Return the low n bits of the bit accumulator (n < 16) */
525 ((unsigned)hold & ((1U << (n)) - 1))
527 /* Remove n bits from the bit accumulator */
528 #define DROPBITS(n) \
531 bits -= (unsigned)(n); \
534 /* Remove zero to seven bits as needed to go to a byte boundary */
542 inflate() uses a state machine to process as much input data and generate as
543 much output data as possible before returning. The state machine is
544 structured roughly as follows:
546 for (;;) switch (state) {
549 if (not enough input data or output space to make progress)
551 ... make progress ...
557 so when inflate() is called again, the same case is attempted again, and
558 if the appropriate resources are provided, the machine proceeds to the
559 next state. The NEEDBITS() macro is usually the way the state evaluates
560 whether it can proceed or should return. NEEDBITS() does the return if
561 the requested bits are not available. The typical use of the BITS macros
565 ... do something with BITS(n) ...
568 where NEEDBITS(n) either returns from inflate() if there isn't enough
569 input left to load n bits into the accumulator, or it continues. BITS(n)
570 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
571 the low n bits off the accumulator. INITBITS() clears the accumulator
572 and sets the number of available bits to zero. BYTEBITS() discards just
573 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
574 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
576 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
577 if there is no input available. The decoding of variable length codes uses
578 PULLBYTE() directly in order to pull just enough bytes to decode the next
581 Some states loop until they get enough input, making sure that enough
582 state information is maintained to continue the loop where it left off
583 if NEEDBITS() returns in the loop. For example, want, need, and keep
584 would all have to actually be part of the saved state in case NEEDBITS()
588 while (want < need) {
590 keep[want++] = BITS(n);
596 As shown above, if the next state is also the next case, then the break
599 A state may also return if there is not enough output space available to
600 complete that state. Those states are copying stored data, writing a
601 literal byte, and copying a matching string.
603 When returning, a "goto inf_leave" is used to update the total counters,
604 update the check value, and determine whether any progress has been made
605 during that inflate() call in order to return the proper return code.
606 Progress is defined as a change in either strm->avail_in or strm->avail_out.
607 When there is a window, goto inf_leave will update the window with the last
608 output written. If a goto inf_leave occurs in the middle of decompression
609 and there is no window currently, goto inf_leave will create one and copy
610 output to the window for the next call of inflate().
612 In this implementation, the flush parameter of inflate() only affects the
613 return code (per zlib.h). inflate() always writes as much as possible to
614 strm->next_out, given the space available and the provided input--the effect
615 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
616 the allocation of and copying into a sliding window until necessary, which
617 provides the effect documented in zlib.h for Z_FINISH when the entire input
618 stream available. So the only thing the flush parameter actually does is:
619 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
620 will return Z_BUF_ERROR if it has not reached the end of the stream.
623 int ZEXPORT inflate(strm, flush)
627 struct inflate_state FAR *state;
628 z_const unsigned char FAR *next; /* next input */
629 unsigned char FAR *put; /* next output */
630 unsigned have, left; /* available input and output */
631 unsigned long hold; /* bit buffer */
632 unsigned bits; /* bits in bit buffer */
633 unsigned in, out; /* save starting available input and output */
634 unsigned copy; /* number of stored or match bytes to copy */
635 unsigned char FAR *from; /* where to copy match bytes from */
636 code here; /* current decoding table entry */
637 code last; /* parent table entry */
638 unsigned len; /* length to copy for repeats, bits to drop */
639 int ret; /* return code */
641 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
643 static const unsigned short order[19] = /* permutation of code lengths */
644 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
646 if (inflateStateCheck(strm) || strm->next_out == Z_NULL ||
647 (strm->next_in == Z_NULL && strm->avail_in != 0))
648 return Z_STREAM_ERROR;
650 state = (struct inflate_state FAR *)strm->state;
651 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
657 switch (state->mode) {
659 if (state->wrap == 0) {
660 state->mode = TYPEDO;
665 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
666 if (state->wbits == 0)
668 state->check = crc32(0L, Z_NULL, 0);
669 CRC2(state->check, hold);
674 if (state->head != Z_NULL)
675 state->head->done = -1;
676 if (!(state->wrap & 1) || /* check if zlib header allowed */
680 ((BITS(8) << 8) + (hold >> 8)) % 31) {
681 strm->msg = (char *)"incorrect header check";
685 if (BITS(4) != Z_DEFLATED) {
686 strm->msg = (char *)"unknown compression method";
692 if (state->wbits == 0)
694 if (len > 15 || len > state->wbits) {
695 strm->msg = (char *)"invalid window size";
699 state->dmax = 1U << len;
700 state->flags = 0; /* indicate zlib header */
701 Tracev((stderr, "inflate: zlib header ok\n"));
702 strm->adler = state->check = adler32(0L, Z_NULL, 0);
703 state->mode = hold & 0x200 ? DICTID : TYPE;
709 state->flags = (int)(hold);
710 if ((state->flags & 0xff) != Z_DEFLATED) {
711 strm->msg = (char *)"unknown compression method";
715 if (state->flags & 0xe000) {
716 strm->msg = (char *)"unknown header flags set";
720 if (state->head != Z_NULL)
721 state->head->text = (int)((hold >> 8) & 1);
722 if ((state->flags & 0x0200) && (state->wrap & 4))
723 CRC2(state->check, hold);
729 if (state->head != Z_NULL)
730 state->head->time = hold;
731 if ((state->flags & 0x0200) && (state->wrap & 4))
732 CRC4(state->check, hold);
738 if (state->head != Z_NULL) {
739 state->head->xflags = (int)(hold & 0xff);
740 state->head->os = (int)(hold >> 8);
742 if ((state->flags & 0x0200) && (state->wrap & 4))
743 CRC2(state->check, hold);
748 if (state->flags & 0x0400) {
750 state->length = (unsigned)(hold);
751 if (state->head != Z_NULL)
752 state->head->extra_len = (unsigned)hold;
753 if ((state->flags & 0x0200) && (state->wrap & 4))
754 CRC2(state->check, hold);
757 else if (state->head != Z_NULL)
758 state->head->extra = Z_NULL;
762 if (state->flags & 0x0400) {
763 copy = state->length;
764 if (copy > have) copy = have;
766 if (state->head != Z_NULL &&
767 state->head->extra != Z_NULL &&
768 (len = state->head->extra_len - state->length) <
769 state->head->extra_max) {
770 zmemcpy(state->head->extra + len, next,
771 len + copy > state->head->extra_max ?
772 state->head->extra_max - len : copy);
774 if ((state->flags & 0x0200) && (state->wrap & 4))
775 state->check = crc32(state->check, next, copy);
778 state->length -= copy;
780 if (state->length) goto inf_leave;
786 if (state->flags & 0x0800) {
787 if (have == 0) goto inf_leave;
790 len = (unsigned)(next[copy++]);
791 if (state->head != Z_NULL &&
792 state->head->name != Z_NULL &&
793 state->length < state->head->name_max)
794 state->head->name[state->length++] = (Bytef)len;
795 } while (len && copy < have);
796 if ((state->flags & 0x0200) && (state->wrap & 4))
797 state->check = crc32(state->check, next, copy);
800 if (len) goto inf_leave;
802 else if (state->head != Z_NULL)
803 state->head->name = Z_NULL;
805 state->mode = COMMENT;
808 if (state->flags & 0x1000) {
809 if (have == 0) goto inf_leave;
812 len = (unsigned)(next[copy++]);
813 if (state->head != Z_NULL &&
814 state->head->comment != Z_NULL &&
815 state->length < state->head->comm_max)
816 state->head->comment[state->length++] = (Bytef)len;
817 } while (len && copy < have);
818 if ((state->flags & 0x0200) && (state->wrap & 4))
819 state->check = crc32(state->check, next, copy);
822 if (len) goto inf_leave;
824 else if (state->head != Z_NULL)
825 state->head->comment = Z_NULL;
829 if (state->flags & 0x0200) {
831 if ((state->wrap & 4) && hold != (state->check & 0xffff)) {
832 strm->msg = (char *)"header crc mismatch";
838 if (state->head != Z_NULL) {
839 state->head->hcrc = (int)((state->flags >> 9) & 1);
840 state->head->done = 1;
842 strm->adler = state->check = crc32(0L, Z_NULL, 0);
848 strm->adler = state->check = ZSWAP32(hold);
853 if (state->havedict == 0) {
857 strm->adler = state->check = adler32(0L, Z_NULL, 0);
861 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
870 state->last = BITS(1);
873 case 0: /* stored block */
874 Tracev((stderr, "inflate: stored block%s\n",
875 state->last ? " (last)" : ""));
876 state->mode = STORED;
878 case 1: /* fixed block */
880 Tracev((stderr, "inflate: fixed codes block%s\n",
881 state->last ? " (last)" : ""));
882 state->mode = LEN_; /* decode codes */
883 if (flush == Z_TREES) {
888 case 2: /* dynamic block */
889 Tracev((stderr, "inflate: dynamic codes block%s\n",
890 state->last ? " (last)" : ""));
894 strm->msg = (char *)"invalid block type";
900 BYTEBITS(); /* go to byte boundary */
902 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
903 strm->msg = (char *)"invalid stored block lengths";
907 state->length = (unsigned)hold & 0xffff;
908 Tracev((stderr, "inflate: stored length %u\n",
912 if (flush == Z_TREES) goto inf_leave;
918 copy = state->length;
920 if (copy > have) copy = have;
921 if (copy > left) copy = left;
922 if (copy == 0) goto inf_leave;
923 zmemcpy(put, next, copy);
928 state->length -= copy;
931 Tracev((stderr, "inflate: stored end\n"));
936 state->nlen = BITS(5) + 257;
938 state->ndist = BITS(5) + 1;
940 state->ncode = BITS(4) + 4;
942 #ifndef PKZIP_BUG_WORKAROUND
943 if (state->nlen > 286 || state->ndist > 30) {
944 strm->msg = (char *)"too many length or distance symbols";
949 Tracev((stderr, "inflate: table sizes ok\n"));
951 state->mode = LENLENS;
954 while (state->have < state->ncode) {
956 state->lens[order[state->have++]] = (unsigned short)BITS(3);
959 while (state->have < 19)
960 state->lens[order[state->have++]] = 0;
961 state->next = state->codes;
962 state->lencode = (const code FAR *)(state->next);
964 ret = inflate_table(CODES, state->lens, 19, &(state->next),
965 &(state->lenbits), state->work);
967 strm->msg = (char *)"invalid code lengths set";
971 Tracev((stderr, "inflate: code lengths ok\n"));
973 state->mode = CODELENS;
976 while (state->have < state->nlen + state->ndist) {
978 here = state->lencode[BITS(state->lenbits)];
979 if ((unsigned)(here.bits) <= bits) break;
984 state->lens[state->have++] = here.val;
987 if (here.val == 16) {
988 NEEDBITS(here.bits + 2);
990 if (state->have == 0) {
991 strm->msg = (char *)"invalid bit length repeat";
995 len = state->lens[state->have - 1];
999 else if (here.val == 17) {
1000 NEEDBITS(here.bits + 3);
1001 DROPBITS(here.bits);
1007 NEEDBITS(here.bits + 7);
1008 DROPBITS(here.bits);
1010 copy = 11 + BITS(7);
1013 if (state->have + copy > state->nlen + state->ndist) {
1014 strm->msg = (char *)"invalid bit length repeat";
1019 state->lens[state->have++] = (unsigned short)len;
1023 /* handle error breaks in while */
1024 if (state->mode == BAD) break;
1026 /* check for end-of-block code (better have one) */
1027 if (state->lens[256] == 0) {
1028 strm->msg = (char *)"invalid code -- missing end-of-block";
1033 /* build code tables -- note: do not change the lenbits or distbits
1034 values here (9 and 6) without reading the comments in inftrees.h
1035 concerning the ENOUGH constants, which depend on those values */
1036 state->next = state->codes;
1037 state->lencode = (const code FAR *)(state->next);
1039 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1040 &(state->lenbits), state->work);
1042 strm->msg = (char *)"invalid literal/lengths set";
1046 state->distcode = (const code FAR *)(state->next);
1047 state->distbits = 6;
1048 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1049 &(state->next), &(state->distbits), state->work);
1051 strm->msg = (char *)"invalid distances set";
1055 Tracev((stderr, "inflate: codes ok\n"));
1057 if (flush == Z_TREES) goto inf_leave;
1063 if (have >= 6 && left >= 258) {
1065 inflate_fast(strm, out);
1067 if (state->mode == TYPE)
1073 here = state->lencode[BITS(state->lenbits)];
1074 if ((unsigned)(here.bits) <= bits) break;
1077 if (here.op && (here.op & 0xf0) == 0) {
1080 here = state->lencode[last.val +
1081 (BITS(last.bits + last.op) >> last.bits)];
1082 if ((unsigned)(last.bits + here.bits) <= bits) break;
1085 DROPBITS(last.bits);
1086 state->back += last.bits;
1088 DROPBITS(here.bits);
1089 state->back += here.bits;
1090 state->length = (unsigned)here.val;
1091 if ((int)(here.op) == 0) {
1092 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1093 "inflate: literal '%c'\n" :
1094 "inflate: literal 0x%02x\n", here.val));
1099 Tracevv((stderr, "inflate: end of block\n"));
1105 strm->msg = (char *)"invalid literal/length code";
1109 state->extra = (unsigned)(here.op) & 15;
1110 state->mode = LENEXT;
1114 NEEDBITS(state->extra);
1115 state->length += BITS(state->extra);
1116 DROPBITS(state->extra);
1117 state->back += state->extra;
1119 Tracevv((stderr, "inflate: length %u\n", state->length));
1120 state->was = state->length;
1125 here = state->distcode[BITS(state->distbits)];
1126 if ((unsigned)(here.bits) <= bits) break;
1129 if ((here.op & 0xf0) == 0) {
1132 here = state->distcode[last.val +
1133 (BITS(last.bits + last.op) >> last.bits)];
1134 if ((unsigned)(last.bits + here.bits) <= bits) break;
1137 DROPBITS(last.bits);
1138 state->back += last.bits;
1140 DROPBITS(here.bits);
1141 state->back += here.bits;
1143 strm->msg = (char *)"invalid distance code";
1147 state->offset = (unsigned)here.val;
1148 state->extra = (unsigned)(here.op) & 15;
1149 state->mode = DISTEXT;
1153 NEEDBITS(state->extra);
1154 state->offset += BITS(state->extra);
1155 DROPBITS(state->extra);
1156 state->back += state->extra;
1158 #ifdef INFLATE_STRICT
1159 if (state->offset > state->dmax) {
1160 strm->msg = (char *)"invalid distance too far back";
1165 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1166 state->mode = MATCH;
1169 if (left == 0) goto inf_leave;
1171 if (state->offset > copy) { /* copy from window */
1172 copy = state->offset - copy;
1173 if (copy > state->whave) {
1175 strm->msg = (char *)"invalid distance too far back";
1179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1180 Trace((stderr, "inflate.c too far\n"));
1181 copy -= state->whave;
1182 if (copy > state->length) copy = state->length;
1183 if (copy > left) copy = left;
1185 state->length -= copy;
1189 if (state->length == 0) state->mode = LEN;
1193 if (copy > state->wnext) {
1194 copy -= state->wnext;
1195 from = state->window + (state->wsize - copy);
1198 from = state->window + (state->wnext - copy);
1199 if (copy > state->length) copy = state->length;
1201 else { /* copy from output */
1202 from = put - state->offset;
1203 copy = state->length;
1205 if (copy > left) copy = left;
1207 state->length -= copy;
1211 if (state->length == 0) state->mode = LEN;
1214 if (left == 0) goto inf_leave;
1215 *put++ = (unsigned char)(state->length);
1223 strm->total_out += out;
1224 state->total += out;
1225 if ((state->wrap & 4) && out)
1226 strm->adler = state->check =
1227 UPDATE_CHECK(state->check, put - out, out);
1229 if ((state->wrap & 4) && (
1231 state->flags ? hold :
1233 ZSWAP32(hold)) != state->check) {
1234 strm->msg = (char *)"incorrect data check";
1239 Tracev((stderr, "inflate: check matches trailer\n"));
1242 state->mode = LENGTH;
1245 if (state->wrap && state->flags) {
1247 if ((state->wrap & 4) && hold != (state->total & 0xffffffff)) {
1248 strm->msg = (char *)"incorrect length check";
1253 Tracev((stderr, "inflate: length matches trailer\n"));
1269 return Z_STREAM_ERROR;
1273 Return from inflate(), updating the total counts and the check value.
1274 If there was no progress during the inflate() call, return a buffer
1275 error. Call updatewindow() to create and/or update the window state.
1276 Note: a memory error from inflate() is non-recoverable.
1280 if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1281 (state->mode < CHECK || flush != Z_FINISH)))
1282 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1286 in -= strm->avail_in;
1287 out -= strm->avail_out;
1288 strm->total_in += in;
1289 strm->total_out += out;
1290 state->total += out;
1291 if ((state->wrap & 4) && out)
1292 strm->adler = state->check =
1293 UPDATE_CHECK(state->check, strm->next_out - out, out);
1294 strm->data_type = (int)state->bits + (state->last ? 64 : 0) +
1295 (state->mode == TYPE ? 128 : 0) +
1296 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1297 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1302 int ZEXPORT inflateEnd(strm)
1305 struct inflate_state FAR *state;
1306 if (inflateStateCheck(strm))
1307 return Z_STREAM_ERROR;
1308 state = (struct inflate_state FAR *)strm->state;
1309 if (state->window != Z_NULL) ZFREE(strm, state->window);
1310 ZFREE(strm, strm->state);
1311 strm->state = Z_NULL;
1312 Tracev((stderr, "inflate: end\n"));
1316 int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1321 struct inflate_state FAR *state;
1324 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1325 state = (struct inflate_state FAR *)strm->state;
1327 /* copy dictionary */
1328 if (state->whave && dictionary != Z_NULL) {
1329 zmemcpy(dictionary, state->window + state->wnext,
1330 state->whave - state->wnext);
1331 zmemcpy(dictionary + state->whave - state->wnext,
1332 state->window, state->wnext);
1334 if (dictLength != Z_NULL)
1335 *dictLength = state->whave;
1339 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1341 const Bytef *dictionary;
1344 struct inflate_state FAR *state;
1345 unsigned long dictid;
1349 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1350 state = (struct inflate_state FAR *)strm->state;
1351 if (state->wrap != 0 && state->mode != DICT)
1352 return Z_STREAM_ERROR;
1354 /* check for correct dictionary identifier */
1355 if (state->mode == DICT) {
1356 dictid = adler32(0L, Z_NULL, 0);
1357 dictid = adler32(dictid, dictionary, dictLength);
1358 if (dictid != state->check)
1359 return Z_DATA_ERROR;
1362 /* copy dictionary to window using updatewindow(), which will amend the
1363 existing dictionary if appropriate */
1364 ret = updatewindow(strm, dictionary + dictLength, dictLength);
1369 state->havedict = 1;
1370 Tracev((stderr, "inflate: dictionary set\n"));
1374 int ZEXPORT inflateGetHeader(strm, head)
1378 struct inflate_state FAR *state;
1381 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1382 state = (struct inflate_state FAR *)strm->state;
1383 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1385 /* save header structure */
1392 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1393 or when out of input. When called, *have is the number of pattern bytes
1394 found in order so far, in 0..3. On return *have is updated to the new
1395 state. If on return *have equals four, then the pattern was found and the
1396 return value is how many bytes were read including the last byte of the
1397 pattern. If *have is less than four, then the pattern has not been found
1398 yet and the return value is len. In the latter case, syncsearch() can be
1399 called again with more data and the *have state. *have is initialized to
1400 zero for the first call.
1402 local unsigned syncsearch(have, buf, len)
1404 const unsigned char FAR *buf;
1412 while (next < len && got < 4) {
1413 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1425 int ZEXPORT inflateSync(strm)
1428 unsigned len; /* number of bytes to look at or looked at */
1429 int flags; /* temporary to save header status */
1430 unsigned long in, out; /* temporary to save total_in and total_out */
1431 unsigned char buf[4]; /* to restore bit buffer to byte string */
1432 struct inflate_state FAR *state;
1434 /* check parameters */
1435 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1436 state = (struct inflate_state FAR *)strm->state;
1437 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1439 /* if first time, start search in bit buffer */
1440 if (state->mode != SYNC) {
1442 state->hold <<= state->bits & 7;
1443 state->bits -= state->bits & 7;
1445 while (state->bits >= 8) {
1446 buf[len++] = (unsigned char)(state->hold);
1451 syncsearch(&(state->have), buf, len);
1454 /* search available input */
1455 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1456 strm->avail_in -= len;
1457 strm->next_in += len;
1458 strm->total_in += len;
1460 /* return no joy or set up to restart inflate() on a new block */
1461 if (state->have != 4) return Z_DATA_ERROR;
1462 if (state->flags == -1)
1463 state->wrap = 0; /* if no header yet, treat as raw */
1465 state->wrap &= ~4; /* no point in computing a check value now */
1466 flags = state->flags;
1467 in = strm->total_in; out = strm->total_out;
1469 strm->total_in = in; strm->total_out = out;
1470 state->flags = flags;
1476 Returns true if inflate is currently at the end of a block generated by
1477 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1478 implementation to provide an additional safety check. PPP uses
1479 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1480 block. When decompressing, PPP checks that at the end of input packet,
1481 inflate is waiting for these length bytes.
1483 int ZEXPORT inflateSyncPoint(strm)
1486 struct inflate_state FAR *state;
1488 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1489 state = (struct inflate_state FAR *)strm->state;
1490 return state->mode == STORED && state->bits == 0;
1493 int ZEXPORT inflateCopy(dest, source)
1497 struct inflate_state FAR *state;
1498 struct inflate_state FAR *copy;
1499 unsigned char FAR *window;
1503 if (inflateStateCheck(source) || dest == Z_NULL)
1504 return Z_STREAM_ERROR;
1505 state = (struct inflate_state FAR *)source->state;
1507 /* allocate space */
1508 copy = (struct inflate_state FAR *)
1509 ZALLOC(source, 1, sizeof(struct inflate_state));
1510 if (copy == Z_NULL) return Z_MEM_ERROR;
1512 if (state->window != Z_NULL) {
1513 window = (unsigned char FAR *)
1514 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1515 if (window == Z_NULL) {
1516 ZFREE(source, copy);
1522 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1523 zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1525 if (state->lencode >= state->codes &&
1526 state->lencode <= state->codes + ENOUGH - 1) {
1527 copy->lencode = copy->codes + (state->lencode - state->codes);
1528 copy->distcode = copy->codes + (state->distcode - state->codes);
1530 copy->next = copy->codes + (state->next - state->codes);
1531 if (window != Z_NULL) {
1532 wsize = 1U << state->wbits;
1533 zmemcpy(window, state->window, wsize);
1535 copy->window = window;
1536 dest->state = (struct internal_state FAR *)copy;
1540 int ZEXPORT inflateUndermine(strm, subvert)
1544 struct inflate_state FAR *state;
1546 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1547 state = (struct inflate_state FAR *)strm->state;
1548 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1549 state->sane = !subvert;
1554 return Z_DATA_ERROR;
1558 int ZEXPORT inflateValidate(strm, check)
1562 struct inflate_state FAR *state;
1564 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1565 state = (struct inflate_state FAR *)strm->state;
1566 if (check && state->wrap)
1573 long ZEXPORT inflateMark(strm)
1576 struct inflate_state FAR *state;
1578 if (inflateStateCheck(strm))
1580 state = (struct inflate_state FAR *)strm->state;
1581 return (long)(((unsigned long)((long)state->back)) << 16) +
1582 (state->mode == COPY ? state->length :
1583 (state->mode == MATCH ? state->was - state->length : 0));
1586 unsigned long ZEXPORT inflateCodesUsed(strm)
1589 struct inflate_state FAR *state;
1590 if (inflateStateCheck(strm)) return (unsigned long)-1;
1591 state = (struct inflate_state FAR *)strm->state;
1592 return (unsigned long)(state->next - state->codes);