本问题是关于将一个128位的值（Haystack）与另一个1–128位的值（Needle）进行二进制互相关，目的是在x64位模式下的英特尔/AMD x86 CPU上最大化该操作的吞吐量，重点关注它们的SIMD指令。

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

下面是一个Needle包含在Haystack中的示例：

下面是一个Needle部分重叠Haystack的示例：

下面是一个与Haystack无相关性的Needle的示例：

以下的函数 CrossCorrelateFwd()，用普通C 语言编写，实现了上面所示的功能。为了与动画匹配并保持简洁且可与所有C 编译器兼容（无论厂商的128位扩展如何），它接收32位参数而不是128位。

它将Needle向 Haystack右滑，找到所有重叠位都匹配的第一次位移。

如果每一对重叠位都匹配，函数返回 k —— Haystack中匹配后缀开始的位置的索引。
如果没有某个位移产生完整的重叠匹配，函数返回 -1。

位编号：位0 = MSB（动画中的最左边的位）。
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);  // Extract bit at position 'shift + j' (0 = MSB) from a 32-bit value.
            int nBit = (int)((Needle >> (NeedleLen - 1 - j)) & 1); // Extract bit at position 'j' (0 = MSB) from an N-bit value.

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

        if (allMatch)
            return (int8_t)shift;
    }

    return -1;
}

// Boilerplate function to convert binary string into 32 bit binary 
// Only used for this example, not useful to optimize with pmovmskb etc.
value (uint32_t)
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"  //Always 32 bits long.
#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 intrinsics或 x86-64汇编来优化吞吐量的建议。

也许可以使用SSE4.2的字符串指令，因为这些指令已经在很大程度上实现了 CrossCorrelateFwd() 的功能，但按字节进行（参见 this question），而这里需要的是按位的互相关/搜索。也许可以将这些SSE4.2字符串指令扩展，通过在循环中对位进行移位/轮换8 次来实现按位搜索。

例如，PCMPESTRI指令由于隐式终止处理，展示了一个非常有用的按字节的末端部分匹配行为怪癖。当haystack恰好为128位，并在needle完成之前结束（由于XMM寄存器边界的部分重叠），如果haystack的后缀等于needle的前缀，则指令报告匹配。无论needle的总长度或重叠的程度如何，只要所有数据仍然在1–16字节的XMM寄存器约束内，这一规律就成立。

我也在考虑shift + PXOR + POPCOUNT或 BitScanForward (BSF) 等组合...

我在IvyBridge Xeon上运行（AVX1 + SSE4.2，且没有BMI仅有 popcnt）因此需要一个在这里也快的版本。同样，任何在后续CPU上也快的版本也会有趣。最好能够用MSVC编译。

我的Needle长度真正是任意的——从2 到128位。基准测试显示非匹配率为66%。Haystack的大小始终恰好是128位。

解决方案

你所做的本质上是一个按位子串搜索（互相关），你的代码之所以慢，是因为逐位比较并且使用嵌套循环（在32位示例中最坏情况约32×32次运算，在真实问题中约128×128次）。

在x86-64上加速的关键是以整寄存器（64/128位）而非逐位来工作，使用XOR来检测不匹配，用位掩码仅测试重叠区域。

这单独已经比你的代码快约20–50倍，

#include <stdint.h>
#include <immintrin.h>

int CrossCorrelate128(uint64_t hi, uint64_t lo,
                      uint64_t nhi, uint64_t nlo,
                      int NeedleLen)
{
    for (int shift = 0; shift < 128; shift++)
    {
        int overlap = NeedleLen < (128 - shift) ? NeedleLen : (128 - shift);

        __uint128_t H = ((__uint128_t)hi << 64) | lo;
        __uint128_t N = ((__uint128_t)nhi << 64) | nlo;

        __uint128_t aligned = N << (128 - NeedleLen - shift);

        __uint128_t mask = (((__uint128_t)1 << overlap) - 1)
                         << (128 - shift - overlap);

        if (((H ^ aligned) & mask) == 0)
            return shift;
    }

    return -1;
}

并且这也完全消除了按位提取的需要。