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},
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    let limbs = n.into_repr().into_bigint().0;
67    FieldElement::from(BigInt(limbs))
68}
69
70/// Calculates the degree of the next smallest power of two
71pub const fn next_power_of_two(n: usize) -> usize {
72    let mut power = 1;
73    let mut ans = 0;
74    while power < n {
75        power <<= 1;
76        ans += 1;
77    }
78    ans
79}
80
81/// Pads the vector with 0 so that the number of elements in the vector is a
82/// power of 2
83#[instrument(skip_all)]
84pub fn pad_to_power_of_two<T: Default>(mut witness: Vec<T>) -> Vec<T> {
85    let target_len = 1 << next_power_of_two(witness.len());
86    witness.reserve_exact(target_len - witness.len());
87    while witness.len() < target_len {
88        witness.push(T::default());
89    }
90    witness
91}
92
93/// Pretty print a float using SI-prefixes.
94#[must_use]
95pub fn human(value: f64) -> impl Display {
96    struct Human(f64);
97    impl Display for Human {
98        fn fmt(&self, f: &mut Formatter) -> FmtResult {
99            let log10 = if self.0.is_normal() {
100                self.0.abs().log10()
101            } else {
102                0.0
103            };
104            let si_power = ((log10 / 3.0).floor() as isize).clamp(-10, 10);
105            let value = self.0 * 10_f64.powi((-si_power * 3) as i32);
106            let digits =
107                f.precision().unwrap_or(3) - 1 - 3.0f64.mul_add(-(si_power as f64), log10) as usize;
108            let separator = if f.alternate() { "" } else { "\u{202F}" };
109            if f.width() == Some(6) && digits == 0 {
110                write!(f, " ")?;
111            }
112            write!(f, "{value:.digits$}{separator}")?;
113            let suffix = "qryzafpnμm kMGTPEZYRQ"
114                .chars()
115                .nth((si_power + 10) as usize)
116                .unwrap();
117            if suffix != ' ' || f.width() == Some(6) {
118                write!(f, "{suffix}")?;
119            }
120            Ok(())
121        }
122    }
123    Human(value)
124}
125
126/// Computes multiplicative inverses using Montgomery's batch inversion trick.
127///
128/// Reduces N field inversions to 1 inversion + 3N multiplications.
129/// See: <https://encrypt.a41.io/primitives/abstract-algebra/group/batch-inverse>
130pub fn batch_inverse_montgomery(values: &[FieldElement]) -> Vec<FieldElement> {
131    let batch_size = values.len();
132    if batch_size == 0 {
133        return Vec::new();
134    }
135
136    if batch_size == 1 {
137        return vec![values[0].inverse().expect("Cannot invert zero")];
138    }
139
140    // Forward pass: compute prefix products
141    let mut prefix = Vec::with_capacity(batch_size);
142    let mut acc = FieldElement::from(1u32);
143    for &v in values {
144        acc *= v;
145        prefix.push(acc);
146    }
147
148    // Invert the total product (single expensive operation)
149    let mut inv_acc = prefix[batch_size - 1]
150        .inverse()
151        .expect("Batch inversion: zero product");
152
153    // Backward pass: compute individual inverses
154    let mut inverses = vec![FieldElement::from(0u32); batch_size];
155    for i in (1..batch_size).rev() {
156        inverses[i] = inv_acc * prefix[i - 1];
157        inv_acc *= values[i];
158    }
159    inverses[0] = inv_acc;
160
161    inverses
162}
provekit_common/utils/mod.rs

provekit_common/utils/
mod.rs
