forked from Consensys/gnark
/
partition.go
69 lines (63 loc) · 1.53 KB
/
partition.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
package bitslice
import (
"math/big"
"github.com/consensys/gnark/frontend"
"github.com/consensys/gnark/std/rangecheck"
)
// Partition partitions v into two parts splitted at bit numbered split. The
// following holds
//
// v = lower + 2^split * upper.
//
// The method enforces that lower < 2^split and upper < 2^split', where
// split'=nbScalar-split. When giving the option [WithNbDigits], we instead use
// the bound split'=nbDigits-split.
func Partition(api frontend.API, v frontend.Variable, split uint, opts ...Option) (lower, upper frontend.Variable) {
opt, err := parseOpts(opts...)
if err != nil {
panic(err)
}
// handle constant case
if vc, ok := api.Compiler().ConstantValue(v); ok {
if opt.digits > 0 && vc.BitLen() > opt.digits {
panic("input larger than bound")
}
if split == 0 {
return 0, vc
}
div := new(big.Int).Lsh(big.NewInt(1), split)
l, u := new(big.Int), new(big.Int)
u.QuoRem(vc, div, l)
return l, u
}
rh := rangecheck.New(api)
if split == 0 {
if opt.digits > 0 {
rh.Check(v, opt.digits)
}
return 0, v
}
ret, err := api.Compiler().NewHint(partitionHint, 2, split, v)
if err != nil {
panic(err)
}
upper = ret[0]
lower = ret[1]
if opt.nocheck {
if opt.digits > 0 {
rh.Check(v, opt.digits)
}
return
}
upperBound := api.Compiler().FieldBitLen()
if opt.digits > 0 {
upperBound = opt.digits
}
rh.Check(upper, upperBound)
rh.Check(lower, int(split))
m := big.NewInt(1)
m.Lsh(m, split)
composed := api.Add(lower, api.Mul(upper, m))
api.AssertIsEqual(composed, v)
return
}