1package sha512
  2
  3import (
  4	"fmt"
  5	"math/big"
  6    "github.com/consensys/gnark/backend/hint"
  7    "github.com/consensys/gnark/frontend"
  8)
  9
 10
 11func padToSameLength(args [][]frontend.Variable) ([][]frontend.Variable, int) {
 12	maxLength := 0
 13	for _, v := range args {
 14		if len(v) > maxLength {
 15			maxLength = len(v)
 16		}
 17	}
 18	result := make([][]frontend.Variable, len(args))
 19	for i := 0; i < len(args); i++ {
 20		if len(args[i]) < maxLength {
 21			arr := make([]frontend.Variable, maxLength)
 22			for j := 0; j < maxLength; j++ {
 23				if j < len(args[i]) {
 24					arr[j] = args[i][j]
 25				} else {
 26					arr[j] = 0
 27				}
 28			}
 29			result[i] = arr
 30		} else {
 31			result[i] = args[i]
 32		}
 33	}
 34	return result, maxLength
 35}
 36
 37func log2(n int) int {
 38	if n <= 0 { panic("undefined") }
 39	result := 0
 40	n -= 1
 41	for n > 0 {
 42		n >>= 1
 43		result += 1
 44	}
 45	return result
 46}
 47
 48func extractBit(n big.Int) bool {
 49	if !n.IsInt64() {
 50		panic("not bit")
 51	}
 52	val := n.Int64()
 53	if val == 0 {
 54		return false
 55	} else if val == 1 {
 56		return true
 57	} else {
 58		panic("not bit")
 59	}
 60}
 61
 62func flatten(arr [][]frontend.Variable) ([]frontend.Variable) {
 63	totalLength := 0
 64	for _, v := range arr {
 65		totalLength += len(v)
 66	}
 67	result := make([]frontend.Variable, totalLength)
 68	i := 0
 69	for _, v := range arr {
 70		for _, u := range v {
 71			result[i] = u
 72			i += 1
 73		}
 74	}
 75	return result
 76}
 77
 78func BinSum(api frontend.API, args ...[]frontend.Variable) ([]frontend.Variable) {
 79	ops := len(args)
 80	in, n := padToSameLength(args)
 81	nout := n + log2(ops)
 82//     var nout = nbits((2**n -1)*ops);
 83//     signal input in[ops][n];
 84//     signal output out[nout];
 85
 86	var hintFn hint.Function = func(field *big.Int, inputs []*big.Int, outputs []*big.Int) error {
 87		if len(inputs) != ops*n { panic("bad length") }
 88		if len(outputs) != nout { panic("bad length") }
 89
 90		maxOutputValue := big.NewInt(1)
 91		maxOutputValue.Lsh(maxOutputValue, uint(nout))
 92		if maxOutputValue.Cmp(field) != -1 { panic("overflow") }
 93
 94		result := big.NewInt(0)
 95		for i := 0; i < ops; i++ {
 96			placeValue := big.NewInt(1)
 97			for j := 0; j < n; j++ {
 98				if extractBit(*inputs[i*n+j]) {
 99					result.Add(result, placeValue)
100				}
101				placeValue.Add(placeValue, placeValue)
102			}
103		}
104		for i := 0; i < nout; i++ {
105			v := new(big.Int).Rsh(result, uint(i))
106			v.And(v, big.NewInt(1))
107			outputs[i] = v
108		}
109		fmt.Println(ops, n, nout, inputs, outputs)
110		return nil
111	}
112
113	out, err := api.NewHint(hintFn, nout, flatten(in)...)
114	if err != nil {
115		panic(err)
116	}
117
118	var lhs frontend.Variable = 0
119	var rhs frontend.Variable = 0
120
121	placeValue := big.NewInt(1)
122	for i := 0; i < nout; i++ {
123		for j := 0; j < ops; j++ {
124			if i < n {
125				lhs = api.Add(lhs, api.Mul(placeValue, in[j][i]))
126			}
127		}
128		rhs = api.Add(rhs, api.Mul(placeValue, out[i]))
129		api.AssertIsBoolean(out[i])
130		placeValue.Add(placeValue, placeValue)
131	}
132	api.AssertIsEqual(lhs, rhs)
133
134	return out
135}