/src/c-blosc2/internal-complibs/zlib-ng-2.0.7/deflate.h
Line | Count | Source (jump to first uncovered line) |
1 | | #ifndef DEFLATE_H_ |
2 | | #define DEFLATE_H_ |
3 | | /* deflate.h -- internal compression state |
4 | | * Copyright (C) 1995-2016 Jean-loup Gailly |
5 | | * For conditions of distribution and use, see copyright notice in zlib.h |
6 | | */ |
7 | | |
8 | | /* WARNING: this file should *not* be used by applications. It is |
9 | | part of the implementation of the compression library and is |
10 | | subject to change. Applications should only use zlib.h. |
11 | | */ |
12 | | |
13 | | #include "zutil.h" |
14 | | #include "zendian.h" |
15 | | |
16 | | /* define NO_GZIP when compiling if you want to disable gzip header and |
17 | | trailer creation by deflate(). NO_GZIP would be used to avoid linking in |
18 | | the crc code when it is not needed. For shared libraries, gzip encoding |
19 | | should be left enabled. */ |
20 | | #ifndef NO_GZIP |
21 | | # define GZIP |
22 | | #endif |
23 | | |
24 | | /* =========================================================================== |
25 | | * Internal compression state. |
26 | | */ |
27 | | |
28 | 0 | #define LENGTH_CODES 29 |
29 | | /* number of length codes, not counting the special END_BLOCK code */ |
30 | | |
31 | 0 | #define LITERALS 256 |
32 | | /* number of literal bytes 0..255 */ |
33 | | |
34 | 0 | #define L_CODES (LITERALS+1+LENGTH_CODES) |
35 | | /* number of Literal or Length codes, including the END_BLOCK code */ |
36 | | |
37 | 0 | #define D_CODES 30 |
38 | | /* number of distance codes */ |
39 | | |
40 | 0 | #define BL_CODES 19 |
41 | | /* number of codes used to transfer the bit lengths */ |
42 | | |
43 | 0 | #define HEAP_SIZE (2*L_CODES+1) |
44 | | /* maximum heap size */ |
45 | | |
46 | 0 | #define MAX_BITS 15 |
47 | | /* All codes must not exceed MAX_BITS bits */ |
48 | | |
49 | 0 | #define BIT_BUF_SIZE 64 |
50 | | /* size of bit buffer in bi_buf */ |
51 | | |
52 | 0 | #define END_BLOCK 256 |
53 | | /* end of block literal code */ |
54 | | |
55 | 0 | #define INIT_STATE 42 /* zlib header -> BUSY_STATE */ |
56 | | #ifdef GZIP |
57 | 0 | # define GZIP_STATE 57 /* gzip header -> BUSY_STATE | EXTRA_STATE */ |
58 | 0 | # define EXTRA_STATE 69 /* gzip extra block -> NAME_STATE */ |
59 | 0 | # define NAME_STATE 73 /* gzip file name -> COMMENT_STATE */ |
60 | 0 | # define COMMENT_STATE 91 /* gzip comment -> HCRC_STATE */ |
61 | 0 | # define HCRC_STATE 103 /* gzip header CRC -> BUSY_STATE */ |
62 | | #endif |
63 | 0 | #define BUSY_STATE 113 /* deflate -> FINISH_STATE */ |
64 | 0 | #define FINISH_STATE 666 /* stream complete */ |
65 | | /* Stream status */ |
66 | | |
67 | 0 | #define HASH_BITS 16u /* log2(HASH_SIZE) */ |
68 | | #ifndef HASH_SIZE |
69 | 0 | # define HASH_SIZE 65536u /* number of elements in hash table */ |
70 | | #endif |
71 | 0 | #define HASH_MASK (HASH_SIZE - 1u) /* HASH_SIZE-1 */ |
72 | | |
73 | | |
74 | | /* Data structure describing a single value and its code string. */ |
75 | | typedef struct ct_data_s { |
76 | | union { |
77 | | uint16_t freq; /* frequency count */ |
78 | | uint16_t code; /* bit string */ |
79 | | } fc; |
80 | | union { |
81 | | uint16_t dad; /* father node in Huffman tree */ |
82 | | uint16_t len; /* length of bit string */ |
83 | | } dl; |
84 | | } ct_data; |
85 | | |
86 | 0 | #define Freq fc.freq |
87 | 0 | #define Code fc.code |
88 | 0 | #define Dad dl.dad |
89 | 0 | #define Len dl.len |
90 | | |
91 | | typedef struct static_tree_desc_s static_tree_desc; |
92 | | |
93 | | typedef struct tree_desc_s { |
94 | | ct_data *dyn_tree; /* the dynamic tree */ |
95 | | int max_code; /* largest code with non zero frequency */ |
96 | | const static_tree_desc *stat_desc; /* the corresponding static tree */ |
97 | | } tree_desc; |
98 | | |
99 | | typedef uint16_t Pos; |
100 | | |
101 | | /* A Pos is an index in the character window. We use short instead of int to |
102 | | * save space in the various tables. |
103 | | */ |
104 | | |
105 | | typedef struct internal_state { |
106 | | PREFIX3(stream) *strm; /* pointer back to this zlib stream */ |
107 | | unsigned char *pending_buf; /* output still pending */ |
108 | | unsigned char *pending_out; /* next pending byte to output to the stream */ |
109 | | uint32_t pending_buf_size; /* size of pending_buf */ |
110 | | uint32_t pending; /* nb of bytes in the pending buffer */ |
111 | | int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ |
112 | | uint32_t gzindex; /* where in extra, name, or comment */ |
113 | | PREFIX(gz_headerp) gzhead; /* gzip header information to write */ |
114 | | int status; /* as the name implies */ |
115 | | int last_flush; /* value of flush param for previous deflate call */ |
116 | | int reproducible; /* Whether reproducible compression results are required. */ |
117 | | |
118 | | int block_open; |
119 | | /* Whether or not a block is currently open for the QUICK deflation scheme. |
120 | | * This is set to 1 if there is an active block, or 0 if the block was just closed. |
121 | | */ |
122 | | |
123 | | /* used by deflate.c: */ |
124 | | |
125 | | unsigned int w_size; /* LZ77 window size (32K by default) */ |
126 | | unsigned int w_bits; /* log2(w_size) (8..16) */ |
127 | | unsigned int w_mask; /* w_size - 1 */ |
128 | | unsigned int lookahead; /* number of valid bytes ahead in window */ |
129 | | |
130 | | unsigned int high_water; |
131 | | /* High water mark offset in window for initialized bytes -- bytes above |
132 | | * this are set to zero in order to avoid memory check warnings when |
133 | | * longest match routines access bytes past the input. This is then |
134 | | * updated to the new high water mark. |
135 | | */ |
136 | | |
137 | | unsigned int window_size; |
138 | | /* Actual size of window: 2*wSize, except when the user input buffer |
139 | | * is directly used as sliding window. |
140 | | */ |
141 | | |
142 | | unsigned char *window; |
143 | | /* Sliding window. Input bytes are read into the second half of the window, |
144 | | * and move to the first half later to keep a dictionary of at least wSize |
145 | | * bytes. With this organization, matches are limited to a distance of |
146 | | * wSize-MAX_MATCH bytes, but this ensures that IO is always |
147 | | * performed with a length multiple of the block size. Also, it limits |
148 | | * the window size to 64K, which is quite useful on MSDOS. |
149 | | * To do: use the user input buffer as sliding window. |
150 | | */ |
151 | | |
152 | | Pos *prev; |
153 | | /* Link to older string with same hash index. To limit the size of this |
154 | | * array to 64K, this link is maintained only for the last 32K strings. |
155 | | * An index in this array is thus a window index modulo 32K. |
156 | | */ |
157 | | |
158 | | Pos *head; /* Heads of the hash chains or 0. */ |
159 | | |
160 | | int block_start; |
161 | | /* Window position at the beginning of the current output block. Gets |
162 | | * negative when the window is moved backwards. |
163 | | */ |
164 | | |
165 | | unsigned int match_length; /* length of best match */ |
166 | | Pos prev_match; /* previous match */ |
167 | | int match_available; /* set if previous match exists */ |
168 | | unsigned int strstart; /* start of string to insert */ |
169 | | unsigned int match_start; /* start of matching string */ |
170 | | |
171 | | unsigned int prev_length; |
172 | | /* Length of the best match at previous step. Matches not greater than this |
173 | | * are discarded. This is used in the lazy match evaluation. |
174 | | */ |
175 | | |
176 | | unsigned int max_chain_length; |
177 | | /* To speed up deflation, hash chains are never searched beyond this length. |
178 | | * A higher limit improves compression ratio but degrades the speed. |
179 | | */ |
180 | | |
181 | | unsigned int max_lazy_match; |
182 | | /* Attempt to find a better match only when the current match is strictly smaller |
183 | | * than this value. This mechanism is used only for compression levels >= 4. |
184 | | */ |
185 | 0 | # define max_insert_length max_lazy_match |
186 | | /* Insert new strings in the hash table only if the match length is not |
187 | | * greater than this length. This saves time but degrades compression. |
188 | | * max_insert_length is used only for compression levels <= 3. |
189 | | */ |
190 | | |
191 | | int level; /* compression level (1..9) */ |
192 | | int strategy; /* favor or force Huffman coding*/ |
193 | | |
194 | | unsigned int good_match; |
195 | | /* Use a faster search when the previous match is longer than this */ |
196 | | |
197 | | int nice_match; /* Stop searching when current match exceeds this */ |
198 | | |
199 | | #if defined(__x86_64__) || defined(_M_X64) || defined(__i386) || defined(_M_IX86) |
200 | | /* Only used if X86_PCLMULQDQ_CRC is defined */ |
201 | | unsigned crc0[4 * 5]; |
202 | | #endif |
203 | | |
204 | | /* used by trees.c: */ |
205 | | /* Didn't use ct_data typedef below to suppress compiler warning */ |
206 | | struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ |
207 | | struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ |
208 | | struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ |
209 | | |
210 | | struct tree_desc_s l_desc; /* desc. for literal tree */ |
211 | | struct tree_desc_s d_desc; /* desc. for distance tree */ |
212 | | struct tree_desc_s bl_desc; /* desc. for bit length tree */ |
213 | | |
214 | | uint16_t bl_count[MAX_BITS+1]; |
215 | | /* number of codes at each bit length for an optimal tree */ |
216 | | |
217 | | int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ |
218 | | int heap_len; /* number of elements in the heap */ |
219 | | int heap_max; /* element of largest frequency */ |
220 | | /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. |
221 | | * The same heap array is used to build all trees. |
222 | | */ |
223 | | |
224 | | unsigned char depth[2*L_CODES+1]; |
225 | | /* Depth of each subtree used as tie breaker for trees of equal frequency |
226 | | */ |
227 | | |
228 | | unsigned int lit_bufsize; |
229 | | /* Size of match buffer for literals/lengths. There are 4 reasons for |
230 | | * limiting lit_bufsize to 64K: |
231 | | * - frequencies can be kept in 16 bit counters |
232 | | * - if compression is not successful for the first block, all input |
233 | | * data is still in the window so we can still emit a stored block even |
234 | | * when input comes from standard input. (This can also be done for |
235 | | * all blocks if lit_bufsize is not greater than 32K.) |
236 | | * - if compression is not successful for a file smaller than 64K, we can |
237 | | * even emit a stored file instead of a stored block (saving 5 bytes). |
238 | | * This is applicable only for zip (not gzip or zlib). |
239 | | * - creating new Huffman trees less frequently may not provide fast |
240 | | * adaptation to changes in the input data statistics. (Take for |
241 | | * example a binary file with poorly compressible code followed by |
242 | | * a highly compressible string table.) Smaller buffer sizes give |
243 | | * fast adaptation but have of course the overhead of transmitting |
244 | | * trees more frequently. |
245 | | * - I can't count above 4 |
246 | | */ |
247 | | |
248 | | unsigned char *sym_buf; /* buffer for distances and literals/lengths */ |
249 | | unsigned int sym_next; /* running index in sym_buf */ |
250 | | unsigned int sym_end; /* symbol table full when sym_next reaches this */ |
251 | | |
252 | | unsigned long opt_len; /* bit length of current block with optimal trees */ |
253 | | unsigned long static_len; /* bit length of current block with static trees */ |
254 | | unsigned int matches; /* number of string matches in current block */ |
255 | | unsigned int insert; /* bytes at end of window left to insert */ |
256 | | |
257 | | /* compressed_len and bits_sent are only used if ZLIB_DEBUG is defined */ |
258 | | unsigned long compressed_len; /* total bit length of compressed file mod 2^32 */ |
259 | | unsigned long bits_sent; /* bit length of compressed data sent mod 2^32 */ |
260 | | |
261 | | /* Reserved for future use and alignment purposes */ |
262 | | char *reserved_p; |
263 | | |
264 | | uint64_t bi_buf; |
265 | | /* Output buffer. bits are inserted starting at the bottom (least significant bits). */ |
266 | | |
267 | | int32_t bi_valid; |
268 | | /* Number of valid bits in bi_buf. All bits above the last valid bit are always zero. */ |
269 | | |
270 | | /* Reserved for future use and alignment purposes */ |
271 | | int32_t reserved[11]; |
272 | | } ALIGNED_(8) deflate_state; |
273 | | |
274 | | typedef enum { |
275 | | need_more, /* block not completed, need more input or more output */ |
276 | | block_done, /* block flush performed */ |
277 | | finish_started, /* finish started, need only more output at next deflate */ |
278 | | finish_done /* finish done, accept no more input or output */ |
279 | | } block_state; |
280 | | |
281 | | /* Output a byte on the stream. |
282 | | * IN assertion: there is enough room in pending_buf. |
283 | | */ |
284 | 0 | #define put_byte(s, c) { \ |
285 | 0 | s->pending_buf[s->pending++] = (unsigned char)(c); \ |
286 | 0 | } |
287 | | |
288 | | /* =========================================================================== |
289 | | * Output a short LSB first on the stream. |
290 | | * IN assertion: there is enough room in pending_buf. |
291 | | */ |
292 | 0 | static inline void put_short(deflate_state *s, uint16_t w) { |
293 | | #if BYTE_ORDER == BIG_ENDIAN |
294 | | w = ZSWAP16(w); |
295 | | #endif |
296 | 0 | memcpy(&s->pending_buf[s->pending], &w, sizeof(w)); |
297 | 0 | s->pending += 2; |
298 | 0 | } Unexecuted instantiation: deflate.c:put_short Unexecuted instantiation: deflate_fast.c:put_short Unexecuted instantiation: deflate_medium.c:put_short Unexecuted instantiation: deflate_quick.c:put_short Unexecuted instantiation: deflate_slow.c:put_short Unexecuted instantiation: functable.c:put_short Unexecuted instantiation: insert_string.c:put_short Unexecuted instantiation: trees.c:put_short Unexecuted instantiation: adler32.c:put_short Unexecuted instantiation: compare258.c:put_short Unexecuted instantiation: crc32.c:put_short Unexecuted instantiation: inflate.c:put_short Unexecuted instantiation: inffast.c:put_short |
299 | | |
300 | | /* =========================================================================== |
301 | | * Output a short MSB first on the stream. |
302 | | * IN assertion: there is enough room in pending_buf. |
303 | | */ |
304 | 0 | static inline void put_short_msb(deflate_state *s, uint16_t w) { |
305 | 0 | #if BYTE_ORDER == LITTLE_ENDIAN |
306 | 0 | w = ZSWAP16(w); |
307 | 0 | #endif |
308 | 0 | memcpy(&s->pending_buf[s->pending], &w, sizeof(w)); |
309 | 0 | s->pending += 2; |
310 | 0 | } Unexecuted instantiation: deflate.c:put_short_msb Unexecuted instantiation: deflate_fast.c:put_short_msb Unexecuted instantiation: deflate_medium.c:put_short_msb Unexecuted instantiation: deflate_quick.c:put_short_msb Unexecuted instantiation: deflate_slow.c:put_short_msb Unexecuted instantiation: functable.c:put_short_msb Unexecuted instantiation: insert_string.c:put_short_msb Unexecuted instantiation: trees.c:put_short_msb Unexecuted instantiation: adler32.c:put_short_msb Unexecuted instantiation: compare258.c:put_short_msb Unexecuted instantiation: crc32.c:put_short_msb Unexecuted instantiation: inflate.c:put_short_msb Unexecuted instantiation: inffast.c:put_short_msb |
311 | | |
312 | | /* =========================================================================== |
313 | | * Output a 32-bit unsigned int LSB first on the stream. |
314 | | * IN assertion: there is enough room in pending_buf. |
315 | | */ |
316 | 0 | static inline void put_uint32(deflate_state *s, uint32_t dw) { |
317 | | #if BYTE_ORDER == BIG_ENDIAN |
318 | | dw = ZSWAP32(dw); |
319 | | #endif |
320 | 0 | memcpy(&s->pending_buf[s->pending], &dw, sizeof(dw)); |
321 | 0 | s->pending += 4; |
322 | 0 | } Unexecuted instantiation: deflate.c:put_uint32 Unexecuted instantiation: deflate_fast.c:put_uint32 Unexecuted instantiation: deflate_medium.c:put_uint32 Unexecuted instantiation: deflate_quick.c:put_uint32 Unexecuted instantiation: deflate_slow.c:put_uint32 Unexecuted instantiation: functable.c:put_uint32 Unexecuted instantiation: insert_string.c:put_uint32 Unexecuted instantiation: trees.c:put_uint32 Unexecuted instantiation: adler32.c:put_uint32 Unexecuted instantiation: compare258.c:put_uint32 Unexecuted instantiation: crc32.c:put_uint32 Unexecuted instantiation: inflate.c:put_uint32 Unexecuted instantiation: inffast.c:put_uint32 |
323 | | |
324 | | /* =========================================================================== |
325 | | * Output a 32-bit unsigned int MSB first on the stream. |
326 | | * IN assertion: there is enough room in pending_buf. |
327 | | */ |
328 | 0 | static inline void put_uint32_msb(deflate_state *s, uint32_t dw) { |
329 | 0 | #if BYTE_ORDER == LITTLE_ENDIAN |
330 | 0 | dw = ZSWAP32(dw); |
331 | 0 | #endif |
332 | 0 | memcpy(&s->pending_buf[s->pending], &dw, sizeof(dw)); |
333 | 0 | s->pending += 4; |
334 | 0 | } Unexecuted instantiation: deflate.c:put_uint32_msb Unexecuted instantiation: deflate_fast.c:put_uint32_msb Unexecuted instantiation: deflate_medium.c:put_uint32_msb Unexecuted instantiation: deflate_quick.c:put_uint32_msb Unexecuted instantiation: deflate_slow.c:put_uint32_msb Unexecuted instantiation: functable.c:put_uint32_msb Unexecuted instantiation: insert_string.c:put_uint32_msb Unexecuted instantiation: trees.c:put_uint32_msb Unexecuted instantiation: adler32.c:put_uint32_msb Unexecuted instantiation: compare258.c:put_uint32_msb Unexecuted instantiation: crc32.c:put_uint32_msb Unexecuted instantiation: inflate.c:put_uint32_msb Unexecuted instantiation: inffast.c:put_uint32_msb |
335 | | |
336 | | /* =========================================================================== |
337 | | * Output a 64-bit unsigned int LSB first on the stream. |
338 | | * IN assertion: there is enough room in pending_buf. |
339 | | */ |
340 | 0 | static inline void put_uint64(deflate_state *s, uint64_t lld) { |
341 | | #if BYTE_ORDER == BIG_ENDIAN |
342 | | lld = ZSWAP64(lld); |
343 | | #endif |
344 | 0 | memcpy(&s->pending_buf[s->pending], &lld, sizeof(lld)); |
345 | 0 | s->pending += 8; |
346 | 0 | } Unexecuted instantiation: deflate.c:put_uint64 Unexecuted instantiation: deflate_fast.c:put_uint64 Unexecuted instantiation: deflate_medium.c:put_uint64 Unexecuted instantiation: deflate_quick.c:put_uint64 Unexecuted instantiation: deflate_slow.c:put_uint64 Unexecuted instantiation: functable.c:put_uint64 Unexecuted instantiation: insert_string.c:put_uint64 Unexecuted instantiation: trees.c:put_uint64 Unexecuted instantiation: adler32.c:put_uint64 Unexecuted instantiation: compare258.c:put_uint64 Unexecuted instantiation: crc32.c:put_uint64 Unexecuted instantiation: inflate.c:put_uint64 Unexecuted instantiation: inffast.c:put_uint64 |
347 | | |
348 | 0 | #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) |
349 | | /* Minimum amount of lookahead, except at the end of the input file. |
350 | | * See deflate.c for comments about the MIN_MATCH+1. |
351 | | */ |
352 | | |
353 | 0 | #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) |
354 | | /* In order to simplify the code, particularly on 16 bit machines, match |
355 | | * distances are limited to MAX_DIST instead of WSIZE. |
356 | | */ |
357 | | |
358 | 0 | #define WIN_INIT MAX_MATCH |
359 | | /* Number of bytes after end of data in window to initialize in order to avoid |
360 | | memory checker errors from longest match routines */ |
361 | | |
362 | | |
363 | | void Z_INTERNAL fill_window(deflate_state *s); |
364 | | void Z_INTERNAL slide_hash_c(deflate_state *s); |
365 | | |
366 | | /* in trees.c */ |
367 | | void Z_INTERNAL zng_tr_init(deflate_state *s); |
368 | | void Z_INTERNAL zng_tr_flush_block(deflate_state *s, char *buf, uint32_t stored_len, int last); |
369 | | void Z_INTERNAL zng_tr_flush_bits(deflate_state *s); |
370 | | void Z_INTERNAL zng_tr_align(deflate_state *s); |
371 | | void Z_INTERNAL zng_tr_stored_block(deflate_state *s, char *buf, uint32_t stored_len, int last); |
372 | | unsigned Z_INTERNAL bi_reverse(unsigned code, int len); |
373 | | void Z_INTERNAL flush_pending(PREFIX3(streamp) strm); |
374 | 0 | #define d_code(dist) ((dist) < 256 ? zng_dist_code[dist] : zng_dist_code[256+((dist)>>7)]) |
375 | | /* Mapping from a distance to a distance code. dist is the distance - 1 and |
376 | | * must not have side effects. zng_dist_code[256] and zng_dist_code[257] are never |
377 | | * used. |
378 | | */ |
379 | | |
380 | | /* Bit buffer and compress bits calculation debugging */ |
381 | | #ifdef ZLIB_DEBUG |
382 | | # define cmpr_bits_add(s, len) s->compressed_len += (len) |
383 | | # define cmpr_bits_align(s) s->compressed_len = (s->compressed_len + 7) & ~7L |
384 | | # define sent_bits_add(s, bits) s->bits_sent += (bits) |
385 | | # define sent_bits_align(s) s->bits_sent = (s->bits_sent + 7) & ~7L |
386 | | #else |
387 | 0 | # define cmpr_bits_add(s, len) Z_UNUSED(len) |
388 | | # define cmpr_bits_align(s) |
389 | 0 | # define sent_bits_add(s, bits) Z_UNUSED(bits) |
390 | | # define sent_bits_align(s) |
391 | | #endif |
392 | | |
393 | | #endif /* DEFLATE_H_ */ |