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