1/*
2 * Copyright (c) 2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/* deflate.h -- internal compression state
29 * Copyright (C) 1995-2004 Jean-loup Gailly
30 * For conditions of distribution and use, see copyright notice in zlib.h
31 */
32
33/* WARNING: this file should *not* be used by applications. It is
34 part of the implementation of the compression library and is
35 subject to change. Applications should only use zlib.h.
36 */
37
38/* @(#) $Id$ */
39
40#ifndef DEFLATE_H
41#define DEFLATE_H
42
43#include "zutil.h"
44
45/* define NO_GZIP when compiling if you want to disable gzip header and
46 trailer creation by deflate(). NO_GZIP would be used to avoid linking in
47 the crc code when it is not needed. For shared libraries, gzip encoding
48 should be left enabled. */
49#ifndef NO_GZIP
50# define GZIP
51#endif
52
53/* ===========================================================================
54 * Internal compression state.
55 */
56
57#define LENGTH_CODES 29
58/* number of length codes, not counting the special END_BLOCK code */
59
60#define LITERALS 256
61/* number of literal bytes 0..255 */
62
63#define L_CODES (LITERALS+1+LENGTH_CODES)
64/* number of Literal or Length codes, including the END_BLOCK code */
65
66#define D_CODES 30
67/* number of distance codes */
68
69#define BL_CODES 19
70/* number of codes used to transfer the bit lengths */
71
72#define HEAP_SIZE (2*L_CODES+1)
73/* maximum heap size */
74
75#define MAX_BITS 15
76/* All codes must not exceed MAX_BITS bits */
77
78#define INIT_STATE 42
79#define EXTRA_STATE 69
80#define NAME_STATE 73
81#define COMMENT_STATE 91
82#define HCRC_STATE 103
83#define BUSY_STATE 113
84#define FINISH_STATE 666
85/* Stream status */
86
87
88/* Data structure describing a single value and its code string. */
89typedef struct ct_data_s {
90 union {
91 ush freq; /* frequency count */
92 ush code; /* bit string */
93 } fc;
94 union {
95 ush dad; /* father node in Huffman tree */
96 ush len; /* length of bit string */
97 } dl;
98} FAR ct_data;
99
100#define Freq fc.freq
101#define Code fc.code
102#define Dad dl.dad
103#define Len dl.len
104
105typedef struct static_tree_desc_s static_tree_desc;
106
107typedef struct tree_desc_s {
108 ct_data *dyn_tree; /* the dynamic tree */
109 int max_code; /* largest code with non zero frequency */
110 static_tree_desc *stat_desc; /* the corresponding static tree */
111} FAR tree_desc;
112
113typedef ush Pos;
114typedef Pos FAR Posf;
115typedef unsigned IPos;
116
117/* A Pos is an index in the character window. We use short instead of int to
118 * save space in the various tables. IPos is used only for parameter passing.
119 */
120
121typedef struct internal_state {
122 z_streamp strm; /* pointer back to this zlib stream */
123 z_input_func zinput;
124 z_output_func zoutput;
125 int status; /* as the name implies */
126 Bytef *pending_buf; /* output still pending */
127 ulg pending_buf_size; /* size of pending_buf */
128 Bytef *pending_out; /* next pending byte to output to the stream */
129 uInt pending; /* nb of bytes in the pending buffer */
130 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
131 gz_headerp gzhead; /* gzip header information to write */
132 uInt gzindex; /* where in extra, name, or comment */
133 Byte method; /* STORED (for zip only) or DEFLATED */
134 int last_flush; /* value of flush param for previous deflate call */
135
136 /* used by deflate.c: */
137
138 uInt w_size; /* LZ77 window size (32K by default) */
139 uInt w_bits; /* log2(w_size) (8..16) */
140 uInt w_mask; /* w_size - 1 */
141
142 Bytef *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 ulg window_size;
153 /* Actual size of window: 2*wSize, except when the user input buffer
154 * is directly used as sliding window.
155 */
156
157 Posf *prev;
158 /* Link to older string with same hash index. To limit the size of this
159 * array to 64K, this link is maintained only for the last 32K strings.
160 * An index in this array is thus a window index modulo 32K.
161 */
162
163 Posf *head; /* Heads of the hash chains or NIL. */
164
165 uInt ins_h; /* hash index of string to be inserted */
166 uInt hash_size; /* number of elements in hash table */
167 uInt hash_bits; /* log2(hash_size) */
168 uInt hash_mask; /* hash_size-1 */
169
170 uInt hash_shift;
171 /* Number of bits by which ins_h must be shifted at each input
172 * step. It must be such that after MIN_MATCH steps, the oldest
173 * byte no longer takes part in the hash key, that is:
174 * hash_shift * MIN_MATCH >= hash_bits
175 */
176
177 long block_start;
178 /* Window position at the beginning of the current output block. Gets
179 * negative when the window is moved backwards.
180 */
181
182 uInt match_length; /* length of best match */
183 IPos prev_match; /* previous match */
184 int match_available; /* set if previous match exists */
185 uInt strstart; /* start of string to insert */
186 uInt match_start; /* start of matching string */
187 uInt lookahead; /* number of valid bytes ahead in window */
188
189 uInt prev_length;
190 /* Length of the best match at previous step. Matches not greater than this
191 * are discarded. This is used in the lazy match evaluation.
192 */
193
194 uInt max_chain_length;
195 /* To speed up deflation, hash chains are never searched beyond this
196 * length. A higher limit improves compression ratio but degrades the
197 * speed.
198 */
199
200 uInt max_lazy_match;
201 /* Attempt to find a better match only when the current match is strictly
202 * smaller than this value. This mechanism is used only for compression
203 * levels >= 4.
204 */
205# define max_insert_length max_lazy_match
206 /* Insert new strings in the hash table only if the match length is not
207 * greater than this length. This saves time but degrades compression.
208 * max_insert_length is used only for compression levels <= 3.
209 */
210
211 int level; /* compression level (1..9) */
212 int strategy; /* favor or force Huffman coding*/
213
214 uInt good_match;
215 /* Use a faster search when the previous match is longer than this */
216
217 int nice_match; /* Stop searching when current match exceeds this */
218
219 /* used by trees.c: */
220 /* Didn't use ct_data typedef below to supress compiler warning */
221 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
222 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
223 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
224
225 struct tree_desc_s l_desc; /* desc. for literal tree */
226 struct tree_desc_s d_desc; /* desc. for distance tree */
227 struct tree_desc_s bl_desc; /* desc. for bit length tree */
228
229 ush bl_count[MAX_BITS+1];
230 /* number of codes at each bit length for an optimal tree */
231
232 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
233 int heap_len; /* number of elements in the heap */
234 int heap_max; /* element of largest frequency */
235 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
236 * The same heap array is used to build all trees.
237 */
238
239 uch depth[2*L_CODES+1];
240 /* Depth of each subtree used as tie breaker for trees of equal frequency
241 */
242
243 uchf *l_buf; /* buffer for literals or lengths */
244
245 uInt lit_bufsize;
246 /* Size of match buffer for literals/lengths. There are 4 reasons for
247 * limiting lit_bufsize to 64K:
248 * - frequencies can be kept in 16 bit counters
249 * - if compression is not successful for the first block, all input
250 * data is still in the window so we can still emit a stored block even
251 * when input comes from standard input. (This can also be done for
252 * all blocks if lit_bufsize is not greater than 32K.)
253 * - if compression is not successful for a file smaller than 64K, we can
254 * even emit a stored file instead of a stored block (saving 5 bytes).
255 * This is applicable only for zip (not gzip or zlib).
256 * - creating new Huffman trees less frequently may not provide fast
257 * adaptation to changes in the input data statistics. (Take for
258 * example a binary file with poorly compressible code followed by
259 * a highly compressible string table.) Smaller buffer sizes give
260 * fast adaptation but have of course the overhead of transmitting
261 * trees more frequently.
262 * - I can't count above 4
263 */
264
265 uInt last_lit; /* running index in l_buf */
266
267 ushf *d_buf;
268 /* Buffer for distances. To simplify the code, d_buf and l_buf have
269 * the same number of elements. To use different lengths, an extra flag
270 * array would be necessary.
271 */
272
273 ulg opt_len; /* bit length of current block with optimal trees */
274 ulg static_len; /* bit length of current block with static trees */
275 uInt matches; /* number of string matches in current block */
276 int last_eob_len; /* bit length of EOB code for last block */
277
278#ifdef DEBUG
279 ulg compressed_len; /* total bit length of compressed file mod 2^32 */
280 ulg bits_sent; /* bit length of compressed data sent mod 2^32 */
281#endif
282
283 ush bi_buf;
284 /* Output buffer. bits are inserted starting at the bottom (least
285 * significant bits).
286 */
287 int bi_valid;
288 /* Number of valid bits in bi_buf. All bits above the last valid bit
289 * are always zero.
290 */
291
292} FAR deflate_state;
293
294/* Output a byte on the stream.
295 * IN assertion: there is enough room in pending_buf.
296 */
297#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
298
299
300#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
301/* Minimum amount of lookahead, except at the end of the input file.
302 * See deflate.c for comments about the MIN_MATCH+1.
303 */
304
305#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
306/* In order to simplify the code, particularly on 16 bit machines, match
307 * distances are limited to MAX_DIST instead of WSIZE.
308 */
309
310 /* in trees.c */
311void _tr_init OF((deflate_state *s));
312int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));
313void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
314 int eof));
315void _tr_align OF((deflate_state *s));
316void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
317 int eof));
318
319#define d_code(dist) \
320 ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
321/* Mapping from a distance to a distance code. dist is the distance - 1 and
322 * must not have side effects. _dist_code[256] and _dist_code[257] are never
323 * used.
324 */
325
326#ifndef DEBUG
327/* Inline versions of _tr_tally for speed: */
328
329#if defined(GEN_TREES_H) || !defined(STDC)
330 extern uch _length_code[];
331 extern uch _dist_code[];
332#else
333 extern const uch _length_code[];
334 extern const uch _dist_code[];
335#endif
336
337# define _tr_tally_lit(s, c, flush) \
338 { uch cc = (c); \
339 s->d_buf[s->last_lit] = 0; \
340 s->l_buf[s->last_lit++] = cc; \
341 s->dyn_ltree[cc].Freq++; \
342 flush = (s->last_lit == s->lit_bufsize-1); \
343 }
344# define _tr_tally_dist(s, distance, length, flush) \
345 { uch len = (uch)(length); \
346 ush dist = (ush)(distance); \
347 s->d_buf[s->last_lit] = dist; \
348 s->l_buf[s->last_lit++] = len; \
349 dist--; \
350 s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
351 s->dyn_dtree[d_code(dist)].Freq++; \
352 flush = (s->last_lit == s->lit_bufsize-1); \
353 }
354#else
355# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
356# define _tr_tally_dist(s, distance, length, flush) \
357 flush = _tr_tally(s, distance, length)
358#endif
359
360#endif /* DEFLATE_H */
361