trees.c File Reference

00240 {
00241 #if defined(GEN_TREES_H) || !defined(STDC)
00242     static int static_init_done = 0;
00243     int n;        /* iterates over tree elements */
00244     int bits;     /* bit counter */
00245     int length;   /* length value */
00246     int code;     /* code value */
00247     int dist;     /* distance index */
00248     ush bl_count[MAX_BITS+1];
00249     /* number of codes at each bit length for an optimal tree */
00250 
00251     if (static_init_done) return;
00252 
00253     /* For some embedded targets, global variables are not initialized: */
00254     static_l_desc.static_tree = static_ltree;
00255     static_l_desc.extra_bits = extra_lbits;
00256     static_d_desc.static_tree = static_dtree;
00257     static_d_desc.extra_bits = extra_dbits;
00258     static_bl_desc.extra_bits = extra_blbits;
00259 
00260     /* Initialize the mapping length (0..255) -> length code (0..28) */
00261     length = 0;
00262     for (code = 0; code < LENGTH_CODES-1; code++) {
00263         base_length[code] = length;
00264         for (n = 0; n < (1<<extra_lbits[code]); n++) {
00265             _length_code[length++] = (uch)code;
00266         }
00267     }
00268     Assert (length == 256, "tr_static_init: length != 256");
00269     /* Note that the length 255 (match length 258) can be represented
00270      * in two different ways: code 284 + 5 bits or code 285, so we
00271      * overwrite length_code[255] to use the best encoding:
00272      */
00273     _length_code[length-1] = (uch)code;
00274 
00275     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
00276     dist = 0;
00277     for (code = 0 ; code < 16; code++) {
00278         base_dist[code] = dist;
00279         for (n = 0; n < (1<<extra_dbits[code]); n++) {
00280             _dist_code[dist++] = (uch)code;
00281         }
00282     }
00283     Assert (dist == 256, "tr_static_init: dist != 256");
00284     dist >>= 7; /* from now on, all distances are divided by 128 */
00285     for ( ; code < D_CODES; code++) {
00286         base_dist[code] = dist << 7;
00287         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
00288             _dist_code[256 + dist++] = (uch)code;
00289         }
00290     }
00291     Assert (dist == 256, "tr_static_init: 256+dist != 512");
00292 
00293     /* Construct the codes of the static literal tree */
00294     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
00295     n = 0;
00296     while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
00297     while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
00298     while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
00299     while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
00300     /* Codes 286 and 287 do not exist, but we must include them in the
00301      * tree construction to get a canonical Huffman tree (longest code
00302      * all ones)
00303      */
00304     gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
00305 
00306     /* The static distance tree is trivial: */
00307     for (n = 0; n < D_CODES; n++) {
00308         static_dtree[n].Len = 5;
00309         static_dtree[n].Code = bi_reverse((unsigned)n, 5);
00310     }
00311     static_init_done = 1;
00312 
00313 #  ifdef GEN_TREES_H
00314     gen_trees_header();
00315 #  endif
00316 #endif /* defined(GEN_TREES_H) || !defined(STDC) */
00317 }

Compounds
struct	static_tree_desc_s
Defines
#define	MAX_BL_BITS 7
#define	END_BLOCK 256
#define	REP_3_6 16
#define	REPZ_3_10 17
#define	REPZ_11_138 18
#define	Buf_size (8 * 2*sizeof(char))
#define	DIST_CODE_LEN 512
#define	send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
#define	put_short(s, w)
#define	send_bits(s, value, length)
#define	MAX(a, b) (a >= b ? a : b)
#define	SMALLEST 1
#define	pqremove(s, tree, top)
#define	smaller(tree, n, m, depth)
Functions
local void tr_static_init	OF ((void))
local void init_block	OF ((deflate_state *s))
local void pqdownheap	OF ((deflate_state s, ct_data tree, int k))
local void gen_bitlen	OF ((deflate_state s, tree_desc desc))
local void gen_codes	OF ((ct_data tree, int max_code, ushf bl_count))
local void scan_tree	OF ((deflate_state s, ct_data tree, int max_code))
local void send_all_trees	OF ((deflate_state *s, int lcodes, int dcodes, int blcodes))
local void compress_block	OF ((deflate_state s, ct_data ltree, ct_data *dtree))
local unsigned bi_reverse	OF ((unsigned value, int length))
local void copy_block	OF ((deflate_state s, charf buf, unsigned len, int header))
local void	tr_static_init ()
void	_tr_init (s) deflate_state *s
Variables
local const int	extra_lbits [LENGTH_CODES] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}
local const int	extra_dbits [D_CODES] = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}
local const int	extra_blbits [BL_CODES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}
local const uch	bl_order [BL_CODES] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}
local ct_data	static_ltree [L_CODES+2]
local ct_data	static_dtree [D_CODES]
uch	_dist_code [DIST_CODE_LEN]
uch	_length_code [MAX_MATCH-MIN_MATCH+1]
local int	base_length [LENGTH_CODES]
local int	base_dist [D_CODES]
local static_tree_desc	static_l_desc
local static_tree_desc	static_d_desc
local static_tree_desc	static_bl_desc
ct_data *	tree
int	k
tree_desc *	desc
int	max_code
ushf *	bl_count
int	lcodes
int	dcodes
int	blcodes
charf *	buf
ulg	stored_len
int	eof
unsigned	dist
unsigned	lc
ct_data *	ltree
ct_data *	dtree
int	len
int	header

trees.c File Reference

Compounds

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation