randombit / botan / 22602980043

coverage: 90.316% (-0.005%) from 90.321%
22602980043

push

github

web-flow 
Merge pull request #5403 from randombit/jack/shift-shift-shift

Small optimization for shift_left and shift_right

103591 of 114699 relevant lines covered (90.32%)

11567426.57 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.57
/src/tests/test_utils_bitvector.cpp
1 
/*
2 
 * (C) 2023-2024 Jack Lloyd
3 
 * (C) 2023-2024 René Meusel, Rohde & Schwarz Cybersecurity
4 
 *
5 
 * Botan is released under the Simplified BSD License (see license.txt)
6 
 */
7 









8



#include "tests.h"










9












10



#if defined(BOTAN_HAS_BITVECTOR)










11



   #include <botan/hex.h>










12



   #include <botan/rng.h>










13



   #include <botan/internal/bitvector.h>










14



   #include <botan/internal/fmt.h>










15



   #include <algorithm>










16



   #include <numeric>










17



   #include <set>










18



#endif










19












20



namespace Botan_Tests {










21












22



#if defined(BOTAN_HAS_BITVECTOR)










23












24



namespace {










25












26



/// Returns a random number in the range [min, max)










27



size_t rand_in_range(Botan::RandomNumberGenerator& rng, size_t min, size_t max) {




74
✔





28



   if(min == max) {




74
✔





29



      return min;










30



   }










31












32



   const size_t val = Botan::load_le<size_t>(rng.random_array<sizeof(size_t)>());




74
✔





33



   return min + (val % (max - min));




74
✔





34



}










35












36



/// Returns @p n integers smaller than @p upper_bound in random order










37



std::vector<size_t> rand_indices(Botan::RandomNumberGenerator& rng, size_t n, size_t upper_bound) {




3
✔





38



   auto shuffle = [&](std::vector<size_t>& v) {




6
✔





39



      // Fisher-Yates shuffle










40



      if(v.size() < 2) {




3
✔





41



         return;










42



      }










43



      for(size_t i = 0; i < v.size() - 1; ++i) {




71
✔





44



         auto j = rand_in_range(rng, i, v.size());




68
✔





45



         std::swap(v[i], v[j]);




68
✔





46



      }










47



   };




3
✔





48












49



   std::vector<size_t> indices(upper_bound);




3
✔





50



   std::iota(indices.begin(), indices.end(), 0);




3
✔





51



   shuffle(indices);




3
✔





52



   indices.resize(n);




3
✔





53



   return indices;




3
✔





54



}




×







55












56



/// Create an empty bitvector of random size and chose a random number of points of interests










57



std::pair<Botan::bitvector, std::set<size_t>> rnd_bitvector_with_rnd_pois(Botan::RandomNumberGenerator& rng) {




3
✔





58



   const Botan::bitvector bv(rand_in_range(rng, 0, 65));




3
✔





59



   const size_t no_poi = rand_in_range(rng, 0, bv.size());




3
✔





60



   auto points_of_interest = rand_indices(rng, no_poi, bv.size());




3
✔





61












62



   return {bv, {points_of_interest.begin(), points_of_interest.end()}};




6
✔





63



}




6
✔





64












65



template <size_t mod>










66



auto pattern_generator(size_t offset = 0) {




79
✔





67



   return [i = offset]() mutable -> bool {




5,209
✔





68



      const bool result = (i % mod) != 0;




5,209
✔





69



      ++i;




5,209
✔





70



      return result;










71



   };










72



}










73












74



std::vector<Test::Result> test_bitvector_bitwise_accessors(Botan::RandomNumberGenerator& rng) {




1
✔





75



   return {




1
✔





76



      CHECK("default constructed bitvector",










77



            [](auto& result) {




1
✔





78



               const Botan::bitvector bv;




1
✔





79



               result.test_is_true("default constructed bitvector is empty", bv.empty());




1
✔





80



               result.test_sz_eq("default constructed bitvector has zero size", bv.size(), size_t(0));




1
✔





81



            }),




1
✔





82












83



      CHECK("preallocated construction of bitvector",










84



            [](auto& result) {




1
✔





85



               Botan::bitvector bv(10);




1
✔





86



               result.test_is_true("allocated bitvector is not empty", !bv.empty());




1
✔





87



               result.test_sz_eq("allocated bitvector has allocated size", bv.size(), size_t(10));




1
✔





88



               for(size_t i = 0; i < 10; ++i) {




11
✔





89



                  result.test_is_true("bit not set yet", !bv.at(i));




10
✔





90



               }










91



            }),




1
✔





92












93



      CHECK("setting bits",










94



            [&](auto& result) {




1
✔





95



               auto [bv, ones] = rnd_bitvector_with_rnd_pois(rng);




1
✔





96












97



               for(const size_t i : ones) {




16
✔





98



                  if(rng.next_byte() % 2 == 0) {




15
✔





99



                     bv.set(i);




6
✔





100



                  } else {










101



                     bv.at(i) = true;




9
✔





102



                  }










103



               }










104



               for(size_t i = 0; i < bv.size(); ++i) {




24
✔





105



                  result.test_is_true(Botan::fmt("bit {} in expected state", i), bv.at(i) == ones.contains(i));




69
✔





106



               }










107



            }),




1
✔





108












109



      CHECK("unsetting bits",










110



            [&](auto& result) {




1
✔





111



               auto [bv, zeros] = rnd_bitvector_with_rnd_pois(rng);




1
✔





112



               for(auto b : bv) {




6
✔





113



                  b.set();




4
✔





114



               }










115












116



               for(const size_t i : zeros) {




1
✔





117



                  if(rng.next_byte() % 2 == 0) {




×







118



                     bv.unset(i);




×







119



                  } else {










120



                     bv.at(i) = false;




×







121



                  }










122



               }










123



               for(size_t i = 0; i < bv.size(); ++i) {




5
✔





124



                  result.test_is_true(Botan::fmt("bit {} in expected state", i), bv.at(i) == !zeros.contains(i));




12
✔





125



               }










126



            }),




1
✔





127












128



      CHECK("flipping bits",










129



            [&](auto& result) {




1
✔





130



               auto [bv, ones] = rnd_bitvector_with_rnd_pois(rng);




1
✔





131












132



               for(size_t i = 0; i < bv.size(); ++i) {




45
✔





133



                  if(std::find(ones.begin(), ones.end(), i) == ones.end()) {




88
✔





134



                     bv.set(i);




15
✔





135



                  }










136



                  bv.flip(i);




44
✔





137



               }










138



               for(size_t i = 0; i < bv.size(); ++i) {




45
✔





139



                  result.test_is_true(Botan::fmt("bit {} in expected state", i), bv.at(i) == ones.contains(i));




132
✔





140



               }










141



            }),




1
✔





142












143



      CHECK("accessors validate offsets",










144



            [](auto& result) {




1
✔





145



               Botan::bitvector bv(10);




1
✔





146



               result.template test_throws<Botan::Invalid_Argument>(




1
✔





147



                  ".at() const out of range", [&] { const_cast<const decltype(bv)&>(bv).at(10); });




2
✔





148



               result.template test_throws<Botan::Invalid_Argument>(".at() out of range", [&] { bv.at(10); });




2
✔





149



               result.template test_throws<Botan::Invalid_Argument>(".set() out of range", [&] { bv.set(10); });




2
✔





150



               result.template test_throws<Botan::Invalid_Argument>(".unset() out of range", [&] { bv.unset(10); });




2
✔





151



               result.template test_throws<Botan::Invalid_Argument>(".flip() out of range", [&] { bv.flip(10); });




2
✔





152



            }),




1
✔





153












154



      CHECK("multiblock handling",










155



            [](auto& result) {




1
✔





156



               Botan::bitvector bv(128);




1
✔





157



               result.test_sz_eq("has more than 64 bits", bv.size(), 128);




1
✔





158



               bv.set(1).set(63).set(64).set(127);




1
✔





159



               for(size_t i = 0; i < bv.size(); ++i) {




129
✔





160



                  const bool expected = (i == 1 || i == 63 || i == 64 || i == 127);




128
✔





161



                  result.test_bool_eq(Botan::fmt("bit {} in expected state", i), bv.at(i), expected);




256
✔





162



               }










163



            }),




1
✔





164












165



      CHECK("subscript operator",










166



            [](auto& result) {




1
✔





167



               Botan::bitvector bv(128);




1
✔





168



               bv[0].set();




1
✔





169



               bv[1] = true;




1
✔





170



               bv[2].flip();




1
✔





171



               bv[64] = true;




1
✔





172



               bv[80] = true;




1
✔





173



               result.test_is_true("bit 0", bv[0]);




1
✔





174



               result.test_is_true("bit 1", bv[1]);




1
✔





175



               result.test_is_true("bit 2", bv[2]);




1
✔





176



               result.test_is_true("bit 3", !bv[3]);




1
✔





177



               result.test_is_true("bit 64", bv[64]);




1
✔





178



               result.test_is_true("bit 80", bv[80]);




1
✔





179



            }),




1
✔





180












181



      CHECK("subscript operator does not validate offsets",










182



            [](auto& result) {




1
✔





183



               Botan::bitvector bv(10);




1
✔





184



               result.template test_throws<Botan::Invalid_Argument>(".at() out of range", [&] { bv.at(10); });




2
✔





185



               // Technically the next line is undefined behaviour.










186



               // Though, the current implementation detail won't










187



               // cause issues, which might change!










188



               result.test_no_throw("subscript out of range", [&] { bv[10]; });




1
✔





189



            }),




1
✔





190












191



      CHECK("bitwise assignment modifiers",










192



            [](auto& result) {




1
✔





193



               Botan::bitvector bv(4);




1
✔





194












195



               result.require("precondition", !bv[0] && !bv[1]);




1
✔





196



               bv[0] &= 1;  // NOLINT(*-use-bool-literals)




1
✔





197



               result.test_is_true("bv[0] still 0", !bv[0]);




1
✔





198



               bv[0].set();




1
✔





199



               bv[0] &= 1;  // NOLINT(*-use-bool-literals)




1
✔





200



               result.test_is_true("bv[0] still 1", bv[0]);




1
✔





201



               bv[0] &= false;




1
✔





202



               result.test_is_true("bv[0] now 0 again", !bv[0]);




1
✔





203



               bv[0] &= !bv[1];




1
✔





204



               result.test_is_true("bv[0] still 0 once more", !bv[0]);




1
✔





205












206



               result.require("precondition 2", !bv[1] && !bv[2]);




1
✔





207



               bv[1] |= 1;  // NOLINT(modernize-use-bool-literals)




1
✔





208



               result.test_is_true("bv[1] is now 1", bv[1]);




1
✔





209



               bv[1] |= 0;  // NOLINT(modernize-use-bool-literals)




1
✔





210



               result.test_is_true("bv[1] is still 1", bv[1]);




1
✔





211



               bv[1].unset();




1
✔





212



               bv[1] |= false;




1
✔





213



               result.test_is_true("bv[1] is 0", !bv[1]);




1
✔





214



               bv[1] |= !bv[2];




1
✔





215



               result.test_is_true("bv[1] is 1 again", bv[1]);




1
✔





216












217



               result.require("precondition 3", !bv[2] && !bv[3]);




1
✔





218



               bv[2] ^= 0;  // NOLINT(modernize-use-bool-literals)




1
✔





219



               result.test_is_true("bv[2] is still 0", !bv[2]);




1
✔





220



               bv[2] ^= true;




1
✔





221



               result.test_is_true("bv[2] is now 1", bv[2]);




1
✔





222



               bv[2] ^= !bv[3];




1
✔





223



               result.test_is_true("bv[2] is 0 again", !bv[2]);




1
✔





224



            }),




1
✔





225



   };




11
✔





226



}




1
✔





227












228



std::vector<Test::Result> test_bitvector_capacity(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





229



   return {




1
✔





230



      CHECK("default constructed bitvector",










231



            [](auto& result) {




1
✔





232



               const Botan::bitvector bv;




1
✔





233



               result.test_is_true("empty", bv.empty());




1
✔





234



               result.test_sz_eq("no size", bv.size(), size_t(0));




1
✔





235



               result.test_sz_eq("no capacity", bv.capacity(), size_t(0));




1
✔





236



            }),




1
✔





237












238



      CHECK("allocated bitvector has capacity",










239



            [](auto& result) {




1
✔





240



               const Botan::bitvector bv(1);




1
✔





241



               result.test_is_true("empty", !bv.empty());




1
✔





242



               result.test_sz_eq("small size", bv.size(), size_t(1));




1
✔





243



               result.test_sz_gte("a little capacity", bv.capacity(), size_t(8));




1
✔





244



            }),




1
✔





245












246



      CHECK("reserved bitvector has capacity",










247



            [](auto& result) {




1
✔





248



               Botan::bitvector bv;




1
✔





249



               result.test_sz_eq("no size", bv.size(), size_t(0));




1
✔





250



               result.test_sz_eq("no capacity", bv.capacity(), size_t(0));




1
✔





251












252



               bv.reserve(64);




1
✔





253



               result.test_sz_eq("no size", bv.size(), size_t(0));




1
✔





254



               result.test_sz_gte("no capacity", bv.capacity(), size_t(64));




1
✔





255












256



               bv.reserve(128);




1
✔





257



               result.test_sz_eq("no size", bv.size(), size_t(0));




1
✔





258



               result.test_sz_gte("no capacity", bv.capacity(), size_t(128));




1
✔





259



            }),




1
✔





260












261



      CHECK("push_back() extends bitvector",










262



            [](Test::Result& result) {




1
✔





263



               Botan::bitvector bv;




1
✔





264



               result.test_is_true("empty", bv.empty());




1
✔





265



               result.test_sz_eq("no size", bv.size(), size_t(0));




1
✔





266












267



               bv.push_back(true);




1
✔





268



               bv.push_back(false);




1
✔





269



               bv.push_back(true);




1
✔





270



               bv.push_back(false);




1
✔





271












272



               result.test_is_true("not empty", !bv.empty());




1
✔





273



               result.test_sz_eq("some size", bv.size(), size_t(4));




1
✔





274



               result.test_sz_gte("capacity is typically bigger than size", bv.capacity(), size_t(8));




1
✔





275












276



               result.test_is_true("bit 0", bv.at(0));




1
✔





277



               result.test_is_true("bit 1", !bv.at(1));




1
✔





278



               result.test_is_true("bit 2", bv.at(2));




1
✔





279



               result.test_is_true("bit 3", !bv.at(3));




1
✔





280












281



               result.test_throws("bit 4 is not yet allocated", [&] { bv.at(4); });




2
✔





282



            }),




1
✔





283












284



      CHECK("pop_back() shortens bitvector",










285



            [](Test::Result& result) {




1
✔





286



               Botan::bitvector bv;




1
✔





287



               bv.push_back(true);




1
✔





288



               bv.push_back(false);




1
✔





289



               bv.push_back(true);




1
✔





290



               bv.push_back(false);




1
✔





291



               result.test_is_true("last is false", !bv.back());




1
✔





292












293



               bv.pop_back();




1
✔





294



               result.test_sz_eq("size() == 3", bv.size(), 3);




1
✔





295



               result.test_is_true("last is true", bv.back());




1
✔





296












297



               bv.pop_back();




1
✔





298



               result.test_sz_eq("size() == 2", bv.size(), 2);




1
✔





299



               result.test_is_true("last is false", !bv.back());




1
✔





300












301



               bv.pop_back();




1
✔





302



               result.test_sz_eq("size() == 1", bv.size(), 1);




1
✔





303



               result.test_is_true("last is true", bv.back());




1
✔





304



               result.test_is_true("first is true", bv.front());




1
✔





305












306



               bv.pop_back();




1
✔





307



               result.test_is_true("empty", bv.empty());




1
✔





308












309



               result.test_throws("bit 4 is not yet allocated", [&] { bv.at(4); });




2
✔





310



            }),




1
✔





311












312



      CHECK("resize()",










313



            [](auto& result) {




1
✔





314



               Botan::bitvector bv(10);




1
✔





315



               bv[0] = true;




1
✔





316



               bv[5] = true;




1
✔





317



               bv[9] = true;




1
✔





318












319



               bv.resize(8);




1
✔





320



               result.test_sz_eq("size is reduced", bv.size(), size_t(8));




1
✔





321












322



               for(size_t i = 0; i < bv.size(); ++i) {




9
✔





323



                  const bool expected = (i == 0 || i == 5);




8
✔





324



                  result.test_bool_eq(Botan::fmt("{} is as expected", i), bv[i], expected);




16
✔





325



               }










326












327



               bv.resize(0);




1
✔





328



               result.test_is_true("resize(0) empties buffer", bv.empty());




1
✔





329












330



               bv.resize(8);




1
✔





331



               result.test_is_true("0 is false", !bv[0]);




1
✔





332



               result.test_is_true("5 is false", !bv[5]);




1
✔





333



            }),




1
✔





334












335



      CHECK("binary bitwise and comparison operators",










336



            [](Test::Result& result) {




1
✔





337



               Botan::bitvector a(8);




1
✔





338



               a.set(0).set(3);




1
✔





339



               Botan::bitvector b(8);




1
✔





340



               b.set(1).set(3);




1
✔





341



               Botan::bitvector c(8);




1
✔





342



               c.set(0).set(3);  // same is a




1
✔





343












344



               result.test_is_true("equal bitvectors compare equal", a == c);




2
✔





345



               result.test_is_true("different bitvectors do not compare equal", !(a == b));




2
✔





346



               result.test_is_true("different bitvectors compare not equal", a != b);




2
✔





347



               result.test_is_true("equal bitvectors do not compare not equal", !(a != c));




2
✔





348












349



               auto or_ab = a | b;




1
✔





350



               result.test_is_true("OR sets union bit 0", or_ab.at(0).is_set());




1
✔





351



               result.test_is_true("OR sets union bit 1", or_ab.at(1).is_set());




1
✔





352



               result.test_is_true("OR sets union bit 3", or_ab.at(3).is_set());




1
✔





353



               result.test_is_true("OR leaves unset bit 2", !or_ab.at(2).is_set());




1
✔





354












355



               auto and_ab = a & b;




1
✔





356



               result.test_is_true("AND keeps common bit 3", and_ab.at(3).is_set());




1
✔





357



               result.test_is_true("AND clears non-common bit 0", !and_ab.at(0).is_set());




1
✔





358



               result.test_is_true("AND clears non-common bit 1", !and_ab.at(1).is_set());




1
✔





359












360



               auto xor_ab = a ^ b;




1
✔





361



               result.test_is_true("XOR sets differing bit 0", xor_ab.at(0).is_set());




1
✔





362



               result.test_is_true("XOR sets differing bit 1", xor_ab.at(1).is_set());




1
✔





363



               result.test_is_true("XOR clears common bit 3", !xor_ab.at(3).is_set());




1
✔





364



            }),




6
✔





365



   };




8
✔





366



}




1
✔





367












368



std::vector<Test::Result> test_bitvector_subvector(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





369



   auto make_bitpattern = [&]<typename T>(T& bitvector, size_t pattern_offset = 0) {




21
✔





370



      auto next = pattern_generator<3>(pattern_offset);




20
✔





371












372



      if constexpr(std::unsigned_integral<T>) {










373



         for(size_t i = 0; i < sizeof(T) * 8; ++i) {




316
✔





374



            bitvector |= static_cast<T>(next()) << i;




304
✔





375



         }










376



      } else {










377



         for(auto& i : bitvector) {




1,616
✔





378



            i = next();




800
✔





379



         }










380



      }










381



   };




8
✔





382












383



   auto bitpattern_at = [&]<std::unsigned_integral T>(T /* ignored */, size_t pattern_offset) -> T {




13
✔





384



      T bitvector = 0;




12
✔





385



      make_bitpattern(bitvector, pattern_offset);




24
✔





386



      return bitvector;










387



   };




1
✔





388












389



   auto check_bitpattern = [&](auto& result, auto& bitvector, size_t offset = 0) {




44
✔





390



      using bv_t = std::remove_cvref_t<decltype(bitvector)>;










391



      auto next = pattern_generator<3>(offset);




43
✔





392












393



      if constexpr(std::unsigned_integral<bv_t>) {










394



         for(size_t i = 0; i < sizeof(bv_t) * 8; ++i) {




496
✔





395



            result.test_bool_eq(Botan::fmt("{} is as expected", i), (bitvector & (bv_t(1) << i)) != 0, next());




960
✔





396



         }










397



      } else {










398



         for(size_t i = 0; i < bitvector.size(); ++i) {




2,056
✔





399



            result.test_bool_eq(Botan::fmt("{} is as expected", i), bitvector[i], next());




4,058
✔





400



         }










401



      }










402



   };




43
✔





403












404



   auto check_bitpattern_with_zero_region = [&](auto& result, auto& bitvector, std::pair<size_t, size_t> zero_region) {




13
✔





405



      auto next = pattern_generator<3>();




12
✔





406



      for(size_t i = 0; i < bitvector.size(); ++i) {




1,212
✔





407



         const bool i_in_range = (zero_region.first <= i && i < zero_region.second);




1,200
✔





408



         const bool expected = next();




1,200
✔





409



         result.test_bool_eq(Botan::fmt("{} is as expected", i), bitvector[i], !i_in_range && expected);




2,400
✔





410



      }










411



   };




12
✔





412












413



   return {




1
✔





414



      CHECK("range errors are caught",










415



            [&](auto& result) {




1
✔





416



               const Botan::bitvector bv(100);




1
✔





417



               result.template test_throws<Botan::Invalid_Argument>("out of range", [&] { bv.subvector(0, 101); });




2
✔





418



               result.template test_throws<Botan::Invalid_Argument>("out of range", [&] { bv.subvector(90, 11); });




2
✔





419



               result.template test_throws<Botan::Invalid_Argument>("out of range", [&] { bv.subvector(100, 1); });




2
✔





420



               result.template test_throws<Botan::Invalid_Argument>("out of range", [&] { bv.subvector(101, 0); });




2
✔





421



            }),




1
✔





422












423



      CHECK("empty copy is allowed",










424



            [&](auto& result) {




1
✔





425



               const Botan::bitvector bv1(100);




1
✔





426



               auto bv2 = bv1.subvector(0, 0);




1
✔





427



               result.test_sz_eq("empty at 0", bv2.size(), size_t(0));




1
✔





428



               auto bv3 = bv1.subvector(10, 0);




1
✔





429



               result.test_sz_eq("empty at 10", bv3.size(), size_t(0));




1
✔





430



               auto bv4 = bv1.subvector(100, 0);




1
✔





431



               result.test_sz_eq("empty at 100", bv3.size(), size_t(0));




1
✔





432



            }),




2
✔





433












434



      CHECK("byte-aligned copy",










435



            [&](auto& result) {




1
✔





436



               Botan::bitvector bv1(100);




1
✔





437



               make_bitpattern(bv1);




1
✔





438












439



               auto bv2 = bv1.subvector(16, 58);




1
✔





440



               result.test_sz_eq("size is as requested", bv2.size(), size_t(58));




1
✔





441



               check_bitpattern(result, bv2, 16);




1
✔





442












443



               auto bv3 = bv1.subvector(32);  // copy until the end




1
✔





444



               result.test_sz_eq("size is as expected", bv3.size(), size_t(68));




1
✔





445



               check_bitpattern(result, bv3, 32);




1
✔





446



            }),




3
✔





447












448



      CHECK("byte-aligned 2",










449



            [&](auto& result) {




1
✔





450



               Botan::bitvector bv1(100);




1
✔





451



               make_bitpattern(bv1);




1
✔





452












453



               auto bv2 = bv1.subvector(8, 91);




1
✔





454



               result.test_sz_eq("size is as expected", bv2.size(), size_t(91));




1
✔





455



               check_bitpattern(result, bv2, 8);




1
✔





456












457



               auto bv3 = bv1.subvector(16, 58);




1
✔





458



               result.test_sz_eq("size is as requested", bv3.size(), size_t(58));




1
✔





459



               check_bitpattern(result, bv3, 16);




1
✔





460












461



               auto bv4 = bv1.subvector(24);  // copy until the end




1
✔





462



               result.test_sz_eq("size is as expected", bv4.size(), size_t(100 - 24));




1
✔





463



               check_bitpattern(result, bv4, 24);




1
✔





464












465



               auto bv5 = bv1.subvector(32);  // copy until the end




1
✔





466



               result.test_sz_eq("size is as expected", bv5.size(), size_t(100 - 32));




1
✔





467



               check_bitpattern(result, bv5, 32);




1
✔





468












469



               auto bv6 = bv1.subvector(48, 51);  // copy until the end




1
✔





470



               result.test_sz_eq("size is as expected", bv6.size(), size_t(51));




1
✔





471



               check_bitpattern(result, bv6, 48);




1
✔





472



            }),




6
✔





473












474



      CHECK("byte-aligned copy must zero-out unused bits",










475



            [&](auto& result) {




1
✔





476



               Botan::bitvector bv1(100);




1
✔





477



               make_bitpattern(bv1);




1
✔





478












479



               auto bv2 = bv1.subvector(16, 17);




1
✔





480



               result.test_sz_eq("size is as requested", bv2.size(), size_t(17));




1
✔





481



               check_bitpattern(result, bv2, 16);




1
✔





482












483



               bv2.resize(32);




1
✔





484



               for(size_t i = 17; i < bv2.size(); ++i) {




16
✔





485



                  result.test_is_true("tail is zero", !bv2[i]);




15
✔





486



               }










487



            }),




2
✔





488












489



      CHECK("unaligned copy",










490



            [&](auto& result) {




1
✔





491



               Botan::bitvector bv1(100);




1
✔





492



               make_bitpattern(bv1);




1
✔





493












494



               auto bv2 = bv1.subvector(19, 69);




1
✔





495



               result.test_sz_eq("size is as requested", bv2.size(), size_t(69));




1
✔





496



               check_bitpattern(result, bv2, 19);




1
✔





497












498



               auto bv3 = bv1.subvector(21);  // copy until the end




1
✔





499



               result.test_sz_eq("size is as expected", bv3.size(), size_t(79));




1
✔





500



               check_bitpattern(result, bv3, 21);




1
✔





501












502



               auto bv4 = bv1.subvector(1, 16);




1
✔





503



               result.test_sz_eq("size is as expected", bv4.size(), size_t(16));




1
✔





504



               check_bitpattern(result, bv4, 1);




1
✔





505












506



               auto bv5 = bv1.subvector(1, 32);




1
✔





507



               result.test_sz_eq("size is as expected", bv5.size(), size_t(32));




1
✔





508



               check_bitpattern(result, bv5, 1);




1
✔





509












510



               auto bv6 = bv5.subvector(1, 12);




1
✔





511



               result.test_sz_eq("size is as expected", bv6.size(), size_t(12));




1
✔





512



               check_bitpattern(result, bv6, 1 + 1);




1
✔





513












514



               auto bv7 = bv1.subvector(17, 67);




1
✔





515



               result.test_sz_eq("size is as expected", bv7.size(), size_t(67));




1
✔





516



               check_bitpattern(result, bv7, 17);




1
✔





517












518



               auto bv8 = bv1.subvector(33);  // copy until the end




1
✔





519



               result.test_sz_eq("size is as expected", bv8.size(), size_t(67));




1
✔





520



               check_bitpattern(result, bv8, 33);




1
✔





521



            }),




8
✔





522












523



      CHECK("byte-aligned unsigned integer subvector",










524



            [&](auto& result) {




1
✔





525



               Botan::bitvector bv1(100);




1
✔





526



               make_bitpattern(bv1);




1
✔





527












528



               const auto u8_0 = bv1.subvector<uint8_t>(0);




1
✔





529



               const auto u8_32 = bv1.subvector<uint8_t>(32);




1
✔





530



               check_bitpattern(result, u8_0, 0);




1
✔





531



               check_bitpattern(result, u8_32, 32);




1
✔





532












533



               const auto u16_0 = bv1.subvector<uint16_t>(0);




1
✔





534



               const auto u16_56 = bv1.subvector<uint16_t>(56);




1
✔





535



               check_bitpattern(result, u16_0, 0);




1
✔





536



               check_bitpattern(result, u16_56, 56);




1
✔





537












538



               const auto u32_0 = bv1.subvector<uint32_t>(0);




1
✔





539



               const auto u32_48 = bv1.subvector<uint32_t>(48);




1
✔





540



               check_bitpattern(result, u32_0, 0);




1
✔





541



               check_bitpattern(result, u32_48, 48);




1
✔





542












543



               const auto u64_0 = bv1.subvector<uint64_t>(0);




1
✔





544



               const auto u64_32 = bv1.subvector<uint64_t>(32);




1
✔





545



               check_bitpattern(result, u64_0, 0);




1
✔





546



               check_bitpattern(result, u64_32, 32);




1
✔





547












548



               result.test_throws("out of range (uint8_t)", [&] { bv1.subvector<uint8_t>(93); });




2
✔





549



               result.test_throws("out of range (uint16_t)", [&] { bv1.subvector<uint16_t>(85); });




2
✔





550



               result.test_throws("out of range (uint32_t)", [&] { bv1.subvector<uint32_t>(69); });




2
✔





551



               result.test_throws("out of range (uint64_t)", [&] { bv1.subvector<uint64_t>(37); });




2
✔





552



            }),




1
✔





553












554



      CHECK("unaligned unsigned integer subvector",










555



            [&](Test::Result& result) {




1
✔





556



               Botan::bitvector bv1(100);




1
✔





557



               make_bitpattern(bv1);




1
✔





558












559



               const auto u8_3 = bv1.subvector<uint8_t>(3);




1
✔





560



               const auto u8_92 = bv1.subvector<uint8_t>(92);




1
✔





561



               check_bitpattern(result, u8_3, 3);




1
✔





562



               check_bitpattern(result, u8_92, 92);




1
✔





563












564



               const auto u16_7 = bv1.subvector<uint16_t>(7);




1
✔





565



               const auto u16_84 = bv1.subvector<uint16_t>(84);




1
✔





566



               check_bitpattern(result, u16_7, 7);




1
✔





567



               check_bitpattern(result, u16_84, 84);




1
✔





568












569



               const auto u32_11 = bv1.subvector<uint32_t>(11);




1
✔





570



               const auto u32_68 = bv1.subvector<uint32_t>(68);




1
✔





571



               check_bitpattern(result, u32_11, 11);




1
✔





572



               check_bitpattern(result, u32_68, 68);




1
✔





573












574



               const auto u64_21 = bv1.subvector<uint64_t>(21);




1
✔





575



               const auto u64_36 = bv1.subvector<uint64_t>(36);




1
✔





576



               check_bitpattern(result, u64_21, 21);




1
✔





577



               check_bitpattern(result, u64_36, 36);




1
✔





578



            }),




1
✔





579












580



      CHECK("byte-aligned unsigned integer subvector replacement",










581



            [&](auto& result) {




1
✔





582



               Botan::bitvector bv1(100);




1
✔





583



               make_bitpattern(bv1);




1
✔





584












585



               bv1.subvector_replace(0, uint8_t(0));




1
✔





586



               check_bitpattern_with_zero_region(result, bv1, {0, 8});




1
✔





587



               bv1.subvector_replace(0, bitpattern_at(uint8_t(0), 0));




2
✔





588



               check_bitpattern(result, bv1);




1
✔





589












590



               bv1.subvector_replace(32, uint8_t(0));




1
✔





591



               check_bitpattern_with_zero_region(result, bv1, {32, 32 + 8});




1
✔





592



               bv1.subvector_replace(32, bitpattern_at(uint8_t(0), 32));




2
✔





593



               check_bitpattern(result, bv1);




1
✔





594












595



               bv1.subvector_replace(56, uint16_t(0));




1
✔





596



               check_bitpattern_with_zero_region(result, bv1, {56, 56 + 16});




1
✔





597



               bv1.subvector_replace(56, bitpattern_at(uint16_t(0), 56));




2
✔





598



               check_bitpattern(result, bv1);




1
✔





599












600



               bv1.subvector_replace(48, uint32_t(0));




1
✔





601



               check_bitpattern_with_zero_region(result, bv1, {48, 48 + 32});




1
✔





602



               bv1.subvector_replace(48, bitpattern_at(uint32_t(0), 48));




2
✔





603



               check_bitpattern(result, bv1);




1
✔





604












605



               bv1.subvector_replace(16, uint64_t(0));




1
✔





606



               check_bitpattern_with_zero_region(result, bv1, {16, 16 + 64});




1
✔





607



               bv1.subvector_replace(16, bitpattern_at(uint64_t(0), 16));




2
✔





608



               check_bitpattern(result, bv1);




1
✔





609












610



               result.test_throws("out of range (uint8_t)", [&] { bv1.subvector_replace<uint8_t>(93, 42); });




2
✔





611



               result.test_throws("out of range (uint16_t)", [&] { bv1.subvector_replace<uint16_t>(85, 42); });




2
✔





612



               result.test_throws("out of range (uint32_t)", [&] { bv1.subvector_replace<uint32_t>(69, 42); });




2
✔





613



               result.test_throws("out of range (uint64_t)", [&] { bv1.subvector_replace<uint64_t>(37, 42); });




2
✔





614



            }),




1
✔





615












616



      CHECK("unaligned unsigned integer subvector replacement",










617



            [&](auto& result) {




1
✔





618



               Botan::bitvector bv1(100);




1
✔





619



               make_bitpattern(bv1);




1
✔





620












621



               bv1.subvector_replace(3, uint8_t(0));




1
✔





622



               check_bitpattern_with_zero_region(result, bv1, {3, 3 + 8});




1
✔





623



               bv1.subvector_replace(3, bitpattern_at(uint8_t(0), 3));




2
✔





624



               check_bitpattern(result, bv1);




1
✔





625












626



               bv1.subvector_replace(92, uint8_t(0));




1
✔





627



               check_bitpattern_with_zero_region(result, bv1, {92, 92 + 8});




1
✔





628



               bv1.subvector_replace(92, bitpattern_at(uint8_t(0), 92));




2
✔





629



               check_bitpattern(result, bv1);




1
✔





630












631



               bv1.subvector_replace(7, uint16_t(0));




1
✔





632



               check_bitpattern_with_zero_region(result, bv1, {7, 7 + 16});




1
✔





633



               bv1.subvector_replace(7, bitpattern_at(uint16_t(0), 7));




2
✔





634



               check_bitpattern(result, bv1);




1
✔





635












636



               bv1.subvector_replace(84, uint16_t(0));




1
✔





637



               check_bitpattern_with_zero_region(result, bv1, {84, 84 + 16});




1
✔





638



               bv1.subvector_replace(84, bitpattern_at(uint16_t(0), 84));




2
✔





639



               check_bitpattern(result, bv1);




1
✔





640












641



               bv1.subvector_replace(11, uint32_t(0));




1
✔





642



               check_bitpattern_with_zero_region(result, bv1, {11, 11 + 32});




1
✔





643



               bv1.subvector_replace(11, bitpattern_at(uint32_t(0), 11));




2
✔





644



               check_bitpattern(result, bv1);




1
✔





645












646



               bv1.subvector_replace(68, uint32_t(0));




1
✔





647



               check_bitpattern_with_zero_region(result, bv1, {68, 68 + 32});




1
✔





648



               bv1.subvector_replace(68, bitpattern_at(uint32_t(0), 68));




2
✔





649



               check_bitpattern(result, bv1);




1
✔





650












651



               bv1.subvector_replace(21, uint64_t(0));




1
✔





652



               check_bitpattern_with_zero_region(result, bv1, {21, 21 + 64});




1
✔





653



               bv1.subvector_replace(21, bitpattern_at(uint64_t(0), 21));




2
✔





654



               check_bitpattern(result, bv1);




1
✔





655



            }),




1
✔





656



   };




11
✔





657



}




1
✔





658












659



std::vector<Test::Result> test_bitvector_global_modifiers_and_predicates(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





660



   auto make_bitpattern = [](auto& bitvector) {




3
✔





661



      auto next = pattern_generator<5>();




2
✔





662



      for(auto& i : bitvector) {




400
✔





663



         i = next();




198
✔





664



      }










665



   };




2
✔





666












667



   auto check_bitpattern = [](auto& result, auto& bitvector) {




2
✔





668



      auto next = pattern_generator<5>();




1
✔





669



      for(size_t i = 0; i < bitvector.size(); ++i) {




100
✔





670



         result.test_bool_eq(Botan::fmt("{} is as expected", i), bitvector[i], next());




198
✔





671



      }










672



   };




1
✔





673












674



   auto check_flipped_bitpattern = [](auto& result, auto& bitvector) {




2
✔





675



      auto next = pattern_generator<5>();




1
✔





676



      for(size_t i = 0; i < bitvector.size(); ++i) {




100
✔





677



         result.test_bool_eq(Botan::fmt("{} is as expected", i), bitvector[i], !next());




198
✔





678



      }










679



   };




1
✔





680












681



   return {




1
✔





682



      CHECK("one bit",










683



            [](auto& result) {




1
✔





684



               Botan::bitvector bv;




1
✔





685



               bv.push_back(true);




1
✔





686












687



               bv.flip();




1
✔





688



               result.test_is_true("bit is flipped", !bv[0]);




1
✔





689












690



               // check that unused bits aren't flipped










691



               bv.resize(8);




1
✔





692



               for(auto&& b : bv) {




9
✔





693



                  result.test_is_true("all bits are false", !b);




8
✔





694



               }










695



               bv.resize(1);




1
✔





696












697



               bv.flip();




1
✔





698



               result.test_is_true("bit is flipped again", bv[0]);




1
✔





699



            }),




1
✔





700












701



      CHECK("bits in many blocks",










702



            [&](auto& result) {




1
✔





703



               Botan::bitvector bv(99);




1
✔





704












705



               make_bitpattern(bv);




1
✔





706



               bv.flip();




1
✔





707



               check_flipped_bitpattern(result, bv);




1
✔





708












709



               bv = ~bv;




2
✔





710



               check_bitpattern(result, bv);




1
✔





711












712



               bv.resize(112);




1
✔





713



               for(size_t i = 99; i < bv.size(); ++i) {




14
✔





714



                  result.test_is_true("just-allocated bit is not set", !bv[i]);




13
✔





715



               }










716



            }),




1
✔





717












718



      CHECK("set and unset",










719



            [&](auto& result) {




1
✔





720



               Botan::bitvector bv(99);




1
✔





721












722



               make_bitpattern(bv);




1
✔





723



               bv.set();




1
✔





724



               bv.resize(128);




1
✔





725



               for(size_t i = 0; i < bv.size(); ++i) {




129
✔





726



                  const bool expected = (i < 99);




128
✔





727



                  result.test_bool_eq("only set bits are set", bv[i], expected);




128
✔





728



               }










729












730



               bv.unset();




1
✔





731



               for(auto&& b : bv) {




130
✔





732



                  result.test_is_true("bit is not set", !b);




128
✔





733



               }










734



            }),




1
✔





735












736



      CHECK("any, none and all",










737



            [&](auto& result) {




1
✔





738



               Botan::bitvector bv(99);




1
✔





739












740



               result.test_is_true("default construction yields all-zero", bv.none_vartime());




1
✔





741



               result.test_is_true("default construction yields all-zero 2", !bv.any_vartime());




1
✔





742



               result.test_is_true("default construction yields all-zero 3", !bv.all_vartime());




1
✔





743



               result.test_is_true("default construction yields all-zero 4", bv.none());




1
✔





744



               result.test_is_true("default construction yields all-zero 5", !bv.any());




1
✔





745



               result.test_is_true("default construction yields all-zero 6", !bv.all());




1
✔





746












747



               bv.set(42);




1
✔





748



               result.test_is_true("setting a bit means there's a bit set", !bv.none_vartime());




1
✔





749



               result.test_is_true("setting a bit means there's a bit set 2", bv.any_vartime());




1
✔





750



               result.test_is_true("setting a bit means there's not all bits set", !bv.all_vartime());




1
✔





751



               result.test_is_true("setting a bit means there's a bit set 3", !bv.none());




1
✔





752



               result.test_is_true("setting a bit means there's a bit set 4", bv.any());




1
✔





753



               result.test_is_true("setting a bit means there's not all bits set 2", !bv.all());




1
✔





754












755



               bv.set();




1
✔





756



               result.test_is_true("setting all bits means there's a bit set", !bv.none_vartime());




1
✔





757



               result.test_is_true("setting all bits means there's a bit set 2", bv.any_vartime());




1
✔





758



               result.test_is_true("setting all bits means all bits are set", bv.all_vartime());




1
✔





759



               result.test_is_true("setting all bits means there's a bit set 3", !bv.none());




1
✔





760



               result.test_is_true("setting all bits means there's a bit set 4", bv.any());




1
✔





761



               result.test_is_true("setting all bits means all bits are set 2", bv.all());




1
✔





762












763



               bv.unset(97);




1
✔





764



               result.test_is_true("a single 0 at the end means that there's a bit set", !bv.none_vartime());




1
✔





765



               result.test_is_true("a single 0 at the end means that there are bits set", bv.any_vartime());




1
✔





766



               result.test_is_true("a single 0 at the end means that there are not all bits set", !bv.all_vartime());




1
✔





767



               result.test_is_true("a single 0 at the end means that there's a bit set 2", !bv.none());




1
✔





768



               result.test_is_true("a single 0 at the end means that there are bits set 2", bv.any());




1
✔





769



               result.test_is_true("a single 0 at the end means that there are not all bits set 2", !bv.all());




1
✔





770












771



               bv.unset();




1
✔





772



               result.test_is_true("unsetting all bits means there's no bit set", bv.none_vartime());




1
✔





773



               result.test_is_true("unsetting all bits means there's no bit set 2", !bv.any_vartime());




1
✔





774



               result.test_is_true("unsetting all bits means there's not all bits set", !bv.all_vartime());




1
✔





775



               result.test_is_true("unsetting all bits means there's no bit set 3", bv.none());




1
✔





776



               result.test_is_true("unsetting all bits means there's no bit set 4", !bv.any());




1
✔





777



               result.test_is_true("unsetting all bits means there's not all bits set 2", !bv.all());




1
✔





778



            }),




1
✔





779












780



      CHECK("hamming weight oddness",










781



            [](auto& result) {




1
✔





782



               const auto even = Botan::hex_decode("FE3410CB0278E4D26602");




1
✔





783



               const auto odd = Botan::hex_decode("BB2418C2B4F288921203");




1
✔





784












785



               result.test_is_true("odd hamming", Botan::bitvector(odd).has_odd_hamming_weight().as_bool());




2
✔





786



               result.test_is_true("even hamming", !Botan::bitvector(even).has_odd_hamming_weight().as_bool());




2
✔





787



            }),




2
✔





788












789



      CHECK("hamming weight",










790



            [](auto& result) {




1
✔





791



               auto naive_count = [](const auto& v) {




5
✔





792



                  size_t weight = 0;




5
✔





793



                  for(const auto& bit : v) {




440
✔





794



                     weight += bit.template as<size_t>();




430
✔





795



                  }










796



                  return weight;




5
✔





797



               };










798












799



               // the last three bits of this bitvector are set, then there's a gap










800



               auto bv = Botan::bitvector(Botan::hex_decode("FE3410CB0278E4D26602E0"));




2
✔





801



               result.test_sz_eq("hamming weight", bv.hamming_weight(), size_t(37));




1
✔





802



               result.test_sz_eq("hamming weight", bv.hamming_weight(), naive_count(bv));




1
✔





803












804



               bv.pop_back();




1
✔





805



               result.test_sz_eq("hamming weight", bv.hamming_weight(), size_t(36));




1
✔





806



               result.test_sz_eq("hamming weight", bv.hamming_weight(), naive_count(bv));




1
✔





807












808



               bv.pop_back();




1
✔





809



               result.test_sz_eq("hamming weight", bv.hamming_weight(), size_t(35));




1
✔





810



               result.test_sz_eq("hamming weight", bv.hamming_weight(), naive_count(bv));




1
✔





811












812



               bv.pop_back();




1
✔





813



               result.test_sz_eq("hamming weight", bv.hamming_weight(), size_t(34));




1
✔





814



               result.test_sz_eq("hamming weight", bv.hamming_weight(), naive_count(bv));




1
✔





815












816



               bv.pop_back();




1
✔





817



               result.test_sz_eq("hamming weight", bv.hamming_weight(), size_t(34));




1
✔





818



               result.test_sz_eq("hamming weight", bv.hamming_weight(), naive_count(bv));




1
✔





819



            }),




1
✔





820



   };




7
✔





821



}




1
✔





822












823



std::vector<Test::Result> test_bitvector_binary_operators(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





824



   auto check_set = [](auto& result, auto bits, std::vector<size_t> set_bits) {




13
✔





825



      for(size_t i = 0; i < bits.size(); ++i) {




252
✔





826



         const bool should_be_set = std::find(set_bits.begin(), set_bits.end(), i) != set_bits.end();




240
✔





827



         result.test_bool_eq(




240
✔





828



            Botan::fmt("{} should {}be set", i, (!should_be_set ? "not " : "")), bits[i], should_be_set);




661
✔





829



      }










830



   };




12
✔





831












832



   auto is_secure_allocator = []<template <typename> typename AllocatorT>(auto& result,




7
✔





833



                                                                          const Botan::bitvector_base<AllocatorT>&) {










834



      result.test_is_true("allocator is Botan::secure_allocator<>",




12
✔





835



                          std::same_as<Botan::secure_allocator<uint8_t>, AllocatorT<uint8_t>>);










836



   };










837












838



   auto is_standard_allocator = []<template <typename> typename AllocatorT>(auto& result,




4
✔





839



                                                                            const Botan::bitvector_base<AllocatorT>&) {










840



      result.test_is_true("allocator is std::allocator<>", std::same_as<std::allocator<uint8_t>, AllocatorT<uint8_t>>);




6
✔





841



   };










842












843



   return {




1
✔





844



      CHECK("bitwise_equals",










845



            [&](auto& result) {




1
✔





846



               Botan::bitvector lhs(20);




1
✔





847



               lhs.set(0).set(4).set(15).set(16).set(19);




1
✔





848



               Botan::bitvector rhs(20);




1
✔





849



               rhs.set(1).set(4).set(16).set(17).set(18);




1
✔





850












851



               result.test_is_false("Not equal bitvectors", lhs.equals_vartime(rhs));




1
✔





852



               result.test_is_false("Not equal bitvectors 2", lhs.equals(rhs));




1
✔





853












854



               lhs.unset().set(13);




1
✔





855



               rhs.unset().set(13);




1
✔





856












857



               result.test_is_true("equal bitvectors", lhs.equals_vartime(rhs));




1
✔





858



               result.test_is_true("equal bitvectors 2", lhs.equals(rhs));




1
✔





859



            }),




2
✔





860












861



      CHECK("bitwise OR",










862



            [&](auto& result) {




1
✔





863



               Botan::bitvector lhs(20);




1
✔





864



               lhs.set(0).set(4).set(15).set(16).set(19);




1
✔





865



               Botan::bitvector rhs(20);




1
✔





866



               rhs.set(1).set(4).set(16).set(17).set(18);




1
✔





867



               Botan::bitvector unary(20);




1
✔





868



               unary.set(8);




1
✔





869












870



               Botan::bitvector res = lhs | rhs;




1
✔





871



               check_set(result, res, {0, 1, 4, 15, 16, 17, 18, 19});




4
✔





872












873



               res |= unary;




1
✔





874



               check_set(result, res, {0, 1, 4, 8, 15, 16, 17, 18, 19});




3
✔





875












876



               is_standard_allocator(result, res);




1
✔





877



            }),




4
✔





878












879



      CHECK("bitwise AND",










880



            [&](auto& result) {




1
✔





881



               Botan::bitvector lhs(20);




1
✔





882



               lhs.set(0).set(4).set(15).set(16).set(18);




1
✔





883



               Botan::bitvector rhs(20);




1
✔





884



               rhs.set(1).set(4).set(16).set(17).set(18);




1
✔





885



               Botan::bitvector unary(20);




1
✔





886



               unary.set(8).set(16);




1
✔





887












888



               Botan::bitvector res = lhs & rhs;




1
✔





889



               check_set(result, res, {4, 16, 18});




4
✔





890












891



               res &= unary;




1
✔





892



               check_set(result, res, {16});




3
✔





893












894



               is_standard_allocator(result, res);




1
✔





895



            }),




4
✔





896












897



      CHECK("bitwise XOR",










898



            [&](auto& result) {




1
✔





899



               Botan::bitvector lhs(20);




1
✔





900



               lhs.set(0).set(4).set(15).set(16).set(18);




1
✔





901



               Botan::bitvector rhs(20);




1
✔





902



               rhs.set(1).set(4).set(16).set(17).set(18);




1
✔





903



               Botan::bitvector unary(20);




1
✔





904



               unary.set(8).set(16);




1
✔





905












906



               Botan::bitvector res = lhs ^ rhs;




1
✔





907



               check_set(result, res, {0, 1, 15, 17});




4
✔





908












909



               res ^= unary;




1
✔





910



               check_set(result, res, {0, 1, 8, 15, 16, 17});




3
✔





911












912



               is_standard_allocator(result, res);




1
✔





913



            }),




4
✔





914












915



      CHECK("bitwise operators with heterogeneous allocators",










916



            [&](auto& result) {




1
✔





917



               Botan::bitvector lhs(20);




1
✔





918



               lhs.set(0).set(4).set(15).set(16).set(18);




1
✔





919



               Botan::secure_bitvector rhs(20);




1
✔





920



               rhs.set(1).set(4).set(16).set(17).set(18);




1
✔





921



               Botan::bitvector unary(20);




1
✔





922



               unary.set(8).set(16);




1
✔





923












924



               auto res1 = lhs | rhs;




1
✔





925



               is_secure_allocator(result, res1);




1
✔





926



               check_set(result, res1, {0, 1, 4, 15, 16, 17, 18});




3
✔





927












928



               auto res2 = rhs | lhs;




1
✔





929



               is_secure_allocator(result, res2);




1
✔





930



               check_set(result, res2, {0, 1, 4, 15, 16, 17, 18});




3
✔





931












932



               auto res3 = lhs & rhs;




1
✔





933



               is_secure_allocator(result, res3);




1
✔





934



               check_set(result, res3, {4, 16, 18});




3
✔





935












936



               auto res4 = rhs & lhs;




1
✔





937



               is_secure_allocator(result, res4);




1
✔





938



               check_set(result, res4, {4, 16, 18});




3
✔





939












940



               auto res5 = lhs ^ rhs;




1
✔





941



               is_secure_allocator(result, res5);




1
✔





942



               check_set(result, res5, {0, 1, 15, 17});




3
✔





943












944



               auto res6 = rhs ^ lhs;




1
✔





945



               is_secure_allocator(result, res6);




1
✔





946



               check_set(result, res6, {0, 1, 15, 17});




4
✔





947



            }),




8
✔





948



   };




6
✔





949



}




1
✔





950












951



std::vector<Test::Result> test_bitvector_serialization(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





952



   constexpr uint8_t outlen = 64;




1
✔





953



   const auto bytearray = [] {




1
✔





954



      std::array<uint8_t, outlen> out{};










955



      for(uint8_t i = 0; i < outlen; ++i) {










956



         out[i] = i;










957



      }










958



      return out;










959



   }();










960












961



   auto validate_bytewise = [](auto& result, const auto& bv, std::span<const uint8_t> bytes) {




3
✔





962



      for(size_t i = 0; i < bytes.size(); ++i) {




129
✔





963



         const uint8_t b = (static_cast<uint8_t>(bv[0 + i * 8]) << 0) | (static_cast<uint8_t>(bv[1 + i * 8]) << 1) |




127
✔





964



                           (static_cast<uint8_t>(bv[2 + i * 8]) << 2) | (static_cast<uint8_t>(bv[3 + i * 8]) << 3) |




127
✔





965



                           (static_cast<uint8_t>(bv[4 + i * 8]) << 4) | (static_cast<uint8_t>(bv[5 + i * 8]) << 5) |




127
✔





966



                           (static_cast<uint8_t>(bv[6 + i * 8]) << 6) | (static_cast<uint8_t>(bv[7 + i * 8]) << 7);




127
✔





967












968



         result.test_sz_eq(




254
✔





969



            Botan::fmt("byte {} is as expected", i), static_cast<size_t>(b), static_cast<size_t>(bytes[i]));




127
✔





970



      }










971



   };




2
✔





972












973



   return {




1
✔





974



      CHECK("empty byte-array",










975



            [](auto& result) {




1
✔





976



               std::vector<uint8_t> bytes;




1
✔





977



               result.require("empty buffer", bytes.empty());




1
✔





978












979



               const Botan::bitvector bv(bytes);




1
✔





980



               result.test_is_true("empty bit vector", bv.empty());




1
✔





981












982



               auto rendered = bv.to_bytes();




1
✔





983



               result.test_is_true("empty bit vector renders an empty buffer", rendered.empty());




1
✔





984



            }),




1
✔





985












986



      CHECK("to_bytes() uses secure_allocator if necessary",










987



            [](auto& result) {




1
✔





988



               const Botan::bitvector bv;




1
✔





989



               const Botan::secure_bitvector sbv;




1
✔





990












991



               auto rbv = bv.to_bytes();




1
✔





992



               auto rsbv = sbv.to_bytes();




1
✔





993












994



               result.test_is_true("ordinary bitvector uses ordinary std::vector",




1
✔





995



                                   std::is_same_v<std::vector<uint8_t>, decltype(rbv)>);










996



               result.test_is_true("secure bitvector uses secure_vector",




1
✔





997



                                   std::is_same_v<Botan::secure_vector<uint8_t>, decltype(rsbv)>);










998



            }),




1
✔





999












1000



      CHECK("load all bits from byte-array (aligned data)",










1001



            [&](auto& result) {




1
✔





1002



               const Botan::bitvector bv(bytearray);




1
✔





1003



               validate_bytewise(result, bv, bytearray);




1
✔





1004












1005



               const auto rbv = bv.to_bytes();




1
✔





1006



               result.test_is_true("uint8_t rendered correctly", std::ranges::equal(bytearray, rbv));




2
✔





1007



            }),




2
✔





1008












1009



      CHECK("load all bits from byte-array (unaligned blocks)",










1010



            [&](auto& result) {




1
✔





1011



               std::array<uint8_t, 63> unaligned_bytearray{};




1
✔





1012



               Botan::copy_mem(unaligned_bytearray, std::span{bytearray}.first<unaligned_bytearray.size()>());




1
✔





1013












1014



               const Botan::bitvector bv(unaligned_bytearray);




1
✔





1015



               validate_bytewise(result, bv, unaligned_bytearray);




1
✔





1016












1017



               const auto rbv = bv.to_bytes();




1
✔





1018



               result.test_is_true("uint8_t rendered correctly", std::ranges::equal(unaligned_bytearray, rbv));




1
✔





1019



            }),




3
✔





1020












1021



      CHECK("load bits from byte-array (unaligned data)",










1022



            [&](auto& result) {




1
✔





1023



               constexpr size_t bits_to_load = 31;




1
✔





1024



               constexpr size_t bytes_to_load = Botan::ceil_tobytes(bits_to_load);




1
✔





1025












1026



               Botan::bitvector bv(bytearray, bits_to_load);




1
✔





1027












1028



               for(size_t i = 0; i < bits_to_load; ++i) {




32
✔





1029



                  const bool expected = (i == 8) || (i == 17) || (i == 24) || (i == 25);




31
✔





1030



                  result.test_bool_eq(Botan::fmt("bit {} is correct", i), bv.at(i), expected);




62
✔





1031



               }










1032












1033



               const auto rbv = bv.to_bytes();




1
✔





1034



               std::array<uint8_t, bytes_to_load> expected_bytes{};




1
✔





1035



               Botan::copy_mem(expected_bytes, std::span{bytearray}.first<bytes_to_load>());




1
✔





1036



               expected_bytes.back() &= (uint8_t(1) << (bits_to_load % 8)) - 1;




1
✔





1037



               result.test_is_true("uint8_t rendered correctly", std::ranges::equal(expected_bytes, rbv));




1
✔





1038



            }),




2
✔





1039












1040



      CHECK("to_bytes(std::span) can handle non-zero out-memory",










1041



            [&](auto& result) {




1
✔





1042



               constexpr size_t bits_to_load = 33;




1
✔





1043



               constexpr size_t bytes_to_load = Botan::ceil_tobytes(bits_to_load);




1
✔





1044












1045



               Botan::bitvector bv(bytearray, bits_to_load);




1
✔





1046



               bv.set(32);




1
✔





1047












1048



               std::array<uint8_t, bytes_to_load> out = {0xFF, 0xFF, 0xFF, 0xFF, 0xFF};




1
✔





1049



               bv.to_bytes(out);




1
✔





1050












1051



               result.test_u8_eq("uint8_t rendered correctly", out[4], 0x01);




1
✔





1052



            }),




1
✔





1053



   };




7
✔





1054



}




1
✔





1055












1056



std::vector<Test::Result> test_bitvector_constant_time_operations(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





1057



   constexpr Botan::CT::Choice yes = Botan::CT::Choice::yes();




1
✔





1058



   constexpr Botan::CT::Choice no = Botan::CT::Choice::no();




1
✔





1059












1060



   return {




1
✔





1061



      CHECK("conditional XOR, block aligned",










1062



            [&](auto& result) {




1
✔





1063



               Botan::bitvector bv1(Botan::hex_decode("BAADF00DCAFEBEEF"));




2
✔





1064



               const Botan::secure_bitvector bv2(Botan::hex_decode("CAFEBEEFC001B33F"));




2
✔





1065



               const auto initial_bv1 = bv1;




1
✔





1066



               const auto xor_result = bv1 ^ bv2;




1
✔





1067












1068



               bv1.ct_conditional_xor(no, bv2);




1
✔





1069



               result.test_is_true("no change after false condition", bv1 == initial_bv1);




1
✔





1070












1071



               bv1.ct_conditional_xor(yes, bv2);




1
✔





1072



               result.test_is_true("XORed if condition was true", bv1 == xor_result);




1
✔





1073



            }),




4
✔





1074












1075



      CHECK("conditional XOR, byte aligned",










1076



            [&](auto& result) {




1
✔





1077



               Botan::bitvector bv1(Botan::hex_decode("BAADF00DCAFEBEEF42"));




2
✔





1078



               const Botan::secure_bitvector bv2(Botan::hex_decode("CAFEBEEFC001B33F13"));




2
✔





1079



               const auto initial_bv1 = bv1;




1
✔





1080



               const auto xor_result = bv1 ^ bv2;




1
✔





1081












1082



               bv1.ct_conditional_xor(no, bv2);




1
✔





1083



               result.test_is_true("no change after false condition", bv1 == initial_bv1);




1
✔





1084












1085



               bv1.ct_conditional_xor(yes, bv2);




1
✔





1086



               result.test_is_true("XORed if condition was true", bv1 == xor_result);




1
✔





1087



            }),




4
✔





1088












1089



      CHECK("conditional XOR, no alignment",










1090



            [&](auto& result) {




1
✔





1091



               Botan::bitvector bv1(Botan::hex_decode("BAADF00DCAFEBEEF42"));




1
✔





1092



               bv1.push_back(true);




1
✔





1093



               bv1.push_back(false);




1
✔





1094



               Botan::secure_bitvector bv2(Botan::hex_decode("CAFEBEEFC001B33F13"));




1
✔





1095



               bv2.push_back(false);




1
✔





1096



               bv2.push_back(false);




1
✔





1097












1098



               const auto initial_bv1 = bv1;




1
✔





1099



               const auto xor_result = bv1 ^ bv2;




1
✔





1100












1101



               bv1.ct_conditional_xor(no, bv2);




1
✔





1102



               result.test_is_true("no change after false condition", bv1 == initial_bv1);




1
✔





1103












1104



               bv1.ct_conditional_xor(yes, bv2);




1
✔





1105



               result.test_is_true("XORed if condition was true", bv1 == xor_result);




1
✔





1106



            }),




4
✔





1107



   };




4
✔





1108



}




1
✔





1109












1110



std::vector<Test::Result> test_bitvector_conditional_xor_workload(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





1111



   Test::Result res("Conditional XOR, Gauss Workload");




1
✔





1112












1113



   auto rng = Test::new_rng("Conditional XOR, Gauss Workload");




1
✔





1114












1115



   const size_t matrix_rows = 1664;




1
✔





1116



   const size_t matrix_columns = 8192;




1
✔





1117












1118



   std::vector<Botan::bitvector> bitvec_vec;




1
✔





1119



   bitvec_vec.reserve(matrix_rows);




1
✔





1120



   for(size_t i = 0; i < matrix_rows; ++i) {




1,665
✔





1121



      bitvec_vec.push_back(Botan::bitvector(rng->random_vec(matrix_columns / 8)));




4,992
✔





1122



   }










1123












1124



   // Simulate #ops of Gaussian Elimination










1125



   const size_t total_iter = matrix_rows * (3 * matrix_rows - 1) / 2;




1
✔





1126



   const auto start = Test::timestamp();




1
✔





1127



   for(size_t i = 0; i < total_iter; ++i) {




4,152,513
✔





1128



      const auto choice = Botan::CT::Choice::from_int(static_cast<uint8_t>(rng->next_byte() % 2));




4,152,512
✔





1129



      bitvec_vec.at(i % matrix_rows).ct_conditional_xor(choice, bitvec_vec.at(rng->next_byte() % matrix_rows));




4,152,512
✔





1130



   }










1131



   res.set_ns_consumed(Test::timestamp() - start);




1
✔





1132












1133



   res.test_is_true("Prevent compiler from optimizing away",




2
✔





1134



                    bitvec_vec.at(0).any_vartime() || bitvec_vec.at(0).none_vartime());




1
✔





1135



   return {res};




3
✔





1136



}




3
✔





1137












1138



std::vector<Test::Result> test_bitvector_iterators(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





1139



   return {




1
✔





1140



      CHECK("Iterators: range-based for loop",










1141



            [](auto& result) {




1
✔





1142



               Botan::bitvector bv(6);




1
✔





1143



               bv.set(0).set(3).set(4);




1
✔





1144












1145



               for(size_t i = 0; auto& ref : bv) {




8
✔





1146



                  const bool expected = i == 0 || i == 3 || i == 4;




6
✔





1147



                  result.test_bool_eq(Botan::fmt("bit {} is as expected", i), ref, expected);




6
✔





1148



                  ++i;




6
✔





1149



               }










1150












1151



               for(size_t i = 0; const auto& ref : bv) {




8
✔





1152



                  const bool expected = i == 0 || i == 3 || i == 4;




6
✔





1153



                  result.test_bool_eq(Botan::fmt("const bit {} is as expected", i), ref, expected);




6
✔





1154



                  ++i;




6
✔





1155



               }










1156












1157



               for(auto ref : bv) {




14
✔





1158



                  ref = true;




6
✔





1159



               }










1160












1161



               result.test_is_true("all bits are set", bv.all_vartime());




1
✔





1162



            }),




1
✔





1163












1164



      CHECK("Iterators: bare usage",










1165



            [](auto& result) {




1
✔





1166



               Botan::bitvector bv(6);




1
✔





1167



               bv.set(0).set(3).set(4);




1
✔





1168












1169



               size_t i = 0;




1
✔





1170



               for(auto itr = bv.begin(); itr != bv.end(); ++itr, ++i) {




7
✔





1171



                  const bool expected = i == 0 || i == 3 || i == 4;




6
✔





1172



                  result.test_bool_eq(Botan::fmt("bit {} is as expected", i), *itr, expected);




12
✔





1173



               }










1174












1175



               i = 0;




1
✔





1176



               for(auto itr = bv.cbegin(); itr != bv.cend(); itr++, ++i) {




7
✔





1177



                  const bool expected = i == 0 || i == 3 || i == 4;




6
✔





1178



                  result.test_bool_eq(Botan::fmt("const bit {} is as expected", i), itr->is_set(), expected);




12
✔





1179



               }










1180












1181



               i = 6;




1
✔





1182



               auto ritr = bv.end();




1
✔





1183



               // NOLINTNEXTLINE(*-avoid-do-while)










1184



               do {










1185



                  --ritr;




6
✔





1186



                  --i;




6
✔





1187



                  const bool expected = i == 0 || i == 3 || i == 4;




6
✔





1188



                  result.test_bool_eq(Botan::fmt("reverse bit {} is as expected", i), *ritr, expected);




6
✔





1189



               } while(ritr != bv.begin());




11
✔





1190












1191



               for(auto& itr : bv) {




8
✔





1192



                  itr.flip();




6
✔





1193



               }










1194












1195



               i = 0;




1
✔





1196



               for(auto itr = bv.begin(); itr != bv.end(); ++itr, ++i) {




7
✔





1197



                  const bool expected = i == 1 || i == 2 || i == 5;




6
✔





1198



                  result.test_bool_eq(Botan::fmt("flipped bit {} is as expected", i), *itr, expected);




12
✔





1199



               }










1200



            }),




1
✔





1201












1202



      CHECK("Iterators: std::distance and std::advance",










1203



            [](auto& result) {




1
✔





1204



               Botan::bitvector bv(6);




1
✔





1205



               result.test_sz_eq("distance", static_cast<size_t>(std::distance(bv.begin(), bv.end())), 6);




2
✔





1206



               result.test_sz_eq("const distance", static_cast<size_t>(std::distance(bv.cbegin(), bv.cend())), 6);




2
✔





1207












1208



               auto b = bv.begin();




1
✔





1209



               std::advance(b, 3);




1
✔





1210



               result.test_sz_eq("half distance", static_cast<size_t>(std::distance(bv.begin(), b)), 3);




2
✔





1211



            }),




1
✔





1212












1213



      CHECK("Iterators: large bitvector",










1214



            [](auto& result) {




1
✔





1215



               Botan::bitvector bv(500);




1
✔





1216












1217



               for(auto itr = bv.begin(); itr != bv.end(); ++itr) {




1,001
✔





1218



                  if(std::distance(bv.begin(), itr) % 2 == 0) {




1,000
✔





1219



                     itr->set();




250
✔





1220



                  }










1221



                  if(std::distance(bv.begin(), itr) % 3 == 0) {




1,000
✔





1222



                     *itr = true;




167
✔





1223



                  }










1224



               }










1225












1226



               for(size_t i = 0; const auto& bit : bv) {




502
✔





1227



                  const bool expected = (i % 2 == 0) || (i % 3 == 0);




500
✔





1228



                  result.test_bool_eq(Botan::fmt("bit {} is as expected", i), bit, expected);




500
✔





1229



                  ++i;




500
✔





1230



               }










1231



            }),




1
✔





1232












1233



      CHECK("Iterators: satiesfies C++20 concepts",










1234



            [](auto& result) {




1
✔





1235



               Botan::secure_bitvector bv(42);




1
✔





1236



               auto ro_itr = bv.cbegin();




1
✔





1237



               auto rw_itr = bv.begin();




1
✔





1238












1239



               using ro = decltype(ro_itr);










1240



               using rw = decltype(rw_itr);










1241












1242



               result.test_is_true("ro input iterator", std::input_iterator<ro>);




1
✔





1243



               result.test_is_true("rw input iterator", std::input_iterator<rw>);




1
✔





1244



               result.test_is_true("ro is not an output iterator", !std::output_iterator<ro, bool>);




1
✔





1245



               result.test_is_true("rw output iterator", std::output_iterator<rw, bool>);




1
✔





1246



               result.test_is_true("ro bidirectional iterator", std::bidirectional_iterator<ro>);




1
✔





1247



               result.test_is_true("rw bidirectional iterator", std::bidirectional_iterator<rw>);




1
✔





1248



               result.test_is_true("ro not a contiguous iterator", !std::contiguous_iterator<ro>);




1
✔





1249



               result.test_is_true("rw not a contiguous iterator", !std::contiguous_iterator<rw>);




1
✔





1250



            }),




1
✔





1251



   };




6
✔





1252



}




1
✔





1253












1254



using TestBitvector = Botan::Strong<Botan::bitvector, struct TestBitvector_>;










1255



using TestSecureBitvector = Botan::Strong<Botan::secure_bitvector, struct TestBitvector_>;










1256



using TestUInt32 = Botan::Strong<uint32_t, struct TestUInt32_>;










1257












1258



std::vector<Test::Result> test_bitvector_strongtype_adapter(Botan::RandomNumberGenerator& /*rng*/) {




1
✔





1259



   Test::Result result("Bitvector in strong type");




1
✔





1260












1261



   TestBitvector bv1(33);




1
✔





1262












1263



   result.test_is_true("bv1 is not empty", !bv1.empty());




1
✔





1264



   result.test_sz_eq("bv1 has size 33", bv1.size(), size_t(33));




1
✔





1265












1266



   bv1[0] = true;




1
✔





1267



   bv1.at(1) = true;




1
✔





1268



   bv1.set(2);




2
✔





1269



   bv1.unset(3);




2
✔





1270



   bv1.flip(4);




2
✔





1271



   bv1.push_back(true);




1
✔





1272



   bv1.push_back(false);




1
✔





1273



   bv1.pop_back();




1
✔





1274












1275



   result.test_is_true("bv1 front is set", bv1.front());




1
✔





1276



   result.test_is_true("bv1 back is set", bv1.back());




1
✔





1277



   result.test_is_true("bv1 has some one bits", bv1.any_vartime());




1
✔





1278



   result.test_is_true("bv1 is not all zero", !bv1.none_vartime());




1
✔





1279



   result.test_is_true("bv1 is not all one", !bv1.all_vartime());




1
✔





1280












1281



   result.test_is_true("hamming weight of bv1", bv1.has_odd_hamming_weight().as_bool());




1
✔





1282












1283



   for(size_t i = 0; auto bit : bv1) {




36
✔





1284



      const bool expected = (i == 0 || i == 1 || i == 2 || i == 4 || i == 33);




34
✔





1285



      result.test_is_true(Botan::fmt("bv1 bit {} is set", i), bit == expected);




34
✔





1286



      ++i;




34
✔





1287



   }










1288












1289



   bv1.flip();




2
✔





1290












1291



   for(size_t i = 0; auto bit : bv1) {




36
✔





1292



      const bool expected = (i == 0 || i == 1 || i == 2 || i == 4 || i == 33);




34
✔





1293



      result.test_is_true(Botan::fmt("bv1 bit {} is set", i), bit != expected);




34
✔





1294



      ++i;




34
✔





1295



   }










1296












1297



   auto bv2 = bv1.as<TestSecureBitvector>();




1
✔





1298












1299



   auto bv3 = bv1 | bv2;




1
✔





1300



   result.test_is_true("bv3 is a secure_bitvector", std::same_as<Botan::secure_bitvector, decltype(bv3)>);




1
✔





1301












1302



   auto bv4 = bv2.subvector<TestSecureBitvector>(0, 5);




1
✔





1303



   result.test_is_true("bv4 is a TestSecureBitvector", std::same_as<TestSecureBitvector, decltype(bv4)>);




1
✔





1304












1305



   auto bv5 = bv2.subvector<TestUInt32>(1);




1
✔





1306



   result.test_is_true("bv5 is a TestUInt32", std::same_as<TestUInt32, decltype(bv5)>);




1
✔





1307



   result.test_u32_eq("bv5 has expected value", bv5.get(), 0xFFFFFFF4);




1
✔





1308












1309



   const auto str = bv4.to_string();




1
✔





1310



   result.test_str_eq("bv4 to_string", str, "00010");




1
✔





1311












1312



   return {result};




3
✔





1313



}




6
✔





1314












1315



}  // namespace










1316












1317



class BitVector_Tests final : public Test {




1
✔





1318



