bit twiddling in C++

[matobinder]

I need to write some code that deals with some memory images. In
essence, these images are just a collection of data, integers, bools,
floats, and so on.

The mucky part with this case is that nothing falls on byte boundries,
so I can't just use the ostream::write() stuff... Let me quick explain
this with an simple example.

I have an image data length of 2 bytes.

So Byte 0, and Byte 1.

Byte 0, Bit 0 ; is a bool
Byte 0, Bit 1 ; is a bool
Byte 0, Bits 2,3 ; represents a value 0,1,2, or 3
Byte 0, Bits 4,5,6,7
AND Byte 1, Bits 0,1,2,3 ; Represent a int(max 255)
Byte 1, Bits 4,5,6,7 ; Always 1111

So for example, I need to generate those two bytes, based on my normal
values in code.

Lets say I have:
int firstBit = 1; // always 0 or 1
int secondBit = 1; // always 0 or 1
int status = 0; //always 0 , 1, 2, or 3
int dataWord = 42; // number from 0-255 //bits 00101010
int tag = 15; // bits 1111

So I would need to generate(listing this in binary)

Byte 0 is: Byte 1 is:
1 1 00 0010 1010 1111


So basically I end up with a bit pattern of "1100001010101111"

I need to go both ways(Generating the bit patterns from the values,
and generating values from the bit pattern)

I'm trying to think of a good way to implement a library to assist
this. I understand all the things I need to worry about dealing with
byte ordering, and signed/unsigned.

I was thinking a good way to do this(maybe?) is just store the bits as
an array of char's. The 8 times the require memory for doing that
wouldn't be bad, as the largest image is 64k(and they willl NEVER be
bigger... its in hardware)

But first, are their any libraries or tools already in existance in
C/C++ that could greatly assist this. I know normal bit operators and
shifting, just looking for a more comprehensive set of tools for this.

I know C, and I am figuring out C++, I see C++ has a bitset class. Not
sure if this is overkill for what I want to do though.

I'm just starting on the begingings of this project and am just trying
to figure out some initial ideas of how I want to work on this. Any
pointers on this would be appreciated.

-mato

 

[Karthik]

I need to write some code that deals with some memory images. In
essence, these images are just a collection of data, integers, bools,
floats, and so on.

The mucky part with this case is that nothing falls on byte boundries,
so I can't just use the ostream::write() stuff... Let me quick explain
this with an simple example.

I have an image data length of 2 bytes.

So Byte 0, and Byte 1.

Byte 0, Bit 0 ; is a bool
Byte 0, Bit 1 ; is a bool
Byte 0, Bits 2,3 ; represents a value 0,1,2, or 3
Byte 0, Bits 4,5,6,7
AND Byte 1, Bits 0,1,2,3 ; Represent a int(max 255)
Byte 1, Bits 4,5,6,7 ; Always 1111

So for example, I need to generate those two bytes, based on my normal
values in code.

Lets say I have:
int firstBit = 1; // always 0 or 1
int secondBit = 1; // always 0 or 1
int status = 0; //always 0 , 1, 2, or 3
int dataWord = 42; // number from 0-255 //bits 00101010
int tag = 15; // bits 1111

So I would need to generate(listing this in binary)

Byte 0 is: Byte 1 is:
1 1 00 0010 1010 1111


So basically I end up with a bit pattern of "1100001010101111"

I need to go both ways(Generating the bit patterns from the values,
and generating values from the bit pattern)

I'm trying to think of a good way to implement a library to assist
this. I understand all the things I need to worry about dealing with
byte ordering, and signed/unsigned.

Look into bitset template in STL.


Just as a sample of what bitset can do for you, here is a piece of code -

#include <bitset>
#include <cstdlib>
#include <iostream>

using namespace std;

int main() {
bitset<32> mine;
mine = 245;
cout << mine << endl;
return EXIT_SUCCESS;
}

HTH

 

[Walter Tross]

I need to write some code that deals with some memory images. In
essence, these images are just a collection of data, integers, bools,
floats, and so on.

[snip]

My suggestion is:

