deflate.c 70.3 KB
Newer Older
M
Mark Adler 已提交
1
/* deflate.c -- compress data using the deflation algorithm
M
Mark Adler 已提交
2
 * Copyright (C) 1995-2013 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[] =
M
Mark Adler 已提交
55
   " deflate 1.2.8.1 Copyright 1995-2013 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));
M
Mark Adler 已提交
77
local void fill_window    OF((deflate_state *s));
M
Mark Adler 已提交
78 79
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 已提交
80
#ifndef FASTEST
M
Mark Adler 已提交
81
local block_state deflate_slow   OF((deflate_state *s, int flush));
M
Mark Adler 已提交
82
#endif
M
Mark Adler 已提交
83 84
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 已提交
85 86
local void lm_init        OF((deflate_state *s));
local void putShortMSB    OF((deflate_state *s, uInt b));
M
Mark Adler 已提交
87
local void flush_pending  OF((z_streamp strm));
M
Mark Adler 已提交
88
local unsigned read_buf   OF((z_streamp strm, Bytef *buf, unsigned size));
M
Mark Adler 已提交
89 90
#ifdef ASMV
      void match_init OF((void)); /* asm code initialization */
M
Mark Adler 已提交
91 92 93
      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 已提交
94 95
#endif

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

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

M
Mark Adler 已提交
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
#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 已提交
123
   compress_func func;
M
Mark Adler 已提交
124 125
} config;

M
Mark Adler 已提交
126 127 128 129
#ifdef FASTEST
local const config configuration_table[2] = {
/*      good lazy nice chain */
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
M
Mark Adler 已提交
130
/* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */
M
Mark Adler 已提交
131
#else
M
Mark Adler 已提交
132
local const config configuration_table[10] = {
M
Mark Adler 已提交
133
/*      good lazy nice chain */
M
Mark Adler 已提交
134
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
M
Mark Adler 已提交
135
/* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
M
Mark Adler 已提交
136 137 138 139 140 141 142 143
/* 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 已提交
144
/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
M
Mark Adler 已提交
145
#endif
M
Mark Adler 已提交
146 147 148 149 150 151

/* 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.
 */

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

M
Mark Adler 已提交
155 156
/* ===========================================================================
 * Update a hash value with the given input byte
M
Mark Adler 已提交
157 158 159
 * 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 已提交
160 161 162
 */
#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)

M
Mark Adler 已提交
163

M
Mark Adler 已提交
164 165 166 167
/* ===========================================================================
 * 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 已提交
168 169
 * If this file is compiled with -DFASTEST, the compression level is forced
 * to 1, and no hash chains are maintained.
M
Mark Adler 已提交
170 171 172
 * 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 已提交
173
 */
M
Mark Adler 已提交
174 175 176 177 178 179
#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 已提交
180
#define INSERT_STRING(s, str, match_head) \
M
Mark Adler 已提交
181
   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
M
Mark Adler 已提交
182
    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
M
Mark Adler 已提交
183
    s->head[s->ins_h] = (Pos)(str))
M
Mark Adler 已提交
184
#endif
M
Mark Adler 已提交
185

M
Mark Adler 已提交
186 187 188 189 190 191
/* ===========================================================================
 * 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 已提交
192
    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
M
Mark Adler 已提交
193

M
Mark Adler 已提交
194
/* ========================================================================= */
M
Mark Adler 已提交
195
int ZEXPORT deflateInit_(strm, level, version, stream_size)
M
Mark Adler 已提交
196
    z_streamp strm;
M
Mark Adler 已提交
197
    int level;
M
Mark Adler 已提交
198 199
    const char *version;
    int stream_size;
M
Mark Adler 已提交
200
{
M
Mark Adler 已提交
201
    return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
M
Mark Adler 已提交
202
                         Z_DEFAULT_STRATEGY, version, stream_size);
M
Mark Adler 已提交
203 204 205 206
    /* To do: ignore strm->next_in if we use it as window */
}

/* ========================================================================= */
M
Mark Adler 已提交
207
int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
M
Mark Adler 已提交
208
                  version, stream_size)
M
Mark Adler 已提交
209
    z_streamp strm;
M
Mark Adler 已提交
210 211 212 213 214
    int  level;
    int  method;
    int  windowBits;
    int  memLevel;
    int  strategy;
M
Mark Adler 已提交
215 216
    const char *version;
    int stream_size;
M
Mark Adler 已提交
217 218
{
    deflate_state *s;
M
Mark Adler 已提交
219
    int wrap = 1;
M
Mark Adler 已提交
220
    static const char my_version[] = ZLIB_VERSION;
M
Mark Adler 已提交
221

M
Mark Adler 已提交
222 223 224 225 226
    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 已提交
227
    if (version == Z_NULL || version[0] != my_version[0] ||
M
Mark Adler 已提交
228
        stream_size != sizeof(z_stream)) {
M
Mark Adler 已提交
229
        return Z_VERSION_ERROR;
M
Mark Adler 已提交
230
    }
M
Mark Adler 已提交
231 232 233
    if (strm == Z_NULL) return Z_STREAM_ERROR;

    strm->msg = Z_NULL;
M
Mark Adler 已提交
234
    if (strm->zalloc == (alloc_func)0) {
235 236 237
#ifdef Z_SOLO
        return Z_STREAM_ERROR;
#else
M
Mark Adler 已提交
238 239
        strm->zalloc = zcalloc;
        strm->opaque = (voidpf)0;
240
#endif
M
Mark Adler 已提交
241
    }
242 243 244 245 246 247
    if (strm->zfree == (free_func)0)
#ifdef Z_SOLO
        return Z_STREAM_ERROR;
#else
        strm->zfree = zcfree;
#endif
M
Mark Adler 已提交
248

M
Mark Adler 已提交
249
#ifdef FASTEST
M
Mark Adler 已提交
250 251 252
    if (level != 0) level = 1;
#else
    if (level == Z_DEFAULT_COMPRESSION) level = 6;
M
Mark Adler 已提交
253
#endif
M
Mark Adler 已提交
254

M
Mark Adler 已提交
255 256
    if (windowBits < 0) { /* suppress zlib wrapper */
        wrap = 0;
M
Mark Adler 已提交
257
        windowBits = -windowBits;
M
Mark Adler 已提交
258
    }
M
Mark Adler 已提交
259 260
#ifdef GZIP
    else if (windowBits > 15) {
M
Mark Adler 已提交
261
        wrap = 2;       /* write gzip wrapper instead */
M
Mark Adler 已提交
262 263 264
        windowBits -= 16;
    }
#endif
M
Mark Adler 已提交
265
    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
M
Mark Adler 已提交
266
        windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
267
        strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) {
M
Mark Adler 已提交
268
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
269
    }
M
Mark Adler 已提交
270
    if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */
M
Mark Adler 已提交
271 272
    s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
    if (s == Z_NULL) return Z_MEM_ERROR;
M
Mark Adler 已提交
273
    strm->state = (struct internal_state FAR *)s;
M
Mark Adler 已提交
274
    s->strm = strm;
275
    s->status = INIT_STATE;     /* to pass state test in deflateReset() */
