...

Вы можете удивиться, почему интерфейс BitBuffer определен с использованием указателей на unsigned char. Во-первых, в стандарте С++ нет такой веши, как указатель на бит. Во-вторых, стандарт С++ гарантирует, что операции над беззнаковыми типами (включая unsigned char, unsigned short, unsigned int и unsigned long) и с будут вызывать сообщения компилятора типа Вы не инициализировали этот байт! или Это некорректное значение! . Бьярн Страуструп пишет в [StroustrupOO]:

Беззнаковые целые типы идеально подходят для использования в качестве хранилища

для битового массива.

От компиляторов требуется предоставить юзможность рассматривать unsigned char (как и другие беззнаковые типы) как просто хранилище набора битов -- именно то, что нам и требуется. Имеются и другие подходы, но данный подход позволит нам получить навыки программирования работы с отдельными битами, что и является основной целью данной задачи.

Главный вопрос при реализации BitBuffer - какое внутреннее представление следует использовать? Я рассмотрю две основные альтернативы.

Попытка №1: использование unsigned char

Первая мысль - реализовать BitBuffer с использованием большого внутреннего блока unsigned char, и самостоятельно работать с отдельными битами при их размещении и выборке. Мы можем позволить классу BitBuffer иметь член типа unsigned char*, который указывал бы на буфер, но, тем не менее, давайте воспользуемся вектором vector<unsigned char>, чтобы не заботиться о вопросах распределения памяти.

Вам кажется, что все это звучит очень просто? Если да - значит, вы не пытались реализовать (и протестировать!) сказанное. Потратьте на это два-три часа, и вновь вернитесь к данной задаче? Я готов держать пари, что больше вы так не скажете.

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

И вот результат. Я не говорю, что он идеален, но он прошел все мои тесты, включая добавление одного и нескольких битов и некоторые граничные случаи. Обратите внимание, что эта версия исходного текста работает одновременно с блоками байтов - например, если мы используем 8-биговые байты и имеем смещение, равное 3 битам, то мы копируем первые три бита как отдельную единицу, и так же поступаем с последними 5 битами, получая 2 операции на байт. Для простоты я также требую, чтобы пользователь предоставлял буферы на байт большие, чем необходимо. Таким образом, я могу упростить свой код, позволив ему работать за концом буфера.

пример 27-1: реализация BitBuffer с использованием vector<unsigned char>. трудная,

скрупулезная работа. Брр...

class BitBuffer { public:

BitBufferC) : buf (0), size (0) { }

Добавление num битов, начиная с первого бита р.

void Append( unsigned char* p, size t num ) {

int bits = numeric limits<unsigned char>::digits;

первый байт назначения и смещение бита 180 Оптимизация и эффективность

int dst = size / bits; i nt off = size % bi ts;

whileC buf .size() < (size +num) / bits + 1 )

buf .push back( 0 ); for( int i = 0; i < (num+bits-l)/bits; ++i ) {

unsigned char mask = FirstBits(num - bits*i);

buf [dst+i] 1= (*(p+i) & mask) off;

if( off > 0 )

buf [dst+i+l] = (*(p+i) & mask) (bits-off);

size += num;

Запрос количества используемых битов

(изначально ноль).

size t SizeC) const { return size ;

получение num битов, начиная с start-го бита

(нумерация начинается с 0), и сохранение результата

начиная с первого бита dst. Буфер, на который

указывает dst, должен быть по крайней мере на один

байт больше, чем минимально необходимый для хранения

num битов.

void Get(size t start, si2e t num, unsigned char* dst) const {

i nt bi ts = numeric limits<unsigned char>::digits;

первый исходный байт и смещение бита int src = start / bits; int off = start % bits;

for( int i = 0; i < (num+bits~l)/bits; ++i ) {

*(dst+i) = buf.....[src+i] off;

if( off > 0 )

*(dst+i) 1= buf [src+i+l] (bits - off);

private:

vector<unsigned char> buf ; size t size ; in bi ts

Создание маски, в которой первые п битов равны 1, а остальные - 0.

unsigned char FirstBits( size t n ) {

int num=min(n,numeric limits<unsigned char>::digits); unsigned char b = 0; while( num-- > 0 ) b = (b 1) I

(l (numeric limits<unsigned char>: :digits-l)) ; return b;

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

Вероятно, разобраться в приведенном исходном тексте (а кое-где даже улучшить его) вам поможет знакомство с книгой [Warien03]. - Прим. ред.

ее наличие. Если наличие ошибки подтвердится - прошу вас, отправьте мне сообщение об ошибке вместе с вашей тестовой профаммой, демонстрирующей наличие ошибки.)

Попытка №2: использование стандартного контейнера упакованных битов

Вторая идея заключается в том, чтобы обратить внимание на то, что стандартная библиотека уже содержит два контейнера для хранения битов: bitset и vector<bool>. Для наших целей bitset - плохой вариант, поскольку bitset<N> имеет фиксированную длину N, а мы должны работать с потоками битов переменной длины. Не получается... Зато vector<bool>, несмотря на все его недостатки в данном случае оказывается тем, что доктор прописал . (Конечно, стандарт не требует, ггобы реализация vector<bool> использовала упакованные беты, а только поощряет это. Тем не менее, большинство реализаций именно так и поступают.)

Самое главное, что я могу сказать о приведенном далее исходном тексте, - это то, что исходный текст примера 27-2 был совершенно корректен при первом его написании.

Да, именно так. Все, что я сделал между первой компиляцией и окончательной версией исходного текста - это исправление несколько мелких синтаксических опечаток, в частности, добавление пропущенной точки с запятой и пары скобок там, где я упустил из виду, что приоритет оператора % выше приоритета оператора +. Вот этот исходный текст.

Пример 27-2: Реализация BitBuffer с использованием

vector<bool>.

class BitBuffer { public:

добавление num битов, начиная с первого бита р.

void AppendC unsigned char* p, size t num ) {

int bits = numeric limits<unsigned char>::digits; for( int i =0; i < num; ++i ) {

buf .push back( *p & (1 (bits-1 - i%bits)) ); if( (i+1) % bits == 0 ) ++p;

Запрос количества используемых битов (изначально ноль). size t size О const { return buf .sizeO;

получение num битов, начиная с start-ro бита

(нумерация начинается с 0), и сохранение результата

начиная с первого бита dst.

void Get( size t start, size t num, unsigned char* dst ) const {

int bits = numeric limits<unsigned char>::digits; *dst = 0;

for( int i = 0; i < num; ++i ) {

*dst i= unsigned char(buf [start+i])

(bits-1 - i%bits); if( (i+1) % bits == 0 ) *++dst = 0;

private:

Более подробно вопрос о vector<bOOl> рассмотрен в [Suttert)21 (задача 1.13 в русском издании). - Прим. ред.