LZW压缩算法 C#源码
usingSystem;
usingSystem.IO;
namespaceGif.Components
{
publicclassLZWEncoder
{
privatestaticreadonlyintEOF=-1;
privateintimgW,imgH;
privatebyte[]pixAry;
privateintinitCodeSize;
privateintremaining;
privateintcurPixel;
//GIFCOMPR.C-GIFImagecompressionroutines
//
//Lempel-Zivcompressionbasedon'compress'.GIFmodificationsby
//DavidRowley(mgardi@watdcsu.waterloo.edu)
//GeneralDEFINEs
staticreadonlyintBITS=12;
staticreadonlyintHSIZE=5003;//80%occupancy
//GIFImagecompression-modified'compress'
//
//Basedon:compress.c-FilecompressionalaIEEEComputer,June1984.
//
//ByAuthors:SpencerW.Thomas(decvax!harpo!utah-cs!utah-gr!thomas)
//JimMcKie(decvax!mcvax!jim)
//SteveDavies(decvax!vax135!petsd!peora!srd)
//KenTurkowski(decvax!decwrl!turtlevax!ken)
//JamesA.Woods(decvax!ihnp4!ames!jaw)
//JoeOrost(decvax!vax135!petsd!joe)
intn_bits;//numberofbits/code
intmaxbits=BITS;//usersettablemax#bits/code
intmaxcode;//maximumcode,givenn_bits
intmaxmaxcode=1<<BITS;//shouldNEVERgeneratethiscode
int[]htab=newint[HSIZE];//这个是放hash的筒子,在这里面可以很快的找到1个key
int[]codetab=newint[HSIZE];
inthsize=HSIZE;//fordynamictablesizing
intfree_ent=0;//firstunusedentry
//blockcompressionparameters--afterallcodesareusedup,
//andcompressionratechanges,startover.
boolclear_flg=false;
//Algorithm:useopenaddressingdoublehashing(nochaining)onthe
//prefixcode/nextcharactercombination.WedoavariantofKnuth's
//algorithmD(vol.3,sec.6.4)alongwithG.Knott'srelatively-prime
//secondaryprobe.Here,themodulardivisionfirstprobeisgivesway
//toafasterexclusive-ormanipulation.Alsodoblockcompressionwith
//anadaptivereset,wherebythecodetableisclearedwhenthecompression
//ratiodecreases,butafterthetablefills.Thevariable-lengthoutput
//codesarere-sizedatthispoint,andaspecialCLEARcodeisgenerated
//forthedecompressor.Lateaddition:constructthetableaccordingto
//filesizefornoticeablespeedimprovementonsmallfiles.Pleasedirect
//questionsaboutthisimplementationtoames!jaw.
intg_init_bits;
intClearCode;
intEOFCode;
//output
//
//Outputthegivencode.
//Inputs:
//code:An_bits-bitinteger.If==-1,thenEOF.Thisassumes
//thatn_bits=<wordsize-1.
//Outputs:
//Outputscodetothefile.
//Assumptions:
//Charsare8bitslong.
//Algorithm:
//MaintainaBITScharacterlongbuffer(sothat8codeswill
//fitinitexactly).UsetheVAXinsvinstructiontoinserteach
//codeinturn.Whenthebufferfillsupemptyitandstartover.
intcur_accum=0;
intcur_bits=0;
int[]masks=
{
0x0000,
0x0001,
0x0003,
0x0007,
0x000F,
0x001F,
0x003F,
0x007F,
0x00FF,
0x01FF,
0x03FF,
0x07FF,
0x0FFF,
0x1FFF,
0x3FFF,
0x7FFF,
0xFFFF};
//Numberofcharacterssofarinthis'packet'
inta_count;
//Definethestorageforthepacketaccumulator
byte[]accum=newbyte[256];
//----------------------------------------------------------------------------
publicLZWEncoder(intwidth,intheight,byte[]pixels,intcolor_depth)
{
imgW=width;
imgH=height;
pixAry=pixels;
initCodeSize=Math.Max(2,color_depth);
}
//Addacharactertotheendofthecurrentpacket,andifitis254
//characters,flushthepackettodisk.
voidAdd(bytec,Streamouts)
{
accum[a_count++]=c;
if(a_count>=254)
Flush(outs);
}
//Clearoutthehashtable
//tableclearforblockcompress
voidClearTable(Streamouts)
{
ResetCodeTable(hsize);
free_ent=ClearCode+2;
clear_flg=true;
Output(ClearCode,outs);
}
//resetcodetable
//全部初始化为-1
voidResetCodeTable(inthsize)
{
for(inti=0;i<hsize;++i)
htab[i]=-1;
}
voidCompress(intinit_bits,Streamouts)
{
intfcode;
inti/*=0*/;
intc;
intent;
intdisp;
inthsize_reg;
inthshift;
//Setuptheglobals:g_init_bits-initialnumberofbits
//原始数据的字长,在gif文件中，原始数据的字长可以为1(单色图),4(16色)，和8(256色)
//开始的时候先加上1
//但是当原始数据长度为1的时候，开始为3
//因此原始长度1->3,4->5,8->9
//?为何原始数据字长为1的时候，开始长度为3呢？?
//如果+1=2，只能表示四种状态，加上clearcode和endcode就用完了。所以必须扩展到3
g_init_bits=init_bits;
//Setupthenecessaryvalues
//是否需要加清除标志
//GIF为了提高压缩率，采用的是变长的字长(VCL)。比如说原始数据是8位，那么开始先加上1位(8+1=9)
//当标号到2^9=512的时候，超过了当前长度9所能表现的最大值，此时后面的标号就必须用10位来表示
//以此类推，当标号到2^12的时候，因为最大为12,不能继续扩展了，需要在2^12=4096的位置上插入一个ClearCode,表示从这往后，从9位重新再来了
clear_flg=false;
n_bits=g_init_bits;
//获得n位数能表述的最大值(gif图像中开始一般为3,5,9，故maxcode一般为7,31,511)
maxcode=MaxCode(n_bits);
//表示从这里我重新开始构造字典字典了，以前的所有标记作废，
//开始使用新的标记。这个标号集的大小多少比较合适呢？据说理论上是越大压缩率越高（我个人感觉太大了也不见得就好），
//不过处理的开销也呈指数增长
//gif规定，clearcode的值为原始数据最大字长所能表达的数值+1;比如原始数据长度为8,则clearcode=1<<(9-1)=256
ClearCode=1<<(init_bits-1);
//结束标志为clearcode+1
EOFCode=ClearCode+1;
//这个是解除结束的
free_ent=ClearCode+2;
//清楚数量
a_count=0;//clearpacket
//从图像中获得下一个像素
ent=NextPixel();
hshift=0;
for(fcode=hsize;fcode<65536;fcode*=2)
++hshift;
//设置hash码范围
hshift=8-hshift;//sethashcoderangebound
hsize_reg=hsize;
//清除固定大小的hash表，用于存储标记，这个相当于字典
ResetCodeTable(hsize_reg);//clearhashtable
Output(ClearCode,outs);
outer_loop:while((c=NextPixel())!=EOF)
{
fcode=(c<<maxbits)+ent;
i=(c<<hshift)^ent;//xorhashing
//嘿嘿,小样,又来了,我认识你
if(htab[i]==fcode)
{
ent=codetab[i];
continue;
}
//这小子,新来的
elseif(htab[i]>=0)//non-emptyslot
{
disp=hsize_reg-i;//secondaryhash(afterG.Knott)
if(i==0)
disp=1;
do
{
if((i-=disp)<0)
i+=hsize_reg;
if(htab[i]==fcode)
{
ent=codetab[i];
gotoouter_loop;
}
}while(htab[i]>=0);
}
Output(ent,outs);
//从这里可以看出,ent就是前缀（prefix）,而当前正在处理的字符标志就是后缀（suffix）
ent=c;
//判断终止结束符是否超过当前位数所能表述的范围
if(free_ent<maxmaxcode)
{
//如果没有超
codetab[i]=free_ent++;//code->hashtable
//hash表里面建立相应索引
htab[i]=fcode;
}
else
//说明超过了当前所能表述的范围,清空字典,重新再来
ClearTable(outs);
}
//Putoutthefinalcode.
Output(ent,outs);
Output(EOFCode,outs);
}
//----------------------------------------------------------------------------
publicvoidEncode(Streamos)
{
os.WriteByte(Convert.ToByte(initCodeSize));//write"initialcodesize"byte
//这个图像包含多少个像素
remaining=imgW*imgH;//resetnavigationvariables
//当前处理的像素索引
curPixel=0;
Compress(initCodeSize+1,os);//compressandwritethepixeldata
os.WriteByte(0);//writeblockterminator
}
//Flushthepackettodisk,andresettheaccumulator
voidFlush(Streamouts)
{
if(a_count>0)
{
outs.WriteByte(Convert.ToByte(a_count));
outs.Write(accum,0,a_count);
a_count=0;
}
}
///<summary>
///获得n位数所能表达的最大数值
///</summary>
///<paramname="n_bits">位数，一般情况下n_bits=9</param>
///<returns>最大值,例如n_bits=8,则返回值就为2^8-1=255</returns>
intMaxCode(intn_bits)
{
return(1<<n_bits)-1;
}
//----------------------------------------------------------------------------
//Returnthenextpixelfromtheimage
//----------------------------------------------------------------------------
///<summary>
///从图像中获得下一个像素
///</summary>
///<returns></returns>
privateintNextPixel()
{
//还剩多少个像素没有处理
//如果没有了,返回结束标志
if(remaining==0)
returnEOF;
//否则处理下一个,并将未处理像素数目-1
--remaining;
//当前处理的像素
inttemp=curPixel+1;
//如果当前处理像素在像素范围之内
if(temp<pixAry.GetUpperBound(0))
{
//下一个像素
bytepix=pixAry[curPixel++];
returnpix&0xff;
}
return0xff;
}
///<summary>
///输出字到输出流
///</summary>
///<paramname="code">要输出的字</param>
///<paramname="outs">输出流</param>
voidOutput(intcode,Streamouts)
{
//得到当前标志位所能表示的最大标志值
cur_accum&=masks[cur_bits];
if(cur_bits>0)
cur_accum|=(code<<cur_bits);
else
//如果标志位为0,就将当前标号为输入流
cur_accum=code;
//当前能标志的最大字长度(9-10-11-12-9-10。。。。。。。)
cur_bits+=n_bits;
//如果当前最大长度大于8
while(cur_bits>=8)
{
//向流中输出一个字节
Add((byte)(cur_accum&0xff),outs);
//将当前标号右移8位
cur_accum>>=8;
cur_bits-=8;
}
//Ifthenextentryisgoingtobetoobigforthecodesize,
//thenincreaseit,ifpossible.
if(free_ent>maxcode||clear_flg)
{
if(clear_flg)
{
maxcode=MaxCode(n_bits=g_init_bits);
clear_flg=false;
}
else
{
++n_bits;
if(n_bits==maxbits)
maxcode=maxmaxcode;
else
maxcode=MaxCode(n_bits);
}
}
if(code==EOFCode)
{
//AtEOF,writetherestofthebuffer.
while(cur_bits>0)
{
Add((byte)(cur_accum&0xff),outs);
cur_accum>>=8;
cur_bits-=8;
}
Flush(outs);
}
}
}
}
以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持毛票票。