lzhdecoder2.cpp

一个解压程序,只要设定了解压路径和解压文件的种类,就可以随意解压

	{
		fillbuf(8);
		mask = 1 << (16-1);
		do
		{
			if( bitbuf&mask )	j = right[j];
			else				j = left[j];
			mask >>= 1;
		}while( j>=np );
		fillbuf(pt_len[j] - 8);
	}
	if( j!=0 )
		j = (1<<(j-1)) + getbits(j-1);
	return j;
}

/**************** LArc ************************/

WORD CLzhDecoder2::decode_c_lzs()
{
	if( getbits(1) )
		return getbits(8);
	else
	{
		matchpos = getbits(11);
		return getbits(4) + 0x100;
	}
}

WORD CLzhDecoder2::decode_p_lzs()
{
#define MAGIC0		18
	return (WORD)((loc-matchpos-MAGIC0)&0x7ff);
}

WORD CLzhDecoder2::decode_c_lz5()
{
	int c;

	if( flagcnt==0 )
	{
		flagcnt = 8;
		flag = getc(in);
	}
	flagcnt--;
	c = getc(in);
	if( (flag&1)==0 )
	{
		matchpos = c;
		c = getc(in);
		matchpos += (c&0xf0)<<4;
		c &= 0x0f;
		c += 0x100;
	}
	flag >>= 1;
	return (WORD)c;
}

WORD CLzhDecoder2::decode_p_lz5()
{
#define MAGIC5		19
	return (WORD)(loc-matchpos-MAGIC5)&0xfff;
}

/******************** lh1-3 *************************************/
/*lh1
	{decode_c_dyn, decode_p_st0, decode_start_fix},
lh2
	{decode_c_dyn, decode_p_dyn, decode_start_dyn},
lh3
	{decode_c_st0, decode_p_st0, decode_start_st0},*/

#define N1 286
#define N2 (2*N1-1)
#define NP			(8*1024/64)
#define NP2			(NP*2-1)
static const int fixed[2][16] = {
	{3, 0x01, 0x04, 0x0c, 0x18, 0x30, 0},	/* old compatible */
	{2, 0x01, 0x01, 0x03, 0x06, 0x0D, 0x1F, 0x4E, 0}	/* 8K buf */
};

void CLzhDecoder2::ready_made(int method)
{
	int             i, j;
	unsigned int    code, weight;
	const int            *tbl;

	tbl = fixed[method];
	j = *tbl++;
	weight = 1 << (16 - j);
	code = 0;
	for( i=0; i<np; i++ )
	{
		while( *tbl==i )
		{
			j++;
			tbl++;
			weight >>= 1;
		}
		pt_len[i] = j;
		pt_code[i] = code;
		code += weight;
	}
}

void CLzhDecoder2::read_tree_c()
{
	int i=0;
	while( i<N1 )
	{
		if( getbits(1) )
			c_len[i] = getbits(4) + 1;
		else
			c_len[i] = 0;
		if( ++i==3 && c_len[0]==1 && c_len[1]==1 && c_len[2]==1 )
		{
			int c = getbits(CBIT);
			for( i=0; i<N1; i++ )	c_len[i] = 0;
			for( i=0; i<4096; i++ )	c_table[i] = c;
			return;
		}
	}
	make_table( N1,c_len,12,c_table );
}

void CLzhDecoder2::read_tree_p()
{
	int i=0;
	while( i<NP )
	{
		pt_len[i] = (BYTE)getbits(4);
		if( ++i==3 && pt_len[0]==1 && pt_len[1]==1 && pt_len[2]==1 )
		{
			int c = getbits(9);
			for( i=0; i<NP; i++ )	c_len[i] = 0;
			for( i=0; i<256; i++ )	c_table[i] = c;
			return;
		}
	}
}

WORD CLzhDecoder2::decode_c_st0()
{
	static unsigned short blocksize = 0;

	if( blocksize==0 )
	{
		blocksize = getbits(16);
		read_tree_c();
		if( getbits(1) )
			read_tree_p();
		else
			ready_made(1);
		make_table( NP,pt_len,8,pt_table );
	}
	blocksize--;
	int j = c_table[bitbuf >> 4];
	if( j<N1 )
		fillbuf(c_len[j]);
	else
	{
		fillbuf(12);
		int i = bitbuf;
		do
		{
			if( (short)i<0 )j = right[j];
			else			j = left[j];
			i <<= 1;
		}while( j>=N1 );
		fillbuf( c_len[j]-12 );
	}
	if( j==N1-1 )
		j += getbits(8);
	return j;
}

WORD CLzhDecoder2::decode_p_st0()
{
	int j = pt_table[bitbuf >> 8];
	if( j<np )
		fillbuf(pt_len[j]);
	else
	{
		fillbuf(8);
		int i = bitbuf;
		do
		{
			if( (short)i<0 )j = right[j];
			else			j = left[j];
			i <<= 1;
		}while( j>=np );
		fillbuf( pt_len[j]-8 );
	}
	return (j<<6)+getbits(6);
}

///////////////