M
Mark Adler 已提交
276

M
Mark Adler 已提交
277
    s->wrap = wrap;
M
Mark Adler 已提交
278
    s->gzhead = Z_NULL;
M
Mark Adler 已提交
279
    s->w_bits = (uInt)windowBits;
M
Mark Adler 已提交
280
    s->w_size = 1 << s->w_bits;
M
Mark Adler 已提交
281
    s->w_mask = s->w_size - 1;
M
Mark Adler 已提交
282

M
Mark Adler 已提交
283
    s->hash_bits = (uInt)memLevel + 7;
M
Mark Adler 已提交
284
    s->hash_size = 1 << s->hash_bits;
M
Mark Adler 已提交
285
    s->hash_mask = s->hash_size - 1;
M
Mark Adler 已提交
286 287
    s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);

M
Mark Adler 已提交
288 289 290
    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 已提交
291

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

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

M
Mark Adler 已提交
296 297
    overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
    s->pending_buf = (uchf *) overlay;
M
Mark Adler 已提交
298
    s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
M
Mark Adler 已提交
299 300

    if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
M
Mark Adler 已提交
301
        s->pending_buf == Z_NULL) {
M
Mark Adler 已提交
302
        s->status = FINISH_STATE;
303
        strm->msg = ERR_MSG(Z_MEM_ERROR);
M
Mark Adler 已提交
304 305
        deflateEnd (strm);
        return Z_MEM_ERROR;
M
Mark Adler 已提交
306
    }
M
Mark Adler 已提交
307 308
    s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
    s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
M
Mark Adler 已提交
309 310 311

    s->level = level;
    s->strategy = strategy;
M
Mark Adler 已提交
312
    s->method = (Byte)method;
M
Mark Adler 已提交
313 314 315 316

    return deflateReset(strm);
}

317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
/* =========================================================================
 * 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 &&
                                           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 已提交
339
/* ========================================================================= */
M
Mark Adler 已提交
340
int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
M
Mark Adler 已提交
341
    z_streamp strm;
M
Mark Adler 已提交
342 343
    const Bytef *dictionary;
    uInt  dictLength;
M
Mark Adler 已提交
344
{
M
Mark Adler 已提交
345
    deflate_state *s;
346 347 348
    uInt str, n;
    int wrap;
    unsigned avail;
349
    z_const unsigned char *next;
M
Mark Adler 已提交
350

351
    if (deflateStateCheck(strm) || dictionary == Z_NULL)
M
Mark Adler 已提交
352
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
353
    s = strm->state;
354 355 356
    wrap = s->wrap;
    if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
357

358 359 360 361 362 363 364 365 366 367 368
    /* 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;
369
            s->insert = 0;
370 371 372
        }
        dictionary += dictLength - s->w_size;  /* use the tail */
        dictLength = s->w_size;
M
Mark Adler 已提交
373 374
    }

375 376 377 378
    /* insert dictionary into window and hash */
    avail = strm->avail_in;
    next = strm->next_in;
    strm->avail_in = dictLength;
379
    strm->next_in = (z_const Bytef *)dictionary;
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
    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 已提交
395
    }
396 397
    s->strstart += s->lookahead;
    s->block_start = (long)s->strstart;
398
    s->insert = s->lookahead;
399 400 401 402 403 404
    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 已提交
405 406 407
    return Z_OK;
}

M
Mark Adler 已提交
408
/* ========================================================================= */
409
int ZEXPORT deflateResetKeep (strm)
M
Mark Adler 已提交
410
    z_streamp strm;
M
Mark Adler 已提交
411 412
{
    deflate_state *s;
M
Mark Adler 已提交
413

414
    if (deflateStateCheck(strm)) {
M
Mark Adler 已提交
415 416
        return Z_STREAM_ERROR;
    }
M
Mark Adler 已提交
417 418 419 420 421 422 423 424 425

    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 已提交
426 427
    if (s->wrap < 0) {
        s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
M
Mark Adler 已提交
428
    }
M
Mark Adler 已提交
429 430 431 432 433 434
    s->status = s->wrap ? INIT_STATE : BUSY_STATE;
    strm->adler =
#ifdef GZIP
        s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
#endif
        adler32(0L, Z_NULL, 0);
M
Mark Adler 已提交
435
    s->last_flush = Z_NO_FLUSH;
M
Mark Adler 已提交
436

M
Mark Adler 已提交
437
    _tr_init(s);
M
Mark Adler 已提交
438 439 440 441

    return Z_OK;
}

442 443 444 445 446 447 448 449 450 451 452 453
/* ========================================================================= */
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 已提交
454 455 456 457 458
/* ========================================================================= */
int ZEXPORT deflateSetHeader (strm, head)
    z_streamp strm;
    gz_headerp head;
{
459 460
    if (deflateStateCheck(strm) || strm->state->wrap != 2)
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
461 462 463 464
    strm->state->gzhead = head;
    return Z_OK;
}

M
Mark Adler 已提交
465 466 467 468 469 470
/* ========================================================================= */
int ZEXPORT deflatePending (strm, pending, bits)
    unsigned *pending;
    int *bits;
    z_streamp strm;
{
471
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
472 473 474 475
    if (pending != Z_NULL)
        *pending = strm->state->pending;
    if (bits != Z_NULL)
        *bits = strm->state->bi_valid;
M
Mark Adler 已提交
476 477 478
    return Z_OK;
}

M
Mark Adler 已提交
479 480 481 482 483 484
/* ========================================================================= */
int ZEXPORT deflatePrime (strm, bits, value)
    z_streamp strm;
    int bits;
    int value;
{
485 486 487
    deflate_state *s;
    int put;

488
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
489 490 491 492 493 494 495 496 497 498 499 500 501
    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 已提交
502 503 504
    return Z_OK;
}

M
Mark Adler 已提交
505
/* ========================================================================= */
M
Mark Adler 已提交
506
int ZEXPORT deflateParams(strm, level, strategy)
M
Mark Adler 已提交
507
    z_streamp strm;
M
Mark Adler 已提交
508 509 510 511 512
    int level;
    int strategy;
{
    deflate_state *s;
    compress_func func;
M
Mark Adler 已提交
513
    int err = Z_OK;
M
Mark Adler 已提交
514

515
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
516 517
    s = strm->state;

M
Mark Adler 已提交
518 519 520 521 522
#ifdef FASTEST
    if (level != 0) level = 1;
#else
    if (level == Z_DEFAULT_COMPRESSION) level = 6;
#endif
M
Mark Adler 已提交
523
    if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
M
Mark Adler 已提交
524
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
525 526 527
    }
    func = configuration_table[s->level].func;

528
    if ((strategy != s->strategy || func != configuration_table[level].func)) {
M
Mark Adler 已提交
529
        /* Flush the last buffer: */
M
Mark Adler 已提交
530
        err = deflate(strm, Z_BLOCK);
531 532
        if (err == Z_BUF_ERROR && s->pending == 0)
            err = Z_OK;
M
Mark Adler 已提交
533 534
    }
    if (s->level != level) {
M
Mark Adler 已提交
535 536 537 538 539
        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 已提交
540 541
    }
    s->strategy = strategy;
