После того, как мы научились создавать и уничтожать потоки битов, следует рассмотреть задачу считывания и записи отдельного бита. Код выполнения считывания отдельного бита показан в листинге 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). Для доступа к отдельным битам все эти дополнительные подпрограммы используют одну и ту же методологию манипуляции битами. Просто соответствующие операции выполняются в цикле.
Теперь, когда в нашем распоряжении имеется класс потока битов, им можно воспользоваться при рассмотрении алгоритмов сжатия и восстановления данных. Мы начнем с исследования алгоритмов кодирования с минимальной избыточностью, а затем рассмотрим более сложное сжатие с применением словаря.
Мы приведем подробное описание трех алгоритмов кодирования с минимальной избыточностью: кодирование Шеннона-Фано (Shannon-Fano), кодирование Хаффмана (Huffman) и сжатие с применением скошенного дерева (splay tree compression), однако рассмотрим реализации только последних двух алгоритмов (алгоритм кодирования Хаффмана ни в чем не уступает, а кое в чем даже превосходит алгоритм кодирования Шеннона-Фано). При использовании каждого из этих алгоритмов входные данные анализируются как поток байтов, и различным значениям байтов тем или иным способом присваиваются различные последовательности битов.