如何计算 ARM Neon 上的按位独占前缀奇偶校验？

Question

我有一个特定的功能，我需要使其便携且高效。 这是简单的实现，仅供参考：

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);

简而言之，该函数计算每个位严格右侧的奇偶校验。

可以使用多种技术来击败这种简单的 O(n) 实现。 最值得注意的是，它相当于

CLMUL(x, -2)

，其中

CLMUL

是无进位乘法。 这是我迄今为止的进展：

#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;
}

x86 版本似乎可以正常工作。我想为 ARM Neon 添加一个案例。

不应该使用SVE2，因为SVE2我根本不需要这个功能。 最容易实现的目标是使用

vmull_p64

并基本上执行 x86 版本的操作，但我听说 64 到 128 位版本是可选的，您必须在运行时检查是否可用。

问题

• 您将如何使用

  vmull_p64

  实现这一点，是否需要运行时检查？
• 如果是，下一个最好的后备实现是什么 没有 SVE2？

Answer 1

这是一个可移植的

O(log N)

解决方案，适用于右侧的位，包括当前位（对于严格位于右侧的位，只需乘以 2）：

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

    T result = x;
    for (int i = 1; i < N; i*=2) {
        result ^= result << i;
    }

    return result; 
}