randombit / botan / 20283898778

coverage: 90.52% (+0.2%) from 90.36%
20283898778

Pull #5167

github

web-flow 
Merge 795a38954 into 3d96b675e
Pull Request #5167: Changes to reduce unnecessary inclusions

101154 of 111748 relevant lines covered (90.52%)

12682929.61 hits per line

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

99.89
/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/rng.h>










12



   #include <botan/internal/bitvector.h>










13



   #include <botan/internal/fmt.h>










14



   #include <algorithm>










15



   #include <numeric>










16



#endif










17












18



namespace Botan_Tests {










19












20



#if defined(BOTAN_HAS_BITVECTOR)










21












22



namespace {










23












24



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










25



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




174✔





26



   if(min == max) {




174✔





27



      return min;










28



   }










29












30



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




174✔





31



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




174✔





32



}










33












34



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










35



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




3✔





36



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




6✔





37



      // Fisher-Yates shuffle










38



      if(v.size() < 2) {




3✔





39



         return;










40



      }










41



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




171✔





42



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




168✔





43



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




168✔





44



      }










45



   };




3✔





46












47



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




3✔





48



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




3✔





49



   shuffle(indices);




3✔





50



   indices.resize(n);




3✔





51



   return indices;




3✔





52



}




×







53












54



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










55



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




3✔





56



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




3✔





57



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




3✔





58



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




3✔





59












60



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




6✔





61



}




6✔





62












63



template <size_t mod>










64



auto pattern_generator(size_t offset = 0) {




79✔





65



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




5,209✔





66



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




5,209✔





67



      ++i;




5,209✔





68



      return result;










69



   };










70



}










71












72



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




1✔





73



   return {




1✔





74



      CHECK("default constructed bitvector",










75



            [](auto& result) {




1✔





76



               const Botan::bitvector bv;




1✔





77



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




2✔





78



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




2✔





79



            }),




1✔





80












81



      CHECK("preallocated construction of bitvector",










82



            [](auto& result) {




1✔





83



               Botan::bitvector bv(10);




1✔





84



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




2✔





85



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




1✔





86



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




11✔





87



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




20✔





88



               }










89



            }),




1✔





90












91



      CHECK("setting bits",










92



            [&](auto& result) {




1✔





93



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




1✔





94












95



               for(const size_t i : ones) {




52✔





96



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




51✔





97



                     bv.set(i);




20✔





98



                  } else {










99



                     bv.at(i) = true;




31✔





100



                  }










101



               }










102



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




58✔





103



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




171✔





104



               }










105



            }),




1✔





106












107



      CHECK("unsetting bits",










108



            [&](auto& result) {




1✔





109



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




1✔





110



               for(auto b : bv) {




59✔





111



                  b.set();




57✔





112



               }










113












114



               for(const size_t i : zeros) {




29✔





115



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




28✔





116



                     bv.unset(i);




14✔





117



                  } else {










118



                     bv.at(i) = false;




14✔





119



                  }










120



               }










121



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




58✔





122



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




171✔





123



               }










124



            }),




1✔





125












126



      CHECK("flipping bits",










127



            [&](auto& result) {




1✔





128



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




1✔





129












130



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




58✔





131



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




114✔





132



                     bv.set(i);




46✔





133



                  }










134



                  bv.flip(i);




57✔





135



               }










136



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




58✔





137



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




171✔





138



               }










139



            }),




1✔





140












141



      CHECK("accessors validate offsets",










142



            [](auto& result) {




1✔





143



               Botan::bitvector bv(10);




1✔





144



               result.template test_throws<Botan::Invalid_Argument>(




2✔





145



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




2✔





146



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




3✔





147



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




3✔





148



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




3✔





149



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




4✔





150



            }),




1✔





151












152



      CHECK("multiblock handling",










153



            [](auto& result) {




1✔





154



               Botan::bitvector bv(128);




1✔





155



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




2✔





156



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




1✔





157



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




129✔





158



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




128✔





159



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




256✔





160



               }










161



            }),




1✔





162












163



      CHECK("subscript operator",










164



            [](auto& result) {




1✔





165



               Botan::bitvector bv(128);




1✔





166



               bv[0].set();




1✔





167



               bv[1] = true;




1✔





168



               bv[2].flip();




1✔





169



               bv[64] = true;




1✔





170



               bv[80] = true;




1✔





171



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




2✔





172



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




2✔





173



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




2✔





174



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




2✔





175



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




2✔





176



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




2✔





177



            }),




1✔





178












