1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

//! This module obtains the gates of a foreign field addition circuit.

use ark_ff::PrimeField;
use num_bigint::BigUint;

use crate::circuits::{
    gate::{CircuitGate, Connect, GateType},
    polynomials::foreign_field_common::BigUintForeignFieldHelpers,
    wires::Wire,
};

use super::witness::FFOps;

impl<F: PrimeField> CircuitGate<F> {
    /// Create foreign field addition gate chain without range checks (needs to wire the range check for result bound manually)
    /// - Inputs
    ///   - starting row
    ///   - operations to perform
    ///   - modulus of the foreign field
    /// - Outputs tuple (next_row, circuit_gates) where
    ///   - next_row      - next row after this gate
    ///   - circuit_gates - vector of circuit gates comprising this gate
    ///
    /// Note that the final structure of the circuit is as follows:
    /// circuit_gates = [
    ///      {
    ///        (i) ->      -> 1 ForeignFieldAdd row
    ///      } * num times
    ///      (n)           -> 1 ForeignFieldAdd row (this is where the final result goes)
    ///      (n+1)         -> 1 Zero row for bound result
    /// ]
    ///
    /// Warning:
    /// - Wire the range check for result bound manually
    /// - Connect to public input containing the 1 value for the overflow in the final bound check
    /// - If the inputs of the addition come from public input, wire it as well
    pub fn create_chain_ffadd(
        start_row: usize,
        opcodes: &[FFOps],
        foreign_field_modulus: &BigUint,
    ) -> (usize, Vec<Self>) {
        if *foreign_field_modulus > BigUint::max_foreign_field_modulus::<F>() {
            panic!(
                "foreign_field_modulus exceeds maximum: {} > {}",
                *foreign_field_modulus,
                BigUint::max_foreign_field_modulus::<F>()
            );
        }

        let next_row = start_row;
        let foreign_field_modulus = foreign_field_modulus.to_field_limbs::<F>();
        let mut circuit_gates = vec![];
        let num = opcodes.len();
        // ---------------------------
        // Foreign field addition gates
        // ---------------------------
        // First the single-addition gates
        for (i, opcode) in opcodes.iter().enumerate() {
            let mut coeffs = foreign_field_modulus.to_vec();
            coeffs.push(opcode.sign::<F>());
            circuit_gates.append(&mut vec![CircuitGate {
                typ: GateType::ForeignFieldAdd,
                wires: Wire::for_row(next_row + i),
                coeffs,
            }]);
        }
        let mut final_coeffs = foreign_field_modulus.to_vec();
        final_coeffs.push(FFOps::Add.sign::<F>());
        // Then the final bound gate and the zero gate
        circuit_gates.append(&mut vec![
            CircuitGate {
                typ: GateType::ForeignFieldAdd,
                wires: Wire::for_row(next_row + num),
                coeffs: final_coeffs,
            },
            CircuitGate {
                typ: GateType::Zero,
                wires: Wire::for_row(next_row + num + 1),
                coeffs: vec![],
            },
        ]);
        (start_row + circuit_gates.len(), circuit_gates)
    }

    /// Create a single foreign field addition gate. This is used for example in the final bound check.
    /// - Inputs
    ///   - starting row
    ///   - operation to perform
    ///   - modulus of the foreign field
    /// - Outputs tuple (next_row, circuit_gates) where
    ///   - next_row      - next row after this gate
    ///   - circuit_gates - vector of circuit gates comprising this gate
    pub fn create_single_ffadd(
        start_row: usize,
        operation: FFOps,
        foreign_field_modulus: &BigUint,
    ) -> (usize, Vec<Self>) {
        if *foreign_field_modulus > BigUint::max_foreign_field_modulus::<F>() {
            panic!(
                "foreign_field_modulus exceeds maximum: {} > {}",
                *foreign_field_modulus,
                BigUint::max_foreign_field_modulus::<F>()
            );
        }

        let foreign_field_modulus = foreign_field_modulus.to_field_limbs::<F>();
        let mut coeffs = foreign_field_modulus.to_vec();
        coeffs.push(operation.sign::<F>());
        let circuit_gates = vec![
            CircuitGate {
                typ: GateType::ForeignFieldAdd,
                wires: Wire::for_row(start_row),
                coeffs,
            },
            CircuitGate {
                typ: GateType::Zero,
                wires: Wire::for_row(start_row + 1),
                coeffs: vec![],
            },
        ];

        (start_row + circuit_gates.len(), circuit_gates)
    }

    /// Extend a chain of foreign field addition gates. It already wires 1 value to the overflow cell.
    /// - Inputs
    ///   - gates: vector of gates to extend
    ///   - pub_row: row of the public input
    ///   - curr_row: mutable reference to the current row
    ///   - opcodes: operations to perform
    ///   - foreign_field_modulus: modulus of the foreign field
    pub fn extend_chain_ffadd(
        gates: &mut Vec<Self>,
        pub_row: usize,
        curr_row: &mut usize,
        opcodes: &[FFOps],
        foreign_field_modulus: &BigUint,
    ) {
        let (next_row, add_gates) =
            Self::create_chain_ffadd(*curr_row, opcodes, foreign_field_modulus);
        gates.extend_from_slice(&add_gates);
        *curr_row = next_row;
        // check overflow flag is one
        gates.connect_cell_pair((pub_row, 0), (*curr_row - 2, 6));
    }

    /// Extend a single foreign field addition gate followed by a zero row containing the result
    pub fn extend_single_ffadd(
        gates: &mut Vec<Self>,
        curr_row: &mut usize,
        operation: FFOps,
        foreign_field_modulus: &BigUint,
    ) {
        let (next_row, add_gates) =
            Self::create_single_ffadd(*curr_row, operation, foreign_field_modulus);
        *curr_row = next_row;
        gates.extend_from_slice(&add_gates);
    }
}