source: trunk/third/zlib/deflate.h @ 15211

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