179



      CHECK("subscript operator does not validate offsets",










180



            [](auto& result) {




1✔





181



               Botan::bitvector bv(10);




1✔





182



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




3✔





183



               // Technically the next line is undefined behaviour.










184



               // Though, the current implementation detail won't










185



               // cause issues, which might change!










186



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




3✔





187



            }),




1✔





188












189



      CHECK("bitwise assignment modifiers",










190



            [](auto& result) {




1✔





191



               Botan::bitvector bv(4);




1✔





192












193



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




2✔





194



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




1✔





195



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




2✔





196



               bv[0].set();




1✔





197



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




1✔





198



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




2✔





199



               bv[0] &= false;




1✔





200



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




2✔





201



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




1✔





202



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




2✔





203












204



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




2✔





205



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




1✔





206



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




2✔





207



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




1✔





208



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




2✔





209



               bv[1].unset();




1✔





210



               bv[1] |= false;




1✔





211



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




2✔





212



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




1✔





213



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




2✔





214












215



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




2✔





216



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




1✔





217



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




2✔





218



               bv[2] ^= true;




1✔





219



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




2✔





220



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




1✔





221



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




2✔





222



            }),




1✔





223



   };




11✔





224



}




1✔





225












226



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




1✔





227



   return {




1✔





228



      CHECK("default constructed bitvector",










229



            [](auto& result) {




1✔





230



               const Botan::bitvector bv;




1✔





231



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




2✔





232



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




2✔





233



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




2✔





234



            }),




1✔





235












236



      CHECK("allocated bitvector has capacity",










237



            [](auto& result) {




1✔





238



               const Botan::bitvector bv(1);




1✔





239



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




2✔





240



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




2✔





241



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




2✔





242



            }),




1✔





243












244



      CHECK("reserved bitvector has capacity",










245



            [](auto& result) {




1✔





246



               Botan::bitvector bv;




1✔





247



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




2✔





248



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




2✔





249












250



               bv.reserve(64);




1✔





251



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




2✔





252



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




2✔





253












254



               bv.reserve(128);




1✔





255



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




2✔





256



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




2✔





257



            }),




1✔





258












259



      CHECK("push_back() extends bitvector",










260



            [](Test::Result& result) {




1✔





261



               Botan::bitvector bv;




1✔





262



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




2✔





263



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




1✔





264












265



               bv.push_back(true);




1✔





266



               bv.push_back(false);




1✔





267



               bv.push_back(true);




1✔





268



               bv.push_back(false);




1✔





269












270



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




2✔





271



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




1✔





272



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




1✔





273












274



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




2✔





275



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




2✔





276



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




2✔





277



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




2✔





278












279



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




4✔





280



            }),




1✔





281












282



      CHECK("pop_back() shortens bitvector",










283



            [](Test::Result& result) {




1✔





284



               Botan::bitvector bv;




1✔





285



               bv.push_back(true);




1✔





286



               bv.push_back(false);




1✔





287



               bv.push_back(true);




1✔





288



               bv.push_back(false);




1✔





289



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




2✔





290












291



               bv.pop_back();




1✔





292



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




1✔





293



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




2✔





294












295



               bv.pop_back();




1✔





296



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




1✔





297



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




2✔





298












299



               bv.pop_back();




1✔





300



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




1✔





301



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




2✔





302



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




2✔





303












304



               bv.pop_back();




1✔





305



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




2✔





306












307



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




4✔





308



            }),




1✔





309












310



      CHECK("resize()",










311



            [](auto& result) {




1✔





312



               Botan::bitvector bv(10);




1✔





313



               bv[0] = true;




1✔





314



               bv[5] = true;




1✔





315



               bv[9] = true;




1✔





316












317



               bv.resize(8);




1✔





318



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




1✔





319












320



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




9✔





321



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




8✔





322



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




16✔





323



               }










324












325



               bv.resize(0);




1✔





326



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




2✔





327












328



               bv.resize(8);




1✔





329



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




2✔





330



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




2✔





331



            }),




1✔





332



   };




7✔





333



}




1✔





334












335



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




1✔





336



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




21✔





337



      auto next = pattern_generator<3>(pattern_offset);




20✔





338












339



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










340



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




316✔





341



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




304✔





342



         }










343



      } else {










344



         for(auto& i : bitvector) {




1,616✔





345



            i = next();




800✔





346



         }










347



      }










348



   };




8✔





349












350



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




13✔





351



      T bitvector = 0;




12✔





352



      make_bitpattern(bitvector, pattern_offset);




24✔





353



      return bitvector;










354



   };




1✔





