deflate.c 76.8 KB
Newer Older
M
Mark Adler 已提交
1
/* deflate.c -- compress data using the deflation algorithm
2
 * Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler
M
Mark Adler 已提交
3
 * For conditions of distribution and use, see copyright notice in zlib.h
M
Mark Adler 已提交
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
 */

/*
 *  ALGORITHM
 *
 *      The "deflation" process depends on being able to identify portions
 *      of the input text which are identical to earlier input (within a
 *      sliding window trailing behind the input currently being processed).
 *
 *      The most straightforward technique turns out to be the fastest for
 *      most input files: try all possible matches and select the longest.
 *      The key feature of this algorithm is that insertions into the string
 *      dictionary are very simple and thus fast, and deletions are avoided
 *      completely. Insertions are performed at each input character, whereas
 *      string matches are performed only when the previous match ends. So it
 *      is preferable to spend more time in matches to allow very fast string
 *      insertions and avoid deletions. The matching algorithm for small
 *      strings is inspired from that of Rabin & Karp. A brute force approach
 *      is used to find longer strings when a small match has been found.
 *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
 *      (by Leonid Broukhis).
 *         A previous version of this file used a more sophisticated algorithm
 *      (by Fiala and Greene) which is guaranteed to run in linear amortized
 *      time, but has a larger average cost, uses more memory and is patented.
 *      However the F&G algorithm may be faster for some highly redundant
 *      files if the parameter max_chain_length (described below) is too large.
 *
 *  ACKNOWLEDGEMENTS
 *
 *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
 *      I found it in 'freeze' written by Leonid Broukhis.
 *      Thanks to many people for bug reports and testing.
 *
 *  REFERENCES
 *
M
Mark Adler 已提交
39
 *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
M
Mark Adler 已提交
40
 *      Available in http://tools.ietf.org/html/rfc1951
M
Mark Adler 已提交
41 42 43 44 45 46 47 48 49
 *
 *      A description of the Rabin and Karp algorithm is given in the book
 *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
 *
 *      Fiala,E.R., and Greene,D.H.
 *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
 *
 */

M
Mark Adler 已提交
50
/* @(#) $Id$ */
M
Mark Adler 已提交
51 52 53

#include "deflate.h"

M
Mark Adler 已提交
54
const char deflate_copyright[] =
55
   " deflate 1.2.9.1 Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
M
Mark Adler 已提交
56 57 58 59 60 61 62
/*
  If you use the zlib library in a product, an acknowledgment is welcome
  in the documentation of your product. If for some reason you cannot
  include such an acknowledgment, I would appreciate that you keep this
  copyright string in the executable of your product.
 */

M
Mark Adler 已提交
63
/* ===========================================================================
M
Mark Adler 已提交
64
 *  Function prototypes.
M
Mark Adler 已提交
65
 */
M
Mark Adler 已提交
66 67 68 69 70 71 72 73 74 75
typedef enum {
    need_more,      /* block not completed, need more input or more output */
    block_done,     /* block flush performed */
    finish_started, /* finish started, need only more output at next deflate */
    finish_done     /* finish done, accept no more input or output */
} block_state;

typedef block_state (*compress_func) OF((deflate_state *s, int flush));
/* Compression function. Returns the block state after the call. */

76
local int deflateStateCheck      OF((z_streamp strm));
77
local void slide_hash     OF((deflate_state *s));
M
Mark Adler 已提交
78
local void fill_window    OF((deflate_state *s));
M
Mark Adler 已提交
79 80
local block_state deflate_stored OF((deflate_state *s, int flush));
local block_state deflate_fast   OF((deflate_state *s, int flush));
M
Mark Adler 已提交
81
#ifndef FASTEST
M
Mark Adler 已提交
82
local block_state deflate_slow   OF((deflate_state *s, int flush));
M
Mark Adler 已提交
83
#endif
M
Mark Adler 已提交
84 85
local block_state deflate_rle    OF((deflate_state *s, int flush));
local block_state deflate_huff   OF((deflate_state *s, int flush));
M
Mark Adler 已提交
86 87
local void lm_init        OF((deflate_state *s));
local void putShortMSB    OF((deflate_state *s, uInt b));
M
Mark Adler 已提交
88
local void flush_pending  OF((z_streamp strm));
M
Mark Adler 已提交
89
local unsigned read_buf   OF((z_streamp strm, Bytef *buf, unsigned size));
M
Mark Adler 已提交
90 91
#ifdef ASMV
      void match_init OF((void)); /* asm code initialization */
M
Mark Adler 已提交
92 93 94
      uInt longest_match  OF((deflate_state *s, IPos cur_match));
#else
local uInt longest_match  OF((deflate_state *s, IPos cur_match));
M
Mark Adler 已提交
95 96
#endif

97
#ifdef ZLIB_DEBUG
M
Mark Adler 已提交
98 99 100 101 102 103 104 105
local  void check_match OF((deflate_state *s, IPos start, IPos match,
                            int length));
#endif

/* ===========================================================================
 * Local data
 */

M
Mark Adler 已提交
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
#define NIL 0
/* Tail of hash chains */

#ifndef TOO_FAR
#  define TOO_FAR 4096
#endif
/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */

/* Values for max_lazy_match, good_match and max_chain_length, depending on
 * the desired pack level (0..9). The values given below have been tuned to
 * exclude worst case performance for pathological files. Better values may be
 * found for specific files.
 */
typedef struct config_s {
   ush good_length; /* reduce lazy search above this match length */
   ush max_lazy;    /* do not perform lazy search above this match length */
   ush nice_length; /* quit search above this match length */
   ush max_chain;
M
Mark Adler 已提交
124
   compress_func func;
M
Mark Adler 已提交
125 126
} config;

M
Mark Adler 已提交
127 128 129 130
#ifdef FASTEST
local const config configuration_table[2] = {
/*      good lazy nice chain */
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
M
Mark Adler 已提交
131
/* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */
M
Mark Adler 已提交
132
#else
M
Mark Adler 已提交
133
local const config configuration_table[10] = {
M
Mark Adler 已提交
134
/*      good lazy nice chain */
M
Mark Adler 已提交
135
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
M
Mark Adler 已提交
136
/* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
M
Mark Adler 已提交
137 138 139 140 141 142 143 144
/* 2 */ {4,    5, 16,    8, deflate_fast},
/* 3 */ {4,    6, 32,   32, deflate_fast},

/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
/* 5 */ {8,   16, 32,   32, deflate_slow},
/* 6 */ {8,   16, 128, 128, deflate_slow},
/* 7 */ {8,   32, 128, 256, deflate_slow},
/* 8 */ {32, 128, 258, 1024, deflate_slow},
M
Mark Adler 已提交
145
/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
M
Mark Adler 已提交
146
#endif
M
Mark Adler 已提交
147 148 149 150 151 152

/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
 * meaning.
 */

153
/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
154
#define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
155

M
Mark Adler 已提交
156 157
/* ===========================================================================
 * Update a hash value with the given input byte
M
Mark Adler 已提交
158 159 160
 * IN  assertion: all calls to UPDATE_HASH are made with consecutive input
 *    characters, so that a running hash key can be computed from the previous
 *    key instead of complete recalculation each time.
M
Mark Adler 已提交
161 162 163
 */
#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)

M
Mark Adler 已提交
164

M
Mark Adler 已提交
165 166 167 168
/* ===========================================================================
 * Insert string str in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
M
Mark Adler 已提交
169 170
 * If this file is compiled with -DFASTEST, the compression level is forced
 * to 1, and no hash chains are maintained.
M
Mark Adler 已提交
171 172 173
 * IN  assertion: all calls to INSERT_STRING are made with consecutive input
 *    characters and the first MIN_MATCH bytes of str are valid (except for
 *    the last MIN_MATCH-1 bytes of the input file).
M
Mark Adler 已提交
174
 */
M
Mark Adler 已提交
175 176 177 178 179 180
#ifdef FASTEST
#define INSERT_STRING(s, str, match_head) \
   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
    match_head = s->head[s->ins_h], \
    s->head[s->ins_h] = (Pos)(str))
#else
M
Mark Adler 已提交
181
#define INSERT_STRING(s, str, match_head) \
M
Mark Adler 已提交
182
   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
M
Mark Adler 已提交
183
    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
M
Mark Adler 已提交
184
    s->head[s->ins_h] = (Pos)(str))
M
Mark Adler 已提交
185
#endif
M
Mark Adler 已提交
186

M
Mark Adler 已提交
187 188 189 190 191 192
/* ===========================================================================
 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
 * prev[] will be initialized on the fly.
 */
#define CLEAR_HASH(s) \
    s->head[s->hash_size-1] = NIL; \
M
Mark Adler 已提交
193
    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
M
Mark Adler 已提交
194

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
/* ===========================================================================
 * Slide the hash table when sliding the window down (could be avoided with 32
 * bit values at the expense of memory usage). We slide even when level == 0 to
 * keep the hash table consistent if we switch back to level > 0 later.
 */
local void slide_hash(s)
    deflate_state *s;
{
    unsigned n, m;
    Posf *p;
    uInt wsize = s->w_size;

    n = s->hash_size;
    p = &s->head[n];
    do {
        m = *--p;
        *p = (Pos)(m >= wsize ? m - wsize : NIL);
    } while (--n);
    n = wsize;
#ifndef FASTEST
    p = &s->prev[n];
    do {
        m = *--p;
        *p = (Pos)(m >= wsize ? m - wsize : NIL);
        /* If n is not on any hash chain, prev[n] is garbage but
         * its value will never be used.
         */
    } while (--n);
#endif
}

M
Mark Adler 已提交
226
/* ========================================================================= */
M
Mark Adler 已提交
227
int ZEXPORT deflateInit_(strm, level, version, stream_size)
M
Mark Adler 已提交
228
    z_streamp strm;
M
Mark Adler 已提交
229
    int level;
M
Mark Adler 已提交
230 231
    const char *version;
    int stream_size;
M
Mark Adler 已提交
232
{
M
Mark Adler 已提交
233
    return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
M
Mark Adler 已提交
234
                         Z_DEFAULT_STRATEGY, version, stream_size);
M
Mark Adler 已提交
235 236 237 238
    /* To do: ignore strm->next_in if we use it as window */
}

/* ========================================================================= */
M
Mark Adler 已提交
239
int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
M
Mark Adler 已提交
240
                  version, stream_size)
M
Mark Adler 已提交
241
    z_streamp strm;
M
Mark Adler 已提交
242 243 244 245 246
    int  level;
    int  method;
    int  windowBits;
    int  memLevel;
    int  strategy;
M
Mark Adler 已提交
247 248
    const char *version;
    int stream_size;
