1 /* deflate.c -- compress data using the deflation algorithm

     2  * Copyright (C) 1995-2005 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 http://www.ietf.org/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$ */

    51 

    52 #include "deflate.h"

    53 

    54 const char deflate_copyright[] =

    55    " deflate 1.2.3 Copyright 1995-2005 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  */

    66 typedef 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 

    73 typedef block_state (*compress_func) OF((deflate_state *s, int flush));

    74 /* Compression function. Returns the block state after the call. */

    75 

    76 local void fill_window    OF((deflate_state *s));

    77 local block_state deflate_stored OF((deflate_state *s, int flush));

    78 local block_state deflate_fast   OF((deflate_state *s, int flush));

    79 #ifndef FASTEST

    80 local block_state deflate_slow   OF((deflate_state *s, int flush));

    81 #endif

    82 local void lm_init        OF((deflate_state *s));

    83 local void putShortMSB    OF((deflate_state *s, uInt b));

    84 local void flush_pending  OF((z_streamp strm));

    85 local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));

    86 #ifndef FASTEST

    87 #ifdef ASMV

    88       void match_init OF((void)); /* asm code initialization */

    89       uInt longest_match  OF((deflate_state *s, IPos cur_match));

    90 #else

    91 local uInt longest_match  OF((deflate_state *s, IPos cur_match));

    92 #endif

    93 #endif

    94 local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));

    95 

    96 #ifdef DEBUG

    97 local  void check_match OF((deflate_state *s, IPos start, IPos match,

    98                             int length));

    99 #endif

   100 

   101 /* ===========================================================================

   102  * Local data

   103  */

   104 

   105 #define NIL 0

   106 /* Tail of hash chains */

   107 

   108 #ifndef TOO_FAR

   109 #  define TOO_FAR 4096

   110 #endif

   111 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */

   112 

   113 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)

   114 /* Minimum amount of lookahead, except at the end of the input file.

   115  * See deflate.c for comments about the MIN_MATCH+1.

   116  */

   117 

   118 /* Values for max_lazy_match, good_match and max_chain_length, depending on

   119  * the desired pack level (0..9). The values given below have been tuned to

   120  * exclude worst case performance for pathological files. Better values may be

   121  * found for specific files.

   122  */

   123 typedef struct config_s {

   124    ush good_length; /* reduce lazy search above this match length */

   125    ush max_lazy;    /* do not perform lazy search above this match length */

   126    ush nice_length; /* quit search above this match length */

   127    ush max_chain;

   128    compress_func func;

   129 } config;

   130 

   131 #ifdef FASTEST

   132 local const config configuration_table[2] = {

   133 /*      good lazy nice chain */

   134 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */

   135 /* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */

   136 #else

   137 local const config configuration_table[10] = {

   138 /*      good lazy nice chain */

   139 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */

   140 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */

   141 /* 2 */ {4,    5, 16,    8, deflate_fast},

   142 /* 3 */ {4,    6, 32,   32, deflate_fast},

   143 

   144 /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */

   145 /* 5 */ {8,   16, 32,   32, deflate_slow},

   146 /* 6 */ {8,   16, 128, 128, deflate_slow},

   147 /* 7 */ {8,   32, 128, 256, deflate_slow},

   148 /* 8 */ {32, 128, 258, 1024, deflate_slow},

   149 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */

   150 #endif

   151 

   152 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4

   153  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different

   154  * meaning.

   155  */

   156 

   157 #define EQUAL 0

   158 /* result of memcmp for equal strings */

   159 

   160 #ifndef NO_DUMMY_DECL

   161 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */

   162 #endif

   163 

   164 /* ===========================================================================

   165  * Update a hash value with the given input byte

   166  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive

   167  *    input characters, so that a running hash key can be computed from the

   168  *    previous key instead of complete recalculation each time.

   169  */

   170 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)

   171 

   172 

   173 /* ===========================================================================

   174  * Insert string str in the dictionary and set match_head to the previous head

   175  * of the hash chain (the most recent string with same hash key). Return

   176  * the previous length of the hash chain.

   177  * If this file is compiled with -DFASTEST, the compression level is forced

   178  * to 1, and no hash chains are maintained.

   179  * IN  assertion: all calls to to INSERT_STRING are made with consecutive

   180  *    input characters and the first MIN_MATCH bytes of str are valid

   181  *    (except for the last MIN_MATCH-1 bytes of the input file).

   182  */

   183 #ifdef FASTEST

   184 #define INSERT_STRING(s, str, match_head) \

   185    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \

   186     match_head = s->head[s->ins_h], \

   187     s->head[s->ins_h] = (Pos)(str))

   188 #else

   189 #define INSERT_STRING(s, str, match_head) \

   190    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \

   191     match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \

   192     s->head[s->ins_h] = (Pos)(str))

   193 #endif

   194 

   195 /* ===========================================================================

   196  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).

   197  * prev[] will be initialized on the fly.

   198  */

   199 #define CLEAR_HASH(s) \

   200     s->head[s->hash_size-1] = NIL; \

   201     zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));

   202 

   203 /* ========================================================================= */

   204 int ZEXPORT deflateInit_(strm, level, version, stream_size)

   205     z_streamp strm;

   206     int level;

   207     const char *version;

   208     int stream_size;

   209 {

   210     return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,

   211                          Z_DEFAULT_STRATEGY, version, stream_size);

   212     /* To do: ignore strm->next_in if we use it as window */

   213 }

   214 

   215 /* ========================================================================= */

   216 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,

   217                   version, stream_size)

   218     z_streamp strm;

   219     int  level;

   220     int  method;

   221     int  windowBits;

   222     int  memLevel;

   223     int  strategy;

   224     const char *version;

   225     int stream_size;

   226 {

   227     deflate_state *s;

   228     int wrap = 1;

   229     static const char my_version[] = ZLIB_VERSION;

   230 

   231     ushf *overlay;

   232     /* We overlay pending_buf and d_buf+l_buf. This works since the average

   233      * output size for (length,distance) codes is <= 24 bits.

   234      */

   235 

   236     if (version == Z_NULL || version[0] != my_version[0] ||

   237         stream_size != sizeof(z_stream)) {

   238         return Z_VERSION_ERROR;

   239     }

   240     if (strm == Z_NULL) return Z_STREAM_ERROR;

   241 

   242     strm->msg = Z_NULL;

   243     if (strm->zalloc == (alloc_func)0) {

   244         strm->zalloc = zcalloc;

   245         strm->opaque = (voidpf)0;

   246     }

   247     if (strm->zfree == (free_func)0) strm->zfree = zcfree;

   248 

   249 #ifdef FASTEST

   250     if (level != 0) level = 1;

   251 #else

   252     if (level == Z_DEFAULT_COMPRESSION) level = 6;

   253 #endif

   254 

   255     if (windowBits < 0) { /* suppress zlib wrapper */

   256         wrap = 0;

   257         windowBits = -windowBits;

   258     }

   259 #ifdef GZIP

   260     else if (windowBits > 15) {

   261         wrap = 2;       /* write gzip wrapper instead */

   262         windowBits -= 16;

   263     }

   264 #endif

   265     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||

   266         windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||

   267         strategy < 0 || strategy > Z_FIXED) {

   268         return Z_STREAM_ERROR;

   269     }

   270     if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */

   271     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));

   272     if (s == Z_NULL) return Z_MEM_ERROR;

   273     strm->state = (struct internal_state FAR *)s;

   274     s->strm = strm;

   275 

   276     s->wrap = wrap;

   277     s->gzhead = Z_NULL;

   278     s->w_bits = windowBits;

   279     s->w_size = 1 << s->w_bits;

   280     s->w_mask = s->w_size - 1;

   281 

   282     s->hash_bits = memLevel + 7;

   283     s->hash_size = 1 << s->hash_bits;

   284     s->hash_mask = s->hash_size - 1;

   285     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);

   286 

   287     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));

   288     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));

   289     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));

   290 

   291     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */

   292 

   293     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);

   294     s->pending_buf = (uchf *) overlay;

   295     s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);

   296 

   297     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||

   298         s->pending_buf == Z_NULL) {

   299         s->status = FINISH_STATE;

   300         strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);

   301         deflateEnd (strm);

   302         return Z_MEM_ERROR;

   303     }

   304     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);

   305     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;

   306 

   307     s->level = level;

   308     s->strategy = strategy;

   309     s->method = (Byte)method;

   310 

   311     return deflateReset(strm);

   312 }

   313 

   314 /* ========================================================================= */

   315 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)

   316     z_streamp strm;

   317     const Bytef *dictionary;

   318     uInt  dictLength;

   319 {

   320     deflate_state *s;

   321     uInt length = dictLength;

   322     uInt n;

   323     IPos hash_head = 0;

   324 

   325     if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||

   326         strm->state->wrap == 2 ||

   327         (strm->state->wrap == 1 && strm->state->status != INIT_STATE))

   328         return Z_STREAM_ERROR;

   329 

   330     s = strm->state;

   331     if (s->wrap)

   332         strm->adler = adler32(strm->adler, dictionary, dictLength);

   333 

   334     if (length < MIN_MATCH) return Z_OK;

   335     if (length > MAX_DIST(s)) {

   336         length = MAX_DIST(s);

   337         dictionary += dictLength - length; /* use the tail of the dictionary */

   338     }

   339     zmemcpy(s->window, dictionary, length);

   340     s->strstart = length;

   341     s->block_start = (long)length;

   342 

   343     /* Insert all strings in the hash table (except for the last two bytes).

   344      * s->lookahead stays null, so s->ins_h will be recomputed at the next

   345      * call of fill_window.

   346      */

   347     s->ins_h = s->window[0];

   348     UPDATE_HASH(s, s->ins_h, s->window[1]);

   349     for (n = 0; n <= length - MIN_MATCH; n++) {

   350         INSERT_STRING(s, n, hash_head);

   351     }

   352     if (hash_head) hash_head = 0;  /* to make compiler happy */

   353     return Z_OK;

   354 }

   355 

   356 /* ========================================================================= */

   357 int ZEXPORT deflateReset (strm)

   358     z_streamp strm;

   359 {

   360     deflate_state *s;

   361 

   362     if (strm == Z_NULL || strm->state == Z_NULL ||

   363         strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {

   364         return Z_STREAM_ERROR;

   365     }

   366 

   367     strm->total_in = strm->total_out = 0;

   368     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */

   369     strm->data_type = Z_UNKNOWN;

   370 

   371     s = (deflate_state *)strm->state;

   372     s->pending = 0;

   373     s->pending_out = s->pending_buf;

   374 

   375     if (s->wrap < 0) {

   376         s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */

   377     }

   378     s->status = s->wrap ? INIT_STATE : BUSY_STATE;

   379     strm->adler =

   380 #ifdef GZIP

   381         s->wrap == 2 ? crc32(0L, Z_NULL, 0) :

   382 #endif

   383         adler32(0L, Z_NULL, 0);

   384     s->last_flush = Z_NO_FLUSH;

   385 

   386     _tr_init(s);

   387     lm_init(s);

   388 

   389     return Z_OK;

   390 }

   391 

   392 /* ========================================================================= */

   393 int ZEXPORT deflateSetHeader (strm, head)

   394     z_streamp strm;

   395     gz_headerp head;

   396 {

   397     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   398     if (strm->state->wrap != 2) return Z_STREAM_ERROR;

   399     strm->state->gzhead = head;

   400     return Z_OK;

   401 }

   402 

   403 /* ========================================================================= */

   404 int ZEXPORT deflatePrime (strm, bits, value)

   405     z_streamp strm;

   406     int bits;

   407     int value;

   408 {

   409     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   410     strm->state->bi_valid = bits;

   411     strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));

   412     return Z_OK;

   413 }

   414 

   415 /* ========================================================================= */

   416 int ZEXPORT deflateParams(strm, level, strategy)

   417     z_streamp strm;

   418     int level;

   419     int strategy;

   420 {

   421     deflate_state *s;

   422     compress_func func;

   423     int err = Z_OK;

   424 

   425     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   426     s = strm->state;

   427 

   428 #ifdef FASTEST

   429     if (level != 0) level = 1;

   430 #else

   431     if (level == Z_DEFAULT_COMPRESSION) level = 6;

   432 #endif

   433     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {

   434         return Z_STREAM_ERROR;

   435     }

   436     func = configuration_table[s->level].func;

   437 

   438     if (func != configuration_table[level].func && strm->total_in != 0) {

   439         /* Flush the last buffer: */

   440         err = deflate(strm, Z_PARTIAL_FLUSH);

   441     }

   442     if (s->level != level) {

   443         s->level = level;

   444         s->max_lazy_match   = configuration_table[level].max_lazy;

   445         s->good_match       = configuration_table[level].good_length;

   446         s->nice_match       = configuration_table[level].nice_length;

   447         s->max_chain_length = configuration_table[level].max_chain;

   448     }

   449     s->strategy = strategy;

   450     return err;

   451 }

   452 

   453 /* ========================================================================= */

   454 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)

   455     z_streamp strm;

   456     int good_length;

   457     int max_lazy;

   458     int nice_length;

   459     int max_chain;

   460 {

   461     deflate_state *s;

   462 

   463     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   464     s = strm->state;

   465     s->good_match = good_length;

   466     s->max_lazy_match = max_lazy;

   467     s->nice_match = nice_length;

   468     s->max_chain_length = max_chain;

   469     return Z_OK;

   470 }

   471 

   472 /* =========================================================================

   473  * For the default windowBits of 15 and memLevel of 8, this function returns

   474  * a close to exact, as well as small, upper bound on the compressed size.

   475  * They are coded as constants here for a reason--if the #define's are

   476  * changed, then this function needs to be changed as well.  The return

   477  * value for 15 and 8 only works for those exact settings.

   478  *

   479  * For any setting other than those defaults for windowBits and memLevel,

   480  * the value returned is a conservative worst case for the maximum expansion

   481  * resulting from using fixed blocks instead of stored blocks, which deflate

   482  * can emit on compressed data for some combinations of the parameters.

   483  *

   484  * This function could be more sophisticated to provide closer upper bounds

   485  * for every combination of windowBits and memLevel, as well as wrap.

   486  * But even the conservative upper bound of about 14% expansion does not

   487  * seem onerous for output buffer allocation.

   488  */

   489 uLong ZEXPORT deflateBound(strm, sourceLen)

   490     z_streamp strm;

   491     uLong sourceLen;

   492 {

   493     deflate_state *s;

   494     uLong destLen;

   495 

   496     /* conservative upper bound */

   497     destLen = sourceLen +

   498               ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11;

   499 

   500     /* if can't get parameters, return conservative bound */

   501     if (strm == Z_NULL || strm->state == Z_NULL)

   502         return destLen;

   503 

   504     /* if not default parameters, return conservative bound */

   505     s = strm->state;

   506     if (s->w_bits != 15 || s->hash_bits != 8 + 7)

   507         return destLen;

   508 

   509     /* default settings: return tight bound for that case */

   510     return compressBound(sourceLen);

   511 }

   512 

   513 /* =========================================================================

   514  * Put a short in the pending buffer. The 16-bit value is put in MSB order.

   515  * IN assertion: the stream state is correct and there is enough room in

   516  * pending_buf.

   517  */

   518 local void putShortMSB (s, b)

   519     deflate_state *s;

   520     uInt b;

   521 {

   522     put_byte(s, (Byte)(b >> 8));

   523     put_byte(s, (Byte)(b & 0xff));

   524 }

   525 

   526 /* =========================================================================

   527  * Flush as much pending output as possible. All deflate() output goes

   528  * through this function so some applications may wish to modify it

   529  * to avoid allocating a large strm->next_out buffer and copying into it.

   530  * (See also read_buf()).

   531  */

   532 local void flush_pending(strm)

   533     z_streamp strm;

   534 {

   535     unsigned len = strm->state->pending;

   536 

   537     if (len > strm->avail_out) len = strm->avail_out;

   538     if (len == 0) return;

   539 

   540     zmemcpy(strm->next_out, strm->state->pending_out, len);

   541     strm->next_out  += len;

   542     strm->state->pending_out  += len;

   543     strm->total_out += len;

   544     strm->avail_out  -= len;

   545     strm->state->pending -= len;

   546     if (strm->state->pending == 0) {

   547         strm->state->pending_out = strm->state->pending_buf;

   548     }

   549 }

   550 

   551 /* ========================================================================= */

   552 int ZEXPORT deflate (strm, flush)

   553     z_streamp strm;

   554     int flush;

   555 {

   556     int old_flush; /* value of flush param for previous deflate call */

   557     deflate_state *s;

   558 

   559     if (strm == Z_NULL || strm->state == Z_NULL ||

   560         flush > Z_FINISH || flush < 0) {

   561         return Z_STREAM_ERROR;

   562     }

   563     s = strm->state;

   564 

   565     if (strm->next_out == Z_NULL ||

   566         (strm->next_in == Z_NULL && strm->avail_in != 0) ||

   567         (s->status == FINISH_STATE && flush != Z_FINISH)) {

   568         ERR_RETURN(strm, Z_STREAM_ERROR);

   569     }

   570     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

   571 

   572     s->strm = strm; /* just in case */

   573     old_flush = s->last_flush;

   574     s->last_flush = flush;

   575 

   576     /* Write the header */

   577     if (s->status == INIT_STATE) {

   578 #ifdef GZIP

   579         if (s->wrap == 2) {

   580             strm->adler = crc32(0L, Z_NULL, 0);

   581             put_byte(s, 31);

   582             put_byte(s, 139);

   583             put_byte(s, 8);

   584             if (s->gzhead == NULL) {

   585                 put_byte(s, 0);

   586                 put_byte(s, 0);

   587                 put_byte(s, 0);

   588                 put_byte(s, 0);

   589                 put_byte(s, 0);

   590                 put_byte(s, s->level == 9 ? 2 :

   591                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?

   592                              4 : 0));

   593                 put_byte(s, OS_CODE);

   594                 s->status = BUSY_STATE;

   595             }

   596             else {

   597                 put_byte(s, (s->gzhead->text ? 1 : 0) +

   598                             (s->gzhead->hcrc ? 2 : 0) +

   599                             (s->gzhead->extra == Z_NULL ? 0 : 4) +

   600                             (s->gzhead->name == Z_NULL ? 0 : 8) +

   601                             (s->gzhead->comment == Z_NULL ? 0 : 16)

   602                         );

   603                 put_byte(s, (Byte)(s->gzhead->time & 0xff));

   604                 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));

   605                 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));

   606                 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));

   607                 put_byte(s, s->level == 9 ? 2 :

   608                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?

   609                              4 : 0));

   610                 put_byte(s, s->gzhead->os & 0xff);

   611                 if (s->gzhead->extra != NULL) {

   612                     put_byte(s, s->gzhead->extra_len & 0xff);

   613                     put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);

   614                 }

   615                 if (s->gzhead->hcrc)

   616                     strm->adler = crc32(strm->adler, s->pending_buf,

   617                                         s->pending);

   618                 s->gzindex = 0;

   619                 s->status = EXTRA_STATE;

   620             }

   621         }

   622         else

   623 #endif

   624         {

   625             uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;

   626             uInt level_flags;

   627 

   628             if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)

   629                 level_flags = 0;

   630             else if (s->level < 6)

   631                 level_flags = 1;

   632             else if (s->level == 6)

   633                 level_flags = 2;

   634             else

   635                 level_flags = 3;

   636             header |= (level_flags << 6);

   637             if (s->strstart != 0) header |= PRESET_DICT;

   638             header += 31 - (header % 31);

   639 

   640             s->status = BUSY_STATE;

   641             putShortMSB(s, header);

   642 

   643             /* Save the adler32 of the preset dictionary: */

   644             if (s->strstart != 0) {

   645                 putShortMSB(s, (uInt)(strm->adler >> 16));

   646                 putShortMSB(s, (uInt)(strm->adler & 0xffff));

   647             }

   648             strm->adler = adler32(0L, Z_NULL, 0);

   649         }

   650     }

   651 #ifdef GZIP

   652     if (s->status == EXTRA_STATE) {

   653         if (s->gzhead->extra != NULL) {

   654             uInt beg = s->pending;  /* start of bytes to update crc */

   655 

   656             while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {

   657                 if (s->pending == s->pending_buf_size) {

   658                     if (s->gzhead->hcrc && s->pending > beg)

   659                         strm->adler = crc32(strm->adler, s->pending_buf + beg,

   660                                             s->pending - beg);

   661                     flush_pending(strm);

   662                     beg = s->pending;

   663                     if (s->pending == s->pending_buf_size)

   664                         break;

   665                 }

   666                 put_byte(s, s->gzhead->extra[s->gzindex]);

   667                 s->gzindex++;

   668             }

   669             if (s->gzhead->hcrc && s->pending > beg)

   670                 strm->adler = crc32(strm->adler, s->pending_buf + beg,

   671                                     s->pending - beg);

   672             if (s->gzindex == s->gzhead->extra_len) {

   673                 s->gzindex = 0;

   674                 s->status = NAME_STATE;

   675             }

   676         }

   677         else

   678             s->status = NAME_STATE;

   679     }

   680     if (s->status == NAME_STATE) {

   681         if (s->gzhead->name != NULL) {

   682             uInt beg = s->pending;  /* start of bytes to update crc */

   683             int val;

   684 

   685             do {

   686                 if (s->pending == s->pending_buf_size) {

   687                     if (s->gzhead->hcrc && s->pending > beg)

   688                         strm->adler = crc32(strm->adler, s->pending_buf + beg,

   689                                             s->pending - beg);

   690                     flush_pending(strm);

   691                     beg = s->pending;

   692                     if (s->pending == s->pending_buf_size) {

   693                         val = 1;

   694                         break;

   695                     }

   696                 }

   697                 val = s->gzhead->name[s->gzindex++];

   698                 put_byte(s, val);

   699             } while (val != 0);

   700             if (s->gzhead->hcrc && s->pending > beg)

   701                 strm->adler = crc32(strm->adler, s->pending_buf + beg,

   702                                     s->pending - beg);

   703             if (val == 0) {

   704                 s->gzindex = 0;

   705                 s->status = COMMENT_STATE;

   706             }

   707         }

   708         else

   709             s->status = COMMENT_STATE;

   710     }

   711     if (s->status == COMMENT_STATE) {

   712         if (s->gzhead->comment != NULL) {

   713             uInt beg = s->pending;  /* start of bytes to update crc */

   714             int val;

   715 

   716             do {

   717                 if (s->pending == s->pending_buf_size) {

   718                     if (s->gzhead->hcrc && s->pending > beg)

   719                         strm->adler = crc32(strm->adler, s->pending_buf + beg,

   720                                             s->pending - beg);

   721                     flush_pending(strm);

   722                     beg = s->pending;

   723                     if (s->pending == s->pending_buf_size) {

   724                         val = 1;

   725                         break;

   726                     }

   727                 }

   728                 val = s->gzhead->comment[s->gzindex++];

   729                 put_byte(s, val);

   730             } while (val != 0);

   731             if (s->gzhead->hcrc && s->pending > beg)

   732                 strm->adler = crc32(strm->adler, s->pending_buf + beg,

   733                                     s->pending - beg);

   734             if (val == 0)

   735                 s->status = HCRC_STATE;

   736         }

   737         else

   738             s->status = HCRC_STATE;

   739     }

   740     if (s->status == HCRC_STATE) {

   741         if (s->gzhead->hcrc) {

   742             if (s->pending + 2 > s->pending_buf_size)

   743                 flush_pending(strm);

   744             if (s->pending + 2 <= s->pending_buf_size) {

   745                 put_byte(s, (Byte)(strm->adler & 0xff));

   746                 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));

   747                 strm->adler = crc32(0L, Z_NULL, 0);

   748                 s->status = BUSY_STATE;

   749             }

   750         }

   751         else

   752             s->status = BUSY_STATE;

   753     }

   754 #endif

   755 

   756     /* Flush as much pending output as possible */

   757     if (s->pending != 0) {

   758         flush_pending(strm);

   759         if (strm->avail_out == 0) {

   760             /* Since avail_out is 0, deflate will be called again with

   761              * more output space, but possibly with both pending and

   762              * avail_in equal to zero. There won't be anything to do,

   763              * but this is not an error situation so make sure we

   764              * return OK instead of BUF_ERROR at next call of deflate:

   765              */

   766             s->last_flush = -1;

   767             return Z_OK;

   768         }

   769 

   770     /* Make sure there is something to do and avoid duplicate consecutive

   771      * flushes. For repeated and useless calls with Z_FINISH, we keep

   772      * returning Z_STREAM_END instead of Z_BUF_ERROR.

   773      */

   774     } else if (strm->avail_in == 0 && flush <= old_flush &&

   775                flush != Z_FINISH) {

   776         ERR_RETURN(strm, Z_BUF_ERROR);

   777     }

   778 

   779     /* User must not provide more input after the first FINISH: */

   780     if (s->status == FINISH_STATE && strm->avail_in != 0) {

   781         ERR_RETURN(strm, Z_BUF_ERROR);

   782     }

   783 

   784     /* Start a new block or continue the current one.

   785      */

   786     if (strm->avail_in != 0 || s->lookahead != 0 ||

   787         (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {

   788         block_state bstate;

   789 

   790         bstate = (*(configuration_table[s->level].func))(s, flush);

   791 

   792         if (bstate == finish_started || bstate == finish_done) {

   793             s->status = FINISH_STATE;

   794         }

   795         if (bstate == need_more || bstate == finish_started) {

   796             if (strm->avail_out == 0) {

   797                 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */

   798             }

   799             return Z_OK;

   800             /* If flush != Z_NO_FLUSH && avail_out == 0, the next call

   801              * of deflate should use the same flush parameter to make sure

   802              * that the flush is complete. So we don't have to output an

   803              * empty block here, this will be done at next call. This also

   804              * ensures that for a very small output buffer, we emit at most

   805              * one empty block.

   806              */

   807         }

   808         if (bstate == block_done) {

   809             if (flush == Z_PARTIAL_FLUSH) {

   810                 _tr_align(s);

   811             } else { /* FULL_FLUSH or SYNC_FLUSH */

   812                 _tr_stored_block(s, (char*)0, 0L, 0);

   813                 /* For a full flush, this empty block will be recognized

   814                  * as a special marker by inflate_sync().

   815                  */

   816                 if (flush == Z_FULL_FLUSH) {

   817                     CLEAR_HASH(s);             /* forget history */

   818                 }

   819             }

   820             flush_pending(strm);

   821             if (strm->avail_out == 0) {

   822               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */

   823               return Z_OK;

   824             }

   825         }

   826     }

   827     Assert(strm->avail_out > 0, "bug2");

   828 

   829     if (flush != Z_FINISH) return Z_OK;

   830     if (s->wrap <= 0) return Z_STREAM_END;

   831 

   832     /* Write the trailer */

   833 #ifdef GZIP

   834     if (s->wrap == 2) {

   835         put_byte(s, (Byte)(strm->adler & 0xff));

   836         put_byte(s, (Byte)((strm->adler >> 8) & 0xff));

   837         put_byte(s, (Byte)((strm->adler >> 16) & 0xff));

   838         put_byte(s, (Byte)((strm->adler >> 24) & 0xff));

   839         put_byte(s, (Byte)(strm->total_in & 0xff));

   840         put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));

   841         put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));

   842         put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));

   843     }

   844     else

   845 #endif

   846     {

   847         putShortMSB(s, (uInt)(strm->adler >> 16));

   848         putShortMSB(s, (uInt)(strm->adler & 0xffff));

   849     }

   850     flush_pending(strm);

   851     /* If avail_out is zero, the application will call deflate again

   852      * to flush the rest.

   853      */

   854     if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */

   855     return s->pending != 0 ? Z_OK : Z_STREAM_END;

   856 }

   857 

   858 /* ========================================================================= */

   859 int ZEXPORT deflateEnd (strm)

   860     z_streamp strm;

   861 {

   862     int status;

   863 

   864     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;

   865 

   866     status = strm->state->status;

   867     if (status != INIT_STATE &&

   868         status != EXTRA_STATE &&

   869         status != NAME_STATE &&

   870         status != COMMENT_STATE &&

   871         status != HCRC_STATE &&

   872         status != BUSY_STATE &&

   873         status != FINISH_STATE) {

   874       return Z_STREAM_ERROR;

   875     }

   876 

   877     /* Deallocate in reverse order of allocations: */

   878     TRY_FREE(strm, strm->state->pending_buf);

   879     TRY_FREE(strm, strm->state->head);

   880     TRY_FREE(strm, strm->state->prev);

   881     TRY_FREE(strm, strm->state->window);

   882 

   883     ZFREE(strm, strm->state);

   884     strm->state = Z_NULL;

   885 

   886     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;

   887 }

   888 

   889 /* =========================================================================

   890  * Copy the source state to the destination state.

   891  * To simplify the source, this is not supported for 16-bit MSDOS (which

   892  * doesn't have enough memory anyway to duplicate compression states).

   893  */

   894 int ZEXPORT deflateCopy (dest, source)

   895     z_streamp dest;

   896     z_streamp source;

   897 {

   898 #ifdef MAXSEG_64K

   899     return Z_STREAM_ERROR;

   900 #else

   901     deflate_state *ds;

   902     deflate_state *ss;

   903     ushf *overlay;

   904 

   905 

   906     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {

   907         return Z_STREAM_ERROR;

   908     }

   909 

   910     ss = source->state;

   911 

   912     zmemcpy(dest, source, sizeof(z_stream));

   913 

   914     ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));

   915     if (ds == Z_NULL) return Z_MEM_ERROR;

   916     dest->state = (struct internal_state FAR *) ds;

   917     zmemcpy(ds, ss, sizeof(deflate_state));

   918     ds->strm = dest;

   919 

   920     ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));

   921     ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));

   922     ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));

   923     overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);

   924     ds->pending_buf = (uchf *) overlay;

   925 

   926     if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||

   927         ds->pending_buf == Z_NULL) {

   928         deflateEnd (dest);

   929         return Z_MEM_ERROR;

   930     }

   931     /* following zmemcpy do not work for 16-bit MSDOS */

   932     zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));

   933     zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));

   934     zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));

   935     zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);

   936 

   937     ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);

   938     ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);

   939     ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;

   940 

   941     ds->l_desc.dyn_tree = ds->dyn_ltree;

   942     ds->d_desc.dyn_tree = ds->dyn_dtree;

   943     ds->bl_desc.dyn_tree = ds->bl_tree;

   944 

   945     return Z_OK;

   946 #endif /* MAXSEG_64K */

   947 }

   948 

   949 /* ===========================================================================

   950  * Read a new buffer from the current input stream, update the adler32

   951  * and total number of bytes read.  All deflate() input goes through

   952  * this function so some applications may wish to modify it to avoid

   953  * allocating a large strm->next_in buffer and copying from it.

   954  * (See also flush_pending()).

   955  */

   956 local int read_buf(strm, buf, size)

   957     z_streamp strm;

   958     Bytef *buf;

   959     unsigned size;

   960 {

   961     unsigned len = strm->avail_in;

   962 

   963     if (len > size) len = size;

   964     if (len == 0) return 0;

   965 

   966     strm->avail_in  -= len;

   967 

   968     if (strm->state->wrap == 1) {

   969         strm->adler = adler32(strm->adler, strm->next_in, len);

   970     }

   971 #ifdef GZIP

   972     else if (strm->state->wrap == 2) {

   973         strm->adler = crc32(strm->adler, strm->next_in, len);

   974     }

   975 #endif

   976     zmemcpy(buf, strm->next_in, len);

   977     strm->next_in  += len;

   978     strm->total_in += len;

   979 

   980     return (int)len;

   981 }

   982 

   983 /* ===========================================================================

   984  * Initialize the "longest match" routines for a new zlib stream

   985  */

   986 local void lm_init (s)

   987     deflate_state *s;

   988 {

   989     s->window_size = (ulg)2L*s->w_size;

   990 

   991     CLEAR_HASH(s);

   992 

   993     /* Set the default configuration parameters:

   994      */

   995     s->max_lazy_match   = configuration_table[s->level].max_lazy;

   996     s->good_match       = configuration_table[s->level].good_length;

   997     s->nice_match       = configuration_table[s->level].nice_length;

   998     s->max_chain_length = configuration_table[s->level].max_chain;

   999 

  1000     s->strstart = 0;

  1001     s->block_start = 0L;

  1002     s->lookahead = 0;

  1003     s->match_length = s->prev_length = MIN_MATCH-1;

  1004     s->match_available = 0;

  1005     s->ins_h = 0;

  1006 #ifndef FASTEST

  1007 #ifdef ASMV

  1008     match_init(); /* initialize the asm code */

  1009 #endif

  1010 #endif

  1011 }

  1012 

  1013 #ifndef FASTEST

  1014 /* ===========================================================================

  1015  * Set match_start to the longest match starting at the given string and

  1016  * return its length. Matches shorter or equal to prev_length are discarded,

  1017  * in which case the result is equal to prev_length and match_start is

  1018  * garbage.

  1019  * IN assertions: cur_match is the head of the hash chain for the current

  1020  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1

  1021  * OUT assertion: the match length is not greater than s->lookahead.

  1022  */

  1023 #ifndef ASMV

  1024 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or

  1025  * match.S. The code will be functionally equivalent.

  1026  */

  1027 local uInt longest_match(s, cur_match)

  1028     deflate_state *s;

  1029     IPos cur_match;                             /* current match */

  1030 {

  1031     unsigned chain_length = s->max_chain_length;/* max hash chain length */

  1032     register Bytef *scan = s->window + s->strstart; /* current string */

  1033     register Bytef *match;                       /* matched string */

  1034     register int len;                           /* length of current match */

  1035     int best_len = s->prev_length;              /* best match length so far */

  1036     int nice_match = s->nice_match;             /* stop if match long enough */

  1037     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?

  1038         s->strstart - (IPos)MAX_DIST(s) : NIL;

  1039     /* Stop when cur_match becomes <= limit. To simplify the code,

  1040      * we prevent matches with the string of window index 0.

  1041      */

  1042     Posf *prev = s->prev;

  1043     uInt wmask = s->w_mask;

  1044 

  1045 #ifdef UNALIGNED_OK

  1046     /* Compare two bytes at a time. Note: this is not always beneficial.

  1047      * Try with and without -DUNALIGNED_OK to check.

  1048      */

  1049     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;

  1050     register ush scan_start = *(ushf*)scan;

  1051     register ush scan_end   = *(ushf*)(scan+best_len-1);

  1052 #else

  1053     register Bytef *strend = s->window + s->strstart + MAX_MATCH;

  1054     register Byte scan_end1  = scan[best_len-1];

  1055     register Byte scan_end   = scan[best_len];

  1056 #endif

  1057 

  1058     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.

  1059      * It is easy to get rid of this optimization if necessary.

  1060      */

  1061     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");

  1062 

  1063     /* Do not waste too much time if we already have a good match: */

  1064     if (s->prev_length >= s->good_match) {

  1065         chain_length >>= 2;

  1066     }

  1067     /* Do not look for matches beyond the end of the input. This is necessary

  1068      * to make deflate deterministic.

  1069      */

  1070     if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;

  1071 

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

  1073 

  1074     do {

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

  1076         match = s->window + cur_match;

  1077 

  1078         /* Skip to next match if the match length cannot increase

  1079          * or if the match length is less than 2.  Note that the checks below

  1080          * for insufficient lookahead only occur occasionally for performance

  1081          * reasons.  Therefore uninitialized memory will be accessed, and

  1082          * conditional jumps will be made that depend on those values.

  1083          * However the length of the match is limited to the lookahead, so

  1084          * the output of deflate is not affected by the uninitialized values.

  1085          */

  1086 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)

  1087         /* This code assumes sizeof(unsigned short) == 2. Do not use

  1088          * UNALIGNED_OK if your compiler uses a different size.

  1089          */

  1090         if (*(ushf*)(match+best_len-1) != scan_end ||

  1091             *(ushf*)match != scan_start) continue;

  1092 

  1093         /* It is not necessary to compare scan[2] and match[2] since they are

  1094          * always equal when the other bytes match, given that the hash keys

  1095          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at

  1096          * strstart+3, +5, ... up to strstart+257. We check for insufficient

  1097          * lookahead only every 4th comparison; the 128th check will be made

  1098          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is

  1099          * necessary to put more guard bytes at the end of the window, or

  1100          * to check more often for insufficient lookahead.

  1101          */

  1102         Assert(scan[2] == match[2], "scan[2]?");

  1103         scan++, match++;

  1104         do {

  1105         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&

  1106                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&

  1107                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&

  1108                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&

  1109                  scan < strend);

  1110         /* The funny "do {}" generates better code on most compilers */

  1111 

  1112         /* Here, scan <= window+strstart+257 */

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

  1114         if (*scan == *match) scan++;

  1115 

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

  1117         scan = strend - (MAX_MATCH-1);

  1118 

  1119 #else /* UNALIGNED_OK */

  1120 

  1121         if (match[best_len]   != scan_end  ||

  1122             match[best_len-1] != scan_end1 ||

  1123             *match            != *scan     ||

  1124             *++match          != scan[1])      continue;

  1125 

  1126         /* The check at best_len-1 can be removed because it will be made

  1127          * again later. (This heuristic is not always a win.)

  1128          * It is not necessary to compare scan[2] and match[2] since they

  1129          * are always equal when the other bytes match, given that

  1130          * the hash keys are equal and that HASH_BITS >= 8.

  1131          */

  1132         scan += 2, match++;

  1133         Assert(*scan == *match, "match[2]?");

  1134 

  1135         /* We check for insufficient lookahead only every 8th comparison;