355












356



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




44✔





357



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










358



      auto next = pattern_generator<3>(offset);




43✔





359












360



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










361



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




496✔





362



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




960✔





363



         }










364



      } else {










365



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




2,056✔





366



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




4,058✔





367



         }










368



      }










369



   };




43✔





370












371



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




13✔





372



      auto next = pattern_generator<3>();




12✔





373



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




1,212✔





374



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




1,200✔





375



         const bool expected = next();




1,200✔





376



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




2,400✔





377



      }










378



   };




12✔





379












380



   return {




1✔





381



      CHECK("range errors are caught",










382



            [&](auto& result) {




1✔





383



               const Botan::bitvector bv(100);




1✔





384



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




3✔





385



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




3✔





386



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




3✔





387



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




4✔





388



            }),




1✔





389












390



      CHECK("empty copy is allowed",










391



            [&](auto& result) {




1✔





392



               const Botan::bitvector bv1(100);




1✔





393



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




1✔





394



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




1✔





395



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




1✔





396



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




1✔





397



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




1✔





398



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




2✔





399



            }),




2✔





400












401



      CHECK("byte-aligned copy",










402



            [&](auto& result) {




1✔





403



               Botan::bitvector bv1(100);




1✔





404



               make_bitpattern(bv1);




1✔





405












406



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




1✔





407



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




1✔





408



               check_bitpattern(result, bv2, 16);




1✔





409












410



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




1✔





411



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




1✔





412



               check_bitpattern(result, bv3, 32);




1✔





413



            }),




3✔





414












415



      CHECK("byte-aligned 2",










416



            [&](auto& result) {




1✔





417



               Botan::bitvector bv1(100);




1✔





418



               make_bitpattern(bv1);




1✔





419












420



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




1✔





421



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




1✔





422



               check_bitpattern(result, bv2, 8);




1✔





423












424



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




1✔





425



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




1✔





426



               check_bitpattern(result, bv3, 16);




1✔





427












428



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




1✔





429



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




1✔





430



               check_bitpattern(result, bv4, 24);




1✔





431












432



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




1✔





433



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




1✔





434



               check_bitpattern(result, bv5, 32);




1✔





435












436



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




1✔





437



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




1✔





438



               check_bitpattern(result, bv6, 48);




1✔





439



            }),




6✔





440












441



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










442



            [&](auto& result) {




1✔





443



               Botan::bitvector bv1(100);




1✔





444



               make_bitpattern(bv1);




1✔





445












446



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




1✔





447



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




1✔





448



               check_bitpattern(result, bv2, 16);




1✔





449












450



               bv2.resize(32);




1✔





451



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




16✔





452



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




30✔





453



               }










454



            }),




2✔





455












456



      CHECK("unaligned copy",










457



            [&](auto& result) {




1✔





458



               Botan::bitvector bv1(100);




1✔





459



               make_bitpattern(bv1);




1✔





460












461



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




1✔





462



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




1✔





463



               check_bitpattern(result, bv2, 19);




1✔





464












465



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




1✔





466



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




1✔





467



               check_bitpattern(result, bv3, 21);




1✔





468












469



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




1✔





470



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




1✔





471



               check_bitpattern(result, bv4, 1);




1✔





472












473



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




1✔





474



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




1✔





475



               check_bitpattern(result, bv5, 1);




1✔





476












477



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




1✔





478



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




1✔





479



               check_bitpattern(result, bv6, 1 + 1);




1✔





480












481



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




1✔





482



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




1✔





483



               check_bitpattern(result, bv7, 17);




1✔





484












485



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




1✔





486



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




1✔





487



               check_bitpattern(result, bv8, 33);




1✔





488



            }),




8✔





489












490



      CHECK("byte-aligned unsigned integer subvector",










491



            [&](auto& result) {




1✔





492



               Botan::bitvector bv1(100);




1✔





493



               make_bitpattern(bv1);




1✔





494












495



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




1✔





496



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




1✔





497



               check_bitpattern(result, u8_0, 0);




1✔





498



               check_bitpattern(result, u8_32, 32);




1✔





499












500



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




1✔





501



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




1✔





502



               check_bitpattern(result, u16_0, 0);




1✔





503



               check_bitpattern(result, u16_56, 56);




1✔





504












505



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




1✔





506



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




1✔





507



               check_bitpattern(result, u32_0, 0);




1✔





508



               check_bitpattern(result, u32_48, 48);




1✔





509












510



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




1✔





511



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




1✔





512



               check_bitpattern(result, u64_0, 0);




1✔





513



               check_bitpattern(result, u64_32, 32);




1✔





514












515



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




3✔





516



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




3✔





517



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




3✔





518



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




4✔





519



            }),




