trees.c File Reference

#include "deflate.h"

Go to the source code of this file.

Classes
struct	static_tree_desc_s

Macros
#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	DIST_CODE_LEN   512 /* see definition of array dist_code below */
#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	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 ZLIB_INTERNAL	_tr_init (deflate_state *s)
local void	init_block (deflate_state *s)
local void	pqdownheap (deflate_state *s, ct_data *tree, int k)
local void	gen_bitlen (deflate_state *s, tree_desc *desc)
local void	gen_codes (ct_data *tree, int max_code, ushf *bl_count)
local void	build_tree (deflate_state *s, tree_desc *desc)
local void	scan_tree (deflate_state *s, ct_data *tree, int max_code)
local void	send_tree (deflate_state *s, ct_data *tree, int max_code)
local int	build_bl_tree (deflate_state *s)
local void	send_all_trees (deflate_state *s, int lcodes, int dcodes, int blcodes)
void ZLIB_INTERNAL	_tr_stored_block (deflate_state *s, charf *buf, ulg stored_len, int last)
void ZLIB_INTERNAL	_tr_flush_bits (deflate_state *s)
void ZLIB_INTERNAL	_tr_align (deflate_state *s)
void ZLIB_INTERNAL	_tr_flush_block (deflate_state *s, charf *buf, ulg stored_len, int last)
int ZLIB_INTERNAL	_tr_tally (deflate_state *s, unsigned dist, unsigned lc)
local void	compress_block (deflate_state *s, ct_data *ltree, ct_data *dtree)
local int	detect_data_type (deflate_state *s)
local unsigned	bi_reverse (unsigned code, int len)
local void	bi_flush (deflate_state *s)
local void	bi_windup (deflate_state *s)
local void	copy_block (deflate_state *s, charf *buf, unsigned len, int header)

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

Macro Definition Documentation

#define DIST_CODE_LEN   512 /* see definition of array dist_code below */

Definition at line 81 of file trees.c.

#define END_BLOCK   256

Definition at line 50 of file trees.c.

#define MAX_BL_BITS   7

Definition at line 47 of file trees.c.

#define pqremove	(		s,
			tree,
			top
	)

Value:

{\
    top = s->heap[SMALLEST]; \
    s->heap[SMALLEST] = s->heap[s->heap_len--]; \
    pqdownheap(s, tree, SMALLEST); \
}

Definition at line 432 of file trees.c.

#define put_short	(		s,
			w
	)

Value:

{ \
    put_byte(s, (uch)((w) & 0xff)); \
    put_byte(s, (uch)((ush)(w) >> 8)); \
}

Definition at line 176 of file trees.c.

#define REP_3_6   16

Definition at line 53 of file trees.c.

#define REPZ_11_138   18

Definition at line 59 of file trees.c.

#define REPZ_3_10   17

Definition at line 56 of file trees.c.

#define send_bits	(		s,
			value,
			length
	)

Value:

{ int len = length;\
  if (s->bi_valid > (int)Buf_size - len) {\
    int val = value;\
    s->bi_buf |= (ush)val << s->bi_valid;\
    put_short(s, s->bi_buf);\
    s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
    s->bi_valid += len - Buf_size;\
  } else {\
    s->bi_buf |= (ush)(value) << s->bi_valid;\
    s->bi_valid += len;\
  }\
}

Definition at line 213 of file trees.c.

#define send_code	(		s,
			c,
			tree
	)		send_bits(s, tree[c].Code, tree[c].Len)

Definition at line 163 of file trees.c.

#define smaller	(		tree,
			n,
			m,
			depth
	)

Value:

