forked from Consensys/gnark
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hints.go
114 lines (95 loc) · 2.53 KB
/
hints.go
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
package bits
import (
"errors"
"math/big"
"github.com/consensys/gnark/constraint/solver"
)
func GetHints() []solver.Hint {
return []solver.Hint{
ithBit,
nBits,
nTrits,
nNaf,
}
}
func init() {
solver.RegisterHint(GetHints()...)
}
// IthBit returns the i-tb bit the input. The function expects exactly two
// integer inputs i and n, takes the little-endian bit representation of n and
// returns its i-th bit.
func ithBit(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
result := results[0]
if !inputs[1].IsUint64() {
result.SetUint64(0)
return nil
}
result.SetUint64(uint64(inputs[0].Bit(int(inputs[1].Uint64()))))
return nil
}
// NBits returns the first bits of the input. The number of returned bits is
// defined by the length of the results slice.
func nBits(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
n := inputs[0]
for i := 0; i < len(results); i++ {
results[i].SetUint64(uint64(n.Bit(i)))
}
return nil
}
// nTrits returns the first trits of the input. The number of returned trits is
// defined by the length of the results slice.
func nTrits(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
n := inputs[0]
// TODO using big.Int Text method is likely not cheap
base3 := n.Text(3)
i := 0
for j := len(base3) - 1; j >= 0 && i < len(results); j-- {
results[i].SetUint64(uint64(base3[j] - 48))
i++
}
for ; i < len(results); i++ {
results[i].SetUint64(0)
}
return nil
}
// NNAF returns the NAF decomposition of the input. The number of digits is
// defined by the number of elements in the results slice.
func nNaf(_ *big.Int, inputs []*big.Int, results []*big.Int) error {
n := inputs[0]
return nafDecomposition(n, results)
}
// nafDecomposition gets the naf decomposition of a big number
func nafDecomposition(a *big.Int, results []*big.Int) error {
if a == nil || a.Sign() == -1 {
return errors.New("invalid input to naf decomposition; negative (or nil) big.Int not supported")
}
var zero, one, three big.Int
one.SetUint64(1)
three.SetUint64(3)
n := 0
// some buffers
var buf, aCopy big.Int
aCopy.Set(a)
for aCopy.Cmp(&zero) != 0 && n < len(results) {
// if aCopy % 2 == 0
buf.And(&aCopy, &one)
// aCopy even
if buf.Cmp(&zero) == 0 {
results[n].SetUint64(0)
} else { // aCopy odd
buf.And(&aCopy, &three)
if buf.IsUint64() && buf.Uint64() == 3 {
results[n].SetInt64(-1)
aCopy.Add(&aCopy, &one)
} else {
results[n].SetUint64(1)
}
}
aCopy.Rsh(&aCopy, 1)
n++
}
for ; n < len(results); n++ {
results[n].SetUint64(0)
}
return nil
}