Интернетте CRC контролдук суммасын эсептөөнүн көптөгөн жолдору бар. Бирок текшерүү суммасы деген эмне жана ал эмне үчүн ушундай жол менен эсептелет? Келгиле, аны аныктайлы.
Нускамалар
1 кадам
Алгач, бир аз теория алалы. Ошентип, CRC деген эмне? Кыскача айтканда, бул сумманы эсептөө түрлөрүнүн бири. Чек суммасы - байланыш каналдары аркылуу берүүдө кабыл алуучу тарапта алынган маалыматтын бүтүндүгүн текшерүү ыкмасы. Мисалы, эң жөнөкөй текшерүүлөрдүн бири - паритеттин битин колдонуу. Бул учурда берилген билдирүүнүн бардык биттери жыйынтыкталып, эгер сумма жуп болуп чыкса, анда билдирүүнүн аягына 0, ал так болсо, анда 1 кошулат, ошондо 1. Алууда, кошуунун суммасы билдирүү биттери да эсептелет жана алынган паритеттин битине салыштырылат. Эгерде алар айырмаланып турушса, анда берүүдө каталар пайда болуп, берилген маалыматтар бурмаланган.
Бирок каталардын бар экендигин аныктоонун бул ыкмасы өтө маалыматсыз жана ар дайым эле иштей бербейт, анткени эгер билдирүүнүн бир нече биттери бурмаланса, сумманын паритети өзгөрүлбөйт. Демек, CRC менен кошо дагы көптөгөн "өнүккөн" текшерүүлөр бар.
Чындыгында, CRC бул сумма эмес, бирок белгилүү бир көлөмдөгү маалыматты (маалыматтык билдирүүнү) туруктуу менен бөлүштүрүүнүн натыйжасы, тагыраак айтканда, билдирүүнү туруктуу менен бөлүштүрүүнүн калдыгы. Бирок, CRC тарыхый жактан "чек суммасы" деп да аталып калган. Билдирүүнүн ар бир бөлүгү CRC маанисине өбөлгө түзөт. Башкача айтканда, эгерде жөнөтүү учурунда баштапкы билдирүүнүн жок дегенде бир бөлүгү өзгөрүлсө, анда текшерүү суммасы да өзгөрөт жана бир кыйла. Бул мындай текшерүүнүн чоң плюсу, анткени ал билдирүүнүн түпнускасын берүү учурунда бурмаланган-бузулбагандыгын бир жактуу аныктоого мүмкүндүк берет.
2-кадам
CRC эсептөөнү баштаардан мурун дагы бир аз теория керек.
Түпнуска билдирүү эмне экени айкын болушу керек. Бул ыктыярдуу узундуктагы биттердин чектеш ырааттуулугу.
Баштапкы билдирүүнү кандай туруктуу түрдө бөлүштүрүшүбүз керек? Бул сан ошондой эле каалаган узундукта болот, бирок, адатта, 1 байттын эселери колдонулат - 8, 16 жана 32 бит. Жөн гана эсептөө оңой, анткени компьютер биттер менен эмес, байттар менен иштейт.
Бөлүүчүнүн константасы, адатта, мындай полином (полином) катары жазылат: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Бул жерде "х" санынын даражасы бир биттин нөлдөгү баштап турган ордун билдирет, ал эми эң маанилүү бит көп мүчөнүн даражасын көрсөтүп, санды чечмелеп жатканда алынып салынат. Башкача айтканда, мурун жазылган сан бинардык түрдө (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-кадам
Жогоруда айтылгандардын негизинде, жогоруда мен сүрөттөгөн бир катар параметрлерди алып, CRC маанисин 32-биттик белгисиз сан катары кайтарып, CRC контролдук суммасын эсептеген Basic. NET функциясын жазалы.
Коомдук бөлүшүлгөн функция GetCrc (ByVal байт катары байт (), ByVal поли As UInteger, милдеттүү эмес ByVal туурасы Integer = 32, милдеттүү эмес ByVal initReg As UInteger = & HFFFFFFFFUI, милдеттүү эмес ByVal finalXor As UInteger OptyFoF, OptionFoFFF, reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Билдирүүнүн туурасын нөл менен толуктаңыз (байт менен эсептөө):
ReDim Сактоо байттары (байт. Узундук - 1 + widthInBytes)
'Билдирүүдөн бир аз кезек түзүңүз:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Ар бир b үчүн байт ин
Dim Ba As New BitArray ({b})
If reverseBytes Then
I As Integer катары = 0ден 7ге чейин
msgFifo. Enqueue (ba (i))
Кийинки
Башка
I As Integer катары = 7ден 0го чейин Кадам -1
msgFifo. Enqueue (ba (i))
Кийинки
End If
Кийинки
'Реестрдин баштапкы толтурулган биттеринен кезек түзүңүз:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (B As Byte InitBytes алып widthInBytes). Reverse
Күңүрт initFifo Жаңы Кезек (Булдык) (туурасы - 1)
Ар бир b үчүн initBytesReversed катары
Dim Ba As New BitArray ({b})
If Not reverseBytes Анда
I As Integer катары = 0ден 7ге чейин
initFifo. Enqueue (ba (i))
Кийинки
Башка
I As Integer катары = 7ден 0го чейин Кадам -1
initFifo. Enqueue (ba (i))
Кийинки
End If
Кийинки
'Shift жана XOR:
Күңүрт регистр UInteger = 0 'катары, туурасы бит регистрин нөлгө толтурат.
Do while msgFifo. Count> 0
Dim poppedBit As Integer = CInt (регистр >> (туурасы - 1)) жана 1 'нөөмөт регистрине чейин аныктайт.
Күңүрт которулганБит катары байт = Convert. ToByte (msgFifo. Dequeue)
Эгерде initFifo. Count> 0 Анда
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor б
End If
регистр = регистр << 1
реестр = регистр Же shifttedBit
Эгерде poppedBit = 1 Андан кийин
реестр = регистр Xor poly
End If
Loop
'Акыркы конверсиялар:
Dim crc As UInteger = register 'Реестрде бөлүнүүнүн калган бөлүгү камтылган == сумма.
If reverseCrc Анда
crc = чагылдыруу (crc, туурасы)
End If
crc = crc Xor finalXor
crc = crc Жана (& HFFFFFFFFFUI >> (32 - туурасы)) 'эң аз биттерди маска кылат.
Retc crc
End Function
