lz77.pas

多种算法压缩与解压缩方式

end;

function TCompress.LowerLog2(n: integer): integer;
var
  i,m:integer;
begin
  i := 0;
  if (n > 0) then
  begin
    m:=1;
    while true do
    begin
      if m=n then
      begin
        result:=i;
        exit;
      end else
      if m>n then
      begin
        result:=i-1;
        exit;
      end;

      m:=m shl 1;
      inc(i);
    end;

  end else result:=-1;

end;

procedure TCompress.MovePos(var piByte, piBit: integer; num: integer);
begin
   num:=num+piBit;
   piByte:=piByte+ (num div 8);
   piBit:=num mod 8
end;

procedure TCompress.SetBit(var Abyte: Byte; iBit: integer; aBit: byte);
var
  j:byte;
begin
  j:=1;
  j:=j shl (7-iBit);
  if aBit>0 then
    Abyte:=Abyte or j
  else
    Abyte:=Abyte and  not j;
end;

function TCompress.UpperLog2(n: integer): integer;
var
  i,m:integer;
begin
  i := 0;
  if (n > 0) then
  begin
    m:=1;
    while true do
    begin
      if m>=n then
      begin
        result:=i;
        exit;
      end;
      m:=m shl 1;
      inc(i);
    end;

  end else result:=-1;

end;

{ TLZ77Compress }

function TLZ77Compress._GetSameLen(src: PChar; srclen, nSeekStart,
  offset: integer): integer;
var
  i,maxsame:integer;
begin

  i := 2; // 已经匹配了2个字节

  maxsame := min(srclen - nSeekStart, nWndSize - offset);
  while (i < maxsame) and (src[nSeekStart + i] = pWnd[offset + i]) do inc(i);
  ASSERT((nSeekStart + i <= srclen) and (offset + i <= nWndSize));
  result:= i;
end;

procedure TLZ77Compress._InitSortTable;
begin
  fillmemory(@SortTable[0], sizeof(WORD) * 65536,$FF);
  fillmemory(@SortFAT[0], sizeof(WORD) * 65536,$FF);
  nWndSize := 0;
  lastbyte:=0;
end;

procedure TLZ77Compress._InsertIndexItem(off: integer);
var
  ch1, ch2:byte;
  offentry:word;
begin
  ch1 := byte(pWnd[off]);
  ch2 := byte(pWnd[off + 1]);

  if (ch1 <> ch2) then
  begin
    // 新建节点
    offentry:=SortTable[ch1 * 256 + ch2];
    if offentry=$FFFF then
       SortTable[ch1 * 256 + ch2]:=off
    else
    begin
      while SortFAT[offentry]<>$FFFF do
        offentry:=SortFAT[offentry];
      SortFAT[offentry]:=off;
    end;
  end else
  begin
    // 对重复2字节串
    // 因为没有虚拟偏移也没有删除操作，只要比较第一个节点
    // 是否和 off 相连接即可

    if (lastbyte=ch1) and (off>0) then
       exit;  //重复项已记录

    offentry:=SortTable[ch1 * 256 + ch2];
    if offentry=$FFFF then
       SortTable[ch1 * 256 + ch2]:=off
    else
    begin
      while SortFAT[offentry]<>$FFFF do
        offentry:=SortFAT[offentry];
      SortFAT[offentry]:=off;
    end;
  end;
  lastbyte:=ch1;
end;

procedure TLZ77Compress._OutCode(dest: PChar; code: DWord; bits: integer;
  isGamma: boolean);
var
 pb:PChar;
 aout,dw:DWORD;
 GammaCode,q,sh:integer;
begin
  if isGamma then
  begin
    // 计算输出位数
    GammaCode :=code - 1;
    q := LowerLog2(GammaCode);
    if (q > 0) then
    begin
      aout := $ffff;
      pb := PChar(@aout);
      // 输出q个1
      CopyBits(dest + CurByte, CurBit,
                    pb, 0, q);
      MovePos(CurByte, CurBit, q);
    end;
    // 输出一个0
    aout := 0;
    pb := PChar(@aout);
    CopyBits(dest + CurByte, CurBit, pb + 3, 7, 1);
    MovePos(CurByte, CurBit, 1);
    if (q > 0) then
    begin
            // 输出余数, q位
      sh := 1;
      sh :=sh shl q;
      aout := GammaCode - sh;
      pb := PChar(@aout);
      InvertDWord(@aout);
      CopyBits(dest + CurByte, CurBit,
                    pb + (32 - q) div 8, (32 - q) mod 8, q);
      MovePos(CurByte, CurBit, q);
    end;
  end else
  begin
    dw := code;
    pb := PChar(@dw);
    InvertDWord(@dw);
    CopyBits(dest + CurByte, CurBit,
                          pb + (32 - bits) div 8, (32 - bits) mod 8, bits);
    MovePos(CurByte,CurBit, bits);
  end;
end;

procedure TLZ77Compress._ScrollWindow(n: integer);
var
  i:integer;
