randombit / botan / 17159911587

coverage: 90.656% (-0.006%) from 90.662%
17159911587

push

github

Brassinolide 
fix clang-tidy & clang-format & macOS test failed

100250 of 110583 relevant lines covered (90.66%)

12199136.65 hits per line

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

99.67
/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/internal/bitvector.h>










12



   #include <botan/internal/fmt.h>










13



   #include <algorithm>










14



   #include <numeric>










15



#endif










16












17



namespace Botan_Tests {










18












19



#if defined(BOTAN_HAS_BITVECTOR)










20












21



namespace {










22












23



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










24



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




96✔





25



   if(min == max) {




96✔





26



      return min;










27



   }










28












29



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




96✔





30



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




96✔





31



}










32












33



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










34



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




3✔





35



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




6✔





36



      // Fisher-Yates shuffle










37



      if(v.size() < 2) {




3✔





38



         return;










39



      }










40



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




93✔





41



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




90✔





42



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




90✔





43



      }










44



   };




3✔





45












46



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




3✔





47



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




3✔





48



   shuffle(indices);




3✔





49



   indices.resize(n);




3✔





50



   return indices;




3✔





51



}




×







52












53



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










54



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




3✔





55



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




3✔





56



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




3✔





57



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




3✔





58












59



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




6✔





60



}




6✔





61












62



template <size_t mod>










63



auto pattern_generator(size_t offset = 0) {




79✔





64



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




5,209✔





65



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




5,209✔





66



      ++i;




5,209✔





67



      return result;










68



   };










69



}










70












71



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




1✔





72



   return {




1✔





73



      CHECK("default constructed bitvector",










74



            [](auto& result) {




1✔





75



               Botan::bitvector bv;




1✔





76



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




2✔





77



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




2✔





78



            }),




1✔





79












80



      CHECK("preallocated construction of bitvector",










81



            [](auto& result) {




1✔





82



               Botan::bitvector bv(10);




1✔





83



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




2✔





84



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




1✔





85



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




11✔





86



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




20✔





87



               }










88



            }),




1✔





89












90



      CHECK("setting bits",










91



            [&](auto& result) {




1✔





92



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




1✔





93












94



               for(size_t i : ones) {




2✔





95



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




1✔





96



                     bv.set(i);




×







97



                  } else {










98



                     bv.at(i) = true;




1✔





99



                  }










100



               }










101



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




47✔





102



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




138✔





103



               }










104



            }),




1✔





105












106



      CHECK("unsetting bits",










107



            [&](auto& result) {




1✔





108



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




1✔





109



               for(auto b : bv) {




23✔





110



                  b.set();




21✔





111



               }










112












113



               for(size_t i : zeros) {




13✔





114



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




12✔





115



                     bv.unset(i);




5✔





116



                  } else {










117



                     bv.at(i) = false;




7✔





118



                  }










119



               }










120



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




22✔





121



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




63✔





122



               }










123



            }),




1✔





124












125



      CHECK("flipping bits",










126



            [&](auto& result) {




1✔





127



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




1✔





128












129



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




27✔





130



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




52✔





131



                     bv.set(i);




26✔





132



                  }










133



                  bv.flip(i);




26✔





134



               }










135



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




27✔





136



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




78✔





137



               }










138



            }),




1✔





139












140



      CHECK("accessors validate offsets",










141



            [](auto& result) {




1✔





142



               Botan::bitvector bv(10);




1✔





143



               result.template test_throws<Botan::Invalid_Argument>(




2✔





144



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




2✔





145



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




3✔





146



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




3✔





147



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




3✔





148



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




4✔





149



            }),




1✔





150












151



      CHECK("multiblock handling",










152



            [](auto& result) {




1✔





153



               Botan::bitvector bv(128);




1✔





154



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




2✔





155



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




1✔





156



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




129✔





157



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




128✔





158



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




256✔





159



               }










160



            }),




1✔





161












162



      CHECK("subscript operator",










163



            [](auto& result) {




1✔





164



               Botan::bitvector bv(128);




1✔





165



               bv[0].set();




1✔





166



               bv[1] = true;




1✔





167



               bv[2].flip();




1✔





168



               bv[64] = true;




1✔





169



               bv[80] = true;




1✔





170



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




2✔





171



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




2✔





172



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




2✔





173



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




2✔





174



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




2✔





175



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




2✔





176



            }),




1✔





177












