halo2_ecc/bigint/
add_no_carry.rs

1use super::{CRTInteger, OverflowInteger};
2use halo2_base::{gates::GateInstructions, utils::ScalarField, Context};
3use itertools::Itertools;
4use std::cmp::max;
5
6/// # Assumptions
7/// * `a, b` have same number of limbs
8pub fn assign<F: ScalarField>(
9    gate: &impl GateInstructions<F>,
10    ctx: &mut Context<F>,
11    a: OverflowInteger<F>,
12    b: OverflowInteger<F>,
13) -> OverflowInteger<F> {
14    let out_limbs = a
15        .limbs
16        .into_iter()
17        .zip_eq(b.limbs)
18        .map(|(a_limb, b_limb)| gate.add(ctx, a_limb, b_limb))
19        .collect();
20
21    OverflowInteger::new(out_limbs, max(a.max_limb_bits, b.max_limb_bits) + 1)
22}
23
24/// # Assumptions
25/// * `a, b` have same number of limbs
26// pass by reference to avoid cloning the BigInt in CRTInteger, unclear if this is optimal
27pub fn crt<F: ScalarField>(
28    gate: &impl GateInstructions<F>,
29    ctx: &mut Context<F>,
30    a: CRTInteger<F>,
31    b: CRTInteger<F>,
32) -> CRTInteger<F> {
33    let out_trunc = assign(gate, ctx, a.truncation, b.truncation);
34    let out_native = gate.add(ctx, a.native, b.native);
35    let out_val = a.value + b.value;
36    CRTInteger::new(out_trunc, out_native, out_val)
37}