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