File Coverage

deflate.c
Criterion Covered Total %
statement 484 857 56.4
branch 348 784 44.3
condition n/a
subroutine n/a
pod n/a
total 832 1641 50.7


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