Portable BitFields Using C++11
There are lots of reasons for using C++’s bit field feature. Perhaps you need a more compact way to represent your data structures, maybe you need to use them to interact with hardware, or if you’re writing an emulator, maybe you want to use them to efficiently represent the hardware that you’re emulating. The list goes on…
NOTE: There has been some discussion in the comments about the degree of portability of this technique. There seems to be a growing consensus that this is in fact undefined behavior. For system-level code, using techniques that are technically UB is pretty much standard practice, but I wanted to fully disclose that unfortunately, this technique is likely UB and it is possible that some compilers/architectures could emit code that has unexpected results.
So, I often see code that looks like this:
union Register {
uint8_t value;
struct {
uint8_t field1 : 2;
uint8_t field2 : 3;
uint8_t field3 : 3;
} bits;
};
The idea is simple. Given an object of type Register, we can easily get the whole 8-bit value. Or you access any of the 3 sub-fields using easy to read, intuitive code, like this:
Register r = { 0 };
r.field1 = 1;
r.field2 = 7;
Instead of the less clear:
uint8_t r = { 0 };
r = (r & ~0x03) | 1;
r = (r & ~0x1c) | (7 << 2);
Bit fields sound infinitely better, right? Well, there is a downside. The ordering of the bit fields is implementation-defined, meaning that if you really care about the actual bit positions, then you have to double-check that your compiler will lay out the bits the way that you expect. Not only that, but if you ever change compilers you may be chasing a bug that is very hard to spot due to the code looking correct. The bit twiddling version may be less clear, and harder to maintain. But at least it is absolutely clear which bits are being set to which. Can’t we have the best of both worlds? Can’t we do that without sacrificing efficiency? The answer is YES!
To maximize flexibility, we’ll want a way to select the underlying type based on the “highest” bit we need to touch. For example, if we have a bit field that starts at bit #5 and is 8 bits wide, we’ll need at least a uint16_t to represent it correctly. Fortunately, C++11 <type_traits> offers a nice and terse way to implement this. std::conditional. You can think of std::conditional as a ternary if, but for a static condition, and will result in 1 of 2 types instead of values. Using this, we can make the following helper class:
template <size_t LastBit>
struct MinimumTypeHelper {
typedef /* depends on LastBit */ type;
}
We are going to create a structure with a single member type. This type, depending on the integer constant will be one of 5 types. This is implemented using the previously mentioned std::conditional, which works like this:
template <bool B, class T, class F>
struct conditional;
If B resolves to true, the member type will be T. Otherwise, it will be F. For example: std::conditional<true, int, float>::type will equal int. Building on this, we can write the following:
template <size_t LastBit>
struct MinimumTypeHelper {
typedef
typename std::conditional<LastBit == 0 , void,
uint8_t>::type type;
};
which simply makes MinimumTypeHelper<N>::type equal void if N is zero, and uint8_t otherwise. But now we want to support 16-bit types. So we replace the false condition with another std::conditional statement, like this:
template <size_t LastBit>
struct MinimumTypeHelper {
typedef
typename std::conditional<LastBit == 0 , void,
typename std::conditional<LastBit <= 8 , uint8_t,
uint16_t>::type>::type type
};
We need all of the ::type’s in there because each std::conditional results in a class which has a type member that is set to one of the parameters given to std::conditional. For each one, we need that type to be passed as a parameter to “parent” conditional. Continuing with this pattern through uint64_t, we end up with the following complete and extensible implementation:
template <size_t LastBit>
struct MinimumTypeHelper {
typedef
typename std::conditional<LastBit == 0 , void,
typename std::conditional<LastBit <= 8 , uint8_t,
typename std::conditional<LastBit <= 16, uint16_t,
typename std::conditional<LastBit <= 32, uint32_t,
typename std::conditional<LastBit <= 64, uint64_t,
void>::type>::type>::type>::type>::type type;
};
So, now given a bit width, we can easily select a type with MinimumTypeHelper<N>::type. We can finally create our bit field.
template <size_t Index, size_t Bits = 1>
class BitField {
private:
enum {
Mask = (1u << Bits) - 1u
};
typedef typename MinimumTypeHelper<Index + Bits>::type T;
public:
template <class T2>
BitField &operator=(T2 value) {
value_ = (value_ & ~(Mask << Index)) | ((value & Mask) << Index);
return *this;
}
operator T() const { return (value_ >> Index) & Mask; }
explicit operator bool() const { return value_ & (Mask << Index); }
BitField &operator++() { return *this = *this + 1; }
T operator++(int) { T r = *this; ++*this; return r; }
BitField &operator--() { return *this = *this - 1; }
T operator--(int) { T r = *this; --*this; return r; }
private:
T value_;
};
Let’s break this down bit-by-bit (oh I crack myself up :-P).
- First we have the
enumMask. For a given bit count, this will create a mask of that many bits. So ifBits == 7, then it will result in0x7f, a pattern of 7 set bits. - Next we have
typedef typename MinimumTypeHelper<Index + Bits>::type T;, which looks complex, but isn’t too bad once we look more closely. All this is doing is defining a membertypebased on a type that can supportIndex + Bitsbits. We need to add them because a bit field 3 bits big at position 11 requires a type of at least 14 bits to represent. - From this point forward, we actually have pretty straightforward code. The constructor will take a value of any type, mask it, and do traditional bit-twiddling to insert it into the value. Using SFINAE, we could restrict the parameter to an integer type if desired.
- We allow conversion to the base type, so it’s trivial to extract the integer value of just this field using
operator T() const. - We allow testing of the field as a boolean using
explicit operator bool() const - Finally, for convenience, we have both increment and decrement operators.
Ok, so we have our class! How the heck do we use it? It’s actually very simple. Once we have all of this framework in place. Re-hashing the example we started with. We could re-write it like this:
union Register {
uint8_t value;
BitField<0,2> field1; // field1 is bits [0-2)
BitField<2,3> field2; // field2 is bits [2-5)
BitField<5,3> field3; // field3 is bits [5-8)
};
Using is just as simple as the original code:
Register r = { 0 };
r.field1 = 1;
r.field2 = 7;
But we now have full control over how the bits will be laid out in memory, and don’t have to worry about portability between compiler implementations and versions. In fact, we just gained a feature previously unmentioned. What if we want a “meta-field” that will alias one or more fields? Using this approach we can have overlapping fields! Let’s use a hardware register as an example:
union Video {
uint8_t raw;
BitField<0,1> background_enabled;
BitField<1,1> sprite_enabled;
// some more fields...
// meta-fields which don't occupy any space :-)
BitField<0,2> screen_enabled;
};
In this example, we can independently test if the background or sprites are enabled. But what if we want to know if either is enabled? We could write:
bool screen_enabled = v.background_enabled || v.sprite_enabled;
But that’s annoying. Because screen_enabled occupies the same space as both of those fields, we can just write:
bool screen_enabled = v.screen_enabled
Using this approach, any set of contiguous bits can be aliased without any size or performance penalty.
What about efficiency? Well looking at what GCC and Clang emit, this approach appears to cause them to emit nearly identical code (often identical). There is one last tweak that we could choose to do. A bit field of size one is really just a boolean, so we can specialize for that to make it clear we have boolean semantics and ensure that the compiler will emit optimal code:
template <size_t Index>
class BitField<Index, 1> {
private:
enum {
Bits = 1,
Mask = 0x01
};
typedef typename MinimumTypeHelper<Index + Bits>::type T;
public:
BitField &operator=(bool value) {
value_ = (value_ & ~(Mask << Index)) | (value << Index);
return *this;
}
explicit operator bool() const { return value_ & (Mask << Index); }
private:
T value_;
};
This code is very similar, but a bit simpler since we just want to be able to get or set the boolean value of the field. Putting it all together into a ready to use header, we have this:
#ifndef BITFIELD_H_
#define BITFIELD_H_
#include <cstdint>
#include <cstddef>
#include <type_traits>
using std::uint8_t;
using std::uint16_t;
using std::uint32_t;
using std::uint64_t;
namespace {
template <size_t LastBit>
struct MinimumTypeHelper {
typedef
typename std::conditional<LastBit == 0 , void,
typename std::conditional<LastBit <= 8 , uint8_t,
typename std::conditional<LastBit <= 16, uint16_t,
typename std::conditional<LastBit <= 32, uint32_t,
typename std::conditional<LastBit <= 64, uint64_t,
void>::type>::type>::type>::type>::type type;
};
}
template <size_t Index, size_t Bits = 1>
class BitField {
private:
enum {
Mask = (1u << Bits) - 1u
};
typedef typename MinimumTypeHelper<Index + Bits>::type T;
public:
template <class T2>
BitField &operator=(T2 value) {
value_ = (value_ & ~(Mask << Index)) | ((value & Mask) << Index);
return *this;
}
operator T() const { return (value_ >> Index) & Mask; }
explicit operator bool() const { return value_ & (Mask << Index); }
BitField &operator++() { return *this = *this + 1; }
T operator++(int) { T r = *this; ++*this; return r; }
BitField &operator--() { return *this = *this - 1; }
T operator--(int) { T r = *this; --*this; return r; }
private:
T value_;
};
template <size_t Index>
class BitField<Index, 1> {
private:
enum {
Bits = 1,
Mask = 0x01
};
typedef typename MinimumTypeHelper<Index + Bits>::type T;
public:
BitField &operator=(bool value) {
value_ = (value_ & ~(Mask << Index)) | (value << Index);
return *this;
}
explicit operator bool() const { return value_ & (Mask << Index); }
private:
T value_;
};
#endif
Happy bit twiddling!