Page 1 of 1
Inline asm: 32bit checksum algorithms (CRC,Adler,FNV,ELF)
Posted: Thu Jan 01, 2004 1:01 pm
by Wayne Diamond
Well I've been programming with Purebasic for a couple of days now, just enough time to learn the ropes and get a grasp on the main differences between Purebasic, and Powerbasic which I normally use. So now that I know the basics I can start to contribute source code rather than just questions!
So today, News Years Day 2004, in a somewhat hungover state, I ported over four different 32-bit checksum algorithms that I had originally written in Powerbasic.
None of these are "homegrown" algorithms, you can find them all on the Internet, just not in Purebasic format (until now)
Anyway without further adue, here they are, I hope people can enjoy using them as much as I enjoyed writing them.
Regards, and thanks for making me welcome,
Wayne
CRC32 checksum algorithm
Posted: Thu Jan 01, 2004 1:02 pm
by Wayne Diamond
Code updated For 5.20+
CRC32 - A relatively fast algorithm that creates a 32-bit checksum. CRC32 is the most commonly-used 32-bit checksum algorithm.
Code: Select all
Procedure.l CRC32(Buffer.l, BufLen.l)
Result.l = 0
MOV esi, Buffer ;esi = ptr to buffer
MOV edi, BufLen ;edi = length of buffer
MOV ecx, -1 ;ecx = -1
MOV edx, ecx ;edx = -1
nextbyte: ;next byte from buffer
XOr eax, eax ;eax = 0
XOr ebx, ebx ;ebx = 0
DB 0xAC ;"lodsb" instruction to get next byte
XOr al, cl ;xor al with cl
MOV cl, ch ;cl = ch
MOV ch, dl ;ch = dl
MOV dl, dh ;dl = dh
MOV dh, 8 ;dh = 8
nextbit: ;next bit in the byte
SHR bx, 1 ;shift bits in bx right by 1
RCR ax, 1 ;(rotate through carry) bits in ax by 1
JNC l_crc32_nocarry ;jump to nocarry if carry flag not set
XOr ax, 0x08320 ;xor ax with 33568
XOr bx, 0x0EDB8 ;xor bx with 60856
nocarry: ;if carry flag wasn't set
DEC dh ;dh = dh - 1
JNZ l_crc32_nextbit ;if dh isnt zero, jump to nextbit
XOr ecx, eax ;xor ecx with eax
XOr edx, ebx ;xor edx with ebx
DEC edi ;finished with that byte, decrement counter
JNZ l_crc32_nextbyte ;if edi counter isnt at 0, jump to nextbyte
Not edx ;invert edx bits - 1s complement
Not ecx ;invert ecx bits - 1s complement
MOV eax, edx ;mov edx into eax
ROL eax, 16 ;rotate bits in eax left by 16 places
MOV ax, cx ;mov cx into ax
MOV Result, eax ;crc32 result is in eax
ProcedureReturn Result
EndProcedure
;// MAIN
Checksum.l = 0
Buffer.s = "Wayne Diamond"
Checksum = CRC32(@Buffer, Len(Buffer))
MessageRequester("CRC32", "Should be 6D32B86A: " + Right("00000000" + Hex(Checksum),8), 0)
Adler32 checksum algorithm
Posted: Thu Jan 01, 2004 1:05 pm
by Wayne Diamond
Code updated For 5.20+
Adler32 - an algorithm used by ZIP files that creates a 32-bit checksum. The algorithm is approximately 33% faster than CRC32, and nearly as reliable. Adler32 is a 32-bit extension and improvement of the Fletcher algorithm, used in the ITU-T x.224 / ISO 8073 standard.
Code: Select all
Procedure.l Adler32(Buffer.l, BufLen.l, Seed.l)
Result.l = 0
MOV edx, Seed
MOVZX ecx, dx
SHR edx, 16
MOV esi, Buffer
MOV eax, BufLen
ADD eax, esi
XOr ebx, ebx
LP:
MOV bl, [esi]
ADD ecx, ebx
CMP ecx, 65521
JB l_adler32_m1
SUB ecx, 65521
M1:
ADD edx, ecx
CMP edx, 65521
JB l_adler32_m2
SUB edx, 65521
M2:
INC esi
CMP esi, eax
JNZ l_adler32_lp
SHL edx, 16
ADD ecx, edx
MOV Result, ecx
ProcedureReturn Result
EndProcedure
;// MAIN
Checksum.l = 0
Buffer.s = "Wayne Diamond"
Checksum = Adler32(@Buffer, Len(Buffer), 1)
MessageRequester("Adler32", "Should be 218804E1: " + Right("00000000" + Hex(Checksum),8), 0)
FNV32 checksum algorithm
Posted: Thu Jan 01, 2004 1:07 pm
by Wayne Diamond
Code updated For 5.20+
FNV32 - A very simple algorithm designed for high-speed hashing resulting in highly dispersed hashes with minimal collisions. Named after its creators Glenn Fowler, Phong Vo, and Landon Curt Noll.
Code: Select all
Procedure.l FNV32(Buffer.l, BufLen.l, offset_basis.l)
MOV esi, Buffer ;esi = ptr to buffer
MOV ecx, BufLen ;ecx = length of buffer (counter)
MOV eax, offset_basis ;set to 0 for FNV-0, or 2166136261 for FNV-1
MOV edi, 0x01000193 ;FNV_32_PRIME = 16777619
XOr ebx, ebx ;ebx = 0
nextbyte:
MUL edi ;eax = eax * FNV_32_PRIME
MOV bl, [esi] ;bl = byte from esi
XOr eax, ebx ;al = al xor bl
INC esi ;esi = esi + 1 (buffer pos)
DEC ecx ;ecx = ecx - 1 (counter)
JNZ l_fnv32_nextbyte ;if ecx is 0, jmp to NextByte
ProcedureReturn
EndProcedure
;// MAIN
Checksum.l = 0
Buffer.s = "Wayne Diamond"
Checksum = FNV32(@Buffer, Len(Buffer), 0)
MessageRequester("FNV32", "Should be 8AFD6DE2: " + Right("00000000" + Hex(Checksum),8), 0)
ELF32 checksum algorithm
Posted: Thu Jan 01, 2004 1:08 pm
by Wayne Diamond
Code updated For 5.20+
ELF32 - Outputs a 32-bit unsigned hash that is the modulo generated by dividing the returned integer by the size of the table. Used in UNIX object files that use the ELF format.
Code: Select all
Procedure.l ELF32(Buffer.l, BufLen.l)
H.l = 0
XOr ebx, ebx ; ebx = result holder (H)
MOV edx, BufLen ; edx = Length
MOV ecx, Buffer ; ecx = Ptr to string
XOr esi, esi ; esi = temp holder
Elf1:
XOr eax, eax
SHL ebx, 4
MOV al, [ecx]
ADD ebx, eax
INC ecx
MOV eax, ebx
And eax, 0xF0000000
CMP eax, 0
JE l_elf32_elf2
MOV esi, eax
SHR esi, 24
XOr ebx, esi
Elf2:
Not eax
And ebx,eax
DEC edx
CMP edx, 0
JNE l_elf32_elf1
MOV H, ebx
ProcedureReturn H
EndProcedure
;// MAIN
Checksum.l = 0
Buffer.s = "Wayne Diamond"
Checksum = ELF32(@Buffer, Len(Buffer))
MessageRequester("ELF32", "Should be 07688354: " + Right("00000000" + Hex(Checksum),8), 0)
Posted: Thu Jan 01, 2004 1:21 pm
by newbie
thx you wayne !
i'm someone who already like your work, may be my name is also gkweb
Posted: Thu Jan 01, 2004 2:04 pm
by Fred
Nice pieces of code, thanks for sharing
