Very nice everyone! When I have some time I'll look into it. For measuring the table generator Maverick's code will be a lot better. As I'm using this proc in my pnglib, and has to be thread-safe, I have to be a bit careful about generating the table. The library doesn't need to be intialized (I prefer to keep it that way) so the table should have been generated the first time it's needed but as multiple threads may use the lib at the same time I would have to use a mutex or something to make sure they do not interfere with each other. However since the time to generate the table is nothing compared to the CRC calculation, I think I'll just generate the table in a local array each time I need to calculate a CRC.. I think it would hardly affect the performance.


iblis wrote:
Why is CRC32 to wonderful anyhow? I've seen other checksum algos that work just fine and are only a few lines of code. CRC seems like overkill to me.

The point is to generate a unique signature from a block of data, right? I can think of about 20 different ways to do that that isn't so cumbersome.

Maybe I have the wrong ideas about CRC. Somebody enlighten me please :D

I can think of 20 as well but I don't think they will all be useful as checksum. CRC has been designed to detect even the smallest changes and I think not every algorithm will do this well.
The adler32 thread in the algorithm section is another example of a checksum. The png specifications say it's as good as CRC (or even better) while it's a lot easier to calculate..

Thomas
Posted on 2002-04-07 05:39:55 by Thomas
BitRAKE, I have understood in what there was a reason of absence of a difference of measurements. It because Athlon XP as has hardware prefetch.
In some cases, using the PREFETCH or PREFECTHW
instruction on processors with hardware prefetch may incur a
reduction in performance.

It was necessary to find a reason ;)
Posted on 2002-04-08 13:48:49 by Nexo
Nexo, interesting - I was not aware of this, thank you.
Posted on 2002-04-08 15:58:20 by bitRAKE
Thomas, could you or someone Pleaseeee post some notes on what CRC is about. I read stuff about it from time to time but to this day i don't really understand what it really do for an app and why... I try to keep up but how can i when things moves so FAST...Is there a post or web site that i can review.

PS: But it's always stronger to me when i here a line or two from one of the members...No rush... just want to know once and for all....Thanks
Posted on 2002-04-08 17:22:30 by cmax
cmax,

CRC is Cyclic Redundancy Check, a fancy word for a checksum algorithm.

Checksums are used to verify data correctness. You take a stream of data, and manipulate it and generate a unique number or string.

So for example, say, during a file transfer, should something go wrong, the checksum ID and the data will not match up, and the program that is receiving the data will know that an error occured, and can request the data again.


To illustrate, here is a very very basic bare bones example of a checksum: Let's say you have a data stream like so:

01 07 4D 9F 32 32 02

and we want to generate a byte-sized checksum. A quick and simple way would be to just add all of the bytes in the data stream together. And you'll get 015A. Snip off the high byte so our checksum fits and you get the checksum 5A.

Now let's say we send our checksum to a client, and tell him to get ready to receive our data... but something goes wrong and the client receives:

01 07 4D 9F 32 00 00

The client takes this data and generates a checksum by adding the bytes together and gets 26. 26 != 5A so the client knows an error occured and sends another request for the data.


That's pretty much it. CRC is just an algorithm that people have come up with that is supposedly the most reliable in detecting data errors.
Posted on 2002-04-08 18:12:27 by iblis
What little i have read about it never explaned what it for, only code for it. I'm slow, i GOT to be told. Now i can go from here.

Thanks iblis
Posted on 2002-04-09 05:35:28 by cmax
I whould recomend everybody to read this link:

http://www.repairfaq.org/filipg/LINK/F_crc_v31.html#CRCV_001

it explains in great details what CRC32 is, why its better than a simple checksum etc.

Dont forget there are methods that evolved from polynomial CRC that can not only detect errore with a probability of 1/2 pow(32) but also correct a lots of errors withour requesting you to retransmit data

This is important for telecomunications but for HDD and CD-ROMs also

Thomas, i am impressed by hose optimizations and maybe we will use them in our CRC32 routines inside HE.

But still, this CRC32 takes us a lot of time in HE game so do you think addler32 is much faster and much important reliable to detect any diferences as CRC32?

Bogdan
:alright:
Posted on 2002-04-27 04:50:36 by BogdanOntanu
There is a faster CRC routine in Unzip 5.50.
Check the CRC_I386.ASM source file !

http://www.info-zip.org/pub/infozip/UnZip.html

JCM
Posted on 2002-05-14 18:25:47 by MCoder
One of the reasons why CRCs are popular is that it's simple to do in hardware. The circuit for generating CRCs can be embedded in silicon. And it's an easy fit for serial interfaces, which transmit data one bit at a time.

Basically, with hardware, you generate the CRC at the same time you're sending the bits out. In other words, zero time.
Posted on 2002-05-15 02:45:01 by tenkey
Thomas

From Your Source,I guess you are tE!

Are You ????

;-)
Posted on 2002-05-15 07:15:19 by purefiring
MCoder: Thanks for the link!

