1592N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1592N/A * This code is free software; you can redistribute it and/or modify it 1592N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 1592N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 1592N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1592N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1592N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1592N/A * version 2 for more details (a copy is included in the LICENSE file that 1592N/A * You should have received a copy of the GNU General Public License version 1592N/A * 2 along with this work; if not, write to the Free Software Foundation, 1592N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1592N/A * Copyright (C) 1995-2005 Mark Adler 1592N/A * For conditions of distribution and use, see copyright notice in zlib.h 1592N/A * - First version -- complete rewrite of inflate to simplify code, avoid 1592N/A * creation of window when not needed, minimize use of window when it is 1592N/A * improve code readability and style over the previous zlib inflate code 1592N/A * - Change external routine names to reduce potential conflicts 1592N/A * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset) 1592N/A * - Fix bug in reuse of allocated window after inflateReset() 1592N/A * - Remove bit fields--back to byte structure for speed 1592N/A * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths 1592N/A * - Change post-increments to pre-increments in inflate_fast(), PPC biased? 1592N/A * - Add compile time option, POSTINC, to use post-increments instead (Intel?) 1592N/A * - Make MATCH copy in inflate() much faster for when inflate_fast() not used 1592N/A * - Use local copies of stream next and avail values, as well as local bit 1592N/A * buffer and bit count in inflate()--for speed when inflate_fast() not used 1592N/A * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings 1592N/A * - Rearrange window copies in inflate_fast() for speed and simplification 1592N/A * - Unroll last copy for window match in inflate_fast() 1592N/A * - Use local copies of window variables in inflate_fast() for speed 1592N/A * - Pull out common write == 0 case for speed in inflate_fast() 1592N/A * - Make op and len in inflate_fast() unsigned for consistency 1592N/A * - Add FAR to lcode and dcode declarations in inflate_fast() 1592N/A * - Simplified bad distance check in inflate_fast() 1592N/A * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new 1592N/A * programs like gzip and unzip -- uses window as output buffer to avoid 1592N/A * - Improved inflateBack() interface to allow the caller to provide initial 1592N/A * - Fixed stored blocks bug in inflateBack() 1592N/A * - Typecasting all around to reduce compiler warnings 1592N/A * - Changed loops from while (1) or do {} while (1) to for (;;), again to 1592N/A * - Changed type of window in inflateBackInit() to unsigned char * 1592N/A * - Changed many types to unsigned or unsigned short to avoid warnings 1592N/A * - Added inflateCopy() function 1592N/A * - Changed inflateBack() interface to provide separate opaque descriptors 1592N/A * for the in() and out() functions 1592N/A * - Changed inflateBack() argument and in_func typedef to swap the length 1592N/A * and buffer address return values for the input function 1592N/A * - Check next_in and next_out for Z_NULL on entry to inflate() 1592N/A * The history for versions after 1.2.0 are in ChangeLog in zlib distribution. 1592N/A Return state with length and distance decoding tables and index sizes set to 1592N/A If BUILDFIXED is defined, then instead this routine builds the tables the 1592N/A first time it's called, and returns those tables the first time and 1592N/A thereafter. This reduces the size of the code by about 2K bytes, in 1592N/A exchange for a little execution time. However, BUILDFIXED should not be 1592N/A used for threaded applications, since the rewriting of the tables and virgin 1592N/A /* build fixed huffman tables if first call (may not be thread safe) */ 1592N/A defines BUILDFIXED, so the tables are built on the fly. makefixed() writes 1592N/A can simply call makefixed to do this: 1592N/A Then that can be linked with zlib built with MAKEFIXED defined and run: 1592N/A puts(
" * Generated automatically by makefixed().");
1592N/A puts(
" /* WARNING: this file should *not* be used by applications.");
1592N/A puts(
" It is part of the implementation of this library and is");
1592N/A Update the window with the last wsize (normally 32K) bytes written before 1592N/A returning. If window does not exist yet, create it. This is only called 1592N/A when a window is already in use, or when output has been written during this 1592N/A inflate call, but the end of the deflate stream has not been reached yet. 1592N/A It is also called to create a window for dictionary data when a dictionary 1592N/A Providing output buffers larger than 32K to inflate() should provide a speed 1592N/A advantage, since only the last 32K of output is copied to the sliding window 1592N/A upon return from inflate(), and since all distances after the first 32K of 1592N/A output will fall in the output data, making match copies simpler and faster. 1592N/A The advantage may be dependent on the size of the processor's data caches. 1592N/A /* if it hasn't been done already, allocate space for the window */ 1592N/A /* if window not in use yet, initialize */ 1592N/A /* copy state->wsize or less output bytes into the circular window */ 1592N/A/* check function to use adler32() for zlib or crc32() for gzip */ 1592N/A/* check macros for header crc */ 1592N/A/* Load registers with state in inflate() for speed */ 1592N/A/* Restore state from registers in inflate() */ 1592N/A/* Clear the input bit accumulator */ 1592N/A/* Get a byte of input into the bit accumulator, or return from inflate() 1592N/A if there is no input available. */ 1592N/A/* Assure that there are at least n bits in the bit accumulator. If there is 1592N/A not enough available input to do that, then return from inflate(). */ 1592N/A/* Return the low n bits of the bit accumulator (n < 16) */ 1592N/A/* Remove n bits from the bit accumulator */ 1592N/A/* Remove zero to seven bits as needed to go to a byte boundary */ 1592N/A/* Reverse the bytes in a 32-bit value */ 1592N/A ((((q) >>
24) &
0xff) + (((q) >>
8) &
0xff00) + \
1592N/A (((q) &
0xff00) <<
8) + (((q) &
0xff) <<
24))
1592N/A inflate() uses a state machine to process as much input data and generate as 1592N/A much output data as possible before returning. The state machine is 1592N/A structured roughly as follows: 1592N/A if (not enough input data or output space to make progress) 1592N/A so when inflate() is called again, the same case is attempted again, and 1592N/A if the appropriate resources are provided, the machine proceeds to the 1592N/A next state. The NEEDBITS() macro is usually the way the state evaluates 1592N/A whether it can proceed or should return. NEEDBITS() does the return if 1592N/A the requested bits are not available. The typical use of the BITS macros 1592N/A ... do something with BITS(n) ... 1592N/A where NEEDBITS(n) either returns from inflate() if there isn't enough 1592N/A input left to load n bits into the accumulator, or it continues. BITS(n) 1592N/A gives the low n bits in the accumulator. When done, DROPBITS(n) drops 1592N/A the low n bits off the accumulator. INITBITS() clears the accumulator 1592N/A and sets the number of available bits to zero. BYTEBITS() discards just 1592N/A enough bits to put the accumulator on a byte boundary. After BYTEBITS() 1592N/A and a NEEDBITS(8), then BITS(8) would return the next byte in the stream. 1592N/A NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return 1592N/A if there is no input available. The decoding of variable length codes uses 1592N/A PULLBYTE() directly in order to pull just enough bytes to decode the next 1592N/A Some states loop until they get enough input, making sure that enough 1592N/A state information is maintained to continue the loop where it left off 1592N/A if NEEDBITS() returns in the loop. For example, want, need, and keep 1592N/A would all have to actually be part of the saved state in case NEEDBITS() 1592N/A As shown above, if the next state is also the next case, then the break 1592N/A A state may also return if there is not enough output space available to 1592N/A complete that state. Those states are copying stored data, writing a 1592N/A literal byte, and copying a matching string. 1592N/A When returning, a "goto inf_leave" is used to update the total counters, 1592N/A update the check value, and determine whether any progress has been made 1592N/A during that inflate() call in order to return the proper return code. 1592N/A Progress is defined as a change in either strm->avail_in or strm->avail_out. 1592N/A When there is a window, goto inf_leave will update the window with the last 1592N/A output written. If a goto inf_leave occurs in the middle of decompression 1592N/A and there is no window currently, goto inf_leave will create one and copy 1592N/A output to the window for the next call of inflate(). 1592N/A In this implementation, the flush parameter of inflate() only affects the 1592N/A return code (per zlib.h). inflate() always writes as much as possible to 1592N/A strm->next_out, given the space available and the provided input--the effect 1592N/A documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers 1592N/A the allocation of and copying into a sliding window until necessary, which 1592N/A provides the effect documented in zlib.h for Z_FINISH when the entire input 1592N/A stream available. So the only thing the flush parameter actually does is: 1592N/A when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it 1592N/A will return Z_BUF_ERROR if it has not reached the end of the stream. 1592N/A unsigned in,
out;
/* save starting available input and output */ 1592N/A unsigned copy;
/* number of stored or match bytes to copy */ 1592N/A unsigned len;
/* length to copy for repeats, bits to drop */ 1592N/A unsigned char hbuf[
4];
/* buffer for gzip header crc calculation */ 1592N/A static const unsigned short order[
19] =
/* permutation of code lengths */ 1592N/A {
16,
17,
18, 0,
8,
7,
9,
6,
10,
5,
11,
4,
12,
3,
13,
2,
14,
1,
15};
1592N/A case 2:
/* dynamic block */ 1592N/A /* handle error breaks in while */ 1592N/A "inflate: literal '%c'\n" :
1592N/A else {
/* copy from output */ 1592N/A Return from inflate(), updating the total counts and the check value. 1592N/A If there was no progress during the inflate() call, return a buffer 1592N/A error. Call updatewindow() to create and/or update the window state. 1592N/A Note: a memory error from inflate() is non-recoverable. 1592N/A /* check for correct dictionary id */ 1592N/A /* copy dictionary to window */ 1592N/A /* save header structure */ 1592N/A Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found 1592N/A or when out of input. When called, *have is the number of pattern bytes 1592N/A found in order so far, in 0..3. On return *have is updated to the new 1592N/A state. If on return *have equals four, then the pattern was found and the 1592N/A return value is how many bytes were read including the last byte of the 1592N/A pattern. If *have is less than four, then the pattern has not been found 1592N/A yet and the return value is len. In the latter case, syncsearch() can be 1592N/A called again with more data and the *have state. *have is initialized to 1592N/A unsigned len;
/* number of bytes to look at or looked at */ 5352N/A unsigned long in,
out;
/* temporary to save total_in and total_out */ 1592N/A unsigned char buf[
4];
/* to restore bit buffer to byte string */ 1592N/A /* if first time, start search in bit buffer */ 1592N/A /* search available input */ 1592N/A /* return no joy or set up to restart inflate() on a new block */ 1592N/A Returns true if inflate is currently at the end of a block generated by 1592N/A Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP 1592N/A implementation to provide an additional safety check. PPP uses 1592N/A Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored 1592N/A block. When decompressing, PPP checks that at the end of input packet, 1592N/A inflate is waiting for these length bytes.