c++ - ¿Cómo puedo barajar bits de manera eficiente?
bit-manipulation z-order-curve (7)
Podría usar una tabla de 256 bytes para cada byte de su número de 16 bits, diseñada de modo que se satisfaga su condición par / impar.
Ah, sí, busque tablas para el rescate :) Incluso puede hacerlo con una sola tabla y un turno adicional:
u16 every_other[256] = {
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f,
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f};
u16 segregate(u16 x)
{
return every_other[x & 0xff]
| every_other[(x >> 8)] << 4
| every_other[(x >> 1) & 0xff] << 8
| every_other[(x >> 9)] << 12;
}
Necesito mezclar un entero sin signo de 16 bits de forma que los índices pares se encuentren en el byte inferior, y los índices impares en el byte superior.
input:
fedcba98 76543210 (contiguously numbered)
output:
fdb97531 eca86420 (even and odd separated)
Mi código se ve así en este momento:
typedef unsigned short u16;
u16 segregate(u16 x)
{
u16 g = (x & 0x0001);
u16 h = (x & 0x0004) >> 1;
u16 i = (x & 0x0010) >> 2;
u16 j = (x & 0x0040) >> 3;
u16 k = (x & 0x0100) >> 4;
u16 l = (x & 0x0400) >> 5;
u16 m = (x & 0x1000) >> 6;
u16 n = (x & 0x4000) >> 7;
u16 o = (x & 0x0002) << 7;
u16 p = (x & 0x0008) << 6;
u16 q = (x & 0x0020) << 5;
u16 r = (x & 0x0080) << 4;
u16 s = (x & 0x0200) << 3;
u16 t = (x & 0x0800) << 2;
u16 u = (x & 0x2000) << 1;
u16 v = (x & 0x8000);
return g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v;
}
Me pregunto si hay una solución más elegante que simplemente extraer y cambiar cada bit individualmente.
A favor de ser corto:
unsigned short segregate(unsigned short x)
{
x = (x & 0x9999) | (x >> 1 & 0x2222) | (x << 1 & 0x4444);
x = (x & 0xC3C3) | (x >> 2 & 0x0C0C) | (x << 2 & 0x3030);
x = (x & 0xF00F) | (x >> 4 & 0x00F0) | (x << 4 & 0x0F00);
return x;
}
El enfoque de tabla mostrado por otros es la versión más portátil y probablemente es bastante rápido.
Si desea aprovechar los conjuntos de instrucciones especiales, también existen otras opciones. Para Intel Haswell y versiones posteriores, por ejemplo, se puede utilizar el siguiente enfoque (requiere la extensión del conjunto de instrucciones BMI2):
unsigned segregate_bmi (unsigned arg)
{
unsigned oddBits = _pext_u32(arg,0x5555);
unsigned evenBits = _pext_u32(arg,0xaaaa);
return (oddBits | (evenBits << 8));
}
Existe un recurso web muy conveniente que ayuda a resolver muchos problemas de permutación de bits: Generador de código para permutaciones de bits . En este caso particular, la introducción de "0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15" en esta página produce un código bastante rápido.
Desafortunadamente, este generador de código no puede producir código de 64 bits (aunque cualquiera puede descargar fuentes y agregar esta opción). Entonces, si necesitamos realizar 4 permutaciones en paralelo utilizando instrucciones de 64 bits, debemos extender todas las máscaras de bits involucradas a 64 bits manualmente:
uint64_t bit_permute_step(uint64_t x, uint64_t m, unsigned shift) {
uint64_t t;
t = ((x >> shift) ^ x) & m;
x = (x ^ t) ^ (t << shift);
return x;
}
uint64_t segregate4(uint64_t x)
{ // generated by http://programming.sirrida.de/calcperm.php, extended to 64-bit
x = bit_permute_step(x, 0x2222222222222222ull, 1);
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0cull, 2);
x = bit_permute_step(x, 0x00f000f000f000f0ull, 4);
return x;
}
El nivel de paralelismo se podría aumentar aún más (8 o 16 permutaciones a la vez) con instrucciones SSE. (Y las versiones recientes de gcc pueden vectorizar este código automáticamente).
Si no se requiere el paralelismo y otras partes del programa no utilizan la memoria caché de datos, una mejor alternativa sería utilizar la tabla de búsqueda. Varias aprobaciones de LUT ya se discutieron en otras respuestas, aún se podrían decir algunas más aquí:
- El primer y el último bit de la palabra de 16 bits nunca se permutan, solo debemos barajar los bits 1..14. Entonces (si queremos realizar la tarea con un solo acceso de LUT) es suficiente tener una LUT con entradas de 16K, lo que significa 32K de memoria.
- Podríamos combinar los métodos de búsqueda y cálculo de tablas. Dos búsquedas en una sola tabla de 256 bytes podrían barajar cada byte de origen por separado. Después de esto solo necesitamos intercambiar dos nibbles de 4 bits medios. Esto permite mantener la tabla de búsqueda pequeña, utiliza solo 2 accesos de memoria y no necesita demasiados cálculos (es decir, cálculos de saldos y accesos de memoria).
Aquí está la implementación del segundo enfoque:
#define B10(x) x+0x00, x+0x10, x+0x01, x+0x11
#define B32(x) B10(x+0x00), B10(x+0x20), B10(x+0x02), B10(x+0x22)
#define B54(x) B32(x+0x00), B32(x+0x40), B32(x+0x04), B32(x+0x44)
uint8_t lut[256] = {B54( 0x00), B54( 0x80), B54( 0x08), B54( 0x88)};
#undef B54
#undef B32
#undef B10
uint_fast16_t segregateLUT(uint_fast16_t x)
{
uint_fast16_t low = lut[x & 0x00ff];
low |= low << 4;
uint_fast16_t high = lut[x >> 8] << 4;
high |= high << 4;
return (low & 0x0f0f) | (high & 0xf0f0);
}
Pero el enfoque más rápido (si la portabilidad no es un problema) es usar la instrucción pext del conjunto de instrucciones BMI2 como lo indica Nils Pipenbrinck . Con un par de pext de 64 bits podríamos realizar 4 shuffles de 16 bits en paralelo. Dado que la instrucción pext está diseñada exactamente para este tipo de permutaciones de bits, este enfoque supera fácilmente a todos los demás.
Mesas. ¡Pero créalos en tiempo de compilación!
namespace details {
constexpr uint8_t bit( unsigned byte, unsigned n ) {
return (byte>>n)&1;
}
constexpr uint8_t even_bits(uint8_t byte) {
return bit(byte, 0) | (bit(byte, 2)<<1) | (bit(byte, 4)<<2) | (bit(byte, 6)<<3);
}
constexpr uint8_t odd_bits(uint8_t byte) {
return even_bits(byte/2);
}
template<unsigned...>struct indexes{using type=indexes;};
template<unsigned Max,unsigned...Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...>{};
template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{};
template<unsigned Max>using make_indexes_t=typename make_indexes<Max>::type;
template<unsigned...Is>
constexpr std::array< uint8_t, 256 > even_bit_table( indexes<Is...> ) {
return { even_bits(Is)... };
}
template<unsigned...Is>
constexpr std::array< uint8_t, 256 > odd_bit_table( indexes<Is...> ) {
return { odd_bits(Is)... };
}
constexpr std::array< uint8_t, 256 > even_bit_table() {
return even_bit_table( make_indexes_t<256>{} );
}
constexpr std::array< uint8_t, 256 > odd_bit_table() {
return odd_bit_table( make_indexes_t<256>{} );
}
static constexpr auto etable = even_bit_table();
static constexpr auto otable = odd_bit_table();
}
uint8_t constexpr even_bits( uint16_t in ) {
return details::etable[(uint8_t)in] | ((details::etable[(uint8_t)(in>>8)])<<4);
}
uint8_t constexpr odd_bits( uint16_t in ) {
return details::otable[(uint8_t)in] | ((details::otable[(uint8_t)(in>>8)])<<4);
}
Podría usar una tabla de 256 bytes para cada byte de su número de 16 bits, diseñada de modo que se satisfaga su condición par / impar. Codifique a mano las entradas de la tabla (o use el algoritmo que ya tiene) para crear las tablas, y luego la mezcla se realizará en tiempo de compilación. Eso sería esencialmente un concepto de tabla de traducción.
Su respuesta a la combinación aleatoria de bits pares e impares para 64 bits no es precisa. Para extender la solución de 16 bits a la solución de 64 bits, no solo necesitamos extender las máscaras, sino también cubrir el intervalo de intercambio desde 1 hasta 16:
x = bit_permute_step(x, 0x2222222222222222, 1);
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0c, 2);
x = bit_permute_step(x, 0x00f000f000f000f0, 4);
**x = bit_permute_step(x, 0x0000ff000000ff00, 8);
x = bit_permute_step(x, 0x00000000ffff0000, 16);**