Mercurial > hg > CbC > CbC_gcc
comparison zlib/deflate.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | ae3a4bfb450b |
children |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* deflate.c -- compress data using the deflation algorithm | 1 /* deflate.c -- compress data using the deflation algorithm |
2 * Copyright (C) 1995-2005 Jean-loup Gailly. | 2 * Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler |
3 * For conditions of distribution and use, see copyright notice in zlib.h | 3 * For conditions of distribution and use, see copyright notice in zlib.h |
4 */ | 4 */ |
5 | 5 |
6 /* | 6 /* |
7 * ALGORITHM | 7 * ALGORITHM |
35 * Thanks to many people for bug reports and testing. | 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 Format Specification". | 39 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". |
40 * Available in http://www.ietf.org/rfc/rfc1951.txt | 40 * Available in http://tools.ietf.org/html/rfc1951 |
41 * | 41 * |
42 * A description of the Rabin and Karp algorithm is given in the book | 42 * A description of the Rabin and Karp algorithm is given in the book |
43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. | 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. |
50 /* @(#) $Id: deflate.c,v 1.1.1.2 2002/03/11 21:53:23 tromey Exp $ */ | 50 /* @(#) $Id: deflate.c,v 1.1.1.2 2002/03/11 21:53:23 tromey Exp $ */ |
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.3 Copyright 1995-2005 Jean-loup Gailly "; | 55 " deflate 1.2.11 Copyright 1995-2017 Jean-loup Gailly and Mark Adler "; |
56 /* | 56 /* |
57 If you use the zlib library in a product, an acknowledgment is welcome | 57 If you use the zlib library in a product, an acknowledgment is welcome |
58 in the documentation of your product. If for some reason you cannot | 58 in the documentation of your product. If for some reason you cannot |
59 include such an acknowledgment, I would appreciate that you keep this | 59 include such an acknowledgment, I would appreciate that you keep this |
60 copyright string in the executable of your product. | 60 copyright string in the executable of your product. |
71 } block_state; | 71 } block_state; |
72 | 72 |
73 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); | 73 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); |
74 /* Compression function. Returns the block state after the call. */ | 74 /* Compression function. Returns the block state after the call. */ |
75 | 75 |
76 local int deflateStateCheck OF((z_streamp strm)); | |
77 local void slide_hash OF((deflate_state *s)); | |
76 local void fill_window OF((deflate_state *s)); | 78 local void fill_window OF((deflate_state *s)); |
77 local block_state deflate_stored OF((deflate_state *s, int flush)); | 79 local block_state deflate_stored OF((deflate_state *s, int flush)); |
78 local block_state deflate_fast OF((deflate_state *s, int flush)); | 80 local block_state deflate_fast OF((deflate_state *s, int flush)); |
79 #ifndef FASTEST | 81 #ifndef FASTEST |
80 local block_state deflate_slow OF((deflate_state *s, int flush)); | 82 local block_state deflate_slow OF((deflate_state *s, int flush)); |
81 #endif | 83 #endif |
84 local block_state deflate_rle OF((deflate_state *s, int flush)); | |
85 local block_state deflate_huff OF((deflate_state *s, int flush)); | |
82 local void lm_init OF((deflate_state *s)); | 86 local void lm_init OF((deflate_state *s)); |
83 local void putShortMSB OF((deflate_state *s, uInt b)); | 87 local void putShortMSB OF((deflate_state *s, uInt b)); |
84 local void flush_pending OF((z_streamp strm)); | 88 local void flush_pending OF((z_streamp strm)); |
85 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); | 89 local unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); |
86 #ifndef FASTEST | |
87 #ifdef ASMV | 90 #ifdef ASMV |
91 # pragma message("Assembler code may have bugs -- use at your own risk") | |
88 void match_init OF((void)); /* asm code initialization */ | 92 void match_init OF((void)); /* asm code initialization */ |
89 uInt longest_match OF((deflate_state *s, IPos cur_match)); | 93 uInt longest_match OF((deflate_state *s, IPos cur_match)); |
90 #else | 94 #else |
91 local uInt longest_match OF((deflate_state *s, IPos cur_match)); | 95 local uInt longest_match OF((deflate_state *s, IPos cur_match)); |
92 #endif | 96 #endif |
93 #endif | 97 |
94 local uInt longest_match_fast OF((deflate_state *s, IPos cur_match)); | 98 #ifdef ZLIB_DEBUG |
95 | |
96 #ifdef DEBUG | |
97 local void check_match OF((deflate_state *s, IPos start, IPos match, | 99 local void check_match OF((deflate_state *s, IPos start, IPos match, |
98 int length)); | 100 int length)); |
99 #endif | 101 #endif |
100 | 102 |
101 /* =========================================================================== | 103 /* =========================================================================== |
107 | 109 |
108 #ifndef TOO_FAR | 110 #ifndef TOO_FAR |
109 # define TOO_FAR 4096 | 111 # define TOO_FAR 4096 |
110 #endif | 112 #endif |
111 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ | 113 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ |
112 | |
113 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) | |
114 /* Minimum amount of lookahead, except at the end of the input file. | |
115 * See deflate.c for comments about the MIN_MATCH+1. | |
116 */ | |
117 | 114 |
118 /* Values for max_lazy_match, good_match and max_chain_length, depending on | 115 /* Values for max_lazy_match, good_match and max_chain_length, depending on |
119 * the desired pack level (0..9). The values given below have been tuned to | 116 * the desired pack level (0..9). The values given below have been tuned to |
120 * exclude worst case performance for pathological files. Better values may be | 117 * exclude worst case performance for pathological files. Better values may be |
121 * found for specific files. | 118 * found for specific files. |
152 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 | 149 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 |
153 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different | 150 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different |
154 * meaning. | 151 * meaning. |
155 */ | 152 */ |
156 | 153 |
157 #define EQUAL 0 | 154 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ |
158 /* result of memcmp for equal strings */ | 155 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0)) |
159 | |
160 #ifndef NO_DUMMY_DECL | |
161 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ | |
162 #endif | |
163 | 156 |
164 /* =========================================================================== | 157 /* =========================================================================== |
165 * Update a hash value with the given input byte | 158 * Update a hash value with the given input byte |
166 * IN assertion: all calls to to UPDATE_HASH are made with consecutive | 159 * IN assertion: all calls to UPDATE_HASH are made with consecutive input |
167 * input characters, so that a running hash key can be computed from the | 160 * characters, so that a running hash key can be computed from the previous |
168 * previous key instead of complete recalculation each time. | 161 * key instead of complete recalculation each time. |
169 */ | 162 */ |
170 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) | 163 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) |
171 | 164 |
172 | 165 |
173 /* =========================================================================== | 166 /* =========================================================================== |
174 * Insert string str in the dictionary and set match_head to the previous head | 167 * Insert string str in the dictionary and set match_head to the previous head |
175 * of the hash chain (the most recent string with same hash key). Return | 168 * of the hash chain (the most recent string with same hash key). Return |
176 * the previous length of the hash chain. | 169 * the previous length of the hash chain. |
177 * If this file is compiled with -DFASTEST, the compression level is forced | 170 * If this file is compiled with -DFASTEST, the compression level is forced |
178 * to 1, and no hash chains are maintained. | 171 * to 1, and no hash chains are maintained. |
179 * IN assertion: all calls to to INSERT_STRING are made with consecutive | 172 * IN assertion: all calls to INSERT_STRING are made with consecutive input |
180 * input characters and the first MIN_MATCH bytes of str are valid | 173 * characters and the first MIN_MATCH bytes of str are valid (except for |
181 * (except for the last MIN_MATCH-1 bytes of the input file). | 174 * the last MIN_MATCH-1 bytes of the input file). |
182 */ | 175 */ |
183 #ifdef FASTEST | 176 #ifdef FASTEST |
184 #define INSERT_STRING(s, str, match_head) \ | 177 #define INSERT_STRING(s, str, match_head) \ |
185 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ | 178 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ |
186 match_head = s->head[s->ins_h], \ | 179 match_head = s->head[s->ins_h], \ |
197 * prev[] will be initialized on the fly. | 190 * prev[] will be initialized on the fly. |
198 */ | 191 */ |
199 #define CLEAR_HASH(s) \ | 192 #define CLEAR_HASH(s) \ |
200 s->head[s->hash_size-1] = NIL; \ | 193 s->head[s->hash_size-1] = NIL; \ |
201 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); | 194 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); |
195 | |
196 /* =========================================================================== | |
197 * Slide the hash table when sliding the window down (could be avoided with 32 | |
198 * bit values at the expense of memory usage). We slide even when level == 0 to | |
199 * keep the hash table consistent if we switch back to level > 0 later. | |
200 */ | |
201 local void slide_hash(s) | |
202 deflate_state *s; | |
203 { | |
204 unsigned n, m; | |
205 Posf *p; | |
206 uInt wsize = s->w_size; | |
207 | |
208 n = s->hash_size; | |
209 p = &s->head[n]; | |
210 do { | |
211 m = *--p; | |
212 *p = (Pos)(m >= wsize ? m - wsize : NIL); | |
213 } while (--n); | |
214 n = wsize; | |
215 #ifndef FASTEST | |
216 p = &s->prev[n]; | |
217 do { | |
218 m = *--p; | |
219 *p = (Pos)(m >= wsize ? m - wsize : NIL); | |
220 /* If n is not on any hash chain, prev[n] is garbage but | |
221 * its value will never be used. | |
222 */ | |
223 } while (--n); | |
224 #endif | |
225 } | |
202 | 226 |
203 /* ========================================================================= */ | 227 /* ========================================================================= */ |
204 int ZEXPORT deflateInit_(strm, level, version, stream_size) | 228 int ZEXPORT deflateInit_(strm, level, version, stream_size) |
205 z_streamp strm; | 229 z_streamp strm; |
206 int level; | 230 int level; |
239 } | 263 } |
240 if (strm == Z_NULL) return Z_STREAM_ERROR; | 264 if (strm == Z_NULL) return Z_STREAM_ERROR; |
241 | 265 |
242 strm->msg = Z_NULL; | 266 strm->msg = Z_NULL; |
243 if (strm->zalloc == (alloc_func)0) { | 267 if (strm->zalloc == (alloc_func)0) { |
268 #ifdef Z_SOLO | |
269 return Z_STREAM_ERROR; | |
270 #else | |
244 strm->zalloc = zcalloc; | 271 strm->zalloc = zcalloc; |
245 strm->opaque = (voidpf)0; | 272 strm->opaque = (voidpf)0; |
246 } | 273 #endif |
247 if (strm->zfree == (free_func)0) strm->zfree = zcfree; | 274 } |
275 if (strm->zfree == (free_func)0) | |
276 #ifdef Z_SOLO | |
277 return Z_STREAM_ERROR; | |
278 #else | |
279 strm->zfree = zcfree; | |
280 #endif | |
248 | 281 |
249 #ifdef FASTEST | 282 #ifdef FASTEST |
250 if (level != 0) level = 1; | 283 if (level != 0) level = 1; |
251 #else | 284 #else |
252 if (level == Z_DEFAULT_COMPRESSION) level = 6; | 285 if (level == Z_DEFAULT_COMPRESSION) level = 6; |
262 windowBits -= 16; | 295 windowBits -= 16; |
263 } | 296 } |
264 #endif | 297 #endif |
265 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || | 298 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || |
266 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || | 299 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || |
267 strategy < 0 || strategy > Z_FIXED) { | 300 strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) { |
268 return Z_STREAM_ERROR; | 301 return Z_STREAM_ERROR; |
269 } | 302 } |
270 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ | 303 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ |
271 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); | 304 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); |
272 if (s == Z_NULL) return Z_MEM_ERROR; | 305 if (s == Z_NULL) return Z_MEM_ERROR; |
273 strm->state = (struct internal_state FAR *)s; | 306 strm->state = (struct internal_state FAR *)s; |
274 s->strm = strm; | 307 s->strm = strm; |
308 s->status = INIT_STATE; /* to pass state test in deflateReset() */ | |
275 | 309 |
276 s->wrap = wrap; | 310 s->wrap = wrap; |
277 s->gzhead = Z_NULL; | 311 s->gzhead = Z_NULL; |
278 s->w_bits = windowBits; | 312 s->w_bits = (uInt)windowBits; |
279 s->w_size = 1 << s->w_bits; | 313 s->w_size = 1 << s->w_bits; |
280 s->w_mask = s->w_size - 1; | 314 s->w_mask = s->w_size - 1; |
281 | 315 |
282 s->hash_bits = memLevel + 7; | 316 s->hash_bits = (uInt)memLevel + 7; |
283 s->hash_size = 1 << s->hash_bits; | 317 s->hash_size = 1 << s->hash_bits; |
284 s->hash_mask = s->hash_size - 1; | 318 s->hash_mask = s->hash_size - 1; |
285 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); | 319 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); |
286 | 320 |
287 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); | 321 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); |
288 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); | 322 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); |
289 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); | 323 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); |
290 | 324 |
325 s->high_water = 0; /* nothing written to s->window yet */ | |
326 | |
291 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ | 327 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ |
292 | 328 |
293 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); | 329 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); |
294 s->pending_buf = (uchf *) overlay; | 330 s->pending_buf = (uchf *) overlay; |
295 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); | 331 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); |
296 | 332 |
297 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || | 333 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || |
298 s->pending_buf == Z_NULL) { | 334 s->pending_buf == Z_NULL) { |
299 s->status = FINISH_STATE; | 335 s->status = FINISH_STATE; |
300 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); | 336 strm->msg = ERR_MSG(Z_MEM_ERROR); |
301 deflateEnd (strm); | 337 deflateEnd (strm); |
302 return Z_MEM_ERROR; | 338 return Z_MEM_ERROR; |
303 } | 339 } |
304 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); | 340 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); |
305 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; | 341 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; |
307 s->level = level; | 343 s->level = level; |
308 s->strategy = strategy; | 344 s->strategy = strategy; |
309 s->method = (Byte)method; | 345 s->method = (Byte)method; |
310 | 346 |
311 return deflateReset(strm); | 347 return deflateReset(strm); |
348 } | |
349 | |
350 /* ========================================================================= | |
351 * Check for a valid deflate stream state. Return 0 if ok, 1 if not. | |
352 */ | |
353 local int deflateStateCheck (strm) | |
354 z_streamp strm; | |
355 { | |
356 deflate_state *s; | |
357 if (strm == Z_NULL || | |
358 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) | |
359 return 1; | |
360 s = strm->state; | |
361 if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE && | |
362 #ifdef GZIP | |
363 s->status != GZIP_STATE && | |
364 #endif | |
365 s->status != EXTRA_STATE && | |
366 s->status != NAME_STATE && | |
367 s->status != COMMENT_STATE && | |
368 s->status != HCRC_STATE && | |
369 s->status != BUSY_STATE && | |
370 s->status != FINISH_STATE)) | |
371 return 1; | |
372 return 0; | |
312 } | 373 } |
313 | 374 |
314 /* ========================================================================= */ | 375 /* ========================================================================= */ |
315 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) | 376 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) |
316 z_streamp strm; | 377 z_streamp strm; |
317 const Bytef *dictionary; | 378 const Bytef *dictionary; |
318 uInt dictLength; | 379 uInt dictLength; |
319 { | 380 { |
320 deflate_state *s; | 381 deflate_state *s; |
321 uInt length = dictLength; | 382 uInt str, n; |
322 uInt n; | 383 int wrap; |
323 IPos hash_head = 0; | 384 unsigned avail; |
324 | 385 z_const unsigned char *next; |
325 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || | 386 |
326 strm->state->wrap == 2 || | 387 if (deflateStateCheck(strm) || dictionary == Z_NULL) |
327 (strm->state->wrap == 1 && strm->state->status != INIT_STATE)) | |
328 return Z_STREAM_ERROR; | 388 return Z_STREAM_ERROR; |
329 | |
330 s = strm->state; | 389 s = strm->state; |
331 if (s->wrap) | 390 wrap = s->wrap; |
391 if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) | |
392 return Z_STREAM_ERROR; | |
393 | |
394 /* when using zlib wrappers, compute Adler-32 for provided dictionary */ | |
395 if (wrap == 1) | |
332 strm->adler = adler32(strm->adler, dictionary, dictLength); | 396 strm->adler = adler32(strm->adler, dictionary, dictLength); |
333 | 397 s->wrap = 0; /* avoid computing Adler-32 in read_buf */ |
334 if (length < MIN_MATCH) return Z_OK; | 398 |
335 if (length > MAX_DIST(s)) { | 399 /* if dictionary would fill window, just replace the history */ |
336 length = MAX_DIST(s); | 400 if (dictLength >= s->w_size) { |
337 dictionary += dictLength - length; /* use the tail of the dictionary */ | 401 if (wrap == 0) { /* already empty otherwise */ |
338 } | 402 CLEAR_HASH(s); |
339 zmemcpy(s->window, dictionary, length); | 403 s->strstart = 0; |
340 s->strstart = length; | 404 s->block_start = 0L; |
341 s->block_start = (long)length; | 405 s->insert = 0; |
342 | 406 } |
343 /* Insert all strings in the hash table (except for the last two bytes). | 407 dictionary += dictLength - s->w_size; /* use the tail */ |
344 * s->lookahead stays null, so s->ins_h will be recomputed at the next | 408 dictLength = s->w_size; |
345 * call of fill_window. | 409 } |
346 */ | 410 |
347 s->ins_h = s->window[0]; | 411 /* insert dictionary into window and hash */ |
348 UPDATE_HASH(s, s->ins_h, s->window[1]); | 412 avail = strm->avail_in; |
349 for (n = 0; n <= length - MIN_MATCH; n++) { | 413 next = strm->next_in; |
350 INSERT_STRING(s, n, hash_head); | 414 strm->avail_in = dictLength; |
351 } | 415 strm->next_in = (z_const Bytef *)dictionary; |
352 if (hash_head) hash_head = 0; /* to make compiler happy */ | 416 fill_window(s); |
417 while (s->lookahead >= MIN_MATCH) { | |
418 str = s->strstart; | |
419 n = s->lookahead - (MIN_MATCH-1); | |
420 do { | |
421 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); | |
422 #ifndef FASTEST | |
423 s->prev[str & s->w_mask] = s->head[s->ins_h]; | |
424 #endif | |
425 s->head[s->ins_h] = (Pos)str; | |
426 str++; | |
427 } while (--n); | |
428 s->strstart = str; | |
429 s->lookahead = MIN_MATCH-1; | |
430 fill_window(s); | |
431 } | |
432 s->strstart += s->lookahead; | |
433 s->block_start = (long)s->strstart; | |
434 s->insert = s->lookahead; | |
435 s->lookahead = 0; | |
436 s->match_length = s->prev_length = MIN_MATCH-1; | |
437 s->match_available = 0; | |
438 strm->next_in = next; | |
439 strm->avail_in = avail; | |
440 s->wrap = wrap; | |
441 return Z_OK; | |
442 } | |
443 | |
444 /* ========================================================================= */ | |
445 int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength) | |
446 z_streamp strm; | |
447 Bytef *dictionary; | |
448 uInt *dictLength; | |
449 { | |
450 deflate_state *s; | |
451 uInt len; | |
452 | |
453 if (deflateStateCheck(strm)) | |
454 return Z_STREAM_ERROR; | |
455 s = strm->state; | |
456 len = s->strstart + s->lookahead; | |
457 if (len > s->w_size) | |
458 len = s->w_size; | |
459 if (dictionary != Z_NULL && len) | |
460 zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len); | |
461 if (dictLength != Z_NULL) | |
462 *dictLength = len; | |
463 return Z_OK; | |
464 } | |
465 | |
466 /* ========================================================================= */ | |
467 int ZEXPORT deflateResetKeep (strm) | |
468 z_streamp strm; | |
469 { | |
470 deflate_state *s; | |
471 | |
472 if (deflateStateCheck(strm)) { | |
473 return Z_STREAM_ERROR; | |
474 } | |
475 | |
476 strm->total_in = strm->total_out = 0; | |
477 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ | |
478 strm->data_type = Z_UNKNOWN; | |
479 | |
480 s = (deflate_state *)strm->state; | |
481 s->pending = 0; | |
482 s->pending_out = s->pending_buf; | |
483 | |
484 if (s->wrap < 0) { | |
485 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ | |
486 } | |
487 s->status = | |
488 #ifdef GZIP | |
489 s->wrap == 2 ? GZIP_STATE : | |
490 #endif | |
491 s->wrap ? INIT_STATE : BUSY_STATE; | |
492 strm->adler = | |
493 #ifdef GZIP | |
494 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : | |
495 #endif | |
496 adler32(0L, Z_NULL, 0); | |
497 s->last_flush = Z_NO_FLUSH; | |
498 | |
499 _tr_init(s); | |
500 | |
353 return Z_OK; | 501 return Z_OK; |
354 } | 502 } |
355 | 503 |
356 /* ========================================================================= */ | 504 /* ========================================================================= */ |
357 int ZEXPORT deflateReset (strm) | 505 int ZEXPORT deflateReset (strm) |
358 z_streamp strm; | 506 z_streamp strm; |
359 { | 507 { |
360 deflate_state *s; | 508 int ret; |
361 | 509 |
362 if (strm == Z_NULL || strm->state == Z_NULL || | 510 ret = deflateResetKeep(strm); |
363 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { | 511 if (ret == Z_OK) |
364 return Z_STREAM_ERROR; | 512 lm_init(strm->state); |
365 } | 513 return ret; |
366 | |
367 strm->total_in = strm->total_out = 0; | |
368 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ | |
369 strm->data_type = Z_UNKNOWN; | |
370 | |
371 s = (deflate_state *)strm->state; | |
372 s->pending = 0; | |
373 s->pending_out = s->pending_buf; | |
374 | |
375 if (s->wrap < 0) { | |
376 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ | |
377 } | |
378 s->status = s->wrap ? INIT_STATE : BUSY_STATE; | |
379 strm->adler = | |
380 #ifdef GZIP | |
381 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : | |
382 #endif | |
383 adler32(0L, Z_NULL, 0); | |
384 s->last_flush = Z_NO_FLUSH; | |
385 | |
386 _tr_init(s); | |
387 lm_init(s); | |
388 | |
389 return Z_OK; | |
390 } | 514 } |
391 | 515 |
392 /* ========================================================================= */ | 516 /* ========================================================================= */ |
393 int ZEXPORT deflateSetHeader (strm, head) | 517 int ZEXPORT deflateSetHeader (strm, head) |
394 z_streamp strm; | 518 z_streamp strm; |
395 gz_headerp head; | 519 gz_headerp head; |
396 { | 520 { |
397 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; | 521 if (deflateStateCheck(strm) || strm->state->wrap != 2) |
398 if (strm->state->wrap != 2) return Z_STREAM_ERROR; | 522 return Z_STREAM_ERROR; |
399 strm->state->gzhead = head; | 523 strm->state->gzhead = head; |
524 return Z_OK; | |
525 } | |
526 | |
527 /* ========================================================================= */ | |
528 int ZEXPORT deflatePending (strm, pending, bits) | |
529 unsigned *pending; | |
530 int *bits; | |
531 z_streamp strm; | |
532 { | |
533 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; | |
534 if (pending != Z_NULL) | |
535 *pending = strm->state->pending; | |
536 if (bits != Z_NULL) | |
537 *bits = strm->state->bi_valid; | |
400 return Z_OK; | 538 return Z_OK; |
401 } | 539 } |
402 | 540 |
403 /* ========================================================================= */ | 541 /* ========================================================================= */ |
404 int ZEXPORT deflatePrime (strm, bits, value) | 542 int ZEXPORT deflatePrime (strm, bits, value) |
405 z_streamp strm; | 543 z_streamp strm; |
406 int bits; | 544 int bits; |
407 int value; | 545 int value; |
408 { | 546 { |
409 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; | 547 deflate_state *s; |
410 strm->state->bi_valid = bits; | 548 int put; |
411 strm->state->bi_buf = (ush)(value & ((1 << bits) - 1)); | 549 |
550 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; | |
551 s = strm->state; | |
552 if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) | |
553 return Z_BUF_ERROR; | |
554 do { | |
555 put = Buf_size - s->bi_valid; | |
556 if (put > bits) | |
557 put = bits; | |
558 s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); | |
559 s->bi_valid += put; | |
560 _tr_flush_bits(s); | |
561 value >>= put; | |
562 bits -= put; | |
563 } while (bits); | |
412 return Z_OK; | 564 return Z_OK; |
413 } | 565 } |
414 | 566 |
415 /* ========================================================================= */ | 567 /* ========================================================================= */ |
416 int ZEXPORT deflateParams(strm, level, strategy) | 568 int ZEXPORT deflateParams(strm, level, strategy) |
418 int level; | 570 int level; |
419 int strategy; | 571 int strategy; |
420 { | 572 { |
421 deflate_state *s; | 573 deflate_state *s; |
422 compress_func func; | 574 compress_func func; |
423 int err = Z_OK; | 575 |
424 | 576 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; |
425 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; | |
426 s = strm->state; | 577 s = strm->state; |
427 | 578 |
428 #ifdef FASTEST | 579 #ifdef FASTEST |
429 if (level != 0) level = 1; | 580 if (level != 0) level = 1; |
430 #else | 581 #else |
433 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { | 584 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { |
434 return Z_STREAM_ERROR; | 585 return Z_STREAM_ERROR; |
435 } | 586 } |
436 func = configuration_table[s->level].func; | 587 func = configuration_table[s->level].func; |
437 | 588 |
438 if (func != configuration_table[level].func && strm->total_in != 0) { | 589 if ((strategy != s->strategy || func != configuration_table[level].func) && |
590 s->high_water) { | |
439 /* Flush the last buffer: */ | 591 /* Flush the last buffer: */ |
440 err = deflate(strm, Z_PARTIAL_FLUSH); | 592 int err = deflate(strm, Z_BLOCK); |
593 if (err == Z_STREAM_ERROR) | |
594 return err; | |
595 if (strm->avail_out == 0) | |
596 return Z_BUF_ERROR; | |
441 } | 597 } |
442 if (s->level != level) { | 598 if (s->level != level) { |
599 if (s->level == 0 && s->matches != 0) { | |
600 if (s->matches == 1) | |
601 slide_hash(s); | |
602 else | |
603 CLEAR_HASH(s); | |
604 s->matches = 0; | |
605 } | |
443 s->level = level; | 606 s->level = level; |
444 s->max_lazy_match = configuration_table[level].max_lazy; | 607 s->max_lazy_match = configuration_table[level].max_lazy; |
445 s->good_match = configuration_table[level].good_length; | 608 s->good_match = configuration_table[level].good_length; |
446 s->nice_match = configuration_table[level].nice_length; | 609 s->nice_match = configuration_table[level].nice_length; |
447 s->max_chain_length = configuration_table[level].max_chain; | 610 s->max_chain_length = configuration_table[level].max_chain; |
448 } | 611 } |
449 s->strategy = strategy; | 612 s->strategy = strategy; |
450 return err; | 613 return Z_OK; |
451 } | 614 } |
452 | 615 |
453 /* ========================================================================= */ | 616 /* ========================================================================= */ |
454 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) | 617 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) |
455 z_streamp strm; | 618 z_streamp strm; |
458 int nice_length; | 621 int nice_length; |
459 int max_chain; | 622 int max_chain; |
460 { | 623 { |
461 deflate_state *s; | 624 deflate_state *s; |
462 | 625 |
463 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; | 626 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; |
464 s = strm->state; | 627 s = strm->state; |
465 s->good_match = good_length; | 628 s->good_match = (uInt)good_length; |
466 s->max_lazy_match = max_lazy; | 629 s->max_lazy_match = (uInt)max_lazy; |
467 s->nice_match = nice_length; | 630 s->nice_match = nice_length; |
468 s->max_chain_length = max_chain; | 631 s->max_chain_length = (uInt)max_chain; |
469 return Z_OK; | 632 return Z_OK; |
470 } | 633 } |
471 | 634 |
472 /* ========================================================================= | 635 /* ========================================================================= |
473 * For the default windowBits of 15 and memLevel of 8, this function returns | 636 * For the default windowBits of 15 and memLevel of 8, this function returns |
479 * For any setting other than those defaults for windowBits and memLevel, | 642 * For any setting other than those defaults for windowBits and memLevel, |
480 * the value returned is a conservative worst case for the maximum expansion | 643 * the value returned is a conservative worst case for the maximum expansion |
481 * resulting from using fixed blocks instead of stored blocks, which deflate | 644 * resulting from using fixed blocks instead of stored blocks, which deflate |
482 * can emit on compressed data for some combinations of the parameters. | 645 * can emit on compressed data for some combinations of the parameters. |
483 * | 646 * |
484 * This function could be more sophisticated to provide closer upper bounds | 647 * This function could be more sophisticated to provide closer upper bounds for |
485 * for every combination of windowBits and memLevel, as well as wrap. | 648 * every combination of windowBits and memLevel. But even the conservative |
486 * But even the conservative upper bound of about 14% expansion does not | 649 * upper bound of about 14% expansion does not seem onerous for output buffer |
487 * seem onerous for output buffer allocation. | 650 * allocation. |
488 */ | 651 */ |
489 uLong ZEXPORT deflateBound(strm, sourceLen) | 652 uLong ZEXPORT deflateBound(strm, sourceLen) |
490 z_streamp strm; | 653 z_streamp strm; |
491 uLong sourceLen; | 654 uLong sourceLen; |
492 { | 655 { |
493 deflate_state *s; | 656 deflate_state *s; |
494 uLong destLen; | 657 uLong complen, wraplen; |
495 | 658 |
496 /* conservative upper bound */ | 659 /* conservative upper bound for compressed data */ |
497 destLen = sourceLen + | 660 complen = sourceLen + |
498 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11; | 661 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; |
499 | 662 |
500 /* if can't get parameters, return conservative bound */ | 663 /* if can't get parameters, return conservative bound plus zlib wrapper */ |
501 if (strm == Z_NULL || strm->state == Z_NULL) | 664 if (deflateStateCheck(strm)) |
502 return destLen; | 665 return complen + 6; |
666 | |
667 /* compute wrapper length */ | |
668 s = strm->state; | |
669 switch (s->wrap) { | |
670 case 0: /* raw deflate */ | |
671 wraplen = 0; | |
672 break; | |
673 case 1: /* zlib wrapper */ | |
674 wraplen = 6 + (s->strstart ? 4 : 0); | |
675 break; | |
676 #ifdef GZIP | |
677 case 2: /* gzip wrapper */ | |
678 wraplen = 18; | |
679 if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ | |
680 Bytef *str; | |
681 if (s->gzhead->extra != Z_NULL) | |
682 wraplen += 2 + s->gzhead->extra_len; | |
683 str = s->gzhead->name; | |
684 if (str != Z_NULL) | |
685 do { | |
686 wraplen++; | |
687 } while (*str++); | |
688 str = s->gzhead->comment; | |
689 if (str != Z_NULL) | |
690 do { | |
691 wraplen++; | |
692 } while (*str++); | |
693 if (s->gzhead->hcrc) | |
694 wraplen += 2; | |
695 } | |
696 break; | |
697 #endif | |
698 default: /* for compiler happiness */ | |
699 wraplen = 6; | |
700 } | |
503 | 701 |
504 /* if not default parameters, return conservative bound */ | 702 /* if not default parameters, return conservative bound */ |
505 s = strm->state; | |
506 if (s->w_bits != 15 || s->hash_bits != 8 + 7) | 703 if (s->w_bits != 15 || s->hash_bits != 8 + 7) |
507 return destLen; | 704 return complen + wraplen; |
508 | 705 |
509 /* default settings: return tight bound for that case */ | 706 /* default settings: return tight bound for that case */ |
510 return compressBound(sourceLen); | 707 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + |
708 (sourceLen >> 25) + 13 - 6 + wraplen; | |
511 } | 709 } |
512 | 710 |
513 /* ========================================================================= | 711 /* ========================================================================= |
514 * Put a short in the pending buffer. The 16-bit value is put in MSB order. | 712 * Put a short in the pending buffer. The 16-bit value is put in MSB order. |
515 * IN assertion: the stream state is correct and there is enough room in | 713 * IN assertion: the stream state is correct and there is enough room in |
522 put_byte(s, (Byte)(b >> 8)); | 720 put_byte(s, (Byte)(b >> 8)); |
523 put_byte(s, (Byte)(b & 0xff)); | 721 put_byte(s, (Byte)(b & 0xff)); |
524 } | 722 } |
525 | 723 |
526 /* ========================================================================= | 724 /* ========================================================================= |
527 * Flush as much pending output as possible. All deflate() output goes | 725 * Flush as much pending output as possible. All deflate() output, except for |
528 * through this function so some applications may wish to modify it | 726 * some deflate_stored() output, goes through this function so some |
529 * to avoid allocating a large strm->next_out buffer and copying into it. | 727 * applications may wish to modify it to avoid allocating a large |
530 * (See also read_buf()). | 728 * strm->next_out buffer and copying into it. (See also read_buf()). |
531 */ | 729 */ |
532 local void flush_pending(strm) | 730 local void flush_pending(strm) |
533 z_streamp strm; | 731 z_streamp strm; |
534 { | 732 { |
535 unsigned len = strm->state->pending; | 733 unsigned len; |
536 | 734 deflate_state *s = strm->state; |
735 | |
736 _tr_flush_bits(s); | |
737 len = s->pending; | |
537 if (len > strm->avail_out) len = strm->avail_out; | 738 if (len > strm->avail_out) len = strm->avail_out; |
538 if (len == 0) return; | 739 if (len == 0) return; |
539 | 740 |
540 zmemcpy(strm->next_out, strm->state->pending_out, len); | 741 zmemcpy(strm->next_out, s->pending_out, len); |
541 strm->next_out += len; | 742 strm->next_out += len; |
542 strm->state->pending_out += len; | 743 s->pending_out += len; |
543 strm->total_out += len; | 744 strm->total_out += len; |
544 strm->avail_out -= len; | 745 strm->avail_out -= len; |
545 strm->state->pending -= len; | 746 s->pending -= len; |
546 if (strm->state->pending == 0) { | 747 if (s->pending == 0) { |
547 strm->state->pending_out = strm->state->pending_buf; | 748 s->pending_out = s->pending_buf; |
548 } | 749 } |
549 } | 750 } |
751 | |
752 /* =========================================================================== | |
753 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1]. | |
754 */ | |
755 #define HCRC_UPDATE(beg) \ | |
756 do { \ | |
757 if (s->gzhead->hcrc && s->pending > (beg)) \ | |
758 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \ | |
759 s->pending - (beg)); \ | |
760 } while (0) | |
550 | 761 |
551 /* ========================================================================= */ | 762 /* ========================================================================= */ |
552 int ZEXPORT deflate (strm, flush) | 763 int ZEXPORT deflate (strm, flush) |
553 z_streamp strm; | 764 z_streamp strm; |
554 int flush; | 765 int flush; |
555 { | 766 { |
556 int old_flush; /* value of flush param for previous deflate call */ | 767 int old_flush; /* value of flush param for previous deflate call */ |
557 deflate_state *s; | 768 deflate_state *s; |
558 | 769 |
559 if (strm == Z_NULL || strm->state == Z_NULL || | 770 if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) { |
560 flush > Z_FINISH || flush < 0) { | |
561 return Z_STREAM_ERROR; | 771 return Z_STREAM_ERROR; |
562 } | 772 } |
563 s = strm->state; | 773 s = strm->state; |
564 | 774 |
565 if (strm->next_out == Z_NULL || | 775 if (strm->next_out == Z_NULL || |
566 (strm->next_in == Z_NULL && strm->avail_in != 0) || | 776 (strm->avail_in != 0 && strm->next_in == Z_NULL) || |
567 (s->status == FINISH_STATE && flush != Z_FINISH)) { | 777 (s->status == FINISH_STATE && flush != Z_FINISH)) { |
568 ERR_RETURN(strm, Z_STREAM_ERROR); | 778 ERR_RETURN(strm, Z_STREAM_ERROR); |
569 } | 779 } |
570 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); | 780 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); |
571 | 781 |
572 s->strm = strm; /* just in case */ | |
573 old_flush = s->last_flush; | 782 old_flush = s->last_flush; |
574 s->last_flush = flush; | 783 s->last_flush = flush; |
575 | |
576 /* Write the header */ | |
577 if (s->status == INIT_STATE) { | |
578 #ifdef GZIP | |
579 if (s->wrap == 2) { | |
580 strm->adler = crc32(0L, Z_NULL, 0); | |
581 put_byte(s, 31); | |
582 put_byte(s, 139); | |
583 put_byte(s, 8); | |
584 if (s->gzhead == NULL) { | |
585 put_byte(s, 0); | |
586 put_byte(s, 0); | |
587 put_byte(s, 0); | |
588 put_byte(s, 0); | |
589 put_byte(s, 0); | |
590 put_byte(s, s->level == 9 ? 2 : | |
591 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? | |
592 4 : 0)); | |
593 put_byte(s, OS_CODE); | |
594 s->status = BUSY_STATE; | |
595 } | |
596 else { | |
597 put_byte(s, (s->gzhead->text ? 1 : 0) + | |
598 (s->gzhead->hcrc ? 2 : 0) + | |
599 (s->gzhead->extra == Z_NULL ? 0 : 4) + | |
600 (s->gzhead->name == Z_NULL ? 0 : 8) + | |
601 (s->gzhead->comment == Z_NULL ? 0 : 16) | |
602 ); | |
603 put_byte(s, (Byte)(s->gzhead->time & 0xff)); | |
604 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); | |
605 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); | |
606 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); | |
607 put_byte(s, s->level == 9 ? 2 : | |
608 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? | |
609 4 : 0)); | |
610 put_byte(s, s->gzhead->os & 0xff); | |
611 if (s->gzhead->extra != NULL) { | |
612 put_byte(s, s->gzhead->extra_len & 0xff); | |
613 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); | |
614 } | |
615 if (s->gzhead->hcrc) | |
616 strm->adler = crc32(strm->adler, s->pending_buf, | |
617 s->pending); | |
618 s->gzindex = 0; | |
619 s->status = EXTRA_STATE; | |
620 } | |
621 } | |
622 else | |
623 #endif | |
624 { | |
625 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; | |
626 uInt level_flags; | |
627 | |
628 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) | |
629 level_flags = 0; | |
630 else if (s->level < 6) | |
631 level_flags = 1; | |
632 else if (s->level == 6) | |
633 level_flags = 2; | |
634 else | |
635 level_flags = 3; | |
636 header |= (level_flags << 6); | |
637 if (s->strstart != 0) header |= PRESET_DICT; | |
638 header += 31 - (header % 31); | |
639 | |
640 s->status = BUSY_STATE; | |
641 putShortMSB(s, header); | |
642 | |
643 /* Save the adler32 of the preset dictionary: */ | |
644 if (s->strstart != 0) { | |
645 putShortMSB(s, (uInt)(strm->adler >> 16)); | |
646 putShortMSB(s, (uInt)(strm->adler & 0xffff)); | |
647 } | |
648 strm->adler = adler32(0L, Z_NULL, 0); | |
649 } | |
650 } | |
651 #ifdef GZIP | |
652 if (s->status == EXTRA_STATE) { | |
653 if (s->gzhead->extra != NULL) { | |
654 uInt beg = s->pending; /* start of bytes to update crc */ | |
655 | |
656 while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { | |
657 if (s->pending == s->pending_buf_size) { | |
658 if (s->gzhead->hcrc && s->pending > beg) | |
659 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
660 s->pending - beg); | |
661 flush_pending(strm); | |
662 beg = s->pending; | |
663 if (s->pending == s->pending_buf_size) | |
664 break; | |
665 } | |
666 put_byte(s, s->gzhead->extra[s->gzindex]); | |
667 s->gzindex++; | |
668 } | |
669 if (s->gzhead->hcrc && s->pending > beg) | |
670 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
671 s->pending - beg); | |
672 if (s->gzindex == s->gzhead->extra_len) { | |
673 s->gzindex = 0; | |
674 s->status = NAME_STATE; | |
675 } | |
676 } | |
677 else | |
678 s->status = NAME_STATE; | |
679 } | |
680 if (s->status == NAME_STATE) { | |
681 if (s->gzhead->name != NULL) { | |
682 uInt beg = s->pending; /* start of bytes to update crc */ | |
683 int val; | |
684 | |
685 do { | |
686 if (s->pending == s->pending_buf_size) { | |
687 if (s->gzhead->hcrc && s->pending > beg) | |
688 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
689 s->pending - beg); | |
690 flush_pending(strm); | |
691 beg = s->pending; | |
692 if (s->pending == s->pending_buf_size) { | |
693 val = 1; | |
694 break; | |
695 } | |
696 } | |
697 val = s->gzhead->name[s->gzindex++]; | |
698 put_byte(s, val); | |
699 } while (val != 0); | |
700 if (s->gzhead->hcrc && s->pending > beg) | |
701 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
702 s->pending - beg); | |
703 if (val == 0) { | |
704 s->gzindex = 0; | |
705 s->status = COMMENT_STATE; | |
706 } | |
707 } | |
708 else | |
709 s->status = COMMENT_STATE; | |
710 } | |
711 if (s->status == COMMENT_STATE) { | |
712 if (s->gzhead->comment != NULL) { | |
713 uInt beg = s->pending; /* start of bytes to update crc */ | |
714 int val; | |
715 | |
716 do { | |
717 if (s->pending == s->pending_buf_size) { | |
718 if (s->gzhead->hcrc && s->pending > beg) | |
719 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
720 s->pending - beg); | |
721 flush_pending(strm); | |
722 beg = s->pending; | |
723 if (s->pending == s->pending_buf_size) { | |
724 val = 1; | |
725 break; | |
726 } | |
727 } | |
728 val = s->gzhead->comment[s->gzindex++]; | |
729 put_byte(s, val); | |
730 } while (val != 0); | |
731 if (s->gzhead->hcrc && s->pending > beg) | |
732 strm->adler = crc32(strm->adler, s->pending_buf + beg, | |
733 s->pending - beg); | |
734 if (val == 0) | |
735 s->status = HCRC_STATE; | |
736 } | |
737 else | |
738 s->status = HCRC_STATE; | |
739 } | |
740 if (s->status == HCRC_STATE) { | |
741 if (s->gzhead->hcrc) { | |
742 if (s->pending + 2 > s->pending_buf_size) | |
743 flush_pending(strm); | |
744 if (s->pending + 2 <= s->pending_buf_size) { | |
745 put_byte(s, (Byte)(strm->adler & 0xff)); | |
746 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); | |
747 strm->adler = crc32(0L, Z_NULL, 0); | |
748 s->status = BUSY_STATE; | |
749 } | |
750 } | |
751 else | |
752 s->status = BUSY_STATE; | |
753 } | |
754 #endif | |
755 | 784 |
756 /* Flush as much pending output as possible */ | 785 /* Flush as much pending output as possible */ |
757 if (s->pending != 0) { | 786 if (s->pending != 0) { |
758 flush_pending(strm); | 787 flush_pending(strm); |
759 if (strm->avail_out == 0) { | 788 if (strm->avail_out == 0) { |
769 | 798 |
770 /* Make sure there is something to do and avoid duplicate consecutive | 799 /* Make sure there is something to do and avoid duplicate consecutive |
771 * flushes. For repeated and useless calls with Z_FINISH, we keep | 800 * flushes. For repeated and useless calls with Z_FINISH, we keep |
772 * returning Z_STREAM_END instead of Z_BUF_ERROR. | 801 * returning Z_STREAM_END instead of Z_BUF_ERROR. |
773 */ | 802 */ |
774 } else if (strm->avail_in == 0 && flush <= old_flush && | 803 } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && |
775 flush != Z_FINISH) { | 804 flush != Z_FINISH) { |
776 ERR_RETURN(strm, Z_BUF_ERROR); | 805 ERR_RETURN(strm, Z_BUF_ERROR); |
777 } | 806 } |
778 | 807 |
779 /* User must not provide more input after the first FINISH: */ | 808 /* User must not provide more input after the first FINISH: */ |
780 if (s->status == FINISH_STATE && strm->avail_in != 0) { | 809 if (s->status == FINISH_STATE && strm->avail_in != 0) { |
781 ERR_RETURN(strm, Z_BUF_ERROR); | 810 ERR_RETURN(strm, Z_BUF_ERROR); |
782 } | 811 } |
812 | |
813 /* Write the header */ | |
814 if (s->status == INIT_STATE) { | |
815 /* zlib header */ | |
816 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; | |
817 uInt level_flags; | |
818 | |
819 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) | |
820 level_flags = 0; | |
821 else if (s->level < 6) | |
822 level_flags = 1; | |
823 else if (s->level == 6) | |
824 level_flags = 2; | |
825 else | |
826 level_flags = 3; | |
827 header |= (level_flags << 6); | |
828 if (s->strstart != 0) header |= PRESET_DICT; | |
829 header += 31 - (header % 31); | |
830 | |
831 putShortMSB(s, header); | |
832 | |
833 /* Save the adler32 of the preset dictionary: */ | |
834 if (s->strstart != 0) { | |
835 putShortMSB(s, (uInt)(strm->adler >> 16)); | |
836 putShortMSB(s, (uInt)(strm->adler & 0xffff)); | |
837 } | |
838 strm->adler = adler32(0L, Z_NULL, 0); | |
839 s->status = BUSY_STATE; | |
840 | |
841 /* Compression must start with an empty pending buffer */ | |
842 flush_pending(strm); | |
843 if (s->pending != 0) { | |
844 s->last_flush = -1; | |
845 return Z_OK; | |
846 } | |
847 } | |
848 #ifdef GZIP | |
849 if (s->status == GZIP_STATE) { | |
850 /* gzip header */ | |
851 strm->adler = crc32(0L, Z_NULL, 0); | |
852 put_byte(s, 31); | |
853 put_byte(s, 139); | |
854 put_byte(s, 8); | |
855 if (s->gzhead == Z_NULL) { | |
856 put_byte(s, 0); | |
857 put_byte(s, 0); | |
858 put_byte(s, 0); | |
859 put_byte(s, 0); | |
860 put_byte(s, 0); | |
861 put_byte(s, s->level == 9 ? 2 : | |
862 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? | |
863 4 : 0)); | |
864 put_byte(s, OS_CODE); | |
865 s->status = BUSY_STATE; | |
866 | |
867 /* Compression must start with an empty pending buffer */ | |
868 flush_pending(strm); | |
869 if (s->pending != 0) { | |
870 s->last_flush = -1; | |
871 return Z_OK; | |
872 } | |
873 } | |
874 else { | |
875 put_byte(s, (s->gzhead->text ? 1 : 0) + | |
876 (s->gzhead->hcrc ? 2 : 0) + | |
877 (s->gzhead->extra == Z_NULL ? 0 : 4) + | |
878 (s->gzhead->name == Z_NULL ? 0 : 8) + | |
879 (s->gzhead->comment == Z_NULL ? 0 : 16) | |
880 ); | |
881 put_byte(s, (Byte)(s->gzhead->time & 0xff)); | |
882 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); | |
883 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); | |
884 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); | |
885 put_byte(s, s->level == 9 ? 2 : | |
886 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? | |
887 4 : 0)); | |
888 put_byte(s, s->gzhead->os & 0xff); | |
889 if (s->gzhead->extra != Z_NULL) { | |
890 put_byte(s, s->gzhead->extra_len & 0xff); | |
891 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); | |
892 } | |
893 if (s->gzhead->hcrc) | |
894 strm->adler = crc32(strm->adler, s->pending_buf, | |
895 s->pending); | |
896 s->gzindex = 0; | |
897 s->status = EXTRA_STATE; | |
898 } | |
899 } | |
900 if (s->status == EXTRA_STATE) { | |
901 if (s->gzhead->extra != Z_NULL) { | |
902 ulg beg = s->pending; /* start of bytes to update crc */ | |
903 uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex; | |
904 while (s->pending + left > s->pending_buf_size) { | |
905 uInt copy = s->pending_buf_size - s->pending; | |
906 zmemcpy(s->pending_buf + s->pending, | |
907 s->gzhead->extra + s->gzindex, copy); | |
908 s->pending = s->pending_buf_size; | |
909 HCRC_UPDATE(beg); | |
910 s->gzindex += copy; | |
911 flush_pending(strm); | |
912 if (s->pending != 0) { | |
913 s->last_flush = -1; | |
914 return Z_OK; | |
915 } | |
916 beg = 0; | |
917 left -= copy; | |
918 } | |
919 zmemcpy(s->pending_buf + s->pending, | |
920 s->gzhead->extra + s->gzindex, left); | |
921 s->pending += left; | |
922 HCRC_UPDATE(beg); | |
923 s->gzindex = 0; | |
924 } | |
925 s->status = NAME_STATE; | |
926 } | |
927 if (s->status == NAME_STATE) { | |
928 if (s->gzhead->name != Z_NULL) { | |
929 ulg beg = s->pending; /* start of bytes to update crc */ | |
930 int val; | |
931 do { | |
932 if (s->pending == s->pending_buf_size) { | |
933 HCRC_UPDATE(beg); | |
934 flush_pending(strm); | |
935 if (s->pending != 0) { | |
936 s->last_flush = -1; | |
937 return Z_OK; | |
938 } | |
939 beg = 0; | |
940 } | |
941 val = s->gzhead->name[s->gzindex++]; | |
942 put_byte(s, val); | |
943 } while (val != 0); | |
944 HCRC_UPDATE(beg); | |
945 s->gzindex = 0; | |
946 } | |
947 s->status = COMMENT_STATE; | |
948 } | |
949 if (s->status == COMMENT_STATE) { | |
950 if (s->gzhead->comment != Z_NULL) { | |
951 ulg beg = s->pending; /* start of bytes to update crc */ | |
952 int val; | |
953 do { | |
954 if (s->pending == s->pending_buf_size) { | |
955 HCRC_UPDATE(beg); | |
956 flush_pending(strm); | |
957 if (s->pending != 0) { | |
958 s->last_flush = -1; | |
959 return Z_OK; | |
960 } | |
961 beg = 0; | |
962 } | |
963 val = s->gzhead->comment[s->gzindex++]; | |
964 put_byte(s, val); | |
965 } while (val != 0); | |
966 HCRC_UPDATE(beg); | |
967 } | |
968 s->status = HCRC_STATE; | |
969 } | |
970 if (s->status == HCRC_STATE) { | |
971 if (s->gzhead->hcrc) { | |
972 if (s->pending + 2 > s->pending_buf_size) { | |
973 flush_pending(strm); | |
974 if (s->pending != 0) { | |
975 s->last_flush = -1; | |
976 return Z_OK; | |
977 } | |
978 } | |
979 put_byte(s, (Byte)(strm->adler & 0xff)); | |
980 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); | |
981 strm->adler = crc32(0L, Z_NULL, 0); | |
982 } | |
983 s->status = BUSY_STATE; | |
984 | |
985 /* Compression must start with an empty pending buffer */ | |
986 flush_pending(strm); | |
987 if (s->pending != 0) { | |
988 s->last_flush = -1; | |
989 return Z_OK; | |
990 } | |
991 } | |
992 #endif | |
783 | 993 |
784 /* Start a new block or continue the current one. | 994 /* Start a new block or continue the current one. |
785 */ | 995 */ |
786 if (strm->avail_in != 0 || s->lookahead != 0 || | 996 if (strm->avail_in != 0 || s->lookahead != 0 || |
787 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { | 997 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { |
788 block_state bstate; | 998 block_state bstate; |
789 | 999 |
790 bstate = (*(configuration_table[s->level].func))(s, flush); | 1000 bstate = s->level == 0 ? deflate_stored(s, flush) : |
1001 s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : | |
1002 s->strategy == Z_RLE ? deflate_rle(s, flush) : | |
1003 (*(configuration_table[s->level].func))(s, flush); | |
791 | 1004 |
792 if (bstate == finish_started || bstate == finish_done) { | 1005 if (bstate == finish_started || bstate == finish_done) { |
793 s->status = FINISH_STATE; | 1006 s->status = FINISH_STATE; |
794 } | 1007 } |
795 if (bstate == need_more || bstate == finish_started) { | 1008 if (bstate == need_more || bstate == finish_started) { |
806 */ | 1019 */ |
807 } | 1020 } |
808 if (bstate == block_done) { | 1021 if (bstate == block_done) { |
809 if (flush == Z_PARTIAL_FLUSH) { | 1022 if (flush == Z_PARTIAL_FLUSH) { |
810 _tr_align(s); | 1023 _tr_align(s); |
811 } else { /* FULL_FLUSH or SYNC_FLUSH */ | 1024 } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ |
812 _tr_stored_block(s, (char*)0, 0L, 0); | 1025 _tr_stored_block(s, (char*)0, 0L, 0); |
813 /* For a full flush, this empty block will be recognized | 1026 /* For a full flush, this empty block will be recognized |
814 * as a special marker by inflate_sync(). | 1027 * as a special marker by inflate_sync(). |
815 */ | 1028 */ |
816 if (flush == Z_FULL_FLUSH) { | 1029 if (flush == Z_FULL_FLUSH) { |
817 CLEAR_HASH(s); /* forget history */ | 1030 CLEAR_HASH(s); /* forget history */ |
1031 if (s->lookahead == 0) { | |
1032 s->strstart = 0; | |
1033 s->block_start = 0L; | |
1034 s->insert = 0; | |
1035 } | |
818 } | 1036 } |
819 } | 1037 } |
820 flush_pending(strm); | 1038 flush_pending(strm); |
821 if (strm->avail_out == 0) { | 1039 if (strm->avail_out == 0) { |
822 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ | 1040 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ |
823 return Z_OK; | 1041 return Z_OK; |
824 } | 1042 } |
825 } | 1043 } |
826 } | 1044 } |
827 Assert(strm->avail_out > 0, "bug2"); | |
828 | 1045 |
829 if (flush != Z_FINISH) return Z_OK; | 1046 if (flush != Z_FINISH) return Z_OK; |
830 if (s->wrap <= 0) return Z_STREAM_END; | 1047 if (s->wrap <= 0) return Z_STREAM_END; |
831 | 1048 |
832 /* Write the trailer */ | 1049 /* Write the trailer */ |
859 int ZEXPORT deflateEnd (strm) | 1076 int ZEXPORT deflateEnd (strm) |
860 z_streamp strm; | 1077 z_streamp strm; |
861 { | 1078 { |
862 int status; | 1079 int status; |
863 | 1080 |
864 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; | 1081 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; |
865 | 1082 |
866 status = strm->state->status; | 1083 status = strm->state->status; |
867 if (status != INIT_STATE && | |
868 status != EXTRA_STATE && | |
869 status != NAME_STATE && | |
870 status != COMMENT_STATE && | |
871 status != HCRC_STATE && | |
872 status != BUSY_STATE && | |
873 status != FINISH_STATE) { | |
874 return Z_STREAM_ERROR; | |
875 } | |
876 | 1084 |
877 /* Deallocate in reverse order of allocations: */ | 1085 /* Deallocate in reverse order of allocations: */ |
878 TRY_FREE(strm, strm->state->pending_buf); | 1086 TRY_FREE(strm, strm->state->pending_buf); |
879 TRY_FREE(strm, strm->state->head); | 1087 TRY_FREE(strm, strm->state->head); |
880 TRY_FREE(strm, strm->state->prev); | 1088 TRY_FREE(strm, strm->state->prev); |
901 deflate_state *ds; | 1109 deflate_state *ds; |
902 deflate_state *ss; | 1110 deflate_state *ss; |
903 ushf *overlay; | 1111 ushf *overlay; |
904 | 1112 |
905 | 1113 |
906 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { | 1114 if (deflateStateCheck(source) || dest == Z_NULL) { |
907 return Z_STREAM_ERROR; | 1115 return Z_STREAM_ERROR; |
908 } | 1116 } |
909 | 1117 |
910 ss = source->state; | 1118 ss = source->state; |
911 | 1119 |
912 zmemcpy(dest, source, sizeof(z_stream)); | 1120 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); |
913 | 1121 |
914 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); | 1122 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); |
915 if (ds == Z_NULL) return Z_MEM_ERROR; | 1123 if (ds == Z_NULL) return Z_MEM_ERROR; |
916 dest->state = (struct internal_state FAR *) ds; | 1124 dest->state = (struct internal_state FAR *) ds; |
917 zmemcpy(ds, ss, sizeof(deflate_state)); | 1125 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); |
918 ds->strm = dest; | 1126 ds->strm = dest; |
919 | 1127 |
920 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); | 1128 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); |
921 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); | 1129 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); |
922 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); | 1130 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); |
928 deflateEnd (dest); | 1136 deflateEnd (dest); |
929 return Z_MEM_ERROR; | 1137 return Z_MEM_ERROR; |
930 } | 1138 } |
931 /* following zmemcpy do not work for 16-bit MSDOS */ | 1139 /* following zmemcpy do not work for 16-bit MSDOS */ |
932 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); | 1140 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); |
933 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); | 1141 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); |
934 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); | 1142 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); |
935 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); | 1143 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); |
936 | 1144 |
937 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); | 1145 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); |
938 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); | 1146 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); |
939 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; | 1147 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; |
951 * and total number of bytes read. All deflate() input goes through | 1159 * and total number of bytes read. All deflate() input goes through |
952 * this function so some applications may wish to modify it to avoid | 1160 * this function so some applications may wish to modify it to avoid |
953 * allocating a large strm->next_in buffer and copying from it. | 1161 * allocating a large strm->next_in buffer and copying from it. |
954 * (See also flush_pending()). | 1162 * (See also flush_pending()). |
955 */ | 1163 */ |
956 local int read_buf(strm, buf, size) | 1164 local unsigned read_buf(strm, buf, size) |
957 z_streamp strm; | 1165 z_streamp strm; |
958 Bytef *buf; | 1166 Bytef *buf; |
959 unsigned size; | 1167 unsigned size; |
960 { | 1168 { |
961 unsigned len = strm->avail_in; | 1169 unsigned len = strm->avail_in; |
963 if (len > size) len = size; | 1171 if (len > size) len = size; |
964 if (len == 0) return 0; | 1172 if (len == 0) return 0; |
965 | 1173 |
966 strm->avail_in -= len; | 1174 strm->avail_in -= len; |
967 | 1175 |
1176 zmemcpy(buf, strm->next_in, len); | |
968 if (strm->state->wrap == 1) { | 1177 if (strm->state->wrap == 1) { |
969 strm->adler = adler32(strm->adler, strm->next_in, len); | 1178 strm->adler = adler32(strm->adler, buf, len); |
970 } | 1179 } |
971 #ifdef GZIP | 1180 #ifdef GZIP |
972 else if (strm->state->wrap == 2) { | 1181 else if (strm->state->wrap == 2) { |
973 strm->adler = crc32(strm->adler, strm->next_in, len); | 1182 strm->adler = crc32(strm->adler, buf, len); |
974 } | 1183 } |
975 #endif | 1184 #endif |
976 zmemcpy(buf, strm->next_in, len); | |
977 strm->next_in += len; | 1185 strm->next_in += len; |
978 strm->total_in += len; | 1186 strm->total_in += len; |
979 | 1187 |
980 return (int)len; | 1188 return len; |
981 } | 1189 } |
982 | 1190 |
983 /* =========================================================================== | 1191 /* =========================================================================== |
984 * Initialize the "longest match" routines for a new zlib stream | 1192 * Initialize the "longest match" routines for a new zlib stream |
985 */ | 1193 */ |
998 s->max_chain_length = configuration_table[s->level].max_chain; | 1206 s->max_chain_length = configuration_table[s->level].max_chain; |
999 | 1207 |
1000 s->strstart = 0; | 1208 s->strstart = 0; |
1001 s->block_start = 0L; | 1209 s->block_start = 0L; |
1002 s->lookahead = 0; | 1210 s->lookahead = 0; |
1211 s->insert = 0; | |
1003 s->match_length = s->prev_length = MIN_MATCH-1; | 1212 s->match_length = s->prev_length = MIN_MATCH-1; |
1004 s->match_available = 0; | 1213 s->match_available = 0; |
1005 s->ins_h = 0; | 1214 s->ins_h = 0; |
1006 #ifndef FASTEST | 1215 #ifndef FASTEST |
1007 #ifdef ASMV | 1216 #ifdef ASMV |
1028 deflate_state *s; | 1237 deflate_state *s; |
1029 IPos cur_match; /* current match */ | 1238 IPos cur_match; /* current match */ |
1030 { | 1239 { |
1031 unsigned chain_length = s->max_chain_length;/* max hash chain length */ | 1240 unsigned chain_length = s->max_chain_length;/* max hash chain length */ |
1032 register Bytef *scan = s->window + s->strstart; /* current string */ | 1241 register Bytef *scan = s->window + s->strstart; /* current string */ |
1033 register Bytef *match; /* matched string */ | 1242 register Bytef *match; /* matched string */ |
1034 register int len; /* length of current match */ | 1243 register int len; /* length of current match */ |
1035 int best_len = s->prev_length; /* best match length so far */ | 1244 int best_len = (int)s->prev_length; /* best match length so far */ |
1036 int nice_match = s->nice_match; /* stop if match long enough */ | 1245 int nice_match = s->nice_match; /* stop if match long enough */ |
1037 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? | 1246 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? |
1038 s->strstart - (IPos)MAX_DIST(s) : NIL; | 1247 s->strstart - (IPos)MAX_DIST(s) : NIL; |
1039 /* Stop when cur_match becomes <= limit. To simplify the code, | 1248 /* Stop when cur_match becomes <= limit. To simplify the code, |
1040 * we prevent matches with the string of window index 0. | 1249 * we prevent matches with the string of window index 0. |
1065 chain_length >>= 2; | 1274 chain_length >>= 2; |
1066 } | 1275 } |
1067 /* Do not look for matches beyond the end of the input. This is necessary | 1276 /* Do not look for matches beyond the end of the input. This is necessary |
1068 * to make deflate deterministic. | 1277 * to make deflate deterministic. |
1069 */ | 1278 */ |
1070 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; | 1279 if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead; |
1071 | 1280 |
1072 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); | 1281 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); |
1073 | 1282 |
1074 do { | 1283 do { |
1075 Assert(cur_match < s->strstart, "no future"); | 1284 Assert(cur_match < s->strstart, "no future"); |
1165 | 1374 |
1166 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; | 1375 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; |
1167 return s->lookahead; | 1376 return s->lookahead; |
1168 } | 1377 } |
1169 #endif /* ASMV */ | 1378 #endif /* ASMV */ |
1170 #endif /* FASTEST */ | 1379 |
1380 #else /* FASTEST */ | |
1171 | 1381 |
1172 /* --------------------------------------------------------------------------- | 1382 /* --------------------------------------------------------------------------- |
1173 * Optimized version for level == 1 or strategy == Z_RLE only | 1383 * Optimized version for FASTEST only |
1174 */ | 1384 */ |
1175 local uInt longest_match_fast(s, cur_match) | 1385 local uInt longest_match(s, cur_match) |
1176 deflate_state *s; | 1386 deflate_state *s; |
1177 IPos cur_match; /* current match */ | 1387 IPos cur_match; /* current match */ |
1178 { | 1388 { |
1179 register Bytef *scan = s->window + s->strstart; /* current string */ | 1389 register Bytef *scan = s->window + s->strstart; /* current string */ |
1180 register Bytef *match; /* matched string */ | 1390 register Bytef *match; /* matched string */ |
1223 | 1433 |
1224 s->match_start = cur_match; | 1434 s->match_start = cur_match; |
1225 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; | 1435 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; |
1226 } | 1436 } |
1227 | 1437 |
1228 #ifdef DEBUG | 1438 #endif /* FASTEST */ |
1439 | |
1440 #ifdef ZLIB_DEBUG | |
1441 | |
1442 #define EQUAL 0 | |
1443 /* result of memcmp for equal strings */ | |
1444 | |
1229 /* =========================================================================== | 1445 /* =========================================================================== |
1230 * Check that the match at match_start is indeed a match. | 1446 * Check that the match at match_start is indeed a match. |
1231 */ | 1447 */ |
1232 local void check_match(s, start, match, length) | 1448 local void check_match(s, start, match, length) |
1233 deflate_state *s; | 1449 deflate_state *s; |
1249 do { putc(s->window[start++], stderr); } while (--length != 0); | 1465 do { putc(s->window[start++], stderr); } while (--length != 0); |
1250 } | 1466 } |
1251 } | 1467 } |
1252 #else | 1468 #else |
1253 # define check_match(s, start, match, length) | 1469 # define check_match(s, start, match, length) |
1254 #endif /* DEBUG */ | 1470 #endif /* ZLIB_DEBUG */ |
1255 | 1471 |
1256 /* =========================================================================== | 1472 /* =========================================================================== |
1257 * Fill the window when the lookahead becomes insufficient. | 1473 * Fill the window when the lookahead becomes insufficient. |
1258 * Updates strstart and lookahead. | 1474 * Updates strstart and lookahead. |
1259 * | 1475 * |
1264 * option -- not supported here). | 1480 * option -- not supported here). |
1265 */ | 1481 */ |
1266 local void fill_window(s) | 1482 local void fill_window(s) |
1267 deflate_state *s; | 1483 deflate_state *s; |
1268 { | 1484 { |
1269 register unsigned n, m; | 1485 unsigned n; |
1270 register Posf *p; | |
1271 unsigned more; /* Amount of free space at the end of the window. */ | 1486 unsigned more; /* Amount of free space at the end of the window. */ |
1272 uInt wsize = s->w_size; | 1487 uInt wsize = s->w_size; |
1488 | |
1489 Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); | |
1273 | 1490 |
1274 do { | 1491 do { |
1275 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); | 1492 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); |
1276 | 1493 |
1277 /* Deal with !@#$% 64K limit: */ | 1494 /* Deal with !@#$% 64K limit: */ |
1290 /* If the window is almost full and there is insufficient lookahead, | 1507 /* If the window is almost full and there is insufficient lookahead, |
1291 * move the upper half to the lower one to make room in the upper half. | 1508 * move the upper half to the lower one to make room in the upper half. |
1292 */ | 1509 */ |
1293 if (s->strstart >= wsize+MAX_DIST(s)) { | 1510 if (s->strstart >= wsize+MAX_DIST(s)) { |
1294 | 1511 |
1295 zmemcpy(s->window, s->window+wsize, (unsigned)wsize); | 1512 zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more); |
1296 s->match_start -= wsize; | 1513 s->match_start -= wsize; |
1297 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ | 1514 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ |
1298 s->block_start -= (long) wsize; | 1515 s->block_start -= (long) wsize; |
1299 | 1516 slide_hash(s); |
1300 /* Slide the hash table (could be avoided with 32 bit values | |
1301 at the expense of memory usage). We slide even when level == 0 | |
1302 to keep the hash table consistent if we switch back to level > 0 | |
1303 later. (Using level 0 permanently is not an optimal usage of | |
1304 zlib, so we don't care about this pathological case.) | |
1305 */ | |
1306 /* %%% avoid this when Z_RLE */ | |
1307 n = s->hash_size; | |
1308 p = &s->head[n]; | |
1309 do { | |
1310 m = *--p; | |
1311 *p = (Pos)(m >= wsize ? m-wsize : NIL); | |
1312 } while (--n); | |
1313 | |
1314 n = wsize; | |
1315 #ifndef FASTEST | |
1316 p = &s->prev[n]; | |
1317 do { | |
1318 m = *--p; | |
1319 *p = (Pos)(m >= wsize ? m-wsize : NIL); | |
1320 /* If n is not on any hash chain, prev[n] is garbage but | |
1321 * its value will never be used. | |
1322 */ | |
1323 } while (--n); | |
1324 #endif | |
1325 more += wsize; | 1517 more += wsize; |
1326 } | 1518 } |
1327 if (s->strm->avail_in == 0) return; | 1519 if (s->strm->avail_in == 0) break; |
1328 | 1520 |
1329 /* If there was no sliding: | 1521 /* If there was no sliding: |
1330 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && | 1522 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && |
1331 * more == window_size - lookahead - strstart | 1523 * more == window_size - lookahead - strstart |
1332 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) | 1524 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) |
1341 | 1533 |
1342 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); | 1534 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); |
1343 s->lookahead += n; | 1535 s->lookahead += n; |
1344 | 1536 |
1345 /* Initialize the hash value now that we have some input: */ | 1537 /* Initialize the hash value now that we have some input: */ |
1346 if (s->lookahead >= MIN_MATCH) { | 1538 if (s->lookahead + s->insert >= MIN_MATCH) { |
1347 s->ins_h = s->window[s->strstart]; | 1539 uInt str = s->strstart - s->insert; |
1348 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); | 1540 s->ins_h = s->window[str]; |
1541 UPDATE_HASH(s, s->ins_h, s->window[str + 1]); | |
1349 #if MIN_MATCH != 3 | 1542 #if MIN_MATCH != 3 |
1350 Call UPDATE_HASH() MIN_MATCH-3 more times | 1543 Call UPDATE_HASH() MIN_MATCH-3 more times |
1351 #endif | 1544 #endif |
1545 while (s->insert) { | |
1546 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); | |
1547 #ifndef FASTEST | |
1548 s->prev[str & s->w_mask] = s->head[s->ins_h]; | |
1549 #endif | |
1550 s->head[s->ins_h] = (Pos)str; | |
1551 str++; | |
1552 s->insert--; | |
1553 if (s->lookahead + s->insert < MIN_MATCH) | |
1554 break; | |
1555 } | |
1352 } | 1556 } |
1353 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, | 1557 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, |
1354 * but this is not important since only literal bytes will be emitted. | 1558 * but this is not important since only literal bytes will be emitted. |
1355 */ | 1559 */ |
1356 | 1560 |
1357 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); | 1561 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); |
1562 | |
1563 /* If the WIN_INIT bytes after the end of the current data have never been | |
1564 * written, then zero those bytes in order to avoid memory check reports of | |
1565 * the use of uninitialized (or uninitialised as Julian writes) bytes by | |
1566 * the longest match routines. Update the high water mark for the next | |
1567 * time through here. WIN_INIT is set to MAX_MATCH since the longest match | |
1568 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. | |
1569 */ | |
1570 if (s->high_water < s->window_size) { | |
1571 ulg curr = s->strstart + (ulg)(s->lookahead); | |
1572 ulg init; | |
1573 | |
1574 if (s->high_water < curr) { | |
1575 /* Previous high water mark below current data -- zero WIN_INIT | |
1576 * bytes or up to end of window, whichever is less. | |
1577 */ | |
1578 init = s->window_size - curr; | |
1579 if (init > WIN_INIT) | |
1580 init = WIN_INIT; | |
1581 zmemzero(s->window + curr, (unsigned)init); | |
1582 s->high_water = curr + init; | |
1583 } | |
1584 else if (s->high_water < (ulg)curr + WIN_INIT) { | |
1585 /* High water mark at or above current data, but below current data | |
1586 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up | |
1587 * to end of window, whichever is less. | |
1588 */ | |
1589 init = (ulg)curr + WIN_INIT - s->high_water; | |
1590 if (init > s->window_size - s->high_water) | |
1591 init = s->window_size - s->high_water; | |
1592 zmemzero(s->window + s->high_water, (unsigned)init); | |
1593 s->high_water += init; | |
1594 } | |
1595 } | |
1596 | |
1597 Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, | |
1598 "not enough room for search"); | |
1358 } | 1599 } |
1359 | 1600 |
1360 /* =========================================================================== | 1601 /* =========================================================================== |
1361 * Flush the current block, with given end-of-file flag. | 1602 * Flush the current block, with given end-of-file flag. |
1362 * IN assertion: strstart is set to the end of the current match. | 1603 * IN assertion: strstart is set to the end of the current match. |
1363 */ | 1604 */ |
1364 #define FLUSH_BLOCK_ONLY(s, eof) { \ | 1605 #define FLUSH_BLOCK_ONLY(s, last) { \ |
1365 _tr_flush_block(s, (s->block_start >= 0L ? \ | 1606 _tr_flush_block(s, (s->block_start >= 0L ? \ |
1366 (charf *)&s->window[(unsigned)s->block_start] : \ | 1607 (charf *)&s->window[(unsigned)s->block_start] : \ |
1367 (charf *)Z_NULL), \ | 1608 (charf *)Z_NULL), \ |
1368 (ulg)((long)s->strstart - s->block_start), \ | 1609 (ulg)((long)s->strstart - s->block_start), \ |
1369 (eof)); \ | 1610 (last)); \ |
1370 s->block_start = s->strstart; \ | 1611 s->block_start = s->strstart; \ |
1371 flush_pending(s->strm); \ | 1612 flush_pending(s->strm); \ |
1372 Tracev((stderr,"[FLUSH]")); \ | 1613 Tracev((stderr,"[FLUSH]")); \ |
1373 } | 1614 } |
1374 | 1615 |
1375 /* Same but force premature exit if necessary. */ | 1616 /* Same but force premature exit if necessary. */ |
1376 #define FLUSH_BLOCK(s, eof) { \ | 1617 #define FLUSH_BLOCK(s, last) { \ |
1377 FLUSH_BLOCK_ONLY(s, eof); \ | 1618 FLUSH_BLOCK_ONLY(s, last); \ |
1378 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ | 1619 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ |
1379 } | 1620 } |
1621 | |
1622 /* Maximum stored block length in deflate format (not including header). */ | |
1623 #define MAX_STORED 65535 | |
1624 | |
1625 /* Minimum of a and b. */ | |
1626 #define MIN(a, b) ((a) > (b) ? (b) : (a)) | |
1380 | 1627 |
1381 /* =========================================================================== | 1628 /* =========================================================================== |
1382 * Copy without compression as much as possible from the input stream, return | 1629 * Copy without compression as much as possible from the input stream, return |
1383 * the current block state. | 1630 * the current block state. |
1384 * This function does not insert new strings in the dictionary since | 1631 * |
1385 * uncompressible data is probably not useful. This function is used | 1632 * In case deflateParams() is used to later switch to a non-zero compression |
1386 * only for the level=0 compression option. | 1633 * level, s->matches (otherwise unused when storing) keeps track of the number |
1387 * NOTE: this function should be optimized to avoid extra copying from | 1634 * of hash table slides to perform. If s->matches is 1, then one hash table |
1388 * window to pending_buf. | 1635 * slide will be done when switching. If s->matches is 2, the maximum value |
1636 * allowed here, then the hash table will be cleared, since two or more slides | |
1637 * is the same as a clear. | |
1638 * | |
1639 * deflate_stored() is written to minimize the number of times an input byte is | |
1640 * copied. It is most efficient with large input and output buffers, which | |
1641 * maximizes the opportunites to have a single copy from next_in to next_out. | |
1389 */ | 1642 */ |
1390 local block_state deflate_stored(s, flush) | 1643 local block_state deflate_stored(s, flush) |
1391 deflate_state *s; | 1644 deflate_state *s; |
1392 int flush; | 1645 int flush; |
1393 { | 1646 { |
1394 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited | 1647 /* Smallest worthy block size when not flushing or finishing. By default |
1395 * to pending_buf_size, and each stored block has a 5 byte header: | 1648 * this is 32K. This can be as small as 507 bytes for memLevel == 1. For |
1649 * large input and output buffers, the stored block size will be larger. | |
1396 */ | 1650 */ |
1397 ulg max_block_size = 0xffff; | 1651 unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size); |
1398 ulg max_start; | 1652 |
1399 | 1653 /* Copy as many min_block or larger stored blocks directly to next_out as |
1400 if (max_block_size > s->pending_buf_size - 5) { | 1654 * possible. If flushing, copy the remaining available input to next_out as |
1401 max_block_size = s->pending_buf_size - 5; | 1655 * stored blocks, if there is enough space. |
1402 } | 1656 */ |
1403 | 1657 unsigned len, left, have, last = 0; |
1404 /* Copy as much as possible from input to output: */ | 1658 unsigned used = s->strm->avail_in; |
1405 for (;;) { | 1659 do { |
1406 /* Fill the window as much as possible: */ | 1660 /* Set len to the maximum size block that we can copy directly with the |
1407 if (s->lookahead <= 1) { | 1661 * available input data and output space. Set left to how much of that |
1408 | 1662 * would be copied from what's left in the window. |
1409 Assert(s->strstart < s->w_size+MAX_DIST(s) || | |
1410 s->block_start >= (long)s->w_size, "slide too late"); | |
1411 | |
1412 fill_window(s); | |
1413 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; | |
1414 | |
1415 if (s->lookahead == 0) break; /* flush the current block */ | |
1416 } | |
1417 Assert(s->block_start >= 0L, "block gone"); | |
1418 | |
1419 s->strstart += s->lookahead; | |
1420 s->lookahead = 0; | |
1421 | |
1422 /* Emit a stored block if pending_buf will be full: */ | |
1423 max_start = s->block_start + max_block_size; | |
1424 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { | |
1425 /* strstart == 0 is possible when wraparound on 16-bit machine */ | |
1426 s->lookahead = (uInt)(s->strstart - max_start); | |
1427 s->strstart = (uInt)max_start; | |
1428 FLUSH_BLOCK(s, 0); | |
1429 } | |
1430 /* Flush if we may have to slide, otherwise block_start may become | |
1431 * negative and the data will be gone: | |
1432 */ | 1663 */ |
1433 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { | 1664 len = MAX_STORED; /* maximum deflate stored block length */ |
1434 FLUSH_BLOCK(s, 0); | 1665 have = (s->bi_valid + 42) >> 3; /* number of header bytes */ |
1435 } | 1666 if (s->strm->avail_out < have) /* need room for header */ |
1436 } | 1667 break; |
1437 FLUSH_BLOCK(s, flush == Z_FINISH); | 1668 /* maximum stored block length that will fit in avail_out: */ |
1438 return flush == Z_FINISH ? finish_done : block_done; | 1669 have = s->strm->avail_out - have; |
1670 left = s->strstart - s->block_start; /* bytes left in window */ | |
1671 if (len > (ulg)left + s->strm->avail_in) | |
1672 len = left + s->strm->avail_in; /* limit len to the input */ | |
1673 if (len > have) | |
1674 len = have; /* limit len to the output */ | |
1675 | |
1676 /* If the stored block would be less than min_block in length, or if | |
1677 * unable to copy all of the available input when flushing, then try | |
1678 * copying to the window and the pending buffer instead. Also don't | |
1679 * write an empty block when flushing -- deflate() does that. | |
1680 */ | |
1681 if (len < min_block && ((len == 0 && flush != Z_FINISH) || | |
1682 flush == Z_NO_FLUSH || | |
1683 len != left + s->strm->avail_in)) | |
1684 break; | |
1685 | |
1686 /* Make a dummy stored block in pending to get the header bytes, | |
1687 * including any pending bits. This also updates the debugging counts. | |
1688 */ | |
1689 last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0; | |
1690 _tr_stored_block(s, (char *)0, 0L, last); | |
1691 | |
1692 /* Replace the lengths in the dummy stored block with len. */ | |
1693 s->pending_buf[s->pending - 4] = len; | |
1694 s->pending_buf[s->pending - 3] = len >> 8; | |
1695 s->pending_buf[s->pending - 2] = ~len; | |
1696 s->pending_buf[s->pending - 1] = ~len >> 8; | |
1697 | |
1698 /* Write the stored block header bytes. */ | |
1699 flush_pending(s->strm); | |
1700 | |
1701 #ifdef ZLIB_DEBUG | |
1702 /* Update debugging counts for the data about to be copied. */ | |
1703 s->compressed_len += len << 3; | |
1704 s->bits_sent += len << 3; | |
1705 #endif | |
1706 | |
1707 /* Copy uncompressed bytes from the window to next_out. */ | |
1708 if (left) { | |
1709 if (left > len) | |
1710 left = len; | |
1711 zmemcpy(s->strm->next_out, s->window + s->block_start, left); | |
1712 s->strm->next_out += left; | |
1713 s->strm->avail_out -= left; | |
1714 s->strm->total_out += left; | |
1715 s->block_start += left; | |
1716 len -= left; | |
1717 } | |
1718 | |
1719 /* Copy uncompressed bytes directly from next_in to next_out, updating | |
1720 * the check value. | |
1721 */ | |
1722 if (len) { | |
1723 read_buf(s->strm, s->strm->next_out, len); | |
1724 s->strm->next_out += len; | |
1725 s->strm->avail_out -= len; | |
1726 s->strm->total_out += len; | |
1727 } | |
1728 } while (last == 0); | |
1729 | |
1730 /* Update the sliding window with the last s->w_size bytes of the copied | |
1731 * data, or append all of the copied data to the existing window if less | |
1732 * than s->w_size bytes were copied. Also update the number of bytes to | |
1733 * insert in the hash tables, in the event that deflateParams() switches to | |
1734 * a non-zero compression level. | |
1735 */ | |
1736 used -= s->strm->avail_in; /* number of input bytes directly copied */ | |
1737 if (used) { | |
1738 /* If any input was used, then no unused input remains in the window, | |
1739 * therefore s->block_start == s->strstart. | |
1740 */ | |
1741 if (used >= s->w_size) { /* supplant the previous history */ | |
1742 s->matches = 2; /* clear hash */ | |
1743 zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size); | |
1744 s->strstart = s->w_size; | |
1745 } | |
1746 else { | |
1747 if (s->window_size - s->strstart <= used) { | |
1748 /* Slide the window down. */ | |
1749 s->strstart -= s->w_size; | |
1750 zmemcpy(s->window, s->window + s->w_size, s->strstart); | |
1751 if (s->matches < 2) | |
1752 s->matches++; /* add a pending slide_hash() */ | |
1753 } | |
1754 zmemcpy(s->window + s->strstart, s->strm->next_in - used, used); | |
1755 s->strstart += used; | |
1756 } | |
1757 s->block_start = s->strstart; | |
1758 s->insert += MIN(used, s->w_size - s->insert); | |
1759 } | |
1760 if (s->high_water < s->strstart) | |
1761 s->high_water = s->strstart; | |
1762 | |
1763 /* If the last block was written to next_out, then done. */ | |
1764 if (last) | |
1765 return finish_done; | |
1766 | |
1767 /* If flushing and all input has been consumed, then done. */ | |
1768 if (flush != Z_NO_FLUSH && flush != Z_FINISH && | |
1769 s->strm->avail_in == 0 && (long)s->strstart == s->block_start) | |
1770 return block_done; | |
1771 | |
1772 /* Fill the window with any remaining input. */ | |
1773 have = s->window_size - s->strstart - 1; | |
1774 if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) { | |
1775 /* Slide the window down. */ | |
1776 s->block_start -= s->w_size; | |
1777 s->strstart -= s->w_size; | |
1778 zmemcpy(s->window, s->window + s->w_size, s->strstart); | |
1779 if (s->matches < 2) | |
1780 s->matches++; /* add a pending slide_hash() */ | |
1781 have += s->w_size; /* more space now */ | |
1782 } | |
1783 if (have > s->strm->avail_in) | |
1784 have = s->strm->avail_in; | |
1785 if (have) { | |
1786 read_buf(s->strm, s->window + s->strstart, have); | |
1787 s->strstart += have; | |
1788 } | |
1789 if (s->high_water < s->strstart) | |
1790 s->high_water = s->strstart; | |
1791 | |
1792 /* There was not enough avail_out to write a complete worthy or flushed | |
1793 * stored block to next_out. Write a stored block to pending instead, if we | |
1794 * have enough input for a worthy block, or if flushing and there is enough | |
1795 * room for the remaining input as a stored block in the pending buffer. | |
1796 */ | |
1797 have = (s->bi_valid + 42) >> 3; /* number of header bytes */ | |
1798 /* maximum stored block length that will fit in pending: */ | |
1799 have = MIN(s->pending_buf_size - have, MAX_STORED); | |
1800 min_block = MIN(have, s->w_size); | |
1801 left = s->strstart - s->block_start; | |
1802 if (left >= min_block || | |
1803 ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH && | |
1804 s->strm->avail_in == 0 && left <= have)) { | |
1805 len = MIN(left, have); | |
1806 last = flush == Z_FINISH && s->strm->avail_in == 0 && | |
1807 len == left ? 1 : 0; | |
1808 _tr_stored_block(s, (charf *)s->window + s->block_start, len, last); | |
1809 s->block_start += len; | |
1810 flush_pending(s->strm); | |
1811 } | |
1812 | |
1813 /* We've done all we can with the available input and output. */ | |
1814 return last ? finish_started : need_more; | |
1439 } | 1815 } |
1440 | 1816 |
1441 /* =========================================================================== | 1817 /* =========================================================================== |
1442 * Compress as much as possible from the input stream, return the current | 1818 * Compress as much as possible from the input stream, return the current |
1443 * block state. | 1819 * block state. |
1447 */ | 1823 */ |
1448 local block_state deflate_fast(s, flush) | 1824 local block_state deflate_fast(s, flush) |
1449 deflate_state *s; | 1825 deflate_state *s; |
1450 int flush; | 1826 int flush; |
1451 { | 1827 { |
1452 IPos hash_head = NIL; /* head of the hash chain */ | 1828 IPos hash_head; /* head of the hash chain */ |
1453 int bflush; /* set if current block must be flushed */ | 1829 int bflush; /* set if current block must be flushed */ |
1454 | 1830 |
1455 for (;;) { | 1831 for (;;) { |
1456 /* Make sure that we always have enough lookahead, except | 1832 /* Make sure that we always have enough lookahead, except |
1457 * at the end of the input file. We need MAX_MATCH bytes | 1833 * at the end of the input file. We need MAX_MATCH bytes |
1467 } | 1843 } |
1468 | 1844 |
1469 /* Insert the string window[strstart .. strstart+2] in the | 1845 /* Insert the string window[strstart .. strstart+2] in the |
1470 * dictionary, and set hash_head to the head of the hash chain: | 1846 * dictionary, and set hash_head to the head of the hash chain: |
1471 */ | 1847 */ |
1848 hash_head = NIL; | |
1472 if (s->lookahead >= MIN_MATCH) { | 1849 if (s->lookahead >= MIN_MATCH) { |
1473 INSERT_STRING(s, s->strstart, hash_head); | 1850 INSERT_STRING(s, s->strstart, hash_head); |
1474 } | 1851 } |
1475 | 1852 |
1476 /* Find the longest match, discarding those <= prev_length. | 1853 /* Find the longest match, discarding those <= prev_length. |
1479 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { | 1856 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { |
1480 /* To simplify the code, we prevent matches with the string | 1857 /* To simplify the code, we prevent matches with the string |
1481 * of window index 0 (in particular we have to avoid a match | 1858 * of window index 0 (in particular we have to avoid a match |
1482 * of the string with itself at the start of the input file). | 1859 * of the string with itself at the start of the input file). |
1483 */ | 1860 */ |
1484 #ifdef FASTEST | 1861 s->match_length = longest_match (s, hash_head); |
1485 if ((s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) || | 1862 /* longest_match() sets match_start */ |
1486 (s->strategy == Z_RLE && s->strstart - hash_head == 1)) { | |
1487 s->match_length = longest_match_fast (s, hash_head); | |
1488 } | |
1489 #else | |
1490 if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { | |
1491 s->match_length = longest_match (s, hash_head); | |
1492 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { | |
1493 s->match_length = longest_match_fast (s, hash_head); | |
1494 } | |
1495 #endif | |
1496 /* longest_match() or longest_match_fast() sets match_start */ | |
1497 } | 1863 } |
1498 if (s->match_length >= MIN_MATCH) { | 1864 if (s->match_length >= MIN_MATCH) { |
1499 check_match(s, s->strstart, s->match_start, s->match_length); | 1865 check_match(s, s->strstart, s->match_start, s->match_length); |
1500 | 1866 |
1501 _tr_tally_dist(s, s->strstart - s->match_start, | 1867 _tr_tally_dist(s, s->strstart - s->match_start, |
1539 s->lookahead--; | 1905 s->lookahead--; |
1540 s->strstart++; | 1906 s->strstart++; |
1541 } | 1907 } |
1542 if (bflush) FLUSH_BLOCK(s, 0); | 1908 if (bflush) FLUSH_BLOCK(s, 0); |
1543 } | 1909 } |
1544 FLUSH_BLOCK(s, flush == Z_FINISH); | 1910 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; |
1545 return flush == Z_FINISH ? finish_done : block_done; | 1911 if (flush == Z_FINISH) { |
1912 FLUSH_BLOCK(s, 1); | |
1913 return finish_done; | |
1914 } | |
1915 if (s->last_lit) | |
1916 FLUSH_BLOCK(s, 0); | |
1917 return block_done; | |
1546 } | 1918 } |
1547 | 1919 |
1548 #ifndef FASTEST | 1920 #ifndef FASTEST |
1549 /* =========================================================================== | 1921 /* =========================================================================== |
1550 * Same as above, but achieves better compression. We use a lazy | 1922 * Same as above, but achieves better compression. We use a lazy |
1553 */ | 1925 */ |
1554 local block_state deflate_slow(s, flush) | 1926 local block_state deflate_slow(s, flush) |
1555 deflate_state *s; | 1927 deflate_state *s; |
1556 int flush; | 1928 int flush; |
1557 { | 1929 { |
1558 IPos hash_head = NIL; /* head of hash chain */ | 1930 IPos hash_head; /* head of hash chain */ |
1559 int bflush; /* set if current block must be flushed */ | 1931 int bflush; /* set if current block must be flushed */ |
1560 | 1932 |
1561 /* Process the input block. */ | 1933 /* Process the input block. */ |
1562 for (;;) { | 1934 for (;;) { |
1563 /* Make sure that we always have enough lookahead, except | 1935 /* Make sure that we always have enough lookahead, except |
1574 } | 1946 } |
1575 | 1947 |
1576 /* Insert the string window[strstart .. strstart+2] in the | 1948 /* Insert the string window[strstart .. strstart+2] in the |
1577 * dictionary, and set hash_head to the head of the hash chain: | 1949 * dictionary, and set hash_head to the head of the hash chain: |
1578 */ | 1950 */ |
1951 hash_head = NIL; | |
1579 if (s->lookahead >= MIN_MATCH) { | 1952 if (s->lookahead >= MIN_MATCH) { |
1580 INSERT_STRING(s, s->strstart, hash_head); | 1953 INSERT_STRING(s, s->strstart, hash_head); |
1581 } | 1954 } |
1582 | 1955 |
1583 /* Find the longest match, discarding those <= prev_length. | 1956 /* Find the longest match, discarding those <= prev_length. |
1589 s->strstart - hash_head <= MAX_DIST(s)) { | 1962 s->strstart - hash_head <= MAX_DIST(s)) { |
1590 /* To simplify the code, we prevent matches with the string | 1963 /* To simplify the code, we prevent matches with the string |
1591 * of window index 0 (in particular we have to avoid a match | 1964 * of window index 0 (in particular we have to avoid a match |
1592 * of the string with itself at the start of the input file). | 1965 * of the string with itself at the start of the input file). |
1593 */ | 1966 */ |
1594 if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) { | 1967 s->match_length = longest_match (s, hash_head); |
1595 s->match_length = longest_match (s, hash_head); | 1968 /* longest_match() sets match_start */ |
1596 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) { | |
1597 s->match_length = longest_match_fast (s, hash_head); | |
1598 } | |
1599 /* longest_match() or longest_match_fast() sets match_start */ | |
1600 | 1969 |
1601 if (s->match_length <= 5 && (s->strategy == Z_FILTERED | 1970 if (s->match_length <= 5 && (s->strategy == Z_FILTERED |
1602 #if TOO_FAR <= 32767 | 1971 #if TOO_FAR <= 32767 |
1603 || (s->match_length == MIN_MATCH && | 1972 || (s->match_length == MIN_MATCH && |
1604 s->strstart - s->match_start > TOO_FAR) | 1973 s->strstart - s->match_start > TOO_FAR) |
1667 if (s->match_available) { | 2036 if (s->match_available) { |
1668 Tracevv((stderr,"%c", s->window[s->strstart-1])); | 2037 Tracevv((stderr,"%c", s->window[s->strstart-1])); |
1669 _tr_tally_lit(s, s->window[s->strstart-1], bflush); | 2038 _tr_tally_lit(s, s->window[s->strstart-1], bflush); |
1670 s->match_available = 0; | 2039 s->match_available = 0; |
1671 } | 2040 } |
1672 FLUSH_BLOCK(s, flush == Z_FINISH); | 2041 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; |
1673 return flush == Z_FINISH ? finish_done : block_done; | 2042 if (flush == Z_FINISH) { |
2043 FLUSH_BLOCK(s, 1); | |
2044 return finish_done; | |
2045 } | |
2046 if (s->last_lit) | |
2047 FLUSH_BLOCK(s, 0); | |
2048 return block_done; | |
1674 } | 2049 } |
1675 #endif /* FASTEST */ | 2050 #endif /* FASTEST */ |
1676 | 2051 |
1677 #if 0 | |
1678 /* =========================================================================== | 2052 /* =========================================================================== |
1679 * For Z_RLE, simply look for runs of bytes, generate matches only of distance | 2053 * For Z_RLE, simply look for runs of bytes, generate matches only of distance |
1680 * one. Do not maintain a hash table. (It will be regenerated if this run of | 2054 * one. Do not maintain a hash table. (It will be regenerated if this run of |
1681 * deflate switches away from Z_RLE.) | 2055 * deflate switches away from Z_RLE.) |
1682 */ | 2056 */ |
1683 local block_state deflate_rle(s, flush) | 2057 local block_state deflate_rle(s, flush) |
1684 deflate_state *s; | 2058 deflate_state *s; |
1685 int flush; | 2059 int flush; |
1686 { | 2060 { |
1687 int bflush; /* set if current block must be flushed */ | 2061 int bflush; /* set if current block must be flushed */ |
1688 uInt run; /* length of run */ | 2062 uInt prev; /* byte at distance one to match */ |
1689 uInt max; /* maximum length of run */ | 2063 Bytef *scan, *strend; /* scan goes up to strend for length of run */ |
1690 uInt prev; /* byte at distance one to match */ | |
1691 Bytef *scan; /* scan for end of run */ | |
1692 | 2064 |
1693 for (;;) { | 2065 for (;;) { |
1694 /* Make sure that we always have enough lookahead, except | 2066 /* Make sure that we always have enough lookahead, except |
1695 * at the end of the input file. We need MAX_MATCH bytes | 2067 * at the end of the input file. We need MAX_MATCH bytes |
1696 * for the longest encodable run. | 2068 * for the longest run, plus one for the unrolled loop. |
1697 */ | 2069 */ |
1698 if (s->lookahead < MAX_MATCH) { | 2070 if (s->lookahead <= MAX_MATCH) { |
1699 fill_window(s); | 2071 fill_window(s); |
1700 if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) { | 2072 if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { |
1701 return need_more; | 2073 return need_more; |
1702 } | 2074 } |
1703 if (s->lookahead == 0) break; /* flush the current block */ | 2075 if (s->lookahead == 0) break; /* flush the current block */ |
1704 } | 2076 } |
1705 | 2077 |
1706 /* See how many times the previous byte repeats */ | 2078 /* See how many times the previous byte repeats */ |
1707 run = 0; | 2079 s->match_length = 0; |
1708 if (s->strstart > 0) { /* if there is a previous byte, that is */ | 2080 if (s->lookahead >= MIN_MATCH && s->strstart > 0) { |
1709 max = s->lookahead < MAX_MATCH ? s->lookahead : MAX_MATCH; | |
1710 scan = s->window + s->strstart - 1; | 2081 scan = s->window + s->strstart - 1; |
1711 prev = *scan++; | 2082 prev = *scan; |
1712 do { | 2083 if (prev == *++scan && prev == *++scan && prev == *++scan) { |
1713 if (*scan++ != prev) | 2084 strend = s->window + s->strstart + MAX_MATCH; |
1714 break; | 2085 do { |
1715 } while (++run < max); | 2086 } while (prev == *++scan && prev == *++scan && |
2087 prev == *++scan && prev == *++scan && | |
2088 prev == *++scan && prev == *++scan && | |
2089 prev == *++scan && prev == *++scan && | |
2090 scan < strend); | |
2091 s->match_length = MAX_MATCH - (uInt)(strend - scan); | |
2092 if (s->match_length > s->lookahead) | |
2093 s->match_length = s->lookahead; | |
2094 } | |
2095 Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); | |
1716 } | 2096 } |
1717 | 2097 |
1718 /* Emit match if have run of MIN_MATCH or longer, else emit literal */ | 2098 /* Emit match if have run of MIN_MATCH or longer, else emit literal */ |
1719 if (run >= MIN_MATCH) { | 2099 if (s->match_length >= MIN_MATCH) { |
1720 check_match(s, s->strstart, s->strstart - 1, run); | 2100 check_match(s, s->strstart, s->strstart - 1, s->match_length); |
1721 _tr_tally_dist(s, 1, run - MIN_MATCH, bflush); | 2101 |
1722 s->lookahead -= run; | 2102 _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); |
1723 s->strstart += run; | 2103 |
2104 s->lookahead -= s->match_length; | |
2105 s->strstart += s->match_length; | |
2106 s->match_length = 0; | |
1724 } else { | 2107 } else { |
1725 /* No match, output a literal byte */ | 2108 /* No match, output a literal byte */ |
1726 Tracevv((stderr,"%c", s->window[s->strstart])); | 2109 Tracevv((stderr,"%c", s->window[s->strstart])); |
1727 _tr_tally_lit (s, s->window[s->strstart], bflush); | 2110 _tr_tally_lit (s, s->window[s->strstart], bflush); |
1728 s->lookahead--; | 2111 s->lookahead--; |
1729 s->strstart++; | 2112 s->strstart++; |
1730 } | 2113 } |
1731 if (bflush) FLUSH_BLOCK(s, 0); | 2114 if (bflush) FLUSH_BLOCK(s, 0); |
1732 } | 2115 } |
1733 FLUSH_BLOCK(s, flush == Z_FINISH); | 2116 s->insert = 0; |
1734 return flush == Z_FINISH ? finish_done : block_done; | 2117 if (flush == Z_FINISH) { |
1735 } | 2118 FLUSH_BLOCK(s, 1); |
1736 #endif | 2119 return finish_done; |
2120 } | |
2121 if (s->last_lit) | |
2122 FLUSH_BLOCK(s, 0); | |
2123 return block_done; | |
2124 } | |
2125 | |
2126 /* =========================================================================== | |
2127 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. | |
2128 * (It will be regenerated if this run of deflate switches away from Huffman.) | |
2129 */ | |
2130 local block_state deflate_huff(s, flush) | |
2131 deflate_state *s; | |
2132 int flush; | |
2133 { | |
2134 int bflush; /* set if current block must be flushed */ | |
2135 | |
2136 for (;;) { | |
2137 /* Make sure that we have a literal to write. */ | |
2138 if (s->lookahead == 0) { | |
2139 fill_window(s); | |
2140 if (s->lookahead == 0) { | |
2141 if (flush == Z_NO_FLUSH) | |
2142 return need_more; | |
2143 break; /* flush the current block */ | |
2144 } | |
2145 } | |
2146 | |
2147 /* Output a literal byte */ | |
2148 s->match_length = 0; | |
2149 Tracevv((stderr,"%c", s->window[s->strstart])); | |
2150 _tr_tally_lit (s, s->window[s->strstart], bflush); | |
2151 s->lookahead--; | |
2152 s->strstart++; | |
2153 if (bflush) FLUSH_BLOCK(s, 0); | |
2154 } | |
2155 s->insert = 0; | |
2156 if (flush == Z_FINISH) { | |
2157 FLUSH_BLOCK(s, 1); | |
2158 return finish_done; | |
2159 } | |
2160 if (s->last_lit) | |
2161 FLUSH_BLOCK(s, 0); | |
2162 return block_done; | |
2163 } |