Извлечь подмножество из boost

Question

Мне нужно извлечь и декодировать биты (idx, idx + 1, ... idx + n_bits) из заданного бустика dynamic_bitset. Я создал следующее решение:

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, получить доступ к базовому хранилищу и самостоятельно извлечь биты.

Код для этого тривиален, но данные (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);
}

Каноническая функция шаблона копирует весь битовый набор в итератор BlockOutputIterator, который не , что мы хотим.

Мы собираемся специализироваться boost::to_block_range, используя один пользовательский тип вместо BlockOutputIterator, который будет содержать все 3 параметра ввода / вывода: а именно

• begin_bit,
• length_of_range и
• назначение.

Если вы вызываете to_block_range с требуемым типом, он будет вызывать вашу собственную функцию вместо стандартного шаблона, но также с полным доступом к внутренним компонентам. Вы по сути подорвали систему спецификации доступа c ++!

N.B. Код примера не проверяет ошибки. Нет попыток убедиться

• , что диапазон вписывается в unsigned long или
• что диапазон не превышает границы набора битов или
• , что в наборе битов используются внутренние значения без знака.