M
Mark Adler 已提交
249 250
{
    deflate_state *s;
M
Mark Adler 已提交
251
    int wrap = 1;
M
Mark Adler 已提交
252
    static const char my_version[] = ZLIB_VERSION;
M
Mark Adler 已提交
253

M
Mark Adler 已提交
254 255 256 257 258
    ushf *overlay;
    /* We overlay pending_buf and d_buf+l_buf. This works since the average
     * output size for (length,distance) codes is <= 24 bits.
     */

M
Mark Adler 已提交
259
    if (version == Z_NULL || version[0] != my_version[0] ||
M
Mark Adler 已提交
260
        stream_size != sizeof(z_stream)) {
M
Mark Adler 已提交
261
        return Z_VERSION_ERROR;
M
Mark Adler 已提交
262
    }
M
Mark Adler 已提交
263 264 265
    if (strm == Z_NULL) return Z_STREAM_ERROR;

    strm->msg = Z_NULL;
M
Mark Adler 已提交
266
    if (strm->zalloc == (alloc_func)0) {
267 268 269
#ifdef Z_SOLO
        return Z_STREAM_ERROR;
#else
M
Mark Adler 已提交
270 271
        strm->zalloc = zcalloc;
        strm->opaque = (voidpf)0;
272
#endif
M
Mark Adler 已提交
273
    }
274 275 276 277 278 279
    if (strm->zfree == (free_func)0)
#ifdef Z_SOLO
        return Z_STREAM_ERROR;
#else
        strm->zfree = zcfree;
#endif
M
Mark Adler 已提交
280

M
Mark Adler 已提交
281
#ifdef FASTEST
M
Mark Adler 已提交
282 283 284
    if (level != 0) level = 1;
#else
    if (level == Z_DEFAULT_COMPRESSION) level = 6;
M
Mark Adler 已提交
285
#endif
M
Mark Adler 已提交
286

M
Mark Adler 已提交
287 288
    if (windowBits < 0) { /* suppress zlib wrapper */
        wrap = 0;
M
Mark Adler 已提交
289
        windowBits = -windowBits;
M
Mark Adler 已提交
290
    }
M
Mark Adler 已提交
291 292
#ifdef GZIP
    else if (windowBits > 15) {
M
Mark Adler 已提交
293
        wrap = 2;       /* write gzip wrapper instead */
M
Mark Adler 已提交
294 295 296
        windowBits -= 16;
    }
#endif
M
Mark Adler 已提交
297
    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
M
Mark Adler 已提交
298
        windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
299
        strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) {
M
Mark Adler 已提交
300
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
301
    }
M
Mark Adler 已提交
302
    if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */
M
Mark Adler 已提交
303 304
    s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
    if (s == Z_NULL) return Z_MEM_ERROR;
M
Mark Adler 已提交
305
    strm->state = (struct internal_state FAR *)s;
M
Mark Adler 已提交
306
    s->strm = strm;
307
    s->status = INIT_STATE;     /* to pass state test in deflateReset() */
M
Mark Adler 已提交
308

M
Mark Adler 已提交
309
    s->wrap = wrap;
M
Mark Adler 已提交
310
    s->gzhead = Z_NULL;
M
Mark Adler 已提交
311
    s->w_bits = (uInt)windowBits;
M
Mark Adler 已提交
312
    s->w_size = 1 << s->w_bits;
M
Mark Adler 已提交
313
    s->w_mask = s->w_size - 1;
M
Mark Adler 已提交
314

M
Mark Adler 已提交
315
    s->hash_bits = (uInt)memLevel + 7;
M
Mark Adler 已提交
316
    s->hash_size = 1 << s->hash_bits;
M
Mark Adler 已提交
317
    s->hash_mask = s->hash_size - 1;
M
Mark Adler 已提交
318 319
    s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);

M
Mark Adler 已提交
320 321 322
    s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
    s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
    s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
M
Mark Adler 已提交
323

M
Mark Adler 已提交
324 325
    s->high_water = 0;      /* nothing written to s->window yet */

M
Mark Adler 已提交
326 327
    s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */

M
Mark Adler 已提交
328 329
    overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
    s->pending_buf = (uchf *) overlay;
M
Mark Adler 已提交
330
    s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
M
Mark Adler 已提交
331 332

    if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
M
Mark Adler 已提交
333
        s->pending_buf == Z_NULL) {
M
Mark Adler 已提交
334
        s->status = FINISH_STATE;
335
        strm->msg = ERR_MSG(Z_MEM_ERROR);
M
Mark Adler 已提交
336 337
        deflateEnd (strm);
        return Z_MEM_ERROR;
M
Mark Adler 已提交
338
    }
M
Mark Adler 已提交
339 340
    s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
    s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
M
Mark Adler 已提交
341 342 343

    s->level = level;
    s->strategy = strategy;
M
Mark Adler 已提交
344
    s->method = (Byte)method;
M
Mark Adler 已提交
345 346 347 348

    return deflateReset(strm);
}

349 350 351 352 353 354 355 356 357 358 359 360
/* =========================================================================
 * Check for a valid deflate stream state. Return 0 if ok, 1 if not.
 */
local int deflateStateCheck (strm)
    z_streamp strm;
{
    deflate_state *s;
    if (strm == Z_NULL ||
        strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)
        return 1;
    s = strm->state;
    if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE &&
361 362 363
#ifdef GZIP
                                           s->status != GZIP_STATE &&
#endif
364 365 366 367 368 369 370 371 372 373
                                           s->status != EXTRA_STATE &&
                                           s->status != NAME_STATE &&
                                           s->status != COMMENT_STATE &&
                                           s->status != HCRC_STATE &&
                                           s->status != BUSY_STATE &&
                                           s->status != FINISH_STATE))
        return 1;
    return 0;
}

M
Mark Adler 已提交
374
/* ========================================================================= */
M
Mark Adler 已提交
375
int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
M
Mark Adler 已提交
376
    z_streamp strm;
M
Mark Adler 已提交
377 378
    const Bytef *dictionary;
    uInt  dictLength;
M
Mark Adler 已提交
379
{
M
Mark Adler 已提交
380
    deflate_state *s;
381 382 383
    uInt str, n;
    int wrap;
    unsigned avail;
384
    z_const unsigned char *next;
M
Mark Adler 已提交
385

386
    if (deflateStateCheck(strm) || dictionary == Z_NULL)
M
Mark Adler 已提交
387
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
388
    s = strm->state;
389 390 391
    wrap = s->wrap;
    if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
392

393 394 395 396 397 398 399 400 401 402 403
    /* when using zlib wrappers, compute Adler-32 for provided dictionary */
    if (wrap == 1)
        strm->adler = adler32(strm->adler, dictionary, dictLength);
    s->wrap = 0;                    /* avoid computing Adler-32 in read_buf */

    /* if dictionary would fill window, just replace the history */
    if (dictLength >= s->w_size) {
        if (wrap == 0) {            /* already empty otherwise */
            CLEAR_HASH(s);
            s->strstart = 0;
            s->block_start = 0L;
404
            s->insert = 0;
405 406 407
        }
        dictionary += dictLength - s->w_size;  /* use the tail */
        dictLength = s->w_size;
M
Mark Adler 已提交
408 409
    }

410 411 412 413
    /* insert dictionary into window and hash */
    avail = strm->avail_in;
    next = strm->next_in;
    strm->avail_in = dictLength;
414
    strm->next_in = (z_const Bytef *)dictionary;
415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
    fill_window(s);
    while (s->lookahead >= MIN_MATCH) {
        str = s->strstart;
        n = s->lookahead - (MIN_MATCH-1);
        do {
            UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
#ifndef FASTEST
            s->prev[str & s->w_mask] = s->head[s->ins_h];
#endif
            s->head[s->ins_h] = (Pos)str;
            str++;
        } while (--n);
        s->strstart = str;
        s->lookahead = MIN_MATCH-1;
        fill_window(s);
M
Mark Adler 已提交
430
    }
431 432
    s->strstart += s->lookahead;
    s->block_start = (long)s->strstart;
433
    s->insert = s->lookahead;
434 435 436 437 438 439
    s->lookahead = 0;
    s->match_length = s->prev_length = MIN_MATCH-1;
    s->match_available = 0;
    strm->next_in = next;
    strm->avail_in = avail;
    s->wrap = wrap;
M
Mark Adler 已提交
440 441 442
    return Z_OK;
}

M
Mark Adler 已提交
443 444 445 446 447 448 449
/* ========================================================================= */
int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength)
    z_streamp strm;
    Bytef *dictionary;
    uInt  *dictLength;
{
    deflate_state *s;
450
    uInt len;
M
Mark Adler 已提交
451 452 453 454

    if (deflateStateCheck(strm))
        return Z_STREAM_ERROR;
    s = strm->state;
455
    len = s->strstart + s->lookahead;
M
Mark Adler 已提交
456 457 458 459 460 461 462 463 464
    if (len > s->w_size)
        len = s->w_size;
    if (dictionary != Z_NULL && len)
        zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len);
    if (dictLength != Z_NULL)
        *dictLength = len;
    return Z_OK;
}

M
Mark Adler 已提交
465
/* ========================================================================= */
466
int ZEXPORT deflateResetKeep (strm)
M
Mark Adler 已提交
467
    z_streamp strm;
M
Mark Adler 已提交
468 469
{
    deflate_state *s;
M
Mark Adler 已提交
470

471
    if (deflateStateCheck(strm)) {
M
Mark Adler 已提交
472 473
        return Z_STREAM_ERROR;
    }
M
Mark Adler 已提交
474 475 476 477 478 479 480 481 482

    strm->total_in = strm->total_out = 0;
    strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
    strm->data_type = Z_UNKNOWN;

    s = (deflate_state *)strm->state;
    s->pending = 0;
    s->pending_out = s->pending_buf;

M
Mark Adler 已提交
483 484
    if (s->wrap < 0) {
        s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
M
Mark Adler 已提交
485
    }
486 487 488 489 490
    s->status =
#ifdef GZIP
        s->wrap == 2 ? GZIP_STATE :
#endif
        s->wrap ? INIT_STATE : BUSY_STATE;
M
Mark Adler 已提交
491 492 493 494 495
    strm->adler =
#ifdef GZIP
        s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
#endif
        adler32(0L, Z_NULL, 0);
M
Mark Adler 已提交
496
    s->last_flush = Z_NO_FLUSH;
M
Mark Adler 已提交
497

M
Mark Adler 已提交
498
    _tr_init(s);
M
Mark Adler 已提交
499 500 501 502

    return Z_OK;
}

503 504 505 506 507 508 509 510 511 512 513 514
/* ========================================================================= */
int ZEXPORT deflateReset (strm)
    z_streamp strm;
{
    int ret;

    ret = deflateResetKeep(strm);
    if (ret == Z_OK)
        lm_init(strm->state);
    return ret;
}

M
Mark Adler 已提交
515 516 517 518 519
/* ========================================================================= */
int ZEXPORT deflateSetHeader (strm, head)
    z_streamp strm;
    gz_headerp head;
{
520 521
    if (deflateStateCheck(strm) || strm->state->wrap != 2)
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
522 523 524 525
    strm->state->gzhead = head;
    return Z_OK;
}

M
Mark Adler 已提交
526 527 528 529 530 531
/* ========================================================================= */
int ZEXPORT deflatePending (strm, pending, bits)
    unsigned *pending;
    int *bits;
    z_streamp strm;
{
532
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
533 534 535 536
    if (pending != Z_NULL)
        *pending = strm->state->pending;
    if (bits != Z_NULL)
        *bits = strm->state->bi_valid;
M
Mark Adler 已提交
537 538 539
    return Z_OK;
}

