litezip.c

来自「是一个C语言的压缩和解压缩的DLL源程序.」· C语言 代码 · 共 1,988 行 · 第 1/5 页

{
	int				n;			// iterates over all tree elements
	int				prevlen;	// last emitted length
	int				curlen;		// length of current code
	int				nextlen;	// length of next code
	register BYTE	count;		// repeat count of the current code
	register BYTE	max_count;	// max repeat count
	register BYTE	min_count;	// min repeat count

	count = 0;
	nextlen = tree[0].dl.len;
	prevlen = -1;

	max_count = 7;
	min_count = 4;
	if (!nextlen)
	{
		max_count = 138;
		min_count = 3;
	}

	// Set to -1 as a sort of "guard marker" that shouldn't be crossed
	tree[max_code + 1].dl.len = (USH)-1;

	for (n = 0; n <= max_code; n++)
	{
		curlen = nextlen;
		nextlen = tree[n+1].dl.len;
		if (++count < max_count && curlen == nextlen) continue;
		if (count < min_count)
			state->ts.bl_tree[curlen].fc.freq = (USH)(state->ts.bl_tree[curlen].fc.freq + count);
        else if (curlen)
		{
			if (curlen != prevlen) ++state->ts.bl_tree[curlen].fc.freq;
			++state->ts.bl_tree[REP_3_6].fc.freq;
		}
		else if (count <= 10)
			++state->ts.bl_tree[REPZ_3_10].fc.freq;
		else
			++state->ts.bl_tree[REPZ_11_138].fc.freq;

		count = 0;
		prevlen = curlen;
		if (!nextlen)
		{
			max_count = 138;
			min_count = 3;
		}
		else if (curlen == nextlen)
		{
			max_count = 6;
			min_count = 3;
		}
		else
		{
			max_count = 7;
			min_count = 4;
		}
	}
}





/*********************** send_tree() ************************
 * Sends a literal or distance tree in compressed form, using
 * the codes in bl_tree().
 */

static BOOL send_tree(register TSTATE *state, CT_DATA *tree, int max_code)
{
	int				n;			// iterates over all tree elements
	int				prevlen;	// last emitted length
	int				curlen;		// length of current code
	int				nextlen;	// length of next code
	register BYTE	count;		// repeat count of the current code
	register BYTE	max_count;	// max repeat count
	register BYTE	min_count;	// min repeat count

	count = 0;
	nextlen = tree[0].dl.len;
	prevlen = -1;

	max_count = 7;
	min_count = 4;
	if (!nextlen)
	{
		max_count = 138;
		min_count = 3;
	}

	for (n = 0; n <= max_code; n++)
	{
		curlen = nextlen;
		nextlen = tree[n+1].dl.len;
		if (++count < max_count && curlen == nextlen) continue;

		if (count < min_count)
		{
			do
			{
				if (!send_code(state, curlen, state->ts.bl_tree)) goto out;
			} while (--count);
		}
		else if (curlen)
		{
			if (curlen != prevlen)
			{
				if (!send_code(state, curlen, state->ts.bl_tree)) goto out;
				--count;
			}
#ifndef NDEBUG
			Assert(state, count >= 3 && count <= 6, " 3_6?");
#endif
			if (!send_code(state, REP_3_6, state->ts.bl_tree) || ! send_bits(state, count - 3, 2)) goto out;

		}
		else if (count <= 10)
		{
			if (!send_code(state, REPZ_3_10, state->ts.bl_tree) || !send_bits(state, count - 3, 3)) goto out;
		}
		else
		{
			if (!send_code(state, REPZ_11_138, state->ts.bl_tree) || !send_bits(state, count - 11, 7))
out:			return(0);
		}

		count = 0;
		prevlen = curlen;
		if (!nextlen)
		{
			max_count = 138;
			min_count = 3;
		}
		else if (curlen == nextlen)
		{
			max_count = 6;
			min_count = 3;
		}
		else
		{
			max_count = 7;
			min_count = 4;
		}
	}

	return(1);
}