void CLzhDecoder2::reconst(int start,int end)
{
	int             i, j, k, l, b;
	unsigned int    f, g;

	for (i = j = start; i < end; i++) {
		if ((k = child[i]) < 0) {
			freq[j] = (freq[i] + 1) / 2;
			child[j] = k;
			j++;
		}
		if (edge[b = block[i]] == i) {
			stock[--avail] = b;
		}
	}
	j--;
	i = end - 1;
	l = end - 2;
	while (i >= start) {
		while (i >= l) {
			freq[i] = freq[j];
			child[i] = child[j];
			i--, j--;
		}
		f = freq[l] + freq[l + 1];
		for (k = start; f < freq[k]; k++);
		while (j >= k) {
			freq[i] = freq[j];
			child[i] = child[j];
			i--, j--;
		}
		freq[i] = f;
		child[i] = l + 1;
		i--;
		l -= 2;
	}
	f = 0;
	for (i = start; i < end; i++) {
		if ((j = child[i]) < 0)
			s_node[~j] = i;
		else
			parent[j] = parent[j - 1] = i;
		if ((g = freq[i]) == f) {
			block[i] = b;
		}
		else {
			edge[b = block[i] = stock[avail++]] = i;
			f = g;
		}
	}
}

int CLzhDecoder2::swap_inc(int p)
{
	int             b, q, r, s;

	b = block[p];
	if ((q = edge[b]) != p) {	/* swap for leader */
		r = child[p];
		s = child[q];
		child[p] = s;
		child[q] = r;
		if (r >= 0)
			parent[r] = parent[r - 1] = q;
		else
			s_node[~r] = q;
		if (s >= 0)
			parent[s] = parent[s - 1] = p;
		else
			s_node[~s] = p;
		p = q;
		goto Adjust;
	}
	else if (b == block[p + 1]) {
Adjust:
		edge[b]++;
		if (++freq[p] == freq[p - 1]) {
			block[p] = block[p - 1];
		}
		else {
			edge[block[p] = stock[avail++]] = p;	/* create block */
		}
	}
	else if (++freq[p] == freq[p - 1]) {
		stock[--avail] = b;	/* delete block */
		block[p] = block[p - 1];
	}
	return parent[p];
}

WORD CLzhDecoder2::decode_c_dyn()
{
	int c = child[ROOT_C];
	short buf = bitbuf,cnt = 0;
	do
	{
		c = child[c - (buf < 0)];
		buf <<= 1;
		if( ++cnt==16 )
		{
			fillbuf(16);
			buf = bitbuf;
			cnt = 0;
		}
	}while( c>0 );
	fillbuf((BYTE)cnt);
	c = ~c;
	update_c(c);
	if( c==n1 )
		c+=getbits(8);
	return c;
}

WORD CLzhDecoder2::decode_p_dyn()
{
	while (count > nextcount)
	{
		make_new_node(nextcount / 64);
		if( (int)(nextcount+=64)>=nn )
			nextcount = 0xffffffff;
	}
	int c = child[ROOT_P];
	short buf = bitbuf,cnt = 0;
	while( c>0 )
	{
		c = child[c - (buf < 0)];
		buf <<= 1;
		if (++cnt == 16)
		{
			fillbuf(16);
			buf = bitbuf;
			cnt = 0;
		}
	}
	fillbuf((BYTE)cnt);
	c = (~c) - N_CHAR;
	update_p(c);

	return (c << 6) + getbits(6);
}

void CLzhDecoder2::update_c(int p)
{
	if (freq[ROOT_C] == 0x8000)
		reconst(0, n_max * 2 - 1);
	freq[ROOT_C]++;
	int q = s_node[p];
	do{q = swap_inc(q);} while (q != ROOT_C);
}

void CLzhDecoder2::update_p(int p)
{
	if (total_p == 0x8000)
	{
		reconst(ROOT_P, most_p + 1);
		total_p = freq[ROOT_P];
		freq[ROOT_P] = 0xffff;
	}
	int q = s_node[p + N_CHAR];
	while( q!=ROOT_P )
		q = swap_inc(q);
	total_p++;
}

void CLzhDecoder2::make_new_node(int p)
{
	int r = most_p + 1;
	int q = r + 1;
	s_node[~(child[r] = child[most_p])] = r;
	child[q] = ~(p + N_CHAR);
	child[most_p] = q;
	freq[r] = freq[most_p];
	freq[q] = 0;
	block[r] = block[most_p];
	if (most_p == ROOT_P)
	{
		freq[ROOT_P] = 0xffff;
		edge[block[ROOT_P]]++;
	}
	parent[r] = parent[q] = most_p;
	edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
	update_p(p);
}


/******************** bit扨埵偺read&write ************************/

void CLzhDecoder2::init_getbits()
{
	bitbuf = 0;
	subbitbuf = 0;
	bitcount = 0;
	fillbuf(16);
}

void CLzhDecoder2::fillbuf(BYTE n)
{
	while( n>bitcount )
	{
		n -= bitcount;
		bitbuf = (bitbuf<<bitcount) + (subbitbuf>>(8-bitcount));
		if( cmpsize!=0 )
		{
			cmpsize--;
			subbitbuf = (BYTE)getc(in);
		}
		else
			subbitbuf = 0;
		bitcount = 8;
	}
	bitcount -= n;
	bitbuf = (bitbuf<<n) + (subbitbuf>>(8-n));
	subbitbuf <<= n;
}

WORD CLzhDecoder2::getbits(BYTE n)
{
	WORD x = bitbuf>>(16-n);
	fillbuf(n);
	return x;
}