Skip to content
This repository
tag: v0.5.9
Fetching contributors…

Cannot retrieve contributors at this time

file 331 lines (270 sloc) 12.173 kb
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
/* deflate.h -- internal compression state
* Copyright (C) 1995-2004 Jean-loup Gailly
* For conditions of distribution and use, see copyright notice in zlib.h
*/

/* WARNING: this file should *not* be used by applications. It is
part of the implementation of the compression library and is
subject to change. Applications should only use zlib.h.
*/

/* @(#) $Id: deflate.h,v 3.6 2005/08/04 19:14:14 tor%cs.brown.edu Exp $ */

#ifndef DEFLATE_H
#define DEFLATE_H

#include "zutil.h"

/* define NO_GZIP when compiling if you want to disable gzip header and
trailer creation by deflate(). NO_GZIP would be used to avoid linking in
the crc code when it is not needed. For shared libraries, gzip encoding
should be left enabled. */
#ifndef NO_GZIP
# define GZIP
#endif

/* ===========================================================================
* Internal compression state.
*/

#define LENGTH_CODES 29
/* number of length codes, not counting the special END_BLOCK code */

#define LITERALS 256
/* number of literal bytes 0..255 */

#define L_CODES (LITERALS+1+LENGTH_CODES)
/* number of Literal or Length codes, including the END_BLOCK code */

#define D_CODES 30
/* number of distance codes */

#define BL_CODES 19
/* number of codes used to transfer the bit lengths */

#define HEAP_SIZE (2*L_CODES+1)
/* maximum heap size */

#define MAX_BITS 15
/* All codes must not exceed MAX_BITS bits */

#define INIT_STATE 42
#define EXTRA_STATE 69
#define NAME_STATE 73
#define COMMENT_STATE 91
#define HCRC_STATE 103
#define BUSY_STATE 113
#define FINISH_STATE 666
/* Stream status */


/* Data structure describing a single value and its code string. */
typedef struct ct_data_s {
    union {
        ush freq; /* frequency count */
        ush code; /* bit string */
    } fc;
    union {
        ush dad; /* father node in Huffman tree */
        ush len; /* length of bit string */
    } dl;
} FAR ct_data;

#define Freq fc.freq
#define Code fc.code
#define Dad dl.dad
#define Len dl.len

typedef struct static_tree_desc_s static_tree_desc;

typedef struct tree_desc_s {
    ct_data *dyn_tree; /* the dynamic tree */
    int max_code; /* largest code with non zero frequency */
    static_tree_desc *stat_desc; /* the corresponding static tree */
} FAR tree_desc;

typedef ush Pos;
typedef Pos FAR Posf;
typedef unsigned IPos;

/* A Pos is an index in the character window. We use short instead of int to
* save space in the various tables. IPos is used only for parameter passing.
*/

