1 /* inflate.c -- zlib decompression
2 * Copyright (C) 1995-2005 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 write == 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 inflateReset2(strm, flags)
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 strm->adler = 1; /* to support ill-conceived Java test suite */
117 state->dmax = 32768U;
118 state->head = Z_NULL;
119 if (!(flags & Z_RESET_KEEP_WINDOW)) {
126 state->lencode = state->distcode = state->next = state->codes;
127 Tracev((stderr, "inflate: reset\n"));
131 int ZEXPORT inflateReset(strm)
134 return inflateReset2(strm, 0);
137 int ZEXPORT inflatePrime(strm, bits, value)
142 struct inflate_state FAR *state;
144 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
145 state = (struct inflate_state FAR *)strm->state;
146 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
147 value &= (1L << bits) - 1;
148 state->hold += value << state->bits;
153 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
159 struct inflate_state FAR *state;
161 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
162 stream_size != (int)(sizeof(z_stream)))
163 return Z_VERSION_ERROR;
164 if (strm == Z_NULL) return Z_STREAM_ERROR;
165 strm->msg = Z_NULL; /* in case we return an error */
166 if (strm->zalloc == (alloc_func)0) {
167 strm->zalloc = zcalloc;
168 strm->opaque = (voidpf)0;
170 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
171 state = (struct inflate_state FAR *)
172 ZALLOC(strm, 1, sizeof(struct inflate_state));
173 if (state == Z_NULL) return Z_MEM_ERROR;
174 Tracev((stderr, "inflate: allocated\n"));
175 strm->state = (struct internal_state FAR *)state;
176 if (windowBits < 0) {
178 windowBits = -windowBits;
181 state->wrap = (windowBits >> 4) + 1;
183 if (windowBits < 48) windowBits &= 15;
186 if (windowBits < 8 || windowBits > 15) {
188 strm->state = Z_NULL;
189 return Z_STREAM_ERROR;
191 state->wbits = (unsigned)windowBits;
192 state->window = Z_NULL;
193 return inflateReset(strm);
196 int ZEXPORT inflateInit_(strm, version, stream_size)
201 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
205 Return state with length and distance decoding tables and index sizes set to
206 fixed code decoding. Normally this returns fixed tables from inffixed.h.
207 If BUILDFIXED is defined, then instead this routine builds the tables the
208 first time it's called, and returns those tables the first time and
209 thereafter. This reduces the size of the code by about 2K bytes, in
210 exchange for a little execution time. However, BUILDFIXED should not be
211 used for threaded applications, since the rewriting of the tables and virgin
212 may not be thread-safe.
214 local void fixedtables(state)
215 struct inflate_state FAR *state;
218 static int virgin = 1;
219 static code *lenfix, *distfix;
220 static code fixed[544];
222 /* build fixed huffman tables if first call (may not be thread safe) */
227 /* literal/length table */
229 while (sym < 144) state->lens[sym++] = 8;
230 while (sym < 256) state->lens[sym++] = 9;
231 while (sym < 280) state->lens[sym++] = 7;
232 while (sym < 288) state->lens[sym++] = 8;
236 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
240 while (sym < 32) state->lens[sym++] = 5;
243 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
245 /* do this just once */
248 #else /* !BUILDFIXED */
249 # include "inffixed.h"
250 #endif /* BUILDFIXED */
251 state->lencode = lenfix;
253 state->distcode = distfix;
261 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
262 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
263 those tables to stdout, which would be piped to inffixed.h. A small program
264 can simply call makefixed to do this:
266 void makefixed(void);
274 Then that can be linked with zlib built with MAKEFIXED defined and run:
281 struct inflate_state state;
284 puts(" /* inffixed.h -- table for decoding fixed codes");
285 puts(" * Generated automatically by makefixed().");
288 puts(" /* WARNING: this file should *not* be used by applications.");
289 puts(" It is part of the implementation of this library and is");
290 puts(" subject to change. Applications should only use zlib.h.");
294 printf(" static const code lenfix[%u] = {", size);
297 if ((low % 7) == 0) printf("\n ");
298 printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
299 state.lencode[low].val);
300 if (++low == size) break;
305 printf("\n static const code distfix[%u] = {", size);
308 if ((low % 6) == 0) printf("\n ");
309 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
310 state.distcode[low].val);
311 if (++low == size) break;
316 #endif /* MAKEFIXED */
319 Update the window with the last wsize (normally 32K) bytes written before
320 returning. If window does not exist yet, create it. This is only called
321 when a window is already in use, or when output has been written during this
322 inflate call, but the end of the deflate stream has not been reached yet.
323 It is also called to create a window for dictionary data when a dictionary
326 Providing output buffers larger than 32K to inflate() should provide a speed
327 advantage, since only the last 32K of output is copied to the sliding window
328 upon return from inflate(), and since all distances after the first 32K of
329 output will fall in the output data, making match copies simpler and faster.
330 The advantage may be dependent on the size of the processor's data caches.
332 local int updatewindow(strm, out)
336 struct inflate_state FAR *state;
339 state = (struct inflate_state FAR *)strm->state;
341 /* if it hasn't been done already, allocate space for the window */
342 if (state->window == Z_NULL) {
343 state->window = (unsigned char FAR *)
344 ZALLOC(strm, 1U << state->wbits,
345 sizeof(unsigned char));
346 if (state->window == Z_NULL) return 1;
349 /* if window not in use yet, initialize */
350 if (state->wsize == 0) {
351 state->wsize = 1U << state->wbits;
356 /* copy state->wsize or less output bytes into the circular window */
357 copy = out - strm->avail_out;
358 if (copy >= state->wsize) {
359 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
361 state->whave = state->wsize;
364 dist = state->wsize - state->write;
365 if (dist > copy) dist = copy;
366 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
369 zmemcpy(state->window, strm->next_out - copy, copy);
371 state->whave = state->wsize;
374 state->write += dist;
375 if (state->write == state->wsize) state->write = 0;
376 if (state->whave < state->wsize) state->whave += dist;
382 /* Macros for inflate(): */
384 /* check function to use adler32() for zlib or crc32() for gzip */
386 # define UPDATE(check, buf, len) \
387 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
389 # define UPDATE(check, buf, len) adler32(check, buf, len)
392 /* check macros for header crc */
394 # define CRC2(check, word) \
396 hbuf[0] = (unsigned char)(word); \
397 hbuf[1] = (unsigned char)((word) >> 8); \
398 check = crc32(check, hbuf, 2); \
401 # define CRC4(check, word) \
403 hbuf[0] = (unsigned char)(word); \
404 hbuf[1] = (unsigned char)((word) >> 8); \
405 hbuf[2] = (unsigned char)((word) >> 16); \
406 hbuf[3] = (unsigned char)((word) >> 24); \
407 check = crc32(check, hbuf, 4); \
411 /* Load registers with state in inflate() for speed */
414 put = strm->next_out; \
415 left = strm->avail_out; \
416 next = strm->next_in; \
417 have = strm->avail_in; \
418 hold = state->hold; \
419 bits = state->bits; \
422 /* Restore state from registers in inflate() */
425 strm->next_out = put; \
426 strm->avail_out = left; \
427 strm->next_in = next; \
428 strm->avail_in = have; \
429 state->hold = hold; \
430 state->bits = bits; \
433 /* Clear the input bit accumulator */
440 /* Get a byte of input into the bit accumulator, or return from inflate()
441 if there is no input available. */
444 if (have == 0) goto inf_leave; \
446 hold += (unsigned long)(*next++) << bits; \
450 /* Assure that there are at least n bits in the bit accumulator. If there is
451 not enough available input to do that, then return from inflate(). */
452 #define NEEDBITS(n) \
454 while (bits < (unsigned)(n)) \
458 /* Return the low n bits of the bit accumulator (n < 16) */
460 ((unsigned)hold & ((1U << (n)) - 1))
462 /* Remove n bits from the bit accumulator */
463 #define DROPBITS(n) \
466 bits -= (unsigned)(n); \
469 /* Remove zero to seven bits as needed to go to a byte boundary */
476 /* Reverse the bytes in a 32-bit value */
478 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
479 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
482 inflate() uses a state machine to process as much input data and generate as
483 much output data as possible before returning. The state machine is
484 structured roughly as follows:
486 for (;;) switch (state) {
489 if (not enough input data or output space to make progress)
491 ... make progress ...
497 so when inflate() is called again, the same case is attempted again, and
498 if the appropriate resources are provided, the machine proceeds to the
499 next state. The NEEDBITS() macro is usually the way the state evaluates
500 whether it can proceed or should return. NEEDBITS() does the return if
501 the requested bits are not available. The typical use of the BITS macros
505 ... do something with BITS(n) ...
508 where NEEDBITS(n) either returns from inflate() if there isn't enough
509 input left to load n bits into the accumulator, or it continues. BITS(n)
510 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
511 the low n bits off the accumulator. INITBITS() clears the accumulator
512 and sets the number of available bits to zero. BYTEBITS() discards just
513 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
514 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
516 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
517 if there is no input available. The decoding of variable length codes uses
518 PULLBYTE() directly in order to pull just enough bytes to decode the next
521 Some states loop until they get enough input, making sure that enough
522 state information is maintained to continue the loop where it left off
523 if NEEDBITS() returns in the loop. For example, want, need, and keep
524 would all have to actually be part of the saved state in case NEEDBITS()
528 while (want < need) {
530 keep[want++] = BITS(n);
536 As shown above, if the next state is also the next case, then the break
539 A state may also return if there is not enough output space available to
540 complete that state. Those states are copying stored data, writing a
541 literal byte, and copying a matching string.
543 When returning, a "goto inf_leave" is used to update the total counters,
544 update the check value, and determine whether any progress has been made
545 during that inflate() call in order to return the proper return code.
546 Progress is defined as a change in either strm->avail_in or strm->avail_out.
547 When there is a window, goto inf_leave will update the window with the last
548 output written. If a goto inf_leave occurs in the middle of decompression
549 and there is no window currently, goto inf_leave will create one and copy
550 output to the window for the next call of inflate().
552 In this implementation, the flush parameter of inflate() only affects the
553 return code (per zlib.h). inflate() always writes as much as possible to
554 strm->next_out, given the space available and the provided input--the effect
555 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
556 the allocation of and copying into a sliding window until necessary, which
557 provides the effect documented in zlib.h for Z_FINISH when the entire input
558 stream available. So the only thing the flush parameter actually does is:
559 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
560 will return Z_BUF_ERROR if it has not reached the end of the stream.
563 int ZEXPORT inflate(strm, flush)
567 struct inflate_state FAR *state;
568 unsigned char FAR *next; /* next input */
569 unsigned char FAR *put; /* next output */
570 unsigned have, left; /* available input and output */
571 unsigned long hold; /* bit buffer */
572 unsigned bits; /* bits in bit buffer */
573 unsigned in, out; /* save starting available input and output */
574 unsigned copy; /* number of stored or match bytes to copy */
575 unsigned char FAR *from; /* where to copy match bytes from */
576 code this; /* current decoding table entry */
577 code last; /* parent table entry */
578 unsigned len; /* length to copy for repeats, bits to drop */
579 int ret; /* return code */
581 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
583 static const unsigned short order[19] = /* permutation of code lengths */
584 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
586 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
587 (strm->next_in == Z_NULL && strm->avail_in != 0))
588 return Z_STREAM_ERROR;
590 state = (struct inflate_state FAR *)strm->state;
591 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
597 switch (state->mode) {
599 if (state->wrap == 0) {
600 state->mode = TYPEDO;
605 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
606 state->check = crc32(0L, Z_NULL, 0);
607 CRC2(state->check, hold);
612 state->flags = 0; /* expect zlib header */
613 if (state->head != Z_NULL)
614 state->head->done = -1;
615 if (!(state->wrap & 1) || /* check if zlib header allowed */
619 ((BITS(8) << 8) + (hold >> 8)) % 31) {
620 strm->msg = (char *)"incorrect header check";
624 if (BITS(4) != Z_DEFLATED) {
625 strm->msg = (char *)"unknown compression method";
631 if (len > state->wbits) {
632 strm->msg = (char *)"invalid window size";
636 state->dmax = 1U << len;
637 Tracev((stderr, "inflate: zlib header ok\n"));
638 strm->adler = state->check = adler32(0L, Z_NULL, 0);
639 state->mode = hold & 0x200 ? DICTID : TYPE;
645 state->flags = (int)(hold);
646 if ((state->flags & 0xff) != Z_DEFLATED) {
647 strm->msg = (char *)"unknown compression method";
651 if (state->flags & 0xe000) {
652 strm->msg = (char *)"unknown header flags set";
656 if (state->head != Z_NULL)
657 state->head->text = (int)((hold >> 8) & 1);
658 if (state->flags & 0x0200) CRC2(state->check, hold);
663 if (state->head != Z_NULL)
664 state->head->time = hold;
665 if (state->flags & 0x0200) CRC4(state->check, hold);
670 if (state->head != Z_NULL) {
671 state->head->xflags = (int)(hold & 0xff);
672 state->head->os = (int)(hold >> 8);
674 if (state->flags & 0x0200) CRC2(state->check, hold);
678 if (state->flags & 0x0400) {
680 state->length = (unsigned)(hold);
681 if (state->head != Z_NULL)
682 state->head->extra_len = (unsigned)hold;
683 if (state->flags & 0x0200) CRC2(state->check, hold);
686 else if (state->head != Z_NULL)
687 state->head->extra = Z_NULL;
690 if (state->flags & 0x0400) {
691 copy = state->length;
692 if (copy > have) copy = have;
694 if (state->head != Z_NULL &&
695 state->head->extra != Z_NULL) {
696 len = state->head->extra_len - state->length;
697 zmemcpy(state->head->extra + len, next,
698 len + copy > state->head->extra_max ?
699 state->head->extra_max - len : copy);
701 if (state->flags & 0x0200)
702 state->check = crc32(state->check, next, copy);
705 state->length -= copy;
707 if (state->length) goto inf_leave;
712 if (state->flags & 0x0800) {
713 if (have == 0) goto inf_leave;
716 len = (unsigned)(next[copy++]);
717 if (state->head != Z_NULL &&
718 state->head->name != Z_NULL &&
719 state->length < state->head->name_max)
720 state->head->name[state->length++] = len;
721 } while (len && copy < have);
722 if (state->flags & 0x0200)
723 state->check = crc32(state->check, next, copy);
726 if (len) goto inf_leave;
728 else if (state->head != Z_NULL)
729 state->head->name = Z_NULL;
731 state->mode = COMMENT;
733 if (state->flags & 0x1000) {
734 if (have == 0) goto inf_leave;
737 len = (unsigned)(next[copy++]);
738 if (state->head != Z_NULL &&
739 state->head->comment != Z_NULL &&
740 state->length < state->head->comm_max)
741 state->head->comment[state->length++] = len;
742 } while (len && copy < have);
743 if (state->flags & 0x0200)
744 state->check = crc32(state->check, next, copy);
747 if (len) goto inf_leave;
749 else if (state->head != Z_NULL)
750 state->head->comment = Z_NULL;
753 if (state->flags & 0x0200) {
755 if (hold != (state->check & 0xffff)) {
756 strm->msg = (char *)"header crc mismatch";
762 if (state->head != Z_NULL) {
763 state->head->hcrc = (int)((state->flags >> 9) & 1);
764 state->head->done = 1;
766 strm->adler = state->check = crc32(0L, Z_NULL, 0);
772 strm->adler = state->check = REVERSE(hold);
776 if (state->havedict == 0) {
780 strm->adler = state->check = adler32(0L, Z_NULL, 0);
783 if (flush == Z_BLOCK) goto inf_leave;
791 state->last = BITS(1);
794 case 0: /* stored block */
795 Tracev((stderr, "inflate: stored block%s\n",
796 state->last ? " (last)" : ""));
797 state->mode = STORED;
799 case 1: /* fixed block */
801 Tracev((stderr, "inflate: fixed codes block%s\n",
802 state->last ? " (last)" : ""));
803 state->mode = LEN; /* decode codes */
805 case 2: /* dynamic block */
806 Tracev((stderr, "inflate: dynamic codes block%s\n",
807 state->last ? " (last)" : ""));
811 strm->msg = (char *)"invalid block type";
817 BYTEBITS(); /* go to byte boundary */
819 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
820 strm->msg = (char *)"invalid stored block lengths";
824 state->length = (unsigned)hold & 0xffff;
825 Tracev((stderr, "inflate: stored length %u\n",
830 copy = state->length;
832 if (copy > have) copy = have;
833 if (copy > left) copy = left;
834 if (copy == 0) goto inf_leave;
835 zmemcpy(put, next, copy);
840 state->length -= copy;
843 Tracev((stderr, "inflate: stored end\n"));
848 state->nlen = BITS(5) + 257;
850 state->ndist = BITS(5) + 1;
852 state->ncode = BITS(4) + 4;
854 #ifndef PKZIP_BUG_WORKAROUND
855 if (state->nlen > 286 || state->ndist > 30) {
856 strm->msg = (char *)"too many length or distance symbols";
861 Tracev((stderr, "inflate: table sizes ok\n"));
863 state->mode = LENLENS;
865 while (state->have < state->ncode) {
867 state->lens[order[state->have++]] = (unsigned short)BITS(3);
870 while (state->have < 19)
871 state->lens[order[state->have++]] = 0;
872 state->next = state->codes;
873 state->lencode = (code const FAR *)(state->next);
875 ret = inflate_table(CODES, state->lens, 19, &(state->next),
876 &(state->lenbits), state->work);
878 strm->msg = (char *)"invalid code lengths set";
882 Tracev((stderr, "inflate: code lengths ok\n"));
884 state->mode = CODELENS;
886 while (state->have < state->nlen + state->ndist) {
888 this = state->lencode[BITS(state->lenbits)];
889 if ((unsigned)(this.bits) <= bits) break;
895 state->lens[state->have++] = this.val;
898 if (this.val == 16) {
899 NEEDBITS(this.bits + 2);
901 if (state->have == 0) {
902 strm->msg = (char *)"invalid bit length repeat";
906 len = state->lens[state->have - 1];
910 else if (this.val == 17) {
911 NEEDBITS(this.bits + 3);
918 NEEDBITS(this.bits + 7);
924 if (state->have + copy > state->nlen + state->ndist) {
925 strm->msg = (char *)"invalid bit length repeat";
930 state->lens[state->have++] = (unsigned short)len;
934 /* handle error breaks in while */
935 if (state->mode == BAD) break;
937 /* build code tables */
938 state->next = state->codes;
939 state->lencode = (code const FAR *)(state->next);
941 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
942 &(state->lenbits), state->work);
944 strm->msg = (char *)"invalid literal/lengths set";
948 state->distcode = (code const FAR *)(state->next);
950 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
951 &(state->next), &(state->distbits), state->work);
953 strm->msg = (char *)"invalid distances set";
957 Tracev((stderr, "inflate: codes ok\n"));
960 if (have >= 6 && left >= 258) {
962 inflate_fast(strm, out);
967 this = state->lencode[BITS(state->lenbits)];
968 if ((unsigned)(this.bits) <= bits) break;
971 if (this.op && (this.op & 0xf0) == 0) {
974 this = state->lencode[last.val +
975 (BITS(last.bits + last.op) >> last.bits)];
976 if ((unsigned)(last.bits + this.bits) <= bits) break;
982 state->length = (unsigned)this.val;
983 if ((int)(this.op) == 0) {
984 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
985 "inflate: literal '%c'\n" :
986 "inflate: literal 0x%02x\n", this.val));
991 Tracevv((stderr, "inflate: end of block\n"));
996 strm->msg = (char *)"invalid literal/length code";
1000 state->extra = (unsigned)(this.op) & 15;
1001 state->mode = LENEXT;
1004 NEEDBITS(state->extra);
1005 state->length += BITS(state->extra);
1006 DROPBITS(state->extra);
1008 Tracevv((stderr, "inflate: length %u\n", state->length));
1012 this = state->distcode[BITS(state->distbits)];
1013 if ((unsigned)(this.bits) <= bits) break;
1016 if ((this.op & 0xf0) == 0) {
1019 this = state->distcode[last.val +
1020 (BITS(last.bits + last.op) >> last.bits)];
1021 if ((unsigned)(last.bits + this.bits) <= bits) break;
1024 DROPBITS(last.bits);
1026 DROPBITS(this.bits);
1028 strm->msg = (char *)"invalid distance code";
1032 state->offset = (unsigned)this.val;
1033 state->extra = (unsigned)(this.op) & 15;
1034 state->mode = DISTEXT;
1037 NEEDBITS(state->extra);
1038 state->offset += BITS(state->extra);
1039 DROPBITS(state->extra);
1041 #ifdef INFLATE_STRICT
1042 if (state->offset > state->dmax) {
1043 strm->msg = (char *)"invalid distance too far back";
1048 if (state->offset > state->whave + out - left) {
1049 strm->msg = (char *)"invalid distance too far back";
1053 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1054 state->mode = MATCH;
1056 if (left == 0) goto inf_leave;
1058 if (state->offset > copy) { /* copy from window */
1059 copy = state->offset - copy;
1060 if (copy > state->write) {
1061 copy -= state->write;
1062 from = state->window + (state->wsize - copy);
1065 from = state->window + (state->write - copy);
1066 if (copy > state->length) copy = state->length;
1068 else { /* copy from output */
1069 from = put - state->offset;
1070 copy = state->length;
1072 if (copy > left) copy = left;
1074 state->length -= copy;
1078 if (state->length == 0) state->mode = LEN;
1081 if (left == 0) goto inf_leave;
1082 *put++ = (unsigned char)(state->length);
1090 strm->total_out += out;
1091 state->total += out;
1093 strm->adler = state->check =
1094 UPDATE(state->check, put - out, out);
1098 state->flags ? hold :
1100 REVERSE(hold)) != state->check) {
1101 strm->msg = (char *)"incorrect data check";
1106 Tracev((stderr, "inflate: check matches trailer\n"));
1109 state->mode = LENGTH;
1111 if (state->wrap && state->flags) {
1113 if (hold != (state->total & 0xffffffffUL)) {
1114 strm->msg = (char *)"incorrect length check";
1119 Tracev((stderr, "inflate: length matches trailer\n"));
1133 return Z_STREAM_ERROR;
1137 Return from inflate(), updating the total counts and the check value.
1138 If there was no progress during the inflate() call, return a buffer
1139 error. Call updatewindow() to create and/or update the window state.
1140 Note: a memory error from inflate() is non-recoverable.
1144 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1145 if (updatewindow(strm, out)) {
1149 in -= strm->avail_in;
1150 out -= strm->avail_out;
1151 strm->total_in += in;
1152 strm->total_out += out;
1153 state->total += out;
1154 if (state->wrap && out)
1155 strm->adler = state->check =
1156 UPDATE(state->check, strm->next_out - out, out);
1157 strm->data_type = state->bits + (state->last ? 64 : 0) +
1158 (state->mode == TYPE ? 128 : 0);
1159 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1164 int ZEXPORT inflateEnd(strm)
1167 struct inflate_state FAR *state;
1168 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1169 return Z_STREAM_ERROR;
1170 state = (struct inflate_state FAR *)strm->state;
1171 if (state->window != Z_NULL) ZFREE(strm, state->window);
1172 ZFREE(strm, strm->state);
1173 strm->state = Z_NULL;
1174 Tracev((stderr, "inflate: end\n"));
1178 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1180 const Bytef *dictionary;
1183 struct inflate_state FAR *state;
1187 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1188 state = (struct inflate_state FAR *)strm->state;
1189 if (state->wrap != 0 && state->mode != DICT)
1190 return Z_STREAM_ERROR;
1192 /* check for correct dictionary id */
1193 if (state->mode == DICT) {
1194 id = adler32(0L, Z_NULL, 0);
1195 id = adler32(id, dictionary, dictLength);
1196 if (id != state->check)
1197 return Z_DATA_ERROR;
1200 /* copy dictionary to window */
1201 if (updatewindow(strm, strm->avail_out)) {
1205 if (dictLength > state->wsize) {
1206 zmemcpy(state->window, dictionary + dictLength - state->wsize,
1208 state->whave = state->wsize;
1211 zmemcpy(state->window + state->wsize - dictLength, dictionary,
1213 state->whave = dictLength;
1215 state->havedict = 1;
1216 Tracev((stderr, "inflate: dictionary set\n"));
1220 int ZEXPORT inflateGetHeader(strm, head)
1224 struct inflate_state FAR *state;
1227 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1228 state = (struct inflate_state FAR *)strm->state;
1229 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1231 /* save header structure */
1238 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1239 or when out of input. When called, *have is the number of pattern bytes
1240 found in order so far, in 0..3. On return *have is updated to the new
1241 state. If on return *have equals four, then the pattern was found and the
1242 return value is how many bytes were read including the last byte of the
1243 pattern. If *have is less than four, then the pattern has not been found
1244 yet and the return value is len. In the latter case, syncsearch() can be
1245 called again with more data and the *have state. *have is initialized to
1246 zero for the first call.
1248 local unsigned syncsearch(have, buf, len)
1250 unsigned char FAR *buf;
1258 while (next < len && got < 4) {
1259 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1271 int ZEXPORT inflateSync(strm)
1274 unsigned len; /* number of bytes to look at or looked at */
1275 unsigned long in, out; /* temporary to save total_in and total_out */
1276 unsigned char buf[4]; /* to restore bit buffer to byte string */
1277 struct inflate_state FAR *state;
1279 /* check parameters */
1280 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1281 state = (struct inflate_state FAR *)strm->state;
1282 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1284 /* if first time, start search in bit buffer */
1285 if (state->mode != SYNC) {
1287 state->hold <<= state->bits & 7;
1288 state->bits -= state->bits & 7;
1290 while (state->bits >= 8) {
1291 buf[len++] = (unsigned char)(state->hold);
1296 syncsearch(&(state->have), buf, len);
1299 /* search available input */
1300 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1301 strm->avail_in -= len;
1302 strm->next_in += len;
1303 strm->total_in += len;
1305 /* return no joy or set up to restart inflate() on a new block */
1306 if (state->have != 4) return Z_DATA_ERROR;
1307 in = strm->total_in; out = strm->total_out;
1309 strm->total_in = in; strm->total_out = out;
1315 Returns true if inflate is currently at the end of a block generated by
1316 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1317 implementation to provide an additional safety check. PPP uses
1318 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1319 block. When decompressing, PPP checks that at the end of input packet,
1320 inflate is waiting for these length bytes.
1322 int ZEXPORT inflateSyncPoint(strm)
1325 struct inflate_state FAR *state;
1327 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1328 state = (struct inflate_state FAR *)strm->state;
1329 return state->mode == STORED && state->bits == 0;
1332 int ZEXPORT inflateCopy(dest, source)
1336 struct inflate_state FAR *state;
1337 struct inflate_state FAR *copy;
1338 unsigned char FAR *window;
1342 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1343 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1344 return Z_STREAM_ERROR;
1345 state = (struct inflate_state FAR *)source->state;
1347 /* allocate space */
1348 copy = (struct inflate_state FAR *)
1349 ZALLOC(source, 1, sizeof(struct inflate_state));
1350 if (copy == Z_NULL) return Z_MEM_ERROR;
1352 if (state->window != Z_NULL) {
1353 window = (unsigned char FAR *)
1354 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1355 if (window == Z_NULL) {
1356 ZFREE(source, copy);
1362 zmemcpy(dest, source, sizeof(z_stream));
1363 zmemcpy(copy, state, sizeof(struct inflate_state));
1364 if (state->lencode >= state->codes &&
1365 state->lencode <= state->codes + ENOUGH - 1) {
1366 copy->lencode = copy->codes + (state->lencode - state->codes);
1367 copy->distcode = copy->codes + (state->distcode - state->codes);
1369 copy->next = copy->codes + (state->next - state->codes);
1370 if (window != Z_NULL) {
1371 wsize = 1U << state->wbits;
1372 zmemcpy(window, state->window, wsize);
1374 copy->window = window;
1375 dest->state = (struct internal_state FAR *)copy;