1✔





520












521



      CHECK("unaligned unsigned integer subvector",










522



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




1✔





523



               Botan::bitvector bv1(100);




1✔





524



               make_bitpattern(bv1);




1✔





525












526



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




1✔





527



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




1✔





528



               check_bitpattern(result, u8_3, 3);




1✔





529



               check_bitpattern(result, u8_92, 92);




1✔





530












531



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




1✔





532



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




1✔





533



               check_bitpattern(result, u16_7, 7);




1✔





534



               check_bitpattern(result, u16_84, 84);




1✔





535












536



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




1✔





537



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




1✔





538



               check_bitpattern(result, u32_11, 11);




1✔





539



               check_bitpattern(result, u32_68, 68);




1✔





540












541



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




1✔





542



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




1✔





543



               check_bitpattern(result, u64_21, 21);




1✔





544



               check_bitpattern(result, u64_36, 36);




1✔





545



            }),




1✔





546












547



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










548



            [&](auto& result) {




1✔





549



               Botan::bitvector bv1(100);




1✔





550



               make_bitpattern(bv1);




1✔





551












552



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




1✔





553



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




1✔





554



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




2✔





555



               check_bitpattern(result, bv1);




1✔





556












557



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




1✔





558



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




1✔





559



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




2✔





560



               check_bitpattern(result, bv1);




1✔





561












562



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




1✔





563



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




1✔





564



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




2✔





565



               check_bitpattern(result, bv1);




1✔





566












567



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




1✔





568



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




1✔





569



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




2✔





570



               check_bitpattern(result, bv1);




1✔





571












572



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




1✔





573



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




1✔





574



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




2✔





575



               check_bitpattern(result, bv1);




1✔





576












577



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




3✔





578



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




3✔





579



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




3✔





580



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




4✔





581



            }),




1✔





582












583



      CHECK("unaligned unsigned integer subvector replacement",










584



            [&](auto& result) {




1✔





585



               Botan::bitvector bv1(100);




1✔





586



               make_bitpattern(bv1);




1✔





587












588



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




1✔





589



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




1✔





590



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




2✔





591



               check_bitpattern(result, bv1);




1✔





592












593



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




1✔





594



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




1✔





595



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




2✔





596



               check_bitpattern(result, bv1);




1✔





597












598



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




1✔





599



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




1✔





600



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




2✔





601



               check_bitpattern(result, bv1);




1✔





602












603



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




1✔





604



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




1✔





605



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




2✔





606



               check_bitpattern(result, bv1);




1✔





607












608



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




1✔





609



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




1✔





610



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




2✔





611



               check_bitpattern(result, bv1);




1✔





612












613



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




1✔





614



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




1✔





615



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




2✔





616



               check_bitpattern(result, bv1);




1✔





617












618



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




1✔





619



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




1✔





620



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




2✔





621



               check_bitpattern(result, bv1);




1✔





622



            }),




1✔





623



   };




11✔





624



}




1✔





625












626



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




1✔





627



   auto make_bitpattern = [](auto& bitvector) {




3✔





628



      auto next = pattern_generator<5>();




2✔





629



      for(auto& i : bitvector) {




400✔





630



         i = next();




198✔





631



      }










632



   };




2✔





633












634



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




2✔





635



      auto next = pattern_generator<5>();




1✔





636



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




100✔





637



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




198✔





638



      }










639



   };




1✔





640












641



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




2✔





642



      auto next = pattern_generator<5>();




1✔





643



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




100✔





644



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




198✔





645



      }










646



   };




1✔





647












648



   return {




1✔





649



      CHECK("one bit",










650



            [](auto& result) {




1✔





651



               Botan::bitvector bv;




1✔





652



               bv.push_back(true);




1✔





653












654



               bv.flip();




1✔





655



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




2✔





656












657



               // check that unused bits aren't flipped










658



               bv.resize(8);




1✔





659



               for(auto&& b : bv) {




9✔





660



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




16✔





661



               }










662



               bv.resize(1);




1✔





663












664



               bv.flip();




1✔





665



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




2✔





666



            }),




1✔





667












668



      CHECK("bits in many blocks",










669



            [&](auto& result) {




1✔





670



               Botan::bitvector bv(99);




1✔





671












672



               make_bitpattern(bv);




1✔





673



               bv.flip();




1✔





674



               check_flipped_bitpattern(result, bv);




1✔





675












676



               bv = ~bv;




2✔





677



               check_bitpattern(result, bv);




1✔





678












679



               bv.resize(112);




1✔





680



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




14✔





681



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




26✔





682



               }










683



            }),




