Wenn man eine Binärzahl einlesen will, die in einem String vorliegt, so gibt es grundsätzlich zwei Möglichkeiten:
1. Man schaut sich von hinten nach Vorne alle Stellen an und addiert diese dann, wenn eine 1 an der entsprechenden Stelle steht
ODER
2. Man Schaut von vorne nach hinten durch und Verdoppelt vor dem Addieren der Stelle einfach das bisherige Ergebnis.
Da die zweite Variante einfacher ist, möchte ich diese hier einfach einmal präsentieren.
Aus der Beschreibung könnte man zunächst auf folgenden Ansatz in Delphi kommen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| function BinaryToDWORD(s : String) : DWORD;
var
i : Integer;
begin
Result := 0;
for i := 1 to Length(s) do
Result := Result*2 + StrToInt(s[i]);
end; |
Schauen wir uns diesen Source einmal an:
Die Zeilen 1 bis 4 sind Vorgeplänkel und nebenschächlich. Hier wird die Funktion zur Umwandlung deklariert und eine benötigte lokale Variable angelegt. Bei Unverständnis dieser Zeilen empfehle ich
Christian's Crashkurs.
Nun weiter. In Zeile 5 initialisieren wir nun unser Ergebnis. 0 Ist hierfür wie geeignet, da es neutral gegenüber der Multiplikation ist.
Im Anschluss folgt der eigentliche Teil der Arbeit. Zeile 6 sagt ersteinmal nur, dass die folgende Aufgabe in Zeile 7 für jedes Zeichen im Eingabestring S von vorn bis hinten (also von links nach rechts) ausgeführt werden soll. Aber was macht
Nun Zeile 7 genau? Hierfür ist ein Blick in die Binär-Darstellung unseres Ergebnisses in Result interessant.
Angenommen, dort steht bereits der Wert 6 drin (d.h. die bisherige Eingabe war '110') und die nächste gelesene Ziffer im Eingabe-String ist eine '1', so wird der Ausdruck:
Delphi-Quelltext
berechnet. In jedem Stellenwert-System ist aber gerade die Multiplikation mit der Basis eine Verschiebung aller Stellen um eine Position nach links. Wenn also 6*2 gerechnet wird, so stimmen alle Positionen im Ergebnis wieder überein, bis auf eine zusätzliche 0, die angefügt wird. Die Anschließende Addition der neuen Stelle ersetzt nun diese letzte Ziffer mit dem Wert aus dem String.
Soweit, nicht gut
Diese Routine hat zwei wesentliche Nachteile:
1. Sie ist langsam
2. Sie fängt keine Fehler ab
1. Ist zuerst einmal nicht offensichtlich, daher komme ich darauf noch einmal zurück. Aber warum 2.???
Nehmen wir einfach einmal die Beispieleingabe 100120 an. Diese ist KEIN Binärstring, wird aber von unserer Routine Problemlos bearbeitet. Als Ergebnis erhalten wir nämlich:
Delphi-Quelltext
1:
| Result := (((((0 shl 1 + 1) shl 1 + 0) shl 1 + 0) shl 1 + 1) shl 1 + 2) shl 1 + 0 := 40; |
Korrekt wäre aber ein Fehler, da 2 keine gültige Binär-Ziffer ist.
Also versuchen wir es doch einmal anders (ich hoffe, ich schreck jetzt keinen mit ASM zu sehr ab ... sieht komplizierter aus, als es ist):
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
| function BinaryToDWORD(const s: String): DWORD;
procedure InvalidBin;
const
FmtInvalidBinary: String = 'Ungültiges Zeichen in Binärdatenstrom.';
begin
Raise EConvertError.Create(FmtInvalidBinary);
end;
asm
PUSH ESI
XOR EDX, EDX
TEST EAX, EAX
JZ @@Bin2DWORD_Finish
MOV ESI, EAX
MOV ECX, DWORD PTR [ESI-4]
TEST ECX, ECX
JMP @@Bin2DWORD_LoopStart
@@Bin2DWORD_Loop:
MOV AL, BYTE PTR [ESI]
MOV AH, AL
AND AH, $FE
CMP AH, $30
JNZ InvalidBin
XOR AL, AH
MOVZX EAX, AL
ADD EDX, EDX
ADD EDX, EAX
INC ESI
DEC ECX
@@Bin2DWORD_LoopStart:
JNZ @@Bin2DWORD_Loop
MOV EAX, EDX
@@Bin2DWORD_Finish:
POP ESI
end; |
Sieht kompliziert aus? Macht aber im Grunde genau das gleiche wie oben. Wo liegt nun der Unterschied?
Dieser Source behebt genau die beiden oben aufgeführten Probleme des ersten Quelltextes. Um dies aber genau zu zeigen, sollte ich glaube ein wenig die Analogien aufzeigen:
Die Zeilen 14 bis 21 entsprechen grob gesagt den Zeilen 5 und 6 aus dem obigen Quelltext, mit dem Unterschied, dass sie direkt auf den Speicher zugreifen und damit keine Aufrufe an die Laufzeit-Bibliothek von Delphi notwendig sind.
Die Zeilen 21-23, 39, 40 und 42 sind nun die eigentliche For-Schleife (d.h. Zeile 6 in Bezug auf die Zählung und Verwaltung des aktuellen String-Zeichens, welches in Zeile 26 gelesen wird.
Die Berechnung ist auch hier wieder:
Delphi-Quelltext
1:
| Result := Result * 2 + NeueZiffer; |
Result steht hierbei immer im Register EDX, während die neue Ziffer im Register EAX (innerhalb der Schleife nur) verwaltet wird.
Nun folgen aber auch schon die Unterschiede:
Anstatt wie im ersten Quelltext die einzelnen Ziffern über StrToInt auswerten zu lassen, kümmmern wir uns in diesem Fall selber drum. Dies hat den Vorteil, dass wir ganz gezielt unsere Kriterien an die gelesenen Zeichen selber prüfen können und nicht auf eine sehr allgemeine Funktion mit Haufenweise Zusatzmöglichkeiten zurückgreifen müssen.
Nun aber zum Herzstück der Konvertierung:
Delphi-Quelltext
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
| { ... }
asm
@@Bin2DWORD_Loop:
MOV AL, BYTE PTR [ESI]
MOV AH, AL
AND AH, $FE
CMP AH, $30
JNZ InvalidBin
XOR AL, AH
MOVZX EAX, AL
ADD EDX, EDX
ADD EDX, EAX
end; |
Wie erwähnt wird in Zeile 26 das Zeichen aus dem String gelesen. Dieses Zeichen wird anschließend (Zeile 2
kopiert. In Zeile 29 wird nun eine Bitmaske verwendet, um herauszubekommen, ob es sich um die Zeichen '0' und '1' oder um ein ungültiges Zeichen handelt. Dazu muss man wissen, dass die Zahlen im ASCII-Zeichensatz an den Stellen 48 bis 57 sind: 0 -> 48, 1 -> 49, ... Wenn man also in der Bitmaske bis auf das letzte Bit alle vergleicht, so muss sowohl für 48 als auch 49 jeweils der Wert 48 auftreten; tut er dies nicht, war das Eingabe-Zeichen ungültig und wir lösen in Zeile 31 einen Fehler aus.
Jetzt müssen wir nur noch aus dem ASCII-Wert eine Binär.-Ziffer machen. Aber nichts leichter als das. Rechnen wir doch mal:
48 and $FE = 48,
49 and $FE = 48 Wahnsinn. Nutzen wir das doch gleich. Da wir in AL unsere Originale Ziffer stehen haben, brauchen wir von dieser einfach nur 48 abzuziehen: Also genau das, was eh im Register AH steht. Alternativ zum Subtrahieren kann man aber auch XOR verwenden, da wir in jedem Fall bis auf das Niederwertigste Bit immer das gleiche Bitmuster in AH und AL stehen haben: Ein XOR blendet also alle Bits außer dem letzten immer auf 0. Zeile 34 sorgt nun dafür, dass wir aus unserem 8-Bit-Operanden eine 32-Bit-Zahl erhalten. Dies ist wichtig, damit wir in Zeile 38 zwei gleichgroße Operanden verarbeiten könneen.
Die Zeilen 37 und 38 Sind nun nur noch die Kurzfassung der oben bereits erwähnten Formel: Bisheriges Ergebnis verdoppeln und neue Ziffer hinten anfügen.
Und sieh da: Ist zwar mehr zu schreiben, funktioniert aber etwa 100 mal schneller als die erste Möglichkeit. Außerdem haben wir dank Assembler sogar noch einen Vorteil: Sollten einmal Overflow-Checks aktiv sein, so ignoriert unsere ASM-Procedure diese einfach; der Source im ersten Beispiel würde bei diesem Versuch eine Exception liefern. Möchte man dieser Verhalten auch in der ASM-Routine, so muss man lediglich zwischen Zeile 36 und 37 eine Zusätzliche Zeile mit einem Befehl
JC OverflowError sowie eine entsprechende Routine OverflowError nach dem Vorbild von InvalidBin ergänzen. Diese Aufgabe überlasse ich aber als Übung ^^
Ich hoffe einmal einen kleinen Einblick gegeben zu haben, warum intuitive Quelltexte in Delphi realisiert oftmals um einiges langsamer sind, als entsprechende Derivate in ASM. Sicherlich ließe sich obiges Beispiel auch noch dahingehend optimieren, dass es die erwähnten Abfragen auch besitzt, aber seine Eleganz würde doch stark darunter leiden
ASM wird umso eleganter, je kryptischer er aussieht und trotzdem noch funktioniert ...
Viel Spaß beim Rumtesten
Moderiert von 
Narses: Beitrag geprüft und einsortiert am 21.04.2008Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
![Antworten [gesperrt]](./graphics/navbar/reply.png)
