Bit Reverse Algorithmus

[derMischka]

Da ich gerade mit FFT arbeite brauche ich eine Funktion, die schnell die Bitumkehrung eines Wertes variabler Bitbreite zurückgibt.

von MSB->LSB zu LSB->MSB

zur Zeit habe ich folgende Umsetzungen:

Variante 1:

Delphi-Quellcode:

function BitRev(inBit{eax}: Cardinal; BitCount{edx}: integer): Cardinal;
asm
  xor  ecx, ecx     // ecx := 0
  test edx, edx     // ist edx = 0?
  jz @Ende          // wenn ja springe zu Ende
  @Loop:
    shr eax, 1      // eax nach rechts schieben -> unterstes Bit ins Carry-Flag
    rcl ecx, 1      // ecx nach links über Carry rotieren
    dec edx         // dec(edx)
   jnz @Loop        // wenn edx <> 0 --> springe zu Loop
  @Ende:
end;

Variante 2:

Delphi-Quellcode:

function BitRev(inBit{eax}: Cardinal; BitCount{edx}: integer): Cardinal;
asm
  mov ecx, edx
  lea edx, [eax * 2]
  shr eax, 1
  and edx, $AAAAAAAA
  and eax, $55555555
  or  eax, edx
  lea edx, [eax * 4]
  shr eax, 2
  and edx, $CCCCCCCC
  and eax, $33333333
  or  eax, edx
  lea edx, [eax * 8]
  shl edx, 1
  shr eax, 4
  and edx, $F0F0F0F0
  and eax, $0F0F0F0F
  or  eax, edx
  bswap eax
  rol eax, cl
end;

habt ihr vielleicht einen noch schnelleren Ansatz ohne LookUpTable?

der Mischka

[Sherlock]

Warum nicht Lookup? Das scheint eigentlich der Stand der Technik zu sein, wenn es schnell sei muss. Zumal es ohne (für manche Menschen) unverständlichen Assemblercode auskommt.

Sherlock

[derMischka]

Zitat:

Warum nicht Lookup?

Da ich bei meiner Aufgabe viel Speicherdurchsatz auf verschiedenen Adressen habe, wäre es toll, wenn für so ein "triviales" Problem alles auf Register-Ebene passiert.

Bei großen Datenmengen wird immer mehr die Speicherbandbreite der limitierende Faktor.

der Mischka

[Neutral General]

Zitat:

Zitat von derMischka (Beitrag 1375082)

Da ich bei meiner Aufgabe viel Speicherdurchsatz auf verschiedenen Adressen habe, wäre es toll, wenn für so ein "triviales" Problem alles auf Register-Ebene passiert.
Bei großen Datenmengen wird immer mehr die Speicherbandbreite der limitierende Faktor.

Hast du das mal ausprobiert?
Ein Lookup ist quasi nur ein mov-Befehl.
Gefühlt (ich habs nicht getestet) sollte das unabhängig vom Speicher am schnellsten sein.
Allein weil es deutlich weniger Taktzyklen benötigt als eine Umrechnung.

[Sherlock]

Eine wie auch immer geartete Assemblerlösung (mit einer Ausnahme) ist immer langsamer als eine simple LUT. Welche Ausnahme? Eine Assemblerimplementierung einer LUT. ;)

Zu Deinem Problem der variablen Länge: Ich gehe davon aus, daß sich die Bitfolge immer glatt in Nibbles aufteilen läßt, dann brauchst Du eine kleine Tabelle mit 16 Einträgen, gegen Die Du die Nibbles laufen läßt, und vertauscht dann deren Reihenfolge. Das sollte zwei bis drei Kernkriterien der Softwareentwicklung erfüllen: Einfach, Lesbar, Wartbar.

Wenn Du immer glatt in Bytes aufteilen kannst, dann machst Du eine größere Tabelle (256 Einträge) und mußt weniger Folgenteile vertauschen.

Diskussion dazu zB hier: https://stackoverflow.com/questions/...byte-in-delphi insbesondere in der akzeptierten Lösung von seiner Delphihaftigkeit David Heffernan.

Sherlock

[derMischka]

Zitat:

Zu Deinem Problem der variablen Länge: Ich gehe davon aus, daß sich die Bitfolge immer glatt in Nibbles aufteilen läßt

Nein, z.B. 9 Bit sind auch möglich.

selbst eine Assembler LUT version wäre nicht so klein ...

Pseudo-Asm-Code

Code:

  // eax = Value
  // edx = BitCount
  movzx ecx, al
  mov   cl, [LUT + ebx]
  movzx ebx, ah
  mov   ch, [LUT + ebx]
  shr   eax, 16
  movzx ebx, al 
  mov   bl, [LUT + ebx]
  shr   eax, 8
  mov   bh, [LUT + eax]
  or    ebx, ecx
  bswap ebx
  mov   ecx, edx
  rol   ebx, cl
  mov   eax, ebx

[freimatz]

Ich fand da interesasnt:

Zitat:

Note: LUT (lookup table) timings are probably rather optimistic here. Due to running in tight loop the whole table was sucked into L1 CPU cache. In real computations this function most probably would be called much less frequently and L1 cache would not keep the table entirely.

D.h. selbst wenn der Code mit LUT schneller ist, kann es passieren dass dadurch anderer Code langsamer wird weil die LUT andere Daten in im Cache verdrängt.

[derMischka]

Zitat:

D.h. selbst wenn der Code mit LUT schneller ist, kann es passieren dass dadurch anderer Code langsamer wird weil die LUT andere Daten in im Cache verdrängt.

Genau das meine ich!!!
Deshalb suche ich Anregungen für eine schnelle Umsetzung ohne LUT.

der Mischka

[Rollo62]

Ich vermute mal deine Lösung entspricht dem:
https://stackoverflow.com/questions/...o-lsb-msb-in-c

Du könntest ja auch mal den Algorithmus in Delphi schreiben und schauen was er im Assembler daraus macht.
Ichkönnte mir vorstellen das Delphi sowas ganz gut optimieren kann.

Rollo

[freimatz]

Was ist denn das Maximum für BitCount 32? Eine Idee wäre noch 32 Varianten für jedes Bitcount der Methode zu machen und über eine Tabelle mit Index Bitcount anzuspringen. Intern kannst du dann die Loop ausrollen.