bit insertion and extraction

[Vince]

Hi,

I would like to extract or insert some values (of different size) inside
a buffer.
I would like to have something like this :


BYTE Buffer[207];


CBitAPI bitbuf<Buffer, sizeof(Buffer)>;

// Extract different data
int version = bitbuf.get(0,4); // Extract 4 bits from bit 0
int whatever = bitbuf.get(4,2); // Extract 2 bits from bit 4
bool ack = bitbuf.get(6,1) //Extract 1 bit from bit 6

or even better :

int nValue;
bitbuf.get(4,2, nValue);

DWORD dwValue;
bitbuf.get(6,4, dwValue);


Unfortunately I searched everywhere (boost, google, ) and I didn't found
anything appropriate.

dynamic_bitset for instance cannot be initialized from an array...

 

[Jon Slaughter]

Hi,

I would like to extract or insert some values (of different size) inside
a buffer.
I would like to have something like this :


BYTE Buffer[207];


CBitAPI bitbuf<Buffer, sizeof(Buffer)>;

// Extract different data
int version = bitbuf.get(0,4); // Extract 4 bits from bit 0
int whatever = bitbuf.get(4,2); // Extract 2 bits from bit 4
bool ack = bitbuf.get(6,1) //Extract 1 bit from bit 6

or even better :

int nValue;
bitbuf.get(4,2, nValue);

DWORD dwValue;
bitbuf.get(6,4, dwValue);


Unfortunately I searched everywhere (boost, google, ) and I didn't found
anything appropriate.

dynamic_bitset for instance cannot be initialized from an array...

lets say you have a bit array A and you want to extract the nth bit.
Normally A would be stored as an array of bytes or ints.


|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxx@xxxx|xxxxxxxx|xxxxxxxx|

lets say we want the bit at the @. First we have to figure out which byte
this is in... its pretty easy, you take the location of @ which is n(it is
28 in this example) and divide by 8 and that gives you what "bin" you are
in(i.e., what byte @ belongs to)

to find out what how "far" into the byte @ is in, we just have to compute
n - 8*floor(n/8).

8*floor(n/8) represents what the location of the byte that @ is in in terms
of bits.

n - 8*floor(n/8) is the same as n mod 8.

so, the simple formula to extract the byte that contains the bit is
(floor(n/8) means n / 8 in integer division)

OurByte = BitArray[floor(n/8)];

Now to get the bit we simply have to do this

((1 << (n % 8)) & OurByte) >> (n % 8)

You should learn bitwise arithmetic to understand that. I'm sure there are
many tutorials online

note that

1 << (n % 8) has a 1 in the position of the location of @ and 0's everywhere
else

so 1 << (28 % 8) = 1 << 4 = 00010000 in the case above (note the 1 is at the
4th bit (this is what (1 << x) means... means we put a 1 at the xth bit)

00010000 & xxx@xxxx = 000@0000

and the << shifts the bit back to the first location..

000@0000 >> (28 % 8) = 000@0000 >> 4 = @0000000 = @


Now, I'm sure you can find some stuff online that can make it clearer if you
don't understand it.

Two things to note: You might want to use ints instead of bytes... I think
you should be ablet o figure out the obvious generalization. Second is that
this has to be modified on different architectures because of the way
certain data types or stored(look for endianess)

Hope that helps some.

Jon

 

[Sensei]

Now to get the bit we simply have to do this

((1 << (n % 8)) & OurByte) >> (n % 8)

Not to mention that it's worth taking a look at the endianness of the
system.

 

[Jon Slaughter]

Not to mention that it's worth taking a look at the endianness of the
system.

heh... I did mention that...

 

[Sensei]

heh... I did mention that...

Really!? I should wear eyeglasses......

 

[Jeff Flinn]

Hi,

I would like to extract or insert some values (of different size) inside
a buffer.
I would like to have something like this :


BYTE Buffer[207];


CBitAPI bitbuf<Buffer, sizeof(Buffer)>;

// Extract different data
int version = bitbuf.get(0,4); // Extract 4 bits from bit 0
int whatever = bitbuf.get(4,2); // Extract 2 bits from bit 4
bool ack = bitbuf.get(6,1) //Extract 1 bit from bit 6

or even better :

int nValue;
bitbuf.get(4,2, nValue);

DWORD dwValue;
bitbuf.get(6,4, dwValue);


Unfortunately I searched everywhere (boost, google, ) and I didn't found
anything appropriate.

dynamic_bitset for instance cannot be initialized from an array...

It can according to:
http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html#header-files

You would use the constructor that takes two input iterators. Since this is
a templated constructor, Buffer elements don't have to be 8bit bytes.

boost::dynamic_bitset<> bits( &Buffer[0], &Buffer[0] + 207 );

Also see the non-member functions from_block_range,to_block_range and
to_ulong that allow transfer from/to integral data types. The latter could
be used to create a templated function to implement your desired behavior.

// Untested and needs error checking

template< typename T, class BITSET >
T extract_value( BITSET aBits, size_t aBegin, size_t aSize )
{
// implement size assertions here

aBits.resize( aBegin + aSize );

return T(aBits<<aBegin).to_ulong());
}


Jeff Flinn