--- /dev/null
+/* deflate.h -- internal compression state\r
+ * Copyright (C) 1995-2012 Jean-loup Gailly\r
+ * For conditions of distribution and use, see copyright notice in zlib.h\r
+ */\r
+\r
+/* WARNING: this file should *not* be used by applications. It is\r
+ part of the implementation of the compression library and is\r
+ subject to change. Applications should only use zlib.h.\r
+ */\r
+\r
+/* @(#) $Id$ */\r
+\r
+#ifndef DEFLATE_H\r
+#define DEFLATE_H\r
+\r
+#include "zutil.h"\r
+\r
+/* define NO_GZIP when compiling if you want to disable gzip header and\r
+ trailer creation by deflate(). NO_GZIP would be used to avoid linking in\r
+ the crc code when it is not needed. For shared libraries, gzip encoding\r
+ should be left enabled. */\r
+#ifndef NO_GZIP\r
+# define GZIP\r
+#endif\r
+\r
+/* ===========================================================================\r
+ * Internal compression state.\r
+ */\r
+\r
+#define LENGTH_CODES 29\r
+/* number of length codes, not counting the special END_BLOCK code */\r
+\r
+#define LITERALS 256\r
+/* number of literal bytes 0..255 */\r
+\r
+#define L_CODES (LITERALS+1+LENGTH_CODES)\r
+/* number of Literal or Length codes, including the END_BLOCK code */\r
+\r
+#define D_CODES 30\r
+/* number of distance codes */\r
+\r
+#define BL_CODES 19\r
+/* number of codes used to transfer the bit lengths */\r
+\r
+#define HEAP_SIZE (2*L_CODES+1)\r
+/* maximum heap size */\r
+\r
+#define MAX_BITS 15\r
+/* All codes must not exceed MAX_BITS bits */\r
+\r
+#define Buf_size 16\r
+/* size of bit buffer in bi_buf */\r
+\r
+#define INIT_STATE 42\r
+#define EXTRA_STATE 69\r
+#define NAME_STATE 73\r
+#define COMMENT_STATE 91\r
+#define HCRC_STATE 103\r
+#define BUSY_STATE 113\r
+#define FINISH_STATE 666\r
+/* Stream status */\r
+\r
+\r
+/* Data structure describing a single value and its code string. */\r
+typedef struct ct_data_s {\r
+ union {\r
+ ush freq; /* frequency count */\r
+ ush code; /* bit string */\r
+ } fc;\r
+ union {\r
+ ush dad; /* father node in Huffman tree */\r
+ ush len; /* length of bit string */\r
+ } dl;\r
+} FAR ct_data;\r
+\r
+#define Freq fc.freq\r
+#define Code fc.code\r
+#define Dad dl.dad\r
+#define Len dl.len\r
+\r
+typedef struct static_tree_desc_s static_tree_desc;\r
+\r
+typedef struct tree_desc_s {\r
+ ct_data *dyn_tree; /* the dynamic tree */\r
+ int max_code; /* largest code with non zero frequency */\r
+ static_tree_desc *stat_desc; /* the corresponding static tree */\r
+} FAR tree_desc;\r
+\r
+typedef ush Pos;\r
+typedef Pos FAR Posf;\r
+typedef unsigned IPos;\r
+\r
+/* A Pos is an index in the character window. We use short instead of int to\r
+ * save space in the various tables. IPos is used only for parameter passing.\r
+ */\r
+\r
+typedef struct internal_state {\r
+ z_streamp strm; /* pointer back to this zlib stream */\r
+ int status; /* as the name implies */\r
+ Bytef *pending_buf; /* output still pending */\r
+ ulg pending_buf_size; /* size of pending_buf */\r
+ Bytef *pending_out; /* next pending byte to output to the stream */\r
+ uInt pending; /* nb of bytes in the pending buffer */\r
+ int wrap; /* bit 0 true for zlib, bit 1 true for gzip */\r
+ gz_headerp gzhead; /* gzip header information to write */\r
+ uInt gzindex; /* where in extra, name, or comment */\r
+ Byte method; /* can only be DEFLATED */\r
+ int last_flush; /* value of flush param for previous deflate call */\r
+\r
+ /* used by deflate.c: */\r
+\r
+ uInt w_size; /* LZ77 window size (32K by default) */\r
+ uInt w_bits; /* log2(w_size) (8..16) */\r
+ uInt w_mask; /* w_size - 1 */\r
+\r
+ Bytef *window;\r
+ /* Sliding window. Input bytes are read into the second half of the window,\r
+ * and move to the first half later to keep a dictionary of at least wSize\r
+ * bytes. With this organization, matches are limited to a distance of\r
+ * wSize-MAX_MATCH bytes, but this ensures that IO is always\r
+ * performed with a length multiple of the block size. Also, it limits\r
+ * the window size to 64K, which is quite useful on MSDOS.\r
+ * To do: use the user input buffer as sliding window.\r
+ */\r
+\r
+ ulg window_size;\r
+ /* Actual size of window: 2*wSize, except when the user input buffer\r
+ * is directly used as sliding window.\r
+ */\r
+\r
+ Posf *prev;\r
+ /* Link to older string with same hash index. To limit the size of this\r
+ * array to 64K, this link is maintained only for the last 32K strings.\r
+ * An index in this array is thus a window index modulo 32K.\r
+ */\r
+\r
+ Posf *head; /* Heads of the hash chains or NIL. */\r
+\r
+ uInt ins_h; /* hash index of string to be inserted */\r
+ uInt hash_size; /* number of elements in hash table */\r
+ uInt hash_bits; /* log2(hash_size) */\r
+ uInt hash_mask; /* hash_size-1 */\r
+\r
+ uInt hash_shift;\r
+ /* Number of bits by which ins_h must be shifted at each input\r
+ * step. It must be such that after MIN_MATCH steps, the oldest\r
+ * byte no longer takes part in the hash key, that is:\r
+ * hash_shift * MIN_MATCH >= hash_bits\r
+ */\r
+\r
+ long block_start;\r
+ /* Window position at the beginning of the current output block. Gets\r
+ * negative when the window is moved backwards.\r
+ */\r
+\r
+ uInt match_length; /* length of best match */\r
+ IPos prev_match; /* previous match */\r
+ int match_available; /* set if previous match exists */\r
+ uInt strstart; /* start of string to insert */\r
+ uInt match_start; /* start of matching string */\r
+ uInt lookahead; /* number of valid bytes ahead in window */\r
+\r
+ uInt prev_length;\r
+ /* Length of the best match at previous step. Matches not greater than this\r
+ * are discarded. This is used in the lazy match evaluation.\r
+ */\r
+\r
+ uInt max_chain_length;\r
+ /* To speed up deflation, hash chains are never searched beyond this\r
+ * length. A higher limit improves compression ratio but degrades the\r
+ * speed.\r
+ */\r
+\r
+ uInt max_lazy_match;\r
+ /* Attempt to find a better match only when the current match is strictly\r
+ * smaller than this value. This mechanism is used only for compression\r
+ * levels >= 4.\r
+ */\r
+# define max_insert_length max_lazy_match\r
+ /* Insert new strings in the hash table only if the match length is not\r
+ * greater than this length. This saves time but degrades compression.\r
+ * max_insert_length is used only for compression levels <= 3.\r
+ */\r
+\r
+ int level; /* compression level (1..9) */\r
+ int strategy; /* favor or force Huffman coding*/\r
+\r
+ uInt good_match;\r
+ /* Use a faster search when the previous match is longer than this */\r
+\r
+ int nice_match; /* Stop searching when current match exceeds this */\r
+\r
+ /* used by trees.c: */\r
+ /* Didn't use ct_data typedef below to suppress compiler warning */\r
+ struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */\r
+ struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */\r
+ struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */\r
+\r
+ struct tree_desc_s l_desc; /* desc. for literal tree */\r
+ struct tree_desc_s d_desc; /* desc. for distance tree */\r
+ struct tree_desc_s bl_desc; /* desc. for bit length tree */\r
+\r
+ ush bl_count[MAX_BITS+1];\r
+ /* number of codes at each bit length for an optimal tree */\r
+\r
+ int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */\r
+ int heap_len; /* number of elements in the heap */\r
+ int heap_max; /* element of largest frequency */\r
+ /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.\r
+ * The same heap array is used to build all trees.\r
+ */\r
+\r
+ uch depth[2*L_CODES+1];\r
+ /* Depth of each subtree used as tie breaker for trees of equal frequency\r
+ */\r
+\r
+ uchf *l_buf; /* buffer for literals or lengths */\r
+\r
+ uInt lit_bufsize;\r
+ /* Size of match buffer for literals/lengths. There are 4 reasons for\r
+ * limiting lit_bufsize to 64K:\r
+ * - frequencies can be kept in 16 bit counters\r
+ * - if compression is not successful for the first block, all input\r
+ * data is still in the window so we can still emit a stored block even\r
+ * when input comes from standard input. (This can also be done for\r
+ * all blocks if lit_bufsize is not greater than 32K.)\r
+ * - if compression is not successful for a file smaller than 64K, we can\r
+ * even emit a stored file instead of a stored block (saving 5 bytes).\r
+ * This is applicable only for zip (not gzip or zlib).\r
+ * - creating new Huffman trees less frequently may not provide fast\r
+ * adaptation to changes in the input data statistics. (Take for\r
+ * example a binary file with poorly compressible code followed by\r
+ * a highly compressible string table.) Smaller buffer sizes give\r
+ * fast adaptation but have of course the overhead of transmitting\r
+ * trees more frequently.\r
+ * - I can't count above 4\r
+ */\r
+\r
+ uInt last_lit; /* running index in l_buf */\r
+\r
+ ushf *d_buf;\r
+ /* Buffer for distances. To simplify the code, d_buf and l_buf have\r
+ * the same number of elements. To use different lengths, an extra flag\r
+ * array would be necessary.\r
+ */\r
+\r
+ ulg opt_len; /* bit length of current block with optimal trees */\r
+ ulg static_len; /* bit length of current block with static trees */\r
+ uInt matches; /* number of string matches in current block */\r
+ uInt insert; /* bytes at end of window left to insert */\r
+\r
+#ifdef DEBUG\r
+ ulg compressed_len; /* total bit length of compressed file mod 2^32 */\r
+ ulg bits_sent; /* bit length of compressed data sent mod 2^32 */\r
+#endif\r
+\r
+ ush bi_buf;\r
+ /* Output buffer. bits are inserted starting at the bottom (least\r
+ * significant bits).\r
+ */\r
+ int bi_valid;\r
+ /* Number of valid bits in bi_buf. All bits above the last valid bit\r
+ * are always zero.\r
+ */\r
+\r
+ ulg high_water;\r
+ /* High water mark offset in window for initialized bytes -- bytes above\r
+ * this are set to zero in order to avoid memory check warnings when\r
+ * longest match routines access bytes past the input. This is then\r
+ * updated to the new high water mark.\r
+ */\r
+\r
+} FAR deflate_state;\r
+\r
+/* Output a byte on the stream.\r
+ * IN assertion: there is enough room in pending_buf.\r
+ */\r
+#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}\r
+\r
+\r
+#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)\r
+/* Minimum amount of lookahead, except at the end of the input file.\r
+ * See deflate.c for comments about the MIN_MATCH+1.\r
+ */\r
+\r
+#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)\r
+/* In order to simplify the code, particularly on 16 bit machines, match\r
+ * distances are limited to MAX_DIST instead of WSIZE.\r
+ */\r
+\r
+#define WIN_INIT MAX_MATCH\r
+/* Number of bytes after end of data in window to initialize in order to avoid\r
+ memory checker errors from longest match routines */\r
+\r
+ /* in trees.c */\r
+void ZLIB_INTERNAL _tr_init OF((deflate_state *s));\r
+int ZLIB_INTERNAL _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));\r
+void ZLIB_INTERNAL _tr_flush_block OF((deflate_state *s, charf *buf,\r
+ ulg stored_len, int last));\r
+void ZLIB_INTERNAL _tr_flush_bits OF((deflate_state *s));\r
+void ZLIB_INTERNAL _tr_align OF((deflate_state *s));\r
+void ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf,\r
+ ulg stored_len, int last));\r
+\r
+#define d_code(dist) \\r
+ ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])\r
+/* Mapping from a distance to a distance code. dist is the distance - 1 and\r
+ * must not have side effects. _dist_code[256] and _dist_code[257] are never\r
+ * used.\r
+ */\r
+\r
+#ifndef DEBUG\r
+/* Inline versions of _tr_tally for speed: */\r
+\r
+#if defined(GEN_TREES_H) || !defined(STDC)\r
+ extern uch ZLIB_INTERNAL _length_code[];\r
+ extern uch ZLIB_INTERNAL _dist_code[];\r
+#else\r
+ extern const uch ZLIB_INTERNAL _length_code[];\r
+ extern const uch ZLIB_INTERNAL _dist_code[];\r
+#endif\r
+\r
+# define _tr_tally_lit(s, c, flush) \\r
+ { uch cc = (c); \\r
+ s->d_buf[s->last_lit] = 0; \\r
+ s->l_buf[s->last_lit++] = cc; \\r
+ s->dyn_ltree[cc].Freq++; \\r
+ flush = (s->last_lit == s->lit_bufsize-1); \\r
+ }\r
+# define _tr_tally_dist(s, distance, length, flush) \\r
+ { uch len = (length); \\r
+ ush dist = (distance); \\r
+ s->d_buf[s->last_lit] = dist; \\r
+ s->l_buf[s->last_lit++] = len; \\r
+ dist--; \\r
+ s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \\r
+ s->dyn_dtree[d_code(dist)].Freq++; \\r
+ flush = (s->last_lit == s->lit_bufsize-1); \\r
+ }\r
+#else\r
+# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)\r
+# define _tr_tally_dist(s, distance, length, flush) \\r
+ flush = _tr_tally(s, distance, length)\r
+#endif\r
+\r
+#endif /* DEFLATE_H */\r
projects / mirror_edk2.git / blobdiff