   public:










1319



      std::vector<Test::Result> run() override {




1
✔





1320



         std::vector<Test::Result> results;




1
✔





1321



         auto& rng = Test::rng();




1
✔





1322












1323



         const std::vector<std::function<std::vector<Test::Result>(Botan::RandomNumberGenerator&)>> funcs{




1
✔





1324



            test_bitvector_bitwise_accessors,










1325



            test_bitvector_capacity,










1326



            test_bitvector_subvector,










1327



            test_bitvector_global_modifiers_and_predicates,










1328



            test_bitvector_binary_operators,










1329



            test_bitvector_serialization,










1330



            test_bitvector_constant_time_operations,










1331



            test_bitvector_conditional_xor_workload,










1332



            test_bitvector_iterators,










1333



            test_bitvector_strongtype_adapter,










1334



         };




11
✔





1335












1336



         for(const auto& test_func : funcs) {




11
✔





1337



            auto fn_results = test_func(rng);




10
✔





1338



            results.insert(results.end(), fn_results.begin(), fn_results.end());




10
✔





1339



         }




10
✔





1340












1341



         return results;




1
✔





1342



      }




2
✔





1343



};










1344












1345



BOTAN_REGISTER_TEST("utils", "bitvector", BitVector_Tests);










1346












1347



#endif










1348












1349



}  // namespace Botan_Tests
























    

  • 

    •