// Lzss.cpp : 定义 DLL 应用程序的入口点。
//
#include "stdafx.h"
////////////////////////////////////////////////////////////////////////////////////////////////
// LZSS 压缩程序
// 程序编写：胡颖卓
// 编写时间：1999年12月
////////////////////////////////////////////////////////////////////////////////////////////////
#include"LZSS.H"
#define N 4096
#define F 18
#define THRESHOLD 2
#define NIL N
LZSS::LZSS()
{
buffer=new unsigned char[N+F-1];
lson=new int[N+1];
rson=new int[N+257];
dad=new int[N+1];
}
LZSS::~LZSS()
{
delete buffer;
delete lson;
delete rson;
delete dad;
}
int LZSS::GetByte()
{
if(InSize++>=InDataSize)return(EOF);
switch(InType)
{
case inMEM :return(*InData++);
case inFILE:return(getc(fpIn));
}
return(EOF);
}
void LZSS::PutByte(unsigned char c)
{
OutSize++;
switch(OutType)
{
case inMEM :*OutData++=c;return;
case inFILE:putc(c,fpOut);return;
}
}
void LZSS::InitTree()
{
int i;
for(i=N+1;i<=N+256;i++)rson[i]=NIL;
for(i=0;i<N;i++)dad[i]=NIL;
}
void LZSS::InsertNode(int r)
{
int i,p,cmp;
unsigned char *key;
cmp=1;key=&buffer[r];p=N+1+key[0];
rson[r]=lson[r]=NIL;mlen=0;
while(1)
{
if(cmp>=0)
{
if(rson[p]!=NIL)p=rson[p];else
{
rson[p]=r;dad[r]=p;return;
}
}else
{
if(lson[p]!=NIL)p=lson[p];else
{
lson[p]=r;dad[r]=p;return;
}
}
for(i=1;i<F;i++)
if((cmp=key[i]-buffer[p+i])!=0)break;
if(i>mlen)
{
mpos=p;
if((mlen=i)>=F)break;
}
}
dad[r]=dad[p];lson[r]=lson[p];rson[r]=rson[p];
dad[lson[p]]=r;dad[rson[p]]=r;
if(rson[dad[p]]==p)rson[dad[p]]=r;
else lson[dad[p]]=r;
dad[p]=NIL;
}
void LZSS::DeleteNode(int p)
{
int q;
if(dad[p]==NIL)return;
if(rson[p]==NIL)q=lson[p];
else if(lson[p]==NIL)q=rson[p];
else
{
q=lson[p];
if(rson[q]!=NIL)
{
do
{
q=rson[q];
}while(rson[q]!=NIL);
rson[dad[q]]=lson[q];dad[lson[q]]=dad[q];
lson[q]=lson[p];dad[lson[p]]=q;
}
rson[q]=rson[p];dad[rson[p]]=q;
}
dad[q]=dad[p];
if(rson[dad[p]]==p)rson[dad[p]]=q;
else lson[dad[p]]=q;
dad[p]=NIL;
}
void LZSS::Encode()
{
int i,c,len,r,s,lml,cbp;
unsigned char codebuf[17],mask;
InitTree();
codebuf[0]=0;
cbp=mask=1;
s=0;r=N-F;
for(i=s;i<r;i++)buffer[i]=' ';
for(len=0;len<F&&(c=GetByte())!=EOF;len++)buffer[r+len]=c;
if(len==0)return;
for(i=1;i<=F;i++)InsertNode(r-i);
InsertNode(r);
do
{
if(mlen>len)mlen=len;
if(mlen<=THRESHOLD)
{
mlen=1;codebuf[0]|=mask;codebuf[cbp++]=buffer[r];
}else
{
codebuf[cbp++]=(unsigned char)mpos;
codebuf[cbp++]=(unsigned char)(((mpos>>4)&0xF0)|(mlen-(THRESHOLD+1)));
}
if((mask<<=1)==0)
{
for(i=0;i<cbp;i++)PutByte(codebuf[i]);
codebuf[0]=0;cbp=mask=1;
}
lml=mlen;
for(i=0;i<lml&&(c=GetByte())!=EOF;i++)
{
DeleteNode(s);buffer[s]=c;
if(s<F-1)buffer[s+N]=c;
s=(s+1)&(N-1);r=(r+1)&(N-1);
InsertNode(r);
}
while(i++<lml)
{
DeleteNode(s);
s=(s+1)&(N-1);r=(r+1)&(N-1);
if(--len)InsertNode(r);
}
}while(len>0);
if(cbp>1)for(i=0;i<cbp;i++)PutByte(codebuf[i]);
}
void LZSS::Decode()
{
int i,j,k,r,c;
unsigned int flags;
for(i=0;i<N-F;i++)buffer[i]=' ';
r=N-F;flags=0;
for(;;)
{
if(((flags>>=1)&256)==0)
{
if((c=GetByte())==EOF)break;
flags=c|0xFF00;
}
if(flags&1)
{
if((c=GetByte())==EOF)break;
PutByte(c);buffer[r++]=c;r&=(N-1);
}else
{
if((i=GetByte())==EOF)break;
if((j=GetByte())==EOF)break;
i|=((j&0xF0)<<4);j=(j&0x0F)+THRESHOLD;
for(k=0;k<=j;k++)
{
c=buffer[(i+k)&(N-1)];
PutByte(c);buffer[r++]=c;r&=(N-1);
}
}
}
}
unsigned long LZSS::Compress(unsigned char *in,unsigned long insize,unsigned char *out)
{
InType=inMEM;InData=in;InDataSize=insize;InSize=0;
OutType=inMEM;OutData=out;OutSize=0;
Encode();
return(OutSize);
}
unsigned long LZSS::Compress(unsigned char *in,unsigned long insize,FILE *out)
{
InType=inMEM;InData=in;InDataSize=insize;InSize=0;
OutType=inFILE;fpOut=out;OutSize=0;
Encode();
return(OutSize);
}
unsigned long LZSS::Compress(FILE *in,unsigned long insize,FILE *out)
{
InType=inFILE;fpIn=in;InDataSize=insize;InSize=0;
OutType=inFILE;fpOut=out;OutSize=0;
Encode();
return(OutSize);
}
unsigned long LZSS::UnCompress(unsigned char *in,unsigned long insize,unsigned char *out)
{
InType=inMEM;InData=in;InDataSize=insize;InSize=0;
OutType=inMEM;OutData=out;OutSize=0;
Decode();
return(OutSize);
}
unsigned long LZSS::UnCompress(FILE *in,unsigned long insize,unsigned char *out)
{
InType=inFILE;fpIn=in;InDataSize=insize;InSize=0;
OutType=inMEM;OutData=out;OutSize=0;
Decode();
return(OutSize);
}
unsigned long LZSS::UnCompress(FILE *in,unsigned long insize,FILE *out)
{
InType=inFILE;fpIn=in;InDataSize=insize;InSize=0;
OutType=inFILE;fpOut=out;OutSize=0;
Decode();
return(OutSize);
}
#ifdef _MANAGED
#pragma managed(push, off)
#endif
BOOL APIENTRY DllMain( HMODULE hModule,
DWORD ul_reason_for_call,
LPVOID lpReserved
)
{
return TRUE;
}
#ifdef _MANAGED
#pragma managed(pop)
#endif
unsigned long Compress(unsigned char * pIn,unsigned long nSize,unsigned char * pOut)
{
LZSS lzss;
return lzss.Compress(pIn, nSize, pOut);
}
unsigned long UnCompress(unsigned char * pIn,unsigned long nSize,unsigned char * pOut)
{
LZSS lzss;
return lzss.UnCompress(pIn, nSize, pOut);
}
