1c9083b85SXin LI /* deflate.c -- compress data using the deflation algorithm 2cd882207SXin LI * Copyright (C) 1995-2022 Jean-loup Gailly and Mark Adler 3c9083b85SXin LI * For conditions of distribution and use, see copyright notice in zlib.h 4c9083b85SXin LI */ 5c9083b85SXin LI 6c9083b85SXin LI /* 7c9083b85SXin LI * ALGORITHM 8c9083b85SXin LI * 9c9083b85SXin LI * The "deflation" process depends on being able to identify portions 10c9083b85SXin LI * of the input text which are identical to earlier input (within a 11c9083b85SXin LI * sliding window trailing behind the input currently being processed). 12c9083b85SXin LI * 13c9083b85SXin LI * The most straightforward technique turns out to be the fastest for 14c9083b85SXin LI * most input files: try all possible matches and select the longest. 15c9083b85SXin LI * The key feature of this algorithm is that insertions into the string 16c9083b85SXin LI * dictionary are very simple and thus fast, and deletions are avoided 17c9083b85SXin LI * completely. Insertions are performed at each input character, whereas 18c9083b85SXin LI * string matches are performed only when the previous match ends. So it 19c9083b85SXin LI * is preferable to spend more time in matches to allow very fast string 20c9083b85SXin LI * insertions and avoid deletions. The matching algorithm for small 21c9083b85SXin LI * strings is inspired from that of Rabin & Karp. A brute force approach 22c9083b85SXin LI * is used to find longer strings when a small match has been found. 23c9083b85SXin LI * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 24c9083b85SXin LI * (by Leonid Broukhis). 25c9083b85SXin LI * A previous version of this file used a more sophisticated algorithm 26c9083b85SXin LI * (by Fiala and Greene) which is guaranteed to run in linear amortized 27c9083b85SXin LI * time, but has a larger average cost, uses more memory and is patented. 28c9083b85SXin LI * However the F&G algorithm may be faster for some highly redundant 29c9083b85SXin LI * files if the parameter max_chain_length (described below) is too large. 30c9083b85SXin LI * 31c9083b85SXin LI * ACKNOWLEDGEMENTS 32c9083b85SXin LI * 33c9083b85SXin LI * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 34c9083b85SXin LI * I found it in 'freeze' written by Leonid Broukhis. 35c9083b85SXin LI * Thanks to many people for bug reports and testing. 36c9083b85SXin LI * 37c9083b85SXin LI * REFERENCES 38c9083b85SXin LI * 39c9083b85SXin LI * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 40c9083b85SXin LI * Available in http://tools.ietf.org/html/rfc1951 41c9083b85SXin LI * 42c9083b85SXin LI * A description of the Rabin and Karp algorithm is given in the book 43c9083b85SXin LI * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 44c9083b85SXin LI * 45c9083b85SXin LI * Fiala,E.R., and Greene,D.H. 46c9083b85SXin LI * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 47c9083b85SXin LI * 48c9083b85SXin LI */ 49c9083b85SXin LI 50c9083b85SXin LI /* @(#) $Id$ */ 51c9083b85SXin LI 52c9083b85SXin LI #include "deflate.h" 53c9083b85SXin LI 54c9083b85SXin LI const char deflate_copyright[] = 55cd882207SXin LI " deflate 1.2.12 Copyright 1995-2022 Jean-loup Gailly and Mark Adler "; 56c9083b85SXin LI /* 57c9083b85SXin LI If you use the zlib library in a product, an acknowledgment is welcome 58c9083b85SXin LI in the documentation of your product. If for some reason you cannot 59c9083b85SXin LI include such an acknowledgment, I would appreciate that you keep this 60c9083b85SXin LI copyright string in the executable of your product. 61c9083b85SXin LI */ 62c9083b85SXin LI 63c9083b85SXin LI /* =========================================================================== 64c9083b85SXin LI * Function prototypes. 65c9083b85SXin LI */ 66c9083b85SXin LI typedef enum { 67c9083b85SXin LI need_more, /* block not completed, need more input or more output */ 68c9083b85SXin LI block_done, /* block flush performed */ 69c9083b85SXin LI finish_started, /* finish started, need only more output at next deflate */ 70c9083b85SXin LI finish_done /* finish done, accept no more input or output */ 71c9083b85SXin LI } block_state; 72c9083b85SXin LI 73c9083b85SXin LI typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 74c9083b85SXin LI /* Compression function. Returns the block state after the call. */ 75c9083b85SXin LI 76c9083b85SXin LI local int deflateStateCheck OF((z_streamp strm)); 77c9083b85SXin LI local void slide_hash OF((deflate_state *s)); 78c9083b85SXin LI local void fill_window OF((deflate_state *s)); 79c9083b85SXin LI local block_state deflate_stored OF((deflate_state *s, int flush)); 80c9083b85SXin LI local block_state deflate_fast OF((deflate_state *s, int flush)); 81c9083b85SXin LI #ifndef FASTEST 82c9083b85SXin LI local block_state deflate_slow OF((deflate_state *s, int flush)); 83c9083b85SXin LI #endif 84c9083b85SXin LI local block_state deflate_rle OF((deflate_state *s, int flush)); 85c9083b85SXin LI local block_state deflate_huff OF((deflate_state *s, int flush)); 86c9083b85SXin LI local void lm_init OF((deflate_state *s)); 87c9083b85SXin LI local void putShortMSB OF((deflate_state *s, uInt b)); 88c9083b85SXin LI local void flush_pending OF((z_streamp strm)); 89c9083b85SXin LI local unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 90c9083b85SXin LI #ifdef ASMV 91c9083b85SXin LI # pragma message("Assembler code may have bugs -- use at your own risk") 92c9083b85SXin LI void match_init OF((void)); /* asm code initialization */ 93c9083b85SXin LI uInt longest_match OF((deflate_state *s, IPos cur_match)); 94c9083b85SXin LI #else 95c9083b85SXin LI local uInt longest_match OF((deflate_state *s, IPos cur_match)); 96c9083b85SXin LI #endif 97c9083b85SXin LI 98c9083b85SXin LI #ifdef ZLIB_DEBUG 99c9083b85SXin LI local void check_match OF((deflate_state *s, IPos start, IPos match, 100c9083b85SXin LI int length)); 101c9083b85SXin LI #endif 102c9083b85SXin LI 103c9083b85SXin LI /* =========================================================================== 104c9083b85SXin LI * Local data 105c9083b85SXin LI */ 106c9083b85SXin LI 107c9083b85SXin LI #define NIL 0 108c9083b85SXin LI /* Tail of hash chains */ 109c9083b85SXin LI 110c9083b85SXin LI #ifndef TOO_FAR 111c9083b85SXin LI # define TOO_FAR 4096 112c9083b85SXin LI #endif 113c9083b85SXin LI /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 114c9083b85SXin LI 115c9083b85SXin LI /* Values for max_lazy_match, good_match and max_chain_length, depending on 116c9083b85SXin LI * the desired pack level (0..9). The values given below have been tuned to 117c9083b85SXin LI * exclude worst case performance for pathological files. Better values may be 118c9083b85SXin LI * found for specific files. 119c9083b85SXin LI */ 120c9083b85SXin LI typedef struct config_s { 121c9083b85SXin LI ush good_length; /* reduce lazy search above this match length */ 122c9083b85SXin LI ush max_lazy; /* do not perform lazy search above this match length */ 123c9083b85SXin LI ush nice_length; /* quit search above this match length */ 124c9083b85SXin LI ush max_chain; 125c9083b85SXin LI compress_func func; 126c9083b85SXin LI } config; 127c9083b85SXin LI 128c9083b85SXin LI #ifdef FASTEST 129c9083b85SXin LI local const config configuration_table[2] = { 130c9083b85SXin LI /* good lazy nice chain */ 131c9083b85SXin LI /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 132c9083b85SXin LI /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 133c9083b85SXin LI #else 134c9083b85SXin LI local const config configuration_table[10] = { 135c9083b85SXin LI /* good lazy nice chain */ 136c9083b85SXin LI /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 137c9083b85SXin LI /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 138c9083b85SXin LI /* 2 */ {4, 5, 16, 8, deflate_fast}, 139c9083b85SXin LI /* 3 */ {4, 6, 32, 32, deflate_fast}, 140c9083b85SXin LI 141c9083b85SXin LI /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 142c9083b85SXin LI /* 5 */ {8, 16, 32, 32, deflate_slow}, 143c9083b85SXin LI /* 6 */ {8, 16, 128, 128, deflate_slow}, 144c9083b85SXin LI /* 7 */ {8, 32, 128, 256, deflate_slow}, 145c9083b85SXin LI /* 8 */ {32, 128, 258, 1024, deflate_slow}, 146c9083b85SXin LI /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 147c9083b85SXin LI #endif 148c9083b85SXin LI 149c9083b85SXin LI /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 150c9083b85SXin LI * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 151c9083b85SXin LI * meaning. 152c9083b85SXin LI */ 153c9083b85SXin LI 154c9083b85SXin LI /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ 155c9083b85SXin LI #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0)) 156c9083b85SXin LI 157c9083b85SXin LI /* =========================================================================== 158c9083b85SXin LI * Update a hash value with the given input byte 159c9083b85SXin LI * IN assertion: all calls to UPDATE_HASH are made with consecutive input 160c9083b85SXin LI * characters, so that a running hash key can be computed from the previous 161c9083b85SXin LI * key instead of complete recalculation each time. 162c9083b85SXin LI */ 163c9083b85SXin LI #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 164c9083b85SXin LI 165c9083b85SXin LI 166c9083b85SXin LI /* =========================================================================== 167c9083b85SXin LI * Insert string str in the dictionary and set match_head to the previous head 168c9083b85SXin LI * of the hash chain (the most recent string with same hash key). Return 169c9083b85SXin LI * the previous length of the hash chain. 170c9083b85SXin LI * If this file is compiled with -DFASTEST, the compression level is forced 171c9083b85SXin LI * to 1, and no hash chains are maintained. 172c9083b85SXin LI * IN assertion: all calls to INSERT_STRING are made with consecutive input 173c9083b85SXin LI * characters and the first MIN_MATCH bytes of str are valid (except for 174c9083b85SXin LI * the last MIN_MATCH-1 bytes of the input file). 175c9083b85SXin LI */ 176c9083b85SXin LI #ifdef FASTEST 177c9083b85SXin LI #define INSERT_STRING(s, str, match_head) \ 178c9083b85SXin LI (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 179c9083b85SXin LI match_head = s->head[s->ins_h], \ 180c9083b85SXin LI s->head[s->ins_h] = (Pos)(str)) 181c9083b85SXin LI #else 182c9083b85SXin LI #define INSERT_STRING(s, str, match_head) \ 183c9083b85SXin LI (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 184c9083b85SXin LI match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 185c9083b85SXin LI s->head[s->ins_h] = (Pos)(str)) 186c9083b85SXin LI #endif 187c9083b85SXin LI 188c9083b85SXin LI /* =========================================================================== 189c9083b85SXin LI * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 190c9083b85SXin LI * prev[] will be initialized on the fly. 191c9083b85SXin LI */ 192110f2297SXin LI #define CLEAR_HASH(s) \ 193110f2297SXin LI do { \ 194c9083b85SXin LI s->head[s->hash_size-1] = NIL; \ 195110f2297SXin LI zmemzero((Bytef *)s->head, \ 196110f2297SXin LI (unsigned)(s->hash_size-1)*sizeof(*s->head)); \ 1970ed1d6fbSXin LI } while (0) 198c9083b85SXin LI 199c9083b85SXin LI /* =========================================================================== 200c9083b85SXin LI * Slide the hash table when sliding the window down (could be avoided with 32 201c9083b85SXin LI * bit values at the expense of memory usage). We slide even when level == 0 to 202c9083b85SXin LI * keep the hash table consistent if we switch back to level > 0 later. 203c9083b85SXin LI */ 204c9083b85SXin LI local void slide_hash(s) 205c9083b85SXin LI deflate_state *s; 206c9083b85SXin LI { 207c9083b85SXin LI unsigned n, m; 208c9083b85SXin LI Posf *p; 209c9083b85SXin LI uInt wsize = s->w_size; 210c9083b85SXin LI 211c9083b85SXin LI n = s->hash_size; 212c9083b85SXin LI p = &s->head[n]; 213c9083b85SXin LI do { 214c9083b85SXin LI m = *--p; 215c9083b85SXin LI *p = (Pos)(m >= wsize ? m - wsize : NIL); 216c9083b85SXin LI } while (--n); 217c9083b85SXin LI n = wsize; 218c9083b85SXin LI #ifndef FASTEST 219c9083b85SXin LI p = &s->prev[n]; 220c9083b85SXin LI do { 221c9083b85SXin LI m = *--p; 222c9083b85SXin LI *p = (Pos)(m >= wsize ? m - wsize : NIL); 223c9083b85SXin LI /* If n is not on any hash chain, prev[n] is garbage but 224c9083b85SXin LI * its value will never be used. 225c9083b85SXin LI */ 226c9083b85SXin LI } while (--n); 227c9083b85SXin LI #endif 228c9083b85SXin LI } 229c9083b85SXin LI 230c9083b85SXin LI /* ========================================================================= */ 231c9083b85SXin LI int ZEXPORT deflateInit_(strm, level, version, stream_size) 232c9083b85SXin LI z_streamp strm; 233c9083b85SXin LI int level; 234c9083b85SXin LI const char *version; 235c9083b85SXin LI int stream_size; 236c9083b85SXin LI { 237c9083b85SXin LI return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 238c9083b85SXin LI Z_DEFAULT_STRATEGY, version, stream_size); 239c9083b85SXin LI /* To do: ignore strm->next_in if we use it as window */ 240c9083b85SXin LI } 241c9083b85SXin LI 242c9083b85SXin LI /* ========================================================================= */ 243c9083b85SXin LI int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 244c9083b85SXin LI version, stream_size) 245c9083b85SXin LI z_streamp strm; 246c9083b85SXin LI int level; 247c9083b85SXin LI int method; 248c9083b85SXin LI int windowBits; 249c9083b85SXin LI int memLevel; 250c9083b85SXin LI int strategy; 251c9083b85SXin LI const char *version; 252c9083b85SXin LI int stream_size; 253c9083b85SXin LI { 254c9083b85SXin LI deflate_state *s; 255c9083b85SXin LI int wrap = 1; 256c9083b85SXin LI static const char my_version[] = ZLIB_VERSION; 257c9083b85SXin LI 258c9083b85SXin LI if (version == Z_NULL || version[0] != my_version[0] || 259c9083b85SXin LI stream_size != sizeof(z_stream)) { 260c9083b85SXin LI return Z_VERSION_ERROR; 261c9083b85SXin LI } 262c9083b85SXin LI if (strm == Z_NULL) return Z_STREAM_ERROR; 263c9083b85SXin LI 264c9083b85SXin LI strm->msg = Z_NULL; 265c9083b85SXin LI if (strm->zalloc == (alloc_func)0) { 266a15cb219SXin LI #if defined(Z_SOLO) && !defined(_KERNEL) 267c9083b85SXin LI return Z_STREAM_ERROR; 268c9083b85SXin LI #else 269c9083b85SXin LI strm->zalloc = zcalloc; 270c9083b85SXin LI strm->opaque = (voidpf)0; 271c9083b85SXin LI #endif 272c9083b85SXin LI } 273c9083b85SXin LI if (strm->zfree == (free_func)0) 274a15cb219SXin LI #if defined(Z_SOLO) && !defined(_KERNEL) 275c9083b85SXin LI return Z_STREAM_ERROR; 276c9083b85SXin LI #else 277c9083b85SXin LI strm->zfree = zcfree; 278c9083b85SXin LI #endif 279c9083b85SXin LI 280c9083b85SXin LI #ifdef FASTEST 281c9083b85SXin LI if (level != 0) level = 1; 282c9083b85SXin LI #else 283c9083b85SXin LI if (level == Z_DEFAULT_COMPRESSION) level = 6; 284c9083b85SXin LI #endif 285c9083b85SXin LI 286c9083b85SXin LI if (windowBits < 0) { /* suppress zlib wrapper */ 287c9083b85SXin LI wrap = 0; 288c9083b85SXin LI windowBits = -windowBits; 289c9083b85SXin LI } 290c9083b85SXin LI #ifdef GZIP 291c9083b85SXin LI else if (windowBits > 15) { 292c9083b85SXin LI wrap = 2; /* write gzip wrapper instead */ 293c9083b85SXin LI windowBits -= 16; 294c9083b85SXin LI } 295c9083b85SXin LI #endif 296c9083b85SXin LI if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 297c9083b85SXin LI windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 298c9083b85SXin LI strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) { 299c9083b85SXin LI return Z_STREAM_ERROR; 300c9083b85SXin LI } 301c9083b85SXin LI if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 302c9083b85SXin LI s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 303c9083b85SXin LI if (s == Z_NULL) return Z_MEM_ERROR; 304c9083b85SXin LI strm->state = (struct internal_state FAR *)s; 305c9083b85SXin LI s->strm = strm; 306c9083b85SXin LI s->status = INIT_STATE; /* to pass state test in deflateReset() */ 307c9083b85SXin LI 308c9083b85SXin LI s->wrap = wrap; 309c9083b85SXin LI s->gzhead = Z_NULL; 310c9083b85SXin LI s->w_bits = (uInt)windowBits; 311c9083b85SXin LI s->w_size = 1 << s->w_bits; 312c9083b85SXin LI s->w_mask = s->w_size - 1; 313c9083b85SXin LI 314c9083b85SXin LI s->hash_bits = (uInt)memLevel + 7; 315c9083b85SXin LI s->hash_size = 1 << s->hash_bits; 316c9083b85SXin LI s->hash_mask = s->hash_size - 1; 317c9083b85SXin LI s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 318c9083b85SXin LI 319c9083b85SXin LI s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 320c9083b85SXin LI s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 321c9083b85SXin LI s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 322c9083b85SXin LI 323c9083b85SXin LI s->high_water = 0; /* nothing written to s->window yet */ 324c9083b85SXin LI 325c9083b85SXin LI s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 326c9083b85SXin LI 327cd882207SXin LI /* We overlay pending_buf and sym_buf. This works since the average size 328cd882207SXin LI * for length/distance pairs over any compressed block is assured to be 31 329cd882207SXin LI * bits or less. 330cd882207SXin LI * 331cd882207SXin LI * Analysis: The longest fixed codes are a length code of 8 bits plus 5 332cd882207SXin LI * extra bits, for lengths 131 to 257. The longest fixed distance codes are 333cd882207SXin LI * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest 334cd882207SXin LI * possible fixed-codes length/distance pair is then 31 bits total. 335cd882207SXin LI * 336cd882207SXin LI * sym_buf starts one-fourth of the way into pending_buf. So there are 337cd882207SXin LI * three bytes in sym_buf for every four bytes in pending_buf. Each symbol 338cd882207SXin LI * in sym_buf is three bytes -- two for the distance and one for the 339cd882207SXin LI * literal/length. As each symbol is consumed, the pointer to the next 340cd882207SXin LI * sym_buf value to read moves forward three bytes. From that symbol, up to 341cd882207SXin LI * 31 bits are written to pending_buf. The closest the written pending_buf 342cd882207SXin LI * bits gets to the next sym_buf symbol to read is just before the last 343cd882207SXin LI * code is written. At that time, 31*(n-2) bits have been written, just 344cd882207SXin LI * after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at 345cd882207SXin LI * 8*n bits into pending_buf. (Note that the symbol buffer fills when n-1 346cd882207SXin LI * symbols are written.) The closest the writing gets to what is unread is 347cd882207SXin LI * then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and 348cd882207SXin LI * can range from 128 to 32768. 349cd882207SXin LI * 350cd882207SXin LI * Therefore, at a minimum, there are 142 bits of space between what is 351cd882207SXin LI * written and what is read in the overlain buffers, so the symbols cannot 352cd882207SXin LI * be overwritten by the compressed data. That space is actually 139 bits, 353cd882207SXin LI * due to the three-bit fixed-code block header. 354cd882207SXin LI * 355cd882207SXin LI * That covers the case where either Z_FIXED is specified, forcing fixed 356cd882207SXin LI * codes, or when the use of fixed codes is chosen, because that choice 357cd882207SXin LI * results in a smaller compressed block than dynamic codes. That latter 358cd882207SXin LI * condition then assures that the above analysis also covers all dynamic 359cd882207SXin LI * blocks. A dynamic-code block will only be chosen to be emitted if it has 360cd882207SXin LI * fewer bits than a fixed-code block would for the same set of symbols. 361cd882207SXin LI * Therefore its average symbol length is assured to be less than 31. So 362cd882207SXin LI * the compressed data for a dynamic block also cannot overwrite the 363cd882207SXin LI * symbols from which it is being constructed. 364cd882207SXin LI */ 365cd882207SXin LI 366cd882207SXin LI s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4); 367cd882207SXin LI s->pending_buf_size = (ulg)s->lit_bufsize * 4; 368c9083b85SXin LI 369c9083b85SXin LI if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 370c9083b85SXin LI s->pending_buf == Z_NULL) { 371c9083b85SXin LI s->status = FINISH_STATE; 372c9083b85SXin LI strm->msg = ERR_MSG(Z_MEM_ERROR); 373c9083b85SXin LI deflateEnd (strm); 374c9083b85SXin LI return Z_MEM_ERROR; 375c9083b85SXin LI } 376cd882207SXin LI s->sym_buf = s->pending_buf + s->lit_bufsize; 377cd882207SXin LI s->sym_end = (s->lit_bufsize - 1) * 3; 378cd882207SXin LI /* We avoid equality with lit_bufsize*3 because of wraparound at 64K 379cd882207SXin LI * on 16 bit machines and because stored blocks are restricted to 380cd882207SXin LI * 64K-1 bytes. 381cd882207SXin LI */ 382c9083b85SXin LI 383c9083b85SXin LI s->level = level; 384c9083b85SXin LI s->strategy = strategy; 385c9083b85SXin LI s->method = (Byte)method; 386c9083b85SXin LI 387c9083b85SXin LI return deflateReset(strm); 388c9083b85SXin LI } 389c9083b85SXin LI 390c9083b85SXin LI /* ========================================================================= 391c9083b85SXin LI * Check for a valid deflate stream state. Return 0 if ok, 1 if not. 392c9083b85SXin LI */ 393c9083b85SXin LI local int deflateStateCheck (strm) 394c9083b85SXin LI z_streamp strm; 395c9083b85SXin LI { 396c9083b85SXin LI deflate_state *s; 397c9083b85SXin LI if (strm == Z_NULL || 398c9083b85SXin LI strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) 399c9083b85SXin LI return 1; 400c9083b85SXin LI s = strm->state; 401c9083b85SXin LI if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE && 402c9083b85SXin LI #ifdef GZIP 403c9083b85SXin LI s->status != GZIP_STATE && 404c9083b85SXin LI #endif 405c9083b85SXin LI s->status != EXTRA_STATE && 406c9083b85SXin LI s->status != NAME_STATE && 407c9083b85SXin LI s->status != COMMENT_STATE && 408c9083b85SXin LI s->status != HCRC_STATE && 409c9083b85SXin LI s->status != BUSY_STATE && 410c9083b85SXin LI s->status != FINISH_STATE)) 411c9083b85SXin LI return 1; 412c9083b85SXin LI return 0; 413c9083b85SXin LI } 414c9083b85SXin LI 415c9083b85SXin LI /* ========================================================================= */ 416c9083b85SXin LI int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 417c9083b85SXin LI z_streamp strm; 418c9083b85SXin LI const Bytef *dictionary; 419c9083b85SXin LI uInt dictLength; 420c9083b85SXin LI { 421c9083b85SXin LI deflate_state *s; 422c9083b85SXin LI uInt str, n; 423c9083b85SXin LI int wrap; 424c9083b85SXin LI unsigned avail; 425c9083b85SXin LI z_const unsigned char *next; 426c9083b85SXin LI 427c9083b85SXin LI if (deflateStateCheck(strm) || dictionary == Z_NULL) 428c9083b85SXin LI return Z_STREAM_ERROR; 429c9083b85SXin LI s = strm->state; 430c9083b85SXin LI wrap = s->wrap; 431c9083b85SXin LI if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) 432c9083b85SXin LI return Z_STREAM_ERROR; 433c9083b85SXin LI 434c9083b85SXin LI /* when using zlib wrappers, compute Adler-32 for provided dictionary */ 435c9083b85SXin LI if (wrap == 1) 436c9083b85SXin LI strm->adler = adler32(strm->adler, dictionary, dictLength); 437c9083b85SXin LI s->wrap = 0; /* avoid computing Adler-32 in read_buf */ 438c9083b85SXin LI 439c9083b85SXin LI /* if dictionary would fill window, just replace the history */ 440c9083b85SXin LI if (dictLength >= s->w_size) { 441c9083b85SXin LI if (wrap == 0) { /* already empty otherwise */ 442c9083b85SXin LI CLEAR_HASH(s); 443c9083b85SXin LI s->strstart = 0; 444c9083b85SXin LI s->block_start = 0L; 445c9083b85SXin LI s->insert = 0; 446c9083b85SXin LI } 447c9083b85SXin LI dictionary += dictLength - s->w_size; /* use the tail */ 448c9083b85SXin LI dictLength = s->w_size; 449c9083b85SXin LI } 450c9083b85SXin LI 451c9083b85SXin LI /* insert dictionary into window and hash */ 452c9083b85SXin LI avail = strm->avail_in; 453c9083b85SXin LI next = strm->next_in; 454c9083b85SXin LI strm->avail_in = dictLength; 455c9083b85SXin LI strm->next_in = (z_const Bytef *)dictionary; 456c9083b85SXin LI fill_window(s); 457c9083b85SXin LI while (s->lookahead >= MIN_MATCH) { 458c9083b85SXin LI str = s->strstart; 459c9083b85SXin LI n = s->lookahead - (MIN_MATCH-1); 460c9083b85SXin LI do { 461c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 462c9083b85SXin LI #ifndef FASTEST 463c9083b85SXin LI s->prev[str & s->w_mask] = s->head[s->ins_h]; 464c9083b85SXin LI #endif 465c9083b85SXin LI s->head[s->ins_h] = (Pos)str; 466c9083b85SXin LI str++; 467c9083b85SXin LI } while (--n); 468c9083b85SXin LI s->strstart = str; 469c9083b85SXin LI s->lookahead = MIN_MATCH-1; 470c9083b85SXin LI fill_window(s); 471c9083b85SXin LI } 472c9083b85SXin LI s->strstart += s->lookahead; 473c9083b85SXin LI s->block_start = (long)s->strstart; 474c9083b85SXin LI s->insert = s->lookahead; 475c9083b85SXin LI s->lookahead = 0; 476c9083b85SXin LI s->match_length = s->prev_length = MIN_MATCH-1; 477c9083b85SXin LI s->match_available = 0; 478c9083b85SXin LI strm->next_in = next; 479c9083b85SXin LI strm->avail_in = avail; 480c9083b85SXin LI s->wrap = wrap; 481c9083b85SXin LI return Z_OK; 482c9083b85SXin LI } 483c9083b85SXin LI 484c9083b85SXin LI /* ========================================================================= */ 485c9083b85SXin LI int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength) 486c9083b85SXin LI z_streamp strm; 487c9083b85SXin LI Bytef *dictionary; 488c9083b85SXin LI uInt *dictLength; 489c9083b85SXin LI { 490c9083b85SXin LI deflate_state *s; 491c9083b85SXin LI uInt len; 492c9083b85SXin LI 493c9083b85SXin LI if (deflateStateCheck(strm)) 494c9083b85SXin LI return Z_STREAM_ERROR; 495c9083b85SXin LI s = strm->state; 496c9083b85SXin LI len = s->strstart + s->lookahead; 497c9083b85SXin LI if (len > s->w_size) 498c9083b85SXin LI len = s->w_size; 499c9083b85SXin LI if (dictionary != Z_NULL && len) 500c9083b85SXin LI zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len); 501c9083b85SXin LI if (dictLength != Z_NULL) 502c9083b85SXin LI *dictLength = len; 503c9083b85SXin LI return Z_OK; 504c9083b85SXin LI } 505c9083b85SXin LI 506c9083b85SXin LI /* ========================================================================= */ 507c9083b85SXin LI int ZEXPORT deflateResetKeep (strm) 508c9083b85SXin LI z_streamp strm; 509c9083b85SXin LI { 510c9083b85SXin LI deflate_state *s; 511c9083b85SXin LI 512c9083b85SXin LI if (deflateStateCheck(strm)) { 513c9083b85SXin LI return Z_STREAM_ERROR; 514c9083b85SXin LI } 515c9083b85SXin LI 516c9083b85SXin LI strm->total_in = strm->total_out = 0; 517c9083b85SXin LI strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 518c9083b85SXin LI strm->data_type = Z_UNKNOWN; 519c9083b85SXin LI 520c9083b85SXin LI s = (deflate_state *)strm->state; 521c9083b85SXin LI s->pending = 0; 522c9083b85SXin LI s->pending_out = s->pending_buf; 523c9083b85SXin LI 524c9083b85SXin LI if (s->wrap < 0) { 525c9083b85SXin LI s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 526c9083b85SXin LI } 527c9083b85SXin LI s->status = 528c9083b85SXin LI #ifdef GZIP 529c9083b85SXin LI s->wrap == 2 ? GZIP_STATE : 530c9083b85SXin LI #endif 531cd882207SXin LI INIT_STATE; 532c9083b85SXin LI strm->adler = 533c9083b85SXin LI #ifdef GZIP 534c9083b85SXin LI s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 535c9083b85SXin LI #endif 536c9083b85SXin LI adler32(0L, Z_NULL, 0); 537c9083b85SXin LI s->last_flush = -2; 538c9083b85SXin LI 539c9083b85SXin LI _tr_init(s); 540c9083b85SXin LI 541c9083b85SXin LI return Z_OK; 542c9083b85SXin LI } 543c9083b85SXin LI 544c9083b85SXin LI /* ========================================================================= */ 545c9083b85SXin LI int ZEXPORT deflateReset (strm) 546c9083b85SXin LI z_streamp strm; 547c9083b85SXin LI { 548c9083b85SXin LI int ret; 549c9083b85SXin LI 550c9083b85SXin LI ret = deflateResetKeep(strm); 551c9083b85SXin LI if (ret == Z_OK) 552c9083b85SXin LI lm_init(strm->state); 553c9083b85SXin LI return ret; 554c9083b85SXin LI } 555c9083b85SXin LI 556c9083b85SXin LI /* ========================================================================= */ 557c9083b85SXin LI int ZEXPORT deflateSetHeader (strm, head) 558c9083b85SXin LI z_streamp strm; 559c9083b85SXin LI gz_headerp head; 560c9083b85SXin LI { 561c9083b85SXin LI if (deflateStateCheck(strm) || strm->state->wrap != 2) 562c9083b85SXin LI return Z_STREAM_ERROR; 563c9083b85SXin LI strm->state->gzhead = head; 564c9083b85SXin LI return Z_OK; 565c9083b85SXin LI } 566c9083b85SXin LI 567c9083b85SXin LI /* ========================================================================= */ 568c9083b85SXin LI int ZEXPORT deflatePending (strm, pending, bits) 569c9083b85SXin LI unsigned *pending; 570c9083b85SXin LI int *bits; 571c9083b85SXin LI z_streamp strm; 572c9083b85SXin LI { 573c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 574c9083b85SXin LI if (pending != Z_NULL) 575c9083b85SXin LI *pending = strm->state->pending; 576c9083b85SXin LI if (bits != Z_NULL) 577c9083b85SXin LI *bits = strm->state->bi_valid; 578c9083b85SXin LI return Z_OK; 579c9083b85SXin LI } 580c9083b85SXin LI 581c9083b85SXin LI /* ========================================================================= */ 582c9083b85SXin LI int ZEXPORT deflatePrime (strm, bits, value) 583c9083b85SXin LI z_streamp strm; 584c9083b85SXin LI int bits; 585c9083b85SXin LI int value; 586c9083b85SXin LI { 587c9083b85SXin LI deflate_state *s; 588c9083b85SXin LI int put; 589c9083b85SXin LI 590c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 591c9083b85SXin LI s = strm->state; 592cd882207SXin LI if (bits < 0 || bits > 16 || 593cd882207SXin LI s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3)) 594c9083b85SXin LI return Z_BUF_ERROR; 595c9083b85SXin LI do { 596c9083b85SXin LI put = Buf_size - s->bi_valid; 597c9083b85SXin LI if (put > bits) 598c9083b85SXin LI put = bits; 599c9083b85SXin LI s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); 600c9083b85SXin LI s->bi_valid += put; 601c9083b85SXin LI _tr_flush_bits(s); 602c9083b85SXin LI value >>= put; 603c9083b85SXin LI bits -= put; 604c9083b85SXin LI } while (bits); 605c9083b85SXin LI return Z_OK; 606c9083b85SXin LI } 607c9083b85SXin LI 608c9083b85SXin LI /* ========================================================================= */ 609c9083b85SXin LI int ZEXPORT deflateParams(strm, level, strategy) 610c9083b85SXin LI z_streamp strm; 611c9083b85SXin LI int level; 612c9083b85SXin LI int strategy; 613c9083b85SXin LI { 614c9083b85SXin LI deflate_state *s; 615c9083b85SXin LI compress_func func; 616c9083b85SXin LI 617c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 618c9083b85SXin LI s = strm->state; 619c9083b85SXin LI 620c9083b85SXin LI #ifdef FASTEST 621c9083b85SXin LI if (level != 0) level = 1; 622c9083b85SXin LI #else 623c9083b85SXin LI if (level == Z_DEFAULT_COMPRESSION) level = 6; 624c9083b85SXin LI #endif 625c9083b85SXin LI if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 626c9083b85SXin LI return Z_STREAM_ERROR; 627c9083b85SXin LI } 628c9083b85SXin LI func = configuration_table[s->level].func; 629c9083b85SXin LI 630c9083b85SXin LI if ((strategy != s->strategy || func != configuration_table[level].func) && 631c9083b85SXin LI s->last_flush != -2) { 632c9083b85SXin LI /* Flush the last buffer: */ 633c9083b85SXin LI int err = deflate(strm, Z_BLOCK); 634c9083b85SXin LI if (err == Z_STREAM_ERROR) 635c9083b85SXin LI return err; 636c9083b85SXin LI if (strm->avail_in || (s->strstart - s->block_start) + s->lookahead) 637c9083b85SXin LI return Z_BUF_ERROR; 638c9083b85SXin LI } 639c9083b85SXin LI if (s->level != level) { 640c9083b85SXin LI if (s->level == 0 && s->matches != 0) { 641c9083b85SXin LI if (s->matches == 1) 642c9083b85SXin LI slide_hash(s); 643c9083b85SXin LI else 644c9083b85SXin LI CLEAR_HASH(s); 645c9083b85SXin LI s->matches = 0; 646c9083b85SXin LI } 647c9083b85SXin LI s->level = level; 648c9083b85SXin LI s->max_lazy_match = configuration_table[level].max_lazy; 649c9083b85SXin LI s->good_match = configuration_table[level].good_length; 650c9083b85SXin LI s->nice_match = configuration_table[level].nice_length; 651c9083b85SXin LI s->max_chain_length = configuration_table[level].max_chain; 652c9083b85SXin LI } 653c9083b85SXin LI s->strategy = strategy; 654c9083b85SXin LI return Z_OK; 655c9083b85SXin LI } 656c9083b85SXin LI 657c9083b85SXin LI /* ========================================================================= */ 658c9083b85SXin LI int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 659c9083b85SXin LI z_streamp strm; 660c9083b85SXin LI int good_length; 661c9083b85SXin LI int max_lazy; 662c9083b85SXin LI int nice_length; 663c9083b85SXin LI int max_chain; 664c9083b85SXin LI { 665c9083b85SXin LI deflate_state *s; 666c9083b85SXin LI 667c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 668c9083b85SXin LI s = strm->state; 669c9083b85SXin LI s->good_match = (uInt)good_length; 670c9083b85SXin LI s->max_lazy_match = (uInt)max_lazy; 671c9083b85SXin LI s->nice_match = nice_length; 672c9083b85SXin LI s->max_chain_length = (uInt)max_chain; 673c9083b85SXin LI return Z_OK; 674c9083b85SXin LI } 675c9083b85SXin LI 676c9083b85SXin LI /* ========================================================================= 677c9083b85SXin LI * For the default windowBits of 15 and memLevel of 8, this function returns 678c9083b85SXin LI * a close to exact, as well as small, upper bound on the compressed size. 679c9083b85SXin LI * They are coded as constants here for a reason--if the #define's are 680c9083b85SXin LI * changed, then this function needs to be changed as well. The return 681c9083b85SXin LI * value for 15 and 8 only works for those exact settings. 682c9083b85SXin LI * 683c9083b85SXin LI * For any setting other than those defaults for windowBits and memLevel, 684c9083b85SXin LI * the value returned is a conservative worst case for the maximum expansion 685c9083b85SXin LI * resulting from using fixed blocks instead of stored blocks, which deflate 686c9083b85SXin LI * can emit on compressed data for some combinations of the parameters. 687c9083b85SXin LI * 688c9083b85SXin LI * This function could be more sophisticated to provide closer upper bounds for 689c9083b85SXin LI * every combination of windowBits and memLevel. But even the conservative 690c9083b85SXin LI * upper bound of about 14% expansion does not seem onerous for output buffer 691c9083b85SXin LI * allocation. 692c9083b85SXin LI */ 693c9083b85SXin LI uLong ZEXPORT deflateBound(strm, sourceLen) 694c9083b85SXin LI z_streamp strm; 695c9083b85SXin LI uLong sourceLen; 696c9083b85SXin LI { 697c9083b85SXin LI deflate_state *s; 698c9083b85SXin LI uLong complen, wraplen; 699c9083b85SXin LI 700c9083b85SXin LI /* conservative upper bound for compressed data */ 701c9083b85SXin LI complen = sourceLen + 702c9083b85SXin LI ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; 703c9083b85SXin LI 704c9083b85SXin LI /* if can't get parameters, return conservative bound plus zlib wrapper */ 705c9083b85SXin LI if (deflateStateCheck(strm)) 706c9083b85SXin LI return complen + 6; 707c9083b85SXin LI 708c9083b85SXin LI /* compute wrapper length */ 709c9083b85SXin LI s = strm->state; 710c9083b85SXin LI switch (s->wrap) { 711c9083b85SXin LI case 0: /* raw deflate */ 712c9083b85SXin LI wraplen = 0; 713c9083b85SXin LI break; 714c9083b85SXin LI case 1: /* zlib wrapper */ 715c9083b85SXin LI wraplen = 6 + (s->strstart ? 4 : 0); 716c9083b85SXin LI break; 717c9083b85SXin LI #ifdef GZIP 718c9083b85SXin LI case 2: /* gzip wrapper */ 719c9083b85SXin LI wraplen = 18; 720c9083b85SXin LI if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 721c9083b85SXin LI Bytef *str; 722c9083b85SXin LI if (s->gzhead->extra != Z_NULL) 723c9083b85SXin LI wraplen += 2 + s->gzhead->extra_len; 724c9083b85SXin LI str = s->gzhead->name; 725c9083b85SXin LI if (str != Z_NULL) 726c9083b85SXin LI do { 727c9083b85SXin LI wraplen++; 728c9083b85SXin LI } while (*str++); 729c9083b85SXin LI str = s->gzhead->comment; 730c9083b85SXin LI if (str != Z_NULL) 731c9083b85SXin LI do { 732c9083b85SXin LI wraplen++; 733c9083b85SXin LI } while (*str++); 734c9083b85SXin LI if (s->gzhead->hcrc) 735c9083b85SXin LI wraplen += 2; 736c9083b85SXin LI } 737c9083b85SXin LI break; 738c9083b85SXin LI #endif 739c9083b85SXin LI default: /* for compiler happiness */ 740c9083b85SXin LI wraplen = 6; 741c9083b85SXin LI } 742c9083b85SXin LI 743c9083b85SXin LI /* if not default parameters, return conservative bound */ 744c9083b85SXin LI if (s->w_bits != 15 || s->hash_bits != 8 + 7) 745c9083b85SXin LI return complen + wraplen; 746c9083b85SXin LI 747c9083b85SXin LI /* default settings: return tight bound for that case */ 748c9083b85SXin LI return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 749c9083b85SXin LI (sourceLen >> 25) + 13 - 6 + wraplen; 750c9083b85SXin LI } 751c9083b85SXin LI 752c9083b85SXin LI /* ========================================================================= 753c9083b85SXin LI * Put a short in the pending buffer. The 16-bit value is put in MSB order. 754c9083b85SXin LI * IN assertion: the stream state is correct and there is enough room in 755c9083b85SXin LI * pending_buf. 756c9083b85SXin LI */ 757c9083b85SXin LI local void putShortMSB (s, b) 758c9083b85SXin LI deflate_state *s; 759c9083b85SXin LI uInt b; 760c9083b85SXin LI { 761c9083b85SXin LI put_byte(s, (Byte)(b >> 8)); 762c9083b85SXin LI put_byte(s, (Byte)(b & 0xff)); 763c9083b85SXin LI } 764c9083b85SXin LI 765c9083b85SXin LI /* ========================================================================= 766c9083b85SXin LI * Flush as much pending output as possible. All deflate() output, except for 767c9083b85SXin LI * some deflate_stored() output, goes through this function so some 768c9083b85SXin LI * applications may wish to modify it to avoid allocating a large 769c9083b85SXin LI * strm->next_out buffer and copying into it. (See also read_buf()). 770c9083b85SXin LI */ 771c9083b85SXin LI local void flush_pending(strm) 772c9083b85SXin LI z_streamp strm; 773c9083b85SXin LI { 774c9083b85SXin LI unsigned len; 775c9083b85SXin LI deflate_state *s = strm->state; 776c9083b85SXin LI 777c9083b85SXin LI _tr_flush_bits(s); 778c9083b85SXin LI len = s->pending; 779c9083b85SXin LI if (len > strm->avail_out) len = strm->avail_out; 780c9083b85SXin LI if (len == 0) return; 781c9083b85SXin LI 782c9083b85SXin LI zmemcpy(strm->next_out, s->pending_out, len); 783c9083b85SXin LI strm->next_out += len; 784c9083b85SXin LI s->pending_out += len; 785c9083b85SXin LI strm->total_out += len; 786c9083b85SXin LI strm->avail_out -= len; 787c9083b85SXin LI s->pending -= len; 788c9083b85SXin LI if (s->pending == 0) { 789c9083b85SXin LI s->pending_out = s->pending_buf; 790c9083b85SXin LI } 791c9083b85SXin LI } 792c9083b85SXin LI 793c9083b85SXin LI /* =========================================================================== 794c9083b85SXin LI * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1]. 795c9083b85SXin LI */ 796c9083b85SXin LI #define HCRC_UPDATE(beg) \ 797c9083b85SXin LI do { \ 798c9083b85SXin LI if (s->gzhead->hcrc && s->pending > (beg)) \ 799c9083b85SXin LI strm->adler = crc32(strm->adler, s->pending_buf + (beg), \ 800c9083b85SXin LI s->pending - (beg)); \ 801c9083b85SXin LI } while (0) 802c9083b85SXin LI 803c9083b85SXin LI /* ========================================================================= */ 804c9083b85SXin LI int ZEXPORT deflate (strm, flush) 805c9083b85SXin LI z_streamp strm; 806c9083b85SXin LI int flush; 807c9083b85SXin LI { 808c9083b85SXin LI int old_flush; /* value of flush param for previous deflate call */ 809c9083b85SXin LI deflate_state *s; 810c9083b85SXin LI 811c9083b85SXin LI if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) { 812c9083b85SXin LI return Z_STREAM_ERROR; 813c9083b85SXin LI } 814c9083b85SXin LI s = strm->state; 815c9083b85SXin LI 816c9083b85SXin LI if (strm->next_out == Z_NULL || 817c9083b85SXin LI (strm->avail_in != 0 && strm->next_in == Z_NULL) || 818c9083b85SXin LI (s->status == FINISH_STATE && flush != Z_FINISH)) { 819c9083b85SXin LI ERR_RETURN(strm, Z_STREAM_ERROR); 820c9083b85SXin LI } 821c9083b85SXin LI if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 822c9083b85SXin LI 823c9083b85SXin LI old_flush = s->last_flush; 824c9083b85SXin LI s->last_flush = flush; 825c9083b85SXin LI 826c9083b85SXin LI /* Flush as much pending output as possible */ 827c9083b85SXin LI if (s->pending != 0) { 828c9083b85SXin LI flush_pending(strm); 829c9083b85SXin LI if (strm->avail_out == 0) { 830c9083b85SXin LI /* Since avail_out is 0, deflate will be called again with 831c9083b85SXin LI * more output space, but possibly with both pending and 832c9083b85SXin LI * avail_in equal to zero. There won't be anything to do, 833c9083b85SXin LI * but this is not an error situation so make sure we 834c9083b85SXin LI * return OK instead of BUF_ERROR at next call of deflate: 835c9083b85SXin LI */ 836c9083b85SXin LI s->last_flush = -1; 837c9083b85SXin LI return Z_OK; 838c9083b85SXin LI } 839c9083b85SXin LI 840c9083b85SXin LI /* Make sure there is something to do and avoid duplicate consecutive 841c9083b85SXin LI * flushes. For repeated and useless calls with Z_FINISH, we keep 842c9083b85SXin LI * returning Z_STREAM_END instead of Z_BUF_ERROR. 843c9083b85SXin LI */ 844c9083b85SXin LI } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 845c9083b85SXin LI flush != Z_FINISH) { 846c9083b85SXin LI ERR_RETURN(strm, Z_BUF_ERROR); 847c9083b85SXin LI } 848c9083b85SXin LI 849c9083b85SXin LI /* User must not provide more input after the first FINISH: */ 850c9083b85SXin LI if (s->status == FINISH_STATE && strm->avail_in != 0) { 851c9083b85SXin LI ERR_RETURN(strm, Z_BUF_ERROR); 852c9083b85SXin LI } 853c9083b85SXin LI 854c9083b85SXin LI /* Write the header */ 855cd882207SXin LI if (s->status == INIT_STATE && s->wrap == 0) 856cd882207SXin LI s->status = BUSY_STATE; 857c9083b85SXin LI if (s->status == INIT_STATE) { 858c9083b85SXin LI /* zlib header */ 859c9083b85SXin LI uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 860c9083b85SXin LI uInt level_flags; 861c9083b85SXin LI 862c9083b85SXin LI if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 863c9083b85SXin LI level_flags = 0; 864c9083b85SXin LI else if (s->level < 6) 865c9083b85SXin LI level_flags = 1; 866c9083b85SXin LI else if (s->level == 6) 867c9083b85SXin LI level_flags = 2; 868c9083b85SXin LI else 869c9083b85SXin LI level_flags = 3; 870c9083b85SXin LI header |= (level_flags << 6); 871c9083b85SXin LI if (s->strstart != 0) header |= PRESET_DICT; 872c9083b85SXin LI header += 31 - (header % 31); 873c9083b85SXin LI 874c9083b85SXin LI putShortMSB(s, header); 875c9083b85SXin LI 876c9083b85SXin LI /* Save the adler32 of the preset dictionary: */ 877c9083b85SXin LI if (s->strstart != 0) { 878c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler >> 16)); 879c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler & 0xffff)); 880c9083b85SXin LI } 881c9083b85SXin LI strm->adler = adler32(0L, Z_NULL, 0); 882c9083b85SXin LI s->status = BUSY_STATE; 883c9083b85SXin LI 884c9083b85SXin LI /* Compression must start with an empty pending buffer */ 885c9083b85SXin LI flush_pending(strm); 886c9083b85SXin LI if (s->pending != 0) { 887c9083b85SXin LI s->last_flush = -1; 888c9083b85SXin LI return Z_OK; 889c9083b85SXin LI } 890c9083b85SXin LI } 891c9083b85SXin LI #ifdef GZIP 892c9083b85SXin LI if (s->status == GZIP_STATE) { 893c9083b85SXin LI /* gzip header */ 894c9083b85SXin LI strm->adler = crc32(0L, Z_NULL, 0); 895c9083b85SXin LI put_byte(s, 31); 896c9083b85SXin LI put_byte(s, 139); 897c9083b85SXin LI put_byte(s, 8); 898c9083b85SXin LI if (s->gzhead == Z_NULL) { 899c9083b85SXin LI put_byte(s, 0); 900c9083b85SXin LI put_byte(s, 0); 901c9083b85SXin LI put_byte(s, 0); 902c9083b85SXin LI put_byte(s, 0); 903c9083b85SXin LI put_byte(s, 0); 904c9083b85SXin LI put_byte(s, s->level == 9 ? 2 : 905c9083b85SXin LI (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 906c9083b85SXin LI 4 : 0)); 907c9083b85SXin LI put_byte(s, OS_CODE); 908c9083b85SXin LI s->status = BUSY_STATE; 909c9083b85SXin LI 910c9083b85SXin LI /* Compression must start with an empty pending buffer */ 911c9083b85SXin LI flush_pending(strm); 912c9083b85SXin LI if (s->pending != 0) { 913c9083b85SXin LI s->last_flush = -1; 914c9083b85SXin LI return Z_OK; 915c9083b85SXin LI } 916c9083b85SXin LI } 917c9083b85SXin LI else { 918c9083b85SXin LI put_byte(s, (s->gzhead->text ? 1 : 0) + 919c9083b85SXin LI (s->gzhead->hcrc ? 2 : 0) + 920c9083b85SXin LI (s->gzhead->extra == Z_NULL ? 0 : 4) + 921c9083b85SXin LI (s->gzhead->name == Z_NULL ? 0 : 8) + 922c9083b85SXin LI (s->gzhead->comment == Z_NULL ? 0 : 16) 923c9083b85SXin LI ); 924c9083b85SXin LI put_byte(s, (Byte)(s->gzhead->time & 0xff)); 925c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 926c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 927c9083b85SXin LI put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 928c9083b85SXin LI put_byte(s, s->level == 9 ? 2 : 929c9083b85SXin LI (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 930c9083b85SXin LI 4 : 0)); 931c9083b85SXin LI put_byte(s, s->gzhead->os & 0xff); 932c9083b85SXin LI if (s->gzhead->extra != Z_NULL) { 933c9083b85SXin LI put_byte(s, s->gzhead->extra_len & 0xff); 934c9083b85SXin LI put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 935c9083b85SXin LI } 936c9083b85SXin LI if (s->gzhead->hcrc) 937c9083b85SXin LI strm->adler = crc32(strm->adler, s->pending_buf, 938c9083b85SXin LI s->pending); 939c9083b85SXin LI s->gzindex = 0; 940c9083b85SXin LI s->status = EXTRA_STATE; 941c9083b85SXin LI } 942c9083b85SXin LI } 943c9083b85SXin LI if (s->status == EXTRA_STATE) { 944c9083b85SXin LI if (s->gzhead->extra != Z_NULL) { 945c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 946c9083b85SXin LI uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex; 947c9083b85SXin LI while (s->pending + left > s->pending_buf_size) { 948c9083b85SXin LI uInt copy = s->pending_buf_size - s->pending; 949c9083b85SXin LI zmemcpy(s->pending_buf + s->pending, 950c9083b85SXin LI s->gzhead->extra + s->gzindex, copy); 951c9083b85SXin LI s->pending = s->pending_buf_size; 952c9083b85SXin LI HCRC_UPDATE(beg); 953c9083b85SXin LI s->gzindex += copy; 954c9083b85SXin LI flush_pending(strm); 955c9083b85SXin LI if (s->pending != 0) { 956c9083b85SXin LI s->last_flush = -1; 957c9083b85SXin LI return Z_OK; 958c9083b85SXin LI } 959c9083b85SXin LI beg = 0; 960c9083b85SXin LI left -= copy; 961c9083b85SXin LI } 962c9083b85SXin LI zmemcpy(s->pending_buf + s->pending, 963c9083b85SXin LI s->gzhead->extra + s->gzindex, left); 964c9083b85SXin LI s->pending += left; 965c9083b85SXin LI HCRC_UPDATE(beg); 966c9083b85SXin LI s->gzindex = 0; 967c9083b85SXin LI } 968c9083b85SXin LI s->status = NAME_STATE; 969c9083b85SXin LI } 970c9083b85SXin LI if (s->status == NAME_STATE) { 971c9083b85SXin LI if (s->gzhead->name != Z_NULL) { 972c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 973c9083b85SXin LI int val; 974c9083b85SXin LI do { 975c9083b85SXin LI if (s->pending == s->pending_buf_size) { 976c9083b85SXin LI HCRC_UPDATE(beg); 977c9083b85SXin LI flush_pending(strm); 978c9083b85SXin LI if (s->pending != 0) { 979c9083b85SXin LI s->last_flush = -1; 980c9083b85SXin LI return Z_OK; 981c9083b85SXin LI } 982c9083b85SXin LI beg = 0; 983c9083b85SXin LI } 984c9083b85SXin LI val = s->gzhead->name[s->gzindex++]; 985c9083b85SXin LI put_byte(s, val); 986c9083b85SXin LI } while (val != 0); 987c9083b85SXin LI HCRC_UPDATE(beg); 988c9083b85SXin LI s->gzindex = 0; 989c9083b85SXin LI } 990c9083b85SXin LI s->status = COMMENT_STATE; 991c9083b85SXin LI } 992c9083b85SXin LI if (s->status == COMMENT_STATE) { 993c9083b85SXin LI if (s->gzhead->comment != Z_NULL) { 994c9083b85SXin LI ulg beg = s->pending; /* start of bytes to update crc */ 995c9083b85SXin LI int val; 996c9083b85SXin LI do { 997c9083b85SXin LI if (s->pending == s->pending_buf_size) { 998c9083b85SXin LI HCRC_UPDATE(beg); 999c9083b85SXin LI flush_pending(strm); 1000c9083b85SXin LI if (s->pending != 0) { 1001c9083b85SXin LI s->last_flush = -1; 1002c9083b85SXin LI return Z_OK; 1003c9083b85SXin LI } 1004c9083b85SXin LI beg = 0; 1005c9083b85SXin LI } 1006c9083b85SXin LI val = s->gzhead->comment[s->gzindex++]; 1007c9083b85SXin LI put_byte(s, val); 1008c9083b85SXin LI } while (val != 0); 1009c9083b85SXin LI HCRC_UPDATE(beg); 1010c9083b85SXin LI } 1011c9083b85SXin LI s->status = HCRC_STATE; 1012c9083b85SXin LI } 1013c9083b85SXin LI if (s->status == HCRC_STATE) { 1014c9083b85SXin LI if (s->gzhead->hcrc) { 1015c9083b85SXin LI if (s->pending + 2 > s->pending_buf_size) { 1016c9083b85SXin LI flush_pending(strm); 1017c9083b85SXin LI if (s->pending != 0) { 1018c9083b85SXin LI s->last_flush = -1; 1019c9083b85SXin LI return Z_OK; 1020c9083b85SXin LI } 1021c9083b85SXin LI } 1022c9083b85SXin LI put_byte(s, (Byte)(strm->adler & 0xff)); 1023c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 1024c9083b85SXin LI strm->adler = crc32(0L, Z_NULL, 0); 1025c9083b85SXin LI } 1026c9083b85SXin LI s->status = BUSY_STATE; 1027c9083b85SXin LI 1028c9083b85SXin LI /* Compression must start with an empty pending buffer */ 1029c9083b85SXin LI flush_pending(strm); 1030c9083b85SXin LI if (s->pending != 0) { 1031c9083b85SXin LI s->last_flush = -1; 1032c9083b85SXin LI return Z_OK; 1033c9083b85SXin LI } 1034c9083b85SXin LI } 1035c9083b85SXin LI #endif 1036c9083b85SXin LI 1037c9083b85SXin LI /* Start a new block or continue the current one. 1038c9083b85SXin LI */ 1039c9083b85SXin LI if (strm->avail_in != 0 || s->lookahead != 0 || 1040c9083b85SXin LI (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 1041c9083b85SXin LI block_state bstate; 1042c9083b85SXin LI 1043c9083b85SXin LI bstate = s->level == 0 ? deflate_stored(s, flush) : 1044c9083b85SXin LI s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 1045c9083b85SXin LI s->strategy == Z_RLE ? deflate_rle(s, flush) : 1046c9083b85SXin LI (*(configuration_table[s->level].func))(s, flush); 1047c9083b85SXin LI 1048c9083b85SXin LI if (bstate == finish_started || bstate == finish_done) { 1049c9083b85SXin LI s->status = FINISH_STATE; 1050c9083b85SXin LI } 1051c9083b85SXin LI if (bstate == need_more || bstate == finish_started) { 1052c9083b85SXin LI if (strm->avail_out == 0) { 1053c9083b85SXin LI s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 1054c9083b85SXin LI } 1055c9083b85SXin LI return Z_OK; 1056c9083b85SXin LI /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 1057c9083b85SXin LI * of deflate should use the same flush parameter to make sure 1058c9083b85SXin LI * that the flush is complete. So we don't have to output an 1059c9083b85SXin LI * empty block here, this will be done at next call. This also 1060c9083b85SXin LI * ensures that for a very small output buffer, we emit at most 1061c9083b85SXin LI * one empty block. 1062c9083b85SXin LI */ 1063c9083b85SXin LI } 1064c9083b85SXin LI if (bstate == block_done) { 1065c9083b85SXin LI if (flush == Z_PARTIAL_FLUSH) { 1066c9083b85SXin LI _tr_align(s); 1067c9083b85SXin LI } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 1068c9083b85SXin LI _tr_stored_block(s, (char*)0, 0L, 0); 1069c9083b85SXin LI /* For a full flush, this empty block will be recognized 1070c9083b85SXin LI * as a special marker by inflate_sync(). 1071c9083b85SXin LI */ 1072c9083b85SXin LI if (flush == Z_FULL_FLUSH) { 1073c9083b85SXin LI CLEAR_HASH(s); /* forget history */ 1074c9083b85SXin LI if (s->lookahead == 0) { 1075c9083b85SXin LI s->strstart = 0; 1076c9083b85SXin LI s->block_start = 0L; 1077c9083b85SXin LI s->insert = 0; 1078c9083b85SXin LI } 1079c9083b85SXin LI } 1080c9083b85SXin LI } 1081c9083b85SXin LI flush_pending(strm); 1082c9083b85SXin LI if (strm->avail_out == 0) { 1083c9083b85SXin LI s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 1084c9083b85SXin LI return Z_OK; 1085c9083b85SXin LI } 1086c9083b85SXin LI } 1087c9083b85SXin LI } 1088c9083b85SXin LI 1089c9083b85SXin LI if (flush != Z_FINISH) return Z_OK; 1090c9083b85SXin LI if (s->wrap <= 0) return Z_STREAM_END; 1091c9083b85SXin LI 1092c9083b85SXin LI /* Write the trailer */ 1093c9083b85SXin LI #ifdef GZIP 1094c9083b85SXin LI if (s->wrap == 2) { 1095c9083b85SXin LI put_byte(s, (Byte)(strm->adler & 0xff)); 1096c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 1097c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 1098c9083b85SXin LI put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 1099c9083b85SXin LI put_byte(s, (Byte)(strm->total_in & 0xff)); 1100c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 1101c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 1102c9083b85SXin LI put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 1103c9083b85SXin LI } 1104c9083b85SXin LI else 1105c9083b85SXin LI #endif 1106c9083b85SXin LI { 1107c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler >> 16)); 1108c9083b85SXin LI putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1109c9083b85SXin LI } 1110c9083b85SXin LI flush_pending(strm); 1111c9083b85SXin LI /* If avail_out is zero, the application will call deflate again 1112c9083b85SXin LI * to flush the rest. 1113c9083b85SXin LI */ 1114c9083b85SXin LI if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 1115c9083b85SXin LI return s->pending != 0 ? Z_OK : Z_STREAM_END; 1116c9083b85SXin LI } 1117c9083b85SXin LI 1118c9083b85SXin LI /* ========================================================================= */ 1119c9083b85SXin LI int ZEXPORT deflateEnd (strm) 1120c9083b85SXin LI z_streamp strm; 1121c9083b85SXin LI { 1122c9083b85SXin LI int status; 1123c9083b85SXin LI 1124c9083b85SXin LI if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 1125c9083b85SXin LI 1126c9083b85SXin LI status = strm->state->status; 1127c9083b85SXin LI 1128c9083b85SXin LI /* Deallocate in reverse order of allocations: */ 1129c9083b85SXin LI TRY_FREE(strm, strm->state->pending_buf); 1130c9083b85SXin LI TRY_FREE(strm, strm->state->head); 1131c9083b85SXin LI TRY_FREE(strm, strm->state->prev); 1132c9083b85SXin LI TRY_FREE(strm, strm->state->window); 1133c9083b85SXin LI 1134c9083b85SXin LI ZFREE(strm, strm->state); 1135c9083b85SXin LI strm->state = Z_NULL; 1136c9083b85SXin LI 1137c9083b85SXin LI return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 1138c9083b85SXin LI } 1139c9083b85SXin LI 1140c9083b85SXin LI /* ========================================================================= 1141c9083b85SXin LI * Copy the source state to the destination state. 1142c9083b85SXin LI * To simplify the source, this is not supported for 16-bit MSDOS (which 1143c9083b85SXin LI * doesn't have enough memory anyway to duplicate compression states). 1144c9083b85SXin LI */ 1145c9083b85SXin LI int ZEXPORT deflateCopy (dest, source) 1146c9083b85SXin LI z_streamp dest; 1147c9083b85SXin LI z_streamp source; 1148c9083b85SXin LI { 1149c9083b85SXin LI #ifdef MAXSEG_64K 1150c9083b85SXin LI return Z_STREAM_ERROR; 1151c9083b85SXin LI #else 1152c9083b85SXin LI deflate_state *ds; 1153c9083b85SXin LI deflate_state *ss; 1154c9083b85SXin LI 1155c9083b85SXin LI 1156c9083b85SXin LI if (deflateStateCheck(source) || dest == Z_NULL) { 1157c9083b85SXin LI return Z_STREAM_ERROR; 1158c9083b85SXin LI } 1159c9083b85SXin LI 1160c9083b85SXin LI ss = source->state; 1161c9083b85SXin LI 1162c9083b85SXin LI zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 1163c9083b85SXin LI 1164c9083b85SXin LI ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 1165c9083b85SXin LI if (ds == Z_NULL) return Z_MEM_ERROR; 1166c9083b85SXin LI dest->state = (struct internal_state FAR *) ds; 1167c9083b85SXin LI zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 1168c9083b85SXin LI ds->strm = dest; 1169c9083b85SXin LI 1170c9083b85SXin LI ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 1171c9083b85SXin LI ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 1172c9083b85SXin LI ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 1173cd882207SXin LI ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4); 1174c9083b85SXin LI 1175c9083b85SXin LI if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 1176c9083b85SXin LI ds->pending_buf == Z_NULL) { 1177c9083b85SXin LI deflateEnd (dest); 1178c9083b85SXin LI return Z_MEM_ERROR; 1179c9083b85SXin LI } 1180c9083b85SXin LI /* following zmemcpy do not work for 16-bit MSDOS */ 1181c9083b85SXin LI zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 1182c9083b85SXin LI zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 1183c9083b85SXin LI zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 1184c9083b85SXin LI zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 1185c9083b85SXin LI 1186c9083b85SXin LI ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 1187cd882207SXin LI ds->sym_buf = ds->pending_buf + ds->lit_bufsize; 1188c9083b85SXin LI 1189c9083b85SXin LI ds->l_desc.dyn_tree = ds->dyn_ltree; 1190c9083b85SXin LI ds->d_desc.dyn_tree = ds->dyn_dtree; 1191c9083b85SXin LI ds->bl_desc.dyn_tree = ds->bl_tree; 1192c9083b85SXin LI 1193c9083b85SXin LI return Z_OK; 1194c9083b85SXin LI #endif /* MAXSEG_64K */ 1195c9083b85SXin LI } 1196c9083b85SXin LI 1197c9083b85SXin LI /* =========================================================================== 1198c9083b85SXin LI * Read a new buffer from the current input stream, update the adler32 1199c9083b85SXin LI * and total number of bytes read. All deflate() input goes through 1200c9083b85SXin LI * this function so some applications may wish to modify it to avoid 1201c9083b85SXin LI * allocating a large strm->next_in buffer and copying from it. 1202c9083b85SXin LI * (See also flush_pending()). 1203c9083b85SXin LI */ 1204c9083b85SXin LI local unsigned read_buf(strm, buf, size) 1205c9083b85SXin LI z_streamp strm; 1206c9083b85SXin LI Bytef *buf; 1207c9083b85SXin LI unsigned size; 1208c9083b85SXin LI { 1209c9083b85SXin LI unsigned len = strm->avail_in; 1210c9083b85SXin LI 1211c9083b85SXin LI if (len > size) len = size; 1212c9083b85SXin LI if (len == 0) return 0; 1213c9083b85SXin LI 1214c9083b85SXin LI strm->avail_in -= len; 1215c9083b85SXin LI 1216c9083b85SXin LI zmemcpy(buf, strm->next_in, len); 1217c9083b85SXin LI if (strm->state->wrap == 1) { 1218c9083b85SXin LI strm->adler = adler32(strm->adler, buf, len); 1219c9083b85SXin LI } 1220c9083b85SXin LI #ifdef GZIP 1221c9083b85SXin LI else if (strm->state->wrap == 2) { 1222c9083b85SXin LI strm->adler = crc32(strm->adler, buf, len); 1223c9083b85SXin LI } 1224c9083b85SXin LI #endif 1225c9083b85SXin LI strm->next_in += len; 1226c9083b85SXin LI strm->total_in += len; 1227c9083b85SXin LI 1228c9083b85SXin LI return len; 1229c9083b85SXin LI } 1230c9083b85SXin LI 1231c9083b85SXin LI /* =========================================================================== 1232c9083b85SXin LI * Initialize the "longest match" routines for a new zlib stream 1233c9083b85SXin LI */ 1234c9083b85SXin LI local void lm_init (s) 1235c9083b85SXin LI deflate_state *s; 1236c9083b85SXin LI { 1237c9083b85SXin LI s->window_size = (ulg)2L*s->w_size; 1238c9083b85SXin LI 1239c9083b85SXin LI CLEAR_HASH(s); 1240c9083b85SXin LI 1241c9083b85SXin LI /* Set the default configuration parameters: 1242c9083b85SXin LI */ 1243c9083b85SXin LI s->max_lazy_match = configuration_table[s->level].max_lazy; 1244c9083b85SXin LI s->good_match = configuration_table[s->level].good_length; 1245c9083b85SXin LI s->nice_match = configuration_table[s->level].nice_length; 1246c9083b85SXin LI s->max_chain_length = configuration_table[s->level].max_chain; 1247c9083b85SXin LI 1248c9083b85SXin LI s->strstart = 0; 1249c9083b85SXin LI s->block_start = 0L; 1250c9083b85SXin LI s->lookahead = 0; 1251c9083b85SXin LI s->insert = 0; 1252c9083b85SXin LI s->match_length = s->prev_length = MIN_MATCH-1; 1253c9083b85SXin LI s->match_available = 0; 1254c9083b85SXin LI s->ins_h = 0; 1255c9083b85SXin LI #ifndef FASTEST 1256c9083b85SXin LI #ifdef ASMV 1257c9083b85SXin LI match_init(); /* initialize the asm code */ 1258c9083b85SXin LI #endif 1259c9083b85SXin LI #endif 1260c9083b85SXin LI } 1261c9083b85SXin LI 1262c9083b85SXin LI #ifndef FASTEST 1263c9083b85SXin LI /* =========================================================================== 1264c9083b85SXin LI * Set match_start to the longest match starting at the given string and 1265c9083b85SXin LI * return its length. Matches shorter or equal to prev_length are discarded, 1266c9083b85SXin LI * in which case the result is equal to prev_length and match_start is 1267c9083b85SXin LI * garbage. 1268c9083b85SXin LI * IN assertions: cur_match is the head of the hash chain for the current 1269c9083b85SXin LI * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1270c9083b85SXin LI * OUT assertion: the match length is not greater than s->lookahead. 1271c9083b85SXin LI */ 1272c9083b85SXin LI #ifndef ASMV 1273c9083b85SXin LI /* For 80x86 and 680x0, an optimized version will be provided in match.asm or 1274c9083b85SXin LI * match.S. The code will be functionally equivalent. 1275c9083b85SXin LI */ 1276c9083b85SXin LI local uInt longest_match(s, cur_match) 1277c9083b85SXin LI deflate_state *s; 1278c9083b85SXin LI IPos cur_match; /* current match */ 1279c9083b85SXin LI { 1280c9083b85SXin LI unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1281c9083b85SXin LI register Bytef *scan = s->window + s->strstart; /* current string */ 1282c9083b85SXin LI register Bytef *match; /* matched string */ 1283c9083b85SXin LI register int len; /* length of current match */ 1284c9083b85SXin LI int best_len = (int)s->prev_length; /* best match length so far */ 1285c9083b85SXin LI int nice_match = s->nice_match; /* stop if match long enough */ 1286c9083b85SXin LI IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1287c9083b85SXin LI s->strstart - (IPos)MAX_DIST(s) : NIL; 1288c9083b85SXin LI /* Stop when cur_match becomes <= limit. To simplify the code, 1289c9083b85SXin LI * we prevent matches with the string of window index 0. 1290c9083b85SXin LI */ 1291c9083b85SXin LI Posf *prev = s->prev; 1292c9083b85SXin LI uInt wmask = s->w_mask; 1293c9083b85SXin LI 1294c9083b85SXin LI #ifdef UNALIGNED_OK 1295c9083b85SXin LI /* Compare two bytes at a time. Note: this is not always beneficial. 1296c9083b85SXin LI * Try with and without -DUNALIGNED_OK to check. 1297c9083b85SXin LI */ 1298c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1299c9083b85SXin LI register ush scan_start = *(ushf*)scan; 1300c9083b85SXin LI register ush scan_end = *(ushf*)(scan+best_len-1); 1301c9083b85SXin LI #else 1302c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1303c9083b85SXin LI register Byte scan_end1 = scan[best_len-1]; 1304c9083b85SXin LI register Byte scan_end = scan[best_len]; 1305c9083b85SXin LI #endif 1306c9083b85SXin LI 1307c9083b85SXin LI /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1308c9083b85SXin LI * It is easy to get rid of this optimization if necessary. 1309c9083b85SXin LI */ 1310c9083b85SXin LI Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1311c9083b85SXin LI 1312c9083b85SXin LI /* Do not waste too much time if we already have a good match: */ 1313c9083b85SXin LI if (s->prev_length >= s->good_match) { 1314c9083b85SXin LI chain_length >>= 2; 1315c9083b85SXin LI } 1316c9083b85SXin LI /* Do not look for matches beyond the end of the input. This is necessary 1317c9083b85SXin LI * to make deflate deterministic. 1318c9083b85SXin LI */ 1319c9083b85SXin LI if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead; 1320c9083b85SXin LI 1321c9083b85SXin LI Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1322c9083b85SXin LI 1323c9083b85SXin LI do { 1324c9083b85SXin LI Assert(cur_match < s->strstart, "no future"); 1325c9083b85SXin LI match = s->window + cur_match; 1326c9083b85SXin LI 1327c9083b85SXin LI /* Skip to next match if the match length cannot increase 1328c9083b85SXin LI * or if the match length is less than 2. Note that the checks below 1329c9083b85SXin LI * for insufficient lookahead only occur occasionally for performance 1330c9083b85SXin LI * reasons. Therefore uninitialized memory will be accessed, and 1331c9083b85SXin LI * conditional jumps will be made that depend on those values. 1332c9083b85SXin LI * However the length of the match is limited to the lookahead, so 1333c9083b85SXin LI * the output of deflate is not affected by the uninitialized values. 1334c9083b85SXin LI */ 1335c9083b85SXin LI #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1336c9083b85SXin LI /* This code assumes sizeof(unsigned short) == 2. Do not use 1337c9083b85SXin LI * UNALIGNED_OK if your compiler uses a different size. 1338c9083b85SXin LI */ 1339c9083b85SXin LI if (*(ushf*)(match+best_len-1) != scan_end || 1340c9083b85SXin LI *(ushf*)match != scan_start) continue; 1341c9083b85SXin LI 1342c9083b85SXin LI /* It is not necessary to compare scan[2] and match[2] since they are 1343c9083b85SXin LI * always equal when the other bytes match, given that the hash keys 1344c9083b85SXin LI * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 1345c9083b85SXin LI * strstart+3, +5, ... up to strstart+257. We check for insufficient 1346c9083b85SXin LI * lookahead only every 4th comparison; the 128th check will be made 1347c9083b85SXin LI * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 1348c9083b85SXin LI * necessary to put more guard bytes at the end of the window, or 1349c9083b85SXin LI * to check more often for insufficient lookahead. 1350c9083b85SXin LI */ 1351c9083b85SXin LI Assert(scan[2] == match[2], "scan[2]?"); 1352c9083b85SXin LI scan++, match++; 1353c9083b85SXin LI do { 1354c9083b85SXin LI } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1355c9083b85SXin LI *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1356c9083b85SXin LI *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1357c9083b85SXin LI *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 1358c9083b85SXin LI scan < strend); 1359c9083b85SXin LI /* The funny "do {}" generates better code on most compilers */ 1360c9083b85SXin LI 1361c9083b85SXin LI /* Here, scan <= window+strstart+257 */ 1362c9083b85SXin LI Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1363c9083b85SXin LI if (*scan == *match) scan++; 1364c9083b85SXin LI 1365c9083b85SXin LI len = (MAX_MATCH - 1) - (int)(strend-scan); 1366c9083b85SXin LI scan = strend - (MAX_MATCH-1); 1367c9083b85SXin LI 1368c9083b85SXin LI #else /* UNALIGNED_OK */ 1369c9083b85SXin LI 1370c9083b85SXin LI if (match[best_len] != scan_end || 1371c9083b85SXin LI match[best_len-1] != scan_end1 || 1372c9083b85SXin LI *match != *scan || 1373c9083b85SXin LI *++match != scan[1]) continue; 1374c9083b85SXin LI 1375c9083b85SXin LI /* The check at best_len-1 can be removed because it will be made 1376c9083b85SXin LI * again later. (This heuristic is not always a win.) 1377c9083b85SXin LI * It is not necessary to compare scan[2] and match[2] since they 1378c9083b85SXin LI * are always equal when the other bytes match, given that 1379c9083b85SXin LI * the hash keys are equal and that HASH_BITS >= 8. 1380c9083b85SXin LI */ 1381c9083b85SXin LI scan += 2, match++; 1382c9083b85SXin LI Assert(*scan == *match, "match[2]?"); 1383c9083b85SXin LI 1384c9083b85SXin LI /* We check for insufficient lookahead only every 8th comparison; 1385c9083b85SXin LI * the 256th check will be made at strstart+258. 1386c9083b85SXin LI */ 1387c9083b85SXin LI do { 1388c9083b85SXin LI } while (*++scan == *++match && *++scan == *++match && 1389c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1390c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1391c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1392c9083b85SXin LI scan < strend); 1393c9083b85SXin LI 1394c9083b85SXin LI Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1395c9083b85SXin LI 1396c9083b85SXin LI len = MAX_MATCH - (int)(strend - scan); 1397c9083b85SXin LI scan = strend - MAX_MATCH; 1398c9083b85SXin LI 1399c9083b85SXin LI #endif /* UNALIGNED_OK */ 1400c9083b85SXin LI 1401c9083b85SXin LI if (len > best_len) { 1402c9083b85SXin LI s->match_start = cur_match; 1403c9083b85SXin LI best_len = len; 1404c9083b85SXin LI if (len >= nice_match) break; 1405c9083b85SXin LI #ifdef UNALIGNED_OK 1406c9083b85SXin LI scan_end = *(ushf*)(scan+best_len-1); 1407c9083b85SXin LI #else 1408c9083b85SXin LI scan_end1 = scan[best_len-1]; 1409c9083b85SXin LI scan_end = scan[best_len]; 1410c9083b85SXin LI #endif 1411c9083b85SXin LI } 1412c9083b85SXin LI } while ((cur_match = prev[cur_match & wmask]) > limit 1413c9083b85SXin LI && --chain_length != 0); 1414c9083b85SXin LI 1415c9083b85SXin LI if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 1416c9083b85SXin LI return s->lookahead; 1417c9083b85SXin LI } 1418c9083b85SXin LI #endif /* ASMV */ 1419c9083b85SXin LI 1420c9083b85SXin LI #else /* FASTEST */ 1421c9083b85SXin LI 1422c9083b85SXin LI /* --------------------------------------------------------------------------- 1423c9083b85SXin LI * Optimized version for FASTEST only 1424c9083b85SXin LI */ 1425c9083b85SXin LI local uInt longest_match(s, cur_match) 1426c9083b85SXin LI deflate_state *s; 1427c9083b85SXin LI IPos cur_match; /* current match */ 1428c9083b85SXin LI { 1429c9083b85SXin LI register Bytef *scan = s->window + s->strstart; /* current string */ 1430c9083b85SXin LI register Bytef *match; /* matched string */ 1431c9083b85SXin LI register int len; /* length of current match */ 1432c9083b85SXin LI register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1433c9083b85SXin LI 1434c9083b85SXin LI /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1435c9083b85SXin LI * It is easy to get rid of this optimization if necessary. 1436c9083b85SXin LI */ 1437c9083b85SXin LI Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1438c9083b85SXin LI 1439c9083b85SXin LI Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1440c9083b85SXin LI 1441c9083b85SXin LI Assert(cur_match < s->strstart, "no future"); 1442c9083b85SXin LI 1443c9083b85SXin LI match = s->window + cur_match; 1444c9083b85SXin LI 1445c9083b85SXin LI /* Return failure if the match length is less than 2: 1446c9083b85SXin LI */ 1447c9083b85SXin LI if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 1448c9083b85SXin LI 1449c9083b85SXin LI /* The check at best_len-1 can be removed because it will be made 1450c9083b85SXin LI * again later. (This heuristic is not always a win.) 1451c9083b85SXin LI * It is not necessary to compare scan[2] and match[2] since they 1452c9083b85SXin LI * are always equal when the other bytes match, given that 1453c9083b85SXin LI * the hash keys are equal and that HASH_BITS >= 8. 1454c9083b85SXin LI */ 1455c9083b85SXin LI scan += 2, match += 2; 1456c9083b85SXin LI Assert(*scan == *match, "match[2]?"); 1457c9083b85SXin LI 1458c9083b85SXin LI /* We check for insufficient lookahead only every 8th comparison; 1459c9083b85SXin LI * the 256th check will be made at strstart+258. 1460c9083b85SXin LI */ 1461c9083b85SXin LI do { 1462c9083b85SXin LI } while (*++scan == *++match && *++scan == *++match && 1463c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1464c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1465c9083b85SXin LI *++scan == *++match && *++scan == *++match && 1466c9083b85SXin LI scan < strend); 1467c9083b85SXin LI 1468c9083b85SXin LI Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1469c9083b85SXin LI 1470c9083b85SXin LI len = MAX_MATCH - (int)(strend - scan); 1471c9083b85SXin LI 1472c9083b85SXin LI if (len < MIN_MATCH) return MIN_MATCH - 1; 1473c9083b85SXin LI 1474c9083b85SXin LI s->match_start = cur_match; 1475c9083b85SXin LI return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 1476c9083b85SXin LI } 1477c9083b85SXin LI 1478c9083b85SXin LI #endif /* FASTEST */ 1479c9083b85SXin LI 1480c9083b85SXin LI #ifdef ZLIB_DEBUG 1481c9083b85SXin LI 1482c9083b85SXin LI #define EQUAL 0 1483c9083b85SXin LI /* result of memcmp for equal strings */ 1484c9083b85SXin LI 1485c9083b85SXin LI /* =========================================================================== 1486c9083b85SXin LI * Check that the match at match_start is indeed a match. 1487c9083b85SXin LI */ 1488c9083b85SXin LI local void check_match(s, start, match, length) 1489c9083b85SXin LI deflate_state *s; 1490c9083b85SXin LI IPos start, match; 1491c9083b85SXin LI int length; 1492c9083b85SXin LI { 1493c9083b85SXin LI /* check that the match is indeed a match */ 1494c9083b85SXin LI if (zmemcmp(s->window + match, 1495c9083b85SXin LI s->window + start, length) != EQUAL) { 1496c9083b85SXin LI fprintf(stderr, " start %u, match %u, length %d\n", 1497c9083b85SXin LI start, match, length); 1498c9083b85SXin LI do { 1499c9083b85SXin LI fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 1500c9083b85SXin LI } while (--length != 0); 1501c9083b85SXin LI z_error("invalid match"); 1502c9083b85SXin LI } 1503c9083b85SXin LI if (z_verbose > 1) { 1504c9083b85SXin LI fprintf(stderr,"\\[%d,%d]", start-match, length); 1505c9083b85SXin LI do { putc(s->window[start++], stderr); } while (--length != 0); 1506c9083b85SXin LI } 1507c9083b85SXin LI } 1508c9083b85SXin LI #else 1509c9083b85SXin LI # define check_match(s, start, match, length) 1510c9083b85SXin LI #endif /* ZLIB_DEBUG */ 1511c9083b85SXin LI 1512c9083b85SXin LI /* =========================================================================== 1513c9083b85SXin LI * Fill the window when the lookahead becomes insufficient. 1514c9083b85SXin LI * Updates strstart and lookahead. 1515c9083b85SXin LI * 1516c9083b85SXin LI * IN assertion: lookahead < MIN_LOOKAHEAD 1517c9083b85SXin LI * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 1518c9083b85SXin LI * At least one byte has been read, or avail_in == 0; reads are 1519c9083b85SXin LI * performed for at least two bytes (required for the zip translate_eol 1520c9083b85SXin LI * option -- not supported here). 1521c9083b85SXin LI */ 1522c9083b85SXin LI local void fill_window(s) 1523c9083b85SXin LI deflate_state *s; 1524c9083b85SXin LI { 1525c9083b85SXin LI unsigned n; 1526c9083b85SXin LI unsigned more; /* Amount of free space at the end of the window. */ 1527c9083b85SXin LI uInt wsize = s->w_size; 1528c9083b85SXin LI 1529c9083b85SXin LI Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 1530c9083b85SXin LI 1531c9083b85SXin LI do { 1532c9083b85SXin LI more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 1533c9083b85SXin LI 1534c9083b85SXin LI /* Deal with !@#$% 64K limit: */ 1535c9083b85SXin LI if (sizeof(int) <= 2) { 1536c9083b85SXin LI if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1537c9083b85SXin LI more = wsize; 1538c9083b85SXin LI 1539c9083b85SXin LI } else if (more == (unsigned)(-1)) { 1540c9083b85SXin LI /* Very unlikely, but possible on 16 bit machine if 1541c9083b85SXin LI * strstart == 0 && lookahead == 1 (input done a byte at time) 1542c9083b85SXin LI */ 1543c9083b85SXin LI more--; 1544c9083b85SXin LI } 1545c9083b85SXin LI } 1546c9083b85SXin LI 1547c9083b85SXin LI /* If the window is almost full and there is insufficient lookahead, 1548c9083b85SXin LI * move the upper half to the lower one to make room in the upper half. 1549c9083b85SXin LI */ 1550c9083b85SXin LI if (s->strstart >= wsize+MAX_DIST(s)) { 1551c9083b85SXin LI 1552c9083b85SXin LI zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more); 1553c9083b85SXin LI s->match_start -= wsize; 1554c9083b85SXin LI s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 1555c9083b85SXin LI s->block_start -= (long) wsize; 1556cd882207SXin LI if (s->insert > s->strstart) 1557cd882207SXin LI s->insert = s->strstart; 1558c9083b85SXin LI slide_hash(s); 1559c9083b85SXin LI more += wsize; 1560c9083b85SXin LI } 1561c9083b85SXin LI if (s->strm->avail_in == 0) break; 1562c9083b85SXin LI 1563c9083b85SXin LI /* If there was no sliding: 1564c9083b85SXin LI * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1565c9083b85SXin LI * more == window_size - lookahead - strstart 1566c9083b85SXin LI * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1567c9083b85SXin LI * => more >= window_size - 2*WSIZE + 2 1568c9083b85SXin LI * In the BIG_MEM or MMAP case (not yet supported), 1569c9083b85SXin LI * window_size == input_size + MIN_LOOKAHEAD && 1570c9083b85SXin LI * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1571c9083b85SXin LI * Otherwise, window_size == 2*WSIZE so more >= 2. 1572c9083b85SXin LI * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1573c9083b85SXin LI */ 1574c9083b85SXin LI Assert(more >= 2, "more < 2"); 1575c9083b85SXin LI 1576c9083b85SXin LI n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 1577c9083b85SXin LI s->lookahead += n; 1578c9083b85SXin LI 1579c9083b85SXin LI /* Initialize the hash value now that we have some input: */ 1580c9083b85SXin LI if (s->lookahead + s->insert >= MIN_MATCH) { 1581c9083b85SXin LI uInt str = s->strstart - s->insert; 1582c9083b85SXin LI s->ins_h = s->window[str]; 1583c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 1584c9083b85SXin LI #if MIN_MATCH != 3 1585c9083b85SXin LI Call UPDATE_HASH() MIN_MATCH-3 more times 1586c9083b85SXin LI #endif 1587c9083b85SXin LI while (s->insert) { 1588c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 1589c9083b85SXin LI #ifndef FASTEST 1590c9083b85SXin LI s->prev[str & s->w_mask] = s->head[s->ins_h]; 1591c9083b85SXin LI #endif 1592c9083b85SXin LI s->head[s->ins_h] = (Pos)str; 1593c9083b85SXin LI str++; 1594c9083b85SXin LI s->insert--; 1595c9083b85SXin LI if (s->lookahead + s->insert < MIN_MATCH) 1596c9083b85SXin LI break; 1597c9083b85SXin LI } 1598c9083b85SXin LI } 1599c9083b85SXin LI /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 1600c9083b85SXin LI * but this is not important since only literal bytes will be emitted. 1601c9083b85SXin LI */ 1602c9083b85SXin LI 1603c9083b85SXin LI } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1604c9083b85SXin LI 1605c9083b85SXin LI /* If the WIN_INIT bytes after the end of the current data have never been 1606c9083b85SXin LI * written, then zero those bytes in order to avoid memory check reports of 1607c9083b85SXin LI * the use of uninitialized (or uninitialised as Julian writes) bytes by 1608c9083b85SXin LI * the longest match routines. Update the high water mark for the next 1609c9083b85SXin LI * time through here. WIN_INIT is set to MAX_MATCH since the longest match 1610c9083b85SXin LI * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 1611c9083b85SXin LI */ 1612c9083b85SXin LI if (s->high_water < s->window_size) { 1613c9083b85SXin LI ulg curr = s->strstart + (ulg)(s->lookahead); 1614c9083b85SXin LI ulg init; 1615c9083b85SXin LI 1616c9083b85SXin LI if (s->high_water < curr) { 1617c9083b85SXin LI /* Previous high water mark below current data -- zero WIN_INIT 1618c9083b85SXin LI * bytes or up to end of window, whichever is less. 1619c9083b85SXin LI */ 1620c9083b85SXin LI init = s->window_size - curr; 1621c9083b85SXin LI if (init > WIN_INIT) 1622c9083b85SXin LI init = WIN_INIT; 1623c9083b85SXin LI zmemzero(s->window + curr, (unsigned)init); 1624c9083b85SXin LI s->high_water = curr + init; 1625c9083b85SXin LI } 1626c9083b85SXin LI else if (s->high_water < (ulg)curr + WIN_INIT) { 1627c9083b85SXin LI /* High water mark at or above current data, but below current data 1628c9083b85SXin LI * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 1629c9083b85SXin LI * to end of window, whichever is less. 1630c9083b85SXin LI */ 1631c9083b85SXin LI init = (ulg)curr + WIN_INIT - s->high_water; 1632c9083b85SXin LI if (init > s->window_size - s->high_water) 1633c9083b85SXin LI init = s->window_size - s->high_water; 1634c9083b85SXin LI zmemzero(s->window + s->high_water, (unsigned)init); 1635c9083b85SXin LI s->high_water += init; 1636c9083b85SXin LI } 1637c9083b85SXin LI } 1638c9083b85SXin LI 1639c9083b85SXin LI Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 1640c9083b85SXin LI "not enough room for search"); 1641c9083b85SXin LI } 1642c9083b85SXin LI 1643c9083b85SXin LI /* =========================================================================== 1644c9083b85SXin LI * Flush the current block, with given end-of-file flag. 1645c9083b85SXin LI * IN assertion: strstart is set to the end of the current match. 1646c9083b85SXin LI */ 1647c9083b85SXin LI #define FLUSH_BLOCK_ONLY(s, last) { \ 1648c9083b85SXin LI _tr_flush_block(s, (s->block_start >= 0L ? \ 1649c9083b85SXin LI (charf *)&s->window[(unsigned)s->block_start] : \ 1650c9083b85SXin LI (charf *)Z_NULL), \ 1651c9083b85SXin LI (ulg)((long)s->strstart - s->block_start), \ 1652c9083b85SXin LI (last)); \ 1653c9083b85SXin LI s->block_start = s->strstart; \ 1654c9083b85SXin LI flush_pending(s->strm); \ 1655c9083b85SXin LI Tracev((stderr,"[FLUSH]")); \ 1656c9083b85SXin LI } 1657c9083b85SXin LI 1658c9083b85SXin LI /* Same but force premature exit if necessary. */ 1659c9083b85SXin LI #define FLUSH_BLOCK(s, last) { \ 1660c9083b85SXin LI FLUSH_BLOCK_ONLY(s, last); \ 1661c9083b85SXin LI if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 1662c9083b85SXin LI } 1663c9083b85SXin LI 1664c9083b85SXin LI /* Maximum stored block length in deflate format (not including header). */ 1665c9083b85SXin LI #define MAX_STORED 65535 1666c9083b85SXin LI 16670ed1d6fbSXin LI #if !defined(MIN) 1668c9083b85SXin LI /* Minimum of a and b. */ 1669c9083b85SXin LI #define MIN(a, b) ((a) > (b) ? (b) : (a)) 16700ed1d6fbSXin LI #endif 1671c9083b85SXin LI 1672c9083b85SXin LI /* =========================================================================== 1673c9083b85SXin LI * Copy without compression as much as possible from the input stream, return 1674c9083b85SXin LI * the current block state. 1675c9083b85SXin LI * 1676c9083b85SXin LI * In case deflateParams() is used to later switch to a non-zero compression 1677c9083b85SXin LI * level, s->matches (otherwise unused when storing) keeps track of the number 1678c9083b85SXin LI * of hash table slides to perform. If s->matches is 1, then one hash table 1679c9083b85SXin LI * slide will be done when switching. If s->matches is 2, the maximum value 1680c9083b85SXin LI * allowed here, then the hash table will be cleared, since two or more slides 1681c9083b85SXin LI * is the same as a clear. 1682c9083b85SXin LI * 1683c9083b85SXin LI * deflate_stored() is written to minimize the number of times an input byte is 1684c9083b85SXin LI * copied. It is most efficient with large input and output buffers, which 1685c9083b85SXin LI * maximizes the opportunites to have a single copy from next_in to next_out. 1686c9083b85SXin LI */ 1687c9083b85SXin LI local block_state deflate_stored(s, flush) 1688c9083b85SXin LI deflate_state *s; 1689c9083b85SXin LI int flush; 1690c9083b85SXin LI { 1691c9083b85SXin LI /* Smallest worthy block size when not flushing or finishing. By default 1692c9083b85SXin LI * this is 32K. This can be as small as 507 bytes for memLevel == 1. For 1693c9083b85SXin LI * large input and output buffers, the stored block size will be larger. 1694c9083b85SXin LI */ 1695c9083b85SXin LI unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size); 1696c9083b85SXin LI 1697c9083b85SXin LI /* Copy as many min_block or larger stored blocks directly to next_out as 1698c9083b85SXin LI * possible. If flushing, copy the remaining available input to next_out as 1699c9083b85SXin LI * stored blocks, if there is enough space. 1700c9083b85SXin LI */ 1701c9083b85SXin LI unsigned len, left, have, last = 0; 1702c9083b85SXin LI unsigned used = s->strm->avail_in; 1703c9083b85SXin LI do { 1704c9083b85SXin LI /* Set len to the maximum size block that we can copy directly with the 1705c9083b85SXin LI * available input data and output space. Set left to how much of that 1706c9083b85SXin LI * would be copied from what's left in the window. 1707c9083b85SXin LI */ 1708c9083b85SXin LI len = MAX_STORED; /* maximum deflate stored block length */ 1709c9083b85SXin LI have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1710c9083b85SXin LI if (s->strm->avail_out < have) /* need room for header */ 1711c9083b85SXin LI break; 1712c9083b85SXin LI /* maximum stored block length that will fit in avail_out: */ 1713c9083b85SXin LI have = s->strm->avail_out - have; 1714c9083b85SXin LI left = s->strstart - s->block_start; /* bytes left in window */ 1715c9083b85SXin LI if (len > (ulg)left + s->strm->avail_in) 1716c9083b85SXin LI len = left + s->strm->avail_in; /* limit len to the input */ 1717c9083b85SXin LI if (len > have) 1718c9083b85SXin LI len = have; /* limit len to the output */ 1719c9083b85SXin LI 1720c9083b85SXin LI /* If the stored block would be less than min_block in length, or if 1721c9083b85SXin LI * unable to copy all of the available input when flushing, then try 1722c9083b85SXin LI * copying to the window and the pending buffer instead. Also don't 1723c9083b85SXin LI * write an empty block when flushing -- deflate() does that. 1724c9083b85SXin LI */ 1725c9083b85SXin LI if (len < min_block && ((len == 0 && flush != Z_FINISH) || 1726c9083b85SXin LI flush == Z_NO_FLUSH || 1727c9083b85SXin LI len != left + s->strm->avail_in)) 1728c9083b85SXin LI break; 1729c9083b85SXin LI 1730c9083b85SXin LI /* Make a dummy stored block in pending to get the header bytes, 1731c9083b85SXin LI * including any pending bits. This also updates the debugging counts. 1732c9083b85SXin LI */ 1733c9083b85SXin LI last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0; 1734c9083b85SXin LI _tr_stored_block(s, (char *)0, 0L, last); 1735c9083b85SXin LI 1736c9083b85SXin LI /* Replace the lengths in the dummy stored block with len. */ 1737c9083b85SXin LI s->pending_buf[s->pending - 4] = len; 1738c9083b85SXin LI s->pending_buf[s->pending - 3] = len >> 8; 1739c9083b85SXin LI s->pending_buf[s->pending - 2] = ~len; 1740c9083b85SXin LI s->pending_buf[s->pending - 1] = ~len >> 8; 1741c9083b85SXin LI 1742c9083b85SXin LI /* Write the stored block header bytes. */ 1743c9083b85SXin LI flush_pending(s->strm); 1744c9083b85SXin LI 1745c9083b85SXin LI #ifdef ZLIB_DEBUG 1746c9083b85SXin LI /* Update debugging counts for the data about to be copied. */ 1747c9083b85SXin LI s->compressed_len += len << 3; 1748c9083b85SXin LI s->bits_sent += len << 3; 1749c9083b85SXin LI #endif 1750c9083b85SXin LI 1751c9083b85SXin LI /* Copy uncompressed bytes from the window to next_out. */ 1752c9083b85SXin LI if (left) { 1753c9083b85SXin LI if (left > len) 1754c9083b85SXin LI left = len; 1755c9083b85SXin LI zmemcpy(s->strm->next_out, s->window + s->block_start, left); 1756c9083b85SXin LI s->strm->next_out += left; 1757c9083b85SXin LI s->strm->avail_out -= left; 1758c9083b85SXin LI s->strm->total_out += left; 1759c9083b85SXin LI s->block_start += left; 1760c9083b85SXin LI len -= left; 1761c9083b85SXin LI } 1762c9083b85SXin LI 1763c9083b85SXin LI /* Copy uncompressed bytes directly from next_in to next_out, updating 1764c9083b85SXin LI * the check value. 1765c9083b85SXin LI */ 1766c9083b85SXin LI if (len) { 1767c9083b85SXin LI read_buf(s->strm, s->strm->next_out, len); 1768c9083b85SXin LI s->strm->next_out += len; 1769c9083b85SXin LI s->strm->avail_out -= len; 1770c9083b85SXin LI s->strm->total_out += len; 1771c9083b85SXin LI } 1772c9083b85SXin LI } while (last == 0); 1773c9083b85SXin LI 1774c9083b85SXin LI /* Update the sliding window with the last s->w_size bytes of the copied 1775c9083b85SXin LI * data, or append all of the copied data to the existing window if less 1776c9083b85SXin LI * than s->w_size bytes were copied. Also update the number of bytes to 1777c9083b85SXin LI * insert in the hash tables, in the event that deflateParams() switches to 1778c9083b85SXin LI * a non-zero compression level. 1779c9083b85SXin LI */ 1780c9083b85SXin LI used -= s->strm->avail_in; /* number of input bytes directly copied */ 1781c9083b85SXin LI if (used) { 1782c9083b85SXin LI /* If any input was used, then no unused input remains in the window, 1783c9083b85SXin LI * therefore s->block_start == s->strstart. 1784c9083b85SXin LI */ 1785c9083b85SXin LI if (used >= s->w_size) { /* supplant the previous history */ 1786c9083b85SXin LI s->matches = 2; /* clear hash */ 1787c9083b85SXin LI zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size); 1788c9083b85SXin LI s->strstart = s->w_size; 1789cd882207SXin LI s->insert = s->strstart; 1790c9083b85SXin LI } 1791c9083b85SXin LI else { 1792c9083b85SXin LI if (s->window_size - s->strstart <= used) { 1793c9083b85SXin LI /* Slide the window down. */ 1794c9083b85SXin LI s->strstart -= s->w_size; 1795c9083b85SXin LI zmemcpy(s->window, s->window + s->w_size, s->strstart); 1796c9083b85SXin LI if (s->matches < 2) 1797c9083b85SXin LI s->matches++; /* add a pending slide_hash() */ 1798cd882207SXin LI if (s->insert > s->strstart) 1799cd882207SXin LI s->insert = s->strstart; 1800c9083b85SXin LI } 1801c9083b85SXin LI zmemcpy(s->window + s->strstart, s->strm->next_in - used, used); 1802c9083b85SXin LI s->strstart += used; 1803cd882207SXin LI s->insert += MIN(used, s->w_size - s->insert); 1804c9083b85SXin LI } 1805c9083b85SXin LI s->block_start = s->strstart; 1806c9083b85SXin LI } 1807c9083b85SXin LI if (s->high_water < s->strstart) 1808c9083b85SXin LI s->high_water = s->strstart; 1809c9083b85SXin LI 1810c9083b85SXin LI /* If the last block was written to next_out, then done. */ 1811c9083b85SXin LI if (last) 1812c9083b85SXin LI return finish_done; 1813c9083b85SXin LI 1814c9083b85SXin LI /* If flushing and all input has been consumed, then done. */ 1815c9083b85SXin LI if (flush != Z_NO_FLUSH && flush != Z_FINISH && 1816c9083b85SXin LI s->strm->avail_in == 0 && (long)s->strstart == s->block_start) 1817c9083b85SXin LI return block_done; 1818c9083b85SXin LI 1819c9083b85SXin LI /* Fill the window with any remaining input. */ 1820cd882207SXin LI have = s->window_size - s->strstart; 1821c9083b85SXin LI if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) { 1822c9083b85SXin LI /* Slide the window down. */ 1823c9083b85SXin LI s->block_start -= s->w_size; 1824c9083b85SXin LI s->strstart -= s->w_size; 1825c9083b85SXin LI zmemcpy(s->window, s->window + s->w_size, s->strstart); 1826c9083b85SXin LI if (s->matches < 2) 1827c9083b85SXin LI s->matches++; /* add a pending slide_hash() */ 1828c9083b85SXin LI have += s->w_size; /* more space now */ 1829cd882207SXin LI if (s->insert > s->strstart) 1830cd882207SXin LI s->insert = s->strstart; 1831c9083b85SXin LI } 1832c9083b85SXin LI if (have > s->strm->avail_in) 1833c9083b85SXin LI have = s->strm->avail_in; 1834c9083b85SXin LI if (have) { 1835c9083b85SXin LI read_buf(s->strm, s->window + s->strstart, have); 1836c9083b85SXin LI s->strstart += have; 1837cd882207SXin LI s->insert += MIN(have, s->w_size - s->insert); 1838c9083b85SXin LI } 1839c9083b85SXin LI if (s->high_water < s->strstart) 1840c9083b85SXin LI s->high_water = s->strstart; 1841c9083b85SXin LI 1842c9083b85SXin LI /* There was not enough avail_out to write a complete worthy or flushed 1843c9083b85SXin LI * stored block to next_out. Write a stored block to pending instead, if we 1844c9083b85SXin LI * have enough input for a worthy block, or if flushing and there is enough 1845c9083b85SXin LI * room for the remaining input as a stored block in the pending buffer. 1846c9083b85SXin LI */ 1847c9083b85SXin LI have = (s->bi_valid + 42) >> 3; /* number of header bytes */ 1848c9083b85SXin LI /* maximum stored block length that will fit in pending: */ 1849c9083b85SXin LI have = MIN(s->pending_buf_size - have, MAX_STORED); 1850c9083b85SXin LI min_block = MIN(have, s->w_size); 1851c9083b85SXin LI left = s->strstart - s->block_start; 1852c9083b85SXin LI if (left >= min_block || 1853c9083b85SXin LI ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH && 1854c9083b85SXin LI s->strm->avail_in == 0 && left <= have)) { 1855c9083b85SXin LI len = MIN(left, have); 1856c9083b85SXin LI last = flush == Z_FINISH && s->strm->avail_in == 0 && 1857c9083b85SXin LI len == left ? 1 : 0; 1858c9083b85SXin LI _tr_stored_block(s, (charf *)s->window + s->block_start, len, last); 1859c9083b85SXin LI s->block_start += len; 1860c9083b85SXin LI flush_pending(s->strm); 1861c9083b85SXin LI } 1862c9083b85SXin LI 1863c9083b85SXin LI /* We've done all we can with the available input and output. */ 1864c9083b85SXin LI return last ? finish_started : need_more; 1865c9083b85SXin LI } 1866c9083b85SXin LI 1867c9083b85SXin LI /* =========================================================================== 1868c9083b85SXin LI * Compress as much as possible from the input stream, return the current 1869c9083b85SXin LI * block state. 1870c9083b85SXin LI * This function does not perform lazy evaluation of matches and inserts 1871c9083b85SXin LI * new strings in the dictionary only for unmatched strings or for short 1872c9083b85SXin LI * matches. It is used only for the fast compression options. 1873c9083b85SXin LI */ 1874c9083b85SXin LI local block_state deflate_fast(s, flush) 1875c9083b85SXin LI deflate_state *s; 1876c9083b85SXin LI int flush; 1877c9083b85SXin LI { 1878c9083b85SXin LI IPos hash_head; /* head of the hash chain */ 1879c9083b85SXin LI int bflush; /* set if current block must be flushed */ 1880c9083b85SXin LI 1881c9083b85SXin LI for (;;) { 1882c9083b85SXin LI /* Make sure that we always have enough lookahead, except 1883c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 1884c9083b85SXin LI * for the next match, plus MIN_MATCH bytes to insert the 1885c9083b85SXin LI * string following the next match. 1886c9083b85SXin LI */ 1887c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD) { 1888c9083b85SXin LI fill_window(s); 1889c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1890c9083b85SXin LI return need_more; 1891c9083b85SXin LI } 1892c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 1893c9083b85SXin LI } 1894c9083b85SXin LI 1895c9083b85SXin LI /* Insert the string window[strstart .. strstart+2] in the 1896c9083b85SXin LI * dictionary, and set hash_head to the head of the hash chain: 1897c9083b85SXin LI */ 1898c9083b85SXin LI hash_head = NIL; 1899c9083b85SXin LI if (s->lookahead >= MIN_MATCH) { 1900c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1901c9083b85SXin LI } 1902c9083b85SXin LI 1903c9083b85SXin LI /* Find the longest match, discarding those <= prev_length. 1904c9083b85SXin LI * At this point we have always match_length < MIN_MATCH 1905c9083b85SXin LI */ 1906c9083b85SXin LI if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1907c9083b85SXin LI /* To simplify the code, we prevent matches with the string 1908c9083b85SXin LI * of window index 0 (in particular we have to avoid a match 1909c9083b85SXin LI * of the string with itself at the start of the input file). 1910c9083b85SXin LI */ 1911c9083b85SXin LI s->match_length = longest_match (s, hash_head); 1912c9083b85SXin LI /* longest_match() sets match_start */ 1913c9083b85SXin LI } 1914c9083b85SXin LI if (s->match_length >= MIN_MATCH) { 1915c9083b85SXin LI check_match(s, s->strstart, s->match_start, s->match_length); 1916c9083b85SXin LI 1917c9083b85SXin LI _tr_tally_dist(s, s->strstart - s->match_start, 1918c9083b85SXin LI s->match_length - MIN_MATCH, bflush); 1919c9083b85SXin LI 1920c9083b85SXin LI s->lookahead -= s->match_length; 1921c9083b85SXin LI 1922c9083b85SXin LI /* Insert new strings in the hash table only if the match length 1923c9083b85SXin LI * is not too large. This saves time but degrades compression. 1924c9083b85SXin LI */ 1925c9083b85SXin LI #ifndef FASTEST 1926c9083b85SXin LI if (s->match_length <= s->max_insert_length && 1927c9083b85SXin LI s->lookahead >= MIN_MATCH) { 1928c9083b85SXin LI s->match_length--; /* string at strstart already in table */ 1929c9083b85SXin LI do { 1930c9083b85SXin LI s->strstart++; 1931c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 1932c9083b85SXin LI /* strstart never exceeds WSIZE-MAX_MATCH, so there are 1933c9083b85SXin LI * always MIN_MATCH bytes ahead. 1934c9083b85SXin LI */ 1935c9083b85SXin LI } while (--s->match_length != 0); 1936c9083b85SXin LI s->strstart++; 1937c9083b85SXin LI } else 1938c9083b85SXin LI #endif 1939c9083b85SXin LI { 1940c9083b85SXin LI s->strstart += s->match_length; 1941c9083b85SXin LI s->match_length = 0; 1942c9083b85SXin LI s->ins_h = s->window[s->strstart]; 1943c9083b85SXin LI UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1944c9083b85SXin LI #if MIN_MATCH != 3 1945c9083b85SXin LI Call UPDATE_HASH() MIN_MATCH-3 more times 1946c9083b85SXin LI #endif 1947c9083b85SXin LI /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1948c9083b85SXin LI * matter since it will be recomputed at next deflate call. 1949c9083b85SXin LI */ 1950c9083b85SXin LI } 1951c9083b85SXin LI } else { 1952c9083b85SXin LI /* No match, output a literal byte */ 1953c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 1954c9083b85SXin LI _tr_tally_lit (s, s->window[s->strstart], bflush); 1955c9083b85SXin LI s->lookahead--; 1956c9083b85SXin LI s->strstart++; 1957c9083b85SXin LI } 1958c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 1959c9083b85SXin LI } 1960c9083b85SXin LI s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 1961c9083b85SXin LI if (flush == Z_FINISH) { 1962c9083b85SXin LI FLUSH_BLOCK(s, 1); 1963c9083b85SXin LI return finish_done; 1964c9083b85SXin LI } 1965cd882207SXin LI if (s->sym_next) 1966c9083b85SXin LI FLUSH_BLOCK(s, 0); 1967c9083b85SXin LI return block_done; 1968c9083b85SXin LI } 1969c9083b85SXin LI 1970c9083b85SXin LI #ifndef FASTEST 1971c9083b85SXin LI /* =========================================================================== 1972c9083b85SXin LI * Same as above, but achieves better compression. We use a lazy 1973c9083b85SXin LI * evaluation for matches: a match is finally adopted only if there is 1974c9083b85SXin LI * no better match at the next window position. 1975c9083b85SXin LI */ 1976c9083b85SXin LI local block_state deflate_slow(s, flush) 1977c9083b85SXin LI deflate_state *s; 1978c9083b85SXin LI int flush; 1979c9083b85SXin LI { 1980c9083b85SXin LI IPos hash_head; /* head of hash chain */ 1981c9083b85SXin LI int bflush; /* set if current block must be flushed */ 1982c9083b85SXin LI 1983c9083b85SXin LI /* Process the input block. */ 1984c9083b85SXin LI for (;;) { 1985c9083b85SXin LI /* Make sure that we always have enough lookahead, except 1986c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 1987c9083b85SXin LI * for the next match, plus MIN_MATCH bytes to insert the 1988c9083b85SXin LI * string following the next match. 1989c9083b85SXin LI */ 1990c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD) { 1991c9083b85SXin LI fill_window(s); 1992c9083b85SXin LI if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1993c9083b85SXin LI return need_more; 1994c9083b85SXin LI } 1995c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 1996c9083b85SXin LI } 1997c9083b85SXin LI 1998c9083b85SXin LI /* Insert the string window[strstart .. strstart+2] in the 1999c9083b85SXin LI * dictionary, and set hash_head to the head of the hash chain: 2000c9083b85SXin LI */ 2001c9083b85SXin LI hash_head = NIL; 2002c9083b85SXin LI if (s->lookahead >= MIN_MATCH) { 2003c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 2004c9083b85SXin LI } 2005c9083b85SXin LI 2006c9083b85SXin LI /* Find the longest match, discarding those <= prev_length. 2007c9083b85SXin LI */ 2008c9083b85SXin LI s->prev_length = s->match_length, s->prev_match = s->match_start; 2009c9083b85SXin LI s->match_length = MIN_MATCH-1; 2010c9083b85SXin LI 2011c9083b85SXin LI if (hash_head != NIL && s->prev_length < s->max_lazy_match && 2012c9083b85SXin LI s->strstart - hash_head <= MAX_DIST(s)) { 2013c9083b85SXin LI /* To simplify the code, we prevent matches with the string 2014c9083b85SXin LI * of window index 0 (in particular we have to avoid a match 2015c9083b85SXin LI * of the string with itself at the start of the input file). 2016c9083b85SXin LI */ 2017c9083b85SXin LI s->match_length = longest_match (s, hash_head); 2018c9083b85SXin LI /* longest_match() sets match_start */ 2019c9083b85SXin LI 2020c9083b85SXin LI if (s->match_length <= 5 && (s->strategy == Z_FILTERED 2021c9083b85SXin LI #if TOO_FAR <= 32767 2022c9083b85SXin LI || (s->match_length == MIN_MATCH && 2023c9083b85SXin LI s->strstart - s->match_start > TOO_FAR) 2024c9083b85SXin LI #endif 2025c9083b85SXin LI )) { 2026c9083b85SXin LI 2027c9083b85SXin LI /* If prev_match is also MIN_MATCH, match_start is garbage 2028c9083b85SXin LI * but we will ignore the current match anyway. 2029c9083b85SXin LI */ 2030c9083b85SXin LI s->match_length = MIN_MATCH-1; 2031c9083b85SXin LI } 2032c9083b85SXin LI } 2033c9083b85SXin LI /* If there was a match at the previous step and the current 2034c9083b85SXin LI * match is not better, output the previous match: 2035c9083b85SXin LI */ 2036c9083b85SXin LI if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 2037c9083b85SXin LI uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 2038c9083b85SXin LI /* Do not insert strings in hash table beyond this. */ 2039c9083b85SXin LI 2040c9083b85SXin LI check_match(s, s->strstart-1, s->prev_match, s->prev_length); 2041c9083b85SXin LI 2042c9083b85SXin LI _tr_tally_dist(s, s->strstart -1 - s->prev_match, 2043c9083b85SXin LI s->prev_length - MIN_MATCH, bflush); 2044c9083b85SXin LI 2045c9083b85SXin LI /* Insert in hash table all strings up to the end of the match. 2046c9083b85SXin LI * strstart-1 and strstart are already inserted. If there is not 2047c9083b85SXin LI * enough lookahead, the last two strings are not inserted in 2048c9083b85SXin LI * the hash table. 2049c9083b85SXin LI */ 2050c9083b85SXin LI s->lookahead -= s->prev_length-1; 2051c9083b85SXin LI s->prev_length -= 2; 2052c9083b85SXin LI do { 2053c9083b85SXin LI if (++s->strstart <= max_insert) { 2054c9083b85SXin LI INSERT_STRING(s, s->strstart, hash_head); 2055c9083b85SXin LI } 2056c9083b85SXin LI } while (--s->prev_length != 0); 2057c9083b85SXin LI s->match_available = 0; 2058c9083b85SXin LI s->match_length = MIN_MATCH-1; 2059c9083b85SXin LI s->strstart++; 2060c9083b85SXin LI 2061c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 2062c9083b85SXin LI 2063c9083b85SXin LI } else if (s->match_available) { 2064c9083b85SXin LI /* If there was no match at the previous position, output a 2065c9083b85SXin LI * single literal. If there was a match but the current match 2066c9083b85SXin LI * is longer, truncate the previous match to a single literal. 2067c9083b85SXin LI */ 2068c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart-1])); 2069c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart-1], bflush); 2070c9083b85SXin LI if (bflush) { 2071c9083b85SXin LI FLUSH_BLOCK_ONLY(s, 0); 2072c9083b85SXin LI } 2073c9083b85SXin LI s->strstart++; 2074c9083b85SXin LI s->lookahead--; 2075c9083b85SXin LI if (s->strm->avail_out == 0) return need_more; 2076c9083b85SXin LI } else { 2077c9083b85SXin LI /* There is no previous match to compare with, wait for 2078c9083b85SXin LI * the next step to decide. 2079c9083b85SXin LI */ 2080c9083b85SXin LI s->match_available = 1; 2081c9083b85SXin LI s->strstart++; 2082c9083b85SXin LI s->lookahead--; 2083c9083b85SXin LI } 2084c9083b85SXin LI } 2085c9083b85SXin LI Assert (flush != Z_NO_FLUSH, "no flush?"); 2086c9083b85SXin LI if (s->match_available) { 2087c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart-1])); 2088c9083b85SXin LI _tr_tally_lit(s, s->window[s->strstart-1], bflush); 2089c9083b85SXin LI s->match_available = 0; 2090c9083b85SXin LI } 2091c9083b85SXin LI s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 2092c9083b85SXin LI if (flush == Z_FINISH) { 2093c9083b85SXin LI FLUSH_BLOCK(s, 1); 2094c9083b85SXin LI return finish_done; 2095c9083b85SXin LI } 2096cd882207SXin LI if (s->sym_next) 2097c9083b85SXin LI FLUSH_BLOCK(s, 0); 2098c9083b85SXin LI return block_done; 2099c9083b85SXin LI } 2100c9083b85SXin LI #endif /* FASTEST */ 2101c9083b85SXin LI 2102c9083b85SXin LI /* =========================================================================== 2103c9083b85SXin LI * For Z_RLE, simply look for runs of bytes, generate matches only of distance 2104c9083b85SXin LI * one. Do not maintain a hash table. (It will be regenerated if this run of 2105c9083b85SXin LI * deflate switches away from Z_RLE.) 2106c9083b85SXin LI */ 2107c9083b85SXin LI local block_state deflate_rle(s, flush) 2108c9083b85SXin LI deflate_state *s; 2109c9083b85SXin LI int flush; 2110c9083b85SXin LI { 2111c9083b85SXin LI int bflush; /* set if current block must be flushed */ 2112c9083b85SXin LI uInt prev; /* byte at distance one to match */ 2113c9083b85SXin LI Bytef *scan, *strend; /* scan goes up to strend for length of run */ 2114c9083b85SXin LI 2115c9083b85SXin LI for (;;) { 2116c9083b85SXin LI /* Make sure that we always have enough lookahead, except 2117c9083b85SXin LI * at the end of the input file. We need MAX_MATCH bytes 2118c9083b85SXin LI * for the longest run, plus one for the unrolled loop. 2119c9083b85SXin LI */ 2120c9083b85SXin LI if (s->lookahead <= MAX_MATCH) { 2121c9083b85SXin LI fill_window(s); 2122c9083b85SXin LI if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 2123c9083b85SXin LI return need_more; 2124c9083b85SXin LI } 2125c9083b85SXin LI if (s->lookahead == 0) break; /* flush the current block */ 2126c9083b85SXin LI } 2127c9083b85SXin LI 2128c9083b85SXin LI /* See how many times the previous byte repeats */ 2129c9083b85SXin LI s->match_length = 0; 2130c9083b85SXin LI if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 2131c9083b85SXin LI scan = s->window + s->strstart - 1; 2132c9083b85SXin LI prev = *scan; 2133c9083b85SXin LI if (prev == *++scan && prev == *++scan && prev == *++scan) { 2134c9083b85SXin LI strend = s->window + s->strstart + MAX_MATCH; 2135c9083b85SXin LI do { 2136c9083b85SXin LI } while (prev == *++scan && prev == *++scan && 2137c9083b85SXin LI prev == *++scan && prev == *++scan && 2138c9083b85SXin LI prev == *++scan && prev == *++scan && 2139c9083b85SXin LI prev == *++scan && prev == *++scan && 2140c9083b85SXin LI scan < strend); 2141c9083b85SXin LI s->match_length = MAX_MATCH - (uInt)(strend - scan); 2142c9083b85SXin LI if (s->match_length > s->lookahead) 2143c9083b85SXin LI s->match_length = s->lookahead; 2144c9083b85SXin LI } 2145c9083b85SXin LI Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); 2146c9083b85SXin LI } 2147c9083b85SXin LI 2148c9083b85SXin LI /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 2149c9083b85SXin LI if (s->match_length >= MIN_MATCH) { 2150c9083b85SXin LI check_match(s, s->strstart, s->strstart - 1, s->match_length); 2151c9083b85SXin LI 2152c9083b85SXin LI _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 2153c9083b85SXin LI 2154c9083b85SXin LI s->lookahead -= s->match_length; 2155c9083b85SXin LI s->strstart += s->match_length; 2156c9083b85SXin LI s->match_length = 0; 2157c9083b85SXin LI } else { 2158c9083b85SXin LI /* No match, output a literal byte */ 2159c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 2160c9083b85SXin LI _tr_tally_lit (s, s->window[s->strstart], bflush); 2161c9083b85SXin LI s->lookahead--; 2162c9083b85SXin LI s->strstart++; 2163c9083b85SXin LI } 2164c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 2165c9083b85SXin LI } 2166c9083b85SXin LI s->insert = 0; 2167c9083b85SXin LI if (flush == Z_FINISH) { 2168c9083b85SXin LI FLUSH_BLOCK(s, 1); 2169c9083b85SXin LI return finish_done; 2170c9083b85SXin LI } 2171cd882207SXin LI if (s->sym_next) 2172c9083b85SXin LI FLUSH_BLOCK(s, 0); 2173c9083b85SXin LI return block_done; 2174c9083b85SXin LI } 2175c9083b85SXin LI 2176c9083b85SXin LI /* =========================================================================== 2177c9083b85SXin LI * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 2178c9083b85SXin LI * (It will be regenerated if this run of deflate switches away from Huffman.) 2179c9083b85SXin LI */ 2180c9083b85SXin LI local block_state deflate_huff(s, flush) 2181c9083b85SXin LI deflate_state *s; 2182c9083b85SXin LI int flush; 2183c9083b85SXin LI { 2184c9083b85SXin LI int bflush; /* set if current block must be flushed */ 2185c9083b85SXin LI 2186c9083b85SXin LI for (;;) { 2187c9083b85SXin LI /* Make sure that we have a literal to write. */ 2188c9083b85SXin LI if (s->lookahead == 0) { 2189c9083b85SXin LI fill_window(s); 2190c9083b85SXin LI if (s->lookahead == 0) { 2191c9083b85SXin LI if (flush == Z_NO_FLUSH) 2192c9083b85SXin LI return need_more; 2193c9083b85SXin LI break; /* flush the current block */ 2194c9083b85SXin LI } 2195c9083b85SXin LI } 2196c9083b85SXin LI 2197c9083b85SXin LI /* Output a literal byte */ 2198c9083b85SXin LI s->match_length = 0; 2199c9083b85SXin LI Tracevv((stderr,"%c", s->window[s->strstart])); 2200c9083b85SXin LI _tr_tally_lit (s, s->window[s->strstart], bflush); 2201c9083b85SXin LI s->lookahead--; 2202c9083b85SXin LI s->strstart++; 2203c9083b85SXin LI if (bflush) FLUSH_BLOCK(s, 0); 2204c9083b85SXin LI } 2205c9083b85SXin LI s->insert = 0; 2206c9083b85SXin LI if (flush == Z_FINISH) { 2207c9083b85SXin LI FLUSH_BLOCK(s, 1); 2208c9083b85SXin LI return finish_done; 2209c9083b85SXin LI } 2210cd882207SXin LI if (s->sym_next) 2211c9083b85SXin LI FLUSH_BLOCK(s, 0); 2212c9083b85SXin LI return block_done; 2213c9083b85SXin LI } 2214