sparse_form.hpp File Reference

#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>
#include "../uint256/uint256.hpp"

Go to the source code of this file.

Classes
class	bb::numeric::sparse_int< base, num_bits >
	Integer type that stores each bit as a separate digit in the given base. Supports addition with single-pass carry propagation. Used to build plookup tables for bitwise operations (XOR, AND) where two sparse_ints are added and the resulting per-digit values encode the operation's truth table. More...

Namespaces
namespace	bb
	Entry point for Barretenberg command-line interface.
namespace	bb::numeric

Functions
std::vector< uint64_t >	bb::numeric::slice_input (const uint256_t &input, const uint64_t base, const size_t num_slices)
	Decompose a uint256_t into digits in the given base (least-significant digit first). If num_slices > 0, returns exactly that many digits. If num_slices == 0, returns as many as needed.
std::vector< uint64_t >	bb::numeric::slice_input_using_variable_bases (const uint256_t &input, const std::vector< uint64_t > &bases)
	Decompose a uint256_t using a different base for each digit position (least-significant first). Throws if the input is too large to be fully represented by the given bases.
template<uint64_t base, uint64_t num_slices>
constexpr std::array< uint256_t, num_slices >	bb::numeric::get_base_powers ()
	Compute [1, base, base^2, ..., base^(num_slices-1)] as uint256_t values.
template<uint64_t base>
constexpr uint256_t	bb::numeric::map_into_sparse_form (const uint64_t input)
	Encode a 32-bit value into sparse form: each binary bit of input becomes a digit in the given base. E.g. with base=3, binary 0b101 becomes 1*3^2 + 0*3^1 + 1*3^0 = 10. Used by plookup tables (SHA256, Keccak, AES, Blake2s) to encode XOR/AND via lookup-friendly representations.
template<uint64_t base>
constexpr uint64_t	bb::numeric::map_from_sparse_form (const uint256_t &input)
	Decode a sparse-form uint256_t back to a 32-bit value. Extracts the base-adic digits from most-significant to least-significant, and recovers the original binary value by reading the low bit of each digit.