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

     2  * Copyright (C) 1995-1998 Jean-loup Gailly.

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

     4  */

     5 

     6 /*

     7  *  ALGORITHM

     8  *

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

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

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

    12  *

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

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

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

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

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

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

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

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

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

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

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

    24  *      (by Leonid Broukhis).

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

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

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

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

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

    30  *

    31  *  ACKNOWLEDGEMENTS

    32  *

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

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

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

    36  *

    37  *  REFERENCES

    38  *

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

    40  *      Available in ftp://ds.internic.net/rfc/rfc1951.txt

    41  *

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

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

    44  *

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

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

    47  *

    48  */

    49 

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

    51 

    52 #include "deflate.h"

    53 

    54 const char deflate_copyright[] =

    55    " deflate 1.1.3 Copyright 1995-1998 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 local block_state deflate_slow   OF((deflate_state *s, int flush));

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

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

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

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

    84 #ifdef ASMV

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

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

    87 #else

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

    89 #endif

    90 

    91 #ifdef DEBUG

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

    93                             int length));

    94 #endif

    95 

    96 /* ===========================================================================

    97  * Local data

    98  */

    99 

   100 #define NIL 0

   101 /* Tail of hash chains */

   102 

   103 #ifndef TOO_FAR

   104 #  define TOO_FAR 4096

   105 #endif

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

   107 

   108 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)

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

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

   111  */

   112 

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

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

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

   116  * found for specific files.

   117  */

   118 typedef struct config_s {

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

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

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

   122    ush max_chain;

   123    compress_func func;

   124 } config;

   125 

   126 local const config configuration_table[10] = {

   127 /*      good lazy nice chain */

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

   129 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */

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

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

   132 

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

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

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

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

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

   138 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */

   139 

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

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

   142  * meaning.

   143  */

   144 

   145 #define EQUAL 0

   146 /* result of memcmp for equal strings */

   147 

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

   149 

   150 /* ===========================================================================

   151  * Update a hash value with the given input byte

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

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

   154  *    previous key instead of complete recalculation each time.

   155  */

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

   157 

   158 

   159 /* ===========================================================================

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

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

   162  * the previous length of the hash chain.

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

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

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

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

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

   168  */

   169 #ifdef FASTEST

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

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

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

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

   174 #else

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

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

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

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

   179 #endif

   180 

   181 /* ===========================================================================

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

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

   184  */

   185 #define CLEAR_HASH(s) \

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

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

   188 

   189 /* ========================================================================= */

   190 int ZEXPORT deflateInit_(z_streamp strm, int level, const char *version, int stream_size)

   191 {

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

   193 			 Z_DEFAULT_STRATEGY, version, stream_size);

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

   195 }

   196 

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

   198 int ZEXPORT deflateInit2_(z_streamp strm, int level, int method, int windowBits, int memLevel, int strategy,

   199 		  const char *version, int stream_size)

   200 {

   201     deflate_state *s;

   202     int noheader = 0;

   203     static const char* my_version = ZLIB_VERSION;

   204 

   205     ushf *overlay;

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

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

   208      */

   209 

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

   211         stream_size != sizeof(z_stream)) {

   212 	return Z_VERSION_ERROR;

   213     }

   214     if (strm == Z_NULL) return Z_STREAM_ERROR;

   215 

   216     strm->msg = Z_NULL;

   217     if (strm->zalloc == Z_NULL) {

   218 	strm->zalloc = zcalloc;

   219 	strm->opaque = (voidpf)0;

   220     }

   221     if (strm->zfree == Z_NULL) strm->zfree = zcfree;

   222 

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

   224 #ifdef FASTEST

   225     level = 1;

   226 #endif

   227 

   228     if (windowBits < 0) { /* undocumented feature: suppress zlib header */

   229         noheader = 1;

   230         windowBits = -windowBits;

   231     }

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

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

   234 	strategy < 0 || strategy > Z_HUFFMAN_ONLY) {

   235         return Z_STREAM_ERROR;

   236     }

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

   238     if (s == Z_NULL) return Z_MEM_ERROR;

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

   240     s->strm = strm;

   241 

   242     s->noheader = noheader;

   243     s->w_bits = windowBits;

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

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

   246 

   247     s->hash_bits = memLevel + 7;

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

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

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

   251 

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

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

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

   255 

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

   257 

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

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

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

   261 

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

   263         s->pending_buf == Z_NULL) {

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

   265         deflateEnd (strm);

   266         return Z_MEM_ERROR;

   267     }

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

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

   270 

   271     s->level = level;

   272     s->strategy = strategy;

   273     s->method = (Byte)method;

   274 

   275     return deflateReset(strm);

   276 }

   277 

   278 /* ========================================================================= */

   279 int ZEXPORT deflateSetDictionary (z_streamp strm, const Bytef *dictionary, uInt dictLength)

   280 {

   281     deflate_state *s;

   282     uInt length = dictLength;

   283     uInt n;

   284     IPos hash_head = 0;

   285 

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

   287         strm->state->status != INIT_STATE) return Z_STREAM_ERROR;

   288 

   289     s = strm->state;

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

   291 

   292     if (length < MIN_MATCH) return Z_OK;

   293     if (length > MAX_DIST(s)) {

   294 	length = MAX_DIST(s);

   295 #ifndef USE_DICT_HEAD

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

   297 #endif

   298     }

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

   300     s->strstart = length;

   301     s->block_start = (long)length;

   302 

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

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

   305      * call of fill_window.

   306      */

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

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

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

   310 	INSERT_STRING(s, n, hash_head);

   311     }

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

   313     return Z_OK;

   314 }

   315 

   316 /* ========================================================================= */

   317 int ZEXPORT deflateReset (z_streamp strm)

   318 {

   319     deflate_state *s;

   320     

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

   322         strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;

   323 

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

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

   326     strm->data_type = Z_UNKNOWN;

   327 

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

   329     s->pending = 0;

   330     s->pending_out = s->pending_buf;

   331 

   332     if (s->noheader < 0) {

   333         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */

   334     }

   335     s->status = s->noheader ? BUSY_STATE : INIT_STATE;

   336     strm->adler = 1;

   337     s->last_flush = Z_NO_FLUSH;

   338 

   339     _tr_init(s);

   340     lm_init(s);

   341 

   342     return Z_OK;

   343 }

   344 

   345 /* ========================================================================= */

   346 int ZEXPORT deflateParams(z_streamp strm, int level, int strategy)

   347 {

   348     deflate_state *s;

   349     compress_func func;

   350     int err = Z_OK;

   351 

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

   353     s = strm->state;

   354 

   355     if (level == Z_DEFAULT_COMPRESSION) {

   356 	level = 6;

   357     }

   358     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) {

   359 	return Z_STREAM_ERROR;

   360     }

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

   362 

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

   364 	/* Flush the last buffer: */

   365 	err = deflate(strm, Z_PARTIAL_FLUSH);

   366     }

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

   368 	s->level = level;

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

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

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

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

   373     }

   374     s->strategy = strategy;

   375     return err;

   376 }

   377 

   378 /* =========================================================================

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

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

   381  * pending_buf.

   382  */

   383 local void putShortMSB (deflate_state *s, uInt b)

   384 {

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

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

   387 }   

   388 

   389 /* =========================================================================

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

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

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

   393  * (See also read_buf()).

   394  */

   395 local void flush_pending(z_streamp strm)

   396 {

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

   398 

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

   400     if (len == 0) return;

   401 

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

   403     strm->next_out  += len;

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

   405     strm->total_out += len;

   406     strm->avail_out  -= len;

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

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

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

   410     }

   411 }

   412 

   413 /* ========================================================================= */

   414 int ZEXPORT deflate (z_streamp strm, int flush)

   415 {

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

   417     deflate_state *s;

   418 

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

   420 	flush > Z_FINISH || flush < 0) {

   421         return Z_STREAM_ERROR;

   422     }

   423     s = strm->state;

   424 

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

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

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

   428         ERR_RETURN(strm, Z_STREAM_ERROR);

   429     }

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

   431 

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

   433     old_flush = s->last_flush;

   434     s->last_flush = flush;

   435 

   436     /* Write the zlib header */

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

   438 

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

   440         uInt level_flags = (s->level-1) >> 1;

   441 

   442         if (level_flags > 3) level_flags = 3;

   443         header |= (level_flags << 6);

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

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

   446 

   447         s->status = BUSY_STATE;

   448         putShortMSB(s, header);

   449 

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

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

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

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

   454 	}

   455 	strm->adler = 1L;

   456     }

   457 

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

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

   460         flush_pending(strm);

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

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

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

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

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

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

   467              */

   468 	    s->last_flush = -1;

   469 	    return Z_OK;

   470 	}

   471 

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

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

   474      * returning Z_STREAM_END instead of Z_BUFF_ERROR.

   475      */

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

   477 	       flush != Z_FINISH) {

   478         ERR_RETURN(strm, Z_BUF_ERROR);

   479     }

   480 

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

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

   483         ERR_RETURN(strm, Z_BUF_ERROR);

   484     }

   485 

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

   487      */

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

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

   490         block_state bstate;

   491 

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

   493 

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

   495             s->status = FINISH_STATE;

   496         }

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

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

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

   500 	    }

   501 	    return Z_OK;

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

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

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

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

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

   507 	     * one empty block.

   508 	     */

   509 	}

   510         if (bstate == block_done) {

   511             if (flush == Z_PARTIAL_FLUSH) {

   512                 _tr_align(s);

   513             } else { /* FULL_FLUSH or SYNC_FLUSH */

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

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

   516                  * as a special marker by inflate_sync().

   517                  */

   518                 if (flush == Z_FULL_FLUSH) {

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

   520                 }

   521             }

   522             flush_pending(strm);

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

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

   525 	      return Z_OK;

   526 	    }

   527         }

   528     }

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

   530 

   531     if (flush != Z_FINISH) return Z_OK;

   532     if (s->noheader) return Z_STREAM_END;

   533 

   534     /* Write the zlib trailer (adler32) */

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

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

   537     flush_pending(strm);

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

   539      * to flush the rest.

   540      */

   541     s->noheader = -1; /* write the trailer only once! */

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

   543 }

   544 

   545 /* ========================================================================= */

   546 int ZEXPORT deflateEnd (z_streamp strm)

   547 {

   548     int status;

   549 

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

   551 

   552     status = strm->state->status;

   553     if (status != INIT_STATE && status != BUSY_STATE &&

   554 	status != FINISH_STATE) {

   555       return Z_STREAM_ERROR;

   556     }

   557 

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

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

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

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

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

   563 

   564     ZFREE(strm, strm->state);

   565     strm->state = Z_NULL;

   566 

   567     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;

   568 }

   569 

   570 /* =========================================================================

   571  * Copy the source state to the destination state.

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

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

   574  */

   575 int ZEXPORT deflateCopy (z_streamp dest, z_streamp source)

   576 {

   577 #ifdef MAXSEG_64K

   578     return Z_STREAM_ERROR;

   579 #else

   580     deflate_state *ds;

   581     deflate_state *ss;

   582     ushf *overlay;

   583 

   584 

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

   586         return Z_STREAM_ERROR;

   587     }

   588 

   589     ss = source->state;

   590 

   591     *dest = *source;

   592 

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

   594     if (ds == Z_NULL) return Z_MEM_ERROR;

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

   596     *ds = *ss;

   597     ds->strm = dest;

   598 

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

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

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

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

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

   604 

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

   606         ds->pending_buf == Z_NULL) {

   607         deflateEnd (dest);

   608         return Z_MEM_ERROR;

   609     }

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

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

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

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

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

   615 

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

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

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

   619 

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

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

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

   623 

   624     return Z_OK;

   625 #endif

   626 }

   627 

   628 /* ===========================================================================

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

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

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

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

   633  * (See also flush_pending()).

   634  */

   635 local int read_buf(z_streamp strm, Bytef *buf, unsigned size)

   636 {

   637     unsigned len = strm->avail_in;

   638 

   639     if (len > size) len = size;

   640     if (len == 0) return 0;

   641 

   642     strm->avail_in  -= len;

   643 

   644     if (!strm->state->noheader) {

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

   646     }

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

   648     strm->next_in  += len;

   649     strm->total_in += len;

   650 

   651     return (int)len;

   652 }

   653 

   654 /* ===========================================================================

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

   656  */

   657 local void lm_init (deflate_state *s)

   658 {

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

   660 

   661     CLEAR_HASH(s);

   662 

   663     /* Set the default configuration parameters:

   664      */

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

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

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

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

   669 

   670     s->strstart = 0;

   671     s->block_start = 0L;

   672     s->lookahead = 0;

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

   674     s->match_available = 0;

   675     s->ins_h = 0;

   676 #ifdef ASMV

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

   678 #endif

   679 }

   680 

   681 /* ===========================================================================

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

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

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

   685  * garbage.

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

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

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

   689  */

   690 #ifndef ASMV

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

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

   693  */

   694 #ifndef FASTEST

   695 local uInt longest_match(deflate_state *s, IPos cur_match)

   696 /* IPos cur_match;         current match */

   697 {

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

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

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

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

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

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

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

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

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

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

   708      */

   709     Posf *prev = s->prev;

   710     uInt wmask = s->w_mask;

   711 

   712 #ifdef UNALIGNED_OK

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

   714      * Try with and without -DUNALIGNED_OK to check.

   715      */

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

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

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

   719 #else

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

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

   722     register Byte scan_end   = scan[best_len];

   723 #endif

   724 

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

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

   727      */

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

   729 

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

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

   732         chain_length >>= 2;

   733     }

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

   735      * to make deflate deterministic.

   736      */

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

   738 

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

   740 

   741     do {

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

   743         match = s->window + cur_match;

   744 

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

   746          * or if the match length is less than 2:

   747          */

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

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

   750          * UNALIGNED_OK if your compiler uses a different size.

   751          */

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

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

   754 

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

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

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

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

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

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

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

   762          * to check more often for insufficient lookahead.

   763          */

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

   765         scan++, match++;

   766         do {

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

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

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

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

   771                  scan < strend);

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

   773 

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

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

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

   777 

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

   779         scan = strend - (MAX_MATCH-1);

   780 

   781 #else /* UNALIGNED_OK */

   782 

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

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

   785             *match            != *scan     ||

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

   787 

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

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

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

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

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

   793          */

   794         scan += 2, match++;

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

   796 

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

   798          * the 256th check will be made at strstart+258.

   799          */

   800         do {

   801         } while (*++scan == *++match && *++scan == *++match &&

   802                  *++scan == *++match && *++scan == *++match &&

   803                  *++scan == *++match && *++scan == *++match &&

   804                  *++scan == *++match && *++scan == *++match &&

   805                  scan < strend);

   806 

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

   808 

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

   810         scan = strend - MAX_MATCH;

   811 

   812 #endif /* UNALIGNED_OK */

   813 

   814         if (len > best_len) {

   815             s->match_start = cur_match;

   816             best_len = len;

   817             if (len >= nice_match) break;

   818 #ifdef UNALIGNED_OK

   819             scan_end = *(ushf*)(scan+best_len-1);

   820 #else

   821             scan_end1  = scan[best_len-1];

   822             scan_end   = scan[best_len];

   823 #endif

   824         }

   825     } while ((cur_match = prev[cur_match & wmask]) > limit

   826              && --chain_length != 0);

   827 

   828     if ((uInt)best_len <= s->lookahead) return (uInt)best_len;

   829     return s->lookahead;

   830 }

   831 

   832 #else /* FASTEST */

   833 /* ---------------------------------------------------------------------------

   834  * Optimized version for level == 1 only

   835  */

   836 local uInt longest_match(deflate_state *s, IPos cur_match)

   837 /*  IPos cur_match      current match. */

   838 {

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

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

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

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

   843 

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

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

   846      */

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

   848 

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

   850 

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

   852 

   853     match = s->window + cur_match;

   854 

   855     /* Return failure if the match length is less than 2:

   856      */

   857     if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;

   858 

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

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

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

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

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

   864      */

   865     scan += 2, match += 2;

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

   867 

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

   869      * the 256th check will be made at strstart+258.

   870      */

   871     do {

   872     } while (*++scan == *++match && *++scan == *++match &&

   873 	     *++scan == *++match && *++scan == *++match &&

   874 	     *++scan == *++match && *++scan == *++match &&

   875 	     *++scan == *++match && *++scan == *++match &&

   876 	     scan < strend);

   877 

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

   879 

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

   881 

   882     if (len < MIN_MATCH) return MIN_MATCH - 1;

   883 

   884     s->match_start = cur_match;

   885     return len <= s->lookahead ? len : s->lookahead;

   886 }

   887 #endif /* FASTEST */

   888 #endif /* ASMV */

   889 

   890 #ifdef DEBUG

   891 /* ===========================================================================

   892  * Check that the match at match_start is indeed a match.

   893  */

   894 local void check_match(deflate_state *s, IPos start, IPos match, int length)

   895 {

   896     /* check that the match is indeed a match */

   897     if (zmemcmp(s->window + match,

   898                 s->window + start, length) != EQUAL) {

   899         fprintf(stderr, " start %u, match %u, length %d\n",

   900 		start, match, length);

   901         do {

   902 	    fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);

   903 	} while (--length != 0);

   904         z_error("invalid match");

   905     }

   906     if (z_verbose > 1) {

   907         fprintf(stderr,"\\[%d,%d]", start-match, length);

   908         do { putc(s->window[start++], stderr); } while (--length != 0);

   909     }

   910 }

   911 #else

   912 #  define check_match(s, start, match, length)

   913 #endif

   914 

   915 /* ===========================================================================

   916  * Fill the window when the lookahead becomes insufficient.

   917  * Updates strstart and lookahead.

   918  *

   919  * IN assertion: lookahead < MIN_LOOKAHEAD

   920  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD

   921  *    At least one byte has been read, or avail_in == 0; reads are

   922  *    performed for at least two bytes (required for the zip translate_eol

   923  *    option -- not supported here).

   924  */

   925 local void fill_window(deflate_state *s)

   926 {

   927     register unsigned n, m;

   928     register Posf *p;

   929     unsigned more;    /* Amount of free space at the end of the window. */

   930     uInt wsize = s->w_size;

   931 

   932     do {

   933         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);

   934 

   935         /* Deal with !@#$% 64K limit: */

   936         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {

   937             more = wsize;

   938 

   939         } else if (more == (unsigned)(-1)) {

   940             /* Very unlikely, but possible on 16 bit machine if strstart == 0

   941              * and lookahead == 1 (input done one byte at time)

   942              */

   943             more--;

   944 

   945         /* If the window is almost full and there is insufficient lookahead,

   946          * move the upper half to the lower one to make room in the upper half.

   947          */

   948         } else if (s->strstart >= wsize+MAX_DIST(s)) {

   949 

   950             zmemcpy(s->window, s->window+wsize, (unsigned)wsize);

   951             s->match_start -= wsize;

   952             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */

   953             s->block_start -= (long) wsize;

   954 

   955             /* Slide the hash table (could be avoided with 32 bit values

   956                at the expense of memory usage). We slide even when level == 0

   957                to keep the hash table consistent if we switch back to level > 0

   958                later. (Using level 0 permanently is not an optimal usage of

   959                zlib, so we don't care about this pathological case.)

   960              */

   961 	    n = s->hash_size;

   962 	    p = &s->head[n];

   963 	    do {

   964 		m = *--p;

   965 		*p = (Pos)(m >= wsize ? m-wsize : NIL);

   966 	    } while (--n);

   967 

   968 	    n = wsize;

   969 #ifndef FASTEST

   970 	    p = &s->prev[n];

   971 	    do {

   972 		m = *--p;

   973 		*p = (Pos)(m >= wsize ? m-wsize : NIL);

   974 		/* If n is not on any hash chain, prev[n] is garbage but

   975 		 * its value will never be used.

   976 		 */

   977 	    } while (--n);

   978 #endif

   979             more += wsize;

   980         }

   981         if (s->strm->avail_in == 0) return;

   982 

   983         /* If there was no sliding:

   984          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&

   985          *    more == window_size - lookahead - strstart

   986          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)

   987          * => more >= window_size - 2*WSIZE + 2

   988          * In the BIG_MEM or MMAP case (not yet supported),

   989          *   window_size == input_size + MIN_LOOKAHEAD  &&

   990          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.

   991          * Otherwise, window_size == 2*WSIZE so more >= 2.

   992          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.

   993          */

   994         Assert(more >= 2, "more < 2");

   995 

   996         n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);

   997         s->lookahead += n;

   998 

   999         /* Initialize the hash value now that we have some input: */

  1000         if (s->lookahead >= MIN_MATCH) {

  1001             s->ins_h = s->window[s->strstart];

  1002             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);

  1003 #if MIN_MATCH != 3

  1004             Call UPDATE_HASH() MIN_MATCH-3 more times

  1005 #endif

  1006         }

  1007         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,

  1008          * but this is not important since only literal bytes will be emitted.

  1009          */

  1010 

  1011     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);

  1012 }

  1013 

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

  1015  * Flush the current block, with given end-of-file flag.

  1016  * IN assertion: strstart is set to the end of the current match.

  1017  */

  1018 #define FLUSH_BLOCK_ONLY(s, eof) { \

  1019    _tr_flush_block(s, (s->block_start >= 0L ? \

  1020                    (charf *)&s->window[(unsigned)s->block_start] : \

  1021                    (charf *)Z_NULL), \

  1022 		(ulg)((long)s->strstart - s->block_start), \

  1023 		(eof)); \

  1024    s->block_start = s->strstart; \

  1025    flush_pending(s->strm); \

  1026    Tracev((stderr,"[FLUSH]")); \

  1027 }

  1028 

  1029 /* Same but force premature exit if necessary. */

  1030 #define FLUSH_BLOCK(s, eof) { \

  1031    FLUSH_BLOCK_ONLY(s, eof); \

  1032    if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \

  1033 }

  1034 

  1035 /* ===========================================================================

  1036  * Copy without compression as much as possible from the input stream, return

  1037  * the current block state.

  1038  * This function does not insert new strings in the dictionary since

  1039  * uncompressible data is probably not useful. This function is used

  1040  * only for the level=0 compression option.

  1041  * NOTE: this function should be optimized to avoid extra copying from

  1042  * window to pending_buf.

  1043  */

  1044 local block_state deflate_stored(deflate_state *s, int flush)

  1045 {

  1046     /* Stored blocks are limited to 0xffff bytes, pending_buf is limited

  1047      * to pending_buf_size, and each stored block has a 5 byte header:

  1048      */

  1049     ulg max_block_size = 0xffff;

  1050     ulg max_start;

  1051 

  1052     if (max_block_size > s->pending_buf_size - 5) {

  1053         max_block_size = s->pending_buf_size - 5;

  1054     }

  1055 

  1056     /* Copy as much as possible from input to output: */

  1057     for (;;) {

  1058         /* Fill the window as much as possible: */

  1059         if (s->lookahead <= 1) {

  1060 

  1061             Assert(s->strstart < s->w_size+MAX_DIST(s) ||

  1062 		   s->block_start >= (long)s->w_size, "slide too late");

  1063 

  1064             fill_window(s);

  1065             if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;

  1066 

  1067             if (s->lookahead == 0) break; /* flush the current block */

  1068         }

  1069 	Assert(s->block_start >= 0L, "block gone");

  1070 

  1071 	s->strstart += s->lookahead;

  1072 	s->lookahead = 0;

  1073 

  1074 	/* Emit a stored block if pending_buf will be full: */

  1075  	max_start = s->block_start + max_block_size;

  1076         if (s->strstart == 0 || (ulg)s->strstart >= max_start) {

  1077 	    /* strstart == 0 is possible when wraparound on 16-bit machine */

  1078 	    s->lookahead = (uInt)(s->strstart - max_start);

  1079 	    s->strstart = (uInt)max_start;

  1080             FLUSH_BLOCK(s, 0);

  1081 	}

  1082 	/* Flush if we may have to slide, otherwise block_start may become

  1083          * negative and the data will be gone:

  1084          */

  1085         if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {

  1086             FLUSH_BLOCK(s, 0);

  1087 	}

  1088     }

  1089     FLUSH_BLOCK(s, flush == Z_FINISH);

  1090     return flush == Z_FINISH ? finish_done : block_done;

  1091 }

  1092 

  1093 /* ===========================================================================

  1094  * Compress as much as possible from the input stream, return the current

  1095  * block state.

  1096  * This function does not perform lazy evaluation of matches and inserts

  1097  * new strings in the dictionary only for unmatched strings or for short

  1098  * matches. It is used only for the fast compression options.

  1099  */

  1100 local block_state deflate_fast(deflate_state *s, int flush)

  1101 {

  1102     IPos hash_head = NIL; /* head of the hash chain */

  1103     int bflush;           /* set if current block must be flushed */

  1104 

  1105     for (;;) {

  1106         /* Make sure that we always have enough lookahead, except

  1107          * at the end of the input file. We need MAX_MATCH bytes

  1108          * for the next match, plus MIN_MATCH bytes to insert the

  1109          * string following the next match.

  1110          */

  1111         if (s->lookahead < MIN_LOOKAHEAD) {

  1112             fill_window(s);

  1113             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {

  1114 	        return need_more;

  1115 	    }

  1116             if (s->lookahead == 0) break; /* flush the current block */

  1117         }

  1118 

  1119         /* Insert the string window[strstart .. strstart+2] in the

  1120          * dictionary, and set hash_head to the head of the hash chain:

  1121          */

  1122         if (s->lookahead >= MIN_MATCH) {

  1123             INSERT_STRING(s, s->strstart, hash_head);

  1124         }

  1125 

  1126         /* Find the longest match, discarding those <= prev_length.

  1127          * At this point we have always match_length < MIN_MATCH

  1128          */

  1129         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {

  1130             /* To simplify the code, we prevent matches with the string

  1131              * of window index 0 (in particular we have to avoid a match

  1132              * of the string with itself at the start of the input file).

  1133              */

  1134             if (s->strategy != Z_HUFFMAN_ONLY) {