Assembler: Reihenfolge eines Bitfelds umdrehen

[theomega]

Hallo Leute,
ich such einen einfachen Assembler-Befehl der die Reihenfolge der Bits in einem Byte umdreht:
Es soll also aus
12345678
das werden:
87654321
mit den Ziffern meine ich natürlich die Stellen nicht den Wert (Der kann ja nur 0 oder 1 sein).

Wer kann mir helfen?

Danke
TO

[Olli]

BSWAP ist dein Freund.

[theomega]

Hy,
danke für die schnelle Antwort, leider bringt mich der Tip nicht weiter, denn der Befehl wird von meinem Microkontroller nicht unterstzütz. Es handelt sich hierbei um einen AVR von Atmel, also um einen 8bit-Controller.
Sonst noch jemand eine Idee?
Danke auf jeden Fall
TO

[Olli]

Zitat:

Zitat von theomega

danke für die schnelle Antwort, leider bringt mich der Tip nicht weiter, denn der Befehl wird von meinem Microkontroller nicht unterstzütz. Es handelt sich hierbei um einen AVR von Atmel, also um einen 8bit-Controller.

LOL, irgendwie vermisse ich diesen Hinweis in der Ausgangsfrage ;)

Du kannst es "manuell" machen. Hast du Rotate- und Shift-Befehle zur Verfügung in deinem ASM? Am besten gib mal einen Link zur Prozessordoku.

[theomega]

Hy,
ja, ich gebe zu, ich hätte die Info reinschreiben müßen, sorry.

Hier ist eine Befehlsliste für den MC:
http://www.avr-asm-tutorial.net/avr_.../commands.html

Wäre super wenn du mir helfen könntest

Gruß und Danke
TO

[Nothine]

Zitat:

Zitat von theomega

Hy,
danke für die schnelle Antwort, leider bringt mich der Tip nicht weiter, denn der Befehl wird von meinem Microkontroller nicht unterstzütz. Es handelt sich hierbei um einen AVR von Atmel, also um einen 8bit-Controller.
Sonst noch jemand eine Idee?
Danke auf jeden Fall
TO

naja, es gibt (laut der dokumentation in deinem letzten post) durchaus einen äquivalenten befehl mit namen SWAP, aber da du (soweit ich das ersehen kann) nicht vorhast nur die nibbles zu vertauschen, bringt es dich im endeffekt auch nicht weiter. ich hab mir das mal durchgelesen und möchte dich vor allem auf ROR und ROL hinweisen, die durchaus die gewünschte funktionalität bieten, du kannst es allerdings nicht mit nur einem befehl realisieren (verbessere mich wer wenn ich falsch liege).

[SirThornberry]

so gehts

Delphi-Quellcode:

function RotateLeft(Value: Longint;Rotate: Byte): Longint; assembler;
asm
   mov     cl, dl
   rol     eax, cl
end;

function RotateRight(Value: Longint; Rotate: Byte): Longint; assembler;
asm
   mov     cl, dl
   ror     eax, cl
end;

sollte also mit einer anweisung getan sein da die zweite hier wohl dazu dient das ganze auf result zu schieben (kenn mich da nicht so aus mit asm)

[Nothine]

Zitat:

Zitat von SirThornberry

sollte also mit einer anweisung getan sein da die zweite hier wohl dazu dient das ganze auf result zu schieben (kenn mich da nicht so aus mit asm)

das problem in diesem fall besteht in der tatsache das ROL und ROR die reihenfolge der bits durchaus beibehalten, z.B.:

Code:

Bit#: 76543210
Bits: 10101100
--------------
rol 2
--------------
Bit#: 76543210
Bits: 10110010

er will aber (natürlich nur sofern ich das richtig verstanden habe) die bitreihenfolge komplett umdrehen, und das ist nicht so ohne weiteres möglich, dafür brauchts schon ein wenig (aber wirklich nur ein wenig :wink:) mehr

(und es geht net um standard inline-assembler, wie aus der ersten antwort von theomega deutlich wird)

[negaH]

Delphi-Quellcode:

{reverse the bit order from a integer}
function SwapBits(Value, Bits: LongWord): LongWord; register;
asm
       BSWAP  EAX
       MOV    ECX,EAX
       AND    EAX,0AAAAAAAAh
       AND    ECX,055555555h
       SHR    EAX,1
       SHL    ECX,1
       OR     EAX,ECX
       MOV    ECX,EAX
       AND    EAX,0CCCCCCCCh
       AND    ECX,033333333h
       SHR    EAX,2
       SHL    ECX,2
       OR     EAX,ECX
       MOV    ECX,EAX
       AND    EAX,0F0F0F0F0h
       AND    ECX,00F0F0F0Fh
       SHR    EAX,4
       SHL    ECX,4
       OR     EAX,ECX
       AND    EDX,01Fh
       JZ     @@1
       MOV    ECX,32
       SUB    ECX,EDX
       SHR    EAX,CL
