使用SSE计算多个字符串的汉明距离

Question

我有n个（8位）字符字符串，它们的长度都相同（假设为m），还有另一个长度相同的字符串s。我需要计算从s到其他每个字符串的汉明距离。在纯C语言中，可以像下面这样实现：

unsigned char strings[n][m];
unsigned char s[m];
int distances[n];

for(i=0; i<n; i++) {
  int distances[i] = 0;
  for(j=0; j<m; j++) {
    if(strings[i][j] != s[j])
      distances[i]++;
  }
}

我想使用gcc和SIMD指令，以更高效地执行这些计算。我已经了解到，在SSE 4.2中，PcmpIstrI可能会很有用，并且我的目标计算机支持该指令集，因此我更喜欢使用SSE 4.2来解决这个问题。

编辑：

我编写了以下函数来计算两个字符串之间的汉明距离:

static inline int popcnt128(__m128i n) {
  const __m128i n_hi = _mm_unpackhi_epi64(n, n);
  return _mm_popcnt_u64(_mm_cvtsi128_si64(n)) + _mm_popcnt_u64(_mm_cvtsi128_si64(n_hi));
}

int HammingDist(const unsigned char *p1, unsigned const char *p2, const int len) {
#define MODE (_SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_EACH | _SIDD_BIT_MASK | _SIDD_NEGATIVE_POLARITY)
  __m128i smm1 = _mm_loadu_si128 ((__m128i*) p1);
  __m128i smm2 = _mm_loadu_si128 ((__m128i*) p2);
  __m128i ResultMask;

  int iters = len / 16;
  int diffs = 0;
  int i;

  for(i=0; i<iters; i++) {
    ResultMask = _mm_cmpestrm (smm1,16,smm2,16,MODE); 

    diffs += popcnt128(ResultMask);
    p1 = p1+16;
    p2 = p2+16;
    smm1 = _mm_loadu_si128 ((__m128i*)p1);
    smm2 =_mm_loadu_si128 ((__m128i*)p2);
  }

  int mod = len % 16;
  if(mod>0) {
     ResultMask = _mm_cmpestrm (smm1,mod,smm2,mod,MODE); 
     diffs += popcnt128(ResultMask);
  }

  return diffs;
} 

那么我可以通过以下方式解决我的问题：

for(i=0; i<n; i++) {
  int distances[i] = HammingDist(s, strings[i], m);
}

这是我能做到的最好吗？还是我可以利用一个字符串始终相同的事实来优化比较？此外，我是否应该对我的数组进行一些调整以提高性能？

另一次尝试

根据Harold的建议，我编写了以下代码：

void _SSE_hammingDistances(const ByteP str, const ByteP strings, int *ds, const int n, const int m) {
    int iters = m / 16;

    __m128i *smm1, *smm2, diffs;

    for(int j=0; j<n; j++) {
        smm1 = (__m128i*)  str;
        smm2 = (__m128i*)  &strings[j*(m+1)]; // m+1, as strings are '\0' terminated

        diffs =  _mm_setzero_si128();

        for (int i = 0; i < iters; i++) {
            diffs = _mm_add_epi8(diffs, _mm_cmpeq_epi8(*smm1, *smm2));
            smm1 += 1;
            smm2 += 1;
        }

        int s = m;
        signed char *ptr = (signed char *) &diffs;
        for(int p=0; p<16; p++) {
            s += *ptr;
            ptr++;
        }

        *ds = s;
        ds++;
    }
}

但是我无法使用 psadbw 对 __m128i 中的字节进行最后的相加。请问有人能帮我解决这个问题吗？

- pepeStck

---

你的问题是什么？ - andy256

实际上，pcmpistri 在这种情况下一点用处都没有，你只需要一个普通的 pcmpeqb 就可以了。而且你也不需要任何 popcnt 的东西，只需将比较结果从计数中减去（因为结果为 -1 表示不同），最后再使用 psadbw 进行处理（或者如果你的字符串长度超过4K，就在处理4K字节之前使用 psadbw）。 - harold

谢谢Harold，我已经发布了我的尝试，尽管我无法使用psadbw。 - pepeStck

如果psadbw的操作数之一为零，则只会将另一个操作数的字节相加。你可以使用它来替代执行水平求和的循环。不过，psadbw按8块进行求和，因此您仍然需要提取2个字并将它们相加。顺便说一句，我注意到您正在添加比较结果，您可以这样做，但结果将为负数（对于psadbw而言，这是不好的-它将字节视为无符号而不是符号扩展） - harold

请记住，您的 i 循环不能超过 255 次迭代，否则会导致字节溢出。 在最后，您可以尝试将 i 循环展开 2 或 4 次，看看是否有利可图。 - stgatilov

Answer 1

这是您最新程序的改进版，它使用 PSADBW （ _mm_sad_epu8 ）来消除标量代码：

void hammingDistances_SSE(const uint8_t * str, const uint8_t * strings, int * const ds, const int n, const int m)
{
    const int iters = m / 16;

    const __m128i smm1 = _mm_loadu_si128((__m128i*)str);

    assert((m & 15) == 0);      // m must be a multiple of 16

    for (int j = 0; j < n; j++)
    {
        __m128i smm2 = _mm_loadu_si128((__m128i*)&strings[j*(m+1)]); // m+1, as strings are '\0' terminated

        __m128i diffs = _mm_setzero_si128();

        for (int i = 0; i < iters; i++)
        {
            diffs = _mm_sub_epi8(diffs, _mm_cmpeq_epi8(smm1, smm2));
        }

        diffs = _mm_sad_epu8(diffs, _mm_setzero_si128());
        ds[j] = m - (_mm_extract_epi16(diffs, 0) + _mm_extract_epi16(diffs, 4));
    }
}

- Paul R