muscle7.62.zip: muscle/zlib/zlib/deflate.h

"Fossies" - the Fresh Open Source Software Archive

Member "muscle/zlib/zlib/deflate.h" (21 Nov 2020, 13150 Bytes) of package /linux/privat/muscle7.62.zip:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "deflate.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report:

7.61_vs_7.62.

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