Botan 3.14.1
Crypto and TLS for C&
bitvector.h
Go to the documentation of this file.
1/*
2 * An abstraction for an arbitrarily large bitvector that can
3 * optionally use the secure_allocator. All bitwise accesses and all
4 * constructors are implemented in constant time. Otherwise, only methods
5 * with the "ct_" pre-fix run in constant time.
6 *
7 * (C) 2023-2024 Jack Lloyd
8 * (C) 2023-2024 René Meusel, Rohde & Schwarz Cybersecurity
9 *
10 * Botan is released under the Simplified BSD License (see license.txt)
11 */
12
13#ifndef BOTAN_BIT_VECTOR_H_
14#define BOTAN_BIT_VECTOR_H_
15
16#include <botan/concepts.h>
17#include <botan/mem_ops.h>
18#include <botan/secmem.h>
19#include <botan/strong_type.h>
20#include <botan/internal/bit_ops.h>
21#include <botan/internal/ct_utils.h>
22#include <botan/internal/int_utils.h>
23#include <botan/internal/loadstor.h>
24#include <botan/internal/stl_util.h>
25
26#include <array>
27#include <memory>
28#include <optional>
29#include <span>
30#include <sstream>
31#include <string>
32#include <utility>
33#include <vector>
34
35namespace Botan {
36
37template <template <typename> typename AllocatorT>
38class bitvector_base;
39
40template <typename T>
41struct is_bitvector : std::false_type {};
42
43template <template <typename> typename T>
44struct is_bitvector<bitvector_base<T>> : std::true_type {};
45
46template <typename T>
47constexpr static bool is_bitvector_v = is_bitvector<T>::value;
48
49template <typename T>
50concept bitvectorish = is_bitvector_v<strong_type_wrapped_type<T>>;
51
52namespace detail {
53
54template <typename T0, typename... Ts>
55struct first_type {
56 using type = T0;
57};
58
59// get the first type from a parameter pack
60// TODO: C++26 will bring Parameter Pack indexing:
61// using first_t = Ts...[0];
62template <typename... Ts>
63 requires(sizeof...(Ts) > 0)
65
66// get the first object from a parameter pack
67// TODO: C++26 will bring Parameter Pack indexing:
68// auto first = s...[0];
69template <typename T0, typename... Ts>
70constexpr static first_t<T0, Ts...> first(T0&& t, Ts&&... /*rest*/) {
71 return std::forward<T0>(t);
72}
73
74template <typename OutT, typename>
75using as = OutT;
76
77template <typename FnT, std::unsigned_integral BlockT, typename... ParamTs>
78using blockwise_processing_callback_return_type = std::invoke_result_t<FnT, as<BlockT, ParamTs>...>;
79
80template <typename FnT, typename BlockT, typename... ParamTs>
82 std::unsigned_integral<BlockT> &&
83 (std::same_as<BlockT, blockwise_processing_callback_return_type<FnT, BlockT, ParamTs...>> ||
84 std::same_as<bool, blockwise_processing_callback_return_type<FnT, BlockT, ParamTs...>> ||
85 std::same_as<void, blockwise_processing_callback_return_type<FnT, BlockT, ParamTs...>>);
86
87template <typename FnT, typename... ParamTs>
89 is_blockwise_processing_callback_return_type<FnT, uint8_t, ParamTs...> &&
90 is_blockwise_processing_callback_return_type<FnT, uint16_t, ParamTs...> &&
91 is_blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs...> &&
92 is_blockwise_processing_callback_return_type<FnT, uint64_t, ParamTs...>;
93
94template <typename FnT, typename... ParamTs>
96 is_blockwise_processing_callback_return_type<FnT, uint8_t, ParamTs..., uint8_t /* mask */> &&
97 is_blockwise_processing_callback_return_type<FnT, uint16_t, ParamTs..., uint16_t /* mask */> &&
98 is_blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs..., uint32_t /* mask */> &&
99 is_blockwise_processing_callback_return_type<FnT, uint64_t, ParamTs..., uint64_t /* mask */>;
100
101/**
102 * Defines the callback constraints for the BitRangeOperator. For further
103 * details, see bitvector_base::range_operation().
104 */
105template <typename FnT, typename... ParamTs>
108
109template <typename FnT, typename... ParamTs>
112 std::same_as<uint32_t, blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs...>>) ||
114 std::same_as<uint32_t, blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs..., first_t<ParamTs...>>>);
115
116template <typename FnT, typename... ParamTs>
119 std::same_as<bool, blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs...>>) ||
121 std::same_as<bool, blockwise_processing_callback_return_type<FnT, uint32_t, ParamTs..., first_t<ParamTs...>>>);
122
123template <typename T>
125 private:
126 using size_type = typename T::size_type;
127
128 public:
129 using difference_type = std::make_signed_t<size_type>;
130 using value_type = std::remove_const_t<decltype(std::declval<T>().at(0))>;
133
134 // TODO: technically, this could be a random access iterator
135 using iterator_category = std::bidirectional_iterator_tag;
136
137 public:
140
141 bitvector_iterator(T* bitvector, size_t offset) : m_bitvector(bitvector) { update(offset); }
142
143 bitvector_iterator(const bitvector_iterator& other) noexcept : m_bitvector(other.m_bitvector) {
144 update(other.m_offset);
145 }
146
147 bitvector_iterator(bitvector_iterator&& other) noexcept : m_bitvector(other.m_bitvector) {
148 update(other.m_offset);
149 }
150
152 if(this != &other) {
153 m_bitvector = other.m_bitvector;
154 update(other.m_offset);
155 }
156 return *this;
157 }
158
160 m_bitvector = other.m_bitvector;
161 update(other.m_offset);
162 return *this;
163 }
164
166 update(signed_offset() + 1);
167 return *this;
168 }
169
171 auto copy = *this;
172 update(signed_offset() + 1);
173 return copy;
174 }
175
177 update(signed_offset() - 1);
178 return *this;
179 }
180
182 auto copy = *this;
183 update(signed_offset() - 1);
184 return copy;
185 }
186
187 std::partial_ordering operator<=>(const bitvector_iterator& other) const noexcept {
188 if(m_bitvector == other.m_bitvector) {
189 return m_offset <=> other.m_offset;
190 } else {
191 return std::partial_ordering::unordered;
192 }
193 }
194
195 bool operator==(const bitvector_iterator& other) const noexcept {
196 return m_bitvector == other.m_bitvector && m_offset == other.m_offset;
197 }
198
199 reference operator*() const { return m_bitref.value(); }
200
201 pointer operator->() const { return &(m_bitref.value()); }
202
203 private:
204 void update(size_type new_offset) {
205 m_offset = new_offset;
206 if(m_offset < m_bitvector->size()) {
207 m_bitref.emplace((*m_bitvector)[m_offset]);
208 } else {
209 // end() iterator
210 m_bitref.reset();
211 }
212 }
213
214 difference_type signed_offset() const { return static_cast<difference_type>(m_offset); }
215
216 private:
217 T* m_bitvector;
218 size_type m_offset;
219 mutable std::optional<value_type> m_bitref;
220};
221
222} // namespace detail
223
224/**
225 * An arbitrarily large bitvector with typical bit manipulation and convenient
226 * bitwise access methods. Don't use `bitvector_base` directly, but the type
227 * aliases::
228 *
229 * * bitvector - with a standard allocator
230 * * secure_bitvector - with a secure allocator that auto-scrubs the memory
231 */
232template <template <typename> typename AllocatorT>
233class bitvector_base final {
234 public:
235 using block_type = uint8_t;
236 using size_type = size_t;
237 using allocator_type = AllocatorT<block_type>;
241
242 static constexpr size_type block_size_bytes = sizeof(block_type);
244 static constexpr bool uses_secure_allocator = std::is_same_v<allocator_type, secure_allocator<block_type>>;
245
246 private:
247 template <template <typename> typename FriendAllocatorT>
248 friend class bitvector_base;
249
250 static constexpr block_type one = block_type(1);
251
252 static constexpr size_type block_offset_shift = size_type(3) + ceil_log2(block_size_bytes);
253 static constexpr size_type block_index_mask = (one << block_offset_shift) - 1;
254
255 static constexpr size_type block_index(size_type pos) { return pos >> block_offset_shift; }
256
257 static constexpr size_type block_offset(size_type pos) { return pos & block_index_mask; }
258
259 private:
260 /**
261 * Internal helper to wrap a single bit in the bitvector and provide
262 * certain convenience access methods.
263 */
264 template <typename BlockT>
265 requires std::same_as<block_type, std::remove_cv_t<BlockT>>
266 class bitref_base {
267 private:
268 friend class bitvector_base<AllocatorT>;
269
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)) {}
272
273 public:
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;
279
280 ~bitref_base() = default;
281
282 public:
283 // NOLINTNEXTLINE(*-explicit-conversions,*-explicit-constructor)
284 constexpr operator bool() const noexcept { return is_set(); }
285
286 constexpr bool is_set() const noexcept { return (m_block & m_mask) > 0; }
287
288 template <std::unsigned_integral T>
289 constexpr T as() const noexcept {
290 return static_cast<T>(is_set());
291 }
292
293 constexpr CT::Choice as_choice() const noexcept {
294 return CT::Choice::from_int(static_cast<BlockT>(m_block & m_mask));
295 }
296
297 protected:
298 BlockT& m_block; // NOLINT(*-non-private-member-variable*)
299 BlockT m_mask; // NOLINT(*-non-private-member-variable*)
300 };
301
302 public:
303 /**
304 * Wraps a constant reference into the bitvector. Bit can be accessed
305 * but not modified.
306 */
307 template <typename BlockT>
308 class bitref final : public bitref_base<BlockT> {
309 public:
310 using bitref_base<BlockT>::bitref_base;
311 };
312
313 /**
314 * Wraps a modifiable reference into the bitvector. Bit may be accessed
315 * and modified (e.g. flipped or XOR'ed).
316 *
317 * Constant-time operations are used for the bit manipulations. The
318 * location of the bit in the bit vector may be leaked, though.
319 */
320 template <typename BlockT>
321 requires(!std::is_const_v<BlockT>)
322 class bitref<BlockT> : public bitref_base<BlockT> {
323 public:
324 using bitref_base<BlockT>::bitref_base;
325
326 ~bitref() = default;
327 bitref(const bitref&) noexcept = default;
328 bitref(bitref&&) noexcept = default;
329
330 constexpr bitref& set() noexcept {
331 this->m_block |= this->m_mask;
332 return *this;
333 }
334
335 constexpr bitref& unset() noexcept {
336 this->m_block &= ~this->m_mask;
337 return *this;
338 }
339
340 constexpr bitref& flip() noexcept {
341 this->m_block ^= this->m_mask;
342 return *this;
343 }
344
345 // NOLINTBEGIN
346
347 constexpr bitref& operator=(bool bit) noexcept {
348 this->m_block =
349 CT::Mask<BlockT>::expand(bit).select(this->m_mask | this->m_block, this->m_block & ~this->m_mask);
350 return *this;
351 }
352
353 constexpr bitref& operator=(CT::Choice bit) noexcept {
354 const auto mask = CT::Mask<BlockT>::from_choice(bit);
355 this->m_block = mask.select(this->m_mask | this->m_block, this->m_block & ~this->m_mask);
356 return *this;
357 }
358
359 constexpr bitref& operator=(const bitref& bit) noexcept { return *this = bit.is_set(); }
360
361 constexpr bitref& operator=(bitref&& bit) noexcept { return *this = bit.is_set(); }
362
363 // NOLINTEND
364
365 constexpr bitref& operator&=(bool other) noexcept {
366 this->m_block &= ~CT::Mask<BlockT>::expand(other).if_not_set_return(this->m_mask);
367 return *this;
368 }
369
370 constexpr bitref& operator&=(CT::Choice other) noexcept {
371 this->m_block &= ~CT::Mask<BlockT>::from_choice(other).if_not_set_return(this->m_mask);
372 return *this;
373 }
374
375 constexpr bitref& operator|=(bool other) noexcept {
376 this->m_block |= CT::Mask<BlockT>::expand(other).if_set_return(this->m_mask);
377 return *this;
378 }
379
380 constexpr bitref& operator|=(CT::Choice other) noexcept {
381 this->m_block |= CT::Mask<BlockT>::from_choice(other).if_set_return(this->m_mask);
382 return *this;
383 }
384
385 constexpr bitref& operator^=(bool other) noexcept {
386 this->m_block ^= CT::Mask<BlockT>::expand(other).if_set_return(this->m_mask);
387 return *this;
388 }
389
390 constexpr bitref& operator^=(CT::Choice other) noexcept {
391 this->m_block ^= CT::Mask<BlockT>::from_choice(other).if_set_return(this->m_mask);
392 return *this;
393 }
394 };
395
396 public:
397 bitvector_base() : m_bits(0) {}
398
399 explicit bitvector_base(size_type bits) : m_bits(bits), m_blocks(ceil_toblocks(bits)) {}
400
401 /**
402 * Initialize the bitvector from a byte-array. Bits are taken byte-wise
403 * from least significant to most significant. Example::
404 *
405 * bitvector[0] -> LSB(Byte[0])
406 * bitvector[1] -> LSB+1(Byte[0])
407 * ...
408 * bitvector[8] -> LSB(Byte[1])
409 *
410 * @param bytes The byte vector to be loaded
411 * @param bits The number of bits to be loaded. This must not be more
412 * than the number of bytes in @p bytes.
413 */
414 bitvector_base(std::span<const uint8_t> bytes, /* NOLINT(*-explicit-conversions,*-explicit-constructor) */
415 std::optional<size_type> bits = std::nullopt) :
416 m_bits() {
417 from_bytes(bytes, bits);
418 }
419
420 bitvector_base(std::initializer_list<block_type> blocks, std::optional<size_type> bits = std::nullopt) :
421 m_bits(bits.value_or(blocks.size() * block_size_bits)), m_blocks(blocks.begin(), blocks.end()) {}
422
423 bool empty() const { return m_bits == 0; }
424
425 size_type size() const { return m_bits; }
426
427 /**
428 * @returns true iff the number of 1-bits in this is odd, false otherwise (constant time)
429 */
431 uint64_t acc = 0;
432 full_range_operation([&](std::unsigned_integral auto block) { acc ^= block; }, *this);
433
434 for(size_t i = (sizeof(acc) * 8) >> 1; i > 0; i >>= 1) {
435 acc ^= acc >> i;
436 }
437
438 return CT::Choice::from_int(acc & one);
439 }
440
441 /**
442 * Counts the number of 1-bits in the bitvector in constant time.
443 * @returns the "population count" (or hamming weight) of the bitvector
444 */
446 size_type acc = 0;
447 full_range_operation([&](std::unsigned_integral auto block) { acc += ct_popcount(block); }, *this);
448 return acc;
449 }
450
451 /**
452 * @returns copies this bitvector into a new bitvector of type @p OutT
453 */
454 template <bitvectorish OutT>
455 OutT as() const {
456 return subvector<OutT>(0, size());
457 }
458
459 /**
460 * @returns true if @p other contains the same bit pattern as this
461 */
462 template <bitvectorish OtherT>
463 bool equals_vartime(const OtherT& other) const noexcept {
464 return size() == other.size() &&
465 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) { return lhs == rhs; },
466 *this,
467 unwrap_strong_type(other));
468 }
469
470 /**
471 * @returns true if @p other contains the same bit pattern as this
472 */
473 template <bitvectorish OtherT>
474 bool equals(const OtherT& other) const noexcept {
475 if(size() != other.size()) {
476 return false;
477 }
478
479 uint64_t acc = 0;
480 full_range_operation(
481 [&]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) { acc |= static_cast<uint64_t>(lhs ^ rhs); },
482 *this,
483 unwrap_strong_type(other));
484 return !CT::Choice::from_int(acc).as_bool();
485 }
486
487 /// @name Serialization
488 /// @{
489
490 /**
491 * Re-initialize the bitvector with the given bytes. See the respective
492 * constructor for details. This should be used only when trying to save
493 * allocations. Otherwise, use the constructor.
494 *
495 * @param bytes the byte range to load bits from
496 * @param bits (optional) if not all @p bytes should be loaded in full
497 */
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()
500 ? bits.value()
501 : mul_or_throw<size_t>(8, bytes.size_bytes(), "bitvector input is too large");
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");
504 resize(new_bits);
505
506 // load as much aligned data as possible
507 const auto verbatim_blocks = new_bits / block_size_bits;
508 const auto verbatim_bytes = verbatim_blocks * block_size_bytes;
509 if(verbatim_blocks > 0) {
510 typecast_copy(std::span{m_blocks}.first(verbatim_blocks), bytes.first(verbatim_bytes));
511 }
512
513 // load remaining unaligned data
514 for(size_type i = verbatim_bytes * 8; i < new_bits; ++i) {
515 ref(i) = ((bytes[i >> 3] & (uint8_t(1) << (i & 7))) != 0);
516 }
517 }
518
519 /**
520 * Renders the bitvector into a byte array. By default, this will use
521 * `std::vector<uint8_t>` or `Botan::secure_vector<uint8_t>`, depending on
522 * the allocator used by the bitvector. The rendering is compatible with
523 * the bit layout explained in the respective constructor.
524 */
525 template <concepts::resizable_byte_buffer OutT =
526 std::conditional_t<uses_secure_allocator, secure_vector<uint8_t>, std::vector<uint8_t>>>
527 OutT to_bytes() const {
528 OutT out(ceil_tobytes(m_bits));
529 to_bytes(out);
530 return out;
531 }
532
533 /**
534 * Renders the bitvector into a properly sized byte range.
535 *
536 * @param out a byte range that has a length of at least `ceil_tobytes(size())`.
537 */
538 void to_bytes(std::span<uint8_t> out) const {
539 const auto bytes_needed = ceil_tobytes(m_bits);
540 BOTAN_ARG_CHECK(bytes_needed <= out.size_bytes(), "Not enough space to render bitvector");
541
542 // copy as much aligned data as possible
543 const auto verbatim_blocks = m_bits / block_size_bits;
544 const auto verbatim_bytes = verbatim_blocks * block_size_bytes;
545 if(verbatim_blocks > 0) {
546 typecast_copy(out.first(verbatim_bytes), std::span{m_blocks}.first(verbatim_blocks));
547 }
548
549 // copy remaining unaligned data
550 clear_mem(out.subspan(verbatim_bytes));
551 for(size_type i = verbatim_bytes * 8; i < m_bits; ++i) {
552 out[i >> 3] |= ref(i).template as<uint8_t>() << (i & 7);
553 }
554 }
555
556 /**
557 * Renders this bitvector into a sequence of "0"s and "1"s.
558 * This is meant for debugging purposes and is not efficient.
559 */
560 std::string to_string() const {
561 std::stringstream ss;
562 for(size_type i = 0; i < size(); ++i) {
563 ss << ref(i);
564 }
565 return ss.str();
566 }
567
568 /// @}
569
570 /// @name Capacity Accessors and Modifiers
571 /// @{
572
573 size_type capacity() const { return m_blocks.capacity() * block_size_bits; }
574
575 void reserve(size_type bits) { m_blocks.reserve(ceil_toblocks(bits)); }
576
577 void resize(size_type bits) {
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());
584 }
585
586 m_bits = bits;
587 zero_unused_bits();
588 }
589
590 void push_back(bool bit) {
591 const auto i = size();
592 resize(i + 1);
593 ref(i) = bit;
594 }
595
597 const auto i = size();
598 resize(i + 1);
599 ref(i) = bit;
600 }
601
602 void pop_back() {
603 if(!empty()) {
604 resize(size() - 1);
605 }
606 }
607
608 /// @}
609
610 /// @name Bitwise and Global Accessors and Modifiers
611 /// @{
612
613 auto at(size_type pos) {
614 check_offset(pos);
615 return ref(pos);
616 }
617
618 // TODO C++23: deducing this
619 auto at(size_type pos) const {
620 check_offset(pos);
621 return ref(pos);
622 }
623
624 auto front() { return ref(0); }
625
626 // TODO C++23: deducing this
627 auto front() const { return ref(0); }
628
629 auto back() { return ref(size() - 1); }
630
631 // TODO C++23: deducing this
632 auto back() const { return ref(size() - 1); }
633
634 /**
635 * Sets the bit at position @p pos.
636 * @throws Botan::Invalid_Argument if @p pos is out of range
637 */
639 check_offset(pos);
640 ref(pos).set();
641 return *this;
642 }
643
644 /**
645 * Sets all currently allocated bits.
646 */
648 full_range_operation(
649 [](std::unsigned_integral auto block) -> decltype(block) {
650 return static_cast<decltype(block)>(~static_cast<decltype(block)>(0));
651 },
652 *this);
653 zero_unused_bits();
654 return *this;
655 }
656
657 /**
658 * Sets all bits in the range [`offset`, `offset + length`). Bits outside
659 * of this range remain unchanged.
660 *
661 * @param offset the position of the first bit to be set
662 * @param length the number of bits to be set
663 * @throws Botan::Invalid_Argument if the range is out of range
664 */
666 BOTAN_ARG_CHECK(offset <= size() && length <= size() - offset, "Out of range");
667
668 if(length > 0) {
669 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
670 *this, offset, length);
671 range_operation(
672 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) -> BlockT {
673 // Note: Bits outside of `mask` (i.e. before/after the range
674 // in the first/last block) must remain unchanged.
675 return static_cast<BlockT>(block | mask);
676 },
677 op);
678 }
679
680 return *this;
681 }
682
683 /**
684 * Unsets all bits in the range [`offset`, `offset + length`). Bits outside
685 * of this range remain unchanged.
686 *
687 * @param offset the position of the first bit to be unset
688 * @param length the number of bits to be unset
689 * @throws Botan::Invalid_Argument if the range is out of range
690 */
692 BOTAN_ARG_CHECK(offset <= size() && length <= size() - offset, "Out of range");
693
694 if(length > 0) {
695 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
696 *this, offset, length);
697 range_operation(
698 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) -> BlockT {
699 // Note: Bits outside of `mask` (i.e. before/after the range
700 // in the first/last block) must remain unchanged.
701 return static_cast<BlockT>(block & static_cast<BlockT>(~mask));
702 },
703 op);
704 }
705
706 return *this;
707 }
708
709 /**
710 * Unsets the bit at position @p pos.
711 * @throws Botan::Invalid_Argument if @p pos is out of range
712 */
714 check_offset(pos);
715 ref(pos).unset();
716 return *this;
717 }
718
719 /**
720 * Unsets all currently allocated bits.
721 */
723 full_range_operation(
724 [](std::unsigned_integral auto block) -> decltype(block) { return static_cast<decltype(block)>(0); },
725 *this);
726 return *this;
727 }
728
729 /**
730 * Flips the bit at position @p pos.
731 * @throws Botan::Invalid_Argument if @p pos is out of range
732 */
734 check_offset(pos);
735 ref(pos).flip();
736 return *this;
737 }
738
739 /**
740 * Flips all currently allocated bits.
741 */
743 full_range_operation([](std::unsigned_integral auto block) -> decltype(block) { return ~block; }, *this);
744 zero_unused_bits();
745 return *this;
746 }
747
748 /**
749 * @returns true iff no bit is set
750 */
751 bool none_vartime() const {
752 return full_range_operation([](std::unsigned_integral auto block) { return block == 0; }, *this);
753 }
754
755 /**
756 * @returns true iff no bit is set in constant time
757 */
758 bool none() const { return hamming_weight() == 0; }
759
760 /**
761 * @returns true iff at least one bit is set
762 */
763 bool any_vartime() const { return !none_vartime(); }
764
765 /**
766 * @returns true iff at least one bit is set in constant time
767 */
768 bool any() const { return !none(); }
769
770 /**
771 * @returns true iff all bits are set
772 */
773 bool all_vartime() const {
774 return full_range_operation(
775 []<std::unsigned_integral BlockT>(BlockT block, BlockT mask) { return block == mask; }, *this);
776 }
777
778 /**
779 * @returns true iff all bits are set in constant time
780 */
781 bool all() const { return hamming_weight() == m_bits; }
782
783 auto operator[](size_type pos) { return ref(pos); }
784
785 // TODO C++23: deducing this
786 auto operator[](size_type pos) const { return ref(pos); }
787
788 /// @}
789
790 /// @name Subvectors
791 /// @{
792
793 /**
794 * Creates a new bitvector with a subsection of this bitvector starting at
795 * @p pos copying exactly @p length bits.
796 */
797 template <bitvectorish OutT = bitvector_base<AllocatorT>>
798 auto subvector(size_type pos, std::optional<size_type> length = std::nullopt) const {
799 const size_type bitlen = length.value_or(size() - pos);
800 BOTAN_ARG_CHECK(pos + bitlen <= size(), "Not enough bits to copy");
801
802 OutT newvector(bitlen);
803
804 // Handle bitvectors that are wrapped in strong types
805 auto& newvector_unwrapped = unwrap_strong_type(newvector);
806
807 if(bitlen > 0) {
808 if(pos % 8 == 0) {
809 copy_mem(
810 newvector_unwrapped.m_blocks,
811 std::span{m_blocks}.subspan(block_index(pos), block_index(pos + bitlen - 1) - block_index(pos) + 1));
812 } else {
813 const BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> from_op(
814 *this, pos, bitlen);
815 const BitRangeOperator<strong_type_wrapped_type<OutT>> to_op(
816 unwrap_strong_type(newvector_unwrapped), 0, bitlen);
817 range_operation([](auto /* to */, auto from) { return from; }, to_op, from_op);
818 }
819
820 newvector_unwrapped.zero_unused_bits();
821 }
822
823 return newvector;
824 }
825
826 /**
827 * Extracts a subvector of bits as an unsigned integral type @p OutT
828 * starting from bit @p pos and copying exactly sizeof(OutT)*8 bits.
829 *
830 * Hint: The bits are in big-endian order, i.e. the least significant bit
831 * is the 0th bit and the most significant bit it the n-th. Hence,
832 * addressing the bits with bitwise operations is done like so:
833 * bool bit = (out_int >> pos) & 1;
834 */
835 template <typename OutT>
836 requires(std::unsigned_integral<strong_type_wrapped_type<OutT>> &&
837 !std::same_as<bool, strong_type_wrapped_type<OutT>>)
838 OutT subvector(size_type pos) const {
839 using result_t = strong_type_wrapped_type<OutT>;
840 constexpr size_t bits = sizeof(result_t) * 8;
841 BOTAN_ARG_CHECK(pos + bits <= size(), "Not enough bits to copy");
842 result_t out = 0;
843
844 if(pos % 8 == 0) {
845 out = load_le<result_t>(std::span{m_blocks}.subspan(block_index(pos)).template first<sizeof(result_t)>());
846 } else {
847 const BitRangeOperator<const bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(
848 *this, pos, bits);
849 range_operation(
850 [&](std::unsigned_integral auto integer) {
851 if constexpr(std::same_as<result_t, decltype(integer)>) {
852 out = integer;
853 }
854 },
855 op);
856 }
857
858 return wrap_strong_type<OutT>(out);
859 }
860
861 /**
862 * Replaces a subvector of bits with the bits of another bitvector @p value
863 * starting at bit @p pos. The number of bits to replace is determined by
864 * the size of @p value.
865 *
866 * @note This is currently supported for byte-aligned @p pos only.
867 *
868 * @throws Not_Implemented when called with @p pos not divisible by 8.
869 *
870 * @param pos the position to start replacing bits
871 * @param value the bitvector to copy bits from
872 */
873 template <typename InT>
874 requires(std::unsigned_integral<strong_type_wrapped_type<InT>> && !std::same_as<bool, InT>)
875 void subvector_replace(size_type pos, InT value) {
877 constexpr size_t bits = sizeof(in_t) * 8;
878 BOTAN_ARG_CHECK(pos + bits <= size(), "Not enough bits to replace");
879
880 if(pos % 8 == 0) {
881 store_le(std::span{m_blocks}.subspan(block_index(pos)).template first<sizeof(in_t)>(),
882 unwrap_strong_type(value));
883 } else {
884 const BitRangeOperator<bitvector_base<AllocatorT>, BitRangeAlignment::no_alignment> op(*this, pos, bits);
885 range_operation(
886 [&]<std::unsigned_integral BlockT>(BlockT block) -> BlockT {
887 if constexpr(std::same_as<in_t, BlockT>) {
888 return unwrap_strong_type(value);
889 } else {
890 // This should never be reached. BOTAN_ASSERT_UNREACHABLE()
891 // caused warning "unreachable code" on MSVC, though. You
892 // don't say!
893 //
894 // Returning the given block back, is the most reasonable
895 // thing to do in this case, though.
896 return block;
897 }
898 },
899 op);
900 }
901 }
902
903 /// @}
904
905 /// @name Operators
906 ///
907 /// @{
908
909 auto operator~() {
910 auto newbv = *this;
911 newbv.flip();
912 return newbv;
913 }
914
915 template <bitvectorish OtherT>
916 auto& operator|=(const OtherT& other) {
917 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs | rhs; },
918 *this,
919 unwrap_strong_type(other));
920 return *this;
921 }
922
923 template <bitvectorish OtherT>
924 auto& operator&=(const OtherT& other) {
925 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs & rhs; },
926 *this,
927 unwrap_strong_type(other));
928 return *this;
929 }
930
931 template <bitvectorish OtherT>
932 auto& operator^=(const OtherT& other) {
933 full_range_operation([]<std::unsigned_integral BlockT>(BlockT lhs, BlockT rhs) -> BlockT { return lhs ^ rhs; },
934 *this,
935 unwrap_strong_type(other));
936 return *this;
937 }
938
939 /// @}
940
941 /// @name Constant Time Operations
942 ///
943 /// @{
944
945 /**
946 * Implements::
947 *
948 * if(condition) {
949 * *this ^= other;
950 * }
951 *
952 * omitting runtime dependence on any of the parameters.
953 */
954 template <bitvectorish OtherT>
955 void ct_conditional_xor(CT::Choice condition, const OtherT& other) {
956 BOTAN_ASSERT_NOMSG(m_bits == other.m_bits);
957 BOTAN_ASSERT_NOMSG(m_blocks.size() == other.m_blocks.size());
958
959 const auto maybe_xor = overloaded{
960 [m = CT::Mask<uint64_t>::from_choice(condition)](uint64_t lhs, uint64_t rhs) -> uint64_t {
961 return lhs ^ m.if_set_return(rhs);
962 },
963 [m = CT::Mask<uint32_t>::from_choice(condition)](uint32_t lhs, uint32_t rhs) -> uint32_t {
964 return lhs ^ m.if_set_return(rhs);
965 },
966 [m = CT::Mask<uint16_t>::from_choice(condition)](uint16_t lhs, uint16_t rhs) -> uint16_t {
967 return lhs ^ m.if_set_return(rhs);
968 },
969 [m = CT::Mask<uint8_t>::from_choice(condition)](uint8_t lhs, uint8_t rhs) -> uint8_t {
970 return lhs ^ m.if_set_return(rhs);
971 },
972 };
973
974 full_range_operation(maybe_xor, *this, unwrap_strong_type(other));
975 }
976
977 constexpr void _const_time_poison() const { CT::poison(m_blocks); }
978
979 constexpr void _const_time_unpoison() const { CT::unpoison(m_blocks); }
980
981 /// @}
982
983 /// @name Iterators
984 ///
985 /// @{
986
987 iterator begin() noexcept { return iterator(this, 0); }
988
989 const_iterator begin() const noexcept { return const_iterator(this, 0); }
990
991 const_iterator cbegin() const noexcept { return const_iterator(this, 0); }
992
993 iterator end() noexcept { return iterator(this, size()); }
994
995 const_iterator end() const noexcept { return const_iterator(this, size()); }
996
997 const_iterator cend() noexcept { return const_iterator(this, size()); }
998
999 /// @}
1000
1001 private:
1002 void check_offset(size_type pos) const {
1003 // BOTAN_ASSERT_NOMSG(!CT::is_poisoned(&m_bits, sizeof(m_bits)));
1004 // BOTAN_ASSERT_NOMSG(!CT::is_poisoned(&pos, sizeof(pos)));
1005 BOTAN_ARG_CHECK(pos < m_bits, "Out of range");
1006 }
1007
1008 void zero_unused_bits() {
1009 const auto first_unused_bit = size();
1010
1011 // Zero out any unused bits in the last block
1012 if(first_unused_bit % block_size_bits != 0) {
1013 const block_type mask = (one << block_offset(first_unused_bit)) - one;
1014 m_blocks[block_index(first_unused_bit)] &= mask;
1015 }
1016 }
1017
1018 static constexpr size_type ceil_toblocks(size_type bits) {
1019 return add_or_throw(bits, block_size_bits - 1, "bitvector size is too large") / block_size_bits;
1020 }
1021
1022 auto ref(size_type pos) const { return bitref<const block_type>(m_blocks, pos); }
1023
1024 auto ref(size_type pos) { return bitref<block_type>(m_blocks, pos); }
1025
1026 private:
1027 enum class BitRangeAlignment : uint8_t { byte_aligned, no_alignment };
1028
1029 /**
1030 * Helper construction to implement bit range operations on the bitvector.
1031 * It basically implements an iterator to read and write blocks of bits
1032 * from the underlying bitvector. Where "blocks of bits" are unsigned
1033 * integers of varying bit lengths.
1034 *
1035 * If the iteration starts at a byte boundary in the underlying bitvector,
1036 * this applies certain optimizations (i.e. loading blocks of bits straight
1037 * from the underlying byte buffer). The optimizations are enabled at
1038 * compile time (with the template parameter `alignment`).
1039 */
1040 template <typename BitvectorT, auto alignment = BitRangeAlignment::byte_aligned>
1041 requires is_bitvector_v<std::remove_cvref_t<BitvectorT>>
1042 class BitRangeOperator {
1043 private:
1044 constexpr static bool is_const() { return std::is_const_v<BitvectorT>; }
1045
1046 struct UnalignedDataHelper {
1047 const uint8_t padding_bits;
1048 const uint8_t bits_to_byte_alignment;
1049 };
1050
1051 public:
1052 BitRangeOperator(BitvectorT& source, size_type start_bitoffset, size_type bitlength) :
1053 m_source(source),
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");
1062 }
1063
1064 explicit BitRangeOperator(BitvectorT& source) : BitRangeOperator(source, 0, source.size()) {}
1065
1066 static constexpr bool is_byte_aligned() { return alignment == BitRangeAlignment::byte_aligned; }
1067
1068 /**
1069 * @returns the overall number of bits to be iterated with this operator
1070 */
1071 size_type size() const { return m_bitlength; }
1072
1073 /**
1074 * @returns the number of bits not yet read from this operator
1075 */
1076 size_type bits_to_read() const { return m_bitlength - m_read_bitpos + m_start_bitoffset; }
1077
1078 /**
1079 * @returns the number of bits still to be written into this operator
1080 */
1081 size_type bits_to_write() const { return m_bitlength - m_write_bitpos + m_start_bitoffset; }
1082
1083 /**
1084 * Loads the next block of bits from the underlying bitvector. No
1085 * bounds checks are performed. The caller can define the size of
1086 * the resulting unsigned integer block.
1087 */
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();
1093
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>());
1097 } else {
1098 const size_type byte_pos = read_bytepos();
1099 const size_type bits_to_collect = std::min(block_bits, bits_to_read());
1100 const size_type bytes_to_load = ceil_tobytes(m_unaligned_helper.padding_bits + bits_to_collect);
1101
1102 // Copy only the bytes that actually contain bits of the range
1103 // into a zero-padded scratch buffer to avoid an overread when
1104 // the range ends near the underlying buffer's end.
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));
1108
1109 // Initialize the left-most bits from the first byte.
1110 result_block = BlockT(bytes[0]) >> m_unaligned_helper.padding_bits;
1111
1112 // If more bits are needed, we pull them from the scratch buffer.
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;
1116 }
1117 }
1118
1119 m_read_bitpos += std::min(block_bits, bits_remaining);
1120 return result_block;
1121 }
1122
1123 /**
1124 * Stores the next block of bits into the underlying bitvector.
1125 * No bounds checks are performed. Storing bit blocks that are not
1126 * aligned at a byte-boundary in the underlying bitvector is
1127 * currently not implemented.
1128 */
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;
1134
1135 if constexpr(is_byte_aligned()) {
1136 const auto sink = m_source.as_byte_span().subspan(write_bytepos()).template first<block_size>();
1137 store_le(sink, block);
1138 } else {
1139 const size_type byte_pos = write_bytepos();
1140 const size_type bits_to_store = std::min(block_bits, bits_to_write());
1141
1142 uint8_t& first_byte = m_source.as_byte_span()[byte_pos];
1143
1144 // Set the left-most bits in the first byte, leaving all others unchanged
1145 first_byte = (first_byte & uint8_t(0xFF >> m_unaligned_helper.bits_to_byte_alignment)) |
1146 uint8_t(block << m_unaligned_helper.padding_bits);
1147
1148 // If more bits are provided, we store them in the remaining bytes.
1149 if(m_unaligned_helper.bits_to_byte_alignment < bits_to_store) {
1150 const size_type bytes_to_store = ceil_tobytes(m_unaligned_helper.padding_bits + bits_to_store) - 1;
1151 const auto remaining_bytes = m_source.as_byte_span().subspan(byte_pos + 1, bytes_to_store);
1152
1153 // Put the relevant bytes into a zero-padded scratch buffer
1154 // to avoid reaching past the underlying buffer's end when
1155 // the range ends near the end of the buffer.
1156 std::array<uint8_t, block_size> bytes{};
1157 copy_mem(std::span{bytes}.first(bytes_to_store), remaining_bytes);
1158
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;
1162 store_le(bytes, new_bytes);
1163
1164 copy_mem(remaining_bytes, std::span{bytes}.first(bytes_to_store));
1165 }
1166 }
1167
1168 m_write_bitpos += std::min(block_bits, bits_to_write());
1169 }
1170
1171 template <std::unsigned_integral BlockT>
1172 requires(is_byte_aligned() && !is_const())
1173 std::span<BlockT> span(size_type blocks) const {
1174 BOTAN_DEBUG_ASSERT(blocks == 0 || is_memory_aligned_to<BlockT>());
1175 BOTAN_DEBUG_ASSERT(read_bytepos() % sizeof(BlockT) == 0);
1176 // Intermittently casting to void* to avoid a compiler warning
1177 void* ptr = reinterpret_cast<void*>(m_source.as_byte_span().data() + read_bytepos());
1178 return {reinterpret_cast<BlockT*>(ptr), blocks};
1179 }
1180
1181 template <std::unsigned_integral BlockT>
1182 requires(is_byte_aligned() && is_const())
1183 std::span<const BlockT> span(size_type blocks) const {
1184 BOTAN_DEBUG_ASSERT(blocks == 0 || is_memory_aligned_to<BlockT>());
1185 BOTAN_DEBUG_ASSERT(read_bytepos() % sizeof(BlockT) == 0);
1186 // Intermittently casting to void* to avoid a compiler warning
1187 const void* ptr = reinterpret_cast<const void*>(m_source.as_byte_span().data() + read_bytepos());
1188 return {reinterpret_cast<const BlockT*>(ptr), blocks};
1189 }
1190
1191 void advance(size_type bytes)
1192 requires(is_byte_aligned())
1193 {
1194 m_read_bitpos += bytes * 8;
1195 m_write_bitpos += bytes * 8;
1196 }
1197
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;
1203
1204 // std::align takes `ptr` as a reference (!), i.e. `void*&` and
1205 // uses it as an out-param. Though, `cptr` is const because this
1206 // method is const-qualified, hence the const_cast<>.
1207 void* ptr = const_cast<void*>(cptr); // NOLINT(*-const-correctness)
1208 size_t size = sizeof(BlockT);
1209 return ptr_before != nullptr && std::align(alignof(BlockT), size, ptr, size) == ptr_before;
1210 }
1211
1212 private:
1213 size_type read_bytepos() const { return m_read_bitpos / 8; }
1214
1215 size_type write_bytepos() const { return m_write_bitpos / 8; }
1216
1217 private:
1218 BitvectorT& m_source;
1219 size_type m_start_bitoffset;
1220 size_type m_bitlength;
1221
1222 UnalignedDataHelper m_unaligned_helper;
1223
1224 mutable size_type m_read_bitpos;
1225 mutable size_type m_write_bitpos;
1226 };
1227
1228 /**
1229 * Helper struct for the low-level handling of blockwise operations
1230 *
1231 * This has two main code paths: Optimized for byte-aligned ranges that
1232 * can simply be taken from memory as-is. And a generic implementation
1233 * that must assemble blocks from unaligned bits before processing.
1234 */
1235 template <typename FnT, typename... ParamTs>
1236 requires detail::blockwise_processing_callback<FnT, ParamTs...>
1237 class blockwise_processing_callback_trait {
1238 public:
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");
1243
1244 /**
1245 * Applies @p fn to the blocks provided in @p blocks by simply reading from
1246 * memory without re-arranging any bits across byte-boundaries.
1247 */
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) {
1251 constexpr size_type bits = sizeof(detail::first_t<BlockTs...>) * 8;
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]...)) {
1256 return false;
1257 }
1258 } else if constexpr(is_manipulator) {
1259 detail::first(blocks...)[i] = apply(fn, bits, blocks[i]...);
1260 } else {
1261 apply(fn, bits, blocks[i]...);
1262 }
1263 }
1264 return true;
1265 }
1266
1267 /**
1268 * Applies @p fn to as many blocks as @p ops provide for the given type.
1269 */
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();
1275 if(bits == 0) {
1276 return true;
1277 }
1278
1279 bits += block_bits; // avoid unsigned integer underflow in the following loop
1280 while(bits > block_bits * 2 - 8) {
1281 bits -= block_bits;
1282 if constexpr(is_predicate) {
1283 if(!apply(fn, bits, ops.template load_next<BlockT>()...)) {
1284 return false;
1285 }
1286 } else if constexpr(is_manipulator) {
1287 detail::first(ops...).store_next(apply(fn, bits, ops.template load_next<BlockT>()...));
1288 } else {
1289 apply(fn, bits, ops.template load_next<BlockT>()...);
1290 }
1291 }
1292 return true;
1293 }
1294
1295 private:
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) {
1300 return fn(blocks..., make_mask<detail::first_t<BlockTs...>>(bits));
1301 } else {
1302 return fn(blocks...);
1303 }
1304 }
1305 };
1306
1307 /**
1308 * Helper function of `full_range_operation` and `range_operation` that
1309 * calls @p fn on a given aligned unsigned integer block as long as the
1310 * underlying bit range contains enough bits to fill the block fully.
1311 *
1312 * This uses bare memory access to gain a speed up for aligned data.
1313 */
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;
1321
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), ...);
1325 return result;
1326 }
1327
1328 /**
1329 * Helper function of `full_range_operation` and `range_operation` that
1330 * calls @p fn on a given unsigned integer block size as long as the
1331 * underlying bit range contains enough bits to fill the block.
1332 */
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...);
1338 }
1339
1340 /**
1341 * Apply @p fn to all bits in the ranges defined by @p ops. If more than
1342 * one range operator is passed to @p ops, @p fn receives corresponding
1343 * blocks of bits from each operator. Therefore, all @p ops have to define
1344 * the exact same length of their underlying ranges.
1345 *
1346 * @p fn may return a bit block that will be stored into the _first_ bit
1347 * range passed into @p ops. If @p fn returns a boolean, and its value is
1348 * `false`, the range operation is cancelled and `false` is returned.
1349 *
1350 * The implementation ensures to pull bits in the largest bit blocks
1351 * possible and reverts to smaller bit blocks only when needed.
1352 */
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");
1358
1359 if constexpr((BitRangeOperatorTs::is_byte_aligned() && ...)) {
1360 // Note: At the moment we can assume that this will always be used
1361 // on the _entire_ bitvector. Therefore, we can safely assume
1362 // that the bitvectors' underlying buffers are properly aligned.
1363 // If this assumption changes, we need to add further handling
1364 // to process a byte padding at the beginning of the bitvector
1365 // until a memory alignment boundary is reached.
1366 //
1367 // An empty range has no blocks to process and a possibly-null
1368 // underlying buffer, so the alignment check does not apply.
1369 if(detail::first(ops...).size() != 0) {
1370 const bool alignment = (ops.template is_memory_aligned_to<uint64_t>() && ...);
1371 BOTAN_ASSERT_NOMSG(alignment);
1372 }
1373
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...);
1378 } else {
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...);
1383 }
1384 }
1385
1386 /**
1387 * Apply @p fn to all bit blocks in the bitvector(s).
1388 */
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)...);
1395 }
1396
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);
1400 }
1401
1402 template <std::unsigned_integral T>
1403 static constexpr T make_mask(size_type bits) {
1404 const bool max = bits >= sizeof(T) * 8;
1405 bits &= T(max - 1);
1406 return (T(!max) << bits) - 1;
1407 }
1408
1409 auto as_byte_span() { return std::span{m_blocks.data(), m_blocks.size() * sizeof(block_type)}; }
1410
1411 auto as_byte_span() const { return std::span{m_blocks.data(), m_blocks.size() * sizeof(block_type)}; }
1412
1413 private:
1414 size_type m_bits;
1415 std::vector<block_type, allocator_type> m_blocks;
1416};
1417
1420
1421namespace detail {
1422
1423/**
1424 * If one of the allocators is a Botan::secure_allocator, this will always
1425 * prefer it. Otherwise, the allocator of @p lhs will be used as a default.
1426 */
1427template <bitvectorish T1, bitvectorish T2>
1428constexpr auto copy_lhs_allocator_aware(const T1& lhs, const T2& /*rhs*/) {
1429 constexpr bool needs_secure_allocator =
1431
1432 if constexpr(needs_secure_allocator) {
1433 return lhs.template as<secure_bitvector>();
1434 } else {
1435 return lhs.template as<bitvector>();
1436 }
1437}
1438
1439} // namespace detail
1440
1441template <bitvectorish T1, bitvectorish T2>
1442auto operator|(const T1& lhs, const T2& rhs) {
1443 auto res = detail::copy_lhs_allocator_aware(lhs, rhs);
1444 res |= rhs;
1445 return res;
1446}
1447
1448template <bitvectorish T1, bitvectorish T2>
1449auto operator&(const T1& lhs, const T2& rhs) {
1450 auto res = detail::copy_lhs_allocator_aware(lhs, rhs);
1451 res &= rhs;
1452 return res;
1453}
1454
1455template <bitvectorish T1, bitvectorish T2>
1456auto operator^(const T1& lhs, const T2& rhs) {
1457 auto res = detail::copy_lhs_allocator_aware(lhs, rhs);
1458 res ^= rhs;
1459 return res;
1460}
1461
1462template <bitvectorish T1, bitvectorish T2>
1463bool operator==(const T1& lhs, const T2& rhs) {
1464 return lhs.equals_vartime(rhs);
1465}
1466
1467namespace detail {
1468
1469/**
1470 * A Strong<> adapter for arbitrarily large bitvectors
1471 */
1472template <concepts::container T>
1473 requires is_bitvector_v<T>
1475 public:
1476 using size_type = typename T::size_type;
1477
1478 public:
1480
1481 auto at(size_type i) const { return this->get().at(i); }
1482
1483 auto at(size_type i) { return this->get().at(i); }
1484
1485 decltype(auto) set(size_type i) { return this->get().set(i); }
1486
1487 decltype(auto) set_range(size_type offset, size_type length) { return this->get().set_range(offset, length); }
1488
1489 decltype(auto) unset_range(size_type offset, size_type length) { return this->get().unset_range(offset, length); }
1490
1491 decltype(auto) unset(size_type i) { return this->get().unset(i); }
1492
1493 decltype(auto) flip(size_type i) { return this->get().flip(i); }
1494
1495 decltype(auto) flip() { return this->get().flip(); }
1496
1497 template <typename OutT>
1498 auto as() const {
1499 return this->get().template as<OutT>();
1500 }
1501
1502 template <bitvectorish OutT = T>
1503 auto subvector(size_type pos, std::optional<size_type> length = std::nullopt) const {
1504 return this->get().template subvector<OutT>(pos, length);
1505 }
1506
1507 template <typename OutT>
1508 requires(std::unsigned_integral<strong_type_wrapped_type<OutT>> &&
1509 !std::same_as<bool, strong_type_wrapped_type<OutT>>)
1510 auto subvector(size_type pos) const {
1511 return this->get().template subvector<OutT>(pos);
1512 }
1513
1514 template <typename InT>
1515 requires(std::unsigned_integral<strong_type_wrapped_type<InT>> && !std::same_as<bool, InT>)
1516 void subvector_replace(size_type pos, InT value) {
1517 return this->get().subvector_replace(pos, value);
1518 }
1519
1520 template <bitvectorish OtherT>
1521 auto equals(const OtherT& other) const {
1522 return this->get().equals(other);
1523 }
1524
1525 auto push_back(bool b) { return this->get().push_back(b); }
1526
1527 auto push_back(CT::Choice b) { return this->get().push_back(b); }
1528
1529 auto pop_back() { return this->get().pop_back(); }
1530
1531 auto front() const { return this->get().front(); }
1532
1533 auto front() { return this->get().front(); }
1534
1535 auto back() const { return this->get().back(); }
1536
1537 auto back() { return this->get().back(); }
1538
1539 auto any_vartime() const { return this->get().any_vartime(); }
1540
1541 auto all_vartime() const { return this->get().all_vartime(); }
1542
1543 auto none_vartime() const { return this->get().none_vartime(); }
1544
1545 auto has_odd_hamming_weight() const { return this->get().has_odd_hamming_weight(); }
1546
1547 auto hamming_weight() const { return this->get().hamming_weight(); }
1548
1549 auto from_bytes(std::span<const uint8_t> bytes, std::optional<size_type> bits = std::nullopt) {
1550 return this->get().from_bytes(bytes, bits);
1551 }
1552
1553 template <typename OutT = T>
1554 auto to_bytes() const {
1555 return this->get().template to_bytes<OutT>();
1556 }
1557
1558 auto to_bytes(std::span<uint8_t> out) const { return this->get().to_bytes(out); }
1559
1560 auto to_string() const { return this->get().to_string(); }
1561
1562 auto capacity() const { return this->get().capacity(); }
1563
1564 auto reserve(size_type n) { return this->get().reserve(n); }
1565
1566 constexpr void _const_time_poison() const { this->get()._const_time_poison(); }
1567
1568 constexpr void _const_time_unpoison() const { this->get()._const_time_unpoison(); }
1569};
1570
1571} // namespace detail
1572
1573} // namespace Botan
1574
1575#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
static constexpr Choice from_int(T v)
Definition ct_utils.h:268
constexpr bool as_bool() const
Definition ct_utils.h:329
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > from_choice(Choice c)
Definition ct_utils.h:407
bitref(bitref &&) noexcept=default
constexpr bitref & operator&=(bool other) noexcept
Definition bitvector.h:365
constexpr bitref & operator=(bitref &&bit) noexcept
Definition bitvector.h:361
constexpr bitref & flip() noexcept
Definition bitvector.h:340
constexpr bitref & operator=(bool bit) noexcept
Definition bitvector.h:347
constexpr bitref & operator=(const bitref &bit) noexcept
Definition bitvector.h:359
constexpr bitref & operator&=(CT::Choice other) noexcept
Definition bitvector.h:370
constexpr bitref & operator^=(bool other) noexcept
Definition bitvector.h:385
constexpr bitref & unset() noexcept
Definition bitvector.h:335
constexpr bitref & operator=(CT::Choice bit) noexcept
Definition bitvector.h:353
bitref(const bitref &) noexcept=default
constexpr bitref & operator|=(CT::Choice other) noexcept
Definition bitvector.h:380
constexpr bitref & set() noexcept
Definition bitvector.h:330
constexpr bitref & operator|=(bool other) noexcept
Definition bitvector.h:375
constexpr bitref & operator^=(CT::Choice other) noexcept
Definition bitvector.h:390
const_iterator begin() const noexcept
Definition bitvector.h:989
bitvector_base & flip()
Definition bitvector.h:742
bitvector_base & flip(size_type pos)
Definition bitvector.h:733
void push_back(CT::Choice bit)
Definition bitvector.h:596
bitvector_base & unset()
Definition bitvector.h:722
void subvector_replace(size_type pos, InT value)
Definition bitvector.h:875
void reserve(size_type bits)
Definition bitvector.h:575
OutT subvector(size_type pos) const
Definition bitvector.h:838
bitvector_base & unset(size_type pos)
Definition bitvector.h:713
bool none() const
Definition bitvector.h:758
auto at(size_type pos) const
Definition bitvector.h:619
auto operator[](size_type pos) const
Definition bitvector.h:786
CT::Choice has_odd_hamming_weight() const
Definition bitvector.h:430
constexpr void _const_time_unpoison() const
Definition bitvector.h:979
std::string to_string() const
Definition bitvector.h:560
bitvector_base & set(size_type pos)
Definition bitvector.h:638
static constexpr size_type block_size_bytes
Definition bitvector.h:242
void from_bytes(std::span< const uint8_t > bytes, std::optional< size_type > bits=std::nullopt)
Definition bitvector.h:498
bitvector_base & set_range(size_type offset, size_type length)
Definition bitvector.h:665
bitvector_base(size_type bits)
Definition bitvector.h:399
size_type hamming_weight() const
Definition bitvector.h:445
auto & operator&=(const OtherT &other)
Definition bitvector.h:924
block_type value_type
Definition bitvector.h:238
const_iterator cbegin() const noexcept
Definition bitvector.h:991
bitvector_base & set()
Definition bitvector.h:647
static constexpr bool uses_secure_allocator
Definition bitvector.h:244
detail::bitvector_iterator< bitvector_base< AllocatorT > > iterator
Definition bitvector.h:239
void ct_conditional_xor(CT::Choice condition, const OtherT &other)
Definition bitvector.h:955
bool none_vartime() const
Definition bitvector.h:751
AllocatorT< block_type > allocator_type
Definition bitvector.h:237
auto operator[](size_type pos)
Definition bitvector.h:783
bool all_vartime() const
Definition bitvector.h:773
void to_bytes(std::span< uint8_t > out) const
Definition bitvector.h:538
bitvector_base & unset_range(size_type offset, size_type length)
Definition bitvector.h:691
size_type capacity() const
Definition bitvector.h:573
friend class bitvector_base
Definition bitvector.h:248
auto & operator|=(const OtherT &other)
Definition bitvector.h:916
auto subvector(size_type pos, std::optional< size_type > length=std::nullopt) const
Definition bitvector.h:798
auto at(size_type pos)
Definition bitvector.h:613
bool empty() const
Definition bitvector.h:423
static constexpr size_type block_size_bits
Definition bitvector.h:243
detail::bitvector_iterator< const bitvector_base< AllocatorT > > const_iterator
Definition bitvector.h:240
void resize(size_type bits)
Definition bitvector.h:577
const_iterator end() const noexcept
Definition bitvector.h:995
bitvector_base(std::span< const uint8_t > bytes, std::optional< size_type > bits=std::nullopt)
Definition bitvector.h:414
bool any_vartime() const
Definition bitvector.h:763
void push_back(bool bit)
Definition bitvector.h:590
auto back() const
Definition bitvector.h:632
constexpr void _const_time_poison() const
Definition bitvector.h:977
OutT to_bytes() const
Definition bitvector.h:527
auto & operator^=(const OtherT &other)
Definition bitvector.h:932
bool equals(const OtherT &other) const noexcept
Definition bitvector.h:474
auto front() const
Definition bitvector.h:627
const_iterator cend() noexcept
Definition bitvector.h:997
bitvector_base(std::initializer_list< block_type > blocks, std::optional< size_type > bits=std::nullopt)
Definition bitvector.h:420
bool equals_vartime(const OtherT &other) const noexcept
Definition bitvector.h:463
typename T::size_type size_type
Definition bitvector.h:1476
auto equals(const OtherT &other) const
Definition bitvector.h:1521
decltype(auto) set_range(size_type offset, size_type length)
Definition bitvector.h:1487
constexpr void _const_time_poison() const
Definition bitvector.h:1566
decltype(auto) unset(size_type i)
Definition bitvector.h:1491
decltype(auto) unset_range(size_type offset, size_type length)
Definition bitvector.h:1489
void subvector_replace(size_type pos, InT value)
Definition bitvector.h:1516
auto subvector(size_type pos) const
Definition bitvector.h:1510
auto from_bytes(std::span< const uint8_t > bytes, std::optional< size_type > bits=std::nullopt)
Definition bitvector.h:1549
auto subvector(size_type pos, std::optional< size_type > length=std::nullopt) const
Definition bitvector.h:1503
Strong_Adapter(std::span< const typename Container_Strong_Adapter_Base< T >::value_type > span)
auto at(size_type i) const
Definition bitvector.h:1481
auto to_bytes(std::span< uint8_t > out) const
Definition bitvector.h:1558
constexpr void _const_time_unpoison() const
Definition bitvector.h:1568
decltype(auto) flip(size_type i)
Definition bitvector.h:1493
decltype(auto) set(size_type i)
Definition bitvector.h:1485
constexpr T & get() &
Definition strong_type.h:81
std::bidirectional_iterator_tag iterator_category
Definition bitvector.h:135
bitvector_iterator & operator=(bitvector_iterator &&other) noexcept
Definition bitvector.h:159
std::remove_const_t< decltype(std::declval< T >().at(0))> value_type
Definition bitvector.h:130
std::partial_ordering operator<=>(const bitvector_iterator &other) const noexcept
Definition bitvector.h:187
bitvector_iterator & operator=(const bitvector_iterator &other) noexcept
Definition bitvector.h:151
bool operator==(const bitvector_iterator &other) const noexcept
Definition bitvector.h:195
bitvector_iterator operator--(int) noexcept
Definition bitvector.h:181
bitvector_iterator & operator++() noexcept
Definition bitvector.h:165
bitvector_iterator & operator--() noexcept
Definition bitvector.h:176
bitvector_iterator(bitvector_iterator &&other) noexcept
Definition bitvector.h:147
bitvector_iterator(T *bitvector, size_t offset)
Definition bitvector.h:141
std::make_signed_t< size_type > difference_type
Definition bitvector.h:129
bitvector_iterator operator++(int) noexcept
Definition bitvector.h:170
bitvector_iterator(const bitvector_iterator &other) noexcept
Definition bitvector.h:143
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
std::invoke_result_t< FnT, as< BlockT, ParamTs >... > blockwise_processing_callback_return_type
Definition bitvector.h:78
constexpr auto copy_lhs_allocator_aware(const T1 &lhs, const T2 &)
Definition bitvector.h:1428
typename first_type< Ts... >::type first_t
Definition bitvector.h:64
constexpr T add_or_throw(T a, T b, std::string_view msg)
Definition int_utils.h:66
ASN1_Type operator|(ASN1_Type x, ASN1_Type y)
Definition asn1_obj.h:84
constexpr T mul_or_throw(T a, T b, std::string_view msg)
Definition int_utils.h:81
bitvector_base< secure_allocator > secure_bitvector
Definition bitvector.h:1418
OctetString operator^(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:109
bitvector_base< std::allocator > bitvector
Definition bitvector.h:1419
constexpr void typecast_copy(ToR &&out, const FromR &in)
Definition mem_ops.h:176
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:140
constexpr decltype(auto) unwrap_strong_type(T &&t)
Generically unwraps a strong type to its underlying type.
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
typename detail::wrapped_type_helper< std::remove_cvref_t< T > >::type strong_type_wrapped_type
Extracts the wrapped type from a strong type.
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
Definition bit_ops.h:176
constexpr decltype(auto) wrap_strong_type(ParamT &&t)
Wraps a value into a caller-defined (strong) type.
BOTAN_FORCE_INLINE constexpr uint8_t ct_popcount(T x)
Definition bit_ops.h:274
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
bool operator==(const AlgorithmIdentifier &x, const AlgorithmIdentifier &y)
Definition alg_id.cpp:54
constexpr auto bitlen(size_t x)
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118
ECIES_Flags operator&(ECIES_Flags a, ECIES_Flags b)
Definition ecies.h:70