Internetda CRC summasini hisoblash uchun ko'plab imkoniyatlar mavjud. Ammo nazorat summasi aniq nima va nima uchun u shu tarzda hisoblab chiqilgan? Keling, buni aniqlaymiz.
Ko'rsatmalar
1-qadam
Birinchidan, keling, bir oz nazariya bilan tanishaylik. Xo'sh, CRC nima o'zi? Muxtasar qilib aytganda, bu summani hisoblash turlaridan biridir. Tekshirish yig'indisi - bu aloqa kanallari orqali uzatishda qabul qilingan tomonda qabul qilingan ma'lumotlarning yaxlitligini tekshirish usuli. Masalan, eng oddiy tekshiruvlardan biri bu parite bitdan foydalanishdir. Bu uzatilgan xabarning barcha bitlari yig'ilganda, agar yig'indisi juft bo'lib chiqsa, u holda xabar oxiriga 0 qo'shiladi, agar g'alati bo'lsa, unda 1. Qabul qilayotganda yig'indining yig'indisi xabar bitlari ham hisoblanadi va olingan parite bit bilan taqqoslanadi. Agar ular bir-biridan farq qiladigan bo'lsa, u holda uzatish paytida xatolar yuzaga keldi va uzatilgan ma'lumotlar buzilgan.
Ammo xatolar mavjudligini aniqlashning bu usuli juda ma'lumotsiz va har doim ham ishlamaydi, chunki agar xabarning bir nechta bitlari buzilgan bo'lsa, yig'indining pariteti o'zgarmasligi mumkin. Shuning uchun, juda ko'p "rivojlangan" tekshiruvlar, shu jumladan CRC mavjud.
Aslida, CRC yig'indisi emas, balki ma'lum miqdordagi ma'lumotni (axborot xabarini) doimiyga bo'lish natijasi, aniqrog'i, xabarni doimiyga bo'lishning qolgan qismi. Biroq, CRC tarixiy jihatdan "cheksum" deb ham ataladi. Xabarning har bir biti CRC qiymatiga hissa qo'shadi. Ya'ni, uzatish paytida asl xabarning kamida bittasi o'zgarsa, nazorat summasi ham o'zgaradi va sezilarli darajada. Bu bunday tekshiruvning katta plyusi, chunki u asl xabarni uzatish paytida buzilganligini yoki yo'qligini aniq aniqlashga imkon beradi.
2-qadam
CRC-ni hisoblashni boshlashdan oldin, biroz ko'proq nazariya kerak.
Asl xabar nima bo'lishi kerakligi aniq bo'lishi kerak. Bu ixtiyoriy uzunlikdagi bitlarning tutashgan ketma-ketligi.
Dastlabki xabarni qanday doimiy ravishda bo'lishimiz kerak? Ushbu raqam har qanday uzunlikda, lekin odatda 1 baytning ko'paytmasi ishlatiladi - 8, 16 va 32 bit. Faqat hisoblash osonroq, chunki kompyuterlar bitlar bilan emas, balki baytlar bilan ishlaydi.
Ajratuvchi doimiylik, odatda, quyidagi kabi polinom (polinom) sifatida yoziladi: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Bu erda "x" sonining darajasi noldan boshlanadigan raqamdagi bitta bitning o'rnini anglatadi va eng muhim bit polinomning darajasini ko'rsatadi va raqamni talqin qilishda tashlanadi. Ya'ni ilgari yozilgan raqam (1) 00000111 ikkilik sonda yoki o'nlik sonda 7 dan boshqa narsa emas. Qavslar ichida men raqamning nazarda tutilgan eng muhim raqamini ko'rsatdim.
Boshqa bir misol: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Odatda ba'zi bir standart polinomlar turli xil CRC turlari uchun ishlatiladi.
3-qadam
Xo'sh, summani qanday hisoblash mumkin? Hisob-kitoblar sonini kamaytirish va shunga muvofiq CRC hisob-kitobini tezlashtirish uchun asosiy usul - xabarni polinomga "bosh bilan" ajratish va uning modifikatsiyalari mavjud. Biz asosiy usulni ko'rib chiqamiz.
Umuman olganda, sonni polinomga bo'lish quyidagi algoritm bo'yicha amalga oshiriladi:
1) nollar bilan to'ldirilgan, uzunligi polinom kengligining uzunligiga teng bo'lgan massiv (registr) yaratiladi;
2) asl xabar polinomning bitlar soniga teng miqdordagi eng kichik bitlardagi nollar bilan to'ldiriladi;
3) xabarning eng muhim biti registrning eng kichik bitiga kiritiladi va bit bit registrning eng muhim bitidan ko'chiriladi;
4) agar kengaytirilgan bit "1" ga teng bo'lsa, u holda ko'plikdagi bitlarga to'g'ri keladigan o'sha registr bitlarida bitlar teskari (XOR operatsiyasi, eksklyuziv YOKI);
5) agar xabarda hali ham bitlar bo'lsa, 3-bosqichga o'ting);
6) xabarning barcha bitlari registrga kirganda va ushbu algoritm bilan ishlov berilganda, bo'linishning qolgan qismi registrda qoladi, bu CRC nazorat summasi.
Shakl asl bit ketma-ketligini (1) 00000111 raqamiga bo'linishini yoki x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 polinomini tasvirlaydi.
4-qadam
Yana bir nechta qo'shimcha teginishlar qoldi. Ehtimol siz sezgan bo'lasiz, xabarni istalgan raqamga bo'lish mumkin. Uni qanday tanlash kerak? CRCni hisoblash uchun ishlatiladigan bir qator standart polinomlar mavjud. Masalan, CRC32 uchun 0x04C11DB7 va CRC16 uchun 0x8005 bo'lishi mumkin.
Bundan tashqari, hisoblash boshidagi registrda siz nollarni emas, balki boshqa raqamlarni yozishingiz mumkin.
Shuningdek, hisob-kitoblar paytida, CRC yakuniy summasini chiqarishdan oldin, ularni boshqa raqamlarga bo'lish mumkin.
Va oxirgi narsa. Ro'yxatdan o'tishda xabarning baytlari eng muhim bit "oldinga", aksincha, eng ahamiyatsiz bit sifatida joylashtirilishi mumkin.
5-qadam
Yuqorida aytilganlarning hammasiga asoslanib, men yuqorida tavsiflangan bir qator parametrlarni qabul qilib va CRC qiymatini 32 bit imzosiz raqam sifatida qaytarish orqali CRC summasini hisoblaydigan Basic. NET funktsiyasini yozamiz.
Umumiy umumiy funktsiya GetCrc (ByVal bayt sifatida bayt (), ByVal poli sifatida UInteger, ixtiyoriy ByVal kengligi sifatida Integer = 32, ixtiyoriy ByVal initReg As UInteger = & HFFFFFFFFUI, ixtiyoriy ByVal finalXor sifatida UInteger OptyVFFFF, va, reverseCrc As Boolean = True) UInteger sifatida
Dim widthInBytes As Integer = width / 8
'Xabar kengligini nollar bilan to'ldiring (baytlarda hisoblash):
ReDim saqlash baytlari (bayt. Uzunlik - 1 + widthInBytes)
'Xabardan biroz navbat hosil qiling:
Dim msgFifo Yangi navbat sifatida (Boolean) (bayt. Sana * 8 - 1)
Har bir b bayt sifatida
Dim ba sifatida yangi BitArray ({b})
Agar reverseBytes Keyin
In As Integer = 0 dan 7 gacha
msgFifo. Enqueue (ba (i))
Keyingisi
Boshqa
In As Integer = 7 dan 0 gacha bo'lgan qadam -1
msgFifo. Enqueue (ba (i))
Keyingisi
Agar tugatish
Keyingisi
'Reyestrning dastlabki to'ldirish qismlaridan navbat yarating:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed IEnumerable (Of Byte) = (B As Byte Init inBytes widthInBytes-ni oling). Reverse
Dim initFifo yangi navbat sifatida (mantiqiy) (kenglik - 1)
InitBytesReversed sifatida har bir b bayt uchun
Dim ba sifatida yangi BitArray ({b})
Agar reverseBytes bo'lmasa
In As Integer = 0 dan 7 gacha
initFifo. Enqueue (ba (i))
Keyingisi
Boshqa
In As Integer = 7 dan 0 gacha bo'lgan qadam -1
initFifo. Enqueue (ba (i))
Keyingisi
Agar tugatish
Keyingisi
'Shift va XOR:
Dim registri UInteger = 0 'sifatida bit-bit registrini nolga to'ldiradi.
Do while msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registr >> (width - 1)) Va 1 'shift registridan oldin aniqlanadi.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Agar initFifo. Count> 0 Keyin
Dim b As byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Agar tugatish
registr = registr << 1
registr = registr Yoki shifttedBit
Agar poppedBit = 1 bo'lsa
registr = registr Xor poly
Agar tugatish
Loop
Yakuniy konversiyalar:
Dim crc As UInteger = registr 'Ro'yxatdan o'tish == checksumning qolgan qismini o'z ichiga oladi.
Agar reverseCrc Keyin
crc = aks ettirish (crc, width)
Agar tugatish
crc = crc Xor finalXor
crc = crc Va (& HFFFFFFFFFUI >> (32-kenglik)) 'eng kichik bitlarni maskalash.
Qaytish crc
Tugatish funktsiyasi
