Functions
BasicTable	generate_witness_extension_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing witness extension sparse digits.

BasicTable	generate_choose_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing choose sparse digits.

BasicTable	generate_majority_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing majority sparse digits.

MultiTable	get_witness_extension_output_table (const MultiTableId id=SHA256_WITNESS_OUTPUT)
	Constructs a MultiTable for normalizing witness extension sparse results back to normal form.

MultiTable	get_choose_output_table (const MultiTableId id=SHA256_CH_OUTPUT)
	Constructs a MultiTable for normalizing choose sparse results back to normal form.

MultiTable	get_majority_output_table (const MultiTableId id=SHA256_MAJ_OUTPUT)
	Constructs a MultiTable for normalizing majority sparse results back to normal form.

std::array< bb::fr, 3 >	get_majority_rotation_multipliers ()
	Returns multipliers for computing Σ₀(a) rotations in majority_with_sigma0.

std::array< bb::fr, 3 >	get_choose_rotation_multipliers ()
	Returns multipliers for computing Σ₁(e) rotations in choose_with_sigma1.

MultiTable	get_witness_extension_input_table (const MultiTableId id=SHA256_WITNESS_INPUT)
	Constructs a MultiTable for decomposing a 32-bit word for message schedule extension.

MultiTable	get_choose_input_table (const MultiTableId id=SHA256_CH_INPUT)
	Constructs a MultiTable for decomposing e into sparse form and computing rotation components for Σ₁(e).

MultiTable	get_majority_input_table (const MultiTableId id=SHA256_MAJ_INPUT)
	Constructs a MultiTable for decomposing a into sparse form and computing rotation components for Σ₀(a).

Function Documentation

◆ generate_choose_normalization_table()

BasicTable bb::plookup::sha256_tables::generate_choose_normalization_table	(	BasicTableId	id,
		const size_t	table_index
	)

inline

Generates a BasicTable for normalizing choose sparse digits.

Template: <base=28, num_bits=2, choose_normalization_table>. Processes num_bits=2 bits per lookup, giving 28² = 784 table entries. Normalizing 32 bits requires 32/2 = 16 lookups (see get_choose_output_table).

Definition at line 295 of file sha256.hpp.

◆ generate_majority_normalization_table()

BasicTable bb::plookup::sha256_tables::generate_majority_normalization_table	(	BasicTableId	id,
		const size_t	table_index
	)

inline

Generates a BasicTable for normalizing majority sparse digits.

Template: <base=16, num_bits=3, majority_normalization_table>. Processes num_bits=3 bits per lookup, giving 16³ = 4096 table entries. Normalizing 32 bits requires ceil(32/3) = 11 lookups (see get_majority_output_table).

Definition at line 309 of file sha256.hpp.

◆ generate_witness_extension_normalization_table()

BasicTable bb::plookup::sha256_tables::generate_witness_extension_normalization_table	(	BasicTableId	id,
		const size_t	table_index
	)

inline

Generates a BasicTable for normalizing witness extension sparse digits.

Template: <base=16, num_bits=3, witness_extension_normalization_table>. Processes num_bits=3 bits per lookup, giving 16³ = 4096 table entries. Normalizing 32 bits requires ceil(32/3) = 11 lookups (see get_witness_extension_output_table).

Definition at line 281 of file sha256.hpp.

◆ get_choose_input_table()

MultiTable bb::plookup::sha256_tables::get_choose_input_table ( const MultiTableId id = SHA256_CH_INPUT )

inline

Constructs a MultiTable for decomposing e into sparse form and computing rotation components for Σ₁(e).

Table Structure

This table decomposes a 32-bit input into 3 limbs and produces three accumulated outputs:

C1: Normal form accumulator (e = L0 + L1·2¹¹ + L2·2²²)
C2: Sparse form accumulator (e_sparse = S0 + S1·B¹¹ + S2·B²², where B=28)
C3: Rotation accumulator for split-boundary rotations, with L1 correction baked in

Limb structure:

L0: bits 0-10 (11 bits)
L1: bits 11-21 (11 bits)
L2: bits 22-31 (10 bits)

Purpose

Used to compute Σ₁(e) + Ch(e,f,g) for SHA-256

Σ₁(e) = (e>>>6) ^ (e>>>11) ^ (e>>>25)
Ch(e,f,g) = (e & f) ^ (~e & g)

In sparse base-28 form, XOR becomes addition (mod 28 per digit), allowing: e + 7·Σ₁(e) = e_sparse + 7·[(e>>>6) + (e>>>11) + (e>>>25)]

