unzip.cpp

看到有兄弟提出的半透明算法

// UnZip.cpp: implementation of the CUnZip class.
//
//////////////////////////////////////////////////////////////////////

#include "UnZip.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CUnZip::CUnZip()
{
	textsize = 0;
	printcount = 0;

	low = 0;
	high = Q4;
	value = 0;
	
	m_pInBuffer = NULL;
	m_nInLength = 0;
	m_nInCur = 0;

	m_pOutBuffer = NULL;
	m_nOutLength = 0;
	m_nOutCur = 0;

	buffer_putbit = 0;
	mask_putbit = 128;

	buffer_getbit = 0;
	mask_getbit = 0;
}

CUnZip::~CUnZip()
{
	Release();
}

void CUnZip::UnCompress(byte *pInBuffer,int nInLength,byte *&pOutBuffer ,int &nOutLength)
{
	m_pInBuffer = pInBuffer;
	m_nInLength = nInLength;
	m_nInCur = 0;

	Decode();
	m_pOutBuffer[m_nOutCur] = 0;
	pOutBuffer = m_pOutBuffer;//m_OutBuffer[0];
	nOutLength = m_nOutCur;//m_OutBuffer.size();
//	m_OutBuffer.push_back(0);
}

void CUnZip::Decode(void)
{
	int  i, j, k, r, c;
	unsigned long int  count;

	if(m_nInLength < sizeof textsize)
		return;
	MEMCPY(&textsize,m_pInBuffer + m_nInCur,sizeof textsize);

	//m_OutBuffer.reserve(textsize);
	m_nOutLength = textsize;
	//m_nOutCur = 0;

	m_nInCur += sizeof textsize;

	m_pOutBuffer = (byte*)MALLOC(textsize);
	MEMSET(m_pOutBuffer, 0, textsize);

	StartDecode();
	StartModel();
	
	for (i = 0; i < N - F; i++) text_buf[i] = ' ';
	r = N - F;
	for (count = 0; count < textsize; ) 
	{
		c = DecodeChar();
		if (c < 256) 
		{
			m_pOutBuffer[m_nOutCur++] = c;
//			m_OutBuffer.push_back(c);
//			m_nOutCur++;

			text_buf[r++] = c;
			r &= (N - 1);
			count++;
		}
		else
		{
			i = (r - DecodePosition() - 1) & (N - 1);
			j = c - 255 + THRESHOLD;
			for (k = 0; k < j; k++) 
			{
				c = text_buf[(i + k) & (N - 1)];
				m_pOutBuffer[m_nOutCur++] = c;
//				m_OutBuffer.push_back(c);
				text_buf[r++] = c;
				r &= (N - 1);
				count++;
			}
		}
		if (count > printcount) 
			printcount += 1024;
	}
}

int CUnZip::DecodeChar(void)
{
	int	 sym, ch;
	unsigned long int  range;
	
	range = high - low;
	sym = BinarySearchSym((unsigned int)(((value - low + 1) * sym_cum[0] - 1) / range));
	high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
	low += (range * sym_cum[sym]) / sym_cum[0];
	for ( ; ; )
	{
		if (low >= Q2)
		{
			value -= Q2;
			low -= Q2;
			high -= Q2;
		}
		else if (low >= Q1 && high <= Q3)
		{
			value -= Q1;
			low -= Q1;
			high -= Q1;
		}
		else if (high > Q2)
			break;
		low += low;
		high += high;
		value = 2 * value + GetBit();
	}
	ch = sym_to_char[sym];
	UpdateModel(sym);
	return ch;
}

int CUnZip::DecodePosition(void)
{
	int position;
	unsigned long int  range;
	
	range = high - low;
	position = BinarySearchPos((unsigned int)(((value - low + 1) * position_cum[0] - 1) / range));
	high = low + (range * position_cum[position    ]) / position_cum[0];
	low +=       (range * position_cum[position + 1]) / position_cum[0];
	for ( ; ; ) {
		if (low >= Q2) {
			value -= Q2;  low -= Q2;  high -= Q2;
		} else if (low >= Q1 && high <= Q3) {
			value -= Q1;  low -= Q1;  high -= Q1;
		} else if (high > Q2) break;
		low += low;  high += high;
		value = 2 * value + GetBit();
	}
	return position;
}

int CUnZip::BinarySearchSym(unsigned int x)
{
	int i, j, k;
	
	i = 1;  j = N_CHAR;
	while (i < j) 
	{
		k = (i + j) / 2;
		if (sym_cum[k] > x) i = k + 1;  else j = k;
	}
	return i;
}

int CUnZip::BinarySearchPos(unsigned int x)
{
	int i, j, k;
	
	i = 1;  j = N;
	while (i < j)
	{
		k = (i + j) / 2;
		if (position_cum[k] > x) i = k + 1;  else j = k;
	}
	return i - 1;
}

int CUnZip::GetBit(void)  /* Get one bit (0 or 1) */
{	
	if ((mask_getbit >>= 1) == 0) 
	{
		buffer_getbit = m_pInBuffer[m_nInCur++];
		mask_getbit = 128;
	}
	return ((buffer_getbit & mask_getbit) != 0);
}


void CUnZip::StartDecode(void)
{
	int i;

	for (i = 0; i < M + 2; i++)
		value = 2 * value + GetBit();
}

void CUnZip::StartModel(void)  /* Initialize model */
{
	int ch, sym, i;
	
	sym_cum[N_CHAR] = 0;
	for (sym = N_CHAR; sym >= 1; sym--) 
	{
		ch = sym - 1;
		char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
		sym_freq[sym] = 1;
		sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
	}
	sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
	position_cum[N] = 0;
	for (i = N; i >= 1; i--)
		position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
			/* empirical distribution function (quite tentative) */
			/* Please devise a better mechanism! */
}

void CUnZip::UpdateModel(int sym)
{
	int i, c, ch_i, ch_sym;
	
	if (sym_cum[0] >= MAX_CUM) 
	{
		c = 0;
		for (i = N_CHAR; i > 0; i--) 
		{
			sym_cum[i] = c;
			c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
		}
		sym_cum[0] = c;
	}
	for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
	if (i < sym) 
	{
		ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
		sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
		char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
	}
	sym_freq[i]++;
	while (--i >= 0) sym_cum[i]++;
}

void CUnZip::Release()
{
	if(m_pOutBuffer)
	{
		m_nOutCur = 0;
		textsize = 0;
		printcount = 0;
		
		low = 0;
		high = Q4;
		value = 0;

		m_pInBuffer = NULL;
		m_nInLength = 0;
		m_nInCur = 0;
		
		FREE(m_pOutBuffer);
		m_pOutBuffer = NULL;
		m_nOutLength = 0;

		buffer_putbit = 0;
		mask_putbit = 128;
		
		buffer_getbit = 0;
		mask_getbit = 0;
	}
}