//////////////////////////////
// LZ77.CPP
//////////////////////////////

#include <windows.h>
#include <stdio.h>
#include <memory.h>
#include <crtdbg.h>

#include "lz77.h"

/////////////////////////////////////////////////////////
// 取log2(n)的upper_bound
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;
}
// UpperLog2
/////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////
// 取log2(n)的lower_bound
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;
}
// LowerLog2
/////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////
// 將位指針*piByte(字節偏移), *piBit(字節內位偏移)后移num位
void CCompress::MovePos(int* piByte, int* piBit, int num)
{
	num += (*piBit);
	(*piByte) += num / 8;
	(*piBit) = num % 8;
}
// MovePos
////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////
// 得到字節byte第pos位的值
//		pos順序為高位起從0記數（左起）
BYTE CCompress::GetBit(BYTE byte, int pos)
{
	int j = 1;
	j <<= 7 - pos;
	if (byte & j)
		return 1;
	else 
		return 0;
}
// GetBit
/////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////
// 設置byte的第iBit位為aBit
//		iBit順序為高位起從0記數（左起）
void CCompress::SetBit(BYTE* byte, int iBit, BYTE aBit)
{
	if (aBit)
		(*byte) |= (1 << (7 - iBit));
	else
		(*byte) &= ~(1 << (7 - iBit));
}
// SetBit
//////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////
// 將DWORD值從高位字節到低位字節排列
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;
}
// InvertDWord
//////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////
// CopyBits : 復制內存中的位流
//		memDest - 目標數據區
//		nDestPos - 目標數據區第一個字節中的起始位
//		memSrc - 源數據區
//		nSrcPos - 源數據區第一個字節的中起始位
//		nBits - 要復制的位數
//	說明：
//		起始位的表示約定為從字節的高位至低位（由左至右）
//		依次為 0，1，... , 7
//		要復制的兩塊數據區不能有重合
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);		
		// 如果還沒有復制完 nBitsToFill 個
		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;	// 已經填充了nBitsToFill位
		iByteDest++;
	}	
}
// CopyBits
/////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////
// CopyBitsInAByte : 在一個字節范圍內復制位流
// 參數含義同 CopyBits 的參數
// 說明：
//		此函數由 CopyBits 調用，不做錯誤檢查，即
//		假定要復制的位都在一個字節范圍內
void CCompress::CopyBitsInAByte(BYTE* memDest, int nDestPos, 
			  BYTE* memSrc, int nSrcPos, int nBits)
{
	BYTE b1, b2;
	b1 = *memSrc;
	b1 <<= nSrcPos; b1 >>= 8 - nBits;	// 將不用復制的位清0
	b1 <<= 8 - nBits - nDestPos;		// 將源和目的字節對齊
	*memDest |= b1;		// 復制值為1的位
	b2 = 0xff; b2 <<= 8 - nDestPos;		// 將不用復制的位置1
	b1 |= b2;
	b2 = 0xff; b2 >>= nDestPos + nBits;
	b1 |= b2;
	*memDest &= b1;		// 復制值為0的位
}
// CopyBitsInAByte
/////////////////////////////////////////////////////////


//------------------------------------------------------------------


void CCompressLZ77::GetCompressFileName(char *dst, char *src)
{
	char FileName[MAX_PATH];
	ZeroMemory(FileName, MAX_PATH);
	char *p;
	memcpy(FileName, src, strlen(src));
	p = strstr(FileName, ".");
	*p = 0;
	strcpy(dst, FileName);
	strcat(dst, ".liz");
}

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;
}

// 向索引中添加一個2字節串
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
	{
		// 對重復2字節串
		// 因為沒有虛擬偏移也沒有刪除操作，只要比較第一個節點
		// 是否和 off 相連接即可
		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;
		}
	}
}

//////////////////////////////////////////
// 將窗口向右滑動n個字節
void CCompressLZ77::_ScrollWindow(int n)
{	
	for (int i = 0; i < n; i++)
	{		
		nWndSize++;		
		if (nWndSize > 1)			
			_InsertIndexItem(nWndSize - 2);
	}
}

///////////////////////////////////////////////////////////
// 得到已經匹配了2個字節的窗口位置offset
// 共能匹配多少個字節
int CCompressLZ77::_GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset)
{
	int i = 2; // 已經匹配了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;
}

///////////////////////////////////////////////////////////
// 在滑動窗口中查找術語
// nSeekStart - 從何處開始匹配
// offset, len - 用于接收結果，表示在滑動窗口內的偏移和長度
// 返回值- 是否查到長度為2或2以上的匹配字節串
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;
}

////////////////////////////////////////
// 輸出壓縮碼
// code - 要輸出的數
// bits - 要輸出的位數(對isGamma=TRUE時無效)
// isGamma - 是否輸出為γ編碼
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;
			// 輸出q個1
			CopyBits(dest + CurByte, CurBit, 
				pb, 0, q);
			MovePos(&CurByte, &CurBit, q);
		}
		// 輸出一個0
		out = 0;
		pb = (BYTE*)&out;		
		CopyBits(dest + CurByte, CurBit, pb + 3, 7, 1);
		MovePos(&CurByte, &CurBit, 1);
		if (q > 0)
		{
			// 輸出余數, q位
			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);
	}
}

bool CCompressLZ77::CompressFile(char* unZipFile, char* zipFile)
{
	WORD flag1, flag2;
	BYTE soubuf[65536];
	BYTE destbuf[65536 + 16];
	FILE* in = fopen(unZipFile, "rb");
	FILE* out = out = fopen(zipFile, "wb");
	if (out == NULL)
	{
		fclose(in);
		return false;
	}
	fseek(in, 0, SEEK_END);
	long soulen = ftell(in);
	fseek(in, 0, SEEK_SET);
	int last = soulen, act;
	while ( last > 0 )
	{
		act = min(65536, last);
		fread(soubuf, act, 1, in);
		last -= act;
		if (act == 65536)			// out 65536 bytes				
			flag1 = 0;		
		else					// out last blocks
			flag1 = act;
		fwrite(&flag1, sizeof(WORD), 1, out);

		int destlen = Compress((BYTE*)soubuf, act, (BYTE*)destbuf);
		if (destlen == 0)		// can't compress the block
		{
			flag2 = flag1;
			fwrite(&flag2, sizeof(WORD), 1, out);
			fwrite(soubuf, act, 1, out);
		}
		else
		{
			flag2 = (WORD)destlen;
			fwrite(&flag2, sizeof(WORD), 1, out);				
			fwrite(destbuf, destlen, 1, out);				
		}
	}
	fclose(in);
	fclose(out);