c - 如何编写比特流

Question

我正在考虑使用C将一些数据写入位流。有两种方法可以想到。一种是将可变位长符号连接成一个连续的位序列，但这样我的解码器可能很难将这些符号从这个连续的位流中分离出来。另一种方法是为哪个符号分配相同数量的比特，这样解码器可以轻松恢复原始数据，但可能会浪费比特，因为符号具有不同的值，这反过来会导致比特流中的许多比特零（我猜这是浪费位）。

任何提示我应该做什么？

我是编程新手。任何帮助将不胜感激。

Answer 1

听起来您正在尝试做一些类似于 Huffman 压缩方案的事情？我会逐字节（char）并跟踪我读取最后一个符号的字节内的偏移量。

假设您的任何符号都不会大于 char。它看起来像这样：

struct bitstream {
   char *data;
   int data_size;           // size of 'data' array
   int last_bit_offset;     // last bit in the stream 

   int current_data_offset; // position in 'data', i.e. data[current_data_offset] is current reading/writing byte
   int current_bit_offset;  // which bit we are currently reading/writing
}

char decodeNextSymbol(bitstream *bs) {

}

int encodeNextSymbol(bitstream *bs, char symbol) {

}

decodeNextSymbol 和 encodeNextSymbol 的匹配代码必须使用 C 按位​​运算（例如，'&'（按位与）和 '|'（按位或）。然后我会列出所有符号的列表，以最短的优先，然后做一个匹配最短符号的while循环。例如，如果你的一个符号是'101'，那么如果流是'1011101'，它将匹配第一个'101'并继续匹配流“1101”的其余部分您还必须处理符号值从一个字节溢出到下一个字节的情况。