1/*
 2
 3Binary Sum
 4==========
 5
 6This component creates a binary sum componet of ops operands and n bits each operand.
 7
 8e is Number of carries: Depends on the number of operands in the input.
 9
10Main Constraint:
11   in[0][0]     * 2^0  +  in[0][1]     * 2^1  + ..... + in[0][n-1]    * 2^(n-1)  +
12 + in[1][0]     * 2^0  +  in[1][1]     * 2^1  + ..... + in[1][n-1]    * 2^(n-1)  +
13 + ..
14 + in[ops-1][0] * 2^0  +  in[ops-1][1] * 2^1  + ..... + in[ops-1][n-1] * 2^(n-1)  +
15 ===
16   out[0] * 2^0  + out[1] * 2^1 +   + out[n+e-1] *2(n+e-1)
17
18To waranty binary outputs:
19
20    out[0]     * (out[0] - 1) === 0
21    out[1]     * (out[0] - 1) === 0
22    .
23    .
24    .
25    out[n+e-1] * (out[n+e-1] - 1) == 0
26
27 */
28
29
30/*
31    This function calculates the number of extra bits in the output to do the full sum.
32 */
33
34function nbits(a) {
35    var n = 1;
36    var r = 0;
37    while (n-1<a) {
38        r++;
39        n *= 2;
40    }
41    return r;
42}
43
44
45template BinSum(n, ops) {
46    var nout = nbits((2**n -1)*ops);
47    signal input in[ops][n];
48    signal output out[nout];
49
50    var lin = 0;
51    var lout = 0;
52
53    var k;
54    var j;
55
56    for (k=0; k<n; k++) {
57        for (j=0; j<ops; j++) {
58            lin += in[j][k] * 2**k;
59        }
60    }
61
62    for (k=0; k<nout; k++) {
63        out[k] <-- (lin >> k) & 1;
64
65        // Ensure out is binary
66        out[k] * (out[k] - 1) === 0;
67
68        lout += out[k] * 2**k;
69    }
70
71    // Ensure the sum;
72
73    lin === lout;
74}