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