CRC Algorithmus
-
Mit meinen begrenzten Assembler Kenntnissen habe ich den CRC Algorithmus mittels inline Assembler implementiert, was deutlich schneller als die original Version ist (im Durchschnitt um ~ 45%), ich denke aber da könnte man noch was rausholen. Vielleicht hat jemand irgendwelche Verbesserungsvorschläge
unsigned crc32(const void* lpBuffer, std::size_t size) { static const unsigned table[] = { /* ... */ }; unsigned crc = ~0; //while (size--) //crc = table[(crc ^ *p++) & 0xff] ^ crc >> 8; std::size_t s = size; __asm { push esi push edi lea edi, table mov esi, lpBuffer mov ecx, s mov edx, crc start: cmp ecx, 0 //have we reached the end? jz end //if so, go to end dec ecx //decrement the counter mov bl, byte ptr [esi] //copy current data byte to bl inc esi //increase data pointer xor eax, eax //clear eax mov al, dl //copy crc byte to al xor al, bl //xor it with current data byte in bl mov ebx, [edi + eax * 4]//copy table byte to ebx mov eax, edx //copy current crc to eax shr eax, 8 //right shift it by 8 xor eax, ebx //xor the table byte with shifted data mov edx, eax //set the result as the current crc value jmp start end: pop edi pop esi mov [crc], edx } return crc ^ ~0; }
-
Ja - lass es.
Ich hab gerade ausprobiert, ob deine Behauptung mit den 45% stimmt. Und siehe da: es ist, wie ich erwartet habe. Mein Ergebnis auf einem Xeon 2.8 GHz:
crc für 100.000.000 Bytes:
Deine Methode - 519 msec
C Code - 450 msecAls Compiler habe ich natürlich den Intel Compiler verwendet.
-
Wo steht, dass ich den Intel Compiler verwende?
-
Hallo,
also erst mal, wie sieht die CRC Berechnung überhaupt aus? Beschreibe es mal
mit Worten.
Ich vermisse Befehle wie lodsb "lädt ein Byte nach AL indirect über den Zeiger ESI aus einem Buffer" und stosb "schreibt den Inhalt von AL indirect über den Zeiger EDI in einen Buffer", der Befehl stosb ist in diesem Fall aber unwichtig, sowie loop durchläuft einen Schleife so oft
wie der Inhalt von cxmov cx,100 copy: lodsb stosb loop copy Copiert 100 Byte von einem zum anderen Buffernoch besser
mov cx,100 rep movsbMit den Befehlen LODSB sowie STOSB kenne ich mich nur im REAL MODE (DOS) aus,
in dem Fall im Bezug auf die Segmente DS:SI, ES:DI.
Da aber der Prozessor unter Win im PROTECTET Mode läuft müsste es auch über ESI DSI Register funktionieren.
-
Nirgends steht das. Aber das solltest du, wenn du auf Performance Wert legst.
-
Ringding schrieb:
Nirgends steht das. Aber das solltest du, wenn du auf Performance Wert legst.
Wiso, nirgends steht das, wenn man vernüftig Assembler programmieren will
sollte man so rational wie möglich vorgehen.Aber interessant ist
void copy(char* buffer1, char* buffer2, int count) { #asm mov esi,buffer1 mov edi,buffer2 mov cx,count rep movsb #endasm return }das functioniert?
-
Ringding, dann poste doch einfach die Assembler-Ausgabe des Intel-Compilers für deinen C-Code. Dann sieht Shlo doch die Optimierungen.
-
Bitte sehr.
C Code:
void addbfcrc (buf, size) register char *buf; register int size; { int i; for (i = 0; i < size; i ++) { crccode = crctab[(int) ((crccode) ^ (buf[i])) & 0xff] ^ (((crccode) >> 8) & 0x00FFFFFFL); } }Assemblercode:
# -- Machine type PW # mark_description "Intel(R) C++ Compiler for 32-bit applications, Version 8.0 Build 20031016Z %s"; # mark_description "-long_double -xN -O3 -S"; .ident "Intel(R) C++ Compiler for 32-bit applications, Version 8.0 Build 20031016Z %s" .ident "-long_double -xN -O3 -S" addbfcrc: # parameter 1: 16 + %esp # parameter 2: 20 + %esp ..B1.1: # Preds ..B1.0 pushl %ebx #9.1 subl $8, %esp #9.1 movl 20(%esp), %ebx #6.6 xorl %ecx, %ecx #11.9 testl %ebx, %ebx #11.4 jle ..B1.9 # Prob 2% #11.4 # LOE ecx ebx ebp esi edi ..B1.2: # Preds ..B1.1 cmpl $6, %ebx #11.4 jl ..B1.10 # Prob 0% #11.4 # LOE ecx ebx ebp esi edi ..B1.3: # Preds ..B1.2 movl crccode, %edx #12.31 movl %esi, 4(%esp) #11.21 movl %ebp, (%esp) #11.21 lea -6(%ebx), %eax #11.21 movl 16(%esp), %ebp #11.21 # LOE eax edx ecx ebx ebp edi ..B1.4: # Preds ..B1.4 ..B1.3 movzbl (%ecx,%ebp), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 movl %edx, crccode #12.7 movzbl 1(%ecx,%ebp), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 movl %edx, crccode #12.7 movzbl 2(%ecx,%ebp), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 movl %edx, crccode #12.7 movzbl 3(%ecx,%ebp), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 movl %edx, crccode #12.7 movzbl 4(%ecx,%ebp), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 addl $5, %ecx #11.28 movl %edx, crccode #12.7 cmpl %eax, %ecx #11.4 jle ..B1.4 # Prob 91% #11.4 # LOE eax edx ecx ebx ebp edi ..B1.5: # Preds ..B1.4 movl 4(%esp), %esi # movl (%esp), %ebp # # LOE edx ecx ebx ebp esi edi ..B1.6: # Preds ..B1.5 ..B1.10 movl 16(%esp), %eax # movl %esi, 4(%esp) # # LOE eax edx ecx ebx ebp edi ..B1.7: # Preds ..B1.7 ..B1.6 movzbl (%ecx,%eax), %esi #12.44 xorl %edx, %esi #12.44 andl $255, %esi #12.55 shrl $8, %edx #13.25 addl $1, %ecx #11.28 andl $16777215, %edx #13.30 xorl crctab(,%esi,4), %edx #13.30 cmpl %ebx, %ecx #11.4 movl %edx, crccode #12.7 jl ..B1.7 # Prob 80% #11.4 # LOE eax edx ecx ebx ebp edi ..B1.8: # Preds ..B1.7 movl 4(%esp), %esi # # LOE ebp esi edi ..B1.9: # Preds ..B1.8 ..B1.1 addl $8, %esp #15.1 popl %ebx #15.1 ret #15.1 # LOE ..B1.10: # Preds ..B1.2 # Infreq movl crccode, %edx #12.31 jmp ..B1.6 # Prob 100% #12.31 .align 4,0x90 # LOE edx ecx ebx ebp esi edi
-
Sonst alles gesund?
-
Ah, der Compiler hat das überflüssige & nicht erkannt. Machen wir also 440msec daraus.
-
also je nach dem was gefordert wird kann auch ein anderer algo eingesetzt werden:
für wenige bytes:CRC32 proc uses ebx esi edi lpbuffer:DWORD, lsize:DWORD mov esi, lpbuffer mov ebx, lsize xor ecx, ecx lea eax, [ecx-1] mov edi, 0EDB88320h @@m1: xor edx, edx mov dl, [esi] xor dl, al @@m2: shr edx, 1 jnc @@m3 xor edx, edi @@m3: inc ecx and cl, 7 jnz @@m2 shr eax, 8 xor eax, edx inc esi dec ebx jg @@m1 not eax RET CRC32 endpfür längere abschnitte eher:
http://board.win32asmcommunity.net/showthread.php?s=&threadid=17782&highlight=CRC32
http://board.win32asmcommunity.net/search.php?s=&action=showresults&searchid=281191&sortby=lastpost&sortorder=descending
bzw der "speed" contest (mehrere algos werden verglichen und erreichen schon auf "lahmen" Maschinen einen höheren Speed als den hier schon mal angegebenen :D:
http://board.win32asmcommunity.net/showthread.php?s=&threadid=4628&perpage=15&highlight=crc32&pagenumber=1mit der richtigen optimierung geht alles, man kann ja auch p4 Chache befehle einbauen und buffer benutzen, wichtig ist ja auch der filezugriff - ob es schneller mit oder ohne Cache gehet usw. also nicht nur der Crc algo sondern auch andere Routinen sind mit einzubeziehen - schließlich kann ein algo nur so schnell arbeiten wie er daten als input bekommt
-
wie wärs denn damit:
__declspec( naked ) unsigned __fastcall crc32_2(const void* lpBuffer, std::size_t size) { static const unsigned table[ 256 ] = { /* ... */ }; _asm { neg edx jz get_out push ebx xor ebx, ebx mov eax, -1 sub ecx, edx _loop: mov bl, al shr eax, 8 xor bl, [ ecx + edx ] xor eax, [ table + ebx * 4 ] inc edx jnz _loop pop ebx not eax get_out:ret } }gegebenenfalls kann man shr eax,8 und xor bl, ... vertauschen, allerdings ist shr auf einem p4 SEHR langsam - in jedem falle wird das ganze im wesentlichen durch den speicherzugriff beschränkt, partielles unrolling und zusammenfassen ( man kann ja [ ecx + edx ] bis [ ecx + edx + 3 ] mit einem mal lesen und dann die subregister benutzen ) bringt zumindest hier auf meinem p4 keinen messbaren geschwindigkeitsunterschied, vermutlich bedingt durch die übergänge 32bit <-> 8bit, was zeitstrafen mit sich bringt
btw, md4 ist nur unwesentlich langsamer (ca. 10%), aber wesentlich sicherer was kollisionen angeht