lzw.pas

lzw压缩源代码, 非常快速的lzw算法,以前保存下来的,现在共享给大家

unit LZW;

interface

uses
  Windows, Messages, SysUtils, Classes;
  //////////////////////////////////////////////////////////////////////////
  //                      Lempel-Ziv & Weleh 算法                         //
  //                                                                      //
  //             GGCAT  改编以进行非常快速的压缩处理                      //
  //                                                                      //
  //        主要改动  小的列表窗口 1024 （ 原为 4096   )                  //
  //                  定长编码输出 方便的快速合并和拆分                   //
  //                                                                      //
  //        性    能  CA 333 Win2000    > 4M Bytes /PerSecond             //
  //                                                                      //
  //        压 缩 率  WinZip SuperFast 方式的   120 %                     //
  //                            2000-12-20                                //
  //////////////////////////////////////////////////////////////////////////
  Const  _WinSize= 1023; //采用小的窗口 牺牲一定的压缩量换取压缩速度 并减少内存使用
        _ClearWnd= 256;
       _EndOfData= 257;

Type

  TProcessingEvent=Procedure(InPutSize,OutPutSize,Percent:Integer;Var Cancel:Boolean) of Object;


  PLZWNode=^TLZWNode;
  TLZWNode=Record
     Value:Byte;                            //本单元包含数据
     Index:SmallInt;                        //本单元的索引
     NodeHigh:SmallInt;                     //子接点上标
     SubNode:Array[0..255] of SmallInt;     //子接点定位列表
     End;

  TInt32Array=Array [0..1] of Integer;
  PInt32Array=^TInt32Array;

  TLZWlite=Class
    Private
      LZWTree:Array [-1.._WinSize] OF PLZWNode;
      CurrentNode:PLZWNode;
      WinPos:Smallint;
      Procedure ResetTable;
    Public
      Function CompressToStream(Src:Pointer;MemStream:Tmemorystream;SrcSize:Integer):Integer;
      Function DeCompressToStream(Src:Pointer;MemStream:Tmemorystream;SrcSize:Integer):Integer;
      Constructor Create;
      Destructor Destroy; Override;
    End;

Implementation

Constructor TLZWlite.Create;
Var I:Integer;
Begin
  Inherited Create;

  For I:=-1 to _WinSize do           //初始化列表
   Begin
     New(LZWTree[I]);                //申请接点
     LZWTree[I].NodeHigh:=-1;
     IF I>=0 then LZWTree[I].Value:=I;
     IF I>=0 then LZWTree[I].Index:=I;
   End;
   LZWTree[-1].NodeHigh:=255;        //定义根接点
   For I:=0 to 255 Do
     LZWTree[-1].SubNode[I]:=I;
End;

Destructor  TLZWlite.Destroy;
Var I:Integer;
Begin
 For I:=-1 to _WinSize do             //退出时释放各个接点
     Begin
      DisPose(LZWTree[I]);
     End;
  Inherited Destroy;
End;

Procedure TLZWlite.ResetTable;
Var I:Integer;
Begin
  For I:=0 To _WinSize Do
      LZWTree[I].NodeHigh:=-1;
   WinPos:=258;
   CurrentNode:=LZWTree[-1];
End;

Function TLZWlite.CompressToStream(Src:Pointer;MemStream:Tmemorystream;SrcSize:Integer):Integer;
VAR SrcData:PByteArray;
    OB,H:Integer;
    I,J:Integer;
    Found,JustComplete:Boolean;
    aDW,DstBegin,DstPtr:Dword;

    Procedure OutV(Value:Integer);
     Asm
                Mov EDX,Value
                Inc OB
                And OB,3

                Cmp OB,1
                Je  @OB1
                Cmp OB,2
                Je  @OB2
                Cmp OB,3
                Je  @OB3
           @OB0:Mov ECX, DstPtr
                Mov EAX,EDX
                Shr AX,8
                OR  EAX,aDW
                Mov [ECX],EAX
                Add ECX,4
                Mov [Ecx],DL
                Inc ECX
                Mov DstPtr,Ecx
                Jmp @Exit
           @OB1:Shl EDX,22
                Mov aDW,EDX
                Jmp @Exit
           @OB2:Shl EDX,12
                Or  aDW,EDX
                Jmp @Exit
           @OB3:Shl EDX,2
                Or  aDW,EDX
           @Exit:
    End;