M
Mark Adler 已提交
540 541 542 543 544 545
/* ========================================================================= */
int ZEXPORT deflatePrime (strm, bits, value)
    z_streamp strm;
    int bits;
    int value;
{
546 547 548
    deflate_state *s;
    int put;

549
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
550 551 552 553 554 555 556 557 558 559 560 561 562
    s = strm->state;
    if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3))
        return Z_BUF_ERROR;
    do {
        put = Buf_size - s->bi_valid;
        if (put > bits)
            put = bits;
        s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
        s->bi_valid += put;
        _tr_flush_bits(s);
        value >>= put;
        bits -= put;
    } while (bits);
M
Mark Adler 已提交
563 564 565
    return Z_OK;
}

M
Mark Adler 已提交
566
/* ========================================================================= */
M
Mark Adler 已提交
567
int ZEXPORT deflateParams(strm, level, strategy)
M
Mark Adler 已提交
568
    z_streamp strm;
M
Mark Adler 已提交
569 570 571 572 573 574
    int level;
    int strategy;
{
    deflate_state *s;
    compress_func func;

575
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
576 577
    s = strm->state;

M
Mark Adler 已提交
578 579 580 581 582
#ifdef FASTEST
    if (level != 0) level = 1;
#else
    if (level == Z_DEFAULT_COMPRESSION) level = 6;
#endif
M
Mark Adler 已提交
583
    if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
M
Mark Adler 已提交
584
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
585 586 587
    }
    func = configuration_table[s->level].func;

588
    if ((strategy != s->strategy || func != configuration_table[level].func)) {
M
Mark Adler 已提交
589
        /* Flush the last buffer: */
590 591 592 593 594
        int err = deflate(strm, Z_BLOCK);
        if (err == Z_STREAM_ERROR)
            return err;
        if (strm->avail_out == 0)
            return Z_BUF_ERROR;
M
Mark Adler 已提交
595 596
    }
    if (s->level != level) {
597 598 599 600 601 602 603
        if (s->level == 0 && s->matches != 0) {
            if (s->matches == 1)
                slide_hash(s);
            else
                CLEAR_HASH(s);
            s->matches = 0;
        }
M
Mark Adler 已提交
604 605 606 607 608
        s->level = level;
        s->max_lazy_match   = configuration_table[level].max_lazy;
        s->good_match       = configuration_table[level].good_length;
        s->nice_match       = configuration_table[level].nice_length;
        s->max_chain_length = configuration_table[level].max_chain;
M
Mark Adler 已提交
609 610
    }
    s->strategy = strategy;
611
    return Z_OK;
M
Mark Adler 已提交
612 613
}

M
Mark Adler 已提交
614 615 616 617 618 619 620 621 622 623
/* ========================================================================= */
int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
    z_streamp strm;
    int good_length;
    int max_lazy;
    int nice_length;
    int max_chain;
{
    deflate_state *s;

624
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
625
    s = strm->state;
M
Mark Adler 已提交
626 627
    s->good_match = (uInt)good_length;
    s->max_lazy_match = (uInt)max_lazy;
M
Mark Adler 已提交
628
    s->nice_match = nice_length;
M
Mark Adler 已提交
629
    s->max_chain_length = (uInt)max_chain;
M
Mark Adler 已提交
630 631 632
    return Z_OK;
}

M
Mark Adler 已提交
633 634 635 636 637 638 639 640 641 642 643 644
/* =========================================================================
 * For the default windowBits of 15 and memLevel of 8, this function returns
 * a close to exact, as well as small, upper bound on the compressed size.
 * They are coded as constants here for a reason--if the #define's are
 * changed, then this function needs to be changed as well.  The return
 * value for 15 and 8 only works for those exact settings.
 *
 * For any setting other than those defaults for windowBits and memLevel,
 * the value returned is a conservative worst case for the maximum expansion
 * resulting from using fixed blocks instead of stored blocks, which deflate
 * can emit on compressed data for some combinations of the parameters.
 *
M
Mark Adler 已提交
645 646 647 648
 * This function could be more sophisticated to provide closer upper bounds for
 * every combination of windowBits and memLevel.  But even the conservative
 * upper bound of about 14% expansion does not seem onerous for output buffer
 * allocation.
M
Mark Adler 已提交
649 650 651 652 653 654
 */
uLong ZEXPORT deflateBound(strm, sourceLen)
    z_streamp strm;
    uLong sourceLen;
{
    deflate_state *s;
M
Mark Adler 已提交
655
    uLong complen, wraplen;
M
Mark Adler 已提交
656

M
Mark Adler 已提交
657 658 659
    /* conservative upper bound for compressed data */
    complen = sourceLen +
              ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
M
Mark Adler 已提交
660

M
Mark Adler 已提交
661
    /* if can't get parameters, return conservative bound plus zlib wrapper */
662
    if (deflateStateCheck(strm))
M
Mark Adler 已提交
663
        return complen + 6;
M
Mark Adler 已提交
664

M
Mark Adler 已提交
665
    /* compute wrapper length */
M
Mark Adler 已提交
666
    s = strm->state;
M
Mark Adler 已提交
667 668 669 670 671 672 673
    switch (s->wrap) {
    case 0:                                 /* raw deflate */
        wraplen = 0;
        break;
    case 1:                                 /* zlib wrapper */
        wraplen = 6 + (s->strstart ? 4 : 0);
        break;
674
#ifdef GZIP
M
Mark Adler 已提交
675 676
    case 2:                                 /* gzip wrapper */
        wraplen = 18;
M
Mark Adler 已提交
677
        if (s->gzhead != Z_NULL) {          /* user-supplied gzip header */
678
            Bytef *str;
M
Mark Adler 已提交
679
            if (s->gzhead->extra != Z_NULL)
M
Mark Adler 已提交
680 681
                wraplen += 2 + s->gzhead->extra_len;
            str = s->gzhead->name;
M
Mark Adler 已提交
682
            if (str != Z_NULL)
M
Mark Adler 已提交
683 684 685 686
                do {
                    wraplen++;
                } while (*str++);
            str = s->gzhead->comment;
M
Mark Adler 已提交
687
            if (str != Z_NULL)
M
Mark Adler 已提交
688 689 690 691 692 693 694
                do {
                    wraplen++;
                } while (*str++);
            if (s->gzhead->hcrc)
                wraplen += 2;
        }
        break;
695
#endif
M
Mark Adler 已提交
696 697 698 699 700
    default:                                /* for compiler happiness */
        wraplen = 6;
    }

    /* if not default parameters, return conservative bound */
M
Mark Adler 已提交
701
    if (s->w_bits != 15 || s->hash_bits != 8 + 7)
M
Mark Adler 已提交
702
        return complen + wraplen;
M
Mark Adler 已提交
703 704

    /* default settings: return tight bound for that case */
M
Mark Adler 已提交
705 706
    return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
           (sourceLen >> 25) + 13 - 6 + wraplen;
M
Mark Adler 已提交
707 708
}

M
Mark Adler 已提交
709
/* =========================================================================
M
Mark Adler 已提交
710
 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
M
Mark Adler 已提交
711
 * IN assertion: the stream state is correct and there is enough room in
M
Mark Adler 已提交
712
 * pending_buf.
M
Mark Adler 已提交
713 714 715 716 717
 */
local void putShortMSB (s, b)
    deflate_state *s;
    uInt b;
{
M
Mark Adler 已提交
718 719
    put_byte(s, (Byte)(b >> 8));
    put_byte(s, (Byte)(b & 0xff));
M
Mark Adler 已提交
720
}
M
Mark Adler 已提交
721 722

/* =========================================================================
723 724 725 726
 * Flush as much pending output as possible. All deflate() output, except for
 * some deflate_stored() output, goes through this function so some
 * applications may wish to modify it to avoid allocating a large
 * strm->next_out buffer and copying into it. (See also read_buf()).
M
Mark Adler 已提交
727 728
 */
local void flush_pending(strm)
M
Mark Adler 已提交
729
    z_streamp strm;
M
Mark Adler 已提交
730
{
731 732
    unsigned len;
    deflate_state *s = strm->state;
M
Mark Adler 已提交
733

734 735
    _tr_flush_bits(s);
    len = s->pending;
M
Mark Adler 已提交
736 737 738
    if (len > strm->avail_out) len = strm->avail_out;
    if (len == 0) return;

739
    zmemcpy(strm->next_out, s->pending_out, len);
M
Mark Adler 已提交
740
    strm->next_out  += len;
741
    s->pending_out  += len;
M
Mark Adler 已提交
742
    strm->total_out += len;
743 744
    strm->avail_out -= len;
    s->pending      -= len;
745 746
    if (s->pending == 0) {
        s->pending_out = s->pending_buf;
M
Mark Adler 已提交
747 748 749
    }
}

750 751 752 753 754 755 756 757 758 759
/* ===========================================================================
 * Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
 */
#define HCRC_UPDATE(beg) \
    do { \
        if (s->gzhead->hcrc && s->pending > (beg)) \
            strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
                                s->pending - (beg)); \
    } while (0)

M
Mark Adler 已提交
760
/* ========================================================================= */
M
Mark Adler 已提交
761
int ZEXPORT deflate (strm, flush)
M
Mark Adler 已提交
762
    z_streamp strm;
M
Mark Adler 已提交
763 764
    int flush;
{
M
Mark Adler 已提交
765
    int old_flush; /* value of flush param for previous deflate call */
M
Mark Adler 已提交
766
    deflate_state *s;
M
Mark Adler 已提交
767

768
    if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) {
M
Mark Adler 已提交
769 770
        return Z_STREAM_ERROR;
    }
M
Mark Adler 已提交
771 772
    s = strm->state;

M
Mark Adler 已提交
773
    if (strm->next_out == Z_NULL ||
774
        (strm->avail_in != 0 && strm->next_in == Z_NULL) ||
M
Mark Adler 已提交
775
        (s->status == FINISH_STATE && flush != Z_FINISH)) {
M
Mark Adler 已提交
776
        ERR_RETURN(strm, Z_STREAM_ERROR);
M
Mark Adler 已提交
777 778 779
    }
    if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

M
Mark Adler 已提交
780 781
    old_flush = s->last_flush;
    s->last_flush = flush;
M
Mark Adler 已提交
782

783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810
    /* Flush as much pending output as possible */
    if (s->pending != 0) {
        flush_pending(strm);
        if (strm->avail_out == 0) {
            /* Since avail_out is 0, deflate will be called again with
             * more output space, but possibly with both pending and
             * avail_in equal to zero. There won't be anything to do,
             * but this is not an error situation so make sure we
             * return OK instead of BUF_ERROR at next call of deflate:
             */
            s->last_flush = -1;
            return Z_OK;
        }

    /* Make sure there is something to do and avoid duplicate consecutive
     * flushes. For repeated and useless calls with Z_FINISH, we keep
     * returning Z_STREAM_END instead of Z_BUF_ERROR.
     */
    } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
               flush != Z_FINISH) {
        ERR_RETURN(strm, Z_BUF_ERROR);
    }

    /* User must not provide more input after the first FINISH: */
    if (s->status == FINISH_STATE && strm->avail_in != 0) {
        ERR_RETURN(strm, Z_BUF_ERROR);
    }

M
Mark Adler 已提交
811
    /* Write the header */
