litezip.c

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

		state->ts.dyn_ltree[state->ts.length_code[lc] + LITERALS + 1].fc.freq++;
		state->ts.dyn_dtree[d_code(dist)].fc.freq++;

		state->ts.d_buf[state->ts.last_dist++] = (USH)dist;
		state->ts.flags |= state->ts.flag_bit;
	}
	state->ts.flag_bit <<= 1;

	// Store the flags if they fill a byte
	if ((state->ts.last_lit & 7) == 0)
	{
		state->ts.flag_buf[state->ts.last_flags++] = state->ts.flags;
		state->ts.flags = 0, state->ts.flag_bit = 1;
	}

	// Try to guess if it is profitable to stop the current block here 
	if (state->level > 2 && (state->ts.last_lit & 0xfff) == 0)
	{
		DWORD	dcode;
		ULG		out_length;
		ULG		in_length;

		// Compute an upper bound for the compressed length
		out_length = (ULG)state->ts.last_lit*8L;
		in_length = (ULG)state->ds.strstart - state->ds.block_start;
		dcode = D_CODES;
		while (dcode--) out_length += (ULG)state->ts.dyn_dtree[dcode].fc.freq * (5L + Extra_dbits[dcode]);
		out_length >>= 3;

#ifndef NDEBUG
		Trace("\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", state->ts.last_lit, state->ts.last_dist, in_length, out_length, 100L - out_length*100L/in_length);
#endif
		// Should we stop the block here?
		if (state->ts.last_dist < state->ts.last_lit/2 && out_length < in_length/2) return(1);
	}

	// NOTE: 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
	return(state->ts.last_lit == LIT_BUFSIZE-1 || state->ts.last_dist == DIST_BUFSIZE);
}





/********************* compress_block() ********************
 * Sends the block data compressed using the given Huffman
 * trees.
 */

static void compress_block(register TSTATE *state, CT_DATA *ltree, CT_DATA *dtree)
{
	unsigned	dist;		// distance of matched string
	int			lc;			// match length or unmatched char (if dist == 0)
	DWORD		lx;			// running index in l_buf
	DWORD		dx;			// running index in d_buf
	DWORD		fx;			// running index in flag_buf
	UCH			flag;		// current flags
	unsigned	code;		// the code to send
	int			extra;		// number of extra bits to send

	lx = dx = fx = flag = 0;

	if (state->ts.last_lit)
	{
		do
		{
			if ((lx & 7) == 0) flag = state->ts.flag_buf[fx++];
			lc = state->ts.l_buf[lx++];

			if ((flag & 1) == 0)
			{
				// send a literal byte
				if (!send_code(state, lc, ltree)) goto out;
			}			// bug in VC4.0 if these {} are removed!!!
			else
			{
				// Here, lc is the match length - MIN_MATCH

				code = state->ts.length_code[lc];

				// send the length code
				if (!send_code(state, code + LITERALS + 1, ltree))
out:				return;

				// send the extra length bits
				extra = Extra_lbits[code];
				if (extra)
				{
					lc -= state->ts.base_length[code];
					if (!send_bits(state,lc, extra)) goto out;
				}

				dist = state->ts.d_buf[dx++];
				// Here, dist is the match distance - 1

				// send the distance code
				code = d_code(dist);
#ifndef NDEBUG
				Assert(state, code < D_CODES, "bad d_code");
#endif
				if (!send_code(state, code, dtree)) goto out;

				// send the extra distance bits
				extra = Extra_dbits[code];
				if (extra)
				{
					dist -= state->ts.base_dist[code];
					if (!send_bits(state, dist, extra)) goto out;
				}
			} // literal or match pair ?

			flag >>= 1;

		} while (lx < state->ts.last_lit);
	}

	send_code(state, END_BLOCK, ltree);
}






/*********************** send_bits() **********************
 * Sends a value on a given number of bits.
 *
 * IN assertion: length <= 16 and value fits in length bits.
 */