Begin
    SrcData:=Src;  MemStream.Clear;
    MemStream.SetSize(SrcSize *10 div 8 +1024);
    DstBegin:=DWord(MemStream.Memory);
    DstPtr:=DWord(MemStream.Memory);
    PDword(DstPtr)^:=SrcSize;
    Inc(DstPtr,4);

    OB:=0;
    ResetTable;
    OutV(_ClearWnd);   JustComplete:=False ;

    For I:=0 to SrcSize-1 Do
    Begin
     Found:=False;
     For J:=0 To CurrentNode.NodeHigh Do                             // 在树中反复嵌套定位
        IF SrcData[I]=LZWTree[CurrentNode.SubNode[J]].Value then
         Begin
           CurrentNode:=LZWTree[CurrentNode.SubNode[J]];
           Found:=True;
           Break;
         End;
     IF Found Then Continue;

     OutV(CurrentNode.Index);

     Inc(CurrentNode.NodeHigh);                      //添加新节点并设置接点关联
     H:=CurrentNode.NodeHigh;
     CurrentNode.SubNode[H]:=WinPos;
     LZWTree[WinPos].Value:=SrcData[I];
     CurrentNode:=LZWTree[SrcData[I]];

     Inc(WinPos);                                    //窗口是否超出大小
     IF WinPos>_WinSize then
       Begin
        OutV(SrcData[I]);
        ResetTable;                                  //树清零
        OutV(_ClearWnd);
        IF I=SrcSize-1 then JustComplete:=True;      //是否恰好结束 以避免重复添加数据
       End;
   End;

   IF Not JustComplete then OutV(CurrentNode.Index); //输出最后的字符
   OutV(_EndOfData);

   IF OB>0 then
      For I:=1 to 4-OB do OutV(0);

  MemStream.SetSize(DstPtr-DstBegin);
  Result:=MemStream.Size;
  MemStream.Position:=0;
End;

Function TLZWlite.DeCompressToStream(Src:Pointer;MemStream:Tmemorystream;SrcSize:Integer):Integer;
Var OutSize,I,J,OB,H,OS:Integer;
    Code,OldCode:Smallint;
    ThisPackDW,DataPtr,DstPtr:DWord;
    ThisPackByte:Byte;
    StringTable:Array [0.._WinSize] of Array of Byte;
    SLTable:Array [0.._WinSize] of SmallInt;

    Procedure GetNextValue;                           //数据单元拆分
      Asm
           CMP OB,1
           JE  @OB1
           CMP OB,2
           JE  @OB2
           CMP OB,3
           JE  @OB3
     @OB0: Mov ECX,DataPtr
           MOV EDX,[ECX]
           Add ECX,4
           Mov ThisPackDW,EDX
           MOV AL,[ECX]
           Inc ECX
           Mov DataPtr,ECX
           Mov ThisPackByte,AL
           Shr EDX,22
           Mov Code,DX
           Jmp @Exit
     @OB1: Mov EAX,ThisPackDW
           Shr EAX,12
           AND EAX,$3FF
           Mov Code,AX
           Jmp @Exit
     @OB2: Mov EAX,ThisPackDW
           Shr EAX,2
           AND EAX,$3FF
           Mov Code,AX
           Jmp @Exit
     @OB3: Mov EAX,ThisPackDW
           Shl EAX,8
           MOV AL,ThisPackByte
           AND EAX,$3FF
           Mov Code,AX
     @Exit:Inc OB
           AND OB,3

      End;

     Procedure OutValue(Index:Smallint);              //输出对应列表的连续数据
      Var I:Integer;
      Begin
       For I:=0 to SLTable[Index]-1 Do
             Begin
             PByte(DstPtr)^:=StringTable[Index,I];
             Inc(DstPtr);
             Inc(OS);
             End;
      End;
Begin
    OB:=0;  OS:=0;
    DataPtr:=DWord(Src);
    OutSize:=PDWord(DataPtr)^;
    Inc(DataPtr,4);

    MemStream.SetSize(OutSize);
    DstPtr:=DWord(MemStream.Memory);
    WinPos:=258;

      For I:=0 To _WinSize Do
             Begin
               IF I<=258 then
               SetLength(StringTable[I],1) ELse
               SetLength(StringTable[I],I-256);
               IF I<=255 then
                      Begin
                        StringTable[I][0]:=I;
                        SLTable[I]:=1;
                      ENd ELse
                        SLTable[I]:=0;
             End;
    GetNextValue;
    While Code<>_EndofData Do
       Begin
        IF Code=_ClearWnd then
          Begin
            WinPos:=258;
            GetNextValue;
            IF Code=_EndofData Then Break  ;
            OutValue(Code);
            OldCode:=Code;
          End Else
            Begin
              IF Code<WinPos Then
                Begin
                  OutValue(Code);
                  H:=SLTable[OldCode];
                  SLTable[WinPos]:=H+1;
                  For J:=0 to H-1 Do
                     StringTable[WinPos][J]:=StringTable[OldCode][J];
                  StringTable[WinPos][H]:=StringTable[Code][0];
                  Inc(WinPos);
                  OldCode:=Code;
                End Else
                  Begin
                    H:=SLtable[OldCode];
                    SLTable[WinPos]:=H+1;
                     For J:=0 to H-1 Do
                       StringTable[WinPos][J]:=StringTable[OldCode][J];
                    StringTable[WinPos][H]:=StringTable[OldCode][0];
                    OutValue(WinPos);
                    Inc(WinPos);
                    OldCode:=Code;
                  End;
             End;
          GetNextValue;
       End;
   IF OS<>OutSize then MemStream.SetSize(OS);
   Result:=OS;
   MemStream.Position:=0;
End;
End.