trees.c File Reference

#include <config.h>
#include <ctype.h>
#include "tailor.h"
#include "gzip.h"

Go to the source code of this file.

Classes
struct	ct_data
struct	tree_desc
Defines
#define	MAX_BITS   15
#define	MAX_BL_BITS   7
#define	LENGTH_CODES   29
#define	LITERALS   256
#define	END_BLOCK   256
#define	L_CODES   (LITERALS+1+LENGTH_CODES)
#define	D_CODES   30
#define	BL_CODES   19
#define	STORED_BLOCK   0
#define	STATIC_TREES   1
#define	DYN_TREES   2
#define	LIT_BUFSIZE   0x8000
#define	REP_3_6   16
#define	REPZ_3_10   17
#define	REPZ_11_138   18
#define	Freq   fc.freq
#define	Code   fc.code
#define	Dad   dl.dad
#define	Len   dl.len
#define	HEAP_SIZE   (2*L_CODES+1)
#define	l_buf   inbuf
#define	send_code(c, tree)   send_bits(tree[c].Code, tree[c].Len)
#define	d_code(dist)   ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
#define	MAX(a, b)   (a >= b ? a : b)
#define	SMALLEST   1
#define	pqremove(tree, top)
#define	smaller(tree, n, m)
Typedefs
typedef ct_data	ct_data
typedef tree_desc	tree_desc
Functions
local void init_block	OF ((void))
void	ct_init (ush *attr, int *methodp)
local void	init_block ()
local void	pqdownheap (ct_data near *tree, int k)
local void	gen_bitlen (tree_desc near *desc)
local void	gen_codes (ct_data near *tree, int max_code)
local void	build_tree (tree_desc near *desc)
local void	scan_tree (ct_data near *tree, int max_code)
local void	send_tree (ct_data near *tree, int max_code)
local int	build_bl_tree ()
local void	send_all_trees (int lcodes, int dcodes, int blcodes)
off_t	flush_block (char *buf, ulg stored_len, int eof)
int	ct_tally (int dist, int lc)
local void	compress_block (ct_data near *ltree, ct_data near *dtree)
local void	set_file_type ()
Variables
local int near	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 int near	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 int near	extra_blbits [BL_CODES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}
local ct_data near	dyn_ltree [HEAP_SIZE]
local ct_data near	dyn_dtree [2 *D_CODES+1]
local ct_data near	static_ltree [L_CODES+2]
local ct_data near	static_dtree [D_CODES]
local ct_data near	bl_tree [2 *BL_CODES+1]
local tree_desc near	l_desc
local tree_desc near	d_desc
local tree_desc near	bl_desc
local ush near	bl_count [MAX_BITS+1]
local uch near	bl_order [BL_CODES] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}
local int near	heap [2 *L_CODES+1]
local int	heap_len
local int	heap_max
local uch near	depth [2 *L_CODES+1]
local uch	length_code [MAX_MATCH-MIN_MATCH+1]
local uch	dist_code [512]
local int near	base_length [LENGTH_CODES]
local int near	base_dist [D_CODES]
local uch near	flag_buf [(LIT_BUFSIZE/8)]
local unsigned	last_lit
local unsigned	last_dist
local unsigned	last_flags
local uch	flags
local uch	flag_bit
local ulg	opt_len
local ulg	static_len
local off_t	compressed_len
local off_t	input_len
ush *	file_type
int *	file_method
long	block_start
unsigned near	strstart

---

Define Documentation

#define BL_CODES   19

Definition at line 104 of file trees.c. Referenced by build_bl_tree(), init_block(), and send_all_trees().

#define Code   fc.code

Definition at line 186 of file trees.c. Referenced by gen_codes(), and longest_match().

#define d_code (  dist   )     ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])

Definition at line 330 of file trees.c. Referenced by compress_block(), and ct_tally().

#define D_CODES   30

Definition at line 101 of file trees.c. Referenced by compress_block(), ct_init(), ct_tally(), init_block(), and send_all_trees().

#define Dad   dl.dad

Definition at line 187 of file trees.c.

#define DYN_TREES   2

Definition at line 119 of file trees.c. Referenced by flush_block().

#define END_BLOCK   256

Definition at line 95 of file trees.c. Referenced by compress_block(), and init_block().