M
Mark Adler 已提交
812
    if (s->status == INIT_STATE) {
813 814 815 816 817 818 819 820 821 822
        /* zlib header */
        uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
        uInt level_flags;

        if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
            level_flags = 0;
        else if (s->level < 6)
            level_flags = 1;
        else if (s->level == 6)
            level_flags = 2;
M
Mark Adler 已提交
823
        else
824 825 826 827 828 829 830 831 832 833 834 835 836 837
            level_flags = 3;
        header |= (level_flags << 6);
        if (s->strstart != 0) header |= PRESET_DICT;
        header += 31 - (header % 31);

        putShortMSB(s, header);

        /* Save the adler32 of the preset dictionary: */
        if (s->strstart != 0) {
            putShortMSB(s, (uInt)(strm->adler >> 16));
            putShortMSB(s, (uInt)(strm->adler & 0xffff));
        }
        strm->adler = adler32(0L, Z_NULL, 0);
        s->status = BUSY_STATE;
M
Mark Adler 已提交
838

839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
        /* Compression must start with an empty pending buffer */
        flush_pending(strm);
        if (s->pending != 0) {
            s->last_flush = -1;
            return Z_OK;
        }
    }
#ifdef GZIP
    if (s->status == GZIP_STATE) {
        /* gzip header */
        strm->adler = crc32(0L, Z_NULL, 0);
        put_byte(s, 31);
        put_byte(s, 139);
        put_byte(s, 8);
        if (s->gzhead == Z_NULL) {
            put_byte(s, 0);
            put_byte(s, 0);
            put_byte(s, 0);
            put_byte(s, 0);
            put_byte(s, 0);
            put_byte(s, s->level == 9 ? 2 :
                     (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
                      4 : 0));
            put_byte(s, OS_CODE);
M
Mark Adler 已提交
863
            s->status = BUSY_STATE;
M
Mark Adler 已提交
864

865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889
            /* Compression must start with an empty pending buffer */
            flush_pending(strm);
            if (s->pending != 0) {
                s->last_flush = -1;
                return Z_OK;
            }
        }
        else {
            put_byte(s, (s->gzhead->text ? 1 : 0) +
                     (s->gzhead->hcrc ? 2 : 0) +
                     (s->gzhead->extra == Z_NULL ? 0 : 4) +
                     (s->gzhead->name == Z_NULL ? 0 : 8) +
                     (s->gzhead->comment == Z_NULL ? 0 : 16)
                     );
            put_byte(s, (Byte)(s->gzhead->time & 0xff));
            put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
            put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
            put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
            put_byte(s, s->level == 9 ? 2 :
                     (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
                      4 : 0));
            put_byte(s, s->gzhead->os & 0xff);
            if (s->gzhead->extra != Z_NULL) {
                put_byte(s, s->gzhead->extra_len & 0xff);
                put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
M
Mark Adler 已提交
890
            }
891 892 893 894 895
            if (s->gzhead->hcrc)
                strm->adler = crc32(strm->adler, s->pending_buf,
                                    s->pending);
            s->gzindex = 0;
            s->status = EXTRA_STATE;
M
Mark Adler 已提交
896
        }
M
Mark Adler 已提交
897
    }
M
Mark Adler 已提交
898
    if (s->status == EXTRA_STATE) {
M
Mark Adler 已提交
899
        if (s->gzhead->extra != Z_NULL) {
900 901 902 903 904 905 906 907 908 909 910 911 912
            ulg beg = s->pending;   /* start of bytes to update crc */
            uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex;
            while (s->pending + left > s->pending_buf_size) {
                uInt copy = s->pending_buf_size - s->pending;
                zmemcpy(s->pending_buf + s->pending,
                        s->gzhead->extra + s->gzindex, copy);
                s->pending = s->pending_buf_size;
                HCRC_UPDATE(beg);
                s->gzindex += copy;
                flush_pending(strm);
                if (s->pending != 0) {
                    s->last_flush = -1;
                    return Z_OK;
M
Mark Adler 已提交
913
                }
914 915
                beg = 0;
                left -= copy;
M
Mark Adler 已提交
916
            }
917 918 919 920 921
            zmemcpy(s->pending_buf + s->pending,
                    s->gzhead->extra + s->gzindex, left);
            s->pending += left;
            HCRC_UPDATE(beg);
            s->gzindex = 0;
M
Mark Adler 已提交
922
        }
923
        s->status = NAME_STATE;
M
Mark Adler 已提交
924 925
    }
    if (s->status == NAME_STATE) {
M
Mark Adler 已提交
926
        if (s->gzhead->name != Z_NULL) {
927
            ulg beg = s->pending;   /* start of bytes to update crc */
M
Mark Adler 已提交
928 929 930
            int val;
            do {
                if (s->pending == s->pending_buf_size) {
931
                    HCRC_UPDATE(beg);
M
Mark Adler 已提交
932
                    flush_pending(strm);
933 934 935
                    if (s->pending != 0) {
                        s->last_flush = -1;
                        return Z_OK;
M
Mark Adler 已提交
936
                    }
937
                    beg = 0;
M
Mark Adler 已提交
938 939 940 941
                }
                val = s->gzhead->name[s->gzindex++];
                put_byte(s, val);
            } while (val != 0);
942 943
            HCRC_UPDATE(beg);
            s->gzindex = 0;
M
Mark Adler 已提交
944
        }
945
        s->status = COMMENT_STATE;
M
Mark Adler 已提交
946 947
    }
    if (s->status == COMMENT_STATE) {
M
Mark Adler 已提交
948
        if (s->gzhead->comment != Z_NULL) {
949
            ulg beg = s->pending;   /* start of bytes to update crc */
M
Mark Adler 已提交
950 951 952
            int val;
            do {
                if (s->pending == s->pending_buf_size) {
953
                    HCRC_UPDATE(beg);
M
Mark Adler 已提交
954
                    flush_pending(strm);
955 956 957
                    if (s->pending != 0) {
                        s->last_flush = -1;
                        return Z_OK;
M
Mark Adler 已提交
958
                    }
959
                    beg = 0;
M
Mark Adler 已提交
960 961 962 963
                }
                val = s->gzhead->comment[s->gzindex++];
                put_byte(s, val);
            } while (val != 0);
964
            HCRC_UPDATE(beg);
M
Mark Adler 已提交
965
        }
966
        s->status = HCRC_STATE;
M
Mark Adler 已提交
967 968 969
    }
    if (s->status == HCRC_STATE) {
        if (s->gzhead->hcrc) {
970
            if (s->pending + 2 > s->pending_buf_size) {
M
Mark Adler 已提交
971
                flush_pending(strm);
972 973 974 975
                if (s->pending != 0) {
                    s->last_flush = -1;
                    return Z_OK;
                }
M
Mark Adler 已提交
976
            }
977 978 979
            put_byte(s, (Byte)(strm->adler & 0xff));
            put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
            strm->adler = crc32(0L, Z_NULL, 0);
M
Mark Adler 已提交
980
        }
981
        s->status = BUSY_STATE;
M
Mark Adler 已提交
982

983
        /* Compression must start with an empty pending buffer */
M
Mark Adler 已提交
984
        flush_pending(strm);
985
        if (s->pending != 0) {
M
Mark Adler 已提交
986 987 988
            s->last_flush = -1;
            return Z_OK;
        }
M
Mark Adler 已提交
989
    }
990
#endif
M
Mark Adler 已提交
991 992 993

    /* Start a new block or continue the current one.
     */
M
Mark Adler 已提交
994 995
    if (strm->avail_in != 0 || s->lookahead != 0 ||
        (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
M
Mark Adler 已提交
996
        block_state bstate;
M
Mark Adler 已提交
997

998 999 1000 1001
        bstate = s->level == 0 ? deflate_stored(s, flush) :
                 s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
                 s->strategy == Z_RLE ? deflate_rle(s, flush) :
                 (*(configuration_table[s->level].func))(s, flush);
M
Mark Adler 已提交
1002 1003

        if (bstate == finish_started || bstate == finish_done) {
M
Mark Adler 已提交
1004
            s->status = FINISH_STATE;
M
Mark Adler 已提交
1005
        }
M
Mark Adler 已提交
1006
        if (bstate == need_more || bstate == finish_started) {
M
Mark Adler 已提交
1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018
            if (strm->avail_out == 0) {
                s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
            }
            return Z_OK;
            /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
             * of deflate should use the same flush parameter to make sure
             * that the flush is complete. So we don't have to output an
             * empty block here, this will be done at next call. This also
             * ensures that for a very small output buffer, we emit at most
             * one empty block.
             */
        }
M
Mark Adler 已提交
1019
        if (bstate == block_done) {
M
Mark Adler 已提交
1020
            if (flush == Z_PARTIAL_FLUSH) {
M
Mark Adler 已提交
1021
                _tr_align(s);
M
Mark Adler 已提交
1022
            } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
M
Mark Adler 已提交
1023
                _tr_stored_block(s, (char*)0, 0L, 0);
M
Mark Adler 已提交
1024 1025 1026 1027
                /* For a full flush, this empty block will be recognized
                 * as a special marker by inflate_sync().
                 */
                if (flush == Z_FULL_FLUSH) {
M
Mark Adler 已提交
1028
                    CLEAR_HASH(s);             /* forget history */
M
Mark Adler 已提交
1029 1030 1031
                    if (s->lookahead == 0) {
                        s->strstart = 0;
                        s->block_start = 0L;
1032
                        s->insert = 0;
M
Mark Adler 已提交
1033
                    }
M
Mark Adler 已提交
1034 1035
                }
            }
M
Mark Adler 已提交
1036
            flush_pending(strm);
M
Mark Adler 已提交
1037 1038 1039 1040
            if (strm->avail_out == 0) {
              s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
              return Z_OK;
            }
M
Mark Adler 已提交
1041
        }
M
Mark Adler 已提交
1042 1043
    }

M
Mark Adler 已提交
1044
    if (flush != Z_FINISH) return Z_OK;
M
Mark Adler 已提交
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064
    if (s->wrap <= 0) return Z_STREAM_END;

    /* Write the trailer */
#ifdef GZIP
    if (s->wrap == 2) {
        put_byte(s, (Byte)(strm->adler & 0xff));
        put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
        put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
        put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
        put_byte(s, (Byte)(strm->total_in & 0xff));
        put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
        put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
        put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
    }
    else
#endif
    {
        putShortMSB(s, (uInt)(strm->adler >> 16));
        putShortMSB(s, (uInt)(strm->adler & 0xffff));
    }
M
Mark Adler 已提交
1065 1066 1067 1068
    flush_pending(strm);
    /* If avail_out is zero, the application will call deflate again
     * to flush the rest.
     */
M
Mark Adler 已提交
1069
    if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
M
Mark Adler 已提交
1070
    return s->pending != 0 ? Z_OK : Z_STREAM_END;
M
Mark Adler 已提交
1071 1072 1073
}

/* ========================================================================= */
M
Mark Adler 已提交
1074
int ZEXPORT deflateEnd (strm)
M
Mark Adler 已提交
1075
    z_streamp strm;
