///////////////////////////////////////////////////////////////////////////////
// 遠程控制軟件-偷窺者  壓縮庫                                               //
// 日期:2001/10/02                                                           //
// 作者:劉東發(fā)                                                               //
// Email:dongfa@yeah.net                                                     //
// http://dongfa.yeah.net                                                    //
// OICQ:5584173  阿東                                                        //
// 作者聲明:                                                                 //
//     此部分代碼是從網(wǎng)上下載獲得，經(jīng)過本人的改寫， 變得容易使用，希望能給   //
// 大家?guī)矸奖?                                                             //
///////////////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "PeeperZip.h"

///////////////////////////////////////////////////////////////////////////////
//LZ77 Part START--------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////
int CCompress::UpperLog2(int n)
{
	int i = 0;
	if (n > 0)
	{
		int m = 1;
		while(1)
		{
			if (m >= n)
				return i;
			m <<= 1;
			i++;
		}
	}
	else 
		return -1;
}

int CCompress::LowerLog2(int n)
{
	int i = 0;
	if (n > 0)
	{
		int m = 1;
		while(1)
		{
			if (m == n)
				return i;
			if (m > n)
				return i - 1;
			m <<= 1;
			i++;
		}
	}
	else 
		return -1;
}

void CCompress::MovePos(int* piByte, int* piBit, int num)
{
	num += (*piBit);
	(*piByte) += num / 8;
	(*piBit) = num % 8;
}

BYTE CCompress::GetBit(BYTE byte, int pos)
{
	int j = 1;
	j <<= 7 - pos;
	if (byte & j)
		return 1;
	else 
		return 0;
}

void CCompress::SetBit(BYTE* byte, int iBit, BYTE aBit)
{
	if (aBit)
		(*byte) |= (1 << (7 - iBit));
	else
		(*byte) &= ~(1 << (7 - iBit));
}

void CCompress::InvertDWord(DWORD* pDW)
{
	union UDWORD{ DWORD dw; BYTE b[4]; };
	UDWORD* pUDW = (UDWORD*)pDW;
	BYTE b;
	b = pUDW->b[0];	pUDW->b[0] = pUDW->b[3]; pUDW->b[3] = b;
	b = pUDW->b[1];	pUDW->b[1] = pUDW->b[2]; pUDW->b[2] = b;
}

void CCompress::CopyBits(BYTE* memDest, int nDestPos, 
			  BYTE* memSrc, int nSrcPos, int nBits)
{
	int iByteDest = 0, iBitDest;
	int iByteSrc = 0, iBitSrc = nSrcPos;

	int nBitsToFill, nBitsCanFill;

	while (nBits > 0)
	{
		nBitsToFill = min(nBits, iByteDest ? 8 : 8 - nDestPos);
		iBitDest = iByteDest ? 0 : nDestPos;
		nBitsCanFill = min(nBitsToFill, 8 - iBitSrc);
		CopyBitsInAByte(memDest + iByteDest, iBitDest, 
			memSrc + iByteSrc, iBitSrc, nBitsCanFill);		
		if (nBitsToFill > nBitsCanFill)
		{
			iByteSrc++; iBitSrc = 0; iBitDest += nBitsCanFill;
			CopyBitsInAByte(memDest + iByteDest, iBitDest, 
					memSrc + iByteSrc, iBitSrc, 
					nBitsToFill - nBitsCanFill);
			iBitSrc += nBitsToFill - nBitsCanFill;
		}
		else 
		{
			iBitSrc += nBitsCanFill;
			if (iBitSrc >= 8)
			{
				iByteSrc++; iBitSrc = 0;
			}
		}

		nBits -= nBitsToFill;
		iByteDest++;
	}	
}

void CCompress::CopyBitsInAByte(BYTE* memDest, int nDestPos, 
			  BYTE* memSrc, int nSrcPos, int nBits)
{
	BYTE b1, b2;
	b1 = *memSrc;
	b1 <<= nSrcPos; b1 >>= 8 - nBits;
	b1 <<= 8 - nBits - nDestPos;
	*memDest |= b1;
	b2 = 0xff; b2 <<= 8 - nDestPos;
	b1 |= b2;
	b2 = 0xff; b2 >>= nDestPos + nBits;
	b1 |= b2;
	*memDest &= b1;
}

