用于流式压缩算法的 C++ 快速位数组类

Question

实现流式压缩算法，通常需要一个具有以下功能的超快FIFO位容器类:

AddBits(UINT n, UINT nBits);  // Add lower nBits bits of n 
GetBitCount();                // Get the number of bits currently stored
GetBits(BYTE* n, UINT nBits); // Extract n Bits, and remove them

位数限制在相对较小的大小(“数据包”大小或更多)。

我正在寻找一个实现此功能的小型 C++ 类。

是的，我可以写一个(并且知道怎么做)，但可能已经有人写过了...

注意:我不想为此将 boost/whatever-big-lib 添加到我的项目中。

Answer 1

当我总是想一次读取 16 位或更少位时，我在嵌入式系统中使用的一种方法是保留一个 32 位长来保存当前的部分 16 位字，以及下一个完整的.然后代码是这样的:

/* ui=unsigned 16-bit ul=unsigned 32-bit   LT == less-than SHL = shift-left */

ul bit_buff;
ui buff_count;
ui *bit_src;

unsigned int readbits(int numbits)
{
  if (buff_count LT numbits)
  {
    bit_buff |= ((ul)(*bit_src++)) SHL buff_ct;
    buff_ct += 16;
  }
  buff_ct -= numbits;
  return bit_buff & ((1 SHL numbits)-1);
}

这可能很容易适应 64 位 long long 的使用，并允许一次提取多达 32 位。