Както обикновено, за да се изчисли циклична контролна сума (crc32 - crc16 - СгС8), omj

В интернет има много възможности за изчисляване на контролна сума CRC. Но какво всъщност е контролна и защо тя се изчислява по този начин? Нека да разследват.

1
Първо, нека да разберете малко теория. Така че, това, което е на КРС? С една дума, това е една от разновидностите на изчисляване на контролната сума. Контролната сума - метод за проверка на целостта на информацията, получена от страната приемник на предаването чрез комуникационни канали. Например, един от най-простите тестове - използване на паритетен малко. Това, когато се добавят всички битове на изпратеното съобщение, а ако сумата е дори, а след това се добавя към съобщението 0, ако странно - 1. Когато на рецепцията, се изчислява като сбор от бита съобщения и се сравнява с полученото паритет малко. Ако те са различни, тогава да се появят грешки при предаване и предаваната информация е изкривено.

Но този метод за определяне наличието на грешки - много uninformative и не винаги работи, защото изкривяването от малкото публикации бита, паритет сумата не може да бъде променена. Поради това, че има много повече "напреднали" тестове, включително и КРС.

В действителност, КРС - това не е в размер, както и в резултат на разделяне на определено количество информация (съобщение данни) до постоянно - или по-скоро, а останалата част от участък мнения на постоянни. Въпреки това, КРС исторически наричан също "контролна". Стойността на КРС допринася всяка частица от съобщението. Това е, ако поне един бит на оригиналното съобщение се е променило в транзит, шах също ще се промени, като значително. Това е един голям плюс на този тест, тъй като тя дава възможност за уникална идентификация изкривен оригиналното съобщение, когато изпращате или не.

2
Преди да се пристъпи към изчисляване на КРС, ще трябва малко повече теория.
Какво е оригиналното съобщение трябва да е ясно. Това е един непрекъснат поредица от битове за произволна дължина.

Що за постоянно, което ние трябва да се разделят на оригиналното съобщение? Също така е много всякаква дължина, но обикновено се използват кратни на 1 байт - 8, 16 и 32 бита. Просто така е по-лесно да се повярва, защото компютрите да работят с байта, а не с бита.

Постоянното-делител обикновено се изписва като полином (полином) така: х ^ 8 + х ^ 2 + х ^ 1 + х ^ 0. Тук, степента на "х" е позицията на битови единици на брой, като се започне с нула, а MSB показва степента на полинома се изхвърля и тълкуването на числото. Това означава, че вече сте записали номера - това е нищо повече от една (1) 00000111 в двойна система за означаване или десетична 7. В скоби, съм мълчалив MSB номер.
Ето един пример: х ^ 16 + х ^ 15 + х ^ 2 + х ^ = 0 (1) 1000000000000101 "= 0x8005 = 32773.
определени стандартни полиноми обикновено се използват за различни видове КРС.

3
Е, как да помисли за шах? Налице е основен метод - разделението на съобщения от полином "в челото" - и нейното изменение, за да се намали количеството на изчисление и по този начин ускорява изчисляването КРС. Ние го основен метод разгледа.

В общи линии, разделението на полином се извършва на такъв алгоритъм:
1) създава масив (регистър) запълва с нули, равни на битовата дължина на полинома;
2) оригиналната публикация е подплатени с нули в долните битове, в количество, равно на броя на битовете на полинома;
3) в ниския регистър е вписано една цифра MSB съобщенията, и се простира от по-старите ни най-малко етап регистър;
4) когато удължен бит е "1", малко инверсия се провежда (операция XOR, XOR) на битовете в регистрите, които съответстват на единици в полином;
5) ако съобщението има повече битове, преминете към стъпка 3);
6), когато са получили всички битове за съобщения в случая и са били обработени от този алгоритъм, регистърът остава остатък от разделението, което е циклична контролна сума.

Фигурата илюстрира разделянето на оригиналната последователност от битове на броя (1) 00000111, или полином х ^ 8 + х ^ 2 + х ^ 1 + х ^ 0.

