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