compress.cpp

用FREE BASIC做的演示程序

				*pOrgData=*((unsigned short*)pData);
				pData+=2;
				pOrgData++;
			}
		}
	}
	
	return true;
}



int GCompressLZSS::s_nMatchLength=0;
int GCompressLZSS::s_nMatchPos=0;
int GCompressLZSS::s_pParent[];
int GCompressLZSS::s_pLeftChild[];
int GCompressLZSS::s_pRightChild[];
unsigned char GCompressLZSS::s_pBuf[];

void GCompressLZSS::InitTree()
{
	for(int i=WINDOW_SIZE+1;i<=WINDOW_SIZE+256;i++)
		s_pRightChild[i]=UNUSE;
	for(i=0;i<WINDOW_SIZE;i++)
		s_pParent[i]=UNUSE;
}
void GCompressLZSS::Insert(int index)
{
	unsigned char *pKey=&s_pBuf[index];
	int cmp=1;
	int pos=WINDOW_SIZE+1+pKey[0];
	s_pLeftChild[index]=UNUSE;
	s_pRightChild[index]=UNUSE;
	s_nMatchLength=0;
	for(;;)
	{
		if(cmp>=0)
		{
			if(s_pRightChild[pos]!=UNUSE)
			{
				pos=s_pRightChild[pos];
			}
			else
			{
				s_pRightChild[pos]=index;
				s_pParent[index]=pos;
				return;
			}
		}
		else
		{
			if(s_pLeftChild[pos]!=UNUSE)
			{
				pos=s_pLeftChild[pos];
			}
			else
			{
				s_pLeftChild[pos]=index;
				s_pParent[index]=pos;
				return;
			}
		}
		for(int i=1;i<FORWORD_BUF_SIZE;i++)
		{
			cmp=pKey[i]-s_pBuf[pos+i];
			if(cmp!=0)
				break;
		}
		if(i>s_nMatchLength)
		{
			s_nMatchLength=i;
			s_nMatchPos=pos;
			if(s_nMatchLength>= FORWORD_BUF_SIZE)
				break;
		}
	}
	s_pParent[index]=s_pParent[pos];
	s_pLeftChild[index]=s_pLeftChild[pos];
	s_pRightChild[index]=s_pRightChild[pos];
	s_pParent[s_pLeftChild[pos]]=index;
	s_pParent[s_pRightChild[pos]]=index;
	if(s_pRightChild[s_pParent[pos]]==pos)
	{
		s_pRightChild[s_pParent[pos]]=index;
	}
	else
	{
		s_pLeftChild[s_pParent[pos]]=index;
	}
	s_pParent[pos]=UNUSE;
}
void GCompressLZSS::Remove(int index)
{
	int tmp;
	if(s_pParent[index]==UNUSE)
		return;
	if(s_pRightChild[index]==UNUSE)
	{
		tmp=s_pLeftChild[index];
	}
	else if(s_pLeftChild[index]==UNUSE)
	{
		tmp=s_pRightChild[index];
	}
	else
	{
		tmp=s_pLeftChild[index];
		if(s_pRightChild[tmp]!=UNUSE)
		{
			while(s_pRightChild[tmp]!=UNUSE)
			{
				tmp=s_pRightChild[tmp];
			}
			s_pRightChild[s_pParent[tmp]]=s_pLeftChild[tmp];
			s_pParent[s_pLeftChild[tmp]]=s_pParent[tmp];
			s_pLeftChild[tmp]=s_pLeftChild[index];
			s_pParent[s_pLeftChild[index]]=tmp;
		}
		s_pRightChild[tmp]=s_pRightChild[index];
		s_pParent[s_pRightChild[index]]=tmp;
	}
	s_pParent[tmp]=s_pParent[index];
	if(s_pRightChild[s_pParent[index]]==index)
	{
		s_pRightChild[s_pParent[index]]=tmp;
	}
    else 
	{
		s_pLeftChild[s_pParent[index]]=tmp;
	}
	s_pParent[index]=UNUSE;
}
bool GCompressLZSS::Compress(void*pOrgData,unsigned long dwOrgDataSize,void**ppCompressData,unsigned long & dwCompressedDataSize)
{
	InitTree();
	unsigned char codebuf[FORWORD_BUF_SIZE-1];
	unsigned char mask=0x1;
	codebuf[0]=0;
	int bit=1;
	int s=0;
	int r=WINDOW_SIZE-FORWORD_BUF_SIZE;
	for(int i=s;i<r;i++)
		s_pBuf[i]=' ';
	
	unsigned char*pData=(unsigned char*)pOrgData;
	unsigned char*pDataEnd=pData+dwOrgDataSize;
	unsigned char*pCompressData=(unsigned char*)malloc(0xffff);
	unsigned char*pCmpData=pCompressData;
	unsigned long dwCurSize=0;
	unsigned long dwMaxSize=0xffff;
	if(!pCompressData)
		return false;
	for(int len=0;len<FORWORD_BUF_SIZE;len++)
	{
		if(pData>=pDataEnd)
			break;
		s_pBuf[r+len]=*pData;
		pData++;
	}
	if(len==0)
		return true;
	for(i=1;i<=FORWORD_BUF_SIZE;i++)
		Insert(r-i);
	Insert(r);
	while(len>0)
	{
		if(s_nMatchLength>len)
			s_nMatchLength=len;
		if(s_nMatchLength<=MINMATCH)
		{
			s_nMatchLength=1;
			codebuf[0]|=mask;
			codebuf[bit++]=s_pBuf[r];
		}
		else
		{
			codebuf[bit++]=(unsigned char)s_nMatchPos;
			codebuf[bit++]=(unsigned char)(((s_nMatchPos>>4)&0xF0)|(s_nMatchLength-(MINMATCH+1)));
		}
		mask<<=1;
		if(mask==0x0)
		{
			dwCurSize+=bit;
			if(dwCurSize >= dwMaxSize)
			{
				dwMaxSize+=0xffff;
				unsigned char*pNewAddr=(unsigned char*)realloc(pCompressData,dwMaxSize);
				if(!pNewAddr)
				{
					free(pCompressData);
					return false;
				}
				pCompressData=pNewAddr;
				pCmpData=pNewAddr+dwCurSize-bit;
			}
			for(i=0;i<bit;i++)
			{
				*pCmpData=codebuf[i];
				pCmpData++;
			}
			codebuf[0]=0;
			mask=0x1;
			bit=1;
		}
		int match=s_nMatchLength;
		for(i=0;i<match;i++)
		{
			if(pData>=pDataEnd)
				break;
			Remove(s);
			s_pBuf[s]=*pData;
			if(s<FORWORD_BUF_SIZE-1)
				s_pBuf[s+WINDOW_SIZE]=*pData;
			s=(s+1)&(WINDOW_SIZE-1);//Mod
			r=(r+1)&(WINDOW_SIZE-1);//Mod
			Insert(r);
			pData++;
		}
		while(i++<match)
		{
			Remove(s);
			s=(s+1)&(WINDOW_SIZE-1);
			r=(r+1)&(WINDOW_SIZE-1);
			if(--len)
				Insert(r);
		}
	}
	if(bit>1)
	{
		dwCurSize+=bit;
		if(dwCurSize >= dwMaxSize)
		{
			dwMaxSize+=0xffff;
			unsigned char*pNewAddr=(unsigned char*)realloc(pCompressData,dwMaxSize);
			if(!pNewAddr)
			{
				free(pCompressData);
				return false;
			}
			pCompressData=pNewAddr;
			pCmpData=pNewAddr+dwCurSize-bit;
		}
		for(i=0;i<bit;i++)
		{
			*pCmpData=codebuf[i];
			pCmpData++;
		}
	}
	*ppCompressData=(unsigned char*)realloc(pCompressData,dwCurSize);
	dwCompressedDataSize=dwCurSize;

	return true;
}
bool GCompressLZSS::Decompress(void*pCompressedData,unsigned long dwCompressedDataSize,void*pDestAddr)
{
	InitTree();
	for(int i=0;i<WINDOW_SIZE-FORWORD_BUF_SIZE;i++)
	{
		s_pBuf[i]=' ';
	}
	int r=WINDOW_SIZE-FORWORD_BUF_SIZE;
	unsigned int mask=0;
	unsigned char*pData=(unsigned char*)pCompressedData;
	unsigned char*pDataEnd=pData+dwCompressedDataSize;
	unsigned char*pOrgData=(unsigned char*)pDestAddr;
	while(pData<pDataEnd)
	{
		if(((mask>>=1)&256)==0)
		{
			mask=*pData|0xFF00;
			pData++;
		}
		if(mask&0x1)
		{
			*pOrgData=*pData;
			s_pBuf[r++]=*pData;
			r&=(WINDOW_SIZE-1);
			pData++;
			pOrgData++;
		}
		else
		{
			int i=*pData;
			pData++;
			int j=*pData;
			pData++;
			i|=(j&0xF0)<<4;
			j=(j&0x0F)+MINMATCH;	
			for(int k=0;k<=j;k++)
			{
				*pOrgData=s_pBuf[(i+k)&(WINDOW_SIZE-1)];
				s_pBuf[r++]=*pOrgData;
				r&=(WINDOW_SIZE-1);
				pOrgData++;
			}
		}
	}
	return true;
}
bool GCompressLZSS::DecompressAutoSize(void*pCompressedData,unsigned long dwCompressedDataSize,void**ppOrgData,unsigned long & dwOrgDataSize)
{
	InitTree();
	for(int i=0;i<WINDOW_SIZE-FORWORD_BUF_SIZE;i++)
	{
		s_pBuf[i]=' ';
	}
	int r=WINDOW_SIZE-FORWORD_BUF_SIZE;
	unsigned int mask=0;
	unsigned char*pData=(unsigned char*)pCompressedData;
	unsigned char*pDataEnd=pData+dwCompressedDataSize;
	
	*ppOrgData=(unsigned char*)malloc(dwCompressedDataSize);
	if(!(*ppOrgData))
		return false;
	unsigned char*pOrgData=(unsigned char*)*ppOrgData;
	unsigned long dwCurSize=0;
	unsigned long dwMaxSize=dwCompressedDataSize;
	
	while(pData<pDataEnd)
	{
		if(((mask>>=1)&256)==0)
		{
			mask=*pData|0xFF00;
			pData++;
		}
		if(mask&0x1)
		{
			dwCurSize++;
			if(dwCurSize>=dwMaxSize)
			{
				dwMaxSize+=dwCompressedDataSize;
				unsigned char*pNewAddr=(unsigned char*)realloc(*ppOrgData,dwMaxSize);
				if(!pNewAddr)
				{
					free(*ppOrgData);
					return false;
				}
				*ppOrgData=pNewAddr;
				pOrgData=pNewAddr+dwCurSize-1;
			}	
			*pOrgData=*pData;
			s_pBuf[r++]=*pData;
			r&=(WINDOW_SIZE-1);
			pData++;
			pOrgData++;
		}
		else
		{
			int i=*pData;
			pData++;
			int j=*pData;
			pData++;
			i|=(j&0xF0)<<4;
			j=(j&0x0F)+MINMATCH;
			dwCurSize+=j+1;
			if(dwCurSize>=dwMaxSize)
			{
				dwMaxSize+=dwCompressedDataSize;
				unsigned char*pNewAddr=(unsigned char*)realloc(*ppOrgData,dwMaxSize);
				if(!pNewAddr)
				{
					free(*ppOrgData);
					return false;
				}
				*ppOrgData=pNewAddr;
				pOrgData=pNewAddr+dwCurSize-j-1;
			}
			for(int k=0;k<=j;k++)
			{
				*pOrgData=s_pBuf[(i+k)&(WINDOW_SIZE-1)];
				s_pBuf[r++]=*pOrgData;
				r&=(WINDOW_SIZE-1);
				pOrgData++;
			}
		}
	}
	*ppOrgData=realloc(*ppOrgData,dwCurSize);
	dwOrgDataSize=dwCurSize;
	return true;
}