Storage size from bits

Last week, we had a look at the computation of Log2 using templates and constexpr. Of course, I had ulterior motives. In particular, I was interested in allocating just the right number of bits for a field in a bit field, but rather than hard-coding it, having it deduced from a template argument. Let’s see how we can do that.

Before I continue, I must thank my fried Roger Cyr that helped me simplify quite a lot my original solution (in particular, he told me about the using syntax, which I didn’t know about). So the strategy is to have an implementation template what gives a few explicit specialization for a given number of bits. If you use the implementation template with an argument of 8, 16, 32, or 64, it will define a type that can hold that many bits, that is, uint8_t, uint16_t, uint32_t, or uint64_t, all defined in <cstdint>. The thing is to emulate something like a type trait, just like what std::numeric_limits<T&gt does.

In addition to the implementation template, there’s a “generic” template that takes an arbitrary argument, and reduce it to 8, 16, 32, or 64, and aliases the corresponding implementation template to type_from_bits which is directly the type used for declaring variables of the right number of bits.

template <int x> struct type_from_bits_; // incomplete type
template <> struct type_from_bits_<64> { using type = uint64_t; };
template <> struct type_from_bits_<32> { using type = uint32_t; };
template <> struct type_from_bits_<16> { using type = uint16_t; };
template <> struct type_from_bits_<8>  { using type = uint8_t; };

template<const int x>
using type_from_bits =
  type_from_bits_<(x>32) ? 64 : ((x>16) ? 32 : ((x>8) ? 16 : 8))>::type;

Having the right type of integers to store a specific range of value is necessary to reduce storage requirements. Why use 64 bits if 8 will do? It’s also useful in bitfields where alignment/padding is determined by the largest type used in the bitfield declaration. If you defined two fields, say int thingie:3 and char gizmo:2, the bitfield will be padded to the next int boundary. It will use 32 bits (if your ints are 32 bits!

So let’s give an example. I was coding something where a node links with its neighbors using indices in an array. If the array is small, I want to use just enough bits to represent indices, and have the bitfield to have the smallest possible alignment. Using last week’s log2 function and the above templates, we can write something like:

type_from_bits<log2(max_items-1)> pred:log2(max_items-1);
type_from_bits<log2(max_items-1)> next:log2(max_items-1);

The syntax is scary, somewhat, but that’s just a regular bitfield. The first part of the declaration is the type, and log2 gives the number of bits needed to store numbers from 0 to max_items-1 inclusive.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: