Adler32 Checksum

[Guimauve]

Hello everyone,

A very simple Adler32 checksum algorithm Source : http://en.wikipedia.org/wiki/Adler-32

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Adler 32 Checksum
; File Name : Adler32.pb
; File version: 1.0.1
; Programming : OK
; Programmed by : Guimauve
; Date : 20-02-2012
; Last Update : 20-02-2012
; PureBasic code : 4.60
; Platform : Windows, Linux, MacOS X
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Notes about Adler32
;
; Source : http://en.wikipedia.org/wiki/Adler-32
;
; In Ascii mode :
;
;     Adler32("Wikipedia") = 300286872
;     Adler32("Wikipedia") = 11E60398 (Hexa)
;
; In Unicode mode :
;
;     Adler32("Wikipedia") = 600572824
;     Adler32("Wikipedia") = 23CC0398 (Hexa)
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure Adler32(*Buffer.Ascii, BufferSize.l)
  
  Adler32_Var_A.i = 1
  Adler32_Var_B.i = 0
  
  For Index = 1 To BufferSize
    
    Adler32_Var_A = (Adler32_Var_A + *Buffer\a) % 65521
    Adler32_Var_B = (Adler32_Var_B + Adler32_Var_A) % 65521
    *Buffer + 1
    
	Next
  
  ProcedureReturn (Adler32_Var_B << 16) | Adler32_Var_A
EndProcedure

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 
; <<<<< !!! WARNING - YOU ARE NOW IN A TESTING ZONE - WARNING !!! <<<<< 
; <<<<< !!! WARNING - THIS CODE SHOULD BE COMMENTED - WARNING !!! <<<<< 
; <<<<< !!! WARNING - BEFORE THE FINAL COMPILATION. - WARNING !!! <<<<< 
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 

String.s = "Wikipedia"
length = StringByteLength(String)

Checksum = Adler32(@String, length)

Debug "Adler32(" + Chr(34) + String + Chr(34) + ") = " + Str(Checksum)
Debug "Adler32(" + Chr(34) + String + Chr(34) + ") = " + Hex(Checksum)

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<

Best regards.
Guimauve

[wilbert]

That's a small algorithm

You might want to use .i instead of .q for your Adler32 vars.
You don't need 64 bits for this routine and handling quads on x86 is slower.

[Guimauve]

That's a small algorithm

You might want to use .i instead of .q for your Adler32 vars.
You don't need 64 bits for this routine and handling quads on x86 is slower.

Done

Best regards
Guimauve

[rudz]

Have not tested it for speed

Replacing

Code: Select all

Adler32_Var_A = (Adler32_Var_A + *Buffer\a) % 65521
Adler32_Var_B = (Adler32_Var_B + Adler32_Var_A) % 65521

With this

Code: Select all

Adler32_Var_A + *Buffer\a % 65521
Adler32_Var_B + Adler32_Var_A % 65521

Gives same results for me

[wilbert]

If you really need it to be fast, ASM is the way to go.
If you want to improve the speed without using ASM, it is faster to use the modulo division less often like this

Code: Select all

Procedure Adler32(*Buffer.Ascii, BufferSize.l)

  Adler32_Var_A.l = 1
  Adler32_Var_B.l = 0
  
  *BufferEnd = *Buffer + BufferSize
  While *Buffer < *BufferEnd
    Adler32_Var_A + *Buffer\a
    Adler32_Var_B + Adler32_Var_A
    *Buffer + 1
    If *Buffer & 2047 = 0
      Adler32_Var_A % 65521
      Adler32_Var_B % 65521
    EndIf
  Wend
  Adler32_Var_A % 65521
  Adler32_Var_B % 65521
  
  ProcedureReturn (Adler32_Var_B << 16) | Adler32_Var_A
EndProcedure

[pcfreak]

There was once an assembler code for this on the forum...

Code: Select all

; English forum: http://purebasic.myforums.net/viewtopic.php?t=8957&highlight=
; Author: Wayne Diamond
; Date: 01. January 2004


; 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.

Procedure.l Adler32(Buffer.l, BufLen.l, Seed.l)
  Result.l = 0
