Extract subset from boost dynamic_bitset

Question

I need to extract and decode the bits (idx, idx+1, ... idx+n_bits) from a given boost dynamic_bitset. I have created the following solution:

boost::dynamic_bitset<> mybitset(...);
// build mask 2^{idx+n_bits} - 2^{idx}
const boost::dynamic_bitset<> mask(mybitset.size(), (1 << idx+n_bits) - (1 << idx));
// shift the masked result idx times and get long
unsigned long u = ((mybitset & mask) >> idx ).to_ulong();

It works well, but as this code is critical for the performance of my application, I am curious if there exists a better way to achieve this?

Answer 1

The solution is easy:

#include <tuple>
    using std::get;
    using std::tuple;
    using std::make_tuple;
#include <boost/dynamic_bitset.hpp>
    using boost::dynamic_bitset;

template <typename Block, typename Allocator>
unsigned block_index(const boost::dynamic_bitset<Block, Allocator>& b, unsigned pos)
{ return pos / b.bits_per_block; }

namespace boost {
template <>
inline void
to_block_range(const dynamic_bitset<>& b, tuple<unsigned, unsigned,  unsigned long&> param)
{

    {
        unsigned beg = get<0>(param);
        unsigned len = get<1>(param);
        unsigned block1 = block_index(b, beg);
        unsigned block2 = block_index(b, beg + len -1);
        unsigned bit_index = beg % b.bits_per_block;
        unsigned long bitmask = (1 << len) - 1;
        get<2>(param) = ((b.m_bits[block1] >> bit_index) |
                               (b.m_bits[block2] << (b.bits_per_block - bit_index)  )) &
                                bitmask;
        return;
    }
}
}


unsigned long res;
to_block_range(bits, make_tuple(pos, len, std::ref(res)));

To call:

boost::dynamic_bitset<> bits;
unsigned long result;
to_block_range(bits, t_extract_range{begin_bit, length_bits, result});

There is no direct, native support in dynamic_bitset.

To get a range of bits, you have to get inside dynamic_bitset, get access to the underlying storage, and extract the bits yourself.

The code to do this is trivial but the data (dynamic_bitset::m_bits) is inside the private part of the class. There are three ways to hack past the private wall:

1. Pretend your compiler is non-conforming.
   #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. This changes private to public by changing BOOST_DYNAMIC_BITSET_PRIVATE.
2. Hacking the dynamic_bitset.hpp header to expose m_bits.
3. The third solution is to work around the current code.

(1) and (2) are brittle, frontal assaults which will be a maintenance nightmare.

Luckily for (3), there are template functions which are friends of dynamic_bitset. We can substitute our own function to do our own extraction by taking over (specialising) this template.

template <typename Block, typename Allocator, typename BlockOutputIterator>
inline void
to_block_range(const dynamic_bitset<Block, Allocator>& b,
               BlockOutputIterator result)
{
    std::copy(b.m_bits.begin(), b.m_bits.end(), result);
}

The canonical template function copies the entire bitset to iterator BlockOutputIterator which is not what we want.

We are going to specialise boost::to_block_range using a single custom type in place of BlockOutputIterator which will hold all 3 i/o parameters: namely

• begin_bit,
• length_of_range and
• destination.

Providing you call to_block_range with the requisite type, it will call your own function instead of the standard template, but with full access to the internals as well. You have essentially subverted the c++ access specification system!

N.B. The example code does no error checking. No attempt to make sure

• that the range fits in unsigned long or
• that the range does not exceed the bounds of the bitset or
• that the bitset uses unsigned longs internally.