#define Freq   fc.freq

Definition at line 185 of file trees.c. Referenced by build_tree().

#define HEAP_SIZE   (2*L_CODES+1)

Definition at line 190 of file trees.c. Referenced by build_tree(), and gen_bitlen().

#define l_buf   inbuf

Definition at line 265 of file trees.c. Referenced by compress_block(), and ct_tally().

#define L_CODES   (LITERALS+1+LENGTH_CODES)

Definition at line 98 of file trees.c. Referenced by ct_init(), init_block(), and send_all_trees().

#define Len   dl.len

Definition at line 188 of file trees.c. Referenced by build_bl_tree(), ct_init(), gen_bitlen(), and send_all_trees().

#define LENGTH_CODES   29

Definition at line 89 of file trees.c. Referenced by ct_init().

#define LIT_BUFSIZE   0x8000

Definition at line 129 of file trees.c. Referenced by ct_tally().

#define LITERALS   256

Definition at line 92 of file trees.c. Referenced by compress_block(), ct_tally(), read_tree(), and set_file_type().

#define MAX (  a, b   )     (a >= b ? a : b)

Definition at line 337 of file trees.c. Referenced by build_tree().

#define MAX_BITS   15

Definition at line 83 of file trees.c. Referenced by ct_init(), gen_bitlen(), and gen_codes().

#define MAX_BL_BITS   7

Definition at line 86 of file trees.c.

#define pqremove (  tree, top   )

Value: {\ top = heap[SMALLEST]; \ heap[SMALLEST] = heap[heap_len--]; \ pqdownheap(tree, SMALLEST); \ } Definition at line 443 of file trees.c. Referenced by build_tree().

#define REP_3_6   16

Definition at line 160 of file trees.c. Referenced by scan_tree(), and send_tree().

#define REPZ_11_138   18

Definition at line 166 of file trees.c. Referenced by scan_tree(), and send_tree().

#define REPZ_3_10   17

Definition at line 163 of file trees.c. Referenced by scan_tree(), and send_tree().

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

Definition at line 321 of file trees.c. Referenced by compress_block(), and send_tree().

#define smaller (  tree, n, m   )