CCompressLZ77::CCompressLZ77()
{	
	SortHeap = new struct STIDXNODE[_MAX_WINDOW_SIZE];
}

CCompressLZ77::~CCompressLZ77()
{
	delete[] SortHeap;
}

void CCompressLZ77::_InitSortTable()
{
	memset(SortTable, 0, sizeof(WORD) * 65536);
	nWndSize = 0;
	HeapPos = 1;
}

void CCompressLZ77::_InsertIndexItem(int off)
{
	WORD q;
	BYTE ch1, ch2;
	ch1 = pWnd[off]; ch2 = pWnd[off + 1];	
	
	if (ch1 != ch2)
	{
		q = HeapPos;
		HeapPos++;
		SortHeap[q].off = off;
		SortHeap[q].next = SortTable[ch1 * 256 + ch2];
		SortTable[ch1 * 256 + ch2] = q;
	}
	else
	{
		q = SortTable[ch1 * 256 + ch2];
		if (q != 0 && off == SortHeap[q].off2 + 1)
		{		
			SortHeap[q].off2 = off;
		}		
		else
		{
			q = HeapPos;
			HeapPos++;
			SortHeap[q].off = off;
			SortHeap[q].off2 = off;
			SortHeap[q].next = SortTable[ch1 * 256 + ch2];
			SortTable[ch1 * 256 + ch2] = q;
		}
	}
}

void CCompressLZ77::_ScrollWindow(int n)
{	
	for (int i = 0; i < n; i++)
	{		
		nWndSize++;		
		if (nWndSize > 1)			
			_InsertIndexItem(nWndSize - 2);
	}
}

int CCompressLZ77::_GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset)
{
	int i = 2;
	int maxsame = min(srclen - nSeekStart, nWndSize - offset);
	while (i < maxsame
			&& src[nSeekStart + i] == pWnd[offset + i])
		i++;
	_ASSERT(nSeekStart + i <= srclen && offset + i <= nWndSize);
	return i;
}

BOOL CCompressLZ77::_SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len)
{	
	int j, m, n;

	if (nSeekStart < srclen - 1)
	{
		BYTE ch1, ch2;
		ch1 = src[nSeekStart]; ch2 = src[nSeekStart + 1];
		WORD p;
		p = SortTable[ch1 * 256 + ch2];
		if (p != 0)
		{
			m = 2; n = SortHeap[p].off;
			while (p != 0)
			{
				j = _GetSameLen(src, srclen, 
					nSeekStart, SortHeap[p].off);
				if ( j > m )
				{ 
					m = j; 
					n = SortHeap[p].off;
				}			
				p = SortHeap[p].next;
			}	
			(*offset) = n; 
			(*len) = m;
			return TRUE;		
		}	
	}
	return FALSE;
}

void CCompressLZ77::_OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma)
{	
	if ( isGamma )
	{
		BYTE* pb;
		DWORD out;
		int GammaCode = (int)code - 1;
		int q = LowerLog2(GammaCode);
		if (q > 0)
		{
			out = 0xffff;
			pb = (BYTE*)&out;
			CopyBits(dest + CurByte, CurBit, 
				pb, 0, q);
			MovePos(&CurByte, &CurBit, q);
		}
		out = 0;
		pb = (BYTE*)&out;		
		CopyBits(dest + CurByte, CurBit, pb + 3, 7, 1);
		MovePos(&CurByte, &CurBit, 1);
		if (q > 0)
		{
			int sh = 1;
			sh <<= q;
			out = GammaCode - sh;
			pb = (BYTE*)&out;
			InvertDWord(&out);
			CopyBits(dest + CurByte, CurBit, 
				pb + (32 - q) / 8, (32 - q) % 8, q);
			MovePos(&CurByte, &CurBit, q);
		}
	}
	else 
	{
		DWORD dw = (DWORD)code;
		BYTE* pb = (BYTE*)&dw;
		InvertDWord(&dw);
		CopyBits(dest + CurByte, CurBit, 
				pb + (32 - bits) / 8, (32 - bits) % 8, bits);
		MovePos(&CurByte, &CurBit, bits);
	}
}

