openvm_circuit_primitives/bigint/
utils.rs

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!(bits <= decomp, "range_check: bits {bits} > decomp {decomp}");
22    let expr = into_expr.into();
23    let bus = VariableRangeCheckerBus::new(range_bus, decomp);
24    bus.range_check(expr, bits).eval(builder, count);
25}
26
27pub fn secp256k1_coord_prime() -> BigUint {
28    BigUint::from_str_radix(
29        "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
30        16,
31    )
32    .unwrap()
33}
34
35pub fn secp256k1_scalar_prime() -> BigUint {
36    BigUint::from_str(
37        "115792089237316195423570985008687907852837564279074904382605163141518161494337",
38    )
39    .unwrap()
40}
41
42// aka P256
43pub fn secp256r1_coord_prime() -> BigUint {
44    BigUint::from_str_radix(
45        "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
46        16,
47    )
48    .unwrap()
49}
50
51pub fn secp256r1_scalar_prime() -> BigUint {
52    BigUint::from_str_radix(
53        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
54        16,
55    )
56    .unwrap()
57}
58
59pub fn big_int_abs(x: &BigInt) -> BigUint {
60    if x.sign() == Sign::Minus {
61        x.neg().to_biguint().unwrap()
62    } else {
63        x.to_biguint().unwrap()
64    }
65}
66
67pub fn big_uint_sub(x: BigUint, y: BigUint) -> BigInt {
68    match x.cmp(&y) {
69        std::cmp::Ordering::Less => BigInt::from_biguint(Sign::Minus, y - x),
70        std::cmp::Ordering::Equal => BigInt::zero(),
71        std::cmp::Ordering::Greater => BigInt::from_biguint(Sign::Plus, x - y),
72    }
73}
74
75// little endian.
76pub fn big_uint_to_limbs(x: &BigUint, limb_bits: usize) -> Vec<usize> {
77    let mut result = Vec::new();
78    let mut x = x.clone();
79    let base = BigUint::from_u32(1 << limb_bits).unwrap();
80    while x > BigUint::zero() {
81        result.push((x.clone() % &base).to_usize().unwrap());
82        x /= &base;
83    }
84    result
85}
86
87pub fn big_uint_to_num_limbs(x: &BigUint, limb_bits: usize, num_limbs: usize) -> Vec<usize> {
88    let limbs = big_uint_to_limbs(x, limb_bits);
89    let num_limbs = max(num_limbs, limbs.len());
90    limbs
91        .iter()
92        .chain(repeat(&0))
93        .take(num_limbs)
94        .copied()
95        .collect()
96}
97
98pub fn big_int_to_limbs(x: &BigInt, limb_bits: usize) -> Vec<isize> {
99    let x_sign = x.sign();
100    let limbs = big_uint_to_limbs(&big_int_abs(x), limb_bits);
101    if x_sign == Sign::Minus {
102        limbs.iter().map(|&x| -(x as isize)).collect()
103    } else {
104        limbs.iter().map(|&x| x as isize).collect()
105    }
106}
107
108pub fn big_int_to_num_limbs(x: &BigInt, limb_bits: usize, num_limbs: usize) -> Vec<isize> {
109    let limbs = big_int_to_limbs(x, limb_bits);
110    let num_limbs = max(num_limbs, limbs.len());
111    limbs
112        .iter()
113        .chain(repeat(&0))
114        .take(num_limbs)
115        .copied()
116        .collect()
117}
118
119pub fn take_limb(deque: &mut VecDeque<usize>, limb_size: usize) -> usize {
120    deque
121        .drain(..limb_size.min(deque.len()))
122        .enumerate()
123        .map(|(i, bit)| bit << i)
124        .sum()
125}
126
127pub fn vec_isize_to_f<F: PrimeField64>(x: Vec<isize>) -> Vec<F> {
128    x.iter()
129        .map(|x| {
130            F::from_canonical_usize(x.unsigned_abs()) * if x >= &0 { F::ONE } else { F::NEG_ONE }
131        })
132        .collect()
133}
openvm_circuit_primitives/bigint/utils.rs

openvm_circuit_primitives/bigint/
utils.rs
