1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2012 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 #if defined(__GNUC__) && __GNUC__>=7
95 #pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
98 /* function prototypes */
99 local void fixedtables OF((struct inflate_state FAR *state));
100 local int updatewindow OF((z_streamp strm, const unsigned char FAR *end,
103 void makefixed OF((void));
105 local unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf,
108 int ZEXPORT inflateResetKeep(strm)
111 struct inflate_state FAR *state;
113 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
114 state = (struct inflate_state FAR *)strm->state;
115 strm->total_in = strm->total_out = state->total = 0;
117 if (state->wrap) /* to support ill-conceived Java test suite */
118 strm->adler = state->wrap & 1;
122 state->dmax = 32768U;
123 state->head = Z_NULL;
126 state->lencode = state->distcode = state->next = state->codes;
129 Tracev((stderr, "inflate: reset\n"));
133 int ZEXPORT inflateReset(strm)
136 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;
143 return inflateResetKeep(strm);
146 int ZEXPORT inflateReset2(strm, windowBits)
151 struct inflate_state FAR *state;
154 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
155 state = (struct inflate_state FAR *)strm->state;
157 /* extract wrap request from windowBits parameter */
158 if (windowBits < 0) {
160 windowBits = -windowBits;
163 wrap = (windowBits >> 4) + 1;
170 /* set number of window bits, free window if different */
171 if (windowBits && (windowBits < 8 || windowBits > 15))
172 return Z_STREAM_ERROR;
173 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
174 ZFREE(strm, state->window);
175 state->window = Z_NULL;
178 /* update state and reset the rest of it */
180 state->wbits = (unsigned)windowBits;
181 return inflateReset(strm);
184 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
191 struct inflate_state FAR *state;
193 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
194 stream_size != (int)(sizeof(z_stream)))
195 return Z_VERSION_ERROR;
196 if (strm == Z_NULL) return Z_STREAM_ERROR;
197 strm->msg = Z_NULL; /* in case we return an error */
198 if (strm->zalloc == (alloc_func)0) {
200 return Z_STREAM_ERROR;
202 strm->zalloc = zcalloc;
203 strm->opaque = (voidpf)0;
206 if (strm->zfree == (free_func)0)
208 return Z_STREAM_ERROR;
210 strm->zfree = zcfree;
212 state = (struct inflate_state FAR *)
213 ZALLOC(strm, 1, sizeof(struct inflate_state));
214 if (state == Z_NULL) return Z_MEM_ERROR;
215 Tracev((stderr, "inflate: allocated\n"));
216 strm->state = (struct internal_state FAR *)state;
217 state->window = Z_NULL;
218 ret = inflateReset2(strm, windowBits);
221 strm->state = Z_NULL;
226 int ZEXPORT inflateInit_(strm, version, stream_size)
231 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
234 int ZEXPORT inflatePrime(strm, bits, value)
239 struct inflate_state FAR *state;
241 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
242 state = (struct inflate_state FAR *)strm->state;
248 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
249 value &= (1L << bits) - 1;
250 state->hold += value << state->bits;
256 Return state with length and distance decoding tables and index sizes set to
257 fixed code decoding. Normally this returns fixed tables from inffixed.h.
258 If BUILDFIXED is defined, then instead this routine builds the tables the
259 first time it's called, and returns those tables the first time and
260 thereafter. This reduces the size of the code by about 2K bytes, in
261 exchange for a little execution time. However, BUILDFIXED should not be
262 used for threaded applications, since the rewriting of the tables and virgin
263 may not be thread-safe.
265 local void fixedtables(state)
266 struct inflate_state FAR *state;
269 static int virgin = 1;
270 static code *lenfix, *distfix;
271 static code fixed[544];
273 /* build fixed huffman tables if first call (may not be thread safe) */
278 /* literal/length table */
280 while (sym < 144) state->lens[sym++] = 8;
281 while (sym < 256) state->lens[sym++] = 9;
282 while (sym < 280) state->lens[sym++] = 7;
283 while (sym < 288) state->lens[sym++] = 8;
287 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
291 while (sym < 32) state->lens[sym++] = 5;
294 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
296 /* do this just once */
299 #else /* !BUILDFIXED */
300 # include "inffixed.h"
301 #endif /* BUILDFIXED */
302 state->lencode = lenfix;
304 state->distcode = distfix;
312 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
313 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
314 those tables to stdout, which would be piped to inffixed.h. A small program
315 can simply call makefixed to do this:
317 void makefixed(void);
325 Then that can be linked with zlib built with MAKEFIXED defined and run:
332 struct inflate_state state;
335 puts(" /* inffixed.h -- table for decoding fixed codes");
336 puts(" * Generated automatically by makefixed().");
339 puts(" /* WARNING: this file should *not* be used by applications.");
340 puts(" It is part of the implementation of this library and is");
341 puts(" subject to change. Applications should only use zlib.h.");
345 printf(" static const code lenfix[%u] = {", size);
348 if ((low % 7) == 0) printf("\n ");
349 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
350 state.lencode[low].bits, state.lencode[low].val);
351 if (++low == size) break;
356 printf("\n static const code distfix[%u] = {", size);
359 if ((low % 6) == 0) printf("\n ");
360 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
361 state.distcode[low].val);
362 if (++low == size) break;
367 #endif /* MAKEFIXED */
370 Update the window with the last wsize (normally 32K) bytes written before
371 returning. If window does not exist yet, create it. This is only called
372 when a window is already in use, or when output has been written during this
373 inflate call, but the end of the deflate stream has not been reached yet.
374 It is also called to create a window for dictionary data when a dictionary
377 Providing output buffers larger than 32K to inflate() should provide a speed
378 advantage, since only the last 32K of output is copied to the sliding window
379 upon return from inflate(), and since all distances after the first 32K of
380 output will fall in the output data, making match copies simpler and faster.
381 The advantage may be dependent on the size of the processor's data caches.
383 local int updatewindow(strm, end, copy)
388 struct inflate_state FAR *state;
391 state = (struct inflate_state FAR *)strm->state;
393 /* if it hasn't been done already, allocate space for the window */
394 if (state->window == Z_NULL) {
395 state->window = (unsigned char FAR *)
396 ZALLOC(strm, 1U << state->wbits,
397 sizeof(unsigned char));
398 if (state->window == Z_NULL) return 1;
401 /* if window not in use yet, initialize */
402 if (state->wsize == 0) {
403 state->wsize = 1U << state->wbits;
408 /* copy state->wsize or less output bytes into the circular window */
409 if (copy >= state->wsize) {
410 zmemcpy(state->window, end - state->wsize, state->wsize);
412 state->whave = state->wsize;
415 dist = state->wsize - state->wnext;
416 if (dist > copy) dist = copy;
417 zmemcpy(state->window + state->wnext, end - copy, dist);
420 zmemcpy(state->window, end - copy, copy);
422 state->whave = state->wsize;
425 state->wnext += dist;
426 if (state->wnext == state->wsize) state->wnext = 0;
427 if (state->whave < state->wsize) state->whave += dist;
433 /* Macros for inflate(): */
435 /* check function to use adler32() for zlib or crc32() for gzip */
437 # define UPDATE(check, buf, len) \
438 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
440 # define UPDATE(check, buf, len) adler32(check, buf, len)
443 /* check macros for header crc */
445 # define CRC2(check, word) \
447 hbuf[0] = (unsigned char)(word); \
448 hbuf[1] = (unsigned char)((word) >> 8); \
449 check = crc32(check, hbuf, 2); \
452 # define CRC4(check, word) \
454 hbuf[0] = (unsigned char)(word); \
455 hbuf[1] = (unsigned char)((word) >> 8); \
456 hbuf[2] = (unsigned char)((word) >> 16); \
457 hbuf[3] = (unsigned char)((word) >> 24); \
458 check = crc32(check, hbuf, 4); \
462 /* Load registers with state in inflate() for speed */
465 put = strm->next_out; \
466 left = strm->avail_out; \
467 next = strm->next_in; \
468 have = strm->avail_in; \
469 hold = state->hold; \
470 bits = state->bits; \
473 /* Restore state from registers in inflate() */
476 strm->next_out = put; \
477 strm->avail_out = left; \
478 strm->next_in = next; \
479 strm->avail_in = have; \
480 state->hold = hold; \
481 state->bits = bits; \
484 /* Clear the input bit accumulator */
491 /* Get a byte of input into the bit accumulator, or return from inflate()
492 if there is no input available. */
495 if (have == 0) goto inf_leave; \
497 hold += (unsigned long)(*next++) << bits; \
501 /* Assure that there are at least n bits in the bit accumulator. If there is
502 not enough available input to do that, then return from inflate(). */
503 #define NEEDBITS(n) \
505 while (bits < (unsigned)(n)) \
509 /* Return the low n bits of the bit accumulator (n < 16) */
511 ((unsigned)hold & ((1U << (n)) - 1))
513 /* Remove n bits from the bit accumulator */
514 #define DROPBITS(n) \
517 bits -= (unsigned)(n); \
520 /* Remove zero to seven bits as needed to go to a byte boundary */
528 inflate() uses a state machine to process as much input data and generate as
529 much output data as possible before returning. The state machine is
530 structured roughly as follows:
532 for (;;) switch (state) {
535 if (not enough input data or output space to make progress)
537 ... make progress ...
543 so when inflate() is called again, the same case is attempted again, and
544 if the appropriate resources are provided, the machine proceeds to the
545 next state. The NEEDBITS() macro is usually the way the state evaluates
546 whether it can proceed or should return. NEEDBITS() does the return if
547 the requested bits are not available. The typical use of the BITS macros
551 ... do something with BITS(n) ...
554 where NEEDBITS(n) either returns from inflate() if there isn't enough
555 input left to load n bits into the accumulator, or it continues. BITS(n)
556 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
557 the low n bits off the accumulator. INITBITS() clears the accumulator
558 and sets the number of available bits to zero. BYTEBITS() discards just
559 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
560 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
562 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
563 if there is no input available. The decoding of variable length codes uses
564 PULLBYTE() directly in order to pull just enough bytes to decode the next
567 Some states loop until they get enough input, making sure that enough
568 state information is maintained to continue the loop where it left off
569 if NEEDBITS() returns in the loop. For example, want, need, and keep
570 would all have to actually be part of the saved state in case NEEDBITS()
574 while (want < need) {
576 keep[want++] = BITS(n);
582 As shown above, if the next state is also the next case, then the break
585 A state may also return if there is not enough output space available to
586 complete that state. Those states are copying stored data, writing a
587 literal byte, and copying a matching string.
589 When returning, a "goto inf_leave" is used to update the total counters,
590 update the check value, and determine whether any progress has been made
591 during that inflate() call in order to return the proper return code.
592 Progress is defined as a change in either strm->avail_in or strm->avail_out.
593 When there is a window, goto inf_leave will update the window with the last
594 output written. If a goto inf_leave occurs in the middle of decompression
595 and there is no window currently, goto inf_leave will create one and copy
596 output to the window for the next call of inflate().
598 In this implementation, the flush parameter of inflate() only affects the
599 return code (per zlib.h). inflate() always writes as much as possible to
600 strm->next_out, given the space available and the provided input--the effect
601 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
602 the allocation of and copying into a sliding window until necessary, which
603 provides the effect documented in zlib.h for Z_FINISH when the entire input
604 stream available. So the only thing the flush parameter actually does is:
605 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
606 will return Z_BUF_ERROR if it has not reached the end of the stream.
609 int ZEXPORT inflate(strm, flush)
613 struct inflate_state FAR *state;
614 z_const unsigned char FAR *next; /* next input */
615 unsigned char FAR *put; /* next output */
616 unsigned have, left; /* available input and output */
617 unsigned long hold; /* bit buffer */
618 unsigned bits; /* bits in bit buffer */
619 unsigned in, out; /* save starting available input and output */
620 unsigned copy; /* number of stored or match bytes to copy */
621 unsigned char FAR *from; /* where to copy match bytes from */
622 code here; /* current decoding table entry */
623 code last; /* parent table entry */
624 unsigned len; /* length to copy for repeats, bits to drop */
625 int ret; /* return code */
627 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
629 static const unsigned short order[19] = /* permutation of code lengths */
630 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
632 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
633 (strm->next_in == Z_NULL && strm->avail_in != 0))
634 return Z_STREAM_ERROR;
636 state = (struct inflate_state FAR *)strm->state;
637 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
643 switch (state->mode) {
645 if (state->wrap == 0) {
646 state->mode = TYPEDO;
651 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
652 state->check = crc32(0L, Z_NULL, 0);
653 CRC2(state->check, hold);
658 state->flags = 0; /* expect zlib header */
659 if (state->head != Z_NULL)
660 state->head->done = -1;
661 if (!(state->wrap & 1) || /* check if zlib header allowed */
665 ((BITS(8) << 8) + (hold >> 8)) % 31) {
666 strm->msg = (char *)"incorrect header check";
670 if (BITS(4) != Z_DEFLATED) {
671 strm->msg = (char *)"unknown compression method";
677 if (state->wbits == 0)
679 else if (len > state->wbits) {
680 strm->msg = (char *)"invalid window size";
684 state->dmax = 1U << len;
685 Tracev((stderr, "inflate: zlib header ok\n"));
686 strm->adler = state->check = adler32(0L, Z_NULL, 0);
687 state->mode = hold & 0x200 ? DICTID : TYPE;
693 state->flags = (int)(hold);
694 if ((state->flags & 0xff) != Z_DEFLATED) {
695 strm->msg = (char *)"unknown compression method";
699 if (state->flags & 0xe000) {
700 strm->msg = (char *)"unknown header flags set";
704 if (state->head != Z_NULL)
705 state->head->text = (int)((hold >> 8) & 1);
706 if (state->flags & 0x0200) CRC2(state->check, hold);
711 if (state->head != Z_NULL)
712 state->head->time = hold;
713 if (state->flags & 0x0200) CRC4(state->check, hold);
718 if (state->head != Z_NULL) {
719 state->head->xflags = (int)(hold & 0xff);
720 state->head->os = (int)(hold >> 8);
722 if (state->flags & 0x0200) CRC2(state->check, hold);
726 if (state->flags & 0x0400) {
728 state->length = (unsigned)(hold);
729 if (state->head != Z_NULL)
730 state->head->extra_len = (unsigned)hold;
731 if (state->flags & 0x0200) CRC2(state->check, hold);
734 else if (state->head != Z_NULL)
735 state->head->extra = Z_NULL;
738 if (state->flags & 0x0400) {
739 copy = state->length;
740 if (copy > have) copy = have;
742 if (state->head != Z_NULL &&
743 state->head->extra != Z_NULL) {
744 len = state->head->extra_len - state->length;
745 zmemcpy(state->head->extra + len, next,
746 len + copy > state->head->extra_max ?
747 state->head->extra_max - len : copy);
749 if (state->flags & 0x0200)
750 state->check = crc32(state->check, next, copy);
753 state->length -= copy;
755 if (state->length) goto inf_leave;
760 if (state->flags & 0x0800) {
761 if (have == 0) goto inf_leave;
764 len = (unsigned)(next[copy++]);
765 if (state->head != Z_NULL &&
766 state->head->name != Z_NULL &&
767 state->length < state->head->name_max)
768 state->head->name[state->length++] = len;
769 } while (len && copy < have);
770 if (state->flags & 0x0200)
771 state->check = crc32(state->check, next, copy);
774 if (len) goto inf_leave;
776 else if (state->head != Z_NULL)
777 state->head->name = Z_NULL;
779 state->mode = COMMENT;
781 if (state->flags & 0x1000) {
782 if (have == 0) goto inf_leave;
785 len = (unsigned)(next[copy++]);
786 if (state->head != Z_NULL &&
787 state->head->comment != Z_NULL &&
788 state->length < state->head->comm_max)
789 state->head->comment[state->length++] = len;
790 } while (len && copy < have);
791 if (state->flags & 0x0200)
792 state->check = crc32(state->check, next, copy);
795 if (len) goto inf_leave;
797 else if (state->head != Z_NULL)
798 state->head->comment = Z_NULL;
801 if (state->flags & 0x0200) {
803 if (hold != (state->check & 0xffff)) {
804 strm->msg = (char *)"header crc mismatch";
810 if (state->head != Z_NULL) {
811 state->head->hcrc = (int)((state->flags >> 9) & 1);
812 state->head->done = 1;
814 strm->adler = state->check = crc32(0L, Z_NULL, 0);
820 strm->adler = state->check = ZSWAP32(hold);
824 if (state->havedict == 0) {
828 strm->adler = state->check = adler32(0L, Z_NULL, 0);
831 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
839 state->last = BITS(1);
842 case 0: /* stored block */
843 Tracev((stderr, "inflate: stored block%s\n",
844 state->last ? " (last)" : ""));
845 state->mode = STORED;
847 case 1: /* fixed block */
849 Tracev((stderr, "inflate: fixed codes block%s\n",
850 state->last ? " (last)" : ""));
851 state->mode = LEN_; /* decode codes */
852 if (flush == Z_TREES) {
857 case 2: /* dynamic block */
858 Tracev((stderr, "inflate: dynamic codes block%s\n",
859 state->last ? " (last)" : ""));
863 strm->msg = (char *)"invalid block type";
869 BYTEBITS(); /* go to byte boundary */
871 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
872 strm->msg = (char *)"invalid stored block lengths";
876 state->length = (unsigned)hold & 0xffff;
877 Tracev((stderr, "inflate: stored length %u\n",
881 if (flush == Z_TREES) goto inf_leave;
885 copy = state->length;
887 if (copy > have) copy = have;
888 if (copy > left) copy = left;
889 if (copy == 0) goto inf_leave;
890 zmemcpy(put, next, copy);
895 state->length -= copy;
898 Tracev((stderr, "inflate: stored end\n"));
903 state->nlen = BITS(5) + 257;
905 state->ndist = BITS(5) + 1;
907 state->ncode = BITS(4) + 4;
909 #ifndef PKZIP_BUG_WORKAROUND
910 if (state->nlen > 286 || state->ndist > 30) {
911 strm->msg = (char *)"too many length or distance symbols";
916 Tracev((stderr, "inflate: table sizes ok\n"));
918 state->mode = LENLENS;
920 while (state->have < state->ncode) {
922 state->lens[order[state->have++]] = (unsigned short)BITS(3);
925 while (state->have < 19)
926 state->lens[order[state->have++]] = 0;
927 state->next = state->codes;
928 state->lencode = (const code FAR *)(state->next);
930 ret = inflate_table(CODES, state->lens, 19, &(state->next),
931 &(state->lenbits), state->work);
933 strm->msg = (char *)"invalid code lengths set";
937 Tracev((stderr, "inflate: code lengths ok\n"));
939 state->mode = CODELENS;
941 while (state->have < state->nlen + state->ndist) {
943 here = state->lencode[BITS(state->lenbits)];
944 if ((unsigned)(here.bits) <= bits) break;
949 state->lens[state->have++] = here.val;
952 if (here.val == 16) {
953 NEEDBITS(here.bits + 2);
955 if (state->have == 0) {
956 strm->msg = (char *)"invalid bit length repeat";
960 len = state->lens[state->have - 1];
964 else if (here.val == 17) {
965 NEEDBITS(here.bits + 3);
972 NEEDBITS(here.bits + 7);
978 if (state->have + copy > state->nlen + state->ndist) {
979 strm->msg = (char *)"invalid bit length repeat";
984 state->lens[state->have++] = (unsigned short)len;
988 /* handle error breaks in while */
989 if (state->mode == BAD) break;
991 /* check for end-of-block code (better have one) */
992 if (state->lens[256] == 0) {
993 strm->msg = (char *)"invalid code -- missing end-of-block";
998 /* build code tables -- note: do not change the lenbits or distbits
999 values here (9 and 6) without reading the comments in inftrees.h
1000 concerning the ENOUGH constants, which depend on those values */
1001 state->next = state->codes;
1002 state->lencode = (const code FAR *)(state->next);
1004 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1005 &(state->lenbits), state->work);
1007 strm->msg = (char *)"invalid literal/lengths set";
1011 state->distcode = (const code FAR *)(state->next);
1012 state->distbits = 6;
1013 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1014 &(state->next), &(state->distbits), state->work);
1016 strm->msg = (char *)"invalid distances set";
1020 Tracev((stderr, "inflate: codes ok\n"));
1022 if (flush == Z_TREES) goto inf_leave;
1026 if (have >= 6 && left >= 258) {
1028 inflate_fast(strm, out);
1030 if (state->mode == TYPE)
1036 here = state->lencode[BITS(state->lenbits)];
1037 if ((unsigned)(here.bits) <= bits) break;
1040 if (here.op && (here.op & 0xf0) == 0) {
1043 here = state->lencode[last.val +
1044 (BITS(last.bits + last.op) >> last.bits)];
1045 if ((unsigned)(last.bits + here.bits) <= bits) break;
1048 DROPBITS(last.bits);
1049 state->back += last.bits;
1051 DROPBITS(here.bits);
1052 state->back += here.bits;
1053 state->length = (unsigned)here.val;
1054 if ((int)(here.op) == 0) {
1055 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1056 "inflate: literal '%c'\n" :
1057 "inflate: literal 0x%02x\n", here.val));
1062 Tracevv((stderr, "inflate: end of block\n"));
1068 strm->msg = (char *)"invalid literal/length code";
1072 state->extra = (unsigned)(here.op) & 15;
1073 state->mode = LENEXT;
1076 NEEDBITS(state->extra);
1077 state->length += BITS(state->extra);
1078 DROPBITS(state->extra);
1079 state->back += state->extra;
1081 Tracevv((stderr, "inflate: length %u\n", state->length));
1082 state->was = state->length;
1086 here = state->distcode[BITS(state->distbits)];
1087 if ((unsigned)(here.bits) <= bits) break;
1090 if ((here.op & 0xf0) == 0) {
1093 here = state->distcode[last.val +
1094 (BITS(last.bits + last.op) >> last.bits)];
1095 if ((unsigned)(last.bits + here.bits) <= bits) break;
1098 DROPBITS(last.bits);
1099 state->back += last.bits;
1101 DROPBITS(here.bits);
1102 state->back += here.bits;
1104 strm->msg = (char *)"invalid distance code";
1108 state->offset = (unsigned)here.val;
1109 state->extra = (unsigned)(here.op) & 15;
1110 state->mode = DISTEXT;
1113 NEEDBITS(state->extra);
1114 state->offset += BITS(state->extra);
1115 DROPBITS(state->extra);
1116 state->back += state->extra;
1118 #ifdef INFLATE_STRICT
1119 if (state->offset > state->dmax) {
1120 strm->msg = (char *)"invalid distance too far back";
1125 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1126 state->mode = MATCH;
1128 if (left == 0) goto inf_leave;
1130 if (state->offset > copy) { /* copy from window */
1131 copy = state->offset - copy;
1132 if (copy > state->whave) {
1134 strm->msg = (char *)"invalid distance too far back";
1138 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1139 Trace((stderr, "inflate.c too far\n"));
1140 copy -= state->whave;
1141 if (copy > state->length) copy = state->length;
1142 if (copy > left) copy = left;
1144 state->length -= copy;
1148 if (state->length == 0) state->mode = LEN;
1152 if (copy > state->wnext) {
1153 copy -= state->wnext;
1154 from = state->window + (state->wsize - copy);
1157 from = state->window + (state->wnext - copy);
1158 if (copy > state->length) copy = state->length;
1160 else { /* copy from output */
1161 from = put - state->offset;
1162 copy = state->length;
1164 if (copy > left) copy = left;
1166 state->length -= copy;
1170 if (state->length == 0) state->mode = LEN;
1173 if (left == 0) goto inf_leave;
1174 *put++ = (unsigned char)(state->length);
1182 strm->total_out += out;
1183 state->total += out;
1185 strm->adler = state->check =
1186 UPDATE(state->check, put - out, out);
1190 state->flags ? hold :
1192 ZSWAP32(hold)) != state->check) {
1193 strm->msg = (char *)"incorrect data check";
1198 Tracev((stderr, "inflate: check matches trailer\n"));
1201 state->mode = LENGTH;
1203 if (state->wrap && state->flags) {
1205 if (hold != (state->total & 0xffffffffUL)) {
1206 strm->msg = (char *)"incorrect length check";
1211 Tracev((stderr, "inflate: length matches trailer\n"));
1225 return Z_STREAM_ERROR;
1229 Return from inflate(), updating the total counts and the check value.
1230 If there was no progress during the inflate() call, return a buffer
1231 error. Call updatewindow() to create and/or update the window state.
1232 Note: a memory error from inflate() is non-recoverable.
1236 if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1237 (state->mode < CHECK || flush != Z_FINISH)))
1238 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1242 in -= strm->avail_in;
1243 out -= strm->avail_out;
1244 strm->total_in += in;
1245 strm->total_out += out;
1246 state->total += out;
1247 if (state->wrap && out)
1248 strm->adler = state->check =
1249 UPDATE(state->check, strm->next_out - out, out);
1250 strm->data_type = state->bits + (state->last ? 64 : 0) +
1251 (state->mode == TYPE ? 128 : 0) +
1252 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1253 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1258 int ZEXPORT inflateEnd(strm)
1261 struct inflate_state FAR *state;
1262 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1263 return Z_STREAM_ERROR;
1264 state = (struct inflate_state FAR *)strm->state;
1265 if (state->window != Z_NULL) ZFREE(strm, state->window);
1266 ZFREE(strm, strm->state);
1267 strm->state = Z_NULL;
1268 Tracev((stderr, "inflate: end\n"));
1272 int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1277 struct inflate_state FAR *state;
1280 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1281 state = (struct inflate_state FAR *)strm->state;
1283 /* copy dictionary */
1284 if (state->whave && dictionary != Z_NULL) {
1285 zmemcpy(dictionary, state->window + state->wnext,
1286 state->whave - state->wnext);
1287 zmemcpy(dictionary + state->whave - state->wnext,
1288 state->window, state->wnext);
1290 if (dictLength != Z_NULL)
1291 *dictLength = state->whave;
1295 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1297 const Bytef *dictionary;
1300 struct inflate_state FAR *state;
1301 unsigned long dictid;
1305 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1306 state = (struct inflate_state FAR *)strm->state;
1307 if (state->wrap != 0 && state->mode != DICT)
1308 return Z_STREAM_ERROR;
1310 /* check for correct dictionary identifier */
1311 if (state->mode == DICT) {
1312 dictid = adler32(0L, Z_NULL, 0);
1313 dictid = adler32(dictid, dictionary, dictLength);
1314 if (dictid != state->check)
1315 return Z_DATA_ERROR;
1318 /* copy dictionary to window using updatewindow(), which will amend the
1319 existing dictionary if appropriate */
1320 ret = updatewindow(strm, dictionary + dictLength, dictLength);
1325 state->havedict = 1;
1326 Tracev((stderr, "inflate: dictionary set\n"));
1330 int ZEXPORT inflateGetHeader(strm, head)
1334 struct inflate_state FAR *state;
1337 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1338 state = (struct inflate_state FAR *)strm->state;
1339 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1341 /* save header structure */
1348 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1349 or when out of input. When called, *have is the number of pattern bytes
1350 found in order so far, in 0..3. On return *have is updated to the new
1351 state. If on return *have equals four, then the pattern was found and the
1352 return value is how many bytes were read including the last byte of the
1353 pattern. If *have is less than four, then the pattern has not been found
1354 yet and the return value is len. In the latter case, syncsearch() can be
1355 called again with more data and the *have state. *have is initialized to
1356 zero for the first call.
1358 local unsigned syncsearch(have, buf, len)
1360 const unsigned char FAR *buf;
1368 while (next < len && got < 4) {
1369 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1381 int ZEXPORT inflateSync(strm)
1384 unsigned len; /* number of bytes to look at or looked at */
1385 unsigned long in, out; /* temporary to save total_in and total_out */
1386 unsigned char buf[4]; /* to restore bit buffer to byte string */
1387 struct inflate_state FAR *state;
1389 /* check parameters */
1390 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1391 state = (struct inflate_state FAR *)strm->state;
1392 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1394 /* if first time, start search in bit buffer */
1395 if (state->mode != SYNC) {
1397 state->hold <<= state->bits & 7;
1398 state->bits -= state->bits & 7;
1400 while (state->bits >= 8) {
1401 buf[len++] = (unsigned char)(state->hold);
1406 syncsearch(&(state->have), buf, len);
1409 /* search available input */
1410 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1411 strm->avail_in -= len;
1412 strm->next_in += len;
1413 strm->total_in += len;
1415 /* return no joy or set up to restart inflate() on a new block */
1416 if (state->have != 4) return Z_DATA_ERROR;
1417 in = strm->total_in; out = strm->total_out;
1419 strm->total_in = in; strm->total_out = out;
1425 Returns true if inflate is currently at the end of a block generated by
1426 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1427 implementation to provide an additional safety check. PPP uses
1428 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1429 block. When decompressing, PPP checks that at the end of input packet,
1430 inflate is waiting for these length bytes.
1432 int ZEXPORT inflateSyncPoint(strm)
1435 struct inflate_state FAR *state;
1437 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1438 state = (struct inflate_state FAR *)strm->state;
1439 return state->mode == STORED && state->bits == 0;
1442 int ZEXPORT inflateCopy(dest, source)
1446 struct inflate_state FAR *state;
1447 struct inflate_state FAR *copy;
1448 unsigned char FAR *window;
1452 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1453 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1454 return Z_STREAM_ERROR;
1455 state = (struct inflate_state FAR *)source->state;
1457 /* allocate space */
1458 copy = (struct inflate_state FAR *)
1459 ZALLOC(source, 1, sizeof(struct inflate_state));
1460 if (copy == Z_NULL) return Z_MEM_ERROR;
1462 if (state->window != Z_NULL) {
1463 window = (unsigned char FAR *)
1464 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1465 if (window == Z_NULL) {
1466 ZFREE(source, copy);
1472 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1473 zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1474 if (state->lencode >= state->codes &&
1475 state->lencode <= state->codes + ENOUGH - 1) {
1476 copy->lencode = copy->codes + (state->lencode - state->codes);
1477 copy->distcode = copy->codes + (state->distcode - state->codes);
1479 copy->next = copy->codes + (state->next - state->codes);
1480 if (window != Z_NULL) {
1481 wsize = 1U << state->wbits;
1482 zmemcpy(window, state->window, wsize);
1484 copy->window = window;
1485 dest->state = (struct internal_state FAR *)copy;
1489 int ZEXPORT inflateUndermine(strm, subvert)
1493 struct inflate_state FAR *state;
1495 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1496 state = (struct inflate_state FAR *)strm->state;
1497 state->sane = !subvert;
1498 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1502 return Z_DATA_ERROR;
1506 long ZEXPORT inflateMark(strm)
1509 struct inflate_state FAR *state;
1511 if (strm == Z_NULL || strm->state == Z_NULL) return ~0xFFFFL; /* Original code returned -1L << 16, but that is undefined behaviour */
1512 state = (struct inflate_state FAR *)strm->state;
1513 return ((long)(state->back) << 16) +
1514 (state->mode == COPY ? state->length :
1515 (state->mode == MATCH ? state->was - state->length : 0));