如何在ARM Neon上实现按位异或前缀奇偶性？含实现与fallback方案

背景 #

该函数的作用是为输入整数的每个比特位，计算其右侧所有比特位的奇偶性（异或累加结果）。以下是参考用的朴素O(n)实现：

template <unsigned_integral T>
constexpr T bitwise_exclusive_prefix_parity_naive(T x)
{
    constexpr int N = std::numeric_limits<T>::digits;

    T result = 0;
    bool parity = false;
    for (int i = 0; i < N; ++i) {
        result |= static_cast<T>(parity) << i;
        parity ^= (x >> i) & 1;
    }

    return result;
}

static_assert(bitwise_exclusive_prefix_parity_naive(0b0000'0000u) == 0b0000'0000);
static_assert(bitwise_exclusive_prefix_parity_naive(0b1111'1111u) == 0b1010'1010);
static_assert(bitwise_exclusive_prefix_parity_naive(0b1001'0000u) == 0b1110'0000);
static_assert(bitwise_exclusive_prefix_parity_naive(0b0100'1000u) == 0b0111'0000);

通过无进位乘法（CLMUL）可将复杂度优化到O(1)，核心逻辑等价于计算CLMUL(x, -2)。目前已完成x86平台的实现，现需添加ARM Neon（禁用SVE2）的高效实现，相关代码进展如下：

#include <x86intrin.h> // only on x86
#include <arm_neon.h>  // only on ARM

template <std::unsigned_integral T>
constexpr T bitwise_exclusive_prefix_parity(T x)
{
    constexpr int N = std::numeric_limits<T>::digits;

#ifdef __PCLMUL__ // x86
    if (!consteval) {
        if constexpr (N <= 64) {
            const __m128i x_128 = _mm_set_epi64x(0, x);
            const __m128i neg2_128 = _mm_set_epi64x(0, -2);
            const __m128i result_128 = _mm_clmulepi64_si128(x_128, neg2_128, 0);
            return _mm_extract_epi64(result_128, 0) & T(-1);
        }
    }
#endif
    x <<= 1;
    for (int i = 1; i < N; i <<= 1) {
        x ^= x << i;
    }
    return x;
}

问题与解答 #

1. 如何使用vmull_p64实现该功能？是否需要运行时检查？ #

vmull_p64是ARM Neon的64位多项式无进位乘法指令，和x86的CLMUL逻辑完全一致，只需计算x与-2的无进位乘积，取低64位即可得到结果。

实现代码

在原有模板函数中添加ARM Neon分支：

#ifdef __ARM_FEATURE_CRYPTO // ARMv8+ Crypto扩展，包含vmull_p64
    if (!consteval) {
        if constexpr (N <= 64) {
            uint64x1_t x_neon = vcreate_u64(x);
            uint64x1_t neg2_neon = vcreate_u64(-2ULL);
            // 执行无进位多项式乘法，得到128位结果
            uint128x1_t result_neon = vmull_p64(x_neon, neg2_neon);
            // 提取低64位并转换为目标类型
            return static_cast<T>(vgetq_lane_u64(result_neon, 0));
        }
    }
#endif

关于运行时检查

• 如果目标平台仅针对ARMv8-A及以上架构，无需运行时检查：vmull_p64是ARMv8 Crypto扩展的标配指令，支持该架构的设备通常都包含此扩展。
• 如果需要兼容ARMv7等旧架构，则需要运行时检测：可通过Linux平台的getauxval(AT_HWCAP)检查HWCAP_NEON_CRYPTO标志，或读取系统寄存器判断是否支持多项式乘法指令。

2. 若需要运行时检查，不使用SVE2的情况下，最优的fallback实现是什么？ #

当前代码中已实现的分治法就是最优的fallback方案，时间复杂度为O(log n)，是位并行的高效实现：

x <<= 1;
for (int i = 1; i < N; i <<= 1) {
    x ^= x << i;
}
return x;

该逻辑通过逐步将高位的奇偶性信息扩散到低位，比朴素循环效率高得多，同时支持constexpr编译期计算，完全满足可移植性要求。

内容的提问来源于stack exchange，提问作者Jan Schultke