abdfhufd.pas

Lazarus is a free and open source development tool for the FreePascal Compiler. The purpose of the p

      FMaxCodeLen := CodeLen;
    inc(LengthCount[CodeLen]);
  end;

  {now we know the maximum code length we can allocate our decoder
   array}
  if (FUsage <> huEncoding) then begin
    DecoderLen := PowerOfTwo[FMaxCodeLen];
    GetMem(FDecodes, DecoderLen * sizeof(longint));
    DecodesEnd := PAnsiChar(FDecodes) + (DecoderLen * sizeof(longint));
    {$IFOPT C+}
    FillChar(FDecodes^, DecoderLen * sizeof(longint), $FF);
    FMask := not (DecoderLen - 1);
    {$ENDIF}
  end;

  {calculate the start codes for each code length}
  Code := 0;
  LengthCount[0] := 0;
  for i := 1 to FDefMaxCodeLen do begin
    Code := (Code + LengthCount[i-1]) shl 1;
    NextCode[i] := Code;
  end;

  {for speed and convenience}
  Decodes := FDecodes;
  Encodes := FEncodes;
  TablePtr := @ByteRevTable;

  {for each symbol...}
  for Symbol := 0 to pred(aCount) do begin
    {calculate the code length}
    CodeLen := aCodeLengths[Symbol + aStartInx];

    {if the code length were zero, just set the relevant entry in the
     encoder array; the decoder array doesn't need anything}
    if (CodeLen = 0) then begin
      if (FUsage <> huDecoding) then
        Encodes^[Symbol] := -1
    end

    {otherwise we need to fill elements in both the encoder and
     decoder arrays}
    else begin
      {calculate *reversed* code}
      Code := NextCode[CodeLen];
      asm
        push esi
        mov eax, Code
        mov esi, TablePtr
        xor ecx, ecx
        xor edx, edx
        mov cl, ah
        mov dl, al
        mov al, [esi+ecx]
        mov ah, [esi+edx]
        mov ecx, 16
        pop esi
        sub ecx, CodeLen
        shr eax, cl
        mov Code, eax
      end;

      {set the code data (bit count, extra bits required, symbol),
       everywhere the reversed code would appear in the decoder array;
       set the code data in the encoder array as well}
      if (Symbol >= aExtraOffset) then begin
        if (FUsage <> huEncoding) then
          CodeData := Symbol +                  { symbol}
                      (CodeLen shl 16) +        { code length}
                      (aExtraBits[Symbol-aExtraOffset] shl 24);
                                                { extra bits required}
        if (FUsage <> huDecoding) then
          Encodes^[Symbol] := Code +            { code}
                      (CodeLen shl 16) +        { code length}
                      (aExtraBits[Symbol-aExtraOffset] shl 24)
                                                { extra bits required}
      end
      else begin
        if (FUsage <> huEncoding) then
          CodeData := Symbol +                  { symbol}
                      (CodeLen shl 16);         { code length}
        if (FUsage <> huDecoding) then
          Encodes^[Symbol] := Code +            { code}
                      (CodeLen shl 16);         { code length}
      end;

      {OPTIMIZATION NOTE: the following code

            CodeIncr := PowerOfTwo[CodeLen];
            while Code < DecoderLen do begin
              Decodes^[Code] := CodeData;
              inc(Code, CodeIncr);
            end;

      was replaced by the asm code below to improve the speed. The
      code in the loop is the big time sink in this routine so it was
      best to replace it.}
      if (FUsage <> huEncoding) then begin
        CodeIncr := PowerOfTwo[CodeLen] * sizeof(longint);
        asm
          push edi                { save edi}
          mov eax, Decodes        { get the Decodes array}
          mov edi, DecodesEnd     { get the end of the Decodes array}
          mov edx, Code           { get Code and..}
          shl edx, 1              { ..multiply by 4}
          shl edx, 1
          add eax, edx            { eax => first element to be set}
          mov edx, CodeData       { get the CodeData}
          mov ecx, CodeIncr       { get the increment per loop}
        @@1:
          mov [eax], edx          { set the element}
          add eax, ecx            { move to the next element}
          cmp eax, edi            { if we haven't gone past the end..}
          jl @@1                  { ..go back for the next one}
          pop edi                 { retrieve edi}
        end;
      end;

      {we've used this code up for this symbol, so increment for the
       next symbol at this code length}
      inc(NextCode[CodeLen]);
    end;
  end;
end;
{--------}
{$IFDEF UseLogging}
procedure TAbDfDecodeHuffmanTree.DebugPrint(aLog : TAbLogger);
{$IFDEF EnableMegaLog}
var
  i : integer;
  Code : longint;
{$ENDIF}
begin
  {to print the huffman tree, we must have a logger...}
  Assert(aLog <> nil,
         'TAbDfDecodeHuffmanTree.DebugPrint needs a logger object to which to print');

  if (FUsage <> huEncoding) then begin
    aLog.WriteLine('Huffman decoder array');
    aLog.WriteLine(Format('Alphabet size:  %d', [FAlphaSize]));
    aLog.WriteLine(Format('Max codelength: %d', [FMaxCodeLen]));

    {$IFDEF EnableMegaLog}
    aLog.WriteLine('Index Len Xtra Symbol                    Reversed Code');
    for i := 0 to pred(PowerOfTwo[FMaxCodeLen]) do begin
      Code := FDecodes^[i];
      if (Code = -1) then
        aLog.WriteLine(Format('%5d%49s', [i, 'no code']))
      else
        aLog.WriteLine(Format('%5d%4d%5d%7d%33s',
                       [i,
                        ((Code shr 16) and $FF),
                        ((Code shr 24) and $FF),
                        (Code and $FFFF),
                        CodeToStr(i, ((Code shr 16) and $FF))]));
    end;
    aLog.WriteLine('---end decoder array---');
    {$ENDIF}
  end;

  if (FUsage <> huDecoding) then begin
    aLog.WriteLine('Huffman encoder array');
    aLog.WriteLine(Format('Alphabet size: %d', [FAlphaSize]));

    {$IFDEF EnableMegaLog}
    aLog.WriteLine('Symbol Len Xtra                    Reversed Code');
    for i := 0 to pred(FAlphaSize) do begin
      Code := FEncodes^[i];
      if (Code = -1) then
        aLog.WriteLine(Format('%6d%42s', [i, 'no code']))
      else
        aLog.WriteLine(Format('%6d%4d%5d%33s',
                       [i,
                        ((Code shr 16) and $FF),
                        ((Code shr 24) and $FF),
                        CodeToStr((Code and $FFFF), ((Code shr 16) and $FF))]));
    end;
    aLog.WriteLine('---end encoder array---');
    {$ENDIF}
  end;
end;
{$ENDIF}
{--------}
function TAbDfDecodeHuffmanTree.Decode(aLookupBits : integer) : longint;
begin
  {protect against dumb programming mistakes (note: FMask only exists
   if assertions are on)}
  {$IFOPT C+}
  Assert((aLookupBits and FMask) = 0,
         'TAbDfDecodeHuffmanTree.Decode: trying to decode too many bits, use LookupBitLength property');
  {$ENDIF}

  {return the code data}
  Result := FDecodes^[aLookupBits];
end;
{--------}
function TAbDfDecodeHuffmanTree.Encode(aSymbol : integer) : longint;
begin
  {protect against dumb programming mistakes}
  Assert((0 <= aSymbol) and (aSymbol < FAlphaSize),
         'TAbDfDecodeHuffmanTree.Encode: trying to encode a symbol that is not in the alphabet');

  {return the code data}
  Result := FEncodes^[aSymbol];

  {if the result is -1, it's another programming mistake: the user is
   attempting to get a code for a symbol that wasn't being used}
  Assert(Result <> -1,
         'TAbDfDecodeHuffmanTree.Encode: trying to encode a symbol that was not used');
end;
{====================================================================}


{===BuildStaticTrees=================================================}
procedure BuildStaticTrees;
var
  i        : integer;
  CodeLens : array [0..287] of integer;
begin
  {this routine builds the static huffman trees, those whose code
   lengths are determined by the deflate spec}

  {the static literal tree first}
  for i := 0 to 143 do
    CodeLens[i] := 8;
  for i := 144 to 255 do
    CodeLens[i] := 9;
  for i := 256 to 279 do
    CodeLens[i] := 7;
  for i := 280 to 287 do
    CodeLens[i] := 8;
  AbStaticLiteralTree := TAbDfDecodeHuffmanTree.Create(288, 15, huBoth);
  AbStaticLiteralTree.Build(CodeLens, 0, 288,
                            dfc_LitExtraBits, dfc_LitExtraOffset);

  {the static distance tree afterwards}
  for i := 0 to 31 do
    CodeLens[i] := 5;
  AbStaticDistanceTree := TAbDfDecodeHuffmanTree.Create(32, 15, huBoth);
  AbStaticDistanceTree.Build(CodeLens, 0, 32,
                             dfc_DistExtraBits, dfc_DistExtraOffset);
end;
{====================================================================}

initialization
  BuildStaticTrees;

finalization
  AbStaticLiteralTree.Free;
  AbStaticDistanceTree.Free;
  
end.