!  MOV edx, [p.v_Seed]
!  MOVZX ecx, dx
!  SHR edx, 16
!  MOV esi, [p.v_Buffer]
!  MOV eax, [p.v_BufLen]
!  ADD eax, esi
!  XOr ebx, ebx
!  LP:
!  MOV bl, [esi]
!  ADD ecx, ebx
!  CMP ecx, 65521
!  JB M1
!  SUB ecx, 65521
!  M1:
!  ADD edx, ecx
!  CMP edx, 65521
!  JB M2
!  SUB edx, 65521
!  M2:
!  INC esi
!  CMP esi, eax
!  JNZ LP
!  SHL edx, 16
!  ADD ecx, edx
!  MOV [p.v_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)

[wilbert]

Yes, I noticed that ASM code.
Here's my (faster) one

Code: Select all

Procedure Adler32(*Buffer, BufferSize.i, Seed.l = 1); x86
  EnableASM
  MOV edx, *Buffer
  MOV ecx, BufferSize
  MOV eax, Seed
  DisableASM
  !push ebx
  !push ebp
  !push edi
  !push esi
  !movzx edi, ax
  !shr eax, 16
  !movzx esi, ax
  !mov ebx, edx
  !mov ebp, 65521
  !adler32_loop:
  !movzx eax, byte [ebx]
  !add edi, eax
  !add esi, edi
  !jns adler32_cont
  
  !adler32_mod:
  !xor edx, edx
  !mov eax, edi
  !div ebp
  !mov edi, edx
  !xor edx, edx
  !mov eax, esi
  !div ebp
  !mov esi, edx
  
  !adler32_cont:
  !inc ebx
  !sub ecx, 1
  !ja adler32_loop
  !jnc adler32_mod
  !mov eax, esi
  !shl eax, 16
  !or eax, edi
  !pop esi
  !pop edi
  !pop ebp
  !pop ebx
  ProcedureReturn
EndProcedure

Code: Select all

Procedure Adler32(*Buffer, BufferSize.i, Seed.l = 1); x64
  EnableASM
  MOV r8, *Buffer
  MOV r9, BufferSize
  MOV eax, Seed
  DisableASM
  !movzx r10, ax
  !shr rax, 16
  !movzx r11, ax
  !mov rcx, 65521
  !adler32_loop:
  !movzx rax, byte [r8]
  !add r10, rax
  !add r11, r10
  !jns adler32_cont
  
  !adler32_mod:
  !xor rdx, rdx
  !mov rax, r10
  !div rcx
  !mov r10, rdx
  !xor rdx, rdx
  !mov rax, r11
  !div rcx
  !mov r11, rdx
  
  !adler32_cont:
  !inc r8
  !sub r9, 1
  !ja adler32_loop
  !jnc adler32_mod
  !mov rax, r11
  !shl rax, 16
  !or rax, r10
  ProcedureReturn
EndProcedure

[Guimauve]

@Wilbert

It's possible to let the compiler to choose witch procedure to use depending on the processor

Code: Select all

CompilerSelect #PB_Compiler_Processor
    
  CompilerCase #PB_Processor_x86
    
    Procedure Adler32(*Buffer, BufferSize.i, Seed.l = 1); x86
      EnableASM
      MOV edx, *Buffer
      MOV ecx, BufferSize
      MOV eax, Seed
      DisableASM
      !push ebx
      !push ebp
      !push edi
      !push esi
      !movzx edi, ax
      !shr eax, 16
      !movzx esi, ax
      !mov ebx, edx
      !mov ebp, 65521
      !adler32_loop:
      !movzx eax, byte [ebx]
      !add edi, eax
      !add esi, edi
      !jns adler32_cont
      
      !adler32_mod:
      !xor edx, edx
      !mov eax, edi
      !div ebp
      !mov edi, edx
      !xor edx, edx
      !mov eax, esi
      !div ebp
      !mov esi, edx
      
      !adler32_cont:
      !inc ebx
      !sub ecx, 1
      !ja adler32_loop
      !jnc adler32_mod
      !mov eax, esi
      !shl eax, 16
      !or eax, edi
      !pop esi
      !pop edi
      !pop ebp
      !pop ebx
      ProcedureReturn
    EndProcedure
    
  CompilerCase #PB_Processor_x64
    
    Procedure Adler32(*Buffer, BufferSize.i, Seed.l = 1); x64
      EnableASM
      MOV r8, *Buffer
      MOV r9, BufferSize
      MOV eax, Seed
      DisableASM
      !movzx r10, ax
      !shr rax, 16
      !movzx r11, ax
      !mov rcx, 65521
      !adler32_loop:
      !movzx rax, byte [r8]
      !add r10, rax
      !add r11, r10
      !jns adler32_cont
      
      !adler32_mod:
      !xor rdx, rdx
      !mov rax, r10
      !div rcx
      !mov r10, rdx
      !xor rdx, rdx
      !mov rax, r11
      !div rcx
      !mov r11, rdx
      
      !adler32_cont:
      !inc r8
      !sub r9, 1
      !ja adler32_loop
      !jnc adler32_mod
      !mov rax, r11
      !shl rax, 16
      !or rax, r10
      ProcedureReturn
    EndProcedure
    