178



      CHECK("subscript operator does not validate offsets",










179



            [](auto& result) {




1✔





180



               Botan::bitvector bv(10);




1✔





181



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




3✔





182



               // Technically the next line is undefined behaviour.










183



               // Though, the current implementation detail won't










184



               // cause issues, which might change!










185



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




3✔





186



            }),




1✔





187












188



      CHECK("bitwise assignment modifiers",










189



            [](auto& result) {




1✔





190



               Botan::bitvector bv(4);




1✔





191












192



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




2✔





193



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




1✔





194



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




2✔





195



               bv[0].set();




1✔





196



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




1✔





197



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




2✔





198



               bv[0] &= false;




1✔





199



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




2✔





200



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




1✔





201



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




2✔





202












203



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




2✔





204



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




1✔





205



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




2✔





206



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




1✔





207



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




2✔





208



               bv[1].unset();




1✔





209



               bv[1] |= false;




1✔





210



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




2✔





211



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




1✔





212



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




2✔





213












214



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




2✔





215



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




1✔





216



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




2✔





217



               bv[2] ^= true;




1✔





218



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




2✔





219



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




1✔





220



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




2✔





221



            }),




1✔





222



   };




11✔





223



}




1✔





224












225



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




1✔





226



   return {




1✔





227



      CHECK("default constructed bitvector",










228



            [](auto& result) {




1✔





229



               Botan::bitvector bv;




1✔





230



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




2✔





231



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




2✔





232



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




3✔





233



            }),




1✔





234












235



      CHECK("allocated bitvector has capacity",










236



            [](auto& result) {




1✔





237



               Botan::bitvector bv(1);




1✔





238



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




2✔





239



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




2✔





240



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




2✔





241



            }),




1✔





242












243



      CHECK("reserved bitvector has capacity",










244



            [](auto& result) {




1✔





245



               Botan::bitvector bv;




1✔





246



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




2✔





247



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




2✔





248












249



               bv.reserve(64);




1✔





250



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




2✔





251



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




2✔





252












253



               bv.reserve(128);




1✔





254



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




2✔





255



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




2✔





256



            }),




1✔





257












258



      CHECK("push_back() extends bitvector",










259



            [](Test::Result& result) {




1✔





260



               Botan::bitvector bv;




1✔





261



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




2✔





262



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




1✔





263












264



               bv.push_back(true);




1✔





265



               bv.push_back(false);




1✔





266



               bv.push_back(true);




1✔





267



               bv.push_back(false);




1✔





268












269



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




2✔





270



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




1✔





271



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




1✔





272












273



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




2✔





274



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




2✔





275



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




2✔





276



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




2✔





277












278



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




4✔





279



            }),




1✔





280












281



      CHECK("pop_back() shortens bitvector",










282



            [](Test::Result& result) {




1✔





283



               Botan::bitvector bv;




1✔





284



               bv.push_back(true);




1✔





285



               bv.push_back(false);




1✔





286



               bv.push_back(true);




1✔





287



               bv.push_back(false);




1✔





288



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




2✔





289












290



               bv.pop_back();




1✔





291



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




1✔





292



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




2✔





293












294



               bv.pop_back();




1✔





295



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




1✔





296



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




2✔





297












298



               bv.pop_back();




1✔





299



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




1✔





300



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




2✔





301



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




2✔





302












303



               bv.pop_back();




1✔





304



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




2✔





305












306



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




4✔





307



            }),




1✔





308












309



      CHECK("resize()",










310



            [](auto& result) {




1✔





311



               Botan::bitvector bv(10);




1✔





312



               bv[0] = true;




1✔





313



               bv[5] = true;




1✔





314



               bv[9] = true;




1✔





315












316



               bv.resize(8);




1✔





317



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




1✔





318












319



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




9✔





320



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




8✔





321



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




16✔





322



               }










323












324



               bv.resize(0);




1✔





325



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




2✔





326












327



               bv.resize(8);




1✔





328



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




2✔





329



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




2✔





330



            }),




1✔





331



   };




7✔





332



}




1✔





333












334



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




1✔





335



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




21✔





336



      auto next = pattern_generator<3>(pattern_offset);




20✔





337












338



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










339



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




316✔





340



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




304✔





341



         }










342



      } else {










343



         for(auto& i : bitvector) {




1,616✔





344



            i = next();




800✔





345



         }










346



      }










347



   };




8✔





348












349



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




13✔





350



      T bitvector = 0;




12✔





351



      make_bitpattern(bitvector, pattern_offset);




24✔





352



      return bitvector;










