#include <bitvector.h>

Classes
class	bitref

class	bitref< BlockT >

Public Types
using	allocator_type = AllocatorT<block_type>

using	block_type = uint8_t

using	const_iterator = detail::bitvector_iterator<const bitvector_base<AllocatorT>>

using	iterator = detail::bitvector_iterator<bitvector_base<AllocatorT>>

using	size_type = size_t

using	value_type = block_type

Public Member Functions
template<bitvectorish OutT>
OutT	as () const

	bitvector_base ()

	bitvector_base (size_type bits)

	bitvector_base (std::initializer_list< block_type > blocks, std::optional< size_type > bits=std::nullopt)

	bitvector_base (std::span< const uint8_t > bytes, std::optional< size_type > bits=std::nullopt)

bool	empty () const

template<bitvectorish OtherT>
bool	equals (const OtherT &other) const noexcept

template<bitvectorish OtherT>
bool	equals_vartime (const OtherT &other) const noexcept

size_type	hamming_weight () const

CT::Choice	has_odd_hamming_weight () const

size_type	size () const

Serialization
void	from_bytes (std::span< const uint8_t > bytes, std::optional< size_type > bits=std::nullopt)

template<concepts::resizable_byte_buffer OutT = std::conditional_t<uses_secure_allocator, secure_vector<uint8_t>, std::vector<uint8_t>>>
OutT	to_bytes () const

void	to_bytes (std::span< uint8_t > out) const

std::string	to_string () const

Capacity Accessors and Modifiers
size_type	capacity () const

void	reserve (size_type bits)

void	resize (size_type bits)

void	push_back (bool bit)

void	pop_back ()

Bitwise and Global Accessors and Modifiers
auto	at (size_type pos)

auto	at (size_type pos) const

auto	front ()

auto	front () const

auto	back ()

auto	back () const

bitvector_base &	set (size_type pos)

bitvector_base &	set ()

bitvector_base &	unset (size_type pos)

bitvector_base &	unset ()

bitvector_base &	flip (size_type pos)

bitvector_base &	flip ()

bool	none_vartime () const

bool	none () const

bool	any_vartime () const

bool	any () const

bool	all_vartime () const

bool	all () const

auto	operator[] (size_type pos)

auto	operator[] (size_type pos) const

Subvectors
template<bitvectorish OutT = bitvector_base<AllocatorT>>
auto	subvector (size_type pos, std::optional< size_type > length=std::nullopt) const

template<typename OutT> requires (std::unsigned_integral<strong_type_wrapped_type<OutT>> && !std::same_as<bool, strong_type_wrapped_type<OutT>>)
OutT	subvector (size_type pos) const

template<typename InT> requires (std::unsigned_integral<strong_type_wrapped_type<InT>> && !std::same_as<bool, InT>)
void	subvector_replace (size_type pos, InT value)

Operators
auto	operator~ ()

template<bitvectorish OtherT>
auto &	operator\|= (const OtherT &other)

template<bitvectorish OtherT>
auto &	operator&= (const OtherT &other)

template<bitvectorish OtherT>
auto &	operator^= (const OtherT &other)

Constant Time Operations
template<bitvectorish OtherT>
void	ct_conditional_xor (CT::Choice condition, const OtherT &other)

constexpr void	_const_time_poison () const

constexpr void	_const_time_unpoison () const

Iterators
iterator	begin () noexcept

const_iterator	begin () const noexcept

const_iterator	cbegin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cend () noexcept

Static Public Attributes
static constexpr size_type	block_size_bits = block_size_bytes * 8

static constexpr size_type	block_size_bytes = sizeof(block_type)

static constexpr bool	uses_secure_allocator = std::is_same_v<allocator_type, secure_allocator<block_type>>

Friends
template<template< typename > typename FriendAllocatorT>
class	bitvector_base

Detailed Description

template<template< typename > typename AllocatorT>
class Botan::bitvector_base< AllocatorT >

An arbitrarily large bitvector with typical bit manipulation and convenient bitwise access methods. Don't use bitvector_base directly, but the type aliases::

