BitStore.h

A concept for types that can access individual bits packed into contiguous primitive unsigned words, along with many free functions that operate on those types.
See the BitStore page for more details. More...

Go to the source code of this file.

Classes
struct	std::formatter< Store >
	Specialise std::formatter to handle bit-stores ... More...

Namespaces
namespace	gf2
	The namespace for the gf2 library.

Concepts
concept	gf2::BitStore
	A concept that is satisfied by all bit-vector-like types, which we refer to as bit-stores.

Functions
Bit Access Functions:
template<BitStore Store>
constexpr bool	gf2::get (Store const &store, usize i)
	Returns the bool value of the bit at index i in the given bit-store.
template<BitStore Store>
constexpr auto	gf2::ref (Store &store, usize i)
	Returns a "reference" to the bit element i in the given bit-store.
template<BitStore Store>
constexpr bool	gf2::front (Store const &store)
	Returns true if the first bit element is set, false otherwise.
template<BitStore Store>
constexpr bool	gf2::back (Store const &store)
	Returns true if the final bit element is set, false otherwise.
template<BitStore Store>
constexpr auto &	gf2::set (Store &store, usize i, bool value=true)
	Sets the bit-element at the given index to the specified boolean value and returns the store for chaining. The default value for value is true.
template<BitStore Store>
constexpr auto &	gf2::flip (Store &store, usize i)
	Flips the value of the bit-element at the given index and returns the store for chaining.
template<BitStore Store>
constexpr auto &	gf2::swap (Store &store, usize i0, usize i1)
	Swaps the bits in the bit-store at indices i0 and i1 and returns the store for chaining.
Store Queries:
template<BitStore Store>
constexpr bool	gf2::is_empty (Store const &store)
	Returns true if the store is empty, false otherwise.
template<BitStore Store>
constexpr bool	gf2::any (Store const &store)
	Returns true if at least one bit in the store is set, false otherwise.
template<BitStore Store>
constexpr bool	gf2::all (Store const &store)
	Returns true if all bits in the store are set, false otherwise.
template<BitStore Store>
constexpr bool	gf2::none (Store const &store)
	Returns true if no bits in the store are set, false otherwise.
Store Mutators:
template<BitStore Store>
constexpr auto &	gf2::set_all (Store &store, bool value=true)
	Sets the bits in the store to the boolean value and returns the store for chaining.
template<BitStore Store>
constexpr auto &	gf2::flip_all (Store &store)
	Flips the value of the bits in the store and returns the store for chaining.
Store Fills:
template<Unsigned Src, BitStore Store>
constexpr auto &	gf2::copy (Src src, Store &store)
	Copies the bits from an unsigned integral src value and returns the store for chaining.
template<BitStore Src, BitStore Store>
constexpr auto &	gf2::copy (Src const &src, Store &store)
	Copies the bits from an equal-sized src store and returns the store for chaining.
template<usize N, BitStore Store>
constexpr auto &	gf2::copy (std::bitset< N > const &src, Store &store)
	Copies the bits of an equal-sized std::bitset and returns the store for chaining.
template<BitStore Store>
constexpr auto &	gf2::copy (Store &store, std::invocable< usize > auto f)
	Fill the store by repeatedly calling f(i) and returns the store for chaining.
template<BitStore Store>
constexpr auto &	gf2::random_fill (Store &store, double p=0.5, u64 seed=0)
	Fill the store with random bits and returns the store for chaining.
Bit Counts:
template<BitStore Store>
constexpr usize	gf2::count_ones (Store const &store)
	Returns the number of set bits in the store.
template<BitStore Store>
constexpr usize	gf2::count_zeros (Store const &store)
	Returns the number of unset bits in the store.
template<BitStore Store>
constexpr usize	gf2::leading_zeros (Store const &store)
	Returns the number of leading zeros in the store.
template<BitStore Store>
constexpr usize	gf2::trailing_zeros (Store const &store)
	Returns the number of trailing zeros in the store.
Set-bit indices:
template<BitStore Store>
constexpr std::optional< usize >	gf2::first_set (Store const &store)
	Returns the index of the first set bit in the bit-store or {} if no bits are set.
