C++ fast bit array class for streaming compression algorithms

Question

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.

what is wrong with boost? stackoverflow.com/questions/2633400/c-c-efficient-bit-array — Anycorn
– Anycorn, Commented Aug 31, 2010 at 18:31
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
– Anycorn, Commented Aug 31, 2010 at 18:40
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
– torak, Commented Aug 31, 2010 at 18:43

supercat · Accepted Answer · 2010-08-31 19:18:41Z

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.

answered Aug 31, 2010 at 19:18

supercat

82k9 gold badges179 silver badges226 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dave · Accepted Answer · 2010-08-31 18:35:37Z

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.

answered Aug 31, 2010 at 18:35

Dave

5,1831 gold badge24 silver badges28 bronze badges

Collectives™ on Stack Overflow

C++ fast bit array class for streaming compression algorithms

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related