lzw.cpp

自己编写的一个采用LZW压缩算法对文件进行压缩的程序；

#include "stdafx.h"
#include <windows.h>
#include <stdio.h>
#include "TypeDefine.h"
#include "LZW.h"
#include "Dictionary.h"
#include "ByteString.h"

#define MEM_BLKLEN  102400
static bool OutputCode(unsigned short**pBase, int* pLen, unsigned short**pCur, unsigned short data)
{	
	// 内存不足
	if( *pCur+1>=*pBase+*pLen )
	{
		int newLen = *pLen + MEM_BLKLEN;	
		unsigned short *newBuf = new unsigned short[newLen];
		if( newBuf==NULL )return false;

		int dataLen = *pCur-*pBase;
		memcpy(newBuf,*pBase,dataLen*sizeof(unsigned short));
		delete[] *pBase;
		*pBase = newBuf;
		*pCur  = *pBase+dataLen;
		*pLen  = newLen;
	}
	
	**pCur=data;	

	return true;
}

static bool OutputBytes(BYTE **pBase, int* pLen, BYTE **pCur, BYTE *pData, int nLen)
{
	// 内存不足
	if( *pCur+nLen>=*pBase+*pLen )
	{
		int newLen = *pLen + MEM_BLKLEN;	
		BYTE *newBuf = new BYTE[newLen];
		if( newBuf==NULL )return false;

		int dataLen = *pCur-*pBase;
		memcpy(newBuf,*pBase,dataLen*sizeof(BYTE));
		delete[] *pBase;
		*pBase = newBuf;
		*pCur  = *pBase+dataLen;
		*pLen  = newLen;
	}
	
	memcpy(*pCur,pData,nLen);
	return true;
}

bool LZW_Compress(BYTE* pSrcBuf, int slen, BYTE **ppDesBuf, int* pdlen)
{	
	BYTE *pByte=pSrcBuf;
	BYTE *pMax=pByte+slen;
	int code=-1,len;

	int dlen = slen;
	unsigned short *pCode = new unsigned short [dlen];
	if( pCode==NULL )return false;

	unsigned short *pOut  = pCode;
	bool bRet = false;

	CDictionary dict;
	dict.Init();
	int ret = 0;
	CByteString strP;
	while( pByte<pMax )
	{	
		//当前前缀P的码字code
		code = dict.FindString(strP);
		if( code<0 )code=-1;

		// P+C	
		strP.Append(*pByte);
	
		//P+C是否在词典中
		if( dict.FindString(strP,code)>=0 )
		{		
		}
		//否
		else
		{			
			// 输出码字
			if( code>=0 )
			{
				if( OutputCode(&pCode, &dlen, &pOut, code) )pOut++;
				else goto FAIL;	
			}

			//P+C添加到词典	
			int ret = dict.AddString(strP,code);
			if( ret==DICTERR_DICTFULL )
			{
				//:词典空间已满，存盘重新再开始				
				// 1.写入分段码
				if( OutputCode(&pCode, &dlen, &pOut, 0xffff) )pOut++;
				else goto FAIL;				

				// 2.初始化压缩参数
				dict.Init();
				strP.Empty();

			}
			else if( ret!=DICTERR_SUCCESS )goto FAIL;

			//令P等于C
			strP = *pByte;		
		}

		pByte++;
	}

	code = dict.FindString(strP);
	// 输出码字
	if( code>=0 && OutputCode(&pCode, &dlen, &pOut, code) )pOut++;
	else goto FAIL;
	
	len	= (BYTE*)pOut-(BYTE*)pCode;
	*ppDesBuf = new BYTE[len];
	if( *ppDesBuf==NULL )goto FAIL;

	memcpy( *ppDesBuf,(BYTE*)pCode,len );
	*pdlen = len;	
	bRet = true;

FAIL:
	if(pCode)delete[] pCode;
	return bRet;

}



bool LZW_Decompress(BYTE* pSrcBuf, int slen, BYTE **ppDesBuf, int* pdlen)
{
	unsigned short* pCode=(unsigned short*)pSrcBuf;
	unsigned short* pMax =(unsigned short*)(pSrcBuf+slen);
	unsigned short cur=0, last=0;
	int code=-1,len;
	BYTE ch;
	int dlen = slen+slen;
	BYTE *pByte = new BYTE[dlen];
	BYTE *pOut=pByte;

	bool bRet = false;
	int  error=0;

	CByteString strP, strC;	
	CDictionary dict;
	dict.Init();

	//输出当前字符串
	if( !dict.GetString(*pCode,strC) )goto FAIL1;
	len = strC.GetLength();	
	if( !OutputBytes(&pByte, &dlen, &pOut, strC.GetBuffer(), len) )goto FAIL2;			
	pOut += len;
	
	//先前码字等于当前码字	
	while( pCode<pMax-1 )
	{
		//当前码字等于码子流的一下个码字
		last = *pCode;
		cur  = *(pCode+1);

		//分段码
		if( cur==0xffff )
		{
			dict.Init();
			cur = *(pCode+2);
			//输出当前字符串			
			if( !dict.GetString(cur,strC) )goto FAIL3;			
			// 内存不足
			len = strC.GetLength();
			if( !OutputBytes(&pByte, &dlen, &pOut, strC.GetBuffer(), len) )goto FAIL4;			
			pOut += len;
			pCode += 2;			
			continue;
		}

		//判断当前码字是否在词典中
		if( dict.FindCode(cur)==DICTERR_SUCCESS )
		{			
			//输出当前字符串
			if( !dict.GetString(cur,strC) )goto FAIL5;		
			len = strC.GetLength();
			if( !OutputBytes(&pByte, &dlen, &pOut, strC.GetBuffer(), len) )goto FAIL6;			
			pOut += len;			

			//当前字符等于当前前缀的第一个字符			
			ch  = strC[0];			
	
			//当前前缀等于先前前缀串			
			if( !dict.GetString(last,strP) )goto FAIL7;						
		
			//把缀串P+C加到词典
			strP.Append(ch);					
			if( dict.AddString(strP,last)!=DICTERR_SUCCESS )
				goto FAIL8;

			strP.Decrease();

		}
		else
		{		
			//当前前缀等于先前前缀串			
			if( !dict.GetString(last,strP) )goto FAIL9;		

			//当前字符等于当前前缀的第一个字符
			ch = strP[0];
			//把缀串P+C加到词典
			strP.Append(ch);						
			if( dict.AddString(strP,last)!=DICTERR_SUCCESS )goto FAIL10;

			//输出缀串P+C
			// 内存不足
			len = strP.GetLength();		
			if( !OutputBytes(&pByte, &dlen, &pOut, strP.GetBuffer(), len) )goto FAIL11;			
			pOut += len;

			strP.Decrease();

		}
	
		pCode++;
	}

	len	= pOut-pByte;
	*ppDesBuf = new BYTE[len];
	if( *ppDesBuf==NULL )goto FAIL12;

	memcpy( *ppDesBuf,(BYTE*)pByte,len );
	*pdlen = len;
	
	bRet = true;


FAIL12:error++;
FAIL11:error++;	
FAIL10:error++;
FAIL9:error++;
FAIL8:error++;
FAIL7:error++;
FAIL6:error++;
FAIL5:error++;
FAIL4:error++;
FAIL3:error++;
FAIL2:error++;
FAIL1:error++;
	if( !bRet )printf("error %d\n",error);
	if(pByte)delete[] pByte;
	return bRet;

}