1/*
 2    Copyright 2018 0KIMS association.
 3
 4    This file is part of circom (Zero Knowledge Circuit Compiler).
 5
 6    circom is a free software: you can redistribute it and/or modify it
 7    under the terms of the GNU General Public License as published by
 8    the Free Software Foundation, either version 3 of the License, or
 9    (at your option) any later version.
10
11    circom is distributed in the hope that it will be useful, but WITHOUT
12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13    or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14    License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with circom. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20/*
21
22Binary Sum
23==========
24
25This component creates a binary sum componet of ops operands and n bits each operand.
26
27e is Number of carries: Depends on the number of operands in the input.
28
29Main Constraint:
30   in[0][0]     * 2^0  +  in[0][1]     * 2^1  + ..... + in[0][n-1]    * 2^(n-1)  +
31 + in[1][0]     * 2^0  +  in[1][1]     * 2^1  + ..... + in[1][n-1]    * 2^(n-1)  +
32 + ..
33 + in[ops-1][0] * 2^0  +  in[ops-1][1] * 2^1  + ..... + in[ops-1][n-1] * 2^(n-1)  +
34 ===
35   out[0] * 2^0  + out[1] * 2^1 +   + out[n+e-1] *2(n+e-1)
36
37To waranty binary outputs:
38
39    out[0]     * (out[0] - 1) === 0
40    out[1]     * (out[0] - 1) === 0
41    .
42    .
43    .
44    out[n+e-1] * (out[n+e-1] - 1) == 0
45
46 */
47
48
49/*
50    This function calculates the number of extra bits in the output to do the full sum.
51 */
52
53function nbits(a) {
54    var n = 1;
55    var r = 0;
56    while (n-1<a) {
57        r++;
58        n *= 2;
59    }
60    return r;
61}
62
63
64template BinSum(n, ops) {
65    var nout = nbits((2**n -1)*ops);
66    signal input in[ops][n];
67    signal output out[nout];
68
69    var lin = 0;
70    var lout = 0;
71
72    var k;
73    var j;
74
75    for (k=0; k<n; k++) {
76        for (j=0; j<ops; j++) {
77            lin += in[j][k] * 2**k;
78        }
79    }
80
81    for (k=0; k<nout; k++) {
82        out[k] <-- (lin >> k) & 1;
83
84        // Ensure out is binary
85        out[k] * (out[k] - 1) === 0;
86
87        lout += out[k] * 2**k;
88    }
89
90    // Ensure the sum;
91
92    lin === lout;
93}