Results 1 to 5 of 5

Thread: What's wrong with this CRC32 algorithm?

  1. #1

    Thread Starter
    Frenzied Member
    Join Date
    Oct 2008
    Posts
    1,181

    What's wrong with this CRC32 algorithm?

    It has 4 settings, InvertInitCRC, MirrorInputBits, MirrorOutputBits, and InvertFinalCRC.
    The standard official CRC32 has all of these set to true, so that was what I first tested it with. And it worked fine with that. I then set each of these to false, one at a time. So I ran 4 tests, each test had 3 of the for settings set to true, and 1 was set to false.
    It worked fine when InvertInitCRC was false.
    It worked fine when MirrorOutputBits was set to false.
    It worked fine when InvertFinalCRC was set to false.
    But it failed when MirrorInputBits was set to false.

    When it failed, it did so by producing a CRC that differed from the output of another known program that calculates CRCs, given the same input and settings in both my own CRC32 implementation and the other program I used to test it.

    The test input data was the ascii string "This is a test."

    The output of my CRC32 when all the settings are True except for MirrorInputBits is:
    D7D303E7

    The output of HxD hex editor (the program I tested my program against) when given the same input, and the same settings as in my program is:
    82AF7086


    My program's CRC32 calculation code is:
    Code:
    Private Const Poly As Long = &H4C11DB7
    
    Private Function CRC32(ByRef Data() As Byte, _
                           ByVal InvertInitCRC As Boolean, _
                           ByVal MirrorInputBits As Boolean, _
                           ByVal MirrorOutputBits As Boolean, _
                           ByVal InvertFinalCRC As Boolean) As Long
                           
                            
    Dim ByteNumber As Long
    Dim BitNumber As Long
    Dim CurrentByte As Long
    Dim CRC As Long
    
    If InvertInitCRC Then CRC = &HFFFFFFFF Else CRC = 0
    
    For ByteNumber = 0 To UBound(Data)
        CurrentByte = Data(ByteNumber)
        If MirrorInputBits Then CurrentByte = ReverseBits32(CurrentByte)
        For BitNumber = 0 To 7
            If (CRC Xor CurrentByte) And &H80000000 Then
                CRC = ShiftLeft32(CRC) Xor Poly
            Else
                CRC = ShiftLeft32(CRC)
            End If
            CurrentByte = ShiftLeft32(CurrentByte)
        Next BitNumber
    Next ByteNumber
    If MirrorOutputBits Then CRC = ReverseBits32(CRC)
    If InvertFinalCRC Then CRC = CRC Xor &HFFFFFFFF
    CRC32 = CRC
    End Function
    
    Private Sub Command1_Click()
    Dim Data() As Byte
    Data() = StrConv("This is a test.", vbFromUnicode)
    Print Hex$(CRC32(Data, True, False, True, True))
    End Sub
    Note that I have neglected to show the supporting functions (such as ShiftLeft32) that the main function uses in the above code snippet, as I have tested them completely and know that they work 100%.


    This help request goes out to any advanced VB6 users who are intimately familiar with CRC algorithms, and who have knowledge of the most common mistakes that programmers might make when implementing CRC algorithms, and how those mistakes would affect the output of a CRC for a given input (in terms of how the input bit pattern is transformed incorrectly by a bad CRC implementation into an incorrect output bit pattern). Any help from advanced programmers here is extremely important for me. Thanks for any help you might be able to give in debugging my code.


    Note that this is not completely my own work. This is my VB6 implementation (with a few extra arguments for the function to make it more versatile) of the below C code that I found in the text document http://www.hackersdelight.org/hdcodetxt/crc.c.txt and therefore it is possible that my source had buggy code to start with.

    Code:
    unsigned int crc32a(unsigned char *message) {
       int i, j;
       unsigned int byte, crc;
    
       i = 0;
       crc = 0xFFFFFFFF;
       while (message[i] != 0) {
          byte = message[i];            // Get next byte.
          byte = reverse(byte);         // 32-bit reversal.
          for (j = 0; j <= 7; j++) {    // Do eight times.
             if ((int)(crc ^ byte) < 0)
                  crc = (crc << 1) ^ 0x04C11DB7;
             else crc = crc << 1;
             byte = byte << 1;          // Ready next msg bit.
          }
          i = i + 1;
       }
       return reverse(~crc);
    }
    Last edited by Ben321; Jun 11th, 2015 at 12:17 PM.

  2. #2
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: What's wrong with this CRC32 algorithm?

    Since you didn't provide the ReverseBits32 and ShiftLeft32 functions, and I don't feel like writing them myself, I'll just take a guess based on what I see in your code, rather than any knowledge of CRC32 in general.

    Since ReverseBits32 is acting on a 32-bit value, and you set an 8-bit value into the 32-bit value, it is accomplishing two things.
    It is reversing the bits of the 8-bit input, but it is also swapping the 8-bit byte to the most significant byte of the 32-bit value, aka byte swapping the 4-byte value.

    I'll take the guess that the byte swapping is important for the algorithm, and you don't do that in the non-MirrorInputBits case.
    So, I would test doing that to see if it fixes your issue. You could do that as below, which would swap the lowest 8-bits of the 32-bit value before swapping the bytes. Alternatively, of course, you could just swap the 8-bits in the byte before assigning the byte to CurrentByte, then do the byte swap.
    Code:
        For ByteNumber = 0 To UBound(Data)
          CurrentByte = Data(ByteNumber)
            If MirrorInputBits Then CurrentByte = ReverseTheInputBits_i_e_theLower8bitsOftheInput(CurrentByte)
    
            CurrentByte = Swap4(CurrentByte)  'always swap the 4 bytes to make the number BigEndian
    '...
    p.s. I did go ahead and write a ReverseBits32, ReverseBits8 and swap4, and did get 82AF7086 with the modified code, so it would seem to indicate that was your issue.
    Last edited by passel; Jun 11th, 2015 at 06:21 AM.

  3. #3

    Thread Starter
    Frenzied Member
    Join Date
    Oct 2008
    Posts
    1,181

    Re: What's wrong with this CRC32 algorithm?

    Quote Originally Posted by passel View Post
    Since you didn't provide the ReverseBits32 and ShiftLeft32 functions, and I don't feel like writing them myself, I'll just take a guess based on what I see in your code, rather than any knowledge of CRC32 in general.

    Since ReverseBits32 is acting on a 32-bit value, and you set an 8-bit value into the 32-bit value, it is accomplishing two things.
    It is reversing the bits of the 8-bit input, but it is also swapping the 8-bit byte to the most significant byte of the 32-bit value, aka byte swapping the 4-byte value.

    I'll take the guess that the byte swapping is important for the algorithm, and you don't do that in the non-MirrorInputBits case.
    So, I would test doing that to see if it fixes your issue. You could do that as below, which would swap the lowest 8-bits of the 32-bit value before swapping the bytes. Alternatively, of course, you could just swap the 8-bits in the byte before assigning the byte to CurrentByte, then do the byte swap.
    Code:
        For ByteNumber = 0 To UBound(Data)
          CurrentByte = Data(ByteNumber)
            If MirrorInputBits Then CurrentByte = ReverseTheInputBits_i_e_theLower8bitsOftheInput(CurrentByte)
    
            CurrentByte = Swap4(CurrentByte)  'always swap the 4 bytes to make the number BigEndian
    '...
    p.s. I did go ahead and write a ReverseBits32, ReverseBits8 and swap4, and did get 82AF7086 with the modified code, so it would seem to indicate that was your issue.


    Ok, thanks. I'll have to try that.

  4. #4

    Thread Starter
    Frenzied Member
    Join Date
    Oct 2008
    Posts
    1,181

    Re: What's wrong with this CRC32 algorithm?

    Ok, so I have now gone and fixed it, so that it will now work for any conditions. For any input that is used, it will always work regardless of which parameters are set to true or false. It now always gives the output that is the same as the output that HxD hex editor's CRC32 gives, when set with the same parameters. I have tested it with different combinations of parameters, and set them the same in HxD, and the result now always match between my program and HxD.

    Here is the complete code of the working program, including the bit shifting, bit swapping, and byte swapping functions.
    Code:
    Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long)
    Private Const Poly As Long = &H4C11DB7
    
    
    
    Private Function CRC32(ByRef Data() As Byte, _
                           ByVal InvertInitCRC As Boolean, _
                           ByVal MirrorInputBits As Boolean, _
                           ByVal MirrorOutputBits As Boolean, _
                           ByVal InvertFinalCRC As Boolean) As Long
                           
                            
    Dim ByteNumber As Long
    Dim BitNumber As Long
    Dim CurrentByte As Long
    Dim CRC As Long
    
    If InvertInitCRC Then CRC = &HFFFFFFFF Else CRC = 0
    
    For ByteNumber = 0 To UBound(Data)
        CurrentByte = Data(ByteNumber)
        If MirrorInputBits Then CurrentByte = ReverseBits8(CurrentByte)
        CurrentByte = SwapBytes4(CurrentByte)
        CRC = CRC Xor CurrentByte
        For BitNumber = 0 To 7
            If CRC And &H80000000 Then
                CRC = ShiftLeft32(CRC) Xor Poly
            Else
                CRC = ShiftLeft32(CRC)
            End If
        Next BitNumber
    Next ByteNumber
    If MirrorOutputBits Then CRC = ReverseBits32(CRC)
    If InvertFinalCRC Then CRC = CRC Xor &HFFFFFFFF
    CRC32 = CRC
    End Function
    
    
    
    Private Function ShiftLeft32(ByVal Value As Long, Optional ByVal BitCount As Long = 1) As Long
    Dim temp As Currency
    Dim temp2 As Long
    
    CopyMemory temp, Value, 4
    temp = temp * (2 ^ BitCount)
    CopyMemory temp2, temp, 4
    ShiftLeft32 = temp2
    End Function
    
    
    
    Private Function ShiftRight32(ByVal Value As Long, Optional ByVal BitCount As Long = 1) As Long
    Dim temp As Currency
    Dim temp2 As Long
    
    CopyMemory temp, Value, 4
    temp = Int((temp * 10000) / (2 ^ BitCount)) / 10000
    CopyMemory temp2, temp, 4
    ShiftRight32 = temp2
    End Function
    
    
    
    Private Function ReverseBits32(ByVal Value As Long) As Long
    Dim Value2 As Long
    Dim n As Long
    
    Value2 = (Value And 1) * &H80000000
    For n = 1 To 31
        Value2 = Value2 + ShiftLeft32(ShiftRight32(Value, n) And 1, 31 - n)
    Next n
    ReverseBits32 = Value2
    End Function
    
    
    
    Private Function ReverseBits8(ByVal Value As Byte) As Byte
    Dim Value2 As Byte
    Dim n As Long
    
    Value2 = (Value And 1) * &H80
    For n = 1 To 7
        Value2 = Value2 + ShiftLeft32(ShiftRight32(Value, n) And 1, 7 - n)
    Next n
    ReverseBits8 = Value2
    End Function
    
    
    
    Private Function SwapBytes4(ByVal Value As Long) As Long
    Dim Value2 As Long
    
    CopyMemory ByVal VarPtr(Value2) + 0, ByVal VarPtr(Value) + 3, 1
    CopyMemory ByVal VarPtr(Value2) + 1, ByVal VarPtr(Value) + 2, 1
    CopyMemory ByVal VarPtr(Value2) + 2, ByVal VarPtr(Value) + 1, 1
    CopyMemory ByVal VarPtr(Value2) + 3, ByVal VarPtr(Value) + 0, 1
    SwapBytes4 = Value2
    End Function
    
    
    
    Private Sub Command1_Click()
    Dim Data() As Byte
    
    Data() = StrConv("This is a test.", vbFromUnicode)
    Print Hex$(CRC32(Data, True, True, True, True))
    End Sub
    Last edited by Ben321; Jun 11th, 2015 at 06:35 PM. Reason: cleaned up the code a bit

  5. #5

    Thread Starter
    Frenzied Member
    Join Date
    Oct 2008
    Posts
    1,181

    Re: What's wrong with this CRC32 algorithm?

    Finally finished up this project, fixed all the errors, and even added CRC16 functionality. It has been thoroughly checked against other software that calculates these CRCs, and I have found that there are no further problems. The complete code along with a description of how to use it is now in the CodeBank in this thread http://www.vbforums.com/showthread.p...045-modCRC-bas

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width