1

Implementing streaming compression algorithms, one usually need a super-fast FIFO bit container class with the following functions:

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

The number of bits is bounded to a relatively small size (the 'packet' size or a bit more).

I'm looking for a small C++ class which implement this functionality.

Yes, I can write one (and know how to do it), but probably someone wrote it already...

Note: I don't want to add boost / whatever-big-lib to my project just for this.

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
  • what is wrong with boost? http://stackoverflow.com/questions/2633400/c-c-efficient-bit-array – Anycorn Aug 31 '10 at 18:31
  • 1
    for the most part boost is header only. you might be missing a lot of implemented functionality by not using it. have you looked at std::bitset – Anycorn Aug 31 '10 at 18:40
  • 1
    You don't want to use boost because adding it to your project will take longer than implementing the class? What about the next such small class, and the next one .... – torak Aug 31 '10 at 18:43

2 Answers2

1

One approach I've used in embedded systems, when I always wanted to read 16 bits or less at a time, was to keep a 32-bit long which holds the current partial 16-bit word, and the next whole one. Then the code was something like:

/* 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);
}

That could probably be readily adapted for use with a 64-bit long long and allow for withdrawal of up to 32 bits at a time.

supercat
  • 77,689
  • 9
  • 166
  • 211
0

I know you don't want to, but you could use a boost dynamic bitset and provide the FIFO capability on top of it using supplier/consumer semantics.

I didn't want to use boost either, but it's really not a big deal. You don't have to do anything with libraries. You just need to have boost available on your build system and include the right include files.

Dave
  • 5,133
  • 21
  • 27