int CCompressLZ77::Compress(BYTE* src, int srclen, BYTE* dest)
{
	int i;
	CurByte = 0; CurBit = 0;	
	int off, len;

	if (srclen > 65536) 
		return -1;

	pWnd = src;
	_InitSortTable();
	for (i = 0; i < srclen; i++)
	{		
		if (CurByte >= srclen)
			return 0;
		if (_SeekPhase(src, srclen, i, &off, &len))
		{			
			_OutCode(dest, 1, 1, FALSE);
			_OutCode(dest, len, 0, TRUE);

			_OutCode(dest, off, UpperLog2(nWndSize), FALSE);
						
			_ScrollWindow(len);
			i += len - 1;
		}
		else
		{
			_OutCode(dest, 0, 1, FALSE);
			_OutCode(dest, (DWORD)(src[i]), 8, FALSE);
			_ScrollWindow(1);
		}
	}
	int destlen = CurByte + ((CurBit) ? 1 : 0);
	if (destlen >= srclen)
		return 0;
	return destlen;
}

BOOL CCompressLZ77::Decompress(BYTE* src, int srclen, BYTE* dest)
{
	int i;
	CurByte = 0; CurBit = 0;
	pWnd = src;		// 初始化窗口
	nWndSize = 0;

	if (srclen > 65536) 
		return FALSE;
	
	for (i = 0; i < srclen; i++)
	{		
		BYTE b = GetBit(dest[CurByte], CurBit);
		MovePos(&CurByte, &CurBit, 1);
		if (b == 0) // 單個字符
		{
			CopyBits(src + i, 0, dest + CurByte, CurBit, 8);
			MovePos(&CurByte, &CurBit, 8);
			nWndSize++;
		}
		else		// 窗口內(nèi)的術(shù)語
		{
			int q = -1;
			while (b != 0)
			{
				q++;
				b = GetBit(dest[CurByte], CurBit);
				MovePos(&CurByte, &CurBit, 1);				
			}
			int len, off;
			DWORD dw = 0;
			BYTE* pb;
			if (q > 0)
			{				
				pb = (BYTE*)&dw;
				CopyBits(pb + (32 - q) / 8, (32 - q) % 8, dest + CurByte, CurBit, q);
				MovePos(&CurByte, &CurBit, q);
				InvertDWord(&dw);
				len = 1;
				len <<= q;
				len += dw;
				len += 1;
			}
			else
				len = 2;

			dw = 0;
			pb = (BYTE*)&dw;
			int bits = UpperLog2(nWndSize);
			CopyBits(pb + (32 - bits) / 8, (32 - bits) % 8, dest + CurByte, CurBit, bits);
			MovePos(&CurByte, &CurBit, bits);
			InvertDWord(&dw);
			off = (int)dw;
			for (int j = 0; j < len; j++)
			{
				_ASSERT(i + j <  srclen);
				_ASSERT(off + j <  _MAX_WINDOW_SIZE);
				
				src[i + j] = pWnd[off + j];
			}
			nWndSize += len;
			i += len - 1;
		}
		if (nWndSize > _MAX_WINDOW_SIZE)
		{
			pWnd += nWndSize - _MAX_WINDOW_SIZE;
			nWndSize = _MAX_WINDOW_SIZE;			
		}
	}

	return TRUE;
}
///////////////////////////////////////////////////////////////////////////////
//LZ77 Part END--------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//LZSS Part START--------------------------------------------------------------
///////////////////////////////////////////////////////////////////////////////