begin
  for i := 0 to n-1 do
  begin
    inc(nWndSize);
    if (nWndSize > 1) then
      _InsertIndexItem(nWndSize - 2);
  end;
end;

function TLZ77Compress._SeekPhase(src: PChar; srclen, nSeekStart: integer;
  var offset, len: Integer): boolean;
var
  j, m, n:integer;
  ch1, ch2:byte;
  p:word;
begin
  if (nSeekStart < srclen - 1) then
  begin
    ch1 := byte(src[nSeekStart]);
    ch2 := byte(src[nSeekStart + 1]);
    p := SortTable[ch1 * 256 + ch2];
    if (p <> $FFFF) then
    begin
      m := 2;
      n := p;
      while (p <> $FFFF) do
      begin
        j := _GetSameLen(src, srclen,
                      nSeekStart, p);
        if ( j > m ) then
        begin
          m := j;
          n := p;
        end;
        p := SortFAT[p];
      end;
      offset := n;
      len := m;
      result:= TRUE;
      exit;
    end;
  end;
  result:=false;

end;

function TLZ77Compress.Compress(src: PChar; srclen: integer;
  dest: PChar): integer;
var
  i ,off, len,destlen:integer;


begin
  CurByte := 0;
  CurBit := 0;
  if (srclen > 65536) then
  begin
    result:=-1;
    exit;
  end;

  pWnd := src;
  _InitSortTable();


  i:=0;
  while i<srclen do
  begin
    if (CurByte >= srclen) then
    begin
      result:=0;
      exit;
    end;
    if _SeekPhase(src, srclen, i, off, len) then
    begin

      // 输出匹配术语 flag(1bit) + len(γ编码) + offset(最大16bit)
      _OutCode(dest, 1, 1, FALSE);
      _OutCode(dest, len, 0, TRUE);

      // 在窗口不满64k大小时，不需要16位存储偏移
      _OutCode(dest, off, UpperLog2(nWndSize), FALSE);

      _ScrollWindow(len);
      inc(i,len - 1);
    end else
    begin
    // 输出单个非匹配字符 0(1bit) + char(8bit)

      _OutCode(dest, 0, 1, FALSE);
      _OutCode(dest, Dword(src[i]), 8, FALSE);
      _ScrollWindow(1);

    end;
    inc(i);
  end;

  destlen := CurByte;
  if CurBit>0 then inc(destlen);
  if (destlen >= srclen) then result:=0 else result:=destlen;


end;

function TLZ77Compress.DeCompress(src: PChar; srclen: integer;
  dest: PChar): boolean;
var
  i,q,len, off,bits,j:integer;
  b:byte;

  dw:DWORD;
  pb:PChar;

begin
  CurByte := 0;
  CurBit := 0;
  pWnd := src;		// 初始化窗口
  nWndSize := 0;
  if (srclen > 65536) then
  begin
    result:=false;
    exit;
  end;
  i:=0;
  while i<srclen do
  begin
    b := GetBit(byte(dest[CurByte]), CurBit);
    MovePos(CurByte, CurBit, 1);
    if (b = 0) then// 单个字符
    begin
       CopyBits(src + i, 0, dest + CurByte, CurBit, 8);
       MovePos(CurByte, CurBit, 8);
       inc(nWndSize);

    end else		// 窗口内的术语
    begin
      q := -1;
      while (b <> 0) do
      begin
        inc(q);
        b := GetBit(byte(dest[CurByte]), CurBit);
        MovePos(CurByte, CurBit, 1);
      end;
      dw := 0;
      if (q > 0) then
      begin
        pb := PChar(@dw);
        CopyBits(pb + (32 - q) div 8, (32 - q) mod 8, dest + CurByte, CurBit, q);
        MovePos(CurByte, CurBit, q);
        InvertDWord(@dw);
        len := 1;
        len :=len shl q;
        len :=len + integer(dw) +1;
      end else
        len := 2;

      // 在窗口不满64k大小时，不需要16位存储偏移
      dw := 0;
      pb :=  PChar(@dw);
      bits := UpperLog2(nWndSize);
      CopyBits(pb + (32 - bits) div 8, (32 - bits) mod 8, dest + CurByte, CurBit, bits);
      MovePos(CurByte, CurBit, bits);
      InvertDWord(@dw);
      off := dw;
      // 输出术语
      for j:=0 to len-1 do
      begin
        ASSERT(i + j <  srclen);
        ASSERT(off + j <  _MAX_WINDOW_SIZE);

        src[i + j] := pWnd[off + j];
      end;
      inc(nWndSize, len);
      inc(i,len - 1);
    end;
    // 滑动窗口
    if (nWndSize > _MAX_WINDOW_SIZE) then
    begin
      inc(pWnd, nWndSize - _MAX_WINDOW_SIZE);
      nWndSize := _MAX_WINDOW_SIZE;
    end;
    inc(i);
  end;
  result:=TRUE;

end;

end.