typedef struct internal_state {
    z_streamp strm; /* pointer back to this zlib stream */
    int status; /* as the name implies */
    Bytef *pending_buf; /* output still pending */
    ulg pending_buf_size; /* size of pending_buf */
    Bytef *pending_out; /* next pending byte to output to the stream */
    uInt pending; /* nb of bytes in the pending buffer */
    int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
    gz_headerp gzhead; /* gzip header information to write */
    uInt gzindex; /* where in extra, name, or comment */
    Byte method; /* STORED (for zip only) or DEFLATED */
    int last_flush; /* value of flush param for previous deflate call */

                /* used by deflate.c: */

    uInt w_size; /* LZ77 window size (32K by default) */
    uInt w_bits; /* log2(w_size) (8..16) */
    uInt w_mask; /* w_size - 1 */

    Bytef *window;
    /* Sliding window. Input bytes are read into the second half of the window,
* and move to the first half later to keep a dictionary of at least wSize
* bytes. With this organization, matches are limited to a distance of
* wSize-MAX_MATCH bytes, but this ensures that IO is always
* performed with a length multiple of the block size. Also, it limits
* the window size to 64K, which is quite useful on MSDOS.
* To do: use the user input buffer as sliding window.
*/

    ulg window_size;
    /* Actual size of window: 2*wSize, except when the user input buffer
* is directly used as sliding window.
*/

    Posf *prev;
    /* Link to older string with same hash index. To limit the size of this
* array to 64K, this link is maintained only for the last 32K strings.
* An index in this array is thus a window index modulo 32K.
*/

    Posf *head; /* Heads of the hash chains or NIL. */

    uInt ins_h; /* hash index of string to be inserted */
    uInt hash_size; /* number of elements in hash table */
    uInt hash_bits; /* log2(hash_size) */
    uInt hash_mask; /* hash_size-1 */

    uInt hash_shift;
    /* Number of bits by which ins_h must be shifted at each input
* step. It must be such that after MIN_MATCH steps, the oldest
* byte no longer takes part in the hash key, that is:
* hash_shift * MIN_MATCH >= hash_bits
*/

    long block_start;
    /* Window position at the beginning of the current output block. Gets
* negative when the window is moved backwards.
*/

    uInt match_length; /* length of best match */
    IPos prev_match; /* previous match */
    int match_available; /* set if previous match exists */
    uInt strstart; /* start of string to insert */
    uInt match_start; /* start of matching string */
    uInt lookahead; /* number of valid bytes ahead in window */

    uInt prev_length;
    /* Length of the best match at previous step. Matches not greater than this
* are discarded. This is used in the lazy match evaluation.
*/

    uInt max_chain_length;
    /* To speed up deflation, hash chains are never searched beyond this
* length. A higher limit improves compression ratio but degrades the
* speed.
*/

    uInt max_lazy_match;
    /* Attempt to find a better match only when the current match is strictly
* smaller than this value. This mechanism is used only for compression
* levels >= 4.
*/
# define max_insert_length max_lazy_match
    /* Insert new strings in the hash table only if the match length is not
* greater than this length. This saves time but degrades compression.
* max_insert_length is used only for compression levels <= 3.
*/

    int level; /* compression level (1..9) */
    int strategy; /* favor or force Huffman coding*/

    uInt good_match;
    /* Use a faster search when the previous match is longer than this */

    int nice_match; /* Stop searching when current match exceeds this */

                /* used by trees.c: */
    /* Didn't use ct_data typedef below to supress compiler warning */
    struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
    struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
    struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */

    struct tree_desc_s l_desc; /* desc. for literal tree */
    struct tree_desc_s d_desc; /* desc. for distance tree */
    struct tree_desc_s bl_desc; /* desc. for bit length tree */

    ush bl_count[MAX_BITS+1];
    /* number of codes at each bit length for an optimal tree */

    int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
    int heap_len; /* number of elements in the heap */
    int heap_max; /* element of largest frequency */
    /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
* The same heap array is used to build all trees.
*/

    uch depth[2*L_CODES+1];
    /* Depth of each subtree used as tie breaker for trees of equal frequency
*/

    uchf *l_buf; /* buffer for literals or lengths */

    uInt lit_bufsize;
    /* Size of match buffer for literals/lengths. There are 4 reasons for
* limiting lit_bufsize to 64K:
* - frequencies can be kept in 16 bit counters
* - if compression is not successful for the first block, all input
* data is still in the window so we can still emit a stored block even
* when input comes from standard input. (This can also be done for
* all blocks if lit_bufsize is not greater than 32K.)
* - if compression is not successful for a file smaller than 64K, we can
* even emit a stored file instead of a stored block (saving 5 bytes).
* This is applicable only for zip (not gzip or zlib).
* - creating new Huffman trees less frequently may not provide fast
* adaptation to changes in the input data statistics. (Take for
* example a binary file with poorly compressible code followed by
* a highly compressible string table.) Smaller buffer sizes give
* fast adaptation but have of course the overhead of transmitting
* trees more frequently.
* - I can't count above 4
*/

    uInt last_lit; /* running index in l_buf */

    ushf *d_buf;
    /* Buffer for distances. To simplify the code, d_buf and l_buf have
* the same number of elements. To use different lengths, an extra flag
* array would be necessary.
*/

    ulg opt_len; /* bit length of current block with optimal trees */
    ulg static_len; /* bit length of current block with static trees */
    uInt matches; /* number of string matches in current block */
    int last_eob_len; /* bit length of EOB code for last block */

#ifdef DEBUG
    ulg compressed_len; /* total bit length of compressed file mod 2^32 */
    ulg bits_sent; /* bit length of compressed data sent mod 2^32 */
#endif

    ush bi_buf;
    /* Output buffer. bits are inserted starting at the bottom (least
* significant bits).
*/
    int bi_valid;
    /* Number of valid bits in bi_buf. All bits above the last valid bit
* are always zero.
*/

} FAR deflate_state;

/* Output a byte on the stream.
* IN assertion: there is enough room in pending_buf.
*/
#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}


#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
/* Minimum amount of lookahead, except at the end of the input file.
* See deflate.c for comments about the MIN_MATCH+1.
*/

#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
/* In order to simplify the code, particularly on 16 bit machines, match
* distances are limited to MAX_DIST instead of WSIZE.
*/

        /* in trees.c */
void _tr_init OF((deflate_state *s));
int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));
void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
                          int eof));
void _tr_align OF((deflate_state *s));
void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
                          int eof));

#define d_code(dist) \
((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
/* Mapping from a distance to a distance code. dist is the distance - 1 and
* must not have side effects. _dist_code[256] and _dist_code[257] are never
* used.
*/

#ifndef DEBUG
/* Inline versions of _tr_tally for speed: */

#if defined(GEN_TREES_H) || !defined(STDC)
  extern uch _length_code[];
  extern uch _dist_code[];
#else
  extern const uch _length_code[];
  extern const uch _dist_code[];
#endif

# define _tr_tally_lit(s, c, flush) \
{ uch cc = (c); \
s->d_buf[s->last_lit] = 0; \
s->l_buf[s->last_lit++] = cc; \
s->dyn_ltree[cc].Freq++; \
flush = (s->last_lit == s->lit_bufsize-1); \
}
# define _tr_tally_dist(s, distance, length, flush) \
{ uch len = (length); \
ush dist = (distance); \
s->d_buf[s->last_lit] = dist; \
s->l_buf[s->last_lit++] = len; \
dist--; \
s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
s->dyn_dtree[d_code(dist)].Freq++; \
flush = (s->last_lit == s->lit_bufsize-1); \
}
#else
# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
# define _tr_tally_dist(s, distance, length, flush) \
flush = _tr_tally(s, distance, length)
#endif

#endif /* DEFLATE_H */
Something went wrong with that request. Please try again.