15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* deflate.h -- internal compression state 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright (C) 1995-2010 Jean-loup Gailly 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * For conditions of distribution and use, see copyright notice in zlib.h 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* WARNING: this file should *not* be used by applications. It is 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) part of the implementation of the compression library and is 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) subject to change. Applications should only use zlib.h. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* @(#) $Id$ */ 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEFLATE_H 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEFLATE_H 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "zutil.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* define NO_GZIP when compiling if you want to disable gzip header and 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) trailer creation by deflate(). NO_GZIP would be used to avoid linking in 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the crc code when it is not needed. For shared libraries, gzip encoding 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) should be left enabled. */ 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef NO_GZIP 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define GZIP 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Internal compression state. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LENGTH_CODES 29 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* number of length codes, not counting the special END_BLOCK code */ 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LITERALS 256 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* number of literal bytes 0..255 */ 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define L_CODES (LITERALS+1+LENGTH_CODES) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* number of Literal or Length codes, including the END_BLOCK code */ 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define D_CODES 30 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* number of distance codes */ 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BL_CODES 19 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* number of codes used to transfer the bit lengths */ 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HEAP_SIZE (2*L_CODES+1) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* maximum heap size */ 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MAX_BITS 15 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* All codes must not exceed MAX_BITS bits */ 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define INIT_STATE 42 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define EXTRA_STATE 69 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define NAME_STATE 73 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define COMMENT_STATE 91 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HCRC_STATE 103 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BUSY_STATE 113 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define FINISH_STATE 666 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Stream status */ 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Data structure describing a single value and its code string. */ 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct ct_data_s { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) union { 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush freq; /* frequency count */ 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush code; /* bit string */ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } fc; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) union { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush dad; /* father node in Huffman tree */ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush len; /* length of bit string */ 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } dl; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} FAR ct_data; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Freq fc.freq 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Code fc.code 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Dad dl.dad 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Len dl.len 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct static_tree_desc_s static_tree_desc; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct tree_desc_s { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *dyn_tree; /* the dynamic tree */ 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code; /* largest code with non zero frequency */ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_tree_desc *stat_desc; /* the corresponding static tree */ 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} FAR tree_desc; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef ush Pos; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef Pos FAR Posf; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef unsigned IPos; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* A Pos is an index in the character window. We use short instead of int to 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * save space in the various tables. IPos is used only for parameter passing. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Z_COOKIE_HASH_SIZE 256 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Z_COOKIE_HASH_MASK (Z_COOKIE_HASH_SIZE-1) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct internal_state { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) z_streamp strm; /* pointer back to this zlib stream */ 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int status; /* as the name implies */ 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bytef *pending_buf; /* output still pending */ 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg pending_buf_size; /* size of pending_buf */ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bytef *pending_out; /* next pending byte to output to the stream */ 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt pending; /* nb of bytes in the pending buffer */ 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gz_headerp gzhead; /* gzip header information to write */ 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt gzindex; /* where in extra, name, or comment */ 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Byte method; /* STORED (for zip only) or DEFLATED */ 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last_flush; /* value of flush param for previous deflate call */ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* used by deflate.c: */ 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt w_size; /* LZ77 window size (32K by default) */ 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt w_bits; /* log2(w_size) (8..16) */ 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt w_mask; /* w_size - 1 */ 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bytef *window; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Sliding window. Input bytes are read into the second half of the window, 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * and move to the first half later to keep a dictionary of at least wSize 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * bytes. With this organization, matches are limited to a distance of 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * wSize-MAX_MATCH bytes, but this ensures that IO is always 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * performed with a length multiple of the block size. Also, it limits 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the window size to 64K, which is quite useful on MSDOS. 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * To do: use the user input buffer as sliding window. 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg window_size; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Actual size of window: 2*wSize, except when the user input buffer 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * is directly used as sliding window. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Posf *prev; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Link to older string with same hash index. To limit the size of this 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * array to 64K, this link is maintained only for the last 32K strings. 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * An index in this array is thus a window index modulo 32K. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Posf *head; /* Heads of the hash chains or NIL. */ 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt ins_h; /* hash index of string to be inserted */ 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt hash_size; /* number of elements in hash table */ 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt hash_bits; /* log2(hash_size) */ 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt hash_mask; /* hash_size-1 */ 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt hash_shift; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bytef *class_bitmap; /* bitmap of class for each byte in window */ 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IPos cookie_locations[Z_COOKIE_HASH_SIZE]; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Number of bits by which ins_h must be shifted at each input 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * step. It must be such that after MIN_MATCH steps, the oldest 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * byte no longer takes part in the hash key, that is: 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * hash_shift * MIN_MATCH >= hash_bits 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) long block_start; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Window position at the beginning of the current output block. Gets 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * negative when the window is moved backwards. 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt match_length; /* length of best match */ 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IPos prev_match; /* previous match */ 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int match_available; /* set if previous match exists */ 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt strstart; /* start of string to insert */ 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt match_start; /* start of matching string */ 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt lookahead; /* number of valid bytes ahead in window */ 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt prev_length; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Length of the best match at previous step. Matches not greater than this 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * are discarded. This is used in the lazy match evaluation. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt max_chain_length; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* To speed up deflation, hash chains are never searched beyond this 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * length. A higher limit improves compression ratio but degrades the 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * speed. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt max_lazy_match; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Attempt to find a better match only when the current match is strictly 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * smaller than this value. This mechanism is used only for compression 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * levels >= 4. 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define max_insert_length max_lazy_match 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Insert new strings in the hash table only if the match length is not 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * greater than this length. This saves time but degrades compression. 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * max_insert_length is used only for compression levels <= 3. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int level; /* compression level (1..9) */ 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int strategy; /* favor or force Huffman coding*/ 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt good_match; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Use a faster search when the previous match is longer than this */ 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nice_match; /* Stop searching when current match exceeds this */ 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* used by trees.c: */ 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Didn't use ct_data typedef below to supress compiler warning */ 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct tree_desc_s l_desc; /* desc. for literal tree */ 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct tree_desc_s d_desc; /* desc. for distance tree */ 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct tree_desc_s bl_desc; /* desc. for bit length tree */ 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush bl_count[MAX_BITS+1]; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* number of codes at each bit length for an optimal tree */ 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int heap_len; /* number of elements in the heap */ 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int heap_max; /* element of largest frequency */ 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The same heap array is used to build all trees. 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uch depth[2*L_CODES+1]; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Depth of each subtree used as tie breaker for trees of equal frequency 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uchf *l_buf; /* buffer for literals or lengths */ 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt lit_bufsize; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Size of match buffer for literals/lengths. There are 4 reasons for 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * limiting lit_bufsize to 64K: 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - frequencies can be kept in 16 bit counters 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - if compression is not successful for the first block, all input 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * data is still in the window so we can still emit a stored block even 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * when input comes from standard input. (This can also be done for 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * all blocks if lit_bufsize is not greater than 32K.) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - if compression is not successful for a file smaller than 64K, we can 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * even emit a stored file instead of a stored block (saving 5 bytes). 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This is applicable only for zip (not gzip or zlib). 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - creating new Huffman trees less frequently may not provide fast 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * adaptation to changes in the input data statistics. (Take for 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * example a binary file with poorly compressible code followed by 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * a highly compressible string table.) Smaller buffer sizes give 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * fast adaptation but have of course the overhead of transmitting 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * trees more frequently. 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - I can't count above 4 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt last_lit; /* running index in l_buf */ 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ushf *d_buf; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Buffer for distances. To simplify the code, d_buf and l_buf have 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the same number of elements. To use different lengths, an extra flag 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * array would be necessary. 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg opt_len; /* bit length of current block with optimal trees */ 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg static_len; /* bit length of current block with static trees */ 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uInt matches; /* number of string matches in current block */ 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last_eob_len; /* bit length of EOB code for last block */ 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg compressed_len; /* total bit length of compressed file mod 2^32 */ 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg bits_sent; /* bit length of compressed data sent mod 2^32 */ 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush bi_buf; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Output buffer. bits are inserted starting at the bottom (least 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * significant bits). 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int bi_valid; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Number of valid bits in bi_buf. All bits above the last valid bit 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * are always zero. 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg high_water; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* High water mark offset in window for initialized bytes -- bytes above 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * this are set to zero in order to avoid memory check warnings when 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * longest match routines access bytes past the input. This is then 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * updated to the new high water mark. 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} FAR deflate_state; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Output a byte on the stream. 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: there is enough room in pending_buf. 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Minimum amount of lookahead, except at the end of the input file. 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * See deflate.c for comments about the MIN_MATCH+1. 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* In order to simplify the code, particularly on 16 bit machines, match 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * distances are limited to MAX_DIST instead of WSIZE. 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define WIN_INIT MAX_MATCH 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Number of bytes after end of data in window to initialize in order to avoid 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memory checker errors from longest match routines */ 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* in trees.c */ 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_init OF((deflate_state *s)); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ZLIB_INTERNAL _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_flush_block OF((deflate_state *s, charf *buf, 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg stored_len, int last)); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_align OF((deflate_state *s)); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf, 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg stored_len, int last)); 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define d_code(dist) \ 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Mapping from a distance to a distance code. dist is the distance - 1 and 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * must not have side effects. _dist_code[256] and _dist_code[257] are never 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * used. 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUG 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Inline versions of _tr_tally for speed: */ 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(GEN_TREES_H) || !defined(STDC) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extern uch ZLIB_INTERNAL _length_code[]; 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extern uch ZLIB_INTERNAL _dist_code[]; 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extern const uch ZLIB_INTERNAL _length_code[]; 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extern const uch ZLIB_INTERNAL _dist_code[]; 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define _tr_tally_lit(s, c, flush) \ 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { uch cc = (c); \ 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->d_buf[s->last_lit] = 0; \ 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->l_buf[s->last_lit++] = cc; \ 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_ltree[cc].Freq++; \ 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) flush = (s->last_lit == s->lit_bufsize-1); \ 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define _tr_tally_dist(s, distance, length, flush) \ 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { uch len = (length); \ 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush dist = (distance); \ 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->d_buf[s->last_lit] = dist; \ 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->l_buf[s->last_lit++] = len; \ 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist--; \ 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_dtree[d_code(dist)].Freq++; \ 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) flush = (s->last_lit == s->lit_bufsize-1); \ 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define _tr_tally_dist(s, distance, length, flush) \ 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) flush = _tr_tally(s, distance, length) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* DEFLATE_H */ 348