Adding upstream version 1.20.14.upstream/1.20.14upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 338 insertions, 0 deletions

diff --git a/src/crypto/internal/edwards25519/field/_asm/fe_amd64_asm.go b/src/crypto/internal/edwards25519/field/_asm/fe_amd64_asm.go
new file mode 100644
index 0000000..411399c
--- /dev/null
+++ b/src/crypto/internal/edwards25519/field/_asm/fe_amd64_asm.go
@@ -0,0 +1,294 @@
+// Copyright (c) 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"fmt"
+
+	. "github.com/mmcloughlin/avo/build"
+	. "github.com/mmcloughlin/avo/gotypes"
+	. "github.com/mmcloughlin/avo/operand"
+	. "github.com/mmcloughlin/avo/reg"
+)
+
+//go:generate go run . -out ../fe_amd64.s -stubs ../fe_amd64.go -pkg field
+
+func main() {
+	Package("crypto/internal/edwards25519/field")
+	ConstraintExpr("amd64,gc,!purego")
+	feMul()
+	feSquare()
+	Generate()
+}
+
+type namedComponent struct {
+	Component
+	name string
+}
+
+func (c namedComponent) String() string { return c.name }
+
+type uint128 struct {
+	name   string
+	hi, lo GPVirtual
+}
+
+func (c uint128) String() string { return c.name }
+
+func feSquare() {
+	TEXT("feSquare", NOSPLIT, "func(out, a *Element)")
+	Doc("feSquare sets out = a * a. It works like feSquareGeneric.")
+	Pragma("noescape")
+
+	a := Dereference(Param("a"))
+	l0 := namedComponent{a.Field("l0"), "l0"}
+	l1 := namedComponent{a.Field("l1"), "l1"}
+	l2 := namedComponent{a.Field("l2"), "l2"}
+	l3 := namedComponent{a.Field("l3"), "l3"}
+	l4 := namedComponent{a.Field("l4"), "l4"}
+
+	// r0 = l0×l0 + 19×2×(l1×l4 + l2×l3)
+	r0 := uint128{"r0", GP64(), GP64()}
+	mul64(r0, 1, l0, l0)
+	addMul64(r0, 38, l1, l4)
+	addMul64(r0, 38, l2, l3)
+
+	// r1 = 2×l0×l1 + 19×2×l2×l4 + 19×l3×l3
+	r1 := uint128{"r1", GP64(), GP64()}
+	mul64(r1, 2, l0, l1)
+	addMul64(r1, 38, l2, l4)
+	addMul64(r1, 19, l3, l3)
+
+	// r2 = = 2×l0×l2 + l1×l1 + 19×2×l3×l4
+	r2 := uint128{"r2", GP64(), GP64()}
+	mul64(r2, 2, l0, l2)
+	addMul64(r2, 1, l1, l1)
+	addMul64(r2, 38, l3, l4)
+
+	// r3 = = 2×l0×l3 + 2×l1×l2 + 19×l4×l4
+	r3 := uint128{"r3", GP64(), GP64()}
+	mul64(r3, 2, l0, l3)
+	addMul64(r3, 2, l1, l2)
+	addMul64(r3, 19, l4, l4)
+
+	// r4 = = 2×l0×l4 + 2×l1×l3 + l2×l2
+	r4 := uint128{"r4", GP64(), GP64()}
+	mul64(r4, 2, l0, l4)
+	addMul64(r4, 2, l1, l3)
+	addMul64(r4, 1, l2, l2)
+
+	Comment("First reduction chain")
+	maskLow51Bits := GP64()
+	MOVQ(Imm((1<<51)-1), maskLow51Bits)
+	c0, r0lo := shiftRightBy51(&r0)
+	c1, r1lo := shiftRightBy51(&r1)
+	c2, r2lo := shiftRightBy51(&r2)
+	c3, r3lo := shiftRightBy51(&r3)
+	c4, r4lo := shiftRightBy51(&r4)
+	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
+	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
+	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
+	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
+	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
+
+	Comment("Second reduction chain (carryPropagate)")
+	// c0 = r0 >> 51
+	MOVQ(r0lo, c0)
+	SHRQ(Imm(51), c0)
+	// c1 = r1 >> 51
+	MOVQ(r1lo, c1)
+	SHRQ(Imm(51), c1)
+	// c2 = r2 >> 51
+	MOVQ(r2lo, c2)
+	SHRQ(Imm(51), c2)
+	// c3 = r3 >> 51
+	MOVQ(r3lo, c3)
+	SHRQ(Imm(51), c3)
+	// c4 = r4 >> 51
+	MOVQ(r4lo, c4)
+	SHRQ(Imm(51), c4)
+	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
+	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
+	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
+	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
+	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
+
+	Comment("Store output")
+	out := Dereference(Param("out"))
+	Store(r0lo, out.Field("l0"))
+	Store(r1lo, out.Field("l1"))
+	Store(r2lo, out.Field("l2"))
+	Store(r3lo, out.Field("l3"))
+	Store(r4lo, out.Field("l4"))
+
+	RET()
+}
+
+func feMul() {
+	TEXT("feMul", NOSPLIT, "func(out, a, b *Element)")
+	Doc("feMul sets out = a * b. It works like feMulGeneric.")
+	Pragma("noescape")
+
+	a := Dereference(Param("a"))
+	a0 := namedComponent{a.Field("l0"), "a0"}
+	a1 := namedComponent{a.Field("l1"), "a1"}
+	a2 := namedComponent{a.Field("l2"), "a2"}
+	a3 := namedComponent{a.Field("l3"), "a3"}
+	a4 := namedComponent{a.Field("l4"), "a4"}
+
+	b := Dereference(Param("b"))
+	b0 := namedComponent{b.Field("l0"), "b0"}
+	b1 := namedComponent{b.Field("l1"), "b1"}
+	b2 := namedComponent{b.Field("l2"), "b2"}
+	b3 := namedComponent{b.Field("l3"), "b3"}
+	b4 := namedComponent{b.Field("l4"), "b4"}
+
+	// r0 = a0×b0 + 19×(a1×b4 + a2×b3 + a3×b2 + a4×b1)
+	r0 := uint128{"r0", GP64(), GP64()}
+	mul64(r0, 1, a0, b0)
+	addMul64(r0, 19, a1, b4)
+	addMul64(r0, 19, a2, b3)
+	addMul64(r0, 19, a3, b2)
+	addMul64(r0, 19, a4, b1)
+
+	// r1 = a0×b1 + a1×b0 + 19×(a2×b4 + a3×b3 + a4×b2)
+	r1 := uint128{"r1", GP64(), GP64()}
+	mul64(r1, 1, a0, b1)
+	addMul64(r1, 1, a1, b0)
+	addMul64(r1, 19, a2, b4)
+	addMul64(r1, 19, a3, b3)
+	addMul64(r1, 19, a4, b2)
+
+	// r2 = a0×b2 + a1×b1 + a2×b0 + 19×(a3×b4 + a4×b3)
+	r2 := uint128{"r2", GP64(), GP64()}
+	mul64(r2, 1, a0, b2)
+	addMul64(r2, 1, a1, b1)
+	addMul64(r2, 1, a2, b0)
+	addMul64(r2, 19, a3, b4)
+	addMul64(r2, 19, a4, b3)
+
+	// r3 = a0×b3 + a1×b2 + a2×b1 + a3×b0 + 19×a4×b4
+	r3 := uint128{"r3", GP64(), GP64()}
+	mul64(r3, 1, a0, b3)
+	addMul64(r3, 1, a1, b2)
+	addMul64(r3, 1, a2, b1)
+	addMul64(r3, 1, a3, b0)
+	addMul64(r3, 19, a4, b4)
+
+	// r4 = a0×b4 + a1×b3 + a2×b2 + a3×b1 + a4×b0
+	r4 := uint128{"r4", GP64(), GP64()}
+	mul64(r4, 1, a0, b4)
+	addMul64(r4, 1, a1, b3)
+	addMul64(r4, 1, a2, b2)
+	addMul64(r4, 1, a3, b1)
+	addMul64(r4, 1, a4, b0)
+
+	Comment("First reduction chain")
+	maskLow51Bits := GP64()
+	MOVQ(Imm((1<<51)-1), maskLow51Bits)
+	c0, r0lo := shiftRightBy51(&r0)
+	c1, r1lo := shiftRightBy51(&r1)
+	c2, r2lo := shiftRightBy51(&r2)
+	c3, r3lo := shiftRightBy51(&r3)
+	c4, r4lo := shiftRightBy51(&r4)
+	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
+	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
+	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
+	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
+	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
+
+	Comment("Second reduction chain (carryPropagate)")
+	// c0 = r0 >> 51
+	MOVQ(r0lo, c0)
+	SHRQ(Imm(51), c0)
+	// c1 = r1 >> 51
+	MOVQ(r1lo, c1)
+	SHRQ(Imm(51), c1)
+	// c2 = r2 >> 51
+	MOVQ(r2lo, c2)
+	SHRQ(Imm(51), c2)
+	// c3 = r3 >> 51
+	MOVQ(r3lo, c3)
+	SHRQ(Imm(51), c3)
+	// c4 = r4 >> 51
+	MOVQ(r4lo, c4)
+	SHRQ(Imm(51), c4)
+	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
+	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
+	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
+	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
+	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
+
+	Comment("Store output")
+	out := Dereference(Param("out"))
+	Store(r0lo, out.Field("l0"))
+	Store(r1lo, out.Field("l1"))
+	Store(r2lo, out.Field("l2"))
+	Store(r3lo, out.Field("l3"))
+	Store(r4lo, out.Field("l4"))
+
+	RET()
+}
+
+// mul64 sets r to i * aX * bX.
+func mul64(r uint128, i int, aX, bX namedComponent) {
+	switch i {
+	case 1:
+		Comment(fmt.Sprintf("%s = %s×%s", r, aX, bX))
+		Load(aX, RAX)
+	case 2:
+		Comment(fmt.Sprintf("%s = 2×%s×%s", r, aX, bX))
+		Load(aX, RAX)
+		SHLQ(Imm(1), RAX)
+	default:
+		panic("unsupported i value")
+	}
+	MULQ(mustAddr(bX)) // RDX, RAX = RAX * bX
+	MOVQ(RAX, r.lo)
+	MOVQ(RDX, r.hi)
+}
+
+// addMul64 sets r to r + i * aX * bX.
+func addMul64(r uint128, i uint64, aX, bX namedComponent) {
+	switch i {
+	case 1:
+		Comment(fmt.Sprintf("%s += %s×%s", r, aX, bX))
+		Load(aX, RAX)
+	default:
+		Comment(fmt.Sprintf("%s += %d×%s×%s", r, i, aX, bX))
+		IMUL3Q(Imm(i), Load(aX, GP64()), RAX)
+	}
+	MULQ(mustAddr(bX)) // RDX, RAX = RAX * bX
+	ADDQ(RAX, r.lo)
+	ADCQ(RDX, r.hi)
+}
+
+// shiftRightBy51 returns r >> 51 and r.lo.
+//
+// After this function is called, the uint128 may not be used anymore.
+func shiftRightBy51(r *uint128) (out, lo GPVirtual) {
+	out = r.hi
+	lo = r.lo
+	SHLQ(Imm(64-51), r.lo, r.hi)
+	r.lo, r.hi = nil, nil // make sure the uint128 is unusable
+	return
+}
+
+// maskAndAdd sets r = r&mask + c*i.
+func maskAndAdd(r, mask, c GPVirtual, i uint64) {
+	ANDQ(mask, r)
+	if i != 1 {
+		IMUL3Q(Imm(i), c, c)
+	}
+	ADDQ(c, r)
+}
+
+func mustAddr(c Component) Op {
+	b, err := c.Resolve()
+	if err != nil {
+		panic(err)
+	}
+	return b.Addr
+}
diff --git a/src/crypto/internal/edwards25519/field/_asm/go.mod b/src/crypto/internal/edwards25519/field/_asm/go.mod
new file mode 100644
index 0000000..1ce2b5e
--- /dev/null
+++ b/src/crypto/internal/edwards25519/field/_asm/go.mod
@@ -0,0 +1,12 @@
+module asm
+
+go 1.19
+
+require github.com/mmcloughlin/avo v0.4.0
+
+require (
+	golang.org/x/mod v0.4.2 // indirect
+	golang.org/x/sys v0.0.0-20211030160813-b3129d9d1021 // indirect
+	golang.org/x/tools v0.1.7 // indirect
+	golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 // indirect
+)
diff --git a/src/crypto/internal/edwards25519/field/_asm/go.sum b/src/crypto/internal/edwards25519/field/_asm/go.sum
new file mode 100644
index 0000000..b4b5914
--- /dev/null
+++ b/src/crypto/internal/edwards25519/field/_asm/go.sum
@@ -0,0 +1,32 @@
+github.com/mmcloughlin/avo v0.4.0 h1:jeHDRktVD+578ULxWpQHkilor6pkdLF7u7EiTzDbfcU=
+github.com/mmcloughlin/avo v0.4.0/go.mod h1:RW9BfYA3TgO9uCdNrKU2h6J8cPD8ZLznvfgHAeszb1s=
+github.com/yuin/goldmark v1.4.0/go.mod h1:mwnBkeHKe2W/ZEtQ+71ViKU8L12m81fl3OWwC1Zlc8k=
+golang.org/x/arch v0.0.0-20210923205945-b76863e36670/go.mod h1:5om86z9Hs0C8fWVUuoMHwpExlXzs5Tkyp9hOrfG7pp8=
+golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/crypto v0.0.0-20191011191535-87dc89f01550/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
+golang.org/x/mod v0.4.2 h1:Gz96sIWK3OalVv/I/qNygP42zyoKp3xptRVCWRFEBvo=
+golang.org/x/mod v0.4.2/go.mod h1:s0Qsj1ACt9ePp/hMypM3fl4fZqREWJwdYDEqhRiZZUA=
+golang.org/x/net v0.0.0-20190404232315-eb5bcb51f2a3/go.mod h1:t9HGtf8HONx5eT2rtn7q6eTqICYqUVnKs3thJo3Qplg=
+golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
+golang.org/x/net v0.0.0-20210805182204-aaa1db679c0d/go.mod h1:9nx3DQGgdP8bBQD5qxJ1jj9UTztislL4KSBs9R2vV5Y=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20210220032951-036812b2e83c/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20210423082822-04245dca01da/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20210809222454-d867a43fc93e/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20211030160813-b3129d9d1021 h1:giLT+HuUP/gXYrG2Plg9WTjj4qhfgaW424ZIFog3rlk=
+golang.org/x/sys v0.0.0-20211030160813-b3129d9d1021/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
+golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+golang.org/x/text v0.3.6/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
+golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
+golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
+golang.org/x/tools v0.1.7 h1:6j8CgantCy3yc8JGBqkDLMKWqZ0RDU2g1HVgacojGWQ=
+golang.org/x/tools v0.1.7/go.mod h1:LGqMHiF4EqQNHR1JncWGqT5BVaXmza+X+BDGol+dOxo=
+golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20191011141410-1b5146add898/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 h1:go1bK/D/BFZV2I8cIQd1NKEZ+0owSTG1fDTci4IqFcE=
+golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+rsc.io/pdf v0.1.1/go.mod h1:n8OzWcQ6Sp37PL01nO98y4iUCRdTGarVfzxY20ICaU4=