Value: (tree[n].Freq < tree[m].Freq || \ (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) Definition at line 454 of file trees.c. Referenced by pqdownheap().

#define SMALLEST   1

Definition at line 435 of file trees.c. Referenced by build_tree().

#define STATIC_TREES   1

Definition at line 118 of file trees.c. Referenced by flush_block().

#define STORED_BLOCK   0

Definition at line 117 of file trees.c. Referenced by flush_block().

---

Typedef Documentation

typedef struct ct_data ct_data

typedef struct tree_desc tree_desc

---

Function Documentation

local int build_bl_tree (   )

Definition at line 803 of file trees.c. References BL_CODES, bl_desc, bl_order, bl_tree, build_tree(), d_desc, dyn_dtree, dyn_ltree, l_desc, Len, tree_desc::max_code, near, opt_len, scan_tree(), static_len, and Tracev. Referenced by flush_block(). { int max_blindex; /* index of last bit length code of non zero freq */ /* Determine the bit length frequencies for literal and distance trees */ scan_tree((ct_data near *)dyn_ltree, l_desc.max_code); scan_tree((ct_data near *)dyn_dtree, d_desc.max_code); /* Build the bit length tree: */ build_tree((tree_desc near *)(&bl_desc)); /* opt_len now includes the length of the tree representations, except * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. */ /* Determine the number of bit length codes to send. The pkzip format * requires that at least 4 bit length codes be sent. (appnote.txt says * 3 but the actual value used is 4.) */ for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { if (bl_tree[bl_order[max_blindex]].Len != 0) break; } /* Update opt_len to include the bit length tree and counts */ opt_len += 3*(max_blindex+1) + 5+5+4; Tracev((stderr, "\ndyn trees: dyn %lu, stat %lu", opt_len, static_len)); return max_blindex; }

local void build_tree (  tree_desc near *  desc  )

Definition at line 622 of file trees.c. References bl_tree, depth, Freq, gen_bitlen(), gen_codes(), heap, heap_len, heap_max, HEAP_SIZE, MAX, near, opt_len, pqdownheap(), pqremove, SMALLEST, and static_len. Referenced by build_bl_tree(), flush_block(), and unpack(). { ct_data near *tree = desc->dyn_tree; ct_data near *stree = desc->static_tree; int elems = desc->elems; int n, m; /* iterate over heap elements */ int max_code = -1; /* largest code with non zero frequency */ int node = elems; /* next internal node of the tree */ /* Construct the initial heap, with least frequent element in * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. * heap[0] is not used. */ heap_len = 0, heap_max = HEAP_SIZE; for (n = 0; n < elems; n++) { if (tree[n].Freq != 0) { heap[++heap_len] = max_code = n; depth[n] = 0; } else { tree[n].Len = 0; } } /* The pkzip format requires that at least one distance code exists, * and that at least one bit should be sent even if there is only one * possible code. So to avoid special checks later on we force at least * two codes of non zero frequency. */ while (heap_len < 2) { int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0); tree[new].Freq = 1; depth[new] = 0; opt_len--; if (stree) static_len -= stree[new].Len; /* new is 0 or 1 so it does not have extra bits */ } desc->max_code = max_code; /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, * establish sub-heaps of increasing lengths: */ for (n = heap_len/2; n >= 1; n--) pqdownheap(tree, n); /* Construct the Huffman tree by repeatedly combining the least two * frequent nodes. */ do { pqremove(tree, n); /* n = node of least frequency */ m = heap[SMALLEST]; /* m = node of next least frequency */ heap[--heap_max] = n; /* keep the nodes sorted by frequency */ heap[--heap_max] = m; /* Create a new node father of n and m */ tree[node].Freq = tree[n].Freq + tree[m].Freq; depth[node] = (uch) (MAX(depth[n], depth[m]) + 1); tree[n].Dad = tree[m].Dad = (ush)node; #ifdef DUMP_BL_TREE if (tree == bl_tree) { fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); } #endif /* and insert the new node in the heap */ heap[SMALLEST] = node++; pqdownheap(tree, SMALLEST); } while (heap_len >= 2); heap[--heap_max] = heap[SMALLEST]; /* At this point, the fields freq and dad are set. We can now * generate the bit lengths. */ gen_bitlen((tree_desc near *)desc); /* The field len is now set, we can generate the bit codes */ gen_codes ((ct_data near *)tree, max_code); }

local void compress_block (  ct_data near *  ltree, ct_data near *  dtree )

Definition at line 1020 of file trees.c. References Assert, base_dist, base_length, d_code, D_CODES, END_BLOCK, extra_dbits, extra_lbits, flag_buf, l_buf, last_lit, length_code, LITERALS, send_bits(), send_code, and Tracecv. Referenced by flush_block(). { unsigned dist; /* distance of matched string */ int lc; /* match length or unmatched char (if dist == 0) */ unsigned lx = 0; /* running index in l_buf */ unsigned dx = 0; /* running index in d_buf */ unsigned fx = 0; /* running index in flag_buf */ uch flag = 0; /* current flags */ unsigned code; /* the code to send */ int extra; /* number of extra bits to send */ if (last_lit != 0) do { if ((lx & 7) == 0) flag = flag_buf[fx++]; lc = l_buf[lx++]; if ((flag & 1) == 0) { send_code(lc, ltree); /* send a literal byte */ Tracecv(isgraph(lc), (stderr," '%c' ", lc)); } else { /* Here, lc is the match length - MIN_MATCH */ code = length_code[lc]; send_code(code+LITERALS+1, ltree); /* send the length code */ extra = extra_lbits[code]; if (extra != 0) { lc -= base_length[code]; send_bits(lc, extra); /* send the extra length bits */ } dist = d_buf[dx++]; /* Here, dist is the match distance - 1 */ code = d_code(dist); Assert (code < D_CODES, "bad d_code"); send_code(code, dtree); /* send the distance code */ extra = extra_dbits[code]; if (extra != 0) { dist -= base_dist[code]; send_bits(dist, extra); /* send the extra distance bits */ } } /* literal or match pair ? */ flag >>= 1; } while (lx < last_lit); send_code(END_BLOCK, ltree); }

void ct_init (  ush *  attr, int *  methodp )

Definition at line 345 of file trees.c. References Assert, base_dist, base_length, bi_reverse(), bl_count, compressed_len, D_CODES, dist_code, extra_dbits, extra_lbits, file_method, file_type, gen_codes(), init_block(), input_len, L_CODES, Len, length_code, LENGTH_CODES, MAX_BITS, near, static_dtree, and static_ltree. Referenced by zip(). { int n; /* iterates over tree elements */ int bits; /* bit counter */ int length; /* length value */ int code; /* code value */ int dist; /* distance index */ file_type = attr; file_method = methodp; compressed_len = input_len = 0L; if (static_dtree[0].Len != 0) return; /* ct_init already called */ /* Initialize the mapping length (0..255) -> length code (0..28) */ length = 0; for (code = 0; code < LENGTH_CODES-1; code++) { base_length[code] = length; for (n = 0; n < (1<<extra_lbits[code]); n++) { length_code[length++] = (uch)code; } } Assert (length == 256, "ct_init: length != 256"); /* Note that the length 255 (match length 258) can be represented * in two different ways: code 284 + 5 bits or code 285, so we * overwrite length_code[255] to use the best encoding: */ length_code[length-1] = (uch)code; /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ dist = 0; for (code = 0 ; code < 16; code++) { base_dist[code] = dist; for (n = 0; n < (1<<extra_dbits[code]); n++) { dist_code[dist++] = (uch)code; } } Assert (dist == 256, "ct_init: dist != 256"); dist >>= 7; /* from now on, all distances are divided by 128 */ for ( ; code < D_CODES; code++) { base_dist[code] = dist << 7; for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { dist_code[256 + dist++] = (uch)code; } } Assert (dist == 256, "ct_init: 256+dist != 512"); /* Construct the codes of the static literal tree */ for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; n = 0; while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; /* Codes 286 and 287 do not exist, but we must include them in the * tree construction to get a canonical Huffman tree (longest code * all ones) */ gen_codes((ct_data near *)static_ltree, L_CODES+1); /* The static distance tree is trivial: */ for (n = 0; n < D_CODES; n++) { static_dtree[n].Len = 5; static_dtree[n].Code = bi_reverse(n, 5); } /* Initialize the first block of the first file: */ init_block(); }

int ct_tally (  int  dist, int  lc )

Definition at line 967 of file trees.c. References Assert, block_start, d_code, D_CODES, DIST_BUFSIZE, dyn_dtree, dyn_ltree, extra_dbits, flag_bit, flag_buf, flags, l_buf, last_dist, last_flags, last_lit, length_code, level, LIT_BUFSIZE, LITERALS, MAX_DIST, MAX_MATCH, MIN_MATCH, strstart, and Trace. Referenced by deflate(), and deflate_fast(). { l_buf[last_lit++] = (uch)lc; if (dist == 0) { /* lc is the unmatched char */ dyn_ltree[lc].Freq++; } else { /* Here, lc is the match length - MIN_MATCH */ dist--; /* dist = match distance - 1 */ Assert((ush)dist < (ush)MAX_DIST && (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match"); dyn_ltree[length_code[lc]+LITERALS+1].Freq++; dyn_dtree[d_code(dist)].Freq++; d_buf[last_dist++] = (ush)dist; flags |= flag_bit; } flag_bit <<= 1; /* Output the flags if they fill a byte: */ if ((last_lit & 7) == 0) { flag_buf[last_flags++] = flags; flags = 0, flag_bit = 1; } /* Try to guess if it is profitable to stop the current block here */ if (level > 2 && (last_lit & 0xfff) == 0) { /* Compute an upper bound for the compressed length */ ulg out_length = (ulg)last_lit*8L; ulg in_length = (ulg)strstart-block_start; int dcode; for (dcode = 0; dcode < D_CODES; dcode++) { out_length += (ulg)dyn_dtree[dcode].Freq*(5L+extra_dbits[dcode]); } out_length >>= 3; Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", last_lit, last_dist, in_length, out_length, 100L - out_length*100L/in_length)); if (last_dist < last_lit/2 && out_length < in_length/2) return 1; } return (last_lit == LIT_BUFSIZE-1 || last_dist == DIST_BUFSIZE); /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K * on 16 bit machines and because stored blocks are restricted to * 64K-1 bytes. */ }

off_t flush_block (  char *  buf, ulg  stored_len, int  eof )

Definition at line 863 of file trees.c. References Assert, bi_windup(), build_bl_tree(), build_tree(), bytes_in, compress_block(), compressed_len, copy_block(), d_desc, dyn_dtree, dyn_ltree, DYN_TREES, file_method, file_type, flag_buf, flags, gzip_error(), init_block(), input_len, l_desc, last_dist, last_flags, last_lit, level, near, opt_len, seekable, send_all_trees(), send_bits(), set_file_type(), static_dtree, static_len, static_ltree, STATIC_TREES, STORED, STORED_BLOCK, Trace, Tracev, and UNKNOWN. { ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ int max_blindex; /* index of last bit length code of non zero freq */ flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */ /* Check if the file is ascii or binary */ if (*file_type == (ush)UNKNOWN) set_file_type(); /* Construct the literal and distance trees */ build_tree((tree_desc near *)(&l_desc)); Tracev((stderr, "\nlit data: dyn %lu, stat %lu", opt_len, static_len)); build_tree((tree_desc near *)(&d_desc)); Tracev((stderr, "\ndist data: dyn %lu, stat %lu", opt_len, static_len)); /* At this point, opt_len and static_len are the total bit lengths of * the compressed block data, excluding the tree representations. */ /* Build the bit length tree for the above two trees, and get the index * in bl_order of the last bit length code to send. */ max_blindex = build_bl_tree(); /* Determine the best encoding. Compute first the block length in bytes */ opt_lenb = (opt_len+3+7)>>3; static_lenb = (static_len+3+7)>>3; input_len += stored_len; /* for debugging only */ Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", opt_lenb, opt_len, static_lenb, static_len, stored_len, last_lit, last_dist)); if (static_lenb <= opt_lenb) opt_lenb = static_lenb; /* If compression failed and this is the first and last block, * and if the zip file can be seeked (to rewrite the local header), * the whole file is transformed into a stored file: */ #ifdef FORCE_METHOD if (level == 1 && eof && compressed_len == 0L) { /* force stored file */ #else if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) { #endif /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ if (!buf) gzip_error ("block vanished"); copy_block(buf, (unsigned)stored_len, 0); /* without header */ compressed_len = stored_len << 3; *file_method = STORED; #ifdef FORCE_METHOD } else if (level == 2 && buf != (char*)0) { /* force stored block */ #else } else if (stored_len+4 <= opt_lenb && buf != (char*)0) { /* 4: two words for the lengths */ #endif /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. * Otherwise we can't have processed more than WSIZE input bytes since * the last block flush, because compression would have been * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to * transform a block into a stored block. */ send_bits((STORED_BLOCK<<1)+eof, 3); /* send block type */ compressed_len = (compressed_len + 3 + 7) & ~7L; compressed_len += (stored_len + 4) << 3; copy_block(buf, (unsigned)stored_len, 1); /* with header */ #ifdef FORCE_METHOD } else if (level == 3) { /* force static trees */ #else } else if (static_lenb == opt_lenb) { #endif send_bits((STATIC_TREES<<1)+eof, 3); compress_block((ct_data near *)static_ltree, (ct_data near *)static_dtree); compressed_len += 3 + static_len; } else { send_bits((DYN_TREES<<1)+eof, 3); send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1); compress_block((ct_data near *)dyn_ltree, (ct_data near *)dyn_dtree); compressed_len += 3 + opt_len; } Assert (compressed_len == bits_sent, "bad compressed size"); init_block(); if (eof) { Assert (input_len == bytes_in, "bad input size"); bi_windup(); compressed_len += 7; /* align on byte boundary */ } return compressed_len >> 3; }

local void gen_bitlen (  tree_desc near *  desc  )

Definition at line 496 of file trees.c. References bl_count, heap, heap_max, HEAP_SIZE, Len, MAX_BITS, near, opt_len, static_len, and Trace. Referenced by build_tree(). { ct_data near *tree = desc->dyn_tree; int near *extra = desc->extra_bits; int base = desc->extra_base; int max_code = desc->max_code; int max_length = desc->max_length; ct_data near *stree = desc->static_tree; int h; /* heap index */ int n, m; /* iterate over the tree elements */ int bits; /* bit length */ int xbits; /* extra bits */ ush f; /* frequency */ int overflow = 0; /* number of elements with bit length too large */ for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; /* In a first pass, compute the optimal bit lengths (which may * overflow in the case of the bit length tree). */ tree[heap[heap_max]].Len = 0; /* root of the heap */ for (h = heap_max+1; h < HEAP_SIZE; h++) { n = heap[h]; bits = tree[tree[n].Dad].Len + 1; if (bits > max_length) bits = max_length, overflow++; tree[n].Len = (ush)bits; /* We overwrite tree[n].Dad which is no longer needed */ if (n > max_code) continue; /* not a leaf node */ bl_count[bits]++; xbits = 0; if (n >= base) xbits = extra[n-base]; f = tree[n].Freq; opt_len += (ulg)f * (bits + xbits); if (stree) static_len += (ulg)f * (stree[n].Len + xbits); } if (overflow == 0) return; Trace((stderr,"\nbit length overflow\n")); /* This happens for example on obj2 and pic of the Calgary corpus */ /* Find the first bit length which could increase: */ do { bits = max_length-1; while (bl_count[bits] == 0) bits--; bl_count[bits]--; /* move one leaf down the tree */ bl_count[bits+1] += 2; /* move one overflow item as its brother */ bl_count[max_length]--; /* The brother of the overflow item also moves one step up, * but this does not affect bl_count[max_length] */ overflow -= 2; } while (overflow > 0); /* Now recompute all bit lengths, scanning in increasing frequency. * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all * lengths instead of fixing only the wrong ones. This idea is taken * from 'ar' written by Haruhiko Okumura.) */ for (bits = max_length; bits != 0; bits--) { n = bl_count[bits]; while (n != 0) { m = heap[--h]; if (m > max_code) continue; if (tree[m].Len != (unsigned) bits) { Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); opt_len += ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq; tree[m].Len = (ush)bits; } n--; } } }

local void gen_codes (  ct_data near *  tree, int  max_code )

Definition at line 581 of file trees.c. References Assert, bi_reverse(), bl_count, Code, MAX_BITS, static_ltree, Tracec, and Tracev. Referenced by build_tree(), and ct_init(). { ush next_code[MAX_BITS+1]; /* next code value for each bit length */ ush code = 0; /* running code value */ int bits; /* bit index */ int n; /* code index */ /* The distribution counts are first used to generate the code values * without bit reversal. */ for (bits = 1; bits <= MAX_BITS; bits++) { next_code[bits] = code = (code + bl_count[bits-1]) << 1; } /* Check that the bit counts in bl_count are consistent. The last code * must be all ones. */ Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, "inconsistent bit counts"); Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); for (n = 0; n <= max_code; n++) { int len = tree[n].Len; if (len == 0) continue; /* Now reverse the bits */ tree[n].Code = bi_reverse(next_code[len]++, len); Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); } }

