Има много опции за изчисляване на контролната сума на CRC в Интернет. Но какво точно представлява контролна сума и защо се изчислява по този начин? Нека го разберем.
Инструкции
Етап 1
Първо, нека да вземем малко теория. И така, какво всъщност е CRC? Накратко, това е една от разновидностите на изчисляването на контролната сума. Контролната сума е метод за проверка на целостта на получената информация от страната на приемника при предаване по комуникационни канали. Например, една от най-простите проверки е използването на бита за паритет. Това е, когато всички битове на предаденото съобщение се сумират и ако сумата се окаже четна, тогава в края на съобщението се добавя 0, ако е нечетно, тогава 1. При получаване сумата от битовете за съобщения също се броят и сравняват с получения бит за четност. Ако те се различават, тогава по време на предаването са възникнали грешки и предадената информация е изкривена.
Но този метод за откриване на наличие на грешки е много неинформативен и не винаги работи, тъй като ако няколко бита на съобщението са изкривени, паритетът на сумата може да не се промени. Следователно има много по-разширени проверки, включително 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
Въз основа на всичко по-горе, нека напишем основна. NET функция, която изчислява контролната сума на CRC, като взема редица параметри, описани по-горе, и връща стойността на CRC като 32-битово неподписано число.
Публична споделена функция GetCrc (ByVal байта като байт (), ByVal поли като UInteger, незадължително ByVal ширина As Integer = 32, незадължително ByVal initReg As UInteger = & HFFFFFFFFUI, незадължително ByVal finalXor As UInteger = & HFFFFFFFFUI, Optional ByVal Optional ByVal reverseCrc As Boolean = True) Като UInteger
Затъмняване на ширинаInBytes като цяло число = ширина / 8
'Допълнете ширината на съобщението с нули (изчисление в байтове):
ReDim Запазване на байтове (байтове. Дължина - 1 + ширинаInBytes)
'Създайте битова опашка от съобщението:
Затъмнете msgFifo като нова опашка (от булева стойност) (байтове. Брой * 8 - 1)
За всеки b като байт в байтове
Dim ba като нов BitArray ({b})
Ако reverseBytes Тогава
За i като цяло число = 0 до 7
msgFifo. Enqueue (ba (i))
Следващия
Иначе
For i As Integer = 7 To 0 Стъпка -1
msgFifo. Enqueue (ba (i))
Следващия
Край ако
Следващия
'Създайте опашка от първоначалните битове за запълване на регистъра:
Затъмнява initBytes като байт () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (От b As Byte In initBytes Вземете widthInBytes).
Затъмнете initFifo като нова опашка (от булева) (ширина - 1)
За всеки b като байт в initBytesReversed
Dim ba като нов BitArray ({b})
Ако не обратните байтове тогава
За i като цяло число = 0 до 7
initFifo. Enqueue (ba (i))
Следващия
Иначе
For i As Integer = 7 To 0 Стъпка -1
initFifo. Enqueue (ba (i))
Следващия
Край ако
Следващия
'Shift и XOR:
Затъмнете регистъра като UInteger = 0 'запълнете битовия регистър с нули.
Направете докато msgFifo. Count> 0
Dim poppedBit As Integer = CInt (регистър >> (ширина - 1)) И 1 'дефинирайте преди регистъра на смяната.
Затъмнен shifiedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Ако initFifo. Count> 0 Тогава
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftHitBit Xor b
Край ако
регистър = регистър << 1
регистър = регистър или изместен бит
Ако poppedBit = 1 Тогава
регистър = регистър Xor поли
Край ако
Примка
„Окончателни преобразувания:
Dim crc As UInteger = register 'Регистърът съдържа остатъка от контролната сума на разделянето ==.
Ако reverseCrc Тогава
crc = отразява (crc, ширина)
Край ако
crc = crc Xor окончателенXor
crc = crc И (& HFFFFFFFFUI >> (32 - ширина)) 'маскира най-малко значимите битове.
Връщане crc
Крайна функция