M
Mark Adler 已提交
1076
{
M
Mark Adler 已提交
1077 1078
    int status;

1079
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
1080

M
Mark Adler 已提交
1081 1082
    status = strm->state->status;

M
Mark Adler 已提交
1083
    /* Deallocate in reverse order of allocations: */
M
Mark Adler 已提交
1084
    TRY_FREE(strm, strm->state->pending_buf);
M
Mark Adler 已提交
1085 1086 1087
    TRY_FREE(strm, strm->state->head);
    TRY_FREE(strm, strm->state->prev);
    TRY_FREE(strm, strm->state->window);
M
Mark Adler 已提交
1088 1089 1090 1091

    ZFREE(strm, strm->state);
    strm->state = Z_NULL;

M
Mark Adler 已提交
1092
    return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
M
Mark Adler 已提交
1093 1094
}

M
Mark Adler 已提交
1095 1096 1097 1098 1099
/* =========================================================================
 * Copy the source state to the destination state.
 * To simplify the source, this is not supported for 16-bit MSDOS (which
 * doesn't have enough memory anyway to duplicate compression states).
 */
M
Mark Adler 已提交
1100
int ZEXPORT deflateCopy (dest, source)
M
Mark Adler 已提交
1101 1102
    z_streamp dest;
    z_streamp source;
M
Mark Adler 已提交
1103
{
M
Mark Adler 已提交
1104 1105 1106 1107 1108 1109 1110 1111
#ifdef MAXSEG_64K
    return Z_STREAM_ERROR;
#else
    deflate_state *ds;
    deflate_state *ss;
    ushf *overlay;


1112
    if (deflateStateCheck(source) || dest == Z_NULL) {
M
Mark Adler 已提交
1113
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
1114
    }
M
Mark Adler 已提交
1115 1116 1117

    ss = source->state;

1118
    zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
M
Mark Adler 已提交
1119

M
Mark Adler 已提交
1120 1121 1122
    ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
    if (ds == Z_NULL) return Z_MEM_ERROR;
    dest->state = (struct internal_state FAR *) ds;
1123
    zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
M
Mark Adler 已提交
1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138
    ds->strm = dest;

    ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
    ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));
    ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));
    overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
    ds->pending_buf = (uchf *) overlay;

    if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
        ds->pending_buf == Z_NULL) {
        deflateEnd (dest);
        return Z_MEM_ERROR;
    }
    /* following zmemcpy do not work for 16-bit MSDOS */
    zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
1139 1140
    zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
    zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
M
Mark Adler 已提交
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
    zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);

    ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
    ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
    ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;

    ds->l_desc.dyn_tree = ds->dyn_ltree;
    ds->d_desc.dyn_tree = ds->dyn_dtree;
    ds->bl_desc.dyn_tree = ds->bl_tree;

M
Mark Adler 已提交
1151
    return Z_OK;
M
Mark Adler 已提交
1152
#endif /* MAXSEG_64K */
M
Mark Adler 已提交
1153 1154 1155 1156
}

/* ===========================================================================
 * Read a new buffer from the current input stream, update the adler32
M
Mark Adler 已提交
1157 1158 1159 1160
 * and total number of bytes read.  All deflate() input goes through
 * this function so some applications may wish to modify it to avoid
 * allocating a large strm->next_in buffer and copying from it.
 * (See also flush_pending()).
M
Mark Adler 已提交
1161
 */
M
Mark Adler 已提交
1162
local unsigned read_buf(strm, buf, size)
M
Mark Adler 已提交
1163
    z_streamp strm;
M
Mark Adler 已提交
1164
    Bytef *buf;
M
Mark Adler 已提交
1165 1166 1167 1168 1169 1170 1171 1172 1173
    unsigned size;
{
    unsigned len = strm->avail_in;

    if (len > size) len = size;
    if (len == 0) return 0;

    strm->avail_in  -= len;

M
Mark Adler 已提交
1174
    zmemcpy(buf, strm->next_in, len);
M
Mark Adler 已提交
1175
    if (strm->state->wrap == 1) {
M
Mark Adler 已提交
1176
        strm->adler = adler32(strm->adler, buf, len);
M
Mark Adler 已提交
1177
    }
M
Mark Adler 已提交
1178 1179
#ifdef GZIP
    else if (strm->state->wrap == 2) {
M
Mark Adler 已提交
1180
        strm->adler = crc32(strm->adler, buf, len);
M
Mark Adler 已提交
1181 1182
    }
#endif
M
Mark Adler 已提交
1183 1184 1185
    strm->next_in  += len;
    strm->total_in += len;

M
Mark Adler 已提交
1186
    return len;
M
Mark Adler 已提交
1187 1188 1189 1190 1191 1192 1193 1194 1195 1196
}

/* ===========================================================================
 * Initialize the "longest match" routines for a new zlib stream
 */
local void lm_init (s)
    deflate_state *s;
{
    s->window_size = (ulg)2L*s->w_size;

M
Mark Adler 已提交
1197
    CLEAR_HASH(s);
M
Mark Adler 已提交
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208

    /* Set the default configuration parameters:
     */
    s->max_lazy_match   = configuration_table[s->level].max_lazy;
    s->good_match       = configuration_table[s->level].good_length;
    s->nice_match       = configuration_table[s->level].nice_length;
    s->max_chain_length = configuration_table[s->level].max_chain;

    s->strstart = 0;
    s->block_start = 0L;
    s->lookahead = 0;
1209
    s->insert = 0;
M
Mark Adler 已提交
1210
    s->match_length = s->prev_length = MIN_MATCH-1;
M
Mark Adler 已提交
1211
    s->match_available = 0;
M
Mark Adler 已提交
1212
    s->ins_h = 0;
M
Mark Adler 已提交
1213
#ifndef FASTEST
M
Mark Adler 已提交
1214 1215 1216
#ifdef ASMV
    match_init(); /* initialize the asm code */
#endif
M
Mark Adler 已提交
1217
#endif
M
Mark Adler 已提交
1218 1219
}

M
Mark Adler 已提交
1220
#ifndef FASTEST
M
Mark Adler 已提交
1221 1222 1223 1224 1225 1226 1227
/* ===========================================================================
 * Set match_start to the longest match starting at the given string and
 * return its length. Matches shorter or equal to prev_length are discarded,
 * in which case the result is equal to prev_length and match_start is
 * garbage.
 * IN assertions: cur_match is the head of the hash chain for the current
 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
M
Mark Adler 已提交
1228
 * OUT assertion: the match length is not greater than s->lookahead.
M
Mark Adler 已提交
1229 1230 1231 1232 1233
 */
#ifndef ASMV
/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
 * match.S. The code will be functionally equivalent.
 */
M
Mark Adler 已提交
1234
local uInt longest_match(s, cur_match)
M
Mark Adler 已提交
1235 1236 1237 1238
    deflate_state *s;
    IPos cur_match;                             /* current match */
{
    unsigned chain_length = s->max_chain_length;/* max hash chain length */
M
Mark Adler 已提交
1239
    register Bytef *scan = s->window + s->strstart; /* current string */
M
Mark Adler 已提交
1240
    register Bytef *match;                      /* matched string */
M
Mark Adler 已提交
1241
    register int len;                           /* length of current match */
M
Mark Adler 已提交
1242
    int best_len = (int)s->prev_length;         /* best match length so far */
M
Mark Adler 已提交
1243
    int nice_match = s->nice_match;             /* stop if match long enough */
M
Mark Adler 已提交
1244
    IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
M
Mark Adler 已提交
1245
        s->strstart - (IPos)MAX_DIST(s) : NIL;
M
Mark Adler 已提交
1246 1247 1248
    /* Stop when cur_match becomes <= limit. To simplify the code,
     * we prevent matches with the string of window index 0.
     */
M
Mark Adler 已提交
1249
    Posf *prev = s->prev;
M
Mark Adler 已提交
1250
    uInt wmask = s->w_mask;
M
Mark Adler 已提交
1251 1252 1253 1254 1255

#ifdef UNALIGNED_OK
    /* Compare two bytes at a time. Note: this is not always beneficial.
     * Try with and without -DUNALIGNED_OK to check.
     */
M
Mark Adler 已提交
1256
    register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
M
Mark Adler 已提交
1257 1258
    register ush scan_start = *(ushf*)scan;
    register ush scan_end   = *(ushf*)(scan+best_len-1);
M
Mark Adler 已提交
1259
#else
M
Mark Adler 已提交
1260
    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
M
Mark Adler 已提交
1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273
    register Byte scan_end1  = scan[best_len-1];
    register Byte scan_end   = scan[best_len];
#endif

    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
     * It is easy to get rid of this optimization if necessary.
     */
    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");

    /* Do not waste too much time if we already have a good match: */
    if (s->prev_length >= s->good_match) {
        chain_length >>= 2;
    }
M
Mark Adler 已提交
1274 1275 1276
    /* Do not look for matches beyond the end of the input. This is necessary
     * to make deflate deterministic.
     */
M
Mark Adler 已提交
1277
    if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead;
M
Mark Adler 已提交
1278

M
Mark Adler 已提交
1279
    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
M
Mark Adler 已提交
1280 1281 1282 1283 1284 1285

    do {
        Assert(cur_match < s->strstart, "no future");
        match = s->window + cur_match;

        /* Skip to next match if the match length cannot increase
M
Mark Adler 已提交
1286 1287 1288 1289 1290 1291
         * or if the match length is less than 2.  Note that the checks below
         * for insufficient lookahead only occur occasionally for performance
         * reasons.  Therefore uninitialized memory will be accessed, and
         * conditional jumps will be made that depend on those values.
         * However the length of the match is limited to the lookahead, so
         * the output of deflate is not affected by the uninitialized values.
M
Mark Adler 已提交
1292 1293 1294 1295 1296
         */
#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
        /* This code assumes sizeof(unsigned short) == 2. Do not use
         * UNALIGNED_OK if your compiler uses a different size.
         */
M
Mark Adler 已提交
1297 1298
        if (*(ushf*)(match+best_len-1) != scan_end ||
            *(ushf*)match != scan_start) continue;
M
Mark Adler 已提交
1299 1300 1301 1302 1303 1304 1305 1306 1307 1308

        /* It is not necessary to compare scan[2] and match[2] since they are
         * always equal when the other bytes match, given that the hash keys
         * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
         * strstart+3, +5, ... up to strstart+257. We check for insufficient
         * lookahead only every 4th comparison; the 128th check will be made
         * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
         * necessary to put more guard bytes at the end of the window, or
         * to check more often for insufficient lookahead.
         */
M
Mark Adler 已提交
1309
        Assert(scan[2] == match[2], "scan[2]?");
M
Mark Adler 已提交
1310 1311
        scan++, match++;
        do {
M
Mark Adler 已提交
1312 1313 1314 1315
        } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
M
Mark Adler 已提交
1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339
                 scan < strend);
        /* The funny "do {}" generates better code on most compilers */

        /* Here, scan <= window+strstart+257 */
        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
        if (*scan == *match) scan++;

        len = (MAX_MATCH - 1) - (int)(strend-scan);
        scan = strend - (MAX_MATCH-1);

#else /* UNALIGNED_OK */

        if (match[best_len]   != scan_end  ||
            match[best_len-1] != scan_end1 ||
            *match            != *scan     ||
            *++match          != scan[1])      continue;

        /* The check at best_len-1 can be removed because it will be made
         * again later. (This heuristic is not always a win.)
         * It is not necessary to compare scan[2] and match[2] since they
         * are always equal when the other bytes match, given that
         * the hash keys are equal and that HASH_BITS >= 8.
         */
        scan += 2, match++;
M
Mark Adler 已提交
1340
        Assert(*scan == *match, "match[2]?");
M
Mark Adler 已提交
1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361

        /* We check for insufficient lookahead only every 8th comparison;
         * the 256th check will be made at strstart+258.
         */
        do {
        } while (*++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 scan < strend);

        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");

        len = MAX_MATCH - (int)(strend - scan);
        scan = strend - MAX_MATCH;

#endif /* UNALIGNED_OK */

        if (len > best_len) {
            s->match_start = cur_match;
            best_len = len;
M
Mark Adler 已提交
1362
            if (len >= nice_match) break;
M
Mark Adler 已提交
1363
#ifdef UNALIGNED_OK
M
Mark Adler 已提交
1364
            scan_end = *(ushf*)(scan+best_len-1);
M
Mark Adler 已提交
1365 1366 1367 1368 1369
#else
            scan_end1  = scan[best_len-1];
            scan_end   = scan[best_len];
#endif
        }
M
Mark Adler 已提交
1370
    } while ((cur_match = prev[cur_match & wmask]) > limit
M
Mark Adler 已提交
1371 1372
             && --chain_length != 0);