class Mem // WARNING: unchecked code
{
unsigned char *_mem; // or vector (just the same)
// .......
void write(int bit, int len, const unsigned char *buf)
{
// frequent special cases can be made MUCH faster than this
int mem_bit = bit & 7;
int mem_byte = bit >> 3;
int buf_bit = 0;
int buf_byte = 0;
for (int i = 0; i < len; i++) {
unsigned b = buf[buf_byte] >> buf_bit & 1;
_mem[mem_byte] = _mem[mem_byte] & ~(1<<mem_bit) | b<<mem_bit;
mem_byte += ++mem_bit >> 3;
mem_bit &= 7;
buf_byte += ++buf_bit >> 3;
buf_bit &= 7;
}
}
void read(unsigned char *buf, int bit, int len)
{
// accordingly
}
public:
// .......
void writeTriple(int bit, int triple)
{
unsigned char buf[3];
#ifdef LITTLE_ENDIAN_MACHINE
{ buf[0] = triple; buf[1] = triple>>8; buf[2] = triple>>16; }
#else
{ buf[2] = triple; buf[1] = triple>>8; buf[0] = triple>>16; }
#endif
write(bit,3*8, buf);
}
// .......
};

instead of passing a bit address you might pass a byte and a bit
offset, depending on how your layout is best described

Walter

 

[Ioannis Vranos]

I'm trying to think of a good way to implement a library to assist
this. I understand all the things I need to worry about dealing with
byte ordering, and signed/unsigned.

I was thinking a good way to do this(maybe?) is just store the bits as
an array of char's. The 8 times the require memory for doing that
wouldn't be bad, as the largest image is 64k(and they willl NEVER be
bigger... its in hardware)

But first, are their any libraries or tools already in existance in
C/C++ that could greatly assist this. I know normal bit operators and
shifting, just looking for a more comprehensive set of tools for this.

I know C, and I am figuring out C++, I see C++ has a bitset class. Not
sure if this is overkill for what I want to do though.

I'm just starting on the begingings of this project and am just trying
to figure out some initial ideas of how I want to work on this. Any
pointers on this would be appreciated.

The best suggestion i can do is have a good, slow, thorough read of an up to
date ISO C++ book. http://www.accu.org at the book reviews section has some
good books.







Ioannis Vranos

 

[Ivan Vecerina]

I need to write some code that deals with some memory images. In
essence, these images are just a collection of data, integers, bools,
floats, and so on.

The mucky part with this case is that nothing falls on byte boundries,
so I can't just use the ostream::write() stuff... Let me quick explain
this with an simple example.

What you are seeking to implement is often needed in compression
algorithms, where variable bit-length encoding of the compressed
data is often used.

What you need to clarify first, is what type of interface do you want:
A) create/manipulate individual words split into sub-bits
B) peek and poke bit-aligned data into a random access(/memory) block
C) input/output stream interfaces working at a bit level.

For A), you could create a small set of functions such as:
void setbits(WORD& w, int bitOffs, int bitLen, WORD bitValues);
WORD getbits(WORD w, int bitOffs, int bitLen);

For B), well, you could start from what Walter has posted...
You mentioned std::bitset: it could be an option.
A good alternative might be boost::dynamic_bitset,
a peer-reviewed library from boost.org -- see:
http://www.boost.org/libs/dynamic_bitset

For C), create an adapter in front of a byte-based i/o protocol
(such as FILE or std::iostream), which buffers the current
partially read/written byte, and provides an interface such as:
void writebits(int bitCnt, WORD bitValues);
WORD readbits(int bitCnt);
You can probably extract such a bit-streaming layer from
a free open source library (i.e. zlib).

The approach I would choose mainly depends on external contraints,
i.e.: how is the data layout defined by your hardware?
I would use the approach that mirrors the way that the
data layout is specified. I think that this is most
important thing to look at for future maintainability.


Regards,
Ivan

 

[Bill Seurer]

I have an image data length of 2 bytes.

So Byte 0, and Byte 1.

Byte 0, Bit 0 ; is a bool
Byte 0, Bit 1 ; is a bool
Byte 0, Bits 2,3 ; represents a value 0,1,2, or 3
Byte 0, Bits 4,5,6,7
AND Byte 1, Bits 0,1,2,3 ; Represent a int(max 255)
Byte 1, Bits 4,5,6,7 ; Always 1111 ....
I was thinking a good way to do this(maybe?) is just store the bits as
an array of char's. The 8 times the require memory for doing that
wouldn't be bad, as the largest image is 64k(and they willl NEVER be
bigger... its in hardware)

Why wouldn't you simply use a struct with bit fields for this?

struct Data {
unsigned f1:1; // bool might work, not sure
unsigned f2:1;
unsigned f3:2;
unsigned f4:8;
unsigned f5:4;
}

Of course yours should use the names of whatever the fields actually are.