353



   };




1✔





354












355



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




44✔





356



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










357



      auto next = pattern_generator<3>(offset);




43✔





358












359



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










360



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




496✔





361



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




960✔





362



         }










363



      } else {










364



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




2,056✔





365



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




4,058✔





366



         }










367



      }










368



   };




43✔





369












370



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




13✔





371



      auto next = pattern_generator<3>();




12✔





372



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




1,212✔





373



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




1,200✔





374



         const bool expected = next();




1,200✔





375



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




2,400✔





376



      }










377



   };




12✔





378












379



   return {




1✔





380



      CHECK("range errors are caught",










381



            [&](auto& result) {




1✔





382



               Botan::bitvector bv(100);




1✔





383



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




3✔





384



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




3✔





385



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




3✔





386



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




4✔





387



            }),




1✔





388












389



      CHECK("empty copy is allowed",










390



            [&](auto& result) {




1✔





391



               Botan::bitvector bv1(100);




1✔





392



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




1✔





393



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




1✔





394



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




1✔





395



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




1✔





396



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




1✔





397



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




2✔





398



            }),




2✔





399












400



      CHECK("byte-aligned copy",










401



            [&](auto& result) {




1✔





402



               Botan::bitvector bv1(100);




1✔





403



               make_bitpattern(bv1);




1✔





404












405



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




1✔





406



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




1✔





407



               check_bitpattern(result, bv2, 16);




1✔





408












409



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




1✔





410



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




1✔





411



               check_bitpattern(result, bv3, 32);




1✔





412



            }),




3✔





413












414



      CHECK("byte-aligned 2",










415



            [&](auto& result) {




1✔





416



               Botan::bitvector bv1(100);




1✔





417



               make_bitpattern(bv1);




1✔





418












419



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




1✔





420



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




1✔





421



               check_bitpattern(result, bv2, 8);




1✔





422












423



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




1✔





424



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




1✔





425



               check_bitpattern(result, bv3, 16);




1✔





426












427



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




1✔





428



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




1✔





429



               check_bitpattern(result, bv4, 24);




1✔





430












431



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




1✔





432



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




1✔





433



               check_bitpattern(result, bv5, 32);




1✔





434












435



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




1✔





436



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




1✔





437



               check_bitpattern(result, bv6, 48);




1✔





438



            }),




6✔





439












440



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










441



            [&](auto& result) {




1✔





442



               Botan::bitvector bv1(100);




1✔





443



               make_bitpattern(bv1);




1✔





444












445



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




1✔





446



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




1✔





447



               check_bitpattern(result, bv2, 16);




1✔





448












449



               bv2.resize(32);




1✔





450



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




16✔





451



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




30✔





452



               }










453



            }),




2✔





454












455



      CHECK("unaligned copy",










456



            [&](auto& result) {




1✔





457



               Botan::bitvector bv1(100);




1✔





458



               make_bitpattern(bv1);




1✔





459












460



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




1✔





461



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




1✔





462



               check_bitpattern(result, bv2, 19);




1✔





463












464



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




1✔





465



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




1✔





466



               check_bitpattern(result, bv3, 21);




1✔





467












468



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




1✔





469



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




1✔





470



               check_bitpattern(result, bv4, 1);




1✔





471












472



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




1✔





473



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




1✔





474



               check_bitpattern(result, bv5, 1);




1✔





475












476



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




1✔





477



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




1✔





478



               check_bitpattern(result, bv6, 1 + 1);




1✔





479












480



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




1✔





481



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




1✔





482



               check_bitpattern(result, bv7, 17);




1✔





483












484



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




1✔





485



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




1✔





486



               check_bitpattern(result, bv8, 33);




1✔





487



            }),




8✔





488












489



      CHECK("byte-aligned unsigned integer subvector",










490



            [&](auto& result) {




1✔





491



               Botan::bitvector bv1(100);




1✔





492



               make_bitpattern(bv1);




1✔





493












494



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




1✔





495



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




1✔





496



               check_bitpattern(result, u8_0, 0);




1✔





497



               check_bitpattern(result, u8_32, 32);




1✔





498












499



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




1✔





500



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




1✔





501



               check_bitpattern(result, u16_0, 0);




1✔





502



               check_bitpattern(result, u16_56, 56);




1✔





503












504



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




1✔





505



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




1✔





506



               check_bitpattern(result, u32_0, 0);




1✔





507



               check_bitpattern(result, u32_48, 48);




1✔





508












509



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




1✔





510



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




1✔





511



               check_bitpattern(result, u64_0, 0);




1✔





512



               check_bitpattern(result, u64_32, 32);




1✔





513












514



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




3✔





515



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




3✔





516



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




3✔





517



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




4✔





518



            }),




