gzip.c

这是一个SIGMA方案的PMP播放器的UCLINUX程序,可播放DVD,VCD,CD MP3...有很好的参考价值.

 * must not have side effects. dist_code[256] and dist_code[257] are never
 * used.
 */

/* the arguments must not have side effects */

/* ===========================================================================
 * Allocate the match buffer, initialize the various tables and save the
 * location of the internal file attribute (ascii/binary) and method
 * (DEFLATE/STORE).
 */
static void ct_init(ush *attr, int *methodp)
{
	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 = 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 *) 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();
}

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

#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(ct_data *tree, int k)
{
	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, heap[j + 1], heap[j]))
			j++;

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

		/* Exchange v with the smallest son */
		heap[k] = heap[j];
		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(tree_desc *desc)
{
	ct_data *tree = desc->dyn_tree;
	const extra_bits_t *extra = desc->extra_bits;
	int base = desc->extra_base;
	int max_code = desc->max_code;
	int max_length = desc->max_length;
	ct_data *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--;
		}
	}
}

/* ===========================================================================
 * 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(ct_data *tree, int max_code)
{
	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));
	}
}

/* ===========================================================================
 * 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(tree_desc *desc)
{
	ct_data *tree = desc->dyn_tree;
	ct_data *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 *) desc);

	/* The field len is now set, we can generate the bit codes */
	gen_codes((ct_data *) 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.)
 */
static void scan_tree(ct_data *tree, int max_code)
{
	int n;						/* iterates over all tree elements */
	int prevlen = -1;			/* last emitted length */
	int curlen;					/* length of current code */
	int nextlen = tree[0].Len;	/* length of next code */
	int count = 0;				/* repeat count of the current code */
	int max_count = 7;			/* max repeat coun