Интернет дээр CRC-ийн хяналтын дүнг тооцоолох олон сонголт байдаг. Гэхдээ хяналтын дүн гэж яг юу юм, яагаад үүнийг ингэж тооцдог юм бэ? Үүнийг олж мэдье.
Зааварчилгаа
1-р алхам
Эхлээд жаахан онол авъя. Тэгэхээр CRC гэж яг юу юм бэ? Товчхондоо бол энэ нь хяналтын дүнг тооцоолох сортуудын нэг юм. Хяналтын нийлбэр нь холбооны сувгаар дамжуулахдаа хүлээн авагчийн талаас хүлээн авсан мэдээллийн бүрэн бүтэн байдлыг шалгах арга юм. Жишээлбэл, хамгийн энгийн шалгалтуудын нэг бол парит битийг ашиглах явдал юм. Энэ бол дамжуулсан мессежийн бүх битүүдийг нэгтгэх бөгөөд хэрэв нийлбэр нь тэгш болвол мэдээний төгсгөлд 0, хэрэв сондгой байвал 1-ийг нэмнэ. мессежийн битийг мөн хүлээн авсан паритеттай харьцуулж тоолно. Хэрэв тэдгээр нь ялгаатай бол дамжуулах явцад алдаа гарсан бөгөөд дамжуулсан мэдээллийг гажуудуулсан болно.
Гэхдээ алдаа байгааг илрүүлэх энэ арга нь маш мэдээлэлгүй бөгөөд үргэлж ажилладаггүй, яагаад гэвэл хэрэв мэдээний хэд хэдэн битийг гажуудуулсан бол нийлбэрийн паритет өөрчлөгдөхгүй байж магадгүй юм. Тиймээс CRC гэх мэт олон "дэвшилтэт" шалгалтууд байдаг.
Үнэн хэрэгтээ, CRC нь нийлбэр биш, харин тодорхой хэмжээний мэдээллийг (мэдээллийн мессеж) тогтмолоор хуваахын үр дүн, илүү тодорхой бол мессежийг тогтмолоор хуваахын үлдэгдэл юм. Гэсэн хэдий ч ХХЗХ-ийг түүхэндээ "хяналтын дүн" гэж нэрлэдэг. Зурвасын хэсэг бүр нь CRC-ийн утгад хувь нэмэр оруулдаг. Энэ нь дамжуулах явцад анхны мессежийн дор хаяж нэг хэсэг өөрчлөгдсөн бол хяналтын дүн мөн өөрчлөгдөж, мэдэгдэхүйц өөрчлөгдөх болно. Энэ нь анхны чекийн мессежийг дамжуулах явцад гажуудсан эсэхийг хоёрдмол утгагүйгээр тодорхойлох боломжийг олгодог тул ийм чекийн том нэмэх юм.
Алхам 2
Бид ХХЗ-ийг тооцоолж эхлэхээс өмнө арай илүү онол хэрэгтэй.
Анхны зурвас юу болох нь тодорхой байх ёстой. Энэ бол дурын урттай битүүдийн зэргэлдээ дараалал юм.
Бид анхны мессежийг хуваах ёстой ямар тогтмол хэмжигдэхүүнтэй вэ? Энэ тоо нь дурын урттай боловч ихэвчлэн 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
Дээр дурдсан бүх зүйл дээр үндэслэн CRC-ийн хяналтын дүнг тооцоолсон Basic. NET функцийг би дээр тайлбарласан хэд хэдэн параметрүүдийг авч CRC утгыг 32 битийн тэмдэггүй тоо болгон буцааж бичье.
Олон нийтийн хуваалцсан функц GetCrc (ByVal байт As Byte (), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal init As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger OptyF, reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Зурвасын өргөнийг тэгээр нэмэх (байтаар тооцох):
ReDim Хадгалах байт (байт. Урт - 1 + widthInBytes)
'Зурвасаас жаахан дараалал үүсгээрэй.
Dim msgFifo As New Queue (Of Boolean) (байт. Тооллого * 8 - 1)
Байт байт болгоны хувьд
Бяцхан байдлаар Шинэ BitArray ({b})
Хэрэв reverseBytes Дараа нь
I As Integer = 0-ээс 7 хүртэл
msgFifo. Enqueue (ba (i))
Дараачийн
Бусад
I As Integer = 7-оос 0 хүртэлх алхам -1
msgFifo. Enqueue (ba (i))
Дараачийн
Хэрэв төгсгөл бол
Дараачийн
'Бүртгэлийн эхний дүүргэлтүүдээс дараалал үүсгэх:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (B As Byte InitBytes нь widthInBytes-ийг авна).
Dim initFifo As New Queue (Of Boolean) (өргөн - 1)
Бит тус бүрийн хувьд initBytesReversed
Бяцхан байдлаар Шинэ BitArray ({b})
Хэрэв үгүй бол reverseBytes Дараа нь
I As Integer = 0-ээс 7 хүртэл
initFifo. Enqueue (ba (i))
Дараачийн
Бусад
I As Integer = 7-оос 0 хүртэлх алхам -1
initFifo. Enqueue (ba (i))
Дараачийн
Хэрэв төгсгөл бол
Дараачийн
'Shift ба XOR:
Бүртгэлийг багасгах UInteger = 0 'гэж өргөн битийн бүртгэлийг тэгээр дүүргэнэ.
Do while msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) ба 1 'shift register-ээс өмнө тодорхойлно.
Бүтэн shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Хэрэв initFifo. Count> 0 Дараа нь
Dim b As byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Хэрэв төгсгөл бол
бүртгэл = бүртгүүлэх << 1
бүртгэл = бүртгүүлэх Эсвэл shiftedBit
Хэрэв poppedBit = 1 Дараа нь
бүртгэл = бүртгүүлэх Xor poly
Хэрэв төгсгөл бол
Гогцоо
'Эцсийн хөрвүүлэлт:
Dim crc As UInteger = register 'Бүртгэлд хуваагдлын үлдэгдэл == хяналтын дүн багтсан болно.
Хэрэв reverseCrc Дараа нь
crc = тусгах (crc, өргөн)
Хэрэв төгсгөл бол
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFFUI >> (32-width)) 'нь хамгийн бага битүүдийг масклана.
Буцах crc
Төгсгөл функц
