Linux Kernel
3.7.1
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Groups
Pages
lib
zlib_deflate
defutil.h
Go to the documentation of this file.
1
2
3
4
#define Assert(err, str)
5
#define Trace(dummy)
6
#define Tracev(dummy)
7
#define Tracecv(err, dummy)
8
#define Tracevv(dummy)
9
10
11
12
#define LENGTH_CODES 29
13
/* number of length codes, not counting the special END_BLOCK code */
14
15
#define LITERALS 256
16
/* number of literal bytes 0..255 */
17
18
#define L_CODES (LITERALS+1+LENGTH_CODES)
19
/* number of Literal or Length codes, including the END_BLOCK code */
20
21
#define D_CODES 30
22
/* number of distance codes */
23
24
#define BL_CODES 19
25
/* number of codes used to transfer the bit lengths */
26
27
#define HEAP_SIZE (2*L_CODES+1)
28
/* maximum heap size */
29
30
#define MAX_BITS 15
31
/* All codes must not exceed MAX_BITS bits */
32
33
#define INIT_STATE 42
34
#define BUSY_STATE 113
35
#define FINISH_STATE 666
36
/* Stream status */
37
38
39
/* Data structure describing a single value and its code string. */
40
typedef
struct
ct_data_s
{
41
union
{
42
ush
freq
;
/* frequency count */
43
ush
code
;
/* bit string */
44
}
fc
;
45
union
{
46
ush
dad
;
/* father node in Huffman tree */
47
ush
len
;
/* length of bit string */
48
}
dl
;
49
}
ct_data
;
50
51
#define Freq fc.freq
52
#define Code fc.code
53
#define Dad dl.dad
54
#define Len dl.len
55
56
typedef
struct
static_tree_desc_s
static_tree_desc
;
57
58
typedef
struct
tree_desc_s
{
59
ct_data
*
dyn_tree
;
/* the dynamic tree */
60
int
max_code
;
/* largest code with non zero frequency */
61
static_tree_desc
*
stat_desc
;
/* the corresponding static tree */
62
}
tree_desc
;
63
64
typedef
ush
Pos
;
65
typedef
unsigned
IPos
;
66
67
/* A Pos is an index in the character window. We use short instead of int to
68
* save space in the various tables. IPos is used only for parameter passing.
69
*/
70
71
typedef
struct
deflate_state
{
72
z_streamp
strm
;
/* pointer back to this zlib stream */
73
int
status
;
/* as the name implies */
74
Byte
*
pending_buf
;
/* output still pending */
75
ulg
pending_buf_size
;
/* size of pending_buf */
76
Byte
*
pending_out
;
/* next pending byte to output to the stream */
77
int
pending
;
/* nb of bytes in the pending buffer */
78
int
noheader
;
/* suppress zlib header and adler32 */
79
Byte
data_type
;
/* UNKNOWN, BINARY or ASCII */
80
Byte
method
;
/* STORED (for zip only) or DEFLATED */
81
int
last_flush
;
/* value of flush param for previous deflate call */
82
83
/* used by deflate.c: */
84
85
uInt
w_size
;
/* LZ77 window size (32K by default) */
86
uInt
w_bits
;
/* log2(w_size) (8..16) */
87
uInt
w_mask
;
/* w_size - 1 */
88
89
Byte
*
window
;
90
/* Sliding window. Input bytes are read into the second half of the window,
91
* and move to the first half later to keep a dictionary of at least wSize
92
* bytes. With this organization, matches are limited to a distance of
93
* wSize-MAX_MATCH bytes, but this ensures that IO is always
94
* performed with a length multiple of the block size. Also, it limits
95
* the window size to 64K, which is quite useful on MSDOS.
96
* To do: use the user input buffer as sliding window.
97
*/
98
99
ulg
window_size
;
100
/* Actual size of window: 2*wSize, except when the user input buffer
101
* is directly used as sliding window.
102
*/
103
104
Pos
*
prev
;
105
/* Link to older string with same hash index. To limit the size of this
106
* array to 64K, this link is maintained only for the last 32K strings.
107
* An index in this array is thus a window index modulo 32K.
108
*/
109
110
Pos
*
head
;
/* Heads of the hash chains or NIL. */
111
112
uInt
ins_h
;
/* hash index of string to be inserted */
113
uInt
hash_size
;
/* number of elements in hash table */
114
uInt
hash_bits
;
/* log2(hash_size) */
115
uInt
hash_mask
;
/* hash_size-1 */
116
117
uInt
hash_shift
;
118
/* Number of bits by which ins_h must be shifted at each input
119
* step. It must be such that after MIN_MATCH steps, the oldest
120
* byte no longer takes part in the hash key, that is:
121
* hash_shift * MIN_MATCH >= hash_bits
122
*/
123
124
long
block_start
;
125
/* Window position at the beginning of the current output block. Gets
126
* negative when the window is moved backwards.
127
*/
128
129
uInt
match_length
;
/* length of best match */
130
IPos
prev_match
;
/* previous match */
131
int
match_available
;
/* set if previous match exists */
132
uInt
strstart
;
/* start of string to insert */
133
uInt
match_start
;
/* start of matching string */
134
uInt
lookahead
;
/* number of valid bytes ahead in window */
135
136
uInt
prev_length
;
137
/* Length of the best match at previous step. Matches not greater than this
138
* are discarded. This is used in the lazy match evaluation.
139
*/
140
141
uInt
max_chain_length
;
142
/* To speed up deflation, hash chains are never searched beyond this
143
* length. A higher limit improves compression ratio but degrades the
144
* speed.
145
*/
146
147
uInt
max_lazy_match
;
148
/* Attempt to find a better match only when the current match is strictly
149
* smaller than this value. This mechanism is used only for compression
150
* levels >= 4.
151
*/
152
# define max_insert_length max_lazy_match
153
/* Insert new strings in the hash table only if the match length is not
154
* greater than this length. This saves time but degrades compression.
155
* max_insert_length is used only for compression levels <= 3.
156
*/
157
158
int
level
;
/* compression level (1..9) */
159
int
strategy
;
/* favor or force Huffman coding*/
160
161
uInt
good_match
;
162
/* Use a faster search when the previous match is longer than this */
163
164
int
nice_match
;
/* Stop searching when current match exceeds this */
165
166
/* used by trees.c: */
167
/* Didn't use ct_data typedef below to suppress compiler warning */
168
struct
ct_data_s
dyn_ltree
[
HEAP_SIZE
];
/* literal and length tree */
169
struct
ct_data_s
dyn_dtree
[2*
D_CODES
+1];
/* distance tree */
170
struct
ct_data_s
bl_tree
[2*
BL_CODES
+1];
/* Huffman tree for bit lengths */
171
172
struct
tree_desc_s
l_desc
;
/* desc. for literal tree */
173
struct
tree_desc_s
d_desc
;
/* desc. for distance tree */
174
struct
tree_desc_s
bl_desc
;
/* desc. for bit length tree */
175
176
ush
bl_count
[
MAX_BITS
+1];
177
/* number of codes at each bit length for an optimal tree */
178
179
int
heap
[2*
L_CODES
+1];
/* heap used to build the Huffman trees */
180
int
heap_len
;
/* number of elements in the heap */
181
int
heap_max
;
/* element of largest frequency */
182
/* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
183
* The same heap array is used to build all trees.
184
*/
185
186
uch
depth
[2*
L_CODES
+1];
187
/* Depth of each subtree used as tie breaker for trees of equal frequency
188
*/
189
190
uch
*
l_buf
;
/* buffer for literals or lengths */
191
192
uInt
lit_bufsize
;
193
/* Size of match buffer for literals/lengths. There are 4 reasons for
194
* limiting lit_bufsize to 64K:
195
* - frequencies can be kept in 16 bit counters
196
* - if compression is not successful for the first block, all input
197
* data is still in the window so we can still emit a stored block even
198
* when input comes from standard input. (This can also be done for
199
* all blocks if lit_bufsize is not greater than 32K.)
200
* - if compression is not successful for a file smaller than 64K, we can
201
* even emit a stored file instead of a stored block (saving 5 bytes).
202
* This is applicable only for zip (not gzip or zlib).
203
* - creating new Huffman trees less frequently may not provide fast
204
* adaptation to changes in the input data statistics. (Take for
205
* example a binary file with poorly compressible code followed by
206
* a highly compressible string table.) Smaller buffer sizes give
207
* fast adaptation but have of course the overhead of transmitting
208
* trees more frequently.
209
* - I can't count above 4
210
*/
211
212
uInt
last_lit
;
/* running index in l_buf */
213
214
ush
*
d_buf
;
215
/* Buffer for distances. To simplify the code, d_buf and l_buf have
216
* the same number of elements. To use different lengths, an extra flag
217
* array would be necessary.
218
*/
219
220
ulg
opt_len
;
/* bit length of current block with optimal trees */
221
ulg
static_len
;
/* bit length of current block with static trees */
222
ulg
compressed_len
;
/* total bit length of compressed file */
223
uInt
matches
;
/* number of string matches in current block */
224
int
last_eob_len
;
/* bit length of EOB code for last block */
225
226
#ifdef DEBUG_ZLIB
227
ulg
bits_sent;
/* bit length of the compressed data */
228
#endif
229
230
ush
bi_buf
;
231
/* Output buffer. bits are inserted starting at the bottom (least
232
* significant bits).
233
*/
234
int
bi_valid
;
235
/* Number of valid bits in bi_buf. All bits above the last valid bit
236
* are always zero.
237
*/
238
239
}
deflate_state
;
240
241
typedef
struct
deflate_workspace
{
242
/* State memory for the deflator */
243
deflate_state
deflate_memory
;
244
Byte
*
window_memory
;
245
Pos
*
prev_memory
;
246
Pos
*
head_memory
;
247
char
*
overlay_memory
;
248
}
deflate_workspace
;
249
250
#define zlib_deflate_window_memsize(windowBits) \
251
(2 * (1 << (windowBits)) * sizeof(Byte))
252
#define zlib_deflate_prev_memsize(windowBits) \
253
((1 << (windowBits)) * sizeof(Pos))
254
#define zlib_deflate_head_memsize(memLevel) \
255
((1 << ((memLevel)+7)) * sizeof(Pos))
256
#define zlib_deflate_overlay_memsize(memLevel) \
257
((1 << ((memLevel)+6)) * (sizeof(ush)+2))
258
259
/* Output a byte on the stream.
260
* IN assertion: there is enough room in pending_buf.
261
*/
262
#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
263
264
265
#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
266
/* Minimum amount of lookahead, except at the end of the input file.
267
* See deflate.c for comments about the MIN_MATCH+1.
268
*/
269
270
#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
271
/* In order to simplify the code, particularly on 16 bit machines, match
272
* distances are limited to MAX_DIST instead of WSIZE.
273
*/
274
275
/* in trees.c */
276
void
zlib_tr_init
(
deflate_state
*
s
);
277
int
zlib_tr_tally
(
deflate_state
*
s
,
unsigned
dist
,
unsigned
lc
);
278
ulg
zlib_tr_flush_block
(
deflate_state
*
s
,
char
*
buf
,
ulg
stored_len,
279
int
eof);
280
void
zlib_tr_align
(
deflate_state
*
s
);
281
void
zlib_tr_stored_block
(
deflate_state
*
s
,
char
*
buf
,
ulg
stored_len,
282
int
eof);
283
void
zlib_tr_stored_type_only
(
deflate_state
*);
284
285
286
/* ===========================================================================
287
* Output a short LSB first on the stream.
288
* IN assertion: there is enough room in pendingBuf.
289
*/
290
#define put_short(s, w) { \
291
put_byte(s, (uch)((w) & 0xff)); \
292
put_byte(s, (uch)((ush)(w) >> 8)); \
293
}
294
295
/* ===========================================================================
296
* Reverse the first len bits of a code, using straightforward code (a faster
297
* method would use a table)
298
* IN assertion: 1 <= len <= 15
299
*/
300
static
inline
unsigned
bi_reverse(
unsigned
code
,
/* the value to invert */
301
int
len)
/* its bit length */
302
{
303
register
unsigned
res
= 0;
304
do
{
305
res |= code & 1;
306
code >>= 1, res <<= 1;
307
}
while
(--len > 0);
308
return
res >> 1;
309
}
310
311
/* ===========================================================================
312
* Flush the bit buffer, keeping at most 7 bits in it.
313
*/
314
static
inline
void
bi_flush(
deflate_state
*
s
)
315
{
316
if
(s->
bi_valid
== 16) {
317
put_short
(s, s->
bi_buf
);
318
s->
bi_buf
= 0;
319
s->
bi_valid
= 0;
320
}
else
if
(s->
bi_valid
>= 8) {
321
put_byte
(s, (
Byte
)s->
bi_buf
);
322
s->
bi_buf
>>= 8;
323
s->
bi_valid
-= 8;
324
}
325
}
326
327
/* ===========================================================================
328
* Flush the bit buffer and align the output on a byte boundary
329
*/
330
static
inline
void
bi_windup(
deflate_state
*s)
331
{
332
if
(s->
bi_valid
> 8) {
333
put_short
(s, s->
bi_buf
);
334
}
else
if
(s->
bi_valid
> 0) {
335
put_byte
(s, (
Byte
)s->
bi_buf
);
336
}
337
s->
bi_buf
= 0;
338
s->
bi_valid
= 0;
339
#ifdef DEBUG_ZLIB
340
s->bits_sent = (s->bits_sent+7) & ~7;
341
#endif
342
}
343
Generated on Thu Jan 10 2013 14:56:00 for Linux Kernel by
1.8.2