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