flat assembler
Message board for the users of flat assembler.

Index > Examples and Tutorials > Optimized crc32 calculation routine and console program

Author
Thread Post new topic Reply to topic
Sasha



Joined: 17 Nov 2011
Posts: 93
Sasha
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.


Description:
Download
Filename: crc32.zip
Filesize: 5.79 KB
Downloaded: 233 Time(s)

Post 15 Jun 2014, 22:38
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16901
Location: In your JS exploiting you and your system
revolution
You appear to be using a fixed polynomial. Perhaps you can consider having an option for the user to define the polynomial at runtime on the command line.
Post 16 Jun 2014, 09:12
View user's profile Send private message Visit poster's website Reply with quote
Sasha



Joined: 17 Nov 2011
Posts: 93
Sasha
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.
Post 16 Jun 2014, 11:19
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16901
Location: In your JS exploiting you and your system
revolution
Sasha wrote:
I need to understand how to generate a look up table.
You can examine the fasmarm CRC32 table constructor called "CRC32_construct_table" along with the CRC_32 function to use it.
Post 16 Jun 2014, 11:26
View user's profile Send private message Visit poster's website Reply with quote
Sasha



Joined: 17 Nov 2011
Posts: 93
Sasha
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..
Post 16 Jun 2014, 12:27
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16901
Location: In your JS exploiting you and your system
revolution
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..
Performance will vary depending upon the machine used.
Post 16 Jun 2014, 12:33
View user's profile Send private message Visit poster's website Reply with quote
Sasha



Joined: 17 Nov 2011
Posts: 93
Sasha
But there are some tips for optimizing, that are always good to follow.
Post 16 Jun 2014, 13:00
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
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];
Post 16 Jun 2014, 17:04
View user's profile Send private message Reply with quote
dmitriy566



Joined: 19 Jun 2012
Posts: 27
Location: Saint-Petersburg, Russia
dmitriy566
Post 09 Jul 2014, 15:47
View user's profile Send private message Reply with quote
Fixit



Joined: 22 Nov 2012
Posts: 161
Fixit
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    
Edit by revolution: Added code tags
Post 09 Jul 2014, 16:26
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.