Schnelles CRC16

[Harper B. (harper)]

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:

//  CRC16/CCITT
//  width: 16
//  polynome: 0x1021 (x16 + x12 + x5 + 1)
//  reflect: yes (bit transmission order: 0,1,2,3,4,5,6,7)
static unsigned short CRCtable[] = {
    0, 4489, ... 
};

#pragma optimize("gt", on)

// \brief calculate the CRC 
// \param pImageStart pointer to first byte
// \param pImageEnd pointer beyond the last last
// \param wOldCRC CRC start value, usually 0xFFFF
// \return new CRC value
WORD CRC16(const BYTE* pImageStart, const BYTE* pImageEnd, WORD wOldCRC)
{
  WORD wCRC;
  WORD w;
  const BYTE* pData;

  wCRC = wOldCRC;
  pData = pImageStart;

  while (pData < pImageEnd)
  {
    w = (wCRC ^ *pData++) & 0xFF;
    wCRC = wCRC >> 8 ^ CRCtable[w];
  }
  return wCRC;
}

Der Compiler erzeugt daraus diesen Code:

CRC16:
    ; load parameters
    mov     ecx, DWORD PTR _pImageStart$[esp-4]
    movzx   eax, WORD PTR _wOldCRC$[esp-4]
    push    esi
    mov      esi, DWORD PTR _pImageEnd$[esp]

    ; initial check (pImageStart < pImageEnd)
    cmp      ecx, esi


    jae      SHORT $LN1@CRC16

    ; ----- calculation loop -----
    movzx   edx, BYTE PTR [ecx]
    xor     dl, al

    movzx   ax, ah
    add      ecx, 1
    and     edx, 255    ; 000000ffH
    movzx   edx, dx
    xor      ax, WORD PTR _CRCtable[edx*2]
    
    cmp      ecx, esi
    movzx   eax, ax
    jb      SHORT $LL2@CRC16
    ; ----- end of calculation loop -----

    pop esi
    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:

    movzx   edx, BYTE PTR [ecx]
    xor     dl, al
    ; ...
    and     edx, 255    ; 000000ffH
    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.

[Jörg W. (dl8dtl) (Moderator)]

Am schnellsten ist halt eine Tabelle, aber die braucht 128 KiB für
die Werte.

[... (Gast)]

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.

[foo (Gast)]

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.

[Peter II (Gast)]

foo schrieb:
> Erspart Vergleiche, kostet Codegröße.

dafür gibt es doch extra:

http://en.wikipedia.org/wiki/Duff's_device

könnte man hier eventuell verwenden.

[Harper B. (harper)]

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?

[Harper B. (harper)]

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.

[Jörg W. (dl8dtl) (Moderator)]

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.