M
Mark Adler 已提交
542
    return err;
M
Mark Adler 已提交
543 544
}

M
Mark Adler 已提交
545 546 547 548 549 550 551 552 553 554
/* ========================================================================= */
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;

555
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
556
    s = strm->state;
M
Mark Adler 已提交
557 558
    s->good_match = (uInt)good_length;
    s->max_lazy_match = (uInt)max_lazy;
M
Mark Adler 已提交
559
    s->nice_match = nice_length;
M
Mark Adler 已提交
560
    s->max_chain_length = (uInt)max_chain;
M
Mark Adler 已提交
561 562 563
    return Z_OK;
}

M
Mark Adler 已提交
564 565 566 567 568 569 570 571 572 573 574 575
/* =========================================================================
 * 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 已提交
576 577 578 579
 * 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 已提交
580 581 582 583 584 585
 */
uLong ZEXPORT deflateBound(strm, sourceLen)
    z_streamp strm;
    uLong sourceLen;
{
    deflate_state *s;
M
Mark Adler 已提交
586 587
    uLong complen, wraplen;
    Bytef *str;
M
Mark Adler 已提交
588

M
Mark Adler 已提交
589 590 591
    /* conservative upper bound for compressed data */
    complen = sourceLen +
              ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
M
Mark Adler 已提交
592

M
Mark Adler 已提交
593
    /* if can't get parameters, return conservative bound plus zlib wrapper */
594
    if (deflateStateCheck(strm))
M
Mark Adler 已提交
595
        return complen + 6;
M
Mark Adler 已提交
596

M
Mark Adler 已提交
597
    /* compute wrapper length */
M
Mark Adler 已提交
598
    s = strm->state;
M
Mark Adler 已提交
599 600 601 602 603 604 605 606 607
    switch (s->wrap) {
    case 0:                                 /* raw deflate */
        wraplen = 0;
        break;
    case 1:                                 /* zlib wrapper */
        wraplen = 6 + (s->strstart ? 4 : 0);
        break;
    case 2:                                 /* gzip wrapper */
        wraplen = 18;
M
Mark Adler 已提交
608 609
        if (s->gzhead != Z_NULL) {          /* user-supplied gzip header */
            if (s->gzhead->extra != Z_NULL)
M
Mark Adler 已提交
610 611
                wraplen += 2 + s->gzhead->extra_len;
            str = s->gzhead->name;
M
Mark Adler 已提交
612
            if (str != Z_NULL)
M
Mark Adler 已提交
613 614 615 616
                do {
                    wraplen++;
                } while (*str++);
            str = s->gzhead->comment;
M
Mark Adler 已提交
617
            if (str != Z_NULL)
M
Mark Adler 已提交
618 619 620 621 622 623 624 625 626 627 628 629
                do {
                    wraplen++;
                } while (*str++);
            if (s->gzhead->hcrc)
                wraplen += 2;
        }
        break;
    default:                                /* for compiler happiness */
        wraplen = 6;
    }

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

    /* default settings: return tight bound for that case */
M
Mark Adler 已提交
634 635
    return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
           (sourceLen >> 25) + 13 - 6 + wraplen;
M
Mark Adler 已提交
636 637
}

M
Mark Adler 已提交
638
/* =========================================================================
M
Mark Adler 已提交
639
 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
M
Mark Adler 已提交
640
 * IN assertion: the stream state is correct and there is enough room in
M
Mark Adler 已提交
641
 * pending_buf.
M
Mark Adler 已提交
642 643 644 645 646
 */
local void putShortMSB (s, b)
    deflate_state *s;
    uInt b;
{
M
Mark Adler 已提交
647 648
    put_byte(s, (Byte)(b >> 8));
    put_byte(s, (Byte)(b & 0xff));
M
Mark Adler 已提交
649
}
M
Mark Adler 已提交
650 651

/* =========================================================================
M
Mark Adler 已提交
652 653 654 655
 * Flush as much pending output as possible. All deflate() 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 已提交
656 657
 */
local void flush_pending(strm)
M
Mark Adler 已提交
658
    z_streamp strm;
M
Mark Adler 已提交
659
{
660 661
    unsigned len;
    deflate_state *s = strm->state;
M
Mark Adler 已提交
662

663 664
    _tr_flush_bits(s);
    len = s->pending;
M
Mark Adler 已提交
665 666 667
    if (len > strm->avail_out) len = strm->avail_out;
    if (len == 0) return;

668
    zmemcpy(strm->next_out, s->pending_out, len);
M
Mark Adler 已提交
669
    strm->next_out  += len;
670
    s->pending_out  += len;
M
Mark Adler 已提交
671 672
    strm->total_out += len;
    strm->avail_out  -= len;
673 674 675
    s->pending -= len;
    if (s->pending == 0) {
        s->pending_out = s->pending_buf;
M
Mark Adler 已提交
676 677 678 679
    }
}

/* ========================================================================= */
M
Mark Adler 已提交
680
int ZEXPORT deflate (strm, flush)
M
Mark Adler 已提交
681
    z_streamp strm;
M
Mark Adler 已提交
682 683
    int flush;
{
M
Mark Adler 已提交
684
    int old_flush; /* value of flush param for previous deflate call */
M
Mark Adler 已提交
685
    deflate_state *s;
M
Mark Adler 已提交
686

687
    if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) {
M
Mark Adler 已提交
688 689
        return Z_STREAM_ERROR;
    }
M
Mark Adler 已提交
690 691
    s = strm->state;

M
Mark Adler 已提交
692
    if (strm->next_out == Z_NULL ||
693
        (strm->avail_in != 0 && strm->next_in == Z_NULL) ||
M
Mark Adler 已提交
694
        (s->status == FINISH_STATE && flush != Z_FINISH)) {
M
Mark Adler 已提交
695
        ERR_RETURN(strm, Z_STREAM_ERROR);
M
Mark Adler 已提交
696 697 698
    }
    if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

M
Mark Adler 已提交
699 700 701
    s->strm = strm; /* just in case */
    old_flush = s->last_flush;
    s->last_flush = flush;
M
Mark Adler 已提交
702

M
Mark Adler 已提交
703
    /* Write the header */
M
Mark Adler 已提交
704
    if (s->status == INIT_STATE) {
M
Mark Adler 已提交
705 706
#ifdef GZIP
        if (s->wrap == 2) {
M
Mark Adler 已提交
707
            strm->adler = crc32(0L, Z_NULL, 0);
M
Mark Adler 已提交
708 709 710
            put_byte(s, 31);
            put_byte(s, 139);
            put_byte(s, 8);
M
Mark Adler 已提交
711
            if (s->gzhead == Z_NULL) {
M
Mark Adler 已提交
712 713 714 715 716 717 718 719
                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));
M
Mark Adler 已提交
720
                put_byte(s, OS_CODE);
M
Mark Adler 已提交
721 722 723 724 725 726 727 728 729
                s->status = BUSY_STATE;
            }
            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)
                        );
M
Mark Adler 已提交
730 731 732 733
                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));