template<BitStore Store>
constexpr std::optional< usize >	gf2::last_set (Store const &store)
	Returns the index of the last set bit in the bit-store or {} if no bits are set.
template<BitStore Store>
constexpr std::optional< usize >	gf2::next_set (Store const &store, usize index)
	Returns the index of the next set bit after index in the store or {} if no more set bits exist.
template<BitStore Store>
constexpr std::optional< usize >	gf2::previous_set (Store const &store, usize index)
	Returns the index of the previous set bit before index in the store or {} if there are none.
Unset-bit Indices:
template<BitStore Store>
constexpr std::optional< usize >	gf2::first_unset (Store const &store)
	Returns the index of the first unset bit in the bit-store or {} if no bits are unset.
template<BitStore Store>
constexpr std::optional< usize >	gf2::last_unset (Store const &store)
	Returns the index of the last unset bit in the bit-store or {} if no bits are unset.
template<BitStore Store>
constexpr std::optional< usize >	gf2::next_unset (Store const &store, usize index)
	Returns the index of the next unset bit after index in the store or {} if no more unset bits exist.
template<BitStore Store>
constexpr std::optional< usize >	gf2::previous_unset (Store const &store, usize index)
	Returns the index of the previous unset bit before index in the store or {} if no more unset bits exist.
Store Iterators:
template<BitStore Store>
constexpr auto	gf2::bits (Store const &store)
	Returns a const iterator over the bool values of the bits in the const bit-store.
template<BitStore Store>
constexpr auto	gf2::bits (Store &store)
	Returns a non-const iterator over the values of the bits in the mutable bit-store.
template<BitStore Store>
constexpr auto	gf2::set_bits (Store const &store)
	Returns an iterator over the indices of any set bits in the bit-store.
template<BitStore Store>
constexpr auto	gf2::unset_bits (Store const &store)
	Returns an iterator over the indices of any unset bits in the bit-store.
template<BitStore Store>
constexpr auto	gf2::store_words (Store const &store)
	Returns a const iterator over all the words underlying the bit-store.
template<BitStore Store>
constexpr auto	gf2::to_words (Store const &store)
	Returns a copy of the words underlying this bit-store.
Store Spans:
template<BitStore Store>
static constexpr auto	gf2::span (Store const &store, usize begin, usize end)
	Constructs a read-only bit-span over the const bit-store store for its bits in the range [begin, end).
template<BitStore Store>
static constexpr auto	gf2::span (Store &store, usize begin, usize end)
	Constructs a bit-span over the bit-store store for its bits in the range [begin, end). This span allows modification of the underlying bits (unless its created from a span that is itself const).
Sub-vectors:
template<BitStore Store>
constexpr auto	gf2::sub (Store const &store, usize begin, usize end)
	Returns a clone of the elements in the half-open range [begin, end) as a new bit-vector.
Store Splits and Joins:
template<BitStore Store>
constexpr void	gf2::split (Store const &store, usize at, BitVec< typename Store::word_type > &left, BitVec< typename Store::word_type > &right)
	Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are stored in the passed bit-vectors left and right.
template<BitStore Store>
constexpr auto	gf2::split (Store const &store, usize at)
	Views a bit-store as two parts containing the elements [0, at) and [at, size()) respectively. Clones of the parts are returned as a pair of new bit-vectors [left, right].
template<BitStore Lhs, BitStore Rhs>
auto	gf2::join (Lhs const &lhs, Rhs const &rhs)
	Returns a new bit-vector formed by joining two bit-stores lhs and rhs.
Interleaving With Zeros:
template<BitStore Store>
constexpr void	gf2::riffle (Store const &store, BitVec< typename Store::word_type > &dst)
	Interleaves the bits of a bit-store with zeros storing the result into the passed bit-vector dst.
template<BitStore Store>
constexpr auto	gf2::riffle (Store const &store)
	Returns a new bit-vector that is the result of riffling the bits in this bit-store with zeros.
