deflate.c

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