1✔





519












520



      CHECK("unaligned unsigned integer subvector",










521



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




1✔





522



               Botan::bitvector bv1(100);




1✔





523



               make_bitpattern(bv1);




1✔





524












525



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




1✔





526



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




1✔





527



               check_bitpattern(result, u8_3, 3);




1✔





528



               check_bitpattern(result, u8_92, 92);




1✔





529












530



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




1✔





531



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




1✔





532



               check_bitpattern(result, u16_7, 7);




1✔





533



               check_bitpattern(result, u16_84, 84);




1✔





534












535



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




1✔





536



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




1✔





537



               check_bitpattern(result, u32_11, 11);




1✔





538



               check_bitpattern(result, u32_68, 68);




1✔





539












540



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




1✔





541



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




1✔





542



               check_bitpattern(result, u64_21, 21);




1✔





543



               check_bitpattern(result, u64_36, 36);




1✔





544



            }),




1✔





545












546



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










547



            [&](auto& result) {




1✔





548



               Botan::bitvector bv1(100);




1✔





549



               make_bitpattern(bv1);




1✔





550












551



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




1✔





552



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




1✔





553



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




2✔





554



               check_bitpattern(result, bv1);




1✔





555












556



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




1✔





557



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




1✔





558



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




2✔





559



               check_bitpattern(result, bv1);




1✔





560












561



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




1✔





562



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




1✔





563



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




2✔





564



               check_bitpattern(result, bv1);




1✔





565












566



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




1✔





567



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




1✔





568



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




2✔





569



               check_bitpattern(result, bv1);




1✔





570












571



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




1✔





572



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




1✔





573



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




2✔





574



               check_bitpattern(result, bv1);




1✔





575












576



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




3✔





577



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




3✔





578



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




3✔





579



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




4✔





580



            }),




1✔





581












582



      CHECK("unaligned unsigned integer subvector replacement",










583



            [&](auto& result) {




1✔





584



               Botan::bitvector bv1(100);




1✔





585



               make_bitpattern(bv1);




1✔





586












587



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




1✔





588



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




1✔





589



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




2✔





590



               check_bitpattern(result, bv1);




1✔





591












592



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




1✔





593



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




1✔





594



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




2✔





595



               check_bitpattern(result, bv1);




1✔





596












597



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




1✔





598



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




1✔





599



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




2✔





600



               check_bitpattern(result, bv1);




1✔





601












602



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




1✔





603



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




1✔





604



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




2✔





605



               check_bitpattern(result, bv1);




1✔





606












607



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




1✔





608



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




1✔





609



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




2✔





610



               check_bitpattern(result, bv1);




1✔





611












612



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




1✔





613



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




1✔





614



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




2✔





615



               check_bitpattern(result, bv1);




1✔





616












617



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




1✔





618



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




1✔





619



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




2✔





620



               check_bitpattern(result, bv1);




1✔





621



            }),




1✔





622



   };




11✔





623



}




1✔





624












625



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




1✔





626



   auto make_bitpattern = [](auto& bitvector) {




3✔





627



      auto next = pattern_generator<5>();




2✔





628



      for(auto& i : bitvector) {




400✔





629



         i = next();




198✔





630



      }










631



   };




2✔





632












633



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




2✔





634



      auto next = pattern_generator<5>();




1✔





635



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




100✔





636



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




198✔





637



      }










638



   };




1✔





639












640



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




2✔





641



      auto next = pattern_generator<5>();




1✔





642



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




100✔





643



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




198✔





644



      }










645



   };




1✔





646












647



   return {




1✔





648



      CHECK("one bit",










649



            [](auto& result) {




1✔





650



               Botan::bitvector bv;




1✔





651



               bv.push_back(true);




1✔





652












653



               bv.flip();




1✔





654



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




2✔





655












656



               // check that unused bits aren't flipped










657



               bv.resize(8);




1✔





658



               for(auto&& b : bv) {




9✔





659



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




16✔





660



               }










661



               bv.resize(1);




1✔





662












663



               bv.flip();




1✔





664



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




2✔





665



            }),




1✔





666












667



      CHECK("bits in many blocks",










668



            [&](auto& result) {




1✔





669



               Botan::bitvector bv(99);




1✔





670












671



               make_bitpattern(bv);




1✔





672



               bv.flip();




1✔





673



               check_flipped_bitpattern(result, bv);




1✔





674












675



               bv = ~bv;




2✔





676



               check_bitpattern(result, bv);




1✔





677












678



               bv.resize(112);




1✔





679



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




14✔





680



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




26✔





681



               }










682



            }),




