199767f8919635c4928607450d9e0abb932109ceToomas Soome/* inflate.c -- zlib decompression
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Copyright (C) 1995-2012 Mark Adler
199767f8919635c4928607450d9e0abb932109ceToomas Soome * For conditions of distribution and use, see copyright notice in zlib.h
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Change history:
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta0 24 Nov 2002
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - First version -- complete rewrite of inflate to simplify code, avoid
199767f8919635c4928607450d9e0abb932109ceToomas Soome * creation of window when not needed, minimize use of window when it is
199767f8919635c4928607450d9e0abb932109ceToomas Soome * needed, make inffast.c even faster, implement gzip decoding, and to
199767f8919635c4928607450d9e0abb932109ceToomas Soome * improve code readability and style over the previous zlib inflate code
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta1 25 Nov 2002
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Use pointers for available input and output checking in inffast.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Remove input and output counters in inffast.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Remove unnecessary second byte pull from length extra in inffast.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Unroll direct copy to three copies per loop in inffast.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta2 4 Dec 2002
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Change external routine names to reduce potential conflicts
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Correct filename to inffixed.h for fixed tables in inflate.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Make hbuf[] unsigned char to match parameter type in inflate.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
199767f8919635c4928607450d9e0abb932109ceToomas Soome * to avoid negation problem on Alphas (64 bit) in inflate.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta3 22 Dec 2002
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Add comments on state->bits assertion in inffast.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Add comments on op field in inftrees.h
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Fix bug in reuse of allocated window after inflateReset()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Remove bit fields--back to byte structure for speed
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Use local copies of stream next and avail values, as well as local bit
199767f8919635c4928607450d9e0abb932109ceToomas Soome * buffer and bit count in inflate()--for speed when inflate_fast() not used
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta4 1 Jan 2003
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Move a comment on output buffer sizes from inffast.c to inflate.c
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Add comments in inffast.c to introduce the inflate_fast() routine
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Rearrange window copies in inflate_fast() for speed and simplification
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Unroll last copy for window match in inflate_fast()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Use local copies of window variables in inflate_fast() for speed
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Pull out common wnext == 0 case for speed in inflate_fast()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Make op and len in inflate_fast() unsigned for consistency
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Add FAR to lcode and dcode declarations in inflate_fast()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Simplified bad distance check in inflate_fast()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
199767f8919635c4928607450d9e0abb932109ceToomas Soome * source file infback.c to provide a call-back interface to inflate for
199767f8919635c4928607450d9e0abb932109ceToomas Soome * programs like gzip and unzip -- uses window as output buffer to avoid
199767f8919635c4928607450d9e0abb932109ceToomas Soome * window copying
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta5 1 Jan 2003
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Improved inflateBack() interface to allow the caller to provide initial
199767f8919635c4928607450d9e0abb932109ceToomas Soome * input in strm.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Fixed stored blocks bug in inflateBack()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta6 4 Jan 2003
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Added comments in inffast.c on effectiveness of POSTINC
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Typecasting all around to reduce compiler warnings
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Changed loops from while (1) or do {} while (1) to for (;;), again to
199767f8919635c4928607450d9e0abb932109ceToomas Soome * make compilers happy
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Changed type of window in inflateBackInit() to unsigned char *
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.beta7 27 Jan 2003
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Changed many types to unsigned or unsigned short to avoid warnings
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Added inflateCopy() function
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1.2.0 9 Mar 2003
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Changed inflateBack() interface to provide separate opaque descriptors
199767f8919635c4928607450d9e0abb932109ceToomas Soome * for the in() and out() functions
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Changed inflateBack() argument and in_func typedef to swap the length
199767f8919635c4928607450d9e0abb932109ceToomas Soome * and buffer address return values for the input function
199767f8919635c4928607450d9e0abb932109ceToomas Soome * - Check next_in and next_out for Z_NULL on entry to inflate()
199767f8919635c4928607450d9e0abb932109ceToomas Soome * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* function prototypes */
199767f8919635c4928607450d9e0abb932109ceToomas Soomelocal void fixedtables OF((struct inflate_state FAR *state));
199767f8919635c4928607450d9e0abb932109ceToomas Soomelocal int updatewindow OF((z_streamp strm, const unsigned char FAR *end,
199767f8919635c4928607450d9e0abb932109ceToomas Soomelocal unsigned syncsearch OF((unsigned FAR *have, const unsigned char FAR *buf,
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->total_in = strm->total_out = state->total = 0;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->wrap) /* to support ill-conceived Java test suite */
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->lencode = state->distcode = state->next = state->codes;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* get the state */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* extract wrap request from windowBits parameter */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* set number of window bits, free window if different */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (windowBits && (windowBits < 8 || windowBits > 15))
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* update state and reset the rest of it */
199767f8919635c4928607450d9e0abb932109ceToomas Soomeint ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = Z_NULL; /* in case we return an error */
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->state = (struct internal_state FAR *)state;
199767f8919635c4928607450d9e0abb932109ceToomas Soomeint ZEXPORT inflateInit_(strm, version, stream_size)
199767f8919635c4928607450d9e0abb932109ceToomas Soome return inflateInit2_(strm, DEF_WBITS, version, stream_size);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome Return state with length and distance decoding tables and index sizes set to
199767f8919635c4928607450d9e0abb932109ceToomas Soome fixed code decoding. Normally this returns fixed tables from inffixed.h.
199767f8919635c4928607450d9e0abb932109ceToomas Soome If BUILDFIXED is defined, then instead this routine builds the tables the
199767f8919635c4928607450d9e0abb932109ceToomas Soome first time it's called, and returns those tables the first time and
199767f8919635c4928607450d9e0abb932109ceToomas Soome thereafter. This reduces the size of the code by about 2K bytes, in
199767f8919635c4928607450d9e0abb932109ceToomas Soome exchange for a little execution time. However, BUILDFIXED should not be
199767f8919635c4928607450d9e0abb932109ceToomas Soome used for threaded applications, since the rewriting of the tables and virgin
199767f8919635c4928607450d9e0abb932109ceToomas Soome may not be thread-safe.
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* build fixed huffman tables if first call (may not be thread safe) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* distance table */
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* do this just once */
199767f8919635c4928607450d9e0abb932109ceToomas Soome#else /* !BUILDFIXED */
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* BUILDFIXED */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
199767f8919635c4928607450d9e0abb932109ceToomas Soome defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
199767f8919635c4928607450d9e0abb932109ceToomas Soome those tables to stdout, which would be piped to inffixed.h. A small program
199767f8919635c4928607450d9e0abb932109ceToomas Soome can simply call makefixed to do this:
199767f8919635c4928607450d9e0abb932109ceToomas Soome void makefixed(void);
199767f8919635c4928607450d9e0abb932109ceToomas Soome int main(void)
199767f8919635c4928607450d9e0abb932109ceToomas Soome makefixed();
199767f8919635c4928607450d9e0abb932109ceToomas Soome Then that can be linked with zlib built with MAKEFIXED defined and run:
199767f8919635c4928607450d9e0abb932109ceToomas Soome puts(" /* inffixed.h -- table for decoding fixed codes");
199767f8919635c4928607450d9e0abb932109ceToomas Soome puts(" * Generated automatically by makefixed().");
199767f8919635c4928607450d9e0abb932109ceToomas Soome puts(" /* WARNING: this file should *not* be used by applications.");
199767f8919635c4928607450d9e0abb932109ceToomas Soome puts(" It is part of the implementation of this library and is");
199767f8919635c4928607450d9e0abb932109ceToomas Soome puts(" subject to change. Applications should only use zlib.h.");
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf(" static const code lenfix[%u] = {", size);
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
199767f8919635c4928607450d9e0abb932109ceToomas Soome state.lencode[low].bits, state.lencode[low].val);
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf("\n static const code distfix[%u] = {", size);
199767f8919635c4928607450d9e0abb932109ceToomas Soome printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* MAKEFIXED */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Update the window with the last wsize (normally 32K) bytes written before
199767f8919635c4928607450d9e0abb932109ceToomas Soome returning. If window does not exist yet, create it. This is only called
199767f8919635c4928607450d9e0abb932109ceToomas Soome when a window is already in use, or when output has been written during this
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate call, but the end of the deflate stream has not been reached yet.
199767f8919635c4928607450d9e0abb932109ceToomas Soome It is also called to create a window for dictionary data when a dictionary
199767f8919635c4928607450d9e0abb932109ceToomas Soome Providing output buffers larger than 32K to inflate() should provide a speed
199767f8919635c4928607450d9e0abb932109ceToomas Soome advantage, since only the last 32K of output is copied to the sliding window
199767f8919635c4928607450d9e0abb932109ceToomas Soome upon return from inflate(), and since all distances after the first 32K of
199767f8919635c4928607450d9e0abb932109ceToomas Soome output will fall in the output data, making match copies simpler and faster.
199767f8919635c4928607450d9e0abb932109ceToomas Soome The advantage may be dependent on the size of the processor's data caches.
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* if it hasn't been done already, allocate space for the window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome sizeof(unsigned char));
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* if window not in use yet, initialize */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* copy state->wsize or less output bytes into the circular window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy(state->window, end - state->wsize, state->wsize);
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy(state->window + state->wnext, end - copy, dist);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->wnext == state->wsize) state->wnext = 0;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->whave < state->wsize) state->whave += dist;
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Macros for inflate(): */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* check function to use adler32() for zlib or crc32() for gzip */
199767f8919635c4928607450d9e0abb932109ceToomas Soome (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
199767f8919635c4928607450d9e0abb932109ceToomas Soome# define UPDATE(check, buf, len) adler32(check, buf, len)
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* check macros for header crc */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Load registers with state in inflate() for speed */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Restore state from registers in inflate() */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Clear the input bit accumulator */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Get a byte of input into the bit accumulator, or return from inflate()
199767f8919635c4928607450d9e0abb932109ceToomas Soome if there is no input available. */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Assure that there are at least n bits in the bit accumulator. If there is
199767f8919635c4928607450d9e0abb932109ceToomas Soome not enough available input to do that, then return from inflate(). */
199767f8919635c4928607450d9e0abb932109ceToomas Soome while (bits < (unsigned)(n)) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Return the low n bits of the bit accumulator (n < 16) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Remove n bits from the bit accumulator */
199767f8919635c4928607450d9e0abb932109ceToomas Soome bits -= (unsigned)(n); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Remove zero to seven bits as needed to go to a byte boundary */
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate() uses a state machine to process as much input data and generate as
199767f8919635c4928607450d9e0abb932109ceToomas Soome much output data as possible before returning. The state machine is
199767f8919635c4928607450d9e0abb932109ceToomas Soome structured roughly as follows:
199767f8919635c4928607450d9e0abb932109ceToomas Soome for (;;) switch (state) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome case STATEn:
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (not enough input data or output space to make progress)
199767f8919635c4928607450d9e0abb932109ceToomas Soome ... make progress ...
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = STATEm;
199767f8919635c4928607450d9e0abb932109ceToomas Soome so when inflate() is called again, the same case is attempted again, and
199767f8919635c4928607450d9e0abb932109ceToomas Soome if the appropriate resources are provided, the machine proceeds to the
199767f8919635c4928607450d9e0abb932109ceToomas Soome next state. The NEEDBITS() macro is usually the way the state evaluates
199767f8919635c4928607450d9e0abb932109ceToomas Soome whether it can proceed or should return. NEEDBITS() does the return if
199767f8919635c4928607450d9e0abb932109ceToomas Soome the requested bits are not available. The typical use of the BITS macros
199767f8919635c4928607450d9e0abb932109ceToomas Soome NEEDBITS(n);
199767f8919635c4928607450d9e0abb932109ceToomas Soome ... do something with BITS(n) ...
199767f8919635c4928607450d9e0abb932109ceToomas Soome DROPBITS(n);
199767f8919635c4928607450d9e0abb932109ceToomas Soome where NEEDBITS(n) either returns from inflate() if there isn't enough
199767f8919635c4928607450d9e0abb932109ceToomas Soome input left to load n bits into the accumulator, or it continues. BITS(n)
199767f8919635c4928607450d9e0abb932109ceToomas Soome gives the low n bits in the accumulator. When done, DROPBITS(n) drops
199767f8919635c4928607450d9e0abb932109ceToomas Soome the low n bits off the accumulator. INITBITS() clears the accumulator
199767f8919635c4928607450d9e0abb932109ceToomas Soome and sets the number of available bits to zero. BYTEBITS() discards just
199767f8919635c4928607450d9e0abb932109ceToomas Soome enough bits to put the accumulator on a byte boundary. After BYTEBITS()
199767f8919635c4928607450d9e0abb932109ceToomas Soome and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
199767f8919635c4928607450d9e0abb932109ceToomas Soome NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
199767f8919635c4928607450d9e0abb932109ceToomas Soome if there is no input available. The decoding of variable length codes uses
199767f8919635c4928607450d9e0abb932109ceToomas Soome PULLBYTE() directly in order to pull just enough bytes to decode the next
199767f8919635c4928607450d9e0abb932109ceToomas Soome code, and no more.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Some states loop until they get enough input, making sure that enough
199767f8919635c4928607450d9e0abb932109ceToomas Soome state information is maintained to continue the loop where it left off
199767f8919635c4928607450d9e0abb932109ceToomas Soome if NEEDBITS() returns in the loop. For example, want, need, and keep
199767f8919635c4928607450d9e0abb932109ceToomas Soome would all have to actually be part of the saved state in case NEEDBITS()
199767f8919635c4928607450d9e0abb932109ceToomas Soome case STATEw:
199767f8919635c4928607450d9e0abb932109ceToomas Soome while (want < need) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome NEEDBITS(n);
199767f8919635c4928607450d9e0abb932109ceToomas Soome keep[want++] = BITS(n);
199767f8919635c4928607450d9e0abb932109ceToomas Soome DROPBITS(n);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = STATEx;
199767f8919635c4928607450d9e0abb932109ceToomas Soome case STATEx:
199767f8919635c4928607450d9e0abb932109ceToomas Soome As shown above, if the next state is also the next case, then the break
199767f8919635c4928607450d9e0abb932109ceToomas Soome A state may also return if there is not enough output space available to
199767f8919635c4928607450d9e0abb932109ceToomas Soome complete that state. Those states are copying stored data, writing a
199767f8919635c4928607450d9e0abb932109ceToomas Soome literal byte, and copying a matching string.
199767f8919635c4928607450d9e0abb932109ceToomas Soome When returning, a "goto inf_leave" is used to update the total counters,
199767f8919635c4928607450d9e0abb932109ceToomas Soome update the check value, and determine whether any progress has been made
199767f8919635c4928607450d9e0abb932109ceToomas Soome during that inflate() call in order to return the proper return code.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Progress is defined as a change in either strm->avail_in or strm->avail_out.
199767f8919635c4928607450d9e0abb932109ceToomas Soome When there is a window, goto inf_leave will update the window with the last
199767f8919635c4928607450d9e0abb932109ceToomas Soome output written. If a goto inf_leave occurs in the middle of decompression
199767f8919635c4928607450d9e0abb932109ceToomas Soome and there is no window currently, goto inf_leave will create one and copy
199767f8919635c4928607450d9e0abb932109ceToomas Soome output to the window for the next call of inflate().
199767f8919635c4928607450d9e0abb932109ceToomas Soome In this implementation, the flush parameter of inflate() only affects the
199767f8919635c4928607450d9e0abb932109ceToomas Soome return code (per zlib.h). inflate() always writes as much as possible to
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->next_out, given the space available and the provided input--the effect
199767f8919635c4928607450d9e0abb932109ceToomas Soome documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
199767f8919635c4928607450d9e0abb932109ceToomas Soome the allocation of and copying into a sliding window until necessary, which
199767f8919635c4928607450d9e0abb932109ceToomas Soome provides the effect documented in zlib.h for Z_FINISH when the entire input
199767f8919635c4928607450d9e0abb932109ceToomas Soome stream available. So the only thing the flush parameter actually does is:
199767f8919635c4928607450d9e0abb932109ceToomas Soome when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
199767f8919635c4928607450d9e0abb932109ceToomas Soome will return Z_BUF_ERROR if it has not reached the end of the stream.
199767f8919635c4928607450d9e0abb932109ceToomas Soome z_const unsigned char FAR *next; /* next input */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned have, left; /* available input and output */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned in, out; /* save starting available input and output */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned copy; /* number of stored or match bytes to copy */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char FAR *from; /* where to copy match bytes from */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned len; /* length to copy for repeats, bits to drop */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
199767f8919635c4928607450d9e0abb932109ceToomas Soome static const unsigned short order[19] = /* permutation of code lengths */
199767f8919635c4928607450d9e0abb932109ceToomas Soome {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
199767f8919635c4928607450d9e0abb932109ceToomas Soome (strm->next_in == Z_NULL && strm->avail_in != 0))
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (!(state->wrap & 1) || /* check if zlib header allowed */
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"unknown compression method";
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->adler = state->check = adler32(0L, Z_NULL, 0);
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"unknown compression method";
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"unknown header flags set";
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->flags & 0x0200) CRC2(state->check, hold);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->flags & 0x0200) CRC4(state->check, hold);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->flags & 0x0200) CRC2(state->check, hold);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->flags & 0x0200) CRC2(state->check, hold);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->check = crc32(state->check, next, copy);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->check = crc32(state->check, next, copy);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->check = crc32(state->check, next, copy);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->head->hcrc = (int)((state->flags >> 9) & 1);
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->adler = state->check = crc32(0L, Z_NULL, 0);
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->adler = state->check = adler32(0L, Z_NULL, 0);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (flush == Z_BLOCK || flush == Z_TREES) goto inf_leave;
199767f8919635c4928607450d9e0abb932109ceToomas Soome case 0: /* stored block */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracev((stderr, "inflate: fixed codes block%s\n",
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracev((stderr, "inflate: dynamic codes block%s\n",
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid stored block lengths";
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"too many length or distance symbols";
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->lens[order[state->have++]] = (unsigned short)BITS(3);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->lencode = (const code FAR *)(state->next);
199767f8919635c4928607450d9e0abb932109ceToomas Soome ret = inflate_table(CODES, state->lens, 19, &(state->next),
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid code lengths set";
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracev((stderr, "inflate: code lengths ok\n"));
199767f8919635c4928607450d9e0abb932109ceToomas Soome while (state->have < state->nlen + state->ndist) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid bit length repeat";
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->have + copy > state->nlen + state->ndist) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid bit length repeat";
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->lens[state->have++] = (unsigned short)len;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* handle error breaks in while */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check for end-of-block code (better have one) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid code -- missing end-of-block";
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* build code tables -- note: do not change the lenbits or distbits
199767f8919635c4928607450d9e0abb932109ceToomas Soome values here (9 and 6) without reading the comments in inftrees.h
199767f8919635c4928607450d9e0abb932109ceToomas Soome concerning the ENOUGH constants, which depend on those values */
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->lencode = (const code FAR *)(state->next);
199767f8919635c4928607450d9e0abb932109ceToomas Soome ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid literal/lengths set";
199767f8919635c4928607450d9e0abb932109ceToomas Soome state->distcode = (const code FAR *)(state->next);
199767f8919635c4928607450d9e0abb932109ceToomas Soome ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
199767f8919635c4928607450d9e0abb932109ceToomas Soome &(state->next), &(state->distbits), state->work);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((unsigned)(last.bits + here.bits) <= bits) break;
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
199767f8919635c4928607450d9e0abb932109ceToomas Soome "inflate: literal '%c'\n" :
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid literal/length code";
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, "inflate: length %u\n", state->length));
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((unsigned)(last.bits + here.bits) <= bits) break;
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid distance too far back";
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracevv((stderr, "inflate: distance %u\n", state->offset));
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->offset > copy) { /* copy from window */
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->msg = (char *)"invalid distance too far back";
199767f8919635c4928607450d9e0abb932109ceToomas Soome#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (copy > state->length) copy = state->length;
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--copy);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (copy > state->length) copy = state->length;
199767f8919635c4928607450d9e0abb932109ceToomas Soome else { /* copy from output */
199767f8919635c4928607450d9e0abb932109ceToomas Soome } while (--copy);
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracev((stderr, "inflate: check matches trailer\n"));
199767f8919635c4928607450d9e0abb932109ceToomas Soome Tracev((stderr, "inflate: length matches trailer\n"));
199767f8919635c4928607450d9e0abb932109ceToomas Soome Return from inflate(), updating the total counts and the check value.
199767f8919635c4928607450d9e0abb932109ceToomas Soome If there was no progress during the inflate() call, return a buffer
199767f8919635c4928607450d9e0abb932109ceToomas Soome error. Call updatewindow() to create and/or update the window state.
199767f8919635c4928607450d9e0abb932109ceToomas Soome Note: a memory error from inflate() is non-recoverable.
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
199767f8919635c4928607450d9e0abb932109ceToomas Soome UPDATE(state->check, strm->next_out - out, out);
199767f8919635c4928607450d9e0abb932109ceToomas Soome strm->data_type = state->bits + (state->last ? 64 : 0) +
199767f8919635c4928607450d9e0abb932109ceToomas Soome (state->mode == LEN_ || state->mode == COPY_ ? 256 : 0);
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (state->window != Z_NULL) ZFREE(strm, state->window);
199767f8919635c4928607450d9e0abb932109ceToomas Soomeint ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check state */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* copy dictionary */
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy(dictionary, state->window + state->wnext,
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy(dictionary + state->whave - state->wnext,
199767f8919635c4928607450d9e0abb932109ceToomas Soomeint ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned long dictid;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check state */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check for correct dictionary identifier */
199767f8919635c4928607450d9e0abb932109ceToomas Soome dictid = adler32(dictid, dictionary, dictLength);
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* copy dictionary to window using updatewindow(), which will amend the
199767f8919635c4928607450d9e0abb932109ceToomas Soome existing dictionary if appropriate */
199767f8919635c4928607450d9e0abb932109ceToomas Soome ret = updatewindow(strm, dictionary + dictLength, dictLength);
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check state */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* save header structure */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
199767f8919635c4928607450d9e0abb932109ceToomas Soome or when out of input. When called, *have is the number of pattern bytes
199767f8919635c4928607450d9e0abb932109ceToomas Soome found in order so far, in 0..3. On return *have is updated to the new
199767f8919635c4928607450d9e0abb932109ceToomas Soome state. If on return *have equals four, then the pattern was found and the
199767f8919635c4928607450d9e0abb932109ceToomas Soome return value is how many bytes were read including the last byte of the
199767f8919635c4928607450d9e0abb932109ceToomas Soome pattern. If *have is less than four, then the pattern has not been found
199767f8919635c4928607450d9e0abb932109ceToomas Soome yet and the return value is len. In the latter case, syncsearch() can be
199767f8919635c4928607450d9e0abb932109ceToomas Soome called again with more data and the *have state. *have is initialized to
199767f8919635c4928607450d9e0abb932109ceToomas Soome zero for the first call.
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned len; /* number of bytes to look at or looked at */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned long in, out; /* temporary to save total_in and total_out */
199767f8919635c4928607450d9e0abb932109ceToomas Soome unsigned char buf[4]; /* to restore bit buffer to byte string */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check parameters */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* if first time, start search in bit buffer */
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* search available input */
199767f8919635c4928607450d9e0abb932109ceToomas Soome len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* return no joy or set up to restart inflate() on a new block */
199767f8919635c4928607450d9e0abb932109ceToomas Soome Returns true if inflate is currently at the end of a block generated by
199767f8919635c4928607450d9e0abb932109ceToomas Soome Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
199767f8919635c4928607450d9e0abb932109ceToomas Soome implementation to provide an additional safety check. PPP uses
199767f8919635c4928607450d9e0abb932109ceToomas Soome Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
199767f8919635c4928607450d9e0abb932109ceToomas Soome block. When decompressing, PPP checks that at the end of input packet,
199767f8919635c4928607450d9e0abb932109ceToomas Soome inflate is waiting for these length bytes.
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome return state->mode == STORED && state->bits == 0;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* check input */
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
199767f8919635c4928607450d9e0abb932109ceToomas Soome source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)source->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* allocate space */
199767f8919635c4928607450d9e0abb932109ceToomas Soome ZALLOC(source, 1, sizeof(struct inflate_state));
199767f8919635c4928607450d9e0abb932109ceToomas Soome ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
199767f8919635c4928607450d9e0abb932109ceToomas Soome /* copy state */
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
199767f8919635c4928607450d9e0abb932109ceToomas Soome zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
199767f8919635c4928607450d9e0abb932109ceToomas Soome copy->lencode = copy->codes + (state->lencode - state->codes);
199767f8919635c4928607450d9e0abb932109ceToomas Soome copy->distcode = copy->codes + (state->distcode - state->codes);
199767f8919635c4928607450d9e0abb932109ceToomas Soome copy->next = copy->codes + (state->next - state->codes);
199767f8919635c4928607450d9e0abb932109ceToomas Soome dest->state = (struct internal_state FAR *)copy;
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
199767f8919635c4928607450d9e0abb932109ceToomas Soome if (strm == Z_NULL || strm->state == Z_NULL) return -(1L << 16);
199767f8919635c4928607450d9e0abb932109ceToomas Soome state = (struct inflate_state FAR *)strm->state;
199767f8919635c4928607450d9e0abb932109ceToomas Soome (state->mode == MATCH ? state->was - state->length : 0));