halo2_ecc/bigint/
scalar_mul_and_add_no_carry.rs

Help
1use super::{CRTInteger, OverflowInteger};
2use halo2_base::{
3    gates::GateInstructions,
4    utils::{log2_ceil, ScalarField},
5    Context,
6    QuantumCell::Constant,
7};
8use itertools::Itertools;
9use std::cmp::max;
10
11/// compute a * c + b = b + a * c
12///
13/// # Assumptions
14/// * `a, b` have same number of limbs
15/// * Number of limbs is nonzero
16/// * `c_log2_ceil = log2_ceil(c)` where `c` is the BigUint value of `c_f`
17// this is uniquely suited for our simple gate
18pub fn assign<F: ScalarField>(
19    gate: &impl GateInstructions<F>,
20    ctx: &mut Context<F>,
21    a: OverflowInteger<F>,
22    b: OverflowInteger<F>,
23    c_f: F,
24    c_log2_ceil: usize,
25) -> OverflowInteger<F> {
26    let out_limbs = a
27        .limbs
28        .into_iter()
29        .zip_eq(b.limbs)
30        .map(|(a_limb, b_limb)| gate.mul_add(ctx, a_limb, Constant(c_f), b_limb))
31        .collect();
32
33    OverflowInteger::new(out_limbs, max(a.max_limb_bits + c_log2_ceil, b.max_limb_bits) + 1)
34}
35
36/// compute a * c + b = b + a * c
37pub fn crt<F: ScalarField>(
38    gate: &impl GateInstructions<F>,
39    ctx: &mut Context<F>,
40    a: CRTInteger<F>,
41    b: CRTInteger<F>,
42    c: i64,
43) -> CRTInteger<F> {
44    debug_assert_eq!(a.truncation.limbs.len(), b.truncation.limbs.len());
45
46    let (c_f, c_abs) = if c >= 0 {
47        let c_abs = u64::try_from(c).unwrap();
48        (F::from(c_abs), c_abs)
49    } else {
50        let c_abs = u64::try_from(-c).unwrap();
51        (-F::from(c_abs), c_abs)
52    };
53
54    let out_trunc = assign(gate, ctx, a.truncation, b.truncation, c_f, log2_ceil(c_abs));
55    let out_native = gate.mul_add(ctx, a.native, Constant(c_f), b.native);
56    let out_val = a.value * c + b.value;
57    CRTInteger::new(out_trunc, out_native, out_val)
58}
halo2_ecc/bigint/scalar_mul_and_add_no_carry.rs

halo2_ecc/bigint/
scalar_mul_and_add_no_carry.rs