1✔





683












684



      CHECK("set and unset",










685



            [&](auto& result) {




1✔





686



               Botan::bitvector bv(99);




1✔





687












688



               make_bitpattern(bv);




1✔





689



               bv.set();




1✔





690



               bv.resize(128);




1✔





691



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




129✔





692



                  const bool expected = (i < 99);




128✔





693



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




256✔





694



               }










695












696



               bv.unset();




1✔





697



               for(auto&& b : bv) {




130✔





698



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




256✔





699



               }










700



            }),




1✔





701












702



      CHECK("any, none and all",










703



            [&](auto& result) {




1✔





704



               Botan::bitvector bv(99);




1✔





705












706



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




2✔





707



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




2✔





708



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




2✔





709



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




2✔





710



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




2✔





711



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




2✔





712












713



               bv.set(42);




1✔





714



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




2✔





715



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




2✔





716



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




2✔





717



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




2✔





718



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




2✔





719



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




2✔





720












721



               bv.set();




1✔





722



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




2✔





723



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




2✔





724



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




2✔





725



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




2✔





726



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




2✔





727



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




2✔





728












729



               bv.unset(97);




1✔





730



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




2✔





731



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




2✔





732



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




2✔





733



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




2✔





734



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




2✔





735



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




2✔





736












737



               bv.unset();




1✔





738



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




2✔





739



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




2✔





740



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




2✔





741



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




2✔





742



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




2✔





743



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




2✔





744



            }),




1✔





745












746



      CHECK("hamming weight oddness",










747



            [](auto& result) {




1✔





748



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




1✔





749



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




1✔





750












751



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




3✔





752



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




3✔





753



            }),




2✔





754












755



      CHECK("hamming weight",










756



            [](auto& result) {




1✔





757



               auto naive_count = [](auto& v) {




5✔





758



                  size_t weight = 0;




5✔





759



                  for(const auto& bit : v) {




440✔





760



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




430✔





761



                  }










762



                  return weight;




5✔





763



               };










764












765



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










766



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




2✔





767



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




1✔





768



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




2✔





769












770



               bv.pop_back();




1✔





771



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




1✔





772



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




2✔





773












774



               bv.pop_back();




1✔





775



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




1✔





776



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




2✔





777












778



               bv.pop_back();




1✔





779



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




1✔





780



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




2✔





781












782



               bv.pop_back();




1✔





783



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




1✔





784



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




2✔





785



            }),




1✔





786



   };




7✔





787



}




1✔





788












789



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




1✔





790



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




13✔





791



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




252✔





792



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




240✔





793



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




661✔





794



      }










795



   };




12✔





796












797



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




7✔





798



                                                                          const Botan::bitvector_base<AllocatorT>&) {










799



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




12✔





800



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










801



   };




6✔





802












803



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




4✔





804



                                                                            const Botan::bitvector_base<AllocatorT>&) {










805



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




6✔





806



   };




3✔





807