static BOOL send_bits(register TSTATE *state, int value, int length)
{
#ifndef NDEBUG
	Assert(state, length > 0 && length <= 15, "invalid length");
	state->bs.bits_sent += (ULG)length;
#endif
	// If not enough room in bi_buf, use (bi_valid) bits from bi_buf and
	// (ZIP_BUF_SIZE - bi_valid) bits from value to flush the filled bi_buf,
	// then fill in the rest of (value), leaving (length - (ZIP_BUF_SIZE-bi_valid))
	// unused bits in bi_buf.
	state->bs.bi_buf |= (value << state->bs.bi_valid);
	state->bs.bi_valid += length;
	if (state->bs.bi_valid > ZIP_BUF_SIZE)
	{
		// If we've filled the output buffer, flush it
		if (state->bs.out_offset + 1 >= state->bs.out_size)
		{
			writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
			if (state->tzip->lasterr) return(0);
			state->bs.out_offset = 0;
		}

		// Store the short in Intel-order
		state->bs.out_buf[state->bs.out_offset++] = (char)((state->bs.bi_buf) & 0xff);
		state->bs.out_buf[state->bs.out_offset++] = (char)((USH)(state->bs.bi_buf) >> 8);

		state->bs.bi_valid -= ZIP_BUF_SIZE;
		state->bs.bi_buf = (unsigned)value >> (length - state->bs.bi_valid);
	}

	return(1);
}





/********************** bi_reverse() *********************
 * Reverses the first "len" bits of a code.
 *
 * code =	The number whose bits are to be shifted.
 * len =	The number of bits to reverse (1 to 15).
 */

static unsigned bi_reverse(register unsigned code, register unsigned char len)
{
	register unsigned res;

	res = 0;
	goto rev;
	do
	{
		res <<= 1;
		code >>= 1;
rev:	res |= code & 1;
	} while (--len);
	return(res);
}





/*********************** bi_windup() ********************
 * Writes out any remaining bits in an incomplete byte.
 */

static void bi_windup(register TSTATE *state)
{
	if (state->bs.bi_valid > 8)
	{
		// If we've filled the output buffer, flush it
		if (state->bs.out_offset + 1 >= state->bs.out_size)
		{
			writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
			state->bs.out_offset = 0;
		}

		// Store the short in Intel-order
		state->bs.out_buf[state->bs.out_offset++] = (char)((state->bs.bi_buf) & 0xff);
		state->bs.out_buf[state->bs.out_offset++] = (char)((USH)(state->bs.bi_buf) >> 8);
	}
	else if (state->bs.bi_valid > 0)
	{
		// If we've filled the output buffer, flush it
		if (state->bs.out_offset >= state->bs.out_size)
		{
			writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
			state->bs.out_offset = 0;
		}

		// Store the byte
		state->bs.out_buf[state->bs.out_offset++] = (char)state->bs.bi_buf;
	}

	// Flush the buffer to the ZIP archive
	writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
	state->bs.bi_buf = state->bs.out_offset = state->bs.bi_valid = 0;
#ifndef NDEBUG
	state->bs.bits_sent = (state->bs.bits_sent+7) & ~7;
#endif
}





/************************ copy_block() ********************
 * Copies a stored block to the zip file, storing first the
 * length and its one's complement if requested.
 */

static void copy_block(register TSTATE *state, char *block, DWORD len, DWORD header)
{
	// Align on a byte boundary by writing out any previous, uncompleted bytes
	bi_windup(state);

	// If a header, write the length and one's complement
	if (header)
	{
		// If we don't have room for 2 shorts, flush the output buffer
		if (state->bs.out_offset + 3 >= state->bs.out_size)
		{
			writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
			state->bs.out_offset = 0;
		}

		// Store the short in Intel-order
		state->bs.out_buf[state->bs.out_offset++] = (char)((len) & 0xff);
		state->bs.out_buf[state->bs.out_offset++] = (char)((USH)(len) >> 8);

		// Store one's complement
		state->bs.out_buf[state->bs.out_offset++] = (char)((~len) & 0xff);
		state->bs.out_buf[state->bs.out_offset++] = (char)((USH)(~len) >> 8);

		// Flush the 2 shorts now (because we're going to flush the block
		// which is in a different memory buffer)
		writeDestination(state->tzip, state->bs.out_buf, state->bs.out_offset);
		state->bs.out_offset = 0;


#ifndef NDEBUG
		state->bs.bits_sent += (2*16);
#endif
	}

	// Write out the block
	writeDestination(state->tzip, block, len);

#ifndef NDEBUG
	state->bs.bits_sent += (ULG)len<<3;
#endif
}






