Riordino bit twiddling

Question

Devo fare un riordino arbitrario di un valore di 7 bit (Sì, lo so che dovrei usare una tabella) e mi chiedo se ci sono alcuni bit hack per farlo.

Esempio:

// <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

---

modifica: Stavo pensando a qualcosa del genere di this

Solo per calci e dato che ero AFTK sto provando una ricerca della forza bruta per trovare soluzioni nella forma:

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

Nessuna soluzione trovata.

Answer 1

Dai un'occhiata all'output del compilatore del tuo " ingenuo " codice, potrebbe sorprenderti. Una volta ho fatto qualcosa del genere e il compilatore (VC ++ 2005) ha completamente cambiato i valori di tutti gli ands e i turni per renderli più efficienti, ad esempio sono sicuro che rimuoverà il tuo " (0x001 & In) > > 3 ".

Ma sì, se il rimpasto è una funzione fissa, probabilmente una tabella è la migliore.

Aggiorna

Per una risata ho guardato l'output del compilatore da VC ++ 2005 ....

Per prima cosa ho provato un valore costante per " In " ma il compilatore non è stato ingannato un po ', ha prodotto questo codice:

mov eax,469h

es. l'ha completamente ottimizzato.

Quindi ... ho provato un input corretto e ho ottenuto questo:

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 

Sono quattro operazioni a turni, cinque AND, quattro OR - non male per sei ingressi. Probabilmente meglio di quanto la maggior parte delle persone potrebbe fare a mano.

Probabilmente è anche ottimizzato per l'esecuzione fuori servizio, quindi saranno meno cicli di clock di quanto sembri. : -)

Answer 2

Il primo passo sembra essere capire una soluzione matematica e ottimizzarla.

vedi qui bit hack

Answer 3

Esistono molti hack di bit-twiddling per operazioni comuni, cioè per invertire l'ordine dei bit in una parola di 32 bit (10 ciascuno di shift, AND e OR, AFAICR).

In questo caso, con una mappatura apparentemente completamente arbitraria da input a output, non riesco a vedere alcun modo di ripulirlo.

Utilizza una tabella di ricerca :)

Answer 4

Prima di ottimizzare, dovresti assicurarti che il tuo modo "ingenuo" stia facendo ciò che intendi. Se trasformo il tuo codice in una funzione ed eseguo questo ciclo:

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

Produce questo output, che contraddice i commenti. In effetti, perde bit.

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

Per ottenere lo shuffle che descrivi, lo scriverei in questo modo:

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