808



   return {




1✔





809



      CHECK("bitwise_equals",










810



            [&](auto& result) {




1✔





811



               Botan::bitvector lhs(20);




1✔





812



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




1✔





813



               Botan::bitvector rhs(20);




1✔





814



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




1✔





815












816



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




1✔





817



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




2✔





818












819



               lhs.unset().set(13);




1✔





820



               rhs.unset().set(13);




1✔





821












822



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




1✔





823



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




2✔





824



            }),




2✔





825












826



      CHECK("bitwise OR",










827



            [&](auto& result) {




1✔





828



               Botan::bitvector lhs(20);




1✔





829



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




1✔





830



               Botan::bitvector rhs(20);




1✔





831



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




1✔





832



               Botan::bitvector unary(20);




1✔





833



               unary.set(8);




1✔





834












835



               Botan::bitvector res = lhs | rhs;




1✔





836



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




4✔





837












838



               res |= unary;




1✔





839



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




3✔





840












841



               is_standard_allocator(result, res);




1✔





842



            }),




4✔





843












844



      CHECK("bitwise AND",










845



            [&](auto& result) {




1✔





846



               Botan::bitvector lhs(20);




1✔





847



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




1✔





848



               Botan::bitvector rhs(20);




1✔





849



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




1✔





850



               Botan::bitvector unary(20);




1✔





851



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




1✔





852












853



               Botan::bitvector res = lhs & rhs;




1✔





854



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




4✔





855












856



               res &= unary;




1✔





857



               check_set(result, res, {16});




3✔





858












859



               is_standard_allocator(result, res);




1✔





860



            }),




4✔





861












862



      CHECK("bitwise XOR",










863



            [&](auto& result) {




1✔





864



               Botan::bitvector lhs(20);




1✔





865



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




1✔





866



               Botan::bitvector rhs(20);




1✔





867



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




1✔





868



               Botan::bitvector unary(20);




1✔





869



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




1✔





870












871



               Botan::bitvector res = lhs ^ rhs;




1✔





872



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




4✔





873












874



               res ^= unary;




1✔





875



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




3✔





876












877



               is_standard_allocator(result, res);




1✔





878



            }),




4✔





879












880



      CHECK("bitwise operators with heterogeneous allocators",










881



            [&](auto& result) {




1✔





882



               Botan::bitvector lhs(20);




1✔





883



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




1✔





884



               Botan::secure_bitvector rhs(20);




1✔





885



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




1✔





886



               Botan::bitvector unary(20);




1✔





887



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




1✔





888












889



               auto res1 = lhs | rhs;




1✔





890



               is_secure_allocator(result, res1);




1✔





891



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




3✔





892












893



               auto res2 = rhs | lhs;




1✔





894



               is_secure_allocator(result, res2);




1✔





895



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




3✔





896












897



               auto res3 = lhs & rhs;




1✔





898



               is_secure_allocator(result, res3);




1✔





899



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




3✔





900












901



               auto res4 = rhs & lhs;




1✔





902



               is_secure_allocator(result, res4);




1✔





903



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




3✔





904












905



               auto res5 = lhs ^ rhs;




1✔





906



               is_secure_allocator(result, res5);




1✔





907



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




3✔





908












909



               auto res6 = rhs ^ lhs;




1✔





910



               is_secure_allocator(result, res6);




1✔





911



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




4✔





912



            }),




8✔





913



   };




6✔





914



}




1✔





915












916



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




1✔





917



   constexpr uint8_t outlen = 64;




1✔





918



   const auto bytearray = [] {




1✔





919



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










920



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










921



         out[i] = i;










922



      }










923



      return out;










924



   }();










925












926



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




3✔





927



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




129✔





928



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




127✔





929



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




127✔





930



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




127✔





931



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




127✔





932












933



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




254✔





934



      }










935



   };




2✔





936












937



   return {




1✔





938



      CHECK("empty byte-array",










939



            [](auto& result) {




1✔





940



               std::vector<uint8_t> bytes;




1✔





941



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




2✔





942












943



               Botan::bitvector bv(bytes);




1✔





944



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




2✔





945












946



               auto rendered = bv.to_bytes();




1✔





947



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




2✔





948



            }),




1✔





949












950



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










951



            [](auto& result) {




1✔





952



               Botan::bitvector bv;




1✔





953



               Botan::secure_bitvector sbv;




1✔





954












955



               auto rbv = bv.to_bytes();




1✔





956



               auto rsbv = sbv.to_bytes();




1✔





957












958



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




2✔





959



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










960



               result.confirm("secure bitvector uses secure_vector",




2✔





961



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










962



            }),




1✔





963












964



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










965



            [&](auto& result) {




1✔





966



               Botan::bitvector bv(bytearray);




1✔





967



               validate_bytewise(result, bv, bytearray);




1✔





968












969



               const auto rbv = bv.to_bytes();




1✔





970



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




3✔





971



            }),




2✔





972












973



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










974



            [&](auto& result) {




1✔





975



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




1✔





976



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




1✔





977












978



               Botan::bitvector bv(unaligned_bytearray);




1✔





979



               validate_bytewise(result, bv, unaligned_bytearray);




1✔





980












981



               const auto rbv = bv.to_bytes();




1✔





982



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




2✔





983



            }),




3✔





984












985



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










986



            [&](auto& result) {




1✔





987



               constexpr size_t bits_to_load = 31;




1✔





988



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




1✔





989












990



               Botan::bitvector bv(bytearray, bits_to_load);




1✔





991












992



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




32✔





993



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




31✔





994



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




62✔





995



               }










996












997



               const auto rbv = bv.to_bytes();




1✔