M
Mark Adler 已提交
734 735 736 737
                put_byte(s, s->level == 9 ? 2 :
                            (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
                             4 : 0));
                put_byte(s, s->gzhead->os & 0xff);
M
Mark Adler 已提交
738
                if (s->gzhead->extra != Z_NULL) {
M
Mark Adler 已提交
739 740 741 742 743 744 745 746 747
                    put_byte(s, s->gzhead->extra_len & 0xff);
                    put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
                }
                if (s->gzhead->hcrc)
                    strm->adler = crc32(strm->adler, s->pending_buf,
                                        s->pending);
                s->gzindex = 0;
                s->status = EXTRA_STATE;
            }
M
Mark Adler 已提交
748
        }
M
Mark Adler 已提交
749
        else
M
Mark Adler 已提交
750 751 752 753
#endif
        {
            uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
            uInt level_flags;
M
Mark Adler 已提交
754

M
Mark Adler 已提交
755 756 757 758 759 760 761 762 763 764 765
            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;
            else
                level_flags = 3;
            header |= (level_flags << 6);
            if (s->strstart != 0) header |= PRESET_DICT;
            header += 31 - (header % 31);
M
Mark Adler 已提交
766

M
Mark Adler 已提交
767 768
            s->status = BUSY_STATE;
            putShortMSB(s, header);
M
Mark Adler 已提交
769

M
Mark Adler 已提交
770 771 772 773 774 775
            /* 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);
M
Mark Adler 已提交
776
        }
M
Mark Adler 已提交
777
    }
M
Mark Adler 已提交
778 779
#ifdef GZIP
    if (s->status == EXTRA_STATE) {
M
Mark Adler 已提交
780
        if (s->gzhead->extra != Z_NULL) {
M
Mark Adler 已提交
781
            uInt beg = s->pending;  /* start of bytes to update crc */
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

            while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
                if (s->pending == s->pending_buf_size) {
                    if (s->gzhead->hcrc && s->pending > beg)
                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                            s->pending - beg);
                    flush_pending(strm);
                    beg = s->pending;
                    if (s->pending == s->pending_buf_size)
                        break;
                }
                put_byte(s, s->gzhead->extra[s->gzindex]);
                s->gzindex++;
            }
            if (s->gzhead->hcrc && s->pending > beg)
                strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                    s->pending - beg);
            if (s->gzindex == s->gzhead->extra_len) {
                s->gzindex = 0;
                s->status = NAME_STATE;
            }
        }
        else
            s->status = NAME_STATE;
    }
    if (s->status == NAME_STATE) {
M
Mark Adler 已提交
808
        if (s->gzhead->name != Z_NULL) {
M
Mark Adler 已提交
809
            uInt beg = s->pending;  /* start of bytes to update crc */
M
Mark Adler 已提交
810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838
            int val;

            do {
                if (s->pending == s->pending_buf_size) {
                    if (s->gzhead->hcrc && s->pending > beg)
                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                            s->pending - beg);
                    flush_pending(strm);
                    beg = s->pending;
                    if (s->pending == s->pending_buf_size) {
                        val = 1;
                        break;
                    }
                }
                val = s->gzhead->name[s->gzindex++];
                put_byte(s, val);
            } while (val != 0);
            if (s->gzhead->hcrc && s->pending > beg)
                strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                    s->pending - beg);
            if (val == 0) {
                s->gzindex = 0;
                s->status = COMMENT_STATE;
            }
        }
        else
            s->status = COMMENT_STATE;
    }
    if (s->status == COMMENT_STATE) {
M
Mark Adler 已提交
839
        if (s->gzhead->comment != Z_NULL) {
M
Mark Adler 已提交
840
            uInt beg = s->pending;  /* start of bytes to update crc */
M
Mark Adler 已提交
841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871
            int val;

            do {
                if (s->pending == s->pending_buf_size) {
                    if (s->gzhead->hcrc && s->pending > beg)
                        strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                            s->pending - beg);
                    flush_pending(strm);
                    beg = s->pending;
                    if (s->pending == s->pending_buf_size) {
                        val = 1;
                        break;
                    }
                }
                val = s->gzhead->comment[s->gzindex++];
                put_byte(s, val);
            } while (val != 0);
            if (s->gzhead->hcrc && s->pending > beg)
                strm->adler = crc32(strm->adler, s->pending_buf + beg,
                                    s->pending - beg);
            if (val == 0)
                s->status = HCRC_STATE;
        }
        else
            s->status = HCRC_STATE;
    }
    if (s->status == HCRC_STATE) {
        if (s->gzhead->hcrc) {
            if (s->pending + 2 > s->pending_buf_size)
                flush_pending(strm);
            if (s->pending + 2 <= s->pending_buf_size) {
M
Mark Adler 已提交
872 873
                put_byte(s, (Byte)(strm->adler & 0xff));
                put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
M
Mark Adler 已提交
874 875 876 877 878 879 880 881
                strm->adler = crc32(0L, Z_NULL, 0);
                s->status = BUSY_STATE;
            }
        }
        else
            s->status = BUSY_STATE;
    }
#endif
M
Mark Adler 已提交
882 883

    /* Flush as much pending output as possible */
M
Mark Adler 已提交
884
    if (s->pending != 0) {
M
Mark Adler 已提交
885
        flush_pending(strm);
M
Mark Adler 已提交
886
        if (strm->avail_out == 0) {
M
Mark Adler 已提交
887 888 889 890 891
            /* 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:
M
Mark Adler 已提交
892
             */
M
Mark Adler 已提交
893 894 895
            s->last_flush = -1;
            return Z_OK;
        }
M
Mark Adler 已提交
896 897 898

    /* Make sure there is something to do and avoid duplicate consecutive
     * flushes. For repeated and useless calls with Z_FINISH, we keep
M
Mark Adler 已提交
899
     * returning Z_STREAM_END instead of Z_BUF_ERROR.
M
Mark Adler 已提交
900
     */
901
    } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
M
Mark Adler 已提交
902
               flush != Z_FINISH) {
M
Mark Adler 已提交
903
        ERR_RETURN(strm, Z_BUF_ERROR);
M
Mark Adler 已提交
904 905 906
    }

    /* User must not provide more input after the first FINISH: */
M
Mark Adler 已提交
907
    if (s->status == FINISH_STATE && strm->avail_in != 0) {
M
Mark Adler 已提交
908
        ERR_RETURN(strm, Z_BUF_ERROR);
M
Mark Adler 已提交
909 910 911 912
    }

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

917 918 919 920
        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 已提交
921 922

        if (bstate == finish_started || bstate == finish_done) {
M
Mark Adler 已提交
923
            s->status = FINISH_STATE;
M
Mark Adler 已提交
924
        }
