Mercurial > ~darius > hgwebdir.cgi > paradise_server

comparison zlib/deflate.h @ 10:1040ca591f2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First entry of Paradise Server 2.9 patch 10 Beta
author darius
date Sat, 06 Dec 1997 04:37:18 +0000
parents
children
comparison
equal deleted inserted replaced
9:331055a97a9d 10:1040ca591f2e
1 /* deflate.h -- internal compression state
2 * Copyright (C) 1995 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,v 1.1.1.1 1997/12/06 04:37:17 darius Exp $ */
12
13 #include "zutil.h"
14
15 /* ===========================================================================
16 * Internal compression state.
17 */
18
19 /* Data type */
20 #define BINARY 0
21 #define ASCII 1
22 #define UNKNOWN 2
23
24 #define LENGTH_CODES 29
25 /* number of length codes, not counting the special END_BLOCK code */
26
27 #define LITERALS 256
28 /* number of literal bytes 0..255 */
29
30 #define L_CODES (LITERALS+1+LENGTH_CODES)
31 /* number of Literal or Length codes, including the END_BLOCK code */
32
33 #define D_CODES 30
34 /* number of distance codes */
35
36 #define BL_CODES 19
37 /* number of codes used to transfer the bit lengths */
38
39 #define HEAP_SIZE (2*L_CODES+1)
40 /* maximum heap size */
41
42 #define MAX_BITS 15
43 /* All codes must not exceed MAX_BITS bits */
44
45 #define INIT_STATE 42
46 #define BUSY_STATE 113
47 #define FINISH_STATE 666
48 /* Stream status */
49
50
51 /* Data structure describing a single value and its code string. */
52 typedef struct ct_data_s {
53 union {
54 ush freq; /* frequency count */
55 ush code; /* bit string */
56 } fc;
57 union {
58 ush dad; /* father node in Huffman tree */
59 ush len; /* length of bit string */
60 } dl;
61 } FAR ct_data;
62
63 #define Freq fc.freq
64 #define Code fc.code
65 #define Dad dl.dad
66 #define Len dl.len
67
68 typedef struct static_tree_desc_s static_tree_desc;
69
70 typedef struct tree_desc_s {
71 ct_data *dyn_tree; /* the dynamic tree */
72 int max_code; /* largest code with non zero frequency */
73 static_tree_desc *stat_desc; /* the corresponding static tree */
74 } FAR tree_desc;
75
76 typedef ush Pos;
77 typedef Pos FAR Posf;
78 typedef unsigned IPos;
79
80 /* A Pos is an index in the character window. We use short instead of int to
81 * save space in the various tables. IPos is used only for parameter passing.
82 */
83
84 typedef struct internal_state {
85 z_stream *strm; /* pointer back to this zlib stream */
86 int status; /* as the name implies */
87 Bytef *pending_buf; /* output still pending */
88 Bytef *pending_out; /* next pending byte to output to the stream */
89 int pending; /* nb of bytes in the pending buffer */
90 uLong adler; /* adler32 of uncompressed data */
91 int noheader; /* suppress zlib header and adler32 */
92 Byte data_type; /* UNKNOWN, BINARY or ASCII */
93 Byte method; /* STORED (for zip only) or DEFLATED */
94
95 /* used by deflate.c: */
96
97 uInt w_size; /* LZ77 window size (32K by default) */
98 uInt w_bits; /* log2(w_size) (8..16) */
99 uInt w_mask; /* w_size - 1 */
100
101 Bytef *window;
102 /* Sliding window. Input bytes are read into the second half of the window,
103 * and move to the first half later to keep a dictionary of at least wSize
104 * bytes. With this organization, matches are limited to a distance of
105 * wSize-MAX_MATCH bytes, but this ensures that IO is always
106 * performed with a length multiple of the block size. Also, it limits
107 * the window size to 64K, which is quite useful on MSDOS.
108 * To do: use the user input buffer as sliding window.
109 */
110
111 ulg window_size;
112 /* Actual size of window: 2*wSize, except when the user input buffer
113 * is directly used as sliding window.
114 */
115
116 Posf *prev;
117 /* Link to older string with same hash index. To limit the size of this
118 * array to 64K, this link is maintained only for the last 32K strings.
119 * An index in this array is thus a window index modulo 32K.
120 */
121
122 Posf *head; /* Heads of the hash chains or NIL. */
123
124 uInt ins_h; /* hash index of string to be inserted */
125 uInt hash_size; /* number of elements in hash table */
126 uInt hash_bits; /* log2(hash_size) */
127 uInt hash_mask; /* hash_size-1 */
128
129 uInt hash_shift;
130 /* Number of bits by which ins_h must be shifted at each input
131 * step. It must be such that after MIN_MATCH steps, the oldest
132 * byte no longer takes part in the hash key, that is:
133 * hash_shift * MIN_MATCH >= hash_bits
134 */
135
136 long block_start;
137 /* Window position at the beginning of the current output block. Gets
138 * negative when the window is moved backwards.
139 */
140
141 uInt match_length; /* length of best match */
142 IPos prev_match; /* previous match */
143 int match_available; /* set if previous match exists */
144 uInt strstart; /* start of string to insert */
145 uInt match_start; /* start of matching string */
146 uInt lookahead; /* number of valid bytes ahead in window */
147
148 uInt prev_length;
149 /* Length of the best match at previous step. Matches not greater than this
150 * are discarded. This is used in the lazy match evaluation.
151 */
152
153 uInt max_chain_length;
154 /* To speed up deflation, hash chains are never searched beyond this
155 * length. A higher limit improves compression ratio but degrades the
156 * speed.
157 */
158
159 uInt max_lazy_match;
160 /* Attempt to find a better match only when the current match is strictly
161 * smaller than this value. This mechanism is used only for compression
162 * levels >= 4.
163 */
164 # define max_insert_length max_lazy_match
165 /* Insert new strings in the hash table only if the match length is not
166 * greater than this length. This saves time but degrades compression.
167 * max_insert_length is used only for compression levels <= 3.
168 */
169
170 int level; /* compression level (1..9) */
171 int strategy; /* favor or force Huffman coding*/
172
173 uInt good_match;
174 /* Use a faster search when the previous match is longer than this */
175
176 int nice_match; /* Stop searching when current match exceeds this */
177
178 /* used by trees.c: */
179 /* Didn't use ct_data typedef below to supress compiler warning */
180 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
181 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
182 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
183
184 struct tree_desc_s l_desc; /* desc. for literal tree */
185 struct tree_desc_s d_desc; /* desc. for distance tree */
186 struct tree_desc_s bl_desc; /* desc. for bit length tree */
187
188 ush bl_count[MAX_BITS+1];
189 /* number of codes at each bit length for an optimal tree */
190
191 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
192 int heap_len; /* number of elements in the heap */
193 int heap_max; /* element of largest frequency */
194 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
195 * The same heap array is used to build all trees.
196 */
197
198 uch depth[2*L_CODES+1];
199 /* Depth of each subtree used as tie breaker for trees of equal frequency
200 */
201
202 uchf *l_buf; /* buffer for literals or lengths */
203
204 uInt lit_bufsize;
205 /* Size of match buffer for literals/lengths. There are 4 reasons for
206 * limiting lit_bufsize to 64K:
207 * - frequencies can be kept in 16 bit counters
208 * - if compression is not successful for the first block, all input
209 * data is still in the window so we can still emit a stored block even
210 * when input comes from standard input. (This can also be done for
211 * all blocks if lit_bufsize is not greater than 32K.)
212 * - if compression is not successful for a file smaller than 64K, we can
213 * even emit a stored file instead of a stored block (saving 5 bytes).
214 * This is applicable only for zip (not gzip or zlib).
215 * - creating new Huffman trees less frequently may not provide fast
216 * adaptation to changes in the input data statistics. (Take for
217 * example a binary file with poorly compressible code followed by
218 * a highly compressible string table.) Smaller buffer sizes give
219 * fast adaptation but have of course the overhead of transmitting
220 * trees more frequently.
221 * - I can't count above 4
222 */
223
224 uInt last_lit; /* running index in l_buf */
225
226 ushf *d_buf;
227 /* Buffer for distances. To simplify the code, d_buf and l_buf have
228 * the same number of elements. To use different lengths, an extra flag
229 * array would be necessary.
230 */
231
232 ulg opt_len; /* bit length of current block with optimal trees */
233 ulg static_len; /* bit length of current block with static trees */
234 ulg compressed_len; /* total bit length of compressed file */
235 uInt matches; /* number of string matches in current block */
236 int last_eob_len; /* bit length of EOB code for last block */
237
238 #ifdef DEBUG
239 ulg bits_sent; /* bit length of the compressed data */
240 #endif
241
242 ush bi_buf;
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
251 } FAR deflate_state;
252
253 /* Output a byte on the stream.
254 * IN assertion: there is enough room in pending_buf.
255 */
256 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
257
258
259 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
260 /* Minimum amount of lookahead, except at the end of the input file.
261 * See deflate.c for comments about the MIN_MATCH+1.
262 */
263
264 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
265 /* In order to simplify the code, particularly on 16 bit machines, match
266 * distances are limited to MAX_DIST instead of WSIZE.
267 */
268
269 /* in trees.c */
270 void ct_init OF((deflate_state *s));
271 int ct_tally OF((deflate_state *s, int dist, int lc));
272 ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, int eof));
273 void ct_align OF((deflate_state *s));
274 void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
275 int eof));