1package goldilocks
 2
 3import (
 4	"math"
 5
 6	"github.com/consensys/gnark/frontend"
 7)
 8
 9// The types, structs, and functions in this file were ported over from the gnark library
10// https://github.com/Consensys/gnark/blob/3421eaa7d544286abf3de8c46282b8d4da6d5da0/std/rangecheck/rangecheck_commit.go
11type Type int
12
13const (
14	R1CS Type = iota
15	SCS
16)
17
18type FrontendTyper interface {
19	FrontendType() Type
20}
21
22type checkedVariable struct {
23	v    frontend.Variable
24	bits int
25}
26
27func getOptimalBasewidth(api frontend.API, collected []checkedVariable) int {
28	if ft, ok := api.(FrontendTyper); ok {
29		switch ft.FrontendType() {
30		case R1CS:
31			return optimalWidth(nbR1CSConstraints, collected)
32		case SCS:
33			return optimalWidth(nbPLONKConstraints, collected)
34		}
35	}
36	return optimalWidth(nbR1CSConstraints, collected)
37}
38
39func optimalWidth(countFn func(baseLength int, collected []checkedVariable) int, collected []checkedVariable) int {
40	min := math.MaxInt64
41	minVal := 0
42	for j := 2; j < 18; j++ {
43		current := countFn(j, collected)
44		if current < min {
45			min = current
46			minVal = j
47		}
48	}
49
50	return minVal
51}
52
53func decompSize(varSize int, limbSize int) int {
54	return (varSize + limbSize - 1) / limbSize
55}
56
57func nbR1CSConstraints(baseLength int, collected []checkedVariable) int {
58	nbDecomposed := 0
59	for i := range collected {
60		nbDecomposed += int(decompSize(collected[i].bits, baseLength))
61	}
62	eqs := len(collected)       // correctness of decomposition
63	nbRight := nbDecomposed     // inverse per decomposed
64	nbleft := (1 << baseLength) // div per table
65	return nbleft + nbRight + eqs + 1
66}
67
68func nbPLONKConstraints(baseLength int, collected []checkedVariable) int {
69	nbDecomposed := 0
70	for i := range collected {
71		nbDecomposed += int(decompSize(collected[i].bits, baseLength))
72	}
73	eqs := nbDecomposed               // check correctness of every decomposition. this is nbDecomp adds + eq cost per collected
74	nbRight := 3 * nbDecomposed       // denominator sub, inv and large sum per table entry
75	nbleft := 3 * (1 << baseLength)   // denominator sub, div and large sum per table entry
76	return nbleft + nbRight + eqs + 1 // and the final assert
77}
78
79func gnarkRangeCheckerSelector(api frontend.API) RangeCheckerType {
80	// Emulate the logic within rangecheck.New
81	// https://github.com/Consensys/gnark/blob/3421eaa7d544286abf3de8c46282b8d4da6d5da0/std/rangecheck/rangecheck.go#L24
82	if _, ok := api.(frontend.Rangechecker); ok {
83		return NATIVE_RANGE_CHECKER
84	} else if _, ok := api.(frontend.Committer); ok {
85		return COMMIT_RANGE_CHECKER
86	} else {
87		return BIT_DECOMP_RANGE_CHECKER
88	}
89}