-
Nov 14th, 2021, 06:29 AM
#1
Thread Starter
Frenzied Member
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.
-
Nov 14th, 2021, 06:49 PM
#2
Thread Starter
Frenzied Member
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
-
Nov 15th, 2021, 05:40 AM
#3
Re: Can somebody debug my CRC code here?
Originally Posted by Ben321
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>
Last edited by wqweto; Nov 15th, 2021 at 05:43 AM.
-
Nov 15th, 2021, 05:10 PM
#4
Thread Starter
Frenzied Member
Re: Can somebody debug my CRC code here?
Originally Posted by wqweto
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|