M
Mark Adler 已提交
925
        if (bstate == need_more || bstate == finish_started) {
M
Mark Adler 已提交
926 927 928 929 930 931 932 933 934 935 936 937
            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 已提交
938
        if (bstate == block_done) {
M
Mark Adler 已提交
939
            if (flush == Z_PARTIAL_FLUSH) {
M
Mark Adler 已提交
940
                _tr_align(s);
M
Mark Adler 已提交
941
            } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
M
Mark Adler 已提交
942
                _tr_stored_block(s, (char*)0, 0L, 0);
M
Mark Adler 已提交
943 944 945 946
                /* 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 已提交
947
                    CLEAR_HASH(s);             /* forget history */
M
Mark Adler 已提交
948 949 950
                    if (s->lookahead == 0) {
                        s->strstart = 0;
                        s->block_start = 0L;
951
                        s->insert = 0;
M
Mark Adler 已提交
952
                    }
M
Mark Adler 已提交
953 954
                }
            }
M
Mark Adler 已提交
955
            flush_pending(strm);
M
Mark Adler 已提交
956 957 958 959
            if (strm->avail_out == 0) {
              s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
              return Z_OK;
            }
M
Mark Adler 已提交
960
        }
M
Mark Adler 已提交
961 962 963
    }
    Assert(strm->avail_out > 0, "bug2");

M
Mark Adler 已提交
964
    if (flush != Z_FINISH) return Z_OK;
M
Mark Adler 已提交
965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984
    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 已提交
985 986 987 988
    flush_pending(strm);
    /* If avail_out is zero, the application will call deflate again
     * to flush the rest.
     */
M
Mark Adler 已提交
989
    if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
M
Mark Adler 已提交
990
    return s->pending != 0 ? Z_OK : Z_STREAM_END;
M
Mark Adler 已提交
991 992 993
}

/* ========================================================================= */
M
Mark Adler 已提交
994
int ZEXPORT deflateEnd (strm)
M
Mark Adler 已提交
995
    z_streamp strm;
M
Mark Adler 已提交
996
{
M
Mark Adler 已提交
997 998
    int status;

999
    if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
M
Mark Adler 已提交
1000

M
Mark Adler 已提交
1001 1002
    status = strm->state->status;

M
Mark Adler 已提交
1003
    /* Deallocate in reverse order of allocations: */
M
Mark Adler 已提交
1004
    TRY_FREE(strm, strm->state->pending_buf);
M
Mark Adler 已提交
1005 1006 1007
    TRY_FREE(strm, strm->state->head);
    TRY_FREE(strm, strm->state->prev);
    TRY_FREE(strm, strm->state->window);
M
Mark Adler 已提交
1008 1009 1010 1011

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

M
Mark Adler 已提交
1012
    return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
M
Mark Adler 已提交
1013 1014
}

M
Mark Adler 已提交
1015 1016 1017 1018 1019
/* =========================================================================
 * 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 已提交
1020
int ZEXPORT deflateCopy (dest, source)
M
Mark Adler 已提交
1021 1022
    z_streamp dest;
    z_streamp source;
M
Mark Adler 已提交
1023
{
M
Mark Adler 已提交
1024 1025 1026 1027 1028 1029 1030 1031
#ifdef MAXSEG_64K
    return Z_STREAM_ERROR;
#else
    deflate_state *ds;
    deflate_state *ss;
    ushf *overlay;


1032
    if (deflateStateCheck(source) || dest == Z_NULL) {
M
Mark Adler 已提交
1033
        return Z_STREAM_ERROR;
M
Mark Adler 已提交
1034
    }
M
Mark Adler 已提交
1035 1036 1037

    ss = source->state;

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

M
Mark Adler 已提交
1040 1041 1042
    ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
    if (ds == Z_NULL) return Z_MEM_ERROR;
    dest->state = (struct internal_state FAR *) ds;
1043
    zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
M
Mark Adler 已提交
1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058
    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));
1059 1060
    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 已提交
1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
    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 已提交
1071
    return Z_OK;
M
Mark Adler 已提交
1072
#endif /* MAXSEG_64K */
M
Mark Adler 已提交
1073 1074 1075 1076
}

/* ===========================================================================
 * Read a new buffer from the current input stream, update the adler32
M
Mark Adler 已提交
1077 1078 1079 1080
 * 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 已提交
1081
 */
M
Mark Adler 已提交
1082
local unsigned read_buf(strm, buf, size)
M
Mark Adler 已提交
1083
    z_streamp strm;
M
Mark Adler 已提交
1084
    Bytef *buf;
M
Mark Adler 已提交
1085 1086 1087 1088 1089 1090 1091 1092 1093
    unsigned size;
{
    unsigned len = strm->avail_in;

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

    strm->avail_in  -= len;

M
Mark Adler 已提交
1094
    zmemcpy(buf, strm->next_in, len);
M
Mark Adler 已提交
1095
    if (strm->state->wrap == 1) {
M
Mark Adler 已提交
1096
        strm->adler = adler32(strm->adler, buf, len);
M
Mark Adler 已提交
1097
    }
M
Mark Adler 已提交
1098 1099
#ifdef GZIP
    else if (strm->state->wrap == 2) {
M
Mark Adler 已提交
1100
        strm->adler = crc32(strm->adler, buf, len);
M
Mark Adler 已提交
1101 1102
    }
#endif
M
Mark Adler 已提交
1103 1104 1105
    strm->next_in  += len;
    strm->total_in += len;

M
Mark Adler 已提交
1106
    return len;
M
Mark Adler 已提交
1107 1108 1109 1110 1111 1112 1113 1114 1115 1116
}

/* ===========================================================================
 * 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 已提交
1117
    CLEAR_HASH(s);
M
Mark Adler 已提交
1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128

    /* 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;
1129
    s->insert = 0;
M
Mark Adler 已提交
1130
    s->match_length = s->prev_length = MIN_MATCH-1;
M
Mark Adler 已提交
1131
    s->match_available = 0;
M
Mark Adler 已提交
1132
    s->ins_h = 0;
M
Mark Adler 已提交
1133
#ifndef FASTEST
M
Mark Adler 已提交
1134 1135 1136
#ifdef ASMV
    match_init(); /* initialize the asm code */
#endif
M
Mark Adler 已提交
1137
#endif
M
Mark Adler 已提交
1138 1139
}

M
Mark Adler 已提交
1140
#ifndef FASTEST
M
Mark Adler 已提交
1141 1142 1143 1144 1145 1146 1147
/* ===========================================================================
 * 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 已提交
1148
 * OUT assertion: the match length is not greater than s->lookahead.
M
Mark Adler 已提交
1149 1150 1151 1152 1153
 */
