bb::scalar_multiplication Namespace Reference

Classes
class	MSM

Functions
void	radix_sort_count_zero_entries (uint64_t *keys, size_t num_entries, uint32_t shift, size_t &num_zero_entries, uint32_t bucket_index_bits, const uint64_t *top_level_keys) noexcept
	Recursive MSD radix sort that also counts entries with zero bucket index.
size_t	sort_point_schedule_and_count_zero_buckets (uint64_t *point_schedule, size_t num_entries, uint32_t bucket_index_bits) noexcept
	Sort point schedule by bucket index and count zero-bucket entries.
template<typename Curve >
Curve::Element	small_mul (const typename MSM< Curve >::MSMData &msm_data) noexcept
template<typename Curve >
Curve::Element	pippenger (PolynomialSpan< const typename Curve::ScalarField > scalars, std::span< const typename Curve::AffineElement > points, bool handle_edge_cases=true) noexcept
	Safe MSM wrapper (defaults to handle_edge_cases=true)
template<typename Curve >
Curve::Element	pippenger_unsafe (PolynomialSpan< const typename Curve::ScalarField > scalars, std::span< const typename Curve::AffineElement > points) noexcept
	Fast MSM wrapper for linearly independent points (no edge case handling)
template curve::Grumpkin::Element	pippenger< curve::Grumpkin > (PolynomialSpan< const curve::Grumpkin::ScalarField > scalars, std::span< const curve::Grumpkin::AffineElement > points, bool handle_edge_cases=true) noexcept
template curve::Grumpkin::Element	pippenger_unsafe< curve::Grumpkin > (PolynomialSpan< const curve::Grumpkin::ScalarField > scalars, std::span< const curve::Grumpkin::AffineElement > points)
template curve::BN254::Element	pippenger< curve::BN254 > (PolynomialSpan< const curve::BN254::ScalarField > scalars, std::span< const curve::BN254::AffineElement > points, bool handle_edge_cases=true)
template curve::BN254::Element	pippenger_unsafe< curve::BN254 > (PolynomialSpan< const curve::BN254::ScalarField > scalars, std::span< const curve::BN254::AffineElement > points)

Variables
constexpr uint32_t	RADIX_BITS = 8
constexpr uint64_t	BUCKET_INDEX_MASK = 0xffffffff

Function Documentation

pippenger()

template<typename Curve >

Curve::Element bb::scalar_multiplication::pippenger ( PolynomialSpan< const typename Curve::ScalarField >  scalars, std::span< const typename Curve::AffineElement >  points, bool  handle_edge_cases  )

noexcept

Safe MSM wrapper (defaults to handle_edge_cases=true)

Definition at line 527 of file scalar_multiplication.cpp.

pippenger< curve::BN254 >()

template curve::BN254::Element bb::scalar_multiplication::pippenger< curve::BN254 >	(	PolynomialSpan< const curve::BN254::ScalarField >	scalars,
		std::span< const curve::BN254::AffineElement >	points,
		bool	handle_edge_cases = true
	)

pippenger< curve::Grumpkin >()

template curve::Grumpkin::Element bb::scalar_multiplication::pippenger< curve::Grumpkin > ( PolynomialSpan< const curve::Grumpkin::ScalarField >  scalars, std::span< const curve::Grumpkin::AffineElement >  points, bool  handle_edge_cases = true  )

noexcept

pippenger_unsafe()

template<typename Curve >

Curve::Element bb::scalar_multiplication::pippenger_unsafe ( PolynomialSpan< const typename Curve::ScalarField >  scalars, std::span< const typename Curve::AffineElement >  points  )

noexcept

Fast MSM wrapper for linearly independent points (no edge case handling)

Definition at line 535 of file scalar_multiplication.cpp.

pippenger_unsafe< curve::BN254 >()

template curve::BN254::Element bb::scalar_multiplication::pippenger_unsafe< curve::BN254 >	(	PolynomialSpan< const curve::BN254::ScalarField >	scalars,
		std::span< const curve::BN254::AffineElement >	points
	)

pippenger_unsafe< curve::Grumpkin >()

template curve::Grumpkin::Element bb::scalar_multiplication::pippenger_unsafe< curve::Grumpkin >	(	PolynomialSpan< const curve::Grumpkin::ScalarField >	scalars,
		std::span< const curve::Grumpkin::AffineElement >	points
	)

radix_sort_count_zero_entries()

void bb::scalar_multiplication::radix_sort_count_zero_entries ( uint64_t *  keys, size_t  num_entries, uint32_t  shift, size_t &  num_zero_entries, uint32_t  bucket_index_bits, const uint64_t *  top_level_keys  )

noexcept

Recursive MSD radix sort that also counts entries with zero bucket index.

Sorts point schedule entries by their bucket index (lower 32 bits) using most-significant-digit radix sort. Processes RADIX_BITS bits per recursive call, starting from the most significant byte. As a side effect, counts entries where bucket_index == 0 (which are skipped during MSM).

Parameters

	keys	Array of point schedule entries to sort in-place (format: point_index << 32 | bucket_index)
	num_entries	Number of entries to sort
	shift	Current bit position to sort on (starts high, decreases by RADIX_BITS each recursion)
[out]	num_zero_entries	Count of entries with bucket_index == 0 (only set at final recursion level)
	bucket_index_bits	Number of bits in the bucket index (used to determine recursion depth)
	top_level_keys	Pointer to original array start; used to detect top-level call for zero counting

Definition at line 14 of file process_buckets.cpp.

small_mul()

template<typename Curve >

Curve::Element bb::scalar_multiplication::small_mul ( const typename MSM< Curve >::MSMData &  msm_data )

noexcept

Definition at line 25 of file scalar_multiplication.cpp.

sort_point_schedule_and_count_zero_buckets()

size_t bb::scalar_multiplication::sort_point_schedule_and_count_zero_buckets ( uint64_t *  point_schedule, size_t  num_entries, uint32_t  bucket_index_bits  )

noexcept

Sort point schedule by bucket index and count zero-bucket entries.

Entry point for radix sort. Sorts entries so that points targeting the same bucket are contiguous, improving cache locality during bucket accumulation. Also counts entries with bucket_index == 0, which represent scalar bits that don't contribute to any bucket in the current Pippenger round.

Parameters

point_schedule	Array of packed entries (point_index << 32 | bucket_index) to sort in-place
num_entries	Number of entries
bucket_index_bits	Number of bits used for bucket indices (determines sort range)

Returns

Number of entries with bucket_index == 0 (these are at the start after sorting)

Definition at line 79 of file process_buckets.cpp.

Variable Documentation

BUCKET_INDEX_MASK

constexpr uint64_t bb::scalar_multiplication::BUCKET_INDEX_MASK = 0xffffffff

constexpr

Definition at line 18 of file process_buckets.hpp.

RADIX_BITS

constexpr uint32_t bb::scalar_multiplication::RADIX_BITS = 8

constexpr

Definition at line 15 of file process_buckets.hpp.