Вычисление расстояний Хэмминга до нескольких строк с помощью SSE

У меня есть символьные строки n (8 бит), все из них одинаковой длины (скажем m), а другая строка s той же длины. Мне нужно вычислить расстояния Хэмминга от s до каждой из остальных строк. В plain 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]++;
  }
}

Я хотел бы использовать инструкции SIMD с gcc для более эффективного выполнения таких вычислений. Я прочитал, что PcmpIstrI в SSE 4.2 может быть полезным, и мой целевой компьютер поддерживает этот набор команд, поэтому я бы предпочел решение с использованием SSE 4.2.

EDIT:

Я написал следующую функцию для вычисления расстояния Хэмминга между двумя строками:

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);
}

Это лучшее, что я могу сделать, или могу ли я использовать тот факт, что одна из сравниваемых строк всегда одна и та же? Кроме того, должен ли я выполнять выравнивание по моим массивам для повышения производительности?

ДРУГОЙ ПОПЫТКА

Следуя рекомендациям Гарольда, я написал следующий код:

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

но я не могу сделать окончательное добавление байтов в __m128i, используя psadbw. Может ли кто-нибудь помочь мне в этом?

Ответ 1