@@1:
end;

aus meinem DEC,

gruß Hagen

[Flocke]

[offtopic]

@Hagen: wo ich deinen Assembler-Code gerade so sehe: kann man da an zwei Stellen nicht noch etwas (zugegeben: minimal) optimieren, indem man Zuweisung + links Schieben durch LEA mit Faktor ersetzt? Die beiden Operanden für OR haben ja keine gemeinsamen Bits, also kann man statt dessen auch einfach addieren.

(das Semikolon soll einen Kommentar einleiten. Ich weiß jetzt aus dem Kopf nicht mehr, ob der Delphi-Assembler das unterstützt)

Code:

{reverse the bit order from a integer}
function SwapBits(Value, Bits: LongWord): LongWord; register;
asm
       BSWAP  EAX

       LEA    ECX,[2*EAX]    ; <-- x2 schon drin
      ;MOV    ECX,EAX
       AND    EAX,0AAAAAAAAh
       AND    ECX,0AAAAAAAAh ; <--
       SHR    EAX,1
      ;SHL    ECX,1          ; <--
       OR     EAX,ECX

       LEA    ECX,[4*EAX]    ; <-- x4 schon drin
      ;MOV    ECX,EAX
       AND    EAX,0CCCCCCCCh
       AND    ECX,0CCCCCCCCh ; <--
       SHR    EAX,2
      ;SHL    ECX,2          ; <--
       OR     EAX,ECX

       MOV    ECX,EAX
       AND    EAX,0F0F0F0F0h
       AND    ECX,00F0F0F0Fh
       SHR    EAX,4
       SHL    ECX,4
       OR     EAX,ECX
       AND    EDX,01Fh
       JZ     @@1
       MOV    ECX,32
       SUB    ECX,EDX
       SHR    EAX,CL
@@1:
end;

oder (2. Variante)

Code:

{reverse the bit order from a integer}
function SwapBits(Value, Bits: LongWord): LongWord; register;
asm
       BSWAP  EAX

       MOV    ECX,EAX
       AND    EAX,0AAAAAAAAh
       AND    ECX,055555555h
       SHR    EAX,1
       LEA    EAX,[EAX+2*ECX]  ;<-- Keine gemeinsamen Bits
      ;SHL    ECX,1
      ;OR     EAX,ECX

       MOV    ECX,EAX
       AND    EAX,0CCCCCCCCh
       AND    ECX,033333333h
       SHR    EAX,2
       LEA    EAX,[EAX+4*ECX]  ;<-- Keine gemeinsamen Bits
      ;SHL    ECX,2
      ;OR     EAX,ECX

      ;MOV    ECX,EAX
       LEA    ECX,[4*EAX]      ;<-- Erstes x4
       AND    EAX,0F0F0F0F0h
       AND    ECX,03C3C3C3Ch   ;<--
       SHR    EAX,4
       LEA    EAX,[EAX+4*ECX]  ;<-- Zweites x4
      ;SHL    ECX,4
      ;OR     EAX,ECX

       AND    EDX,01Fh
       JZ     @@1
       MOV    ECX,32
       SUB    ECX,EDX
       SHR    EAX,CL
@@1:
end;

Ich weiß natürlich nicht, ob das irgendwelche negativen Einflüsse auf den Instruction-Cache hat und die ganze Sache ggf. vielleicht doch langsamer macht.

[/offtopic]

[Phistev]

BSWAP steht theomega doch nicht zur Verfügung :roll: Also bringt Hagen's Idee nicht unbedingt etwas

[theomega]

Danke für die vielen Antworten, ich habe es inzwischen durch ein achtfaches rausschieben links und wieder reinschieben auch links gelöst. Dummerweise braucht die Sache damit 16 Prozessorzyklen, ist ein bischen ärgerlich, aber es funktioniert zumindest.

Gruß
TO

[negaH]

@Flocke: ja diese optimierungen wären möglich, natürlich sollte man dann wieder einige OpCodes in ihrer reihenfolge verschieben. Das bewirkt dann das der Code auf Piplined CPU's (alle neueren CPU's) wieder schneller ausgeführt werden kann.

Das BSWAP EAX kann ohne Problem vermieden werden.