/* ===========================================================================
 * Update a hash value with the given input byte
 * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
 *    input characters, so that a running hash key can be computed from the
 *    previous key instead of complete recalculation each time.
 */
#define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)





/* ===========================================================================
 * Insert string s in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
 *    input characters and the first MIN_MATCH bytes of s are valid
 *    (except for the last MIN_MATCH-1 bytes of the input file).
 */
#define INSERT_STRING(s, match_head) \
   (UPDATE_HASH(state->ds.ins_h, state->ds.window[(s) + (MIN_MATCH-1)]), \
    state->ds.prev[(s) & WMASK] = match_head = state->ds.head[state->ds.ins_h], \
    state->ds.head[state->ds.ins_h] = (s))





/************************ lm_init() ***********************
 * Initializes the "longest match" routines in preparation of
 * writing a new zip file.
 *
 * NOTE: state->ds.window_size is > 0 if the source file in
 * its entirety is already read into the state->ds.window[]
 * array, 0 otherwise. In the first case, window_size is
 * sufficient to contain the whole input file plus MIN_LOOKAHEAD
 * bytes (to avoid referencing memory beyond the end
 * of window[] when looking for matches towards the end).
 */

static void lm_init(register TSTATE *state, DWORD pack_level, USH *flags)
{
	register unsigned j;

	// Do not slide the window if the whole input is already in memory (window_size > 0)
//	state->ds.sliding = 0;
//	if (!state->ds.window_size)
//	{
		state->ds.sliding = 1;
		state->ds.window_size = (ULG)(2L * WSIZE);
//	}

	// Initialize the hash table (avoiding 64K overflow for 16 bit systems).
	// prev[] will be initialized on the fly
	state->ds.head[HASH_SIZE - 1] = 0;
	ZeroMemory(state->ds.head, (HASH_SIZE - 1) * sizeof(*state->ds.head));

	// Set the default configuration parameters:
	state->ds.max_lazy_match = ConfigurationTable[pack_level].max_lazy;
	state->ds.good_match = ConfigurationTable[pack_level].good_length;
	state->ds.nice_match = ConfigurationTable[pack_level].nice_length;
	state->ds.max_chain_length = ConfigurationTable[pack_level].max_chain;
	if (pack_level <= 2) *flags |= FAST;
	else if (pack_level >= 8) *flags |= SLOW;

	// ??? reduce max_chain_length for binary files


	// Fill the state->ds.window[] buffer with source bytes
	if (!(state->ds.lookahead = readFromSource(state->tzip, state->ds.window, WSIZE * 2))) return;

	// At start of input buffer, and haven't reached the end of the source yet
	state->ds.strstart = state->ds.block_start = state->ds.eofile = 0;

	// Make sure that we always have enough lookahead
	if (state->ds.lookahead < MIN_LOOKAHEAD) fill_window(state);

	// If lookahead < MIN_MATCH, ins_h is garbage, but this is
	// not important since only literal bytes will be emitted
	state->ds.ins_h = 0;
	for (j=0; j < MIN_MATCH - 1; j++) UPDATE_HASH(state->ds.ins_h, state->ds.window[j]);
}





/********************** longest_match() *******************
 * Sets match_start to the longest match starting at the
 * given string and return its length. Any match shorter or
 * equal to prev_length ia discarded, in which case the
 * result is equal to prev_length and match_start is
 * garbage.
 *
 * IN assertions: cur_match is the head of the hash chain for the current
 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 */

static int longest_match(register TSTATE *state, unsigned cur_match)
{
	unsigned chain_length = state->ds.max_chain_length;   // max hash chain length
	register UCH *scan = state->ds.window + state->ds.strstart; // current string
	register UCH *match;                    // matched string
	register int len;