bb::plookup::sparse_tables Namespace Reference

Functions
template<uint64_t base, uint64_t num_rotated_bits>
std::array< bb::fr, 2 >	get_sparse_table_with_rotation_values (const std::array< uint64_t, 2 > key)
	Computes the sparse form values for a given key, used as a callback for plookup table queries.
template<uint64_t base, uint64_t bits_per_slice, uint64_t num_rotated_bits>
BasicTable	generate_sparse_table_with_rotation (BasicTableId id, const size_t table_index)
	Generates a BasicTable that maps integers to their sparse form representation, with optional 32-bit rotation.
template<size_t base, const uint64_t * base_table>
std::array< bb::fr, 2 >	get_sparse_normalization_values (const std::array< uint64_t, 2 > key)
	Computes the normalized output for a sparse value based on a provided normalization table.
template<size_t base, uint64_t num_bits, const uint64_t * base_table>
BasicTable	generate_sparse_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing sparse form values back to normal form.

Function Documentation

generate_sparse_normalization_table()

template<size_t base, uint64_t num_bits, const uint64_t * base_table>

BasicTable bb::plookup::sparse_tables::generate_sparse_normalization_table ( BasicTableId  id, const size_t  table_index  )

inline

Generates a BasicTable for normalizing sparse form values back to normal form.

This table converts sparse arithmetic results into actual bit values. Each sparse digit encodes a sum of bits; the normalization table extracts the XOR result (and optionally other Boolean function results like Ch or Maj).

Table structure (base^num_bits many entries):

• C1 (input): All possible sparse values with num_bits digits
• C2 (output): Normalized result where each sparse digit is mapped through base_table
• C3: Unused (always 0)

The num_bits parameter controls how many bits are normalized per lookup. Larger num_bits = fewer lookups needed, but larger table.

Template Parameters

base	The sparse form base
num_bits	Number of sparse digits (= original bits) processed per lookup
base_table	The per-digit normalization table (e.g., choose_normalization_table)

Definition at line 162 of file sparse.hpp.

generate_sparse_table_with_rotation()

template<uint64_t base, uint64_t bits_per_slice, uint64_t num_rotated_bits>

BasicTable bb::plookup::sparse_tables::generate_sparse_table_with_rotation ( BasicTableId  id, const size_t  table_index  )

inline

Generates a BasicTable that maps integers to their sparse form representation, with optional 32-bit rotation.

Sparse form is a representation where each bit of a binary integer is mapped to a coefficient in a higher base. For a binary value with bits b_i ∈ {0,1}, the sparse form is: Σ(b_i * base^i). This representation enables efficient XOR computation in circuits: XOR can be computed by adding sparse representations and then "normalizing" (reducing coefficients modulo 2).

Example with base=7: binary 0b101 (decimal 5) → 7^0 + 7^2 = 1 + 49 = 50

The table has three columns:

• C1: Original input value in range [0, 2^bits_per_slice)
• C2: Sparse form of the input
• C3: Sparse form of the input rotated right by num_rotated_bits (32-bit rotation), or identical to C2 if num_rotated_bits == 0

Step sizes are used when combining multiple lookups to reconstruct larger values:

• column_1_step_size = 2^11 (for combining input slices)
• column_2/3_step_size = base^bits_per_slice (for combining sparse output slices)

Template Parameters

base	The base for sparse representation (e.g., 7 for SHA256 tables)
bits_per_slice	Number of bits per table entry; table size = 2^bits_per_slice
num_rotated_bits	Number of bits to rotate right (0 for no rotation)

Parameters

id	The identifier for this lookup table
table_index	Index of this table in the table registry

Returns

BasicTable The constructed lookup table

Definition at line 80 of file sparse.hpp.

get_sparse_normalization_values()

template<size_t base, const uint64_t * base_table>

std::array< bb::fr, 2 > bb::plookup::sparse_tables::get_sparse_normalization_values ( const std::array< uint64_t, 2 >  key )

inline

Computes the normalized output for a sparse value based on a provided normalization table.

Template Parameters

base	The sparse form base
base_table	The normalization lookup table (maps sparse digit → normalized bit(s))

Parameters

key	The lookup key; key[0] is the sparse input value, key[1] is unused

Returns

{normalized_value, 0} where normalized_value has one output bit per input sparse digit

Definition at line 125 of file sparse.hpp.

get_sparse_table_with_rotation_values()

template<uint64_t base, uint64_t num_rotated_bits>

std::array< bb::fr, 2 > bb::plookup::sparse_tables::get_sparse_table_with_rotation_values ( const std::array< uint64_t, 2 >  key )

inline

Computes the sparse form values for a given key, used as a callback for plookup table queries.

Given an input key, returns:

• t0 (C2): The sparse form of the input
• t1 (C3): The sparse form of the input rotated by num_rotated_bits (or t0 if num_rotated_bits == 0)

Template Parameters

base	The base for sparse representation
num_rotated_bits	Number of bits to rotate right (0 for no rotation)

Parameters

key	Array where key[0] is the input value to convert (key[1] is unused; the array has 2 elements to conform to the standard plookup callback interface)

Returns

{C2, C3} where:

• C2 = sparse(input): the input converted to sparse base form
• C3 = sparse(rotate32(input, num_rotated_bits)): the rotated input in sparse form (equals C2 if num_rotated_bits == 0)

Definition at line 36 of file sparse.hpp.