contador SSE de 128 bits

Question

Necesito una función de una variable __m128i que tenga un período de 2^128. No necesita aumentar monótonamente (como un contador), pero visite cada valor una vez.

El ejemplo más simple que pude pensar es en realidad un contador de 128 bits, pero me pareció difícil de implementar en SSE. ¿Hay alguna solución más simple/más rápida?

Answer 1

Aquí hay un contador monótono. Aunque no estoy seguro si puedes llamarlo simple.

Suponiendo que ONE y ZERO están siempre en registros, entonces esto debería compilarse a 5 instrucciones. (7 o 8 si VEX-codificación no se utiliza)

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

Código de prueba (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; 
} 

de salida:

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

---

Ligeramente mejor versión sugerido por @ Norbert P. Guarda 1 instrucción sobre mi solución original.

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

Nunca olvide el principio KISS.

pegar (se requieren enteros sin signo para envolver alrededor de la norma C, por lo tanto visitar cada valor sólo una vez) esto:

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

en this rendimientos (para x64):

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

fácil /¿suficientemente rapido? Si en línea que, es probable que sea capaz de salirse con sólo los addq/adcq (los movq s ret y está obligado por la ABI x64: si la función en línea, que no están obligados)

---

para abordar el comentario de Voo sobre la suckiness de MSVC, puede utilizar el siguiente:

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

no tengo un MSVC instalar cerca, así que no puedo probarlo, pero debería rendimiento algo similar a lo que publique arriba. Entonces, si realmente necesita un __m128i, debería poder cast las dos mitades.