This is an adoption of the corresponding Linux commit: | commit 9deef9c5b8fcc702e69252bef46735d8b0d1f70c | Author: Fabian Blatter <[email protected]> | AuthorDate: Sun Jun 7 13:24:35 2026 +0200 | | crypto: ecc - Optimize vli additive operations using compiler builtins | | Replace the software carry flag emulation with compiler builtins. | | Even the newest compilers struggle with taking advantage of the | hardware carry flag. Compiler builtins allow the compiler to | much more easily achieve this while still remaining constant-time. | | This yields an approximately 6-7% performance improvement | on the ecc_gen_privkey, ecc_make_pub_key and crypto_ecdh_shared_secret | functions on x86_64 on all curve sizes. | | Additionally, the code becomes much more readable. | | Signed-off-by: Fabian Blatter <[email protected]> | Reviewed-by: Stefan Berger <[email protected]> | Signed-off-by: Herbert Xu <[email protected]>
We take this mainly to stay in sync with Linux, so the Origin-URL can follow along with the next fix. Signed-off-by: Ahmad Fatoum <[email protected]> --- crypto/ecc.c | 100 +++++++++++++++++++++++++++++++-------------------- 1 file changed, 61 insertions(+), 39 deletions(-) diff --git a/crypto/ecc.c b/crypto/ecc.c index 67faae0a68f9..01cb1ae88ead 100644 --- a/crypto/ecc.c +++ b/crypto/ecc.c @@ -1,4 +1,4 @@ -// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406 +// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=9deef9c5b8fcc702e69252bef46735d8b0d1f70c /* * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved. * Copyright (c) 2019 Vitaly Chikunov <[email protected]> @@ -267,6 +267,48 @@ static void vli_rshift1(u64 *vli, unsigned int ndigits) } } +#ifdef __has_builtin +#if __has_builtin(__builtin_addcll) +#define USE_BUILTIN_ADDC +#endif +#endif + +/* Computes result = left + right + carry_in and updates carry_out */ +static inline void add_carry(u64 left, u64 right, u64 *result, u64 carry_in, + u64 *carry_out) +{ +#ifdef USE_BUILTIN_ADDC + *result = __builtin_addcll(left, right, carry_in, carry_out); +#else + u64 sum1, sum2; + u64 c1 = __builtin_uaddll_overflow(left, right, &sum1); + u64 c2 = __builtin_uaddll_overflow(sum1, carry_in, &sum2); + *result = sum2; + *carry_out = c1 | c2; +#endif +} + +#ifdef __has_builtin +#if __has_builtin(__builtin_subcll) +#define USE_BUILTIN_SUBC +#endif +#endif + +/* Computes result = left - right - borrow_in and updates borrow_out */ +static inline void sub_borrow(u64 left, u64 right, u64 *result, u64 borrow_in, + u64 *borrow_out) +{ +#ifdef USE_BUILTIN_SUBC + *result = __builtin_subcll(left, right, borrow_in, borrow_out); +#else + u64 diff1, diff2; + u64 b1 = __builtin_usubll_overflow(left, right, &diff1); + u64 b2 = __builtin_usubll_overflow(diff1, borrow_in, &diff2); + *result = diff2; + *borrow_out = b1 | b2; +#endif +} + /* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_add(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) @@ -274,15 +316,8 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right, u64 carry = 0; int i; - for (i = 0; i < ndigits; i++) { - u64 sum; - - sum = left[i] + right[i] + carry; - if (sum != left[i]) - carry = (sum < left[i]); - - result[i] = sum; - } + for (i = 0; i < ndigits; i++) + add_carry(left[i], right[i], &result[i], carry, &carry); return carry; } @@ -291,40 +326,29 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right, static u64 vli_uadd(u64 *result, const u64 *left, u64 right, unsigned int ndigits) { - u64 carry = right; + u64 carry; int i; - for (i = 0; i < ndigits; i++) { - u64 sum; + if (ndigits == 0) + return right; - sum = left[i] + carry; - if (sum != left[i]) - carry = (sum < left[i]); - else - carry = !!carry; + carry = __builtin_uaddll_overflow(left[0], right, &result[0]); - result[i] = sum; - } + for (i = 1; i < ndigits; i++) + carry = __builtin_uaddll_overflow(left[i], carry, &result[i]); return carry; } /* Computes result = left - right, returning borrow. Can modify in place. */ u64 vli_sub(u64 *result, const u64 *left, const u64 *right, - unsigned int ndigits) + unsigned int ndigits) { u64 borrow = 0; int i; - for (i = 0; i < ndigits; i++) { - u64 diff; - - diff = left[i] - right[i] - borrow; - if (diff != left[i]) - borrow = (diff > left[i]); - - result[i] = diff; - } + for (i = 0; i < ndigits; i++) + sub_borrow(left[i], right[i], &result[i], borrow, &borrow); return borrow; } @@ -332,20 +356,18 @@ EXPORT_SYMBOL(vli_sub); /* Computes result = left - right, returning borrow. Can modify in place. */ static u64 vli_usub(u64 *result, const u64 *left, u64 right, - unsigned int ndigits) + unsigned int ndigits) { - u64 borrow = right; + u64 borrow; int i; - for (i = 0; i < ndigits; i++) { - u64 diff; + if (ndigits == 0) + return right; - diff = left[i] - borrow; - if (diff != left[i]) - borrow = (diff > left[i]); + borrow = __builtin_usubll_overflow(left[0], right, &result[0]); - result[i] = diff; - } + for (i = 1; i < ndigits; i++) + borrow = __builtin_usubll_overflow(left[i], borrow, &result[i]); return borrow; } -- 2.47.3
