From 6719336428da455c0708c7f1564c873d6f6e2c6d Mon Sep 17 00:00:00 2001 From: Egon Elbre Date: Tue, 18 Feb 2025 13:17:16 +0200 Subject: [PATCH] crypto/internal/fips140/edwards25519/field: optimize *19 MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Using a `x*19 == x + (x + x<<3)<<1` gives a significant performance improvement for arm devices that have a slow multiply. Surprisingly it also seems to help Mac M1 and AMD64+purgo a bit. goos: linux goarch: arm64 pkg: crypto/internal/fips140/edwards25519 │ OLD │ NEW │ │ sec/op │ sec/op vs base │ EncodingDecoding-4 166.3µ ± 0% 158.7µ ± 0% -4.57% (p=0.000 n=10) ScalarBaseMult-4 286.0µ ± 0% 281.2µ ± 0% -1.70% (p=0.000 n=10) ScalarMult-4 1.042m ± 0% 1.009m ± 0% -3.22% (p=0.000 n=10) VarTimeDoubleScalarBaseMult-4 1.042m ± 0% 1.003m ± 0% -3.66% (p=0.000 n=10) geomean 476.7µ 461.0µ -3.29% pkg: crypto/internal/fips140/edwards25519/field │ OLD │ NEW │ │ sec/op │ sec/op vs base │ Add-4 45.24n ± 0% 45.22n ± 0% ~ (p=0.166 n=10) Multiply-4 447.5n ± 0% 454.0n ± 0% +1.46% (p=0.000 n=10) Square-4 289.7n ± 0% 278.2n ± 0% -3.99% (p=0.000 n=10) Invert-4 79.45µ ± 0% 75.83µ ± 0% -4.55% (p=0.000 n=10) Mult32-4 78.67n ± 0% 78.66n ± 0% ~ (p=0.272 n=10) Bytes-4 120.5n ± 0% 120.6n ± 0% ~ (p=0.390 n=10) geomean 405.0n 400.2n -1.20% goos: darwin goarch: arm64 pkg: crypto/internal/fips140/edwards25519 cpu: Apple M1 Pro │ OLD │ NEW │ │ sec/op │ sec/op vs base │ EncodingDecoding-10 10.04µ ± 0% 10.10µ ± 0% +0.54% (p=0.000 n=10) ScalarBaseMult-10 12.72µ ± 0% 12.65µ ± 0% -0.50% (p=0.000 n=10) ScalarMult-10 51.82µ ± 0% 51.49µ ± 0% -0.63% (p=0.000 n=10) VarTimeDoubleScalarBaseMult-10 50.63µ ± 2% 49.41µ ± 0% -2.41% (p=0.001 n=10) geomean 24.06µ 23.88µ -0.75% pkg: crypto/internal/fips140/edwards25519/field │ OLD │ NEW │ │ sec/op │ sec/op vs base │ Add-10 6.327n ± 2% 6.009n ± 1% -5.03% (p=0.000 n=10) Multiply-10 19.12n ± 0% 19.59n ± 0% +2.48% (p=0.000 n=10) Square-10 17.88n ± 0% 18.14n ± 0% +1.40% (p=0.000 n=10) Invert-10 4.816µ ± 0% 4.854µ ± 0% +0.78% (p=0.000 n=10) Mult32-10 6.188n ± 0% 6.151n ± 0% -0.61% (p=0.001 n=10) Bytes-10 7.460n ± 0% 7.463n ± 1% ~ (p=0.795 n=10) geomean 27.99n 27.94n -0.19% tags: purego goos: windows goarch: amd64 pkg: crypto/internal/fips140/edwards25519 cpu: AMD Ryzen Threadripper 2950X 16-Core Processor │ OLD │ NEW │ │ sec/op │ sec/op vs base │ EncodingDecoding-32 13.61µ ± 1% 12.86µ ± 0% -5.54% (p=0.000 n=10) ScalarBaseMult-32 22.88µ ± 2% 21.28µ ± 1% -6.98% (p=0.000 n=10) ScalarMult-32 79.29µ ± 3% 74.83µ ± 1% -5.63% (p=0.000 n=10) VarTimeDoubleScalarBaseMult-32 77.91µ ± 2% 73.85µ ± 0% -5.22% (p=0.000 n=10) geomean 37.24µ 35.06µ -5.85% pkg: crypto/internal/fips140/edwards25519/field │ OLD │ NEW │ │ sec/op │ sec/op vs base │ Add-32 5.723n ± 2% 5.700n ± 1% ~ (p=0.218 n=10) Multiply-32 30.63n ± 1% 29.24n ± 2% -4.52% (p=0.000 n=10) Square-32 24.30n ± 1% 23.06n ± 1% -5.10% (p=0.000 n=10) Invert-32 6.368µ ± 1% 5.952µ ± 2% -6.53% (p=0.000 n=10) Mult32-32 5.303n ± 2% 5.240n ± 1% -1.17% (p=0.041 n=10) Bytes-32 12.47n ± 1% 12.39n ± 1% ~ (p=0.137 n=10) geomean 34.86n 33.78n -3.10% Change-Id: I889b322bf49293516574d3e9514734a49cca1f86 Reviewed-on: https://go-review.googlesource.com/c/go/+/650277 Reviewed-by: Filippo Valsorda Reviewed-by: Ian Lance Taylor Reviewed-by: Michael Pratt LUCI-TryBot-Result: Go LUCI Auto-Submit: Filippo Valsorda --- .../fips140/edwards25519/field/fe_generic.go | 134 +++++++++--------- .../fips140/edwards25519/field/fe_test.go | 14 +- 2 files changed, 76 insertions(+), 72 deletions(-) diff --git a/src/crypto/internal/fips140/edwards25519/field/fe_generic.go b/src/crypto/internal/fips140/edwards25519/field/fe_generic.go index 86f5fd9553..f1d0ff3715 100644 --- a/src/crypto/internal/fips140/edwards25519/field/fe_generic.go +++ b/src/crypto/internal/fips140/edwards25519/field/fe_generic.go @@ -12,20 +12,42 @@ type uint128 struct { lo, hi uint64 } -// mul64 returns a * b. -func mul64(a, b uint64) uint128 { +// mul returns a * b. +func mul(a, b uint64) uint128 { hi, lo := bits.Mul64(a, b) return uint128{lo, hi} } -// addMul64 returns v + a * b. -func addMul64(v uint128, a, b uint64) uint128 { +// addMul returns v + a * b. +func addMul(v uint128, a, b uint64) uint128 { hi, lo := bits.Mul64(a, b) lo, c := bits.Add64(lo, v.lo, 0) hi, _ = bits.Add64(hi, v.hi, c) return uint128{lo, hi} } +// mul19 returns v * 19. +func mul19(v uint64) uint64 { + // Using this approach seems to yield better optimizations than *19. + return v + (v+v<<3)<<1 +} + +// addMul19 returns v + 19 * a * b, where a and b are at most 52 bits. +func addMul19(v uint128, a, b uint64) uint128 { + hi, lo := bits.Mul64(mul19(a), b) + lo, c := bits.Add64(lo, v.lo, 0) + hi, _ = bits.Add64(hi, v.hi, c) + return uint128{lo, hi} +} + +// addMul38 returns v + 38 * a * b, where a and b are at most 52 bits. +func addMul38(v uint128, a, b uint64) uint128 { + hi, lo := bits.Mul64(mul19(a), b*2) + lo, c := bits.Add64(lo, v.lo, 0) + hi, _ = bits.Add64(hi, v.hi, c) + return uint128{lo, hi} +} + // shiftRightBy51 returns a >> 51. a is assumed to be at most 115 bits. func shiftRightBy51(a uint128) uint64 { return (a.hi << (64 - 51)) | (a.lo >> 51) @@ -76,45 +98,40 @@ func feMulGeneric(v, a, b *Element) { // // Finally we add up the columns into wide, overlapping limbs. - a1_19 := a1 * 19 - a2_19 := a2 * 19 - a3_19 := a3 * 19 - a4_19 := a4 * 19 - // r0 = a0×b0 + 19×(a1×b4 + a2×b3 + a3×b2 + a4×b1) - r0 := mul64(a0, b0) - r0 = addMul64(r0, a1_19, b4) - r0 = addMul64(r0, a2_19, b3) - r0 = addMul64(r0, a3_19, b2) - r0 = addMul64(r0, a4_19, b1) + r0 := mul(a0, b0) + r0 = addMul19(r0, a1, b4) + r0 = addMul19(r0, a2, b3) + r0 = addMul19(r0, a3, b2) + r0 = addMul19(r0, a4, b1) // r1 = a0×b1 + a1×b0 + 19×(a2×b4 + a3×b3 + a4×b2) - r1 := mul64(a0, b1) - r1 = addMul64(r1, a1, b0) - r1 = addMul64(r1, a2_19, b4) - r1 = addMul64(r1, a3_19, b3) - r1 = addMul64(r1, a4_19, b2) + r1 := mul(a0, b1) + r1 = addMul(r1, a1, b0) + r1 = addMul19(r1, a2, b4) + r1 = addMul19(r1, a3, b3) + r1 = addMul19(r1, a4, b2) // r2 = a0×b2 + a1×b1 + a2×b0 + 19×(a3×b4 + a4×b3) - r2 := mul64(a0, b2) - r2 = addMul64(r2, a1, b1) - r2 = addMul64(r2, a2, b0) - r2 = addMul64(r2, a3_19, b4) - r2 = addMul64(r2, a4_19, b3) + r2 := mul(a0, b2) + r2 = addMul(r2, a1, b1) + r2 = addMul(r2, a2, b0) + r2 = addMul19(r2, a3, b4) + r2 = addMul19(r2, a4, b3) // r3 = a0×b3 + a1×b2 + a2×b1 + a3×b0 + 19×a4×b4 - r3 := mul64(a0, b3) - r3 = addMul64(r3, a1, b2) - r3 = addMul64(r3, a2, b1) - r3 = addMul64(r3, a3, b0) - r3 = addMul64(r3, a4_19, b4) + r3 := mul(a0, b3) + r3 = addMul(r3, a1, b2) + r3 = addMul(r3, a2, b1) + r3 = addMul(r3, a3, b0) + r3 = addMul19(r3, a4, b4) // r4 = a0×b4 + a1×b3 + a2×b2 + a3×b1 + a4×b0 - r4 := mul64(a0, b4) - r4 = addMul64(r4, a1, b3) - r4 = addMul64(r4, a2, b2) - r4 = addMul64(r4, a3, b1) - r4 = addMul64(r4, a4, b0) + r4 := mul(a0, b4) + r4 = addMul(r4, a1, b3) + r4 = addMul(r4, a2, b2) + r4 = addMul(r4, a3, b1) + r4 = addMul(r4, a4, b0) // After the multiplication, we need to reduce (carry) the five coefficients // to obtain a result with limbs that are at most slightly larger than 2⁵¹, @@ -149,7 +166,7 @@ func feMulGeneric(v, a, b *Element) { c3 := shiftRightBy51(r3) c4 := shiftRightBy51(r4) - rr0 := r0.lo&maskLow51Bits + c4*19 + rr0 := r0.lo&maskLow51Bits + mul19(c4) rr1 := r1.lo&maskLow51Bits + c0 rr2 := r2.lo&maskLow51Bits + c1 rr3 := r3.lo&maskLow51Bits + c2 @@ -190,44 +207,31 @@ func feSquareGeneric(v, a *Element) { // l0l4 19×l4l4 19×l3l4 19×l2l4 19×l1l4 = // -------------------------------------- // r4 r3 r2 r1 r0 - // - // With precomputed 2×, 19×, and 2×19× terms, we can compute each limb with - // only three Mul64 and four Add64, instead of five and eight. - - l0_2 := l0 * 2 - l1_2 := l1 * 2 - - l1_38 := l1 * 38 - l2_38 := l2 * 38 - l3_38 := l3 * 38 - - l3_19 := l3 * 19 - l4_19 := l4 * 19 // r0 = l0×l0 + 19×(l1×l4 + l2×l3 + l3×l2 + l4×l1) = l0×l0 + 19×2×(l1×l4 + l2×l3) - r0 := mul64(l0, l0) - r0 = addMul64(r0, l1_38, l4) - r0 = addMul64(r0, l2_38, l3) + r0 := mul(l0, l0) + r0 = addMul38(r0, l1, l4) + r0 = addMul38(r0, l2, l3) // r1 = l0×l1 + l1×l0 + 19×(l2×l4 + l3×l3 + l4×l2) = 2×l0×l1 + 19×2×l2×l4 + 19×l3×l3 - r1 := mul64(l0_2, l1) - r1 = addMul64(r1, l2_38, l4) - r1 = addMul64(r1, l3_19, l3) + r1 := mul(l0*2, l1) + r1 = addMul38(r1, l2, l4) + r1 = addMul19(r1, l3, l3) // r2 = l0×l2 + l1×l1 + l2×l0 + 19×(l3×l4 + l4×l3) = 2×l0×l2 + l1×l1 + 19×2×l3×l4 - r2 := mul64(l0_2, l2) - r2 = addMul64(r2, l1, l1) - r2 = addMul64(r2, l3_38, l4) + r2 := mul(l0*2, l2) + r2 = addMul(r2, l1, l1) + r2 = addMul38(r2, l3, l4) // r3 = l0×l3 + l1×l2 + l2×l1 + l3×l0 + 19×l4×l4 = 2×l0×l3 + 2×l1×l2 + 19×l4×l4 - r3 := mul64(l0_2, l3) - r3 = addMul64(r3, l1_2, l2) - r3 = addMul64(r3, l4_19, l4) + r3 := mul(l0*2, l3) + r3 = addMul(r3, l1*2, l2) + r3 = addMul19(r3, l4, l4) // r4 = l0×l4 + l1×l3 + l2×l2 + l3×l1 + l4×l0 = 2×l0×l4 + 2×l1×l3 + l2×l2 - r4 := mul64(l0_2, l4) - r4 = addMul64(r4, l1_2, l3) - r4 = addMul64(r4, l2, l2) + r4 := mul(l0*2, l4) + r4 = addMul(r4, l1*2, l3) + r4 = addMul(r4, l2, l2) c0 := shiftRightBy51(r0) c1 := shiftRightBy51(r1) @@ -235,7 +239,7 @@ func feSquareGeneric(v, a *Element) { c3 := shiftRightBy51(r3) c4 := shiftRightBy51(r4) - rr0 := r0.lo&maskLow51Bits + c4*19 + rr0 := r0.lo&maskLow51Bits + mul19(c4) rr1 := r1.lo&maskLow51Bits + c0 rr2 := r2.lo&maskLow51Bits + c1 rr3 := r3.lo&maskLow51Bits + c2 @@ -256,7 +260,7 @@ func (v *Element) carryPropagateGeneric() *Element { // c4 is at most 64 - 51 = 13 bits, so c4*19 is at most 18 bits, and // the final l0 will be at most 52 bits. Similarly for the rest. - v.l0 = v.l0&maskLow51Bits + c4*19 + v.l0 = v.l0&maskLow51Bits + mul19(c4) v.l1 = v.l1&maskLow51Bits + c0 v.l2 = v.l2&maskLow51Bits + c1 v.l3 = v.l3&maskLow51Bits + c2 diff --git a/src/crypto/internal/fips140/edwards25519/field/fe_test.go b/src/crypto/internal/fips140/edwards25519/field/fe_test.go index 0d7ae2b0f6..eca6d63b74 100644 --- a/src/crypto/internal/fips140/edwards25519/field/fe_test.go +++ b/src/crypto/internal/fips140/edwards25519/field/fe_test.go @@ -128,25 +128,25 @@ func TestMultiplyDistributesOverAdd(t *testing.T) { func TestMul64to128(t *testing.T) { a := uint64(5) b := uint64(5) - r := mul64(a, b) + r := mul(a, b) if r.lo != 0x19 || r.hi != 0 { t.Errorf("lo-range wide mult failed, got %d + %d*(2**64)", r.lo, r.hi) } a = uint64(18014398509481983) // 2^54 - 1 b = uint64(18014398509481983) // 2^54 - 1 - r = mul64(a, b) + r = mul(a, b) if r.lo != 0xff80000000000001 || r.hi != 0xfffffffffff { t.Errorf("hi-range wide mult failed, got %d + %d*(2**64)", r.lo, r.hi) } a = uint64(1125899906842661) b = uint64(2097155) - r = mul64(a, b) - r = addMul64(r, a, b) - r = addMul64(r, a, b) - r = addMul64(r, a, b) - r = addMul64(r, a, b) + r = mul(a, b) + r = addMul(r, a, b) + r = addMul(r, a, b) + r = addMul(r, a, b) + r = addMul(r, a, b) if r.lo != 16888498990613035 || r.hi != 640 { t.Errorf("wrong answer: %d + %d*(2**64)", r.lo, r.hi) } -- 2.50.0