CompilerEndSelect

Best regards
Guimauve

[wilbert]

I know.
That might be a better solution.

I noticed all those Adler and Fletcher checksums look the same.
I'm thinking it might be useful to have them all in one procedure.
Adler64 / Fletcher64 should also be possible but I can't find any checksums online to check if the code would be correct.
Do you know of any test codes for those ?

[Guimauve]

I know.
That might be a better solution.

I noticed all those Adler and Fletcher checksums look the same.
I'm thinking it might be useful to have them all in one procedure.
Adler64 / Fletcher64 should also be possible but I can't find any checksums online to check if the code would be correct.
Do you know of any test codes for those ?

Unfortunately no, this is why I have stop the after the "32" version.

Best regards
Guimauve

[Guimauve]

A little modification of my previous message. This the proper way to to manage multi-processor codes.

Code: Select all

Procedure Adler32(*Buffer, BufferSize.i, Seed.l = 1)
  
  CompilerSelect #PB_Compiler_Processor
 
    CompilerCase #PB_Processor_x86

      EnableASM
      MOV edx, *Buffer
      MOV ecx, BufferSize
      MOV eax, Seed
      DisableASM
      !push ebx
      !push ebp
      !push edi
      !push esi
      !movzx edi, ax
      !shr eax, 16
      !movzx esi, ax
      !mov ebx, edx
      !mov ebp, 65521
      !adler32_loop:
      !movzx eax, byte [ebx]
      !add edi, eax
      !add esi, edi
      !jns adler32_cont
      
      !adler32_mod:
      !xor edx, edx
      !mov eax, edi
      !div ebp
      !mov edi, edx
      !xor edx, edx
      !mov eax, esi
      !div ebp
      !mov esi, edx
      
      !adler32_cont:
      !inc ebx
      !sub ecx, 1
      !ja adler32_loop
      !jnc adler32_mod
      !mov eax, esi
      !shl eax, 16
      !or eax, edi
      !pop esi
      !pop edi
      !pop ebp
      !pop ebx
      
    CompilerCase #PB_Processor_x64
      
      EnableASM
      MOV r8, *Buffer
      MOV r9, BufferSize
      MOV eax, Seed
      DisableASM
      !movzx r10, ax
      !shr rax, 16
      !movzx r11, ax
      !mov rcx, 65521
      !adler32_loop:
      !movzx rax, byte [r8]
      !add r10, rax
      !add r11, r10
      !jns adler32_cont
      
      !adler32_mod:
      !xor rdx, rdx
      !mov rax, r10
      !div rcx
      !mov r10, rdx
      !xor rdx, rdx
      !mov rax, r11
      !div rcx
      !mov r11, rdx
      
      !adler32_cont:
      !inc r8
      !sub r9, 1
      !ja adler32_loop
      !jnc adler32_mod
      !mov rax, r11
      !shl rax, 16
      !or rax, r10
      
  CompilerEndSelect
  
  ProcedureReturn
EndProcedure

This way the Adler32() appear only once instead of two in the procedure browser.

Best regards
Guimauve

[wilbert]

Here's a more universal approach but Adler and Fletcher 64 are only available for x64 and Adler 64 is unverified.

Code: Select all

