Index
> Tutorials and Examples > Optimized crc32 calculation routine and console program |
| Author |
|
|
Sasha 15 Jun 2014, 22:38
Once I wanted to discover what is crc. I've seen the crc32 instruction in manual, but didn't know, that my cpu doesn't support it. When I realized it, I wrote the routine, that calculates it. But the routine itself is not so useful, so I've wrote a console program, that calculates crc32 of the string that you input or of a file that you redirect and also shows some manipulations with console functions. The crc32 routine was optimized and benchmarked to show the best resultes. But the file access is not optimised.
Type crc32 and then input your string, to calculate its crc32 value. Or type crc32 < filename to calculate the crc32 of a file. The output can also be redirected. Type crc32 < inputfilename > outputfilename If you see an error, please let me know.
|
|||||||||||
15 Jun 2014, 22:38 |
|
|
Sasha 16 Jun 2014, 11:19
Yes, it is fixed, commonly used crc32 polynomial. Many options can be added, but this utility has no options at all, even filedata it takes through standard input. Also, to do this, I need to understand how to generate a look up table.
|
|||
|
16 Jun 2014, 11:19 |
|
|
revolution 16 Jun 2014, 11:26
Sasha wrote: I need to understand how to generate a look up table. |
|||
|
16 Jun 2014, 11:26 |
|
|
Sasha 16 Jun 2014, 12:27
I've looked at it. The .align section is the by-byte routine similar to mine. But I found mine a little faster even though you need to use one more register. I also tried to work with a bigger blocks, but then your code grows, and it makes a negative effect..
|
|||
|
16 Jun 2014, 12:27 |
|
|
revolution 16 Jun 2014, 12:33
Sasha wrote: I've looked at it. The .align section is the by-byte routine similar to mine. But I found mine a little faster even though you need to use one more register. I also tried to work with a bigger blocks, but then your code grows, and it makes a negative effect.. |
|||
|
16 Jun 2014, 12:33 |
|
|
Sasha 16 Jun 2014, 13:00
But there are some tips for optimizing, that are always good to follow.
|
|||
|
16 Jun 2014, 13:00 |
|
|
baldr 16 Jun 2014, 17:04
Sasha,
That table contains remainders for bytes 0…255 (plain CRC32 without pre-/post-conditioning). Actually your table is for LSb-first variation (MSb corresponds to the term with the least x power), thus polynomial really is 0xEDB88320 (0x04C11DB7 bit-reversed, so implicit 1-bit for the x³² term is to the right of b₀). Those tables are easily identified by either crc32_table[1] or crc32_table[128], one of which should be equal to the generating poly. Another way to generate that table is to use simple identities: t[1<<n]==t[1<<(n+1)]>>1 and t[x ^ y] == t[x] ^ t[y] (first one is LSb-first-specific; it doesn't hold for t[4] => t[2] transition, you'll need to add poly again: t[2] == t[4]>>1 ^ 0xEDB88320, because of x²⁶ term). Start with trivial t[0] = 0; t[0x80] = 0xEDB88320; Fill t[0x40], t[0x20],… t[1] using first identity. Fill the gaps using second identity: t[3] = t[2]^t[1]; t[5] = t[4]^t[1]; t[6] = t[4]^t[2]; t[7] = t[4]^t[3]; t[9] = t[8]^t[1]; t[10] = t[8]^t[2]; t[11] = t[8]^t[3]; t[12] = t[8]^t[4];… |
|||
|
16 Jun 2014, 17:04 |
|
|
dmitriy566 09 Jul 2014, 15:47
|
|||
|
09 Jul 2014, 15:47 |
|
|
Fixit 09 Jul 2014, 16:26
Code: ; crc.asm - Performs a CRC on files specified in the command line. ; Com file By James Vahn, based on Edwin T. Floyd 's CRC-32 routine. May 15, 1994 Copyright 1994 by James Vahn, All Rights Reserved I make this code available for educational purposes and if substantial code from this is used in your software, I'd appreciate credit given to me and Mr. Floyd in your documention. /* cseg segment assume cs:cseg,ds:cseg org 100h ;COM format Begin proc far cld ;Get the filename and wildcards mov si,82h ;from the command tail. lo1: lodsb ;Find filename in PSP cmp al,0Dh jne lo1 mov byte ptr [si-1],0h ;Filename delimiter. findfirst: mov cx,16h ;incl. directories mov dx,82h ;command tail location mov ah,4Eh int 21h jnc findnext jmp error findnext: mov si,9Eh cmp byte ptr[si],'.' ;Don't print '.. <dir>' jne pname mov bx,95h test byte ptr[bx],00010000b jz pname jmp close pname: ;Print the filename onscreen. lodsb or al,al ;Is it a zero? ASCIIZ je open mov dl,al mov ah,2h int 21h jmp pname open: mov bx,95h mov al,byte ptr[bx] test al,00010000b ;Is it a directory? jz dofile ;nope! mov dx,offset dirmsg ;Print <dir> and skip CRC mov ah,09h int 21h jmp close dofile: mov dl,09h ;Tab separator. 20h for space. mov ah,2h int 21h mov ax,03D00h ;Open for read. mov dx,9Eh ;Filename in default DTA (PSP) int 21h jc error2 mov word ptr [hndl],ax read: mov ah,03Fh mov bx,word ptr [hndl] mov dx,offset buf mov cx,0FEFFh ;Leave room in buffer for stack. sub cx,dx ;Maximum buffer size. int 21h jc error3 or ax,ax ;End of file? je exit call UpdateCRC32 ;calculate CRC. jmp read exit: xor word ptr [initcrc],0FFFFh ;Finish CRC calculation. xor word ptr [initcrc+2],0FFFFh mov ax,word ptr [initcrc+2] call bin2hex ;Print CRC to screen. mov ax,word ptr [initcrc] call bin2hex mov ax,0FFFFh mov word ptr[initcrc],ax mov word ptr[initcrc+2],ax mov dx,offset CRLF ;linefeed mov ah,09h int 21h close: mov bx,word ptr [hndl] mov ah,3Eh ;close file. int 21h mov ah,4Fh ;Do more files. int 21h jc toDOS jmp findnext toDOS: mov ax,04C00h ;Normal exit to DOS. int 21h Begin endp ;***************************************************** error proc near mov ah,09h mov dx,offset errmsg int 21h mov ax,04C01h ;Exit errorlevel 1. int 21h error endp ;***************************************************** error2 proc near mov ah,09h mov dx,offset errmsg2 int 21h mov ax,04C02h ;Exit errorlevel 2. int 21h error2 endp ;***************************************************** error3 proc near mov ah,09h mov dx,offset errmsg3 int 21h mov ax,04C03h ;Exit errorlevel 3. int 21h error3 endp ;***************************************************** bin2hex proc near ;Convert AX to HEX ASCII output bin2he: mov cx,4 ;4 hex digits mov bx,10h ;divisor bin2h1: xor dx,dx ;zero DX for 16 bit divide div bx ;leaves quotient in AX add dl,'0' ;convert remainder to ASCII cmp dl,'9' jna bin2h2 add dl,'A'-'9'-1 bin2h2: push dx ;put on stack loop bin2h1 ;repeat mov cx,4 bin2h3: pop ax ;pop most significant digit first mov dl,al mov ah,02h int 21h loop bin2h3 ret bin2hex endp ;***************************************************** UpdateCRC32 proc near ; UpdateCRC32 takes an initial CRC value and updates it from ; data in 'buf'. The updated CRC is then stored in InitCRC. mov si,offset buf mov cx,ax jcxz bye les ax,[initcrc] mov dx,ES lo2: xor bh,bh mov bl,al lodsb xor bl,al mov al,ah mov ah,dl mov dl,dh xor dh,dh shl bx,1 shl bx,1 les bx,[crc32tab+bx] xor ax,bx mov bx,ES xor dx,bx loop lo2 mov word ptr [initcrc],ax ; Store result in InitCRC mov word ptr [initcrc+2],dx bye: ret UpdateCRC32 endp ;***************************************************** ; 32 bit reverse crc table for polynomial EDB88320h (Zmodem,PKZip) ; X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 crc32tab dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah, 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h, 00edb8832h, 079dcb8a4h dd 0e0d5e91eh, 097d2d988h, 009b64c2bh, 07eb17cbdh, 0e7b82d07h dd 090bf1d91h, 01db71064h, 06ab020f2h, 0f3b97148h, 084be41deh dd 01adad47dh, 06ddde4ebh, 0f4d4b551h, 083d385c7h, 0136c9856h dd 0646ba8c0h, 0fd62f97ah, 08a65c9ech, 014015c4fh, 063066cd9h dd 0fa0f3d63h, 08d080df5h, 03b6e20c8h, 04c69105eh, 0d56041e4h dd 0a2677172h, 03c03e4d1h, 04b04d447h, 0d20d85fdh, 0a50ab56bh dd 035b5a8fah, 042b2986ch, 0dbbbc9d6h, 0acbcf940h, 032d86ce3h dd 045df5c75h, 0dcd60dcfh, 0abd13d59h, 026d930ach, 051de003ah dd 0c8d75180h, 0bfd06116h, 021b4f4b5h, 056b3c423h, 0cfba9599h dd 0b8bda50fh, 02802b89eh, 05f058808h, 0c60cd9b2h, 0b10be924h dd 02f6f7c87h, 058684c11h, 0c1611dabh, 0b6662d3dh, 076dc4190h dd 001db7106h, 098d220bch, 0efd5102ah, 071b18589h, 006b6b51fh dd 09fbfe4a5h, 0e8b8d433h, 07807c9a2h, 00f00f934h, 09609a88eh dd 0e10e9818h, 07f6a0dbbh, 0086d3d2dh, 091646c97h, 0e6635c01h dd 06b6b51f4h, 01c6c6162h, 0856530d8h, 0f262004eh, 06c0695edh dd 01b01a57bh, 08208f4c1h, 0f50fc457h, 065b0d9c6h, 012b7e950h dd 08bbeb8eah, 0fcb9887ch, 062dd1ddfh, 015da2d49h, 08cd37cf3h dd 0fbd44c65h, 04db26158h, 03ab551ceh, 0a3bc0074h, 0d4bb30e2h dd 04adfa541h, 03dd895d7h, 0a4d1c46dh, 0d3d6f4fbh, 04369e96ah dd 0346ed9fch, 0ad678846h, 0da60b8d0h, 044042d73h, 033031de5h dd 0aa0a4c5fh, 0dd0d7cc9h, 05005713ch, 0270241aah, 0be0b1010h dd 0c90c2086h, 05768b525h, 0206f85b3h, 0b966d409h, 0ce61e49fh dd 05edef90eh, 029d9c998h, 0b0d09822h, 0c7d7a8b4h, 059b33d17h dd 02eb40d81h, 0b7bd5c3bh, 0c0ba6cadh, 0edb88320h, 09abfb3b6h dd 003b6e20ch, 074b1d29ah, 0ead54739h, 09dd277afh, 004db2615h dd 073dc1683h, 0e3630b12h, 094643b84h, 00d6d6a3eh, 07a6a5aa8h dd 0e40ecf0bh, 09309ff9dh, 00a00ae27h, 07d079eb1h, 0f00f9344h dd 08708a3d2h, 01e01f268h, 06906c2feh, 0f762575dh, 0806567cbh dd 0196c3671h, 06e6b06e7h, 0fed41b76h, 089d32be0h, 010da7a5ah dd 067dd4acch, 0f9b9df6fh, 08ebeeff9h, 017b7be43h, 060b08ed5h dd 0d6d6a3e8h, 0a1d1937eh, 038d8c2c4h, 04fdff252h, 0d1bb67f1h dd 0a6bc5767h, 03fb506ddh, 048b2364bh, 0d80d2bdah, 0af0a1b4ch dd 036034af6h, 041047a60h, 0df60efc3h, 0a867df55h, 0316e8eefh dd 04669be79h, 0cb61b38ch, 0bc66831ah, 0256fd2a0h, 05268e236h dd 0cc0c7795h, 0bb0b4703h, 0220216b9h, 05505262fh, 0c5ba3bbeh dd 0b2bd0b28h, 02bb45a92h, 05cb36a04h, 0c2d7ffa7h, 0b5d0cf31h dd 02cd99e8bh, 05bdeae1dh, 09b64c2b0h, 0ec63f226h, 0756aa39ch dd 0026d930ah, 09c0906a9h, 0eb0e363fh, 072076785h, 005005713h dd 095bf4a82h, 0e2b87a14h, 07bb12baeh, 00cb61b38h, 092d28e9bh dd 0e5d5be0dh, 07cdcefb7h, 00bdbdf21h, 086d3d2d4h, 0f1d4e242h dd 068ddb3f8h, 01fda836eh, 081be16cdh, 0f6b9265bh, 06fb077e1h dd 018b74777h, 088085ae6h, 0ff0f6a70h, 066063bcah, 011010b5ch dd 08f659effh, 0f862ae69h, 0616bffd3h, 0166ccf45h, 0a00ae278h dd 0d70dd2eeh, 04e048354h, 03903b3c2h, 0a7672661h, 0d06016f7h dd 04969474dh, 03e6e77dbh, 0aed16a4ah, 0d9d65adch, 040df0b66h dd 037d83bf0h, 0a9bcae53h, 0debb9ec5h, 047b2cf7fh, 030b5ffe9h dd 0bdbdf21ch, 0cabac28ah, 053b39330h, 024b4a3a6h, 0bad03605h dd 0cdd70693h, 054de5729h, 023d967bfh, 0b3667a2eh, 0c4614ab8h dd 05d681b02h, 02a6f2b94h, 0b40bbe37h, 0c30c8ea1h, 05a05df1bh dd 02d02ef8dh initcrc dd 0FFFFFFFFh ;Initial CRC value errmsg db 'File not found- Useage: CRC FILENAME.*',0Dh,0Ah,24h errmsg2 db 'error 2, cannot open file.',0Dh,0Ah,24h errmsg3 db 'error 3, cannot read file.',0Dh,0Ah,24h crlf db 0Dh,0Ah,24h dirmsg db 9,'<dir>',0Dh,0Ah,24h hndl dw 0 ;File handle storage. buf db 0 ;Dynamic storage. Do not move! cseg ends end Begin |
|||
|
09 Jul 2014, 16:26 |
|
< Last Thread | Next Thread > |
Forum Rules:
|