4
Аз останах няколко допълнителни щрихи. Както можете да видите, съобщението може да се раздели на произволен брой. Как да го изберем? Има редица стандартни полиноми, които се използват при изчисляването на КРС. Например, CRC32 за това може да бъде номер 0x04C11DB7, и за това може да бъде CRC16 0x8005.
Освен това, в случая в началото на изчисленията може да се запише не нулева, но някой друг номер.

Също така в изчисленията непосредствено преди издаването на окончателния CRC контролна могат да бъдат разделени в някакъв друг номер.

И за последен. Съобщението байта за записване в регистъра може да се постави като най-значимия бит "напред", и обратно, младши.

5
Въз основа на изложеното по-горе, нека да напише функция на езика на Basic .NET, която ще се изчисли контролната сума на КРС, като редица параметри, които описах по-горе, и връщане на стойността на КРС като 32-битови неподписани номера.

Публична Споделено Функция GetCrc (ByVal байта Както Байт (), ByVal поли Както UInteger, незадължително ByVal ширина Като цяло число = 32, по избор ByVal initReg Както UInteger = HFFFFFFFFUI, незадължително ByVal finalXor Както UInteger = HFFFFFFFFUI, Допълнителни ByVal reverseBytes Както Булева = Вярно е, незадължително ByVal reverseCrc Както Булева = True) Както UInteger

Дим widthInBytes Като цяло число = ширина 8

"Завършването на съобщението ширина нули (изчисление в байтове):
ReDim Боатин байта (bytes.Length - 1 + widthInBytes)

"Създаване на всички битове на съобщението:
Дим msgFifo Както New опашка (на булевата) (bytes.Count * 8-1)
За Всеки б Както Байт В байта
Дим ба Както New BitArray ()
Ако reverseBytes Тогава
Защото Като цяло число = 0 до 7
msgFifo.Enqueue (ба (I))
до
още
Защото Като цяло число = 7 Към 0 Стъпка -1
msgFifo.Enqueue (ба (I))
до
Крайна сметка, ако
до

"Създаване на всички части от първоначалната пълнене на регистъра:
Дим initBytes Както Байт () = BitConverter.GetBytes (initReg)
Дим initBytesReversed Както IEnumerable (От Byte) = (От б Както Байт В initBytes Вземете widthInBytes) .Reverse
Дим initFifo Както New опашка (на булевата) (широчина - 1)
За Всеки б Както Байт В initBytesReversed
Дим ба Както New BitArray ()
Ако не се reverseBytes Тогава
Защото Като цяло число = 0 до 7
initFifo.Enqueue (ба (I))
до
още
Защото Като цяло число = 7 Към 0 Стъпка -1
initFifo.Enqueue (ба (I))
до
Крайна сметка, ако
до

"Shift и XOR:
Дим се регистрирате като UInteger = 0 "запълни регистър ширина-малко с нули.
Смятате Докато msgFifo.Count> 0

Дим poppedBit Като цяло число = CInt (регистър >> (ширина - 1)) и 1 ", за да се определи регистър смяна.

Дим shiftedBit Както Байт = Convert.ToByte (msgFifo.Dequeue)
Ако initFifo.Count> 0 След
Дим б Както Байт = Convert.ToByte (initFifo.Dequeue)
shiftedBit = shiftedBit XOR б
Крайна сметка, ако

регистрирате = регистрирате <<1
Регистър = регистрирате или shiftedBit

Ако poppedBit = 1 Тогава
регистрирате = регистрирате XOR поли
Крайна сметка, ако
контур

"Крайно преобразуване:
Дим CRC Както UInteger = регистрирате "регистър съдържа остатъка от делене == контролна сума.
Ако reverseCrc Тогава
CRC = отразява (CRC, ширина)
Крайна сметка, ако
CRC = CRC XOR finalXor
КРС = КРС и се (HFFFFFFFFUI >> (32 - ширина)) "маскира младши битове.

здравословни съвети
Предложената програма е лошо мащабируемост. Това означава, че тя работи добре при изчисляване на контролната сума CRC за кратки съобщения до няколко десетки килобайта. При изчисляване на КРС за дълго съобщение, размерът на десетки или стотици мегабайта, програмата ще претовари процесора и паметта, както цялото съобщение се зарежда в масива. За да работите с такива големи съобщения трябва да се прилагат междинен буфер, което ще изпрати съобщение на програмата на малки порции.
източник