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:
1 | // CRC16/CCITT
|
2 | // width: 16
|
3 | // polynome: 0x1021 (x16 + x12 + x5 + 1)
|
4 | // reflect: yes (bit transmission order: 0,1,2,3,4,5,6,7)
|
5 | static unsigned short CRCtable[] = {
|
6 | 0, 4489, ...
|
7 | };
|
8 |
|
9 | #pragma optimize("gt", on)
|
10 |
|
11 | // \brief calculate the CRC
|
12 | // \param pImageStart pointer to first byte
|
13 | // \param pImageEnd pointer beyond the last last
|
14 | // \param wOldCRC CRC start value, usually 0xFFFF
|
15 | // \return new CRC value
|
16 | WORD CRC16(const BYTE* pImageStart, const BYTE* pImageEnd, WORD wOldCRC)
|
17 | {
|
18 | WORD wCRC;
|
19 | WORD w;
|
20 | const BYTE* pData;
|
21 |
|
22 | wCRC = wOldCRC;
|
23 | pData = pImageStart;
|
24 |
|
25 | while (pData < pImageEnd)
|
26 | {
|
27 | w = (wCRC ^ *pData++) & 0xFF;
|
28 | wCRC = wCRC >> 8 ^ CRCtable[w];
|
29 | }
|
30 | return wCRC;
|
31 | }
|
Der Compiler erzeugt daraus diesen Code:
1 | CRC16:
|
2 | ; load parameters
|
3 | mov ecx, DWORD PTR _pImageStart$[esp-4]
|
4 | movzx eax, WORD PTR _wOldCRC$[esp-4]
|
5 | push esi
|
6 | mov esi, DWORD PTR _pImageEnd$[esp]
|
7 |
|
8 | ; initial check (pImageStart < pImageEnd)
|
9 | cmp ecx, esi
|
10 |
|
11 |
|
12 | jae SHORT $LN1@CRC16
|
13 |
|
14 | ; ----- calculation loop -----
|
15 | movzx edx, BYTE PTR [ecx]
|
16 | xor dl, al
|
17 |
|
18 | movzx ax, ah
|
19 | add ecx, 1
|
20 | and edx, 255 ; 000000ffH
|
21 | movzx edx, dx
|
22 | xor ax, WORD PTR _CRCtable[edx*2]
|
23 |
|
24 | cmp ecx, esi
|
25 | movzx eax, ax
|
26 | jb SHORT $LL2@CRC16
|
27 | ; ----- end of calculation loop -----
|
28 |
|
29 | pop esi
|
30 | ret
|
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.