String Representations:
template<BitStore Store>
static std::string	gf2::to_binary_string (Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
	Returns a binary string representation of a store.
template<BitStore Store>
static std::string	gf2::to_string (Store const &store, std::string_view sep="", std::string_view pre="", std::string_view post="")
	Returns a binary string representation of a store.
template<BitStore Store>
static std::string	gf2::to_pretty_string (Store const &store)
	Returns a "pretty" string representation of a store.
template<BitStore Store>
static std::string	gf2::to_hex_string (Store const &store)
	Returns the "hex" string representation of the bits in the bit-store.
template<BitStore Store>
static std::string	gf2::describe (Store const &store)
	Detailed Description of a Bit-Store.
template<BitStore Store>
std::ostream &	gf2::operator<< (Store const &store, std::ostream &s)
	The usual output stream operator for a bit-store.
The Equality Operator:
template<BitStore Lhs, BitStore Rhs>
constexpr bool	gf2::operator== (Lhs const &lhs, Rhs const &rhs)
	Checks that any pair of bit-stores are equal in content.
In-place Bit Shifts:
template<BitStore Store>
constexpr void	gf2::operator<<= (Store &store, usize shift)
	In-place left shift of a bit-store by shift bits.
template<BitStore Store>
constexpr void	gf2::operator>>= (Store &store, usize shift)
	In-place right shift of a store by shift bits.
Out-of-place Bit Shifts:
template<BitStore Store>
constexpr auto	gf2::operator<< (Store const &store, usize shift)
	Returns a new bit-vector that is the store shifted left by shift bits.
template<BitStore Store>
constexpr auto	gf2::operator>> (Store const &store, usize shift)
	Returns a new bit-vector that is lhs shifted right by shift bits.
In-place Bitwise Operations:
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void	gf2::operator^= (Lhs &lhs, Rhs const &rhs)
	In-place XOR of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void	gf2::operator&= (Lhs &lhs, Rhs const &rhs)
	In-place AND of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void	gf2::operator|= (Lhs &lhs, Rhs const &rhs)
	In-place OR of one bit-store with an equal-sized bit-store.
Out-of-place Bitwise Operations:
template<BitStore Store>
constexpr auto	gf2::operator~ (Store const &store)
	Returns a new bit-vector that has the same bits as a bit-store but with all the bits flipped.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto	gf2::operator^ (Lhs const &lhs, Rhs const &rhs)
	Returns the XOR of two equal-sized bit-stores as a new bit-vector.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto	gf2::operator& (Lhs const &lhs, Rhs const &rhs)
	Returns the AND of two equal-sized bit-stores as a new bit-vector.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto	gf2::operator| (Lhs const &lhs, Rhs const &rhs)
	Returns the OR of two equal-sized bit-stores as a new bit-vector.
In-place Arithmetic Operations:
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void	gf2::operator+= (Lhs &lhs, Rhs const &rhs)
	In-place addition of one bit-store with an equal-sized bit-store.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr void	gf2::operator-= (Lhs &lhs, Rhs const &rhs)
	In-place difference of one bit-store with an equal-sized bit-store.
Out-of-place Arithmetic Operations:
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto	gf2::operator+ (Lhs const &lhs, Rhs const &rhs)
	Adds two equal-sized bit-stores and returns the result as a new bit-vector.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr auto	gf2::operator- (Lhs const &lhs, Rhs const &rhs)
	Subtracts two equal-sized bit-stores and returns the result as a new bit-vector.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr bool	gf2::dot (Lhs const &lhs, Rhs const &rhs)
	Dot Products:
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
constexpr bool	gf2::operator* (Lhs const &lhs, Rhs const &rhs)
	Operator * returns the dot product of lhs and rhs as a boolean value.
template<BitStore Lhs, BitStore Rhs> requires std::same_as<typename Lhs::word_type, typename Rhs::word_type>
auto	gf2::convolve (Lhs const &lhs, Rhs const &rhs)
	Convolutions:

Detailed Description

A concept for types that can access individual bits packed into contiguous primitive unsigned words, along with many free functions that operate on those types.
See the BitStore page for more details.