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
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;
133 state->dmax = 32768U;
134 state->head = Z_NULL;
137 state->lencode = state->distcode = state->next = state->codes;
140 Tracev((stderr, "inflate: reset\n"));
144 int ZEXPORT inflateReset(strm)
147 struct inflate_state FAR *state;
149 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
150 state = (struct inflate_state FAR *)strm->state;
154 return inflateResetKeep(strm);
157 int ZEXPORT inflateReset2(strm, windowBits)
162 struct inflate_state FAR *state;
165 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
166 state = (struct inflate_state FAR *)strm->state;
168 /* extract wrap request from windowBits parameter */
169 if (windowBits < 0) {
171 windowBits = -windowBits;
174 wrap = (windowBits >> 4) + 5;
181 /* set number of window bits, free window if different */
182 if (windowBits && (windowBits < 8 || windowBits > 15))
183 return Z_STREAM_ERROR;
184 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
185 ZFREE(strm, state->window);
186 state->window = Z_NULL;
189 /* update state and reset the rest of it */
191 state->wbits = (unsigned)windowBits;
192 return inflateReset(strm);
195 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
202 struct inflate_state FAR *state;
204 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
205 stream_size != (int)(sizeof(z_stream)))
206 return Z_VERSION_ERROR;
207 if (strm == Z_NULL) return Z_STREAM_ERROR;
208 strm->msg = Z_NULL; /* in case we return an error */
209 if (strm->zalloc == (alloc_func)0) {
210 #if defined(Z_SOLO) && !defined(_KERNEL)
211 return Z_STREAM_ERROR;
213 strm->zalloc = zcalloc;
214 strm->opaque = (voidpf)0;
217 if (strm->zfree == (free_func)0)
218 #if defined(Z_SOLO) && !defined(_KERNEL)
219 return Z_STREAM_ERROR;
221 strm->zfree = zcfree;
223 state = (struct inflate_state FAR *)
224 ZALLOC(strm, 1, sizeof(struct inflate_state));
225 if (state == Z_NULL) return Z_MEM_ERROR;
226 Tracev((stderr, "inflate: allocated\n"));
227 strm->state = (struct internal_state FAR *)state;
229 state->window = Z_NULL;
230 state->mode = HEAD; /* to pass state test in inflateReset2() */
231 ret = inflateReset2(strm, windowBits);
234 strm->state = Z_NULL;
239 int ZEXPORT inflateInit_(strm, version, stream_size)
244 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
247 int ZEXPORT inflatePrime(strm, bits, value)
252 struct inflate_state FAR *state;
254 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
255 state = (struct inflate_state FAR *)strm->state;
261 if (bits > 16 || state->bits + (uInt)bits > 32) return Z_STREAM_ERROR;
262 value &= (1L << bits) - 1;
263 state->hold += (unsigned)value << state->bits;
264 state->bits += (uInt)bits;
269 Return state with length and distance decoding tables and index sizes set to
270 fixed code decoding. Normally this returns fixed tables from inffixed.h.
271 If BUILDFIXED is defined, then instead this routine builds the tables the
272 first time it's called, and returns those tables the first time and
273 thereafter. This reduces the size of the code by about 2K bytes, in
274 exchange for a little execution time. However, BUILDFIXED should not be
275 used for threaded applications, since the rewriting of the tables and virgin
276 may not be thread-safe.
278 local void fixedtables(state)
279 struct inflate_state FAR *state;
282 static int virgin = 1;
283 static code *lenfix, *distfix;
284 static code fixed[544];
286 /* build fixed huffman tables if first call (may not be thread safe) */
291 /* literal/length table */
293 while (sym < 144) state->lens[sym++] = 8;
294 while (sym < 256) state->lens[sym++] = 9;
295 while (sym < 280) state->lens[sym++] = 7;
296 while (sym < 288) state->lens[sym++] = 8;
300 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
304 while (sym < 32) state->lens[sym++] = 5;
307 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
309 /* do this just once */
312 #else /* !BUILDFIXED */
313 # include "inffixed.h"
314 #endif /* BUILDFIXED */
315 state->lencode = lenfix;
317 state->distcode = distfix;
325 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
326 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
327 those tables to stdout, which would be piped to inffixed.h. A small program
328 can simply call makefixed to do this:
330 void makefixed(void);
338 Then that can be linked with zlib built with MAKEFIXED defined and run:
345 struct inflate_state state;
348 puts(" /* inffixed.h -- table for decoding fixed codes");
349 puts(" * Generated automatically by makefixed().");
352 puts(" /* WARNING: this file should *not* be used by applications.");
353 puts(" It is part of the implementation of this library and is");
354 puts(" subject to change. Applications should only use zlib.h.");
358 printf(" static const code lenfix[%u] = {", size);
361 if ((low % 7) == 0) printf("\n ");
362 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
363 state.lencode[low].bits, state.lencode[low].val);
364 if (++low == size) break;
369 printf("\n static const code distfix[%u] = {", size);
372 if ((low % 6) == 0) printf("\n ");
373 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
374 state.distcode[low].val);
375 if (++low == size) break;
380 #endif /* MAKEFIXED */
383 Update the window with the last wsize (normally 32K) bytes written before
384 returning. If window does not exist yet, create it. This is only called
385 when a window is already in use, or when output has been written during this
386 inflate call, but the end of the deflate stream has not been reached yet.
387 It is also called to create a window for dictionary data when a dictionary
390 Providing output buffers larger than 32K to inflate() should provide a speed
391 advantage, since only the last 32K of output is copied to the sliding window
392 upon return from inflate(), and since all distances after the first 32K of
393 output will fall in the output data, making match copies simpler and faster.
394 The advantage may be dependent on the size of the processor's data caches.
396 local int updatewindow(strm, end, copy)
401 struct inflate_state FAR *state;
404 state = (struct inflate_state FAR *)strm->state;
406 /* if it hasn't been done already, allocate space for the window */
407 if (state->window == Z_NULL) {
408 state->window = (unsigned char FAR *)
409 ZALLOC(strm, 1U << state->wbits,
410 sizeof(unsigned char));
411 if (state->window == Z_NULL) return 1;
414 /* if window not in use yet, initialize */
415 if (state->wsize == 0) {
416 state->wsize = 1U << state->wbits;
421 /* copy state->wsize or less output bytes into the circular window */
422 if (copy >= state->wsize) {
423 zmemcpy(state->window, end - state->wsize, state->wsize);
425 state->whave = state->wsize;
428 dist = state->wsize - state->wnext;
429 if (dist > copy) dist = copy;
430 zmemcpy(state->window + state->wnext, end - copy, dist);
433 zmemcpy(state->window, end - copy, copy);
435 state->whave = state->wsize;
438 state->wnext += dist;
439 if (state->wnext == state->wsize) state->wnext = 0;
440 if (state->whave < state->wsize) state->whave += dist;
446 /* Macros for inflate(): */
448 /* check function to use adler32() for zlib or crc32() for gzip */
450 # define UPDATE(check, buf, len) \
451 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
453 # define UPDATE(check, buf, len) adler32(check, buf, len)
456 /* check macros for header crc */
458 # define CRC2(check, word) \
460 hbuf[0] = (unsigned char)(word); \
461 hbuf[1] = (unsigned char)((word) >> 8); \
462 check = crc32(check, hbuf, 2); \
465 # define CRC4(check, word) \
467 hbuf[0] = (unsigned char)(word); \
468 hbuf[1] = (unsigned char)((word) >> 8); \
469 hbuf[2] = (unsigned char)((word) >> 16); \
470 hbuf[3] = (unsigned char)((word) >> 24); \
471 check = crc32(check, hbuf, 4); \
475 /* Load registers with state in inflate() for speed */
478 put = strm->next_out; \
479 left = strm->avail_out; \
480 next = strm->next_in; \
481 have = strm->avail_in; \
482 hold = state->hold; \
483 bits = state->bits; \
486 /* Restore state from registers in inflate() */
489 strm->next_out = put; \
490 strm->avail_out = left; \
491 strm->next_in = next; \
492 strm->avail_in = have; \
493 state->hold = hold; \
494 state->bits = bits; \
497 /* Clear the input bit accumulator */
504 /* Get a byte of input into the bit accumulator, or return from inflate()
505 if there is no input available. */
508 if (have == 0) goto inf_leave; \
510 hold += (unsigned long)(*next++) << bits; \
514 /* Assure that there are at least n bits in the bit accumulator. If there is
515 not enough available input to do that, then return from inflate(). */
516 #define NEEDBITS(n) \
518 while (bits < (unsigned)(n)) \
522 /* Return the low n bits of the bit accumulator (n < 16) */
524 ((unsigned)hold & ((1U << (n)) - 1))
526 /* Remove n bits from the bit accumulator */
527 #define DROPBITS(n) \
530 bits -= (unsigned)(n); \
533 /* Remove zero to seven bits as needed to go to a byte boundary */
541 inflate() uses a state machine to process as much input data and generate as
542 much output data as possible before returning. The state machine is
543 structured roughly as follows:
545 for (;;) switch (state) {
548 if (not enough input data or output space to make progress)
550 ... make progress ...
556 so when inflate() is called again, the same case is attempted again, and
557 if the appropriate resources are provided, the machine proceeds to the
558 next state. The NEEDBITS() macro is usually the way the state evaluates
559 whether it can proceed or should return. NEEDBITS() does the return if
560 the requested bits are not available. The typical use of the BITS macros
564 ... do something with BITS(n) ...
567 where NEEDBITS(n) either returns from inflate() if there isn't enough
568 input left to load n bits into the accumulator, or it continues. BITS(n)
569 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
570 the low n bits off the accumulator. INITBITS() clears the accumulator
571 and sets the number of available bits to zero. BYTEBITS() discards just
572 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
573 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
575 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
576 if there is no input available. The decoding of variable length codes uses
577 PULLBYTE() directly in order to pull just enough bytes to decode the next
580 Some states loop until they get enough input, making sure that enough
581 state information is maintained to continue the loop where it left off
582 if NEEDBITS() returns in the loop. For example, want, need, and keep
583 would all have to actually be part of the saved state in case NEEDBITS()
587 while (want < need) {
589 keep[want++] = BITS(n);
595 As shown above, if the next state is also the next case, then the break
598 A state may also return if there is not enough output space available to
599 complete that state. Those states are copying stored data, writing a
600 literal byte, and copying a matching string.
602 When returning, a "goto inf_leave" is used to update the total counters,
603 update the check value, and determine whether any progress has been made
604 during that inflate() call in order to return the proper return code.
605 Progress is defined as a change in either strm->avail_in or strm->avail_out.
606 When there is a window, goto inf_leave will update the window with the last
607 output written. If a goto inf_leave occurs in the middle of decompression
608 and there is no window currently, goto inf_leave will create one and copy
609 output to the window for the next call of inflate().
611 In this implementation, the flush parameter of inflate() only affects the
612 return code (per zlib.h). inflate() always writes as much as possible to
613 strm->next_out, given the space available and the provided input--the effect
614 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
615 the allocation of and copying into a sliding window until necessary, which
616 provides the effect documented in zlib.h for Z_FINISH when the entire input
617 stream available. So the only thing the flush parameter actually does is:
618 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
619 will return Z_BUF_ERROR if it has not reached the end of the stream.
622 int ZEXPORT inflate(strm, flush)
626 struct inflate_state FAR *state;
627 z_const unsigned char FAR *next; /* next input */
628 unsigned char FAR *put; /* next output */
629 unsigned have, left; /* available input and output */
630 unsigned long hold; /* bit buffer */
631 unsigned bits; /* bits in bit buffer */
632 unsigned in, out; /* save starting available input and output */
633 unsigned copy; /* number of stored or match bytes to copy */
634 unsigned char FAR *from; /* where to copy match bytes from */
635 code here; /* current decoding table entry */
636 code last; /* parent table entry */
637 unsigned len; /* length to copy for repeats, bits to drop */
638 int ret; /* return code */
640 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
642 static const unsigned short order[19] = /* permutation of code lengths */
643 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
645 if (inflateStateCheck(strm) || strm->next_out == Z_NULL ||
646 (strm->next_in == Z_NULL && strm->avail_in != 0))
647 return Z_STREAM_ERROR;
649 state = (struct inflate_state FAR *)strm->state;
650 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
656 switch (state->mode) {
658 if (state->wrap == 0) {
659 state->mode = TYPEDO;
664 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
665 if (state->wbits == 0)
667 state->check = crc32(0L, Z_NULL, 0);
668 CRC2(state->check, hold);
673 state->flags = 0; /* expect zlib header */
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 Tracev((stderr, "inflate: zlib header ok\n"));
701 strm->adler = state->check = adler32(0L, Z_NULL, 0);
702 state->mode = hold & 0x200 ? DICTID : TYPE;
708 state->flags = (int)(hold);
709 if ((state->flags & 0xff) != Z_DEFLATED) {
710 strm->msg = (char *)"unknown compression method";
714 if (state->flags & 0xe000) {
715 strm->msg = (char *)"unknown header flags set";
719 if (state->head != Z_NULL)
720 state->head->text = (int)((hold >> 8) & 1);
721 if ((state->flags & 0x0200) && (state->wrap & 4))
722 CRC2(state->check, hold);
727 if (state->head != Z_NULL)
728 state->head->time = hold;
729 if ((state->flags & 0x0200) && (state->wrap & 4))
730 CRC4(state->check, hold);
735 if (state->head != Z_NULL) {
736 state->head->xflags = (int)(hold & 0xff);
737 state->head->os = (int)(hold >> 8);
739 if ((state->flags & 0x0200) && (state->wrap & 4))
740 CRC2(state->check, hold);
744 if (state->flags & 0x0400) {
746 state->length = (unsigned)(hold);
747 if (state->head != Z_NULL)
748 state->head->extra_len = (unsigned)hold;
749 if ((state->flags & 0x0200) && (state->wrap & 4))
750 CRC2(state->check, hold);
753 else if (state->head != Z_NULL)
754 state->head->extra = Z_NULL;
757 if (state->flags & 0x0400) {
758 copy = state->length;
759 if (copy > have) copy = have;
761 if (state->head != Z_NULL &&
762 state->head->extra != Z_NULL &&
763 (len = state->head->extra_len - state->length) <
764 state->head->extra_max) {
765 zmemcpy(state->head->extra + len, next,
766 len + copy > state->head->extra_max ?
767 state->head->extra_max - len : copy);
769 if ((state->flags & 0x0200) && (state->wrap & 4))
770 state->check = crc32(state->check, next, copy);
773 state->length -= copy;
775 if (state->length) goto inf_leave;
780 if (state->flags & 0x0800) {
781 if (have == 0) goto inf_leave;
784 len = (unsigned)(next[copy++]);
785 if (state->head != Z_NULL &&
786 state->head->name != Z_NULL &&
787 state->length < state->head->name_max)
788 state->head->name[state->length++] = (Bytef)len;
789 } while (len && copy < have);
790 if ((state->flags & 0x0200) && (state->wrap & 4))
791 state->check = crc32(state->check, next, copy);
794 if (len) goto inf_leave;
796 else if (state->head != Z_NULL)
797 state->head->name = Z_NULL;
799 state->mode = COMMENT;
801 if (state->flags & 0x1000) {
802 if (have == 0) goto inf_leave;
805 len = (unsigned)(next[copy++]);
806 if (state->head != Z_NULL &&
807 state->head->comment != Z_NULL &&
808 state->length < state->head->comm_max)
809 state->head->comment[state->length++] = (Bytef)len;
810 } while (len && copy < have);
811 if ((state->flags & 0x0200) && (state->wrap & 4))
812 state->check = crc32(state->check, next, copy);
815 if (len) goto inf_leave;
817 else if (state->head != Z_NULL)
818 state->head->comment = Z_NULL;
821 if (state->flags & 0x0200) {
823 if ((state->wrap & 4) && hold != (state->check & 0xffff)) {
824 strm->msg = (char *)"header crc mismatch";
830 if (state->head != Z_NULL) {
831 state->head->hcrc = (int)((state->flags >> 9) & 1);
832 state->head->done = 1;
834 strm->adler = state->check = crc32(0L, Z_NULL, 0);
840 strm->adler = state->check = ZSWAP32(hold);
844 if (state->havedict == 0) {
848 strm->adler = state->check = adler32(0L, Z_NULL, 0);
851 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
859 state->last = BITS(1);
862 case 0: /* stored block */
863 Tracev((stderr, "inflate: stored block%s\n",
864 state->last ? " (last)" : ""));
865 state->mode = STORED;
867 case 1: /* fixed block */
869 Tracev((stderr, "inflate: fixed codes block%s\n",
870 state->last ? " (last)" : ""));
871 state->mode = LEN_; /* decode codes */
872 if (flush == Z_TREES) {
877 case 2: /* dynamic block */
878 Tracev((stderr, "inflate: dynamic codes block%s\n",
879 state->last ? " (last)" : ""));
883 strm->msg = (char *)"invalid block type";
889 BYTEBITS(); /* go to byte boundary */
891 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
892 strm->msg = (char *)"invalid stored block lengths";
896 state->length = (unsigned)hold & 0xffff;
897 Tracev((stderr, "inflate: stored length %u\n",
901 if (flush == Z_TREES) goto inf_leave;
905 copy = state->length;
907 if (copy > have) copy = have;
908 if (copy > left) copy = left;
909 if (copy == 0) goto inf_leave;
910 zmemcpy(put, next, copy);
915 state->length -= copy;
918 Tracev((stderr, "inflate: stored end\n"));
923 state->nlen = BITS(5) + 257;
925 state->ndist = BITS(5) + 1;
927 state->ncode = BITS(4) + 4;
929 #ifndef PKZIP_BUG_WORKAROUND
930 if (state->nlen > 286 || state->ndist > 30) {
931 strm->msg = (char *)"too many length or distance symbols";
936 Tracev((stderr, "inflate: table sizes ok\n"));
938 state->mode = LENLENS;
940 while (state->have < state->ncode) {
942 state->lens[order[state->have++]] = (unsigned short)BITS(3);
945 while (state->have < 19)
946 state->lens[order[state->have++]] = 0;
947 state->next = state->codes;
948 state->lencode = (const code FAR *)(state->next);
950 ret = inflate_table(CODES, state->lens, 19, &(state->next),
951 &(state->lenbits), state->work);
953 strm->msg = (char *)"invalid code lengths set";
957 Tracev((stderr, "inflate: code lengths ok\n"));
959 state->mode = CODELENS;
961 while (state->have < state->nlen + state->ndist) {
963 here = state->lencode[BITS(state->lenbits)];
964 if ((unsigned)(here.bits) <= bits) break;
969 state->lens[state->have++] = here.val;
972 if (here.val == 16) {
973 NEEDBITS(here.bits + 2);
975 if (state->have == 0) {
976 strm->msg = (char *)"invalid bit length repeat";
980 len = state->lens[state->have - 1];
984 else if (here.val == 17) {
985 NEEDBITS(here.bits + 3);
992 NEEDBITS(here.bits + 7);
998 if (state->have + copy > state->nlen + state->ndist) {
999 strm->msg = (char *)"invalid bit length repeat";
1004 state->lens[state->have++] = (unsigned short)len;
1008 /* handle error breaks in while */
1009 if (state->mode == BAD) break;
1011 /* check for end-of-block code (better have one) */
1012 if (state->lens[256] == 0) {
1013 strm->msg = (char *)"invalid code -- missing end-of-block";
1018 /* build code tables -- note: do not change the lenbits or distbits
1019 values here (9 and 6) without reading the comments in inftrees.h
1020 concerning the ENOUGH constants, which depend on those values */
1021 state->next = state->codes;
1022 state->lencode = (const code FAR *)(state->next);
1024 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1025 &(state->lenbits), state->work);
1027 strm->msg = (char *)"invalid literal/lengths set";
1031 state->distcode = (const code FAR *)(state->next);
1032 state->distbits = 6;
1033 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1034 &(state->next), &(state->distbits), state->work);
1036 strm->msg = (char *)"invalid distances set";
1040 Tracev((stderr, "inflate: codes ok\n"));
1042 if (flush == Z_TREES) goto inf_leave;
1046 if (have >= 6 && left >= 258) {
1048 inflate_fast(strm, out);
1050 if (state->mode == TYPE)
1056 here = state->lencode[BITS(state->lenbits)];
1057 if ((unsigned)(here.bits) <= bits) break;
1060 if (here.op && (here.op & 0xf0) == 0) {
1063 here = state->lencode[last.val +
1064 (BITS(last.bits + last.op) >> last.bits)];
1065 if ((unsigned)(last.bits + here.bits) <= bits) break;
1068 DROPBITS(last.bits);
1069 state->back += last.bits;
1071 DROPBITS(here.bits);
1072 state->back += here.bits;
1073 state->length = (unsigned)here.val;
1074 if ((int)(here.op) == 0) {
1075 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1076 "inflate: literal '%c'\n" :
1077 "inflate: literal 0x%02x\n", here.val));
1082 Tracevv((stderr, "inflate: end of block\n"));
1088 strm->msg = (char *)"invalid literal/length code";
1092 state->extra = (unsigned)(here.op) & 15;
1093 state->mode = LENEXT;
1096 NEEDBITS(state->extra);
1097 state->length += BITS(state->extra);
1098 DROPBITS(state->extra);
1099 state->back += state->extra;
1101 Tracevv((stderr, "inflate: length %u\n", state->length));
1102 state->was = state->length;
1106 here = state->distcode[BITS(state->distbits)];
1107 if ((unsigned)(here.bits) <= bits) break;
1110 if ((here.op & 0xf0) == 0) {
1113 here = state->distcode[last.val +
1114 (BITS(last.bits + last.op) >> last.bits)];
1115 if ((unsigned)(last.bits + here.bits) <= bits) break;
1118 DROPBITS(last.bits);
1119 state->back += last.bits;
1121 DROPBITS(here.bits);
1122 state->back += here.bits;
1124 strm->msg = (char *)"invalid distance code";
1128 state->offset = (unsigned)here.val;
1129 state->extra = (unsigned)(here.op) & 15;
1130 state->mode = DISTEXT;
1133 NEEDBITS(state->extra);
1134 state->offset += BITS(state->extra);
1135 DROPBITS(state->extra);
1136 state->back += state->extra;
1138 #ifdef INFLATE_STRICT
1139 if (state->offset > state->dmax) {
1140 strm->msg = (char *)"invalid distance too far back";
1145 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1146 state->mode = MATCH;
1148 if (left == 0) goto inf_leave;
1150 if (state->offset > copy) { /* copy from window */
1151 copy = state->offset - copy;
1152 if (copy > state->whave) {
1154 strm->msg = (char *)"invalid distance too far back";
1158 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1159 Trace((stderr, "inflate.c too far\n"));
1160 copy -= state->whave;
1161 if (copy > state->length) copy = state->length;
1162 if (copy > left) copy = left;
1164 state->length -= copy;
1168 if (state->length == 0) state->mode = LEN;
1172 if (copy > state->wnext) {
1173 copy -= state->wnext;
1174 from = state->window + (state->wsize - copy);
1177 from = state->window + (state->wnext - copy);
1178 if (copy > state->length) copy = state->length;
1180 else { /* copy from output */
1181 from = put - state->offset;
1182 copy = state->length;
1184 if (copy > left) copy = left;
1186 state->length -= copy;
1190 if (state->length == 0) state->mode = LEN;
1193 if (left == 0) goto inf_leave;
1194 *put++ = (unsigned char)(state->length);
1202 strm->total_out += out;
1203 state->total += out;
1204 if ((state->wrap & 4) && out)
1205 strm->adler = state->check =
1206 UPDATE(state->check, put - out, out);
1208 if ((state->wrap & 4) && (
1210 state->flags ? hold :
1212 ZSWAP32(hold)) != state->check) {
1213 strm->msg = (char *)"incorrect data check";
1218 Tracev((stderr, "inflate: check matches trailer\n"));
1221 state->mode = LENGTH;
1223 if (state->wrap && state->flags) {
1225 if (hold != (state->total & 0xffffffffUL)) {
1226 strm->msg = (char *)"incorrect length check";
1231 Tracev((stderr, "inflate: length matches trailer\n"));
1245 return Z_STREAM_ERROR;
1249 Return from inflate(), updating the total counts and the check value.
1250 If there was no progress during the inflate() call, return a buffer
1251 error. Call updatewindow() to create and/or update the window state.
1252 Note: a memory error from inflate() is non-recoverable.
1256 if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1257 (state->mode < CHECK || flush != Z_FINISH)))
1258 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1262 in -= strm->avail_in;
1263 out -= strm->avail_out;
1264 strm->total_in += in;
1265 strm->total_out += out;
1266 state->total += out;
1267 if ((state->wrap & 4) && out)
1268 strm->adler = state->check =
1269 UPDATE(state->check, strm->next_out - out, out);
1270 strm->data_type = (int)state->bits + (state->last ? 64 : 0) +
1271 (state->mode == TYPE ? 128 : 0) +
1272 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1273 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1278 int ZEXPORT inflateEnd(strm)
1281 struct inflate_state FAR *state;
1282 if (inflateStateCheck(strm))
1283 return Z_STREAM_ERROR;
1284 state = (struct inflate_state FAR *)strm->state;
1285 if (state->window != Z_NULL) ZFREE(strm, state->window);
1286 ZFREE(strm, strm->state);
1287 strm->state = Z_NULL;
1288 Tracev((stderr, "inflate: end\n"));
1292 int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1297 struct inflate_state FAR *state;
1300 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1301 state = (struct inflate_state FAR *)strm->state;
1303 /* copy dictionary */
1304 if (state->whave && dictionary != Z_NULL) {
1305 zmemcpy(dictionary, state->window + state->wnext,
1306 state->whave - state->wnext);
1307 zmemcpy(dictionary + state->whave - state->wnext,
1308 state->window, state->wnext);
1310 if (dictLength != Z_NULL)
1311 *dictLength = state->whave;
1315 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1317 const Bytef *dictionary;
1320 struct inflate_state FAR *state;
1321 unsigned long dictid;
1325 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1326 state = (struct inflate_state FAR *)strm->state;
1327 if (state->wrap != 0 && state->mode != DICT)
1328 return Z_STREAM_ERROR;
1330 /* check for correct dictionary identifier */
1331 if (state->mode == DICT) {
1332 dictid = adler32(0L, Z_NULL, 0);
1333 dictid = adler32(dictid, dictionary, dictLength);
1334 if (dictid != state->check)
1335 return Z_DATA_ERROR;
1338 /* copy dictionary to window using updatewindow(), which will amend the
1339 existing dictionary if appropriate */
1340 ret = updatewindow(strm, dictionary + dictLength, dictLength);
1345 state->havedict = 1;
1346 Tracev((stderr, "inflate: dictionary set\n"));
1350 int ZEXPORT inflateGetHeader(strm, head)
1354 struct inflate_state FAR *state;
1357 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1358 state = (struct inflate_state FAR *)strm->state;
1359 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1361 /* save header structure */
1368 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1369 or when out of input. When called, *have is the number of pattern bytes
1370 found in order so far, in 0..3. On return *have is updated to the new
1371 state. If on return *have equals four, then the pattern was found and the
1372 return value is how many bytes were read including the last byte of the
1373 pattern. If *have is less than four, then the pattern has not been found
1374 yet and the return value is len. In the latter case, syncsearch() can be
1375 called again with more data and the *have state. *have is initialized to
1376 zero for the first call.
1378 local unsigned syncsearch(have, buf, len)
1380 const unsigned char FAR *buf;
1388 while (next < len && got < 4) {
1389 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1401 int ZEXPORT inflateSync(strm)
1404 unsigned len; /* number of bytes to look at or looked at */
1405 unsigned long in, out; /* temporary to save total_in and total_out */
1406 unsigned char buf[4]; /* to restore bit buffer to byte string */
1407 struct inflate_state FAR *state;
1409 /* check parameters */
1410 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1411 state = (struct inflate_state FAR *)strm->state;
1412 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1414 /* if first time, start search in bit buffer */
1415 if (state->mode != SYNC) {
1417 state->hold <<= state->bits & 7;
1418 state->bits -= state->bits & 7;
1420 while (state->bits >= 8) {
1421 buf[len++] = (unsigned char)(state->hold);
1426 syncsearch(&(state->have), buf, len);
1429 /* search available input */
1430 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1431 strm->avail_in -= len;
1432 strm->next_in += len;
1433 strm->total_in += len;
1435 /* return no joy or set up to restart inflate() on a new block */
1436 if (state->have != 4) return Z_DATA_ERROR;
1437 in = strm->total_in; out = strm->total_out;
1439 strm->total_in = in; strm->total_out = out;
1445 Returns true if inflate is currently at the end of a block generated by
1446 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1447 implementation to provide an additional safety check. PPP uses
1448 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1449 block. When decompressing, PPP checks that at the end of input packet,
1450 inflate is waiting for these length bytes.
1452 int ZEXPORT inflateSyncPoint(strm)
1455 struct inflate_state FAR *state;
1457 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1458 state = (struct inflate_state FAR *)strm->state;
1459 return state->mode == STORED && state->bits == 0;
1462 int ZEXPORT inflateCopy(dest, source)
1466 struct inflate_state FAR *state;
1467 struct inflate_state FAR *copy;
1468 unsigned char FAR *window;
1472 if (inflateStateCheck(source) || dest == Z_NULL)
1473 return Z_STREAM_ERROR;
1474 state = (struct inflate_state FAR *)source->state;
1476 /* allocate space */
1477 copy = (struct inflate_state FAR *)
1478 ZALLOC(source, 1, sizeof(struct inflate_state));
1479 if (copy == Z_NULL) return Z_MEM_ERROR;
1481 if (state->window != Z_NULL) {
1482 window = (unsigned char FAR *)
1483 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1484 if (window == Z_NULL) {
1485 ZFREE(source, copy);
1491 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1492 zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1494 if (state->lencode >= state->codes &&
1495 state->lencode <= state->codes + ENOUGH - 1) {
1496 copy->lencode = copy->codes + (state->lencode - state->codes);
1497 copy->distcode = copy->codes + (state->distcode - state->codes);
1499 copy->next = copy->codes + (state->next - state->codes);
1500 if (window != Z_NULL) {
1501 wsize = 1U << state->wbits;
1502 zmemcpy(window, state->window, wsize);
1504 copy->window = window;
1505 dest->state = (struct internal_state FAR *)copy;
1509 int ZEXPORT inflateUndermine(strm, subvert)
1513 struct inflate_state FAR *state;
1515 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1516 state = (struct inflate_state FAR *)strm->state;
1517 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1518 state->sane = !subvert;
1523 return Z_DATA_ERROR;
1527 int ZEXPORT inflateValidate(strm, check)
1531 struct inflate_state FAR *state;
1533 if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1534 state = (struct inflate_state FAR *)strm->state;
1542 long ZEXPORT inflateMark(strm)
1545 struct inflate_state FAR *state;
1547 if (inflateStateCheck(strm))
1549 state = (struct inflate_state FAR *)strm->state;
1550 return (long)(((unsigned long)((long)state->back)) << 16) +
1551 (state->mode == COPY ? state->length :
1552 (state->mode == MATCH ? state->was - state->length : 0));
1555 unsigned long ZEXPORT inflateCodesUsed(strm)
1558 struct inflate_state FAR *state;
1559 if (inflateStateCheck(strm)) return (unsigned long)-1;
1560 state = (struct inflate_state FAR *)strm->state;
1561 return (unsigned long)(state->next - state->codes);