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

FreeMem(FBuffer, StreamBufferSize);

end;

inherited Destroy;

end;

Обратите внимание, что оба конструктора Create выделяют большой буфер байтов (размер которого не меньше 4 Кб), чтобы базовый поток был доступен только для блоков данных. Иначе говоря, мы будем осуществлять буферизацию базового потока. Следовательно, метод Destroy должен освобождать этот буфер, убедившись, что на момент вывода потока битов любые все еще буферизованные данные записаны в базовый поток.

Обратите внимание на ссылку на своеобразное поле класса FStrmBroken. Оно служит средством обхода возможного условия ошибки. Предположим, что базовым потоком был экземпляр TFileStream, и что во время использования выходного потока битов имело место переполнение диска. В этом случае требуется запись выходного потока битов, сигнализирующего о подобной проблеме как об исключительной ситуации. Как только это исключение сгенерировано, дальнейшие попытки записи в базовый поток лишены всякого смысла, поэтому код устанавливает значение поля FStrmBroken равным true, сигнализируя о прерывании потока.

После того, как мы научились создавать и уничтожать потоки битов, следует рассмотреть задачу считывания и записи отдельного бита. Код выполнения считывания отдельного бита показан в листинге 11.3. Метод ReadBit возвращает булево значение - true, если следующий считанный из потока бит был установлен, и false в противном случае.

Мы используем байт маски (FMask), содержащий единственный бит установки и выполняем операцию AND (n) для этой маски и текущего байта (FAccum) из базового потока. Если результат отличен от нуля, бит в байте был установлен, и мы должны вернуть значение true. Если он равен нулю, бит в байте был очищен, и мы возвращаем значение false. Затем мы выполняем сдвиг маски влево на один бит, чтобы выдвинуть единственный бит маски на одну позицию. Если в момент начала процесса маска была нулевой, это означает, что нужно выполнить считывание нового байта из буфера и сбросить маску. Если буфер был пуст или был полностью считан, необходимо выполнить считывание из базового потока с целью заполнения следующего буфера.

Листинг 11.3. Считывание отдельного бита из объекта TtdInputBitStream

function TtdInputBitStream.ReadBit : boolean;

begin

{если в текущей аккумуляторной переменной никаких битов не осталось, необходимо выполнить считывание следующего байта аккумуляторной переменной и сбросить значение маски}

if (FMask = 0) then begin

if (FBufPos >= FBufEnd) then

ibsReadBuffer;

FAccum := byte(FBuffer [FBufPos] );

inc(FBufPos);

FMask := 1;

end;

{извлечь следующий бит}

Result := (FAccum and FMask) <> 0;

FMask := FMask shl 1;

end;

После того, как мы выяснили, как выполняется считывание отдельного бита, покажем, что запись отдельного бита - тот же самый процесс, только выполняемый в обратном порядке. Код метода WriteBit, в котором единственный бит передается как булево значение - true, если бит установлен, и false, если он очищен - приведен в листинге 11.4.

Листинг 11.4. Запись отдельного бита в объект TtdOutputBitStream

procedure TtdOutputBitStream.WriteBit(aBit : boolean);

begin

{установить следующий свободный бит}

if aBit then

FAccum := (FAccum or FMask);

FMask := FMask shl 1;

{/при отсутствии свободных битов в текущей аккумуляторной переменной ее значение нужно записать в буфер и сбросить значение аккумуляторной переменной и маски}

if (FMask = 0) then begin

byte(FBuffer[FBufPos]) := FAccum;

inc(FBufPos);

if (FBufPos >= StreamBufferSize) then

obsWriteBuffer;

FAccum := 0;

FMask := 1;

end;

end;

Поскольку обработка всегда начинается при значении аккумуляторного байта (FAccum) равном нулю, нужно всего лишь записать эти биты установки, а не очистить их. Мы снова используем маску (EMask), содержащую единственный бит установки, но на этот раз чтобы установить соответствующий бит, после чего выполняем операцию OR (ИЛИ) между маской и значением аккумуляторной переменной. Затем мы сдвигаем маску влево на один бит, подготавливая к обработке следующий бит. Однако если теперь значение маски равно нулю, потребуется сохранить аккумуляторный байт в буфере (записывая буфер в базовый поток, если буфер полон), а затем сбросить значение аккумуляторного байта и маски.

Полный код обоих классов TtdInputBitStrem и TtdOutputBitStrem можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStrms.pas. Полный код содержит также подпрограммы одновременного считывания и записи нескольких битов - либо восьми битов отдельного байта (ReadByte и WriteByte), либо переменного числа байтов из массива байтов (ReadBits и WriteBits). Для доступа к отдельным битам все эти дополнительные подпрограммы используют одну и ту же методологию манипуляции битами. Просто соответствующие операции выполняются в цикле.

Сжатие с минимальной избыточностью