1  
 2  pragma circom 2.2.0;
 3  
 4  //------------------------------------------------------------------------------
 5  
 6  function FloorLog2(n) {
 7    return (n==0) ? -1 : (1 + FloorLog2(n>>1));
 8  }
 9  
10  function CeilLog2(n) {
11    return (n==0) ? 0 : (1 + FloorLog2(n-1));
12  }
13  
14  //------------------------------------------------------------------------------
15  // decompose an n-bit number into bits (least significant bit first)
16  
17  template ToBits(n) {
18    signal input  inp;
19    signal output out[n];
20  
21    var sum = 0;
22    for(var i=0; i<n; i++) {
23      out[i] <-- (inp >> i) & 1;
24      out[i] * (1-out[i]) === 0;
25      sum += (1<<i) * out[i];
26    }
27  
28    inp === sum;
29  }
30  
31  //------------------------------------------------------------------------------
32  // check equality to zero; that is, compute `(inp==0) ? 1 : 0`
33  
34  template IsZero() {
35    signal input  inp;
36    signal output out;
37  
38    // guess the inverse
39    signal inv;
40    inv <-- (inp != 0) ? (1/inp) : 0 ;
41  
42    // if `inp==0`, then by definition `out==1`
43    // if `out==0`, then the inverse must must exist, so `inp!=0`
44    out <== 1 - inp * inv;
45  
46    // enfore that either `inp` or `out` must be zero
47    inp*out === 0;
48  }
49  
50  //------------------------------------------------------------------------------
51  // check equality of two field elements; that is, computes `(A==B) ? 1 : 0`
52  
53  template IsEqual() {
54    signal input  A,B;
55    signal output out;
56  
57    component isz = IsZero();
58    isz.inp <== A - B;
59    isz.out ==> out;
60  }
61  
62  //------------------------------------------------------------------------------