HGLOBAL C_LZSS::Encode(char *chData, int nSize)
{
	if(!AfxIsValidAddress(chData, nSize))
		return NULL;

//緩沖數(shù)據(jù)區(qū)大小
const int nMaxSize = 65536;

	HGLOBAL hZip = NULL;
	hZip = ::GlobalAlloc(GHND, nMaxSize);
	if(hZip == NULL)
	{
		return NULL;
	}
	LPBYTE lpZipData = (LPBYTE)::GlobalLock(hZip);
	BYTE byMaxBuf[nMaxSize];
	ZeroMemory(byMaxBuf, nMaxSize);

	int nCurPos = 0; //記下數(shù)據(jù)的位置

	int nZipPos = 0; //記下壓縮數(shù)據(jù)的位置
	int nBufPos = 0; //記下當前存儲位置hZip
	int nZipSize = 0; //壓縮后數(shù)據(jù)的大小

	int  i, c, len, r, s, last_match_length, code_buf_ptr;
	unsigned char code_buf[17], mask;
	InitTree();
	code_buf[0] = 0;
	code_buf_ptr = mask = 1;
	s = 0;  r = LZSS_N - LZSS_F;
	for(i = s; i < r; i++)
	{
		text_buf[i] = ' ';
	}
	for(len = 0; len < LZSS_F && (nCurPos < nSize/*getc(infile)*/); len++)
	{
		c = chData[nCurPos]; //add
		nCurPos ++; //add
		text_buf[r + len] = c;
	}
	if((textsize = len) == 0)
	{
		return false;
	}
	for(i = 1; i <= LZSS_F; i++)
	{
		InsertNode(r - i);
	}
	InsertNode(r);
	do
	{
		if(match_length > len)
		{
			match_length = len;
		}
		if(match_length <= LZSS_THRESHOLD)
		{
			match_length = 1;
			code_buf[0] |= mask;
			code_buf[code_buf_ptr++] = text_buf[r];
		}
		else
		{
			code_buf[code_buf_ptr++] = (unsigned char) match_position;
			code_buf[code_buf_ptr++] = (unsigned char)
				(((match_position >> 4) & 0xf0)
			  | (match_length - (LZSS_THRESHOLD + 1)));
		}
		if((mask <<= 1) == 0)
		{
			for(i = 0; i < code_buf_ptr; i++)
			{
				//存儲這個壓縮字節(jié)
				if(nZipPos >= nMaxSize)
				{
					nZipPos = 0;
					memcpy(lpZipData + nBufPos, byMaxBuf, nMaxSize);
					nBufPos += nMaxSize;

					::GlobalUnlock(hZip); //重新分配內(nèi)存
					hZip = ::GlobalReAlloc(hZip, nBufPos + nMaxSize, 0);
					lpZipData = (LPBYTE)::GlobalLock(hZip);
				}
				byMaxBuf[nZipPos] = code_buf[i];
				nZipPos ++;
				nZipSize ++; //當前壓縮數(shù)據(jù)的大小
			}
			codesize += code_buf_ptr;
			code_buf[0] = 0;
			code_buf_ptr = mask = 1;
		}
		last_match_length = match_length;
		for(i = 0; i < last_match_length && (nCurPos < nSize)/*c = getc(infile)) != EOF*/; i++)
		{
			c = chData[nCurPos]; //add
			nCurPos ++; //add
			DeleteNode(s);
			text_buf[s] = c;
			if(s < LZSS_F - 1)
			{
				text_buf[s + LZSS_N] = c;
			}
			s = (s + 1) & (LZSS_N - 1);
			r = (r + 1) & (LZSS_N - 1);
			InsertNode(r);
		}
		if((textsize += i) > printcount)
		{
			printcount += 1024;
		}
		while(i++ < last_match_length)
		{
			DeleteNode(s);
			s = (s + 1) & (LZSS_N - 1);
			r = (r + 1) & (LZSS_N - 1);
			if(--len)
			{
				InsertNode(r);
			}
		}
	}while (len > 0);
	if(code_buf_ptr > 1)
	{
		for(i = 0; i < code_buf_ptr; i++)
		{
			//存儲這個壓縮字節(jié)
			if(nZipPos >= nMaxSize)
			{
				nZipPos = 0;
				memcpy(lpZipData + nBufPos, byMaxBuf, nMaxSize);
				nBufPos += nMaxSize;

				::GlobalUnlock(hZip); //重新分配內(nèi)存
				hZip = ::GlobalReAlloc(hZip, nBufPos + nMaxSize, 0);
				lpZipData = (LPBYTE)::GlobalLock(hZip);
			}
			byMaxBuf[nZipPos] = code_buf[i];
			nZipPos ++;
			nZipSize ++; //當前壓縮數(shù)據(jù)的大小
		}
		codesize += code_buf_ptr;
	}
	//存儲剩余的壓縮數(shù)據(jù)
	if(nZipPos > 0)
	{
		memcpy(lpZipData + nBufPos, byMaxBuf, nZipPos);
	}
	::GlobalUnlock(hZip); //重新分配內(nèi)存
	hZip = ::GlobalReAlloc(hZip, nZipSize, 0);
	return hZip;
}

HGLOBAL C_LZSS::Decode(char *chZipData, int nZipSize)
{
	if(!AfxIsValidAddress(chZipData, nZipSize))