128-битный счетчик SSE? - PullRequest
Новая
       39

128-битный счетчик SSE?

7 голосов
/ 19 февраля 2012

Мне нужна функция переменной __m128i с периодом 2 ^ 128. Не нужно монотонно увеличивать (например, счетчик), но посещать каждое значение один раз.

Самый простой пример, который я мог бы вспомнить, - это на самом деле 128-битный счетчик, но я обнаружил, что его трудно реализовать в SSE. Есть ли более простые / быстрые решения?

Ответы [ 2 ]

5 голосов
/ 19 февраля 2012

Вот монотонный счетчик.Я не уверен, что вы можете назвать это простым.

Если предположить, что и ONE, и ZERO всегда находятся в регистрах, то это должно скомпилировать 5 инструкций.(7 или 8, если VEX-кодирование не используется) 

inline __m128i nextc(__m128i x){
    const __m128i ONE = _mm_setr_epi32(1,0,0,0);
    const __m128i ZERO = _mm_setzero_si128();

    x = _mm_add_epi64(x,ONE);
    __m128i t = _mm_cmpeq_epi64(x,ZERO);
    t = _mm_and_si128(t,ONE);
    t = _mm_unpacklo_epi64(ZERO,t);
    x = _mm_add_epi64(x,t);

    return x;
}

Тестовый код (MSVC): 

int main() {

    __m128i x = _mm_setr_epi32(0xfffffffa,0xffffffff,1,0);

    int c = 0;
    while (c++ < 10){
        cout << x.m128i_u64[0] << "  " << x.m128i_u64[1] << endl;
        x = nextc(x);
    }

    return 0;
}

Выход: 

18446744073709551610  1
18446744073709551611  1
18446744073709551612  1
18446744073709551613  1
18446744073709551614  1
18446744073709551615  1
0  2
1  2
2  2
3  2

Немного лучшая версия, предложенная @Norbert P. Она сохраняет 1 инструкцию по сравнению с моим исходным решением. 

inline __m128i nextc(__m128i x){
    const __m128i ONE = _mm_setr_epi32(1,0,0,0);
    const __m128i ZERO = _mm_setzero_si128();

    x = _mm_add_epi64(x,ONE);
    __m128i t = _mm_cmpeq_epi64(x,ZERO);
    t = _mm_unpacklo_epi64(ZERO,t);
    x = _mm_sub_epi64(x,t);

    return x;
}
4 голосов
/ 19 февраля 2012

Никогда не забывайте принцип KISS.

Вставьте это (целые числа без знака необходимо обернуть по стандарту C, следовательно, посещая каждое значение только один раз): 

__uint128_t inc(__uint128_t x) {
  return x+1;
}

в this выходы (для x64): 

    addq    $1, %rdi
    adcq    $0, %rsi
    movq    %rdi, %rax
    movq    %rsi, %rdx
    ret

достаточно просто / быстро?Если вы включите это, вы, вероятно, сможете обойтись только с addq / adcq (movq s и ret требуются ABI x64: если вы встроите функцию, они необязательно)

Чтобы ответить на комментарий Воо о непристойности MSVC, вы можете использовать следующее: 

inline void inc(unsigned long long *x, unsigned long long *y) {
  if (!++*x) ++*y; // yay for obfuscation!
}

У меня нет установки MSVC поблизости, поэтому я не могупротестируйте его, но должно привести к чему-то похожему на то, что я выложил выше.Затем, если вам действительно нужен __m128i, вы сможете разыграть две половинки.

...