Bits di ordine elevato: prendili e crea un uint64_t in un uint8_t

Question

Supponiamo che tu abbia un uint64_t e che si preoccupi solo del bit di ordine elevato per ogni byte nel tuo uint64_t. In questo modo:

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

Esiste un modo più veloce di:

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 spostamento x, mascherando e aggiungendo il bit corretto per ogni byte? Questo compilerà per un sacco di assembly e sto cercando un modo più veloce ... La macchina che sto usando ha solo fino alle istruzioni SSE2 e non sono riuscito a trovare utili SIMD ops.

Grazie per l'aiuto.

Answer 1

Come ho menzionato in un commento, pmovmskb fa quello che vuoi. Ecco come si potrebbe usare:

MMX + SSE1:

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

SSE2:

movq xmm0, input 
pmovmskb output, xmm0 

E ho guardato il nuovo modo

BMI2:

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

Answer 2

non avete bisogno di tutte le AND logiche separate, è possibile semplificare a:

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

(assumendo che il tipo di funzione di ritorno è uint8_t).

È inoltre possibile convertire che per un loop srotolato:

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; 

non sono sicuro che sarà un rendimento migliore, in pratica, anche se mi piacerebbe tendo a puntare al primo - il secondo potrebbe produrre codice più corto ma con una lunga catena di dipendenza.

Answer 3

Ed ecco come farlo usando SSE intrinseche:

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

funziona bene con:

gcc -msse 

Answer 4

Questo sembra funzionare:

return (x & 0x8080808080808080) % 127; 

Answer 5

In primo luogo non si ha realmente bisogno di tante operazioni. È possibile agire su più di un bit alla volta:

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

Un'alternativa è utilizzare modulo per eseguire aggiunte laterali. La prima cosa da notare è che x % n è la somma delle cifre nella base n+1, quindi se n+1 è 2^k, si aggiungono gruppi di k bit. Se si inizia con t = (x >> 7) & 0x0101010101010101 come sopra, si desidera sommare gruppi di 7 bit, quindi t % 127 sarebbe la soluzione. Ma t%127 funziona solo per risultati fino a 126.0x8080808080808080 e qualsiasi cosa sopra darà risultati errati. Ho provato alcune correzioni, nessuna dove facile.

Provare a utilizzare il modulo per metterci nella situazione in cui è presente solo l'ultimo passaggio dell'algoritmo precedente. Quello che vogliamo è quello di mantenere i due bit meno significativi, e quindi avere la somma degli altri uno, raggruppati per 14. Quindi

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

Ma t >> 2 T/4 e < < 2 è moltiplicando per 4. E se abbiamo (a % b)*c == (a*c % b*c), quindi (((t>>2) % 0x3FFF) << 2) è (t & ~3) % 0xFFFC. Ma abbiamo anche il fatto che a + b% c = (a + b)% c se è inferiore a c. Quindi abbiamo semplicemente u = t % FFFC. Dare:

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

Answer 6

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

opere. Il & seleziona i bit che si desidera conservare. La moltiplicazione di tutti i bit nel byte più significativo e lo spostamento li sposta nel byte meno significativo. Poiché la moltiplicazione è veloce sulla maggior parte delle CPU moderne, non dovrebbe essere molto più lenta rispetto all'utilizzo di assembly.