PureBasic Forum
https://www.purebasic.fr/english/

FastCRC module
https://www.purebasic.fr/english/viewtopic.php?f=12&t=73462
Page 1 of 1

Author:  wilbert [ Fri Aug 23, 2019 12:27 pm ]
Post subject:  FastCRC module

FastCRC is an asm optimized CRC module capable of calculating CRC's with a width between 1 and 64 bits.
It uses Slice-8 for x64 and Slice-4 for x86.
Data tables are 16KiB for each algorithm on x64 and 8KiB for each algorithm on x86.

Feedback is welcome :)
If there's a CRC algorithm you need that isn't in the preset list, feel also free to let me know.

Wilbert

Code:
; FastCRC module by Wilbert

; Last updated : August 26, 2019

; CRC parameters came from
; http://reveng.sourceforge.net/crc-catalogue/
 
DeclareModule FastCRC
 
  Enumeration
    #CRC8
    #CRC16_CCITT
    #CRC16_MODBUS
    #CRC32
    #CRC32_BZIP2
    #CRC32_C
    #CRC32_OGG
    #CRC64_ECMA
    #CRC64_ISO
   
    #CUSTOM_CRC
    #_CRC_COUNT_
  EndEnumeration
 
  Declare.q FastCRC (CRCType, *Buffer.Ascii, Size, Continuation = #False, CRC.q = 0)
  Declare.q FileCRC (CRCType, Filename.s)
  Declare.s HexCRC  (CRC.q, Width, UpperCase = #False)
  Declare.q Reflect (CRC.q, Width)
 
  Declare InitCustomCRC (Width, Poly.q, Init.q, RefIn, RefOut, XOrOut.q)
 
EndDeclareModule

Module FastCRC
 
  DisableDebugger
  EnableExplicit
  EnableASM
 
  ;->> Constants <<
  #Slices = SizeOf(Integer); Use 8 slices on x64 and 4 on x86
     
  ;->> Structures <<
  Structure Nibbles : n.a[16] : EndStructure
  Structure _CRCTable : n.q[256] : EndStructure
  Structure CRCTable  : s._CRCTable[#Slices] : EndStructure
 
  Structure CRC_Info
    Width.i
    Poly.q
    Init.q
    RefIn.i
    RefOut.i
    XOrOut.q
    Check.q
    Name.s
    LUT.CRCTable
  EndStructure
 
  ;->> Globals <<
  Global Dim CRC_Info.CRC_Info(#_CRC_COUNT_ - 1)
 
  ;->> INITIALIZE ALGORITHMS <<
  Declare InitCRC(CRCType, Width, Poly.q, Init.q, RefIn, RefOut, XOrOut.q, Check.q, Name.s)
 
  InitCRC(#CRC8, 8, $07, 0, #False, #False, 0, $f4, "CRC-8")
  InitCRC(#CRC16_CCITT, 16, $1021, -1, #False, #False, 0, $29b1, "CRC-16/CCITT")
  InitCRC(#CRC16_MODBUS, 16, $8005, -1, #True, #True, 0, $4b37, "CRC-16/MODBUS")
  InitCRC(#CRC32, 32, $04c11db7, -1, #True, #True, -1, $cbf43926, "CRC-32")
  InitCRC(#CRC32_BZIP2, 32, $04c11db7, -1, #False, #False, -1, $fc891918, "CRC-32/BZIP2")
  InitCRC(#CRC32_C, 32, $1edc6f41, -1, #True, #True, -1, $e3069283, "CRC-32/C")
  InitCRC(#CRC32_OGG, 32, $04c11db7, 0, #False, #False, 0, $89a1897f, "CRC-32/OGG")
  InitCRC(#CRC64_ECMA, 64, $42f0e1eba9ea3693, 0, #False, #False, 0, $6c40df5f0b497347, "CRC-64/ECMA")
  InitCRC(#CRC64_ISO, 64, $000000000000001b, -1, #True, #True, -1, $b90956c775a41001, "CRC-64/ISO")
 
  ;->> Procedures <<
 
  ; >> Swap bytes <<
  Procedure.q BSwap64(CRC.q)
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rax, [p.v_CRC]
      !bswap rax
      ProcedureReturn
    CompilerElse
      !mov edx, [p.v_CRC]
      !mov eax, [p.v_CRC + 4]
      !bswap edx
      !bswap eax
      ProcedureReturn
    CompilerEndIf
  EndProcedure 
 
  ; >> Reverse bits <<
  Procedure.q Reflect(CRC.q, Width)
    Protected CRC_.q, i = Width
    While i
      CRC_ | (CRC >> (i - 1) & 1) << (Width - i)
      i - 1
    Wend
    ProcedureReturn CRC_
  EndProcedure
 
  ; >> Convert CRC to string <<
  Procedure.s HexCRC(CRC.q, Width, UpperCase = #False)
    Protected c, n, Nibbles.Nibbles
    If Width < 64
      CRC & (1 << Width - 1)
    EndIf
    If UpperCase
      c = $37
    Else
      c = $57
    EndIf
    Width = (Width + 3) >> 2
    While Width
      Width - 1
      n = CRC & $f
      If n > 9
        Nibbles\n[Width] = c + n
      Else
        Nibbles\n[Width] = $30 + n
      EndIf
      CRC >> 4
    Wend
    ProcedureReturn PeekS(@Nibbles, 16, #PB_Ascii)
  EndProcedure
 
  ; >> Initialize CRC table <<
  Procedure InitCRCTable(*CRCTable.CRCTable, Width, Poly.q, RefIn)
    Protected.i i, j, k, CRC.q
   
    If RefIn
      Poly = Reflect(Poly, Width)
      For i = 0 To 255
        !xor edx, edx               ; edx:eax = i
        !mov eax, [p.v_i]
        !mov ecx, 8                 ; loop 8 times
        !.refl_loop:
        !shr edx, 1                 ; edx:eax >> 1
        !rcr eax, 1
        !jnc .refl_xor_skip         ; if shifted out bit was set
        !xor eax, [p.v_Poly]        ; xor edx:eax, Poly
        !xor edx, [p.v_Poly + 4]
        !.refl_xor_skip:
        !sub ecx, 1
        !jnz .refl_loop
        !mov [p.v_CRC], eax         ; CRC = edx:eax
        !mov [p.v_CRC + 4], edx
        *CRCTable\s[0]\n[i] = CRC
      Next
    Else
      Poly << (64 - Width)
      For i = 0 To 255
        !xor eax, eax               ; edx:eax = i << 56
        !mov edx, [p.v_i]
        !shl edx, 24
        !mov ecx, 8                 ; loop 8 times
        !.fwd_loop:
        !add eax, eax               ; edx:eax << 1
        !adc edx, edx
        !jnc .fwd_xor_skip          ; if shifted out bit was set
        !xor eax, [p.v_Poly]        ; xor edx:eax, Poly
        !xor edx, [p.v_Poly + 4]
        !.fwd_xor_skip:
        !sub ecx, 1
        !jnz .fwd_loop
        !bswap eax                  ; swap bytes of edx:eax
        !bswap edx
        !mov [p.v_CRC], edx         ; store to CRC
        !mov [p.v_CRC + 4], eax       
        *CRCTable\s[0]\n[i] = CRC
      Next 
    EndIf
   
    For i = 0 To 255
      CRC = *CRCTable\s[0]\n[i]
      For j = 1 To #Slices - 1
        !mov eax, [p.v_CRC]         ; edx:eax = CRC
        !mov edx, [p.v_CRC + 4]
        !mov [p.v_k], al            ; k = al
        !shrd eax, edx, 8           ; edx:eax >> 8
        !shr edx, 8
        !mov [p.v_CRC], eax         ; CRC = edx:eax
        !mov [p.v_CRC + 4], edx
        CRC ! *CRCTable\s[0]\n[k]
        *CRCTable\s[j]\n[i] = CRC
      Next
    Next
   
  EndProcedure
 
  ; >> Initialize CRC algorithm <<
  Procedure InitCRC(CRCType, Width, Poly.q, Init.q, RefIn, RefOut, XOrOut.q, Check.q, Name.s)
    CRC_Info(CRCType)\Width = Width
    CRC_Info(CRCType)\Poly = Poly
    CRC_Info(CRCType)\RefIn = RefIn
    CRC_Info(CRCType)\RefOut = RefOut
    CRC_Info(CRCType)\Check = Check
    CRC_Info(CRCType)\Name = Name
    If Width < 64
      CRC_Info(CRCType)\Init = Init & (1 << Width - 1)
      CRC_Info(CRCType)\XOrOut = XOrOut & (1 << Width - 1)
    Else
      CRC_Info(CRCType)\Init = Init
      CRC_Info(CRCType)\XOrOut = XOrOut
    EndIf
    InitCRCTable(@CRC_Info(CRCType)\LUT, Width, Poly, RefIn)
  EndProcedure
 
  ;->> Main CRC procedure <<
 
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    Macro M_FastCRC(slice)
      !movzx eax, dl
      !shr rdx, 8
      !xor r8, [r10 + slice*2048 + rax*8]
    EndMacro
  CompilerElse
    Macro M_FastCRC(slice)
      !movzx ebx, cl
      !shr ecx, 8
      !xor eax, [edi + slice*2048 + ebx*8]
      !xor edx, [edi + slice*2048 + ebx*8 + 4]
    EndMacro
  CompilerEndIf
 
  Procedure.q FastCRC(CRCType, *Buffer.Ascii, Size, Continuation = #False, CRC.q = 0)
    Protected *CRCTable.CRCTable = @CRC_Info(CRCType)\LUT
    Protected Width = CRC_Info(CRCType)\Width
   
    If Continuation
      CRC ! CRC_Info(CRCType)\XOrOut
      If CRC_Info(CRCType)\RefOut <> CRC_Info(CRCType)\RefIn
        CRC = Reflect(CRC, Width) 
      EndIf
      If CRC_Info(CRCType)\RefIn = #False
        CRC = BSwap64(CRC << (64 - Width))
      EndIf   
    Else
      CRC = CRC_Info(CRCType)\Init
    EndIf
   
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov r8, [p.v_CRC]
      !mov r9, [p.p_Buffer]
      !mov r10, [p.p_CRCTable]
      !mov ecx, [p.v_Size]
      !.l0:                         ; 8 bytes at a time loop
      !sub ecx, 8
      !jc .l1
      !mov rdx, [r9]
      !add r9, 8
      !xor rdx, r8
      !xor r8, r8
      M_FastCRC(7)
      M_FastCRC(6)
      M_FastCRC(5)
      M_FastCRC(4)
      M_FastCRC(3)
      M_FastCRC(2)
      M_FastCRC(1)
      M_FastCRC(0)
      !jmp .l0
      !.l1:
      !test ecx, 4
      !jz .l2
      !mov edx, [r9]                ; handle 4 bytes
      !add r9, 4
      !xor rdx, r8   
      !shr r8, 32
      M_FastCRC(3)
      M_FastCRC(2)
      M_FastCRC(1)
      M_FastCRC(0)
      !.l2:
      !test ecx, 2
      !jz .l3
      !movzx edx, word [r9]         ; handle 2 bytes
      !add r9, 2
      !xor rdx, r8
      !shr r8, 16
      M_FastCRC(1)
      M_FastCRC(0)
      !.l3:
      !test ecx, 1
      !jz .l4
      !movzx edx, byte [r9]         ; handle 1 byte
      !xor rdx, r8   
      !shr r8, 8
      M_FastCRC(0)
      !.l4:
      !mov [p.v_CRC], r8
    CompilerElse
      !mov [esp - 4], ebx           ; backup ebx, esi and edi
      !mov [esp - 8], esi
      !mov [esp - 12], edi
      !mov edi, [p.p_CRCTable]
      !mov esi, [p.p_Buffer]
      !mov eax, [p.v_CRC]
      !mov edx, [p.v_CRC + 4]
      !.l0:                         ; 4 bytes at a time loop
      !sub dword [p.v_Size], 4
      !jc .l1
      !mov ecx, [esi]
      !add esi, 4
      !xor ecx, eax
      !mov eax, edx
      !xor edx, edx
      M_FastCRC(3)
      M_FastCRC(2)
      M_FastCRC(1)
      M_FastCRC(0)
      !jmp .l0
      !.l1:
      !test dword [p.v_Size], 2
      !jz .l2
      !movzx ecx, word [esi]        ; handle 2 bytes
      !add esi, 2
      !xor ecx, eax
      !shrd eax, edx, 16
      !shr edx, 16
      M_FastCRC(1)
      M_FastCRC(0)
      !.l2:
      !test dword [p.v_Size], 1
      !jz .l3
      !movzx ecx, byte [esi]        ; handle 1 byte
      !xor ecx, eax
      !shrd eax, edx, 8
      !shr edx, 8
      M_FastCRC(0)
      !.l3:
      !mov [p.v_CRC], eax           ; store result
      !mov [p.v_CRC + 4], edx
      !mov edi, [esp - 12]          ; restore edi, esi and ebx
      !mov esi, [esp - 8]
      !mov ebx, [esp - 4]
    CompilerEndIf
   
    If CRC_Info(CRCType)\RefIn = #False
      CRC = BSwap64(CRC) >> (64 - Width)
      If Width < 64
        CRC = CRC & (1 << Width - 1)
      EndIf
    EndIf       
   
    If CRC_Info(CRCType)\RefOut <> CRC_Info(CRCType)\RefIn
      CRC = Reflect(CRC, Width) 
    EndIf
    ProcedureReturn CRC ! CRC_Info(CRCType)\XOrOut
   
  EndProcedure
 
  ; >> Set custom CRC algorithm <<
  Procedure InitCustomCRC(Width, Poly.q, Init.q, RefIn, RefOut, XOrOut.q)
    InitCRC(#CUSTOM_CRC, Width, Poly, Init, RefIn, RefOut, XOrOut, 0, "")
  EndProcedure
   
  ; >> Calculate the CRC of a file <<
  Procedure.q FileCRC(CRCType, Filename.s)
    Protected Dim Buffer.q(4095); 32 KiB
    Protected.i File, Bytes, CRC.q
   
    File = ReadFile(#PB_Any, Filename)
    Bytes = ReadData(File, @Buffer(), 32768)
    CRC = FastCRC(CRCType, @Buffer(), Bytes)
    While Bytes
      Bytes = ReadData(File, @Buffer(), 32768)
      CRC = FastCRC(CRCType, @Buffer(), Bytes, #True, CRC)
    Wend
    CloseFile(File)
   
    ProcedureReturn CRC
  EndProcedure 
 
   
  ;->> Internal check when debugger is on <<
  EnableDebugger
  CompilerIf #PB_Compiler_Debugger
    Procedure Check()
      Protected.i i, CRC1.q, CRC2.q
      Protected Dim DataBytes.a(9)
      PokeS(@DataBytes(), "123456789", 9, #PB_Ascii)
      ; Check all predefined CRC algorithms
      While i < #CUSTOM_CRC
        CRC1 = FastCRC(i, @DataBytes(), 7)
        CRC1 = FastCRC(i, @DataBytes(7), 2, #True, CRC1)
        CRC2 = FastCRC(i, @DataBytes(), 9)
        If CRC1 <> CRC2 Or CRC1 <> CRC_Info(i)\Check
          Debug "There's a problem with " + CRC_Info(i)\Name
        EndIf
        i + 1
      Wend
      ; Check some special conditions
      For i = 1 To 3
        Select i
          Case 1:
            InitCRC(#CUSTOM_CRC, 5, $05, -1, #True, #True, -1, $19, "CRC-5/USB"); Width < 8
          Case 2:
            InitCRC(#CUSTOM_CRC, 12, $80f, 0, #False, #True, 0, $daf, "CRC-12/UMTS"); RefIn <> RefOut
          Case 3:
            InitCRC(#CUSTOM_CRC, 40, $0004820009, 0, #False, #False, -1, $d4164fc646, "CRC-40/GSM"); Width 40
        EndSelect
        CRC1 = FastCRC(#CUSTOM_CRC, @DataBytes(), 7)
        CRC1 = FastCRC(#CUSTOM_CRC, @DataBytes(7), 2, #True, CRC1)
        CRC2 = FastCRC(#CUSTOM_CRC, @DataBytes(), 9)
        If CRC1 <> CRC2 Or CRC1 <> CRC_Info(#CUSTOM_CRC)\Check
          Debug "There's a problem with " + CRC_Info(#CUSTOM_CRC)\Name
        EndIf
      Next
    EndProcedure
    Check()
  CompilerEndIf
 
EndModule

Author:  wilbert [ Fri Aug 23, 2019 12:28 pm ]
Post subject:  Re: FastCRC module

Example
Code:
UseModule FastCRC

*Mem = AllocateMemory(1234567, #PB_Memory_NoClear)
RandomSeed(0)
RandomData(*Mem, 1234567)

CRC.q = FastCRC(#CRC32, *Mem, 1234567)
Debug HexCRC(CRC, 32)

CRC.q = FastCRC(#CRC64_ISO, *Mem, 1234567)
Debug HexCRC(CRC, 64)

Author:  Kwai chang caine [ Fri Aug 23, 2019 3:19 pm ]
Post subject:  Re: FastCRC module

Hello Wilbert :D
Juste for your information :wink: (because i don't know what is the real use of your splendid and complex code) :oops:
That works here, with W10 X64 / V5.70 X86
I have "afddbd76" like return
Thanks for sharing 8)

Author:  wilbert [ Fri Aug 23, 2019 3:27 pm ]
Post subject:  Re: FastCRC module

Kwai chang caine wrote:
I have "afddbd76" like return

Thanks for letting me know that it works KCC :)

I didn't use RandomSeed so the returned value was different each time.
So I updated my example code above.
On my computer it now returns...

168b9520
5f715dd2b17bd448

The module is just for when you need to calculate the CRC for a lot of data and you need it to be fast or can be useful when you need a crc algorithm that is not very common since it's a more general solution without a hardcoded lookup table.

Author:  Kwai chang caine [ Sat Aug 24, 2019 7:08 pm ]
Post subject:  Re: FastCRC module

Master wrote:
Thanks for letting me know that it works KCC
Always happy to can help a little bit one of my saver :wink:

Me too i have now :D
Quote:
168b9520
5f715dd2b17bd448

Author:  collectordave [ Sun Aug 25, 2019 8:30 am ]
Post subject:  Re: FastCRC module

Thanks wilbert

With 19,000 + ogg files to tag properly I will certainly be giving this a good workout.

Just brilliant.

CD

Author:  Mijikai [ Sun Aug 25, 2019 8:47 am ]
Post subject:  Re: FastCRC module

Wow, thank you Wilbert :)

Author:  collectordave [ Sun Aug 25, 2019 9:15 am ]
Post subject:  Re: FastCRC module

Just tried with Checkoggfile app using:-

Code:
Procedure.s MyFastCRC(*Buffer,BufferLength.i)
   
 Define CRC.q

CRC = FastCRC::FastCRC(FastCRC::#CRC32_OGG, *Buffer,BufferLength)
ProcedureReturn UCase(FastCRC::HexCRC(CRC, 32))
 
EndProcedure


Had trouble with

Code:
      OriginalCheckSum = Hex(PeekL(*Buffer + 22),#PB_Long)
     
      OriginalCheckSum = RSet(OriginalCheckSum,8,"0")


The PB Hex() doesn't pack the leading zeros so added second line

The difference with a medium sized ogg file can be counted in seconds, using fastcrc blink and you miss it.

This was a WOW moment

Thanks wilbert

Author:  wilbert [ Sun Aug 25, 2019 11:10 am ]
Post subject:  Re: FastCRC module

Thanks for the positive feedback :)

collectordave wrote:
Code:
ProcedureReturn UCase(FastCRC::HexCRC(CRC, 32))

Don't know if you already noticed it but the HexCRC procedure has an optional parameter to return an uppercase result. :wink:

Author:  collectordave [ Sun Aug 25, 2019 1:26 pm ]
Post subject:  Re: FastCRC module

oticed the uppercase and did this

Code:
Procedure.s HexCRC(CRC.q, Width, UpperCase = #True)


Still came back with lowercase.

Changed my call to

Code:
FastCRC::HexCRC(CRC, 32,#True)


and it comes back in uppercase.

I thought that where a parameter was not specified it would use the default in the procedure.

However I did not change it in the declaration section. A little duh! moment

CD

Author:  wilbert [ Mon Aug 26, 2019 6:21 am ]
Post subject:  Re: FastCRC module

I updated the code of the module.
Quite a few of the CRC algorithms I added were probably never going to be used and only there to check some special conditions to make sure the CRC module itself functions properly.
I removed those from the preset list and included some additional checks in the procedure named Check which is only being called if the debugger is on.

You can also set a custom algorithm now without modifying the preset list.
Code:
InitCustomCRC(32, $04c11db7, 0, 0, 0, 0)
A.l = $12345678
Debug HexCRC(FastCRC(#CUSTOM_CRC, @A, 4), 32)

Page 1 of 1 All times are UTC + 1 hour
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/