M
Mark Adler 已提交
1373
    if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
M
Mark Adler 已提交
1374
    return s->lookahead;
M
Mark Adler 已提交
1375
}
M
Mark Adler 已提交
1376
#endif /* ASMV */
M
Mark Adler 已提交
1377 1378

#else /* FASTEST */
M
Mark Adler 已提交
1379 1380

/* ---------------------------------------------------------------------------
M
Mark Adler 已提交
1381
 * Optimized version for FASTEST only
M
Mark Adler 已提交
1382
 */
M
Mark Adler 已提交
1383
local uInt longest_match(s, cur_match)
M
Mark Adler 已提交
1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420
    deflate_state *s;
    IPos cur_match;                             /* current match */
{
    register Bytef *scan = s->window + s->strstart; /* current string */
    register Bytef *match;                       /* matched string */
    register int len;                           /* length of current match */
    register Bytef *strend = s->window + s->strstart + MAX_MATCH;

    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
     * It is easy to get rid of this optimization if necessary.
     */
    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");

    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");

    Assert(cur_match < s->strstart, "no future");

    match = s->window + cur_match;

    /* Return failure if the match length is less than 2:
     */
    if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;

    /* The check at best_len-1 can be removed because it will be made
     * again later. (This heuristic is not always a win.)
     * It is not necessary to compare scan[2] and match[2] since they
     * are always equal when the other bytes match, given that
     * the hash keys are equal and that HASH_BITS >= 8.
     */
    scan += 2, match += 2;
    Assert(*scan == *match, "match[2]?");

    /* We check for insufficient lookahead only every 8th comparison;
     * the 256th check will be made at strstart+258.
     */
    do {
    } while (*++scan == *++match && *++scan == *++match &&
M
Mark Adler 已提交
1421 1422 1423 1424
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             scan < strend);
M
Mark Adler 已提交
1425 1426 1427 1428 1429 1430 1431 1432

    Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");

    len = MAX_MATCH - (int)(strend - scan);

    if (len < MIN_MATCH) return MIN_MATCH - 1;

    s->match_start = cur_match;
M
Mark Adler 已提交
1433
    return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
M
Mark Adler 已提交
1434
}
M
Mark Adler 已提交
1435

M
Mark Adler 已提交
1436 1437
#endif /* FASTEST */

1438
#ifdef ZLIB_DEBUG
1439 1440 1441 1442

#define EQUAL 0
/* result of memcmp for equal strings */

M
Mark Adler 已提交
1443 1444 1445 1446 1447 1448 1449 1450 1451
/* ===========================================================================
 * Check that the match at match_start is indeed a match.
 */
local void check_match(s, start, match, length)
    deflate_state *s;
    IPos start, match;
    int length;
{
    /* check that the match is indeed a match */
M
Mark Adler 已提交
1452 1453
    if (zmemcmp(s->window + match,
                s->window + start, length) != EQUAL) {
M
Mark Adler 已提交
1454
        fprintf(stderr, " start %u, match %u, length %d\n",
M
Mark Adler 已提交
1455
                start, match, length);
M
Mark Adler 已提交
1456
        do {
M
Mark Adler 已提交
1457 1458
            fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
        } while (--length != 0);
M
Mark Adler 已提交
1459 1460
        z_error("invalid match");
    }
M
Mark Adler 已提交
1461
    if (z_verbose > 1) {
M
Mark Adler 已提交
1462 1463
        fprintf(stderr,"\\[%d,%d]", start-match, length);
        do { putc(s->window[start++], stderr); } while (--length != 0);
M
Mark Adler 已提交
1464 1465 1466 1467
    }
}
#else
#  define check_match(s, start, match, length)
1468
#endif /* ZLIB_DEBUG */
M
Mark Adler 已提交
1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482

/* ===========================================================================
 * Fill the window when the lookahead becomes insufficient.
 * Updates strstart and lookahead.
 *
 * IN assertion: lookahead < MIN_LOOKAHEAD
 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
 *    At least one byte has been read, or avail_in == 0; reads are
 *    performed for at least two bytes (required for the zip translate_eol
 *    option -- not supported here).
 */
local void fill_window(s)
    deflate_state *s;
{
1483
    unsigned n;
M
Mark Adler 已提交
1484
    unsigned more;    /* Amount of free space at the end of the window. */
M
Mark Adler 已提交
1485
    uInt wsize = s->w_size;
M
Mark Adler 已提交
1486

1487 1488
    Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");

M
Mark Adler 已提交
1489
    do {
M
Mark Adler 已提交
1490
        more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
M
Mark Adler 已提交
1491

M
Mark Adler 已提交
1492
        /* Deal with !@#$% 64K limit: */
M
Mark Adler 已提交
1493 1494 1495
        if (sizeof(int) <= 2) {
            if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
                more = wsize;
M
Mark Adler 已提交
1496

M
Mark Adler 已提交
1497 1498
            } else if (more == (unsigned)(-1)) {
                /* Very unlikely, but possible on 16 bit machine if
M
Mark Adler 已提交
1499
                 * strstart == 0 && lookahead == 1 (input done a byte at time)
M
Mark Adler 已提交
1500 1501 1502 1503
                 */
                more--;
            }
        }
M
Mark Adler 已提交
1504 1505 1506 1507

        /* If the window is almost full and there is insufficient lookahead,
         * move the upper half to the lower one to make room in the upper half.
         */
M
Mark Adler 已提交
1508
        if (s->strstart >= wsize+MAX_DIST(s)) {
M
Mark Adler 已提交
1509

1510
            zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more);
M
Mark Adler 已提交
1511 1512 1513
            s->match_start -= wsize;
            s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
            s->block_start -= (long) wsize;
1514
            slide_hash(s);
M
Mark Adler 已提交
1515
            more += wsize;
M
Mark Adler 已提交
1516
        }
1517
        if (s->strm->avail_in == 0) break;
M
Mark Adler 已提交
1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531

        /* If there was no sliding:
         *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
         *    more == window_size - lookahead - strstart
         * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
         * => more >= window_size - 2*WSIZE + 2
         * In the BIG_MEM or MMAP case (not yet supported),
         *   window_size == input_size + MIN_LOOKAHEAD  &&
         *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
         * Otherwise, window_size == 2*WSIZE so more >= 2.
         * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
         */
        Assert(more >= 2, "more < 2");

M
Mark Adler 已提交
1532
        n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
M
Mark Adler 已提交
1533
        s->lookahead += n;
M
Mark Adler 已提交
1534

M
Mark Adler 已提交
1535
        /* Initialize the hash value now that we have some input: */
1536 1537 1538 1539
        if (s->lookahead + s->insert >= MIN_MATCH) {
            uInt str = s->strstart - s->insert;
            s->ins_h = s->window[str];
            UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
M
Mark Adler 已提交
1540 1541 1542
#if MIN_MATCH != 3
            Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553
            while (s->insert) {
                UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
#ifndef FASTEST
                s->prev[str & s->w_mask] = s->head[s->ins_h];
#endif
                s->head[s->ins_h] = (Pos)str;
                str++;
                s->insert--;
                if (s->lookahead + s->insert < MIN_MATCH)
                    break;
            }
M
Mark Adler 已提交
1554 1555 1556 1557 1558
        }
        /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
         * but this is not important since only literal bytes will be emitted.
         */

M
Mark Adler 已提交
1559
    } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
M
Mark Adler 已提交
1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593

    /* If the WIN_INIT bytes after the end of the current data have never been
     * written, then zero those bytes in order to avoid memory check reports of
     * the use of uninitialized (or uninitialised as Julian writes) bytes by
     * the longest match routines.  Update the high water mark for the next
     * time through here.  WIN_INIT is set to MAX_MATCH since the longest match
     * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
     */
    if (s->high_water < s->window_size) {
        ulg curr = s->strstart + (ulg)(s->lookahead);
        ulg init;

        if (s->high_water < curr) {
            /* Previous high water mark below current data -- zero WIN_INIT
             * bytes or up to end of window, whichever is less.
             */
            init = s->window_size - curr;
            if (init > WIN_INIT)
                init = WIN_INIT;
            zmemzero(s->window + curr, (unsigned)init);
            s->high_water = curr + init;
        }
        else if (s->high_water < (ulg)curr + WIN_INIT) {
            /* High water mark at or above current data, but below current data
             * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
             * to end of window, whichever is less.
             */
            init = (ulg)curr + WIN_INIT - s->high_water;
            if (init > s->window_size - s->high_water)
                init = s->window_size - s->high_water;
            zmemzero(s->window + s->high_water, (unsigned)init);
            s->high_water += init;
        }
    }
1594 1595 1596

    Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
           "not enough room for search");
M
Mark Adler 已提交
1597 1598 1599 1600 1601 1602
}

/* ===========================================================================
 * Flush the current block, with given end-of-file flag.
 * IN assertion: strstart is set to the end of the current match.
 */
M
Mark Adler 已提交
1603
#define FLUSH_BLOCK_ONLY(s, last) { \
M
Mark Adler 已提交
1604 1605 1606
   _tr_flush_block(s, (s->block_start >= 0L ? \
                   (charf *)&s->window[(unsigned)s->block_start] : \
                   (charf *)Z_NULL), \
M
Mark Adler 已提交
1607
                (ulg)((long)s->strstart - s->block_start), \
M
Mark Adler 已提交
1608
                (last)); \
M
Mark Adler 已提交
1609 1610
   s->block_start = s->strstart; \
   flush_pending(s->strm); \
M
Mark Adler 已提交
1611
   Tracev((stderr,"[FLUSH]")); \
M
Mark Adler 已提交
1612 1613 1614
}

/* Same but force premature exit if necessary. */
M
Mark Adler 已提交
1615 1616 1617
#define FLUSH_BLOCK(s, last) { \
   FLUSH_BLOCK_ONLY(s, last); \
   if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
M
Mark Adler 已提交
1618 1619
}

1620 1621 1622 1623 1624 1625
/* Maximum stored block length in deflate format (not including header). */
#define MAX_STORED 65535

/* Minimum of a and b. */
#define MIN(a, b) ((a) > (b) ? (b) : (a))