1✔





684












685



      CHECK("set and unset",










686



            [&](auto& result) {




1✔





687



               Botan::bitvector bv(99);




1✔





688












689



               make_bitpattern(bv);




1✔





690



               bv.set();




1✔





691



               bv.resize(128);




1✔





692



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




129✔





693



                  const bool expected = (i < 99);




128✔





694



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




256✔





695



               }










696












697



               bv.unset();




1✔





698



               for(auto&& b : bv) {




130✔





699



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




256✔





700



               }










701



            }),




1✔





702












703



      CHECK("any, none and all",










704



            [&](auto& result) {




1✔





705



               Botan::bitvector bv(99);




1✔





706












707



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




2✔





708



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




2✔





709



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




2✔





710



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




2✔





711



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




2✔





712



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




2✔





713












714



               bv.set(42);




1✔





715



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




2✔





716



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




2✔





717



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




2✔





718



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




2✔





719



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




2✔





720



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




2✔





721












722



               bv.set();




1✔





723



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




2✔





724



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




2✔





725



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




2✔





726



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




2✔





727



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




2✔





728



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




2✔





729












730



               bv.unset(97);




1✔





731



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




2✔





732



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




2✔





733



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




2✔





734



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




2✔





735



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




2✔





736



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




2✔





737












738



               bv.unset();




1✔





739



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




2✔





740



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




2✔





741



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




2✔





742



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




2✔





743



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




2✔





744



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




2✔





745



            }),




1✔





746












747



      CHECK("hamming weight oddness",










748



            [](auto& result) {




1✔





749



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




1✔





750



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




1✔





751












752



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




3✔





753



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




3✔





754



            }),




2✔





755












756



      CHECK("hamming weight",










757



            [](auto& result) {




1✔





758



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




5✔





759



                  size_t weight = 0;




5✔





760



                  for(const auto& bit : v) {




440✔





761



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




430✔





762



                  }










763



                  return weight;




5✔





764



               };










765












766



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










767



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




2✔





768



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




1✔





769



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




2✔





770












771



               bv.pop_back();




1✔





772



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




1✔





773



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




2✔





774












775



               bv.pop_back();




1✔





776



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




1✔





777



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




2✔





778












779



               bv.pop_back();




1✔





780



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




1✔





781



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




2✔





782












783



               bv.pop_back();




1✔





784



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




1✔





785



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




2✔





786



            }),




1✔





787



   };




7✔





788



}




1✔





789












790



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




1✔





791



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




13✔





792



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




252✔





793



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




240✔





794



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




661✔





795



      }










796



   };




12✔





797












798



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




7✔





799



                                                                          const Botan::bitvector_base<AllocatorT>&) {










800



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




12✔





801



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










802



   };




6✔





803












804



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




4✔





805



                                                                            const Botan::bitvector_base<AllocatorT>&) {










806



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




6✔





807



   };




3✔





808












