crypto: Keep the safegcd 128-bit sums out of intx::uint128

Aperta
#1,808 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
52/100
Tipo di issue
Refactoring
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
cpp

Direzione di ricerca

Read modarith.cpp and compare the safegcd matrix sum helpers with the two options described in the issue. First check the intx dependency status for chfast/intx#374 and whether it changes the addmul() workaround in #1803; otherwise, assess using unsigned __int128 under INTX_HAS_BUILTIN_INT128 while retaining the existing helpers for 32-bit targets. Done means the chosen approach preserves 32-bit support and is checked against the reported inversion benchmarks.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

The safegcd inversion (#1806) accumulates its matrix products in intx::uint128. GCC splits their carry chains (20 setb in modinv_scaled<uint256>) and keeps the sums partly in stack slots, the same problem as #1801.

Per inversion, Zen 3, random inputs over 4 moduli:

GCC 16 Clang 23
intx v0.15.0 (current) 4640 cycles 4119 cycles
intx master, with chfast/intx#374 (builtin add/sub for GCC, unreleased) −2.2% ±0
intx master, helpers using builtin signed multiply and shift −4.8% +0.8%
sums as unsigned __int128 −5.9% −3.4%

Options:

  1. Release intx with chfast/intx#374 and upgrade it here. Check whether this also makes the GCC workaround in addmul() (#1803) unnecessary.
  2. In modarith.cpp, use unsigned __int128 for the sums when INTX_HAS_BUILTIN_INT128, keeping the intx::uint128 helpers for 32-bit targets. This needs a second set of the 128-bit helpers:
#if INTX_HAS_BUILTIN_INT128
using Int128 = intx::builtin_uint128;  // Two's complement.
uint64_t lo(Int128 x) noexcept { return static_cast<uint64_t>(x); }
uint64_t hi(Int128 x) noexcept { return static_cast<uint64_t>(x >> 64); }
Int128 mul_su(int64_t a, uint64_t b) noexcept
{
    return Int128{static_cast<uint64_t>(a)} * b - (Int128{b & static_cast<uint64_t>(a >> 63)} << 64);
}
Int128 mul_ss(int64_t a, int64_t b) noexcept { return static_cast<Int128>(static_cast<__int128>(a) * b); }
Int128 sar64(Int128 x) noexcept { return static_cast<Int128>(static_cast<__int128>(x) >> 64); }
Int128 sext(int64_t x) noexcept { return static_cast<Int128>(static_cast<__int128>(x)); }
#else
// The current intx::uint128 versions.
#endif

A single generic version, with only the type alias under #if, gives −2.1% (GCC) and −1.7% (Clang). The rest of the gap cannot be closed in intx without changing the storage of uint<128>, whose constexpr word access needs the two uint64_t words.

Lingua principale
C++
Stelle
979
Fork
340
Merge medio
12h 16m
PR unite (30g)
25

Preparare l'ambiente

  • Include un Dockerfile o un file Docker Compose
  • Nessun modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di ipsilon/evmone

Tutte le issue di ipsilon/evmone

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.