provekit_common/utils/
mod.rs

1mod print_abi;
2pub mod serde_ark;
3pub mod serde_ark_option;
4pub mod serde_ark_vec;
5pub mod serde_hex;
6pub mod serde_jsonify;
7pub mod sumcheck;
8
9pub use self::print_abi::PrintAbi;
10use {
11    crate::{FieldElement, NoirElement},
12    ark_ff::{BigInt, Field, PrimeField as _},
13    ruint::{aliases::U256, uint},
14    std::{
15        fmt::{Display, Formatter, Result as FmtResult},
16        mem::MaybeUninit,
17    },
18    tracing::instrument,
19};
20
21/// 1/2 for the BN254
22pub const HALF: FieldElement = uint_to_field(uint!(
23    10944121435919637611123202872628637544274182200208017171849102093287904247809_U256
24));
25
26/// Target single-thread workload size for `T`.
27/// Should ideally be a multiple of a cache line (64 bytes)
28/// and close to the L1 cache size (32 KB).
29pub const fn workload_size<T: Sized>() -> usize {
30    const CACHE_SIZE: usize = 1 << 15;
31    CACHE_SIZE / size_of::<T>()
32}
33
34/// Unzip a [[(T,T); N]; M] into ([[T; N]; M],[[T; N]; M]) using move semantics
35// TODO: Cleanup when <https://github.com/rust-lang/rust/issues/96097> lands
36#[allow(unsafe_code)] // Required for `MaybeUninit`
37fn unzip_double_array<T: Sized, const N: usize, const M: usize>(
38    input: [[(T, T); N]; M],
39) -> ([[T; N]; M], [[T; N]; M]) {
40    // Create uninitialized memory for the output arrays
41    let mut left: [[MaybeUninit<T>; N]; M] = [const { [const { MaybeUninit::uninit() }; N] }; M];
42    let mut right: [[MaybeUninit<T>; N]; M] = [const { [const { MaybeUninit::uninit() }; N] }; M];
43
44    // Move results to output arrays
45    for (i, a) in input.into_iter().enumerate() {
46        for (j, (l, r)) in a.into_iter().enumerate() {
47            left[i][j] = MaybeUninit::new(l);
48            right[i][j] = MaybeUninit::new(r);
49        }
50    }
51
52    // Convert the arrays of MaybeUninit into fully initialized arrays
53    // Safety: All the elements have been initialized above
54    let left = left.map(|a| a.map(|u| unsafe { u.assume_init() }));
55    let right = right.map(|a| a.map(|u| unsafe { u.assume_init() }));
56    (left, right)
57}
58
59pub const fn uint_to_field(i: U256) -> FieldElement {
60    FieldElement::new(BigInt(i.into_limbs()))
61}
62
63/// Convert a Noir field element to a native `FieldElement`
64#[inline(always)]
65pub fn noir_to_native(n: NoirElement) -> FieldElement {
66    FieldElement::from(BigInt(n.into_repr().into_bigint().0))
67}
68
69/// Calculates the degree of the next smallest power of two
70pub const fn next_power_of_two(n: usize) -> usize {
71    let mut power = 1;
72    let mut ans = 0;
73    while power < n {
74        power <<= 1;
75        ans += 1;
76    }
77    ans
78}
79
80/// Pads the vector with 0 so that the number of elements in the vector is a
81/// power of 2
82#[instrument(skip_all)]
83pub fn pad_to_power_of_two<T: Default>(mut witness: Vec<T>) -> Vec<T> {
84    let target_len = 1 << next_power_of_two(witness.len());
85    witness.reserve_exact(target_len - witness.len());
86    while witness.len() < target_len {
87        witness.push(T::default());
88    }
89    witness
90}
91
92/// Pretty print a float using SI-prefixes.
93#[must_use]
94pub fn human(value: f64) -> impl Display {
95    struct Human(f64);
96    impl Display for Human {
97        fn fmt(&self, f: &mut Formatter) -> FmtResult {
98            let log10 = if self.0.is_normal() {
99                self.0.abs().log10()
100            } else {
101                0.0
102            };
103            let si_power = ((log10 / 3.0).floor() as isize).clamp(-10, 10);
104            let value = self.0 * 10_f64.powi((-si_power * 3) as i32);
105            let digits =
106                f.precision().unwrap_or(3) - 1 - 3.0f64.mul_add(-(si_power as f64), log10) as usize;
107            let separator = if f.alternate() { "" } else { "\u{202F}" };
108            if f.width() == Some(6) && digits == 0 {
109                write!(f, " ")?;
110            }
111            write!(f, "{value:.digits$}{separator}")?;
112            let suffix = "qryzafpnμm kMGTPEZYRQ"
113                .chars()
114                .nth((si_power + 10) as usize)
115                .unwrap();
116            if suffix != ' ' || f.width() == Some(6) {
117                write!(f, "{suffix}")?;
118            }
119            Ok(())
120        }
121    }
122    Human(value)
123}
124
125/// Computes multiplicative inverses using Montgomery's batch inversion trick.
126///
127/// Reduces N field inversions to 1 inversion + 3N multiplications.
128/// See: <https://encrypt.a41.io/primitives/abstract-algebra/group/batch-inverse>
129pub fn batch_inverse_montgomery(values: &[FieldElement]) -> Vec<FieldElement> {
130    let batch_size = values.len();
131    if batch_size == 0 {
132        return Vec::new();
133    }
134
135    if batch_size == 1 {
136        return vec![values[0].inverse().expect("Cannot invert zero")];
137    }
138
139    // Forward pass: compute prefix products
140    let mut prefix = Vec::with_capacity(batch_size);
141    let mut acc = FieldElement::from(1u32);
142    for &v in values {
143        acc *= v;
144        prefix.push(acc);
145    }
146
147    // Invert the total product (single expensive operation)
148    let mut inv_acc = prefix[batch_size - 1]
149        .inverse()
150        .expect("Batch inversion: zero product");
151
152    // Backward pass: compute individual inverses
153    let mut inverses = vec![FieldElement::from(0u32); batch_size];
154    for i in (1..batch_size).rev() {
155        inverses[i] = inv_acc * prefix[i - 1];
156        inv_acc *= values[i];
157    }
158    inverses[0] = inv_acc;
159
160    inverses
161}
provekit_common/utils/mod.rs

provekit_common/utils/
mod.rs
