It is currently Thu Oct 24, 2019 12:37 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: FastCRC module
PostPosted: Fri Aug 23, 2019 12:27 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3493
Location: Netherlands
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

_________________
macOS 10.15 Catalina, PB 5.71 x64


Last edited by wilbert on Mon Aug 26, 2019 6:12 am, edited 6 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Fri Aug 23, 2019 12:28 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3493
Location: Netherlands
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)

_________________
macOS 10.15 Catalina, PB 5.71 x64


Last edited by wilbert on Fri Aug 23, 2019 3:23 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Fri Aug 23, 2019 3:19 pm 
Offline
Addict
Addict
User avatar

Joined: Sun Nov 05, 2006 11:42 pm
Posts: 4511
Location: Lyon - France
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


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Fri Aug 23, 2019 3:27 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3493
Location: Netherlands
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.

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sat Aug 24, 2019 7:08 pm 
Offline
Addict
Addict
User avatar

Joined: Sun Nov 05, 2006 11:42 pm
Posts: 4511
Location: Lyon - France
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

_________________
ImageThe happiness is a road...
Not a destination


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sun Aug 25, 2019 8:30 am 
Offline
Addict
Addict

Joined: Fri Aug 28, 2015 6:10 pm
Posts: 1026
Location: Portugal
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sun Aug 25, 2019 8:47 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Sep 11, 2016 2:17 pm
Posts: 544
Wow, thank you Wilbert :)


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sun Aug 25, 2019 9:15 am 
Offline
Addict
Addict

Joined: Fri Aug 28, 2015 6:10 pm
Posts: 1026
Location: Portugal
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

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


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sun Aug 25, 2019 11:10 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3493
Location: Netherlands
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:

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Sun Aug 25, 2019 1:26 pm 
Offline
Addict
Addict

Joined: Fri Aug 28, 2015 6:10 pm
Posts: 1026
Location: Portugal
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

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


Top
 Profile  
Reply with quote  
 Post subject: Re: FastCRC module
PostPosted: Mon Aug 26, 2019 6:21 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3493
Location: Netherlands
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)

_________________
macOS 10.15 Catalina, PB 5.71 x64


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye