Algoritmo per espansione/duplicazione bit?

Esiste un algoritmo (veloce) efficiente che eseguirà l'espansione/duplicazione di bit?Algoritmo per espansione/duplicazione bit?

Ad esempio, espandere ogni bit in un valore 8bit da 3 (creando un valore 24bit):

1101 0101 => 11111100 01110001 11000111

Il metodo di forza bruta che è stato proposto è quello di creare una tabella di ricerca. In futuro, potrebbe essere necessario che il valore di espansione sia variabile. Cioè, nell'esempio sopra ci stiamo espandendo per 3 ma potrebbe essere necessario espandere di alcuni altri valori. Ciò richiederebbe più tabelle di ricerca che vorrei evitare, se possibile.

fonte

2012-01-26 jivany

Se si tratta solo di valori a 8 bit, la tabella di ricerca è quasi sicuramente l'opzione migliore. Usa pochissimo spazio. Puoi fornire maggiori dettagli sul tuo caso d'uso e su quali operazioni ti aspetti di essere comuni? – templatetypedef

L'input è un flusso di bit seriale costante. Nell'attuale requisito, ogni blocco di dati arriva a 8 byte alla volta, il che richiede quindi che ogni bit espanso per 3 venga inviato come un altro flusso di bit. 64 bit in 192 bit fuori. Un requisito futuro può comportare l'aggiunta di bit "header" prima di ogni valore espanso a 8 bit e, naturalmente, il riempimento su un limite di byte. Le LUT sono veloci ma, vista la frequenza con cui è necessario eseguirle, qualsiasi potenziale miglioramento delle prestazioni sarebbe apprezzato. – jivany

Molte architetture dispongono di istruzioni che possono velocizzare notevolmente questo tipo di calcolo. Se non hai paura di rompere la compatibilità multipiattaforma facendo leva su queste istruzioni è quasi certamente una vittoria - e se stai ottimizzando qualcosa che questo algoritmicamente "banale", allora la chiave per l'ottimizzazione a basso livello è fondamentale. – Kaganar

C'è una possibilità di renderlo più veloce della tabella di ricerca se i calcoli aritmetici sono per qualche motivo più veloci dell'accesso alla memoria. Questo può essere possibile se i calcoli sono vettorizzati (PPC AltiVec o Intel SSE) e/o se altre parti del programma devono utilizzare ogni bit di memoria cache.

Se fattore di espansione = 3, sono necessari solo 7 istruzioni:

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7;

O altra alternativa, con 10 istruzioni:

out = (in | in << 8) & 0x0F00F; 
out = (out | out << 4) & 0x0C30C3; 
out = (out | out << 2) & 0x249249; 
out *= 7;

Per altri fattori di espansione> = 3:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = out * ((1 << shift) + 1) & mask; 
} 
out *= (1 << N) - 1;

o altra alternativa, per fattori di espansione> = 2:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = (out | out << shift) & mask; 
} 
out *= (1 << N) - 1;

shift e mask valori da calcolare prima dell'elaborazione del flusso di bit.

fonte

2012-01-28 08:54:21

Risposta fantastica.Il mio collega e io ci siamo avvicinati a questo mentre facevamo un po 'di brainstorming di lavagna a mano e lavagna ma questo è molto più efficiente del nostro approccio. Dovrò eseguire alcuni test una volta implementato il resto del codice e vedere come funziona. – jivany

Qualcuno ha un collegamento con la matematica dietro questo? Ho cercato in giro ma sono riuscito a trovare la magia senza una spiegazione su come funziona. Vedo che c'è qualche schema per i numeri magici, ma tutto il resto mi sfugge. –

nvm, l'ho capito. Aiuta a scrivere il binario e poi trova il modello. Tuttavia, qualsiasi link sull'argomento sarebbe molto apprezzato. https://gist.github.com/corytodd/056ed01228f59fee9a13d00fc25b9a62 –

È possibile eseguire un bit di input alla volta. Naturalmente, sarà più lento di una tabella di ricerca, ma se si sta facendo qualcosa come scrivere per un microcontroller a 8 bit, senza spazio sufficiente per un tavolo, dovrebbe avere il più piccolo impronta ROM possibile.

fonte

2012-01-26 21:37:47 comingstorm

Algoritmo per espansione/duplicazione bit?

risposta

Problemi correlati