998



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




1✔





999



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




1✔





1000



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




1✔





1001



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




2✔





1002



            }),




2✔





1003












1004



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










1005



            [&](auto& result) {




1✔





1006



               constexpr size_t bits_to_load = 33;




1✔





1007



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




1✔





1008












1009



               Botan::bitvector bv(bytearray, bits_to_load);




1✔





1010



               bv.set(32);




1✔





1011












1012



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




1✔





1013



               bv.to_bytes(out);




1✔





1014












1015



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




2✔





1016



            }),




1✔





1017



   };




7✔





1018



}




1✔





1019












1020



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




1✔





1021



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




1✔





1022



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




1✔





1023












1024



   return {




1✔





1025



      CHECK("conditional XOR, block aligned",










1026



            [&](auto& result) {




1✔





1027



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




2✔





1028



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




2✔





1029



               const auto initial_bv1 = bv1;




1✔





1030



               const auto xor_result = bv1 ^ bv2;




1✔





1031












1032



               bv1.ct_conditional_xor(no, bv2);




1✔





1033



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




2✔





1034












1035



               bv1.ct_conditional_xor(yes, bv2);




1✔





1036



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




2✔





1037



            }),




4✔





1038












1039



      CHECK("conditional XOR, byte aligned",










1040



            [&](auto& result) {




1✔





1041



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




2✔





1042



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




2✔





1043



               const auto initial_bv1 = bv1;




1✔





1044



               const auto xor_result = bv1 ^ bv2;




1✔





1045












1046



               bv1.ct_conditional_xor(no, bv2);




1✔





1047



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




2✔





1048












1049



               bv1.ct_conditional_xor(yes, bv2);




1✔





1050



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




2✔





1051



            }),




4✔





1052












1053



      CHECK("conditional XOR, no alignment",










1054



            [&](auto& result) {




1✔





1055



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




1✔





1056



               bv1.push_back(true);




1✔





1057



               bv1.push_back(false);




1✔





1058



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




1✔





1059



               bv2.push_back(false);




1✔





1060



               bv2.push_back(false);




1✔





1061












1062



               const auto initial_bv1 = bv1;




1✔





1063



               const auto xor_result = bv1 ^ bv2;




1✔





1064












1065



               bv1.ct_conditional_xor(no, bv2);




1✔





1066



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




2✔





1067












1068



               bv1.ct_conditional_xor(yes, bv2);




1✔





1069



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




2✔





1070



            }),




4✔





1071



   };




4✔





1072



}




1✔





1073












1074



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




1✔





1075



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




1✔





1076












1077



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




1✔





1078












1079



   const size_t matrix_rows = 1664;




1✔





1080



   const size_t matrix_columns = 8192;




1✔





1081












1082



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




1✔





1083



   bitvec_vec.reserve(matrix_rows);




1✔





1084



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




1,665✔





1085



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




4,992✔





1086



   }










1087












1088



   // Simulate #ops of Gaussian Elimination










1089



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




1✔





1090



   const auto start = Test::timestamp();




1✔





1091



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




4,152,513✔





1092



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




4,152,512✔





1093



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




4,152,512✔





1094



   }










1095



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




1✔





1096












1097



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




3✔





1098



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




1✔





1099



   return {res};




3✔





1100



}




3✔





1101












1102



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




1✔





1103



   return {




1✔





1104



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










1105



            [](auto& result) {




1✔





1106



               Botan::bitvector bv(6);




1✔





1107



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




1✔





1108












1109



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




8✔





1110



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




6✔





1111



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




6✔





1112



                  ++i;




6✔





1113



               }










1114












1115



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




8✔





1116



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




6✔





1117



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




6✔





1118



                  ++i;




6✔





1119



               }










1120












1121



               for(auto ref : bv) {




14✔





1122



                  ref = true;




6✔





1123



               }










1124












1125



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




2✔





1126



            }),




1✔





1127












1128



      CHECK("Iterators: bare usage",










1129



            [](auto& result) {




1✔





1130



               Botan::bitvector bv(6);




1✔





1131



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




1✔





1132












1133



               size_t i = 0;




1✔





1134



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




7✔





1135



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




6✔





1136



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




12✔





1137



               }










1138












1139



               i = 0;




1✔





1140



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




7✔





1141



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




6✔





1142



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




12✔





1143



               }










1144












1145



               i = 6;




1✔





1146



               auto ritr = bv.end();




1✔





1147



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