/************************* build_bl_tree() *******************
 * Constructs the Huffman tree for the bit lengths and returns
 * the index in BL_order[] of the last bit length code to send.
 */

static int build_bl_tree(register TSTATE *state)
{
	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(state, state->ts.dyn_ltree, state->ts.l_desc.max_code);
	scan_tree(state, state->ts.dyn_dtree, state->ts.d_desc.max_code);

	// Build the bit length tree:
	build_tree(state,(TREE_DESC *)(&state->ts.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 (state->ts.bl_tree[BL_order[max_blindex]].dl.len != 0) break;
	}

	// Update opt_len to include the bit length tree and counts
	state->ts.opt_len += 3*(max_blindex+1) + 5+5+4;
#ifndef NDEBUG
	Trace("\ndyn trees: dyn %ld, stat %ld", state->ts.opt_len, state->ts.static_len);
#endif
	return(max_blindex);
}





/************************* send_all_trees() *******************
 * Sends the header for a block using dynamic Huffman trees:
 * the counts, the lengths of the bit length codes, the literal
 * tree and the distance tree.
 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
 */
static BOOL send_all_trees(register TSTATE *state, int lcodes, int dcodes, int blcodes)
{
	int		rank;	// index into BL_order[]

#ifndef NDEBUG
	Assert(state,lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
	Assert(state,lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, "too many codes");
	Trace("\nbl counts: ");
#endif

	if (send_bits(state, lcodes - 257, 5) &&	// not +255 as stated in appnote.txt 1.93a or -256 in 2.04c
		send_bits(state, dcodes - 1, 5) &&
		send_bits(state, blcodes - 4,  4))		// not -3 as stated in appnote.txt
	{
		for (rank = 0; rank < blcodes; rank++)
		{
#ifndef NDEBUG
			Trace("\nbl code %2d ", BL_order[rank]);
#endif
			if (!send_bits(state,state->ts.bl_tree[BL_order[rank]].dl.len, 3)) goto out;
		}
#ifndef NDEBUG
		Trace("\nbl tree: sent %ld", state->bs.bits_sent);
#endif

		// Send the literal tree
		if (send_tree(state, (CT_DATA *)state->ts.dyn_ltree, lcodes - 1))
		{
#ifndef NDEBUG
			Trace("\nlit tree: sent %ld", state->bs.bits_sent);
#endif
			// Send the distance tree
			if (send_tree(state, state->ts.dyn_dtree, dcodes - 1))
			{
#ifndef NDEBUG
				Trace("\ndist tree: sent %ld", state->bs.bits_sent);
#endif
				return(1);
			}
		}
	}
out:
	return(0);
}





/********************* set_file_type() ********************
 * Sets the file type to ASCII or BINARY, using a crude 
 * approximation: binary if more than 20% of the bytes are
 * <= 6 or >= 128, ascii otherwise.
 *
 * IN assertion: the fields freq of dyn_ltree are set and
 * the total of all frequencies does not exceed 64K (to fit
 * in an int on 16 bit machines).
 */

static void set_file_type(register TSTATE *state)
{
	unsigned	n;
	unsigned	ascii_freq;
	unsigned	bin_freq;

	n = ascii_freq = bin_freq = 0;
	
	while (n < 7)        bin_freq += state->ts.dyn_ltree[n++].fc.freq;
	while (n < 128)    ascii_freq += state->ts.dyn_ltree[n++].fc.freq;
	while (n < LITERALS) bin_freq += state->ts.dyn_ltree[n++].fc.freq;
	*state->ts.file_type = (USH)(bin_freq > (ascii_freq >> 2) ? BINARY : ASCII);
}





/************************* flush_block() ********************
 * Determines the best encoding for the current block: dynamic
 * trees, static trees or store, and outputs the encoded block
 * to the zip file.
 *
 * RETURNS: The total compressed length (in bytes) for the
 * file so far.
 */

static void flush_block(register TSTATE *state, char *buf, ULG stored_len, DWORD eof)
{
	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

	state->ts.flag_buf[state->ts.last_flags] = state->ts.flags; // Save the flags for the last 8 items 

	// Check if the file is ascii or binary
	if (*state->ts.file_type == (USH)UNKNOWN) set_file_type(state);

	// Construct the literal and distance trees
	build_tree(state, (TREE_DESC *)(&state->ts.l_desc));
#ifndef NDEBUG
	Trace("\nlit data: dyn %ld, stat %ld", state->ts.opt_len, state->ts.static_len);
#endif

	build_tree(state,(TREE_DESC *)(&state->ts.d_desc));
#ifndef NDEBUG
	Trace("\ndist data: dyn %ld, stat %ld", state->ts.opt_len, state->ts.static_len);
#endif
	// 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(state);

	// Determine the best encoding. Compute first the block length in bytes
	opt_lenb = (state->ts.opt_len+3+7)>>3;
	static_lenb = (state->ts.static_len+3+7)>>3;

#ifndef NDEBUG
	state->ts.input_len += stored_len;
	Trace("\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", opt_lenb, state->ts.opt_len, static_lenb, state->ts.static_len, stored_len, state->ts.last_lit, state->ts.last_dist);
#endif

	if (static_lenb <= opt_lenb) opt_lenb = static_lenb;

	if (stored_len + 4 <= opt_lenb && buf)
	{
		// two words for the lengths
		// 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 block type
		send_bits(state, (STORED_BLOCK << 1) + eof, 3);
		state->ts.cmpr_bytelen += ((state->ts.cmpr_len_bits + 3 + 7) >> 3) + stored_len + 4;
		state->ts.cmpr_len_bits = 0;
		copy_block(state, buf, (unsigned)stored_len, 1); // with header
	}
	else if (static_lenb == opt_lenb)
	{
		send_bits(state, (STATIC_TREES << 1) + eof, 3);
		compress_block(state,(CT_DATA *)state->ts.static_ltree, (CT_DATA *)state->ts.static_dtree);
		state->ts.cmpr_len_bits += 3 + state->ts.static_len;
		goto upd;
	}
	else
	{
		send_bits(state, (DYN_TREES << 1) + eof, 3);
		send_all_trees(state,state->ts.l_desc.max_code + 1, state->ts.d_desc.max_code + 1, max_blindex + 1);
		compress_block(state, state->ts.dyn_ltree, state->ts.dyn_dtree);
		state->ts.cmpr_len_bits += 3 + state->ts.opt_len;
upd:	state->ts.cmpr_bytelen += state->ts.cmpr_len_bits >> 3;
		state->ts.cmpr_len_bits &= 7;
	}
#ifndef NDEBUG
	Assert(state,((state->ts.cmpr_bytelen << 3) + state->ts.cmpr_len_bits) == state->bs.bits_sent, "bad compressed size");
#endif

	if (!state->tzip->lasterr)
	{
		init_block(state);

		if (eof)
		{
			bi_windup(state);
			state->ts.cmpr_len_bits += 7;	// align on byte boundary
		}
#ifndef NDEBUG
		Trace("\n");
#endif
		// Set compressed size so far
		state->tzip->csize = state->ts.cmpr_bytelen + (state->ts.cmpr_len_bits >> 3);
	}
}




/********************* ct_tally() **********************
 * Saves the match info and tallies the frequency counts.
 * 
 * RETURNS: TRUE if the current block must be flushed.
 */

static unsigned char ct_tally(register TSTATE *state, int dist, int lc)
{
	state->ts.l_buf[state->ts.last_lit++] = (UCH)lc;
	if (!dist)
	{
		// lc is the unmatched char
		state->ts.dyn_ltree[lc].fc.freq++;
	}
	else
	{
		// Here, lc is the match length - MIN_MATCH
		--dist;				// dist = match distance - 1
#ifndef NDEBUG
		Assert(state,(USH)dist < (USH)MAX_DIST && (USH)lc <= (USH)(MAX_MATCH-MIN_MATCH) && (USH)d_code(dist) < (USH)D_CODES,  "ct_tally: bad match");
#endif