Вы должны отслеживать два состояния: биты, которые вы пишете для каждого символа, количество которых будет варьироваться в зависимости от уровня символа в дереве, и 8-битные фрагменты, в которые вы пишете. Вам нужно будет поиграть с выходными блоками на битовом уровне.
Есть разные подходы. Вот решение, которое записывает биты по одному, сдвигая бит данных и добавляя бит для записи. Когда бит данных заполнен, он записывается в выходной приемник 8-битного блока. Приведенный ниже код проверяет переполнение битов данных с помощью сигнального бита, который в конечном итоге выходит за пределы 8-битного диапазона:
static unsigned int out = 0x01;
void write_bit(bool bit)
{
out <<= 1; // shift byte to make room
if (bit) out |= 0x01; // set lowest bit id desired
if (out & 0x100) { // was the sentinel bit shifted out?
write_byte(out & 0xff); // final output of 8-bit chunk
out = 0x01; // reset to sentinel vylue
}
}
void flush_bit()
{
while (out != 0x01) write_bit(false);
}
int main()
{
write_bit(1);
write_bit(0);
write_bit(1);
// ...
flush_bit();
return 0;
}
flush() гарантирует, что биты, которые все еще находятся в байте данных, будут записаны путем заполнения последовательности Хаффмана нулевыми битами.
Фактический битовый вывод работает следующим образом:
0000 0001 // initial state: one sentinel bit
0000 0011 // after writing a 1
0000 0110 // after writing a 0
1101 1111 // after writing five more 1s
1 1011 1110 // after writing a 0: data byte is full
// write 1011 1110 to final output
0000 0001 // reset data byte
Чтобы это работало, бит данных должен быть сохранен в виде целого числа, которое может содержать больше бит, чем байт.
Вы также можете отслеживать состояние байта с помощью отдельной переменной. Запись битов по одному, вероятно, неэффективна, но проста.
person
M Oehm
schedule
22.03.2014
