Фундаментальные алгоритмы и структуры данных в Delphi

FromChar := FCurrent - aDistance;

ToChar := FCurrent;

for i := 1 to aLength do

begin

ToChar^ := FromChar^;

inc(FromChar);

inc(ToChar);

end;

{сместить начало скользящего окна}

swAdvanceAfterAdd(aLength);

end;

procedure TtdLZSlidingWindow.swAdvanceAfterAdd(aCount : integer);

begin

{при необходимости сместить начало скользящего окна}

if ( (FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin

inc(FStart, aCount);

inc(FStartOffset, aCount);

end;

{сместить текущий указатель}

inc(FCurrent, aCount);

{проверить смещение в зону переполнения}

if (FStart >= FMidPoint) then begin

{записать дополнительные данные в поток (от позиции FBuffer до позиции FStart)}

swWriteToStream(false);

{переместить текущие данные обратно в начало буфера}

Move(FStart^, FBuffer^, FCurrent - FStart );

{сбросить различные указатели}

dec(FCurrent, FStart - FBuffer);

FStart := FBuffer;

end;

end;

procedure TtdLZSlidingWindow.swSetCapacity(aValue : longint);

var

NewQueue : PAnsiChar;

begin

{округлить запрошенный объем до ближайшего значения, кратного 64 байтам}

aValue := (aValue + 63) and $7FFFFFC0;

{распределить новый буфер}

GetMem(NewQueue, aValue * 2);

{уничтожить старый буфер}

if ( FBuffer <> nil ) then

FreeMem(FBuffer, FBufferEnd - FBuffer);

{установить начальный/конечный и другие указатели}

FBuffer := NewQueue;

FStart := NewQueue;

FCurrent := NewQueue;

FLookAheadEnd := NewQueue;

FBufferEnd := NewQueue + (aValue * 2);

FMidPoint := NewQueue + aValue;

end;

procedure TtdLZSlidingWindow.swWriteToStream(aFinalBlock : boolean);

var

BytesToWrite : longint;

begin

{записать данные перед текущим скользящим окном}

if aFinalBlock then

BytesToWrite := FCurrent - Fbuffer else

BytesToWrite := FStart - FBuffer;

FStream.WriteBuffer(FBuffer^, BytesToWrite);

end;

Метод AddChar добавляет одиночный литеральный символ в скользящее окно и сдвигает это окно вперед на один байт. Внутренний метод swAdvanceAfterAdd выполняет реальный сдвиг и после сдвига окна проверяет, может ли еще один блок быть записан в выходной поток. Метод AddCode добавляет пару расстояние/длина в скользящее окно, по одному копируя символы из уже декодированной части скользящего окна в текущую позицию. Затем скользящее окно сдвигается вперед.

Теперь достаточно легко создать код восстановления. (Создавать код восстановления раньше кода сжатия кажется несколько неестественным, но в действительности формат сжатых данных настолько определен, что это можно сделать. Кроме того, это проще!) Мы реализуем основной цикл в виде машины состояний с тремя состояниями: считывание и обработка байта флага, считывание и обработка символа и, наконец, считывание и обработка кода расстояния/длины. Код показан в листинге 11.24. Обратите внимание, что определение момента завершения восстановления осуществляется по количеству байтов в несжатом потоке, записанному программой сжатия в начало сжатого потока.

После проверки того, что входной поток является закодированным с применением алгоритма LZ77, программа считывает количество несжатых данных. Затем осуществляется вход в простую машину состояний, состояния которой определяются байтом флага, считываемого из входного потока. Если текущее состояние -dsGetFlagByte, программа считывает из входного потока следующий байт флага. Если состояние - dsGetChar, программа считывает из входного потока литеральный символ и добавляет его в скользящее окно. В противном случае состоянием будет dsGetDistLen, и программа считывает из входного потока пару расстояние/ длина и добавляет ее в скользящее окно. Этот процесс продолжается до тех пор, пока не будут восстановлены все данные входного потока.

Листинг 11.24. Основной код программы сжатия, использующей алгоритм LZ77

procedure TDLZDecompress(aInStream, aOutStream : TStream);

type

TDecodeState = (dsGetFlagByte, dsGetChar, dsGetDistLen);

var

SlideWin : TtdLZSlidingWindow;

BytesUnpacked : longint;

TotalSize : longint;

LongValue : longint;

DecodeState : TDecodeState;

FlagByte : byte;

FlagMask : byte;

NextChar : AnsiChar;

NextDistLen : longint;

CodeCount : integer;

Len : integer;

begin

SlideWin := TtdLZSlidingWindow.Create(aOutStream, false);

try

SlideWin.Name := 'LZ77 Decompress sliding window';

{считать из потока заголовок: символы 'TDLZ', за которыми следует размер входного потока}

aInStream.ReadBuffer(LongValue, sizeof(LongValue));

if (LongValue <> TDLZHeader) then

RaiseError(tdeLZBadEncodedStream, 'TDLZDecompress');

aInStream.ReadBuffer(TotalSize, sizeof(TotalSize));

{подготовиться к восстановлению}

BytesUnpacked := 0;

NextDistLen := 0;

DecodeState := dsGetFlagByte;

CodeCount := 0;

FlagMask := 1;

{до тех nop, пока остаются байты для восстановления...}

while (BytesUnpacked < TotalSize) do

begin

{считывать следующий элемент в данном состоянии декодирования}

case DecodeState of

dsGetFlagByte : begin

aInStream.ReadBuffer(FlagByte, 1);

CodeCount := 0;

FlagMask := 1;

end;

dsGetChar : begin

aInStream.ReadBuffer(NextChar, 1);

SlideWin.AddChar(NextChar);

inc(BytesUnpacked);

end;

dsGetDistLen : begin

aInStream.ReadBuffer(NextDistLen, 2);

Len := (NextDistLen and tdcLZLengthMask) + 3;

SlideWin.AddCode( (NextDistLen shr tdcLZDistanceShift) + 1, Len);

inc(BytesUnpacked, Len);

end;

end;

{вычислить следующее состояние декодирования}

inc(CodeCount);

if (CodeCount > 8) then