x86-64 CPU下128位位串的高效互相关实现优化问询

算力阿峰

2026-4-13

这是一个关于128位数据（Haystack，即目标串）与1-128位数据（Needle，即模式串）的二进制互相关问题，目标是在Intel/AMD x86-64架构CPU上最大化该操作的吞吐量，重点利用SIMD指令集。

由于显示宽度限制，以下示例简化为32位：

模式串完全包含在目标串中的示例：
模式串与目标串部分重叠的示例：
模式串与目标串无关联的示例：

下面的纯C函数CrossCorrelateFwd()实现了上述功能。为了匹配动画示例且不依赖厂商特定的128位扩展，它使用32位参数而非128位参数。

该函数将模式串向右滑动过目标串，找到第一个所有重叠位都匹配的偏移量：

如果所有重叠位都匹配，函数返回k——目标串中匹配后缀开始的索引。
如果没有任何偏移能产生完全匹配，函数返回-1。

位编号规则：bit 0 = 最高位（动画中的最左侧）。
重叠长度计算公式：overlapLen = min(NeedleLen, 32 - k)

#include <stdio.h>
#include <stdint.h>

int8_t CrossCorrelateFwd(uint32_t Haystack, uint32_t Needle, uint8_t NeedleLen)
{
    int shift;

    for (shift = 0; shift < 32; shift++)
    {
        int overlapLen = NeedleLen < (32 - shift) ? NeedleLen : (32 - shift);
        int allMatch = 1;
        int j;

        for (j = 0; j < overlapLen; j++)
        {
            int hBit = (int)((Haystack >> (31 - shift - j)) & 1);  // 从32位值中提取位置'shift + j'的位（0为最高位）
            int nBit = (int)((Needle >> (NeedleLen - 1 - j)) & 1); // 从N位值中提取位置'j'的位（0为最高位）

            if (hBit != nBit)
            {
                allMatch = 0;
                break;
            }
        }

        if (allMatch)
            return (int8_t)shift;
    }

    return -1;
}

// 将二进制字符串转换为32位值的辅助函数
// 仅用于示例，无需用pmovmskb等指令优化
static inline uint32_t S2B(const char* s, uint8_t* slen)
{
    uint32_t i = 0;
    const char* p = s;
    while (*p) {
        i <<= 1;
        i += (*p++ - '0');
    }

    if (slen)
        *slen = (uint8_t)(p - s);

    return i;
}


int main()
{
#define Haystack "11001010010010111010111001101011"  // 固定32位长度
#define Needle   "0001101"

    uint8_t NeedleLen = 0;
    int8_t idxHay = CrossCorrelateFwd(S2B(Haystack, NULL), S2B(Needle, &NeedleLen), NeedleLen);

    if (idxHay<0)
        printf("\t%s\n\t% *s\n", Haystack, 33 + NeedleLen, Needle);
    else
        printf("\t%s\n%u:\t% *s\n",Haystack, idxHay, idxHay + NeedleLen, Needle );

    return 0;
}

这个函数虽然能正常工作，但速度非常慢。当前它处理最多32位的参数，但我们的目标是处理最长128位的参数（刚好填满一个XMM寄存器）。

我希望得到如何利用x86-64 SIMD指令（MSVC内联函数或x86-64汇编）优化吞吐量的建议。

我考虑过SSE4.2的字符串指令——这些指令的功能几乎和CrossCorrelateFwd()一致，但是按字节处理的。而我们需要的是按位的互相关/搜索。或许可以通过循环移位/旋转8次来扩展这些SSE4.2指令，实现按位搜索？

比如PCMPESTRI指令有一个很实用的特性：由于隐式终止处理，当目标串刚好128位长，且在模式串匹配完成前就到了XMM寄存器边界时，如果目标串的后缀等于模式串的前缀，指令会报告匹配。只要数据在1-16字节的XMM寄存器限制内，无论模式串总长度或重叠范围如何，这个特性都成立。

我还考虑过移位 + PXOR + POPCOUNT或者BitScanForward（BSF）等指令组合的方案。

补充说明：
我运行代码的环境是IvyBridge Xeon（支持AVX1 + SSE4.2，仅支持popcnt，无BMI指令），所以需要针对这个平台的高效实现。当然，针对后续新CPU的高效实现我也很感兴趣，最好能兼容MSVC编译。

我的模式串长度完全随机，范围是2到128位。基准测试显示，66%的情况是无匹配结果。目标串长度固定为128位。

备注：内容来源于stack exchange，提问作者George Robinson