1package prover
  2
  3import (
  4	"bytes"
  5	"math/big"
  6
  7	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
  8	"github.com/iden3/go-circom-prover-verifier/types"
  9	"github.com/iden3/go-iden3-crypto/ff"
 10)
 11
 12func arrayOfZeroes(n int) []*big.Int {
 13	r := make([]*big.Int, n)
 14	for i := 0; i < n; i++ {
 15		r[i] = new(big.Int).SetInt64(0)
 16	}
 17	return r[:]
 18}
 19
 20func arrayOfZeroesE(n int) []*ff.Element {
 21	r := make([]*ff.Element, n)
 22	for i := 0; i < n; i++ {
 23		r[i] = ff.NewElement()
 24	}
 25	return r[:]
 26}
 27
 28func arrayOfZeroesG1(n int) []*bn256.G1 {
 29	r := make([]*bn256.G1, n)
 30	for i := 0; i < n; i++ {
 31		r[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 32	}
 33	return r[:]
 34}
 35
 36func arrayOfZeroesG2(n int) []*bn256.G2 {
 37	r := make([]*bn256.G2, n)
 38	for i := 0; i < n; i++ {
 39		r[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 40	}
 41	return r[:]
 42}
 43
 44func fAdd(a, b *big.Int) *big.Int {
 45	ab := new(big.Int).Add(a, b)
 46	return ab.Mod(ab, types.R)
 47}
 48
 49func fSub(a, b *big.Int) *big.Int {
 50	ab := new(big.Int).Sub(a, b)
 51	return new(big.Int).Mod(ab, types.R)
 52}
 53
 54func fMul(a, b *big.Int) *big.Int {
 55	ab := new(big.Int).Mul(a, b)
 56	return ab.Mod(ab, types.R)
 57}
 58
 59func fDiv(a, b *big.Int) *big.Int {
 60	ab := new(big.Int).Mul(a, new(big.Int).ModInverse(b, types.R))
 61	return new(big.Int).Mod(ab, types.R)
 62}
 63
 64func fNeg(a *big.Int) *big.Int {
 65	return new(big.Int).Mod(new(big.Int).Neg(a), types.R)
 66}
 67
 68func fInv(a *big.Int) *big.Int {
 69	return new(big.Int).ModInverse(a, types.R)
 70}
 71
 72func fExp(base *big.Int, e *big.Int) *big.Int {
 73	res := big.NewInt(1)
 74	rem := new(big.Int).Set(e)
 75	exp := base
 76
 77	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
 78		// if BigIsOdd(rem) {
 79		if rem.Bit(0) == 1 { // .Bit(0) returns 1 when is odd
 80			res = fMul(res, exp)
 81		}
 82		exp = fMul(exp, exp)
 83		rem.Rsh(rem, 1)
 84	}
 85	return res
 86}
 87
 88func max(a, b int) int {
 89	if a > b {
 90		return a
 91	}
 92	return b
 93}
 94
 95func polynomialSub(a, b []*big.Int) []*big.Int {
 96	r := arrayOfZeroes(max(len(a), len(b)))
 97	for i := 0; i < len(a); i++ {
 98		r[i] = fAdd(r[i], a[i])
 99	}
100	for i := 0; i < len(b); i++ {
101		r[i] = fSub(r[i], b[i])
102	}
103	return r
104}
105
106func polynomialSubE(a, b []*ff.Element) []*ff.Element {
107	r := arrayOfZeroesE(max(len(a), len(b)))
108	for i := 0; i < len(a); i++ {
109		r[i].Add(r[i], a[i])
110	}
111	for i := 0; i < len(b); i++ {
112		r[i].Sub(r[i], b[i])
113	}
114	return r
115}
116
117func polynomialMul(a, b []*big.Int) []*big.Int {
118	r := arrayOfZeroes(len(a) + len(b) - 1)
119	for i := 0; i < len(a); i++ {
120		for j := 0; j < len(b); j++ {
121			r[i+j] = fAdd(r[i+j], fMul(a[i], b[j]))
122		}
123	}
124	return r
125}
126
127func polynomialMulE(a, b []*ff.Element) []*ff.Element {
128	r := arrayOfZeroesE(len(a) + len(b) - 1)
129	for i := 0; i < len(a); i++ {
130		for j := 0; j < len(b); j++ {
131			r[i+j].Add(r[i+j], ff.NewElement().Mul(a[i], b[j]))
132		}
133	}
134	return r
135}
136
137func polynomialDiv(a, b []*big.Int) ([]*big.Int, []*big.Int) {
138	// https://en.wikipedia.org/wiki/Division_algorithm
139	r := arrayOfZeroes(len(a) - len(b) + 1)
140	rem := a
141	for len(rem) >= len(b) {
142		l := fDiv(rem[len(rem)-1], b[len(b)-1])
143		pos := len(rem) - len(b)
144		r[pos] = l
145		aux := arrayOfZeroes(pos)
146		aux1 := append(aux, l)
147		aux2 := polynomialSub(rem, polynomialMul(b, aux1))
148		rem = aux2[:len(aux2)-1]
149	}
150	return r, rem
151}
152
153func polynomialDivE(a, b []*ff.Element) ([]*ff.Element, []*ff.Element) {
154	// https://en.wikipedia.org/wiki/Division_algorithm
155	r := arrayOfZeroesE(len(a) - len(b) + 1)
156	rem := a
157	for len(rem) >= len(b) {
158		l := ff.NewElement().Div(rem[len(rem)-1], b[len(b)-1])
159		pos := len(rem) - len(b)
160		r[pos] = l
161		aux := arrayOfZeroesE(pos)
162		aux1 := append(aux, l)
163		aux2 := polynomialSubE(rem, polynomialMulE(b, aux1))
164		rem = aux2[:len(aux2)-1]
165	}
166	return r, rem
167}