809



   return {




1✔





810



      CHECK("bitwise_equals",










811



            [&](auto& result) {




1✔





812



               Botan::bitvector lhs(20);




1✔





813



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




1✔





814



               Botan::bitvector rhs(20);




1✔





815



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




1✔





816












817



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




1✔





818



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




2✔





819












820



               lhs.unset().set(13);




1✔





821



               rhs.unset().set(13);




1✔





822












823



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




1✔





824



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




2✔





825



            }),




2✔





826












827



      CHECK("bitwise OR",










828



            [&](auto& result) {




1✔





829



               Botan::bitvector lhs(20);




1✔





830



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




1✔





831



               Botan::bitvector rhs(20);




1✔





832



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




1✔





833



               Botan::bitvector unary(20);




1✔





834



               unary.set(8);




1✔





835












836



               Botan::bitvector res = lhs | rhs;




1✔





837



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




4✔





838












839



               res |= unary;




1✔





840



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




3✔





841












842



               is_standard_allocator(result, res);




1✔





843



            }),




4✔





844












845



      CHECK("bitwise AND",










846



            [&](auto& result) {




1✔





847



               Botan::bitvector lhs(20);




1✔





848



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




1✔





849



               Botan::bitvector rhs(20);




1✔





850



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




1✔





851



               Botan::bitvector unary(20);




1✔





852



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




1✔





853












854



               Botan::bitvector res = lhs & rhs;




1✔





855



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




4✔





856












857



               res &= unary;




1✔





858



               check_set(result, res, {16});




3✔





859












860



               is_standard_allocator(result, res);




1✔





861



            }),




4✔





862












863



      CHECK("bitwise XOR",










864



            [&](auto& result) {




1✔





865



               Botan::bitvector lhs(20);




1✔





866



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




1✔





867



               Botan::bitvector rhs(20);




1✔





868



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




1✔





869



               Botan::bitvector unary(20);




1✔





870



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




1✔





871












872



               Botan::bitvector res = lhs ^ rhs;




1✔





873



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




4✔





874












875



               res ^= unary;




1✔





876



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




3✔





877












878



               is_standard_allocator(result, res);




1✔





879



            }),




4✔





880












881



      CHECK("bitwise operators with heterogeneous allocators",










882



            [&](auto& result) {




1✔





883



               Botan::bitvector lhs(20);




1✔





884



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




1✔





885



               Botan::secure_bitvector rhs(20);




1✔





886



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




1✔





887



               Botan::bitvector unary(20);




1✔





888



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




1✔





889












890



               auto res1 = lhs | rhs;




1✔





891



               is_secure_allocator(result, res1);




1✔





892



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




3✔





893












894



               auto res2 = rhs | lhs;




1✔





895



               is_secure_allocator(result, res2);




1✔





896



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




3✔





897












898



               auto res3 = lhs & rhs;




1✔





899



               is_secure_allocator(result, res3);




1✔





900



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




3✔





901












902



               auto res4 = rhs & lhs;




1✔





903



               is_secure_allocator(result, res4);




1✔





904



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




3✔





905












906



               auto res5 = lhs ^ rhs;




1✔





907



               is_secure_allocator(result, res5);




1✔





908



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




3✔





909












910



               auto res6 = rhs ^ lhs;




1✔





911



               is_secure_allocator(result, res6);




1✔





912



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




4✔





913



            }),




8✔





914



   };




6✔





915



}




1✔





916












917



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




1✔





918



   constexpr uint8_t outlen = 64;




1✔





919



   const auto bytearray = [] {




1✔





920



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










921



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










922



         out[i] = i;










923



      }










924



      return out;










925



   }();










926












927



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




3✔





928



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




129✔





929



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




127✔





930



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




127✔





931



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




127✔





932



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




127✔





933












934



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




254✔





935



      }










936



   };




2✔





937












938



   return {




1✔





939



      CHECK("empty byte-array",










940



            [](auto& result) {




1✔





941



               std::vector<uint8_t> bytes;




1✔





942



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




2✔





943












944



               const Botan::bitvector bv(bytes);




1✔





945



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




2✔





946












947



               auto rendered = bv.to_bytes();




1✔





948



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




2✔





949



            }),




1✔





950












951



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










952



            [](auto& result) {




1✔





953



               const Botan::bitvector bv;




1✔





954



               const Botan::secure_bitvector sbv;




1✔





955












956



               auto rbv = bv.to_bytes();




1✔





957



               auto rsbv = sbv.to_bytes();




1✔





958












959



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




2✔





960



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










961



               result.confirm("secure bitvector uses secure_vector",




2✔





962



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










963



            }),




1✔





964












965



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










966



            [&](auto& result) {




1✔





967



               const Botan::bitvector bv(bytearray);




1✔





968



               validate_bytewise(result, bv, bytearray);




1✔





969












970



               const auto rbv = bv.to_bytes();




1✔





971



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




3✔





972



            }),




2✔





973












974



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










975



            [&](auto& result) {




1✔





976



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




1✔





977



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




1✔





978












979



               const Botan::bitvector bv(unaligned_bytearray);




1✔





980



               validate_bytewise(result, bv, unaligned_bytearray);




1✔





981












982



               const auto rbv = bv.to_bytes();




1✔





983



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




2✔





984



            }),




3✔





985












986



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










987



            [&](auto& result) {




1✔





988



               constexpr size_t bits_to_load = 31;




1✔





989



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




1✔





990












991



               Botan::bitvector bv(bytearray, bits_to_load);




1✔





992












993



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




32✔





994



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




31✔





995



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




62✔





996



               }










997












998



               const auto rbv = bv.to_bytes();




1✔





999



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




1✔





1000



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




1✔





1001



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




1✔





1002



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




2✔





1003



            }),




2✔





1004












1005



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










