FastCRC module

Share your advanced PureBasic knowledge/code with the community.
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

FastCRC module

Post by wilbert »

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: Select all

; 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
Last edited by wilbert on Mon Aug 26, 2019 6:12 am, edited 6 times in total.
Windows (x64)
Raspberry Pi OS (Arm64)
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: FastCRC module

Post by wilbert »

Example

Code: Select all

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)
Last edited by wilbert on Fri Aug 23, 2019 3:23 pm, edited 1 time in total.
Windows (x64)
Raspberry Pi OS (Arm64)
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: FastCRC module

Post by Kwai chang caine »

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)
ImageThe happiness is a road...
Not a destination
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: FastCRC module

Post by wilbert »

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.
Windows (x64)
Raspberry Pi OS (Arm64)
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: FastCRC module

Post by Kwai chang caine »

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
168b9520
5f715dd2b17bd448
ImageThe happiness is a road...
Not a destination
collectordave
Addict
Addict
Posts: 1309
Joined: Fri Aug 28, 2015 6:10 pm
Location: Portugal

Re: FastCRC module

Post by collectordave »

Thanks wilbert

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

Just brilliant.

CD
Any intelligent fool can make things bigger and more complex. It takes a touch of genius — and a lot of courage to move in the opposite direction.
User avatar
Mijikai
Addict
Addict
Posts: 1360
Joined: Sun Sep 11, 2016 2:17 pm

Re: FastCRC module

Post by Mijikai »

Wow, thank you Wilbert :)
collectordave
Addict
Addict
Posts: 1309
Joined: Fri Aug 28, 2015 6:10 pm
Location: Portugal

Re: FastCRC module

Post by collectordave »

Just tried with Checkoggfile app using:-

Code: Select all

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: Select all

      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
Any intelligent fool can make things bigger and more complex. It takes a touch of genius — and a lot of courage to move in the opposite direction.
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: FastCRC module

Post by wilbert »

Thanks for the positive feedback :)
collectordave wrote:

Code: Select all

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:
Windows (x64)
Raspberry Pi OS (Arm64)
collectordave
Addict
Addict
Posts: 1309
Joined: Fri Aug 28, 2015 6:10 pm
Location: Portugal

Re: FastCRC module

Post by collectordave »

oticed the uppercase and did this

Code: Select all

Procedure.s HexCRC(CRC.q, Width, UpperCase = #True)
Still came back with lowercase.

Changed my call to

Code: Select all

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
Any intelligent fool can make things bigger and more complex. It takes a touch of genius — and a lot of courage to move in the opposite direction.
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: FastCRC module

Post by wilbert »

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: Select all

InitCustomCRC(32, $04c11db7, 0, 0, 0, 0)
A.l = $12345678
Debug HexCRC(FastCRC(#CUSTOM_CRC, @A, 4), 32)
Windows (x64)
Raspberry Pi OS (Arm64)
Post Reply