将 16 字节字符串与 SSE 进行比较

Question

我有 16 字节 'strings'（它们可能更短，但您可以假设它们末尾用零填充），但您可能不会假设它们是 16 字节对齐的（至少不总是） .

如何编写将它们与 SSE 内在函数进行比较（为了相等）的例程？我发现这段代码片段可能会有帮助，但我不确定它是否合适？

register __m128i xmm0, xmm1; 
register unsigned int eax; 

xmm0 = _mm_load_epi128((__m128i*)(a)); 
xmm1 = _mm_load_epi128((__m128i*)(b)); 

xmm0 = _mm_cmpeq_epi8(xmm0, xmm1); 

eax = _mm_movemask_epi8(xmm0); 

if(eax==0xffff) //equal 
else   //not equal

有人可以解释一下或者写一个函数体吗？

它需要在 GCC/mingw 中工作（在 32 位 Windows 上）。

Answer 1

向量比较指令将其结果作为掩码，根据相应源之间的比较，元素全为 1（真）或全为 0（假）元素。

请参阅 https://whosebug.com/tags/x86/info 以获取一些链接，这些链接将告诉您这些内在函数的作用。

问题中的代码看起来应该可以工作。

如果您想找出哪些元素不相等，请使用 movemask 版本（pmovmskb 或 movmskps）。您可以 tzcnt / bsf 对第一个匹配项进行位扫描，或 popcnt 对匹配项进行计数。完全相等给你一个 0xffff 掩码，不相等给你 0.

您可能想知道 SSE4.1 ptest 在这里是否有用。它是可用的，但实际上并没有更快，特别是如果您对结果进行分支而不是将其转换为布尔值 0 / -1。

 // slower alternative using SSE4.1 ptest
__m128i avec, bvec;
avec = _mm_loadu_si128((__m128i*)(a)); 
bvec = _mm_loadu_si128((__m128i*)(b)); 

__m128i diff = _mm_xor_si128(avec, bvec);  // XOR: all zero only if *a==*b

if(_mm_test_all_zeros(diff, diff))  { //equal 
} else {   //not equal 
}

在 asm 中，ptest 是 2 微指令，并且不能与 jcc 条件分支宏融合。因此前端的总 pxor + ptest + 分支是 4 微指令，并且仍然会破坏其中一个输入，除非您有 AVX 将异或结果放入第三个寄存器。

pcmpeqb xmm0, xmm1 / pmovmskb eax, xmm0 / cmp/jcc 总共是 3 微指令，在 Intel 和 AMD CPU 上 cmp/jcc 融合成 1 微指令。

如果您有更宽的元素，您可以在 pcmpeqd/q 的结果上使用 movmskps 或 movmskpd 以获得 4 位或 2 位掩码。如果您想在不除以每个元素 4 或 8 个字节的情况下进行位扫描或 popcnt，这将非常有用。（或者使用 AVX2，8 位或 4 位而不是 32 位掩码。）

ptest 只是一个好主意，如果您不需要任何额外的指令来为其构建输入：测试是否为全零，有或没有掩码。例如检查每个元素或某些元素中的某些位。

Answer 2

好吧，我不确定这是否会更快，但可以通过单个 SSE 4.2 指令完成：检查 PCMPISTRI（压缩比较隐式长度字符串，Return 索引）进位and/or 溢出标志：

if (_mm_cmpistrc(a, b, mode))   // checks the carry flag (not set = equal)
  // equal
else
  // unequal

模式将是（针对您的情况）：

const int mode = 
  SIDD_UBYTE_OPS |         // 16-bytes per xmm
  SIDD_CMP_EQUAL_EACH |    // strcmp
  SIDD_NEGATIVE_POLARITY;  // find first different byte

不幸的是，这条指令的文档很少。因此，如果有人找到合适的资源来汇总所有模式组合和生成的标志，请分享。

Answer 3

我会尽力帮助解决被遗忘的有人可以解释这个问题的一部分吗。

register __m128i xmm0, xmm1; 
register unsigned int eax;

这里我们声明了一些变量。 __m128i 是 SSE 寄存器整数运算的内置类型。请注意，变量的名称根本无关紧要，但作者将它们命名为与在汇编中调用相应的 CPU 寄存器完全相同。 xmm0、xmm1、xmm2、xmm3、……都是SSE操作的寄存器。 eax 是通用寄存器之一。

register 关键字很久以前就被用来建议编译器将变量放在 CPU 寄存器中。今天它完全没用了，我想。有关详细信息，请参阅 this question。

xmm0 = _mm_loadu_si128((__m128i*)(a)); 
xmm1 = _mm_loadu_si128((__m128i*)(b));

此代码已按照@harold 的建议进行了修改。这里我们从给定的内存指针（可能未对齐）加载 16 个字节到变量 xmm0 和 xmm1。在汇编代码中，这些变量很可能直接位于寄存器中，因此该内在函数会产生未对齐的内存负载。将指针转换为 __m128i* 类型是必要的，因为 intrinsic 接受这种指针类型，尽管我不知道英特尔为什么这样做。

xmm0 = _mm_cmpeq_epi8(xmm0, xmm1);

这里我们比较 xmm0 变量中的每个字节与 xmm1 变量中的相应字节是否相等。后缀 _epi8 表示对 8 位元素，即字节进行操作。它有点类似于 memcmp(&xmm0, &xmm1, 16)，但会生成其他结果。它 return 是一个 16 字节的值，其中包含 0xFF 代表每个具有相同值的字节，以及 0x00 代表每个具有不同值的字节。

eax = _mm_movemask_epi8(xmm0);

这是SSE2中的一条非常重要的指令，通常用于编写带有某些SSE条件的if语句。它从 XMM 参数中的 16 个字节中的每一个中取出最高位，并将它们写入一个 16 位整数。在汇编级别，这个数字位于通用寄存器中，允许我们在之后快速检查它的值。

if(eax==0xffff) //equal 
else   //not equal

如果两个 XMM 寄存器的所有 16 个字节都相等，则 _mm_cmpeq_epi8 必须 return 一个设置了所有 128 位的掩码。 _mm_movemask_epi8 将 return 完整的 16 位掩码，即 0xFFFF。如果任何两个比较的字节不同，相应的字节将由 _mm_cmpeq_epi8 填充为零，因此 _mm_movemask_epi8 将 return 16 位掩码与相应的位 not 设置，所以它会小于 0xFFFF.

此外，这里是封装在函数中的解释代码：

bool AreEqual(const char *a, const char *b) {
  __m128i xmm0, xmm1; 
  unsigned int eax; 
  xmm0 = _mm_loadu_si128((__m128i*)(a)); 
  xmm1 = _mm_loadu_si128((__m128i*)(b)); 
  xmm0 = _mm_cmpeq_epi8(xmm0, xmm1); 
  eax = _mm_movemask_epi8(xmm0); 
  return (eax == 0xffff); //equal 
}

将 16 字节字符串与 SSE 进行比较

Compare 16 byte strings with SSE

c

gcc

x86

sse

simd