There are many options for calculating the CRC checksum on the Internet. But what exactly is a checksum and why is it calculated in this way? Let's figure it out.
Instructions
Step 1
Let's start with a little theory. So what exactly is CRC? In short, this is one of the varieties of checksum calculation. Checksum is a method of checking the integrity of the received information on the receiver side when transmitting over communication channels. For example, one of the simplest checks is to use the parity bit. This is when all the bits of the transmitted message are summed up, and if the sum turns out to be even, then 0 is added to the end of the message, if it is odd, then 1. When receiving, the sum of the message bits is also counted and compared with the received parity bit. If they differ, then errors occurred during transmission and the transmitted information was distorted.
But this method of detecting the presence of errors is very uninformative and does not always work, because if several bits of the message are distorted, the parity of the sum may not change. Therefore, there are many more "advanced" checks, including CRC.
In fact, CRC is not a sum, but the result of dividing a certain amount of information (informational message) by a constant, or rather, the remainder of dividing a message by a constant. However, the CRC is also historically referred to as a "checksum". Each bit of the message contributes to the CRC value. That is, if at least one bit of the original message changes during transmission, the checksum will also change, and significantly. This is a big plus of such a check, since it allows you to unambiguously determine whether the original message was distorted during transmission or not.
Step 2
Before we start calculating the CRC, a little more theory is needed.
What is the original message should be clear. It is a contiguous sequence of bits of arbitrary length.
What is the constant by which we should divide the original message? This number is also of any length, but usually multiples of 1 byte are used - 8, 16 and 32 bits. It's just easier to count, because computers work with bytes, not with bits.
The divisor constant is usually written as a polynomial (polynomial) like this: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Here, the power of the number "x" means the position of the one-bit in the number, starting from zero, and the most significant bit indicates the degree of the polynomial and is discarded when interpreting the number. That is, the previously written number is nothing more than (1) 00000111 in binary, or 7 in decimal. In parentheses, I have indicated the implied most significant digit of the number.
Here's another example: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Usually some standard polynomials are used for different types of CRCs.
Step 3
So how do you calculate the checksum? There is a basic method - dividing a message into a polynomial "head-on" - and its modifications in order to reduce the number of calculations and, accordingly, speed up the CRC calculation. We will look at the basic method.
In general, the division of a number by a polynomial is performed according to the following algorithm:
1) an array (register) is created, filled with zeros, equal in length to the length of the length of the polynomial;
2) the original message is supplemented with zeros in the least significant bits, in an amount equal to the number of bits of the polynomial;
3) one most significant bit of the message is entered into the least significant bit of the register, and one bit is moved from the most significant bit of the register;
4) if the extended bit is equal to "1", then the bits are inverted (XOR operation, exclusive OR) in those register bits that correspond to the ones in the polynomial;
5) if there are still bits in the message, go to step 3);
6) when all the bits of the message entered the register and were processed by this algorithm, the remainder of the division remains in the register, which is the CRC checksum.
The figure illustrates the division of the original bit sequence by the number (1) 00000111, or the polynomial x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Step 4
There are a couple of additional touches left. As you may have noticed, the message can be divided by any number. How to choose it? There are a number of standard polynomials that are used to calculate the CRC. For example, for CRC32 it might be 0x04C11DB7, and for CRC16 it might be 0x8005.
In addition, in the register at the beginning of the calculation, you can write not zeros, but some other number.
Also, during calculations, immediately before issuing the final CRC checksum, they can be divided by some other number.
And the last thing. When writing to the register, the message bytes can be placed as the most significant bit "forward", and vice versa, the least significant one.
Step 5
Based on all of the above, let's write a Basic. NET function that calculates the CRC checksum by taking a number of parameters that I described above and returning the CRC value as a 32-bit unsigned number.
Public Shared Function GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFFUI, Optional ByVal reverseBytes, Optional Boolean ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Supplement the message width with zeros (calculation in bytes):
ReDim Preserve bytes (bytes. Length - 1 + widthInBytes)
'Create a bit queue from the message:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
For Each b As Byte In bytes
Dim ba As New BitArray ({b})
If reverseBytes Then
For i As Integer = 0 To 7
msgFifo. Enqueue (ba (i))
Next
Else
For i As Integer = 7 To 0 Step -1
msgFifo. Enqueue (ba (i))
Next
End If
Next
'Create a queue from the bits of the initial filling of the register:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo As New Queue (Of Boolean) (width - 1)
For Each b As Byte In initBytesReversed
Dim ba As New BitArray ({b})
If Not reverseBytes Then
For i As Integer = 0 To 7
initFifo. Enqueue (ba (i))
Next
Else
For i As Integer = 7 To 0 Step -1
initFifo. Enqueue (ba (i))
Next
End If
Next
'Shift and XOR:
Dim register As UInteger = 0 'fill the width-bit register with zeros.
Do While msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) And 1 'define before shift register.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
If initFifo. Count> 0 Then
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
End If
register = register << 1
register = register Or shiftedBit
If poppedBit = 1 Then
register = register Xor poly
End If
Loop
'Final conversions:
Dim crc As UInteger = register 'The register contains the remainder of the division == checksum.
If reverseCrc Then
crc = reflect (crc, width)
End If
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - width)) 'mask the least significant bits.
Return crc
End Function
