Функции упаковки и распаковки битовых структур

[apolukhin]

Перенос предложения: голоса +7, -0 Автор идеи: Олег Фатхиев

Хочется иметь функции, позволяющие конвертировать контейнеры, содержащие интегральные типы, в последовательность нулей и единиц. И наоборот.

Часто бывает нужно работать с последовательностью бит, а не байт. Для работы с битами удобно использовать std::vector или std::bitset, однако возникает необходимость сжать такую структуру в последовательность, например, uint64_t или же в строку. В битсет есть похожая функциональность в методах std::bitset::to_ulong и std::bitset::to_ullong, однако они возвращают не последовательность чисел, а лишь одно число, что ограничивает их применение.

template <class T, class InputIt, class OutputIt>
void pack_bits_to(InputIt first, InputIt last, OutputIt d_first)
{
    static_assert(std::is_integral<T>::value);

    while (first != last) {
        DataType buf = 0;

        for (std::size_t i = 0; i < 8 * sizeof(T); ++i) {
            bool bit = (first != last) ? (*(first++)) : 0;
            buf = buf | static_cast<DataType>(bit << i);
        }

        *(d_first++) = buf;
    }
}

template <class T, class InputIt, class OutputIt>
void unpack_bits_from(InputIt first, InputIt last, OutputIt d_first)
{
    static_assert(std::is_integral<T>::value);

    while (first != last) {
        for (std::size_t i = 0; i < 8 * sizeof(T); ++i) {
            *(d_first++) = (1 & (*first >> i));
        }
        ++first;
    }
}​

Пример использования:

// packing example
std::vector<bool> input = { 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0 };
std::string output;
pack_bits_to<char>(input.begin(), input.end(), std::back_inserter(output));
// output == {0b10100000, 0b00110001}

// unpacking example
std::string input = {0b10100000, 0b00110001};
std::vector<bool> output;
unpack_bits_from<char>(input.begin(), input.end(), std::back_inserter(output));
// output == { 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0 }

Замечу, что в качестве последовательности бит совершенно не обязательно должен использоваться std::vector.

[apolukhin]

Виктор Губин, 14 июня 2018, 13:33 Было-бы здорово имень что-то вроде

uint8_t b = 0xBF;

bool bi0 = a[0]; bool bi1 = b[1]; ... bool bi7 = b[7];

Еще-бы непомешало ввести в стандарт раширения типа builtin_clz, __builtin_clrsb, builtin_popcount, builtin_parity, __builtin_bswap16 ... builtin_bswap64 от GCC и __lzcnt, _BitScanForward,_BitScanReverse, _bittest, _byteswap_ushort ... _byteswap_uint64 от MS VC++

Alexander, 15 июня 2018, 20:25 Виктор Губин, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0553r2.html

[apolukhin]

Хорошая идея - добавить алгоритмы в стандартную библиотеку. Учтите что надо будет добавить и в std::ranges

[bakwc]

Ещё предложение на эту же тему - добавить в стандарт требование на последовательное хранение в виде набора бит (оно и так уже так реализовано в том же gcc), и вывести наружу методы доступа к сырым запакованным данным. Это будет эффективней (с точки зрения производительности) чем перепаковывать уже запакованные данные отдельными методами.