purefiring: No I'm not, although I have used several sources (inculding tE's iirc) to produce the optimized version (see first test results).

Thomas
Posted on 2002-05-15 10:06:18 by Thomas
proc Nexo_ct

Nexo,
you know whose proc it is
here is post from fido talks.asm


? TALKS.ASM (2:5054/29.54) ???????????????????????????????????????? TALKS.ASM ?
Msg : 5305 of 7854
From : Stepan Polovnikov 2:5056/16.47 25 Oct 01 21:00:16
To : All 27 Oct 01 12:48:44
Subj : CRC32
???????????????????????????????????????????????????????????????????????????????
Hello, All!

udataseg
tblCRC32 dd 256 dup (?)

codeseg
proc InitCRC32
lea edi,[tblCRC32]
xor ebx,ebx
mov ebp,0EDB88320h
@@lp: mov eax,ebx
mov ecx,8
@@lpB: xor esi,esi
shr eax,1
cmovc esi,ebp
xor eax,esi
dec ecx
jne @@lpB
stosd
inc bl
jne @@lp
ret
endp

;<esi-buffer
;<ecx-size

;>edx-CRC32

proc CalcCRC32
or edx,-1
lea edi,[tblCRC32]
sub ecx,4
jl @@doB
@@lp: xor edx,[esi]
add esi,4
REPT 4
movzx eax,dl
shr edx,8
xor edx,[edi+4*eax]
ENDM
sub ecx,4
jge @@lp

@@doB: mov eax,[tblmsk+4*(ecx+4)]
and eax,[esi]
xor edx,eax
jmp [tblunr+4*(ecx+4)]
align 4
tblmsk dd 0,0FFh,0FFFFh,0FFFFFFh
tblunr dd @@unr+3*9,@@unr+2*9,@@unr+1*9,@@unr+0*9
@@unr:
REPT 3
movzx eax,dl
shr edx,8
xor edx,[edi+4*eax]
ENDM
not edx
ret
endp

Stepan
--- GoldED+/W32 1.1.5-20010807
* Origin: NETMAIL (2:5056/16.47)
Posted on 2002-08-13 14:10:23 by The Svin
Hi Thomas, I tested your crc32 routines, both are very
fast but second procedure can't calculate checksum for
1 byte long data in the input. Check it out...

Thomas2 proc uses ebx esi edi buf:DWORD, len:DWORD

mov esi, buf
mov edi, offset CRCtable
mov edx, len
shr edx, 1
or ecx, -1
xor eax, eax
@@:
mov al,
xor al, cl
shr ecx, 8
mov ebx,
xor ecx, ebx

mov al,
xor al, cl
shr ecx, 8
mov ebx,
add esi,2
xor ecx, ebx

dec edx ; problem with that
jnz @B ; edx==0FFFFFFFFh

test len, 1
jz @F
mov al,
xor al, cl
inc esi
shr ecx, 8
mov ebx,
xor ecx, ebx
@@:

mov eax, ecx
not eax
ret

Thomas2 endp

Btw: nice work anyway. :alright:
Posted on 2002-08-14 11:47:21 by cybult

Nexo,
you know whose proc it is
here is post from fido talks.asm

I known, because Stepan make this post here :grin: :grin: :grin:
Posted on 2002-08-15 12:28:45 by Nexo
crc32: ;esi-> data
;eax=crc32
;ecx=number of bytes
xor ebx,ebx
xor edx,edx
test cl,1
jz label1
mov dl,
inc esi
xor dl,al
shr eax,8
xor eax,
label1:
shr ecx,1
jz label3
mov dl,
inc esi
label2:
xor dl,al
shr eax,8
xor eax,
mov bl,
mov dl,
add esi,2
xor bl,al
shr eax,8
xor eax,
dec ecx
jnz label2
dec esi
label3:
ret

;note: i haven't test it
Posted on 2002-08-31 13:42:55 by octavio
crc32: ;esi-> data
;eax=crc32
;ecx=number of bytes
xor ebx,ebx
xor edx,edx
test cl,1
jz label1
mov dl,
inc esi
xor dl,al
shr eax,8
xor eax,
label1:
shr ecx,1
jz label3
mov dl,
inc esi
label2:
xor dl,al
shr eax,8
xor eax,
mov bl,
mov dl,
add esi,2
xor bl,al
shr eax,8
xor eax,
dec ecx
jnz label2
dec esi
label3:
ret

;note: i haven't test it
Posted on 2002-08-31 13:49:25 by octavio
If you want to do a really fast crc32 for large files, look into async file I/O.
You can read a new block of data (eg 64 kb) in the background, while you calc the crc32 of the current one.
This means the harddisk becomes the bottleneck, not the CPU.
Someone had made an asm crc32, and when he tried out the async stuff in VB, it was already faster than his asm-routine, so I guess it's nice stuff :)
Posted on 2003-12-15 12:00:23 by Bruce-li