crypto/bn256: full switchover to cloudflare's code (#16301)

* crypto/bn256: full switchover to cloudflare's code

* crypto/bn256: only use cloudflare for optimized architectures

* crypto/bn256: upstream fallback for non-optimized code

* .travis, build: drop support for Go 1.8 (need type aliases)

* crypto/bn256/cloudflare: enable curve mul lattice optimization

1 files changed, 173 insertions, 0 deletions

diff --git a/crypto/bn256/cloudflare/gfp_generic.go b/crypto/bn256/cloudflare/gfp_generic.go
new file mode 100644
index 000000000..8e6be9596
--- /dev/null
+++ b/crypto/bn256/cloudflare/gfp_generic.go
@@ -0,0 +1,173 @@
+// +build !amd64,!arm64 generic
+
+package bn256
+
+func gfpCarry(a *gfP, head uint64) {
+	b := &gfP{}
+
+	var carry uint64
+	for i, pi := range p2 {
+		ai := a[i]
+		bi := ai - pi - carry
+		b[i] = bi
+		carry = (pi&^ai | (pi|^ai)&bi) >> 63
+	}
+	carry = carry &^ head
+
+	// If b is negative, then return a.
+	// Else return b.
+	carry = -carry
+	ncarry := ^carry
+	for i := 0; i < 4; i++ {
+		a[i] = (a[i] & carry) | (b[i] & ncarry)
+	}
+}
+
+func gfpNeg(c, a *gfP) {
+	var carry uint64
+	for i, pi := range p2 {
+		ai := a[i]
+		ci := pi - ai - carry
+		c[i] = ci
+		carry = (ai&^pi | (ai|^pi)&ci) >> 63
+	}
+	gfpCarry(c, 0)
+}
+
+func gfpAdd(c, a, b *gfP) {
+	var carry uint64
+	for i, ai := range a {
+		bi := b[i]
+		ci := ai + bi + carry
+		c[i] = ci
+		carry = (ai&bi | (ai|bi)&^ci) >> 63
+	}
+	gfpCarry(c, carry)
+}
+
+func gfpSub(c, a, b *gfP) {
+	t := &gfP{}
+
+	var carry uint64
+	for i, pi := range p2 {
+		bi := b[i]
+		ti := pi - bi - carry
+		t[i] = ti
+		carry = (bi&^pi | (bi|^pi)&ti) >> 63
+	}
+
+	carry = 0
+	for i, ai := range a {
+		ti := t[i]
+		ci := ai + ti + carry
+		c[i] = ci
+		carry = (ai&ti | (ai|ti)&^ci) >> 63
+	}
+	gfpCarry(c, carry)
+}
+
+func mul(a, b [4]uint64) [8]uint64 {
+	const (
+		mask16 uint64 = 0x0000ffff
+		mask32 uint64 = 0xffffffff
+	)
+
+	var buff [32]uint64
+	for i, ai := range a {
+		a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48
+
+		for j, bj := range b {
+			b0, b2 := bj&mask32, bj>>32
+
+			off := 4 * (i + j)
+			buff[off+0] += a0 * b0
+			buff[off+1] += a1 * b0
+			buff[off+2] += a2*b0 + a0*b2
+			buff[off+3] += a3*b0 + a1*b2
+			buff[off+4] += a2 * b2
+			buff[off+5] += a3 * b2
+		}
+	}
+
+	for i := uint(1); i < 4; i++ {
+		shift := 16 * i
+
+		var head, carry uint64
+		for j := uint(0); j < 8; j++ {
+			block := 4 * j
+
+			xi := buff[block]
+			yi := (buff[block+i] << shift) + head
+			zi := xi + yi + carry
+			buff[block] = zi
+			carry = (xi&yi | (xi|yi)&^zi) >> 63
+
+			head = buff[block+i] >> (64 - shift)
+		}
+	}
+
+	return [8]uint64{buff[0], buff[4], buff[8], buff[12], buff[16], buff[20], buff[24], buff[28]}
+}
+
+func halfMul(a, b [4]uint64) [4]uint64 {
+	const (
+		mask16 uint64 = 0x0000ffff
+		mask32 uint64 = 0xffffffff
+	)
+
+	var buff [18]uint64
+	for i, ai := range a {
+		a0, a1, a2, a3 := ai&mask16, (ai>>16)&mask16, (ai>>32)&mask16, ai>>48
+
+		for j, bj := range b {
+			if i+j > 3 {
+				break
+			}
+			b0, b2 := bj&mask32, bj>>32
+
+			off := 4 * (i + j)
+			buff[off+0] += a0 * b0
+			buff[off+1] += a1 * b0
+			buff[off+2] += a2*b0 + a0*b2
+			buff[off+3] += a3*b0 + a1*b2
+			buff[off+4] += a2 * b2
+			buff[off+5] += a3 * b2
+		}
+	}
+
+	for i := uint(1); i < 4; i++ {
+		shift := 16 * i
+
+		var head, carry uint64
+		for j := uint(0); j < 4; j++ {
+			block := 4 * j
+
+			xi := buff[block]
+			yi := (buff[block+i] << shift) + head
+			zi := xi + yi + carry
+			buff[block] = zi
+			carry = (xi&yi | (xi|yi)&^zi) >> 63
+
+			head = buff[block+i] >> (64 - shift)
+		}
+	}
+
+	return [4]uint64{buff[0], buff[4], buff[8], buff[12]}
+}
+
+func gfpMul(c, a, b *gfP) {
+	T := mul(*a, *b)
+	m := halfMul([4]uint64{T[0], T[1], T[2], T[3]}, np)
+	t := mul([4]uint64{m[0], m[1], m[2], m[3]}, p2)
+
+	var carry uint64
+	for i, Ti := range T {
+		ti := t[i]
+		zi := Ti + ti + carry
+		T[i] = zi
+		carry = (Ti&ti | (Ti|ti)&^zi) >> 63
+	}
+
+	*c = gfP{T[4], T[5], T[6], T[7]}
+	gfpCarry(c, carry)
+}