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