"Fossies" - the Fresh Open Source Software Archive

Member "mariadb-connector-c-3.0.9-src/zlib/deflate.c" (8 Feb 2019, 67992 Bytes) of package /linux/misc/mariadb-connector-c-3.0.9-src.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /* deflate.c -- compress data using the deflation algorithm
    2  * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler
    3  * For conditions of distribution and use, see copyright notice in zlib.h
    4  */
    5 
    6 /*
    7  *  ALGORITHM
    8  *
    9  *      The "deflation" process depends on being able to identify portions
   10  *      of the input text which are identical to earlier input (within a
   11  *      sliding window trailing behind the input currently being processed).
   12  *
   13  *      The most straightforward technique turns out to be the fastest for
   14  *      most input files: try all possible matches and select the longest.
   15  *      The key feature of this algorithm is that insertions into the string
   16  *      dictionary are very simple and thus fast, and deletions are avoided
   17  *      completely. Insertions are performed at each input character, whereas
   18  *      string matches are performed only when the previous match ends. So it
   19  *      is preferable to spend more time in matches to allow very fast string
   20  *      insertions and avoid deletions. The matching algorithm for small
   21  *      strings is inspired from that of Rabin & Karp. A brute force approach
   22  *      is used to find longer strings when a small match has been found.
   23  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
   24  *      (by Leonid Broukhis).
   25  *         A previous version of this file used a more sophisticated algorithm
   26  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
   27  *      time, but has a larger average cost, uses more memory and is patented.
   28  *      However the F&G algorithm may be faster for some highly redundant
   29  *      files if the parameter max_chain_length (described below) is too large.
   30  *
   31  *  ACKNOWLEDGEMENTS
   32  *
   33  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
   34  *      I found it in 'freeze' written by Leonid Broukhis.
   35  *      Thanks to many people for bug reports and testing.
   36  *
   37  *  REFERENCES
   38  *
   39  *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
   40  *      Available in http://www.ietf.org/rfc/rfc1951.txt
   41  *
   42  *      A description of the Rabin and Karp algorithm is given in the book
   43  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
   44  *
   45  *      Fiala,E.R., and Greene,D.H.
   46  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
   47  *
   48  */
   49 
   50 /* @(#) $Id$ */
   51 
   52 #include "deflate.h"
   53 
   54 const char deflate_copyright[] =
   55    " deflate 1.2.5 Copyright 1995-2010 Jean-loup Gailly and Mark Adler ";
   56 /*
   57   If you use the zlib library in a product, an acknowledgment is welcome
   58   in the documentation of your product. If for some reason you cannot
   59   include such an acknowledgment, I would appreciate that you keep this
   60   copyright string in the executable of your product.
   61  */
   62 
   63 /* ===========================================================================
   64  *  Function prototypes.
   65  */
   66 typedef enum {
   67     need_more,      /* block not completed, need more input or more output */
   68     block_done,     /* block flush performed */
   69     finish_started, /* finish started, need only more output at next deflate */
   70     finish_done     /* finish done, accept no more input or output */
   71 } block_state;
   72 
   73 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
   74 /* Compression function. Returns the block state after the call. */
   75 
   76 local void fill_window    OF((deflate_state *s));
   77 local block_state deflate_stored OF((deflate_state *s, int flush));
   78 local block_state deflate_fast   OF((deflate_state *s, int flush));
   79 #ifndef FASTEST
   80 local block_state deflate_slow   OF((deflate_state *s, int flush));
   81 #endif
   82 local block_state deflate_rle    OF((deflate_state *s, int flush));
   83 local block_state deflate_huff   OF((deflate_state *s, int flush));
   84 local void lm_init        OF((deflate_state *s));
   85 local void putShortMSB    OF((deflate_state *s, uInt b));
   86 local void flush_pending  OF((z_streamp strm));
   87 local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));
   88 #ifdef ASMV
   89       void match_init OF((void)); /* asm code initialization */
   90       uInt longest_match  OF((deflate_state *s, IPos cur_match));
   91 #else
   92 local uInt longest_match  OF((deflate_state *s, IPos cur_match));
   93 #endif
   94 
   95 #ifdef DEBUG
   96 local  void check_match OF((deflate_state *s, IPos start, IPos match,
   97                             int length));
   98 #endif
   99 
  100 /* ===========================================================================
  101  * Local data
  102  */
  103 
  104 #define NIL 0
  105 /* Tail of hash chains */
  106 
  107 #ifndef TOO_FAR
  108 #  define TOO_FAR 4096
  109 #endif
  110 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  111 
  112 /* Values for max_lazy_match, good_match and max_chain_length, depending on
  113  * the desired pack level (0..9). The values given below have been tuned to
  114  * exclude worst case performance for pathological files. Better values may be
  115  * found for specific files.
  116  */
  117 typedef struct config_s {
  118    ush good_length; /* reduce lazy search above this match length */
  119    ush max_lazy;    /* do not perform lazy search above this match length */
  120    ush nice_length; /* quit search above this match length */
  121    ush max_chain;
  122    compress_func func;
  123 } config;
  124 
  125 #ifdef FASTEST
  126 local const config configuration_table[2] = {
  127 /*      good lazy nice chain */
  128 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  129 /* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */
  130 #else
  131 local const config configuration_table[10] = {
  132 /*      good lazy nice chain */
  133 /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  134 /* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
  135 /* 2 */ {4,    5, 16,    8, deflate_fast},
  136 /* 3 */ {4,    6, 32,   32, deflate_fast},
  137 
  138 /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
  139 /* 5 */ {8,   16, 32,   32, deflate_slow},
  140 /* 6 */ {8,   16, 128, 128, deflate_slow},
  141 /* 7 */ {8,   32, 128, 256, deflate_slow},
  142 /* 8 */ {32, 128, 258, 1024, deflate_slow},
  143 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
  144 #endif
  145 
  146 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  147  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  148  * meaning.
  149  */
  150 
  151 #define EQUAL 0
  152 /* result of memcmp for equal strings */
  153 
  154 #ifndef NO_DUMMY_DECL
  155 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
  156 #endif
  157 
  158 /* ===========================================================================
  159  * Update a hash value with the given input byte
  160  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  161  *    input characters, so that a running hash key can be computed from the
  162  *    previous key instead of complete recalculation each time.
  163  */
  164 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
  165 
  166 
  167 /* ===========================================================================
  168  * Insert string str in the dictionary and set match_head to the previous head
  169  * of the hash chain (the most recent string with same hash key). Return
  170  * the previous length of the hash chain.
  171  * If this file is compiled with -DFASTEST, the compression level is forced
  172  * to 1, and no hash chains are maintained.
  173  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  174  *    input characters and the first MIN_MATCH bytes of str are valid
  175  *    (except for the last MIN_MATCH-1 bytes of the input file).
  176  */
  177 #ifdef FASTEST
  178 #define INSERT_STRING(s, str, match_head) \
  179    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  180     match_head = s->head[s->ins_h], \
  181     s->head[s->ins_h] = (Pos)(str))
  182 #else
  183 #define INSERT_STRING(s, str, match_head) \
  184    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  185     match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
  186     s->head[s->ins_h] = (Pos)(str))
  187 #endif
  188 
  189 /* ===========================================================================
  190  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  191  * prev[] will be initialized on the fly.
  192  */
  193 #define CLEAR_HASH(s) \
  194     s->head[s->hash_size-1] = NIL; \
  195     zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
  196 
  197 /* ========================================================================= */
  198 int ZEXPORT deflateInit_(strm, level, version, stream_size)
  199     z_streamp strm;
  200     int level;
  201     const char *version;
  202     int stream_size;
  203 {
  204     return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
  205                          Z_DEFAULT_STRATEGY, version, stream_size);
  206     /* To do: ignore strm->next_in if we use it as window */
  207 }
  208 
  209 /* ========================================================================= */
  210 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
  211                   version, stream_size)
  212     z_streamp strm;
  213     int  level;
  214     int  method;
  215     int  windowBits;
  216     int  memLevel;
  217     int  strategy;
  218     const char *version;
  219     int stream_size;
  220 {
  221     deflate_state *s;
  222     int wrap = 1;
  223     static const char my_version[] = ZLIB_VERSION;
  224 
  225     ushf *overlay;
  226     /* We overlay pending_buf and d_buf+l_buf. This works since the average
  227      * output size for (length,distance) codes is <= 24 bits.
  228      */
  229 
  230     if (version == Z_NULL || version[0] != my_version[0] ||
  231         stream_size != sizeof(z_stream)) {
  232         return Z_VERSION_ERROR;
  233     }
  234     if (strm == Z_NULL) return Z_STREAM_ERROR;
  235 
  236     strm->msg = Z_NULL;
  237     if (strm->zalloc == (alloc_func)0) {
  238         strm->zalloc = zcalloc;
  239         strm->opaque = (voidpf)0;
  240     }
  241     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
  242 
  243 #ifdef FASTEST
  244     if (level != 0) level = 1;
  245 #else
  246     if (level == Z_DEFAULT_COMPRESSION) level = 6;
  247 #endif
  248 
  249     if (windowBits < 0) { /* suppress zlib wrapper */
  250         wrap = 0;
  251         windowBits = -windowBits;
  252     }
  253 #ifdef GZIP
  254     else if (windowBits > 15) {
  255         wrap = 2;       /* write gzip wrapper instead */
  256         windowBits -= 16;
  257     }
  258 #endif
  259     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
  260         windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
  261         strategy < 0 || strategy > Z_FIXED) {
  262         return Z_STREAM_ERROR;
  263     }
  264     if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */
  265     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
  266     if (s == Z_NULL) return Z_MEM_ERROR;
  267     strm->state = (struct internal_state FAR *)s;
  268     s->strm = strm;
  269 
  270     s->wrap = wrap;
  271     s->gzhead = Z_NULL;
  272     s->w_bits = windowBits;
  273     s->w_size = 1 << s->w_bits;
  274     s->w_mask = s->w_size - 1;
  275 
  276     s->hash_bits = memLevel + 7;
  277     s->hash_size = 1 << s->hash_bits;
  278     s->hash_mask = s->hash_size - 1;
  279     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
  280 
  281     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
  282     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
  283     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
  284 
  285     s->high_water = 0;      /* nothing written to s->window yet */
  286 
  287     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
  288 
  289     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
  290     s->pending_buf = (uchf *) overlay;
  291     s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
  292 
  293     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
  294         s->pending_buf == Z_NULL) {
  295         s->status = FINISH_STATE;
  296         strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
  297         deflateEnd (strm);
  298         return Z_MEM_ERROR;
  299     }
  300     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
  301     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
  302 
  303     s->level = level;
  304     s->strategy = strategy;
  305     s->method = (Byte)method;
  306 
  307     return deflateReset(strm);
  308 }
  309 
  310 /* ========================================================================= */
  311 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
  312     z_streamp strm;
  313     const Bytef *dictionary;
  314     uInt  dictLength;
  315 {
  316     deflate_state *s;
  317     uInt length = dictLength;
  318     uInt n;
  319     IPos hash_head = 0;
  320 
  321     if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
  322         strm->state->wrap == 2 ||
  323         (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
  324         return Z_STREAM_ERROR;
  325 
  326     s = strm->state;
  327     if (s->wrap)
  328         strm->adler = adler32(strm->adler, dictionary, dictLength);
  329 
  330     if (length < MIN_MATCH) return Z_OK;
  331     if (length > s->w_size) {
  332         length = s->w_size;
  333         dictionary += dictLength - length; /* use the tail of the dictionary */
  334     }
  335     zmemcpy(s->window, dictionary, length);
  336     s->strstart = length;
  337     s->block_start = (long)length;
  338 
  339     /* Insert all strings in the hash table (except for the last two bytes).
  340      * s->lookahead stays null, so s->ins_h will be recomputed at the next
  341      * call of fill_window.
  342      */
  343     s->ins_h = s->window[0];
  344     UPDATE_HASH(s, s->ins_h, s->window[1]);
  345     for (n = 0; n <= length - MIN_MATCH; n++) {
  346         INSERT_STRING(s, n, hash_head);
  347     }
  348     if (hash_head) hash_head = 0;  /* to make compiler happy */
  349     return Z_OK;
  350 }
  351 
  352 /* ========================================================================= */
  353 int ZEXPORT deflateReset (strm)
  354     z_streamp strm;
  355 {
  356     deflate_state *s;
  357 
  358     if (strm == Z_NULL || strm->state == Z_NULL ||
  359         strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
  360         return Z_STREAM_ERROR;
  361     }
  362 
  363     strm->total_in = strm->total_out = 0;
  364     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
  365     strm->data_type = Z_UNKNOWN;
  366 
  367     s = (deflate_state *)strm->state;
  368     s->pending = 0;
  369     s->pending_out = s->pending_buf;
  370 
  371     if (s->wrap < 0) {
  372         s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
  373     }
  374     s->status = s->wrap ? INIT_STATE : BUSY_STATE;
  375     strm->adler =
  376 #ifdef GZIP
  377         s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
  378 #endif
  379         adler32(0L, Z_NULL, 0);
  380     s->last_flush = Z_NO_FLUSH;
  381 
  382     _tr_init(s);
  383     lm_init(s);
  384 
  385     return Z_OK;
  386 }
  387 
  388 /* ========================================================================= */
  389 int ZEXPORT deflateSetHeader (strm, head)
  390     z_streamp strm;
  391     gz_headerp head;
  392 {
  393     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  394     if (strm->state->wrap != 2) return Z_STREAM_ERROR;
  395     strm->state->gzhead = head;
  396     return Z_OK;
  397 }
  398 
  399 /* ========================================================================= */
  400 int ZEXPORT deflatePrime (strm, bits, value)
  401     z_streamp strm;
  402     int bits;
  403     int value;
  404 {
  405     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  406     strm->state->bi_valid = bits;
  407     strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
  408     return Z_OK;
  409 }
  410 
  411 /* ========================================================================= */
  412 int ZEXPORT deflateParams(strm, level, strategy)
  413     z_streamp strm;
  414     int level;
  415     int strategy;
  416 {
  417     deflate_state *s;
  418     compress_func func;
  419     int err = Z_OK;
  420 
  421     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  422     s = strm->state;
  423 
  424 #ifdef FASTEST
  425     if (level != 0) level = 1;
  426 #else
  427     if (level == Z_DEFAULT_COMPRESSION) level = 6;
  428 #endif
  429     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
  430         return Z_STREAM_ERROR;
  431     }
  432     func = configuration_table[s->level].func;
  433 
  434     if ((strategy != s->strategy || func != configuration_table[level].func) &&
  435         strm->total_in != 0) {
  436         /* Flush the last buffer: */
  437         err = deflate(strm, Z_BLOCK);
  438     }
  439     if (s->level != level) {
  440         s->level = level;
  441         s->max_lazy_match   = configuration_table[level].max_lazy;
  442         s->good_match       = configuration_table[level].good_length;
  443         s->nice_match       = configuration_table[level].nice_length;
  444         s->max_chain_length = configuration_table[level].max_chain;
  445     }
  446     s->strategy = strategy;
  447     return err;
  448 }
  449 
  450 /* ========================================================================= */
  451 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
  452     z_streamp strm;
  453     int good_length;
  454     int max_lazy;
  455     int nice_length;
  456     int max_chain;
  457 {
  458     deflate_state *s;
  459 
  460     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  461     s = strm->state;
  462     s->good_match = good_length;
  463     s->max_lazy_match = max_lazy;
  464     s->nice_match = nice_length;
  465     s->max_chain_length = max_chain;
  466     return Z_OK;
  467 }
  468 
  469 /* =========================================================================
  470  * For the default windowBits of 15 and memLevel of 8, this function returns
  471  * a close to exact, as well as small, upper bound on the compressed size.
  472  * They are coded as constants here for a reason--if the #define's are
  473  * changed, then this function needs to be changed as well.  The return
  474  * value for 15 and 8 only works for those exact settings.
  475  *
  476  * For any setting other than those defaults for windowBits and memLevel,
  477  * the value returned is a conservative worst case for the maximum expansion
  478  * resulting from using fixed blocks instead of stored blocks, which deflate
  479  * can emit on compressed data for some combinations of the parameters.
  480  *
  481  * This function could be more sophisticated to provide closer upper bounds for
  482  * every combination of windowBits and memLevel.  But even the conservative
  483  * upper bound of about 14% expansion does not seem onerous for output buffer
  484  * allocation.
  485  */
  486 uLong ZEXPORT deflateBound(strm, sourceLen)
  487     z_streamp strm;
  488     uLong sourceLen;
  489 {
  490     deflate_state *s;
  491     uLong complen, wraplen;
  492     Bytef *str;
  493 
  494     /* conservative upper bound for compressed data */
  495     complen = sourceLen +
  496               ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
  497 
  498     /* if can't get parameters, return conservative bound plus zlib wrapper */
  499     if (strm == Z_NULL || strm->state == Z_NULL)
  500         return complen + 6;
  501 
  502     /* compute wrapper length */
  503     s = strm->state;
  504     switch (s->wrap) {
  505     case 0:                                 /* raw deflate */
  506         wraplen = 0;
  507         break;
  508     case 1:                                 /* zlib wrapper */
  509         wraplen = 6 + (s->strstart ? 4 : 0);
  510         break;
  511     case 2:                                 /* gzip wrapper */
  512         wraplen = 18;
  513         if (s->gzhead != Z_NULL) {          /* user-supplied gzip header */
  514             if (s->gzhead->extra != Z_NULL)
  515                 wraplen += 2 + s->gzhead->extra_len;
  516             str = s->gzhead->name;
  517             if (str != Z_NULL)
  518                 do {
  519                     wraplen++;
  520                 } while (*str++);
  521             str = s->gzhead->comment;
  522             if (str != Z_NULL)
  523                 do {
  524                     wraplen++;
  525                 } while (*str++);
  526             if (s->gzhead->hcrc)
  527                 wraplen += 2;
  528         }
  529         break;
  530     default:                                /* for compiler happiness */
  531         wraplen = 6;
  532     }
  533 
  534     /* if not default parameters, return conservative bound */
  535     if (s->w_bits != 15 || s->hash_bits != 8 + 7)
  536         return complen + wraplen;
  537 
  538     /* default settings: return tight bound for that case */
  539     return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
  540            (sourceLen >> 25) + 13 - 6 + wraplen;
  541 }
  542 
  543 /* =========================================================================
  544  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
  545  * IN assertion: the stream state is correct and there is enough room in
  546  * pending_buf.
  547  */
  548 local void putShortMSB (s, b)
  549     deflate_state *s;
  550     uInt b;
  551 {
  552     put_byte(s, (Byte)(b >> 8));
  553     put_byte(s, (Byte)(b & 0xff));
  554 }
  555 
  556 /* =========================================================================
  557  * Flush as much pending output as possible. All deflate() output goes
  558  * through this function so some applications may wish to modify it
  559  * to avoid allocating a large strm->next_out buffer and copying into it.
  560  * (See also read_buf()).
  561  */
  562 local void flush_pending(strm)
  563     z_streamp strm;
  564 {
  565     unsigned len = strm->state->pending;
  566 
  567     if (len > strm->avail_out) len = strm->avail_out;
  568     if (len == 0) return;
  569 
  570     zmemcpy(strm->next_out, strm->state->pending_out, len);
  571     strm->next_out  += len;
  572     strm->state->pending_out  += len;
  573     strm->total_out += len;
  574     strm->avail_out  -= len;
  575     strm->state->pending -= len;
  576     if (strm->state->pending == 0) {
  577         strm->state->pending_out = strm->state->pending_buf;
  578     }
  579 }
  580 
  581 /* ========================================================================= */
  582 int ZEXPORT deflate (strm, flush)
  583     z_streamp strm;
  584     int flush;
  585 {
  586     int old_flush; /* value of flush param for previous deflate call */
  587     deflate_state *s;
  588 
  589     if (strm == Z_NULL || strm->state == Z_NULL ||
  590         flush > Z_BLOCK || flush < 0) {
  591         return Z_STREAM_ERROR;
  592     }
  593     s = strm->state;
  594 
  595     if (strm->next_out == Z_NULL ||
  596         (strm->next_in == Z_NULL && strm->avail_in != 0) ||
  597         (s->status == FINISH_STATE && flush != Z_FINISH)) {
  598         ERR_RETURN(strm, Z_STREAM_ERROR);
  599     }
  600     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
  601 
  602     s->strm = strm; /* just in case */
  603     old_flush = s->last_flush;
  604     s->last_flush = flush;
  605 
  606     /* Write the header */
  607     if (s->status == INIT_STATE) {
  608 #ifdef GZIP
  609         if (s->wrap == 2) {
  610             strm->adler = crc32(0L, Z_NULL, 0);
  611             put_byte(s, 31);
  612             put_byte(s, 139);
  613             put_byte(s, 8);
  614             if (s->gzhead == Z_NULL) {
  615                 put_byte(s, 0);
  616                 put_byte(s, 0);
  617                 put_byte(s, 0);
  618                 put_byte(s, 0);
  619                 put_byte(s, 0);
  620                 put_byte(s, s->level == 9 ? 2 :
  621                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
  622                              4 : 0));
  623                 put_byte(s, OS_CODE);
  624                 s->status = BUSY_STATE;
  625             }
  626             else {
  627                 put_byte(s, (s->gzhead->text ? 1 : 0) +
  628                             (s->gzhead->hcrc ? 2 : 0) +
  629                             (s->gzhead->extra == Z_NULL ? 0 : 4) +
  630                             (s->gzhead->name == Z_NULL ? 0 : 8) +
  631                             (s->gzhead->comment == Z_NULL ? 0 : 16)
  632                         );
  633                 put_byte(s, (Byte)(s->gzhead->time & 0xff));
  634                 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
  635                 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
  636                 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
  637                 put_byte(s, s->level == 9 ? 2 :
  638                             (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
  639                              4 : 0));
  640                 put_byte(s, s->gzhead->os & 0xff);
  641                 if (s->gzhead->extra != Z_NULL) {
  642                     put_byte(s, s->gzhead->extra_len & 0xff);
  643                     put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
  644                 }
  645                 if (s->gzhead->hcrc)
  646                     strm->adler = crc32(strm->adler, s->pending_buf,
  647                                         s->pending);
  648                 s->gzindex = 0;
  649                 s->status = EXTRA_STATE;
  650             }
  651         }
  652         else
  653 #endif
  654         {
  655             uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
  656             uInt level_flags;
  657 
  658             if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
  659                 level_flags = 0;
  660             else if (s->level < 6)
  661                 level_flags = 1;
  662             else if (s->level == 6)
  663                 level_flags = 2;
  664             else
  665                 level_flags = 3;
  666             header |= (level_flags << 6);
  667             if (s->strstart != 0) header |= PRESET_DICT;
  668             header += 31 - (header % 31);
  669 
  670             s->status = BUSY_STATE;
  671             putShortMSB(s, header);
  672 
  673             /* Save the adler32 of the preset dictionary: */
  674             if (s->strstart != 0) {
  675                 putShortMSB(s, (uInt)(strm->adler >> 16));
  676                 putShortMSB(s, (uInt)(strm->adler & 0xffff));
  677             }
  678             strm->adler = adler32(0L, Z_NULL, 0);
  679         }
  680     }
  681 #ifdef GZIP
  682     if (s->status == EXTRA_STATE) {
  683         if (s->gzhead->extra != Z_NULL) {
  684             uInt beg = s->pending;  /* start of bytes to update crc */
  685 
  686             while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
  687                 if (s->pending == s->pending_buf_size) {
  688                     if (s->gzhead->hcrc && s->pending > beg)
  689                         strm->adler = crc32(strm->adler, s->pending_buf + beg,
  690                                             s->pending - beg);
  691                     flush_pending(strm);
  692                     beg = s->pending;
  693                     if (s->pending == s->pending_buf_size)
  694                         break;
  695                 }
  696                 put_byte(s, s->gzhead->extra[s->gzindex]);
  697                 s->gzindex++;
  698             }
  699             if (s->gzhead->hcrc && s->pending > beg)
  700                 strm->adler = crc32(strm->adler, s->pending_buf + beg,
  701                                     s->pending - beg);
  702             if (s->gzindex == s->gzhead->extra_len) {
  703                 s->gzindex = 0;
  704                 s->status = NAME_STATE;
  705             }
  706         }
  707         else
  708             s->status = NAME_STATE;
  709     }
  710     if (s->status == NAME_STATE) {
  711         if (s->gzhead->name != Z_NULL) {
  712             uInt beg = s->pending;  /* start of bytes to update crc */
  713             int val;
  714 
  715             do {
  716                 if (s->pending == s->pending_buf_size) {
  717                     if (s->gzhead->hcrc && s->pending > beg)
  718                         strm->adler = crc32(strm->adler, s->pending_buf + beg,
  719                                             s->pending - beg);
  720                     flush_pending(strm);
  721                     beg = s->pending;
  722                     if (s->pending == s->pending_buf_size) {
  723                         val = 1;
  724                         break;
  725                     }
  726                 }
  727                 val = s->gzhead->name[s->gzindex++];
  728                 put_byte(s, val);
  729             } while (val != 0);
  730             if (s->gzhead->hcrc && s->pending > beg)
  731                 strm->adler = crc32(strm->adler, s->pending_buf + beg,
  732                                     s->pending - beg);
  733             if (val == 0) {
  734                 s->gzindex = 0;
  735                 s->status = COMMENT_STATE;
  736             }
  737         }
  738         else
  739             s->status = COMMENT_STATE;
  740     }
  741     if (s->status == COMMENT_STATE) {
  742         if (s->gzhead->comment != Z_NULL) {
  743             uInt beg = s->pending;  /* start of bytes to update crc */
  744             int val;
  745 
  746             do {
  747                 if (s->pending == s->pending_buf_size) {
  748                     if (s->gzhead->hcrc && s->pending > beg)
  749                         strm->adler = crc32(strm->adler, s->pending_buf + beg,
  750                                             s->pending - beg);
  751                     flush_pending(strm);
  752                     beg = s->pending;
  753                     if (s->pending == s->pending_buf_size) {
  754                         val = 1;
  755                         break;
  756                     }
  757                 }
  758                 val = s->gzhead->comment[s->gzindex++];
  759                 put_byte(s, val);
  760             } while (val != 0);
  761             if (s->gzhead->hcrc && s->pending > beg)
  762                 strm->adler = crc32(strm->adler, s->pending_buf + beg,
  763                                     s->pending - beg);
  764             if (val == 0)
  765                 s->status = HCRC_STATE;
  766         }
  767         else
  768             s->status = HCRC_STATE;
  769     }
  770     if (s->status == HCRC_STATE) {
  771         if (s->gzhead->hcrc) {
  772             if (s->pending + 2 > s->pending_buf_size)
  773                 flush_pending(strm);
  774             if (s->pending + 2 <= s->pending_buf_size) {
  775                 put_byte(s, (Byte)(strm->adler & 0xff));
  776                 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
  777                 strm->adler = crc32(0L, Z_NULL, 0);
  778                 s->status = BUSY_STATE;
  779             }
  780         }
  781         else
  782             s->status = BUSY_STATE;
  783     }
  784 #endif
  785 
  786     /* Flush as much pending output as possible */
  787     if (s->pending != 0) {
  788         flush_pending(strm);
  789         if (strm->avail_out == 0) {
  790             /* Since avail_out is 0, deflate will be called again with
  791              * more output space, but possibly with both pending and
  792              * avail_in equal to zero. There won't be anything to do,
  793              * but this is not an error situation so make sure we
  794              * return OK instead of BUF_ERROR at next call of deflate:
  795              */
  796             s->last_flush = -1;
  797             return Z_OK;
  798         }
  799 
  800     /* Make sure there is something to do and avoid duplicate consecutive
  801      * flushes. For repeated and useless calls with Z_FINISH, we keep
  802      * returning Z_STREAM_END instead of Z_BUF_ERROR.
  803      */
  804     } else if (strm->avail_in == 0 && flush <= old_flush &&
  805                flush != Z_FINISH) {
  806         ERR_RETURN(strm, Z_BUF_ERROR);
  807     }
  808 
  809     /* User must not provide more input after the first FINISH: */
  810     if (s->status == FINISH_STATE && strm->avail_in != 0) {
  811         ERR_RETURN(strm, Z_BUF_ERROR);
  812     }
  813 
  814     /* Start a new block or continue the current one.
  815      */
  816     if (strm->avail_in != 0 || s->lookahead != 0 ||
  817         (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
  818         block_state bstate;
  819 
  820         bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
  821                     (s->strategy == Z_RLE ? deflate_rle(s, flush) :
  822                         (*(configuration_table[s->level].func))(s, flush));
  823 
  824         if (bstate == finish_started || bstate == finish_done) {
  825             s->status = FINISH_STATE;
  826         }
  827         if (bstate == need_more || bstate == finish_started) {
  828             if (strm->avail_out == 0) {
  829                 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
  830             }
  831             return Z_OK;
  832             /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
  833              * of deflate should use the same flush parameter to make sure
  834              * that the flush is complete. So we don't have to output an
  835              * empty block here, this will be done at next call. This also
  836              * ensures that for a very small output buffer, we emit at most
  837              * one empty block.
  838              */
  839         }
  840         if (bstate == block_done) {
  841             if (flush == Z_PARTIAL_FLUSH) {
  842                 _tr_align(s);
  843             } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
  844                 _tr_stored_block(s, (char*)0, 0L, 0);
  845                 /* For a full flush, this empty block will be recognized
  846                  * as a special marker by inflate_sync().
  847                  */
  848                 if (flush == Z_FULL_FLUSH) {
  849                     CLEAR_HASH(s);             /* forget history */
  850                     if (s->lookahead == 0) {
  851                         s->strstart = 0;
  852                         s->block_start = 0L;
  853                     }
  854                 }
  855             }
  856             flush_pending(strm);
  857             if (strm->avail_out == 0) {
  858               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
  859               return Z_OK;
  860             }
  861         }
  862     }
  863     Assert(strm->avail_out > 0, "bug2");
  864 
  865     if (flush != Z_FINISH) return Z_OK;
  866     if (s->wrap <= 0) return Z_STREAM_END;
  867 
  868     /* Write the trailer */
  869 #ifdef GZIP
  870     if (s->wrap == 2) {
  871         put_byte(s, (Byte)(strm->adler & 0xff));
  872         put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
  873         put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
  874         put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
  875         put_byte(s, (Byte)(strm->total_in & 0xff));
  876         put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
  877         put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
  878         put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
  879     }
  880     else
  881 #endif
  882     {
  883         putShortMSB(s, (uInt)(strm->adler >> 16));
  884         putShortMSB(s, (uInt)(strm->adler & 0xffff));
  885     }
  886     flush_pending(strm);
  887     /* If avail_out is zero, the application will call deflate again
  888      * to flush the rest.
  889      */
  890     if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
  891     return s->pending != 0 ? Z_OK : Z_STREAM_END;
  892 }
  893 
  894 /* ========================================================================= */
  895 int ZEXPORT deflateEnd (strm)
  896     z_streamp strm;
  897 {
  898     int status;
  899 
  900     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  901 
  902     status = strm->state->status;
  903     if (status != INIT_STATE &&
  904         status != EXTRA_STATE &&
  905         status != NAME_STATE &&
  906         status != COMMENT_STATE &&
  907         status != HCRC_STATE &&
  908         status != BUSY_STATE &&
  909         status != FINISH_STATE) {
  910       return Z_STREAM_ERROR;
  911     }
  912 
  913     /* Deallocate in reverse order of allocations: */
  914     TRY_FREE(strm, strm->state->pending_buf);
  915     TRY_FREE(strm, strm->state->head);
  916     TRY_FREE(strm, strm->state->prev);
  917     TRY_FREE(strm, strm->state->window);
  918 
  919     ZFREE(strm, strm->state);
  920     strm->state = Z_NULL;
  921 
  922     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
  923 }
  924 
  925 /* =========================================================================
  926  * Copy the source state to the destination state.
  927  * To simplify the source, this is not supported for 16-bit MSDOS (which
  928  * doesn't have enough memory anyway to duplicate compression states).
  929  */
  930 int ZEXPORT deflateCopy (dest, source)
  931     z_streamp dest;
  932     z_streamp source;
  933 {
  934 #ifdef MAXSEG_64K
  935     return Z_STREAM_ERROR;
  936 #else
  937     deflate_state *ds;
  938     deflate_state *ss;
  939     ushf *overlay;
  940 
  941 
  942     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
  943         return Z_STREAM_ERROR;
  944     }
  945 
  946     ss = source->state;
  947 
  948     zmemcpy(dest, source, sizeof(z_stream));
  949 
  950     ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
  951     if (ds == Z_NULL) return Z_MEM_ERROR;
  952     dest->state = (struct internal_state FAR *) ds;
  953     zmemcpy(ds, ss, sizeof(deflate_state));
  954     ds->strm = dest;
  955 
  956     ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
  957     ds->prev   = (Posf *)  ZALLOC(dest, ds->w_size, sizeof(Pos));
  958     ds->head   = (Posf *)  ZALLOC(dest, ds->hash_size, sizeof(Pos));
  959     overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
  960     ds->pending_buf = (uchf *) overlay;
  961 
  962     if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
  963         ds->pending_buf == Z_NULL) {
  964         deflateEnd (dest);
  965         return Z_MEM_ERROR;
  966     }
  967     /* following zmemcpy do not work for 16-bit MSDOS */
  968     zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
  969     zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
  970     zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
  971     zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
  972 
  973     ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
  974     ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
  975     ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
  976 
  977     ds->l_desc.dyn_tree = ds->dyn_ltree;
  978     ds->d_desc.dyn_tree = ds->dyn_dtree;
  979     ds->bl_desc.dyn_tree = ds->bl_tree;
  980 
  981     return Z_OK;
  982 #endif /* MAXSEG_64K */
  983 }
  984 
  985 /* ===========================================================================
  986  * Read a new buffer from the current input stream, update the adler32
  987  * and total number of bytes read.  All deflate() input goes through
  988  * this function so some applications may wish to modify it to avoid
  989  * allocating a large strm->next_in buffer and copying from it.
  990  * (See also flush_pending()).
  991  */
  992 local int read_buf(strm, buf, size)
  993     z_streamp strm;
  994     Bytef *buf;
  995     unsigned size;
  996 {
  997     unsigned len = strm->avail_in;
  998 
  999     if (len > size) len = size;
 1000     if (len == 0) return 0;
 1001 
 1002     strm->avail_in  -= len;
 1003 
 1004     if (strm->state->wrap == 1) {
 1005         strm->adler = adler32(strm->adler, strm->next_in, len);
 1006     }
 1007 #ifdef GZIP
 1008     else if (strm->state->wrap == 2) {
 1009         strm->adler = crc32(strm->adler, strm->next_in, len);
 1010     }
 1011 #endif
 1012     zmemcpy(buf, strm->next_in, len);
 1013     strm->next_in  += len;
 1014     strm->total_in += len;
 1015 
 1016     return (int)len;
 1017 }
 1018 
 1019 /* ===========================================================================
 1020  * Initialize the "longest match" routines for a new zlib stream
 1021  */
 1022 local void lm_init (s)
 1023     deflate_state *s;
 1024 {
 1025     s->window_size = (ulg)2L*s->w_size;
 1026 
 1027     CLEAR_HASH(s);
 1028 
 1029     /* Set the default configuration parameters:
 1030      */
 1031     s->max_lazy_match   = configuration_table[s->level].max_lazy;
 1032     s->good_match       = configuration_table[s->level].good_length;
 1033     s->nice_match       = configuration_table[s->level].nice_length;
 1034     s->max_chain_length = configuration_table[s->level].max_chain;
 1035 
 1036     s->strstart = 0;
 1037     s->block_start = 0L;
 1038     s->lookahead = 0;
 1039     s->match_length = s->prev_length = MIN_MATCH-1;
 1040     s->match_available = 0;
 1041     s->ins_h = 0;
 1042 #ifndef FASTEST
 1043 #ifdef ASMV
 1044     match_init(); /* initialize the asm code */
 1045 #endif
 1046 #endif
 1047 }
 1048 
 1049 #ifndef FASTEST
 1050 /* ===========================================================================
 1051  * Set match_start to the longest match starting at the given string and
 1052  * return its length. Matches shorter or equal to prev_length are discarded,
 1053  * in which case the result is equal to prev_length and match_start is
 1054  * garbage.
 1055  * IN assertions: cur_match is the head of the hash chain for the current
 1056  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 1057  * OUT assertion: the match length is not greater than s->lookahead.
 1058  */
 1059 #ifndef ASMV
 1060 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
 1061  * match.S. The code will be functionally equivalent.
 1062  */
 1063 local uInt longest_match(s, cur_match)
 1064     deflate_state *s;
 1065     IPos cur_match;                             /* current match */
 1066 {
 1067     unsigned chain_length = s->max_chain_length;/* max hash chain length */
 1068     register Bytef *scan = s->window + s->strstart; /* current string */
 1069     register Bytef *match;                       /* matched string */
 1070     register int len;                           /* length of current match */
 1071     int best_len = s->prev_length;              /* best match length so far */
 1072     int nice_match = s->nice_match;             /* stop if match long enough */
 1073     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
 1074         s->strstart - (IPos)MAX_DIST(s) : NIL;
 1075     /* Stop when cur_match becomes <= limit. To simplify the code,
 1076      * we prevent matches with the string of window index 0.
 1077      */
 1078     Posf *prev = s->prev;
 1079     uInt wmask = s->w_mask;
 1080 
 1081 #ifdef UNALIGNED_OK
 1082     /* Compare two bytes at a time. Note: this is not always beneficial.
 1083      * Try with and without -DUNALIGNED_OK to check.
 1084      */
 1085     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
 1086     register ush scan_start = *(ushf*)scan;
 1087     register ush scan_end   = *(ushf*)(scan+best_len-1);
 1088 #else
 1089     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
 1090     register Byte scan_end1  = scan[best_len-1];
 1091     register Byte scan_end   = scan[best_len];
 1092 #endif
 1093 
 1094     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
 1095      * It is easy to get rid of this optimization if necessary.
 1096      */
 1097     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
 1098 
 1099     /* Do not waste too much time if we already have a good match: */
 1100     if (s->prev_length >= s->good_match) {
 1101         chain_length >>= 2;
 1102     }
 1103     /* Do not look for matches beyond the end of the input. This is necessary
 1104      * to make deflate deterministic.
 1105      */
 1106     if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
 1107 
 1108     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
 1109 
 1110     do {
 1111         Assert(cur_match < s->strstart, "no future");
 1112         match = s->window + cur_match;
 1113 
 1114         /* Skip to next match if the match length cannot increase
 1115          * or if the match length is less than 2.  Note that the checks below
 1116          * for insufficient lookahead only occur occasionally for performance
 1117          * reasons.  Therefore uninitialized memory will be accessed, and
 1118          * conditional jumps will be made that depend on those values.
 1119          * However the length of the match is limited to the lookahead, so
 1120          * the output of deflate is not affected by the uninitialized values.
 1121          */
 1122 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
 1123         /* This code assumes sizeof(unsigned short) == 2. Do not use
 1124          * UNALIGNED_OK if your compiler uses a different size.
 1125          */
 1126         if (*(ushf*)(match+best_len-1) != scan_end ||
 1127             *(ushf*)match != scan_start) continue;
 1128 
 1129         /* It is not necessary to compare scan[2] and match[2] since they are
 1130          * always equal when the other bytes match, given that the hash keys
 1131          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
 1132          * strstart+3, +5, ... up to strstart+257. We check for insufficient
 1133          * lookahead only every 4th comparison; the 128th check will be made
 1134          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
 1135          * necessary to put more guard bytes at the end of the window, or
 1136          * to check more often for insufficient lookahead.
 1137          */
 1138         Assert(scan[2] == match[2], "scan[2]?");
 1139         scan++, match++;
 1140         do {
 1141         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1142                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1143                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1144                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
 1145                  scan < strend);
 1146         /* The funny "do {}" generates better code on most compilers */
 1147 
 1148         /* Here, scan <= window+strstart+257 */
 1149         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
 1150         if (*scan == *match) scan++;
 1151 
 1152         len = (MAX_MATCH - 1) - (int)(strend-scan);
 1153         scan = strend - (MAX_MATCH-1);
 1154 
 1155 #else /* UNALIGNED_OK */
 1156 
 1157         if (match[best_len]   != scan_end  ||
 1158             match[best_len-1] != scan_end1 ||
 1159             *match            != *scan     ||
 1160             *++match          != scan[1])      continue;
 1161 
 1162         /* The check at best_len-1 can be removed because it will be made
 1163          * again later. (This heuristic is not always a win.)
 1164          * It is not necessary to compare scan[2] and match[2] since they
 1165          * are always equal when the other bytes match, given that
 1166          * the hash keys are equal and that HASH_BITS >= 8.
 1167          */
 1168         scan += 2, match++;
 1169         Assert(*scan == *match, "match[2]?");
 1170 
 1171         /* We check for insufficient lookahead only every 8th comparison;
 1172          * the 256th check will be made at strstart+258.
 1173          */
 1174         do {
 1175         } while (*++scan == *++match && *++scan == *++match &&
 1176                  *++scan == *++match && *++scan == *++match &&
 1177                  *++scan == *++match && *++scan == *++match &&
 1178                  *++scan == *++match && *++scan == *++match &&
 1179                  scan < strend);
 1180 
 1181         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
 1182 
 1183         len = MAX_MATCH - (int)(strend - scan);
 1184         scan = strend - MAX_MATCH;
 1185 
 1186 #endif /* UNALIGNED_OK */
 1187 
 1188         if (len > best_len) {
 1189             s->match_start = cur_match;
 1190             best_len = len;
 1191             if (len >= nice_match) break;
 1192 #ifdef UNALIGNED_OK
 1193             scan_end = *(ushf*)(scan+best_len-1);
 1194 #else
 1195             scan_end1  = scan[best_len-1];
 1196             scan_end   = scan[best_len];
 1197 #endif
 1198         }
 1199     } while ((cur_match = prev[cur_match & wmask]) > limit
 1200              && --chain_length != 0);
 1201 
 1202     if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
 1203     return s->lookahead;
 1204 }
 1205 #endif /* ASMV */
 1206 
 1207 #else /* FASTEST */
 1208 
 1209 /* ---------------------------------------------------------------------------
 1210  * Optimized version for FASTEST only
 1211  */
 1212 local uInt longest_match(s, cur_match)
 1213     deflate_state *s;
 1214     IPos cur_match;                             /* current match */
 1215 {
 1216     register Bytef *scan = s->window + s->strstart; /* current string */
 1217     register Bytef *match;                       /* matched string */
 1218     register int len;                           /* length of current match */
 1219     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
 1220 
 1221     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
 1222      * It is easy to get rid of this optimization if necessary.
 1223      */
 1224     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
 1225 
 1226     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
 1227 
 1228     Assert(cur_match < s->strstart, "no future");
 1229 
 1230     match = s->window + cur_match;
 1231 
 1232     /* Return failure if the match length is less than 2:
 1233      */
 1234     if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
 1235 
 1236     /* The check at best_len-1 can be removed because it will be made
 1237      * again later. (This heuristic is not always a win.)
 1238      * It is not necessary to compare scan[2] and match[2] since they
 1239      * are always equal when the other bytes match, given that
 1240      * the hash keys are equal and that HASH_BITS >= 8.
 1241      */
 1242     scan += 2, match += 2;
 1243     Assert(*scan == *match, "match[2]?");
 1244 
 1245     /* We check for insufficient lookahead only every 8th comparison;
 1246      * the 256th check will be made at strstart+258.
 1247      */
 1248     do {
 1249     } while (*++scan == *++match && *++scan == *++match &&
 1250              *++scan == *++match && *++scan == *++match &&
 1251              *++scan == *++match && *++scan == *++match &&
 1252              *++scan == *++match && *++scan == *++match &&
 1253              scan < strend);
 1254 
 1255     Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
 1256 
 1257     len = MAX_MATCH - (int)(strend - scan);
 1258 
 1259     if (len < MIN_MATCH) return MIN_MATCH - 1;
 1260 
 1261     s->match_start = cur_match;
 1262     return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
 1263 }
 1264 
 1265 #endif /* FASTEST */
 1266 
 1267 #ifdef DEBUG
 1268 /* ===========================================================================
 1269  * Check that the match at match_start is indeed a match.
 1270  */
 1271 local void check_match(s, start, match, length)
 1272     deflate_state *s;
 1273     IPos start, match;
 1274     int length;
 1275 {
 1276     /* check that the match is indeed a match */
 1277     if (zmemcmp(s->window + match,
 1278                 s->window + start, length) != EQUAL) {
 1279         fprintf(stderr, " start %u, match %u, length %d\n",
 1280                 start, match, length);
 1281         do {
 1282             fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
 1283         } while (--length != 0);
 1284         z_error("invalid match");
 1285     }
 1286     if (z_verbose > 1) {
 1287         fprintf(stderr,"\\[%d,%d]", start-match, length);
 1288         do { putc(s->window[start++], stderr); } while (--length != 0);
 1289     }
 1290 }
 1291 #else
 1292 #  define check_match(s, start, match, length)
 1293 #endif /* DEBUG */
 1294 
 1295 /* ===========================================================================
 1296  * Fill the window when the lookahead becomes insufficient.
 1297  * Updates strstart and lookahead.
 1298  *
 1299  * IN assertion: lookahead < MIN_LOOKAHEAD
 1300  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
 1301  *    At least one byte has been read, or avail_in == 0; reads are
 1302  *    performed for at least two bytes (required for the zip translate_eol
 1303  *    option -- not supported here).
 1304  */
 1305 local void fill_window(s)
 1306     deflate_state *s;
 1307 {
 1308     register unsigned n, m;
 1309     register Posf *p;
 1310     unsigned more;    /* Amount of free space at the end of the window. */
 1311     uInt wsize = s->w_size;
 1312 
 1313     do {
 1314         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
 1315 
 1316         /* Deal with !@#$% 64K limit: */
 1317         if (sizeof(int) <= 2) {
 1318             if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
 1319                 more = wsize;
 1320 
 1321             } else if (more == (unsigned)(-1)) {
 1322                 /* Very unlikely, but possible on 16 bit machine if
 1323                  * strstart == 0 && lookahead == 1 (input done a byte at time)
 1324                  */
 1325                 more--;
 1326             }
 1327         }
 1328 
 1329         /* If the window is almost full and there is insufficient lookahead,
 1330          * move the upper half to the lower one to make room in the upper half.
 1331          */
 1332         if (s->strstart >= wsize+MAX_DIST(s)) {
 1333 
 1334             zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
 1335             s->match_start -= wsize;
 1336             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
 1337             s->block_start -= (long) wsize;
 1338 
 1339             /* Slide the hash table (could be avoided with 32 bit values
 1340                at the expense of memory usage). We slide even when level == 0
 1341                to keep the hash table consistent if we switch back to level > 0
 1342                later. (Using level 0 permanently is not an optimal usage of
 1343                zlib, so we don't care about this pathological case.)
 1344              */
 1345             n = s->hash_size;
 1346             p = &s->head[n];
 1347             do {
 1348                 m = *--p;
 1349                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
 1350             } while (--n);
 1351 
 1352             n = wsize;
 1353 #ifndef FASTEST
 1354             p = &s->prev[n];
 1355             do {
 1356                 m = *--p;
 1357                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
 1358                 /* If n is not on any hash chain, prev[n] is garbage but
 1359                  * its value will never be used.
 1360                  */
 1361             } while (--n);
 1362 #endif
 1363             more += wsize;
 1364         }
 1365         if (s->strm->avail_in == 0) return;
 1366 
 1367         /* If there was no sliding:
 1368          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
 1369          *    more == window_size - lookahead - strstart
 1370          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
 1371          * => more >= window_size - 2*WSIZE + 2
 1372          * In the BIG_MEM or MMAP case (not yet supported),
 1373          *   window_size == input_size + MIN_LOOKAHEAD  &&
 1374          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
 1375          * Otherwise, window_size == 2*WSIZE so more >= 2.
 1376          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
 1377          */
 1378         Assert(more >= 2, "more < 2");
 1379 
 1380         n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
 1381         s->lookahead += n;
 1382 
 1383         /* Initialize the hash value now that we have some input: */
 1384         if (s->lookahead >= MIN_MATCH) {
 1385             s->ins_h = s->window[s->strstart];
 1386             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
 1387 #if MIN_MATCH != 3
 1388             Call UPDATE_HASH() MIN_MATCH-3 more times
 1389 #endif
 1390         }
 1391         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
 1392          * but this is not important since only literal bytes will be emitted.
 1393          */
 1394 
 1395     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
 1396 
 1397     /* If the WIN_INIT bytes after the end of the current data have never been
 1398      * written, then zero those bytes in order to avoid memory check reports of
 1399      * the use of uninitialized (or uninitialised as Julian writes) bytes by
 1400      * the longest match routines.  Update the high water mark for the next
 1401      * time through here.  WIN_INIT is set to MAX_MATCH since the longest match
 1402      * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
 1403      */
 1404     if (s->high_water < s->window_size) {
 1405         ulg curr = s->strstart + (ulg)(s->lookahead);
 1406         ulg init;
 1407 
 1408         if (s->high_water < curr) {
 1409             /* Previous high water mark below current data -- zero WIN_INIT
 1410              * bytes or up to end of window, whichever is less.
 1411              */
 1412             init = s->window_size - curr;
 1413             if (init > WIN_INIT)
 1414                 init = WIN_INIT;
 1415             zmemzero(s->window + curr, (unsigned)init);
 1416             s->high_water = curr + init;
 1417         }
 1418         else if (s->high_water < (ulg)curr + WIN_INIT) {
 1419             /* High water mark at or above current data, but below current data
 1420              * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
 1421              * to end of window, whichever is less.
 1422              */
 1423             init = (ulg)curr + WIN_INIT - s->high_water;
 1424             if (init > s->window_size - s->high_water)
 1425                 init = s->window_size - s->high_water;
 1426             zmemzero(s->window + s->high_water, (unsigned)init);
 1427             s->high_water += init;
 1428         }
 1429     }
 1430 }
 1431 
 1432 /* ===========================================================================
 1433  * Flush the current block, with given end-of-file flag.
 1434  * IN assertion: strstart is set to the end of the current match.
 1435  */
 1436 #define FLUSH_BLOCK_ONLY(s, last) { \
 1437    _tr_flush_block(s, (s->block_start >= 0L ? \
 1438                    (charf *)&s->window[(unsigned)s->block_start] : \
 1439                    (charf *)Z_NULL), \
 1440                 (ulg)((long)s->strstart - s->block_start), \
 1441                 (last)); \
 1442    s->block_start = s->strstart; \
 1443    flush_pending(s->strm); \
 1444    Tracev((stderr,"[FLUSH]")); \
 1445 }
 1446 
 1447 /* Same but force premature exit if necessary. */
 1448 #define FLUSH_BLOCK(s, last) { \
 1449    FLUSH_BLOCK_ONLY(s, last); \
 1450    if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
 1451 }
 1452 
 1453 /* ===========================================================================
 1454  * Copy without compression as much as possible from the input stream, return
 1455  * the current block state.
 1456  * This function does not insert new strings in the dictionary since
 1457  * uncompressible data is probably not useful. This function is used
 1458  * only for the level=0 compression option.
 1459  * NOTE: this function should be optimized to avoid extra copying from
 1460  * window to pending_buf.
 1461  */
 1462 local block_state deflate_stored(s, flush)
 1463     deflate_state *s;
 1464     int flush;
 1465 {
 1466     /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
 1467      * to pending_buf_size, and each stored block has a 5 byte header:
 1468      */
 1469     ulg max_block_size = 0xffff;
 1470     ulg max_start;
 1471 
 1472     if (max_block_size > s->pending_buf_size - 5) {
 1473         max_block_size = s->pending_buf_size - 5;
 1474     }
 1475 
 1476     /* Copy as much as possible from input to output: */
 1477     for (;;) {
 1478         /* Fill the window as much as possible: */
 1479         if (s->lookahead <= 1) {
 1480 
 1481             Assert(s->strstart < s->w_size+MAX_DIST(s) ||
 1482                    s->block_start >= (long)s->w_size, "slide too late");
 1483 
 1484             fill_window(s);
 1485             if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
 1486 
 1487             if (s->lookahead == 0) break; /* flush the current block */
 1488         }
 1489         Assert(s->block_start >= 0L, "block gone");
 1490 
 1491         s->strstart += s->lookahead;
 1492         s->lookahead = 0;
 1493 
 1494         /* Emit a stored block if pending_buf will be full: */
 1495         max_start = s->block_start + max_block_size;
 1496         if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
 1497             /* strstart == 0 is possible when wraparound on 16-bit machine */
 1498             s->lookahead = (uInt)(s->strstart - max_start);
 1499             s->strstart = (uInt)max_start;
 1500             FLUSH_BLOCK(s, 0);
 1501         }
 1502         /* Flush if we may have to slide, otherwise block_start may become
 1503          * negative and the data will be gone:
 1504          */
 1505         if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
 1506             FLUSH_BLOCK(s, 0);
 1507         }
 1508     }
 1509     FLUSH_BLOCK(s, flush == Z_FINISH);
 1510     return flush == Z_FINISH ? finish_done : block_done;
 1511 }
 1512 
 1513 /* ===========================================================================
 1514  * Compress as much as possible from the input stream, return the current
 1515  * block state.
 1516  * This function does not perform lazy evaluation of matches and inserts
 1517  * new strings in the dictionary only for unmatched strings or for short
 1518  * matches. It is used only for the fast compression options.
 1519  */
 1520 local block_state deflate_fast(s, flush)
 1521     deflate_state *s;
 1522     int flush;
 1523 {
 1524     IPos hash_head;       /* head of the hash chain */
 1525     int bflush;           /* set if current block must be flushed */
 1526 
 1527     for (;;) {
 1528         /* Make sure that we always have enough lookahead, except
 1529          * at the end of the input file. We need MAX_MATCH bytes
 1530          * for the next match, plus MIN_MATCH bytes to insert the
 1531          * string following the next match.
 1532          */
 1533         if (s->lookahead < MIN_LOOKAHEAD) {
 1534             fill_window(s);
 1535             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
 1536                 return need_more;
 1537             }
 1538             if (s->lookahead == 0) break; /* flush the current block */
 1539         }
 1540 
 1541         /* Insert the string window[strstart .. strstart+2] in the
 1542          * dictionary, and set hash_head to the head of the hash chain:
 1543          */
 1544         hash_head = NIL;
 1545         if (s->lookahead >= MIN_MATCH) {
 1546             INSERT_STRING(s, s->strstart, hash_head);
 1547         }
 1548 
 1549         /* Find the longest match, discarding those <= prev_length.
 1550          * At this point we have always match_length < MIN_MATCH
 1551          */
 1552         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
 1553             /* To simplify the code, we prevent matches with the string
 1554              * of window index 0 (in particular we have to avoid a match
 1555              * of the string with itself at the start of the input file).
 1556              */
 1557             s->match_length = longest_match (s, hash_head);
 1558             /* longest_match() sets match_start */
 1559         }
 1560         if (s->match_length >= MIN_MATCH) {
 1561             check_match(s, s->strstart, s->match_start, s->match_length);
 1562 
 1563             _tr_tally_dist(s, s->strstart - s->match_start,
 1564                            s->match_length - MIN_MATCH, bflush);
 1565 
 1566             s->lookahead -= s->match_length;
 1567 
 1568             /* Insert new strings in the hash table only if the match length
 1569              * is not too large. This saves time but degrades compression.
 1570              */
 1571 #ifndef FASTEST
 1572             if (s->match_length <= s->max_insert_length &&
 1573                 s->lookahead >= MIN_MATCH) {
 1574                 s->match_length--; /* string at strstart already in table */
 1575                 do {
 1576                     s->strstart++;
 1577                     INSERT_STRING(s, s->strstart, hash_head);
 1578                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
 1579                      * always MIN_MATCH bytes ahead.
 1580                      */
 1581                 } while (--s->match_length != 0);
 1582                 s->strstart++;
 1583             } else
 1584 #endif
 1585             {
 1586                 s->strstart += s->match_length;
 1587                 s->match_length = 0;
 1588                 s->ins_h = s->window[s->strstart];
 1589                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
 1590 #if MIN_MATCH != 3
 1591                 Call UPDATE_HASH() MIN_MATCH-3 more times
 1592 #endif
 1593                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
 1594                  * matter since it will be recomputed at next deflate call.
 1595                  */
 1596             }
 1597         } else {
 1598             /* No match, output a literal byte */
 1599             Tracevv((stderr,"%c", s->window[s->strstart]));
 1600             _tr_tally_lit (s, s->window[s->strstart], bflush);
 1601             s->lookahead--;
 1602             s->strstart++;
 1603         }
 1604         if (bflush) FLUSH_BLOCK(s, 0);
 1605     }
 1606     FLUSH_BLOCK(s, flush == Z_FINISH);
 1607     return flush == Z_FINISH ? finish_done : block_done;
 1608 }
 1609 
 1610 #ifndef FASTEST
 1611 /* ===========================================================================
 1612  * Same as above, but achieves better compression. We use a lazy
 1613  * evaluation for matches: a match is finally adopted only if there is
 1614  * no better match at the next window position.
 1615  */
 1616 local block_state deflate_slow(s, flush)
 1617     deflate_state *s;
 1618     int flush;
 1619 {
 1620     IPos hash_head;          /* head of hash chain */
 1621     int bflush;              /* set if current block must be flushed */
 1622 
 1623     /* Process the input block. */
 1624     for (;;) {
 1625         /* Make sure that we always have enough lookahead, except
 1626          * at the end of the input file. We need MAX_MATCH bytes
 1627          * for the next match, plus MIN_MATCH bytes to insert the
 1628          * string following the next match.
 1629          */
 1630         if (s->lookahead < MIN_LOOKAHEAD) {
 1631             fill_window(s);
 1632             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
 1633                 return need_more;
 1634             }
 1635             if (s->lookahead == 0) break; /* flush the current block */
 1636         }
 1637 
 1638         /* Insert the string window[strstart .. strstart+2] in the
 1639          * dictionary, and set hash_head to the head of the hash chain:
 1640          */
 1641         hash_head = NIL;
 1642         if (s->lookahead >= MIN_MATCH) {
 1643             INSERT_STRING(s, s->strstart, hash_head);
 1644         }
 1645 
 1646         /* Find the longest match, discarding those <= prev_length.
 1647          */
 1648         s->prev_length = s->match_length, s->prev_match = s->match_start;
 1649         s->match_length = MIN_MATCH-1;
 1650 
 1651         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
 1652             s->strstart - hash_head <= MAX_DIST(s)) {
 1653             /* To simplify the code, we prevent matches with the string
 1654              * of window index 0 (in particular we have to avoid a match
 1655              * of the string with itself at the start of the input file).
 1656              */
 1657             s->match_length = longest_match (s, hash_head);
 1658             /* longest_match() sets match_start */
 1659 
 1660             if (s->match_length <= 5 && (s->strategy == Z_FILTERED
 1661 #if TOO_FAR <= 32767
 1662                 || (s->match_length == MIN_MATCH &&
 1663                     s->strstart - s->match_start > TOO_FAR)
 1664 #endif
 1665                 )) {
 1666 
 1667                 /* If prev_match is also MIN_MATCH, match_start is garbage
 1668                  * but we will ignore the current match anyway.
 1669                  */
 1670                 s->match_length = MIN_MATCH-1;
 1671             }
 1672         }
 1673         /* If there was a match at the previous step and the current
 1674          * match is not better, output the previous match:
 1675          */
 1676         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
 1677             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
 1678             /* Do not insert strings in hash table beyond this. */
 1679 
 1680             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
 1681 
 1682             _tr_tally_dist(s, s->strstart -1 - s->prev_match,
 1683                            s->prev_length - MIN_MATCH, bflush);
 1684 
 1685             /* Insert in hash table all strings up to the end of the match.
 1686              * strstart-1 and strstart are already inserted. If there is not
 1687              * enough lookahead, the last two strings are not inserted in
 1688              * the hash table.
 1689              */
 1690             s->lookahead -= s->prev_length-1;
 1691             s->prev_length -= 2;
 1692             do {
 1693                 if (++s->strstart <= max_insert) {
 1694                     INSERT_STRING(s, s->strstart, hash_head);
 1695                 }
 1696             } while (--s->prev_length != 0);
 1697             s->match_available = 0;
 1698             s->match_length = MIN_MATCH-1;
 1699             s->strstart++;
 1700 
 1701             if (bflush) FLUSH_BLOCK(s, 0);
 1702 
 1703         } else if (s->match_available) {
 1704             /* If there was no match at the previous position, output a
 1705              * single literal. If there was a match but the current match
 1706              * is longer, truncate the previous match to a single literal.
 1707              */
 1708             Tracevv((stderr,"%c", s->window[s->strstart-1]));
 1709             _tr_tally_lit(s, s->window[s->strstart-1], bflush);
 1710             if (bflush) {
 1711                 FLUSH_BLOCK_ONLY(s, 0);
 1712             }
 1713             s->strstart++;
 1714             s->lookahead--;
 1715             if (s->strm->avail_out == 0) return need_more;
 1716         } else {
 1717             /* There is no previous match to compare with, wait for
 1718              * the next step to decide.
 1719              */
 1720             s->match_available = 1;
 1721             s->strstart++;
 1722             s->lookahead--;
 1723         }
 1724     }
 1725     Assert (flush != Z_NO_FLUSH, "no flush?");
 1726     if (s->match_available) {
 1727         Tracevv((stderr,"%c", s->window[s->strstart-1]));
 1728         _tr_tally_lit(s, s->window[s->strstart-1], bflush);
 1729         s->match_available = 0;
 1730     }
 1731     FLUSH_BLOCK(s, flush == Z_FINISH);
 1732     return flush == Z_FINISH ? finish_done : block_done;
 1733 }
 1734 #endif /* FASTEST */
 1735 
 1736 /* ===========================================================================
 1737  * For Z_RLE, simply look for runs of bytes, generate matches only of distance
 1738  * one.  Do not maintain a hash table.  (It will be regenerated if this run of
 1739  * deflate switches away from Z_RLE.)
 1740  */
 1741 local block_state deflate_rle(s, flush)
 1742     deflate_state *s;
 1743     int flush;
 1744 {
 1745     int bflush;             /* set if current block must be flushed */
 1746     uInt prev;              /* byte at distance one to match */
 1747     Bytef *scan, *strend;   /* scan goes up to strend for length of run */
 1748 
 1749     for (;;) {
 1750         /* Make sure that we always have enough lookahead, except
 1751          * at the end of the input file. We need MAX_MATCH bytes
 1752          * for the longest encodable run.
 1753          */
 1754         if (s->lookahead < MAX_MATCH) {
 1755             fill_window(s);
 1756             if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) {
 1757                 return need_more;
 1758             }
 1759             if (s->lookahead == 0) break; /* flush the current block */
 1760         }
 1761 
 1762         /* See how many times the previous byte repeats */
 1763         s->match_length = 0;
 1764         if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
 1765             scan = s->window + s->strstart - 1;
 1766             prev = *scan;
 1767             if (prev == *++scan && prev == *++scan && prev == *++scan) {
 1768                 strend = s->window + s->strstart + MAX_MATCH;
 1769                 do {
 1770                 } while (prev == *++scan && prev == *++scan &&
 1771                          prev == *++scan && prev == *++scan &&
 1772                          prev == *++scan && prev == *++scan &&
 1773                          prev == *++scan && prev == *++scan &&
 1774                          scan < strend);
 1775                 s->match_length = MAX_MATCH - (int)(strend - scan);
 1776                 if (s->match_length > s->lookahead)
 1777                     s->match_length = s->lookahead;
 1778             }
 1779         }
 1780 
 1781         /* Emit match if have run of MIN_MATCH or longer, else emit literal */
 1782         if (s->match_length >= MIN_MATCH) {
 1783             check_match(s, s->strstart, s->strstart - 1, s->match_length);
 1784 
 1785             _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
 1786 
 1787             s->lookahead -= s->match_length;
 1788             s->strstart += s->match_length;
 1789             s->match_length = 0;
 1790         } else {
 1791             /* No match, output a literal byte */
 1792             Tracevv((stderr,"%c", s->window[s->strstart]));
 1793             _tr_tally_lit (s, s->window[s->strstart], bflush);
 1794             s->lookahead--;
 1795             s->strstart++;
 1796         }
 1797         if (bflush) FLUSH_BLOCK(s, 0);
 1798     }
 1799     FLUSH_BLOCK(s, flush == Z_FINISH);
 1800     return flush == Z_FINISH ? finish_done : block_done;
 1801 }
 1802 
 1803 /* ===========================================================================
 1804  * For Z_HUFFMAN_ONLY, do not look for matches.  Do not maintain a hash table.
 1805  * (It will be regenerated if this run of deflate switches away from Huffman.)
 1806  */
 1807 local block_state deflate_huff(s, flush)
 1808     deflate_state *s;
 1809     int flush;
 1810 {
 1811     int bflush;             /* set if current block must be flushed */
 1812 
 1813     for (;;) {
 1814         /* Make sure that we have a literal to write. */
 1815         if (s->lookahead == 0) {
 1816             fill_window(s);
 1817             if (s->lookahead == 0) {
 1818                 if (flush == Z_NO_FLUSH)
 1819                     return need_more;
 1820                 break;      /* flush the current block */
 1821             }
 1822         }
 1823 
 1824         /* Output a literal byte */
 1825         s->match_length = 0;
 1826         Tracevv((stderr,"%c", s->window[s->strstart]));
 1827         _tr_tally_lit (s, s->window[s->strstart], bflush);
 1828         s->lookahead--;
 1829         s->strstart++;
 1830         if (bflush) FLUSH_BLOCK(s, 0);
 1831     }
 1832     FLUSH_BLOCK(s, flush == Z_FINISH);
 1833     return flush == Z_FINISH ? finish_done : block_done;
 1834 }