247 template <
template <
typename>
typename FriendAllocatorT>
253 static constexpr size_type block_index_mask = (one << block_offset_shift) - 1;
255 static constexpr size_type block_index(
size_type pos) {
return pos >> block_offset_shift; }
257 static constexpr size_type block_offset(
size_type pos) {
return pos & block_index_mask; }
264 template <
typename BlockT>
265 requires std::same_as<block_type, std::remove_cv_t<BlockT>>
270 constexpr bitref_base(std::span<BlockT> blocks,
size_type pos) noexcept :
271 m_block(blocks[block_index(pos)]), m_mask(one << block_offset(pos)) {}
274 bitref_base() =
delete;
275 bitref_base(
const bitref_base&)
noexcept =
default;
276 bitref_base(bitref_base&&) noexcept = default;
277 bitref_base& operator=(const bitref_base&) = delete;
278 bitref_base& operator=(bitref_base&&) = delete;
280 ~bitref_base() = default;
284 constexpr operator
bool() const noexcept {
return is_set(); }
286 constexpr bool is_set() const noexcept {
return (m_block & m_mask) > 0; }
288 template <std::
unsigned_
integral T>
289 constexpr T
as() const noexcept {
290 return static_cast<T
>(is_set());
293 constexpr CT::Choice as_choice() const noexcept {
307 template <
typename BlockT>
308 class bitref final :
public bitref_base<BlockT> {
310 using bitref_base<BlockT>::bitref_base;
320 template <
typename BlockT>
321 requires(!std::is_const_v<BlockT>)
324 using bitref_base<BlockT>::bitref_base;
331 this->m_block |= this->m_mask;
336 this->m_block &= ~this->m_mask;
341 this->m_block ^= this->m_mask;
355 this->m_block = mask.select(this->m_mask | this->m_block, this->m_block & ~this->m_mask);
366 this->m_block &=
~CT::Mask<BlockT>::expand(other).if_not_set_return(this->m_mask);
371 this->m_block &=
~CT::Mask<BlockT>::from_choice(other).if_not_set_return(this->m_mask);
415 std::optional<size_type> bits = std::nullopt) :
420 bitvector_base(std::initializer_list<block_type> blocks, std::optional<size_type> bits = std::nullopt) :
423 bool empty()
const {
return m_bits == 0; }
432 full_range_operation([&](std::unsigned_integral
auto block) { acc ^= block; }, *
this);
434 for(
size_t i = (
sizeof(acc) * 8) >> 1; i > 0; i >>= 1) {
447 full_range_operation([&](std::unsigned_integral
auto block) { acc +=
ct_popcount(block); }, *
this);
454 template <bitvectorish OutT>
462 template <bitvectorish OtherT>
464 return size() == other.size() &&
465 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) {
return lhs == rhs; },
473 template <bitvectorish OtherT>
474 bool equals(
const OtherT& other)
const noexcept {
475 if(
size() != other.size()) {
480 full_range_operation(
481 [&]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) { acc |=
static_cast<uint64_t
>(lhs ^ rhs); },
498 void from_bytes(std::span<const uint8_t> bytes, std::optional<size_type> bits = std::nullopt) {
499 const size_type new_bits = bits.has_value()
502 const size_type bytes_needed = (new_bits / 8) + (new_bits % 8 != 0 ? 1 : 0);
503 BOTAN_ARG_CHECK(bytes_needed <= bytes.size_bytes(),
"not enough data to load so many bits");
509 if(verbatim_blocks > 0) {
510 typecast_copy(std::span{m_blocks}.first(verbatim_blocks), bytes.first(verbatim_bytes));
514 for(
size_type i = verbatim_bytes * 8; i < new_bits; ++i) {
515 ref(i) = ((bytes[i >> 3] & (uint8_t(1) << (i & 7))) != 0);
526 std::conditional_t<uses_secure_allocator, secure_vector<uint8_t>, std::vector<uint8_t>>>
540 BOTAN_ARG_CHECK(bytes_needed <= out.size_bytes(),
"Not enough space to render bitvector");
545 if(verbatim_blocks > 0) {
546 typecast_copy(out.first(verbatim_bytes), std::span{m_blocks}.first(verbatim_blocks));
551 for(
size_type i = verbatim_bytes * 8; i < m_bits; ++i) {
552 out[i >> 3] |= ref(i).template
as<uint8_t>() << (i & 7);
561 std::stringstream ss;
578 const auto new_number_of_blocks = ceil_toblocks(bits);
579 const auto old_number_of_blocks = m_blocks.size();
580 if(new_number_of_blocks > old_number_of_blocks) {
581 m_blocks.insert(m_blocks.end(), new_number_of_blocks - old_number_of_blocks,
block_type(0));
582 }
else if(new_number_of_blocks < old_number_of_blocks) {
583 m_blocks.erase(m_blocks.begin() + new_number_of_blocks, m_blocks.end());
591 const auto i =
size();
597 const auto i =
size();
627 auto front()
const {
return ref(0); }
648 full_range_operation(
649 [](std::unsigned_integral
auto block) ->
decltype(block) {
650 return static_cast<decltype(block)
>(~static_cast<decltype(block)>(0));
669 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
670 *
this, offset, length);
672 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) -> BlockT {
675 return static_cast<BlockT
>(block | mask);
695 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
696 *
this, offset, length);
698 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) -> BlockT {
701 return static_cast<BlockT
>(block &
static_cast<BlockT
>(~mask));
723 full_range_operation(
724 [](std::unsigned_integral
auto block) ->
decltype(block) {
return static_cast<decltype(block)
>(0); },
743 full_range_operation([](std::unsigned_integral
auto block) ->
decltype(block) {
return ~block; }, *
this);
752 return full_range_operation([](std::unsigned_integral
auto block) {
return block == 0; }, *
this);
774 return full_range_operation(
775 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) {
return block == mask; }, *
this);
797 template <bitvectorish OutT = bitvector_base<AllocatorT>>
810 newvector_unwrapped.m_blocks,
811 std::span{m_blocks}.subspan(block_index(pos), block_index(pos +
bitlen - 1) - block_index(pos) + 1));
813 const BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> from_op(
815 const BitRangeOperator<strong_type_wrapped_type<OutT>> to_op(
817 range_operation([](
auto ,
auto from) {
return from; }, to_op, from_op);
820 newvector_unwrapped.zero_unused_bits();
835 template <
typename OutT>
836 requires(std::unsigned_integral<strong_type_wrapped_type<OutT>> &&
837 !std::same_as<bool, strong_type_wrapped_type<OutT>>)
840 constexpr size_t bits =
sizeof(result_t) * 8;
845 out =
load_le<result_t>(std::span{m_blocks}.subspan(block_index(pos)).
template first<
sizeof(result_t)>());
847 const BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
850 [&](std::unsigned_integral
auto integer) {
851 if constexpr(std::same_as<result_t,
decltype(integer)>) {
873 template <
typename InT>
874 requires(std::unsigned_integral<strong_type_wrapped_type<InT>> && !std::same_as<bool, InT>)
877 constexpr size_t bits =
sizeof(in_t) * 8;
881 store_le(std::span{m_blocks}.subspan(block_index(pos)).
template first<
sizeof(in_t)>(),
884 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(*
this, pos, bits);
886 [&]<std::unsigned_integral BlockT>(BlockT block) -> BlockT {
887 if constexpr(std::same_as<in_t, BlockT>) {
915 template <bitvectorish OtherT>
917 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT {
return lhs | rhs; },
923 template <bitvectorish OtherT>
925 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT {
return lhs & rhs; },
931 template <bitvectorish OtherT>
933 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT {
return lhs ^ rhs; },
954 template <bitvectorish OtherT>
961 return lhs ^ m.if_set_return(rhs);
964 return lhs ^ m.if_set_return(rhs);
967 return lhs ^ m.if_set_return(rhs);
970 return lhs ^ m.if_set_return(rhs);
1002 void check_offset(
size_type pos)
const {
1008 void zero_unused_bits() {
1009 const auto first_unused_bit =
size();
1013 const block_type mask = (one << block_offset(first_unused_bit)) - one;
1014 m_blocks[block_index(first_unused_bit)] &= mask;
1027 enum class BitRangeAlignment : uint8_t { byte_aligned, no_alignment };
1040 template <
typename BitvectorT, auto alignment = BitRangeAlignment::
byte_aligned>
1041 requires is_bitvector_v<std::remove_cvref_t<BitvectorT>>
1042 class BitRangeOperator {
1044 constexpr static bool is_const() {
return std::is_const_v<BitvectorT>; }
1046 struct UnalignedDataHelper {
1047 const uint8_t padding_bits;
1048 const uint8_t bits_to_byte_alignment;
1052 BitRangeOperator(BitvectorT& source,
size_type start_bitoffset,
size_type bitlength) :
1054 m_start_bitoffset(start_bitoffset),
1055 m_bitlength(bitlength),
1056 m_unaligned_helper({.padding_bits =
static_cast<uint8_t
>(start_bitoffset % 8),
1057 .bits_to_byte_alignment =
static_cast<uint8_t
>(8 - (start_bitoffset % 8))}),
1058 m_read_bitpos(start_bitoffset),
1059 m_write_bitpos(start_bitoffset) {
1060 BOTAN_ASSERT(!is_byte_aligned() || (m_start_bitoffset % 8 == 0),
"byte alignment guarantee");
1061 BOTAN_ASSERT(m_source.size() >= m_start_bitoffset + m_bitlength,
"enough bytes in underlying source");
1064 explicit BitRangeOperator(BitvectorT& source) : BitRangeOperator(source, 0, source.size()) {}
1066 static constexpr bool is_byte_aligned() {
return alignment == BitRangeAlignment::byte_aligned; }
1076 size_type bits_to_read()
const {
return m_bitlength - m_read_bitpos + m_start_bitoffset; }
1081 size_type bits_to_write()
const {
return m_bitlength - m_write_bitpos + m_start_bitoffset; }
1088 template <std::
unsigned_
integral BlockT>
1089 BlockT load_next()
const {
1090 constexpr size_type block_size =
sizeof(BlockT);
1091 constexpr size_type block_bits = block_size * 8;
1092 const auto bits_remaining = bits_to_read();
1094 BlockT result_block = 0;
1095 if constexpr(is_byte_aligned()) {
1096 result_block =
load_le(m_source.as_byte_span().subspan(read_bytepos()).
template first<block_size>());
1098 const size_type byte_pos = read_bytepos();
1099 const size_type bits_to_collect = std::min(block_bits, bits_to_read());
1105 std::array<uint8_t, block_size + 1> bytes{};
1106 copy_mem(std::span{bytes}.first(bytes_to_load),
1107 m_source.as_byte_span().subspan(byte_pos, bytes_to_load));
1110 result_block = BlockT(bytes[0]) >> m_unaligned_helper.padding_bits;
1113 if(m_unaligned_helper.bits_to_byte_alignment < bits_to_collect) {
1114 const BlockT block =
load_le(std::span{bytes}.template subspan<1, block_size>());
1115 result_block |= block << m_unaligned_helper.bits_to_byte_alignment;
1119 m_read_bitpos += std::min(block_bits, bits_remaining);
1120 return result_block;
1129 template <std::
unsigned_
integral BlockT>
1130 requires(!is_const())
1131 void store_next(BlockT block) {
1132 constexpr size_type block_size =
sizeof(BlockT);
1133 constexpr size_type block_bits = block_size * 8;
1135 if constexpr(is_byte_aligned()) {
1136 const auto sink = m_source.as_byte_span().subspan(write_bytepos()).template first<block_size>();
1139 const size_type byte_pos = write_bytepos();
1140 const size_type bits_to_store = std::min(block_bits, bits_to_write());
1142 uint8_t& first_byte = m_source.as_byte_span()[byte_pos];
1145 first_byte = (first_byte & uint8_t(0xFF >> m_unaligned_helper.bits_to_byte_alignment)) |
1146 uint8_t(block << m_unaligned_helper.padding_bits);
1149 if(m_unaligned_helper.bits_to_byte_alignment < bits_to_store) {
1151 const auto remaining_bytes = m_source.as_byte_span().subspan(byte_pos + 1, bytes_to_store);
1156 std::array<uint8_t, block_size> bytes{};
1157 copy_mem(std::span{bytes}.first(bytes_to_store), remaining_bytes);
1159 const BlockT padding_mask = ~(BlockT(-1) >> m_unaligned_helper.bits_to_byte_alignment);
1160 const BlockT new_bytes =
1161 (
load_le(bytes) & padding_mask) | block >> m_unaligned_helper.bits_to_byte_alignment;
1164 copy_mem(remaining_bytes, std::span{bytes}.first(bytes_to_store));
1168 m_write_bitpos += std::min(block_bits, bits_to_write());
1171 template <std::
unsigned_
integral BlockT>
1172 requires(is_byte_aligned() && !is_const())
1173 std::span<BlockT> span(
size_type blocks)
const {
1177 void* ptr =
reinterpret_cast<void*
>(m_source.as_byte_span().data() + read_bytepos());
1178 return {
reinterpret_cast<BlockT*
>(ptr), blocks};
1181 template <std::
unsigned_
integral BlockT>
1182 requires(is_byte_aligned() && is_const())
1183 std::span<const BlockT> span(
size_type blocks)
const {
1187 const void* ptr =
reinterpret_cast<const void*
>(m_source.as_byte_span().data() + read_bytepos());
1188 return {
reinterpret_cast<const BlockT*
>(ptr), blocks};
1192 requires(is_byte_aligned())
1194 m_read_bitpos += bytes * 8;
1195 m_write_bitpos += bytes * 8;
1198 template <std::
unsigned_
integral BlockT>
1199 requires(is_byte_aligned())
1200 size_t is_memory_aligned_to()
const {
1201 const void* cptr = m_source.as_byte_span().data() + read_bytepos();
1202 const void* ptr_before = cptr;
1207 void* ptr =
const_cast<void*
>(cptr);
1208 size_t size =
sizeof(BlockT);
1209 return ptr_before !=
nullptr && std::align(
alignof(BlockT), size, ptr, size) == ptr_before;
1213 size_type read_bytepos()
const {
return m_read_bitpos / 8; }
1215 size_type write_bytepos()
const {
return m_write_bitpos / 8; }
1218 BitvectorT& m_source;
1222 UnalignedDataHelper m_unaligned_helper;
1235 template <
typename FnT,
typename... ParamTs>
1236 requires detail::blockwise_processing_callback<FnT, ParamTs...>
1237 class blockwise_processing_callback_trait {
1239 constexpr static bool needs_mask = detail::blockwise_processing_callback_with_mask<FnT, ParamTs...>;
1240 constexpr static bool is_manipulator = detail::manipulating_blockwise_processing_callback<FnT, ParamTs...>;
1241 constexpr static bool is_predicate = detail::predicate_blockwise_processing_callback<FnT, ParamTs...>;
1242 static_assert(!is_manipulator || !is_predicate,
"cannot be manipulator and predicate at the same time");
1248 template <std::unsigned_integral... BlockTs>
1249 requires(all_same_v<std::remove_cv_t<BlockTs>...> &&
sizeof...(BlockTs) ==
sizeof...(ParamTs))
1250 constexpr static bool apply_on_full_blocks(FnT fn, std::span<BlockTs>... blocks) {
1252 const size_type iterations = detail::first(blocks...).size();
1253 for(
size_type i = 0; i < iterations; ++i) {
1254 if constexpr(is_predicate) {
1255 if(!apply(fn, bits, blocks[i]...)) {
1258 }
else if constexpr(is_manipulator) {
1259 detail::first(blocks...)[i] = apply(fn, bits, blocks[i]...);
1261 apply(fn, bits, blocks[i]...);
1270 template <std::unsigned_integral BlockT,
typename... BitRangeOperatorTs>
1271 requires(
sizeof...(BitRangeOperatorTs) ==
sizeof...(ParamTs))
1272 constexpr static bool apply_on_unaligned_blocks(FnT fn, BitRangeOperatorTs&... ops) {
1273 constexpr size_type block_bits =
sizeof(BlockT) * 8;
1274 auto bits = detail::first(ops...).bits_to_read();
1280 while(bits > block_bits * 2 - 8) {
1282 if constexpr(is_predicate) {
1283 if(!apply(fn, bits, ops.template load_next<BlockT>()...)) {
1286 }
else if constexpr(is_manipulator) {
1287 detail::first(ops...).store_next(apply(fn, bits, ops.template load_next<BlockT>()...));
1289 apply(fn, bits, ops.template load_next<BlockT>()...);
1296 template <std::unsigned_integral... BlockTs>
1297 requires(all_same_v<std::remove_cv_t<BlockTs>...>)
1298 constexpr static auto apply(FnT fn,
size_type bits, BlockTs... blocks) {
1299 if constexpr(needs_mask) {
1302 return fn(blocks...);
1314 template <std::unsigned_integral BlockT,
typename FnT,
typename... BitRangeOperatorTs>
1315 requires(detail::blockwise_processing_callback<FnT, BitRangeOperatorTs...> &&
1316 sizeof...(BitRangeOperatorTs) > 0)
1317 static bool _process_in_fully_aligned_blocks_of(FnT fn, BitRangeOperatorTs&... ops) {
1318 constexpr size_type block_bytes =
sizeof(BlockT);
1319 constexpr size_type block_bits = block_bytes * 8;
1320 const size_type blocks = detail::first(ops...).bits_to_read() / block_bits;
1322 using callback_trait = blockwise_processing_callback_trait<FnT, BitRangeOperatorTs...>;
1323 const auto result = callback_trait::apply_on_full_blocks(fn, ops.template span<BlockT>(blocks)...);
1324 (ops.advance(block_bytes * blocks), ...);
1333 template <std::unsigned_integral BlockT,
typename FnT,
typename... BitRangeOperatorTs>
1334 requires(detail::blockwise_processing_callback<FnT, BitRangeOperatorTs...>)
1335 static bool _process_in_unaligned_blocks_of(FnT fn, BitRangeOperatorTs&... ops) {
1336 using callback_trait = blockwise_processing_callback_trait<FnT, BitRangeOperatorTs...>;
1337 return callback_trait::template apply_on_unaligned_blocks<BlockT>(fn, ops...);
1353 template <
typename FnT,
typename... BitRangeOperatorTs>
1354 requires(detail::blockwise_processing_callback<FnT, BitRangeOperatorTs...> &&
1355 sizeof...(BitRangeOperatorTs) > 0)
1356 static bool range_operation(FnT fn, BitRangeOperatorTs... ops) {
1357 BOTAN_ASSERT(has_equal_lengths(ops...),
"all BitRangeOperators have the same length");
1359 if constexpr((BitRangeOperatorTs::is_byte_aligned() && ...)) {
1369 if(detail::first(ops...).
size() != 0) {
1370 const bool alignment = (ops.template is_memory_aligned_to<uint64_t>() && ...);
1374 return _process_in_fully_aligned_blocks_of<uint64_t>(fn, ops...) &&
1375 _process_in_fully_aligned_blocks_of<uint32_t>(fn, ops...) &&
1376 _process_in_fully_aligned_blocks_of<uint16_t>(fn, ops...) &&
1377 _process_in_unaligned_blocks_of<uint8_t>(fn, ops...);
1379 return _process_in_unaligned_blocks_of<uint64_t>(fn, ops...) &&
1380 _process_in_unaligned_blocks_of<uint32_t>(fn, ops...) &&
1381 _process_in_unaligned_blocks_of<uint16_t>(fn, ops...) &&
1382 _process_in_unaligned_blocks_of<uint8_t>(fn, ops...);
1389 template <
typename FnT,
typename... BitvectorTs>
1390 requires(detail::blockwise_processing_callback<FnT, BitvectorTs...> &&
1391 (is_bitvector_v<std::remove_cvref_t<BitvectorTs>> && ... &&
true))
1392 static bool full_range_operation(FnT&& fn, BitvectorTs&... bitvecs) {
1393 BOTAN_ASSERT(has_equal_lengths(bitvecs...),
"all bitvectors have the same length");
1394 return range_operation(std::forward<FnT>(fn), BitRangeOperator<BitvectorTs>(bitvecs)...);
1397 template <
typename SomeT,
typename... SomeTs>
1398 static bool has_equal_lengths(
const SomeT& v,
const SomeTs&... vs) {
1399 return ((v.size() == vs.size()) && ... &&
true);
1402 template <std::
unsigned_
integral T>
1403 static constexpr T make_mask(
size_type bits) {
1404 const bool max = bits >=
sizeof(T) * 8;
1406 return (T(!max) << bits) - 1;
1409 auto as_byte_span() {
return std::span{m_blocks.data(), m_blocks.size() *
sizeof(
block_type)}; }
1411 auto as_byte_span()
const {
return std::span{m_blocks.data(), m_blocks.size() *
sizeof(
block_type)}; }
1415 std::vector<block_type, allocator_type> m_blocks;