M
Mark Adler 已提交
1626 1627
/* ===========================================================================
 * Copy without compression as much as possible from the input stream, return
M
Mark Adler 已提交
1628
 * the current block state.
1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639
 *
 * In case deflateParams() is used to later switch to a non-zero compression
 * level, s->matches (otherwise unused when storing) keeps track of the number
 * of hash table slides to perform. If s->matches is 1, then one hash table
 * slide will be done when switching. If s->matches is 2, the maximum value
 * allowed here, then the hash table will be cleared, since two or more slides
 * is the same as a clear.
 *
 * deflate_stored() is written to minimize the number of times an input byte is
 * copied. It is most efficient with large input and output buffers, which
 * maximizes the opportunites to have a single copy from next_in to next_out.
M
Mark Adler 已提交
1640
 */
M
Mark Adler 已提交
1641
local block_state deflate_stored(s, flush)
M
Mark Adler 已提交
1642 1643 1644
    deflate_state *s;
    int flush;
{
1645 1646 1647
    /* Smallest worthy block size when not flushing or finishing. By default
     * this is 32K. This can be as small as 507 bytes for memLevel == 1. For
     * large input and output buffers, the stored block size will be larger.
M
Mark Adler 已提交
1648
     */
1649
    unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size);
M
Mark Adler 已提交
1650

1651 1652 1653 1654
    /* Copy as many min_block or larger stored blocks directly to next_out as
     * possible. If flushing, copy the remaining available input to next_out as
     * stored blocks, if there is enough space.
     */
1655
    unsigned len, left, have, last = 0;
1656
    unsigned used = s->strm->avail_in;
1657
    do {
1658 1659 1660 1661 1662 1663
        /* Set len to the maximum size block that we can copy directly with the
         * available input data and output space. Set left to how much of that
         * would be copied from what's left in the window.
         */
        len = MAX_STORED;       /* maximum deflate stored block length */
        have = (s->bi_valid + 42) >> 3;         /* number of header bytes */
1664 1665
        if (s->strm->avail_out < have)          /* need room for header */
            break;
1666
            /* maximum stored block length that will fit in avail_out: */
1667
        have = s->strm->avail_out - have;
1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680
        left = s->strstart - s->block_start;    /* bytes left in window */
        if (len > (ulg)left + s->strm->avail_in)
            len = left + s->strm->avail_in;     /* limit len to the input */
        if (len > have)
            len = have;                         /* limit len to the output */
        if (left > len)
            left = len;                         /* limit window pull to len */

        /* If the stored block would be less than min_block in length, or if
         * unable to copy all of the available input when flushing, then try
         * copying to the window and the pending buffer instead. Also don't
         * write an empty block when flushing -- deflate() does that.
         */
1681 1682
        if (len < min_block && ((len == 0 && flush != Z_FINISH) ||
                                flush == Z_NO_FLUSH ||
1683 1684 1685 1686 1687 1688 1689 1690
                                len - left != s->strm->avail_in))
            break;

        /* Make a dummy stored block in pending to get the header bytes,
         * including any pending bits. This also updates the debugging counts.
         */
        last = flush == Z_FINISH && len - left == s->strm->avail_in ? 1 : 0;
        _tr_stored_block(s, (char *)0, 0L, last);
M
Mark Adler 已提交
1691

1692 1693 1694 1695 1696
        /* Replace the lengths in the dummy stored block with len. */
        s->pending_buf[s->pending - 4] = len;
        s->pending_buf[s->pending - 3] = len >> 8;
        s->pending_buf[s->pending - 2] = ~len;
        s->pending_buf[s->pending - 1] = ~len >> 8;
M
Mark Adler 已提交
1697

1698 1699
        /* Write the stored block header bytes. */
        flush_pending(s->strm);
M
Mark Adler 已提交
1700

1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714
        /* Update debugging counts for the data about to be copied. */
#ifdef ZLIB_DEBUG
        s->compressed_len += len << 3;
        s->bits_sent += len << 3;
#endif

        /* Copy uncompressed bytes from the window to next_out. */
        if (left) {
            zmemcpy(s->strm->next_out, s->window + s->block_start, left);
            s->strm->next_out += left;
            s->strm->avail_out -= left;
            s->strm->total_out += left;
            s->block_start += left;
            len -= left;
M
Mark Adler 已提交
1715
        }
1716 1717 1718 1719 1720 1721 1722 1723 1724

        /* Copy uncompressed bytes directly from next_in to next_out, updating
         * the check value.
         */
        if (len) {
            read_buf(s->strm, s->strm->next_out, len);
            s->strm->next_out += len;
            s->strm->avail_out -= len;
            s->strm->total_out += len;
M
Mark Adler 已提交
1725
        }
1726
    } while (last == 0);
1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737

    /* Update the sliding window with the last s->w_size bytes of the copied
     * data, or append all of the copied data to the existing window if less
     * than s->w_size bytes were copied. Also update the number of bytes to
     * insert in the hash tables, in the event that deflateParams() switches to
     * a non-zero compression level.
     */
    used -= s->strm->avail_in;      /* number of input bytes directly copied */
    if (used) {
        /* If any input was used, then no unused input remains in the window,
         * therefore s->block_start == s->strstart.
M
Mark Adler 已提交
1738
         */
1739 1740 1741 1742
        if (used >= s->w_size) {    /* supplant the previous history */
            s->matches = 2;         /* clear hash */
            zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
            s->strstart = s->w_size;
M
Mark Adler 已提交
1743
        }
1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756
        else {
            if (s->window_size - s->strstart <= used) {
                /* Slide the window down. */
                s->strstart -= s->w_size;
                zmemcpy(s->window, s->window + s->w_size, s->strstart);
                if (s->matches < 2)
                    s->matches++;   /* add a pending slide_hash() */
            }
            zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
            s->strstart += used;
        }
        s->block_start = s->strstart;
        s->insert += MIN(used, s->w_size - s->insert);
M
Mark Adler 已提交
1757
    }
1758

1759 1760 1761 1762 1763 1764 1765 1766
    /* If the last block was written to next_out, then done. */
    if (last)
        return finish_done;

    /* If flushing and all input has been consumed, then done. */
    if (flush != Z_NO_FLUSH && flush != Z_FINISH &&
        s->strm->avail_in == 0 && (long)s->strstart == s->block_start)
        return block_done;
1767 1768 1769

    /* Fill the window with any remaining input. */
    have = s->window_size - s->strstart - 1;
1770
    if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) {
1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796
        /* Slide the window down. */
        s->block_start -= s->w_size;
        s->strstart -= s->w_size;
        zmemcpy(s->window, s->window + s->w_size, s->strstart);
        if (s->matches < 2)
            s->matches++;           /* add a pending slide_hash() */
        have += s->w_size;          /* more space now */
    }
    if (have > s->strm->avail_in)
        have = s->strm->avail_in;
    if (have) {
        read_buf(s->strm, s->window + s->strstart, have);
        s->strstart += have;
    }

    /* There was not enough avail_out to write a complete worthy or flushed
     * stored block to next_out. Write a stored block to pending instead, if we
     * have enough input for a worthy block, or if flushing and there is enough
     * room for the remaining input as a stored block in the pending buffer.
     */
    have = (s->bi_valid + 42) >> 3;         /* number of header bytes */
        /* maximum stored block length that will fit in pending: */
    have = MIN(s->pending_buf_size - have, MAX_STORED);
    min_block = MIN(have, s->w_size);
    left = s->strstart - s->block_start;
    if (left >= min_block ||
1797 1798
        ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH &&
         s->strm->avail_in == 0 && left <= have)) {
1799 1800 1801 1802 1803 1804
        len = MIN(left, have);
        last = flush == Z_FINISH && s->strm->avail_in == 0 &&
               len == left ? 1 : 0;
        _tr_stored_block(s, (charf *)s->window + s->block_start, len, last);
        s->block_start += len;
        flush_pending(s->strm);
1805
    }
1806 1807

    /* We've done all we can with the available input and output. */
1808
    return last ? finish_started : need_more;
M
Mark Adler 已提交
1809 1810
}

M
Mark Adler 已提交
1811
/* ===========================================================================
M
Mark Adler 已提交
1812 1813
 * Compress as much as possible from the input stream, return the current
 * block state.
M
Mark Adler 已提交
1814
 * This function does not perform lazy evaluation of matches and inserts
M
Mark Adler 已提交
1815 1816 1817
 * new strings in the dictionary only for unmatched strings or for short
 * matches. It is used only for the fast compression options.
 */
M
Mark Adler 已提交
1818
local block_state deflate_fast(s, flush)
M
Mark Adler 已提交
1819 1820 1821
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
1822
    IPos hash_head;       /* head of the hash chain */
M
Mark Adler 已提交
1823
    int bflush;           /* set if current block must be flushed */
M
Mark Adler 已提交
1824 1825 1826 1827 1828 1829 1830 1831

    for (;;) {
        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
         * for the next match, plus MIN_MATCH bytes to insert the
         * string following the next match.
         */
        if (s->lookahead < MIN_LOOKAHEAD) {
M
Mark Adler 已提交
1832
            fill_window(s);
M
Mark Adler 已提交
1833
            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
1834 1835
                return need_more;
            }
M
Mark Adler 已提交
1836 1837
            if (s->lookahead == 0) break; /* flush the current block */
        }
M
Mark Adler 已提交
1838 1839 1840 1841

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
M
Mark Adler 已提交
1842
        hash_head = NIL;
M
Mark Adler 已提交
1843 1844 1845
        if (s->lookahead >= MIN_MATCH) {
            INSERT_STRING(s, s->strstart, hash_head);
        }
M
Mark Adler 已提交
1846 1847 1848 1849 1850 1851 1852 1853 1854

        /* Find the longest match, discarding those <= prev_length.
         * At this point we have always match_length < MIN_MATCH
         */
        if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
            /* To simplify the code, we prevent matches with the string
             * of window index 0 (in particular we have to avoid a match
             * of the string with itself at the start of the input file).
             */
M
Mark Adler 已提交
1855 1856
            s->match_length = longest_match (s, hash_head);
            /* longest_match() sets match_start */
M
Mark Adler 已提交
1857 1858 1859 1860
        }
        if (s->match_length >= MIN_MATCH) {
            check_match(s, s->strstart, s->match_start, s->match_length);

M
Mark Adler 已提交
1861 1862
            _tr_tally_dist(s, s->strstart - s->match_start,
                           s->match_length - MIN_MATCH, bflush);
M
Mark Adler 已提交
1863 1864 1865 1866 1867 1868

            s->lookahead -= s->match_length;

            /* Insert new strings in the hash table only if the match length
             * is not too large. This saves time but degrades compression.
             */
M
Mark Adler 已提交
1869
#ifndef FASTEST
M
Mark Adler 已提交
1870 1871
            if (s->match_length <= s->max_insert_length &&
                s->lookahead >= MIN_MATCH) {
M
Mark Adler 已提交
1872
                s->match_length--; /* string at strstart already in table */
M
Mark Adler 已提交
1873 1874 1875 1876
                do {
                    s->strstart++;
                    INSERT_STRING(s, s->strstart, hash_head);
                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
M
Mark Adler 已提交
1877
                     * always MIN_MATCH bytes ahead.
M
Mark Adler 已提交
1878 1879
                     */
                } while (--s->match_length != 0);
M
Mark Adler 已提交
1880
                s->strstart++;
M
Mark Adler 已提交
1881 1882
            } else
#endif
M
Mark Adler 已提交
1883
            {
M
Mark Adler 已提交
1884 1885 1886 1887 1888 1889 1890
                s->strstart += s->match_length;
                s->match_length = 0;
                s->ins_h = s->window[s->strstart];
                UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
#if MIN_MATCH != 3
                Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
M
Mark Adler 已提交
1891 1892 1893
                /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
                 * matter since it will be recomputed at next deflate call.
                 */
M
Mark Adler 已提交
1894 1895 1896 1897
            }
        } else {
            /* No match, output a literal byte */
            Tracevv((stderr,"%c", s->window[s->strstart]));
M
Mark Adler 已提交
1898
            _tr_tally_lit (s, s->window[s->strstart], bflush);
M
Mark Adler 已提交
1899
            s->lookahead--;
M
Mark Adler 已提交
1900
            s->strstart++;
M
Mark Adler 已提交
1901 1902 1903
        }
        if (bflush) FLUSH_BLOCK(s, 0);
    }
