gf2::BitStore

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

#include <BitStore.h>

Concept definition

template<typename Store>
concept gf2::BitStore =  requires(Store store, const Store const_store) {
    
    typename Store::word_type;
    requires Unsigned<typename Store::word_type>;
 
    
    { const_store.size() } -> std::same_as<usize>;
 
    
    { const_store.store() } -> std::same_as<const typename Store::word_type*>;
 
    
    
    { store.store() } -> std::convertible_to<const typename Store::word_type*>;
 
    
    
    { const_store.offset() } -> std::same_as<u8>;
 
    
    
    
    
    { const_store.words() } -> std::same_as<usize>;
 
    
    
    
    
    
    
    
    
    
    
    { const_store.word(usize{}) } -> std::same_as<typename Store::word_type>;
 
    
    
    
    
    
    
    
    
    
    
    
    { store.set_word(usize{}, typename Store::word_type{}) } -> std::same_as<void>;
}

Detailed Description

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

Required Type

The types all have, or view, a Store of contiguous bits packed into contiguous primitive unsigned words. They must expose the specific integer word type, Store::word_type, holding the store's bit elements. Almost all operations on and between bit-stores work a whole word at a time, so are inherently parallel.

Required Methods

The bit-store types must provide the following methods:

Method	Description
size()	Returns the number of bits in the store.
store() const	Returns a read-only pointer to the first word holding bits in the store.
store()	Returns a pointer to the first word holding bits in the store.
offset()	Returns the bit location of the store's first bit element in the *store() word.

The offset will always be zero for bit-sets and bit-vectors but typically non-zero for bit-spans, which are views into contiguous bits that need not aligned with underlying word boundaries.

Extra Required Methods

Strictly speaking, the four methods above are sufficient. However, in practise bit-stores all provide three extra methods that have a large impact on overall performance:

Method	Description
words()	This is always gf2::words_needed<Store::word_type>(size()) but cached for efficiency.
word(i)	Returns a "word" from the store that is possibly synthesised from two real words.
set_word(i, val)	Sets the value of a "word" in the store, possibly altering two real words.

These methods are at the core of every loop in the library, so have a measurable performance impact. They are trivially implemented for bit-sets and bit-vectors, but require some work for bit-spans where "words" are usually synthesised on the fly from pairs of real underlying unsigned integers.

Provided Functions

We define dozens of useful free functions that operate on any type satisfying the BitStore concept.
See the BitStore page for more details.