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 Jean-loup Gailly. 1592N/A * For conditions of distribution and use, see copyright notice in zlib.h 1592N/A * The "deflation" process depends on being able to identify portions 1592N/A * of the input text which are identical to earlier input (within a 1592N/A * sliding window trailing behind the input currently being processed). 1592N/A * The most straightforward technique turns out to be the fastest for 1592N/A * most input files: try all possible matches and select the longest. 1592N/A * The key feature of this algorithm is that insertions into the string 1592N/A * dictionary are very simple and thus fast, and deletions are avoided 1592N/A * completely. Insertions are performed at each input character, whereas 1592N/A * string matches are performed only when the previous match ends. So it 1592N/A * is preferable to spend more time in matches to allow very fast string 1592N/A * insertions and avoid deletions. The matching algorithm for small 1592N/A * strings is inspired from that of Rabin & Karp. A brute force approach 1592N/A * is used to find longer strings when a small match has been found. 1592N/A * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 1592N/A * A previous version of this file used a more sophisticated algorithm 1592N/A * (by Fiala and Greene) which is guaranteed to run in linear amortized 1592N/A * time, but has a larger average cost, uses more memory and is patented. 1592N/A * However the F&G algorithm may be faster for some highly redundant 1592N/A * files if the parameter max_chain_length (described below) is too large. 1592N/A * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 1592N/A * I found it in 'freeze' written by Leonid Broukhis. 1592N/A * Thanks to many people for bug reports and testing. 1592N/A * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 1592N/A * A description of the Rabin and Karp algorithm is given in the book 1592N/A * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 1592N/A * Fiala,E.R., and Greene,D.H. 1592N/A * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 1592N/A " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";
1592N/A If you use the zlib library in a product, an acknowledgment is welcome 1592N/A in the documentation of your product. If for some reason you cannot 1592N/A include such an acknowledgment, I would appreciate that you keep this 1592N/A copyright string in the executable of your product. 1592N/A/* =========================================================================== 1592N/A/* Compression function. Returns the block state after the call. */ 1592N/A/* =========================================================================== 1592N/A/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 1592N/A/* Minimum amount of lookahead, except at the end of the input file. 1592N/A/* Values for max_lazy_match, good_match and max_chain_length, depending on 1592N/A * the desired pack level (0..9). The values given below have been tuned to 1592N/A * exclude worst case performance for pathological files. Better values may be 1592N/A * found for specific files. 1592N/A/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 1592N/A * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 1592N/A/* result of memcmp for equal strings */ 1592N/A/* =========================================================================== 1592N/A * Update a hash value with the given input byte 1592N/A * IN assertion: all calls to to UPDATE_HASH are made with consecutive 1592N/A * input characters, so that a running hash key can be computed from the 1592N/A * previous key instead of complete recalculation each time. 1592N/A/* =========================================================================== 1592N/A * Insert string str in the dictionary and set match_head to the previous head 1592N/A * of the hash chain (the most recent string with same hash key). Return 1592N/A * the previous length of the hash chain. 1592N/A * If this file is compiled with -DFASTEST, the compression level is forced 1592N/A * to 1, and no hash chains are maintained. 1592N/A * IN assertion: all calls to to INSERT_STRING are made with consecutive 1592N/A * input characters and the first MIN_MATCH bytes of str are valid 1592N/A * (except for the last MIN_MATCH-1 bytes of the input file). 1592N/A/* =========================================================================== 1592N/A * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 1592N/A * prev[] will be initialized on the fly. 1592N/A/* ========================================================================= */ 1592N/A /* To do: ignore strm->next_in if we use it as window */ 1592N/A/* ========================================================================= */ 1592N/A /* We overlay pending_buf and d_buf+l_buf. This works since the average 1592N/A * output size for (length,distance) codes is <= 24 bits. 1592N/A/* ========================================================================= */ 1592N/A /* Insert all strings in the hash table (except for the last two bytes). 1592N/A * s->lookahead stays null, so s->ins_h will be recomputed at the next 1592N/A/* ========================================================================= */ 1592N/A s->
wrap = -s->
wrap;
/* was made negative by deflate(..., Z_FINISH); */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A /* Flush the last buffer: */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= 1592N/A * For the default windowBits of 15 and memLevel of 8, this function returns 1592N/A * a close to exact, as well as small, upper bound on the compressed size. 1592N/A * They are coded as constants here for a reason--if the #define's are 1592N/A * changed, then this function needs to be changed as well. The return 1592N/A * value for 15 and 8 only works for those exact settings. 1592N/A * For any setting other than those defaults for windowBits and memLevel, 1592N/A * the value returned is a conservative worst case for the maximum expansion 1592N/A * resulting from using fixed blocks instead of stored blocks, which deflate 1592N/A * can emit on compressed data for some combinations of the parameters. 1592N/A * This function could be more sophisticated to provide closer upper bounds 1592N/A * for every combination of windowBits and memLevel, as well as wrap. 1592N/A * But even the conservative upper bound of about 14% expansion does not 1592N/A * seem onerous for output buffer allocation. 1592N/A /* conservative upper bound */ 1592N/A /* if can't get parameters, return conservative bound */ 1592N/A /* if not default parameters, return conservative bound */ 1592N/A /* default settings: return tight bound for that case */ 1592N/A/* ========================================================================= 1592N/A * Put a short in the pending buffer. The 16-bit value is put in MSB order. 1592N/A * IN assertion: the stream state is correct and there is enough room in 1592N/A/* ========================================================================= 1592N/A * Flush as much pending output as possible. All deflate() output goes 1592N/A * through this function so some applications may wish to modify it 1592N/A * to avoid allocating a large strm->next_out buffer and copying into it. 1592N/A/* ========================================================================= */ 1592N/A /* Save the adler32 of the preset dictionary: */ 1592N/A /* Flush as much pending output as possible */ 1592N/A /* Since avail_out is 0, deflate will be called again with 1592N/A * more output space, but possibly with both pending and 1592N/A * avail_in equal to zero. There won't be anything to do, 1592N/A * but this is not an error situation so make sure we 1592N/A * return OK instead of BUF_ERROR at next call of deflate: 1592N/A /* Make sure there is something to do and avoid duplicate consecutive 1592N/A * flushes. For repeated and useless calls with Z_FINISH, we keep 1592N/A * returning Z_STREAM_END instead of Z_BUF_ERROR. 1592N/A /* User must not provide more input after the first FINISH: */ 1592N/A /* Start a new block or continue the current one. 1592N/A /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 1592N/A * of deflate should use the same flush parameter to make sure 1592N/A * that the flush is complete. So we don't have to output an 1592N/A * empty block here, this will be done at next call. This also 1592N/A * ensures that for a very small output buffer, we emit at most 1592N/A }
else {
/* FULL_FLUSH or SYNC_FLUSH */ 1592N/A /* For a full flush, this empty block will be recognized 1592N/A * as a special marker by inflate_sync(). 1592N/A /* If avail_out is zero, the application will call deflate again 1592N/A/* ========================================================================= */ 1592N/A /* Deallocate in reverse order of allocations: */ 1592N/A/* ========================================================================= 1592N/A * Copy the source state to the destination state. 1592N/A * To simplify the source, this is not supported for 16-bit MSDOS (which 1592N/A * doesn't have enough memory anyway to duplicate compression states). 1592N/A /* following zmemcpy do not work for 16-bit MSDOS */ 1592N/A/* =========================================================================== 1592N/A * Read a new buffer from the current input stream, update the adler32 1592N/A * and total number of bytes read. All deflate() input goes through 1592N/A * this function so some applications may wish to modify it to avoid 1592N/A * allocating a large strm->next_in buffer and copying from it. 1592N/A * (See also flush_pending()). 1592N/A/* =========================================================================== 1592N/A * Initialize the "longest match" routines for a new zlib stream 1592N/A /* Set the default configuration parameters: 1592N/A/* =========================================================================== 1592N/A * Set match_start to the longest match starting at the given string and 1592N/A * return its length. Matches shorter or equal to prev_length are discarded, 1592N/A * in which case the result is equal to prev_length and match_start is 1592N/A * IN assertions: cur_match is the head of the hash chain for the current 1592N/A * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1592N/A * OUT assertion: the match length is not greater than s->lookahead. 1592N/A/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 1592N/A * match.S. The code will be functionally equivalent. 1592N/A register int len;
/* length of current match */ 1592N/A /* Stop when cur_match becomes <= limit. To simplify the code, 1592N/A * we prevent matches with the string of window index 0. 1592N/A /* Compare two bytes at a time. Note: this is not always beneficial. 1592N/A * Try with and without -DUNALIGNED_OK to check. 1592N/A /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1592N/A * It is easy to get rid of this optimization if necessary. 1592N/A /* Do not waste too much time if we already have a good match: */ 1592N/A /* Do not look for matches beyond the end of the input. This is necessary 1592N/A * to make deflate deterministic. 1592N/A /* Skip to next match if the match length cannot increase 1592N/A * or if the match length is less than 2. Note that the checks below 1592N/A * for insufficient lookahead only occur occasionally for performance 1592N/A * reasons. Therefore uninitialized memory will be accessed, and 1592N/A * conditional jumps will be made that depend on those values. 1592N/A * However the length of the match is limited to the lookahead, so 1592N/A * the output of deflate is not affected by the uninitialized values. 1592N/A /* This code assumes sizeof(unsigned short) == 2. Do not use 1592N/A * UNALIGNED_OK if your compiler uses a different size. 1592N/A /* It is not necessary to compare scan[2] and match[2] since they are 1592N/A * always equal when the other bytes match, given that the hash keys 1592N/A * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1592N/A * strstart+3, +5, ... up to strstart+257. We check for insufficient 1592N/A * lookahead only every 4th comparison; the 128th check will be made 1592N/A * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 1592N/A * necessary to put more guard bytes at the end of the window, or 1592N/A * to check more often for insufficient lookahead. 1592N/A /* The funny "do {}" generates better code on most compilers */ 1592N/A /* Here, scan <= window+strstart+257 */ 1592N/A /* The check at best_len-1 can be removed because it will be made 1592N/A * again later. (This heuristic is not always a win.) 1592N/A * It is not necessary to compare scan[2] and match[2] since they 1592N/A * are always equal when the other bytes match, given that 1592N/A * the hash keys are equal and that HASH_BITS >= 8. 1592N/A /* We check for insufficient lookahead only every 8th comparison; 1592N/A * the 256th check will be made at strstart+258. 1592N/A/* --------------------------------------------------------------------------- 1592N/A * Optimized version for level == 1 or strategy == Z_RLE only 1592N/A register int len;
/* length of current match */ 1592N/A /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1592N/A * It is easy to get rid of this optimization if necessary. 1592N/A /* Return failure if the match length is less than 2: 1592N/A /* The check at best_len-1 can be removed because it will be made 1592N/A * again later. (This heuristic is not always a win.) 1592N/A * It is not necessary to compare scan[2] and match[2] since they 1592N/A * are always equal when the other bytes match, given that 1592N/A * the hash keys are equal and that HASH_BITS >= 8. 1592N/A /* We check for insufficient lookahead only every 8th comparison; 1592N/A * the 256th check will be made at strstart+258. 1592N/A/* =========================================================================== 1592N/A * Check that the match at match_start is indeed a match. 1592N/A /* check that the match is indeed a match */ 1592N/A/* =========================================================================== 1592N/A * Fill the window when the lookahead becomes insufficient. 1592N/A * Updates strstart and lookahead. 1592N/A * IN assertion: lookahead < MIN_LOOKAHEAD 1592N/A * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 1592N/A * At least one byte has been read, or avail_in == 0; reads are 1592N/A * performed for at least two bytes (required for the zip translate_eol 1592N/A * option -- not supported here). 1592N/A unsigned more;
/* Amount of free space at the end of the window. */ 1592N/A /* Deal with !@#$% 64K limit: */ 1592N/A /* Very unlikely, but possible on 16 bit machine if 1592N/A * strstart == 0 && lookahead == 1 (input done a byte at time) 1592N/A /* If the window is almost full and there is insufficient lookahead, 1592N/A * move the upper half to the lower one to make room in the upper half. 1592N/A /* Slide the hash table (could be avoided with 32 bit values 1592N/A at the expense of memory usage). We slide even when level == 0 1592N/A to keep the hash table consistent if we switch back to level > 0 1592N/A later. (Using level 0 permanently is not an optimal usage of 1592N/A zlib, so we don't care about this pathological case.) 1592N/A /* %%% avoid this when Z_RLE */ 1592N/A /* If n is not on any hash chain, prev[n] is garbage but 1592N/A * its value will never be used. 1592N/A /* If there was no sliding: 1592N/A * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1592N/A * more == window_size - lookahead - strstart 1592N/A * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1592N/A * => more >= window_size - 2*WSIZE + 2 1592N/A * In the BIG_MEM or MMAP case (not yet supported), 1592N/A * window_size == input_size + MIN_LOOKAHEAD && 1592N/A * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1592N/A * Otherwise, window_size == 2*WSIZE so more >= 2. 1592N/A * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1592N/A /* Initialize the hash value now that we have some input: */ 1592N/A /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 1592N/A * but this is not important since only literal bytes will be emitted. 1592N/A/* =========================================================================== 1592N/A * Flush the current block, with given end-of-file flag. 1592N/A * IN assertion: strstart is set to the end of the current match. 1592N/A/* Same but force premature exit if necessary. */ 1592N/A/* =========================================================================== 1592N/A * Copy without compression as much as possible from the input stream, return 1592N/A * This function does not insert new strings in the dictionary since 1592N/A * uncompressible data is probably not useful. This function is used 1592N/A * only for the level=0 compression option. 1592N/A * NOTE: this function should be optimized to avoid extra copying from 1592N/A /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 1592N/A * to pending_buf_size, and each stored block has a 5 byte header: 1592N/A /* Copy as much as possible from input to output: */ 1592N/A /* Fill the window as much as possible: */ 1592N/A /* Emit a stored block if pending_buf will be full: */ 1592N/A /* strstart == 0 is possible when wraparound on 16-bit machine */ 1592N/A /* Flush if we may have to slide, otherwise block_start may become 1592N/A * negative and the data will be gone: 1592N/A/* =========================================================================== 1592N/A * Compress as much as possible from the input stream, return the current 1592N/A * This function does not perform lazy evaluation of matches and inserts 1592N/A * new strings in the dictionary only for unmatched strings or for short 1592N/A * matches. It is used only for the fast compression options. 1592N/A /* Make sure that we always have enough lookahead, except 1592N/A * at the end of the input file. We need MAX_MATCH bytes 1592N/A * for the next match, plus MIN_MATCH bytes to insert the 1592N/A * string following the next match. 1592N/A /* Insert the string window[strstart .. strstart+2] in the 1592N/A * dictionary, and set hash_head to the head of the hash chain: 1592N/A /* Find the longest match, discarding those <= prev_length. 1592N/A * At this point we have always match_length < MIN_MATCH 1592N/A /* To simplify the code, we prevent matches with the string 1592N/A * of window index 0 (in particular we have to avoid a match 1592N/A * of the string with itself at the start of the input file). 1592N/A /* longest_match() or longest_match_fast() sets match_start */ 1592N/A /* Insert new strings in the hash table only if the match length 1592N/A * is not too large. This saves time but degrades compression. 1592N/A /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1592N/A * always MIN_MATCH bytes ahead. 1592N/A /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1592N/A * matter since it will be recomputed at next deflate call. 1592N/A /* No match, output a literal byte */ 1592N/A/* =========================================================================== 1592N/A * Same as above, but achieves better compression. We use a lazy 1592N/A * evaluation for matches: a match is finally adopted only if there is 1592N/A * no better match at the next window position. 1592N/A /* Process the input block. */ 1592N/A /* Make sure that we always have enough lookahead, except 1592N/A * at the end of the input file. We need MAX_MATCH bytes 1592N/A * for the next match, plus MIN_MATCH bytes to insert the 1592N/A * string following the next match. 1592N/A /* Insert the string window[strstart .. strstart+2] in the 1592N/A * dictionary, and set hash_head to the head of the hash chain: 1592N/A /* Find the longest match, discarding those <= prev_length. 1592N/A /* To simplify the code, we prevent matches with the string 1592N/A * of window index 0 (in particular we have to avoid a match 1592N/A * of the string with itself at the start of the input file). 1592N/A /* longest_match() or longest_match_fast() sets match_start */ 1592N/A /* If prev_match is also MIN_MATCH, match_start is garbage 1592N/A * but we will ignore the current match anyway. 1592N/A /* If there was a match at the previous step and the current 1592N/A * match is not better, output the previous match: 1592N/A /* Do not insert strings in hash table beyond this. */ 1592N/A /* Insert in hash table all strings up to the end of the match. 1592N/A * strstart-1 and strstart are already inserted. If there is not 1592N/A * enough lookahead, the last two strings are not inserted in 1592N/A /* If there was no match at the previous position, output a 1592N/A * single literal. If there was a match but the current match 1592N/A * is longer, truncate the previous match to a single literal. 1592N/A /* There is no previous match to compare with, wait for 1592N/A/* =========================================================================== 1592N/A * For Z_RLE, simply look for runs of bytes, generate matches only of distance 1592N/A * one. Do not maintain a hash table. (It will be regenerated if this run of 1592N/A * deflate switches away from Z_RLE.) 1592N/A /* Make sure that we always have enough lookahead, except 1592N/A * at the end of the input file. We need MAX_MATCH bytes 1592N/A * for the longest encodable run. 1592N/A /* See how many times the previous byte repeats */ 1592N/A /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 1592N/A /* No match, output a literal byte */