Each rotation is decomposed per-limb. For each limb, rotations either:

Stay contiguous (handled via scalar multiplication by rotation coefficients c0, c1, c2)
Split across the bit-31/0 boundary (handled via lookup table in C3)

Column 3 Correction Term

When computing rotations, we multiply e_sparse by L0's rotation coefficient c0 (see choose_with_sigma1). This gives each limb a coefficient proportional to its position:

L0 gets c0 (correct)
L1 gets B¹¹·c0 (needs a correction to make it equal to c1)
L2 gets B²²·c0 (needs a correction to make it equal to c2)

The L2 correction is handled directly in the choose_with_sigma1 function.

The L1 correction factor δ = c1 - B¹¹·c0 is baked into the C3 accumulator via column_3_coefficients. When C3 is accumulated, it produces: C3[0] = raw[0] + raw[2] + S1 + S1·δ The S1·δ term corrects L1's coefficient from B¹¹·c0 to c1.

Specify the functions defining the rotation to be applied to each of three limbs. This is only for handling the limbs which split across the 31/0-bit boundary when rotated.

table_rotation = SHA256_rotation - limb_start_position

Limb	Start pos	SHA256 rot	Table rot
L0	0	6	6 - 0 = 6
L1	11	11	11 - 11 = 0
L2	22	25	25 - 22 = 3

Definition at line 526 of file sha256.hpp.

◆ get_choose_output_table()

MultiTable bb::plookup::sha256_tables::get_choose_output_table ( const MultiTableId id = SHA256_CH_OUTPUT )

inline

Constructs a MultiTable for normalizing choose sparse results back to normal form.

Allows for normalizing 32 bits using 16 lookups of 2 bits each (32/2 = 16).

Definition at line 344 of file sha256.hpp.

◆ get_choose_rotation_multipliers()

std::array< bb::fr, 3 > bb::plookup::sha256_tables::get_choose_rotation_multipliers ( )

inline

Returns multipliers for computing Σ₁(e) rotations in choose_with_sigma1.

