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

Question

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

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

Answer 1

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

Предполагая, что 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 

---

Немного лучше вариант предложенный @ Норберт П. Это экономит 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; 
} 

Answer 2

Никогда не забывайте принцип 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 с и ret требуются от x64 ABI: если вы встраивать функцию, они не требуются)

---

для решения комментария VOO по поводу suckiness из MSVC, вы можете использовать следующее:

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

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