Инструкция
1
Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма - это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок - использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной - то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.
Но такой способ определения наличия ошибок - очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более "продвинутых" проверок, в том числе CRC.
По сути, CRC - это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее - остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют "контрольная сумма". В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.
Но такой способ определения наличия ошибок - очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более "продвинутых" проверок, в том числе CRC.
По сути, CRC - это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее - остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют "контрольная сумма". В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.
2
Прежде чем приступать к вычислению CRC, понадобится ещё немного теории.
Что такое исходное сообщение должно быть понятно. Это непрерывная последовательность битов произвольной длины.
Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту - 8, 16 и 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число - это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101" = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.
Что такое исходное сообщение должно быть понятно. Это непрерывная последовательность битов произвольной длины.
Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту - 8, 16 и 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.
Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x^8 + x^2 + x^1 + x^0. Здесь степень числа "x" означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число - это не что иное как (1)00000111 в двоичной системе счисления, или 7 в десятичной. В скобках я указал подразумеваемый старший разряд числа.
Вот ещё пример: x^16 + x^15 + x^2 + x^0 = (1)1000000000000101" = 0x8005 = 32773.
Обычно используются некие стандартные многочлены для разных типов CRC.
3
Так как же считать контрольную сумму? Существует базовый метод - деление сообщения на полином "в лоб" - и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Мы рассмотрим именно базовый метод.
В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен "1", то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.
В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен "1", то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.
4
Осталась ещё пара дополнительных штрихов. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.
И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом "вперёд", так и наоборот, младшим.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.
И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом "вперёд", так и наоборот, младшим.
5
На основании всего вышеизложенного, давайте напишем функцию на языке Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.
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 As Boolean = True, Optional ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width \ 8
'Дополняем сообщение width нулями (расчёт в байтах):
ReDim Preserve bytes(bytes.Length - 1 + widthInBytes)
'Создаём очередь битов из сообщения:
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
'Создаём очередь из битов начального заполнения регистра:
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
'Сдвиг и XOR:
Dim register As UInteger = 0 'заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0
Dim poppedBit As Integer = CInt(register >> (width - 1)) And 1 'определить перед сдвигом регистра.
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
'Финальные преобразования:
Dim crc As UInteger = register 'Регистр содержит остаток от деления == контрольную сумму.
If reverseCrc Then
crc = reflect(crc, width)
End If
crc = crc Xor finalXor
crc = crc And (&HFFFFFFFFUI >> (32 - width)) 'маскируем младшие разряды.
Return crc
End Function
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 As Boolean = True, Optional ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width \ 8
'Дополняем сообщение width нулями (расчёт в байтах):
ReDim Preserve bytes(bytes.Length - 1 + widthInBytes)
'Создаём очередь битов из сообщения:
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
'Создаём очередь из битов начального заполнения регистра:
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
'Сдвиг и XOR:
Dim register As UInteger = 0 'заполняем width-разрядный регистр нулями.
Do While msgFifo.Count > 0
Dim poppedBit As Integer = CInt(register >> (width - 1)) And 1 'определить перед сдвигом регистра.
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
'Финальные преобразования:
Dim crc As UInteger = register 'Регистр содержит остаток от деления == контрольную сумму.
If reverseCrc Then
crc = reflect(crc, width)
End If
crc = crc Xor finalXor
crc = crc And (&HFFFFFFFFUI >> (32 - width)) 'маскируем младшие разряды.
Return crc
End Function
Полезный совет
Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в массив. Для работы с такими большими сообщениями нужно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.
