Существуют различные варианты реализации CRC (Циклического Избыточного Кода), их просто огромное множество. Самым, пожалуй, популярным из них является CRC32 — и это число 32-х битное. С помощью него можно хешировать данные, и количество различных вариантов этих данных будет равно 2 32 , почти 4 миллиарда различных хешей.
Алгоритм расчета CRC состоит из 2 частей:
- Создается таблица размером 256, состоящая из 32 битных значений для каждого символа
- На основе входящего потока символов вычисляется конечное значение CRC
§ Инициализация таблицы символов
Для каждого символа создается собственный уникальный код в таблице. Сначала входящему значению присваивается код символа от 0 до 255 (байт).
- Если в младшем байте значения кода 1 (единица), то тогда сдвинуть код вправо и применить XOR 0xEDB88320
- Если же там 0, то просто сдвинуть вправо
- Повторить процедуру 8 раз (по количеству входящих битов в исходный байт)
- Присвоить в таблице полученное значение
Как легко догадаться, подобную таблицу необязательно генерировать каждый раз, потому что каждому коду символа всегда соответствует какое-то фиксированное значение, поэтому можно сгенерировать таблицу единожды и пользоваться ей далее для всех операции crc.
Контрольная сумма crc + modbus rtu
§ Расчет CRC
После успешного получения таблицы, теперь можно легко произвести расчет CRC32 для любой входящей строки. Это делается крайне элементарно:
- 1. Сначала инициализируется переменная CRC всеми единицами (битами)
- 2. Для каждого нового символа делается XOR с предыдущим значением переменной CRC, и берется только нижние 8 бит, из ранее сгенерированной таблицы выбирается необходимое значение
- 3. Делается XOR над полученным значением и сдвинутым на 8 бит вправо предыдущим значением CRC
- 4. Повторяется 2 и 3 до тех пор, пока все символы не будут обработаны
- 5. После обработки все биты в результате должны быть инвертированы
Все, получается итоговое значение CRC32. Все очень просто. Главное запомнить, как это работает.
§ Код на С++
Ниже приведен код из Википедии для расчета CRC32
unsigned int CRC32(unsigned char *buf, unsigned long len) < unsigned long crc_table[256], crc; for (int i = 0; i < 256; i++) < crc = i; for (int j = 0; j < 8; j++) crc = (crc >> 1) ^ (crc crc_table[i] = crc; >; crc = 0xFFFFFFFFUL; while (len—) crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) return crc ^ 0xFFFFFFFFUL; >
§ Таблица CRC32
Заранее вычисленные значения в таблице.
uint32_t lookup[256] = < 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D >;
§ Модуль для верилога
Табличное значение t для d .
57. CRC алгоритм (Урок 48. Теория)
module crc32table ( input [ 7:0] d, output [31:0] t ); assign t[0] = d[2]; assign t[1] = d[0]^d[3]; assign t[2] = d[0]^d[1]^d[4]; assign t[3] = d[1]^d[2]^d[5]; assign t[4] = d[0]^d[2]^d[3]^d[6]; assign t[5] = d[1]^d[3]^d[4]^d[7]; assign t[6] = d[4]^d[5]; assign t[7] = d[0]^d[5]^d[6]; assign t[8] = d[1]^d[6]^d[7]; assign t[9] = d[7]; assign t[10] = d[2]; assign t[11] = d[3]; assign t[12] = d[0]^d[4]; assign t[13] = d[0]^d[1]^d[5]; assign t[14] = d[1]^d[2]^d[6]; assign t[15] = d[2]^d[3]^d[7]; assign t[16] = d[0]^d[2]^d[3]^d[4]; assign t[17] = d[0]^d[1]^d[3]^d[4]^d[5]; assign t[18] = d[0]^d[1]^d[2]^d[4]^d[5]^d[6]; assign t[19] = d[1]^d[2]^d[3]^d[5]^d[6]^d[7]; assign t[20] = d[3]^d[4]^d[6]^d[7]; assign t[21] = d[2]^d[4]^d[5]^d[7]; assign t[22] = d[2]^d[3]^d[5]^d[6]; assign t[23] = d[3]^d[4]^d[6]^d[7]; assign t[24] = d[0]^d[2]^d[4]^d[5]^d[7]; assign t[25] = d[0]^d[1]^d[2]^d[3]^d[5]^d[6]; assign t[26] = d[0]^d[1]^d[2]^d[3]^d[4]^d[6]^d[7]; assign t[27] = d[1]^d[3]^d[4]^d[5]^d[7]; assign t[28] = d[0]^d[4]^d[5]^d[6]; assign t[29] = d[0]^d[1]^d[5]^d[6]^d[7]; assign t[30] = d[0]^d[1]^d[6]^d[7]; assign t[31] = d[1]^d[7]; endmodule
Источник: www.neurofox.ru
AS-CRC32
AS-CRC32 — это программа, предназначенная для проверки целостности файла. Она рассчитывает значение CRC32 выбранного файла и позволяет сравнить его с оригинальным значением, давая тем самым возможность убедиться, что файл не был поврежден или изменен. Полученное значение также можно сохранить в специальный файл.
Кроме этого, AS-CRC32 может рассчитать значение CRC32 для любого текста и сравнить его с оригинальным значением, если таковое имеется. Утилита также имеет опцию, которая позволяет ей встроиться в Проводник, добавив новую команду для расчета CRC32 в контекстное меню.
Скачайте AS-CRC32 с freeSOFT.ru: это бесплатно, безопасно и быстро.
Источник: freesoft.ru
Как просто посчитать контрольную сумму CRC (CRC32 — CRC16 — CRC8)
В интернете существует большое количество вариантов расчёта контрольной суммы CRC. Но что же собственно такое контрольная сумма и почему она рассчитывается именно так? Давайте разбираться.
Статьи по теме:
- Как просто посчитать контрольную сумму CRC (CRC32 — CRC16 — CRC8)
- Как считать сумму
- Как исправить ошибку данных crc в 2017 году
Инструкция
Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма — это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок — использование бита чётности.
Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной — то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.
Но такой способ определения наличия ошибок — очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.
По сути, CRC — это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее — остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.
Прежде чем приступать к вычислению 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.
Так как же считать контрольную сумму? Существует базовый метод — деление сообщения на полином «в лоб» — и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Мы рассмотрим именно базовый метод.
В общем виде, деление числа на многочлен выполняется по такому алгоритму:
1) создаётся массив (регистр), заполненный нулями, равный по длине разрядности полинома;
2) исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома;
3) в младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит;
4) если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме;
5) если в сообщении ещё есть биты, переходим к шагу 3);
6) когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.
Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x^8 + x^2 + x^1 + x^0.
Осталась ещё пара дополнительных штрихов. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.
Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число.
Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC могут делить на какое-то другое число.
И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим.
На основании всего вышеизложенного, давайте напишем функцию на языке 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 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()
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()
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 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 (> (32 — width)) ‘маскируем младшие разряды.
Источник: www.kakprosto.ru