Inline asm: 32bit checksum algorithms (CRC,Adler,FNV,ELF)

[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

[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)

[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)

[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)

[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)

[newbie]

thx you wayne !

i'm someone who already like your work, may be my name is also gkweb

[Fred]

Nice pieces of code, thanks for sharing