1904
    s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1905 1906 1907 1908 1909 1910 1911
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (s->last_lit)
        FLUSH_BLOCK(s, 0);
    return block_done;
M
Mark Adler 已提交
1912 1913
}

M
Mark Adler 已提交
1914
#ifndef FASTEST
M
Mark Adler 已提交
1915 1916 1917 1918 1919
/* ===========================================================================
 * Same as above, but achieves better compression. We use a lazy
 * evaluation for matches: a match is finally adopted only if there is
 * no better match at the next window position.
 */
M
Mark Adler 已提交
1920
local block_state deflate_slow(s, flush)
M
Mark Adler 已提交
1921 1922 1923
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
1924
    IPos hash_head;          /* head of hash chain */
M
Mark Adler 已提交
1925 1926 1927 1928 1929 1930 1931 1932 1933 1934
    int bflush;              /* set if current block must be flushed */

    /* Process the input block. */
    for (;;) {
        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
         * for the next match, plus MIN_MATCH bytes to insert the
         * string following the next match.
         */
        if (s->lookahead < MIN_LOOKAHEAD) {
M
Mark Adler 已提交
1935
            fill_window(s);
M
Mark Adler 已提交
1936
            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
1937 1938
                return need_more;
            }
M
Mark Adler 已提交
1939 1940
            if (s->lookahead == 0) break; /* flush the current block */
        }
M
Mark Adler 已提交
1941 1942 1943 1944

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
M
Mark Adler 已提交
1945
        hash_head = NIL;
M
Mark Adler 已提交
1946 1947 1948
        if (s->lookahead >= MIN_MATCH) {
            INSERT_STRING(s, s->strstart, hash_head);
        }
M
Mark Adler 已提交
1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960

        /* Find the longest match, discarding those <= prev_length.
         */
        s->prev_length = s->match_length, s->prev_match = s->match_start;
        s->match_length = MIN_MATCH-1;

        if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
            s->strstart - hash_head <= MAX_DIST(s)) {
            /* To simplify the code, we prevent matches with the string
             * of window index 0 (in particular we have to avoid a match
             * of the string with itself at the start of the input file).
             */
M
Mark Adler 已提交
1961 1962
            s->match_length = longest_match (s, hash_head);
            /* longest_match() sets match_start */
M
Mark Adler 已提交
1963

M
Mark Adler 已提交
1964
            if (s->match_length <= 5 && (s->strategy == Z_FILTERED
M
Mark Adler 已提交
1965
#if TOO_FAR <= 32767
M
Mark Adler 已提交
1966 1967 1968 1969
                || (s->match_length == MIN_MATCH &&
                    s->strstart - s->match_start > TOO_FAR)
#endif
                )) {
M
Mark Adler 已提交
1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980

                /* If prev_match is also MIN_MATCH, match_start is garbage
                 * but we will ignore the current match anyway.
                 */
                s->match_length = MIN_MATCH-1;
            }
        }
        /* If there was a match at the previous step and the current
         * match is not better, output the previous match:
         */
        if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
M
Mark Adler 已提交
1981 1982
            uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
            /* Do not insert strings in hash table beyond this. */
M
Mark Adler 已提交
1983 1984 1985

            check_match(s, s->strstart-1, s->prev_match, s->prev_length);

M
Mark Adler 已提交
1986
            _tr_tally_dist(s, s->strstart -1 - s->prev_match,
M
Mark Adler 已提交
1987
                           s->prev_length - MIN_MATCH, bflush);
M
Mark Adler 已提交
1988 1989

            /* Insert in hash table all strings up to the end of the match.
M
Mark Adler 已提交
1990 1991 1992
             * strstart-1 and strstart are already inserted. If there is not
             * enough lookahead, the last two strings are not inserted in
             * the hash table.
M
Mark Adler 已提交
1993 1994 1995 1996
             */
            s->lookahead -= s->prev_length-1;
            s->prev_length -= 2;
            do {
M
Mark Adler 已提交
1997 1998 1999
                if (++s->strstart <= max_insert) {
                    INSERT_STRING(s, s->strstart, hash_head);
                }
M
Mark Adler 已提交
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012
            } while (--s->prev_length != 0);
            s->match_available = 0;
            s->match_length = MIN_MATCH-1;
            s->strstart++;

            if (bflush) FLUSH_BLOCK(s, 0);

        } else if (s->match_available) {
            /* If there was no match at the previous position, output a
             * single literal. If there was a match but the current match
             * is longer, truncate the previous match to a single literal.
             */
            Tracevv((stderr,"%c", s->window[s->strstart-1]));
M
Mark Adler 已提交
2013 2014
            _tr_tally_lit(s, s->window[s->strstart-1], bflush);
            if (bflush) {
M
Mark Adler 已提交
2015
                FLUSH_BLOCK_ONLY(s, 0);
M
Mark Adler 已提交
2016 2017 2018
            }
            s->strstart++;
            s->lookahead--;
M
Mark Adler 已提交
2019
            if (s->strm->avail_out == 0) return need_more;
M
Mark Adler 已提交
2020 2021 2022 2023 2024 2025 2026 2027 2028
        } else {
            /* There is no previous match to compare with, wait for
             * the next step to decide.
             */
            s->match_available = 1;
            s->strstart++;
            s->lookahead--;
        }
    }
M
Mark Adler 已提交
2029
    Assert (flush != Z_NO_FLUSH, "no flush?");
M
Mark Adler 已提交
2030
    if (s->match_available) {
M
Mark Adler 已提交
2031
        Tracevv((stderr,"%c", s->window[s->strstart-1]));
M
Mark Adler 已提交
2032
        _tr_tally_lit(s, s->window[s->strstart-1], bflush);
M
Mark Adler 已提交
2033
        s->match_available = 0;
M
Mark Adler 已提交
2034
    }
2035
    s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
2036 2037 2038 2039 2040 2041 2042
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (s->last_lit)
        FLUSH_BLOCK(s, 0);
    return block_done;
M
Mark Adler 已提交
2043
}
M
Mark Adler 已提交
2044
#endif /* FASTEST */
M
Mark Adler 已提交
2045 2046 2047 2048 2049 2050 2051 2052 2053 2054

/* ===========================================================================
 * For Z_RLE, simply look for runs of bytes, generate matches only of distance
 * one.  Do not maintain a hash table.  (It will be regenerated if this run of
 * deflate switches away from Z_RLE.)
 */
local block_state deflate_rle(s, flush)
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
2055 2056 2057
    int bflush;             /* set if current block must be flushed */
    uInt prev;              /* byte at distance one to match */
    Bytef *scan, *strend;   /* scan goes up to strend for length of run */
M
Mark Adler 已提交
2058 2059 2060 2061

    for (;;) {
        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
2062
         * for the longest run, plus one for the unrolled loop.
M
Mark Adler 已提交
2063
         */
2064
        if (s->lookahead <= MAX_MATCH) {
M
Mark Adler 已提交
2065
            fill_window(s);
2066
            if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
2067 2068 2069 2070 2071 2072
                return need_more;
            }
            if (s->lookahead == 0) break; /* flush the current block */
        }

        /* See how many times the previous byte repeats */
M
Mark Adler 已提交
2073 2074
        s->match_length = 0;
        if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
M
Mark Adler 已提交
2075
            scan = s->window + s->strstart - 1;
M
Mark Adler 已提交
2076 2077 2078 2079 2080 2081 2082 2083 2084
            prev = *scan;
            if (prev == *++scan && prev == *++scan && prev == *++scan) {
                strend = s->window + s->strstart + MAX_MATCH;
                do {
                } while (prev == *++scan && prev == *++scan &&
                         prev == *++scan && prev == *++scan &&
                         prev == *++scan && prev == *++scan &&
                         prev == *++scan && prev == *++scan &&
                         scan < strend);
M
Mark Adler 已提交
2085
                s->match_length = MAX_MATCH - (uInt)(strend - scan);
M
Mark Adler 已提交
2086 2087 2088
                if (s->match_length > s->lookahead)
                    s->match_length = s->lookahead;
            }
2089
            Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
M
Mark Adler 已提交
2090 2091 2092
        }

        /* Emit match if have run of MIN_MATCH or longer, else emit literal */
M
Mark Adler 已提交
2093 2094 2095 2096 2097 2098 2099 2100
        if (s->match_length >= MIN_MATCH) {
            check_match(s, s->strstart, s->strstart - 1, s->match_length);

            _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);

            s->lookahead -= s->match_length;
            s->strstart += s->match_length;
            s->match_length = 0;
M
Mark Adler 已提交
2101 2102 2103 2104 2105 2106 2107 2108 2109
        } else {
            /* No match, output a literal byte */
            Tracevv((stderr,"%c", s->window[s->strstart]));
            _tr_tally_lit (s, s->window[s->strstart], bflush);
            s->lookahead--;
            s->strstart++;
        }
        if (bflush) FLUSH_BLOCK(s, 0);
    }
2110
    s->insert = 0;
2111 2112 2113 2114 2115 2116 2117
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (s->last_lit)
        FLUSH_BLOCK(s, 0);
    return block_done;
M
Mark Adler 已提交
2118
}
M
Mark Adler 已提交
2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148

/* ===========================================================================
 * For Z_HUFFMAN_ONLY, do not look for matches.  Do not maintain a hash table.
 * (It will be regenerated if this run of deflate switches away from Huffman.)
 */
local block_state deflate_huff(s, flush)
    deflate_state *s;
    int flush;
{
    int bflush;             /* set if current block must be flushed */

    for (;;) {
        /* Make sure that we have a literal to write. */
        if (s->lookahead == 0) {
            fill_window(s);
            if (s->lookahead == 0) {
                if (flush == Z_NO_FLUSH)
                    return need_more;
                break;      /* flush the current block */
            }
        }

        /* Output a literal byte */
        s->match_length = 0;
        Tracevv((stderr,"%c", s->window[s->strstart]));
        _tr_tally_lit (s, s->window[s->strstart], bflush);
        s->lookahead--;
        s->strstart++;
        if (bflush) FLUSH_BLOCK(s, 0);
    }
2149
    s->insert = 0;
2150 2151 2152 2153 2154 2155 2156
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if (s->last_lit)
        FLUSH_BLOCK(s, 0);
    return block_done;
M
Mark Adler 已提交
2157
}