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