Bits Library
From codegorilla
Contents |
The C++ Bits Library
When I was implementing the STUN2 draft protocol at mediagrids, I found that because STUN2 aimed to be bit compatible with the original STUN protocol so they had decided to scatter some values in different bit areas that needed to be reconstructed and this resulted in what I considered to be messy code.
Outside of work I decided my mpl could do with a little practice, and this bit scattering seemed an ideal challenge, so I developed this bits library taking advantage of the boost mpl (tested recently with 1.36) and here I share this work with you.
The aim was to present the bit patterns in the code rather than their usual hex or decimal equivalent, thus aiding maintainability and future understanding for other developers.
The Source
The bits library is a header file only library, including the main header bits/algo.h is sufficient as this includes the files:
- bits/bits.h - defined the base types and some simple algorithms that the more complex algorithms use.
- bits/to_decimal.h - a simple compile time algorithm that converts the bits representations into the decimal equivalent.
- bits/pull_out.h - contains the algorithm to pull out specific bits and reconstruct a new value (squashing the pulled bits together)
- bits/push_in.h - contains the algorithm to push bits into a bigger value from a smaller value such that they allow the bits to be scattered.
The public functionality is exposed in the namespace bits which in turn resides inside the boost namespace, there is also a bits_detail namespace which contains the implementation detail of the functionality exposed.
The latest version is available via subversion, http://svn.codegorilla.co.uk/bits_lib/trunk/include/bits
The Basics (bits/bits.h)
Types
Two main types are defined, byte and word which are 8 and 16 bit respectively.
- byte
- A template type which takes 8 parameters which represent the bits that make up the byte, with the MSB (most significant byte) on the left (1st parameter).
typedef bits::byte<0,0,1,1,0,0,1,1> fifty_one;
- word
- A template type which takes 16 parameters which represent the bits the make up the word, with the MSB on the left.
typedef bits::word<0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1> seven;
Longer bit representations can be made up of these parts using the byte and word types with the mpl::vector:
typedef mpl::vector< bits::byte<0,0,1,1,0,0,1,1>, bits::byte<0,0,1,1,0,0,1,1>, bits::byte<0,0,1,1,0,0,1,1> > twenty_four_bts; typedef mpl::vector< bits::word<0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1>, bits::byte<0,0,1,1,0,0,1,1>, bits::byte<0,0,1,1,0,0,1,1> > thirty_two_bits;
Any combination of byte and word and be placed into the vector to make up (potentially) any bit length, although the total length it limited by the algorithms and the data they manipulate. Notice how we use typedef, as these types are used during compile time, no variable instantiation is required and wouldn't make sense anyhow.
Note: any vector_c size of type bool can be used in all the algorithms, a nibble (4 bits) would be defined as mpl::vector_c<bool,0,1,1,1>, which is 4 bits holding the value 7.
A couple of types are defined that represent a byte with all zeros and a byte with all ones, these are called byte_zeros and byte_ones respectively.
Basic algorithms
bits_one and bits_zero
These two algorithms are compile time evaluated and count the bits that are either one or zero and return that value, its type is based on mpl::int_ which is an integer representation.
- bits_one<X>::value
- bits_zero<X>::value
Where X is a bit representation, value is of type mpl::int_ (C++ type int).
By themselves these algorithms seem of little value, but they are used by some of the more complex algorithms and give you the opportunity to develop your own algorithms.
Example
#include "bits/bits.h" #include <boost/mpl/vector.hpp> #include <boost/cstdint.hpp> #include <assert.h> namespace bits = boost::bits; namespace mpl = boost::mpl; using boost::uint32_t; using boost::uint16_t; using boost::uint8_t; void main() { typedef bits::byte<0,1,1,0,1,1,0,1> value_109; uint32_t bits_that_are_one = bits::bits_one<value_109>::value; assert( bits_that_are_one == 5 ); uint32_t bits_that_are_zero = bits::bits_zero<value_109>::value; assert( bits_that_are_zero == 3 ); typedef mpl::vector< bits::byte<0,1,1,1,0,0,0,0>, bits::byte<0,1,0,0,1,1,1,0> > big_number; // 28750 bits_that_are_one = bits::bits_one<big_number>::value; assert( bits_that_are_one == 7 ); bits_that_are_zero = bits::bits_zero<big_number>::value; assert( bits_that_are_zero == 9 ); }
bits_size
This is another simple algorithm that count the number of bits.
- bits_size<X>::value
Where X is a bit representation, value is of type mpl::int_ (C++ type int).
By themselves this algorithms seem of little value, but they are used by some of the more complex algorithms and give you the opportunity to develop your own algorithms.
Example
#include "bits/bits.h" #include <boost/mpl/vector.hpp> #include <boost/cstdint.hpp> #include <assert.h> namespace bits = boost::bits; namespace mpl = boost::mpl; using boost::uint32_t; using boost::uint16_t; using boost::uint8_t; void main() { typedef bits::byte<0,1,1,0,1,1,0,1> value_109; uint32_t bits_size = bits::bits_size<value_109>::value; assert( bits_size == 8 ); typedef mpl::vector< bits::byte<0,1,1,1,0,0,0,0>, bits::byte<0,1,0,0,1,1,1,0> > big_number; bits_size = bits::bits_size<big_number>::value; assert( bits_size == 16 ); }
Decimal Algorithm (bits/to_decimal.h)
This algorithm is a compile time conversion from a bit representation type to a integer value.
- to_decimal<X>::value
Where X is a bit representation, value is of type mpl::int_ (C++ type int).
Example
#include "bits/to_decimal.h" #include <boost/mpl/vector.hpp> #include <boost/cstdint.hpp> #include <assert.h> namespace bits = boost::bits; namespace mpl = boost::mpl; using boost::uint32_t; using boost::uint16_t; using boost::uint8_t; void main() { typedef bits::byte<0,1,1,0,1,1,0,1> value_109; uint32_t decimal_value = bits::to_decimal<value_109>::value; assert( decimal_value == 109 ); typedef mpl::vector< bits::byte<0,1,1,1,0,0,0,0>, bits::byte<0,1,0,0,1,1,1,0> > big_number; // 28750 decimal_value = bits::to_decimal<big_number>::value; assert( decimal_value == 28750 ); }
Pull Out Algorithm (bits/pull_out.h)
This algorithm is mix of compile time evaluation and runtime functionality to perform the function of converting one value to another only taking those bits specified from the first value and reconstructing a new value whose bit length is just those bits pulled out (hence pull out).
Yes, I know, not a very good explanation so I'll try to show what I mean in the following:
A protocol transfers a 16 bit number (Value1), the protocol defined that bit 14 and bit 3 (0 based bit numbering, LSB = bit 0) define the protocol mode (silly I know, but just look at STUN2), these 2 bits define 4 protocol mode, 0 to 3, we could do all this checking with masks no problem but with pull_out we can do it slightly differently hopefully (arguably) making the code clearer.
// simple enum, defining the 4 values in their 2 bit form. enum protocol_mode { simple = 0, basic = 1, adv = 2, hard = 3 }; protocol_mode get_mode( uint16_t msg ) { // bit 14 and bit 3 selected typedef bits::word<0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0> mode_mask; // notice that we have to static_cast the result (specified as uint8_t) // because enum type do not support shift operations return static_cast<protocol_mode>( bits::pull_out<mode_mask>::apply<uint8_t>( msg ) ); }
For comparison, here is the same code using the actual values
enum protocol_mode { simple = 0x0000, basic = 0x0008, adv = 0x4000, hard = 0x4008 }; #define MODE_MASK 0x4008 protocol_mode get_mode( uint16_t msg ) { return static_cast<protocol_mode>( msg & MODE_MASK ); }
Some would say, and rightly so, that the latter is clearer. But this is just an example, imagine this protocol was extended to use another bit so that there were 8 values rather than 4 and that this was spread over 32 bits rather than 16 which would be easier to extend now?
- pull_out<X>::apply<R>( P )
Where X is a bit representation, R is the type that will contain the pulled out bits and P is the value to pull the bits from.
Example
The extended above to cope with a 3 bit mode from a 32 bit value, bit 23 is the MSB of the mode.
#include "bits/pull_out.h" #include <boost/mpl/vector.hpp> #include <boost/cstdint.hpp> #include <assert.h> namespace bits = boost::bits; namespace mpl = boost::mpl; using boost::uint32_t; using boost::uint16_t; using boost::uint8_t; // simple enum, defining the 8 values in their 3 bit form. enum protocol_mode { simple = 0, basic = 1, adv = 2, hard = 3, new1 = 4, new2 = 5, new3 = 6, new4 = 7 }; protocol_mode get_mode( uint32_t msg ) { // bit 23, 14 and bit 3 selected typedef mpl::vector< bits::byte_zeros, bits::byte<1,0,0,0,0,0,0,0>, bits::word<0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0> > mode_mask; return static_cast<protocol_mode>( bits::pull_out<mode_mask>::apply<uint8_t>( msg ) ); } void main() { protocol_mode mode = get_mode( 0x4092AF18 ); assert( mode == new2 ); }
Push In Algorithm (bits/push_in.h)
This algorithm is the opposite of the pull out algorithm, in that is allows you to push bits into an existing value.
- push_in<X>::apply( C, N )
Where X is a bit representation, C is the existing bits (and the return type), N are the new bits to place into C.
The bit representation X defined the bits to replace in C starting at the MSB with the bits in N starting at the LSB (this ensure that even if 2 bits are required they are taken from the 2 LSB in N.
Example
Based on the example from pull_out, here we construct a protocol message given a mode.
#include "bits/push_in.h" #include <boost/mpl/vector.hpp> #include <boost/cstdint.hpp> #include <assert.h> namespace bits = boost::bits; namespace mpl = boost::mpl; using boost::uint32_t; using boost::uint16_t; using boost::uint8_t; // simple enum, defining the 8 values in their 3 bit form. enum protocol_mode { simple = 0, basic = 1, adv = 2, hard = 3, new1 = 4, new2 = 5, new3 = 6, new4 = 7 }; uint32_t set_mode( uint32_t msg, protocol_mode mode ) { // bit 23, 14 and bit 3 selected typedef mpl::vector< bits::byte_zeros, bits::byte<1,0,0,0,0,0,0,0>, bits::word<0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0> > mode_mask; return bits::push_in<mode_mask>::apply( msg, static_cast<uint8_t>(mode) ); } void main() { uint32_t msg = set_mode( 0, new2 ); assert( msg == 0x00800008 ); }
