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