lemon-project-template-glpk
diff deps/glpk/src/zlib/deflate.h @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/src/zlib/deflate.h Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,342 @@ 1.4 +/* deflate.h -- internal compression state 1.5 + * Copyright (C) 1995-2010 Jean-loup Gailly 1.6 + * For conditions of distribution and use, see copyright notice in zlib.h 1.7 + */ 1.8 + 1.9 +/* WARNING: this file should *not* be used by applications. It is 1.10 + part of the implementation of the compression library and is 1.11 + subject to change. Applications should only use zlib.h. 1.12 + */ 1.13 + 1.14 +/* @(#) $Id$ */ 1.15 + 1.16 +#ifndef DEFLATE_H 1.17 +#define DEFLATE_H 1.18 + 1.19 +#include "zutil.h" 1.20 + 1.21 +/* define NO_GZIP when compiling if you want to disable gzip header and 1.22 + trailer creation by deflate(). NO_GZIP would be used to avoid linking in 1.23 + the crc code when it is not needed. For shared libraries, gzip encoding 1.24 + should be left enabled. */ 1.25 +#ifndef NO_GZIP 1.26 +# define GZIP 1.27 +#endif 1.28 + 1.29 +/* =========================================================================== 1.30 + * Internal compression state. 1.31 + */ 1.32 + 1.33 +#define LENGTH_CODES 29 1.34 +/* number of length codes, not counting the special END_BLOCK code */ 1.35 + 1.36 +#define LITERALS 256 1.37 +/* number of literal bytes 0..255 */ 1.38 + 1.39 +#define L_CODES (LITERALS+1+LENGTH_CODES) 1.40 +/* number of Literal or Length codes, including the END_BLOCK code */ 1.41 + 1.42 +#define D_CODES 30 1.43 +/* number of distance codes */ 1.44 + 1.45 +#define BL_CODES 19 1.46 +/* number of codes used to transfer the bit lengths */ 1.47 + 1.48 +#define HEAP_SIZE (2*L_CODES+1) 1.49 +/* maximum heap size */ 1.50 + 1.51 +#define MAX_BITS 15 1.52 +/* All codes must not exceed MAX_BITS bits */ 1.53 + 1.54 +#define INIT_STATE 42 1.55 +#define EXTRA_STATE 69 1.56 +#define NAME_STATE 73 1.57 +#define COMMENT_STATE 91 1.58 +#define HCRC_STATE 103 1.59 +#define BUSY_STATE 113 1.60 +#define FINISH_STATE 666 1.61 +/* Stream status */ 1.62 + 1.63 + 1.64 +/* Data structure describing a single value and its code string. */ 1.65 +typedef struct ct_data_s { 1.66 + union { 1.67 + ush freq; /* frequency count */ 1.68 + ush code; /* bit string */ 1.69 + } fc; 1.70 + union { 1.71 + ush dad; /* father node in Huffman tree */ 1.72 + ush len; /* length of bit string */ 1.73 + } dl; 1.74 +} FAR ct_data; 1.75 + 1.76 +#define Freq fc.freq 1.77 +#define Code fc.code 1.78 +#define Dad dl.dad 1.79 +#define Len dl.len 1.80 + 1.81 +typedef struct static_tree_desc_s static_tree_desc; 1.82 + 1.83 +typedef struct tree_desc_s { 1.84 + ct_data *dyn_tree; /* the dynamic tree */ 1.85 + int max_code; /* largest code with non zero frequency */ 1.86 + static_tree_desc *stat_desc; /* the corresponding static tree */ 1.87 +} FAR tree_desc; 1.88 + 1.89 +typedef ush Pos; 1.90 +typedef Pos FAR Posf; 1.91 +typedef unsigned IPos; 1.92 + 1.93 +/* A Pos is an index in the character window. We use short instead of int to 1.94 + * save space in the various tables. IPos is used only for parameter passing. 1.95 + */ 1.96 + 1.97 +typedef struct internal_state { 1.98 + z_streamp strm; /* pointer back to this zlib stream */ 1.99 + int status; /* as the name implies */ 1.100 + Bytef *pending_buf; /* output still pending */ 1.101 + ulg pending_buf_size; /* size of pending_buf */ 1.102 + Bytef *pending_out; /* next pending byte to output to the stream */ 1.103 + uInt pending; /* nb of bytes in the pending buffer */ 1.104 + int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 1.105 + gz_headerp gzhead; /* gzip header information to write */ 1.106 + uInt gzindex; /* where in extra, name, or comment */ 1.107 + Byte method; /* STORED (for zip only) or DEFLATED */ 1.108 + int last_flush; /* value of flush param for previous deflate call */ 1.109 + 1.110 + /* used by deflate.c: */ 1.111 + 1.112 + uInt w_size; /* LZ77 window size (32K by default) */ 1.113 + uInt w_bits; /* log2(w_size) (8..16) */ 1.114 + uInt w_mask; /* w_size - 1 */ 1.115 + 1.116 + Bytef *window; 1.117 + /* Sliding window. Input bytes are read into the second half of the window, 1.118 + * and move to the first half later to keep a dictionary of at least wSize 1.119 + * bytes. With this organization, matches are limited to a distance of 1.120 + * wSize-MAX_MATCH bytes, but this ensures that IO is always 1.121 + * performed with a length multiple of the block size. Also, it limits 1.122 + * the window size to 64K, which is quite useful on MSDOS. 1.123 + * To do: use the user input buffer as sliding window. 1.124 + */ 1.125 + 1.126 + ulg window_size; 1.127 + /* Actual size of window: 2*wSize, except when the user input buffer 1.128 + * is directly used as sliding window. 1.129 + */ 1.130 + 1.131 + Posf *prev; 1.132 + /* Link to older string with same hash index. To limit the size of this 1.133 + * array to 64K, this link is maintained only for the last 32K strings. 1.134 + * An index in this array is thus a window index modulo 32K. 1.135 + */ 1.136 + 1.137 + Posf *head; /* Heads of the hash chains or NIL. */ 1.138 + 1.139 + uInt ins_h; /* hash index of string to be inserted */ 1.140 + uInt hash_size; /* number of elements in hash table */ 1.141 + uInt hash_bits; /* log2(hash_size) */ 1.142 + uInt hash_mask; /* hash_size-1 */ 1.143 + 1.144 + uInt hash_shift; 1.145 + /* Number of bits by which ins_h must be shifted at each input 1.146 + * step. It must be such that after MIN_MATCH steps, the oldest 1.147 + * byte no longer takes part in the hash key, that is: 1.148 + * hash_shift * MIN_MATCH >= hash_bits 1.149 + */ 1.150 + 1.151 + long block_start; 1.152 + /* Window position at the beginning of the current output block. Gets 1.153 + * negative when the window is moved backwards. 1.154 + */ 1.155 + 1.156 + uInt match_length; /* length of best match */ 1.157 + IPos prev_match; /* previous match */ 1.158 + int match_available; /* set if previous match exists */ 1.159 + uInt strstart; /* start of string to insert */ 1.160 + uInt match_start; /* start of matching string */ 1.161 + uInt lookahead; /* number of valid bytes ahead in window */ 1.162 + 1.163 + uInt prev_length; 1.164 + /* Length of the best match at previous step. Matches not greater than this 1.165 + * are discarded. This is used in the lazy match evaluation. 1.166 + */ 1.167 + 1.168 + uInt max_chain_length; 1.169 + /* To speed up deflation, hash chains are never searched beyond this 1.170 + * length. A higher limit improves compression ratio but degrades the 1.171 + * speed. 1.172 + */ 1.173 + 1.174 + uInt max_lazy_match; 1.175 + /* Attempt to find a better match only when the current match is strictly 1.176 + * smaller than this value. This mechanism is used only for compression 1.177 + * levels >= 4. 1.178 + */ 1.179 +# define max_insert_length max_lazy_match 1.180 + /* Insert new strings in the hash table only if the match length is not 1.181 + * greater than this length. This saves time but degrades compression. 1.182 + * max_insert_length is used only for compression levels <= 3. 1.183 + */ 1.184 + 1.185 + int level; /* compression level (1..9) */ 1.186 + int strategy; /* favor or force Huffman coding*/ 1.187 + 1.188 + uInt good_match; 1.189 + /* Use a faster search when the previous match is longer than this */ 1.190 + 1.191 + int nice_match; /* Stop searching when current match exceeds this */ 1.192 + 1.193 + /* used by trees.c: */ 1.194 + /* Didn't use ct_data typedef below to supress compiler warning */ 1.195 + struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 1.196 + struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 1.197 + struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 1.198 + 1.199 + struct tree_desc_s l_desc; /* desc. for literal tree */ 1.200 + struct tree_desc_s d_desc; /* desc. for distance tree */ 1.201 + struct tree_desc_s bl_desc; /* desc. for bit length tree */ 1.202 + 1.203 + ush bl_count[MAX_BITS+1]; 1.204 + /* number of codes at each bit length for an optimal tree */ 1.205 + 1.206 + int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 1.207 + int heap_len; /* number of elements in the heap */ 1.208 + int heap_max; /* element of largest frequency */ 1.209 + /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 1.210 + * The same heap array is used to build all trees. 1.211 + */ 1.212 + 1.213 + uch depth[2*L_CODES+1]; 1.214 + /* Depth of each subtree used as tie breaker for trees of equal frequency 1.215 + */ 1.216 + 1.217 + uchf *l_buf; /* buffer for literals or lengths */ 1.218 + 1.219 + uInt lit_bufsize; 1.220 + /* Size of match buffer for literals/lengths. There are 4 reasons for 1.221 + * limiting lit_bufsize to 64K: 1.222 + * - frequencies can be kept in 16 bit counters 1.223 + * - if compression is not successful for the first block, all input 1.224 + * data is still in the window so we can still emit a stored block even 1.225 + * when input comes from standard input. (This can also be done for 1.226 + * all blocks if lit_bufsize is not greater than 32K.) 1.227 + * - if compression is not successful for a file smaller than 64K, we can 1.228 + * even emit a stored file instead of a stored block (saving 5 bytes). 1.229 + * This is applicable only for zip (not gzip or zlib). 1.230 + * - creating new Huffman trees less frequently may not provide fast 1.231 + * adaptation to changes in the input data statistics. (Take for 1.232 + * example a binary file with poorly compressible code followed by 1.233 + * a highly compressible string table.) Smaller buffer sizes give 1.234 + * fast adaptation but have of course the overhead of transmitting 1.235 + * trees more frequently. 1.236 + * - I can't count above 4 1.237 + */ 1.238 + 1.239 + uInt last_lit; /* running index in l_buf */ 1.240 + 1.241 + ushf *d_buf; 1.242 + /* Buffer for distances. To simplify the code, d_buf and l_buf have 1.243 + * the same number of elements. To use different lengths, an extra flag 1.244 + * array would be necessary. 1.245 + */ 1.246 + 1.247 + ulg opt_len; /* bit length of current block with optimal trees */ 1.248 + ulg static_len; /* bit length of current block with static trees */ 1.249 + uInt matches; /* number of string matches in current block */ 1.250 + int last_eob_len; /* bit length of EOB code for last block */ 1.251 + 1.252 +#ifdef DEBUG 1.253 + ulg compressed_len; /* total bit length of compressed file mod 2^32 */ 1.254 + ulg bits_sent; /* bit length of compressed data sent mod 2^32 */ 1.255 +#endif 1.256 + 1.257 + ush bi_buf; 1.258 + /* Output buffer. bits are inserted starting at the bottom (least 1.259 + * significant bits). 1.260 + */ 1.261 + int bi_valid; 1.262 + /* Number of valid bits in bi_buf. All bits above the last valid bit 1.263 + * are always zero. 1.264 + */ 1.265 + 1.266 + ulg high_water; 1.267 + /* High water mark offset in window for initialized bytes -- bytes above 1.268 + * this are set to zero in order to avoid memory check warnings when 1.269 + * longest match routines access bytes past the input. This is then 1.270 + * updated to the new high water mark. 1.271 + */ 1.272 + 1.273 +} FAR deflate_state; 1.274 + 1.275 +/* Output a byte on the stream. 1.276 + * IN assertion: there is enough room in pending_buf. 1.277 + */ 1.278 +#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 1.279 + 1.280 + 1.281 +#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 1.282 +/* Minimum amount of lookahead, except at the end of the input file. 1.283 + * See deflate.c for comments about the MIN_MATCH+1. 1.284 + */ 1.285 + 1.286 +#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 1.287 +/* In order to simplify the code, particularly on 16 bit machines, match 1.288 + * distances are limited to MAX_DIST instead of WSIZE. 1.289 + */ 1.290 + 1.291 +#define WIN_INIT MAX_MATCH 1.292 +/* Number of bytes after end of data in window to initialize in order to avoid 1.293 + memory checker errors from longest match routines */ 1.294 + 1.295 + /* in trees.c */ 1.296 +void ZLIB_INTERNAL _tr_init OF((deflate_state *s)); 1.297 +int ZLIB_INTERNAL _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 1.298 +void ZLIB_INTERNAL _tr_flush_block OF((deflate_state *s, charf *buf, 1.299 + ulg stored_len, int last)); 1.300 +void ZLIB_INTERNAL _tr_align OF((deflate_state *s)); 1.301 +void ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf, 1.302 + ulg stored_len, int last)); 1.303 + 1.304 +#define d_code(dist) \ 1.305 + ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 1.306 +/* Mapping from a distance to a distance code. dist is the distance - 1 and 1.307 + * must not have side effects. _dist_code[256] and _dist_code[257] are never 1.308 + * used. 1.309 + */ 1.310 + 1.311 +#ifndef DEBUG 1.312 +/* Inline versions of _tr_tally for speed: */ 1.313 + 1.314 +#if defined(GEN_TREES_H) || !defined(STDC) 1.315 + extern uch ZLIB_INTERNAL _length_code[]; 1.316 + extern uch ZLIB_INTERNAL _dist_code[]; 1.317 +#else 1.318 + extern const uch ZLIB_INTERNAL _length_code[]; 1.319 + extern const uch ZLIB_INTERNAL _dist_code[]; 1.320 +#endif 1.321 + 1.322 +# define _tr_tally_lit(s, c, flush) \ 1.323 + { uch cc = (c); \ 1.324 + s->d_buf[s->last_lit] = 0; \ 1.325 + s->l_buf[s->last_lit++] = cc; \ 1.326 + s->dyn_ltree[cc].Freq++; \ 1.327 + flush = (s->last_lit == s->lit_bufsize-1); \ 1.328 + } 1.329 +# define _tr_tally_dist(s, distance, length, flush) \ 1.330 + { uch len = (length); \ 1.331 + ush dist = (distance); \ 1.332 + s->d_buf[s->last_lit] = dist; \ 1.333 + s->l_buf[s->last_lit++] = len; \ 1.334 + dist--; \ 1.335 + s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 1.336 + s->dyn_dtree[d_code(dist)].Freq++; \ 1.337 + flush = (s->last_lit == s->lit_bufsize-1); \ 1.338 + } 1.339 +#else 1.340 +# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 1.341 +# define _tr_tally_dist(s, distance, length, flush) \ 1.342 + flush = _tr_tally(s, distance, length) 1.343 +#endif 1.344 + 1.345 +#endif /* DEFLATE_H */