Add ARM PMULL support#100
Draft
jharveyb wants to merge 4 commits into
Draft
Conversation
MulWithClMulReduce and MulTrinomial had the SSE intrinsics inlined
throughout. This refactor routes every intrinsic call through static-inline
wrappers (ClmulLoad64, ClmulExtract64, ClmulAsPoly, Clmul00, Clmul01,
ClmulXor, ClmulOr, ClmulSrliEpi64<N>, ClmulSlliEpi64<N>, ClmulSrliBytes<N>)
and introduces two type aliases:
Clmul128 — 128-bit in-flight data (shifts, XOR, OR operate on this).
ClmulPoly — the type PCLMULQDQ / PMULL wants as operand.
On x86 these are both __m128i and the ClmulAsPoly conversion is the
identity. A future ARM backend can make them distinct (uint64x2_t vs
poly64x2_t) so the PMULL wrappers read naturally without obscuring the
lane-shift code with poly64 casts. The alias split also makes MOD128's
role — a pre-loaded multiplication constant — explicit.
Lane-shift wrappers are templates so the shift amount stays a compile-time
immediate, matching the x86 intrinsic requirement (and the ARM NEON
requirement a future patch will rely on).
No call sites outside this header are affected; the eight
clmul_{1..8}byte*.cpp files remain intrinsic-free.
Both autotools (configure.ac) and CMake (cmake/SystemIntrospection.cmake) now try -mpclmul first and, on hosts where that fails, fall back to -march=armv8-a+crypto (aarch64). Whichever check succeeds sets the same HAVE_CLMUL and CLMUL_CXXFLAGS that the rest of the build system already consumes. HAVE_CLMUL now means "a carryless-multiply ISA is available," not specifically x86 CLMUL. ENABLE_CLMUL is widened to ENABLE_CLMUL || ENABLE_PMULL. A host only has one carryless-multiply ISA, so the fallback chain compiles with the flag that actually matches the target. MSVC ARM64 is deliberately excluded — it uses a different header and flag convention and is out of scope here.
The wrapper functions introduced by the previous refactor now have two implementations selected at compile time: __PCLMUL__ -> x86 (PCLMULQDQ) __ARM_FEATURE_CRYPTO / __ARM_FEATURE_AES -> ARMv8 (PMULL/PMULL2) The ARM backend uses the dual-type alias the refactor set up: Clmul128 = uint64x2_t — in-flight data (lane shifts, XOR, OR) ClmulPoly = poly64x2_t — vmull_p64 operand type PMULL operands are extracted via vgetq_lane_p64 from poly64x2_t. Modern aarch64 compilers (GCC 13+, Clang 19+) fuse vgetq_lane_p64 + vmull_p64 into a direct PMULL with NEON register operands, so values stay in the SIMD pipeline without SIMD->GPR roundtrips. MOD128 is pre-loaded once as a ClmulPoly at the top of MulWithClMulReduce and reused across reduction rounds, avoiding per-call re-materialization. MulWithClMulReduce uses only the 0x00 and 0x01 imm8 selectors of x86 PCLMULQDQ — i.e. lo(a)xlo(b) and hi(a)xlo(b). Those map to vmull_p64 on lane-0/lane-0 and lane-1/lane-0 respectively. vmull_high_p64 (PMULL2) isn't needed. Scalar loads use vsetq_lane_p64 into a zero-initialized vector, mirroring the x86 _mm_cvtsi64_si128 semantics (payload in lane 0, lane 1 zero). Lane-shift wrappers map to vshrq_n_u64 / vshlq_n_u64 directly; byte-shift maps via vextq_u8 against a zero vector. A compile-time #error fires if neither ISA is selected, so accidental inclusion in a non-accelerated build fails loudly instead of silently falling back.
Extend the existing x86 CPUID check with ARM-specific branches so that
the same EnableClmul() gate works on either ISA. Dispatch is on
architecture predefined macros (__x86_64__/__i386__/_M_X64/_M_IX86 vs
__aarch64__/__arm__/_M_ARM64), then on OS:
Apple always true (A7+ and Apple Silicon have PMULL)
Windows IsProcessorFeaturePresent(PF_ARM_V8_CRYPTO_INSTRUCTIONS_AVAILABLE)
Linux getauxval(AT_HWCAP) & HWCAP_PMULL (aarch64)
getauxval(AT_HWCAP2) & HWCAP2_PMULL (arm32)
FreeBSD elf_aux_info(AT_HWCAP, ...)
other true (trust the compile-time gate)
The FieldImpl enum, extern declarations, and Construct() dispatch are
unchanged — impl=CLMUL on an ARM build now maps to the PMULL-backed
MulWithClMulReduce, transparently to library consumers.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
PMULL is the equivalent of the x86 CLMUL instruction for accelerating polynomial multiplication. It's available on many recent ARMv8 chips that support the Cryptography Extension instructions, such as the Broadcom BCM2712 in the Raspberry Pi 5, as well as older chips like the Rockchip RK3399 (used in many Raspberry Pi alternatives).
This PR extends the CLMUL implementation to use PMULL via ARMv8 intrinsics, if support was detected at build time. This provides a 2-4x speedup for sketch decoding, across almost all field element sizes, sketch sizes, and sketch error counts.
The raw data used for these plots, the modified bench.cpp code used to generate the data, and Python code to explore that data and generate other plots, are on this branch:
https://github.com/jharveyb/minisketch/commits/pmull_benching/
The TSV-formatted results are in
doc/benchmark_results.This PR as-is is passing existing tests, and feature detection at build time works. Left in draft as I'm looking for feedback on the build-time feature detection, and on this approach vs. having a completely separate templated impl in a separate file from the original CLMUL implementation. This option seemed like a smaller diff overall.
Further reference material:
https://developer.arm.com/architectures/instruction-sets/intrinsics/#q=pmull