Як просто порахувати контрольну суму CRC (CRC32 - CRC16 - CRC8)

Як просто порахувати контрольну суму CRC (CRC32 - CRC16 - CRC8)


В інтернеті існує велика кількість варіантів розрахунку контрольної суми CRC. Але що ж власне таке контрольна сума і чому вона розраховується саме так? Давайте розбиратися.

Інструкція

1. Для початку давайте трохи розберемося в теорії. Отже, що ж таке CRC? Якщо коротко, це один з різновидів підрахунку контрольної суми. Контрольна сума - це метод перевірки цілісності прийнятої інформації на боці приймача при передачі по каналах зв 'язку. Наприклад, одна з найпростіших перевірок - використання біта чітності. Це якщо підсумовуються всі біти повідомлення, що передаються, і якщо сума виявляється чіткою, то в кінець повідомлення додається 0, якщо непарний - то 1. При прийомі також підраховується сума битів повідомлення, і порівнюється з прийнятим битом чітності. Якщо вони відрізняються, значить при передачі виникли помилки, і передана інформація була спотворена. Але такий спосіб визначення наявності помилок - дуже неінформативний і спрацьовує не завжди, оскільки при спотворенні декількох бітів повідомлення, чіткість суми може не змінитися. Тому існує безліч більш "" просунутих "перевірок, у тому числі 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.

3. То як же рахувати контрольну суму? Існує базовий метод - ділення повідомлення на поліном "" в лоб "- і його модифікації в цілях зменшення кількості обчислень і, відповідно, прискорення розрахунку CRC. Ми розглянемо саме базовий метод. Загалом, поділ числа на багаточлен виконується за таким алгоритмом: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 можуть ділити на якесь інше число. І останнє. Байти повідомлення під час запису в регістр можуть поміщатися як старшим битом "вперед", так і навпаки, молодшим.

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 reversebDim 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 (& HFFFFFFUI > > (32 - width)) ' Return crcEnd Function