1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2010 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 void fixedtables OF((struct inflate_state FAR *state));
96 local int updatewindow OF((z_streamp strm, unsigned out));
98 void makefixed OF((void));
100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
103 int ZEXPORT inflateReset(strm)
106 struct inflate_state FAR *state;
108 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
109 state = (struct inflate_state FAR *)strm->state;
110 strm->total_in = strm->total_out = state->total = 0;
112 strm->adler = 1; /* to support ill-conceived Java test suite */
116 state->dmax = 32768U;
117 state->head = Z_NULL;
123 state->lencode = state->distcode = state->next = state->codes;
126 Tracev((stderr, "inflate: reset\n"));
130 int ZEXPORT inflateReset2(strm, windowBits)
135 struct inflate_state FAR *state;
138 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
139 state = (struct inflate_state FAR *)strm->state;
141 /* extract wrap request from windowBits parameter */
142 if (windowBits < 0) {
144 windowBits = -windowBits;
147 wrap = (windowBits >> 4) + 1;
154 /* set number of window bits, free window if different */
155 if (windowBits && (windowBits < 8 || windowBits > 15))
156 return Z_STREAM_ERROR;
157 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
158 ZFREE(strm, state->window);
159 state->window = Z_NULL;
162 /* update state and reset the rest of it */
164 state->wbits = (unsigned)windowBits;
165 return inflateReset(strm);
168 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
175 struct inflate_state FAR *state;
177 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
178 stream_size != (int)(sizeof(z_stream)))
179 return Z_VERSION_ERROR;
180 if (strm == Z_NULL) return Z_STREAM_ERROR;
181 strm->msg = Z_NULL; /* in case we return an error */
182 if (strm->zalloc == (alloc_func)0) {
183 strm->zalloc = zcalloc;
184 strm->opaque = (voidpf)0;
186 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
187 state = (struct inflate_state FAR *)
188 ZALLOC(strm, 1, sizeof(struct inflate_state));
189 if (state == Z_NULL) return Z_MEM_ERROR;
190 Tracev((stderr, "inflate: allocated\n"));
191 strm->state = (struct internal_state FAR *)state;
192 state->window = Z_NULL;
193 ret = inflateReset2(strm, windowBits);
196 strm->state = Z_NULL;
201 int ZEXPORT inflateInit_(strm, version, stream_size)
206 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
209 int ZEXPORT inflatePrime(strm, bits, value)
214 struct inflate_state FAR *state;
216 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
217 state = (struct inflate_state FAR *)strm->state;
223 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
224 value &= (1L << bits) - 1;
225 state->hold += value << state->bits;
231 Return state with length and distance decoding tables and index sizes set to
232 fixed code decoding. Normally this returns fixed tables from inffixed.h.
233 If BUILDFIXED is defined, then instead this routine builds the tables the
234 first time it's called, and returns those tables the first time and
235 thereafter. This reduces the size of the code by about 2K bytes, in
236 exchange for a little execution time. However, BUILDFIXED should not be
237 used for threaded applications, since the rewriting of the tables and virgin
238 may not be thread-safe.
240 local void fixedtables(state)
241 struct inflate_state FAR *state;
244 static int virgin = 1;
245 static code *lenfix, *distfix;
246 static code fixed[544];
248 /* build fixed huffman tables if first call (may not be thread safe) */
253 /* literal/length table */
255 while (sym < 144) state->lens[sym++] = 8;
256 while (sym < 256) state->lens[sym++] = 9;
257 while (sym < 280) state->lens[sym++] = 7;
258 while (sym < 288) state->lens[sym++] = 8;
262 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
266 while (sym < 32) state->lens[sym++] = 5;
269 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
271 /* do this just once */
274 #else /* !BUILDFIXED */
275 # include "inffixed.h"
276 #endif /* BUILDFIXED */
277 state->lencode = lenfix;
279 state->distcode = distfix;
287 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
288 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
289 those tables to stdout, which would be piped to inffixed.h. A small program
290 can simply call makefixed to do this:
292 void makefixed(void);
300 Then that can be linked with zlib built with MAKEFIXED defined and run:
307 struct inflate_state state;
310 puts(" /* inffixed.h -- table for decoding fixed codes");
311 puts(" * Generated automatically by makefixed().");
314 puts(" /* WARNING: this file should *not* be used by applications.");
315 puts(" It is part of the implementation of this library and is");
316 puts(" subject to change. Applications should only use zlib.h.");
320 printf(" static const code lenfix[%u] = {", size);
323 if ((low % 7) == 0) printf("\n ");
324 printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
325 state.lencode[low].val);
326 if (++low == size) break;
331 printf("\n static const code distfix[%u] = {", size);
334 if ((low % 6) == 0) printf("\n ");
335 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
336 state.distcode[low].val);
337 if (++low == size) break;
342 #endif /* MAKEFIXED */
345 Update the window with the last wsize (normally 32K) bytes written before
346 returning. If window does not exist yet, create it. This is only called
347 when a window is already in use, or when output has been written during this
348 inflate call, but the end of the deflate stream has not been reached yet.
349 It is also called to create a window for dictionary data when a dictionary
352 Providing output buffers larger than 32K to inflate() should provide a speed
353 advantage, since only the last 32K of output is copied to the sliding window
354 upon return from inflate(), and since all distances after the first 32K of
355 output will fall in the output data, making match copies simpler and faster.
356 The advantage may be dependent on the size of the processor's data caches.
358 local int updatewindow(strm, out)
362 struct inflate_state FAR *state;
365 state = (struct inflate_state FAR *)strm->state;
367 /* if it hasn't been done already, allocate space for the window */
368 if (state->window == Z_NULL) {
369 state->window = (unsigned char FAR *)
370 ZALLOC(strm, 1U << state->wbits,
371 sizeof(unsigned char));
372 if (state->window == Z_NULL) return 1;
375 /* if window not in use yet, initialize */
376 if (state->wsize == 0) {
377 state->wsize = 1U << state->wbits;
382 /* copy state->wsize or less output bytes into the circular window */
383 copy = out - strm->avail_out;
384 if (copy >= state->wsize) {
385 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
387 state->whave = state->wsize;
390 dist = state->wsize - state->wnext;
391 if (dist > copy) dist = copy;
392 zmemcpy(state->window + state->wnext, strm->next_out - copy, dist);
395 zmemcpy(state->window, strm->next_out - copy, copy);
397 state->whave = state->wsize;
400 state->wnext += dist;
401 if (state->wnext == state->wsize) state->wnext = 0;
402 if (state->whave < state->wsize) state->whave += dist;
408 /* Macros for inflate(): */
410 /* check function to use adler32() for zlib or crc32() for gzip */
412 # define UPDATE(check, buf, len) \
413 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
415 # define UPDATE(check, buf, len) adler32(check, buf, len)
418 /* check macros for header crc */
420 # define CRC2(check, word) \
422 hbuf[0] = (unsigned char)(word); \
423 hbuf[1] = (unsigned char)((word) >> 8); \
424 check = crc32(check, hbuf, 2); \
427 # define CRC4(check, word) \
429 hbuf[0] = (unsigned char)(word); \
430 hbuf[1] = (unsigned char)((word) >> 8); \
431 hbuf[2] = (unsigned char)((word) >> 16); \
432 hbuf[3] = (unsigned char)((word) >> 24); \
433 check = crc32(check, hbuf, 4); \
437 /* Load registers with state in inflate() for speed */
440 put = strm->next_out; \
441 left = strm->avail_out; \
442 next = strm->next_in; \
443 have = strm->avail_in; \
444 hold = state->hold; \
445 bits = state->bits; \
448 /* Restore state from registers in inflate() */
451 strm->next_out = put; \
452 strm->avail_out = left; \
453 strm->next_in = next; \
454 strm->avail_in = have; \
455 state->hold = hold; \
456 state->bits = bits; \
459 /* Clear the input bit accumulator */
466 /* Get a byte of input into the bit accumulator, or return from inflate()
467 if there is no input available. */
470 if (have == 0) goto inf_leave; \
472 hold += (unsigned long)(*next++) << bits; \
476 /* Assure that there are at least n bits in the bit accumulator. If there is
477 not enough available input to do that, then return from inflate(). */
478 #define NEEDBITS(n) \
480 while (bits < (unsigned)(n)) \
484 /* Return the low n bits of the bit accumulator (n < 16) */
486 ((unsigned)hold & ((1U << (n)) - 1))
488 /* Remove n bits from the bit accumulator */
489 #define DROPBITS(n) \
492 bits -= (unsigned)(n); \
495 /* Remove zero to seven bits as needed to go to a byte boundary */
502 /* Reverse the bytes in a 32-bit value */
504 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
505 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
508 inflate() uses a state machine to process as much input data and generate as
509 much output data as possible before returning. The state machine is
510 structured roughly as follows:
512 for (;;) switch (state) {
515 if (not enough input data or output space to make progress)
517 ... make progress ...
523 so when inflate() is called again, the same case is attempted again, and
524 if the appropriate resources are provided, the machine proceeds to the
525 next state. The NEEDBITS() macro is usually the way the state evaluates
526 whether it can proceed or should return. NEEDBITS() does the return if
527 the requested bits are not available. The typical use of the BITS macros
531 ... do something with BITS(n) ...
534 where NEEDBITS(n) either returns from inflate() if there isn't enough
535 input left to load n bits into the accumulator, or it continues. BITS(n)
536 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
537 the low n bits off the accumulator. INITBITS() clears the accumulator
538 and sets the number of available bits to zero. BYTEBITS() discards just
539 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
540 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
542 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
543 if there is no input available. The decoding of variable length codes uses
544 PULLBYTE() directly in order to pull just enough bytes to decode the next
547 Some states loop until they get enough input, making sure that enough
548 state information is maintained to continue the loop where it left off
549 if NEEDBITS() returns in the loop. For example, want, need, and keep
550 would all have to actually be part of the saved state in case NEEDBITS()
554 while (want < need) {
556 keep[want++] = BITS(n);
562 As shown above, if the next state is also the next case, then the break
565 A state may also return if there is not enough output space available to
566 complete that state. Those states are copying stored data, writing a
567 literal byte, and copying a matching string.
569 When returning, a "goto inf_leave" is used to update the total counters,
570 update the check value, and determine whether any progress has been made
571 during that inflate() call in order to return the proper return code.
572 Progress is defined as a change in either strm->avail_in or strm->avail_out.
573 When there is a window, goto inf_leave will update the window with the last
574 output written. If a goto inf_leave occurs in the middle of decompression
575 and there is no window currently, goto inf_leave will create one and copy
576 output to the window for the next call of inflate().
578 In this implementation, the flush parameter of inflate() only affects the
579 return code (per zlib.h). inflate() always writes as much as possible to
580 strm->next_out, given the space available and the provided input--the effect
581 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
582 the allocation of and copying into a sliding window until necessary, which
583 provides the effect documented in zlib.h for Z_FINISH when the entire input
584 stream available. So the only thing the flush parameter actually does is:
585 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
586 will return Z_BUF_ERROR if it has not reached the end of the stream.
589 int ZEXPORT inflate(strm, flush)
593 struct inflate_state FAR *state;
594 unsigned char FAR *next; /* next input */
595 unsigned char FAR *put; /* next output */
596 unsigned have, left; /* available input and output */
597 unsigned long hold; /* bit buffer */
598 unsigned bits; /* bits in bit buffer */
599 unsigned in, out; /* save starting available input and output */
600 unsigned copy; /* number of stored or match bytes to copy */
601 unsigned char FAR *from; /* where to copy match bytes from */
602 code here; /* current decoding table entry */
603 code last; /* parent table entry */
604 unsigned len; /* length to copy for repeats, bits to drop */
605 int ret; /* return code */
607 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
609 static const unsigned short order[19] = /* permutation of code lengths */
610 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
612 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
613 (strm->next_in == Z_NULL && strm->avail_in != 0))
614 return Z_STREAM_ERROR;
616 state = (struct inflate_state FAR *)strm->state;
617 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
623 switch (state->mode) {
625 if (state->wrap == 0) {
626 state->mode = TYPEDO;
631 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
632 state->check = crc32(0L, Z_NULL, 0);
633 CRC2(state->check, hold);
638 state->flags = 0; /* expect zlib header */
639 if (state->head != Z_NULL)
640 state->head->done = -1;
641 if (!(state->wrap & 1) || /* check if zlib header allowed */
645 ((BITS(8) << 8) + (hold >> 8)) % 31) {
646 strm->msg = (char *)"incorrect header check";
650 if (BITS(4) != Z_DEFLATED) {
651 strm->msg = (char *)"unknown compression method";
657 if (state->wbits == 0)
659 else if (len > state->wbits) {
660 strm->msg = (char *)"invalid window size";
664 state->dmax = 1U << len;
665 Tracev((stderr, "inflate: zlib header ok\n"));
666 strm->adler = state->check = adler32(0L, Z_NULL, 0);
667 state->mode = hold & 0x200 ? DICTID : TYPE;
673 state->flags = (int)(hold);
674 if ((state->flags & 0xff) != Z_DEFLATED) {
675 strm->msg = (char *)"unknown compression method";
679 if (state->flags & 0xe000) {
680 strm->msg = (char *)"unknown header flags set";
684 if (state->head != Z_NULL)
685 state->head->text = (int)((hold >> 8) & 1);
686 if (state->flags & 0x0200) CRC2(state->check, hold);
691 if (state->head != Z_NULL)
692 state->head->time = hold;
693 if (state->flags & 0x0200) CRC4(state->check, hold);
698 if (state->head != Z_NULL) {
699 state->head->xflags = (int)(hold & 0xff);
700 state->head->os = (int)(hold >> 8);
702 if (state->flags & 0x0200) CRC2(state->check, hold);
706 if (state->flags & 0x0400) {
708 state->length = (unsigned)(hold);
709 if (state->head != Z_NULL)
710 state->head->extra_len = (unsigned)hold;
711 if (state->flags & 0x0200) CRC2(state->check, hold);
714 else if (state->head != Z_NULL)
715 state->head->extra = Z_NULL;
718 if (state->flags & 0x0400) {
719 copy = state->length;
720 if (copy > have) copy = have;
722 if (state->head != Z_NULL &&
723 state->head->extra != Z_NULL) {
724 len = state->head->extra_len - state->length;
725 zmemcpy(state->head->extra + len, next,
726 len + copy > state->head->extra_max ?
727 state->head->extra_max - len : copy);
729 if (state->flags & 0x0200)
730 state->check = crc32(state->check, next, copy);
733 state->length -= copy;
735 if (state->length) goto inf_leave;
740 if (state->flags & 0x0800) {
741 if (have == 0) goto inf_leave;
744 len = (unsigned)(next[copy++]);
745 if (state->head != Z_NULL &&
746 state->head->name != Z_NULL &&
747 state->length < state->head->name_max)
748 state->head->name[state->length++] = len;
749 } while (len && copy < have);
750 if (state->flags & 0x0200)
751 state->check = crc32(state->check, next, copy);
754 if (len) goto inf_leave;
756 else if (state->head != Z_NULL)
757 state->head->name = Z_NULL;
759 state->mode = COMMENT;
761 if (state->flags & 0x1000) {
762 if (have == 0) goto inf_leave;
765 len = (unsigned)(next[copy++]);
766 if (state->head != Z_NULL &&
767 state->head->comment != Z_NULL &&
768 state->length < state->head->comm_max)
769 state->head->comment[state->length++] = len;
770 } while (len && copy < have);
771 if (state->flags & 0x0200)
772 state->check = crc32(state->check, next, copy);
775 if (len) goto inf_leave;
777 else if (state->head != Z_NULL)
778 state->head->comment = Z_NULL;
781 if (state->flags & 0x0200) {
783 if (hold != (state->check & 0xffff)) {
784 strm->msg = (char *)"header crc mismatch";
790 if (state->head != Z_NULL) {
791 state->head->hcrc = (int)((state->flags >> 9) & 1);
792 state->head->done = 1;
794 strm->adler = state->check = crc32(0L, Z_NULL, 0);
800 strm->adler = state->check = REVERSE(hold);
804 if (state->havedict == 0) {
808 strm->adler = state->check = adler32(0L, Z_NULL, 0);
811 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
819 state->last = BITS(1);
822 case 0: /* stored block */
823 Tracev((stderr, "inflate: stored block%s\n",
824 state->last ? " (last)" : ""));
825 state->mode = STORED;
827 case 1: /* fixed block */
829 Tracev((stderr, "inflate: fixed codes block%s\n",
830 state->last ? " (last)" : ""));
831 state->mode = LEN_; /* decode codes */
832 if (flush == Z_TREES) {
837 case 2: /* dynamic block */
838 Tracev((stderr, "inflate: dynamic codes block%s\n",
839 state->last ? " (last)" : ""));
843 strm->msg = (char *)"invalid block type";
849 BYTEBITS(); /* go to byte boundary */
851 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
852 strm->msg = (char *)"invalid stored block lengths";
856 state->length = (unsigned)hold & 0xffff;
857 Tracev((stderr, "inflate: stored length %u\n",
861 if (flush == Z_TREES) goto inf_leave;
865 copy = state->length;
867 if (copy > have) copy = have;
868 if (copy > left) copy = left;
869 if (copy == 0) goto inf_leave;
870 zmemcpy(put, next, copy);
875 state->length -= copy;
878 Tracev((stderr, "inflate: stored end\n"));
883 state->nlen = BITS(5) + 257;
885 state->ndist = BITS(5) + 1;
887 state->ncode = BITS(4) + 4;
889 #ifndef PKZIP_BUG_WORKAROUND
890 if (state->nlen > 286 || state->ndist > 30) {
891 strm->msg = (char *)"too many length or distance symbols";
896 Tracev((stderr, "inflate: table sizes ok\n"));
898 state->mode = LENLENS;
900 while (state->have < state->ncode) {
902 state->lens[order[state->have++]] = (unsigned short)BITS(3);
905 while (state->have < 19)
906 state->lens[order[state->have++]] = 0;
907 state->next = state->codes;
908 state->lencode = (code const FAR *)(state->next);
910 ret = inflate_table(CODES, state->lens, 19, &(state->next),
911 &(state->lenbits), state->work);
913 strm->msg = (char *)"invalid code lengths set";
917 Tracev((stderr, "inflate: code lengths ok\n"));
919 state->mode = CODELENS;
921 while (state->have < state->nlen + state->ndist) {
923 here = state->lencode[BITS(state->lenbits)];
924 if ((unsigned)(here.bits) <= bits) break;
930 state->lens[state->have++] = here.val;
933 if (here.val == 16) {
934 NEEDBITS(here.bits + 2);
936 if (state->have == 0) {
937 strm->msg = (char *)"invalid bit length repeat";
941 len = state->lens[state->have - 1];
945 else if (here.val == 17) {
946 NEEDBITS(here.bits + 3);
953 NEEDBITS(here.bits + 7);
959 if (state->have + copy > state->nlen + state->ndist) {
960 strm->msg = (char *)"invalid bit length repeat";
965 state->lens[state->have++] = (unsigned short)len;
969 /* handle error breaks in while */
970 if (state->mode == BAD) break;
972 /* check for end-of-block code (better have one) */
973 if (state->lens[256] == 0) {
974 strm->msg = (char *)"invalid code -- missing end-of-block";
979 /* build code tables -- note: do not change the lenbits or distbits
980 values here (9 and 6) without reading the comments in inftrees.h
981 concerning the ENOUGH constants, which depend on those values */
982 state->next = state->codes;
983 state->lencode = (code const FAR *)(state->next);
985 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
986 &(state->lenbits), state->work);
988 strm->msg = (char *)"invalid literal/lengths set";
992 state->distcode = (code const FAR *)(state->next);
994 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
995 &(state->next), &(state->distbits), state->work);
997 strm->msg = (char *)"invalid distances set";
1001 Tracev((stderr, "inflate: codes ok\n"));
1003 if (flush == Z_TREES) goto inf_leave;
1007 if (have >= 6 && left >= 258) {
1009 inflate_fast(strm, out);
1011 if (state->mode == TYPE)
1017 here = state->lencode[BITS(state->lenbits)];
1018 if ((unsigned)(here.bits) <= bits) break;
1021 if (here.op && (here.op & 0xf0) == 0) {
1024 here = state->lencode[last.val +
1025 (BITS(last.bits + last.op) >> last.bits)];
1026 if ((unsigned)(last.bits + here.bits) <= bits) break;
1029 DROPBITS(last.bits);
1030 state->back += last.bits;
1032 DROPBITS(here.bits);
1033 state->back += here.bits;
1034 state->length = (unsigned)here.val;
1035 if ((int)(here.op) == 0) {
1036 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1037 "inflate: literal '%c'\n" :
1038 "inflate: literal 0x%02x\n", here.val));
1043 Tracevv((stderr, "inflate: end of block\n"));
1049 strm->msg = (char *)"invalid literal/length code";
1053 state->extra = (unsigned)(here.op) & 15;
1054 state->mode = LENEXT;
1057 NEEDBITS(state->extra);
1058 state->length += BITS(state->extra);
1059 DROPBITS(state->extra);
1060 state->back += state->extra;
1062 Tracevv((stderr, "inflate: length %u\n", state->length));
1063 state->was = state->length;
1067 here = state->distcode[BITS(state->distbits)];
1068 if ((unsigned)(here.bits) <= bits) break;
1071 if ((here.op & 0xf0) == 0) {
1074 here = state->distcode[last.val +
1075 (BITS(last.bits + last.op) >> last.bits)];
1076 if ((unsigned)(last.bits + here.bits) <= bits) break;
1079 DROPBITS(last.bits);
1080 state->back += last.bits;
1082 DROPBITS(here.bits);
1083 state->back += here.bits;
1085 strm->msg = (char *)"invalid distance code";
1089 state->offset = (unsigned)here.val;
1090 state->extra = (unsigned)(here.op) & 15;
1091 state->mode = DISTEXT;
1094 NEEDBITS(state->extra);
1095 state->offset += BITS(state->extra);
1096 DROPBITS(state->extra);
1097 state->back += state->extra;
1099 #ifdef INFLATE_STRICT
1100 if (state->offset > state->dmax) {
1101 strm->msg = (char *)"invalid distance too far back";
1106 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1107 state->mode = MATCH;
1109 if (left == 0) goto inf_leave;
1111 if (state->offset > copy) { /* copy from window */
1112 copy = state->offset - copy;
1113 if (copy > state->whave) {
1115 strm->msg = (char *)"invalid distance too far back";
1119 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1120 Trace((stderr, "inflate.c too far\n"));
1121 copy -= state->whave;
1122 if (copy > state->length) copy = state->length;
1123 if (copy > left) copy = left;
1125 state->length -= copy;
1129 if (state->length == 0) state->mode = LEN;
1133 if (copy > state->wnext) {
1134 copy -= state->wnext;
1135 from = state->window + (state->wsize - copy);
1138 from = state->window + (state->wnext - copy);
1139 if (copy > state->length) copy = state->length;
1141 else { /* copy from output */
1142 from = put - state->offset;
1143 copy = state->length;
1145 if (copy > left) copy = left;
1147 state->length -= copy;
1151 if (state->length == 0) state->mode = LEN;
1154 if (left == 0) goto inf_leave;
1155 *put++ = (unsigned char)(state->length);
1163 strm->total_out += out;
1164 state->total += out;
1166 strm->adler = state->check =
1167 UPDATE(state->check, put - out, out);
1171 state->flags ? hold :
1173 REVERSE(hold)) != state->check) {
1174 strm->msg = (char *)"incorrect data check";
1179 Tracev((stderr, "inflate: check matches trailer\n"));
1182 state->mode = LENGTH;
1184 if (state->wrap && state->flags) {
1186 if (hold != (state->total & 0xffffffffUL)) {
1187 strm->msg = (char *)"incorrect length check";
1192 Tracev((stderr, "inflate: length matches trailer\n"));
1206 return Z_STREAM_ERROR;
1210 Return from inflate(), updating the total counts and the check value.
1211 If there was no progress during the inflate() call, return a buffer
1212 error. Call updatewindow() to create and/or update the window state.
1213 Note: a memory error from inflate() is non-recoverable.
1217 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1218 if (updatewindow(strm, out)) {
1222 in -= strm->avail_in;
1223 out -= strm->avail_out;
1224 strm->total_in += in;
1225 strm->total_out += out;
1226 state->total += out;
1227 if (state->wrap && out)
1228 strm->adler = state->check =
1229 UPDATE(state->check, strm->next_out - out, out);
1230 strm->data_type = state->bits + (state->last ? 64 : 0) +
1231 (state->mode == TYPE ? 128 : 0) +
1232 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1233 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1238 int ZEXPORT inflateEnd(strm)
1241 struct inflate_state FAR *state;
1242 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1243 return Z_STREAM_ERROR;
1244 state = (struct inflate_state FAR *)strm->state;
1245 if (state->window != Z_NULL) ZFREE(strm, state->window);
1246 ZFREE(strm, strm->state);
1247 strm->state = Z_NULL;
1248 Tracev((stderr, "inflate: end\n"));
1252 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1254 const Bytef *dictionary;
1257 struct inflate_state FAR *state;
1261 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1262 state = (struct inflate_state FAR *)strm->state;
1263 if (state->wrap != 0 && state->mode != DICT)
1264 return Z_STREAM_ERROR;
1266 /* check for correct dictionary id */
1267 if (state->mode == DICT) {
1268 id = adler32(0L, Z_NULL, 0);
1269 id = adler32(id, dictionary, dictLength);
1270 if (id != state->check)
1271 return Z_DATA_ERROR;
1274 /* copy dictionary to window */
1275 if (updatewindow(strm, strm->avail_out)) {
1279 if (dictLength > state->wsize) {
1280 zmemcpy(state->window, dictionary + dictLength - state->wsize,
1282 state->whave = state->wsize;
1285 zmemcpy(state->window + state->wsize - dictLength, dictionary,
1287 state->whave = dictLength;
1289 state->havedict = 1;
1290 Tracev((stderr, "inflate: dictionary set\n"));
1294 int ZEXPORT inflateGetHeader(strm, head)
1298 struct inflate_state FAR *state;
1301 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1302 state = (struct inflate_state FAR *)strm->state;
1303 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1305 /* save header structure */
1312 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1313 or when out of input. When called, *have is the number of pattern bytes
1314 found in order so far, in 0..3. On return *have is updated to the new
1315 state. If on return *have equals four, then the pattern was found and the
1316 return value is how many bytes were read including the last byte of the
1317 pattern. If *have is less than four, then the pattern has not been found
1318 yet and the return value is len. In the latter case, syncsearch() can be
1319 called again with more data and the *have state. *have is initialized to
1320 zero for the first call.
1322 local unsigned syncsearch(have, buf, len)
1324 unsigned char FAR *buf;
1332 while (next < len && got < 4) {
1333 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1345 int ZEXPORT inflateSync(strm)
1348 unsigned len; /* number of bytes to look at or looked at */
1349 unsigned long in, out; /* temporary to save total_in and total_out */
1350 unsigned char buf[4]; /* to restore bit buffer to byte string */
1351 struct inflate_state FAR *state;
1353 /* check parameters */
1354 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1355 state = (struct inflate_state FAR *)strm->state;
1356 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1358 /* if first time, start search in bit buffer */
1359 if (state->mode != SYNC) {
1361 state->hold <<= state->bits & 7;
1362 state->bits -= state->bits & 7;
1364 while (state->bits >= 8) {
1365 buf[len++] = (unsigned char)(state->hold);
1370 syncsearch(&(state->have), buf, len);
1373 /* search available input */
1374 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1375 strm->avail_in -= len;
1376 strm->next_in += len;
1377 strm->total_in += len;
1379 /* return no joy or set up to restart inflate() on a new block */
1380 if (state->have != 4) return Z_DATA_ERROR;
1381 in = strm->total_in; out = strm->total_out;
1383 strm->total_in = in; strm->total_out = out;
1389 Returns true if inflate is currently at the end of a block generated by
1390 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1391 implementation to provide an additional safety check. PPP uses
1392 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1393 block. When decompressing, PPP checks that at the end of input packet,
1394 inflate is waiting for these length bytes.
1396 int ZEXPORT inflateSyncPoint(strm)
1399 struct inflate_state FAR *state;
1401 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1402 state = (struct inflate_state FAR *)strm->state;
1403 return state->mode == STORED && state->bits == 0;
1406 int ZEXPORT inflateCopy(dest, source)
1410 struct inflate_state FAR *state;
1411 struct inflate_state FAR *copy;
1412 unsigned char FAR *window;
1416 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1417 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1418 return Z_STREAM_ERROR;
1419 state = (struct inflate_state FAR *)source->state;
1421 /* allocate space */
1422 copy = (struct inflate_state FAR *)
1423 ZALLOC(source, 1, sizeof(struct inflate_state));
1424 if (copy == Z_NULL) return Z_MEM_ERROR;
1426 if (state->window != Z_NULL) {
1427 window = (unsigned char FAR *)
1428 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1429 if (window == Z_NULL) {
1430 ZFREE(source, copy);
1436 zmemcpy(dest, source, sizeof(z_stream));
1437 zmemcpy(copy, state, sizeof(struct inflate_state));
1438 if (state->lencode >= state->codes &&
1439 state->lencode <= state->codes + ENOUGH - 1) {
1440 copy->lencode = copy->codes + (state->lencode - state->codes);
1441 copy->distcode = copy->codes + (state->distcode - state->codes);
1443 copy->next = copy->codes + (state->next - state->codes);
1444 if (window != Z_NULL) {
1445 wsize = 1U << state->wbits;
1446 zmemcpy(window, state->window, wsize);
1448 copy->window = window;
1449 dest->state = (struct internal_state FAR *)copy;
1453 int ZEXPORT inflateUndermine(strm, subvert)
1457 struct inflate_state FAR *state;
1459 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1460 state = (struct inflate_state FAR *)strm->state;
1461 state->sane = !subvert;
1462 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1466 return Z_DATA_ERROR;
1470 long ZEXPORT inflateMark(strm)
1473 struct inflate_state FAR *state;
1475 if (strm == Z_NULL || strm->state == Z_NULL) return -1L << 16;
1476 state = (struct inflate_state FAR *)strm->state;
1477 return ((long)(state->back) << 16) +
1478 (state->mode == COPY ? state->length :
1479 (state->mode == MATCH ? state->was - state->length : 0));