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