14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* deflate.h -- internal compression state 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Copyright (C) 1995-2004 Jean-loup Gailly 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * For conditions of distribution and use, see copyright notice in zlib.h 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* WARNING: this file should *not* be used by applications. It is 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm part of the implementation of the compression library and is 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm subject to change. Applications should only use zlib.h. 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* @(#) $Id$ */ 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifndef DEFLATE_H 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define DEFLATE_H 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "zutil.h" 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* define NO_GZIP when compiling if you want to disable gzip header and 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm trailer creation by deflate(). NO_GZIP would be used to avoid linking in 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm the crc code when it is not needed. For shared libraries, gzip encoding 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm should be left enabled. */ 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifndef NO_GZIP 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define GZIP 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* =========================================================================== 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * Internal compression state. 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define LENGTH_CODES 29 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* number of length codes, not counting the special END_BLOCK code */ 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define LITERALS 256 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* number of literal bytes 0..255 */ 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define L_CODES (LITERALS+1+LENGTH_CODES) 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* number of Literal or Length codes, including the END_BLOCK code */ 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define D_CODES 30 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* number of distance codes */ 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define BL_CODES 19 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* number of codes used to transfer the bit lengths */ 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define HEAP_SIZE (2*L_CODES+1) 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* maximum heap size */ 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define MAX_BITS 15 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* All codes must not exceed MAX_BITS bits */ 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define INIT_STATE 42 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define EXTRA_STATE 69 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define NAME_STATE 73 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define COMMENT_STATE 91 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define HCRC_STATE 103 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define BUSY_STATE 113 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define FINISH_STATE 666 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Stream status */ 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Data structure describing a single value and its code string. */ 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct ct_data_s { 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm union { 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush freq; /* frequency count */ 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush code; /* bit string */ 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } fc; 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm union { 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush dad; /* father node in Huffman tree */ 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush len; /* length of bit string */ 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } dl; 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} FAR ct_data; 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define Freq fc.freq 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define Code fc.code 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define Dad dl.dad 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define Len dl.len 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct static_tree_desc_s static_tree_desc; 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct tree_desc_s { 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ct_data *dyn_tree; /* the dynamic tree */ 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int max_code; /* largest code with non zero frequency */ 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm static_tree_desc *stat_desc; /* the corresponding static tree */ 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} FAR tree_desc; 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef ush Pos; 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef Pos FAR Posf; 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef unsigned IPos; 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* A Pos is an index in the character window. We use short instead of int to 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * save space in the various tables. IPos is used only for parameter passing. 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtypedef struct internal_state { 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm z_streamp strm; /* pointer back to this zlib stream */ 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int status; /* as the name implies */ 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Bytef *pending_buf; /* output still pending */ 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg pending_buf_size; /* size of pending_buf */ 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Bytef *pending_out; /* next pending byte to output to the stream */ 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt pending; /* nb of bytes in the pending buffer */ 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm gz_headerp gzhead; /* gzip header information to write */ 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt gzindex; /* where in extra, name, or comment */ 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Byte method; /* STORED (for zip only) or DEFLATED */ 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int last_flush; /* value of flush param for previous deflate call */ 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* used by deflate.c: */ 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt w_size; /* LZ77 window size (32K by default) */ 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt w_bits; /* log2(w_size) (8..16) */ 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt w_mask; /* w_size - 1 */ 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Bytef *window; 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Sliding window. Input bytes are read into the second half of the window, 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * and move to the first half later to keep a dictionary of at least wSize 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * bytes. With this organization, matches are limited to a distance of 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * wSize-MAX_MATCH bytes, but this ensures that IO is always 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * performed with a length multiple of the block size. Also, it limits 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * the window size to 64K, which is quite useful on MSDOS. 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * To do: use the user input buffer as sliding window. 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg window_size; 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Actual size of window: 2*wSize, except when the user input buffer 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * is directly used as sliding window. 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Posf *prev; 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Link to older string with same hash index. To limit the size of this 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * array to 64K, this link is maintained only for the last 32K strings. 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * An index in this array is thus a window index modulo 32K. 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Posf *head; /* Heads of the hash chains or NIL. */ 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt ins_h; /* hash index of string to be inserted */ 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt hash_size; /* number of elements in hash table */ 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt hash_bits; /* log2(hash_size) */ 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt hash_mask; /* hash_size-1 */ 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt hash_shift; 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Number of bits by which ins_h must be shifted at each input 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * step. It must be such that after MIN_MATCH steps, the oldest 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * byte no longer takes part in the hash key, that is: 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * hash_shift * MIN_MATCH >= hash_bits 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm long block_start; 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Window position at the beginning of the current output block. Gets 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * negative when the window is moved backwards. 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt match_length; /* length of best match */ 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm IPos prev_match; /* previous match */ 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int match_available; /* set if previous match exists */ 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt strstart; /* start of string to insert */ 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt match_start; /* start of matching string */ 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt lookahead; /* number of valid bytes ahead in window */ 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt prev_length; 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Length of the best match at previous step. Matches not greater than this 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * are discarded. This is used in the lazy match evaluation. 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt max_chain_length; 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* To speed up deflation, hash chains are never searched beyond this 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * length. A higher limit improves compression ratio but degrades the 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * speed. 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt max_lazy_match; 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Attempt to find a better match only when the current match is strictly 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * smaller than this value. This mechanism is used only for compression 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * levels >= 4. 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define max_insert_length max_lazy_match 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Insert new strings in the hash table only if the match length is not 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * greater than this length. This saves time but degrades compression. 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * max_insert_length is used only for compression levels <= 3. 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int level; /* compression level (1..9) */ 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int strategy; /* favor or force Huffman coding*/ 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt good_match; 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Use a faster search when the previous match is longer than this */ 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int nice_match; /* Stop searching when current match exceeds this */ 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* used by trees.c: */ 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Didn't use ct_data typedef below to supress compiler warning */ 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct tree_desc_s l_desc; /* desc. for literal tree */ 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct tree_desc_s d_desc; /* desc. for distance tree */ 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm struct tree_desc_s bl_desc; /* desc. for bit length tree */ 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush bl_count[MAX_BITS+1]; 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* number of codes at each bit length for an optimal tree */ 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int heap_len; /* number of elements in the heap */ 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int heap_max; /* element of largest frequency */ 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * The same heap array is used to build all trees. 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uch depth[2*L_CODES+1]; 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Depth of each subtree used as tie breaker for trees of equal frequency 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uchf *l_buf; /* buffer for literals or lengths */ 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt lit_bufsize; 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Size of match buffer for literals/lengths. There are 4 reasons for 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * limiting lit_bufsize to 64K: 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * - frequencies can be kept in 16 bit counters 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * - if compression is not successful for the first block, all input 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * data is still in the window so we can still emit a stored block even 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * when input comes from standard input. (This can also be done for 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * all blocks if lit_bufsize is not greater than 32K.) 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * - if compression is not successful for a file smaller than 64K, we can 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * even emit a stored file instead of a stored block (saving 5 bytes). 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * This is applicable only for zip (not gzip or zlib). 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * - creating new Huffman trees less frequently may not provide fast 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * adaptation to changes in the input data statistics. (Take for 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * example a binary file with poorly compressible code followed by 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * a highly compressible string table.) Smaller buffer sizes give 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * fast adaptation but have of course the overhead of transmitting 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * trees more frequently. 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * - I can't count above 4 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt last_lit; /* running index in l_buf */ 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ushf *d_buf; 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Buffer for distances. To simplify the code, d_buf and l_buf have 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * the same number of elements. To use different lengths, an extra flag 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * array would be necessary. 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg opt_len; /* bit length of current block with optimal trees */ 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg static_len; /* bit length of current block with static trees */ 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uInt matches; /* number of string matches in current block */ 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int last_eob_len; /* bit length of EOB code for last block */ 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifdef DEBUG 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg compressed_len; /* total bit length of compressed file mod 2^32 */ 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ulg bits_sent; /* bit length of compressed data sent mod 2^32 */ 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush bi_buf; 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Output buffer. bits are inserted starting at the bottom (least 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * significant bits). 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int bi_valid; 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* Number of valid bits in bi_buf. All bits above the last valid bit 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * are always zero. 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} FAR deflate_state; 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Output a byte on the stream. 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * IN assertion: there is enough room in pending_buf. 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Minimum amount of lookahead, except at the end of the input file. 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * See deflate.c for comments about the MIN_MATCH+1. 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* In order to simplify the code, particularly on 16 bit machines, match 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * distances are limited to MAX_DIST instead of WSIZE. 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm /* in trees.c */ 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid _tr_init OF((deflate_state *s)); 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmint _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int eof)); 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid _tr_align OF((deflate_state *s)); 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int eof)); 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#define d_code(dist) \ 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Mapping from a distance to a distance code. dist is the distance - 1 and 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * must not have side effects. _dist_code[256] and _dist_code[257] are never 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm * used. 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm */ 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#ifndef DEBUG 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Inline versions of _tr_tally for speed: */ 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#if defined(GEN_TREES_H) || !defined(STDC) 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm extern uch _length_code[]; 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm extern uch _dist_code[]; 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#else 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm extern const uch _length_code[]; 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm extern const uch _dist_code[]; 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define _tr_tally_lit(s, c, flush) \ 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm { uch cc = (c); \ 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->d_buf[s->last_lit] = 0; \ 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->l_buf[s->last_lit++] = cc; \ 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->dyn_ltree[cc].Freq++; \ 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm flush = (s->last_lit == s->lit_bufsize-1); \ 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define _tr_tally_dist(s, distance, length, flush) \ 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm { uch len = (length); \ 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ush dist = (distance); \ 3184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->d_buf[s->last_lit] = dist; \ 3194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->l_buf[s->last_lit++] = len; \ 3204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dist--; \ 3214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 3224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s->dyn_dtree[d_code(dist)].Freq++; \ 3234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm flush = (s->last_lit == s->lit_bufsize-1); \ 3244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 3254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#else 3264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 3274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# define _tr_tally_dist(s, distance, length, flush) \ 3284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm flush = _tr_tally(s, distance, length) 3294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif 3304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#endif /* DEFLATE_H */ 332