1148



               do {










1149



                  --ritr;




6✔





1150



                  --i;




6✔





1151



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




6✔





1152



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




6✔





1153



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




11✔





1154












1155



               for(auto& itr : bv) {




8✔





1156



                  itr.flip();




6✔





1157



               }










1158












1159



               i = 0;




1✔





1160



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




7✔





1161



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




6✔





1162



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




12✔





1163



               }










1164



            }),




1✔





1165












1166



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










1167



            [](auto& result) {




1✔





1168



               Botan::bitvector bv(6);




1✔





1169



               using signed_size_t = std::make_signed_t<size_t>;










1170












1171



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




2✔





1172



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




3✔





1173












1174



               auto b = bv.begin();




1✔





1175



               std::advance(b, 3);




1✔





1176



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




3✔





1177



            }),




1✔





1178












1179



      CHECK("Iterators: large bitvector",










1180



            [](auto& result) {




1✔





1181



               Botan::bitvector bv(500);




1✔





1182












1183



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




1,001✔





1184



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




1,000✔





1185



                     itr->set();




250✔





1186



                  }










1187



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




1,000✔





1188



                     *itr = true;




167✔





1189



                  }










1190



               }










1191












1192



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




502✔





1193



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




500✔





1194



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




500✔





1195



                  ++i;




500✔





1196



               }










1197



            }),




1✔





1198












1199



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










1200



            [](auto& result) {




1✔





1201



               Botan::secure_bitvector bv(42);




1✔





1202



               auto ro_itr = bv.cbegin();




1✔





1203



               auto rw_itr = bv.begin();




1✔





1204












1205



               using ro = decltype(ro_itr);










1206



               using rw = decltype(rw_itr);










1207












1208



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




2✔





1209



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




2✔





1210



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




2✔





1211



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




2✔





1212



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




2✔





1213



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




2✔





1214



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




2✔





1215



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




2✔





1216



            }),




1✔





1217



   };




6✔





1218



}




1✔





1219












1220



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










1221



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










1222



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










1223












1224



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




1✔





1225



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




1✔





1226












1227



   TestBitvector bv1(33);




1✔





1228












1229



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




2✔





1230



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




1✔





1231












1232



   bv1[0] = true;




1✔





1233



   bv1.at(1) = true;




1✔





1234



   bv1.set(2);




2✔





1235



   bv1.unset(3);




2✔





1236



   bv1.flip(4);




2✔





1237



   bv1.push_back(true);




1✔





1238



   bv1.push_back(false);




1✔





1239



   bv1.pop_back();




1✔





1240












1241



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




2✔





1242



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




2✔





1243



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




2✔





1244



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




2✔





1245



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




2✔





1246












1247



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




2✔





1248












1249



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




36✔





1250



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




34✔





1251



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




68✔





1252



      ++i;




34✔





1253



   }










1254












1255



   bv1.flip();




2✔





1256












1257



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




36✔





1258



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




34✔





1259



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




68✔





1260



      ++i;




34✔





1261



   }










1262












1263



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




1✔





1264












1265



   auto bv3 = bv1 | bv2;




1✔





1266



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




2✔





1267












1268



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




1✔





1269



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




2✔





1270












1271



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




1✔





1272



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




2✔





1273



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




1✔





1274












1275



   const auto str = bv4.to_string();




1✔





1276



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




2✔





1277












1278



   return {result};




3✔





1279



}




6✔





1280












1281



}  // namespace










1282












1283



class BitVector_Tests final : public Test {




×







1284



   public:










1285



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




1✔





1286



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




1✔





1287



         auto& rng = Test::rng();




1✔





1288












1289



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




1✔





1290



            test_bitvector_bitwise_accessors,










1291



            test_bitvector_capacity,










1292



            test_bitvector_subvector,










1293



            test_bitvector_global_modifiers_and_predicates,










1294



            test_bitvector_binary_operators,










1295



            test_bitvector_serialization,










1296



            test_bitvector_constant_time_operations,










1297



            test_bitvector_conditional_xor_workload,










1298



            test_bitvector_iterators,










1299



            test_bitvector_strongtype_adapter,










1300



         };




11✔





1301












1302



         for(const auto& test_func : funcs) {




11✔





1303



            auto fn_results = test_func(rng);




10✔





1304



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




10✔





1305



         }




10✔





1306












1307



         return results;




1✔





1308



      }




2✔





1309



};










1310












1311



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










1312












1313



#endif










1314












1315



}  // namespace Botan_Tests
























    

  • 

    •