Results 1 to 4 of 4

Thread: Can somebody debug my CRC code here?

  1. #1

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

    Can somebody debug my CRC code here?

    I'm trying to write a CRC16 calculator, in albeit not the most efficient way, in a way that is a literal software implementation of how it would be implemented in hardware (the shift register and all of that). And it actually works, so long as the initial shift register bits are all zeros (initval=0x0000). However, it fails to work under any non-zero value for the initial shift register value. Even an initval of 0xFFFF which has absolutely no bit order dependency, still doesn't work.

    For example, it works when I try to implement CRC-16/XMODEM (poly=0x1021, initval=0x0000, output_xor=0x0000, and no input or output bit order reversal).
    However, it doesn't work when I try to implement CRC-16/CCITT-FALSE (poly=0x1021, initval=0xFFFF, output_xor=0x0000, and no input or output bit order reversal).

    Literally the ONLY thing different between CRC-16/XMODEM and CRC-16/CCITT-FALSE is that CRC-16/CCITT-FALSE has an initial shift register value of 0xFFFF instead of 0x0000. I can verify the output of my software by using known input, and looking for the expected output. The ascii text string "123456789" is the commonly used test input, and CRC-16/XMODEM should give an output of 0x31C3, while CRC-16/CCITT-FALSE should give an output of 0x29B1. However, there's one big problem. When I use the technique I've been using for implementing 16bit CRCs, my version of CRC-16/CCITT-FALSE does NOT output 0x29B1 for the test input (proving that something is wrong somewhere), even though my version of CRC-16/XMODEM DOES output 0x31C3 (as it should) for the test input.

    Here's my code below, that is in Module1 in my VB6 program. I've annotated it so you can see what each part of the code is supposed to do. Please tell me what part of this code is wrong.
    Code:
    'This module generically calculates almost any 16bit CRC (so long as it doesn't require swapping the bit order)
    
    Dim ShiftRegister() As Byte
    Dim Poly() As Byte
    
    'This function puts an initial value into the shift register, which isn't always 0x0000, depending on the CRC you are implementing
    Public Sub LoadSR(ByVal Value As Integer)
        'Convert the signed Integer into an unsigned Integer (or more accurately into a signed Long)
        IntToBits Value And &HFFFF&, ShiftRegister()
    End Sub
    
    
    'This funciton sets the polynomial for the CRC
    Public Sub SetPoly(ByVal Value As Integer)
        'Convert the signed Integer into an unsigned Integer (or more accurately into a signed Long)
        IntToBits Value And &HFFFF&, Poly()
    End Sub
    
    Public Function CalculateCRC(ByRef Bytes() As Byte) As Integer
        Dim ByteCount As Long
        Dim BitCount As Long
        Dim CRC As Long
        Dim n As Long
        Dim i As Long
        Dim Bits() As Byte
        Dim OBit As Byte
        
        'Get the number of bytes of input data and setup the bits array
        ByteCount = UBound(Bytes) + 1
        BitCount = ByteCount * 8
        ReDim Bits(BitCount - 1)
        
        'Populate the bits array by spliting the bytes into bits
        For n = 0 To ByteCount - 1
            Bits(n * 8 + 0) = (Bytes(n) \ &H80) And 1
            Bits(n * 8 + 1) = (Bytes(n) \ &H40) And 1
            Bits(n * 8 + 2) = (Bytes(n) \ &H20) And 1
            Bits(n * 8 + 3) = (Bytes(n) \ &H10) And 1
            Bits(n * 8 + 4) = (Bytes(n) \ &H8) And 1
            Bits(n * 8 + 5) = (Bytes(n) \ &H4) And 1
            Bits(n * 8 + 6) = (Bytes(n) \ &H2) And 1
            Bits(n * 8 + 7) = (Bytes(n) \ &H1) And 1
        Next n
        
        'Calculate CRC from data
        For n = 0 To BitCount - 1
            OBit = ShiftRegister(0)
            For i = 0 To 14
                ShiftRegister(i) = ShiftRegister(i + 1)
            Next i
            ShiftRegister(15) = Bits(n)
            If OBit = 1 Then
                For i = 0 To 15
                    ShiftRegister(i) = ShiftRegister(i) Xor Poly(i)
                Next i
            End If
        Next n
        
        'Flush CRC bits and perform final calculations
        For n = 0 To 15
            OBit = ShiftRegister(0)
            For i = 0 To 14
                ShiftRegister(i) = ShiftRegister(i + 1)
            Next i
            ShiftRegister(15) = 0
            If OBit = 1 Then
                For i = 0 To 15
                    ShiftRegister(i) = ShiftRegister(i) Xor Poly(i)
                Next i
            End If
        Next n
        
        'Combine the bits of the shift register into the CRC variable
        For i = 0 To 15
            CRC = CRC + ShiftRegister(i) * 2 ^ (15 - i)
        Next i
        
        'Convert the unsigned integer into a signed integer and output it (vb6 doesn't support true unsigned Integers, so up till now it was using a signed Long)
        CalculateCRC = (CRC And &H7FFF&) - (CRC And &H8000&)
        
    End Function
    
    
    
    Private Sub IntToBits(ByVal Value As Long, ByRef ArrayOut() As Byte)
        Dim n As Long
        ReDim ArrayOut(15)
        For n = 0 To 15
            ArrayOut(n) = (Value \ (2 ^ (15 - n))) And 1
        Next n
    End Sub

    Here's the code in my form that calls the functions in the module, and prints the result to the form. Here it's initializing the shift register for CRC-16/XMODEM
    Code:
    Private Sub Form_Load()
        Dim Bytes() As Byte
    
        Bytes() = StrConv("123456789", vbFromUnicode)
        
        LoadSR 0
        SetPoly &H1021
        
        Print Hex$(CalculateCRC(Bytes))
    End Sub
    Here's the form code again, but this time it's initializing the shift register for CRC-16/CCITT-FALSE
    Code:
    Private Sub Form_Load()
        Dim Bytes() As Byte
    
        Bytes() = StrConv("123456789", vbFromUnicode)
        
        LoadSR &HFFFF
        SetPoly &H1021
        
        Print Hex$(CalculateCRC(Bytes))
    End Sub
    Last edited by Ben321; Nov 14th, 2021 at 06:33 AM.

  2. #2

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

    Re: Can somebody debug my CRC code here?

    Ok so it seems I misunderstood how the initial value (from here in referred to as InitVal) of a CRC works. I assumed InitVal was supposed to be loaded into the shift register prior to clocking any data bits into the shift register, so that the CRC would run calculations over the bits of InitVal before running the calculations over the data bits. This was based on what I thought I remember reading in actual technical literature on the workings of CRCs. However, this consistently gave me the different results when compared to known CRC implementations. So I eventually tried something I didn't expect to work, but was more of a last ditch effort to fix my algorithm, and that something was to load no initial bits into the actual shift register (leaving it all zeros), but rather XOR InitVal into the first 16bits of data, and then after that run the CRC calculations over this new data (same as old data except for the first 16 bits). And this fixed it. I don't know why it fixed it, but it did. If anybody can explain why this fix works, please reply.

    Here's the code for my new generic 16bit CRC calculation module. in addition to input XOR, it also now implements output XOR and reflecting input bits, and reflecting output bits. This code allows you to implement ANY 16bit CRC now.

    Code:
    'This module generically calculates any 16bit CRC
    
    Dim ShiftRegister() As Byte
    Dim Poly() As Byte
    Dim InitXOR() As Byte
    Dim FinalXOR() As Byte
    Public ReflectInputBits As Boolean
    Public ReflectOutputBits As Boolean
    
    'This function sets the initial XOR value
    Public Sub SetInitXOR(ByVal Value As Integer)
        
        'Convert the signed Integer into an unsigned Integer (or more accurately into a signed Long)
        IntToBits Value And &HFFFF&, InitXOR()
    End Sub
    
    'This function sets the final XOR value
    Public Sub SetFinalXOR(ByVal Value As Integer)
        IntToBits Value And &HFFFF&, FinalXOR()
    End Sub
    
    'This funciton sets the polynomial for the CRC
    Public Sub SetPoly(ByVal Value As Integer)
        'Convert the signed Integer into an unsigned Integer (or more accurately into a signed Long)
        IntToBits Value And &HFFFF&, Poly()
    End Sub
    
    Public Function CalculateCRC(ByRef Bytes() As Byte) As Integer
        Dim ByteCount As Long
        Dim BitCount As Long
        Dim CRC As Long
        Dim n As Long
        Dim i As Long
        Dim Bits() As Byte
        Dim OBit As Byte
        
        ReDim ShiftRegister(15)
        
        'Get the number of bytes of input data and setup the bits array
        ByteCount = UBound(Bytes) + 1
        BitCount = ByteCount * 8
        ReDim Bits(BitCount - 1)
        
        'Populate the bits array by spliting the bytes into bits
        If ReflectInputBits = False Then
            For n = 0 To ByteCount - 1
                Bits(n * 8 + 0) = (Bytes(n) \ &H80) And 1
                Bits(n * 8 + 1) = (Bytes(n) \ &H40) And 1
                Bits(n * 8 + 2) = (Bytes(n) \ &H20) And 1
                Bits(n * 8 + 3) = (Bytes(n) \ &H10) And 1
                Bits(n * 8 + 4) = (Bytes(n) \ &H8) And 1
                Bits(n * 8 + 5) = (Bytes(n) \ &H4) And 1
                Bits(n * 8 + 6) = (Bytes(n) \ &H2) And 1
                Bits(n * 8 + 7) = (Bytes(n) \ &H1) And 1
            Next n
        Else
            For n = 0 To ByteCount - 1
                Bits(n * 8 + 0) = (Bytes(n) \ &H1) And 1
                Bits(n * 8 + 1) = (Bytes(n) \ &H2) And 1
                Bits(n * 8 + 2) = (Bytes(n) \ &H4) And 1
                Bits(n * 8 + 3) = (Bytes(n) \ &H8) And 1
                Bits(n * 8 + 4) = (Bytes(n) \ &H10) And 1
                Bits(n * 8 + 5) = (Bytes(n) \ &H20) And 1
                Bits(n * 8 + 6) = (Bytes(n) \ &H40) And 1
                Bits(n * 8 + 7) = (Bytes(n) \ &H80) And 1
            Next n
        End If
        
        'Perform init xor
        For i = 0 To 15
            Bits(i) = Bits(i) Xor InitXOR(i)
        Next i
    
        'Calculate CRC from data
        For n = 0 To BitCount - 1
            OBit = ShiftRegister(0)
            For i = 0 To 14
                ShiftRegister(i) = ShiftRegister(i + 1)
            Next i
            ShiftRegister(15) = Bits(n)
            If OBit = 1 Then
                For i = 0 To 15
                    ShiftRegister(i) = ShiftRegister(i) Xor Poly(i)
                Next i
            End If
        Next n
        
        'Flush CRC bits and perform final calculations
        For n = 0 To 15
            OBit = ShiftRegister(0)
            For i = 0 To 14
                ShiftRegister(i) = ShiftRegister(i + 1)
            Next i
            ShiftRegister(15) = 0
            If OBit = 1 Then
                For i = 0 To 15
                    ShiftRegister(i) = ShiftRegister(i) Xor Poly(i)
                Next i
            End If
        Next n
        
        'Perform final xor
        If ReflectInputBits = False Then
            For i = 0 To 15
                ShiftRegister(i) = ShiftRegister(i) Xor FinalXOR(i)
            Next i
        Else
            For i = 0 To 15
                ShiftRegister(i) = ShiftRegister(i) Xor FinalXOR(15 - i)
            Next i
        End If
        
        
        
        'Combine the bits of the shift register into the CRC variable
        If ReflectOutputBits = False Then
            For i = 0 To 15
                CRC = CRC + ShiftRegister(i) * 2 ^ (15 - i)
            Next i
        Else
            For i = 0 To 15
                CRC = CRC + ShiftRegister(i) * 2 ^ i
            Next i
        End If
        
        'Convert the unsigned integer into a signed integer and output it (vb6 doesn't support true unsigned Integers, so up till now it was using a signed Long)
        CalculateCRC = (CRC And &H7FFF&) - (CRC And &H8000&)
        
    End Function
    
    
    
    Private Sub IntToBits(ByVal Value As Long, ByRef ArrayOut() As Byte)
        Dim n As Long
        ReDim ArrayOut(15)
        For n = 0 To 15
            ArrayOut(n) = (Value \ (2 ^ (15 - n))) And 1
        Next n
    End Sub

  3. #3
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,120

    Re: Can somebody debug my CRC code here?

    Quote Originally Posted by Ben321 View Post
    This code allows you to implement ANY 16bit CRC now.
    I think adding bitness to the implementation would allow implementing ANY 8-bit, 16-bit or 32-bit CRC and would be awesome.

    Just probably make a single entry-point wrapper function with everything (init/final/poly values, bitness and reflection) as parameters to this function and final result returned in retval.

    A second function like the wrapper above but which accepts current CRC value would allow calculating the redundancy code in chunks e.g. while receiving piecemeal data from a TCP socket or uncompressing a file from disk in blocks of 4KB.

    cheers,
    </wqw>

  4. #4

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

    Re: Can somebody debug my CRC code here?

    Quote Originally Posted by wqweto View Post
    I think adding bitness to the implementation would allow implementing ANY 8-bit, 16-bit or 32-bit CRC and would be awesome.

    Just probably make a single entry-point wrapper function with everything (init/final/poly values, bitness and reflection) as parameters to this function and final result returned in retval.

    A second function like the wrapper above but which accepts current CRC value would allow calculating the redundancy code in chunks e.g. while receiving piecemeal data from a TCP socket or uncompressing a file from disk in blocks of 4KB.

    cheers,
    </wqw>
    The problem with that last idea, is that doing the initial XOR must be performed only during the first iteration, while the finalizing steps (flushing the bits after the last piece of data, mirroring the bit order of the output, and doing the final XOR on the output) must only be done on the last iteration. But my current code does all of the process in one step, making it only suitable to process data with a known size (not an open-ended data stream). I would need 3 functions otherwise (InitCRC, UpdateCRC, and FinalizeCRC).

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