When computing rotations, we multiply e_sparse by c0 (L0's coefficient). This gives L2 a coefficient of B²²·c0, but we need c2. The correction δ = c2 - B²²·c0 is applied to L2's contribution. L1 correction is handled in the input table (see get_choose_input_table).

Returns: {c0, 0, L2_correction} where L2_correction = c2 - 28²²·c0

Definition at line 409 of file sha256.hpp.

◆ get_majority_input_table()

MultiTable bb::plookup::sha256_tables::get_majority_input_table ( const MultiTableId id = SHA256_MAJ_INPUT )

inline

Constructs a MultiTable for decomposing a into sparse form and computing rotation components for Σ₀(a).

Table Structure

This table decomposes a 32-bit input into 3 limbs and produces three accumulated outputs:

C1: Normal form accumulator (a = L0 + L1·2¹¹ + L2·2²²)
C2: Sparse form accumulator (a_sparse = S0 + S1·B¹¹ + S2·B²², where B=16)
C3: Rotation accumulator for split-boundary rotations, with L2 correction baked in

Limb structure:

L0: bits 0-10 (11 bits)
L1: bits 11-21 (11 bits)
L2: bits 22-31 (10 bits)

Purpose

Used to compute Σ₀(a) + Maj(a,b,c) for SHA-256:

Σ₀(a) = (a>>>2) ^ (a>>>13) ^ (a>>>22)
Maj(a,b,c) = (a & b) ^ (a & c) ^ (b & c)

In sparse base-16 form, XOR becomes addition (mod 16 per digit), allowing: a + 4·Σ₀(a) = a_sparse + 4·[(a>>>2) + (a>>>13) + (a>>>22)]

Each rotation is decomposed per-limb. For each limb, rotations either:

Stay contiguous (handled via scalar multiplication by rotation coefficients c0, c1, c2)
Split across the bit-31/0 boundary (handled via lookup table in C3)

Column 3 Correction Term

When computing rotations, we multiply a_sparse by L0's rotation coefficient c0 (see majority_with_sigma0). This gives each limb a coefficient proportional to its position:

L0 gets c0 (correct)
L1 gets B¹¹·c0 (needs a correction to make it equal to c1)
L2 gets B²²·c0 (needs a correction to make it equal to c2)

The L1 correction is handled directly in the majority_with_sigma0 function.

The L2 correction factor δ = c2 - B¹¹·c1 is baked into the C3 accumulator via column_3_coefficients. When C3 is accumulated, it produces: C3[0] = raw[0] + raw[1] + S2 + S2·δ The S2·δ term corrects L2's coefficient.

Specify the functions defining the rotation to be applied to each of three limbs. This is only for handling the limbs which split across the 31/0-bit boundary when rotated.

table_rotation = SHA256_rotation - limb_start_position

Limb	Start pos	SHA256 rot	Table rot
L0	0	2	2 - 0 = 2
L1	11	13	13 - 11 = 2
L2	22	22	22 - 22 = 0

Definition at line 604 of file sha256.hpp.

◆ get_majority_output_table()

MultiTable bb::plookup::sha256_tables::get_majority_output_table ( const MultiTableId id = SHA256_MAJ_OUTPUT )

inline

Constructs a MultiTable for normalizing majority sparse results back to normal form.

Allows for normalizing 32 bits using 11 lookups of 3 bits each (ceil(32/3) = 11).

Definition at line 366 of file sha256.hpp.

◆ get_majority_rotation_multipliers()

std::array< bb::fr, 3 > bb::plookup::sha256_tables::get_majority_rotation_multipliers ( )

inline

Returns multipliers for computing Σ₀(a) rotations in majority_with_sigma0.

When computing rotations, we multiply a_sparse by c0 (L0's coefficient). This gives L1 a coefficient of B¹¹·c0, but we need c1. The correction δ = c1 - B¹¹·c0 is applied to L1's contribution. L2 correction is handled in the input table (see get_majority_input_table).

Returns: {c0, L1_correction, 0} where L1_correction = c1 - 16¹¹·c0

Definition at line 392 of file sha256.hpp.

◆ get_witness_extension_input_table()

MultiTable bb::plookup::sha256_tables::get_witness_extension_input_table ( const MultiTableId id = SHA256_WITNESS_INPUT )

inline

Constructs a MultiTable for decomposing a 32-bit word for message schedule extension.

Table Structure

This table decomposes a 32-bit input into 4 limbs and produces outputs via lookup:

C1: Normal form accumulator (x = L0 + L1·2³ + L2·2¹⁰ + L3·2¹⁸)
C2: Sparse form of each limb (NOT accumulated)
C3: Rotated sparse form for split-boundary corrections (NOT accumulated)

Limb structure (boundaries chosen to work nicely with rotation magnitudes):

L0: bits 0-2 (3 bits)
L1: bits 3-9 (7 bits)
L2: bits 10-17 (8 bits)
L3: bits 18-31 (14 bits)

Purpose

Used to compute the SHA-256 message schedule extension: w[i] = σ₁(w[i-2]) + w[i-7] + σ₀(w[i-15]) + w[i-16] where: σ₀(x) = (x>>>7) ^ (x>>>18) ^ (x>>3) — applied to w[i-15] σ₁(x) = (x>>>17) ^ (x>>>19) ^ (x>>10) — applied to w[i-2]

The same decomposition serves BOTH σ₀ and σ₁, with limb boundaries at 3, 10, 18 aligning with the shift/rotation parameters of both functions.

Specify the functions defining the rotation to be applied to each of three limbs. This is only for handling the limbs which split across the 31/0-bit boundary when rotated. The table handles rotations from both σ₀ and σ₁.

table_rotation = splitting_rotation - limb_start_position

Limb	Start	Splitting rot	Table rot
L0	0	(none)	0 (unused)
L1	3	7 (from σ₀)	7 - 3 = 4
L2	10	17 (from σ₁)	17 - 10 = 7
L3	18	19 (from σ₁)	19 - 18 = 1

Definition at line 445 of file sha256.hpp.

◆ get_witness_extension_output_table()

MultiTable bb::plookup::sha256_tables::get_witness_extension_output_table ( const MultiTableId id = SHA256_WITNESS_OUTPUT )

inline

Constructs a MultiTable for normalizing witness extension sparse results back to normal form.

Allows for normalizing 32 bits using 11 lookups of 3 bits each (ceil(32/3) = 11).

Definition at line 321 of file sha256.hpp.

Functions

Function Documentation

◆ generate_choose_normalization_table()

◆ generate_majority_normalization_table()

◆ generate_witness_extension_normalization_table()

◆ get_choose_input_table()

Table Structure

Purpose

Column 3 Correction Term

◆ get_choose_output_table()

◆ get_choose_rotation_multipliers()

◆ get_majority_input_table()

Table Structure

Purpose

Column 3 Correction Term

◆ get_majority_output_table()

◆ get_majority_rotation_multipliers()

◆ get_witness_extension_input_table()

Table Structure

Purpose

◆ get_witness_extension_output_table()