trees.c File Reference

Output deflated data using Huffman coding. More...

#include "deflate.h"

Data Structures
struct	static_tree_desc

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	TCONST   const
#define	put_short(s, w)
#define	send_code(s, c, tree)   send_bits(s, tree[c].Code, tree[c].Len)
#define	send_bits(s, value, length)
#define	SMALLEST   1
#define	pqremove(s, tree, top)
#define	smaller(tree, n, m, depth)

Functions
local unsigned	bi_reverse (unsigned code, int len)
local void	bi_flush (deflate_state *s)
local void	bi_windup (deflate_state *s)
local void	gen_codes (ct_data *tree, int max_code, ushf *bl_count)
local void	tr_static_init ()
local void	init_block (deflate_state *s)
void ZLIB_INTERNAL	_tr_init (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	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)
local void	compress_block (deflate_state *s, const ct_data *ltree, const ct_data *dtree)
local int	detect_data_type (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)

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 TCONST static_tree_desc	static_l_desc
local TCONST static_tree_desc	static_d_desc
local TCONST static_tree_desc	static_bl_desc

Detailed Description

Output deflated data using Huffman coding.

Copyright (C) 1995-2021 Jean-loup Gailly detect_data_type() function provided freely by Cosmin Truta, 2006 For conditions of distribution and use, see copyright notice in zlib.h

ALGORITHM

The "deflation" process uses several Huffman trees. The more common source values are represented by shorter bit sequences.

Each code tree is stored in a compressed form which is itself a Huffman encoding of the lengths of all the code strings (in ascending order by source values). The actual code strings are reconstructed from the lengths in the inflate process, as described in the deflate specification.

REFERENCES

 Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
 Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc

 Storer, James A.
     Data Compression:  Methods and Theory, pp. 49-50.
     Computer Science Press, 1988.  ISBN 0-7167-8156-5.

 Sedgewick, R.
     Algorithms, p290.
     Addison-Wesley, 1983. ISBN 0-201-06672-6.

Macro Definition Documentation

pqremove

#define pqremove	(		s,
			tree,
			top
	)

Value:

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

put_short

#define put_short	(		s,
			w
	)

Value:

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

send_bits

#define send_bits	(		s,
			value,
			length
	)

Value:

{ int len = length;\
  if (s->bi_valid > (int)Buf_size - len) {\
    int val = (int)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;\
  }\
}

smaller

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

Value:

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

Variable Documentation

static_bl_desc

local TCONST static_tree_desc static_bl_desc

Initial value:

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

static_d_desc

local TCONST static_tree_desc static_d_desc

Initial value:

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

static_l_desc

local TCONST static_tree_desc static_l_desc

Initial value:

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