SIMD：逐个字符比较两个字符串并找出匹配的总数

Question

我正在开发一种生物信息学工具。我对应用 SIMD 来提高其速度感兴趣。给定两个长度相等的字符串，我想快速计算两个字符串具有相同字符的索引总数。

例如，假设我们有 S1="AATTGGCCAAC" 和 S2="AATTCTCCAAC"。然后，由于它们的长度为 11，并且仅在位置 5 和 6 处不同（S1 中的“GG”和 S2 中的“CT”），因此输出应为 9。

这是我到目前为止所拥有的：

#include <string>
#include <immintrin.h>
using namespace std;
#include <memory.h>
int main()
{
 register __m128i str_A, str_B, char_eq;


str_A = _mm_load_si128((__m128i*)("AATTGGCCAAC")); 
str_B = _mm_load_si128((__m128i*)("AATTCTCCAAC")); 

char_eq = _mm_cmpeq_epi8(str_A, str_B); 

}

字符串比较似乎工作正常。

uint8_t val[11];
    memcpy(val, &char_eq, sizeof(val));
    printf("Numerical: %i %i %i %i %i %i %i %i %i %i %i \n", 
           val[0], val[1], val[2], val[3], val[4], val[5], 
           val[6], val[7],val[8], val[9], val[10]);          
}

，输出 255 255 255 255 0 0 255 255 255 255 255

现在我有一个名为 char_eq 的寄存器 __m128i 对象，其中包含有关每个字符是否匹配或不匹配的信息。如何将此 __m128i char_eq 对象转换为编码匹配字符数的整数？ 我能想到的唯一方法是手动添加布尔值（即 1+1+1+1+0+0+1+1+1+1+1），但这违背了使用 SIMD 的目的，因为这将需要 length(str) 添加次数。

查找两个字符串中匹配字符总数的最快方法是什么？我希望能做到 O(1)。预先感谢您！

Answer 1

int _mm_movemask_epi8 (__m128i a)

以 16 位值的形式返回 a 中 16 个 8 位值的最高位。 如果该值为 (1<<16)-1, all bits are set, i.e. all 16 bytes matched.

如果要检查前 n 个字节 (1 <= n <= 16), you can check if result >= (1<