You have to keep track of two states: The bits you write for each character, whose number will vary according to the characher's level in the tree and the 8-bit chunks that you write to. You will need to fiddle with the output chunks on the bit level.
There are various approaches. Here's a solution that writes the bits one at a time by shifting a data bit and appending the bit to write. When the data bit is full, it is written to the 8-bit-chunk output sink. The code below checks for data bit overflow with a sentinel bit, that eventually is shifted out of the 8-bit range:
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;
}
The flush()
ensures that bits that are still in the data byte are written out by padding the Huffman sequence with zero bits.
The actual bit output works like this:
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
For this to work, the data bit has to be stored in an integer that can hold more bits than a byte.
You could also keep track of the byte state with a separate variable. Writing bits one by one is probably not efficient, but straightforward.