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 /* function prototypes */
95 local void fixedtables OF((struct inflate_state FAR *state));
96 local int updatewindow OF((z_streamp strm, const unsigned char FAR *end,
99 void makefixed OF((void));
101 local unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf,
104 int ZEXPORT inflateResetKeep(strm)
107 struct inflate_state FAR *state;
109 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
110 state = (struct inflate_state FAR *)strm->state;
111 strm->total_in = strm->total_out = state->total = 0;
113 if (state->wrap) /* to support ill-conceived Java test suite */
114 strm->adler = state->wrap & 1;
118 state->dmax = 32768U;
119 state->head = Z_NULL;
122 state->lencode = state->distcode = state->next = state->codes;
125 Tracev((stderr, "inflate: reset\n"));
129 int ZEXPORT inflateReset(strm)
132 struct inflate_state FAR *state;
134 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
135 state = (struct inflate_state FAR *)strm->state;
139 return inflateResetKeep(strm);
142 int ZEXPORT inflateReset2(strm, windowBits)
147 struct inflate_state FAR *state;
150 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
151 state = (struct inflate_state FAR *)strm->state;
153 /* extract wrap request from windowBits parameter */
154 if (windowBits < 0) {
156 windowBits = -windowBits;
159 wrap = (windowBits >> 4) + 5;
166 /* set number of window bits, free window if different */
167 if (windowBits && (windowBits < 8 || windowBits > 15))
168 return Z_STREAM_ERROR;
169 if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
170 ZFREE(strm, state->window);
171 state->window = Z_NULL;
174 /* update state and reset the rest of it */
176 state->wbits = (unsigned)windowBits;
177 return inflateReset(strm);
180 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
187 struct inflate_state FAR *state;
189 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
190 stream_size != (int)(sizeof(z_stream)))
191 return Z_VERSION_ERROR;
192 if (strm == Z_NULL) return Z_STREAM_ERROR;
193 strm->msg = Z_NULL; /* in case we return an error */
194 if (strm->zalloc == (alloc_func)0) {
196 return Z_STREAM_ERROR;
198 strm->zalloc = zcalloc;
199 strm->opaque = (voidpf)0;
202 if (strm->zfree == (free_func)0)
204 return Z_STREAM_ERROR;
206 strm->zfree = zcfree;
208 state = (struct inflate_state FAR *)
209 ZALLOC(strm, 1, sizeof(struct inflate_state));
210 if (state == Z_NULL) return Z_MEM_ERROR;
211 Tracev((stderr, "inflate: allocated\n"));
212 strm->state = (struct internal_state FAR *)state;
213 state->window = Z_NULL;
214 ret = inflateReset2(strm, windowBits);
217 strm->state = Z_NULL;
222 int ZEXPORT inflateInit_(strm, version, stream_size)
227 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
230 int ZEXPORT inflatePrime(strm, bits, value)
235 struct inflate_state FAR *state;
237 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
238 state = (struct inflate_state FAR *)strm->state;
244 if (bits > 16 || state->bits + (uInt)bits > 32) return Z_STREAM_ERROR;
245 value &= (1L << bits) - 1;
246 state->hold += (unsigned)value << state->bits;
247 state->bits += (uInt)bits;
252 Return state with length and distance decoding tables and index sizes set to
253 fixed code decoding. Normally this returns fixed tables from inffixed.h.
254 If BUILDFIXED is defined, then instead this routine builds the tables the
255 first time it's called, and returns those tables the first time and
256 thereafter. This reduces the size of the code by about 2K bytes, in
257 exchange for a little execution time. However, BUILDFIXED should not be
258 used for threaded applications, since the rewriting of the tables and virgin
259 may not be thread-safe.
261 local void fixedtables(state)
262 struct inflate_state FAR *state;
265 static int virgin = 1;
266 static code *lenfix, *distfix;
267 static code fixed[544];
269 /* build fixed huffman tables if first call (may not be thread safe) */
274 /* literal/length table */
276 while (sym < 144) state->lens[sym++] = 8;
277 while (sym < 256) state->lens[sym++] = 9;
278 while (sym < 280) state->lens[sym++] = 7;
279 while (sym < 288) state->lens[sym++] = 8;
283 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
287 while (sym < 32) state->lens[sym++] = 5;
290 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
292 /* do this just once */
295 #else /* !BUILDFIXED */
296 # include "inffixed.h"
297 #endif /* BUILDFIXED */
298 state->lencode = lenfix;
300 state->distcode = distfix;
308 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
309 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
310 those tables to stdout, which would be piped to inffixed.h. A small program
311 can simply call makefixed to do this:
313 void makefixed(void);
321 Then that can be linked with zlib built with MAKEFIXED defined and run:
328 struct inflate_state state;
331 puts(" /* inffixed.h -- table for decoding fixed codes");
332 puts(" * Generated automatically by makefixed().");
335 puts(" /* WARNING: this file should *not* be used by applications.");
336 puts(" It is part of the implementation of this library and is");
337 puts(" subject to change. Applications should only use zlib.h.");
341 printf(" static const code lenfix[%u] = {", size);
344 if ((low % 7) == 0) printf("\n ");
345 printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
346 state.lencode[low].bits, state.lencode[low].val);
347 if (++low == size) break;
352 printf("\n static const code distfix[%u] = {", size);
355 if ((low % 6) == 0) printf("\n ");
356 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
357 state.distcode[low].val);
358 if (++low == size) break;
363 #endif /* MAKEFIXED */
366 Update the window with the last wsize (normally 32K) bytes written before
367 returning. If window does not exist yet, create it. This is only called
368 when a window is already in use, or when output has been written during this
369 inflate call, but the end of the deflate stream has not been reached yet.
370 It is also called to create a window for dictionary data when a dictionary
373 Providing output buffers larger than 32K to inflate() should provide a speed
374 advantage, since only the last 32K of output is copied to the sliding window
375 upon return from inflate(), and since all distances after the first 32K of
376 output will fall in the output data, making match copies simpler and faster.
377 The advantage may be dependent on the size of the processor's data caches.
379 local int updatewindow(strm, end, copy)
384 struct inflate_state FAR *state;
387 state = (struct inflate_state FAR *)strm->state;
389 /* if it hasn't been done already, allocate space for the window */
390 if (state->window == Z_NULL) {
391 state->window = (unsigned char FAR *)
392 ZALLOC(strm, 1U << state->wbits,
393 sizeof(unsigned char));
394 if (state->window == Z_NULL) return 1;
397 /* if window not in use yet, initialize */
398 if (state->wsize == 0) {
399 state->wsize = 1U << state->wbits;
404 /* copy state->wsize or less output bytes into the circular window */
405 if (copy >= state->wsize) {
406 zmemcpy(state->window, end - state->wsize, state->wsize);
408 state->whave = state->wsize;
411 dist = state->wsize - state->wnext;
412 if (dist > copy) dist = copy;
413 zmemcpy(state->window + state->wnext, end - copy, dist);
416 zmemcpy(state->window, end - copy, copy);
418 state->whave = state->wsize;
421 state->wnext += dist;
422 if (state->wnext == state->wsize) state->wnext = 0;
423 if (state->whave < state->wsize) state->whave += dist;
429 /* Macros for inflate(): */
431 /* check function to use adler32() for zlib or crc32() for gzip */
433 # define UPDATE(check, buf, len) \
434 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
436 # define UPDATE(check, buf, len) adler32(check, buf, len)
439 /* check macros for header crc */
441 # define CRC2(check, word) \
443 hbuf[0] = (unsigned char)(word); \
444 hbuf[1] = (unsigned char)((word) >> 8); \
445 check = crc32(check, hbuf, 2); \
448 # define CRC4(check, word) \
450 hbuf[0] = (unsigned char)(word); \
451 hbuf[1] = (unsigned char)((word) >> 8); \
452 hbuf[2] = (unsigned char)((word) >> 16); \
453 hbuf[3] = (unsigned char)((word) >> 24); \
454 check = crc32(check, hbuf, 4); \
458 /* Load registers with state in inflate() for speed */
461 put = strm->next_out; \
462 left = strm->avail_out; \
463 next = strm->next_in; \
464 have = strm->avail_in; \
465 hold = state->hold; \
466 bits = state->bits; \
469 /* Restore state from registers in inflate() */
472 strm->next_out = put; \
473 strm->avail_out = left; \
474 strm->next_in = next; \
475 strm->avail_in = have; \
476 state->hold = hold; \
477 state->bits = bits; \
480 /* Clear the input bit accumulator */
487 /* Get a byte of input into the bit accumulator, or return from inflate()
488 if there is no input available. */
491 if (have == 0) goto inf_leave; \
493 hold += (unsigned long)(*next++) << bits; \
497 /* Assure that there are at least n bits in the bit accumulator. If there is
498 not enough available input to do that, then return from inflate(). */
499 #define NEEDBITS(n) \
501 while (bits < (unsigned)(n)) \
505 /* Return the low n bits of the bit accumulator (n < 16) */
507 ((unsigned)hold & ((1U << (n)) - 1))
509 /* Remove n bits from the bit accumulator */
510 #define DROPBITS(n) \
513 bits -= (unsigned)(n); \
516 /* Remove zero to seven bits as needed to go to a byte boundary */
524 inflate() uses a state machine to process as much input data and generate as
525 much output data as possible before returning. The state machine is
526 structured roughly as follows:
528 for (;;) switch (state) {
531 if (not enough input data or output space to make progress)
533 ... make progress ...
539 so when inflate() is called again, the same case is attempted again, and
540 if the appropriate resources are provided, the machine proceeds to the
541 next state. The NEEDBITS() macro is usually the way the state evaluates
542 whether it can proceed or should return. NEEDBITS() does the return if
543 the requested bits are not available. The typical use of the BITS macros
547 ... do something with BITS(n) ...
550 where NEEDBITS(n) either returns from inflate() if there isn't enough
551 input left to load n bits into the accumulator, or it continues. BITS(n)
552 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
553 the low n bits off the accumulator. INITBITS() clears the accumulator
554 and sets the number of available bits to zero. BYTEBITS() discards just
555 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
556 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
558 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
559 if there is no input available. The decoding of variable length codes uses
560 PULLBYTE() directly in order to pull just enough bytes to decode the next
563 Some states loop until they get enough input, making sure that enough
564 state information is maintained to continue the loop where it left off
565 if NEEDBITS() returns in the loop. For example, want, need, and keep
566 would all have to actually be part of the saved state in case NEEDBITS()
570 while (want < need) {
572 keep[want++] = BITS(n);
578 As shown above, if the next state is also the next case, then the break
581 A state may also return if there is not enough output space available to
582 complete that state. Those states are copying stored data, writing a
583 literal byte, and copying a matching string.
585 When returning, a "goto inf_leave" is used to update the total counters,
586 update the check value, and determine whether any progress has been made
587 during that inflate() call in order to return the proper return code.
588 Progress is defined as a change in either strm->avail_in or strm->avail_out.
589 When there is a window, goto inf_leave will update the window with the last
590 output written. If a goto inf_leave occurs in the middle of decompression
591 and there is no window currently, goto inf_leave will create one and copy
592 output to the window for the next call of inflate().
594 In this implementation, the flush parameter of inflate() only affects the
595 return code (per zlib.h). inflate() always writes as much as possible to
596 strm->next_out, given the space available and the provided input--the effect
597 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
598 the allocation of and copying into a sliding window until necessary, which
599 provides the effect documented in zlib.h for Z_FINISH when the entire input
600 stream available. So the only thing the flush parameter actually does is:
601 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
602 will return Z_BUF_ERROR if it has not reached the end of the stream.
605 int ZEXPORT inflate(strm, flush)
609 struct inflate_state FAR *state;
610 z_const unsigned char FAR *next; /* next input */
611 unsigned char FAR *put; /* next output */
612 unsigned have, left; /* available input and output */
613 unsigned long hold; /* bit buffer */
614 unsigned bits; /* bits in bit buffer */
615 unsigned in, out; /* save starting available input and output */
616 unsigned copy; /* number of stored or match bytes to copy */
617 unsigned char FAR *from; /* where to copy match bytes from */
618 code here; /* current decoding table entry */
619 code last; /* parent table entry */
620 unsigned len; /* length to copy for repeats, bits to drop */
621 int ret; /* return code */
623 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
625 static const unsigned short order[19] = /* permutation of code lengths */
626 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
628 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
629 (strm->next_in == Z_NULL && strm->avail_in != 0))
630 return Z_STREAM_ERROR;
632 state = (struct inflate_state FAR *)strm->state;
633 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
639 switch (state->mode) {
641 if (state->wrap == 0) {
642 state->mode = TYPEDO;
647 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
648 if (state->wbits == 0)
650 state->check = crc32(0L, Z_NULL, 0);
651 CRC2(state->check, hold);
656 state->flags = 0; /* expect zlib header */
657 if (state->head != Z_NULL)
658 state->head->done = -1;
659 if (!(state->wrap & 1) || /* check if zlib header allowed */
663 ((BITS(8) << 8) + (hold >> 8)) % 31) {
664 strm->msg = (char *)"incorrect header check";
668 if (BITS(4) != Z_DEFLATED) {
669 strm->msg = (char *)"unknown compression method";
675 if (state->wbits == 0)
677 if (len > 15 || len > state->wbits) {
678 strm->msg = (char *)"invalid window size";
682 state->dmax = 1U << len;
683 Tracev((stderr, "inflate: zlib header ok\n"));
684 strm->adler = state->check = adler32(0L, Z_NULL, 0);
685 state->mode = hold & 0x200 ? DICTID : TYPE;
691 state->flags = (int)(hold);
692 if ((state->flags & 0xff) != Z_DEFLATED) {
693 strm->msg = (char *)"unknown compression method";
697 if (state->flags & 0xe000) {
698 strm->msg = (char *)"unknown header flags set";
702 if (state->head != Z_NULL)
703 state->head->text = (int)((hold >> 8) & 1);
704 if ((state->flags & 0x0200) && (state->wrap & 4))
705 CRC2(state->check, hold);
710 if (state->head != Z_NULL)
711 state->head->time = hold;
712 if ((state->flags & 0x0200) && (state->wrap & 4))
713 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) && (state->wrap & 4))
723 CRC2(state->check, hold);
727 if (state->flags & 0x0400) {
729 state->length = (unsigned)(hold);
730 if (state->head != Z_NULL)
731 state->head->extra_len = (unsigned)hold;
732 if ((state->flags & 0x0200) && (state->wrap & 4))
733 CRC2(state->check, hold);
736 else if (state->head != Z_NULL)
737 state->head->extra = Z_NULL;
740 if (state->flags & 0x0400) {
741 copy = state->length;
742 if (copy > have) copy = have;
744 if (state->head != Z_NULL &&
745 state->head->extra != Z_NULL) {
746 len = state->head->extra_len - state->length;
747 zmemcpy(state->head->extra + len, next,
748 len + copy > state->head->extra_max ?
749 state->head->extra_max - len : copy);
751 if ((state->flags & 0x0200) && (state->wrap & 4))
752 state->check = crc32(state->check, next, copy);
755 state->length -= copy;
757 if (state->length) goto inf_leave;
762 if (state->flags & 0x0800) {
763 if (have == 0) goto inf_leave;
766 len = (unsigned)(next[copy++]);
767 if (state->head != Z_NULL &&
768 state->head->name != Z_NULL &&
769 state->length < state->head->name_max)
770 state->head->name[state->length++] = (Bytef)len;
771 } while (len && copy < have);
772 if ((state->flags & 0x0200) && (state->wrap & 4))
773 state->check = crc32(state->check, next, copy);
776 if (len) goto inf_leave;
778 else if (state->head != Z_NULL)
779 state->head->name = Z_NULL;
781 state->mode = COMMENT;
783 if (state->flags & 0x1000) {
784 if (have == 0) goto inf_leave;
787 len = (unsigned)(next[copy++]);
788 if (state->head != Z_NULL &&
789 state->head->comment != Z_NULL &&
790 state->length < state->head->comm_max)
791 state->head->comment[state->length++] = (Bytef)len;
792 } while (len && copy < have);
793 if ((state->flags & 0x0200) && (state->wrap & 4))
794 state->check = crc32(state->check, next, copy);
797 if (len) goto inf_leave;
799 else if (state->head != Z_NULL)
800 state->head->comment = Z_NULL;
803 if (state->flags & 0x0200) {
805 if ((state->wrap & 4) && hold != (state->check & 0xffff)) {
806 strm->msg = (char *)"header crc mismatch";
812 if (state->head != Z_NULL) {
813 state->head->hcrc = (int)((state->flags >> 9) & 1);
814 state->head->done = 1;
816 strm->adler = state->check = crc32(0L, Z_NULL, 0);
822 strm->adler = state->check = ZSWAP32(hold);
826 if (state->havedict == 0) {
830 strm->adler = state->check = adler32(0L, Z_NULL, 0);
833 if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
841 state->last = BITS(1);
844 case 0: /* stored block */
845 Tracev((stderr, "inflate: stored block%s\n",
846 state->last ? " (last)" : ""));
847 state->mode = STORED;
849 case 1: /* fixed block */
851 Tracev((stderr, "inflate: fixed codes block%s\n",
852 state->last ? " (last)" : ""));
853 state->mode = LEN_; /* decode codes */
854 if (flush == Z_TREES) {
859 case 2: /* dynamic block */
860 Tracev((stderr, "inflate: dynamic codes block%s\n",
861 state->last ? " (last)" : ""));
865 strm->msg = (char *)"invalid block type";
871 BYTEBITS(); /* go to byte boundary */
873 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
874 strm->msg = (char *)"invalid stored block lengths";
878 state->length = (unsigned)hold & 0xffff;
879 Tracev((stderr, "inflate: stored length %u\n",
883 if (flush == Z_TREES) goto inf_leave;
887 copy = state->length;
889 if (copy > have) copy = have;
890 if (copy > left) copy = left;
891 if (copy == 0) goto inf_leave;
892 zmemcpy(put, next, copy);
897 state->length -= copy;
900 Tracev((stderr, "inflate: stored end\n"));
905 state->nlen = BITS(5) + 257;
907 state->ndist = BITS(5) + 1;
909 state->ncode = BITS(4) + 4;
911 #ifndef PKZIP_BUG_WORKAROUND
912 if (state->nlen > 286 || state->ndist > 30) {
913 strm->msg = (char *)"too many length or distance symbols";
918 Tracev((stderr, "inflate: table sizes ok\n"));
920 state->mode = LENLENS;
922 while (state->have < state->ncode) {
924 state->lens[order[state->have++]] = (unsigned short)BITS(3);
927 while (state->have < 19)
928 state->lens[order[state->have++]] = 0;
929 state->next = state->codes;
930 state->lencode = (const code FAR *)(state->next);
932 ret = inflate_table(CODES, state->lens, 19, &(state->next),
933 &(state->lenbits), state->work);
935 strm->msg = (char *)"invalid code lengths set";
939 Tracev((stderr, "inflate: code lengths ok\n"));
941 state->mode = CODELENS;
943 while (state->have < state->nlen + state->ndist) {
945 here = state->lencode[BITS(state->lenbits)];
946 if ((unsigned)(here.bits) <= bits) break;
951 state->lens[state->have++] = here.val;
954 if (here.val == 16) {
955 NEEDBITS(here.bits + 2);
957 if (state->have == 0) {
958 strm->msg = (char *)"invalid bit length repeat";
962 len = state->lens[state->have - 1];
966 else if (here.val == 17) {
967 NEEDBITS(here.bits + 3);
974 NEEDBITS(here.bits + 7);
980 if (state->have + copy > state->nlen + state->ndist) {
981 strm->msg = (char *)"invalid bit length repeat";
986 state->lens[state->have++] = (unsigned short)len;
990 /* handle error breaks in while */
991 if (state->mode == BAD) break;
993 /* check for end-of-block code (better have one) */
994 if (state->lens[256] == 0) {
995 strm->msg = (char *)"invalid code -- missing end-of-block";
1000 /* build code tables -- note: do not change the lenbits or distbits
1001 values here (9 and 6) without reading the comments in inftrees.h
1002 concerning the ENOUGH constants, which depend on those values */
1003 state->next = state->codes;
1004 state->lencode = (const code FAR *)(state->next);
1006 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1007 &(state->lenbits), state->work);
1009 strm->msg = (char *)"invalid literal/lengths set";
1013 state->distcode = (const code FAR *)(state->next);
1014 state->distbits = 6;
1015 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1016 &(state->next), &(state->distbits), state->work);
1018 strm->msg = (char *)"invalid distances set";
1022 Tracev((stderr, "inflate: codes ok\n"));
1024 if (flush == Z_TREES) goto inf_leave;
1028 if (have >= 6 && left >= 258) {
1030 inflate_fast(strm, out);
1032 if (state->mode == TYPE)
1038 here = state->lencode[BITS(state->lenbits)];
1039 if ((unsigned)(here.bits) <= bits) break;
1042 if (here.op && (here.op & 0xf0) == 0) {
1045 here = state->lencode[last.val +
1046 (BITS(last.bits + last.op) >> last.bits)];
1047 if ((unsigned)(last.bits + here.bits) <= bits) break;
1050 DROPBITS(last.bits);
1051 state->back += last.bits;
1053 DROPBITS(here.bits);
1054 state->back += here.bits;
1055 state->length = (unsigned)here.val;
1056 if ((int)(here.op) == 0) {
1057 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1058 "inflate: literal '%c'\n" :
1059 "inflate: literal 0x%02x\n", here.val));
1064 Tracevv((stderr, "inflate: end of block\n"));
1070 strm->msg = (char *)"invalid literal/length code";
1074 state->extra = (unsigned)(here.op) & 15;
1075 state->mode = LENEXT;
1078 NEEDBITS(state->extra);
1079 state->length += BITS(state->extra);
1080 DROPBITS(state->extra);
1081 state->back += state->extra;
1083 Tracevv((stderr, "inflate: length %u\n", state->length));
1084 state->was = state->length;
1088 here = state->distcode[BITS(state->distbits)];
1089 if ((unsigned)(here.bits) <= bits) break;
1092 if ((here.op & 0xf0) == 0) {
1095 here = state->distcode[last.val +
1096 (BITS(last.bits + last.op) >> last.bits)];
1097 if ((unsigned)(last.bits + here.bits) <= bits) break;
1100 DROPBITS(last.bits);
1101 state->back += last.bits;
1103 DROPBITS(here.bits);
1104 state->back += here.bits;
1106 strm->msg = (char *)"invalid distance code";
1110 state->offset = (unsigned)here.val;
1111 state->extra = (unsigned)(here.op) & 15;
1112 state->mode = DISTEXT;
1115 NEEDBITS(state->extra);
1116 state->offset += BITS(state->extra);
1117 DROPBITS(state->extra);
1118 state->back += state->extra;
1120 #ifdef INFLATE_STRICT
1121 if (state->offset > state->dmax) {
1122 strm->msg = (char *)"invalid distance too far back";
1127 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1128 state->mode = MATCH;
1130 if (left == 0) goto inf_leave;
1132 if (state->offset > copy) { /* copy from window */
1133 copy = state->offset - copy;
1134 if (copy > state->whave) {
1136 strm->msg = (char *)"invalid distance too far back";
1140 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1141 Trace((stderr, "inflate.c too far\n"));
1142 copy -= state->whave;
1143 if (copy > state->length) copy = state->length;
1144 if (copy > left) copy = left;
1146 state->length -= copy;
1150 if (state->length == 0) state->mode = LEN;
1154 if (copy > state->wnext) {
1155 copy -= state->wnext;
1156 from = state->window + (state->wsize - copy);
1159 from = state->window + (state->wnext - copy);
1160 if (copy > state->length) copy = state->length;
1162 else { /* copy from output */
1163 from = put - state->offset;
1164 copy = state->length;
1166 if (copy > left) copy = left;
1168 state->length -= copy;
1172 if (state->length == 0) state->mode = LEN;
1175 if (left == 0) goto inf_leave;
1176 *put++ = (unsigned char)(state->length);
1184 strm->total_out += out;
1185 state->total += out;
1186 if ((state->wrap & 4) && out)
1187 strm->adler = state->check =
1188 UPDATE(state->check, put - out, out);
1190 if ((state->wrap & 4) && (
1192 state->flags ? hold :
1194 ZSWAP32(hold)) != state->check) {
1195 strm->msg = (char *)"incorrect data check";
1200 Tracev((stderr, "inflate: check matches trailer\n"));
1203 state->mode = LENGTH;
1205 if (state->wrap && state->flags) {
1207 if (hold != (state->total & 0xffffffffUL)) {
1208 strm->msg = (char *)"incorrect length check";
1213 Tracev((stderr, "inflate: length matches trailer\n"));
1227 return Z_STREAM_ERROR;
1231 Return from inflate(), updating the total counts and the check value.
1232 If there was no progress during the inflate() call, return a buffer
1233 error. Call updatewindow() to create and/or update the window state.
1234 Note: a memory error from inflate() is non-recoverable.
1238 if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
1239 (state->mode < CHECK || flush != Z_FINISH)))
1240 if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1244 in -= strm->avail_in;
1245 out -= strm->avail_out;
1246 strm->total_in += in;
1247 strm->total_out += out;
1248 state->total += out;
1249 if ((state->wrap & 4) && out)
1250 strm->adler = state->check =
1251 UPDATE(state->check, strm->next_out - out, out);
1252 strm->data_type = (int)state->bits + (state->last ? 64 : 0) +
1253 (state->mode == TYPE ? 128 : 0) +
1254 (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
1255 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1260 int ZEXPORT inflateEnd(strm)
1263 struct inflate_state FAR *state;
1264 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1265 return Z_STREAM_ERROR;
1266 state = (struct inflate_state FAR *)strm->state;
1267 if (state->window != Z_NULL) ZFREE(strm, state->window);
1268 ZFREE(strm, strm->state);
1269 strm->state = Z_NULL;
1270 Tracev((stderr, "inflate: end\n"));
1274 int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1279 struct inflate_state FAR *state;
1282 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1283 state = (struct inflate_state FAR *)strm->state;
1285 /* copy dictionary */
1286 if (state->whave && dictionary != Z_NULL) {
1287 zmemcpy(dictionary, state->window + state->wnext,
1288 state->whave - state->wnext);
1289 zmemcpy(dictionary + state->whave - state->wnext,
1290 state->window, state->wnext);
1292 if (dictLength != Z_NULL)
1293 *dictLength = state->whave;
1297 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1299 const Bytef *dictionary;
1302 struct inflate_state FAR *state;
1303 unsigned long dictid;
1307 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1308 state = (struct inflate_state FAR *)strm->state;
1309 if (state->wrap != 0 && state->mode != DICT)
1310 return Z_STREAM_ERROR;
1312 /* check for correct dictionary identifier */
1313 if (state->mode == DICT) {
1314 dictid = adler32(0L, Z_NULL, 0);
1315 dictid = adler32(dictid, dictionary, dictLength);
1316 if (dictid != state->check)
1317 return Z_DATA_ERROR;
1320 /* copy dictionary to window using updatewindow(), which will amend the
1321 existing dictionary if appropriate */
1322 ret = updatewindow(strm, dictionary + dictLength, dictLength);
1327 state->havedict = 1;
1328 Tracev((stderr, "inflate: dictionary set\n"));
1332 int ZEXPORT inflateGetHeader(strm, head)
1336 struct inflate_state FAR *state;
1339 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1340 state = (struct inflate_state FAR *)strm->state;
1341 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1343 /* save header structure */
1350 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1351 or when out of input. When called, *have is the number of pattern bytes
1352 found in order so far, in 0..3. On return *have is updated to the new
1353 state. If on return *have equals four, then the pattern was found and the
1354 return value is how many bytes were read including the last byte of the
1355 pattern. If *have is less than four, then the pattern has not been found
1356 yet and the return value is len. In the latter case, syncsearch() can be
1357 called again with more data and the *have state. *have is initialized to
1358 zero for the first call.
1360 local unsigned syncsearch(have, buf, len)
1362 const unsigned char FAR *buf;
1370 while (next < len && got < 4) {
1371 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1383 int ZEXPORT inflateSync(strm)
1386 unsigned len; /* number of bytes to look at or looked at */
1387 unsigned long in, out; /* temporary to save total_in and total_out */
1388 unsigned char buf[4]; /* to restore bit buffer to byte string */
1389 struct inflate_state FAR *state;
1391 /* check parameters */
1392 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1393 state = (struct inflate_state FAR *)strm->state;
1394 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1396 /* if first time, start search in bit buffer */
1397 if (state->mode != SYNC) {
1399 state->hold <<= state->bits & 7;
1400 state->bits -= state->bits & 7;
1402 while (state->bits >= 8) {
1403 buf[len++] = (unsigned char)(state->hold);
1408 syncsearch(&(state->have), buf, len);
1411 /* search available input */
1412 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1413 strm->avail_in -= len;
1414 strm->next_in += len;
1415 strm->total_in += len;
1417 /* return no joy or set up to restart inflate() on a new block */
1418 if (state->have != 4) return Z_DATA_ERROR;
1419 in = strm->total_in; out = strm->total_out;
1421 strm->total_in = in; strm->total_out = out;
1427 Returns true if inflate is currently at the end of a block generated by
1428 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1429 implementation to provide an additional safety check. PPP uses
1430 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1431 block. When decompressing, PPP checks that at the end of input packet,
1432 inflate is waiting for these length bytes.
1434 int ZEXPORT inflateSyncPoint(strm)
1437 struct inflate_state FAR *state;
1439 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1440 state = (struct inflate_state FAR *)strm->state;
1441 return state->mode == STORED && state->bits == 0;
1444 int ZEXPORT inflateCopy(dest, source)
1448 struct inflate_state FAR *state;
1449 struct inflate_state FAR *copy;
1450 unsigned char FAR *window;
1454 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1455 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1456 return Z_STREAM_ERROR;
1457 state = (struct inflate_state FAR *)source->state;
1459 /* allocate space */
1460 copy = (struct inflate_state FAR *)
1461 ZALLOC(source, 1, sizeof(struct inflate_state));
1462 if (copy == Z_NULL) return Z_MEM_ERROR;
1464 if (state->window != Z_NULL) {
1465 window = (unsigned char FAR *)
1466 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1467 if (window == Z_NULL) {
1468 ZFREE(source, copy);
1474 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1475 zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1476 if (state->lencode >= state->codes &&
1477 state->lencode <= state->codes + ENOUGH - 1) {
1478 copy->lencode = copy->codes + (state->lencode - state->codes);
1479 copy->distcode = copy->codes + (state->distcode - state->codes);
1481 copy->next = copy->codes + (state->next - state->codes);
1482 if (window != Z_NULL) {
1483 wsize = 1U << state->wbits;
1484 zmemcpy(window, state->window, wsize);
1486 copy->window = window;
1487 dest->state = (struct internal_state FAR *)copy;
1491 int ZEXPORT inflateUndermine(strm, subvert)
1495 struct inflate_state FAR *state;
1497 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1498 state = (struct inflate_state FAR *)strm->state;
1499 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1500 state->sane = !subvert;
1505 return Z_DATA_ERROR;
1509 int ZEXPORT inflateValidate(strm, check)
1513 struct inflate_state FAR *state;
1515 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1516 state = (struct inflate_state FAR *)strm->state;
1524 long ZEXPORT inflateMark(strm)
1527 struct inflate_state FAR *state;
1529 if (strm == Z_NULL || strm->state == Z_NULL)
1531 state = (struct inflate_state FAR *)strm->state;
1532 return (long)(((unsigned long)((long)state->back)) << 16) +
1533 (state->mode == COPY ? state->length :
1534 (state->mode == MATCH ? state->was - state->length : 0));
1537 unsigned long ZEXPORT inflateCodesUsed(strm)
1540 struct inflate_state FAR *state;
1541 if (strm == Z_NULL || strm->state == Z_NULL) return (unsigned long)0 - 1;
1542 state = (struct inflate_state FAR *)strm->state;
1543 return (unsigned long)(state->next - state->codes);