Frequently Asked Questions

Why is this not just std::bitset or boost::dynamic_bitset or std::vector<bool>?

• None of these data types have the ability to "encode" ( see: packing ) data in the binary within them. ( NB: both bitsets can be constructed with a long )
• None of these data types have the ability to "decode" ( see: unpacking ) data from the binary within them.
• Logical operations on ranges of bits within these types loses the semantics meaning.
• There exists no way to return a "reference to a range of bits" in these data types.

Fixed size bit container modeling:

Lets say you need to model a MIPS 1 instruction. And you want to be able to encode an instruction for "addiu $1, $2, 100" ( This example taken from inside cover Computer Organization & Design, Patterson,Hennessy ) .

typedef bit_array<32> mips_1_inst ; 
enum Opcodes { // ...
               Addiu = 9, ///< Add immediate Unsigned
               // ...
             } ; 
mips_1_inst simple ; 
uint_8_t rs_reg = 2 ; 
uint_8_t rt_reg = 1 ; 
int_16_t immediate = 100 ;
simple.pack( Addiu, 31, 25 ) ; 	
simple.pack( rs_reg, 25, 21 ) ; 
simple.pack( rt_reg, 20, 16 ) ; 
simple.pack( immediate, 15, 0 );

In the above example a bit_array<32> is used to model a 32 bit MIPS instruction. The range of bits are selected and their values are checked before they are encoded within the given bit sequence. Also when packing negative numbers they are represented in a "2's complement" bit encoding.

typedef std::bitset<32> mips_1_inst ; 
enum Opcodes { // ...
               Addiu = 9, ///< Add immediate Unsigned
               // ...
              } ; 
mips_1_inst simple ;
uint_8_t rs_reg = 2 ; 
uint_8_t rt_reg = 1 ; 
int_16_t immediate = 100 ;
simple |= ( mips_1_inst((long)Addiu) <<= 25 ) ; 					
simple |= ( mips_1_inst((long)rs_reg) <<= 21 ) ;
simple |= ( mips_1_inst((long)rt_reg) <<= 16 ) ; 
simple |= ( mips_1_inst((long)immediate) ) ; 
// simple now encodes the MIPS 1 instruction : addiu $1,$2, 100 //

In the above example a bitset<32> is used to model a 32 bit MIPS instruction. There is no checking of values when converted to long. If for instance the value of immediate were -1, the cast to long would have every bit set ( Assuming a 2's complement encoding for long, which is not guaranteed ).

This problem can be solved by double shifting ( to guarantee 0's in unset bit positions ). or by calling set/reset on every bit we want to be 0'd out. This is what that would look like:

simple |= ( mips_1_inst((long)rs_reg) <<= 27 ) >>= 6 ; // set bits 25:21 equal to value of rs_reg

This operation requires using two numbers 27 ( which is 32( size ) - 5 ( bit length ) ) to clear upper bits, and then right shifting by 6 ( 31 (upper bit index ) - 25 ( final upper bit index ) ). To move the least significant bits to the 21's position. We could have also done this.

simple |= ( mips_1_inst((long)rs_reg & (long)0x1f) >>= 21 ; // sets bits 25:21 equal to value of rs_reg. 

Both of the above solutions require extra typing just to guarantee the setting of bits doesn't pollute neighboring bits. It provides no error checking as to the value range, since a value larger than 0x1f will be silently truncated.

Resizable Bit Containers

To be Completed