Reordenar poco bits

Question

Necesito hacer un reordenamiento arbitrario de un valor de 7 bits (Sí, sé que debería estar usando una tabla) y me pregunto si hay hacks de bits para hacer esto.

Ejemplo:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

---

editar: Estaba pensando en algo como esto

Sólo por diversión y porque estaba AFTK Estoy intentando una búsqueda de fuerza bruta para encontrar soluciones de la forma:

((In * C1) >> C2) & 0x7f

No se encontraron soluciones.

Answer 1

Echa un vistazo a la salida del compilador de tu " ingenuo " código, puede sorprenderte. Una vez hice algo así y el compilador (VC ++ 2005) cambió por completo los valores de todos los ands y cambios para que sean más eficientes, por ejemplo, estoy seguro de que eliminaría su " (0x001 & amp; In) > > 3 " ;.

Pero sí, si la reorganización es una función fija, entonces una tabla es probablemente la mejor.

Actualizar

Por una risa miré la salida del compilador de VC ++ 2005 ....

Primero probé un valor constante para " In " pero el compilador no fue engañado ni un poco, produjo este código:

mov eax,469h

es decir. Lo optimizó completamente.

Entonces ... probé una entrada adecuada y obtuve esto:

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx 

Son cuatro operaciones de turno, cinco AND, cuatro OR, no está mal para seis entradas. Probablemente mejor de lo que la mayoría de la gente podría hacer a mano.

Probablemente también esté optimizado para la ejecución fuera de orden, por lo que será menos ciclos de reloj de lo que parece. :-)

Answer 2

El primer paso parece ser comprender una solución matemática y optimizarla.

vea aquí hacks de bits

Answer 3

Hay un montón de hacks de twitsdling para operaciones comunes, es decir, para invertir el orden de los bits en una palabra de 32 bits (10 de desplazamiento, AND y OR, AFAICR).

En este caso, con una asignación aparentemente completamente arbitraria de entrada a salida, no veo ninguna forma de limpiar esto.

Usa una tabla de búsqueda :)

Answer 4

Antes de optimizar, debes asegurarte de que tu forma "ingenua" es hacer lo que pretendes. Si hago su código en una función y ejecuto este bucle:

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

Produce esta salida, que contradice los comentarios. De hecho, pierde bits.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

Para obtener el orden aleatorio que describe, lo codificaría así:

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;