1006



            [&](auto& result) {




1✔





1007



               constexpr size_t bits_to_load = 33;




1✔





1008



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




1✔





1009












1010



               Botan::bitvector bv(bytearray, bits_to_load);




1✔





1011



               bv.set(32);




1✔





1012












1013



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




1✔





1014



               bv.to_bytes(out);




1✔





1015












1016



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




2✔





1017



            }),




1✔





1018



   };




7✔





1019



}




1✔





1020












1021



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




1✔





1022



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




1✔





1023



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




1✔





1024












1025



   return {




1✔





1026



      CHECK("conditional XOR, block aligned",










1027



            [&](auto& result) {




1✔





1028



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




2✔





1029



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




2✔





1030



               const auto initial_bv1 = bv1;




1✔





1031



               const auto xor_result = bv1 ^ bv2;




1✔





1032












1033



               bv1.ct_conditional_xor(no, bv2);




1✔





1034



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




2✔





1035












1036



               bv1.ct_conditional_xor(yes, bv2);




1✔





1037



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




2✔





1038



            }),




4✔





1039












1040



      CHECK("conditional XOR, byte aligned",










1041



            [&](auto& result) {




1✔





1042



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




2✔





1043



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




2✔





1044



               const auto initial_bv1 = bv1;




1✔





1045



               const auto xor_result = bv1 ^ bv2;




1✔





1046












1047



               bv1.ct_conditional_xor(no, bv2);




1✔





1048



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




2✔





1049












1050



               bv1.ct_conditional_xor(yes, bv2);




1✔





1051



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




2✔





1052



            }),




4✔





1053












1054



      CHECK("conditional XOR, no alignment",










1055



            [&](auto& result) {




1✔





1056



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




1✔





1057



               bv1.push_back(true);




1✔





1058



               bv1.push_back(false);




1✔





1059



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




1✔





1060



               bv2.push_back(false);




1✔





1061



               bv2.push_back(false);




1✔





1062












1063



               const auto initial_bv1 = bv1;




1✔





1064



               const auto xor_result = bv1 ^ bv2;




1✔





1065












1066



               bv1.ct_conditional_xor(no, bv2);




1✔





1067



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




2✔





1068












1069



               bv1.ct_conditional_xor(yes, bv2);




1✔





1070



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




2✔





1071



            }),




4✔





1072



   };




4✔





1073



}




1✔





1074












1075



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




1✔





1076



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




1✔





1077












1078



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




1✔





1079












1080



   const size_t matrix_rows = 1664;




1✔





1081



   const size_t matrix_columns = 8192;




1✔





1082












1083



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




1✔





1084



   bitvec_vec.reserve(matrix_rows);




1✔





1085



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




1,665✔





1086



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




4,992✔





1087



   }










1088












1089



   // Simulate #ops of Gaussian Elimination










1090



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




1✔





1091



   const auto start = Test::timestamp();




1✔





1092



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




4,152,513✔





1093



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




4,152,512✔





1094



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




4,152,512✔





1095



   }










1096



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




1✔





1097












1098



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




3✔





1099



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




1✔





1100



   return {res};




3✔





1101



}




3✔





1102












1103



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




1✔





1104



   return {




1✔





1105



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










1106



            [](auto& result) {




1✔





1107



               Botan::bitvector bv(6);




1✔





1108



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




1✔





1109












1110



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




8✔





1111



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




6✔





1112



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




6✔





1113



                  ++i;




6✔





1114



               }










1115












1116



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




8✔





1117



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




6✔





1118



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




6✔





1119



                  ++i;




6✔





1120



               }










1121












1122



               for(auto ref : bv) {




14✔





1123



                  ref = true;




6✔





1124



               }










1125












1126



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




2✔





1127



            }),




1✔





1128












1129



      CHECK("Iterators: bare usage",










1130



            [](auto& result) {




1✔





1131



               Botan::bitvector bv(6);




1✔





1132



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




1✔





1133












1134



               size_t i = 0;




1✔





1135



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




7✔





1136



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




6✔





1137



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




12✔





1138



               }










1139












1140



               i = 0;




1✔





1141



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




7✔





1142



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




6✔





1143



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




12✔





1144



               }










1145












1146



               i = 6;




1✔





1147



               auto ritr = bv.end();




1✔





1148



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










1149



               do {










1150



                  --ritr;




6✔





1151



                  --i;




6✔





1152



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




6✔





1153



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




6✔





1154



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




11✔





1155












1156



               for(auto& itr : bv) {




8✔





1157



                  itr.flip();




6✔





1158



               }










1159












1160



               i = 0;




1✔





1161



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




7✔





1162



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




6✔





1163



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




12✔





1164



               }










1165



            }),




