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

我有n（8位）字符串，它们全都具有相同的长度（如m），而另一个字符串s的长度相同。我需要计算从s到其他每个字符串的汉明距离。在普通的C，如：使用SSE计算与几个字符串的汉明距离

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]++; 
    } 
}

我想使用SIMD指令与gcc更有效地执行这样的计算。我已经读过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); 
}

这是我能做的最好的事情还是我可以使用这样一个事实，即所比较的字符串之一总是相同的？另外，我应该在阵列上进行一些调整以提高性能？

另一种尝试

继哈罗德的recomendation，我已经写了下面的代码：

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。任何人都可以帮助我吗？

来源

2013-07-28 pepeStck

究竟什么是你的问题？ – andy256

实际上'pcmpistri'根本没用，在这种情况下你只需要一个普通的'pcmpeqb'。而且你也不需要任何popcnt-stuff，只需从count中减去比较结果（因为结果是-1，它们是不同的），最后是psadbw它们（或者如果你的字符串是4K或更长的时间，'psadbw'就在处理4K字节之前） – harold

感谢harold，虽然我无法使用psadbw，但我发布了我的尝试。 – pepeStck

这是你的最新程序，该程序使用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)); 
    } 
}

来源

2015-10-19 08:16:54

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

回答

相关问题