source: trunk/third/zlib/deflate.c @ 17315

Revision 17315, 47.9 KB checked in by zacheiss, 23 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r17314, which included commits to RCS files with non-trunk default branches.
Line 
1/* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2002 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 *  ALGORITHM
8 *
9 *      The "deflation" process depends on being able to identify portions
10 *      of the input text which are identical to earlier input (within a
11 *      sliding window trailing behind the input currently being processed).
12 *
13 *      The most straightforward technique turns out to be the fastest for
14 *      most input files: try all possible matches and select the longest.
15 *      The key feature of this algorithm is that insertions into the string
16 *      dictionary are very simple and thus fast, and deletions are avoided
17 *      completely. Insertions are performed at each input character, whereas
18 *      string matches are performed only when the previous match ends. So it
19 *      is preferable to spend more time in matches to allow very fast string
20 *      insertions and avoid deletions. The matching algorithm for small
21 *      strings is inspired from that of Rabin & Karp. A brute force approach
22 *      is used to find longer strings when a small match has been found.
23 *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
24 *      (by Leonid Broukhis).
25 *         A previous version of this file used a more sophisticated algorithm
26 *      (by Fiala and Greene) which is guaranteed to run in linear amortized
27 *      time, but has a larger average cost, uses more memory and is patented.
28 *      However the F&G algorithm may be faster for some highly redundant
29 *      files if the parameter max_chain_length (described below) is too large.
30 *
31 *  ACKNOWLEDGEMENTS
32 *
33 *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
34 *      I found it in 'freeze' written by Leonid Broukhis.
35 *      Thanks to many people for bug reports and testing.
36 *
37 *  REFERENCES
38 *
39 *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
40 *      Available in ftp://ds.internic.net/rfc/rfc1951.txt
41 *
42 *      A description of the Rabin and Karp algorithm is given in the book
43 *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
44 *
45 *      Fiala,E.R., and Greene,D.H.
46 *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
47 *
48 */
49
50/* @(#) $Id: deflate.c,v 1.1.1.2 2002-03-12 17:19:11 zacheiss Exp $ */
51
52#include "deflate.h"
53
54const char deflate_copyright[] =
55   " deflate 1.1.4 Copyright 1995-2002 Jean-loup Gailly ";
56/*
57  If you use the zlib library in a product, an acknowledgment is welcome
58  in the documentation of your product. If for some reason you cannot
59  include such an acknowledgment, I would appreciate that you keep this
60  copyright string in the executable of your product.
61 */
62
63/* ===========================================================================
64 *  Function prototypes.
65 */
66typedef enum {
67    need_more,      /* block not completed, need more input or more output */
68    block_done,     /* block flush performed */
69    finish_started, /* finish started, need only more output at next deflate */
70    finish_done     /* finish done, accept no more input or output */
71} block_state;
72
73typedef block_state (*compress_func) OF((deflate_state *s, int flush));
74/* Compression function. Returns the block state after the call. */
75
76local void fill_window    OF((deflate_state *s));
77local block_state deflate_stored OF((deflate_state *s, int flush));
78local block_state deflate_fast   OF((deflate_state *s, int flush));
79local block_state deflate_slow   OF((deflate_state *s, int flush));
80local void lm_init        OF((deflate_state *s));
81local void putShortMSB    OF((deflate_state *s, uInt b));
82local void flush_pending  OF((z_streamp strm));
83local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));
84#ifdef ASMV
85      void match_init OF((void)); /* asm code initialization */
86      uInt longest_match  OF((deflate_state *s, IPos cur_match));
87#else
88local uInt longest_match  OF((deflate_state *s, IPos cur_match));
89#endif
90
91#ifdef DEBUG
92local  void check_match OF((deflate_state *s, IPos start, IPos match,
93                            int length));
94#endif
95
96/* ===========================================================================
97 * Local data
98 */
99
100#define NIL 0
101/* Tail of hash chains */
102
103#ifndef TOO_FAR
104#  define TOO_FAR 4096
105#endif
106/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
107
108#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
109/* Minimum amount of lookahead, except at the end of the input file.
110 * See deflate.c for comments about the MIN_MATCH+1.
111 */
112
113/* Values for max_lazy_match, good_match and max_chain_length, depending on
114 * the desired pack level (0..9). The values given below have been tuned to
115 * exclude worst case performance for pathological files. Better values may be
116 * found for specific files.
117 */
118typedef struct config_s {
119   ush good_length; /* reduce lazy search above this match length */
120   ush max_lazy;    /* do not perform lazy search above this match length */
121   ush nice_length; /* quit search above this match length */
122   ush max_chain;
123   compress_func func;
124} config;
125
126local const config configuration_table[10] = {
127/*      good lazy nice chain */
128/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
129/* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
130/* 2 */ {4,    5, 16,    8, deflate_fast},
131/* 3 */ {4,    6, 32,   32, deflate_fast},
132
133/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
134/* 5 */ {8,   16, 32,   32, deflate_slow},
135/* 6 */ {8,   16, 128, 128, deflate_slow},
136/* 7 */ {8,   32, 128, 256, deflate_slow},
137/* 8 */ {32, 128, 258, 1024, deflate_slow},
138/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */
139
140/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
141 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
142 * meaning.
143 */
144
145#define EQUAL 0
146/* result of memcmp for equal strings */
147
148struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
149
150/* ===========================================================================
151 * Update a hash value with the given input byte
152 * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
153 *    input characters, so that a running hash key can be computed from the
154 *    previous key instead of complete recalculation each time.
155 */
156#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
157
158
159/* ===========================================================================
160 * Insert string str in the dictionary and set match_head to the previous head
161 * of the hash chain (the most recent string with same hash key). Return
162 * the previous length of the hash chain.
163 * If this file is compiled with -DFASTEST, the compression level is forced
164 * to 1, and no hash chains are maintained.
165 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
166 *    input characters and the first MIN_MATCH bytes of str are valid
167 *    (except for the last MIN_MATCH-1 bytes of the input file).
168 */
169#ifdef FASTEST
170#define INSERT_STRING(s, str, match_head) \
171   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
172    match_head = s->head[s->ins_h], \
173    s->head[s->ins_h] = (Pos)(str))
174#else
175#define INSERT_STRING(s, str, match_head) \
176   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
177    s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
178    s->head[s->ins_h] = (Pos)(str))
179#endif
180
181/* ===========================================================================
182 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
183 * prev[] will be initialized on the fly.
184 */
185#define CLEAR_HASH(s) \
186    s->head[s->hash_size-1] = NIL; \
187    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
188
189/* ========================================================================= */
190int ZEXPORT deflateInit_(strm, level, version, stream_size)
191    z_streamp strm;
192    int level;
193    const char *version;
194    int stream_size;
195{
196    return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
197                         Z_DEFAULT_STRATEGY, version, stream_size);
198    /* To do: ignore strm->next_in if we use it as window */
199}
200
201/* ========================================================================= */
202int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
203                  version, stream_size)
204    z_streamp strm;
205    int  level;
206    int  method;
207    int  windowBits;
208    int  memLevel;
209    int  strategy;
210    const char *version;
211    int stream_size;
212{
213    deflate_state *s;
214    int noheader = 0;
215    static const char* my_version = ZLIB_VERSION;
216
217    ushf *overlay;
218    /* We overlay pending_buf and d_buf+l_buf. This works since the average
219     * output size for (length,distance) codes is <= 24 bits.
220     */
221
222    if (version == Z_NULL || version[0] != my_version[0] ||
223        stream_size != sizeof(z_stream)) {
224        return Z_VERSION_ERROR;
225    }
226    if (strm == Z_NULL) return Z_STREAM_ERROR;
227
228    strm->msg = Z_NULL;
229    if (strm->zalloc == Z_NULL) {
230        strm->zalloc = zcalloc;
231        strm->opaque = (voidpf)0;
232    }
233    if (strm->zfree == Z_NULL) strm->zfree = zcfree;
234
235    if (level == Z_DEFAULT_COMPRESSION) level = 6;
236#ifdef FASTEST
237    level = 1;
238#endif
239
240    if (windowBits < 0) { /* undocumented feature: suppress zlib header */
241        noheader = 1;
242        windowBits = -windowBits;
243    }
244    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
245        windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
246        strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
247        return Z_STREAM_ERROR;
248    }
249    s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
250    if (s == Z_NULL) return Z_MEM_ERROR;
251    strm->state = (struct internal_state FAR *)s;
252    s->strm = strm;
253
254    s->noheader = noheader;
255    s->w_bits = windowBits;
256    s->w_size = 1 << s->w_bits;
257    s->w_mask = s->w_size - 1;
258
259    s->hash_bits = memLevel + 7;
260    s->hash_size = 1 << s->hash_bits;
261    s->hash_mask = s->hash_size - 1;
262    s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
263
264    s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
265    s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
266    s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
267
268    s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
269
270    overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
271    s->pending_buf = (uchf *) overlay;
272    s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
273
274    if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
275        s->pending_buf == Z_NULL) {
276        strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
277        deflateEnd (strm);
278        return Z_MEM_ERROR;
279    }
280    s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
281    s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
282
283    s->level = level;
284    s->strategy = strategy;
285    s->method = (Byte)method;
286
287    return deflateReset(strm);
288}
289
290/* ========================================================================= */
291int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
292    z_streamp strm;
293    const Bytef *dictionary;
294    uInt  dictLength;
295{
296    deflate_state *s;
297    uInt length = dictLength;
298    uInt n;
299    IPos hash_head = 0;
300
301    if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
302        strm->state->status != INIT_STATE) return Z_STREAM_ERROR;
303
304    s = strm->state;
305    strm->adler = adler32(strm->adler, dictionary, dictLength);
306
307    if (length < MIN_MATCH) return Z_OK;
308    if (length > MAX_DIST(s)) {
309        length = MAX_DIST(s);
310#ifndef USE_DICT_HEAD
311        dictionary += dictLength - length; /* use the tail of the dictionary */
312#endif
313    }
314    zmemcpy(s->window, dictionary, length);
315    s->strstart = length;
316    s->block_start = (long)length;
317
318    /* Insert all strings in the hash table (except for the last two bytes).
319     * s->lookahead stays null, so s->ins_h will be recomputed at the next
320     * call of fill_window.
321     */
322    s->ins_h = s->window[0];
323    UPDATE_HASH(s, s->ins_h, s->window[1]);
324    for (n = 0; n <= length - MIN_MATCH; n++) {
325        INSERT_STRING(s, n, hash_head);
326    }
327    if (hash_head) hash_head = 0;  /* to make compiler happy */
328    return Z_OK;
329}
330
331/* ========================================================================= */
332int ZEXPORT deflateReset (strm)
333    z_streamp strm;
334{
335    deflate_state *s;
336   
337    if (strm == Z_NULL || strm->state == Z_NULL ||
338        strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
339
340    strm->total_in = strm->total_out = 0;
341    strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
342    strm->data_type = Z_UNKNOWN;
343
344    s = (deflate_state *)strm->state;
345    s->pending = 0;
346    s->pending_out = s->pending_buf;
347
348    if (s->noheader < 0) {
349        s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
350    }
351    s->status = s->noheader ? BUSY_STATE : INIT_STATE;
352    strm->adler = 1;
353    s->last_flush = Z_NO_FLUSH;
354
355    _tr_init(s);
356    lm_init(s);
357
358    return Z_OK;
359}
360
361/* ========================================================================= */
362int ZEXPORT deflateParams(strm, level, strategy)
363    z_streamp strm;
364    int level;
365    int strategy;
366{
367    deflate_state *s;
368    compress_func func;
369    int err = Z_OK;
370
371    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
372    s = strm->state;
373
374    if (level == Z_DEFAULT_COMPRESSION) {
375        level = 6;
376    }
377    if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
378        return Z_STREAM_ERROR;
379    }
380    func = configuration_table[s->level].func;
381
382    if (func != configuration_table[level].func && strm->total_in != 0) {
383        /* Flush the last buffer: */
384        err = deflate(strm, Z_PARTIAL_FLUSH);
385    }
386    if (s->level != level) {
387        s->level = level;
388        s->max_lazy_match   = configuration_table[level].max_lazy;
389        s->good_match       = configuration_table[level].good_length;
390        s->nice_match       = configuration_table[level].nice_length;
391        s->max_chain_length = configuration_table[level].max_chain;
392    }
393    s->strategy = strategy;
394    return err;
395}
396
397/* =========================================================================
398 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
399 * IN assertion: the stream state is correct and there is enough room in
400 * pending_buf.
401 */
402local void putShortMSB (s, b)
403    deflate_state *s;
404    uInt b;
405{
406    put_byte(s, (Byte)(b >> 8));
407    put_byte(s, (Byte)(b & 0xff));
408}   
409
410/* =========================================================================
411 * Flush as much pending output as possible. All deflate() output goes
412 * through this function so some applications may wish to modify it
413 * to avoid allocating a large strm->next_out buffer and copying into it.
414 * (See also read_buf()).
415 */
416local void flush_pending(strm)
417    z_streamp strm;
418{
419    unsigned len = strm->state->pending;
420
421    if (len > strm->avail_out) len = strm->avail_out;
422    if (len == 0) return;
423
424    zmemcpy(strm->next_out, strm->state->pending_out, len);
425    strm->next_out  += len;
426    strm->state->pending_out  += len;
427    strm->total_out += len;
428    strm->avail_out  -= len;
429    strm->state->pending -= len;
430    if (strm->state->pending == 0) {
431        strm->state->pending_out = strm->state->pending_buf;
432    }
433}
434
435/* ========================================================================= */
436int ZEXPORT deflate (strm, flush)
437    z_streamp strm;
438    int flush;
439{
440    int old_flush; /* value of flush param for previous deflate call */
441    deflate_state *s;
442
443    if (strm == Z_NULL || strm->state == Z_NULL ||
444        flush > Z_FINISH || flush < 0) {
445        return Z_STREAM_ERROR;
446    }
447    s = strm->state;
448
449    if (strm->next_out == Z_NULL ||
450        (strm->next_in == Z_NULL && strm->avail_in != 0) ||
451        (s->status == FINISH_STATE && flush != Z_FINISH)) {
452        ERR_RETURN(strm, Z_STREAM_ERROR);
453    }
454    if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
455
456    s->strm = strm; /* just in case */
457    old_flush = s->last_flush;
458    s->last_flush = flush;
459
460    /* Write the zlib header */
461    if (s->status == INIT_STATE) {
462
463        uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
464        uInt level_flags = (s->level-1) >> 1;
465
466        if (level_flags > 3) level_flags = 3;
467        header |= (level_flags << 6);
468        if (s->strstart != 0) header |= PRESET_DICT;
469        header += 31 - (header % 31);
470
471        s->status = BUSY_STATE;
472        putShortMSB(s, header);
473
474        /* Save the adler32 of the preset dictionary: */
475        if (s->strstart != 0) {
476            putShortMSB(s, (uInt)(strm->adler >> 16));
477            putShortMSB(s, (uInt)(strm->adler & 0xffff));
478        }
479        strm->adler = 1L;
480    }
481
482    /* Flush as much pending output as possible */
483    if (s->pending != 0) {
484        flush_pending(strm);
485        if (strm->avail_out == 0) {
486            /* Since avail_out is 0, deflate will be called again with
487             * more output space, but possibly with both pending and
488             * avail_in equal to zero. There won't be anything to do,
489             * but this is not an error situation so make sure we
490             * return OK instead of BUF_ERROR at next call of deflate:
491             */
492            s->last_flush = -1;
493            return Z_OK;
494        }
495
496    /* Make sure there is something to do and avoid duplicate consecutive
497     * flushes. For repeated and useless calls with Z_FINISH, we keep
498     * returning Z_STREAM_END instead of Z_BUFF_ERROR.
499     */
500    } else if (strm->avail_in == 0 && flush <= old_flush &&
501               flush != Z_FINISH) {
502        ERR_RETURN(strm, Z_BUF_ERROR);
503    }
504
505    /* User must not provide more input after the first FINISH: */
506    if (s->status == FINISH_STATE && strm->avail_in != 0) {
507        ERR_RETURN(strm, Z_BUF_ERROR);
508    }
509
510    /* Start a new block or continue the current one.
511     */
512    if (strm->avail_in != 0 || s->lookahead != 0 ||
513        (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
514        block_state bstate;
515
516        bstate = (*(configuration_table[s->level].func))(s, flush);
517
518        if (bstate == finish_started || bstate == finish_done) {
519            s->status = FINISH_STATE;
520        }
521        if (bstate == need_more || bstate == finish_started) {
522            if (strm->avail_out == 0) {
523                s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
524            }
525            return Z_OK;
526            /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
527             * of deflate should use the same flush parameter to make sure
528             * that the flush is complete. So we don't have to output an
529             * empty block here, this will be done at next call. This also
530             * ensures that for a very small output buffer, we emit at most
531             * one empty block.
532             */
533        }
534        if (bstate == block_done) {
535            if (flush == Z_PARTIAL_FLUSH) {
536                _tr_align(s);
537            } else { /* FULL_FLUSH or SYNC_FLUSH */
538                _tr_stored_block(s, (char*)0, 0L, 0);
539                /* For a full flush, this empty block will be recognized
540                 * as a special marker by inflate_sync().
541                 */
542                if (flush == Z_FULL_FLUSH) {
543                    CLEAR_HASH(s);             /* forget history */
544                }
545            }
546            flush_pending(strm);
547            if (strm->avail_out == 0) {
548              s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
549              return Z_OK;
550            }
551        }
552    }
553    Assert(strm->avail_out > 0, "bug2");
554
555    if (flush != Z_FINISH) return Z_OK;
556    if (s->noheader) return Z_STREAM_END;
557
558    /* Write the zlib trailer (adler32) */
559    putShortMSB(s, (uInt)(strm->adler >> 16));
560    putShortMSB(s, (uInt)(strm->adler & 0xffff));
561    flush_pending(strm);
562    /* If avail_out is zero, the application will call deflate again
563     * to flush the rest.
564     */
565    s->noheader = -1; /* write the trailer only once! */
566    return s->pending != 0 ? Z_OK : Z_STREAM_END;
567}
568
569/* ========================================================================= */
570int ZEXPORT deflateEnd (strm)
571    z_streamp strm;
572{
573    int status;
574
575    if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
576
577    status = strm->state->status;
578    if (status != INIT_STATE && status != BUSY_STATE &&
579        status != FINISH_STATE) {
580      return Z_STREAM_ERROR;
581    }
582
583    /* Deallocate in reverse order of allocations: */
584    TRY_FREE(strm, strm->state->pending_buf);
585    TRY_FREE(strm, strm->state->head);
586    TRY_FREE(strm, strm->state->prev);
587    TRY_FREE(strm, strm->state->window);
588
589    ZFREE(strm, strm->state);
590    strm->state = Z_NULL;
591
592    return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
593}
594
595/* =========================================================================
596 * Copy the source state to the destination state.
597 * To simplify the source, this is not supported for 16-bit MSDOS (which
598 * doesn't have enough memory anyway to duplicate compression states).
599 */
600int ZEXPORT deflateCopy (dest, source)
601    z_streamp dest;
602    z_streamp source;
603{
604#ifdef MAXSEG_64K
605    return Z_STREAM_ERROR;
606#else
607    deflate_state *ds;
608    deflate_state *ss;
609    ushf *overlay;
610
611
612    if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
613        return Z_STREAM_ERROR;
614    }
615
616    ss = source->state;
617
618    *dest = *source;
619
620    ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
621    if (ds == Z_NULL) return Z_MEM_ERROR;
622    dest->state = (struct internal_state FAR *) ds;
623    *ds = *ss;
624    ds->strm = dest;
625
626    ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
627    ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));
628    ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));
629    overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
630    ds->pending_buf = (uchf *) overlay;
631
632    if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
633        ds->pending_buf == Z_NULL) {
634        deflateEnd (dest);
635        return Z_MEM_ERROR;
636    }
637    /* following zmemcpy do not work for 16-bit MSDOS */
638    zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
639    zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
640    zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
641    zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
642
643    ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
644    ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
645    ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
646
647    ds->l_desc.dyn_tree = ds->dyn_ltree;
648    ds->d_desc.dyn_tree = ds->dyn_dtree;
649    ds->bl_desc.dyn_tree = ds->bl_tree;
650
651    return Z_OK;
652#endif
653}
654
655/* ===========================================================================
656 * Read a new buffer from the current input stream, update the adler32
657 * and total number of bytes read.  All deflate() input goes through
658 * this function so some applications may wish to modify it to avoid
659 * allocating a large strm->next_in buffer and copying from it.
660 * (See also flush_pending()).
661 */
662local int read_buf(strm, buf, size)
663    z_streamp strm;
664    Bytef *buf;
665    unsigned size;
666{
667    unsigned len = strm->avail_in;
668
669    if (len > size) len = size;
670    if (len == 0) return 0;
671
672    strm->avail_in  -= len;
673
674    if (!strm->state->noheader) {
675        strm->adler = adler32(strm->adler, strm->next_in, len);
676    }
677    zmemcpy(buf, strm->next_in, len);
678    strm->next_in  += len;
679    strm->total_in += len;
680
681    return (int)len;
682}
683
684/* ===========================================================================
685 * Initialize the "longest match" routines for a new zlib stream
686 */
687local void lm_init (s)
688    deflate_state *s;
689{
690    s->window_size = (ulg)2L*s->w_size;
691
692    CLEAR_HASH(s);
693
694    /* Set the default configuration parameters:
695     */
696    s->max_lazy_match   = configuration_table[s->level].max_lazy;
697    s->good_match       = configuration_table[s->level].good_length;
698    s->nice_match       = configuration_table[s->level].nice_length;
699    s->max_chain_length = configuration_table[s->level].max_chain;
700
701    s->strstart = 0;
702    s->block_start = 0L;
703    s->lookahead = 0;
704    s->match_length = s->prev_length = MIN_MATCH-1;
705    s->match_available = 0;
706    s->ins_h = 0;
707#ifdef ASMV
708    match_init(); /* initialize the asm code */
709#endif
710}
711
712/* ===========================================================================
713 * Set match_start to the longest match starting at the given string and
714 * return its length. Matches shorter or equal to prev_length are discarded,
715 * in which case the result is equal to prev_length and match_start is
716 * garbage.
717 * IN assertions: cur_match is the head of the hash chain for the current
718 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
719 * OUT assertion: the match length is not greater than s->lookahead.
720 */
721#ifndef ASMV
722/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
723 * match.S. The code will be functionally equivalent.
724 */
725#ifndef FASTEST
726local uInt longest_match(s, cur_match)
727    deflate_state *s;
728    IPos cur_match;                             /* current match */
729{
730    unsigned chain_length = s->max_chain_length;/* max hash chain length */
731    register Bytef *scan = s->window + s->strstart; /* current string */
732    register Bytef *match;                       /* matched string */
733    register int len;                           /* length of current match */
734    int best_len = s->prev_length;              /* best match length so far */
735    int nice_match = s->nice_match;             /* stop if match long enough */
736    IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
737        s->strstart - (IPos)MAX_DIST(s) : NIL;
738    /* Stop when cur_match becomes <= limit. To simplify the code,
739     * we prevent matches with the string of window index 0.
740     */
741    Posf *prev = s->prev;
742    uInt wmask = s->w_mask;
743
744#ifdef UNALIGNED_OK
745    /* Compare two bytes at a time. Note: this is not always beneficial.
746     * Try with and without -DUNALIGNED_OK to check.
747     */
748    register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
749    register ush scan_start = *(ushf*)scan;
750    register ush scan_end   = *(ushf*)(scan+best_len-1);
751#else
752    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
753    register Byte scan_end1  = scan[best_len-1];
754    register Byte scan_end   = scan[best_len];
755#endif
756
757    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
758     * It is easy to get rid of this optimization if necessary.
759     */
760    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
761
762    /* Do not waste too much time if we already have a good match: */
763    if (s->prev_length >= s->good_match) {
764        chain_length >>= 2;
765    }
766    /* Do not look for matches beyond the end of the input. This is necessary
767     * to make deflate deterministic.
768     */
769    if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
770
771    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
772
773    do {
774        Assert(cur_match < s->strstart, "no future");
775        match = s->window + cur_match;
776
777        /* Skip to next match if the match length cannot increase
778         * or if the match length is less than 2:
779         */
780#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
781        /* This code assumes sizeof(unsigned short) == 2. Do not use
782         * UNALIGNED_OK if your compiler uses a different size.
783         */
784        if (*(ushf*)(match+best_len-1) != scan_end ||
785            *(ushf*)match != scan_start) continue;
786
787        /* It is not necessary to compare scan[2] and match[2] since they are
788         * always equal when the other bytes match, given that the hash keys
789         * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
790         * strstart+3, +5, ... up to strstart+257. We check for insufficient
791         * lookahead only every 4th comparison; the 128th check will be made
792         * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
793         * necessary to put more guard bytes at the end of the window, or
794         * to check more often for insufficient lookahead.
795         */
796        Assert(scan[2] == match[2], "scan[2]?");
797        scan++, match++;
798        do {
799        } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
800                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
801                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
802                 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
803                 scan < strend);
804        /* The funny "do {}" generates better code on most compilers */
805
806        /* Here, scan <= window+strstart+257 */
807        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
808        if (*scan == *match) scan++;
809
810        len = (MAX_MATCH - 1) - (int)(strend-scan);
811        scan = strend - (MAX_MATCH-1);
812
813#else /* UNALIGNED_OK */
814
815        if (match[best_len]   != scan_end  ||
816            match[best_len-1] != scan_end1 ||
817            *match            != *scan     ||
818            *++match          != scan[1])      continue;
819
820        /* The check at best_len-1 can be removed because it will be made
821         * again later. (This heuristic is not always a win.)
822         * It is not necessary to compare scan[2] and match[2] since they
823         * are always equal when the other bytes match, given that
824         * the hash keys are equal and that HASH_BITS >= 8.
825         */
826        scan += 2, match++;
827        Assert(*scan == *match, "match[2]?");
828
829        /* We check for insufficient lookahead only every 8th comparison;
830         * the 256th check will be made at strstart+258.
831         */
832        do {
833        } while (*++scan == *++match && *++scan == *++match &&
834                 *++scan == *++match && *++scan == *++match &&
835                 *++scan == *++match && *++scan == *++match &&
836                 *++scan == *++match && *++scan == *++match &&
837                 scan < strend);
838
839        Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
840
841        len = MAX_MATCH - (int)(strend - scan);
842        scan = strend - MAX_MATCH;
843
844#endif /* UNALIGNED_OK */
845
846        if (len > best_len) {
847            s->match_start = cur_match;
848            best_len = len;
849            if (len >= nice_match) break;
850#ifdef UNALIGNED_OK
851            scan_end = *(ushf*)(scan+best_len-1);
852#else
853            scan_end1  = scan[best_len-1];
854            scan_end   = scan[best_len];
855#endif
856        }
857    } while ((cur_match = prev[cur_match & wmask]) > limit
858             && --chain_length != 0);
859
860    if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
861    return s->lookahead;
862}
863
864#else /* FASTEST */
865/* ---------------------------------------------------------------------------
866 * Optimized version for level == 1 only
867 */
868local uInt longest_match(s, cur_match)
869    deflate_state *s;
870    IPos cur_match;                             /* current match */
871{
872    register Bytef *scan = s->window + s->strstart; /* current string */
873    register Bytef *match;                       /* matched string */
874    register int len;                           /* length of current match */
875    register Bytef *strend = s->window + s->strstart + MAX_MATCH;
876
877    /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
878     * It is easy to get rid of this optimization if necessary.
879     */
880    Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
881
882    Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
883
884    Assert(cur_match < s->strstart, "no future");
885
886    match = s->window + cur_match;
887
888    /* Return failure if the match length is less than 2:
889     */
890    if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
891
892    /* The check at best_len-1 can be removed because it will be made
893     * again later. (This heuristic is not always a win.)
894     * It is not necessary to compare scan[2] and match[2] since they
895     * are always equal when the other bytes match, given that
896     * the hash keys are equal and that HASH_BITS >= 8.
897     */
898    scan += 2, match += 2;
899    Assert(*scan == *match, "match[2]?");
900
901    /* We check for insufficient lookahead only every 8th comparison;
902     * the 256th check will be made at strstart+258.
903     */
904    do {
905    } while (*++scan == *++match && *++scan == *++match &&
906             *++scan == *++match && *++scan == *++match &&
907             *++scan == *++match && *++scan == *++match &&
908             *++scan == *++match && *++scan == *++match &&
909             scan < strend);
910
911    Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
912
913    len = MAX_MATCH - (int)(strend - scan);
914
915    if (len < MIN_MATCH) return MIN_MATCH - 1;
916
917    s->match_start = cur_match;
918    return len <= s->lookahead ? len : s->lookahead;
919}
920#endif /* FASTEST */
921#endif /* ASMV */
922
923#ifdef DEBUG
924/* ===========================================================================
925 * Check that the match at match_start is indeed a match.
926 */
927local void check_match(s, start, match, length)
928    deflate_state *s;
929    IPos start, match;
930    int length;
931{
932    /* check that the match is indeed a match */
933    if (zmemcmp(s->window + match,
934                s->window + start, length) != EQUAL) {
935        fprintf(stderr, " start %u, match %u, length %d\n",
936                start, match, length);
937        do {
938            fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
939        } while (--length != 0);
940        z_error("invalid match");
941    }
942    if (z_verbose > 1) {
943        fprintf(stderr,"\\[%d,%d]", start-match, length);
944        do { putc(s->window[start++], stderr); } while (--length != 0);
945    }
946}
947#else
948#  define check_match(s, start, match, length)
949#endif
950
951/* ===========================================================================
952 * Fill the window when the lookahead becomes insufficient.
953 * Updates strstart and lookahead.
954 *
955 * IN assertion: lookahead < MIN_LOOKAHEAD
956 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
957 *    At least one byte has been read, or avail_in == 0; reads are
958 *    performed for at least two bytes (required for the zip translate_eol
959 *    option -- not supported here).
960 */
961local void fill_window(s)
962    deflate_state *s;
963{
964    register unsigned n, m;
965    register Posf *p;
966    unsigned more;    /* Amount of free space at the end of the window. */
967    uInt wsize = s->w_size;
968
969    do {
970        more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
971
972        /* Deal with !@#$% 64K limit: */
973        if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
974            more = wsize;
975
976        } else if (more == (unsigned)(-1)) {
977            /* Very unlikely, but possible on 16 bit machine if strstart == 0
978             * and lookahead == 1 (input done one byte at time)
979             */
980            more--;
981
982        /* If the window is almost full and there is insufficient lookahead,
983         * move the upper half to the lower one to make room in the upper half.
984         */
985        } else if (s->strstart >= wsize+MAX_DIST(s)) {
986
987            zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
988            s->match_start -= wsize;
989            s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
990            s->block_start -= (long) wsize;
991
992            /* Slide the hash table (could be avoided with 32 bit values
993               at the expense of memory usage). We slide even when level == 0
994               to keep the hash table consistent if we switch back to level > 0
995               later. (Using level 0 permanently is not an optimal usage of
996               zlib, so we don't care about this pathological case.)
997             */
998            n = s->hash_size;
999            p = &s->head[n];
1000            do {
1001                m = *--p;
1002                *p = (Pos)(m >= wsize ? m-wsize : NIL);
1003            } while (--n);
1004
1005            n = wsize;
1006#ifndef FASTEST
1007            p = &s->prev[n];
1008            do {
1009                m = *--p;
1010                *p = (Pos)(m >= wsize ? m-wsize : NIL);
1011                /* If n is not on any hash chain, prev[n] is garbage but
1012                 * its value will never be used.
1013                 */
1014            } while (--n);
1015#endif
1016            more += wsize;
1017        }
1018        if (s->strm->avail_in == 0) return;
1019
1020        /* If there was no sliding:
1021         *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1022         *    more == window_size - lookahead - strstart
1023         * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1024         * => more >= window_size - 2*WSIZE + 2
1025         * In the BIG_MEM or MMAP case (not yet supported),
1026         *   window_size == input_size + MIN_LOOKAHEAD  &&
1027         *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1028         * Otherwise, window_size == 2*WSIZE so more >= 2.
1029         * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1030         */
1031        Assert(more >= 2, "more < 2");
1032
1033        n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1034        s->lookahead += n;
1035
1036        /* Initialize the hash value now that we have some input: */
1037        if (s->lookahead >= MIN_MATCH) {
1038            s->ins_h = s->window[s->strstart];
1039            UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1040#if MIN_MATCH != 3
1041            Call UPDATE_HASH() MIN_MATCH-3 more times
1042#endif
1043        }
1044        /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1045         * but this is not important since only literal bytes will be emitted.
1046         */
1047
1048    } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1049}
1050
1051/* ===========================================================================
1052 * Flush the current block, with given end-of-file flag.
1053 * IN assertion: strstart is set to the end of the current match.
1054 */
1055#define FLUSH_BLOCK_ONLY(s, eof) { \
1056   _tr_flush_block(s, (s->block_start >= 0L ? \
1057                   (charf *)&s->window[(unsigned)s->block_start] : \
1058                   (charf *)Z_NULL), \
1059                (ulg)((long)s->strstart - s->block_start), \
1060                (eof)); \
1061   s->block_start = s->strstart; \
1062   flush_pending(s->strm); \
1063   Tracev((stderr,"[FLUSH]")); \
1064}
1065
1066/* Same but force premature exit if necessary. */
1067#define FLUSH_BLOCK(s, eof) { \
1068   FLUSH_BLOCK_ONLY(s, eof); \
1069   if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
1070}
1071
1072/* ===========================================================================
1073 * Copy without compression as much as possible from the input stream, return
1074 * the current block state.
1075 * This function does not insert new strings in the dictionary since
1076 * uncompressible data is probably not useful. This function is used
1077 * only for the level=0 compression option.
1078 * NOTE: this function should be optimized to avoid extra copying from
1079 * window to pending_buf.
1080 */
1081local block_state deflate_stored(s, flush)
1082    deflate_state *s;
1083    int flush;
1084{
1085    /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1086     * to pending_buf_size, and each stored block has a 5 byte header:
1087     */
1088    ulg max_block_size = 0xffff;
1089    ulg max_start;
1090
1091    if (max_block_size > s->pending_buf_size - 5) {
1092        max_block_size = s->pending_buf_size - 5;
1093    }
1094
1095    /* Copy as much as possible from input to output: */
1096    for (;;) {
1097        /* Fill the window as much as possible: */
1098        if (s->lookahead <= 1) {
1099
1100            Assert(s->strstart < s->w_size+MAX_DIST(s) ||
1101                   s->block_start >= (long)s->w_size, "slide too late");
1102
1103            fill_window(s);
1104            if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
1105
1106            if (s->lookahead == 0) break; /* flush the current block */
1107        }
1108        Assert(s->block_start >= 0L, "block gone");
1109
1110        s->strstart += s->lookahead;
1111        s->lookahead = 0;
1112
1113        /* Emit a stored block if pending_buf will be full: */
1114        max_start = s->block_start + max_block_size;
1115        if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
1116            /* strstart == 0 is possible when wraparound on 16-bit machine */
1117            s->lookahead = (uInt)(s->strstart - max_start);
1118            s->strstart = (uInt)max_start;
1119            FLUSH_BLOCK(s, 0);
1120        }
1121        /* Flush if we may have to slide, otherwise block_start may become
1122         * negative and the data will be gone:
1123         */
1124        if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
1125            FLUSH_BLOCK(s, 0);
1126        }
1127    }
1128    FLUSH_BLOCK(s, flush == Z_FINISH);
1129    return flush == Z_FINISH ? finish_done : block_done;
1130}
1131
1132/* ===========================================================================
1133 * Compress as much as possible from the input stream, return the current
1134 * block state.
1135 * This function does not perform lazy evaluation of matches and inserts
1136 * new strings in the dictionary only for unmatched strings or for short
1137 * matches. It is used only for the fast compression options.
1138 */
1139local block_state deflate_fast(s, flush)
1140    deflate_state *s;
1141    int flush;
1142{
1143    IPos hash_head = NIL; /* head of the hash chain */
1144    int bflush;           /* set if current block must be flushed */
1145
1146    for (;;) {
1147        /* Make sure that we always have enough lookahead, except
1148         * at the end of the input file. We need MAX_MATCH bytes
1149         * for the next match, plus MIN_MATCH bytes to insert the
1150         * string following the next match.
1151         */
1152        if (s->lookahead < MIN_LOOKAHEAD) {
1153            fill_window(s);
1154            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1155                return need_more;
1156            }
1157            if (s->lookahead == 0) break; /* flush the current block */
1158        }
1159
1160        /* Insert the string window[strstart .. strstart+2] in the
1161         * dictionary, and set hash_head to the head of the hash chain:
1162         */
1163        if (s->lookahead >= MIN_MATCH) {
1164            INSERT_STRING(s, s->strstart, hash_head);
1165        }
1166
1167        /* Find the longest match, discarding those <= prev_length.
1168         * At this point we have always match_length < MIN_MATCH
1169         */
1170        if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1171            /* To simplify the code, we prevent matches with the string
1172             * of window index 0 (in particular we have to avoid a match
1173             * of the string with itself at the start of the input file).
1174             */
1175            if (s->strategy != Z_HUFFMAN_ONLY) {
1176                s->match_length = longest_match (s, hash_head);
1177            }
1178            /* longest_match() sets match_start */
1179        }
1180        if (s->match_length >= MIN_MATCH) {
1181            check_match(s, s->strstart, s->match_start, s->match_length);
1182
1183            _tr_tally_dist(s, s->strstart - s->match_start,
1184                           s->match_length - MIN_MATCH, bflush);
1185
1186            s->lookahead -= s->match_length;
1187
1188            /* Insert new strings in the hash table only if the match length
1189             * is not too large. This saves time but degrades compression.
1190             */
1191#ifndef FASTEST
1192            if (s->match_length <= s->max_insert_length &&
1193                s->lookahead >= MIN_MATCH) {
1194                s->match_length--; /* string at strstart already in hash table */
1195                do {
1196                    s->strstart++;
1197                    INSERT_STRING(s, s->strstart, hash_head);
1198                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1199                     * always MIN_MATCH bytes ahead.
1200                     */
1201                } while (--s->match_length != 0);
1202                s->strstart++;
1203            } else
1204#endif
1205            {
1206                s->strstart += s->match_length;
1207                s->match_length = 0;
1208                s->ins_h = s->window[s->strstart];
1209                UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1210#if MIN_MATCH != 3
1211                Call UPDATE_HASH() MIN_MATCH-3 more times
1212#endif
1213                /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1214                 * matter since it will be recomputed at next deflate call.
1215                 */
1216            }
1217        } else {
1218            /* No match, output a literal byte */
1219            Tracevv((stderr,"%c", s->window[s->strstart]));
1220            _tr_tally_lit (s, s->window[s->strstart], bflush);
1221            s->lookahead--;
1222            s->strstart++;
1223        }
1224        if (bflush) FLUSH_BLOCK(s, 0);
1225    }
1226    FLUSH_BLOCK(s, flush == Z_FINISH);
1227    return flush == Z_FINISH ? finish_done : block_done;
1228}
1229
1230/* ===========================================================================
1231 * Same as above, but achieves better compression. We use a lazy
1232 * evaluation for matches: a match is finally adopted only if there is
1233 * no better match at the next window position.
1234 */
1235local block_state deflate_slow(s, flush)
1236    deflate_state *s;
1237    int flush;
1238{
1239    IPos hash_head = NIL;    /* head of hash chain */
1240    int bflush;              /* set if current block must be flushed */
1241
1242    /* Process the input block. */
1243    for (;;) {
1244        /* Make sure that we always have enough lookahead, except
1245         * at the end of the input file. We need MAX_MATCH bytes
1246         * for the next match, plus MIN_MATCH bytes to insert the
1247         * string following the next match.
1248         */
1249        if (s->lookahead < MIN_LOOKAHEAD) {
1250            fill_window(s);
1251            if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1252                return need_more;
1253            }
1254            if (s->lookahead == 0) break; /* flush the current block */
1255        }
1256
1257        /* Insert the string window[strstart .. strstart+2] in the
1258         * dictionary, and set hash_head to the head of the hash chain:
1259         */
1260        if (s->lookahead >= MIN_MATCH) {
1261            INSERT_STRING(s, s->strstart, hash_head);
1262        }
1263
1264        /* Find the longest match, discarding those <= prev_length.
1265         */
1266        s->prev_length = s->match_length, s->prev_match = s->match_start;
1267        s->match_length = MIN_MATCH-1;
1268
1269        if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1270            s->strstart - hash_head <= MAX_DIST(s)) {
1271            /* To simplify the code, we prevent matches with the string
1272             * of window index 0 (in particular we have to avoid a match
1273             * of the string with itself at the start of the input file).
1274             */
1275            if (s->strategy != Z_HUFFMAN_ONLY) {
1276                s->match_length = longest_match (s, hash_head);
1277            }
1278            /* longest_match() sets match_start */
1279
1280            if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
1281                 (s->match_length == MIN_MATCH &&
1282                  s->strstart - s->match_start > TOO_FAR))) {
1283
1284                /* If prev_match is also MIN_MATCH, match_start is garbage
1285                 * but we will ignore the current match anyway.
1286                 */
1287                s->match_length = MIN_MATCH-1;
1288            }
1289        }
1290        /* If there was a match at the previous step and the current
1291         * match is not better, output the previous match:
1292         */
1293        if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1294            uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1295            /* Do not insert strings in hash table beyond this. */
1296
1297            check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1298
1299            _tr_tally_dist(s, s->strstart -1 - s->prev_match,
1300                           s->prev_length - MIN_MATCH, bflush);
1301
1302            /* Insert in hash table all strings up to the end of the match.
1303             * strstart-1 and strstart are already inserted. If there is not
1304             * enough lookahead, the last two strings are not inserted in
1305             * the hash table.
1306             */
1307            s->lookahead -= s->prev_length-1;
1308            s->prev_length -= 2;
1309            do {
1310                if (++s->strstart <= max_insert) {
1311                    INSERT_STRING(s, s->strstart, hash_head);
1312                }
1313            } while (--s->prev_length != 0);
1314            s->match_available = 0;
1315            s->match_length = MIN_MATCH-1;
1316            s->strstart++;
1317
1318            if (bflush) FLUSH_BLOCK(s, 0);
1319
1320        } else if (s->match_available) {
1321            /* If there was no match at the previous position, output a
1322             * single literal. If there was a match but the current match
1323             * is longer, truncate the previous match to a single literal.
1324             */
1325            Tracevv((stderr,"%c", s->window[s->strstart-1]));
1326            _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1327            if (bflush) {
1328                FLUSH_BLOCK_ONLY(s, 0);
1329            }
1330            s->strstart++;
1331            s->lookahead--;
1332            if (s->strm->avail_out == 0) return need_more;
1333        } else {
1334            /* There is no previous match to compare with, wait for
1335             * the next step to decide.
1336             */
1337            s->match_available = 1;
1338            s->strstart++;
1339            s->lookahead--;
1340        }
1341    }
1342    Assert (flush != Z_NO_FLUSH, "no flush?");
1343    if (s->match_available) {
1344        Tracevv((stderr,"%c", s->window[s->strstart-1]));
1345        _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1346        s->match_available = 0;
1347    }
1348    FLUSH_BLOCK(s, flush == Z_FINISH);
1349    return flush == Z_FINISH ? finish_done : block_done;
1350}
Note: See TracBrowser for help on using the repository browser.