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

Go to the SVN repository for this file.

1 /* deflate.h -- internal compression state
2  * Copyright (C) 1995-2018 Jean-loup Gailly
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 /* WARNING: this file should *not* be used by applications. It is
7  part of the implementation of the compression library and is
8  subject to change. Applications should only use zlib.h.
9  */
10 
11 /* @(#) $Id: deflate.h 102009 2024-03-18 16:58:23Z ivanov $ */
12 
13 #ifndef DEFLATE_H
14 #define DEFLATE_H
15 
16 #include "zutil_cf.h"
17 
18 /* ===========================================================================
19  * Internal compression state.
20  */
21 
22 #define LENGTH_CODES 29
23 /* number of length codes, not counting the special END_BLOCK code */
24 
25 #define LITERALS 256
26 /* number of literal bytes 0..255 */
27 
28 #define L_CODES (LITERALS+1+LENGTH_CODES)
29 /* number of Literal or Length codes, including the END_BLOCK code */
30 
31 #define D_CODES 30
32 /* number of distance codes */
33 
34 #define BL_CODES 19
35 /* number of codes used to transfer the bit lengths */
36 
37 #define HEAP_SIZE (2*L_CODES+1)
38 /* maximum heap size */
39 
40 #define MAX_BITS 15
41 /* All codes must not exceed MAX_BITS bits */
42 
43 #define Buf_size 64
44 /* size of bit buffer in bi_buf */
45 
46 #define INIT_STATE 42
47 #define EXTRA_STATE 69
48 #define NAME_STATE 73
49 #define COMMENT_STATE 91
50 #define HCRC_STATE 103
51 #define BUSY_STATE 113
52 #define FINISH_STATE 666
53 /* Stream status */
54 
55 
56 /* Data structure describing a single value and its code string. */
57 typedef struct ct_data_s {
58  union {
59  uint16_t freq; /* frequency count */
60  uint16_t code; /* bit string */
61  } fc;
62  union {
63  uint16_t dad; /* father node in Huffman tree */
64  uint16_t len; /* length of bit string */
65  } dl;
67 
68 #define Freq fc.freq
69 #define Code fc.code
70 #define Dad dl.dad
71 #define Len dl.len
72 
74 
75 typedef struct tree_desc_s {
76  ct_data *dyn_tree; /* the dynamic tree */
77  int max_code; /* largest code with non zero frequency */
78  static_tree_desc *stat_desc; /* the corresponding static tree */
80 
81 typedef uint16_t Pos;
82 typedef uint32_t IPos;
83 
84 /* A Pos is an index in the character window. We use short instead of int to
85  * save space in the various tables. IPos is used only for parameter passing.
86  */
87 
88 typedef struct internal_state {
89  z_streamp strm; /* pointer back to this zlib stream */
90  int status; /* as the name implies */
91  uint8_t *pending_buf; /* output still pending */
92  uint64_t pending_buf_size; /* size of pending_buf */
93  uint8_t *pending_out; /* next pending byte to output to the stream */
94  uint32_t pending; /* nb of bytes in the pending buffer */
95  int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
96  gz_headerp gzhead; /* gzip header information to write */
97  uint32_t gzindex; /* where in extra, name, or comment */
98  uint8_t method; /* can only be DEFLATED */
99  int last_flush; /* value of flush param for previous deflate call */
100 
101  /* used by deflate.c: */
102  uint32_t w_size; /* LZ77 window size (32K by default) */
103  uint32_t w_bits; /* log2(w_size) (8..16) */
104  uint32_t w_mask; /* w_size - 1 */
105 
107  /* Sliding window. Input bytes are read into the second half of the window,
108  * and move to the first half later to keep a dictionary of at least wSize
109  * bytes. With this organization, matches are limited to a distance of
110  * wSize-MAX_MATCH bytes, but this ensures that IO is always
111  * performed with a length multiple of the block size. Also, it limits
112  * the window size to 64K, which is quite useful on MSDOS.
113  * To do: use the user input buffer as sliding window.
114  */
115 
117  /* Actual size of window: 2*wSize, except when the user input buffer
118  * is directly used as sliding window.
119  */
120 
122  /* Link to older string with same hash index. To limit the size of this
123  * array to 64K, this link is maintained only for the last 32K strings.
124  * An index in this array is thus a window index modulo 32K.
125  */
126 
127  Pos *head; /* Heads of the hash chains or NIL. */
128 
129  uint32_t ins_h; /* hash index of string to be inserted */
130  uint32_t hash_size; /* number of elements in hash table */
131  uint32_t hash_bits; /* log2(hash_size) */
132  uint32_t hash_mask; /* hash_size-1 */
133 
135  /* Number of bits by which ins_h must be shifted at each input
136  * step. It must be such that after MIN_MATCH steps, the oldest
137  * byte no longer takes part in the hash key, that is:
138  * hash_shift * MIN_MATCH >= hash_bits
139  */
140 
141  long block_start;
142  /* Window position at the beginning of the current output block. Gets
143  * negative when the window is moved backwards.
144  */
145 
146  uint32_t match_length; /* length of best match */
147  IPos prev_match; /* previous match */
148  int match_available; /* set if previous match exists */
149  uint32_t strstart; /* start of string to insert */
150  uint32_t match_start; /* start of matching string */
151  uint32_t lookahead; /* number of valid bytes ahead in window */
152 
154  /* Length of the best match at previous step. Matches not greater than this
155  * are discarded. This is used in the lazy match evaluation.
156  */
157 
159  /* To speed up deflation, hash chains are never searched beyond this
160  * length. A higher limit improves compression ratio but degrades the
161  * speed.
162  */
163 
165  /* Attempt to find a better match only when the current match is strictly
166  * smaller than this value. This mechanism is used only for compression
167  * levels >= 4.
168  */
169 # define max_insert_length max_lazy_match
170  /* Insert new strings in the hash table only if the match length is not
171  * greater than this length. This saves time but degrades compression.
172  * max_insert_length is used only for compression levels <= 3.
173  */
174 
175  int level; /* compression level (1..9) */
176  int strategy; /* favor or force Huffman coding*/
177 
179  /* Use a faster search when the previous match is longer than this */
180 
181  int nice_match; /* Stop searching when current match exceeds this */
182 
183  /* used by trees.c: */
184  /* Didn't use ct_data typedef below to suppress compiler warning */
185  struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
186  struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
187  struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
188 
189  struct tree_desc_s l_desc; /* desc. for literal tree */
190  struct tree_desc_s d_desc; /* desc. for distance tree */
191  struct tree_desc_s bl_desc; /* desc. for bit length tree */
192 
194  /* number of codes at each bit length for an optimal tree */
195 
196  int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
197  int heap_len; /* number of elements in the heap */
198  int heap_max; /* element of largest frequency */
199  /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
200  * The same heap array is used to build all trees.
201  */
202 
204  /* Depth of each subtree used as tie breaker for trees of equal frequency
205  */
206 
207  uint8_t *sym_buf; /* buffer for distances and literals/lengths */
208 
210  /* Size of match buffer for literals/lengths. There are 4 reasons for
211  * limiting lit_bufsize to 64K:
212  * - frequencies can be kept in 16 bit counters
213  * - if compression is not successful for the first block, all input
214  * data is still in the window so we can still emit a stored block even
215  * when input comes from standard input. (This can also be done for
216  * all blocks if lit_bufsize is not greater than 32K.)
217  * - if compression is not successful for a file smaller than 64K, we can
218  * even emit a stored file instead of a stored block (saving 5 bytes).
219  * This is applicable only for zip (not gzip or zlib).
220  * - creating new Huffman trees less frequently may not provide fast
221  * adaptation to changes in the input data statistics. (Take for
222  * example a binary file with poorly compressible code followed by
223  * a highly compressible string table.) Smaller buffer sizes give
224  * fast adaptation but have of course the overhead of transmitting
225  * trees more frequently.
226  * - I can't count above 4
227  */
228 
229  uInt sym_next; /* running index in sym_buf */
230  uInt sym_end; /* symbol table full when sym_next reaches this */
231 
232  uint64_t opt_len; /* bit length of current block with optimal trees */
233  uint64_t static_len; /* bit length of current block with static trees */
234  uint32_t matches; /* number of string matches in current block */
235  uint32_t insert; /* bytes at end of window left to insert */
236 
237 #ifdef ZLIB_DEBUG
238  uint64_t compressed_len; /* total bit length of compressed file mod 2^32 */
239  uint64_t bits_sent; /* bit length of compressed data sent mod 2^32 */
240 #endif
241 
243  /* Output buffer. bits are inserted starting at the bottom (least
244  * significant bits).
245  */
246  int bi_valid;
247  /* Number of valid bits in bi_buf. All bits above the last valid bit
248  * are always zero.
249  */
250 
252  /* High water mark offset in window for initialized bytes -- bytes above
253  * this are set to zero in order to avoid memory check warnings when
254  * longest match routines access bytes past the input. This is then
255  * updated to the new high water mark.
256  */
257 
259 
260 /* Output a byte on the stream.
261  * IN assertion: there is enough room in pending_buf.
262  */
263 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
264 
265 /* ===========================================================================
266  * Output a short LSB first on the stream.
267  * IN assertion: there is enough room in pendingBuf.
268  */
269 
270 #define put_short(s, w) { \
271  s->pending += 2; \
272  *(ush*)(&s->pending_buf[s->pending - 2]) = (w) ; \
273 }
274 
275 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
276 /* Minimum amount of lookahead, except at the end of the input file.
277  * See deflate.c for comments about the MIN_MATCH+1.
278  */
279 
280 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
281 /* In order to simplify the code, particularly on 16 bit machines, match
282  * distances are limited to MAX_DIST instead of WSIZE.
283  */
284 
285 #define WIN_INIT MAX_MATCH
286 /* Number of bytes after end of data in window to initialize in order to avoid
287  memory checker errors from longest match routines */
288 
289  /* in trees.c */
293  uint64_t stored_len, int last);
297  uint64_t stored_len, int last);
298 
299 #define d_code(dist) \
300  ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
301 /* Mapping from a distance to a distance code. dist is the distance - 1 and
302  * must not have side effects. _dist_code[256] and _dist_code[257] are never
303  * used.
304  */
305 
306 extern const uint8_t ZLIB_INTERNAL _length_code[];
307 extern const uint8_t ZLIB_INTERNAL _dist_code[];
308 
309 # define _tr_tally_lit(s, c, flush) \
310  { uch cc = (c); \
311  s->sym_buf[s->sym_next++] = 0; \
312  s->sym_buf[s->sym_next++] = 0; \
313  s->sym_buf[s->sym_next++] = cc; \
314  s->dyn_ltree[cc].Freq++; \
315  flush = (s->sym_next == s->sym_end); \
316  }
317 # define _tr_tally_dist(s, distance, length, flush) \
318  { uch len = (uch)(length); \
319  ush dist = (ush)(distance); \
320  s->sym_buf[s->sym_next++] = dist; \
321  s->sym_buf[s->sym_next++] = dist >> 8; \
322  s->sym_buf[s->sym_next++] = len; \
323  dist--; \
324  s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
325  s->dyn_dtree[d_code(dist)].Freq++; \
326  flush = (s->sym_next == s->sym_end); \
327  }
328 
329 #ifdef _MSC_VER
330 
331 /* MSC doesn't have __builtin_expect. Just ignore likely/unlikely and
332  hope the compiler optimizes for the best.
333 */
334 #define likely(x) (x)
335 #define unlikely(x) (x)
336 
337 int __inline __builtin_ctzl(unsigned long mask)
338 {
339  unsigned long index ;
340 
341  return _BitScanForward(&index, mask) == 0 ? 32 : ((int)index) ;
342 }
343 #else
344 #define likely(x) __builtin_expect((x),1)
345 #define unlikely(x) __builtin_expect((x),0)
346 #endif
347 
348 #endif /* DEFLATE_H */
ncbi::TMaskedQueryRegions mask
Uint4 IPos
unsigned short Pos
static ulg compressed_len
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:51
static int lc
Definition: getdata.c:30
Uint8 uint64_t
unsigned char uint8_t
Uint2 uint16_t
Uint4 uint32_t
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
char * buf
uint16_t freq
Definition: deflate.h:59
union ct_data_s::@1166 fc
uint16_t dad
Definition: deflate.h:63
union ct_data_s::@1167 dl
uint16_t len
Definition: deflate.h:64
uint16_t code
Definition: deflate.h:60
struct tree_desc_s l_desc
Definition: deflate.h:202
uint32_t hash_bits
Definition: deflate.h:131
IPos prev_match
Definition: deflate.h:160
uInt sym_next
Definition: deflate.h:242
uint32_t match_start
Definition: deflate.h:150
uint32_t matches
Definition: deflate.h:234
uint32_t w_size
Definition: deflate.h:102
uint64_t opt_len
Definition: deflate.h:232
uint32_t window_size
Definition: deflate.h:116
uint32_t good_match
Definition: deflate.h:178
uint32_t max_chain_length
Definition: deflate.h:158
uint32_t ins_h
Definition: deflate.h:129
uch depth[2 *(256+1+29)+1]
Definition: deflate.h:216
int nice_match
Definition: deflate.h:194
uint32_t insert
Definition: deflate.h:235
uint64_t high_water
Definition: deflate.h:251
uint32_t pending
Definition: deflate.h:94
uint64_t static_len
Definition: deflate.h:233
struct ct_data_s dyn_dtree[2 *30+1]
Definition: deflate.h:199
Pos * prev
Definition: deflate.h:121
uint32_t prev_length
Definition: deflate.h:153
long block_start
Definition: deflate.h:154
uInt sym_end
Definition: deflate.h:243
uint32_t gzindex
Definition: deflate.h:97
struct ct_data_s bl_tree[2 *19+1]
Definition: deflate.h:200
ush bl_count[15+1]
Definition: deflate.h:206
uint32_t hash_size
Definition: deflate.h:130
uint8_t method
Definition: deflate.h:98
Pos * head
Definition: deflate.h:127
uint8_t * window
Definition: deflate.h:106
uint8_t * pending_buf
Definition: deflate.h:91
uint8_t * sym_buf
Definition: deflate.h:207
uint32_t w_bits
Definition: deflate.h:103
struct tree_desc_s bl_desc
Definition: deflate.h:204
uint32_t hash_shift
Definition: deflate.h:134
uint32_t max_lazy_match
Definition: deflate.h:164
int last_flush
Definition: deflate.h:111
z_streamp strm
Definition: deflate.h:101
struct tree_desc_s d_desc
Definition: deflate.h:203
uint32_t w_mask
Definition: deflate.h:104
uint8_t * pending_out
Definition: deflate.h:93
gz_headerp gzhead
Definition: deflate.h:108
int match_available
Definition: deflate.h:161
uint64_t pending_buf_size
Definition: deflate.h:92
uint32_t lookahead
Definition: deflate.h:151
int heap[2 *(256+1+29)+1]
Definition: deflate.h:209
uint32_t strstart
Definition: deflate.h:149
uint32_t lit_bufsize
Definition: deflate.h:209
uint32_t hash_mask
Definition: deflate.h:132
uint32_t match_length
Definition: deflate.h:146
uint64_t bi_buf
Definition: deflate.h:242
struct ct_data_s dyn_ltree[(2 *(256+1+29)+1)]
Definition: deflate.h:198
int max_code
Definition: deflate.h:88
static_tree_desc * stat_desc
Definition: deflate.h:78
ct_data * dyn_tree
Definition: deflate.h:87
unsigned int uInt
Definition: zconf.h:395
struct ct_data_s ct_data
ush Pos
Definition: deflate.h:92
uch ZLIB_INTERNAL _length_code[]
Definition: trees.c:104
unsigned IPos
Definition: deflate.h:94
struct tree_desc_s tree_desc
struct internal_state deflate_state
uch ZLIB_INTERNAL _dist_code[]
Definition: trees.c:98
#define HEAP_SIZE
Definition: deflate.h:37
#define L_CODES
Definition: deflate.h:28
void ZLIB_INTERNAL _tr_stored_block(deflate_state *s, uint8_t *buf, uint64_t stored_len, int last)
Definition: trees.c:802
void ZLIB_INTERNAL _tr_init(deflate_state *s)
Definition: trees.c:379
#define MAX_BITS
Definition: deflate.h:40
void ZLIB_INTERNAL _tr_flush_bits(deflate_state *s)
Definition: trees.c:887
#define D_CODES
Definition: deflate.h:31
#define BL_CODES
Definition: deflate.h:34
void ZLIB_INTERNAL _tr_align(deflate_state *s)
Definition: trees.c:897
void ZLIB_INTERNAL _tr_flush_block(deflate_state *s, uint8_t *buf, uint64_t stored_len, int last)
Definition: trees.c:837
int ZLIB_INTERNAL _tr_tally(deflate_state *s, uint32_t dist, unsigned lc)
#define ZLIB_INTERNAL
Definition: zutil.h:19
Modified on Fri Jul 19 17:08:58 2024 by modify_doxy.py rev. 669887