1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

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

    26  * Copyright (C) 1995-2005 Jean-loup Gailly.

    27  * For conditions of distribution and use, see copyright notice in zlib.h

    28  */

    29 

    30 /*

    31  *  ALGORITHM

    32  *

    33  *      The "deflation" process depends on being able to identify portions

    34  *      of the input text which are identical to earlier input (within a

    35  *      sliding window trailing behind the input currently being processed).

    36  *

    37  *      The most straightforward technique turns out to be the fastest for

    38  *      most input files: try all possible matches and select the longest.

    39  *      The key feature of this algorithm is that insertions into the string

    40  *      dictionary are very simple and thus fast, and deletions are avoided

    41  *      completely. Insertions are performed at each input character, whereas

    42  *      string matches are performed only when the previous match ends. So it

    43  *      is preferable to spend more time in matches to allow very fast string

    44  *      insertions and avoid deletions. The matching algorithm for small

    45  *      strings is inspired from that of Rabin & Karp. A brute force approach

    46  *      is used to find longer strings when a small match has been found.

    47  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze

    48  *      (by Leonid Broukhis).

    49  *         A previous version of this file used a more sophisticated algorithm

    50  *      (by Fiala and Greene) which is guaranteed to run in linear amortized

    51  *      time, but has a larger average cost, uses more memory and is patented.

    52  *      However the F&G algorithm may be faster for some highly redundant

    53  *      files if the parameter max_chain_length (described below) is too large.

    54  *

    55  *  ACKNOWLEDGEMENTS

    56  *

    57  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and

    58  *      I found it in 'freeze' written by Leonid Broukhis.

    59  *      Thanks to many people for bug reports and testing.

    60  *

    61  *  REFERENCES

    62  *

    63  *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".

    64  *      Available in http://www.ietf.org/rfc/rfc1951.txt

    65  *

    66  *      A description of the Rabin and Karp algorithm is given in the book

    67  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.

    68  *

    69  *      Fiala,E.R., and Greene,D.H.

    70  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595

    71  *

    72  */

    73 

    74 /* @(#) $Id$ */

    75 

    76 #include "deflate.h"

    77 

    78 const char deflate_copyright[] =

    79    " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";

    80 /*

    81   If you use the zlib library in a product, an acknowledgment is welcome

    82   in the documentation of your product. If for some reason you cannot

    83   include such an acknowledgment, I would appreciate that you keep this

    84   copyright string in the executable of your product.

    85  */

    86 

    87 /* ===========================================================================

    88  *  Function prototypes.

    89  */

    90 typedef enum {

    91     need_more,      /* block not completed, need more input or more output */

    92     block_done,     /* block flush performed */

    93     finish_started, /* finish started, need only more output at next deflate */

    94     finish_done     /* finish done, accept no more input or output */

    95 } block_state;

    96 

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

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

    99 

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

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

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

   103 #ifndef FASTEST

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

   105 #endif

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

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

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

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

   110 #ifndef FASTEST

   111 #ifdef ASMV

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

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

   114 #else

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

   116 #endif

   117 #endif

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

   119 

   120 #ifdef DEBUG

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

   122                             int length));

   123 #endif

   124 

   125 /* ===========================================================================

   126  * Local data

   127  */

   128 

   129 #define NIL 0

   130 /* Tail of hash chains */

   131 

   132 #ifndef TOO_FAR

   133 #  define TOO_FAR 4096

   134 #endif

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

   136 

   137 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)

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

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

   140  */

   141 

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

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

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

   145  * found for specific files.

   146  */

   147 typedef struct config_s {

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

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

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

   151    ush max_chain;

   152    compress_func func;

   153 } config;

   154 

   155 #ifdef FASTEST

   156 local const config configuration_table[2] = {

   157 /*      good lazy nice chain */

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

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

   160 #else

   161 local const config configuration_table[10] = {

   162 /*      good lazy nice chain */

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

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

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

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

   167 

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

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

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

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

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

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

   174 #endif

   175 

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

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

   178  * meaning.

   179  */

   180 

   181 #define EQUAL 0

   182 /* result of memcmp for equal strings */

   183 

   184 #ifndef NO_DUMMY_DECL

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

   186 #endif

   187 

   188 /* ===========================================================================

   189  * Update a hash value with the given input byte

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

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

   192  *    previous key instead of complete recalculation each time.

   193  */

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

   195 

   196 

   197 /* ===========================================================================

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

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

   200  * the previous length of the hash chain.

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

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

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

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

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

   206  */

   207 #ifdef FASTEST

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

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

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

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

   212 #else

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

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

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

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

   217 #endif

   218 

   219 /* ===========================================================================

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

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

   222  */

   223 #define CLEAR_HASH(s) \

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

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

   226 

   227 /* ========================================================================= */

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

   229     z_streamp strm;

   230     int level;

   231     const char *version;

   232     int stream_size;

   233 {

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

   235                          Z_DEFAULT_STRATEGY, version, stream_size);

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

   237 }

   238 

   239 /* ========================================================================= */

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

   241                   version, stream_size)

   242     z_streamp strm;

   243     int  level;

   244     int  method;

   245     int  windowBits;

   246     int  memLevel;

   247     int  strategy;

   248     const char *version;

   249     int stream_size;

   250 {

   251     deflate_state *s;

   252     int wrap = 1;

   253     static const char my_version[] = ZLIB_VERSION;

   254 

   255     ushf *overlay;

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

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

   258      */

   259 

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

   261         stream_size != sizeof(z_stream)) {

   262         return Z_VERSION_ERROR;

   263     }

   264     if (strm == Z_NULL) return Z_STREAM_ERROR;

   265 

   266     strm->msg = Z_NULL;

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

   268         strm->zalloc = zcalloc;

   269         strm->opaque = (voidpf)0;

   270     }

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

   272 

   273 #ifdef FASTEST

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

   275 #else

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

   277 #endif

   278 

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

   280         wrap = 0;

   281         windowBits = -windowBits;

   282     }

   283 #ifdef GZIP

   284     else if (windowBits > 15) {

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

   286         windowBits -= 16;

   287     }

   288 #endif

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

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

   291         strategy < 0 || strategy > Z_FIXED) {

   292         return Z_STREAM_ERROR;

   293     }

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

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

   296     if (s == Z_NULL) return Z_MEM_ERROR;

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

   298     s->strm = strm;

   299 

   300     s->wrap = wrap;

   301     s->gzhead = Z_NULL;

   302     s->w_bits = windowBits;

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

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

   305 

   306     s->hash_bits = memLevel + 7;

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

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

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

   310 

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

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

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

   314 

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

   316 

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

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

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

   320 

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

   322         s->pending_buf == Z_NULL) {

   323         s->status = FINISH_STATE;

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

   325         deflateEnd (strm);

   326         return Z_MEM_ERROR;

   327     }

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

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

   330 

   331     s->level = level;

   332     s->strategy = strategy;

   333     s->method = (Byte)method;

   334 

   335     return deflateReset(strm);

   336 }

   337 

   338 /* ========================================================================= */

   339 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)

   340     z_streamp strm;

   341     const Bytef *dictionary;

   342     uInt  dictLength;

   343 {

   344     deflate_state *s;

   345     uInt length = dictLength;

   346     uInt n;

   347     IPos hash_head = 0;

   348 

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

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

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

   352         return Z_STREAM_ERROR;

   353 

   354     s = strm->state;

   355     if (s->wrap)

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

   357 

   358     if (length < MIN_MATCH) return Z_OK;

   359     if (length > MAX_DIST(s)) {

   360         length = MAX_DIST(s);

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

   362     }

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

   364     s->strstart = length;

   365     s->block_start = (long)length;

   366 

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

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

   369      * call of fill_window.

   370      */

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

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

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

   374         INSERT_STRING(s, n, hash_head);

   375     }

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

   377     return Z_OK;

   378 }

   379 

   380 /* ========================================================================= */

   381 int ZEXPORT deflateReset (strm)

   382     z_streamp strm;

   383 {

   384     deflate_state *s;

   385 

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

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

   388         return Z_STREAM_ERROR;

   389     }

   390 

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

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

   393     strm->data_type = Z_UNKNOWN;

   394 

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

   396     s->pending = 0;

   397     s->pending_out = s->pending_buf;

   398 

   399     if (s->wrap < 0) {

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

   401     }

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

   403     strm->adler =

   404 #ifdef GZIP

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

   406 #endif

   407         adler32(0L, Z_NULL, 0);

   408     s->last_flush = Z_NO_FLUSH;

   409 

   410     _tr_init(s);

   411     lm_init(s);

   412 

   413     return Z_OK;

   414 }

   415 

   416 /* ========================================================================= */

   417 int ZEXPORT deflateSetHeader (strm, head)

   418     z_streamp strm;

   419     gz_headerp head;

   420 {

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

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

   423     strm->state->gzhead = head;

   424     return Z_OK;

   425 }

   426 

   427 /* ========================================================================= */

   428 int ZEXPORT deflatePrime (strm, bits, value)

   429     z_streamp strm;

   430     int bits;

   431     int value;

   432 {

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

   434     strm->state->bi_valid = bits;

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

   436     return Z_OK;

   437 }

   438 

   439 /* ========================================================================= */

   440 int ZEXPORT deflateParams(strm, level, strategy)

   441     z_streamp strm;

   442     int level;

   443     int strategy;

   444 {

   445     deflate_state *s;

   446     compress_func func;

   447     int err = Z_OK;

   448 

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

   450     s = strm->state;

   451 

   452 #ifdef FASTEST

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

   454 #else

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

   456 #endif

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

   458         return Z_STREAM_ERROR;

   459     }

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

   461 

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

   463         /* Flush the last buffer: */

   464         err = deflate(strm, Z_PARTIAL_FLUSH);

   465     }

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

   467         s->level = level;

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

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

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

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

   472     }

   473     s->strategy = strategy;

   474     return err;

   475 }

   476 

   477 /* ========================================================================= */

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

   479     z_streamp strm;

   480     int good_length;

   481     int max_lazy;

   482     int nice_length;

   483     int max_chain;

   484 {

   485     deflate_state *s;

   486 

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

   488     s = strm->state;

   489     s->good_match = good_length;

   490     s->max_lazy_match = max_lazy;

   491     s->nice_match = nice_length;

   492     s->max_chain_length = max_chain;

   493     return Z_OK;

   494 }

   495 

   496 /* =========================================================================

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

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

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

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

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

   502  *

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

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

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

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

   507  *

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

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

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

   511  * seem onerous for output buffer allocation.

   512  */

   513 uLong ZEXPORT deflateBound(strm, sourceLen)

   514     z_streamp strm;

   515     uLong sourceLen;

   516 {

   517     deflate_state *s;

   518     uLong destLen;

   519 

   520     /* conservative upper bound */

   521     destLen = sourceLen +

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

   523 

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

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

   526         return destLen;

   527 

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

   529     s = strm->state;

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

   531         return destLen;

   532 

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

   534     return compressBound(sourceLen);

   535 }

   536 

   537 /* =========================================================================

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

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

   540  * pending_buf.

   541  */

   542 local void putShortMSB (s, b)

   543     deflate_state *s;

   544     uInt b;

   545 {

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

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

   548 }

   549 

   550 /* =========================================================================

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

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

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

   554  * (See also read_buf()).

   555  */

   556 local void flush_pending(strm)

   557     z_streamp strm;

   558 {

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

   560 

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

   562     if (len == 0) return;

   563 

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

   565     strm->next_out  += len;

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

   567     strm->total_out += len;

   568     strm->avail_out  -= len;

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

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

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

   572     }

   573 }

   574 

   575 /* ========================================================================= */

   576 int ZEXPORT deflate (strm, flush)

   577     z_streamp strm;

   578     int flush;

   579 {

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

   581     deflate_state *s;

   582 

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

   584         flush > Z_FINISH || flush < 0) {

   585         return Z_STREAM_ERROR;

   586     }

   587     s = strm->state;

   588 

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

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

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

   592         ERR_RETURN(strm, Z_STREAM_ERROR);

   593     }

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

   595 

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

   597     old_flush = s->last_flush;

   598     s->last_flush = flush;

   599 

   600     /* Write the header */

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

   602 #ifdef GZIP

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

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

   605             put_byte(s, 31);

   606             put_byte(s, 139);

   607             put_byte(s, 8);

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

   609                 put_byte(s, 0);

   610                 put_byte(s, 0);

   611                 put_byte(s, 0);

   612                 put_byte(s, 0);

   613                 put_byte(s, 0);

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

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

   616                              4 : 0));

   617                 put_byte(s, OS_CODE);

   618                 s->status = BUSY_STATE;

   619             }

   620             else {

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

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

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

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

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

   626                         );

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

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

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

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

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

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

   633                              4 : 0));

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

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

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

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

   638                 }

   639                 if (s->gzhead->hcrc)

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

   641                                         s->pending);

   642                 s->gzindex = 0;

   643                 s->status = EXTRA_STATE;

   644             }

   645         }

   646         else

   647 #endif

   648         {

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

   650             uInt level_flags;

   651 

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

   653                 level_flags = 0;

   654             else if (s->level < 6)

   655                 level_flags = 1;

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

   657                 level_flags = 2;

   658             else

   659                 level_flags = 3;

   660             header |= (level_flags << 6);

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

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

   663 

   664             s->status = BUSY_STATE;

   665             putShortMSB(s, header);

   666 

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

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

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

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

   671             }

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

   673         }

   674     }

   675 #ifdef GZIP

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

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

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

   679 

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

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

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

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

   684                                             s->pending - beg);

   685                     flush_pending(strm);

   686                     beg = s->pending;

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

   688                         break;

   689                 }

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

   691                 s->gzindex++;

   692             }

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

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

   695                                     s->pending - beg);

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

   697                 s->gzindex = 0;

   698                 s->status = NAME_STATE;

   699             }

   700         }

   701         else

   702             s->status = NAME_STATE;

   703     }

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

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

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

   707             int val;

   708 

   709             do {

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

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

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

   713                                             s->pending - beg);

   714                     flush_pending(strm);

   715                     beg = s->pending;

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

   717                         val = 1;

   718                         break;

   719                     }

   720                 }

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

   722                 put_byte(s, val);

   723             } while (val != 0);

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

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

   726                                     s->pending - beg);

   727             if (val == 0) {

   728                 s->gzindex = 0;

   729                 s->status = COMMENT_STATE;

   730             }

   731         }

   732         else

   733             s->status = COMMENT_STATE;

   734     }

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

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

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

   738             int val;

   739 

   740             do {

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

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

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

   744                                             s->pending - beg);

   745                     flush_pending(strm);

   746                     beg = s->pending;

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

   748                         val = 1;

   749                         break;

   750                     }

   751                 }

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

   753                 put_byte(s, val);

   754             } while (val != 0);

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

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

   757                                     s->pending - beg);

   758             if (val == 0)

   759                 s->status = HCRC_STATE;

   760         }

   761         else

   762             s->status = HCRC_STATE;

   763     }

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

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

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

   767                 flush_pending(strm);

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

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

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

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

   772                 s->status = BUSY_STATE;

   773             }

   774         }

   775         else

   776             s->status = BUSY_STATE;

   777     }

   778 #endif

   779 

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

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

   782         flush_pending(strm);

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

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

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

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

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

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

   789              */

   790             s->last_flush = -1;

   791             return Z_OK;

   792         }

   793 

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

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

   796      * returning Z_STREAM_END instead of Z_BUF_ERROR.

   797      */

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

   799                flush != Z_FINISH) {

   800         ERR_RETURN(strm, Z_BUF_ERROR);

   801     }

   802 

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

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

   805         ERR_RETURN(strm, Z_BUF_ERROR);

   806     }

   807 

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

   809      */

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

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

   812         block_state bstate;

   813 

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

   815 

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

   817             s->status = FINISH_STATE;

   818         }

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

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

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

   822             }

   823             return Z_OK;

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

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

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

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

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

   829              * one empty block.

   830              */

   831         }

   832         if (bstate == block_done) {

   833             if (flush == Z_PARTIAL_FLUSH) {

   834                 _tr_align(s);

   835             } else { /* FULL_FLUSH or SYNC_FLUSH */

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

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

   838                  * as a special marker by inflate_sync().

   839                  */

   840                 if (flush == Z_FULL_FLUSH) {

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

   842                 }

   843             }

   844             flush_pending(strm);

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

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

   847               return Z_OK;

   848             }

   849         }

   850     }

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

   852 

   853     if (flush != Z_FINISH) return Z_OK;

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

   855 

   856     /* Write the trailer */

   857 #ifdef GZIP

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

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

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

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

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

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

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

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

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

   867     }

   868     else

   869 #endif

   870     {

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

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

   873     }

   874     flush_pending(strm);

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

   876      * to flush the rest.

   877      */

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

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

   880 }

   881 

   882 /* ========================================================================= */

   883 int ZEXPORT deflateEnd (strm)

   884     z_streamp strm;

   885 {

   886     int status;

   887 

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

   889 

   890     status = strm->state->status;

   891     if (status != INIT_STATE &&

   892         status != EXTRA_STATE &&

   893         status != NAME_STATE &&

   894         status != COMMENT_STATE &&

   895         status != HCRC_STATE &&

   896         status != BUSY_STATE &&

   897         status != FINISH_STATE) {

   898       return Z_STREAM_ERROR;

   899     }

   900 

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

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

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

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

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

   906 

   907     ZFREE(strm, strm->state);

   908     strm->state = Z_NULL;

   909 

   910     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;

   911 }

   912 

   913 /* =========================================================================

   914  * Copy the source state to the destination state.

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

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

   917  */

   918 int ZEXPORT deflateCopy (dest, source)

   919     z_streamp dest;

   920     z_streamp source;

   921 {

   922 #ifdef MAXSEG_64K

   923     return Z_STREAM_ERROR;

   924 #else

   925     deflate_state *ds;

   926     deflate_state *ss;

   927     ushf *overlay;

   928 

   929 

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

   931         return Z_STREAM_ERROR;

   932     }

   933 

   934     ss = source->state;

   935 

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

   937 

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

   939     if (ds == Z_NULL) return Z_MEM_ERROR;

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

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

   942     ds->strm = dest;

   943 

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

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

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

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

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

   949 

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

   951         ds->pending_buf == Z_NULL) {

   952         deflateEnd (dest);

   953         return Z_MEM_ERROR;

   954     }

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

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

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

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

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

   960 

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

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

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

   964 

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

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

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

   968 

   969     return Z_OK;

   970 #endif /* MAXSEG_64K */

   971 }

   972 

   973 /* ===========================================================================

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

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

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

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

   978  * (See also flush_pending()).

   979  */

   980 local int read_buf(strm, buf, size)

   981     z_streamp strm;

   982     Bytef *buf;

   983     unsigned size;

   984 {

   985     unsigned len = strm->avail_in;

   986 

   987     if (len > size) len = size;

   988     if (len == 0) return 0;

   989 

   990     strm->avail_in  -= len;

   991 

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

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

   994     }

   995 #ifdef GZIP

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

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

   998     }

   999 #endif

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

  1001     strm->next_in  += len;

  1002     strm->total_in += len;

  1003 

  1004     return (int)len;

  1005 }

  1006 

  1007 /* ===========================================================================

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

  1009  */

  1010 local void lm_init (s)

  1011     deflate_state *s;

  1012 {

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

  1014 

  1015     CLEAR_HASH(s);

  1016 

  1017     /* Set the default configuration parameters:

  1018      */

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

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

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

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

  1023 

  1024     s->strstart = 0;

  1025     s->block_start = 0L;

  1026     s->lookahead = 0;

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

  1028     s->match_available = 0;

  1029     s->ins_h = 0;

  1030 #ifndef FASTEST

  1031 #ifdef ASMV

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

  1033 #endif

  1034 #endif

  1035 }

  1036 

  1037 #ifndef FASTEST

  1038 /* ===========================================================================

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

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

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

  1042  * garbage.

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

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

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

  1046  */

  1047 #ifndef ASMV

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

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

  1050  */

  1051 local uInt longest_match(s, cur_match)

  1052     deflate_state *s;

  1053     IPos cur_match;                             /* current match */

  1054 {

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

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

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

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

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

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

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

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

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

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

  1065      */

  1066     Posf *prev = s->prev;

  1067     uInt wmask = s->w_mask;

  1068 

  1069 #ifdef UNALIGNED_OK

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

  1071      * Try with and without -DUNALIGNED_OK to check.

  1072      */

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

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

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

  1076 #else

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

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

  1079     register Byte scan_end   = scan[best_len];

  1080 #endif

  1081 

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

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

  1084      */

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

  1086 

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

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

  1089         chain_length >>= 2;

  1090     }

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

  1092      * to make deflate deterministic.

  1093      */

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

  1095 

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

  1097 

  1098     do {

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

  1100         match = s->window + cur_match;

  1101 

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

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

  1104          * for insufficient lookahead only occur occasionally for performance

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

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

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

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

  1109          */

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

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

  1112          * UNALIGNED_OK if your compiler uses a different size.

  1113          */

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

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

  1116 

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

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

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

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

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

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

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

  1124          * to check more often for insufficient lookahead.

  1125          */

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

  1127         scan++, match++;

  1128         do {

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

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

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

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

  1133                  scan < strend);

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