#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 已提交
1154
local uInt longest_match(s, cur_match)
M
Mark Adler 已提交
1155 1156 1157 1158
    deflate_state *s;
    IPos cur_match;                             /* current match */
{
    unsigned chain_length = s->max_chain_length;/* max hash chain length */
M
Mark Adler 已提交
1159
    register Bytef *scan = s->window + s->strstart; /* current string */
M
Mark Adler 已提交
1160
    register Bytef *match;                      /* matched string */
M
Mark Adler 已提交
1161
    register int len;                           /* length of current match */
M
Mark Adler 已提交
1162
    int best_len = (int)s->prev_length;         /* best match length so far */
M
Mark Adler 已提交
1163
    int nice_match = s->nice_match;             /* stop if match long enough */
M
Mark Adler 已提交
1164
    IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
M
Mark Adler 已提交
1165
        s->strstart - (IPos)MAX_DIST(s) : NIL;
M
Mark Adler 已提交
1166 1167 1168
    /* Stop when cur_match becomes <= limit. To simplify the code,
     * we prevent matches with the string of window index 0.
     */
M
Mark Adler 已提交
1169
    Posf *prev = s->prev;
M
Mark Adler 已提交
1170
    uInt wmask = s->w_mask;
M
Mark Adler 已提交
1171 1172 1173 1174 1175

#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 已提交
1176
    register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
M
Mark Adler 已提交
1177 1178
    register ush scan_start = *(ushf*)scan;
    register ush scan_end   = *(ushf*)(scan+best_len-1);
M
Mark Adler 已提交
1179
#else
M
Mark Adler 已提交
1180
    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
M
Mark Adler 已提交
1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193
    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 已提交
1194 1195 1196
    /* Do not look for matches beyond the end of the input. This is necessary
     * to make deflate deterministic.
     */
M
Mark Adler 已提交
1197
    if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead;
M
Mark Adler 已提交
1198

M
Mark Adler 已提交
1199
    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
M
Mark Adler 已提交
1200 1201 1202 1203 1204 1205

    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 已提交
1206 1207 1208 1209 1210 1211
         * 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 已提交
1212 1213 1214 1215 1216
         */
#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 已提交
1217 1218
        if (*(ushf*)(match+best_len-1) != scan_end ||
            *(ushf*)match != scan_start) continue;
M
Mark Adler 已提交
1219 1220 1221 1222 1223 1224 1225 1226 1227 1228

        /* 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 已提交
1229
        Assert(scan[2] == match[2], "scan[2]?");
M
Mark Adler 已提交
1230 1231
        scan++, match++;
        do {
M
Mark Adler 已提交
1232 1233 1234 1235
        } 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 已提交
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259
                 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 已提交
1260
        Assert(*scan == *match, "match[2]?");
M
Mark Adler 已提交
1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281

        /* 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 已提交
1282
            if (len >= nice_match) break;
M
Mark Adler 已提交
1283
#ifdef UNALIGNED_OK
M
Mark Adler 已提交
1284
            scan_end = *(ushf*)(scan+best_len-1);
M
Mark Adler 已提交
1285 1286 1287 1288 1289
#else
            scan_end1  = scan[best_len-1];
            scan_end   = scan[best_len];
#endif
        }
M
Mark Adler 已提交
1290
    } while ((cur_match = prev[cur_match & wmask]) > limit
M
Mark Adler 已提交
1291 1292
             && --chain_length != 0);

M
Mark Adler 已提交
1293
    if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
M
Mark Adler 已提交
1294
    return s->lookahead;
M
Mark Adler 已提交
1295
}
M
Mark Adler 已提交
1296
#endif /* ASMV */
M
Mark Adler 已提交
1297 1298

#else /* FASTEST */
M
Mark Adler 已提交
1299 1300

/* ---------------------------------------------------------------------------
M
Mark Adler 已提交
1301
 * Optimized version for FASTEST only
M
Mark Adler 已提交
1302
 */
M
Mark Adler 已提交
1303
local uInt longest_match(s, cur_match)
M
Mark Adler 已提交
1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340
    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 已提交
1341 1342 1343 1344
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             *++scan == *++match && *++scan == *++match &&
             scan < strend);
M
Mark Adler 已提交
1345 1346 1347 1348 1349 1350 1351 1352

    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 已提交
1353
    return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
M
Mark Adler 已提交
1354
}
M
Mark Adler 已提交
1355

M
Mark Adler 已提交
1356 1357
#endif /* FASTEST */

1358
#ifdef ZLIB_DEBUG
1359 1360 1361 1362

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

M
Mark Adler 已提交
1363 1364 1365 1366 1367 1368 1369 1370 1371
/* ===========================================================================
 * 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 已提交
1372 1373
    if (zmemcmp(s->window + match,
                s->window + start, length) != EQUAL) {
M
Mark Adler 已提交
1374
        fprintf(stderr, " start %u, match %u, length %d\n",
M
Mark Adler 已提交
1375
                start, match, length);
M
Mark Adler 已提交
1376
        do {
M
Mark Adler 已提交
1377 1378
            fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
        } while (--length != 0);
M
Mark Adler 已提交
1379 1380
        z_error("invalid match");
    }
M
Mark Adler 已提交
1381
    if (z_verbose > 1) {
M
Mark Adler 已提交
1382 1383
        fprintf(stderr,"\\[%d,%d]", start-match, length);
        do { putc(s->window[start++], stderr); } while (--length != 0);
M
Mark Adler 已提交
1384 1385 1386 1387
    }
}
#else
#  define check_match(s, start, match, length)
1388
#endif /* ZLIB_DEBUG */
M
Mark Adler 已提交
1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403

/* ===========================================================================
 * 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;
{
    register unsigned n, m;
M
Mark Adler 已提交
1404
    register Posf *p;
M
Mark Adler 已提交
1405
    unsigned more;    /* Amount of free space at the end of the window. */
M
Mark Adler 已提交
1406
    uInt wsize = s->w_size;
M
Mark Adler 已提交
1407

1408 1409
    Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");

M
Mark Adler 已提交
1410
    do {
M
Mark Adler 已提交
1411
        more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
M
Mark Adler 已提交
1412

M
Mark Adler 已提交
1413
        /* Deal with !@#$% 64K limit: */
M
Mark Adler 已提交
1414 1415 1416
        if (sizeof(int) <= 2) {
            if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
                more = wsize;
M
Mark Adler 已提交
1417

M
Mark Adler 已提交
1418 1419
            } else if (more == (unsigned)(-1)) {
                /* Very unlikely, but possible on 16 bit machine if
M
Mark Adler 已提交
1420
                 * strstart == 0 && lookahead == 1 (input done a byte at time)
M
Mark Adler 已提交
1421 1422 1423 1424
                 */
                more--;
            }
        }
M
Mark Adler 已提交
1425 1426 1427 1428

        /* 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 已提交
1429
        if (s->strstart >= wsize+MAX_DIST(s)) {
M
Mark Adler 已提交
1430

M
Mark Adler 已提交
1431
            zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
M
Mark Adler 已提交
1432 1433 1434
            s->match_start -= wsize;
            s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
            s->block_start -= (long) wsize;
M
Mark Adler 已提交
1435

M
Mark Adler 已提交
1436
            /* Slide the hash table (could be avoided with 32 bit values
M
Mark Adler 已提交
1437 1438 1439 1440
               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. (Using level 0 permanently is not an optimal usage of
               zlib, so we don't care about this pathological case.)
M
Mark Adler 已提交
1441
             */
M
Mark Adler 已提交
1442 1443 1444 1445 1446 1447 1448 1449
            n = s->hash_size;
            p = &s->head[n];
            do {
                m = *--p;
                *p = (Pos)(m >= wsize ? m-wsize : NIL);
            } while (--n);

            n = wsize;
M
Mark Adler 已提交
1450
#ifndef FASTEST
M
Mark Adler 已提交
1451 1452 1453 1454 1455 1456 1457 1458
            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);
