Потоки битов

Потоки битов

Прежде чем приступить к исследованию реальных алгоритмов сжатия, необходимо кратко рассмотреть задачу манипулирования битами. При использовании большинства алгоритмов сжатия, которые будут рассмотрены, сжатие данных выполняется с использованием переменного количества битов, независимо от того, рассматриваются ли данные в качестве последовательности символов или лексем. Нельзя считать, что байты всегда будут состоять из групп по 8 битов.

Нам потребуется выполнять две базовых операции: считывание отельного бита и запись отдельного бита. На основе этих операций можно было бы построить операции, выполняющие считывание и запись сразу нескольких битов. Поэтому мы разработаем и создадим поток битов (bit stream) - структуру данных, содержащую в себе набор битов. Понятно, что поток битов будет использовать еще одну структуру данных, в которой данные битов хранятся в виде последовательности байтов. Эта структура будет извлекать биты в соответствии с байтами в данных, на основе которых она построена. Поскольку мы используем Delphi, в качестве базовой структуры данных потока битов мы выберем объект TStream (или производный от него). В результате, например, мы смогли бы рассматривать поток памяти или поток файла как поток битов. Фактически, поскольку потоки битов будут использоваться только в качестве последовательных групп битов, мы создадим два различных типа: входной поток битов и выходной поток битов. Кроме того, можно избавиться от обычно используемого метода Seek, поскольку поиск в потоке битов мы выполнять не будем.

Код интерфейса классов TtdInputBitStream и TtdOutputBitStream приведен в листинге 11.1.

Листинг 11.1. Интерфейс классов потоков битов

type

TtdInputBitStream = class private

FAccum : byte;

FBufEnd : integer;

FBuffer : PAnsiChar;

FBufPos : integer;

FMask : byte;

FName : TtdNameString;

FStream : TStream;

protected

procedure ibsError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure ibsReadBuffer;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

function ReadBit : boolean;

procedure ReadBits(var aBitString : TtdBitString; aBitCount : integer);

function ReadByte : byte;

property Name : TtdNameString read FName write FName;

end;

TtdOutputBitStream = class private

FAccum : byte;

FBuffer : PAnsiChar;

FBufPos : integer;

FMask : byte;

FName : TtdNameString;

FStream : TStream;

FStrmBroken : boolean;

protected

procedure obsError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure obsWriteBuffer;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

procedure WriteBit(aBit : boolean);

procedure WriteBits(const aBitString : TtdBitString);

procedure WriteByte(aByte : byte);

property Name : TtdNameString read FName write FName;

end;

Оба конструктора Create требуют передачи им в качестве параметра уже созданного производного объекта TStream. Из этого потока байтов класс потока битов будет извлекать или сохранять отдельные байты. Код конструкторов Create и деструкторов Destroy этих классов приведен в листинге 11.2.

Листинг 11.2. Создание и уничтожение объектов потока битов

constructor TtdInputBitStream.Create(aStream : TStream);

begin

inherited Create;

FStream := aStream;

GetMem(FBuffer, StreamBufferSize);

end;

destructor TtdInputBitStream.Destroy;

begin

if (FBuffer <> nil) then

FreeMem(FBuffer, StreamBufferSize);

inherited Destroy;

end;

constructor TtdOutputBitStream.Create(aStream : TStream);

begin

inherited Create;

FStream := aStream;

GetMem(FBuffer, StreamBufferSize);

FMask := 1;

{подготовиться к записи первого бита}

end;

destructor TtdOutputBitStream.Destroy;

begin

if (FBuffer <> nil) then begin

{если значение Mask не равно 1, это означает присутствие в аккумуляторной переменной каких-то бит, которые требуется записать в буфер. Следует убедиться, что буфер записывается в базовый поток}

if not FStrmBroken then begin

if (FMasko 1) then begin

byte(FBuffer[FBufPos]) := FAccum;

inc(FBufPos);

end;

if ( FBuf Pos > 0 ) then

obsWriteBuffer;

end;

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). Для доступа к отдельным битам все эти дополнительные подпрограммы используют одну и ту же методологию манипуляции битами. Просто соответствующие операции выполняются в цикле.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Облегченные потоки

Из книги автора

Облегченные потоки Примечание Облегченные потоки относятся к специальной тематике. Ознакомьтесь с комментарием, включенным в конце первого абзаца приведенного ниже списка, и решите для себя, стоит ли вам читать данный раздел. Облегченные потоки (fibers), как говорит само


Потоки

