deflate.h revision 381716e9396b55b1adb8235b020c37344f60ab07
19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* deflate.h -- internal compression state 2381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Copyright (C) 1995-2010 Jean-loup Gailly 39e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 49e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 59e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 69e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* WARNING: this file should *not* be used by applications. It is 79e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project part of the implementation of the compression library and is 89e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subject to change. Applications should only use zlib.h. 99e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* @(#) $Id$ */ 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef DEFLATE_H 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define DEFLATE_H 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "zutil.h" 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* define NO_GZIP when compiling if you want to disable gzip header and 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project trailer creation by deflate(). NO_GZIP would be used to avoid linking in 209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the crc code when it is not needed. For shared libraries, gzip encoding 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project should be left enabled. */ 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef NO_GZIP 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define GZIP 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Internal compression state. 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define LENGTH_CODES 29 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* number of length codes, not counting the special END_BLOCK code */ 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define LITERALS 256 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* number of literal bytes 0..255 */ 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define L_CODES (LITERALS+1+LENGTH_CODES) 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* number of Literal or Length codes, including the END_BLOCK code */ 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define D_CODES 30 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* number of distance codes */ 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define BL_CODES 19 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* number of codes used to transfer the bit lengths */ 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define HEAP_SIZE (2*L_CODES+1) 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* maximum heap size */ 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAX_BITS 15 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* All codes must not exceed MAX_BITS bits */ 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define INIT_STATE 42 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define EXTRA_STATE 69 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define NAME_STATE 73 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define COMMENT_STATE 91 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define HCRC_STATE 103 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define BUSY_STATE 113 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define FINISH_STATE 666 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Stream status */ 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Data structure describing a single value and its code string. */ 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef struct ct_data_s { 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project union { 649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush freq; /* frequency count */ 659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush code; /* bit string */ 669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } fc; 679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project union { 689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush dad; /* father node in Huffman tree */ 699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush len; /* length of bit string */ 709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } dl; 719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} FAR ct_data; 729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define Freq fc.freq 749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define Code fc.code 759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define Dad dl.dad 769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define Len dl.len 779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef struct static_tree_desc_s static_tree_desc; 799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef struct tree_desc_s { 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *dyn_tree; /* the dynamic tree */ 829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code; /* largest code with non zero frequency */ 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_tree_desc *stat_desc; /* the corresponding static tree */ 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} FAR tree_desc; 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef ush Pos; 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef Pos FAR Posf; 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef unsigned IPos; 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* A Pos is an index in the character window. We use short instead of int to 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * save space in the various tables. IPos is used only for parameter passing. 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projecttypedef struct internal_state { 959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project z_streamp strm; /* pointer back to this zlib stream */ 969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int status; /* as the name implies */ 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Bytef *pending_buf; /* output still pending */ 989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg pending_buf_size; /* size of pending_buf */ 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Bytef *pending_out; /* next pending byte to output to the stream */ 1009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt pending; /* nb of bytes in the pending buffer */ 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int wrap; /* bit 0 true for zlib, bit 1 true for gzip */ 1029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project gz_headerp gzhead; /* gzip header information to write */ 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt gzindex; /* where in extra, name, or comment */ 1049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Byte method; /* STORED (for zip only) or DEFLATED */ 1059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int last_flush; /* value of flush param for previous deflate call */ 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* used by deflate.c: */ 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt w_size; /* LZ77 window size (32K by default) */ 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt w_bits; /* log2(w_size) (8..16) */ 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt w_mask; /* w_size - 1 */ 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Bytef *window; 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Sliding window. Input bytes are read into the second half of the window, 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and move to the first half later to keep a dictionary of at least wSize 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bytes. With this organization, matches are limited to a distance of 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * wSize-MAX_MATCH bytes, but this ensures that IO is always 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * performed with a length multiple of the block size. Also, it limits 1199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the window size to 64K, which is quite useful on MSDOS. 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * To do: use the user input buffer as sliding window. 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg window_size; 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Actual size of window: 2*wSize, except when the user input buffer 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * is directly used as sliding window. 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Posf *prev; 1299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Link to older string with same hash index. To limit the size of this 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * array to 64K, this link is maintained only for the last 32K strings. 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * An index in this array is thus a window index modulo 32K. 1329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Posf *head; /* Heads of the hash chains or NIL. */ 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt ins_h; /* hash index of string to be inserted */ 1379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt hash_size; /* number of elements in hash table */ 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt hash_bits; /* log2(hash_size) */ 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt hash_mask; /* hash_size-1 */ 1409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt hash_shift; 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Number of bits by which ins_h must be shifted at each input 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * step. It must be such that after MIN_MATCH steps, the oldest 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * byte no longer takes part in the hash key, that is: 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * hash_shift * MIN_MATCH >= hash_bits 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project long block_start; 1499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Window position at the beginning of the current output block. Gets 1509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * negative when the window is moved backwards. 1519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt match_length; /* length of best match */ 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project IPos prev_match; /* previous match */ 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int match_available; /* set if previous match exists */ 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt strstart; /* start of string to insert */ 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt match_start; /* start of matching string */ 1589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt lookahead; /* number of valid bytes ahead in window */ 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt prev_length; 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Length of the best match at previous step. Matches not greater than this 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are discarded. This is used in the lazy match evaluation. 1639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt max_chain_length; 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* To speed up deflation, hash chains are never searched beyond this 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * length. A higher limit improves compression ratio but degrades the 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * speed. 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt max_lazy_match; 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Attempt to find a better match only when the current match is strictly 1739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * smaller than this value. This mechanism is used only for compression 1749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * levels >= 4. 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define max_insert_length max_lazy_match 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Insert new strings in the hash table only if the match length is not 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * greater than this length. This saves time but degrades compression. 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * max_insert_length is used only for compression levels <= 3. 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int level; /* compression level (1..9) */ 1839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int strategy; /* favor or force Huffman coding*/ 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt good_match; 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Use a faster search when the previous match is longer than this */ 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int nice_match; /* Stop searching when current match exceeds this */ 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* used by trees.c: */ 1919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Didn't use ct_data typedef below to supress compiler warning */ 1929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 1939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 1949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 1959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct tree_desc_s l_desc; /* desc. for literal tree */ 1979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct tree_desc_s d_desc; /* desc. for distance tree */ 1989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct tree_desc_s bl_desc; /* desc. for bit length tree */ 1999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush bl_count[MAX_BITS+1]; 2019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* number of codes at each bit length for an optimal tree */ 2029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 2049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int heap_len; /* number of elements in the heap */ 2059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int heap_max; /* element of largest frequency */ 2069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 2079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * The same heap array is used to build all trees. 2089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uch depth[2*L_CODES+1]; 2119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Depth of each subtree used as tie breaker for trees of equal frequency 2129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uchf *l_buf; /* buffer for literals or lengths */ 2159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt lit_bufsize; 2179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Size of match buffer for literals/lengths. There are 4 reasons for 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * limiting lit_bufsize to 64K: 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - frequencies can be kept in 16 bit counters 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - if compression is not successful for the first block, all input 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * data is still in the window so we can still emit a stored block even 2229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * when input comes from standard input. (This can also be done for 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * all blocks if lit_bufsize is not greater than 32K.) 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - if compression is not successful for a file smaller than 64K, we can 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * even emit a stored file instead of a stored block (saving 5 bytes). 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * This is applicable only for zip (not gzip or zlib). 2279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - creating new Huffman trees less frequently may not provide fast 2289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * adaptation to changes in the input data statistics. (Take for 2299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * example a binary file with poorly compressible code followed by 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a highly compressible string table.) Smaller buffer sizes give 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * fast adaptation but have of course the overhead of transmitting 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * trees more frequently. 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - I can't count above 4 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt last_lit; /* running index in l_buf */ 2379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ushf *d_buf; 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Buffer for distances. To simplify the code, d_buf and l_buf have 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the same number of elements. To use different lengths, an extra flag 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * array would be necessary. 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg opt_len; /* bit length of current block with optimal trees */ 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg static_len; /* bit length of current block with static trees */ 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uInt matches; /* number of string matches in current block */ 2479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int last_eob_len; /* bit length of EOB code for last block */ 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg compressed_len; /* total bit length of compressed file mod 2^32 */ 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg bits_sent; /* bit length of compressed data sent mod 2^32 */ 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush bi_buf; 2559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Output buffer. bits are inserted starting at the bottom (least 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * significant bits). 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bi_valid; 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Number of valid bits in bi_buf. All bits above the last valid bit 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are always zero. 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 263381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes ulg high_water; 264381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* High water mark offset in window for initialized bytes -- bytes above 265381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * this are set to zero in order to avoid memory check warnings when 266381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * longest match routines access bytes past the input. This is then 267381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * updated to the new high water mark. 268381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes */ 269381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} FAR deflate_state; 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Output a byte on the stream. 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: there is enough room in pending_buf. 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Minimum amount of lookahead, except at the end of the input file. 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * See deflate.c for comments about the MIN_MATCH+1. 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 2849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* In order to simplify the code, particularly on 16 bit machines, match 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * distances are limited to MAX_DIST instead of WSIZE. 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 288381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#define WIN_INIT MAX_MATCH 289381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes/* Number of bytes after end of data in window to initialize in order to avoid 290381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes memory checker errors from longest match routines */ 291381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* in trees.c */ 293381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_init OF((deflate_state *s)); 294381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesint ZLIB_INTERNAL _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 295381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_flush_block OF((deflate_state *s, charf *buf, 296381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes ulg stored_len, int last)); 297381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_align OF((deflate_state *s)); 298381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf, 299381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes ulg stored_len, int last)); 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define d_code(dist) \ 3029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Mapping from a distance to a distance code. dist is the distance - 1 and 3049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * must not have side effects. _dist_code[256] and _dist_code[257] are never 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * used. 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef DEBUG 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Inline versions of _tr_tally for speed: */ 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#if defined(GEN_TREES_H) || !defined(STDC) 312381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes extern uch ZLIB_INTERNAL _length_code[]; 313381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes extern uch ZLIB_INTERNAL _dist_code[]; 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 315381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes extern const uch ZLIB_INTERNAL _length_code[]; 316381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes extern const uch ZLIB_INTERNAL _dist_code[]; 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define _tr_tally_lit(s, c, flush) \ 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project { uch cc = (c); \ 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->d_buf[s->last_lit] = 0; \ 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->l_buf[s->last_lit++] = cc; \ 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_ltree[cc].Freq++; \ 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project flush = (s->last_lit == s->lit_bufsize-1); \ 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define _tr_tally_dist(s, distance, length, flush) \ 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project { uch len = (length); \ 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush dist = (distance); \ 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->d_buf[s->last_lit] = dist; \ 3309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->l_buf[s->last_lit++] = len; \ 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist--; \ 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_dtree[d_code(dist)].Freq++; \ 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project flush = (s->last_lit == s->lit_bufsize-1); \ 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define _tr_tally_dist(s, distance, length, flush) \ 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project flush = _tr_tally(s, distance, length) 3409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 3419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* DEFLATE_H */ 343