Commit e45bdc6bd6

Frank Denis <124872+jedisct1@users.noreply.github.com>
2024-04-14 01:13:22
std.crypto.pcurves.*: simpler, smaller, faster u64 addition with carry (#19644)
signature/s: Algorithm Before After ---------------+---------+------- ecdsa-p256 3707 4396 ecdsa-p384 1067 1332 ecdsa-secp256k1 4490 5147 Add ECDSA to the benchmark by the way.
master
1 parent a59ad71
Changed files (7)
lib
std
crypto
pcurves
p256
p256_64.zig
p256_scalar_64.zig
p384
p384_64.zig
p384_scalar_64.zig
secp256k1
secp256k1_64.zig
secp256k1_scalar_64.zig
benchmark.zig
lib/std/crypto/pcurves/p256/p256_64.zig
@@ -73,12 +73,9 @@ pub const NonMontgomeryDomainFieldElement = [4]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -95,12 +92,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/pcurves/p256/p256_scalar_64.zig
@@ -73,12 +73,9 @@ pub const NonMontgomeryDomainFieldElement = [4]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -95,12 +92,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/pcurves/p384/p384_64.zig
@@ -42,12 +42,9 @@ pub const NonMontgomeryDomainFieldElement = [6]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -64,12 +61,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/pcurves/p384/p384_scalar_64.zig
@@ -42,12 +42,9 @@ pub const NonMontgomeryDomainFieldElement = [6]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -64,12 +61,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/pcurves/secp256k1/secp256k1_64.zig
@@ -42,12 +42,9 @@ pub const NonMontgomeryDomainFieldElement = [4]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -64,12 +61,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/pcurves/secp256k1/secp256k1_scalar_64.zig
@@ -42,12 +42,9 @@ pub const NonMontgomeryDomainFieldElement = [4]u64;
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @addWithOverflow(arg2, arg3);
-    const ov2 = @addWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) +% arg3 +% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function subborrowxU64 is a subtraction with borrow.
@@ -64,12 +61,9 @@ inline fn addcarryxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) vo
 ///   out1: [0x0 ~> 0xffffffffffffffff]
 ///   out2: [0x0 ~> 0x1]
 inline fn subborrowxU64(out1: *u64, out2: *u1, arg1: u1, arg2: u64, arg3: u64) void {
-    @setRuntimeSafety(mode == .Debug);
-
-    const ov1 = @subWithOverflow(arg2, arg3);
-    const ov2 = @subWithOverflow(ov1[0], arg1);
-    out1.* = ov2[0];
-    out2.* = ov1[1] | ov2[1];
+    const x = @as(u128, arg2) -% arg3 -% arg1;
+    out1.* = @truncate(x);
+    out2.* = @truncate(x >> 64);
 }
 
 /// The function mulxU64 is a multiplication, returning the full double-width result.
lib/std/crypto/benchmark.zig
@@ -131,7 +131,12 @@ pub fn benchmarkKeyExchange(comptime DhKeyExchange: anytype, comptime exchange_c
     return throughput;
 }
 
-const signatures = [_]Crypto{Crypto{ .ty = crypto.sign.Ed25519, .name = "ed25519" }};
+const signatures = [_]Crypto{
+    Crypto{ .ty = crypto.sign.Ed25519, .name = "ed25519" },
+    Crypto{ .ty = crypto.sign.ecdsa.EcdsaP256Sha256, .name = "ecdsa-p256" },
+    Crypto{ .ty = crypto.sign.ecdsa.EcdsaP384Sha384, .name = "ecdsa-p384" },
+    Crypto{ .ty = crypto.sign.ecdsa.EcdsaSecp256k1Sha256, .name = "ecdsa-secp256k1" },
+};
 
 pub fn benchmarkSignature(comptime Signature: anytype, comptime signatures_count: comptime_int) !u64 {
     const msg = [_]u8{0} ** 64;