1✔





1166












1167



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










1168



            [](auto& result) {




1✔





1169



               Botan::bitvector bv(6);




1✔





1170



               using signed_size_t = std::make_signed_t<size_t>;










1171












1172



               result.test_is_eq("distance", std::distance(bv.begin(), bv.end()), signed_size_t(6));




2✔





1173



               result.test_is_eq("const distance", std::distance(bv.cbegin(), bv.cend()), signed_size_t(6));




3✔





1174












1175



               auto b = bv.begin();




1✔





1176



               std::advance(b, 3);




1✔





1177



               result.test_is_eq("half distance", std::distance(bv.begin(), b), signed_size_t(3));




3✔





1178



            }),




1✔





1179












1180



      CHECK("Iterators: large bitvector",










1181



            [](auto& result) {




1✔





1182



               Botan::bitvector bv(500);




1✔





1183












1184



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




1,001✔





1185



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




1,000✔





1186



                     itr->set();




250✔





1187



                  }










1188



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




1,000✔





1189



                     *itr = true;




167✔





1190



                  }










1191



               }










1192












1193



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




502✔





1194



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




500✔





1195



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




500✔





1196



                  ++i;




500✔





1197



               }










1198



            }),




1✔





1199












1200



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










1201



            [](auto& result) {




1✔





1202



               Botan::secure_bitvector bv(42);




1✔





1203



               auto ro_itr = bv.cbegin();




1✔





1204



               auto rw_itr = bv.begin();




1✔





1205












1206



               using ro = decltype(ro_itr);










1207



               using rw = decltype(rw_itr);










1208












1209



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




2✔





1210



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




2✔





1211



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




2✔





1212



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




2✔





1213



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




2✔





1214



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




2✔





1215



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




2✔





1216



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




2✔





1217



            }),




1✔





1218



   };




6✔





1219



}




1✔





1220












1221



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










1222



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










1223



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










1224












1225



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




1✔





1226



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




1✔





1227












1228



   TestBitvector bv1(33);




1✔





1229












1230



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




2✔





1231



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




1✔





1232












1233



   bv1[0] = true;




1✔





1234



   bv1.at(1) = true;




1✔





1235



   bv1.set(2);




2✔





1236



   bv1.unset(3);




2✔





1237



   bv1.flip(4);




2✔





1238



   bv1.push_back(true);




1✔





1239



   bv1.push_back(false);




1✔





1240



   bv1.pop_back();




1✔





1241












1242



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




2✔





1243



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




2✔





1244



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




2✔





1245



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




2✔





1246



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




2✔





1247












1248



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




2✔





1249












1250



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




36✔





1251



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




34✔





1252



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




68✔





1253



      ++i;




34✔





1254



   }










1255












1256



   bv1.flip();




2✔





1257












1258



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




36✔





1259



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




34✔





1260



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




68✔





1261



      ++i;




34✔





1262



   }










1263












1264



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




1✔





1265












1266



   auto bv3 = bv1 | bv2;




1✔





1267



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




2✔





1268












1269



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




1✔





1270



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




2✔





1271












1272



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




1✔





1273



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




2✔





1274



   result.test_is_eq<TestUInt32::wrapped_type>("bv5 has expected value", bv5.get(), 0xFFFFFFF4);




1✔





1275












1276



   const auto str = bv4.to_string();




1✔





1277



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




2✔





1278












1279



   return {result};




3✔





1280



}




6✔





1281












1282



}  // namespace










1283












1284



class BitVector_Tests final : public Test {




1✔





1285



   public:










1286



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




1✔





1287



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




1✔





1288



         auto& rng = Test::rng();




1✔





1289












1290



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




1✔





1291



            test_bitvector_bitwise_accessors,










1292



            test_bitvector_capacity,










1293



            test_bitvector_subvector,










1294



            test_bitvector_global_modifiers_and_predicates,










1295



            test_bitvector_binary_operators,










1296



            test_bitvector_serialization,










1297



            test_bitvector_constant_time_operations,










1298



            test_bitvector_conditional_xor_workload,










1299



            test_bitvector_iterators,










1300



            test_bitvector_strongtype_adapter,










1301



         };




11✔





1302












1303



         for(const auto& test_func : funcs) {




11✔





1304



            auto fn_results = test_func(rng);




10✔





1305



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




10✔





1306



         }




10✔





1307












1308



         return results;




1✔





1309



      }




2✔





1310



};










1311












1312



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










1313












1314



#endif










1315












1316



}  // namespace Botan_Tests
























    

  • 

    •