Из книги автора

Потоки Последующие расширения[14] POSIX специфицируют широкий спектр механизмов «легких процессов» — потоков (группа API pthread_*()). Техника потоков вводит новую парадигму программирования вместо уже ставших традиционными UNIX-методов. Это обстоятельство часто недооценивается.


10.4 ПОТОКИ

Из книги автора

10.4 ПОТОКИ Схема реализации драйверов устройств, хотя и отвечает заложенным требованиям, страдает некоторыми недостатками, которые с годами стали заметнее. Разные драйверы имеют тенденцию дублировать свои функции, в частности драйверы, которые реализуют сетевые


Редактирование отдельных битов значения параметра

Из книги автора

Редактирование отдельных битов значения параметра Это довольно интересная и, можно сказать, уникальная возможность, с помощью которой можно изменить отдельный бит параметра, не изменяя другие его биты. Для реализации этой возможности применяется ключевое слово BitReg,


Потоки

Из книги автора

Потоки Хотя концепция процессов в системах Unix используется уже очень давно, возможность использовать несколько потоков внутри одного процесса появилась относительно недавно. Стандарт потоков Posix.1, называемый Pthreads, был принят в 1995 году. С точки зрения взаимодействия


38. Потоки

Из книги автора

38. Потоки Язык C++ не обладает средствами для ввода/вывода. Ему это и не нужно; подобные средства легко и элегантно можно создать, применяя сам язык. Стандартная библиотека потокового ввода/вывода дает возможность осуществлять гибкий и эффективный с гарантией типа метод


7.3.1.2. Потоки

Из книги автора

7.3.1.2. Потоки Потоки (streams) сетевого взаимодействия были разработаны Деннисом Ритчи для Unix Version 8 (1985). Их новая реализация называется STREAMS (именно так, в документации все буквы прописные). Впервые она стала доетупной в версии 3.0 System V Unix (1986). Средство STREAMS обеспечивало


7.3.1.2. Потоки

Из книги автора

7.3.1.2. Потоки Потоки (streams) сетевого взаимодействия были разработаны Деннисом Ритчи для Unix Version 8 (1985). Их новая реализация называется STREAMS (именно так, в документации все буквы прописные). Впервые она стала доступной в версии 3.0 System V Unix (1986). Средство STREAMS обеспечивало


2.2.1.1 Потоки

Из книги автора

2.2.1.1 Потоки Архитектуру INFORMIX-OnLine DS называют также многопотоковой. Для каждого клиента создается так называемый поток, или нить (thread). Поток - это подзадача, выполняемая в рамках одного из серверных процессов. В некоторых случаях для обслуживания одного клиентского


Глава 8 Потоки

Из книги автора

Глава 8 Потоки ``bad input char: .Ppm(*=P!..*@Z9A*)5!!!!!"syui!!!"!Mp#V6P?p8`;!4lf amp; сообщение об ошибке (сокращенное) Язык С++ не обеспечивает средств для ввода/вывода. Ему это и не нужно. Такие средства легко и элегантно можно содать с помощью самого языка. Описанная здесь стандартная билиотека


8.3 Файлы и Потоки

Из книги автора

8.3 Файлы и Потоки Потоки обычно связаны с файлами. Библиотека потоков содает стандартный поток ввода cin, стандартный поток вывода cout и стандартный поток ошибок cerr. Программист может отрывать другие файлы и создавать для них


1.6.2. Установка битов SUID и SGID

Из книги автора

1.6.2. Установка битов SUID и SGID Чтобы установить бит SUID, вставьте цифру 4 перед числом, задающим режим доступа. Биту SGID соответствует цифра 2. Если одновременно устанавливаются оба бита, следует ввести цифру 6 (4 + 2).В строке режима установленные биты SUID и SGID обозначаются


Распад битов[225] Марк Дери[226]

Из книги автора

Распад битов[225] Марк Дери[226] В медиатусовке мало кто расстроился, узнав о его уходе, но вот лично автор этой статьи сожалеет о том, что мы уже не сможем придираться к Хитрому Нику. В декабре 1998 года Николас Негропонте из Wired, директор Лаборатории медиа Массачусетского


Часть четвертая Возьмем от битов лучшее

Из книги автора

Часть четвертая Возьмем от битов лучшее В этом разделе я переключусь на более позитивную перспективу, опишу отличия кибернетического тотализма от гуманизма, рассмотрев эволюцию культуры человека.Я надеюсь показать, что каждый способ мышления имеет свое законное место