M
Mark Adler 已提交
1459
#endif
M
Mark Adler 已提交
1460
            more += wsize;
M
Mark Adler 已提交
1461
        }
1462
        if (s->strm->avail_in == 0) break;
M
Mark Adler 已提交
1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476

        /* 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 已提交
1477
        n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
M
Mark Adler 已提交
1478
        s->lookahead += n;
M
Mark Adler 已提交
1479

M
Mark Adler 已提交
1480
        /* Initialize the hash value now that we have some input: */
1481 1482 1483 1484
        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 已提交
1485 1486 1487
#if MIN_MATCH != 3
            Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498
            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 已提交
1499 1500 1501 1502 1503
        }
        /* 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 已提交
1504
    } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
M
Mark Adler 已提交
1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538

    /* 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;
        }
    }
1539 1540 1541

    Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
           "not enough room for search");
M
Mark Adler 已提交
1542 1543 1544 1545 1546 1547
}

/* ===========================================================================
 * 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 已提交
1548
#define FLUSH_BLOCK_ONLY(s, last) { \
M
Mark Adler 已提交
1549 1550 1551
   _tr_flush_block(s, (s->block_start >= 0L ? \
                   (charf *)&s->window[(unsigned)s->block_start] : \
                   (charf *)Z_NULL), \
M
Mark Adler 已提交
1552
                (ulg)((long)s->strstart - s->block_start), \
M
Mark Adler 已提交
1553
                (last)); \
M
Mark Adler 已提交
1554 1555
   s->block_start = s->strstart; \
   flush_pending(s->strm); \
M
Mark Adler 已提交
1556
   Tracev((stderr,"[FLUSH]")); \
M
Mark Adler 已提交
1557 1558 1559
}

/* Same but force premature exit if necessary. */
M
Mark Adler 已提交
1560 1561 1562
#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 已提交
1563 1564
}

M
Mark Adler 已提交
1565 1566
/* ===========================================================================
 * Copy without compression as much as possible from the input stream, return
M
Mark Adler 已提交
1567 1568 1569
 * the current block state.
 * This function does not insert new strings in the dictionary since
 * uncompressible data is probably not useful. This function is used
M
Mark Adler 已提交
1570
 * only for the level=0 compression option.
M
Mark Adler 已提交
1571 1572
 * NOTE: this function should be optimized to avoid extra copying from
 * window to pending_buf.
M
Mark Adler 已提交
1573
 */
M
Mark Adler 已提交
1574
local block_state deflate_stored(s, flush)
M
Mark Adler 已提交
1575 1576 1577
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588
    /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
     * to pending_buf_size, and each stored block has a 5 byte header:
     */
    ulg max_block_size = 0xffff;
    ulg max_start;

    if (max_block_size > s->pending_buf_size - 5) {
        max_block_size = s->pending_buf_size - 5;
    }

    /* Copy as much as possible from input to output: */
M
Mark Adler 已提交
1589 1590 1591 1592 1593
    for (;;) {
        /* Fill the window as much as possible: */
        if (s->lookahead <= 1) {

            Assert(s->strstart < s->w_size+MAX_DIST(s) ||
M
Mark Adler 已提交
1594
                   s->block_start >= (long)s->w_size, "slide too late");
M
Mark Adler 已提交
1595 1596

            fill_window(s);
M
Mark Adler 已提交
1597
            if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
M
Mark Adler 已提交
1598 1599 1600

            if (s->lookahead == 0) break; /* flush the current block */
        }
M
Mark Adler 已提交
1601
        Assert(s->block_start >= 0L, "block gone");
M
Mark Adler 已提交
1602

M
Mark Adler 已提交
1603 1604
        s->strstart += s->lookahead;
        s->lookahead = 0;
M
Mark Adler 已提交
1605

M
Mark Adler 已提交
1606
        /* Emit a stored block if pending_buf will be full: */
M
Mark Adler 已提交
1607
        max_start = max_block_size + (ulg)s->block_start;
M
Mark Adler 已提交
1608
        if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
M
Mark Adler 已提交
1609 1610 1611
            /* strstart == 0 is possible when wraparound on 16-bit machine */
            s->lookahead = (uInt)(s->strstart - max_start);
            s->strstart = (uInt)max_start;
M
Mark Adler 已提交
1612
            FLUSH_BLOCK(s, 0);
M
Mark Adler 已提交
1613 1614
        }
        /* Flush if we may have to slide, otherwise block_start may become
M
Mark Adler 已提交
1615 1616
         * negative and the data will be gone:
         */
M
Mark Adler 已提交
1617 1618
        if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
            FLUSH_BLOCK(s, 0);
M
Mark Adler 已提交
1619
        }
M
Mark Adler 已提交
1620
    }
1621
    s->insert = 0;
1622 1623 1624 1625 1626 1627 1628
    if (flush == Z_FINISH) {
        FLUSH_BLOCK(s, 1);
        return finish_done;
    }
    if ((long)s->strstart > s->block_start)
        FLUSH_BLOCK(s, 0);
    return block_done;
M
Mark Adler 已提交
1629 1630
}

M
Mark Adler 已提交
1631
/* ===========================================================================
M
Mark Adler 已提交
1632 1633
 * Compress as much as possible from the input stream, return the current
 * block state.
M
Mark Adler 已提交
1634
 * This function does not perform lazy evaluation of matches and inserts
M
Mark Adler 已提交
1635 1636 1637
 * 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 已提交
1638
local block_state deflate_fast(s, flush)
M
Mark Adler 已提交
1639 1640 1641
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
1642
    IPos hash_head;       /* head of the hash chain */
M
Mark Adler 已提交
1643
    int bflush;           /* set if current block must be flushed */
M
Mark Adler 已提交
1644 1645 1646 1647 1648 1649 1650 1651

    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 已提交
1652
            fill_window(s);
M
Mark Adler 已提交
1653
            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
1654 1655
                return need_more;
            }
M
Mark Adler 已提交
1656 1657
            if (s->lookahead == 0) break; /* flush the current block */
        }
M
Mark Adler 已提交
1658 1659 1660 1661

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
M
Mark Adler 已提交
1662
        hash_head = NIL;
M
Mark Adler 已提交
1663 1664 1665
        if (s->lookahead >= MIN_MATCH) {
            INSERT_STRING(s, s->strstart, hash_head);
        }
M
Mark Adler 已提交
1666 1667 1668 1669 1670 1671 1672 1673 1674

        /* 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 已提交
1675 1676
            s->match_length = longest_match (s, hash_head);
            /* longest_match() sets match_start */