bitvector - with a standard allocator
secure_bitvector - with a secure allocator that auto-scrubs the memory

Definition at line 232 of file bitvector.h.

Member Typedef Documentation

◆ allocator_type

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::allocator_type = AllocatorT<block_type>

Definition at line 236 of file bitvector.h.

◆ block_type

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::block_type = uint8_t

Definition at line 234 of file bitvector.h.

◆ const_iterator

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::const_iterator = detail::bitvector_iterator<const bitvector_base<AllocatorT>>

Definition at line 239 of file bitvector.h.

◆ iterator

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::iterator = detail::bitvector_iterator<bitvector_base<AllocatorT>>

Definition at line 238 of file bitvector.h.

◆ size_type

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::size_type = size_t

Definition at line 235 of file bitvector.h.

◆ value_type

template<template< typename > typename AllocatorT>

using Botan::bitvector_base< AllocatorT >::value_type = block_type

Definition at line 237 of file bitvector.h.

Constructor & Destructor Documentation

◆ bitvector_base() [1/4]

template<template< typename > typename AllocatorT>

Botan::bitvector_base< AllocatorT >::bitvector_base ( )

inline

Definition at line 374 of file bitvector.h.

374: m_bits(0) {}

◆ bitvector_base() [2/4]

template<template< typename > typename AllocatorT>

Botan::bitvector_base< AllocatorT >::bitvector_base ( size_type bits )

inline

Definition at line 376 of file bitvector.h.

376: m_bits(bits), m_blocks(ceil_toblocks(bits)) {}

Botan::bitvector_base

Definition bitvector.h:232

◆ bitvector_base() [3/4]

template<template< typename > typename AllocatorT>

Botan::bitvector_base< AllocatorT >::bitvector_base	(	std::span< const uint8_t >	bytes,
		std::optional< size_type >	bits = std::nullopt )

inline

Initialize the bitvector from a byte-array. Bits are taken byte-wise from least significant to most significant. Example::

bitvector[0] -> LSB(Byte[0]) bitvector[1] -> LSB+1(Byte[0]) ... bitvector[8] -> LSB(Byte[1])

Parameters

bytes	The byte vector to be loaded
bits	The number of bits to be loaded. This must not be more than the number of bytes in `bytes`.

Definition at line 391 of file bitvector.h.

                                                                                             {
         from_bytes(bytes, bits);
      }

◆ bitvector_base() [4/4]

template<template< typename > typename AllocatorT>

Botan::bitvector_base< AllocatorT >::bitvector_base	(	std::initializer_list< block_type >	blocks,
		std::optional< size_type >	bits = std::nullopt )

inline

Definition at line 395 of file bitvector.h.

395 :

396 m_bits(bits.value_or(blocks.size() * block_size_bits)), m_blocks(blocks.begin(), blocks.end()) {}

Botan::bitvector_base::block_size_bits

static constexpr size_type block_size_bits

Definition bitvector.h:242

Botan::bitvector_base::size

size_type size() const

Definition bitvector.h:400

Botan::bitvector_base::begin

iterator begin() noexcept

Definition bitvector.h:886

Botan::bitvector_base::end

iterator end() noexcept

Definition bitvector.h:892

Member Function Documentation

◆ _const_time_poison()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::_const_time_poison ( ) const

inlineconstexpr

Definition at line 876 of file bitvector.h.

876{ CT::poison(m_blocks); }

Botan::CT::poison

constexpr void poison(const T *p, size_t n)

Definition ct_utils.h:54

◆ _const_time_unpoison()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::_const_time_unpoison ( ) const

inlineconstexpr

Definition at line 878 of file bitvector.h.

878{ CT::unpoison(m_blocks); }

Botan::CT::unpoison

constexpr void unpoison(const T *p, size_t n)

Definition ct_utils.h:65

◆ all()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::all ( ) const

inline

Returns: true iff all bits are set in constant time

Definition at line 681 of file bitvector.h.

681{ return hamming_weight() == m_bits; }

Botan::bitvector_base::hamming_weight