Procedure AFChecksum(*Buffer, BufferSize.i, Mode.i = 2)
  EnableASM
  CompilerSelect #PB_Compiler_Processor
    CompilerCase #PB_Processor_x86
      MOV edx, *Buffer
      MOV ecx, BufferSize
      MOV eax, Mode
      !push ebx
      !push ebp
      !push edi
      !push esi
      !and eax, 7
      !shl eax, 4
      !lea ebx, [aftable + eax]
      !mov ebp, [ebx]
      !mov edi, [ebx + 4]
      !mov esi, [ebx + 8]
      !mov al, [ebx + 12] 
      !mov [esp - 1], al
      !mov ebx, edx
      !afchecksum_loop:
      !movzx eax, byte [ebx]
      !add edi, eax
      !add esi, edi
      !jns afchecksum_cont
      !afchecksum_mod:
      !xor edx, edx
      !mov eax, edi
      !div ebp
      !mov edi, edx
      !xor edx, edx
      !mov eax, esi
      !div ebp
      !mov esi, edx
      !afchecksum_cont:
      !inc ebx
      !sub ecx, 1
      !ja afchecksum_loop
      !jnc afchecksum_mod
      !mov cl, [esp - 1]
      !mov eax, esi
      !shl eax, cl
      !or eax, edi
      !pop esi
      !pop edi
      !pop ebp
      !pop ebx
    CompilerCase #PB_Processor_x64
      MOV r8, *Buffer
      MOV r9, BufferSize
      MOV rax, Mode
      !and rax, 7
      !shl rax, 4
      !lea r10, [aftable]
      !lea r10, [r10 + rax]
      !mov ecx, [r10]
      !mov edx, [r10 + 4]
      !mov eax, [r10 + 8]
      !mov r11, rax
      !mov al, [r10 + 12] 
      !mov [esp - 1], al    
      !mov r10, rdx
      !afchecksum_loop:
      !movzx rax, byte [r8]
      !add r10, rax
      !add r11, r10
      !jns afchecksum_cont
      !afchecksum_mod:
      !xor rdx, rdx
      !mov rax, r10
      !div rcx
      !mov r10, rdx
      !xor rdx, rdx
      !mov rax, r11
      !div rcx
      !mov r11, rdx
      !afchecksum_cont:
      !inc r8
      !sub r9, 1
      !ja afchecksum_loop
      !jnc afchecksum_mod
      !mov cl, [esp - 1]
      !mov rax, r11
      !shl rax, cl
      !or rax, r10
  CompilerEndSelect
  ProcedureReturn
  !aftable:
  !dd 0xf, 0xf, 0xf, 0x4; Fletcher-8 (mode 0)
  !dd 0xff, 0xff, 0xff, 0x8; Fletcher-16 (mode 1)
  !dd 0xffff, 0xffff, 0xffff, 0x10; Fletcher-32 (mode 2)
  !dd 0xffffffff, 0xffffffff, 0xffffffff, 0x20; Fletcher-64 (mode 3)
  !dd 0xd, 0x1, 0x0, 0x4; Adler-8 (mode 4)
  !dd 0xfb, 0x01, 0x00, 0x8; Adler-16 (mode 5)
  !dd 0xfff1, 0x0001, 0x0000, 0x10; Adler-32 (mode 6)
  !dd 0xfffffffb, 0x00000001, 0x00000000, 0x20; Adler-64 (mode 7)
  DisableASM
EndProcedure

For Fletcher64 I have a separate x86 version

Code: Select all

Procedure.q Fletcher64(*Buffer, BufferSize.i); x86
  EnableASM
  MOV edx, *Buffer
  MOV ecx, BufferSize
  !push edi
  !push esi
  !mov edi, -1
  !mov esi, -1
  !fletcher64_loop:
  !movzx eax, byte [edx]
  !add edi, eax
  !adc edi, 0
  !add esi, edi
  !adc esi, 0
  !inc edx
  !dec ecx
  !jnz fletcher64_loop
  !mov edx, esi
  !mov eax, edi
  !add edx, 1
  !adc edx, -1
  !add eax, 1
  !adc eax, -1
  !pop esi
  !pop edi
  ProcedureReturn
  DisableASM
EndProcedure