M
Mark Adler 已提交
1677 1678 1679 1680
        }
        if (s->match_length >= MIN_MATCH) {
            check_match(s, s->strstart, s->match_start, s->match_length);

M
Mark Adler 已提交
1681 1682
            _tr_tally_dist(s, s->strstart - s->match_start,
                           s->match_length - MIN_MATCH, bflush);
M
Mark Adler 已提交
1683 1684 1685 1686 1687 1688

            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 已提交
1689
#ifndef FASTEST
M
Mark Adler 已提交
1690 1691
            if (s->match_length <= s->max_insert_length &&
                s->lookahead >= MIN_MATCH) {
M
Mark Adler 已提交
1692
                s->match_length--; /* string at strstart already in table */
M
Mark Adler 已提交
1693 1694 1695 1696
                do {
                    s->strstart++;
                    INSERT_STRING(s, s->strstart, hash_head);
                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
M
Mark Adler 已提交
1697
                     * always MIN_MATCH bytes ahead.
M
Mark Adler 已提交
1698 1699
                     */
                } while (--s->match_length != 0);
M
Mark Adler 已提交
1700
                s->strstart++;
M
Mark Adler 已提交
1701 1702
            } else
#endif
M
Mark Adler 已提交
1703
            {
M
Mark Adler 已提交
1704 1705 1706 1707 1708 1709 1710
                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 已提交
1711 1712 1713
                /* 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 已提交
1714 1715 1716 1717
            }
        } else {
            /* No match, output a literal byte */
            Tracevv((stderr,"%c", s->window[s->strstart]));
M
Mark Adler 已提交
1718
            _tr_tally_lit (s, s->window[s->strstart], bflush);
M
Mark Adler 已提交
1719
            s->lookahead--;
M
Mark Adler 已提交
1720
            s->strstart++;
M
Mark Adler 已提交
1721 1722 1723
        }
        if (bflush) FLUSH_BLOCK(s, 0);
    }
1724
    s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1725 1726 1727 1728 1729 1730 1731
    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 已提交
1732 1733
}

M
Mark Adler 已提交
1734
#ifndef FASTEST
M
Mark Adler 已提交
1735 1736 1737 1738 1739
/* ===========================================================================
 * 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 已提交
1740
local block_state deflate_slow(s, flush)
M
Mark Adler 已提交
1741 1742 1743
    deflate_state *s;
    int flush;
{
M
Mark Adler 已提交
1744
    IPos hash_head;          /* head of hash chain */
M
Mark Adler 已提交
1745 1746 1747 1748 1749 1750 1751 1752 1753 1754
    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 已提交
1755
            fill_window(s);
M
Mark Adler 已提交
1756
            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
1757 1758
                return need_more;
            }
M
Mark Adler 已提交
1759 1760
            if (s->lookahead == 0) break; /* flush the current block */
        }
M
Mark Adler 已提交
1761 1762 1763 1764

        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
M
Mark Adler 已提交
1765
        hash_head = NIL;
M
Mark Adler 已提交
1766 1767 1768
        if (s->lookahead >= MIN_MATCH) {
            INSERT_STRING(s, s->strstart, hash_head);
        }
M
Mark Adler 已提交
1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780

        /* 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 已提交
1781 1782
            s->match_length = longest_match (s, hash_head);
            /* longest_match() sets match_start */
M
Mark Adler 已提交
1783

M
Mark Adler 已提交
1784
            if (s->match_length <= 5 && (s->strategy == Z_FILTERED
M
Mark Adler 已提交
1785
#if TOO_FAR <= 32767
M
Mark Adler 已提交
1786 1787 1788 1789
                || (s->match_length == MIN_MATCH &&
                    s->strstart - s->match_start > TOO_FAR)
#endif
                )) {
M
Mark Adler 已提交
1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800

                /* 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 已提交
1801 1802
            uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
            /* Do not insert strings in hash table beyond this. */
M
Mark Adler 已提交
1803 1804 1805

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

M
Mark Adler 已提交
1806
            _tr_tally_dist(s, s->strstart -1 - s->prev_match,
M
Mark Adler 已提交
1807
                           s->prev_length - MIN_MATCH, bflush);
M
Mark Adler 已提交
1808 1809

            /* Insert in hash table all strings up to the end of the match.
M
Mark Adler 已提交
1810 1811 1812
             * 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 已提交
1813 1814 1815 1816
             */
            s->lookahead -= s->prev_length-1;
            s->prev_length -= 2;
            do {
M
Mark Adler 已提交
1817 1818 1819
                if (++s->strstart <= max_insert) {
                    INSERT_STRING(s, s->strstart, hash_head);
                }
M
Mark Adler 已提交
1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832
            } 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 已提交
1833 1834
            _tr_tally_lit(s, s->window[s->strstart-1], bflush);
            if (bflush) {
M
Mark Adler 已提交
1835
                FLUSH_BLOCK_ONLY(s, 0);
M
Mark Adler 已提交
1836 1837 1838
            }
            s->strstart++;
            s->lookahead--;
M
Mark Adler 已提交
1839
            if (s->strm->avail_out == 0) return need_more;
M
Mark Adler 已提交
1840 1841 1842 1843 1844 1845 1846 1847 1848
        } 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 已提交
1849
    Assert (flush != Z_NO_FLUSH, "no flush?");
M
Mark Adler 已提交
1850
    if (s->match_available) {
M
Mark Adler 已提交
1851
        Tracevv((stderr,"%c", s->window[s->strstart-1]));
M
Mark Adler 已提交
1852
        _tr_tally_lit(s, s->window[s->strstart-1], bflush);
M
Mark Adler 已提交
1853
        s->match_available = 0;
M
Mark Adler 已提交
1854
    }
1855
    s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1856 1857 1858 1859 1860 1861 1862
    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 已提交
1863
}
M
Mark Adler 已提交
1864
#endif /* FASTEST */
M
Mark Adler 已提交
1865 1866 1867 1868 1869 1870 1871 1872 1873 1874

/* ===========================================================================
 * 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 已提交
1875 1876 1877
    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 已提交
1878 1879 1880 1881

    for (;;) {
        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
1882
         * for the longest run, plus one for the unrolled loop.
M
Mark Adler 已提交
1883
         */
1884
        if (s->lookahead <= MAX_MATCH) {
M
Mark Adler 已提交
1885
            fill_window(s);
1886
            if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
M
Mark Adler 已提交
1887 1888 1889 1890 1891 1892
                return need_more;
            }
            if (s->lookahead == 0) break; /* flush the current block */
        }

        /* See how many times the previous byte repeats */
M
Mark Adler 已提交
1893 1894
        s->match_length = 0;
        if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
M
Mark Adler 已提交
1895
            scan = s->window + s->strstart - 1;
M
Mark Adler 已提交
1896 1897 1898 1899 1900 1901 1902 1903 1904
            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 已提交
1905
                s->match_length = MAX_MATCH - (uInt)(strend - scan);
M
Mark Adler 已提交
1906 1907 1908
                if (s->match_length > s->lookahead)
                    s->match_length = s->lookahead;
            }
1909
            Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
M
Mark Adler 已提交
1910 1911 1912
        }

        /* Emit match if have run of MIN_MATCH or longer, else emit literal */
M
Mark Adler 已提交
1913 1914 1915 1916 1917 1918 1919 1920
        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 已提交
1921 1922 1923 1924 1925 1926 1927 1928 1929
        } 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);
    }
1930
    s->insert = 0;
1931 1932 1933 1934 1935 1936 1937
    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 已提交
1938
}
M
Mark Adler 已提交
1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968

/* ===========================================================================
 * 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);
    }
1969
    s->insert = 0;
1970 1971 1972 1973 1974 1975 1976
    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 已提交
1977
}