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},
13    ark_ff_v06::PrimeField as _,
14    ruint::{aliases::U256, uint},
15    std::{
16        fmt::{Display, Formatter, Result as FmtResult},
17        mem::MaybeUninit,
18    },
19    tracing::instrument,
20};
21
22/// 1/2 for the BN254
23pub const HALF: FieldElement = uint_to_field(uint!(
24    10944121435919637611123202872628637544274182200208017171849102093287904247809_U256
25));
26
27/// Target single-thread workload size for `T`.
28/// Should ideally be a multiple of a cache line (64 bytes)
29/// and close to the L1 cache size (32 KB).
30pub const fn workload_size<T: Sized>() -> usize {
31    const CACHE_SIZE: usize = 1 << 15;
32    CACHE_SIZE / size_of::<T>()
33}
34
35/// Unzip a [[(T,T); N]; M] into ([[T; N]; M],[[T; N]; M]) using move semantics
36// TODO: Cleanup when <https://github.com/rust-lang/rust/issues/96097> lands
37#[allow(unsafe_code)] // Required for `MaybeUninit`
38fn unzip_double_array<T: Sized, const N: usize, const M: usize>(
39    input: [[(T, T); N]; M],
40) -> ([[T; N]; M], [[T; N]; M]) {
41    // Create uninitialized memory for the output arrays
42    let mut left: [[MaybeUninit<T>; N]; M] = [const { [const { MaybeUninit::uninit() }; N] }; M];
43    let mut right: [[MaybeUninit<T>; N]; M] = [const { [const { MaybeUninit::uninit() }; N] }; M];
44
45    // Move results to output arrays
46    for (i, a) in input.into_iter().enumerate() {
47        for (j, (l, r)) in a.into_iter().enumerate() {
48            left[i][j] = MaybeUninit::new(l);
49            right[i][j] = MaybeUninit::new(r);
50        }
51    }
52
53    // Convert the arrays of MaybeUninit into fully initialized arrays
54    // Safety: All the elements have been initialized above
55    let left = left.map(|a| a.map(|u| unsafe { u.assume_init() }));
56    let right = right.map(|a| a.map(|u| unsafe { u.assume_init() }));
57    (left, right)
58}
59
60pub const fn uint_to_field(i: U256) -> FieldElement {
61    FieldElement::new(BigInt(i.into_limbs()))
62}
63
64/// Convert a Noir field element to a native `FieldElement`
65#[inline(always)]
66pub fn noir_to_native(n: NoirElement) -> FieldElement {
67    FieldElement::from(BigInt(n.into_repr().into_bigint().0))
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
