从boost dynamic_bitset中提取子集

Question

我需要从给定的boost dynamic_bitset中提取和解码位(idx,idx + 1,... idx + n_bits).我创建了以下解决方案:

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();

它运行良好,但由于此代码对我的应用程序的性能至关重要,我很好奇是否有更好的方法来实现这一点？

Answer 1

解决方案很简单:

#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)));

致电:

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

没有直接的原生支持dynamic_bitset.

要获得一系列位,您必须进入内部dynamic_bitset,访问底层存储,并自行提取位.

执行此操作的代码很简单,但data(dynamic_bitset::m_bits)位于类的私有部分中.破解私人墙有三种方法:

1. 假装您的编译器不符合要求.
   #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS.这将改变private以public通过改变BOOST_DYNAMIC_BITSET_PRIVATE.
2. 攻击dynamic_bitset.hpp标题以暴露m_bits.
3. 第三种解决方案是解决当前的代码.

(1)和(2)是脆弱的正面攻击,这将是一场维护噩梦.

幸运的是,(3),存在有模板函数friend号第dynamic_bitset.我们可以通过接管(专门化)这个模板来替换我们自己的函数来进行自己的提取.

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);
}

规范模板函数将整个 bitset 复制到迭代器BlockOutputIterator,这不是我们想要的.

我们将专门boost::to_block_range使用一个自定义类型代替BlockOutputIterator其将包含所有3个i/o参数:即

• begin_bit,
• length_of_range 和
• 目的地.

如果您to_block_range使用必需类型调用,它将调用您自己的函数而不是标准模板,但也可以完全访问内部函数.你基本上颠覆了c ++访问规范系统!

NB示例代码没有错误检查.没有尝试确定

• 范围适合无符号长或
• 该范围不超过bitset的范围或
• bitset在内部使用unsigned longs.