Re: [PATCH] crypto: ecc - Optimize vli additive operations using compiler builtins

On Sun, 5 Jul 2026 at 07:33, Herbert Xu <[email protected]> wrote:
>
> On Sun, Jun 07, 2026 at 01:24:35PM +0200, Fabian Blatter wrote:
> > 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]>
> > ---
> >
> > Hi,
> >
> > I'd like to expand on the benchmarks, compare the generated assembly,
> > and clarify some things.
> >
> >
> > Use of compiler builtins:
> >
> > This patch uses __builtin_addcll, __builtin_subcll when available and
> > otherwise __builtin_uaddll_overflow, __builtin_usubll_overflow. the
> > latter have existed since ancient gcc versions, so no third fallback
> > is needed.
> >
> > I have put the add_carry and sub_borrow inline functions with the
> > preprocessor logic for builtin selection directly in crypto/ecc.c.
> > Please let me know if you would like them to be somewhere else.
> >
> > They do not emit data-dependent branches, and so remain constant-time.
> >
> >
> > Benchmarks:
> >
> > All benchmarks were run single-threaded on my AMD 7700X CPU limited to
> > 5.6Ghz. I have measured both nanoseconds and clock cycles, since their
> > combination can hint at downclocking issues and allows calculation of
> > the clock speed during the benchmark.
> >
> > I have omitted the raw output from the benchmarking code, as they much
> > exceed the 72 character limit.
> >
> > I have calculated the percent differences, included clock speed
> > calculations and relevant summaries.
> >
> >
> > Macro benchmarks:
> >
> > These were run in a virtualized environment using virtme-ng on the
> > compiled linux kernel image compiled with default flags.
> >
> > (the first value is the original time per operation, the second the
> > patched one. cc is short for clock cycles)
> >
> > Curve keypair generation (ecc_gen_privkey + ecc_make_pub_key):
> >
> > P256:
> >  - 646963ns/op -> 600632ns/op = -7.71%
> >  - 2911300cc/op -> 2702854cc/op = -7.71%
> >  - 4.4999Ghz -> 4.5000Ghz = no difference
> >
> > P384:
> >  - 1239160ns/op -> 1153940ns/op = -7.38%
> >  - 5576250cc/op -> 5192749cc/op = -7.38%
> >  - 4.5000Ghz -> 4.5000Ghz = no difference
> >
> > Shared secret generation (crypto_ecdh_shared_secret):
> >
> > P256:
> >  - 320114ns/op -> 297548ns/op = -7.58%
> >  - 1440521cc/op -> 1338972cc/op = -7.58%
> >  - 4.5000Ghz -> 4.5000Ghz = no difference
> >
> > P384:
> >  - 620768ns/op -> 582560ns/op = -6.55%
> >  - 2793467cc/op -> 2621529cc/op = -6.55%
> >  - 4.5000Ghz -> 4.5000Ghz = no difference
> >
> > The benchmarks clearly indicate a roughly 6-7% performance increase on
> > the public API functions. It also appears that virtme-ng limited the
> > clock speed to 4.5Ghz
> >
> >
> > Micro benchmarks:
> >
> > Since the vli additive functions only rely on u64 being defined, these
> > were run without virtualization and with varying compilers and
> > compiler flags.
> >
> > The microbenchmarks show much more mixed results, depending
> > heavily on the compiler and optimization level used.
> >
> > For instance, on gcc and O2, the vli_add present in the
> > patch is actually 25.3% slower than the original one. I have tracked
> > this down to gcc using a weird way to restore the carry flag after
> > each iteration, causing way more dependent instructions, preventing
> > ILP from executing multiple at once.
> >
> > This is quite interesting, since, as far as I know, the kernel compiles
> > with gcc and O2 by default, yet the macro-level benchmarks still show a
> > performance increase. The effect seems to be reversed when crypto/ecc.c
> > gets compiled. Or maybe the linux kernel uses some additional
> > optimization flags, I am unsure.
> >
> > However, most of the time, the patched version outperforms the original
> > one by a wide margin:
> >  - On clang -O2 or -O3, vli_add and vli_uadd show a 4.074x and 5.384x
> >    speedup.
> >  - On gcc, vli_uadd shows a 74% performance increase at O2,
> >    and a 2.07x speedup at O3.
> >
> > The performance profile of vli_sub and vli_usub is almost identical to
> > that of vli_add and vli_uadd.
> >
> >
> > Assembly comparison:
> >
> > I have put together a piece of code on Compiler explorer, to make sure
> > it compiles on old gcc versions, view instructions and play around with
> > compiler settings.
> >
> > If you would like, you can play around yourself here:
> > https://godbolt.org/z/1jT5zesz8
> >
> > When using clang 22.1 at -O3 -march=lunarlake, the difference between
> > the patched and original version is particularly clear. The patched
> > version produces this assembly in the unrolled vli_add loop:
> >
> > mov     rax, qword ptr [rsi + 8*rcx + 16]
> > adc     rax, qword ptr [rdx + 8*rcx + 16]
> > mov     qword ptr [rdi + 8*rcx + 16], rax
> > mov     rax, qword ptr [rsi + 8*rcx + 24]
> > adc     rax, qword ptr [rdx + 8*rcx + 24]
> > mov     qword ptr [rdi + 8*rcx + 24], rax
> > mov     rax, qword ptr [rsi + 8*rcx + 32]
> > adc     rax, qword ptr [rdx + 8*rcx + 32]
> > mov     qword ptr [rdi + 8*rcx + 32], rax
> > mov     rax, qword ptr [rsi + 8*rcx + 40]
> > adc     rax, qword ptr [rdx + 8*rcx + 40]
> > mov     qword ptr [rdi + 8*rcx + 40], rax
> > mov     rax, qword ptr [rsi + 8*rcx + 48]
> > adc     rax, qword ptr [rdx + 8*rcx + 48]
> >
> > This is basically optimal for an inner loop. It's pure adc and mov
> > instructions. The loop counting part is still nowhere near perfect,
> > and still uses setc instructions. But it is still better than what
> > the original version produces with the same compiler and flags:
> >
> > mov     r10, qword ptr [rsi + 8*rcx]
> > lea     r11, [r10 + rax]
> > add     r11, qword ptr [rdx + 8*rcx]
> > xor     ebx, ebx
> > cmp     r11, r10
> > setb    bl
> > cmove   rbx, rax
> > mov     qword ptr [rdi + 8*rcx], r11
> > mov     rax, qword ptr [rsi + 8*rcx + 8]
> > lea     r10, [rax + rbx]
> > add     r10, qword ptr [rdx + 8*rcx + 8]
> > xor     r11d, r11d
> > cmp     r10, rax
> > setb    r11b
> > cmove   r11, rbx
> > mov     qword ptr [rdi + 8*rcx + 8], r10
> > mov     rax, qword ptr [rsi + 8*rcx + 16]
> > lea     r10, [rax + r11]
> > add     r10, qword ptr [rdx + 8*rcx + 16]
> > xor     ebx, ebx
> > cmp     r10, rax
> > setb    bl
> > cmove   rbx, r11
> > mov     qword ptr [rdi + 8*rcx + 16], r10
> > mov     rax, qword ptr [rsi + 8*rcx + 24]
> > lea     r10, [rax + rbx]
> > add     r10, qword ptr [rdx + 8*rcx + 24]
> > xor     r11d, r11d
> > cmp     r10, rax
> > setb    r11b
> > cmove   r11, rbx
> >
> > This is downright horrendous. that entire block of processes only 4
> > limbs, thats 8 instructions per limb! The add instructions
> > are also not adc instructions, showing that the carry flag is
> > being fully emulated. This demonstrates how even on the newest
> > compilers and at the highest optimization level, still cannot
> > generate hardware carry chains without explicit use of builtins.
> >
> > I should note that not just clang 22.1.0 with -O3 -march=lunarlake
> > does this. Gcc and clang show this behaviour on every version i have
> > tested, regardless of target architecture.
> >
> > I am not very familiar with ARM or RISC-V assembly, but looking at
> > compiler explorer, the effect clearly persists, and in the case of
> > RISC-V actually gets much worse.
> >
> > This affects all architectures across all compilers and compiler
> > flags.
> >
> >
> > If you have gotten this far, thank you for reading this and I am looking
> > forward to any feedback! If you would like any changes to this patch,
> > I am very happy to send a v2.
> >
> >  crypto/ecc.c | 98 ++++++++++++++++++++++++++++++++--------------------
> >  1 file changed, 60 insertions(+), 38 deletions(-)
>
> Patch applied.  Thanks.
> --
> Email: Herbert Xu <[email protected]>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt


Hi,

So about the rewrite of crypto/ecc.c to a constant-time
Montgomery ladder, I'd like to just make sure it is still on the table.

I also have a few questions about the rewrite:

The paper (https://eprint.iacr.org/2020/956.pdf), which is mentioned
in the conversation Lukas sent, uses a different type of curve
than the current implementation. Is a rewrite using entirely different
elliptic curves intended, or is there some other algorithm that
should be used with the existing NIST curves?

The paper also talks about assembly and how to make
it constant-time by avoiding memory operations
and doing everything in registers. Is it intended
to be an Assembly implementation or is C acceptable?
If it is Assembly, I could only reasonably contribute an x64
version.

Regards,
Fabian