bit permutation

[tib (Gast)]

Hallo!

Ich habe 8 Register mit natürlich 64 Bit. Diese sollen nun nach 
folgender Vorschrift permutiert werden: p(i) = i + i*15 mod 63, für i = 
0..63, d.h. wenn das alte erste Register so aussah: 0,1,2,3,4,5,6,7 usw. 
soll das neue so aussehen: 0,4,8,12,16,20,24,28 usw. Bisher habe ich 
dafür immer Shifts benutzt, d.h. ich leere ein Register und verteile so 
die Bits auf die entsprechenden Register. Diese Art der Permuation ist 
aber mit 128 Zyklen (2 pro Bit: Bit holen und Bit draufschieben) sehr 
ineffizient. Hat damit vielleicht jemand Erfahrung, wie man so etwas 
effizient implementieren kann, in (AVR) Assembler. Gibt es da eine 
Möglichkeit das als Look Up Table zu realisieren?

[Florian (Gast)]

Eine Lookup-Tabelle mit 64 bit wäre aber doch schon relativ groß. Ich 
befürchte, soviel Speicher wirst Du nicht am AVR anschließen können bzw. 
bezahlen wollen.

[Peter D. (peda)]

tib wrote:

> die Bits auf die entsprechenden Register. Diese Art der Permuation ist
> aber mit 128 Zyklen (2 pro Bit: Bit holen und Bit draufschieben) sehr
> ineffizient.

Warum ist das (6,4µs) ineffizient ?

Wie schnell kommen die Daten rein, wie müssen sie noch verarbeitet 
werden und wie schnell gehen sie raus ?

Wenn das alles zusammen wesentlich kürzer als 6,4µs dauert, dann ist es 
wirklich ineffizient.


Peter

[A.K. (Gast)]

Eine einzige Tabelle geht natürlich nicht, aber die Input-Bytes lassen 
sich ja unabhängig voneinander auf jeweils 8 Bytes output abbilden, die 
dann zusammenaddiert werden. Macht 8*8 Tabellen mit je 256 Bytes = 16KB.

Der Haken daran: Das ist noch langsamer.