Rev 129 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
107 | pj | 1 | /* deflate.c -- compress data using the deflation algorithm |
2 | * Copyright (C) 1995-2002 Jean-loup Gailly. |
||
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
||
4 | */ |
||
5 | |||
6 | /* |
||
7 | * ALGORITHM |
||
8 | * |
||
9 | * The "deflation" process depends on being able to identify portions |
||
10 | * of the input text which are identical to earlier input (within a |
||
11 | * sliding window trailing behind the input currently being processed). |
||
12 | * |
||
13 | * The most straightforward technique turns out to be the fastest for |
||
14 | * most input files: try all possible matches and select the longest. |
||
15 | * The key feature of this algorithm is that insertions into the string |
||
16 | * dictionary are very simple and thus fast, and deletions are avoided |
||
17 | * completely. Insertions are performed at each input character, whereas |
||
18 | * string matches are performed only when the previous match ends. So it |
||
19 | * is preferable to spend more time in matches to allow very fast string |
||
20 | * insertions and avoid deletions. The matching algorithm for small |
||
21 | * strings is inspired from that of Rabin & Karp. A brute force approach |
||
22 | * is used to find longer strings when a small match has been found. |
||
23 | * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze |
||
24 | * (by Leonid Broukhis). |
||
25 | * A previous version of this file used a more sophisticated algorithm |
||
26 | * (by Fiala and Greene) which is guaranteed to run in linear amortized |
||
27 | * time, but has a larger average cost, uses more memory and is patented. |
||
28 | * However the F&G algorithm may be faster for some highly redundant |
||
29 | * files if the parameter max_chain_length (described below) is too large. |
||
30 | * |
||
31 | * ACKNOWLEDGEMENTS |
||
32 | * |
||
33 | * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and |
||
34 | * I found it in 'freeze' written by Leonid Broukhis. |
||
35 | * Thanks to many people for bug reports and testing. |
||
36 | * |
||
37 | * REFERENCES |
||
38 | * |
||
39 | * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". |
||
40 | * Available in ftp://ds.internic.net/rfc/rfc1951.txt |
||
41 | * |
||
42 | * A description of the Rabin and Karp algorithm is given in the book |
||
43 | * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. |
||
44 | * |
||
45 | * Fiala,E.R., and Greene,D.H. |
||
46 | * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 |
||
47 | * |
||
48 | */ |
||
49 | |||
129 | giacomo | 50 | /* @(#) $Id: deflate.c,v 1.2 2003-04-23 09:08:13 giacomo Exp $ */ |
107 | pj | 51 | |
52 | #include "deflate.h" |
||
53 | |||
54 | const char deflate_copyright[] = |
||
55 | " deflate 1.1.4 Copyright 1995-2002 Jean-loup Gailly "; |
||
56 | /* |
||
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 |
||
59 | include such an acknowledgment, I would appreciate that you keep this |
||
60 | copyright string in the executable of your product. |
||
61 | */ |
||
62 | |||
63 | /* =========================================================================== |
||
64 | * Function prototypes. |
||
65 | */ |
||
66 | typedef enum { |
||
67 | need_more, /* block not completed, need more input or more output */ |
||
68 | block_done, /* block flush performed */ |
||
69 | finish_started, /* finish started, need only more output at next deflate */ |
||
70 | finish_done /* finish done, accept no more input or output */ |
||
71 | } block_state; |
||
72 | |||
73 | typedef block_state (*compress_func) OF((deflate_state *s, int flush)); |
||
74 | /* Compression function. Returns the block state after the call. */ |
||
75 | |||
76 | local void fill_window OF((deflate_state *s)); |
||
77 | local block_state deflate_stored OF((deflate_state *s, int flush)); |
||
78 | local block_state deflate_fast OF((deflate_state *s, int flush)); |
||
79 | local block_state deflate_slow OF((deflate_state *s, int flush)); |
||
80 | local void lm_init OF((deflate_state *s)); |
||
81 | local void putShortMSB OF((deflate_state *s, uInt b)); |
||
82 | local void flush_pending OF((z_streamp strm)); |
||
83 | local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); |
||
84 | #ifdef ASMV |
||
85 | void match_init OF((void)); /* asm code initialization */ |
||
86 | uInt longest_match OF((deflate_state *s, IPos cur_match)); |
||
87 | #else |
||
88 | local uInt longest_match OF((deflate_state *s, IPos cur_match)); |
||
89 | #endif |
||
90 | |||
91 | #ifdef DEBUG |
||
92 | local void check_match OF((deflate_state *s, IPos start, IPos match, |
||
93 | int length)); |
||
94 | #endif |
||
95 | |||
96 | /* =========================================================================== |
||
97 | * Local data |
||
98 | */ |
||
99 | |||
129 | giacomo | 100 | #ifdef NIL |
101 | #undef NIL |
||
102 | #endif |
||
103 | |||
107 | pj | 104 | #define NIL 0 |
105 | /* Tail of hash chains */ |
||
106 | |||
107 | #ifndef TOO_FAR |
||
108 | # define TOO_FAR 4096 |
||
109 | #endif |
||
110 | /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ |
||
111 | |||
112 | #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) |
||
113 | /* Minimum amount of lookahead, except at the end of the input file. |
||
114 | * See deflate.c for comments about the MIN_MATCH+1. |
||
115 | */ |
||
116 | |||
117 | /* Values for max_lazy_match, good_match and max_chain_length, depending on |
||
118 | * the desired pack level (0..9). The values given below have been tuned to |
||
119 | * exclude worst case performance for pathological files. Better values may be |
||
120 | * found for specific files. |
||
121 | */ |
||
122 | typedef struct config_s { |
||
123 | ush good_length; /* reduce lazy search above this match length */ |
||
124 | ush max_lazy; /* do not perform lazy search above this match length */ |
||
125 | ush nice_length; /* quit search above this match length */ |
||
126 | ush max_chain; |
||
127 | compress_func func; |
||
128 | } config; |
||
129 | |||
130 | local const config configuration_table[10] = { |
||
131 | /* good lazy nice chain */ |
||
132 | /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ |
||
133 | /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ |
||
134 | /* 2 */ {4, 5, 16, 8, deflate_fast}, |
||
135 | /* 3 */ {4, 6, 32, 32, deflate_fast}, |
||
136 | |||
137 | /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ |
||
138 | /* 5 */ {8, 16, 32, 32, deflate_slow}, |
||
139 | /* 6 */ {8, 16, 128, 128, deflate_slow}, |
||
140 | /* 7 */ {8, 32, 128, 256, deflate_slow}, |
||
141 | /* 8 */ {32, 128, 258, 1024, deflate_slow}, |
||
142 | /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ |
||
143 | |||
144 | /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 |
||
145 | * For deflate_fast() (levels <= 3) good is ignored and lazy has a different |
||
146 | * meaning. |
||
147 | */ |
||
148 | |||
149 | #define EQUAL 0 |
||
150 | /* result of memcmp for equal strings */ |
||
151 | |||
152 | struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ |
||
153 | |||
154 | /* =========================================================================== |
||
155 | * Update a hash value with the given input byte |
||
156 | * IN assertion: all calls to to UPDATE_HASH are made with consecutive |
||
157 | * input characters, so that a running hash key can be computed from the |
||
158 | * previous key instead of complete recalculation each time. |
||
159 | */ |
||
160 | #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) |
||
161 | |||
162 | |||
163 | /* =========================================================================== |
||
164 | * Insert string str in the dictionary and set match_head to the previous head |
||
165 | * of the hash chain (the most recent string with same hash key). Return |
||
166 | * the previous length of the hash chain. |
||
167 | * If this file is compiled with -DFASTEST, the compression level is forced |
||
168 | * to 1, and no hash chains are maintained. |
||
169 | * IN assertion: all calls to to INSERT_STRING are made with consecutive |
||
170 | * input characters and the first MIN_MATCH bytes of str are valid |
||
171 | * (except for the last MIN_MATCH-1 bytes of the input file). |
||
172 | */ |
||
173 | #ifdef FASTEST |
||
174 | #define INSERT_STRING(s, str, match_head) \ |
||
175 | (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ |
||
176 | match_head = s->head[s->ins_h], \ |
||
177 | s->head[s->ins_h] = (Pos)(str)) |
||
178 | #else |
||
179 | #define INSERT_STRING(s, str, match_head) \ |
||
180 | (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ |
||
181 | s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ |
||
182 | s->head[s->ins_h] = (Pos)(str)) |
||
183 | #endif |
||
184 | |||
185 | /* =========================================================================== |
||
186 | * Initialize the hash table (avoiding 64K overflow for 16 bit systems). |
||
187 | * prev[] will be initialized on the fly. |
||
188 | */ |
||
189 | #define CLEAR_HASH(s) \ |
||
190 | s->head[s->hash_size-1] = NIL; \ |
||
191 | zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); |
||
192 | |||
193 | /* ========================================================================= */ |
||
194 | int ZEXPORT deflateInit_(strm, level, version, stream_size) |
||
195 | z_streamp strm; |
||
196 | int level; |
||
197 | const char *version; |
||
198 | int stream_size; |
||
199 | { |
||
200 | return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, |
||
201 | Z_DEFAULT_STRATEGY, version, stream_size); |
||
202 | /* To do: ignore strm->next_in if we use it as window */ |
||
203 | } |
||
204 | |||
205 | /* ========================================================================= */ |
||
206 | int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, |
||
207 | version, stream_size) |
||
208 | z_streamp strm; |
||
209 | int level; |
||
210 | int method; |
||
211 | int windowBits; |
||
212 | int memLevel; |
||
213 | int strategy; |
||
214 | const char *version; |
||
215 | int stream_size; |
||
216 | { |
||
217 | deflate_state *s; |
||
218 | int noheader = 0; |
||
219 | static const char* my_version = ZLIB_VERSION; |
||
220 | |||
221 | ushf *overlay; |
||
222 | /* We overlay pending_buf and d_buf+l_buf. This works since the average |
||
223 | * output size for (length,distance) codes is <= 24 bits. |
||
224 | */ |
||
225 | |||
226 | if (version == Z_NULL || version[0] != my_version[0] || |
||
227 | stream_size != sizeof(z_stream)) { |
||
228 | return Z_VERSION_ERROR; |
||
229 | } |
||
230 | if (strm == Z_NULL) return Z_STREAM_ERROR; |
||
231 | |||
232 | strm->msg = Z_NULL; |
||
233 | if (strm->zalloc == Z_NULL) { |
||
234 | strm->zalloc = zcalloc; |
||
235 | strm->opaque = (voidpf)0; |
||
236 | } |
||
237 | if (strm->zfree == Z_NULL) strm->zfree = zcfree; |
||
238 | |||
239 | if (level == Z_DEFAULT_COMPRESSION) level = 6; |
||
240 | #ifdef FASTEST |
||
241 | level = 1; |
||
242 | #endif |
||
243 | |||
244 | if (windowBits < 0) { /* undocumented feature: suppress zlib header */ |
||
245 | noheader = 1; |
||
246 | windowBits = -windowBits; |
||
247 | } |
||
248 | if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || |
||
249 | windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || |
||
250 | strategy < 0 || strategy > Z_HUFFMAN_ONLY) { |
||
251 | return Z_STREAM_ERROR; |
||
252 | } |
||
253 | s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); |
||
254 | if (s == Z_NULL) return Z_MEM_ERROR; |
||
255 | strm->state = (struct internal_state FAR *)s; |
||
256 | s->strm = strm; |
||
257 | |||
258 | s->noheader = noheader; |
||
259 | s->w_bits = windowBits; |
||
260 | s->w_size = 1 << s->w_bits; |
||
261 | s->w_mask = s->w_size - 1; |
||
262 | |||
263 | s->hash_bits = memLevel + 7; |
||
264 | s->hash_size = 1 << s->hash_bits; |
||
265 | s->hash_mask = s->hash_size - 1; |
||
266 | s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); |
||
267 | |||
268 | s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); |
||
269 | s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); |
||
270 | s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); |
||
271 | |||
272 | s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ |
||
273 | |||
274 | overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); |
||
275 | s->pending_buf = (uchf *) overlay; |
||
276 | s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); |
||
277 | |||
278 | if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || |
||
279 | s->pending_buf == Z_NULL) { |
||
280 | strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); |
||
281 | deflateEnd (strm); |
||
282 | return Z_MEM_ERROR; |
||
283 | } |
||
284 | s->d_buf = overlay + s->lit_bufsize/sizeof(ush); |
||
285 | s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; |
||
286 | |||
287 | s->level = level; |
||
288 | s->strategy = strategy; |
||
289 | s->method = (Byte)method; |
||
290 | |||
291 | return deflateReset(strm); |
||
292 | } |
||
293 | |||
294 | /* ========================================================================= */ |
||
295 | int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) |
||
296 | z_streamp strm; |
||
297 | const Bytef *dictionary; |
||
298 | uInt dictLength; |
||
299 | { |
||
300 | deflate_state *s; |
||
301 | uInt length = dictLength; |
||
302 | uInt n; |
||
303 | IPos hash_head = 0; |
||
304 | |||
305 | if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || |
||
306 | strm->state->status != INIT_STATE) return Z_STREAM_ERROR; |
||
307 | |||
308 | s = strm->state; |
||
309 | strm->adler = adler32(strm->adler, dictionary, dictLength); |
||
310 | |||
311 | if (length < MIN_MATCH) return Z_OK; |
||
312 | if (length > MAX_DIST(s)) { |
||
313 | length = MAX_DIST(s); |
||
314 | #ifndef USE_DICT_HEAD |
||
315 | dictionary += dictLength - length; /* use the tail of the dictionary */ |
||
316 | #endif |
||
317 | } |
||
318 | zmemcpy(s->window, dictionary, length); |
||
319 | s->strstart = length; |
||
320 | s->block_start = (long)length; |
||
321 | |||
322 | /* Insert all strings in the hash table (except for the last two bytes). |
||
323 | * s->lookahead stays null, so s->ins_h will be recomputed at the next |
||
324 | * call of fill_window. |
||
325 | */ |
||
326 | s->ins_h = s->window[0]; |
||
327 | UPDATE_HASH(s, s->ins_h, s->window[1]); |
||
328 | for (n = 0; n <= length - MIN_MATCH; n++) { |
||
329 | INSERT_STRING(s, n, hash_head); |
||
330 | } |
||
331 | if (hash_head) hash_head = 0; /* to make compiler happy */ |
||
332 | return Z_OK; |
||
333 | } |
||
334 | |||
335 | /* ========================================================================= */ |
||
336 | int ZEXPORT deflateReset (strm) |
||
337 | z_streamp strm; |
||
338 | { |
||
339 | deflate_state *s; |
||
340 | |||
341 | if (strm == Z_NULL || strm->state == Z_NULL || |
||
342 | strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; |
||
343 | |||
344 | strm->total_in = strm->total_out = 0; |
||
345 | strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ |
||
346 | strm->data_type = Z_UNKNOWN; |
||
347 | |||
348 | s = (deflate_state *)strm->state; |
||
349 | s->pending = 0; |
||
350 | s->pending_out = s->pending_buf; |
||
351 | |||
352 | if (s->noheader < 0) { |
||
353 | s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ |
||
354 | } |
||
355 | s->status = s->noheader ? BUSY_STATE : INIT_STATE; |
||
356 | strm->adler = 1; |
||
357 | s->last_flush = Z_NO_FLUSH; |
||
358 | |||
359 | _tr_init(s); |
||
360 | lm_init(s); |
||
361 | |||
362 | return Z_OK; |
||
363 | } |
||
364 | |||
365 | /* ========================================================================= */ |
||
366 | int ZEXPORT deflateParams(strm, level, strategy) |
||
367 | z_streamp strm; |
||
368 | int level; |
||
369 | int strategy; |
||
370 | { |
||
371 | deflate_state *s; |
||
372 | compress_func func; |
||
373 | int err = Z_OK; |
||
374 | |||
375 | if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
||
376 | s = strm->state; |
||
377 | |||
378 | if (level == Z_DEFAULT_COMPRESSION) { |
||
379 | level = 6; |
||
380 | } |
||
381 | if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { |
||
382 | return Z_STREAM_ERROR; |
||
383 | } |
||
384 | func = configuration_table[s->level].func; |
||
385 | |||
386 | if (func != configuration_table[level].func && strm->total_in != 0) { |
||
387 | /* Flush the last buffer: */ |
||
388 | err = deflate(strm, Z_PARTIAL_FLUSH); |
||
389 | } |
||
390 | if (s->level != level) { |
||
391 | s->level = level; |
||
392 | s->max_lazy_match = configuration_table[level].max_lazy; |
||
393 | s->good_match = configuration_table[level].good_length; |
||
394 | s->nice_match = configuration_table[level].nice_length; |
||
395 | s->max_chain_length = configuration_table[level].max_chain; |
||
396 | } |
||
397 | s->strategy = strategy; |
||
398 | return err; |
||
399 | } |
||
400 | |||
401 | /* ========================================================================= |
||
402 | * Put a short in the pending buffer. The 16-bit value is put in MSB order. |
||
403 | * IN assertion: the stream state is correct and there is enough room in |
||
404 | * pending_buf. |
||
405 | */ |
||
406 | local void putShortMSB (s, b) |
||
407 | deflate_state *s; |
||
408 | uInt b; |
||
409 | { |
||
410 | put_byte(s, (Byte)(b >> 8)); |
||
411 | put_byte(s, (Byte)(b & 0xff)); |
||
412 | } |
||
413 | |||
414 | /* ========================================================================= |
||
415 | * Flush as much pending output as possible. All deflate() output goes |
||
416 | * through this function so some applications may wish to modify it |
||
417 | * to avoid allocating a large strm->next_out buffer and copying into it. |
||
418 | * (See also read_buf()). |
||
419 | */ |
||
420 | local void flush_pending(strm) |
||
421 | z_streamp strm; |
||
422 | { |
||
423 | unsigned len = strm->state->pending; |
||
424 | |||
425 | if (len > strm->avail_out) len = strm->avail_out; |
||
426 | if (len == 0) return; |
||
427 | |||
428 | zmemcpy(strm->next_out, strm->state->pending_out, len); |
||
429 | strm->next_out += len; |
||
430 | strm->state->pending_out += len; |
||
431 | strm->total_out += len; |
||
432 | strm->avail_out -= len; |
||
433 | strm->state->pending -= len; |
||
434 | if (strm->state->pending == 0) { |
||
435 | strm->state->pending_out = strm->state->pending_buf; |
||
436 | } |
||
437 | } |
||
438 | |||
439 | /* ========================================================================= */ |
||
440 | int ZEXPORT deflate (strm, flush) |
||
441 | z_streamp strm; |
||
442 | int flush; |
||
443 | { |
||
444 | int old_flush; /* value of flush param for previous deflate call */ |
||
445 | deflate_state *s; |
||
446 | |||
447 | if (strm == Z_NULL || strm->state == Z_NULL || |
||
448 | flush > Z_FINISH || flush < 0) { |
||
449 | return Z_STREAM_ERROR; |
||
450 | } |
||
451 | s = strm->state; |
||
452 | |||
453 | if (strm->next_out == Z_NULL || |
||
454 | (strm->next_in == Z_NULL && strm->avail_in != 0) || |
||
455 | (s->status == FINISH_STATE && flush != Z_FINISH)) { |
||
456 | ERR_RETURN(strm, Z_STREAM_ERROR); |
||
457 | } |
||
458 | if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); |
||
459 | |||
460 | s->strm = strm; /* just in case */ |
||
461 | old_flush = s->last_flush; |
||
462 | s->last_flush = flush; |
||
463 | |||
464 | /* Write the zlib header */ |
||
465 | if (s->status == INIT_STATE) { |
||
466 | |||
467 | uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; |
||
468 | uInt level_flags = (s->level-1) >> 1; |
||
469 | |||
470 | if (level_flags > 3) level_flags = 3; |
||
471 | header |= (level_flags << 6); |
||
472 | if (s->strstart != 0) header |= PRESET_DICT; |
||
473 | header += 31 - (header % 31); |
||
474 | |||
475 | s->status = BUSY_STATE; |
||
476 | putShortMSB(s, header); |
||
477 | |||
478 | /* Save the adler32 of the preset dictionary: */ |
||
479 | if (s->strstart != 0) { |
||
480 | putShortMSB(s, (uInt)(strm->adler >> 16)); |
||
481 | putShortMSB(s, (uInt)(strm->adler & 0xffff)); |
||
482 | } |
||
483 | strm->adler = 1L; |
||
484 | } |
||
485 | |||
486 | /* Flush as much pending output as possible */ |
||
487 | if (s->pending != 0) { |
||
488 | flush_pending(strm); |
||
489 | if (strm->avail_out == 0) { |
||
490 | /* Since avail_out is 0, deflate will be called again with |
||
491 | * more output space, but possibly with both pending and |
||
492 | * avail_in equal to zero. There won't be anything to do, |
||
493 | * but this is not an error situation so make sure we |
||
494 | * return OK instead of BUF_ERROR at next call of deflate: |
||
495 | */ |
||
496 | s->last_flush = -1; |
||
497 | return Z_OK; |
||
498 | } |
||
499 | |||
500 | /* Make sure there is something to do and avoid duplicate consecutive |
||
501 | * flushes. For repeated and useless calls with Z_FINISH, we keep |
||
502 | * returning Z_STREAM_END instead of Z_BUFF_ERROR. |
||
503 | */ |
||
504 | } else if (strm->avail_in == 0 && flush <= old_flush && |
||
505 | flush != Z_FINISH) { |
||
506 | ERR_RETURN(strm, Z_BUF_ERROR); |
||
507 | } |
||
508 | |||
509 | /* User must not provide more input after the first FINISH: */ |
||
510 | if (s->status == FINISH_STATE && strm->avail_in != 0) { |
||
511 | ERR_RETURN(strm, Z_BUF_ERROR); |
||
512 | } |
||
513 | |||
514 | /* Start a new block or continue the current one. |
||
515 | */ |
||
516 | if (strm->avail_in != 0 || s->lookahead != 0 || |
||
517 | (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { |
||
518 | block_state bstate; |
||
519 | |||
520 | bstate = (*(configuration_table[s->level].func))(s, flush); |
||
521 | |||
522 | if (bstate == finish_started || bstate == finish_done) { |
||
523 | s->status = FINISH_STATE; |
||
524 | } |
||
525 | if (bstate == need_more || bstate == finish_started) { |
||
526 | if (strm->avail_out == 0) { |
||
527 | s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ |
||
528 | } |
||
529 | return Z_OK; |
||
530 | /* If flush != Z_NO_FLUSH && avail_out == 0, the next call |
||
531 | * of deflate should use the same flush parameter to make sure |
||
532 | * that the flush is complete. So we don't have to output an |
||
533 | * empty block here, this will be done at next call. This also |
||
534 | * ensures that for a very small output buffer, we emit at most |
||
535 | * one empty block. |
||
536 | */ |
||
537 | } |
||
538 | if (bstate == block_done) { |
||
539 | if (flush == Z_PARTIAL_FLUSH) { |
||
540 | _tr_align(s); |
||
541 | } else { /* FULL_FLUSH or SYNC_FLUSH */ |
||
542 | _tr_stored_block(s, (char*)0, 0L, 0); |
||
543 | /* For a full flush, this empty block will be recognized |
||
544 | * as a special marker by inflate_sync(). |
||
545 | */ |
||
546 | if (flush == Z_FULL_FLUSH) { |
||
547 | CLEAR_HASH(s); /* forget history */ |
||
548 | } |
||
549 | } |
||
550 | flush_pending(strm); |
||
551 | if (strm->avail_out == 0) { |
||
552 | s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ |
||
553 | return Z_OK; |
||
554 | } |
||
555 | } |
||
556 | } |
||
557 | Assert(strm->avail_out > 0, "bug2"); |
||
558 | |||
559 | if (flush != Z_FINISH) return Z_OK; |
||
560 | if (s->noheader) return Z_STREAM_END; |
||
561 | |||
562 | /* Write the zlib trailer (adler32) */ |
||
563 | putShortMSB(s, (uInt)(strm->adler >> 16)); |
||
564 | putShortMSB(s, (uInt)(strm->adler & 0xffff)); |
||
565 | flush_pending(strm); |
||
566 | /* If avail_out is zero, the application will call deflate again |
||
567 | * to flush the rest. |
||
568 | */ |
||
569 | s->noheader = -1; /* write the trailer only once! */ |
||
570 | return s->pending != 0 ? Z_OK : Z_STREAM_END; |
||
571 | } |
||
572 | |||
573 | /* ========================================================================= */ |
||
574 | int ZEXPORT deflateEnd (strm) |
||
575 | z_streamp strm; |
||
576 | { |
||
577 | int status; |
||
578 | |||
579 | if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
||
580 | |||
581 | status = strm->state->status; |
||
582 | if (status != INIT_STATE && status != BUSY_STATE && |
||
583 | status != FINISH_STATE) { |
||
584 | return Z_STREAM_ERROR; |
||
585 | } |
||
586 | |||
587 | /* Deallocate in reverse order of allocations: */ |
||
588 | TRY_FREE(strm, strm->state->pending_buf); |
||
589 | TRY_FREE(strm, strm->state->head); |
||
590 | TRY_FREE(strm, strm->state->prev); |
||
591 | TRY_FREE(strm, strm->state->window); |
||
592 | |||
593 | ZFREE(strm, strm->state); |
||
594 | strm->state = Z_NULL; |
||
595 | |||
596 | return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; |
||
597 | } |
||
598 | |||
599 | /* ========================================================================= |
||
600 | * Copy the source state to the destination state. |
||
601 | * To simplify the source, this is not supported for 16-bit MSDOS (which |
||
602 | * doesn't have enough memory anyway to duplicate compression states). |
||
603 | */ |
||
604 | int ZEXPORT deflateCopy (dest, source) |
||
605 | z_streamp dest; |
||
606 | z_streamp source; |
||
607 | { |
||
608 | #ifdef MAXSEG_64K |
||
609 | return Z_STREAM_ERROR; |
||
610 | #else |
||
611 | deflate_state *ds; |
||
612 | deflate_state *ss; |
||
613 | ushf *overlay; |
||
614 | |||
615 | |||
616 | if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { |
||
617 | return Z_STREAM_ERROR; |
||
618 | } |
||
619 | |||
620 | ss = source->state; |
||
621 | |||
622 | *dest = *source; |
||
623 | |||
624 | ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); |
||
625 | if (ds == Z_NULL) return Z_MEM_ERROR; |
||
626 | dest->state = (struct internal_state FAR *) ds; |
||
627 | *ds = *ss; |
||
628 | ds->strm = dest; |
||
629 | |||
630 | ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); |
||
631 | ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); |
||
632 | ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); |
||
633 | overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); |
||
634 | ds->pending_buf = (uchf *) overlay; |
||
635 | |||
636 | if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || |
||
637 | ds->pending_buf == Z_NULL) { |
||
638 | deflateEnd (dest); |
||
639 | return Z_MEM_ERROR; |
||
640 | } |
||
641 | /* following zmemcpy do not work for 16-bit MSDOS */ |
||
642 | zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); |
||
643 | zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); |
||
644 | zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); |
||
645 | zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); |
||
646 | |||
647 | ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); |
||
648 | ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); |
||
649 | ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; |
||
650 | |||
651 | ds->l_desc.dyn_tree = ds->dyn_ltree; |
||
652 | ds->d_desc.dyn_tree = ds->dyn_dtree; |
||
653 | ds->bl_desc.dyn_tree = ds->bl_tree; |
||
654 | |||
655 | return Z_OK; |
||
656 | #endif |
||
657 | } |
||
658 | |||
659 | /* =========================================================================== |
||
660 | * Read a new buffer from the current input stream, update the adler32 |
||
661 | * and total number of bytes read. All deflate() input goes through |
||
662 | * this function so some applications may wish to modify it to avoid |
||
663 | * allocating a large strm->next_in buffer and copying from it. |
||
664 | * (See also flush_pending()). |
||
665 | */ |
||
666 | local int read_buf(strm, buf, size) |
||
667 | z_streamp strm; |
||
668 | Bytef *buf; |
||
669 | unsigned size; |
||
670 | { |
||
671 | unsigned len = strm->avail_in; |
||
672 | |||
673 | if (len > size) len = size; |
||
674 | if (len == 0) return 0; |
||
675 | |||
676 | strm->avail_in -= len; |
||
677 | |||
678 | if (!strm->state->noheader) { |
||
679 | strm->adler = adler32(strm->adler, strm->next_in, len); |
||
680 | } |
||
681 | zmemcpy(buf, strm->next_in, len); |
||
682 | strm->next_in += len; |
||
683 | strm->total_in += len; |
||
684 | |||
685 | return (int)len; |
||
686 | } |
||
687 | |||
688 | /* =========================================================================== |
||
689 | * Initialize the "longest match" routines for a new zlib stream |
||
690 | */ |
||
691 | local void lm_init (s) |
||
692 | deflate_state *s; |
||
693 | { |
||
694 | s->window_size = (ulg)2L*s->w_size; |
||
695 | |||
696 | CLEAR_HASH(s); |
||
697 | |||
698 | /* Set the default configuration parameters: |
||
699 | */ |
||
700 | s->max_lazy_match = configuration_table[s->level].max_lazy; |
||
701 | s->good_match = configuration_table[s->level].good_length; |
||
702 | s->nice_match = configuration_table[s->level].nice_length; |
||
703 | s->max_chain_length = configuration_table[s->level].max_chain; |
||
704 | |||
705 | s->strstart = 0; |
||
706 | s->block_start = 0L; |
||
707 | s->lookahead = 0; |
||
708 | s->match_length = s->prev_length = MIN_MATCH-1; |
||
709 | s->match_available = 0; |
||
710 | s->ins_h = 0; |
||
711 | #ifdef ASMV |
||
712 | match_init(); /* initialize the asm code */ |
||
713 | #endif |
||
714 | } |
||
715 | |||
716 | /* =========================================================================== |
||
717 | * Set match_start to the longest match starting at the given string and |
||
718 | * return its length. Matches shorter or equal to prev_length are discarded, |
||
719 | * in which case the result is equal to prev_length and match_start is |
||
720 | * garbage. |
||
721 | * IN assertions: cur_match is the head of the hash chain for the current |
||
722 | * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 |
||
723 | * OUT assertion: the match length is not greater than s->lookahead. |
||
724 | */ |
||
725 | #ifndef ASMV |
||
726 | /* For 80x86 and 680x0, an optimized version will be provided in match.asm or |
||
727 | * match.S. The code will be functionally equivalent. |
||
728 | */ |
||
729 | #ifndef FASTEST |
||
730 | local uInt longest_match(s, cur_match) |
||
731 | deflate_state *s; |
||
732 | IPos cur_match; /* current match */ |
||
733 | { |
||
734 | unsigned chain_length = s->max_chain_length;/* max hash chain length */ |
||
735 | register Bytef *scan = s->window + s->strstart; /* current string */ |
||
736 | register Bytef *match; /* matched string */ |
||
737 | register int len; /* length of current match */ |
||
738 | int best_len = s->prev_length; /* best match length so far */ |
||
739 | int nice_match = s->nice_match; /* stop if match long enough */ |
||
740 | IPos limit = s->strstart > (IPos)MAX_DIST(s) ? |
||
741 | s->strstart - (IPos)MAX_DIST(s) : NIL; |
||
742 | /* Stop when cur_match becomes <= limit. To simplify the code, |
||
743 | * we prevent matches with the string of window index 0. |
||
744 | */ |
||
745 | Posf *prev = s->prev; |
||
746 | uInt wmask = s->w_mask; |
||
747 | |||
748 | #ifdef UNALIGNED_OK |
||
749 | /* Compare two bytes at a time. Note: this is not always beneficial. |
||
750 | * Try with and without -DUNALIGNED_OK to check. |
||
751 | */ |
||
752 | register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; |
||
753 | register ush scan_start = *(ushf*)scan; |
||
754 | register ush scan_end = *(ushf*)(scan+best_len-1); |
||
755 | #else |
||
756 | register Bytef *strend = s->window + s->strstart + MAX_MATCH; |
||
757 | register Byte scan_end1 = scan[best_len-1]; |
||
758 | register Byte scan_end = scan[best_len]; |
||
759 | #endif |
||
760 | |||
761 | /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. |
||
762 | * It is easy to get rid of this optimization if necessary. |
||
763 | */ |
||
764 | Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); |
||
765 | |||
766 | /* Do not waste too much time if we already have a good match: */ |
||
767 | if (s->prev_length >= s->good_match) { |
||
768 | chain_length >>= 2; |
||
769 | } |
||
770 | /* Do not look for matches beyond the end of the input. This is necessary |
||
771 | * to make deflate deterministic. |
||
772 | */ |
||
773 | if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; |
||
774 | |||
775 | Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); |
||
776 | |||
777 | do { |
||
778 | Assert(cur_match < s->strstart, "no future"); |
||
779 | match = s->window + cur_match; |
||
780 | |||
781 | /* Skip to next match if the match length cannot increase |
||
782 | * or if the match length is less than 2: |
||
783 | */ |
||
784 | #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) |
||
785 | /* This code assumes sizeof(unsigned short) == 2. Do not use |
||
786 | * UNALIGNED_OK if your compiler uses a different size. |
||
787 | */ |
||
788 | if (*(ushf*)(match+best_len-1) != scan_end || |
||
789 | *(ushf*)match != scan_start) continue; |
||
790 | |||
791 | /* It is not necessary to compare scan[2] and match[2] since they are |
||
792 | * always equal when the other bytes match, given that the hash keys |
||
793 | * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at |
||
794 | * strstart+3, +5, ... up to strstart+257. We check for insufficient |
||
795 | * lookahead only every 4th comparison; the 128th check will be made |
||
796 | * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is |
||
797 | * necessary to put more guard bytes at the end of the window, or |
||
798 | * to check more often for insufficient lookahead. |
||
799 | */ |
||
800 | Assert(scan[2] == match[2], "scan[2]?"); |
||
801 | scan++, match++; |
||
802 | do { |
||
803 | } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
||
804 | *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
||
805 | *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
||
806 | *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
||
807 | scan < strend); |
||
808 | /* The funny "do {}" generates better code on most compilers */ |
||
809 | |||
810 | /* Here, scan <= window+strstart+257 */ |
||
811 | Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); |
||
812 | if (*scan == *match) scan++; |
||
813 | |||
814 | len = (MAX_MATCH - 1) - (int)(strend-scan); |
||
815 | scan = strend - (MAX_MATCH-1); |
||
816 | |||
817 | #else /* UNALIGNED_OK */ |
||
818 | |||
819 | if (match[best_len] != scan_end || |
||
820 | match[best_len-1] != scan_end1 || |
||
821 | *match != *scan || |
||
822 | *++match != scan[1]) continue; |
||
823 | |||
824 | /* The check at best_len-1 can be removed because it will be made |
||
825 | * again later. (This heuristic is not always a win.) |
||
826 | * It is not necessary to compare scan[2] and match[2] since they |
||
827 | * are always equal when the other bytes match, given that |
||
828 | * the hash keys are equal and that HASH_BITS >= 8. |
||
829 | */ |
||
830 | scan += 2, match++; |
||
831 | Assert(*scan == *match, "match[2]?"); |
||
832 | |||
833 | /* We check for insufficient lookahead only every 8th comparison; |
||
834 | * the 256th check will be made at strstart+258. |
||
835 | */ |
||
836 | do { |
||
837 | } while (*++scan == *++match && *++scan == *++match && |
||
838 | *++scan == *++match && *++scan == *++match && |
||
839 | *++scan == *++match && *++scan == *++match && |
||
840 | *++scan == *++match && *++scan == *++match && |
||
841 | scan < strend); |
||
842 | |||
843 | Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); |
||
844 | |||
845 | len = MAX_MATCH - (int)(strend - scan); |
||
846 | scan = strend - MAX_MATCH; |
||
847 | |||
848 | #endif /* UNALIGNED_OK */ |
||
849 | |||
850 | if (len > best_len) { |
||
851 | s->match_start = cur_match; |
||
852 | best_len = len; |
||
853 | if (len >= nice_match) break; |
||
854 | #ifdef UNALIGNED_OK |
||
855 | scan_end = *(ushf*)(scan+best_len-1); |
||
856 | #else |
||
857 | scan_end1 = scan[best_len-1]; |
||
858 | scan_end = scan[best_len]; |
||
859 | #endif |
||
860 | } |
||
861 | } while ((cur_match = prev[cur_match & wmask]) > limit |
||
862 | && --chain_length != 0); |
||
863 | |||
864 | if ((uInt)best_len <= s->lookahead) return (uInt)best_len; |
||
865 | return s->lookahead; |
||
866 | } |
||
867 | |||
868 | #else /* FASTEST */ |
||
869 | /* --------------------------------------------------------------------------- |
||
870 | * Optimized version for level == 1 only |
||
871 | */ |
||
872 | local uInt longest_match(s, cur_match) |
||
873 | deflate_state *s; |
||
874 | IPos cur_match; /* current match */ |
||
875 | { |
||
876 | register Bytef *scan = s->window + s->strstart; /* current string */ |
||
877 | register Bytef *match; /* matched string */ |
||
878 | register int len; /* length of current match */ |
||
879 | register Bytef *strend = s->window + s->strstart + MAX_MATCH; |
||
880 | |||
881 | /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. |
||
882 | * It is easy to get rid of this optimization if necessary. |
||
883 | */ |
||
884 | Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); |
||
885 | |||
886 | Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); |
||
887 | |||
888 | Assert(cur_match < s->strstart, "no future"); |
||
889 | |||
890 | match = s->window + cur_match; |
||
891 | |||
892 | /* Return failure if the match length is less than 2: |
||
893 | */ |
||
894 | if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; |
||
895 | |||
896 | /* The check at best_len-1 can be removed because it will be made |
||
897 | * again later. (This heuristic is not always a win.) |
||
898 | * It is not necessary to compare scan[2] and match[2] since they |
||
899 | * are always equal when the other bytes match, given that |
||
900 | * the hash keys are equal and that HASH_BITS >= 8. |
||
901 | */ |
||
902 | scan += 2, match += 2; |
||
903 | Assert(*scan == *match, "match[2]?"); |
||
904 | |||
905 | /* We check for insufficient lookahead only every 8th comparison; |
||
906 | * the 256th check will be made at strstart+258. |
||
907 | */ |
||
908 | do { |
||
909 | } while (*++scan == *++match && *++scan == *++match && |
||
910 | *++scan == *++match && *++scan == *++match && |
||
911 | *++scan == *++match && *++scan == *++match && |
||
912 | *++scan == *++match && *++scan == *++match && |
||
913 | scan < strend); |
||
914 | |||
915 | Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); |
||
916 | |||
917 | len = MAX_MATCH - (int)(strend - scan); |
||
918 | |||
919 | if (len < MIN_MATCH) return MIN_MATCH - 1; |
||
920 | |||
921 | s->match_start = cur_match; |
||
922 | return len <= s->lookahead ? len : s->lookahead; |
||
923 | } |
||
924 | #endif /* FASTEST */ |
||
925 | #endif /* ASMV */ |
||
926 | |||
927 | #ifdef DEBUG |
||
928 | /* =========================================================================== |
||
929 | * Check that the match at match_start is indeed a match. |
||
930 | */ |
||
931 | local void check_match(s, start, match, length) |
||
932 | deflate_state *s; |
||
933 | IPos start, match; |
||
934 | int length; |
||
935 | { |
||
936 | /* check that the match is indeed a match */ |
||
937 | if (zmemcmp(s->window + match, |
||
938 | s->window + start, length) != EQUAL) { |
||
939 | cprintf(" start %u, match %u, length %d\n", |
||
940 | start, match, length); |
||
941 | do { |
||
942 | cprintf("%c%c", s->window[match++], s->window[start++]); |
||
943 | } while (--length != 0); |
||
944 | z_error("invalid match"); |
||
945 | } |
||
946 | if (z_verbose > 1) { |
||
947 | cprintf("\\[%d,%d]", start-match, length); |
||
948 | do { putc(s->window[start++], stderr); } while (--length != 0); |
||
949 | } |
||
950 | } |
||
951 | #else |
||
952 | # define check_match(s, start, match, length) |
||
953 | #endif |
||
954 | |||
955 | /* =========================================================================== |
||
956 | * Fill the window when the lookahead becomes insufficient. |
||
957 | * Updates strstart and lookahead. |
||
958 | * |
||
959 | * IN assertion: lookahead < MIN_LOOKAHEAD |
||
960 | * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD |
||
961 | * At least one byte has been read, or avail_in == 0; reads are |
||
962 | * performed for at least two bytes (required for the zip translate_eol |
||
963 | * option -- not supported here). |
||
964 | */ |
||
965 | local void fill_window(s) |
||
966 | deflate_state *s; |
||
967 | { |
||
968 | register unsigned n, m; |
||
969 | register Posf *p; |
||
970 | unsigned more; /* Amount of free space at the end of the window. */ |
||
971 | uInt wsize = s->w_size; |
||
972 | |||
973 | do { |
||
974 | more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); |
||
975 | |||
976 | /* Deal with !@#$% 64K limit: */ |
||
977 | if (more == 0 && s->strstart == 0 && s->lookahead == 0) { |
||
978 | more = wsize; |
||
979 | |||
980 | } else if (more == (unsigned)(-1)) { |
||
981 | /* Very unlikely, but possible on 16 bit machine if strstart == 0 |
||
982 | * and lookahead == 1 (input done one byte at time) |
||
983 | */ |
||
984 | more--; |
||
985 | |||
986 | /* If the window is almost full and there is insufficient lookahead, |
||
987 | * move the upper half to the lower one to make room in the upper half. |
||
988 | */ |
||
989 | } else if (s->strstart >= wsize+MAX_DIST(s)) { |
||
990 | |||
991 | zmemcpy(s->window, s->window+wsize, (unsigned)wsize); |
||
992 | s->match_start -= wsize; |
||
993 | s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ |
||
994 | s->block_start -= (long) wsize; |
||
995 | |||
996 | /* Slide the hash table (could be avoided with 32 bit values |
||
997 | at the expense of memory usage). We slide even when level == 0 |
||
998 | to keep the hash table consistent if we switch back to level > 0 |
||
999 | later. (Using level 0 permanently is not an optimal usage of |
||
1000 | zlib, so we don't care about this pathological case.) |
||
1001 | */ |
||
1002 | n = s->hash_size; |
||
1003 | p = &s->head[n]; |
||
1004 | do { |
||
1005 | m = *--p; |
||
1006 | *p = (Pos)(m >= wsize ? m-wsize : NIL); |
||
1007 | } while (--n); |
||
1008 | |||
1009 | n = wsize; |
||
1010 | #ifndef FASTEST |
||
1011 | p = &s->prev[n]; |
||
1012 | do { |
||
1013 | m = *--p; |
||
1014 | *p = (Pos)(m >= wsize ? m-wsize : NIL); |
||
1015 | /* If n is not on any hash chain, prev[n] is garbage but |
||
1016 | * its value will never be used. |
||
1017 | */ |
||
1018 | } while (--n); |
||
1019 | #endif |
||
1020 | more += wsize; |
||
1021 | } |
||
1022 | if (s->strm->avail_in == 0) return; |
||
1023 | |||
1024 | /* If there was no sliding: |
||
1025 | * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && |
||
1026 | * more == window_size - lookahead - strstart |
||
1027 | * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) |
||
1028 | * => more >= window_size - 2*WSIZE + 2 |
||
1029 | * In the BIG_MEM or MMAP case (not yet supported), |
||
1030 | * window_size == input_size + MIN_LOOKAHEAD && |
||
1031 | * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. |
||
1032 | * Otherwise, window_size == 2*WSIZE so more >= 2. |
||
1033 | * If there was sliding, more >= WSIZE. So in all cases, more >= 2. |
||
1034 | */ |
||
1035 | Assert(more >= 2, "more < 2"); |
||
1036 | |||
1037 | n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); |
||
1038 | s->lookahead += n; |
||
1039 | |||
1040 | /* Initialize the hash value now that we have some input: */ |
||
1041 | if (s->lookahead >= MIN_MATCH) { |
||
1042 | s->ins_h = s->window[s->strstart]; |
||
1043 | UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); |
||
1044 | #if MIN_MATCH != 3 |
||
1045 | Call UPDATE_HASH() MIN_MATCH-3 more times |
||
1046 | #endif |
||
1047 | } |
||
1048 | /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, |
||
1049 | * but this is not important since only literal bytes will be emitted. |
||
1050 | */ |
||
1051 | |||
1052 | } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); |
||
1053 | } |
||
1054 | |||
1055 | /* =========================================================================== |
||
1056 | * Flush the current block, with given end-of-file flag. |
||
1057 | * IN assertion: strstart is set to the end of the current match. |
||
1058 | */ |
||
1059 | #define FLUSH_BLOCK_ONLY(s, eof) { \ |
||
1060 | _tr_flush_block(s, (s->block_start >= 0L ? \ |
||
1061 | (charf *)&s->window[(unsigned)s->block_start] : \ |
||
1062 | (charf *)Z_NULL), \ |
||
1063 | (ulg)((long)s->strstart - s->block_start), \ |
||
1064 | (eof)); \ |
||
1065 | s->block_start = s->strstart; \ |
||
1066 | flush_pending(s->strm); \ |
||
1067 | Tracev((stderr,"[FLUSH]")); \ |
||
1068 | } |
||
1069 | |||
1070 | /* Same but force premature exit if necessary. */ |
||
1071 | #define FLUSH_BLOCK(s, eof) { \ |
||
1072 | FLUSH_BLOCK_ONLY(s, eof); \ |
||
1073 | if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ |
||
1074 | } |
||
1075 | |||
1076 | /* =========================================================================== |
||
1077 | * Copy without compression as much as possible from the input stream, return |
||
1078 | * the current block state. |
||
1079 | * This function does not insert new strings in the dictionary since |
||
1080 | * uncompressible data is probably not useful. This function is used |
||
1081 | * only for the level=0 compression option. |
||
1082 | * NOTE: this function should be optimized to avoid extra copying from |
||
1083 | * window to pending_buf. |
||
1084 | */ |
||
1085 | local block_state deflate_stored(s, flush) |
||
1086 | deflate_state *s; |
||
1087 | int flush; |
||
1088 | { |
||
1089 | /* Stored blocks are limited to 0xffff bytes, pending_buf is limited |
||
1090 | * to pending_buf_size, and each stored block has a 5 byte header: |
||
1091 | */ |
||
1092 | ulg max_block_size = 0xffff; |
||
1093 | ulg max_start; |
||
1094 | |||
1095 | if (max_block_size > s->pending_buf_size - 5) { |
||
1096 | max_block_size = s->pending_buf_size - 5; |
||
1097 | } |
||
1098 | |||
1099 | /* Copy as much as possible from input to output: */ |
||
1100 | for (;;) { |
||
1101 | /* Fill the window as much as possible: */ |
||
1102 | if (s->lookahead <= 1) { |
||
1103 | |||
1104 | Assert(s->strstart < s->w_size+MAX_DIST(s) || |
||
1105 | s->block_start >= (long)s->w_size, "slide too late"); |
||
1106 | |||
1107 | fill_window(s); |
||
1108 | if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; |
||
1109 | |||
1110 | if (s->lookahead == 0) break; /* flush the current block */ |
||
1111 | } |
||
1112 | Assert(s->block_start >= 0L, "block gone"); |
||
1113 | |||
1114 | s->strstart += s->lookahead; |
||
1115 | s->lookahead = 0; |
||
1116 | |||
1117 | /* Emit a stored block if pending_buf will be full: */ |
||
1118 | max_start = s->block_start + max_block_size; |
||
1119 | if (s->strstart == 0 || (ulg)s->strstart >= max_start) { |
||
1120 | /* strstart == 0 is possible when wraparound on 16-bit machine */ |
||
1121 | s->lookahead = (uInt)(s->strstart - max_start); |
||
1122 | s->strstart = (uInt)max_start; |
||
1123 | FLUSH_BLOCK(s, 0); |
||
1124 | } |
||
1125 | /* Flush if we may have to slide, otherwise block_start may become |
||
1126 | * negative and the data will be gone: |
||
1127 | */ |
||
1128 | if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { |
||
1129 | FLUSH_BLOCK(s, 0); |
||
1130 | } |
||
1131 | } |
||
1132 | FLUSH_BLOCK(s, flush == Z_FINISH); |
||
1133 | return flush == Z_FINISH ? finish_done : block_done; |
||
1134 | } |
||
1135 | |||
1136 | /* =========================================================================== |
||
1137 | * Compress as much as possible from the input stream, return the current |
||
1138 | * block state. |
||
1139 | * This function does not perform lazy evaluation of matches and inserts |
||
1140 | * new strings in the dictionary only for unmatched strings or for short |
||
1141 | * matches. It is used only for the fast compression options. |
||
1142 | */ |
||
1143 | local block_state deflate_fast(s, flush) |
||
1144 | deflate_state *s; |
||
1145 | int flush; |
||
1146 | { |
||
1147 | IPos hash_head = NIL; /* head of the hash chain */ |
||
1148 | int bflush; /* set if current block must be flushed */ |
||
1149 | |||
1150 | for (;;) { |
||
1151 | /* Make sure that we always have enough lookahead, except |
||
1152 | * at the end of the input file. We need MAX_MATCH bytes |
||
1153 | * for the next match, plus MIN_MATCH bytes to insert the |
||
1154 | * string following the next match. |
||
1155 | */ |
||
1156 | if (s->lookahead < MIN_LOOKAHEAD) { |
||
1157 | fill_window(s); |
||
1158 | if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { |
||
1159 | return need_more; |
||
1160 | } |
||
1161 | if (s->lookahead == 0) break; /* flush the current block */ |
||
1162 | } |
||
1163 | |||
1164 | /* Insert the string window[strstart .. strstart+2] in the |
||
1165 | * dictionary, and set hash_head to the head of the hash chain: |
||
1166 | */ |
||
1167 | if (s->lookahead >= MIN_MATCH) { |
||
1168 | INSERT_STRING(s, s->strstart, hash_head); |
||
1169 | } |
||
1170 | |||
1171 | /* Find the longest match, discarding those <= prev_length. |
||
1172 | * At this point we have always match_length < MIN_MATCH |
||
1173 | */ |
||
1174 | if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { |
||
1175 | /* To simplify the code, we prevent matches with the string |
||
1176 | * of window index 0 (in particular we have to avoid a match |
||
1177 | * of the string with itself at the start of the input file). |
||
1178 | */ |
||
1179 | if (s->strategy != Z_HUFFMAN_ONLY) { |
||
1180 | s->match_length = longest_match (s, hash_head); |
||
1181 | } |
||
1182 | /* longest_match() sets match_start */ |
||
1183 | } |
||
1184 | if (s->match_length >= MIN_MATCH) { |
||
1185 | check_match(s, s->strstart, s->match_start, s->match_length); |
||
1186 | |||
1187 | _tr_tally_dist(s, s->strstart - s->match_start, |
||
1188 | s->match_length - MIN_MATCH, bflush); |
||
1189 | |||
1190 | s->lookahead -= s->match_length; |
||
1191 | |||
1192 | /* Insert new strings in the hash table only if the match length |
||
1193 | * is not too large. This saves time but degrades compression. |
||
1194 | */ |
||
1195 | #ifndef FASTEST |
||
1196 | if (s->match_length <= s->max_insert_length && |
||
1197 | s->lookahead >= MIN_MATCH) { |
||
1198 | s->match_length--; /* string at strstart already in hash table */ |
||
1199 | do { |
||
1200 | s->strstart++; |
||
1201 | INSERT_STRING(s, s->strstart, hash_head); |
||
1202 | /* strstart never exceeds WSIZE-MAX_MATCH, so there are |
||
1203 | * always MIN_MATCH bytes ahead. |
||
1204 | */ |
||
1205 | } while (--s->match_length != 0); |
||
1206 | s->strstart++; |
||
1207 | } else |
||
1208 | #endif |
||
1209 | { |
||
1210 | s->strstart += s->match_length; |
||
1211 | s->match_length = 0; |
||
1212 | s->ins_h = s->window[s->strstart]; |
||
1213 | UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); |
||
1214 | #if MIN_MATCH != 3 |
||
1215 | Call UPDATE_HASH() MIN_MATCH-3 more times |
||
1216 | #endif |
||
1217 | /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not |
||
1218 | * matter since it will be recomputed at next deflate call. |
||
1219 | */ |
||
1220 | } |
||
1221 | } else { |
||
1222 | /* No match, output a literal byte */ |
||
1223 | Tracevv((stderr,"%c", s->window[s->strstart])); |
||
1224 | _tr_tally_lit (s, s->window[s->strstart], bflush); |
||
1225 | s->lookahead--; |
||
1226 | s->strstart++; |
||
1227 | } |
||
1228 | if (bflush) FLUSH_BLOCK(s, 0); |
||
1229 | } |
||
1230 | FLUSH_BLOCK(s, flush == Z_FINISH); |
||
1231 | return flush == Z_FINISH ? finish_done : block_done; |
||
1232 | } |
||
1233 | |||
1234 | /* =========================================================================== |
||
1235 | * Same as above, but achieves better compression. We use a lazy |
||
1236 | * evaluation for matches: a match is finally adopted only if there is |
||
1237 | * no better match at the next window position. |
||
1238 | */ |
||
1239 | local block_state deflate_slow(s, flush) |
||
1240 | deflate_state *s; |
||
1241 | int flush; |
||
1242 | { |
||
1243 | IPos hash_head = NIL; /* head of hash chain */ |
||
1244 | int bflush; /* set if current block must be flushed */ |
||
1245 | |||
1246 | /* Process the input block. */ |
||
1247 | for (;;) { |
||
1248 | /* Make sure that we always have enough lookahead, except |
||
1249 | * at the end of the input file. We need MAX_MATCH bytes |
||
1250 | * for the next match, plus MIN_MATCH bytes to insert the |
||
1251 | * string following the next match. |
||
1252 | */ |
||
1253 | if (s->lookahead < MIN_LOOKAHEAD) { |
||
1254 | fill_window(s); |
||
1255 | if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { |
||
1256 | return need_more; |
||
1257 | } |
||
1258 | if (s->lookahead == 0) break; /* flush the current block */ |
||
1259 | } |
||
1260 | |||
1261 | /* Insert the string window[strstart .. strstart+2] in the |
||
1262 | * dictionary, and set hash_head to the head of the hash chain: |
||
1263 | */ |
||
1264 | if (s->lookahead >= MIN_MATCH) { |
||
1265 | INSERT_STRING(s, s->strstart, hash_head); |
||
1266 | } |
||
1267 | |||
1268 | /* Find the longest match, discarding those <= prev_length. |
||
1269 | */ |
||
1270 | s->prev_length = s->match_length, s->prev_match = s->match_start; |
||
1271 | s->match_length = MIN_MATCH-1; |
||
1272 | |||
1273 | if (hash_head != NIL && s->prev_length < s->max_lazy_match && |
||
1274 | s->strstart - hash_head <= MAX_DIST(s)) { |
||
1275 | /* To simplify the code, we prevent matches with the string |
||
1276 | * of window index 0 (in particular we have to avoid a match |
||
1277 | * of the string with itself at the start of the input file). |
||
1278 | */ |
||
1279 | if (s->strategy != Z_HUFFMAN_ONLY) { |
||
1280 | s->match_length = longest_match (s, hash_head); |
||
1281 | } |
||
1282 | /* longest_match() sets match_start */ |
||
1283 | |||
1284 | if (s->match_length <= 5 && (s->strategy == Z_FILTERED || |
||
1285 | (s->match_length == MIN_MATCH && |
||
1286 | s->strstart - s->match_start > TOO_FAR))) { |
||
1287 | |||
1288 | /* If prev_match is also MIN_MATCH, match_start is garbage |
||
1289 | * but we will ignore the current match anyway. |
||
1290 | */ |
||
1291 | s->match_length = MIN_MATCH-1; |
||
1292 | } |
||
1293 | } |
||
1294 | /* If there was a match at the previous step and the current |
||
1295 | * match is not better, output the previous match: |
||
1296 | */ |
||
1297 | if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { |
||
1298 | uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; |
||
1299 | /* Do not insert strings in hash table beyond this. */ |
||
1300 | |||
1301 | check_match(s, s->strstart-1, s->prev_match, s->prev_length); |
||
1302 | |||
1303 | _tr_tally_dist(s, s->strstart -1 - s->prev_match, |
||
1304 | s->prev_length - MIN_MATCH, bflush); |
||
1305 | |||
1306 | /* Insert in hash table all strings up to the end of the match. |
||
1307 | * strstart-1 and strstart are already inserted. If there is not |
||
1308 | * enough lookahead, the last two strings are not inserted in |
||
1309 | * the hash table. |
||
1310 | */ |
||
1311 | s->lookahead -= s->prev_length-1; |
||
1312 | s->prev_length -= 2; |
||
1313 | do { |
||
1314 | if (++s->strstart <= max_insert) { |
||
1315 | INSERT_STRING(s, s->strstart, hash_head); |
||
1316 | } |
||
1317 | } while (--s->prev_length != 0); |
||
1318 | s->match_available = 0; |
||
1319 | s->match_length = MIN_MATCH-1; |
||
1320 | s->strstart++; |
||
1321 | |||
1322 | if (bflush) FLUSH_BLOCK(s, 0); |
||
1323 | |||
1324 | } else if (s->match_available) { |
||
1325 | /* If there was no match at the previous position, output a |
||
1326 | * single literal. If there was a match but the current match |
||
1327 | * is longer, truncate the previous match to a single literal. |
||
1328 | */ |
||
1329 | Tracevv((stderr,"%c", s->window[s->strstart-1])); |
||
1330 | _tr_tally_lit(s, s->window[s->strstart-1], bflush); |
||
1331 | if (bflush) { |
||
1332 | FLUSH_BLOCK_ONLY(s, 0); |
||
1333 | } |
||
1334 | s->strstart++; |
||
1335 | s->lookahead--; |
||
1336 | if (s->strm->avail_out == 0) return need_more; |
||
1337 | } else { |
||
1338 | /* There is no previous match to compare with, wait for |
||
1339 | * the next step to decide. |
||
1340 | */ |
||
1341 | s->match_available = 1; |
||
1342 | s->strstart++; |
||
1343 | s->lookahead--; |
||
1344 | } |
||
1345 | } |
||
1346 | Assert (flush != Z_NO_FLUSH, "no flush?"); |
||
1347 | if (s->match_available) { |
||
1348 | Tracevv((stderr,"%c", s->window[s->strstart-1])); |
||
1349 | _tr_tally_lit(s, s->window[s->strstart-1], bflush); |
||
1350 | s->match_available = 0; |
||
1351 | } |
||
1352 | FLUSH_BLOCK(s, flush == Z_FINISH); |
||
1353 | return flush == Z_FINISH ? finish_done : block_done; |
||
1354 | } |