size_type hamming_weight() const

Definition bitvector.h:420

◆ all_vartime()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::all_vartime ( ) const

inline

Returns: true iff all bits are set

Definition at line 673 of file bitvector.h.

                               {
         return full_range_operation(
            []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) { return block == mask; }, *this);
      }

◆ any()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::any ( ) const

inline

Returns: true iff at least one bit is set in constant time

Definition at line 668 of file bitvector.h.

668{ return !none(); }

Botan::bitvector_base::none

bool none() const

Definition bitvector.h:658

◆ any_vartime()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::any_vartime ( ) const

inline

Returns: true iff at least one bit is set

Definition at line 663 of file bitvector.h.

663{ return !none_vartime(); }

Botan::bitvector_base::none_vartime

bool none_vartime() const

Definition bitvector.h:651

◆ as()

template<template< typename > typename AllocatorT>

template<bitvectorish OutT>

OutT Botan::bitvector_base< AllocatorT >::as ( ) const

inline

Returns: copies this bitvector into a new bitvector of type OutT

Definition at line 430 of file bitvector.h.

                      {
         return subvector<OutT>(0, size());
      }

Referenced by Botan::bitvector_base< secure_allocator >::to_bytes().

◆ at() [1/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::at ( size_type pos )

inline

Definition at line 567 of file bitvector.h.

                             {
         check_offset(pos);
         return ref(pos);
      }

◆ at() [2/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::at ( size_type pos ) const

inline

Definition at line 573 of file bitvector.h.

                                   {
         check_offset(pos);
         return ref(pos);
      }

◆ back() [1/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::back ( )

inline

Definition at line 583 of file bitvector.h.

583{ return ref(size() - 1); }

◆ back() [2/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::back ( ) const

inline

Definition at line 586 of file bitvector.h.

586{ return ref(size() - 1); }

◆ begin() [1/2]

template<template< typename > typename AllocatorT>

const_iterator Botan::bitvector_base< AllocatorT >::begin ( ) const

inlinenoexcept

Definition at line 888 of file bitvector.h.

888{ return const_iterator(this, 0); }

Botan::bitvector_base::const_iterator

detail::bitvector_iterator< const bitvector_base< AllocatorT > > const_iterator

Definition bitvector.h:239

◆ begin() [2/2]

template<template< typename > typename AllocatorT>

iterator Botan::bitvector_base< AllocatorT >::begin ( )

inlinenoexcept

Definition at line 886 of file bitvector.h.

886{ return iterator(this, 0); }

Botan::bitvector_base::iterator

detail::bitvector_iterator< bitvector_base< AllocatorT > > iterator

Definition bitvector.h:238

◆ capacity()

template<template< typename > typename AllocatorT>

size_type Botan::bitvector_base< AllocatorT >::capacity ( ) const

inline

Definition at line 536 of file bitvector.h.

536{ return m_blocks.capacity() * block_size_bits; }

◆ cbegin()

template<template< typename > typename AllocatorT>

const_iterator Botan::bitvector_base< AllocatorT >::cbegin ( ) const

inlinenoexcept

Definition at line 890 of file bitvector.h.

890{ return const_iterator(this, 0); }

◆ cend()

template<template< typename > typename AllocatorT>

const_iterator Botan::bitvector_base< AllocatorT >::cend ( )

inlinenoexcept

Definition at line 896 of file bitvector.h.

896{ return const_iterator(this, size()); }

◆ ct_conditional_xor()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

void Botan::bitvector_base< AllocatorT >::ct_conditional_xor	(	CT::Choice	condition,
		const OtherT &	other )

inline

Implements::

if(condition) { *this ^= other; }

omitting runtime dependence on any of the parameters.

Definition at line 854 of file bitvector.h.

                                                                       {
         BOTAN_ASSERT_NOMSG(m_bits == other.m_bits);
         BOTAN_ASSERT_NOMSG(m_blocks.size() == other.m_blocks.size());
 
         auto maybe_xor = overloaded{
            [m = CT::Mask<uint64_t>::from_choice(condition)](uint64_t lhs, uint64_t rhs) -> uint64_t {
               return lhs ^ m.if_set_return(rhs);
            },
            [m = CT::Mask<uint32_t>::from_choice(condition)](uint32_t lhs, uint32_t rhs) -> uint32_t {
               return lhs ^ m.if_set_return(rhs);
            },
            [m = CT::Mask<uint16_t>::from_choice(condition)](uint16_t lhs, uint16_t rhs) -> uint16_t {
               return lhs ^ m.if_set_return(rhs);
            },
            [m = CT::Mask<uint8_t>::from_choice(condition)](uint8_t lhs, uint8_t rhs) -> uint8_t {
               return lhs ^ m.if_set_return(rhs);
            },
         };
 
         full_range_operation(maybe_xor, *this, unwrap_strong_type(other));
      }

◆ empty()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::empty ( ) const

inline

Definition at line 398 of file bitvector.h.

398{ return m_bits == 0; }

Referenced by Botan::bitvector_base< secure_allocator >::pop_back().

◆ end() [1/2]

template<template< typename > typename AllocatorT>

const_iterator Botan::bitvector_base< AllocatorT >::end ( ) const

inlinenoexcept

Definition at line 894 of file bitvector.h.

894{ return const_iterator(this, size()); }

◆ end() [2/2]

template<template< typename > typename AllocatorT>

iterator Botan::bitvector_base< AllocatorT >::end ( )

inlinenoexcept

Definition at line 892 of file bitvector.h.

892{ return iterator(this, size()); }

◆ equals()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

bool Botan::bitvector_base< AllocatorT >::equals ( const OtherT & other ) const

inlinenoexcept

Returns: true if other contains the same bit pattern as this

Definition at line 449 of file bitvector.h.

                                                      {
         return (*this ^ other).none();
      }

◆ equals_vartime()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

bool Botan::bitvector_base< AllocatorT >::equals_vartime ( const OtherT & other ) const

inlinenoexcept

Returns: true if other contains the same bit pattern as this

Definition at line 438 of file bitvector.h.

                                                              {
         return size() == other.size() &&
                full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) { return lhs == rhs; },
                                     *this,
                                     unwrap_strong_type(other));
      }

◆ flip() [1/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::flip ( )

inline

Flips all currently allocated bits.

Definition at line 642 of file bitvector.h.

                             {
         full_range_operation([](std::unsigned_integral auto block) -> decltype(block) { return ~block; }, *this);
         zero_unused_bits();
         return *this;
      }

◆ flip() [2/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::flip ( size_type pos )

inline

Flips the bit at position pos.

Exceptions

Botan::Invalid_Argument if pos is out of range

Definition at line 633 of file bitvector.h.

                                          {
         check_offset(pos);
         ref(pos).flip();
         return *this;
      }

◆ from_bytes()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::from_bytes	(	std::span< const uint8_t >	bytes,
		std::optional< size_type >	bits = std::nullopt )

inline

Re-initialize the bitvector with the given bytes. See the respective constructor for details. This should be used only when trying to save allocations. Otherwise, use the constructor.

Parameters

bytes	the byte range to load bits from
bits	(optional) if not all `bytes` should be loaded in full

Definition at line 464 of file bitvector.h.

                                                                                              {
         m_bits = bits.value_or(bytes.size_bytes() * 8);
         BOTAN_ARG_CHECK(m_bits <= bytes.size_bytes() * 8, "not enough data to load so many bits");
         resize(m_bits);
 
         // load as much aligned data as possible
         const auto verbatim_blocks = m_bits / block_size_bits;
         const auto verbatim_bytes = verbatim_blocks * block_size_bytes;
         if(verbatim_blocks > 0) {
            typecast_copy(std::span{m_blocks}.first(verbatim_blocks), bytes.first(verbatim_bytes));
         }
 
         // load remaining unaligned data
         for(size_type i = verbatim_bytes * 8; i < m_bits; ++i) {
            ref(i) = ((bytes[i >> 3] & (uint8_t(1) << (i & 7))) != 0);
         }
      }

Referenced by Botan::bitvector_base< secure_allocator >::bitvector_base().

◆ front() [1/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::front ( )

inline

Definition at line 578 of file bitvector.h.

578{ return ref(0); }

◆ front() [2/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::front ( ) const

inline

Definition at line 581 of file bitvector.h.

581{ return ref(0); }

◆ hamming_weight()

template<template< typename > typename AllocatorT>

size_type Botan::bitvector_base< AllocatorT >::hamming_weight ( ) const

inline

Counts the number of 1-bits in the bitvector in constant time.

Returns: the "population count" (or hamming weight) of the bitvector

Definition at line 420 of file bitvector.h.

                                       {
         size_type acc = 0;
         full_range_operation([&](std::unsigned_integral auto block) { acc += ct_popcount(block); }, *this);
         return acc;
      }

Referenced by Botan::bitvector_base< secure_allocator >::all(), and Botan::bitvector_base< secure_allocator >::none().

◆ has_odd_hamming_weight()

template<template< typename > typename AllocatorT>

CT::Choice Botan::bitvector_base< AllocatorT >::has_odd_hamming_weight ( ) const

inline

Returns: true iff the number of 1-bits in this is odd, false otherwise (constant time)

Definition at line 405 of file bitvector.h.

                                              {
         uint64_t acc = 0;
         full_range_operation([&](std::unsigned_integral auto block) { acc ^= block; }, *this);
 
         for(size_t i = (sizeof(acc) * 8) >> 1; i > 0; i >>= 1) {
            acc ^= acc >> i;
         }
 
         return CT::Choice::from_int(acc & one);
      }

◆ none()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::none ( ) const

inline

Returns: true iff no bit is set in constant time

Definition at line 658 of file bitvector.h.

658{ return hamming_weight() == 0; }

Referenced by Botan::bitvector_base< secure_allocator >::any().

◆ none_vartime()

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::none_vartime ( ) const

inline

Returns: true iff no bit is set

Definition at line 651 of file bitvector.h.

                                {
         return full_range_operation([](std::unsigned_integral auto block) { return block == 0; }, *this);
      }

Referenced by Botan::bitvector_base< secure_allocator >::any_vartime().

◆ operator&=()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

auto & Botan::bitvector_base< AllocatorT >::operator&= ( const OtherT & other )

inline

Definition at line 823 of file bitvector.h.

                                            {
         full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs & rhs; },
                              *this,
                              unwrap_strong_type(other));
         return *this;
      }

◆ operator[]() [1/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::operator[] ( size_type pos )

inline

Definition at line 683 of file bitvector.h.

683{ return ref(pos); }

◆ operator[]() [2/2]

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::operator[] ( size_type pos ) const

inline

Definition at line 686 of file bitvector.h.

686{ return ref(pos); }

◆ operator^=()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

auto & Botan::bitvector_base< AllocatorT >::operator^= ( const OtherT & other )

inline

Definition at line 831 of file bitvector.h.

                                            {
         full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs ^ rhs; },
                              *this,
                              unwrap_strong_type(other));
         return *this;
      }

◆ operator|=()

template<template< typename > typename AllocatorT>

template<bitvectorish OtherT>

auto & Botan::bitvector_base< AllocatorT >::operator|= ( const OtherT & other )

inline

Definition at line 815 of file bitvector.h.

                                            {
         full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs | rhs; },
                              *this,
                              unwrap_strong_type(other));
         return *this;
      }

◆ operator~()

template<template< typename > typename AllocatorT>

auto Botan::bitvector_base< AllocatorT >::operator~ ( )

inline

Definition at line 808 of file bitvector.h.

                       {
         auto newbv = *this;
         newbv.flip();
         return newbv;
      }

◆ pop_back()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::pop_back ( )

inline

Definition at line 556 of file bitvector.h.

                      {
         if(!empty()) {
            resize(size() - 1);
         }
      }

◆ push_back()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::push_back ( bool bit )

inline

Definition at line 550 of file bitvector.h.

                               {
         const auto i = size();
         resize(i + 1);
         ref(i) = bit;
      }

◆ reserve()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::reserve ( size_type bits )

inline

Definition at line 538 of file bitvector.h.

538{ m_blocks.reserve(ceil_toblocks(bits)); }

◆ resize()

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::resize ( size_type bits )

inline

Definition at line 540 of file bitvector.h.

                                  {
         const auto new_number_of_blocks = ceil_toblocks(bits);
         if(new_number_of_blocks != m_blocks.size()) {
            m_blocks.resize(new_number_of_blocks);
         }
 
         m_bits = bits;
         zero_unused_bits();
      }

Referenced by Botan::bitvector_base< secure_allocator >::from_bytes(), Botan::bitvector_base< secure_allocator >::pop_back(), and Botan::bitvector_base< secure_allocator >::push_back().

◆ set() [1/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::set ( )

inline

Sets all currently allocated bits.

Definition at line 601 of file bitvector.h.

                            {
         full_range_operation(
            [](std::unsigned_integral auto block) -> decltype(block) { return static_cast<decltype(block)>(~0); },
            *this);
         zero_unused_bits();
         return *this;
      }

◆ set() [2/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::set ( size_type pos )

inline

Sets the bit at position pos.

Exceptions

Botan::Invalid_Argument if pos is out of range

Definition at line 592 of file bitvector.h.

                                         {
         check_offset(pos);
         ref(pos).set();
         return *this;
      }

◆ size()

template<template< typename > typename AllocatorT>

size_type Botan::bitvector_base< AllocatorT >::size ( ) const

inline

Definition at line 400 of file bitvector.h.

400{ return m_bits; }

◆ subvector() [1/2]

template<template< typename > typename AllocatorT>

template<typename OutT>
requires (std::unsigned_integral<strong_type_wrapped_type<OutT>> && !std::same_as<bool, strong_type_wrapped_type<OutT>>)

OutT Botan::bitvector_base< AllocatorT >::subvector ( size_type pos ) const

inline

Extracts a subvector of bits as an unsigned integral type OutT starting from bit pos and copying exactly sizeof(OutT)*8 bits.

Hint: The bits are in big-endian order, i.e. the least significant bit is the 0th bit and the most significant bit it the n-th. Hence, addressing the bits with bitwise operations is done like so: bool bit = (out_int >> pos) & 1;

Definition at line 738 of file bitvector.h.

                                          {
         using result_t = strong_type_wrapped_type<OutT>;
         constexpr size_t bits = sizeof(result_t) * 8;
         BOTAN_ARG_CHECK(pos + bits <= size(), "Not enough bits to copy");
         result_t out = 0;
 
         if(pos % 8 == 0) {
            out = load_le<result_t>(std::span{m_blocks}.subspan(block_index(pos)).template first<sizeof(result_t)>());
         } else {
            BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(*this, pos, bits);
            range_operation(
               [&](std::unsigned_integral auto integer) {
                  if constexpr(std::same_as<result_t, decltype(integer)>) {
                     out = integer;
                  }
               },
               op);
         }
 
         return wrap_strong_type<OutT>(out);
      }

◆ subvector() [2/2]

template<template< typename > typename AllocatorT>

template<bitvectorish OutT = bitvector_base<AllocatorT>>

auto Botan::bitvector_base< AllocatorT >::subvector	(	size_type	pos,
		std::optional< size_type >	length = std::nullopt ) const

inline

Creates a new bitvector with a subsection of this bitvector starting at pos copying exactly length bits.

Definition at line 698 of file bitvector.h.

                                                                                      {
         size_type bitlen = length.value_or(size() - pos);
         BOTAN_ARG_CHECK(pos + bitlen <= size(), "Not enough bits to copy");
 
         OutT newvector(bitlen);
 
         // Handle bitvectors that are wrapped in strong types
         auto& newvector_unwrapped = unwrap_strong_type(newvector);
 
         if(bitlen > 0) {
            if(pos % 8 == 0) {
               copy_mem(
                  newvector_unwrapped.m_blocks,
                  std::span{m_blocks}.subspan(block_index(pos), block_index(pos + bitlen - 1) - block_index(pos) + 1));
            } else {
               BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> from_op(
                  *this, pos, bitlen);
               BitRangeOperator<strong_type_wrapped_type<OutT>> to_op(
                  unwrap_strong_type(newvector_unwrapped), 0, bitlen);
               range_operation([](auto /* to */, auto from) { return from; }, to_op, from_op);
            }
 
            newvector_unwrapped.zero_unused_bits();
         }
 
         return newvector;
      }

Referenced by Botan::bitvector_base< secure_allocator >::as().

◆ subvector_replace()

template<template< typename > typename AllocatorT>

template<typename InT>
requires (std::unsigned_integral<strong_type_wrapped_type<InT>> && !std::same_as<bool, InT>)

void Botan::bitvector_base< AllocatorT >::subvector_replace	(	size_type	pos,
		InT	value )

inline

Replaces a subvector of bits with the bits of another bitvector value starting at bit pos. The number of bits to replace is determined by the size of value.

Note: This is currently supported for byte-aligned pos only.

Exceptions

Not_Implemented when called with pos not divisible by 8.

Parameters

pos	the position to start replacing bits
value	the bitvector to copy bits from

Definition at line 774 of file bitvector.h.

                                                       {
         using in_t = strong_type_wrapped_type<InT>;
         constexpr size_t bits = sizeof(in_t) * 8;
         BOTAN_ARG_CHECK(pos + bits <= size(), "Not enough bits to replace");
 
         if(pos % 8 == 0) {
            store_le(std::span{m_blocks}.subspan(block_index(pos)).template first<sizeof(in_t)>(),
                     unwrap_strong_type(value));
         } else {
            BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(*this, pos, bits);
            range_operation(
               [&]<std::unsigned_integral BlockT>(BlockT block) -> BlockT {
                  if constexpr(std::same_as<in_t, BlockT>) {
                     return unwrap_strong_type(value);
                  } else {
                     // This should never be reached. BOTAN_ASSERT_UNREACHABLE()
                     // caused warning "unreachable code" on MSVC, though. You
                     // don't say!
                     //
                     // Returning the given block back, is the most reasonable
                     // thing to do in this case, though.
                     return block;
                  }
               },
               op);
         }
      }

◆ to_bytes() [1/2]

template<template< typename > typename AllocatorT>

template<concepts::resizable_byte_buffer OutT = std::conditional_t<uses_secure_allocator, secure_vector<uint8_t>, std::vector<uint8_t>>>

OutT Botan::bitvector_base< AllocatorT >::to_bytes ( ) const

inline

Renders the bitvector into a byte array. By default, this will use std::vector<uint8_t> or Botan::secure_vector<uint8_t>, depending on the allocator used by the bitvector. The rendering is compatible with the bit layout explained in the respective constructor.

Definition at line 490 of file bitvector.h.

                            {
         OutT out(ceil_tobytes(m_bits));
         to_bytes(out);
         return out;
      }

Referenced by Botan::Classic_McEliece_Encryptor::raw_kem_encrypt(), and Botan::bitvector_base< secure_allocator >::to_bytes().

◆ to_bytes() [2/2]

template<template< typename > typename AllocatorT>

void Botan::bitvector_base< AllocatorT >::to_bytes ( std::span< uint8_t > out ) const

inline

Renders the bitvector into a properly sized byte range.

Parameters

out	a byte range that has a length of at least `ceil_tobytes(size())`.

Definition at line 501 of file bitvector.h.

                                                {
         const auto bytes_needed = ceil_tobytes(m_bits);
         BOTAN_ARG_CHECK(bytes_needed <= out.size_bytes(), "Not enough space to render bitvector");
 
         // copy as much aligned data as possible
         const auto verbatim_blocks = m_bits / block_size_bits;
         const auto verbatim_bytes = verbatim_blocks * block_size_bytes;
         if(verbatim_blocks > 0) {
            typecast_copy(out.first(verbatim_bytes), std::span{m_blocks}.first(verbatim_blocks));
         }
 
         // copy remaining unaligned data
         clear_mem(out.subspan(verbatim_bytes));
         for(size_type i = verbatim_bytes * 8; i < m_bits; ++i) {
            out[i >> 3] |= ref(i).template as<uint8_t>() << (i & 7);
         }
      }

◆ to_string()

template<template< typename > typename AllocatorT>

std::string Botan::bitvector_base< AllocatorT >::to_string ( ) const

inline

Renders this bitvector into a sequence of "0"s and "1"s. This is meant for debugging purposes and is not efficient.

Definition at line 523 of file bitvector.h.

                                  {
         std::stringstream ss;
         for(size_type i = 0; i < size(); ++i) {
            ss << ref(i);
         }
         return ss.str();
      }

◆ unset() [1/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::unset ( )

inline

Unsets all currently allocated bits.

Definition at line 622 of file bitvector.h.

                              {
         full_range_operation(
            [](std::unsigned_integral auto block) -> decltype(block) { return static_cast<decltype(block)>(0); },
            *this);
         return *this;
      }

◆ unset() [2/2]

template<template< typename > typename AllocatorT>

bitvector_base & Botan::bitvector_base< AllocatorT >::unset ( size_type pos )

inline

Unsets the bit at position pos.

Exceptions

Botan::Invalid_Argument if pos is out of range

Definition at line 613 of file bitvector.h.

                                           {
         check_offset(pos);
         ref(pos).unset();
         return *this;
      }

Friends And Related Symbol Documentation

◆ bitvector_base

template<template< typename > typename AllocatorT>

template<template< typename > typename FriendAllocatorT>

friend class bitvector_base

friend

Definition at line 247 of file bitvector.h.

Member Data Documentation

◆ block_size_bits

template<template< typename > typename AllocatorT>

size_type Botan::bitvector_base< AllocatorT >::block_size_bits = block_size_bytes * 8

staticconstexpr

Definition at line 242 of file bitvector.h.

◆ block_size_bytes

template<template< typename > typename AllocatorT>

size_type Botan::bitvector_base< AllocatorT >::block_size_bytes = sizeof(block_type)

staticconstexpr

Definition at line 241 of file bitvector.h.

◆ uses_secure_allocator

template<template< typename > typename AllocatorT>

bool Botan::bitvector_base< AllocatorT >::uses_secure_allocator = std::is_same_v<allocator_type, secure_allocator<block_type>>

staticconstexpr

Definition at line 243 of file bitvector.h.

The documentation for this class was generated from the following file:

src/lib/utils/bitvector/bitvector.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ block_type

◆ const_iterator

◆ iterator

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ bitvector_base() [1/4]

◆ bitvector_base() [2/4]

◆ bitvector_base() [3/4]

◆ bitvector_base() [4/4]

Member Function Documentation

◆ _const_time_poison()

◆ _const_time_unpoison()

◆ all()

◆ all_vartime()

◆ any()

◆ any_vartime()

◆ as()

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ cbegin()

◆ cend()

◆ ct_conditional_xor()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equals()

◆ equals_vartime()

◆ flip() [1/2]

◆ flip() [2/2]

◆ from_bytes()

◆ front() [1/2]

◆ front() [2/2]

◆ hamming_weight()

◆ has_odd_hamming_weight()

◆ none()

◆ none_vartime()

◆ operator&=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ operator^=()

◆ operator|=()

◆ operator~()

◆ pop_back()

◆ push_back()

◆ reserve()

◆ resize()

◆ set() [1/2]

◆ set() [2/2]

◆ size()

◆ subvector() [1/2]

◆ subvector() [2/2]

◆ subvector_replace()

◆ to_bytes() [1/2]

◆ to_bytes() [2/2]

◆ to_string()

◆ unset() [1/2]

◆ unset() [2/2]

Friends And Related Symbol Documentation

◆ bitvector_base

Member Data Documentation

◆ block_size_bits

◆ block_size_bytes

◆ uses_secure_allocator