local void init_block (   )

Definition at line 420 of file trees.c. References BL_CODES, bl_tree, D_CODES, dyn_dtree, dyn_ltree, END_BLOCK, flag_bit, flags, L_CODES, last_dist, last_flags, last_lit, opt_len, and static_len. Referenced by ct_init(), and flush_block(). { int n; /* iterates over tree elements */ /* Initialize the trees. */ for (n = 0; n < L_CODES; n++) dyn_ltree[n].Freq = 0; for (n = 0; n < D_CODES; n++) dyn_dtree[n].Freq = 0; for (n = 0; n < BL_CODES; n++) bl_tree[n].Freq = 0; dyn_ltree[END_BLOCK].Freq = 1; opt_len = static_len = 0L; last_lit = last_dist = last_flags = 0; flags = 0; flag_bit = 1; }

local void init_block OF (  (void)   )

Definition at line 268 of file gzip.c. { fprintf (stderr, "Try `%s --help' for more information.\n", program_name); do_exit (ERROR); }

local void pqdownheap (  ct_data near *  tree, int  k )

Definition at line 464 of file trees.c. References heap, heap_len, j, and smaller. Referenced by build_tree(). { int v = heap[k]; int j = k << 1; /* left son of k */ while (j <= heap_len) { /* Set j to the smallest of the two sons: */ if (j < heap_len && smaller(tree,