16 Taktzyklen für eine Schleifenbasierte Lösung halte ich für zu optimistisch. Ich würde eher ca. 64 Zyklen abschätzen wollen. Das liegt am Konstruktionsdesign der heutigen CPU's. Diese CPU's bevorzugen Atomare, Flag-unabhängige und parallelisierbare Instruktionen. Im Grunde sind also Operationen wie RCL,ROL,ROR,RCR das genaue Gegenteil von "guten" Instruktionen auf neueren CPU's. Verschlimmert wird das dann noch wenn diese OpCodes in einer Schleife programmiert werden. Zu den rein theoretischen Taktzyklen muß man dann noch einige Branches, Misses und Waitstates in den U/V Pipelines hinzu rechnen. Das macht die 16 Taktzyklen Angabe eher unwahrscheinlich.

Ganz im Gegensatz dazu steht mein Source. Dieser vermischt die Registerbenutzung, Flagauswertungen und Abhängigkeiten der einzelnen Register, so daß der Code quasi in parallel in zwei Pipelines getrennt ablaufen kann. Statt für 2 OpCodes 2 Taktzyklen zu benötigen werden diese 2 OpCodes nur noch 1 Taktzyklus benötigen, ergo der Code läuft doppelt so schnell als die theoretisch errechneten Taktzyklen laut OpCodes. Hinzukommt dann noch das der Source nur einen einzigsten Branch besitzt, der Hauptcode ist also ein unrolled und Schleifenloser Code. Solch Code kann durch die CPU viel viel schneller abgearbeitet werden.
In meinen eigenen Test's habe ich auf einem P4/1.5Ghz eine Durchschnittliche Laufzeit von 10 Taktzyklen gemessen.

@Flocke: obige Ausführungen erklären auch warum ich den LEA Trick vermieden habe, dieser OpCode kann nur in der U Pipeline der CPU ausgeführt werden, im Gegensatz zu MOV,SHR,SHL,ADD,SUB,OR,AND usw. Es ist (nach meinem Gefühl) sehr wahrscheinlicher das das LEA zwar den Code verkürzt und vereinfacht, aber eben NICHT beschleunigt. Das müsste man aber praktischer Weise noch beweisen (statt sich auf mein Gefühl zu verlassen, bin mir aber ziemlich sicher das es so ist). Der Nachteil vom LEA ist nämlich dessen OpCode Länge, sprich die Anzahl der benötigten Bytes im Codesegment. Der Prozessorteil der diese Instruktionen aus dem Speicher in die CPU lädt und dann diesen OpCode Dekodieren muß benötigt somit mehr Zeit für LEA als für zb. MOV EAX,ECX o.ä.


Gruß Hagen

[Flocke]

@Hagen: Du hast sehr wahrscheinlich Recht. Mit Pipelining habe ich mich noch nicht so intensiv befasst, meine Assembler-Zeit endete so ca. vor 8 Jahren, so dass ich eher für 486 optimiert gedacht habe.

Zu den 16 Taktzyklen: theomega hat doch nur einen 8-Bit Mikroprozessor, und da werden wohl 16 Instruktionen = 16 Taktzyklen sein (8x LSR plus 8x ROL), wenn auch vielleicht nicht im GHz-Bereich!

[alzaimar]

Wieso benutzt ihr nicht einfach eine Lookuptabelle? Das dürfte IMHO das bei weitem schnellste sein (1-2 Takte pro Byte), sämtliche Optimierungsüberlegungen sind damit hinfällig, und zur Not gehts auch in nativem Delphi:

Delphi-Quellcode:

Type TFourBytes = Array [0..3] Of Byte;
Function ReverseBits (aValue : Integer) : Integer;
Begin
  TFourBytes(Result)[3] := rbLookup[TFourBytes(aValue)[0]];
  TFourBytes(Result)[2] := rbLookup[TFourBytes(aValue)[1]];
  TFourBytes(Result)[1] := rbLookup[TFourBytes(aValue)[2]];
  TFourBytes(Result)[0] := rbLookup[TFourBytes(aValue)[3]];
End;

Wobei in rbLookup[b] der die Bit-Inverse der Zahl b (0..255) steht.

[negaH]

Zitat:

theomega hat doch nur einen 8-Bit Mikroprozessor

Hm, sehe ich auch gerade, er hat das viel zu versteckt nebenbei erwähnt.

@theomega: schau mal hier rein http://www.mikrocontroller.net/forum/ , da werden sie geholfen.

Auf einem AVR wird selbstverständlich eine Schleife oder sogar auch unrolled Loop mit den OpCodes RCL, RCR seine 32 Taktzyklen für 16 Bitwerte ergeben. Im obengenannten Forum finden sich aber auch bessere Varianten, die im Grunde auf dem gleichen Trick wie mein Intel Code arbeiten.

Gruß Hagen