(tree[n].Freq < tree[m].Freq || \
   (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

Definition at line 443 of file trees.c.

#define SMALLEST   1

Definition at line 424 of file trees.c.

Function Documentation

void ZLIB_INTERNAL _tr_align

(

deflate_state *

s)

Definition at line 892 of file trees.c.

void ZLIB_INTERNAL _tr_flush_bits

(

deflate_state *

s)

Definition at line 882 of file trees.c.

void ZLIB_INTERNAL _tr_flush_block	(	deflate_state *	s,
		charf *	buf,
		ulg	stored_len,
		int	last
	)

Definition at line 907 of file trees.c.

void ZLIB_INTERNAL _tr_init

(

deflate_state *

s)

Definition at line 381 of file trees.c.

void ZLIB_INTERNAL _tr_stored_block	(	deflate_state *	s,
		charf *	buf,
		ulg	stored_len,
		int	last
	)

Definition at line 865 of file trees.c.

int ZLIB_INTERNAL _tr_tally	(	deflate_state *	s,
		unsigned	dist,
		unsigned	lc
	)

Definition at line 1008 of file trees.c.

local void bi_flush

(

deflate_state *

s)

Definition at line 1167 of file trees.c.

local unsigned bi_reverse	(	unsigned	code,
		int	len
	)

Definition at line 1152 of file trees.c.

local void bi_windup

(

deflate_state *

s)

Definition at line 1184 of file trees.c.

local int build_bl_tree

(

deflate_state *

s)

Definition at line 801 of file trees.c.

local void build_tree	(	deflate_state *	s,
		tree_desc *	desc
	)

Definition at line 617 of file trees.c.

local void compress_block	(	deflate_state *	s,
		ct_data *	ltree,
		ct_data *	dtree
	)

Definition at line 1058 of file trees.c.

local void copy_block	(	deflate_state *	s,
		charf *	buf,
		unsigned	len,
		int	header
	)

Definition at line 1203 of file trees.c.

local int detect_data_type

(

deflate_state *

s)

Definition at line 1118 of file trees.c.

local void gen_bitlen	(	deflate_state *	s,
		tree_desc *	desc
	)

Definition at line 488 of file trees.c.

local void gen_codes	(	ct_data *	tree,
		int	max_code,
		ushf *	bl_count
	)

Definition at line 575 of file trees.c.

local void init_block

(

deflate_state *

s)

Definition at line 409 of file trees.c.

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 pqdownheap	(	deflate_state *	s,
		ct_data *	tree,
		int	k
	)

Definition at line 453 of file trees.c.

local void scan_tree	(	deflate_state *	s,
		ct_data *	tree,
		int	max_code
	)

Definition at line 705 of file trees.c.

local void send_all_trees	(	deflate_state *	s,
		int	lcodes,
		int	dcodes,
		int	blcodes
	)

Definition at line 836 of file trees.c.

local void send_tree	(	deflate_state *	s,
		ct_data *	tree,
		int	max_code
	)

Definition at line 750 of file trees.c.

local void tr_static_init

(

)

Definition at line 234 of file trees.c.

Variable Documentation

uch _dist_code[DIST_CODE_LEN]

Definition at line 98 of file trees.c.

uch _length_code[MAX_MATCH-MIN_MATCH+1]

Definition at line 104 of file trees.c.

local int base_dist[D_CODES]

Definition at line 110 of file trees.c.

local int base_length[LENGTH_CODES]

Definition at line 107 of file trees.c.

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}

Definition at line 72 of file trees.c.

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}

Definition at line 69 of file trees.c.

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}

Definition at line 66 of file trees.c.

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}

Definition at line 63 of file trees.c.

local static_tree_desc static_bl_desc

Initial value:

=
{(const ct_data *)0, extra_blbits, 0,   BL_CODES, MAX_BL_BITS}

Definition at line 131 of file trees.c.

local static_tree_desc static_d_desc

Initial value:

=
{static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS}

Definition at line 128 of file trees.c.

local ct_data static_dtree[D_CODES]

Definition at line 93 of file trees.c.

local static_tree_desc static_l_desc

Initial value:

=
{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}

Definition at line 125 of file trees.c.

local ct_data static_ltree[L_CODES+2]

Definition at line 86 of file trees.c.