Bits de orden superior: Tómelos y conviértase en uint64_t en uint8_t

Question

Digamos que tiene uint64_t y solo se preocupa por el bit de orden superior para cada byte en su uint64_t. De este modo:

uint32_t: 0000 ... 0000 1000 0000 1000 1000 0000 1000 0000 ---> 0000 1111

¿Hay una manera más rápida que:

return 
    (
    ((x >> 56) & 128)+ 
    ((x >> 49) & 64)+ 
    ((x >> 42) & 32)+ 
    ((x >> 35) & 16)+ 
    ((x >> 28) & 8)+ 
    ((x >> 21) & 4)+ 
    ((x >> 14) & 2)+ 
    ((x >> 7) & 1) 
    ) 

Aka desplazamiento x, ¿Enmascarar y agregar el bit correcto para cada byte? Esto compilará mucho ensamblaje y estoy buscando una forma más rápida ... La máquina que estoy usando solo tiene las instrucciones SSE2 y no pude encontrar operaciones SIMD útiles.

Gracias por la ayuda.

Answer 1

Como mencioné en un comentario, pmovmskb hace lo que quiere. He aquí cómo se podría utilizar:

MMX + SSE1:

movq mm0, input ; input can be r/m 
pmovmskb output, mm0 ; output must be r 

SSE2:

movq xmm0, input 
pmovmskb output, xmm0 

Y busqué la nueva forma

BMI2:

mov rax, 0x8080808080808080 
pext output, input, rax ; input must be r 

Answer 2

usted no necesita todas las AND lógicos separados, puede simplificar a:

x &= 0x8080808080808080; 
return (x >> 7) | (x >> 14) | (x >> 21) | (x >> 28) | 
     (x >> 35) | (x >> 42) | (x >> 49) | (x >> 56); 

(suponiendo que el tipo de retorno de la función es uint8_t).

También puede convertir eso a un bucle desenrollado:

uint8_t r = 0; 

x &= 0x8080808080808080; 

x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
x >>= 7; r |= x; 
return r; 

No estoy seguro de lo que se obtienen mejores resultados en la práctica, aunque yo tiendo a apostar en la primera - la segunda podría producir un código más corto pero con una larga cadena de dependencia

Answer 3

Y he aquí cómo hacerlo usando SSE intrínsecos:

#include <xmmintrin.h> 
#include <inttypes.h> 
#include <stdio.h> 

int main (void) 
{ 
    uint64_t x 
    = 0b0000000010000000000000001000000000000000100000000000000010000000; 

    printf ("%x\n", _mm_movemask_pi8 ((__m64) x)); 
    return 0; 
} 

funciona bien con:

gcc -msse 

Answer 4

Esto parece funcionar:

return (x & 0x8080808080808080) % 127; 

Answer 5

En primer lugar, realmente no necesita tantas operaciones. Puede actuar en más de un bit a la vez:

x = (x >> 7) & 0x0101010101010101; // 0x0101010101010101 
x |= x >> 28;      // 0x????????11111111 
x |= x >> 14;      // 0x????????????5555 
x |= x >> 7;      // 0x??????????????FF 
return x & 0xFF; 

Una alternativa es usar módulo para hacer adiciones laterales. Lo primero es tener en cuenta que x % n es la suma de los dígitos en la base n+1, por lo que si n+1 es 2^k, está agregando grupos de k bits. Si comienza con t = (x >> 7) & 0x0101010101010101 como anteriormente, desea sumar grupos de 7 bits, por lo que t % 127 sería la solución. Pero t%127 funciona solo para resultados de hasta 126.0x8080808080808080 y cualquier cosa anterior dará resultado incorrecto. He intentado algunas correcciones, ninguna fue fácil.

Intentando usar módulo para ponernos en la situación en la que solo era posible el último paso del algoritmo anterior. Lo que queremos es mantener los dos bits menos significativos, y luego tener la suma de la otra, agrupados por 14. Así

ull t = (x & 0x8080808080808080) >> 7; 
ull u = (t & 3) | (((t>>2) % 0x3FFF) << 2); 
return (u | (u>>7)) & 0xFF; 

Pero t >> 2 es t/4 y < < 2 se multiplica por 4. Y si tenemos (a % b)*c == (a*c % b*c), entonces (((t>>2) % 0x3FFF) << 2) es (t & ~3) % 0xFFFC. Pero también tenemos el hecho de que a + b% c = (a + b)% c si es menor que c. Entonces simplemente tenemos u = t % FFFC. Dando:

ull t = ((x & 0x8080808080808080) >> 7) % 0xFFFC; 
return (t | (t>>7)) & 0xFF; 

Answer 6

return ((x & 0x8080808080808080) * 0x2040810204081) >> 56; 

obras. El & selecciona los bits que desea conservar. Las multiplicaciones de todos los bits en el byte más significativo, y el cambio los mueve al byte menos significativo. Como la multiplicación es rápida en la mayoría de las CPU modernas, esto no debería ser mucho más lento que con el ensamblaje.