NCBI C++ ToolKit
deflate.c
Go to the documentation of this file.

Go to the SVN repository for this file.

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