openvm_circuit_primitives/bigint/
utils.rs

Help
1use std::{cmp::max, collections::VecDeque, iter::repeat, ops::Neg, str::FromStr};
2
3use num_bigint::{BigInt, BigUint, Sign};
4use num_traits::{FromPrimitive, Num, ToPrimitive, Zero};
5use openvm_stark_backend::{
6    interaction::{BusIndex, InteractionBuilder},
7    p3_field::PrimeField64,
8};
9
10use crate::var_range::VariableRangeCheckerBus;
11
12// Checks that the given expression is within bits number of bits.
13pub fn range_check<AB: InteractionBuilder>(
14    builder: &mut AB,
15    range_bus: BusIndex, // The bus number for range checker.
16    decomp: usize,       // The ranger checker checks the numbers are within decomp bits.
17    bits: usize,
18    into_expr: impl Into<AB::Expr>,
19    count: impl Into<AB::Expr>,
20) {
21    assert!(
22        bits <= decomp,
23        "range_check: bits {} > decomp {}",
24        bits,
25        decomp
26    );
27    let expr = into_expr.into();
28    let bus = VariableRangeCheckerBus::new(range_bus, decomp);
29    bus.range_check(expr, bits).eval(builder, count);
30}
31
32pub fn secp256k1_coord_prime() -> BigUint {
33    BigUint::from_str_radix(
34        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
35        16,
36    )
37    .unwrap()
38}
39
40pub fn secp256k1_scalar_prime() -> BigUint {
41    BigUint::from_str(
42        "115792089237316195423570985008687907852837564279074904382605163141518161494337",
43    )
44    .unwrap()
45}
46
47// aka P256
48pub fn secp256r1_coord_prime() -> BigUint {
49    BigUint::from_str_radix(
50        "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
51        16,
52    )
53    .unwrap()
54}
55
56pub fn secp256r1_scalar_prime() -> BigUint {
57    BigUint::from_str_radix(
58        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
59        16,
60    )
61    .unwrap()
62}
63
64pub fn big_int_abs(x: &BigInt) -> BigUint {
65    if x.sign() == Sign::Minus {
66        x.neg().to_biguint().unwrap()
67    } else {
68        x.to_biguint().unwrap()
69    }
70}
71
72pub fn big_uint_sub(x: BigUint, y: BigUint) -> BigInt {
73    match x.cmp(&y) {
74        std::cmp::Ordering::Less => BigInt::from_biguint(Sign::Minus, y - x),
75        std::cmp::Ordering::Equal => BigInt::zero(),
76        std::cmp::Ordering::Greater => BigInt::from_biguint(Sign::Plus, x - y),
77    }
78}
79
80// little endian.
81pub fn big_uint_to_limbs(x: &BigUint, limb_bits: usize) -> Vec<usize> {
82    let mut result = Vec::new();
83    let mut x = x.clone();
84    let base = BigUint::from_u32(1 << limb_bits).unwrap();
85    while x > BigUint::zero() {
86        result.push((x.clone() % &base).to_usize().unwrap());
87        x /= &base;
88    }
89    result
90}
91
92pub fn big_uint_to_num_limbs(x: &BigUint, limb_bits: usize, num_limbs: usize) -> Vec<usize> {
93    let limbs = big_uint_to_limbs(x, limb_bits);
94    let num_limbs = max(num_limbs, limbs.len());
95    limbs
96        .iter()
97        .chain(repeat(&0))
98        .take(num_limbs)
99        .copied()
100        .collect()
101}
102
103pub fn big_int_to_limbs(x: &BigInt, limb_bits: usize) -> Vec<isize> {
104    let x_sign = x.sign();
105    let limbs = big_uint_to_limbs(&big_int_abs(x), limb_bits);
106    if x_sign == Sign::Minus {
107        limbs.iter().map(|&x| -(x as isize)).collect()
108    } else {
109        limbs.iter().map(|&x| x as isize).collect()
110    }
111}
112
113pub fn big_int_to_num_limbs(x: &BigInt, limb_bits: usize, num_limbs: usize) -> Vec<isize> {
114    let limbs = big_int_to_limbs(x, limb_bits);
115    let num_limbs = max(num_limbs, limbs.len());
116    limbs
117        .iter()
118        .chain(repeat(&0))
119        .take(num_limbs)
120        .copied()
121        .collect()
122}
123
124pub fn take_limb(deque: &mut VecDeque<usize>, limb_size: usize) -> usize {
125    deque
126        .drain(..limb_size.min(deque.len()))
127        .enumerate()
128        .map(|(i, bit)| bit << i)
129        .sum()
130}
131
132pub fn vec_isize_to_f<F: PrimeField64>(x: Vec<isize>) -> Vec<F> {
133    x.iter()
134        .map(|x| {
135            F::from_canonical_usize(x.unsigned_abs()) * if x >= &0 { F::ONE } else { F::NEG_ONE }
136        })
137        .collect()
138}
openvm_circuit_primitives/bigint/utils.rs

openvm_circuit_primitives/bigint/
utils.rs
