pgpztrees.c

著名的加密软件的应用于电子邮件中

		/* 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] = (byte)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++] = (byte)code;
			}
		}
		ZipAssert (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++] = (byte)code;
			}
		}
		ZipAssert (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((struct 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 = bit_reverse(n, 5);
}

		return 0;
	}

void ct_free()
{
#ifdef PGP
/* Wipe static arrays */
memset(dyn_ltree, 0, sizeof(dyn_ltree));
memset(dyn_dtree, 0, sizeof(dyn_dtree));
memset(bl_tree, 0, sizeof(bl_tree));
memset(bl_count, 0, sizeof(bl_count));
memset(heap, 0, sizeof(heap));
memset(depth, 0, sizeof(depth));
memset(flag_buf, 0, sizeof(flag_buf));

/* Wipe static variables */
heap_len = 0;
heap_max = 0;
last_lit = 0;
last_dist = 0;
last_flags = 0;
flags = 0;
flag_bit = 0;
opt_len = 0;
static_len = 0;
compressed_len = 0;
input_len = 0;

/* Wipe buffers - d_buf in two halves to avoid 64K limits */
memset(d_buf, 0, DIST_BUFSIZE/2 * sizeof(word16));
memset(d_buf+DIST_BUFSIZE/2, 0, (DIST_BUFSIZE+1)/2 * sizeof(word16));
memset(l_buf, 0, LIT_BUFSIZE);
#endif
#ifdef DYN_ALLOC
fcfree(d_buf);
fcfree(l_buf);
d_buf = NULL;
l_buf = NULL;
#endif
}

/* ===========================================================================
* Initialize a new block.
*/
static void
init_block(void)
{
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;
}

#define SMALLEST 1
/* Index within the heap array of least frequent node in the Huffman tree */


/* ===========================================================================
* Remove the smallest element from the heap and recreate the heap with
* one less element. Updates heap and heap_len.
*/
#define pqremove(tree, top) \
{\
top = heap[SMALLEST]; \
heap[SMALLEST] = heap[heap_len--]; \
pqdownheap(tree, SMALLEST); \
}

/* ===========================================================================
* Compares to subtrees, using the tree depth as tie breaker when
* the subtrees have equal frequency. This minimizes the worst case length.
*/
#define smaller(tree, n, m) \
(tree[n].Freq < tree[m].Freq || \
(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))

/* ===========================================================================
* Restore the heap property by moving down the tree starting at node k,
* exchanging a node with the smallest of its two sons if necessary, stopping
* when the heap property is re-established (each father smaller than its
* two sons).
*/
static void
pqdownheap(struct ct_data near *tree, int k)
	{
		int v = heap[k];
		int j = k << 1; /* left son of k */
		int htemp; /* required because of bug in SASC compiler */

		while (j <= heap_len) {
		/* Set j to the smallest of the two sons: */
		if (j < heap_len && smaller(tree, heap[j+1], heap[j])) j++;

		/* Exit if v is smaller than both sons */
		htemp = heap[j];
		if (smaller(tree, v, htemp)) break;

		/* Exchange v with the smallest son */
			heap[k] = htemp;
		k = j;

		/* And continue down the tree, setting j to the left son of k */
		j <<= 1;
		}
		heap[k] = v;
         }

/* ===========================================================================
* Compute the optimal bit lengths for a tree and update the total bit length
* for the current block.
* IN assertion: the fields freq and dad are set, heap[heap_max] and
* above are the tree nodes sorted by increasing frequency.
* OUT assertions: the field len is set to the optimal bit length, the
* array bl_count contains the frequencies for each bit length.
* The length opt_len is updated; static_len is also updated if stree is
* not null.
*/
static void
gen_bitlen(struct tree_desc near *desc)
{
struct ct_data near *tree = desc->dyn_tree;
int const near *extra = desc->extra_bits;
int base = desc->extra_base;
int max_code = desc->max_code;
int max_length = desc->max_length;
struct 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 */
	word16 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 = (word16)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 += (word32)f * (bits + xbits);
		if (stree)
		static_len += (word32)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 - tree[m].Len) * tree[m].Freq;
		tree[m].Len = (word16)bits;
}
n--;
}
}
}

/* ===========================================================================
* Generate the codes for a given tree and bit counts (which need not be
* optimal).
* IN assertion: the array bl_count contains the bit length statistics for
* the given tree and the field len is set for all tree elements.
* OUT assertion: the field code is set for all tree elements of non
* zero code length.
*/
static void
gen_codes(struct ct_data near *tree, int max_code)
{
word16 next_code[MAX_BITS+1]; /* next code value for each bit length */
word16 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.
*/
ZipAssert (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 = bit_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));
}
	}

/* ===========================================================================
* Construct one Huffman tree and assigns the code bit strings and lengths.
* Update the total bit length for the current block.
* IN assertion: the field freq is set for all tree elements.
* OUT assertions: the fields len and code are set to the optimal bit length
* and corresponding code. The length opt_len is updated; static_len is
* also updated if stree is not null. The field max_code is set.
*/
static void
build_tree(struct tree_desc near *desc)
{
struct ct_data near *tree = desc->dyn_tree;
	struct 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) {
		n = heap[++heap_len] = (max_code < 2 ? ++max_code : 0);
		tree[n].Freq = 1;
		depth[n] = 0;
		opt_len--;
		if (stree)
		static_len -= stree[n].Len;
		/* n 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] = (byte)(MAX(depth[n], depth[m]) + 1);
		tree[n].Dad = tree[m].Dad = (word16)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(desc);

/* The field len is now set, we can generate the bit codes */
gen_codes (tree, max_code);
}

/* ===========================================================================
* Scan a literal or distance tree to determine the frequencies of the codes
* in the bit length tree. Updates opt_len to take into account the repeat
* counts. (The contribution of the bit length codes will be added later
* during the construction of bl_tree.)