Assembler: Reihenfolge eines Bitfelds umdrehen

[Phistev]

BSWAP steht theomega doch nicht zur Verfügung 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