1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>deflate.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.2.15 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="namespaces.html">Namespace List</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="classes.html">Alphabetical List</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Compound Members</a> </center>
<hr><h1>deflate.h</h1><div class="fragment"><pre>00001 <font class="comment">/* deflate.h -- internal compression state</font>
00002 <font class="comment"> * Copyright (C) 1995-1998 Jean-loup Gailly</font>
00003 <font class="comment"> * For conditions of distribution and use, see copyright notice in zlib.h </font>
00004 <font class="comment"> */</font>
00005
00006 <font class="comment">/* WARNING: this file should *not* be used by applications. It is</font>
00007 <font class="comment"> part of the implementation of the compression library and is</font>
00008 <font class="comment"> subject to change. Applications should only use zlib.h.</font>
00009 <font class="comment"> */</font>
00010
00011 <font class="comment">/* @(#) $Id: deflate_8h-source.html,v 1.3 2002/06/20 20:23:08 mgruner Exp $ */</font>
00012
00013 <font class="preprocessor">#ifndef _DEFLATE_H</font>
00014 <font class="preprocessor"></font><font class="preprocessor">#define _DEFLATE_H</font>
00015 <font class="preprocessor"></font>
00016 <font class="preprocessor">#include "zutil.h"</font>
00017
00018 <font class="comment">/* ===========================================================================</font>
00019 <font class="comment"> * Internal compression state.</font>
00020 <font class="comment"> */</font>
00021
00022 <font class="preprocessor">#define LENGTH_CODES 29</font>
00023 <font class="preprocessor"></font><font class="comment">/* number of length codes, not counting the special END_BLOCK code */</font>
00024
00025 <font class="preprocessor">#define LITERALS 256</font>
00026 <font class="preprocessor"></font><font class="comment">/* number of literal bytes 0..255 */</font>
00027
00028 <font class="preprocessor">#define L_CODES (LITERALS+1+LENGTH_CODES)</font>
00029 <font class="preprocessor"></font><font class="comment">/* number of Literal or Length codes, including the END_BLOCK code */</font>
00030
00031 <font class="preprocessor">#define D_CODES 30</font>
00032 <font class="preprocessor"></font><font class="comment">/* number of distance codes */</font>
00033
00034 <font class="preprocessor">#define BL_CODES 19</font>
00035 <font class="preprocessor"></font><font class="comment">/* number of codes used to transfer the bit lengths */</font>
00036
00037 <font class="preprocessor">#define HEAP_SIZE (2*L_CODES+1)</font>
00038 <font class="preprocessor"></font><font class="comment">/* maximum heap size */</font>
00039
00040 <font class="preprocessor">#define MAX_BITS 15</font>
00041 <font class="preprocessor"></font><font class="comment">/* All codes must not exceed MAX_BITS bits */</font>
00042
00043 <font class="preprocessor">#define INIT_STATE 42</font>
00044 <font class="preprocessor"></font><font class="preprocessor">#define BUSY_STATE 113</font>
00045 <font class="preprocessor"></font><font class="preprocessor">#define FINISH_STATE 666</font>
00046 <font class="preprocessor"></font><font class="comment">/* Stream status */</font>
00047
00048
00049 <font class="comment">/* Data structure describing a single value and its code string. */</font>
00050 <font class="keyword">typedef</font> <font class="keyword">struct </font>ct_data_s {
00051 <font class="keyword">union </font>{
00052 ush freq; <font class="comment">/* frequency count */</font>
00053 ush code; <font class="comment">/* bit string */</font>
00054 } fc;
00055 <font class="keyword">union </font>{
00056 ush dad; <font class="comment">/* father node in Huffman tree */</font>
00057 ush len; <font class="comment">/* length of bit string */</font>
00058 } dl;
00059 } FAR ct_data;
00060
00061 <font class="preprocessor">#define Freq fc.freq</font>
00062 <font class="preprocessor"></font><font class="preprocessor">#define Code fc.code</font>
00063 <font class="preprocessor"></font><font class="preprocessor">#define Dad dl.dad</font>
00064 <font class="preprocessor"></font><font class="preprocessor">#define Len dl.len</font>
00065 <font class="preprocessor"></font>
00066 <font class="keyword">typedef</font> <font class="keyword">struct </font>static_tree_desc_s static_tree_desc;
00067
00068 <font class="keyword">typedef</font> <font class="keyword">struct </font>tree_desc_s {
00069 ct_data *dyn_tree; <font class="comment">/* the dynamic tree */</font>
00070 <font class="keywordtype">int</font> max_code; <font class="comment">/* largest code with non zero frequency */</font>
00071 static_tree_desc *stat_desc; <font class="comment">/* the corresponding static tree */</font>
00072 } FAR tree_desc;
00073
00074 <font class="keyword">typedef</font> ush Pos;
00075 <font class="keyword">typedef</font> Pos FAR Posf;
00076 <font class="keyword">typedef</font> <font class="keywordtype">unsigned</font> IPos;
00077
00078 <font class="comment">/* A Pos is an index in the character window. We use short instead of int to</font>
00079 <font class="comment"> * save space in the various tables. IPos is used only for parameter passing.</font>
00080 <font class="comment"> */</font>
00081
00082 <font class="keyword">typedef</font> <font class="keyword">struct </font>internal_state {
00083 z_streamp strm; <font class="comment">/* pointer back to this zlib stream */</font>
00084 <font class="keywordtype">int</font> status; <font class="comment">/* as the name implies */</font>
00085 Bytef *pending_buf; <font class="comment">/* output still pending */</font>
00086 ulg pending_buf_size; <font class="comment">/* size of pending_buf */</font>
00087 Bytef *pending_out; <font class="comment">/* next pending byte to output to the stream */</font>
00088 <font class="keywordtype">int</font> pending; <font class="comment">/* nb of bytes in the pending buffer */</font>
00089 <font class="keywordtype">int</font> noheader; <font class="comment">/* suppress zlib header and adler32 */</font>
00090 Byte data_type; <font class="comment">/* UNKNOWN, BINARY or ASCII */</font>
00091 Byte method; <font class="comment">/* STORED (for zip only) or DEFLATED */</font>
00092 <font class="keywordtype">int</font> last_flush; <font class="comment">/* value of flush param for previous deflate call */</font>
00093
00094 <font class="comment">/* used by deflate.c: */</font>
00095
00096 uInt w_size; <font class="comment">/* LZ77 window size (32K by default) */</font>
00097 uInt w_bits; <font class="comment">/* log2(w_size) (8..16) */</font>
00098 uInt w_mask; <font class="comment">/* w_size - 1 */</font>
00099
00100 Bytef *window;
00101 <font class="comment">/* Sliding window. Input bytes are read into the second half of the window,</font>
00102 <font class="comment"> * and move to the first half later to keep a dictionary of at least wSize</font>
00103 <font class="comment"> * bytes. With this organization, matches are limited to a distance of</font>
00104 <font class="comment"> * wSize-MAX_MATCH bytes, but this ensures that IO is always</font>
00105 <font class="comment"> * performed with a length multiple of the block size. Also, it limits</font>
00106 <font class="comment"> * the window size to 64K, which is quite useful on MSDOS.</font>
00107 <font class="comment"> * To do: use the user input buffer as sliding window.</font>
00108 <font class="comment"> */</font>
00109
00110 ulg window_size;
00111 <font class="comment">/* Actual size of window: 2*wSize, except when the user input buffer</font>
00112 <font class="comment"> * is directly used as sliding window.</font>
00113 <font class="comment"> */</font>
00114
00115 Posf *prev;
00116 <font class="comment">/* Link to older string with same hash index. To limit the size of this</font>
00117 <font class="comment"> * array to 64K, this link is maintained only for the last 32K strings.</font>
00118 <font class="comment"> * An index in this array is thus a window index modulo 32K.</font>
00119 <font class="comment"> */</font>
00120
00121 Posf *head; <font class="comment">/* Heads of the hash chains or NIL. */</font>
00122
00123 uInt ins_h; <font class="comment">/* hash index of string to be inserted */</font>
00124 uInt hash_size; <font class="comment">/* number of elements in hash table */</font>
00125 uInt hash_bits; <font class="comment">/* log2(hash_size) */</font>
00126 uInt hash_mask; <font class="comment">/* hash_size-1 */</font>
00127
00128 uInt hash_shift;
00129 <font class="comment">/* Number of bits by which ins_h must be shifted at each input</font>
00130 <font class="comment"> * step. It must be such that after MIN_MATCH steps, the oldest</font>
00131 <font class="comment"> * byte no longer takes part in the hash key, that is:</font>
00132 <font class="comment"> * hash_shift * MIN_MATCH >= hash_bits</font>
00133 <font class="comment"> */</font>
00134
00135 <font class="keywordtype">long</font> block_start;
00136 <font class="comment">/* Window position at the beginning of the current output block. Gets</font>
00137 <font class="comment"> * negative when the window is moved backwards.</font>
00138 <font class="comment"> */</font>
00139
00140 uInt match_length; <font class="comment">/* length of best match */</font>
00141 IPos prev_match; <font class="comment">/* previous match */</font>
00142 <font class="keywordtype">int</font> match_available; <font class="comment">/* set if previous match exists */</font>
00143 uInt strstart; <font class="comment">/* start of string to insert */</font>
00144 uInt match_start; <font class="comment">/* start of matching string */</font>
00145 uInt lookahead; <font class="comment">/* number of valid bytes ahead in window */</font>
00146
00147 uInt prev_length;
00148 <font class="comment">/* Length of the best match at previous step. Matches not greater than this</font>
00149 <font class="comment"> * are discarded. This is used in the lazy match evaluation.</font>
00150 <font class="comment"> */</font>
00151
00152 uInt max_chain_length;
00153 <font class="comment">/* To speed up deflation, hash chains are never searched beyond this</font>
00154 <font class="comment"> * length. A higher limit improves compression ratio but degrades the</font>
00155 <font class="comment"> * speed.</font>
00156 <font class="comment"> */</font>
00157
00158 uInt max_lazy_match;
00159 <font class="comment">/* Attempt to find a better match only when the current match is strictly</font>
00160 <font class="comment"> * smaller than this value. This mechanism is used only for compression</font>
00161 <font class="comment"> * levels >= 4.</font>
00162 <font class="comment"> */</font>
00163 <font class="preprocessor"># define max_insert_length max_lazy_match</font>
00164 <font class="preprocessor"></font> <font class="comment">/* Insert new strings in the hash table only if the match length is not</font>
00165 <font class="comment"> * greater than this length. This saves time but degrades compression.</font>
00166 <font class="comment"> * max_insert_length is used only for compression levels <= 3.</font>
00167 <font class="comment"> */</font>
00168
00169 <font class="keywordtype">int</font> level; <font class="comment">/* compression level (1..9) */</font>
00170 <font class="keywordtype">int</font> strategy; <font class="comment">/* favor or force Huffman coding*/</font>
00171
00172 uInt good_match;
00173 <font class="comment">/* Use a faster search when the previous match is longer than this */</font>
00174
00175 <font class="keywordtype">int</font> nice_match; <font class="comment">/* Stop searching when current match exceeds this */</font>
00176
00177 <font class="comment">/* used by trees.c: */</font>
00178 <font class="comment">/* Didn't use ct_data typedef below to supress compiler warning */</font>
00179 <font class="keyword">struct </font>ct_data_s dyn_ltree[HEAP_SIZE]; <font class="comment">/* literal and length tree */</font>
00180 <font class="keyword">struct </font>ct_data_s dyn_dtree[2*D_CODES+1]; <font class="comment">/* distance tree */</font>
00181 <font class="keyword">struct </font>ct_data_s bl_tree[2*BL_CODES+1]; <font class="comment">/* Huffman tree for bit lengths */</font>
00182
00183 <font class="keyword">struct </font>tree_desc_s l_desc; <font class="comment">/* desc. for literal tree */</font>
00184 <font class="keyword">struct </font>tree_desc_s d_desc; <font class="comment">/* desc. for distance tree */</font>
00185 <font class="keyword">struct </font>tree_desc_s bl_desc; <font class="comment">/* desc. for bit length tree */</font>
00186
00187 ush bl_count[MAX_BITS+1];
00188 <font class="comment">/* number of codes at each bit length for an optimal tree */</font>
00189
00190 <font class="keywordtype">int</font> heap[2*L_CODES+1]; <font class="comment">/* heap used to build the Huffman trees */</font>
00191 <font class="keywordtype">int</font> heap_len; <font class="comment">/* number of elements in the heap */</font>
00192 <font class="keywordtype">int</font> heap_max; <font class="comment">/* element of largest frequency */</font>
00193 <font class="comment">/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.</font>
00194 <font class="comment"> * The same heap array is used to build all trees.</font>
00195 <font class="comment"> */</font>
00196
00197 uch depth[2*L_CODES+1];
00198 <font class="comment">/* Depth of each subtree used as tie breaker for trees of equal frequency</font>
00199 <font class="comment"> */</font>
00200
00201 uchf *l_buf; <font class="comment">/* buffer for literals or lengths */</font>
00202
00203 uInt lit_bufsize;
00204 <font class="comment">/* Size of match buffer for literals/lengths. There are 4 reasons for</font>
00205 <font class="comment"> * limiting lit_bufsize to 64K:</font>
00206 <font class="comment"> * - frequencies can be kept in 16 bit counters</font>
00207 <font class="comment"> * - if compression is not successful for the first block, all input</font>
00208 <font class="comment"> * data is still in the window so we can still emit a stored block even</font>
00209 <font class="comment"> * when input comes from standard input. (This can also be done for</font>
00210 <font class="comment"> * all blocks if lit_bufsize is not greater than 32K.)</font>
00211 <font class="comment"> * - if compression is not successful for a file smaller than 64K, we can</font>
00212 <font class="comment"> * even emit a stored file instead of a stored block (saving 5 bytes).</font>
00213 <font class="comment"> * This is applicable only for zip (not gzip or zlib).</font>
00214 <font class="comment"> * - creating new Huffman trees less frequently may not provide fast</font>
00215 <font class="comment"> * adaptation to changes in the input data statistics. (Take for</font>
00216 <font class="comment"> * example a binary file with poorly compressible code followed by</font>
00217 <font class="comment"> * a highly compressible string table.) Smaller buffer sizes give</font>
00218 <font class="comment"> * fast adaptation but have of course the overhead of transmitting</font>
00219 <font class="comment"> * trees more frequently.</font>
00220 <font class="comment"> * - I can't count above 4</font>
00221 <font class="comment"> */</font>
00222
00223 uInt last_lit; <font class="comment">/* running index in l_buf */</font>
00224
00225 ushf *d_buf;
00226 <font class="comment">/* Buffer for distances. To simplify the code, d_buf and l_buf have</font>
00227 <font class="comment"> * the same number of elements. To use different lengths, an extra flag</font>
00228 <font class="comment"> * array would be necessary.</font>
00229 <font class="comment"> */</font>
00230
00231 ulg opt_len; <font class="comment">/* bit length of current block with optimal trees */</font>
00232 ulg static_len; <font class="comment">/* bit length of current block with static trees */</font>
00233 uInt matches; <font class="comment">/* number of string matches in current block */</font>
00234 <font class="keywordtype">int</font> last_eob_len; <font class="comment">/* bit length of EOB code for last block */</font>
00235
00236 <font class="preprocessor">#ifdef DEBUG</font>
00237 <font class="preprocessor"></font> ulg compressed_len; <font class="comment">/* total bit length of compressed file mod 2^32 */</font>
00238 ulg bits_sent; <font class="comment">/* bit length of compressed data sent mod 2^32 */</font>
00239 <font class="preprocessor">#endif</font>
00240 <font class="preprocessor"></font>
00241 ush bi_buf;
00242 <font class="comment">/* Output buffer. bits are inserted starting at the bottom (least</font>
00243 <font class="comment"> * significant bits).</font>
00244 <font class="comment"> */</font>
00245 <font class="keywordtype">int</font> bi_valid;
00246 <font class="comment">/* Number of valid bits in bi_buf. All bits above the last valid bit</font>
00247 <font class="comment"> * are always zero.</font>
00248 <font class="comment"> */</font>
00249
00250 } FAR deflate_state;
00251
00252 <font class="comment">/* Output a byte on the stream.</font>
00253 <font class="comment"> * IN assertion: there is enough room in pending_buf.</font>
00254 <font class="comment"> */</font>
00255 <font class="preprocessor">#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}</font>
00256 <font class="preprocessor"></font>
00257
00258 <font class="preprocessor">#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)</font>
00259 <font class="preprocessor"></font><font class="comment">/* Minimum amount of lookahead, except at the end of the input file.</font>
00260 <font class="comment"> * See deflate.c for comments about the MIN_MATCH+1.</font>
00261 <font class="comment"> */</font>
00262
00263 <font class="preprocessor">#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)</font>
00264 <font class="preprocessor"></font><font class="comment">/* In order to simplify the code, particularly on 16 bit machines, match</font>
00265 <font class="comment"> * distances are limited to MAX_DIST instead of WSIZE.</font>
00266 <font class="comment"> */</font>
00267
00268 <font class="comment">/* in trees.c */</font>
00269 <font class="keywordtype">void</font> _tr_init OF((deflate_state *s));
00270 <font class="keywordtype">int</font> _tr_tally OF((deflate_state *s, <font class="keywordtype">unsigned</font> dist, <font class="keywordtype">unsigned</font> lc));
00271 <font class="keywordtype">void</font> _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
00272 <font class="keywordtype">int</font> eof));
00273 <font class="keywordtype">void</font> _tr_align OF((deflate_state *s));
00274 <font class="keywordtype">void</font> _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
00275 <font class="keywordtype">int</font> eof));
00276
00277 <font class="preprocessor">#define d_code(dist) \</font>
00278 <font class="preprocessor"> ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])</font>
00279 <font class="preprocessor"></font><font class="comment">/* Mapping from a distance to a distance code. dist is the distance - 1 and</font>
00280 <font class="comment"> * must not have side effects. _dist_code[256] and _dist_code[257] are never</font>
00281 <font class="comment"> * used.</font>
00282 <font class="comment"> */</font>
00283
00284 <font class="preprocessor">#ifndef DEBUG</font>
00285 <font class="preprocessor"></font><font class="comment">/* Inline versions of _tr_tally for speed: */</font>
00286
00287 <font class="preprocessor">#if defined(GEN_TREES_H) || !defined(STDC)</font>
00288 <font class="preprocessor"></font> <font class="keyword">extern</font> uch _length_code[];
00289 <font class="keyword">extern</font> uch _dist_code[];
00290 <font class="preprocessor">#else</font>
00291 <font class="preprocessor"></font> <font class="keyword">extern</font> <font class="keyword">const</font> uch _length_code[];
00292 <font class="keyword">extern</font> <font class="keyword">const</font> uch _dist_code[];
00293 <font class="preprocessor">#endif</font>
00294 <font class="preprocessor"></font>
00295 <font class="preprocessor"># define _tr_tally_lit(s, c, flush) \</font>
00296 <font class="preprocessor"> { uch cc = (c); \</font>
00297 <font class="preprocessor"> s->d_buf[s->last_lit] = 0; \</font>
00298 <font class="preprocessor"> s->l_buf[s->last_lit++] = cc; \</font>
00299 <font class="preprocessor"> s->dyn_ltree[cc].Freq++; \</font>
00300 <font class="preprocessor"> flush = (s->last_lit == s->lit_bufsize-1); \</font>
00301 <font class="preprocessor"> }</font>
00302 <font class="preprocessor"></font><font class="preprocessor"># define _tr_tally_dist(s, distance, length, flush) \</font>
00303 <font class="preprocessor"> { uch len = (length); \</font>
00304 <font class="preprocessor"> ush dist = (distance); \</font>
00305 <font class="preprocessor"> s->d_buf[s->last_lit] = dist; \</font>
00306 <font class="preprocessor"> s->l_buf[s->last_lit++] = len; \</font>
00307 <font class="preprocessor"> dist--; \</font>
00308 <font class="preprocessor"> s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \</font>
00309 <font class="preprocessor"> s->dyn_dtree[d_code(dist)].Freq++; \</font>
00310 <font class="preprocessor"> flush = (s->last_lit == s->lit_bufsize-1); \</font>
00311 <font class="preprocessor"> }</font>
00312 <font class="preprocessor"></font><font class="preprocessor">#else</font>
00313 <font class="preprocessor"></font><font class="preprocessor"># define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)</font>
00314 <font class="preprocessor"></font><font class="preprocessor"># define _tr_tally_dist(s, distance, length, flush) \</font>
00315 <font class="preprocessor"> flush = _tr_tally(s, distance, length) </font>
00316 <font class="preprocessor"></font><font class="preprocessor">#endif</font>
00317 <font class="preprocessor"></font>
00318 <font class="preprocessor">#endif</font>
</pre></div><hr><address align="right"><small>Generated on Thu Jun 20 22:12:58 2002 for The Sword Project by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0
width=110 height=53></a>1.2.15 </small></address>
</body>
</html>
|
