Reference¶
-
namespace kitty¶
Enums
-
enum top_decomposition¶
Values:
-
enumerator none¶
-
enumerator and_¶
-
enumerator or_¶
-
enumerator lt_¶
-
enumerator le_¶
-
enumerator xor_¶
-
enumerator none¶
Functions
-
template<typename TT, typename Callback = decltype(detail::exact_spectral_canonization_null_callback)>
TT exact_linear_canonization(const TT &tt, Callback &&fn = detail::exact_spectral_canonization_null_callback)¶ Applies exact linear classification.
This algorithms applies all linear input transformations to a function and returns the function with the smallest integer representation as representative of the equivalence class.
- Parameters
tt – Truth table
-
template<typename TT>
TT exact_linear_output_canonization(const TT &tt)¶ Applies exact linear classification and output negation.
This algorithms applies all linear input transformations to a function and its complement and returns the function with the smallest integer representation as representative of the equivalence class.
- Parameters
tt – Truth table
-
template<typename TT, typename Callback = decltype(detail::exact_spectral_canonization_null_callback)>
TT exact_affine_canonization(const TT &tt, Callback &&fn = detail::exact_spectral_canonization_null_callback)¶ Applies exact affine classification.
This algorithms applies all linear input transformations and input complementations to a function and returns the function with the smallest integer representation as representative of the equivalence class.
- Parameters
tt – Truth table
-
template<typename TT>
TT exact_affine_output_canonization(const TT &tt)¶ Applies exact affine classification and output negation.
This algorithms applies all linear input transformations and input complementations to a function and its complement and returns the function with the smallest integer representation as representative of the equivalence class.
- Parameters
tt – Truth table
-
template<typename TT, typename Fn>
auto unary_operation(const TT &tt, Fn &&op)¶ Perform bitwise unary operation on truth table.
- Parameters
tt – Truth table
op – Unary operation that takes as input a word (
uint64_t
) and returns a word
- Returns
new constructed truth table of same type and dimensions
-
template<typename TT, typename Fn>
auto binary_operation(const TT &first, const TT &second, Fn &&op)¶ Perform bitwise binary operation on two truth tables.
The dimensions of
first
andsecond
must match. This is ensured at compile-time for static truth tables, but at run-time for dynamic truth tables.- Parameters
first – First truth table
second – Second truth table
op – Binary operation that takes as input two words (
uint64_t
) and returns a word
- Returns
new constructed truth table of same type and dimensions
-
template<typename TT, typename Fn>
auto ternary_operation(const TT &first, const TT &second, const TT &third, Fn &&op)¶ Perform bitwise ternary operation on three truth tables.
The dimensions of
first
,second
, andthird
must match. This is ensured at compile-time for static truth tables, but at run-time for dynamic truth tables.- Parameters
first – First truth table
second – Second truth table
third – Third truth table
op – Ternary operation that takes as input three words (
uint64_t
) and returns a word
- Returns
new constructed truth table of same type and dimensions
-
template<typename TT, typename Fn>
auto quaternary_operation(const TT &first, const TT &second, const TT &third, const TT &fourth, Fn &&op)¶ Perform bitwise quaternary operation on four truth tables.
The dimensions of all truth tables must match. This is ensured at compile-time for static truth tables, but at run-time for dynamic truth tables.
- Parameters
first – First truth table
second – Second truth table
third – Third truth table
fourth – Fourth truth table
op – Quaternary operation that takes as input four words (
uint64_t
) and returns a word
- Returns
new constructed truth table of same type and dimensions
-
template<typename TT, typename Fn>
bool binary_predicate(const TT &first, const TT &second, Fn &&op)¶ Computes a predicate based on two truth tables.
The dimensions of
first
andsecond
must match. This is ensured at compile-time for static truth tables, but at run-time for dynamic truth tables.- Parameters
first – First truth table
second – Second truth table
op – Binary operation that takes as input two words (
uint64_t
) and returns a Boolean
- Returns
true or false based on the predicate
-
template<typename TT, typename Fn>
bool ternary_predicate(const TT &first, const TT &second, const TT &third, Fn &&op)¶ Computes a predicate based on three truth tables.
The dimensions of
first
,second
andthird
must match. This is ensured at compile-time for static truth tables, but at run-time for dynamic truth tables.- Parameters
first – First truth table
second – Second truth table
third – Third truth table
op – Ternary operation that takes as input three words (
uint64_t
) and returns a Boolean
- Returns
true or false based on the predicate
-
template<typename TT, typename Fn>
void assign_operation(TT &tt, Fn &&op)¶ Assign computed values to bits.
The functor
op
computes bits which are assigned to the bits of the truth table.- Parameters
tt – Truth table
op – Unary operation that takes no input and returns a word (
uint64_t
)
-
template<typename TT, typename Fn>
void for_each_block(const TT &tt, Fn &&op)¶ Iterates through each block of a truth table.
The functor
op
is called for every block of the truth table.- Parameters
tt – Truth table
op – Unary operation that takes as input a word (
uint64_t
) and returns void
-
template<typename TT, typename Fn>
void for_each_block_reversed(const TT &tt, Fn &&op)¶ Iterates through each block of a truth table in reverse order.
The functor
op
is called for every block of the truth table in reverse order.- Parameters
tt – Truth table
op – Unary operation that takes as input a word (
uint64_t
) and returns void
-
template<typename TT, typename Fn>
inline void for_each_one_bit(const TT &tt, Fn &&op)¶ Iterates through each 1-bit in the truth table.
The functor
op
is called for every bit position of the truth table for which the bit is assigned 1.- Parameters
tt – Truth table
op – Unary operation that takes as input a word (
uint64_t
) and returns void
-
template<typename TT>
void set_bit(TT &tt, uint64_t index)¶ Sets bit at index to true.
- Parameters
tt – Truth table
index – Bit index
-
template<typename TT>
auto get_bit(const TT &tt, uint64_t index)¶ Gets bit at index.
- Parameters
tt – Truth table
index – Bit index
- Returns
1 if bit is set, otherwise 0
-
template<typename TT>
void clear_bit(TT &tt, uint64_t index)¶ Clears bit at index (sets bit at index to false)
- Parameters
tt – Truth table
index – Bit index
-
template<typename TT>
void flip_bit(TT &tt, uint64_t index)¶ Flips bit at index.
- Parameters
tt – Truth table
index – Bit index
-
template<typename TT>
void flip_bit(ternary_truth_table<TT> &tt, uint64_t index)¶
-
template<typename TT>
inline uint64_t count_ones(const TT &tt)¶ Count ones in truth table.
- Parameters
tt – Truth table
-
template<typename TT>
inline uint64_t count_zeros(const TT &tt)¶ Count zeros in truth table.
- Parameters
tt – Truth table
-
template<typename TT>
int64_t find_first_one_bit(const TT &tt, int64_t start = 0)¶ Finds least-significant one-bit.
Returns -1, if truth table is constant 0.
- Parameters
tt – Truth table
start – Bit to start from (default is 0)
-
template<typename TT>
int64_t find_last_one_bit(const TT &tt)¶ Finds most-significant one-bit.
Returns -1, if truth table is constant 0.
- Parameters
tt – Truth table
-
template<typename TT>
int64_t find_first_bit_difference(const TT &first, const TT &second)¶ Finds least-significant bit difference.
Returns -1, if truth tables are the same
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
int64_t find_last_bit_difference(const TT &first, const TT &second)¶ Finds most-significant bit difference.
Returns -1, if truth tables are the same
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
std::vector<cube> cnf_characteristic(const TT &tt)¶ Create CNF of the characteristic function.
Creates a CNF representation for the characteritic function of the input function, also known as Tseytin transformation. To obtain small CNF, an ISOP is computed.
- Parameters
tt – Truth table
-
template<typename TT>
inline TT create(unsigned num_vars)¶ Creates truth table with number of variables.
If some truth table instance is given, one can create a truth table with the same type by calling the
construct()
method on it. This function helps if only the number of variables is known and the base type and uniforms the creation of static and dynamic truth tables. Note, however, that for static truth tablesnum_vars
must be consistent to the number of variables in the truth table type.- Parameters
num_vars – Number of variables
-
template<typename TT>
void create_nth_var(TT &tt, uint8_t var_index, bool complement = false)¶ Constructs projections (single-variable functions)
- Parameters
tt – Truth table
var_index – Index of the variable, must be smaller than the truth table’s number of variables
complement – If true, realize inverse projection
-
template<class TT>
TT nth_var(uint8_t num_vars, uint8_t var_index, bool complement = false)¶ Constructs projections (single-variable functions) out-of-place.
- Parameters
tt – Truth table
var_index – Index of the variable, must be smaller than the truth table’s number of variables
complement – If true, realize inverse projection
-
template<typename TT>
void create_from_binary_string(TT &tt, const std::string &binary)¶ Constructs truth table from binary string.
Note that the first character in the string represents the most significant bit in the truth table. For example, the 2-input AND function is represented by the binary string “1000”. The number of characters in
binary
must match the number of bits intt
.- Parameters
tt – Truth table
binary – Binary string with as many characters as bits in the truth table
-
template<typename TT>
void create_from_hex_string(TT &tt, const std::string &hex)¶ Constructs truth table from hexadecimal string.
Note that the first character in the string represents the four most significant bit in the truth table. For example, the 3-input majority function is represented by the binary string “E8” or “e8”. The number of characters in
hex
must be one fourth the number of bits intt
.- Parameters
tt – Truth table
hex – Hexadecimal string
-
template<typename TT>
void create_from_raw(TT &tt, std::istream &in)¶ Creates string from raw character data.
Can create a truth table from the data that is produced by
print_raw
, e.g., from binary files orstd::stringstream
.- Parameters
tt – Truth table
in – Input stream
-
template<typename TT>
void create_random(TT &tt, std::default_random_engine::result_type seed)¶ Constructs a truth table from random value.
Computes random words and assigns them to the truth table. The number of variables is determined from the truth table.
- Parameters
tt – Truth table
seed – Random seed
-
template<typename TT>
void create_random(TT &tt)¶ Constructs a truth table from random value.
Computes random words and assigns them to the truth table. The number of variables is determined from the truth table. Seed is taken from current time.
- Parameters
tt – Truth table
-
template<typename TT, typename InputIt>
void create_from_words(TT &tt, InputIt begin, InputIt end)¶ Constructs a truth table from a range of words.
The range of words is given in terms of a begin and end iterator. Hence, it’s possible to copy words from a C++ container or a C array.
- Parameters
tt – Truth table
begin – Begin iterator
end – End iterator
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void create_from_cubes(TT &tt, const std::vector<cube> &cubes, bool esop = false)¶ Creates truth table from cubes representation.
A sum-of-product is represented as a vector of products (called cubes).
An empty truth table is given as first argument to determine type and number of variables. Literals in products that do not fit the number of variables of the truth table are ignored.
The cube representation only allows truth table sizes up to 32 variables.
- Parameters
tt – Truth table
cubes – Vector of cubes
esop – Use ESOP instead of SOP
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void create_from_clauses(TT &tt, const std::vector<cube> &clauses, bool esop = false)¶ Creates truth table from clause representation.
A product-of-sum is represented as a vector of sums (called clauses).
An empty truth table is given as first argument to determine type and number of variables. Literals in sums that do not fit the number of variables of the truth table are ignored.
The clause representation only allows truth table sizes up to 32 variables.
- Parameters
tt – Truth table
clauses – Vector of clauses
esop – Use product of exclusive sums instead of POS
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
inline void create_majority(TT &tt)¶ Constructs majority-n function.
The number of variables is determined from the truth table.
- Parameters
tt – Truth table
-
template<typename TT>
void create_threshold(TT &tt, uint8_t threshold)¶ Constructs threshold function.
The resulting function is true, if strictly more than
threshold
inputs areThe number of variables is determined from the truth table.
- Parameters
tt – Truth table
threshold – threshold value
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void create_equals(TT &tt, uint8_t bitcount)¶ Constructs equals-k function.
The resulting function is true, if exactly
bitcount
bits are 1. The number of variables is determiend from the truth table.- Parameters
tt – Truth table
bitcount – equals-k value
-
template<typename TT>
void create_symmetric(TT &tt, uint64_t counts)¶ Constructs symmetric function.
Bits in
counts
are numbered from 0 to 63. If biti
is set incounts
, the created truth table will evaluate to true, ifi
bits are set in the input assignment.- Parameters
tt – Truth table
counts – Bitcount mask
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void create_parity(TT &tt)¶ Constructs parity function over n variables.
The number of variables is determined from the truth table.
- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_from_chain(TT &tt, const std::vector<std::string> &steps, std::string *error = nullptr)¶ Constructs truth table from Boolean chain.
If
tt
has \(n\) variables, then each string insteps
is of the formx<i> = x<j> <op> x<k>
where
<i>
is an increasing number starting from \(n + 1\), and<j>
and<k>
refer to previous steps or primary inputs where \(j < i\) and \(k < i\). Primary inputs are indexed from \(1\) to \(n\). The last computed step will be assigned tott
. The following operators are supported:<op>
Operation
Truth table
"!|"
Nondisjunction
0001
">"
Nonimplication
0010
"<"
Converse nonimplication
0100
"^"
Exclusive disjunction
0110
"!&"
Nonconjunction
0111
"&"
Conjunction
1000
"="
Equivalence
1001
">="
Nonimplication
1011
"<="
Implication
1101
"|"
Disjunction
1110
The following example will generate the majority function:
kitty::static_truth_table<3> tt; kitty::create_from_chain( tt, {"x4 = x1 & x2", "x5 = x1 & x3", "x6 = x2 & x3", "x7 = x4 | x5", "x8 = x6 | x7"} );
If parsing fails, the function returns
false
, and iferror
is notnullptr
, it contains a descriptive reason, why parsing failed. Otherwise, the function returnstrue
.- Parameters
tt – Truth table
steps – Vector of steps
error – If not null, a pointer to store the error message
- Returns
True on success
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_multiple_from_chain(unsigned num_vars, std::vector<TT> &tts, const std::vector<std::string> &steps, std::string *error = nullptr)¶ Constructs truth tables from Boolean chain.
Like
create_from_chain
, but also returns all internally computed steps.- Parameters
num_vars – Number of input variables
tts – Truth table for all steps, tt[i] corresponds to step x \((i + 1)\)
steps – Vector of steps
error – If not null, a pointer to store the error message
- Returns
True on success
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_from_chain(TT &tt, std::istream &in, std::string *error = nullptr)¶ Constructs truth table from Boolean chain.
Like the other
create_from_chain
function, but reads chain from an input stream instead of a vector of strings. Lines are separated by a new line. Empty lines are skipped over.- Parameters
tt – Truth table
in – Input stream to read chain
error – If not null, a pointer to store the error message
- Returns
True on success
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_multiple_from_chain(unsigned num_vars, std::vector<TT> &tts, std::istream &in, std::string *error = nullptr)¶ Constructs truth tables from Boolean chain.
Like
create_from_chain
, but also returns all internally computed steps.- Parameters
num_vars – Number of input variables
tts – Truth table for all steps, tt[i] corresponds to step x \((i + 1)\)
in – Input stream to read chain
error – If not null, a pointer to store the error message
- Returns
True on success
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
inline void create_characteristic(TT &tt, const TTFrom &from)¶ Creates characteristic function.
Creates the truth table of the characteristic function, which contains one additional variable. The new output variable will be the most-significant variable of the new function.
- Parameters
tt – Truth table for characteristic function
from – Input truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_from_expression(TT &tt, const std::string &expression, std::vector<TT> const &input_tts)¶ Creates truth table from textual expression.
An expression
E
is a constant0
or1
, or a truth tablea
,b
, …,p
from the vectorinput_tts
, the negation of an expression!E
, the conjunction of multiple expressions(E...E)
, the disjunction of multiple expressions{E...E}
, the exclusive OR of multiple expressions[E...E]
, or the majority of three expressions<EEE>
.- Parameters
tt – Truth table
from – Expression as string
input_tts – Input truth tables assigned to a, b, …
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_from_expression(TT &tt, const std::string &expression)¶ Creates truth table from textual expression.
An expression
E
is a constant0
or1
, or a variablea
,b
, …,p
, the negation of an expression!E
, the conjunction of multiple expressions(E...E)
, the disjunction of multiple expressions{E...E}
, the exclusive OR of multiple expressions[E...E]
, or the majority of three expressions<EEE>
. Examples are[(ab)(!ac)]
to describe if-then-else, or!{!a!b}
to describe the application of De Morgan’s law to(ab)
. The size of the truth table must fit the largest variable in the expression, e.g., ifc
is the largest variable, then the truth table have at least three variables.- Parameters
tt – Truth table
from – Expression as string
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool create_from_formula(TT &tt, const std::string &expression, const std::vector<std::string> &var_names)¶ Creates a truth table from a Boolean formula.
Translates a Boolean expression to a truth table with the variable names and ordering defined by
var_names
. The supported Boolean operations are the negation!a
ora'
, the conjunctiona*b
ora&b
ora b
, the disjunctiona+b
, ora|b
, and the exclusive ORa^b
. Brackets()
can be used for the operation order.- Parameters
tt – Truth table
from – Expression as string
input_tts – Variable names
-
template<class TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void create_prime(TT &tt)¶ Creates function where on-set corresponds to prime numbers.
This creates a function in which \(f(x) = 1\), if and only if \(x\) is a prime number in its integer representation. The function only works for truth tables with at most 10 variables. The number of variables is determined from the truth table.
- Parameters
tt – Truth table
-
inline void print_cubes(const std::vector<cube> &cubes, unsigned length = 32u, std::ostream &os = std::cout)¶
Prints all cubes in a vector.
- Parameters
cubes – Vector of cubes
length – Number of variables in each cube
os – Output stream
-
template<class TT>
top_decomposition is_top_decomposable(const TT &tt, uint32_t var_index, TT *func = nullptr, bool allow_xor = true)¶ Checks, whether function is top disjoint decomposable.
Checks whether the input function
tt
can be represented by the function \(f = g(h(X_1), a)\), where \(a \notin X_1\). The return value is \(g\):top_decomposition::and_
: \(g = a \land h(X_1)\)top_decomposition::or_
: \(g = a \lor h(X_1)\)top_decomposition::lt_
: \(g = \bar a \land h(X_1)\)top_decomposition::le_
: \(g = \bar a \lor h(X_1)\)top_decomposition::xor_
: \(g = a \oplus h(X_1)\)top_decomposition::none
: decomposition does not exist
The function can return the remainder function \(h\), whic will not depend on \(a\).
- Parameters
tt – Input function \(f\)
var_index – Variable \(a\)
func – If not
null
and decomposition exists, its value is assigned the remainder \(h\)allow_xor – Set to false to disable XOR decomposition
-
template<class TT>
bottom_decomposition is_bottom_decomposable(const TT &tt, uint32_t var_index1, uint32_t var_index2, TT *func = nullptr, bool allow_xor = true)¶ Checks, whether function is bottom disjoint decomposable.
Checks whether the input function
tt
can be represented by the function \(f = h(X_1, g(a, b))\), where \(a, b \notin X_1\). The return value is \(g\):bottom_decomposition::and_
: \(g = a \land b\)bottom_decomposition::or_
: \(g = a \lor b\)bottom_decomposition::lt_
: \(g = \bar a \land b\)bottom_decomposition::le_
: \(g = \bar a \lor b\)bottom_decomposition::xor_
: \(g = a \oplus b\)bottom_decomposition::none
: decomposition does not exist
The function can return the remainder function \(h\) in where \(g\) is substituted by \(a\). The remainder function will not depend on \(b\).
- Parameters
tt – Input function \(f\)
var_index1 – Variable \(a\)
var_index2 – Variable \(b\)
func – If not
null
and decomposition exists, its value is assigned the remainder \(h\)allow_xor – Set to false to disable XOR decomposition
-
template<class TT>
std::tuple<TT, bi_decomposition, std::vector<TT>> is_bi_decomposable(const TT &tt, const TT &dc)¶ Checks whether a function is bi-decomposable.
Checks whether an incompletely specified function (ISF)
tt
can be represented by the function \(f = h(l(X_1, X_3), g(X_2, X_3))\). It returns a tuple of: 1. :math:’f’, which is a completely specified Boolean function compatible with the input ISF 2. :math:’h’, which is the type of decomposition (and, or, xor, weak and, weak or) 3. :math:’l’ and :math:’g’, given as ISF (ON-set and DC-set)The algorithm is inspired by “An Algorithm for Bi-Decomposition of Logic Functions” by A. Mishchenko et al. presented in DAC 2001.
- Parameters
tt – ON-set of the input function \(f\)
dc – DC-set of the input function \(f\)
-
template<class TT>
std::tuple<TT, bi_decomposition, std::vector<TT>> is_bi_decomposable_mc(const TT &tt, const TT &dc)¶ Checks whether a function is bi-decomposable using XOR as preferred operation.
Checks whether an incompletely specified function (ISF)
tt
can be represented by the function \(f = h(l(X_1, X_3), g(X_2, X_3))\). It returns a tuple of: 1. :math:’f’, which is a completely specified Boolean function compatible with the input ISF 2. :math:’h’, which is the type of decomposition (and, or, xor, weak and, weak or) 3. :math:’l’ and :math:’g’, given as ISF (ON-set and DC-set)The algorithm is inspired by “An Algorithm for Bi-Decomposition of Logic Functions” by A. Mishchenko et al. presented in DAC 2001.
The cost is changed to add more XOR gates compared to AND/OR gates. This cost function is motivated by minimizing the number of AND gates in XAGs for cryptography and security applications. For these applications XOR gates are “free”.
- Parameters
tt – ON-set of the input function \(f\)
dc – DC-set of the input function \(f\)
-
template<class TTf, class TTg, class TTh>
bool is_ashenhurst_decomposable(const TTf &tt, const std::vector<uint32_t> &zs_index, const std::vector<uint32_t> &ys_index, const TTg &outer_func, const TTh &inner_func)¶ Checks, whether a function is Ashenhurst decomposable.
Given functions f(.), g(.), and h(.) and a partition on arguments into z and y. This function determines whether f(x) is decomposable into g(z, h(y)) where x = union(z,y) and intersect(z, y) = null. This function does not check for permutation of variables given by zs_index and ys_index. The elements in these vectors are treated as ordered values.
- Parameters
tt – The function to the check the decomposition on (function f)
zs_index – The ordered set of indices of vector x (input to f) that are the inputs to outer_func (g).
ys_index – The ordered set of indices of vector x (input to f) that are input to the inner_func (h).
outer_func – The outer decomposition function (function g).
inner_func – The inner decomposition function (function h).
- Returns
true if the given decomposition is a valid one, false otherwise.
-
template<class TTf, class TTg, class TTh>
uint32_t ashenhurst_decomposition(const TTf &tt, const std::vector<uint32_t> &ys_index, std::vector<std::pair<TTg, TTh>> &decomposition)¶ Finds all of the possible Ashenhurst decompositions of a function given an input partitioning.
- Parameters
tt – The function to find all of its decompositions
ys_index – Indices indicating the partitioning of inputs
decomposition – A vector of decomposition pairs. This serves as a return return container.
- Returns
Returns the number of possible decompositions.
-
template<class TT, class CanonizationFn>
void fuller_neighborhood_enumeration(std::vector<TT> &functions, CanonizationFn &&canonization_fn)¶ Enumerate all representatives using 1-neighborhood search.
This function is based on Algorithm 4.2.1 in the PhD thesis “Analysis of Affine Equivalent Boolean Functions for Cryptography” by J.E. Fuller (Queensland University of Technology)
- Parameters
functions – Vector must be initialized with single seed function, will contain all enumerated functions after call
canonization_fn – A canonization function, which takes as input a truth table and returns a truth table
-
template<typename TT>
inline std::vector<cube> esop_from_optimum_pkrm(const TT &tt)¶ Computes ESOP representation using optimum PKRM.
This algorithm first computes an ESOP using the algorithm described in [R. Drechsler, IEEE Trans. C 48(9), 1999, 987–990].
The algorithm applies post-optimization to merge distance-1 cubes.
- Parameters
tt – Truth table
-
template<class TT>
std::vector<cube> esop_from_pprm(const TT &func)¶ Computes PPRM representation for a function.
This algorithm applies recursively the positive Davio decomposition which eventually leads into the PPRM representation of a function.
- Parameters
tt – Truth table
-
inline std::size_t hash_block(uint64_t word)¶
Hash function for 64-bit word.
-
inline void hash_combine(std::size_t &seed, std::size_t other)¶
Combines two hash values.
-
template<typename TT>
std::vector<uint32_t> get_minterms(const TT &tt)¶ Computes all minterms.
- Parameters
tt – Truth table
-
inline std::vector<std::pair<std::vector<uint32_t>::const_iterator, std::vector<uint32_t>::const_iterator>> get_jbuddies(const std::vector<uint32_t> &minterms, uint32_t j)¶
Computes all j-buddies in a list of minterms.
Computes all pairs \((k, k')\) such that \(k < k'\) and the two minterms at indexes \(k\) and \(k'\) only differ in bit \(j\).
This algorithm is described by Knuth in Exercise TAOCP 7.1.1-29.
- Parameters
minterms – Vector of minterms
j – Bit position
-
inline std::vector<cube> get_prime_implicants_morreale(const std::vector<uint32_t> &minterms, unsigned num_vars)¶
Computes all prime implicants (from minterms)
This algorithm computes all prime implicants for a list of minterms. The running time is at most proportional to \(mn\), where \(m\) is the number of minterms and \(n\) is the number of variables.
The algorithm is described in Exercise TAOCP 7.1.1-30 by Knuth and is inspired by the algorithm described in [E. Morreale, IEEE Trans. EC 16(5), 1967, 611–620].
- Parameters
minterms – Vector of minterms (as integer values)
num_vars – Number of variables
-
template<typename TT>
std::vector<cube> get_prime_implicants_morreale(const TT &tt)¶ Computes all prime implicants (from truth table)
Computes minterms from truth table and calls overloaded function.
- Parameters
tt – Truth table
-
template<typename TT>
inline std::vector<cube> isop(const TT &tt)¶ Computes ISOP representation.
Computes the irredundant sum-of-products representation using the Minato-Morreale algorithm [S. Minato, IEEE Trans. CAD 15(4), 1996, 377-384].
- Parameters
tt – Truth table
-
template<typename TT, typename Callback = decltype(detail::exact_npn_canonization_null_callback<TT>)>
std::tuple<TT, uint32_t, std::vector<uint8_t>> exact_p_canonization(const TT &tt, Callback &&fn = detail::exact_npn_canonization_null_callback<TT>)¶ Exact P canonization.
Given a truth table, this function finds the lexicographically smallest truth table in its P class, called P representative. Two functions are in the same P class, if one can obtain one from the other by input permutation.
The function can accept a callback as second parameter which is called for every visited function when trying out all combinations. This allows to exhaustively visit the whole P class.
The function returns a NPN configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the P representative
input negations and output negation, which is 0 in this case
input permutation to apply
- Parameters
tt – The truth table
fn – Callback for each visited truth table in the class (default does nothing)
- Returns
NPN configuration
-
template<typename TT, typename Callback = decltype(detail::exact_npn_canonization_null_callback<TT>)>
std::tuple<TT, uint32_t, std::vector<uint8_t>> exact_npn_canonization(const TT &tt, Callback &&fn = detail::exact_npn_canonization_null_callback<TT>)¶ Exact NPN canonization.
Given a truth table, this function finds the lexicographically smallest truth table in its NPN class, called NPN representative. Two functions are in the same NPN class, if one can obtain one from the other by input negation, input permutation, and output negation.
The function can accept a callback as second parameter which is called for every visited function when trying out all combinations. This allows to exhaustively visit the whole NPN class.
The function returns a NPN configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the NPN representative
input negations and output negation, output negation is stored as bit n, where n is the number of variables in
tt
input permutation to apply
- Parameters
tt – The truth table (with at most 6 variables)
fn – Callback for each visited truth table in the class (default does nothing)
- Returns
NPN configuration
-
template<typename TT, typename Callback = decltype(detail::exact_npn_canonization_null_callback<TT>)>
std::tuple<TT, uint32_t> exact_n_canonization(const TT &tt, Callback &&fn = detail::exact_npn_canonization_null_callback<TT>)¶ Exact N canonization.
Given a truth table, this function finds the lexicographically smallest truth table in its N class, called N representative. Two functions are in the same N class, if one can obtain one from the other by input negations.
The function can accept a callback as second parameter which is called for every visited function when trying out all combinations. This allows to exhaustively visit the whole N class.
The function returns a N configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the N representative
input negations that lead to the representative
- Parameters
tt – The truth table
fn – Callback for each visited truth table in the class (default does nothing)
- Returns
N configurations
-
template<typename TT>
std::tuple<TT, uint32_t, std::vector<uint8_t>> flip_swap_npn_canonization(const TT &tt)¶ Flip-swap NPN heuristic.
This algorithm will iteratively try to reduce the numeric value of the truth table by first inverting each input, then inverting the output, and then swapping each pair of inputs. Every improvement is accepted, the algorithm stops, if no more improvement can be achieved.
The function returns a NPN configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the NPN representative
input negations and output negation, output negation is stored as bit n, where n is the number of variables in
tt
input permutation to apply
- Parameters
tt – Truth table
- Returns
NPN configuration
-
template<typename TT>
std::tuple<TT, uint32_t, std::vector<uint8_t>> sifting_npn_canonization(const TT &tt)¶ Sifting NPN heuristic.
The algorithm will always consider two adjacent variables and try all possible transformations on these two. It will try once in forward direction and once in backward direction. It will try for the regular function and inverted function.
The function returns a NPN configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the NPN representative
input negations and output negation, output negation is stored as bit n, where n is the number of variables in
tt
input permutation to apply
- Parameters
tt – Truth table
- Returns
NPN configuration
-
template<typename TT>
std::tuple<TT, uint32_t, std::vector<uint8_t>> sifting_p_canonization(const TT &tt)¶ Sifting P heuristic.
The algorithm will always consider two adjacent variables and try all possible transformations on these two. It will try once in forward direction and once in backward direction. It will try for the regular function.
The function returns a P configuration which contains the necessary transformations to obtain the representative. It is a tuple of
the P representative
input negations and output negation, which is 0 in this case
input permutation to apply
- Parameters
tt – Truth table
- Returns
NPN configuration
-
template<typename TT, typename Callback>
void exact_np_enumeration(const TT &tt, Callback &&fn)¶ Exact NP enumeration.
Given a truth table, this function enumerates all the functions in its NP class. Two functions are in the same NP class, if one can be obtained from the other by input negation and input permutation.
The function takes a callback as second parameter which is called for every enumerated function. The callback should take as parameters:
NP-enumerated truth table
input negations
input permutation to apply
- Parameters
tt – Truth table
fn – Callback for each enumerated truth table in the NP class
-
template<typename TT, typename Callback>
void exact_p_enumeration(const TT &tt, Callback &&fn)¶ Exact P enumeration.
Given a truth table, this function enumerates all the functions in its P class. Two functions are in the same P class, if one can be obtained from the other by input permutation.
The function takes a callback as second parameter which is called for every enumerated function. The callback should take as parameters:
P-enumerated truth table
input permutation to apply
- Parameters
tt – Truth table
fn – Callback for each enumerated truth table in the P class
-
template<typename TT, typename Callback>
void exact_n_enumeration(const TT &tt, Callback &&fn)¶ Exact N enumeration.
Given a truth table, this function enumerates all the functions in its N class. Two functions are in the same N class, if one can be obtained from the other by input negation.
The function takes a callback as second parameter which is called for every enumerated function. The callback should take as parameters:
N-enumerated truth table
input negation to apply
- Parameters
tt – Truth table
fn – Callback for each enumerated truth table in the N class
-
template<typename TT, typename Callback = decltype(detail::exact_npn_canonization_null_callback<TT>)>
std::tuple<TT, std::vector<uint32_t>> exact_n_canonization_complete(const TT &tt, Callback &&fn = detail::exact_npn_canonization_null_callback<TT>)¶ Exact N canonization complete.
Given a truth table, this function finds the lexicographically smallest truth table in its N class, called N representative. Two functions are in the same N class, if one can obtain one from the other by input negations.
The function can accept a callback as second parameter which is called for every visited function when trying out all combinations. This allows to exhaustively visit the whole N class.
The function returns all the N configurations which contains the necessary transformations to obtain the representative. It is a tuple of
the N representative
a vector of all input negations that lead to the representative
- Parameters
tt – The truth table
fn – Callback for each visited truth table in the class (default does nothing)
- Returns
N configurations
-
template<typename TT>
TT create_from_npn_config(const std::tuple<TT, uint32_t, std::vector<uint8_t>> &config)¶ Obtain truth table from NPN configuration.
Given an NPN configuration, which contains a representative function, input/output negations, and input permutations this function computes the original truth table.
- Parameters
config – NPN configuration
-
template<typename TT>
inline ternary_truth_table<TT> unary_not(const ternary_truth_table<TT> &tt)¶
-
template<typename TT>
inline quaternary_truth_table<TT> unary_not(const quaternary_truth_table<TT> &tt)¶
-
template<typename TT>
inline TT unary_not_if(const TT &tt, bool cond)¶ Inverts all bits in a truth table, based on a condition
-
template<typename TT>
inline TT binary_and(const TT &first, const TT &second)¶ Bitwise AND of two truth tables.
-
template<typename TT>
inline ternary_truth_table<TT> binary_and(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Bitwise AND of two ternary truth tables.
Computation rules:
0 & 0 = 0 & 1 = 1 & 0 = 0
1 & 1 = 1
0 & - = - & 0 = 0
1 & x = x & 1 = x & - = - & x = x & x = x
-
template<typename TT>
inline quaternary_truth_table<TT> binary_and(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Bitwise OR of two quaternary truth tables.
Computation rules:
0 & 0 = 0 & 1 = 1 & 0 = 0
1 & 1 = 1
0 & - = - & 0 = x & 0 = 0 & x = 0
1 & - = - & 1 = - & - = -
1 & x = x & 1 = x & - = - & x = x & x = x
-
template<typename TT>
inline TT binary_or(const TT &first, const TT &second)¶ Bitwise OR of two truth tables.
-
template<typename TT>
inline ternary_truth_table<TT> binary_or(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Bitwise OR of two ternary truth tables.
Computation rules:
0 | 0 = 0
0 | 1 = 1 | 0 = 1 | 1 = 1
1 | - = - | 1 = 1
0 | - = - | 0 = - | - = -
-
template<typename TT>
inline quaternary_truth_table<TT> binary_or(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Bitwise OR of two quaternary truth tables.
Computation rules:
0 | 0 = 0
0 | 1 = 1 | 0 = 1 | 1 = 1
1 | - = - | 1 = x | 1 = 1 | x = 1
0 | - = - | 0 = - | - = -
0 | x = x | 0 = x | - = - | x = x | x = x
-
template<typename TT>
inline TT binary_xor(const TT &first, const TT &second)¶ Bitwise XOR of two truth tables.
-
template<typename TT>
inline ternary_truth_table<TT> binary_xor(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Bitwise XOR of two ternary truth tables.
Computation rules:
0 ^ 0 = 1 ^ 1 = 0
0 ^ 1 = 1 ^ 0 = 1
0 ^ - = - ^ 0 = 1 ^ - = - ^ 1 = - ^ - = -
-
template<typename TT>
inline quaternary_truth_table<TT> binary_xor(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Bitwise XOR of two ternary truth tables.
Computation rules:
0 ^ 0 = 1 ^ 1 = 0
0 ^ 1 = 1 ^ 0 = 1
0 ^ - = - ^ 0 = 1 ^ - = - ^ 1 = - ^ - = -
0 ^ x = x ^ 0 = 1 ^ x = x ^ 1 = - ^ x = x ^ - = x ^ x = x
-
template<typename TT>
inline TT ternary_majority(const TT &first, const TT &second, const TT &third)¶ Ternary majority of three truth tables.
-
template<typename TT>
inline ternary_truth_table<TT> ternary_majority(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second, const ternary_truth_table<TT> &third)¶ Ternary majority of three truth tables.
-
template<typename TT>
inline quaternary_truth_table<TT> ternary_majority(quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second, const quaternary_truth_table<TT> &third)¶ Ternary majority of three quaternary truth tables.
Computation rules: When there are two 0, 1, or x the result is 0, 1, x
ternary_majority(0, 1, -) = ternary_majority(0, -, -) = ternary_majority(1, -, -) = -
ternary_majority(0, 1, x) = ternary_majority(0, x, -) = ternary_majority(1, x, -) = ternary_majority(x, -, -) = x
ternary_majority is commutative
-
template<typename TT>
inline TT ternary_ite(const TT &first, const TT &second, const TT &third)¶ Performs ternary if-then-else of three truth tables.
- Parameters
first – Truth table for condition
second – Truth table for then-case
third – Truth table for else-case
-
template<typename TT>
inline ternary_truth_table<TT> ternary_ite(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second, const ternary_truth_table<TT> &third)¶
-
template<typename TT>
inline quaternary_truth_table<TT> ternary_ite(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second, const quaternary_truth_table<TT> &third)¶ Performs ternary if-then-else of three quaternary truth tables.
In general, each time the result would depend from a x, x is the result. For example, ternary_ite( -, 0, x ) = x However, ternary_ite( x, 0, 0 ) = ternary_ite( -, 0, 0 ) = 0 ternary_ite( x, 1, 1 ) = ternary_ite( -, 1, 1 ) = 1 ternary_ite( x, -, - ) = ternary_ite( -, -, - ) = -
- Parameters
first – Truth table for condition
second – Truth table for then-case
third – Truth table for else-case
-
template<typename TT>
inline TT mux_var(uint8_t var_index, const TT &then_, const TT &else_)¶ Muxes two truth tables based on a variable.
- Parameters
var_index – Variable index
then_ – Truth table for the then-case
else_ – Truth table for the else-case
-
template<typename TT>
inline ternary_truth_table<TT> mux_var(uint8_t var_index, const ternary_truth_table<TT> &then_, const ternary_truth_table<TT> &else_)¶ Muxes two ternary truth tables based on a variable.
Values that are not taken by the projections become 0s.
- Parameters
var_index – Variable index
then_ – Truth table for the then-case
else_ – Truth table for the else-case
-
template<typename TT>
inline quaternary_truth_table<TT> mux_var(uint8_t var_index, const quaternary_truth_table<TT> &then_, const quaternary_truth_table<TT> &else_)¶ Muxes two ternary truth tables based on a variable.
Values that are not taken by the projections become 0s.
- Parameters
var_index – Variable index
then_ – Truth table for the then-case
else_ – Truth table for the else-case
-
template<typename TT>
inline bool equal(const TT &first, const TT &second)¶ Checks whether two truth tables are equal.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool equal(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶
-
template<typename TT>
inline bool equal(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶
-
template<typename TT>
inline bool implies(const TT &first, const TT &second)¶ Checks if first truth table implies a second truth table.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool implies(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Checks if first ternary truth table implies a second ternary truth table.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool implies(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Checks if first quaternary truth table implies a second quaternary truth table.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool less_than(const TT &first, const TT &second)¶ Checks whether a truth table is lexicographically smaller than another.
Comparison is initiated from most-significant bit.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool less_than(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Checks whether a ternary truth table is lexicographically smaller than another.
Comparison is initiated from most-significant bit and don’t cares are considered as 0.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool less_than(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Checks whether a quaternary truth table is lexicographically smaller than another.
Comparison is initiated from most-significant bit Don’t cares are considered as 0 and don’t knows are considered as 1.
- Parameters
first – First truth table
second – Second truth table
-
template<typename TT>
inline bool is_const0(const TT &tt)¶ Checks whether truth table is contant 0.
- Parameters
tt – Truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true>
bool intersection_is_empty(const TT &first, const TT &second)¶ Checks whether the intersection of two truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true>
bool intersection_is_empty(const ternary_truth_table<TT> &a, const ternary_truth_table<TT> &b)¶ Checks whether the intersection of two ternary truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true>
bool intersection_is_empty(const quaternary_truth_table<TT> &a, const quaternary_truth_table<TT> &b)¶ Checks whether the intersection of two quaternary truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true, bool polarity3 = true>
bool intersection_is_empty(const TT &first, const TT &second, const TT &third)¶ Checks whether the intersection of three truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
third – Third truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
polarity3 – Polarity of the first truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true, bool polarity3 = true>
bool intersection_is_empty(const ternary_truth_table<TT> &a, const ternary_truth_table<TT> &b, const ternary_truth_table<TT> &c)¶ Checks whether the intersection of three ternary truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
third – Third truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
polarity3 – Polarity of the first truth table
-
template<typename TT, bool polarity1 = true, bool polarity2 = true, bool polarity3 = true>
bool intersection_is_empty(const quaternary_truth_table<TT> &a, const quaternary_truth_table<TT> &b, const quaternary_truth_table<TT> &c)¶ Checks whether the intersection of three quaternary truth tables is empty.
- Parameters
first – First truth table
second – Second truth table
third – Third truth table
polarity1 – Polarity of the first truth table
polarity2 – Polarity of the second truth table
polarity3 – Polarity of the first truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool has_var(const TT &tt, uint8_t var_index)¶ Checks whether truth table depends on given variable index.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT>
bool has_var(const ternary_truth_table<TT> &tt, uint8_t var_index)¶ Checks whether a ternary truth table depends on given variable index Don’t cares are treated like zeros.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool has_var(const quaternary_truth_table<TT> &tt, uint8_t var_index)¶ Checks whether a quaternary truth table depends on given variable index. This function returns false if the truth table potentially does not depend on the variable (due to don’t cares) and returns true if the truth table potentially depends on the variable (due to don’t knows).
For example, has_var( -01-, 0 ) = has_var( -01-, 1 ) = false. In the first case the truth table is considered to be 0011 and in the second case the truth table is considered to be 1010.
Yet, has_var( x01-, 0 ) = has_var( x01-, 1 ) = true. In the first case we cannot assume x = 0 and in the second case we cannot assume x = 1.
Finally, has_var( x0-0, 1 ) = true, since the don’t care should be equal to an unknown value.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT>
void next_inplace(TT &tt)¶ Computes the next lexicographically larger truth table.
This methods updates
tt
to become the next lexicographically larger truth table. Iftt
is already the largest truth table, the updated truth table will contain all zeros.- Parameters
tt – Truth table
-
template<typename TT>
void next_inplace(ternary_truth_table<TT> &tt)¶ Computes the next lexicographically larger truth table.
This methods updates
tt
to become the next lexicographically larger truth table. Iftt
is already the largest truth table, the updated truth table will contain all zeros.Don’t cares are treated like zeros, so the truth tables 1110 and 111- will become 1111.
This method never increase the number of don’t cares of the input truth table.
For example, truth table -101 will become -110, not -11-.
- Parameters
tt – Truth table
-
template<typename TT>
void next_inplace(quaternary_truth_table<TT> &tt)¶ Computes the next lexicographically larger truth table.
This methods updates
tt
to become the next lexicographically larger truth table. Iftt
is already the largest truth table, the updated truth table will contain all zeros.Lexicographical increasing order for quaternary truth table:
0, 1, -, x
- Parameters
tt – Truth table
-
template<typename TT>
inline TT next(const TT &tt)¶ Returns the next lexicographically larger truth table.
Out-of-place variant for
next_inplace
.- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor0_inplace(TT &tt, uint8_t var_index)¶ Computes co-factor with respect to 0.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor0_inplace(ternary_truth_table<TT> &tt, uint8_t var_index)¶ Computes co-factor with respect to 0.
- Parameters
tt – Ternary truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor0_inplace(quaternary_truth_table<TT> &tt, uint8_t var_index)¶ Computes co-factor with respect to 0.
- Parameters
tt – Ternary truth table
var_index – Variable index
-
template<typename TT>
TT cofactor0(const TT &tt, uint8_t var_index)¶ Returns co-factor with respect to 0.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor1_inplace(TT &tt, uint8_t var_index)¶ Computes co-factor with respect to 1.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor1_inplace(ternary_truth_table<TT> &tt, uint8_t var_index)¶ Computes co-factor with respect to 1.
- Parameters
tt – Ternary truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void cofactor1_inplace(quaternary_truth_table<TT> &tt, uint8_t var_index)¶ Computes co-factor with respect to 1.
- Parameters
tt – Ternary truth table
var_index – Variable index
-
template<typename TT>
TT cofactor1(const TT &tt, uint8_t var_index)¶ Returns co-factor with respect to 1.
- Parameters
tt – Truth table
var_index – Variable index
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_adjacent_inplace(TT &tt, uint8_t var_index)¶ Swaps two adjacent variables in a truth table.
The function swaps variable
var_index
withvar_index + 1
. The function will changett
in-place. Iftt
should not be changed, one can useswap_adjacent
instead.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_adjacent_inplace(ternary_truth_table<TT> &tt, uint8_t var_index)¶ Swaps two adjacent variables in a truth table.
The function swaps variable
var_index
withvar_index + 1
. The function will changett
in-place. Iftt
should not be changed, one can useswap_adjacent
instead.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_adjacent_inplace(quaternary_truth_table<TT> &tt, uint8_t var_index)¶ Swaps two adjacent variables in a truth table.
The function swaps variable
var_index
withvar_index + 1
. The function will changett
in-place. Iftt
should not be changed, one can useswap_adjacent
instead.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT>
inline TT swap_adjacent(const TT &tt, uint8_t var_index)¶ Swaps two adjacent variables in a truth table.
The function swaps variable
var_index
withvar_index + 1
. The function will return a new truth table with the result.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_inplace(TT &tt, uint8_t var_index1, uint8_t var_index2)¶ Swaps two variables in a truth table.
The function swaps variable
var_index1
withvar_index2
. The function will changett
in-place. Iftt
should not be changed, one can useswap
instead.- Parameters
tt – Truth table
var_index1 – First variable
var_index2 – Second variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_inplace(ternary_truth_table<TT> &tt, uint8_t var_index1, uint8_t var_index2)¶ Swaps two variables in a truth table.
The function swaps variable
var_index1
withvar_index2
. The function will changett
in-place. Iftt
should not be changed, one can useswap
instead.- Parameters
tt – Ternary truth table
var_index1 – First variable
var_index2 – Second variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void swap_inplace(quaternary_truth_table<TT> &tt, uint8_t var_index1, uint8_t var_index2)¶ Swaps two variables in a truth table.
The function swaps variable
var_index1
withvar_index2
. The function will changett
in-place. Iftt
should not be changed, one can useswap
instead.- Parameters
tt – Ternary truth table
var_index1 – First variable
var_index2 – Second variable
-
template<typename TT>
inline TT swap(const TT &tt, uint8_t var_index1, uint8_t var_index2)¶ Swaps two adjacent variables in a truth table.
The function swaps variable
var_index1
withvar_index2
. The function will return a new truth table with the result.- Parameters
tt – Truth table
var_index1 – First variable
var_index2 – Second variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void flip_inplace(TT &tt, uint8_t var_index)¶ Flips a variable in a truth table.
The function flips variable
var_index
intt
. The function will changett
in-place. Iftt
should not be changed, one can useflip
instead.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void flip_inplace(ternary_truth_table<TT> &tt, uint8_t var_index)¶ Flips a variable in a ternary truth table.
The function flips variable
var_index
intt
. The function will changett
in-place. Iftt
should not be changed, one can useflip
instead.- Parameters
tt – Ternary truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void flip_inplace(quaternary_truth_table<TT> &tt, uint8_t var_index)¶ Flips a variable in a ternary truth table.
The function flips variable
var_index
intt
. The function will changett
in-place. Iftt
should not be changed, one can useflip
instead.- Parameters
tt – Ternary truth table
var_index – A variable
-
template<typename TT>
inline TT flip(const TT &tt, uint8_t var_index)¶ Flips a variable in a truth table.
The function flips variable
var_index
intt
. The function will not changett
and return the result as a copy.- Parameters
tt – Truth table
var_index – A variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
std::vector<uint8_t> min_base_inplace(TT &tt)¶ Reorders truth table to have minimum base.
This function will reorder variables, such that there are no “holes”. For example, the function \( x_0 \land x_2 \) will be changed to \( x_0 \land x_1 \) by swapping \( x_1 \) with \( x_2 \). That is all variables that are not in the functional support will be moved to the back. Note that the size of the truth table is not changed, because for
static_truth_table
one cannot compute it at compile-time.The function changes the truth table and returns a vector with all variable indexes that were in the functional support of the original function.
- Parameters
tt – Truth table
-
template<typename TT>
void expand_inplace(TT &tt, const std::vector<uint8_t> &support)¶ Expands truth table from minimum base to original based on support.
This is the inverse operation to
min_base_inplace
, where the support is used to swap variables back to their original positions.- Parameters
tt – Truth table
support – Original indexes of support variables
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void extend_to_inplace(TT &tt, const TTFrom &from)¶ Extends smaller truth table to larger one.
The most significant variables will not be in the functional support of the resulting truth table, but the method is helpful to align a truth table when being used with another one.
- Parameters
tt – Larger truth table to create
from – Smaller truth table to copy from
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void extend_to_inplace(ternary_truth_table<TT> &tt, const ternary_truth_table<TTFrom> &from)¶ Extends smaller ternary truth table to larger one.
The most significant variables will not be in the functional support of the resulting truth table, but the method is helpful to align a truth table when being used with another one.
- Parameters
tt – Larger ternary truth table to create
from – Smaller ternary truth table to copy from
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void extend_to_inplace(quaternary_truth_table<TT> &tt, const quaternary_truth_table<TTFrom> &from)¶ Extends smaller ternary truth table to larger one.
The most significant variables will not be in the functional support of the resulting truth table, but the method is helpful to align a truth table when being used with another one.
- Parameters
tt – Larger ternary truth table to create
from – Smaller ternary truth table to copy from
-
template<uint32_t NumVars, typename TTFrom>
inline static_truth_table<NumVars> extend_to(const TTFrom &from)¶ Extends smaller truth table to larger static one.
This is an out-of-place version of
extend_to_inplace
that has the truth table as a return value. It only works for creating static truth tables. The template parameterNumVars
must be equal or larger to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline dynamic_truth_table extend_to(const TTFrom &from, unsigned num_vars)¶ Extends smaller truth table to larger dynamic one.
This is an out-of-place version of
extend_to_inplace
that has the truth table as a return value. It only works for creating dynamic truth tables. The parameternum_vars
must be equal or larger to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline ternary_truth_table<TTFrom> extend_to(const ternary_truth_table<TTFrom> &from, unsigned num_vars)¶ Extends smaller ternary truth table to larger one of the same underlying type.
This is an out-of-place version of
extend_to_inplace
that has the truth table as a return value. It only works for creating dynamic truth tables. The parameternum_vars
must be equal or larger to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline quaternary_truth_table<TTFrom> extend_to(const quaternary_truth_table<TTFrom> &from, unsigned num_vars)¶ Extends smaller ternary truth table to larger one of the same underlying type.
This is an out-of-place version of
extend_to_inplace
that has the truth table as a return value. It only works for creating dynamic truth tables. The parameternum_vars
must be equal or larger to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void shrink_to_inplace(TT &tt, const TTFrom &from)¶ Shrinks larger truth table to smaller one.
The function expects that the most significant bits, which are cut off, are not in the functional support of the original function. Only then it is ensured that the resulting function is equivalent.
- Parameters
tt – Smaller truth table to create
from – Larger truth table to copy from
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void shrink_to_inplace(ternary_truth_table<TT> &tt, const ternary_truth_table<TTFrom> &from)¶ Shrinks larger ternary truth table to smaller one.
The function expects that the most significant bits, which are cut off, are not in the functional support of the original function. Only then it is ensured that the resulting function is equivalent.
- Parameters
tt – Smaller ternary truth table to create
from – Larger ternary truth table to copy from
-
template<typename TT, typename TTFrom, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
void shrink_to_inplace(quaternary_truth_table<TT> &tt, const quaternary_truth_table<TTFrom> &from)¶ Shrinks larger ternary truth table to smaller one.
The function expects that the most significant bits, which are cut off, are not in the functional support of the original function. Only then it is ensured that the resulting function is equivalent.
- Parameters
tt – Smaller ternary truth table to create
from – Larger ternary truth table to copy from
-
template<uint32_t NumVars, typename TTFrom>
inline static_truth_table<NumVars> shrink_to(const TTFrom &from)¶ Shrinks larger truth table to smaller static one.
This is an out-of-place version of
shrink_to
that has the truth table as a return value. It only works for creating static truth tables. The template parameterNumVars
must be equal or smaller to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline dynamic_truth_table shrink_to(const TTFrom &from, unsigned num_vars)¶ Shrinks larger truth table to smaller dynamic one.
This is an out-of-place version of
shrink_to
that has the truth table as a return value. It only works for creating dynamic tables. The parameternum_vars
must be equal or smaller to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline ternary_truth_table<TTFrom> shrink_to(const ternary_truth_table<TTFrom> &from, unsigned num_vars)¶ Shrinks larger ternary truth table to smaller one of the same underlying type.
This is an out-of-place version of
shrink_to
that has the truth table as a return value. It only works for creating dynamic tables. The parameternum_vars
must be equal or smaller to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TTFrom>
inline quaternary_truth_table<TTFrom> shrink_to(const quaternary_truth_table<TTFrom> &from, unsigned num_vars)¶ Shrinks larger ternary truth table to smaller one of the same underlying type.
This is an out-of-place version of
shrink_to
that has the truth table as a return value. It only works for creating dynamic tables. The parameternum_vars
must be equal or smaller to the number of variables infrom
.- Parameters
from – Smaller truth table to copy from
-
template<typename TT>
void shift_left_inplace(TT &tt, uint64_t shift)¶ Left-shift truth table.
Drops overflowing most-significant bits and fills up least-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline void shift_left_inplace(ternary_truth_table<TT> &tt, uint64_t shift)¶ Left-shift ternary truth table.
Drops overflowing most-significant bits and fills up least-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline void shift_left_inplace(quaternary_truth_table<TT> &tt, uint64_t shift)¶ Left-shift quaternary truth table.
Drops overflowing most-significant bits and fills up least-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline TT shift_left(const TT &tt, uint64_t shift)¶ Left-shift truth table.
Out-of-place variant of
shift_left_inplace
.- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
void shift_right_inplace(TT &tt, uint64_t shift)¶ Right-shift truth table.
Drops overflowing least-significant bits and fills up most-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline void shift_right_inplace(ternary_truth_table<TT> &tt, uint64_t shift)¶ Right-shift ternary truth table.
Drops overflowing most-significant bits and fills up least-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline void shift_right_inplace(quaternary_truth_table<TT> &tt, uint64_t shift)¶ Right-shift quaternary truth table.
Drops overflowing most-significant bits and fills up least-significant bits with zeroes.
- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<typename TT>
inline TT shift_right(const TT &tt, uint64_t shift)¶ Right-shift truth table.
Out-of-place variant of
shift_right_inplace
.- Parameters
tt – Truth table
shift – Number of bits to shift
-
template<class TTf, class TTv, typename = std::enable_if_t<is_complete_truth_table<TTf>::value>>
inline auto compose_truth_table(const TTf &f, const std::vector<TTv> &vars)¶ Composes a truth table.
Given a function
f
, and a set of truth tables as arguments, computes the composed truth table. For example, iff(x1, x2) = 1001
andvars = {x1 = 1001, x2= 1010}
, the function returns 1100. This function can be regarded as a general operator with arityvars.size()
where the behavior of the operator is given by f.- Parameters
f – The outer function
vars – The ordered set of input variables
- Returns
The composed truth table with vars.size() variables
-
template<class TTf, class TTv, typename = std::enable_if_t<is_complete_truth_table<TTf>::value>>
inline auto compose_truth_table(const ternary_truth_table<TTf> &f, const std::vector<ternary_truth_table<TTv>> &vars)¶ Composes a truth table.
Given a function
f
, and a set of truth tables as arguments, computes the composed truth table. For example, iff(x1, x2) = 1001
andvars = {x1 = 1001, x2= 1010}
, the function returns 1000. In case of don’t cares this method treats them as “don’t knows”. For example, iff(x1, x2) = 1-00
andvars = {x1 = 1001, x2= 1010}
, the function returns 100-. For example, iff(x1, x2) = 1-00
andvars = {x1 = 1001, x2= -010}
, the function returns -00-. However, iff(x1, x2) = 1100
andvars = {x1 = 1001, x2= -010}
, the function returns 1001.This function does not support truth quaternary table with more than 6 variables.
- Parameters
f – The outer function
vars – The ordered set of input variables
- Returns
The composed truth table with vars.size() variables
-
template<class TTf, class TTv, typename = std::enable_if_t<is_complete_truth_table<TTf>::value>>
inline auto compose_truth_table(const quaternary_truth_table<TTf> &f, const std::vector<quaternary_truth_table<TTv>> &vars)¶ Composes a truth table.
Given a function
f
, and a set of truth tables as arguments, computes the composed truth table. For example, iff(x1, x2) = 1001
andvars = {x1 = 1001, x2= 1010}
, the function returns 1000. For example, iff(x1, x2) = 1-00
andvars = {x1 = 1001, x2= 1010}
, the function returns 100-. For example, iff(x1, x2) = 1-00
andvars = {x1 = 1001, x2= -010}
, the function returns 100-. Iff(x1, x2) = 1100
andvars = {x1 = 1x01, x2= -01x}
, the function returns 1x01.This function does not support truth quaternary table with more than 6 variables.
- Parameters
f – The outer function
vars – The ordered set of input variables
- Returns
The composed truth table with vars.size() variables
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
inline void shift_with_mask_inplace(TT &f, uint8_t mask)¶ Shifts a small truth table with respect to a mask.
This function only works for truth tables with up to 6 inputs. The function rearranges the variables according to a mask. For example, assume the 3-input truth table \( x_0 \land x_1 \), which is not defined on \( x_2 \). Applying this funtion with a mask
0b101
yields the function \( x_0 \land x_2 \), and the mask0b110
yields the function \( x_1 \land x_2 \). The bits in the mask provide the new positions. It is important that the positions in the mask do not exceed the truth table size, since all operations are performed in-place and cannot change the number of variables of the truth table.- Parameters
tt – Truth table
mask – Shift mask
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
inline void shift_with_mask_inplace(ternary_truth_table<TT> &f, uint8_t mask)¶ Shifts a small truth table with respect to a mask.
This function only works for truth tables with up to 6 inputs. The function rearranges the variables according to a mask. For example, assume the 3-input truth table \( x_0 \land x_1 \), which is not defined on \( x_2 \). Applying this funtion with a mask
0b101
yields the function \( x_0 \land x_2 \), and the mask0b110
yields the function \( x_1 \land x_2 \). The bits in the mask provide the new positions. It is important that the positions in the mask do not exceed the truth table size, since all operations are performed in-place and cannot change the number of variables of the truth table. The final result will not contain don’t cares, they are all turned into 0s.- Parameters
tt – Truth table
mask – Shift mask
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
inline void shift_with_mask_inplace(quaternary_truth_table<TT> &f, uint8_t mask)¶
-
template<class TT>
inline TT shift_with_mask(const TT &f, uint8_t mask)¶ Shifts a small truth table with respect to a mask.
Out-of-place variant of
shift_with_mask_inplace
.- Parameters
tt – Truth table
mask – Shift mask
-
inline dynamic_truth_table operator~(const dynamic_truth_table &tt)¶
Operator for unary_not.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator~(const static_truth_table<NumVars> &tt)¶ Operator for unary_not.
-
inline partial_truth_table operator~(const partial_truth_table &tt)¶
Operator for unary_not.
-
template<typename TT>
inline ternary_truth_table<TT> operator~(const ternary_truth_table<TT> &tt)¶ Operator for unary_not.
-
template<typename TT>
inline quaternary_truth_table<TT> operator~(const quaternary_truth_table<TT> &tt)¶ Operator for unary_not.
-
inline dynamic_truth_table operator&(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_and.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator&(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_and.
-
inline partial_truth_table operator&(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_and.
-
template<typename TT>
inline ternary_truth_table<TT> operator&(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_and.
-
template<typename TT>
inline quaternary_truth_table<TT> operator&(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_and.
-
inline void operator&=(dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_and and assign.
-
template<uint32_t NumVars>
inline void operator&=(static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_and and assign.
-
inline void operator&=(partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_and and assign.
-
template<typename TT>
inline void operator&=(ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_and and assign.
-
template<typename TT>
inline void operator&=(quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_and and assign.
-
inline dynamic_truth_table operator|(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_or.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator|(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_or.
-
inline partial_truth_table operator|(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_or.
-
template<typename TT>
inline ternary_truth_table<TT> operator|(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_or.
-
template<typename TT>
inline quaternary_truth_table<TT> operator|(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_or.
-
inline void operator|=(dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_or and assign.
-
template<uint32_t NumVars>
inline void operator|=(static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_or and assign.
-
inline void operator|=(partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_or and assign.
-
template<typename TT>
inline void operator|=(ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_or and assign.
-
template<typename TT>
inline void operator|=(quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_or and assign.
-
inline dynamic_truth_table operator^(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_xor.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator^(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_xor.
-
inline partial_truth_table operator^(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_xor.
-
template<typename TT>
inline ternary_truth_table<TT> operator^(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_xor.
-
template<typename TT>
inline quaternary_truth_table<TT> operator^(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_xor.
-
inline void operator^=(dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for binary_xor and assign.
-
template<uint32_t NumVars>
inline void operator^=(static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for binary_xor and assign.
-
inline void operator^=(partial_truth_table &first, const partial_truth_table &second)¶
Operator for binary_xor and assign.
-
template<typename TT>
inline void operator^=(ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for binary_xor and assign.
-
template<typename TT>
inline void operator^=(quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for binary_xor and assign.
-
inline bool operator==(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for equal.
-
template<uint32_t NumVars>
inline bool operator==(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for equal.
-
inline bool operator==(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for equal.
-
template<typename TT>
inline bool operator==(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for equal.
-
template<typename TT>
inline bool operator==(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for equal.
-
inline bool operator!=(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for not equals (!equal)
-
template<uint32_t NumVars>
inline bool operator!=(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for not equals (!equal)
-
inline bool operator!=(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for not equal.
-
template<typename TT>
inline bool operator!=(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for not equals (!equal)
-
template<typename TT>
inline bool operator!=(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for not equals (!equal)
-
inline bool operator<(const dynamic_truth_table &first, const dynamic_truth_table &second)¶
Operator for less_than.
-
template<uint32_t NumVars>
inline bool operator<(const static_truth_table<NumVars> &first, const static_truth_table<NumVars> &second)¶ Operator for less_than.
-
inline bool operator<(const partial_truth_table &first, const partial_truth_table &second)¶
Operator for less_than.
-
template<typename TT>
inline bool operator<(const ternary_truth_table<TT> &first, const ternary_truth_table<TT> &second)¶ Operator for less_than.
-
template<typename TT>
inline bool operator<(const quaternary_truth_table<TT> &first, const quaternary_truth_table<TT> &second)¶ Operator for less_than.
-
inline dynamic_truth_table operator<<(const dynamic_truth_table &tt, uint64_t shift)¶
Operator for left_shift.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator<<(const static_truth_table<NumVars> &tt, uint64_t shift)¶ Operator for left_shift.
-
inline partial_truth_table operator<<(const partial_truth_table &tt, uint64_t shift)¶
Operator for left_shift.
-
template<typename TT>
inline ternary_truth_table<TT> operator<<(const ternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for left_shift.
-
template<typename TT>
inline quaternary_truth_table<TT> operator<<(const quaternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for left_shift.
-
inline void operator<<=(dynamic_truth_table &tt, uint64_t shift)¶
Operator for left_shift_inplace.
-
template<uint32_t NumVars>
inline void operator<<=(static_truth_table<NumVars> &tt, uint64_t shift)¶ Operator for left_shift_inplace.
-
inline void operator<<=(partial_truth_table &tt, uint64_t shift)¶
Operator for left_shift_inplace.
-
template<typename TT>
inline void operator<<=(ternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for left_shift_inplace.
-
template<typename TT>
inline void operator<<=(quaternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for left_shift_inplace.
-
inline dynamic_truth_table operator>>(const dynamic_truth_table &tt, uint64_t shift)¶
Operator for right_shift.
-
template<uint32_t NumVars>
inline static_truth_table<NumVars> operator>>(const static_truth_table<NumVars> &tt, uint64_t shift)¶ Operator for right_shift.
-
inline partial_truth_table operator>>(const partial_truth_table &tt, uint64_t shift)¶
Operator for right_shift.
-
template<typename TT>
inline ternary_truth_table<TT> operator>>(const ternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for right_shift.
-
template<typename TT>
inline quaternary_truth_table<TT> operator>>(const quaternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for right_shift.
-
inline void operator>>=(dynamic_truth_table &tt, uint64_t shift)¶
Operator for right_shift_inplace.
-
template<uint32_t NumVars>
inline void operator>>=(static_truth_table<NumVars> &tt, uint64_t shift)¶ Operator for right_shift_inplace.
-
inline void operator>>=(partial_truth_table &tt, uint64_t shift)¶
Operator for right_shift_inplace.
-
template<typename TT>
inline void operator>>=(ternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for right_shift_inplace.
-
template<typename TT>
inline void operator>>=(quaternary_truth_table<TT> &tt, uint64_t shift)¶ Operator for right_shift_inplace.
-
template<typename TT>
inline void delta_swap_inplace(TT &tt, uint64_t delta, const TT &omega)¶ Applies delta-swap operation.
The delta-swap operation swaps all position pairs \((i, i+\delta)\), for which \(\omega\) is set 1 at position \(i\).
See also Eq. 7.1.3-(69) in The Art of Computer Programming.
- Parameters
tt – Truth table
delta – Index distance delta
omega – Enable mask
-
template<typename TT>
TT delta_swap(const TT &tt, uint64_t delta, const TT &omega)¶ Applies delta-swap operation.
Out-of-place variant for
delta_swap_inplace
.
-
template<typename TT>
void permute_with_masks_inplace(TT &tt, const std::vector<TT> &masks)¶ Permutes a truth table using a sequence of delta-swaps.
Masks is an array containing the \(\omega\) masks. The \(\delta\) values are chosen as increasing and decreasing powers of 2, as described in Eq. 7.1.3-(71) of The Art of Computer Programming.
- Parameters
tt – Truth table
masks – Array of omega-masks
-
template<typename TT>
TT permute_with_masks(const TT &tt, const std::vector<TT> &masks)¶ Permutes a truth table using a sequence of delta-swaps.
Out-of-place variant of
permute_with_masks_inplace
.
-
template<typename TT>
std::vector<TT> compute_permutation_masks(const TT &tt, const std::vector<uint32_t> &permutation)¶ Computes permutation bitmasks.
These bitmasks can be used with the
permute_with_masks
algorithm. The algorithm to compute these masks is described in The Art of Computer Programming, Section 7.1.3 ‘Bit permutation in general’.The input truth table can be arbitrary but is used to determine the type and size of of the returned permutation masks.
- Parameters
tt – Base truth table to derive types and size
permutation – Permutation
-
template<typename TT>
void print_binary(const TT &tt, std::ostream &os = std::cout)¶ Prints truth table in binary representation.
The most-significant bit will be the first character of the string.
- Parameters
tt – Truth table
os – Output stream
-
template<typename TT>
void print_binary(const ternary_truth_table<TT> &tt, std::ostream &os = std::cout)¶
-
template<typename TT>
void print_binary(const quaternary_truth_table<TT> &tt, std::ostream &os = std::cout)¶
-
template<typename TT>
void print_kmap(const TT &tt, std::ostream &os = std::cout)¶ Prints K-map of given truth table.
Columns represent the values of the least significant variables, rows of the most significant ones.
- Parameters
tt – Truth table
os – Output stream (default = cout)
-
template<typename TT, typename = std::enable_if_t<is_completely_specified_truth_table<TT>::value>>
void print_hex(const TT &tt, std::ostream &os = std::cout)¶ Prints truth table in hexadecimal representation.
The most-significant bit will be the first character of the string.
- Parameters
tt – Truth table
os – Output stream
-
template<typename TT, typename = std::enable_if_t<!std::is_same<TT, ternary_truth_table<dynamic_truth_table>>::value>>
void print_raw(const TT &tt, std::ostream &os)¶ Prints truth table in raw binary presentation (for file I/O)
This function is useful to store large truth tables in binary files or
std::stringstream
. Each word is stored into 8 characters.- Parameters
tt – Truth table
os – Output stream
-
template<typename TT>
inline std::string to_binary(const TT &tt)¶ Returns truth table as a string in binary representation.
Calls
print_binary
internally on a string stream.- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_completely_specified_truth_table<TT>::value>>
inline std::string to_hex(const TT &tt)¶ Returns truth table as a string in hexadecimal representation.
Calls
print_hex
internally on a string stream.- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<!std::is_same<TT, partial_truth_table>::value>, typename = std::enable_if_t<is_completely_specified_truth_table<TT>::value>>
void print_xmas_tree_for_function(const TT &tt, std::ostream &os = std::cout)¶ Prints minterms of a Boolean function in christmas tree pattern.
This function prints all minterms of a Boolean function and arranges them according to the christmas tree pattern as described in Section 7.2.1.6 in The Art of Computer Programming by Donald E. Knuth. Minterms from the off-set are printed in red, minterms from the on-set are printed in green.
- Parameters
tt – Truth table
os – Output stream
-
template<class TT>
void print_xmas_tree_for_functions(uint32_t num_vars, const std::vector<std::pair<std::function<bool(TT const&)>, std::vector<int>>> &style_predicates = {}, std::ostream &os = std::cout)¶ Prints all Boolean functions of n variables in christmas tree pattern.
This function prints all Boolean functions of n variables and arranges them according to the christmas tree pattern as described in Section 7.2.1.6 in The Art of Computer Programming by Donald E. Knuth. Functions can be printed in different styles according to some properties.
- Parameters
tt – Number of variables
style_predicates – Each pair has a predicate
bool(TT const&)
to check whether a certain property holds for the truth table the element in the tree represents. If this predicate evaluates to true, then the second element in the pair are indexes of style (ANSI term) to change the string in the output.os – Output stream
-
template<typename TT, typename = std::enable_if_t<!std::is_same<TT, partial_truth_table>::value>>
std::string anf_to_expression(const TT &anf)¶ Creates an expression for an ANF form.
- Parameters
anf – Truth table in ANF encoding
-
template<typename TT, typename = std::enable_if_t<!std::is_same<TT, partial_truth_table>::value>>
std::string anf_to_expression(const ternary_truth_table<TT> &anf)¶ Creates an expression for an ANF form.
All don’t cares are considered to be zero.
It is a “restricted” ANF for the ternary turth table.
- Parameters
anf – Ternary truth table in ANF encoding
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
std::pair<uint32_t, std::vector<uint32_t>> chow_parameters(const TT &tt)¶ Returns the Chow parameter of a function The Chow parameters is a set of values \(N(f), \Sigma(f)\), where \(N(f)\) is the size of the ON-set, and \(\Sigma(f)\) is the sum of all input assignments in the ON-set. For example for \(f = x_1 \lor x_2\) the function returns \((3, (2,2))\).
- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool is_canalizing(const TT &tt)¶ Checks whether a function is canalizing.
- Parameters
tt – Truth table
-
template<typename TT>
bool is_horn(const TT &tt)¶ Checks whether a function is Horn A function is Horn, if it can be represented using Horn clauses.
- Parameters
tt – Truth table
-
template<typename TT>
bool is_krom(const TT &tt)¶ Checks whether a function is Krom A function is Krom, if it can be represented using Krom clauses.
- Parameters
tt – Truth table
-
template<typename TT>
bool is_symmetric_in(const TT &tt, uint8_t var_index1, uint8_t var_index2)¶ Checks whether a function is symmetric in a pair of variables A function is symmetric in two variables, if it is invariant to swapping them.
- Parameters
tt – Truth table
var_index1 – Index of first variable
var_index2 – Index of second variable
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool is_monotone(const TT &tt)¶ Checks whether a function is monotone A function is monotone if f(x) ≤ f(y) whenever x ⊆ y.
- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool is_selfdual(const TT &tt)¶ Checks whether a function is selfdual A function is selfdual if !f(x, y, …, z) = f(!x, !y, …, !z)
- Parameters
tt – Truth table
-
template<typename TT>
bool is_normal(const TT &tt)¶ Checks if a function is normal A function is normal iff f(0, …, 0) = 0.
- Parameters
tt – Truth table
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool is_trivial(const TT &tt)¶ Checks if a function is trivial A function is trival if it is equal to (or the complement of) a variable or constant zero.
- Parameters
tt – Truth table
-
template<typename TT, typename Fn>
void foreach_runlength(const TT &tt, Fn &&fn)¶ Generate runlength encoding of a function This function iterates through the bits of a function and calls a function for each runlength and value. For example, if this function is called for the AND function 1000, it will call
fn
first with argumentsfalse
and3
, and then a second time with argumentstrue
, and1
.- Parameters
tt – Truth table
fn – Function of signature
void(bool, uint32_t)
-
template<typename TT>
std::vector<uint32_t> runlength_pattern(const TT &tt)¶ Returns the runlength encoding pattern of a function This function does only count the lengths, e.g., for 1000 it will return
{3, 1}
, and so it does for the NAND function 0111.- Parameters
tt – Truth table
-
template<typename TT>
inline uint32_t polynomial_degree(const TT &tt)¶ Compute polynomial degree The polyomial degree is the number of variables in the largest monomial in the functoons ANF (PPRM).
- Parameters
tt – Truth table
-
template<typename TT>
inline uint64_t absolute_distinguishing_power(const TT &tt)¶ Returns the absolute distinguishing power of a function The absolute distinguishing power of a function f is the number of distinguishing bit pair {i,j} such that f(i) != f(j).
- Parameters
tt – Truth table
-
template<typename TT>
inline uint64_t relative_distinguishing_power(const TT &tt, const TT &target_tt)¶ Returns the relative distinguishing power of a function wrt. to a target function Quantifies the number of distinguishing bit pairs in the target function that can be distinguished by another function.
- Parameters
tt – Truth table of function
target_tt – Truth table of target function
-
template<typename TT>
bool is_covered_with_divisors(TT const &target, std::vector<TT> const &divisors)¶ Return true iff each distinguishing bit pair of the target function is also distinguishable by the divisor functions.
- Parameters
target – Truth table of the target functions
divisors – Truth tables of the divisor functions
-
template<typename TT, typename Callback = decltype(detail::exact_spectral_canonization_null_callback)>
inline TT exact_spectral_canonization(const TT &tt, Callback &&fn = detail::exact_spectral_canonization_null_callback)¶ Exact spectral canonization.
The function can be passed as second argument a callback that is called with a vector of spectral operations necessary to transform the input function into the representative.
- Parameters
tt – Truth table
fn – Callback to retrieve list of transformations (optional)
-
template<typename TT, typename Callback = decltype(detail::exact_spectral_canonization_null_callback)>
inline std::pair<TT, bool> exact_spectral_canonization_limit(const TT &tt, unsigned step_limit, Callback &&fn = detail::exact_spectral_canonization_null_callback)¶ Exact spectral canonization (with recursion limit)
This function gets as additional argument a recursion limit. The canonization is stopped once this limit is reached and the current representative at this point is being returned. The return value is a pair, where the first entry is the representative, and the second entry indicates whether the solution is known to be exact or not.
A function can be passed as second argument that is callback called with a vector of spectral operations necessary to transform the input function into the representative.
- Parameters
tt – Truth table
limit – Recursion limit
fn – Callback to retrieve list of transformations (optional)
-
template<typename TT, typename Callback = decltype(detail::exact_spectral_canonization_null_callback)>
inline TT hybrid_exact_spectral_canonization(const TT &tt, Callback &&fn = detail::exact_spectral_canonization_null_callback)¶ Exact spectral canonization (with Reed-Muller preprocessor)
A function can be passed as second argument that is callback called with a vector of spectral operations necessary to transform the input function into the representative.
The algorithm is based on the paper: M. Soeken, E. Testa, D.M. Miller: A hybrid spectral method for checking Boolean function equivalence, PACRIM 2019.
- Parameters
tt – Truth table
fn – Callback to retrieve list of transformations (optional)
-
template<typename TT>
inline void print_spectrum(const TT &tt, std::ostream &os = std::cout)¶ Print spectral representation of a function in RW order.
- Parameters
tt – Truth table
os – Output stream
-
template<typename TT>
inline std::vector<int32_t> rademacher_walsh_spectrum(const TT &tt)¶ Returns the Rademacher-Walsh spectrum of a truth table.
The order of coefficients is in the same order as input assignments to the truth table.
- Parameters
tt – Truth table
-
template<typename TT>
inline std::vector<int32_t> autocorrelation_spectrum(const TT &tt)¶ Returns the autocorrelation spectrum of a truth table.
The autocorrelation spectrum gives an indication of the imbalance of all first order derivates of a Boolean function.
The spectral coefficient \(r(x)\) for input \(x \in \{0,1\}^n\) is computed by \(r(x) = \sum_{y\in\{0,1\}^n}\hat f(y)\hat f(x \oplus y)\), where \(\hat f\) is the \(\{-1,1\}\) encoding of the input function \(f\).
- Parameters
tt – Truth table for input function \(f\)
-
inline std::vector<uint32_t> spectrum_distribution(const std::vector<int32_t> &spectrum)¶
Returns distribution of absolute spectrum coefficients.
This functions returns a vector with \(2^{n-1} + 1\) nonnegative entries, in which the entry at position \(i\) indicates how many coeffecients in the spectum have absolute value \(2i\). The compression is possible, since all spectra in this package have positive coefficients.
- Parameters
spectrum – Spectrum
-
template<typename TT>
inline uint32_t get_spectral_class(const TT &tt)¶ Returns unique index for a spectral equivalence class.
This functions works for functions with up to 5 inputs. It uses the distribution of coefficients in the Rademacher Walsh spectrum, and in case of ambiguity also the coeffcienents in the auto-correlation spectrum. It does not compute the transformation sequences in order to get to the class representative and is therefore faster than canoninization.
- Parameters
tt – Truth table
-
template<class TT>
TT spectral_representative(const TT &func)¶ Returns spectral representative using lookup.
This function returns the spectral representative for functions with up to 5 variables, but does not give the possibility to obtain the transformation sequence to obtain the function from the representative.
func Truth table for function with at most 5 variables.
-
inline std::pair<std::vector<cube>, std::vector<uint64_t>> simple_spp(const std::vector<cube> &esop, uint32_t num_vars)¶
Merges products in an ESOP into pseudo products.
Given, e.g., the two cubes
abc
andabd
, this algorithm will combine them into a single cubeab(c+d)
. The term(c+d)
is stored as a literal in the first argument of the result pair, starting free indexes afternum_vars
. Which literals are used is stored in the second argument of the result pair, as bitpattern over the original inputs.- Parameters
esop – ESOP form
num_vars – Number of variables in ESOP form
-
class cube
-
struct dynamic_truth_table¶
- #include <dynamic_truth_table.hpp>
Truth table in which number of variables is known at runtime.
-
template<typename TT>
struct hash¶ - #include <hash.hpp>
Computes hash values for truth tables.
-
template<class TT>
struct is_complete_truth_table : public false_type¶ Subclassed by kitty::is_complete_truth_table< kitty::quaternary_truth_table< TT > >, kitty::is_complete_truth_table< kitty::ternary_truth_table< TT > >
- template<> dynamic_truth_table > : public true_type
- template<> partial_truth_table > : public false_type
- template<class TT> quaternary_truth_table< TT > > : public kitty::is_complete_truth_table< TT >
- template<uint32_t NumVars> static_truth_table< NumVars > > : public true_type
- template<class TT> ternary_truth_table< TT > > : public kitty::is_complete_truth_table< TT >
-
template<class TT>
struct is_completely_specified_truth_table : public false_type¶
- template<> dynamic_truth_table > : public true_type
- template<> partial_truth_table > : public true_type
- template<class TT> quaternary_truth_table< TT > > : public false_type
- template<uint32_t NumVars> static_truth_table< NumVars > > : public true_type
- template<class TT> ternary_truth_table< TT > > : public false_type
-
template<class TT>
struct is_truth_table : public false_type¶ Subclassed by kitty::is_truth_table< kitty::quaternary_truth_table< TT > >, kitty::is_truth_table< kitty::ternary_truth_table< TT > >
- template<> dynamic_truth_table > : public true_type
- template<> partial_truth_table > : public true_type
- template<class TT> quaternary_truth_table< TT > > : public kitty::is_truth_table< TT >
- template<uint32_t NumVars> static_truth_table< NumVars > > : public true_type
- template<class TT> ternary_truth_table< TT > > : public kitty::is_truth_table< TT >
-
template<typename TT>
class karnaugh_map¶
-
struct partial_truth_table¶
- #include <partial_truth_table.hpp>
Truth table with resizable, arbitrary number of bits
-
template<class TT>
struct quaternary_truth_table¶
-
template<uint32_t NumVars, bool = (NumVars <= 6)>
struct static_truth_table¶ - #include <static_truth_table.hpp>
Truth table in which number of variables is known at compile time.
We dispatch on the Boolean template parameter to distinguish between a small truth table (up to 6 variables) and a large truth table (more than 6 variables). A small truth table fits into a single block and therefore dedicated optimizations are possible.
-
template<uint32_t NumVars>
struct static_truth_table<NumVars, false>¶ - #include <static_truth_table.hpp>
Truth table (more than 6 variables) in which number of variables is known at compile time.
-
template<uint32_t NumVars>
struct static_truth_table<NumVars, true>¶ - #include <static_truth_table.hpp>
Truth table (for up to 6 variables) in which number of variables is known at compile time.
-
template<class TT>
struct ternary_truth_table¶
-
namespace detail¶
Functions
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
bool formula_execute_operation(std::stack<TT> &truth_tables, unsigned const op)¶
-
inline std::vector<uint32_t> enumerate_zs_index(const std::vector<uint32_t> &ys_index, uint32_t max_index)¶
A helper function to enumerate missing indices.
- Parameters
ys_index – A list of already selected indices
max_index – The maximum value for an index
- Returns
Remaining indices
-
template<typename TT>
std::pair<TT, TT> compute_permutation_masks_pair(const TT &tt, std::vector<uint32_t> &left, std::vector<uint32_t> &right, unsigned step)¶
-
inline std::string to_binary(uint16_t value, uint32_t num_vars)¶
-
inline void print_xmas_tree(std::ostream &os, uint32_t num_vars, const std::vector<std::pair<std::function<bool(uint16_t)>, std::vector<int>>> &style_predicates = {})¶
-
inline void fast_hadamard_transform(std::vector<int32_t> &s, bool reverse = false)¶
-
inline std::vector<uint32_t> get_rw_coeffecient_order(uint32_t num_vars)¶
-
inline void exact_spectral_canonization_null_callback(const std::vector<spectral_operation> &operations)¶
Variables
-
static std::vector<uint64_t> spectral_repr[] = {{0x0}, {0x0}, {0x0, 0x8}, {0x00, 0x80, 0x88}, {0x0000, 0x8000, 0x8080, 0x0888, 0x8888, 0x2a80, 0xf888, 0x7888}, {0x00000000, 0x80000000, 0x80008000, 0x00808080, 0x80808080, 0x08888000, 0xaa2a2a80, 0x88080808, 0x2888a000, 0xf7788000, 0xa8202020, 0x08880888, 0xbd686868, 0xaa808080, 0x7e686868, 0x2208a208, 0x08888888, 0x88888888, 0xea404040, 0x2a802a80, 0x73d28c88, 0xea808080, 0xa28280a0, 0x13284c88, 0xa2220888, 0xaae6da80, 0x58d87888, 0x8c88ac28, 0x8880f880, 0x9ee8e888, 0x4268c268, 0x16704c80, 0x78888888, 0x4966bac0, 0x372840a0, 0x5208d288, 0x7ca00428, 0xf8880888, 0x2ec0ae40, 0xf888f888, 0x58362ec0, 0x0eb8f6c0, 0x567cea40, 0xf8887888, 0x78887888, 0xe72890a0, 0x268cea40, 0x6248eac0}}¶
-
template<class TT>
struct anf_spectrum¶
-
template<typename TT>
class miller_spectral_canonization_impl¶
-
struct spectral_operation¶
-
class spectrum¶
-
template<typename TT, typename = std::enable_if_t<is_complete_truth_table<TT>::value>>
-
enum top_decomposition¶