Ich habe eine Routine geschrieben, die ein CRC16 korrekt berechnet.
Diese Routine compiliere ich mit dem Microsoft C++ Compiler von VS2005.
Programmversion cl.exe: 14.00.50727.762
Die Routine arbeitet zwar, könnte aber durchaus schneller sein.
Der Code sieht so aus:
Der spannende Teil dieses Codes ist die caculation loop, da diese für
jedes Byte ausgeführtwird. In dieser Loop sind 10 Assembleranweisungen.
Dabei habe ich einen Verdacht, dass diese nicht optimal sind. Hier sind
die (nach meiner Meinung) kritischen Zeilen:
1
movzx edx, BYTE PTR [ecx]
2
xor dl, al
3
; ...
4
and edx, 255 ; 000000ffH
5
movzx edx, dx
Jede Anweisung ändert das Register DL oder EDX.
In der ersten wird ein Byte in das 32 Bit Register geladen. Das sollte
die oberen Bytes auf 0 setzen.
Das XOR ändert nur das untere Byte, die drei oberen bleiben 0.
Das AND sorgt dafür, dass ... die oberen Bytes auf 0 gesetzt werden.
Das MOVZX erweitert die unteren 16 Bit (DX) auf 32 Bit, wobei die oberen
beiden Bytes auf 0 gesetzt werden.
Kann ich meinem Eindruck trauen, dass die letzten beiden Zeilen
überflüssig sind? Kann der Compiler so schlecht sein?
Gibt es einen andere Algorithmus, gerne auch in 486 Assembler, der
schneller ist? Dabei könnte man berücksichtigen, dass mit der Routine
das CRC16 über einen Bereich von mehreren Megabyte berechnet werden
soll. Ein Epilog für verbleibende x Bytes wäre kein Problem.
Die byte-weise Verarbeitung der Daten macht den Prozessor wahrscheinlich
auch langsam. Ich hab vor paar Jahren mal im optimization guide von
Intel gelesen und da stand drin, dass bei byte-weisen Zugriffen sehr
viele wait states anfallen. Ich weiß allerdings nicht wie das bei
aktuellen Prozessoren ist.
Du kannst z.B. mal Loop Unrolling machen.
Deine Daten sind ja wahrscheinlich länger.
Also z.B: Input 300 bytes,
in der loop immer z.B. 32 bytes verrechen.
Bleibt 300 % 32 -> 12 restbytes zu verrechnen.
Erspart Vergleiche, kostet Codegröße.
Jörg Wunsch schrieb:> Am schnellsten ist halt eine Tabelle, aber die braucht 128 KiB für> die Werte.
In meinem Code ist schon eine CRCtable mit 512 16-Bit Werten enthalten.
Wie in etwas muss ich mir eine 128 kByte große Tabelle vorstellen?
foo schrieb:>> Dabei könnte man berücksichtigen, dass mit der Routine>> das CRC16 über einen Bereich von mehreren Megabyte berechnet>> werden soll.>> Deine Daten sind ja wahrscheinlich länger.
Ja wirklich, dass wäre also durch n-faches Hinschreiben des
Schleifenkörpers zu erledigen, wobei vorher die Anzahl durch n dividiert
werden muss.
> Erspart Vergleiche, kostet Codegröße.
Codegröße ist in der konkreten Anwenung nicht kritische. Das könnte ich
mal probieren.
Harper Blues schrieb:> In meinem Code ist schon eine CRCtable mit 512 16-Bit Werten enthalten.> Wie in etwas muss ich mir eine 128 kByte große Tabelle vorstellen?
Jaja, stimmt schon, ich hatte mich vertan.
