Kuna chaguzi nyingi za kuhesabu checksum ya CRC kwenye mtandao. Lakini checksum ni nini haswa na kwa nini imehesabiwa kwa njia hii? Wacha tuigundue.
Maagizo
Hatua ya 1
Kwanza, wacha tupate nadharia kidogo. Kwa hivyo CRC ni nini hasa? Kwa kifupi, hii ni moja ya aina ya hesabu ya checksum. Checksum ni njia ya kuangalia uaminifu wa habari iliyopokelewa kwa upande wa mpokeaji wakati wa kupitisha njia za mawasiliano. Kwa mfano, moja ya hundi rahisi ni kutumia usawa kidogo. Huu ndio wakati bits zote za ujumbe uliosambazwa zimefupishwa, na ikiwa jumla inageuka kuwa sawa, basi 0 huongezwa mwisho wa ujumbe, ikiwa ni ya kushangaza, basi 1. Unapopokea, jumla ya bits ujumbe pia ni kuhesabiwa na ikilinganishwa na kupokea usawa kidogo. Ikiwa zinatofautiana, basi makosa yalitokea wakati wa usafirishaji na habari iliyosambazwa ilipotoshwa.
Lakini njia hii ya kugundua uwepo wa makosa haijulikani sana na haifanyi kazi kila wakati, kwa sababu ikiwa bits kadhaa za ujumbe zimepotoshwa, usawa wa jumla hauwezi kubadilika. Kwa hivyo, kuna ukaguzi zaidi "wa hali ya juu", pamoja na CRC.
Kwa kweli, CRC sio jumla, lakini matokeo ya kugawanya idadi fulani ya habari (ujumbe wa habari) na mara kwa mara, au tuseme, salio la kugawanya ujumbe na mara kwa mara. Walakini, CRC pia inajulikana kihistoria kama "checksum". Kila sehemu ya ujumbe inachangia thamani ya CRC. Hiyo ni, ikiwa angalau ujumbe mmoja wa asili unabadilika wakati wa usambazaji, checksum pia itabadilika, na kwa kiasi kikubwa. Hii ni pamoja na kubwa ya hundi kama hiyo, kwani hukuruhusu kuamua bila shaka ikiwa ujumbe wa asili ulipotoshwa wakati wa usafirishaji au la.
Hatua ya 2
Kabla ya kuanza kuhesabu CRC, nadharia kidogo zaidi inahitajika.
Je! Ni ujumbe gani wa asili unapaswa kuwa wazi. Ni mlolongo unaojumuisha wa urefu wa kiholela.
Je! Ni nini mara kwa mara ambacho tunapaswa kugawanya ujumbe wa asili? Nambari hii pia ina urefu wowote, lakini kawaida kuzidisha kwa 1 baiti hutumiwa - 8, 16 na 32 bits. Ni rahisi tu kuhesabu, kwa sababu kompyuta hufanya kazi na ka, sio na bits.
Mara kwa mara msuluhishi huandikwa kama polynomial (polynomial) kama hii: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Hapa, kiwango cha nambari "x" inamaanisha nafasi ya nambari moja kwa nambari, kuanzia sifuri, na kidogo muhimu zaidi inaonyesha kiwango cha polynomial na hutupwa wakati wa kutafsiri nambari. Hiyo ni, nambari iliyoandikwa hapo awali sio zaidi ya (1) 00000111 kwa binary, au 7 kwa desimali. Katika mabano, nilionyesha nambari muhimu zaidi ya nambari.
Hapa kuna mfano mwingine: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Kawaida polynomials zingine hutumiwa kwa aina tofauti za CRC.
Hatua ya 3
Kwa hivyo unahesabuje checksum? Kuna njia ya msingi - kugawanya ujumbe katika "kichwa-mbele" cha polynomial - na marekebisho yake ili kupunguza idadi ya mahesabu na, ipasavyo, kuharakisha hesabu ya CRC. Tutaangalia njia ya msingi.
Kwa ujumla, mgawanyiko wa nambari na polynomial hufanywa kulingana na algorithm ifuatayo:
1) safu (rejista) imeundwa, imejazwa na zero, sawa na urefu na urefu wa upana wa polynomial;
2) ujumbe wa asili unaongezewa na sifuri kwa bits kidogo, kwa kiasi sawa na idadi ya bits ya polynomial;
3) ujumbe mmoja muhimu zaidi umeingizwa kwenye sajili ndogo zaidi, na kidogo huhamishwa kutoka kwa rejista muhimu zaidi;
4) ikiwa kipengee kilichopanuliwa ni sawa na "1", basi bits zinageuzwa (operesheni ya XOR, kipekee AU) katika zile rejista ambazo zinahusiana na zile zilizo kwenye polynomial;
5) ikiwa bado kuna bits kwenye ujumbe, nenda kwa hatua ya 3);
6) wakati bits zote za ujumbe ziliingia kwenye rejista na zilichakatwa na algorithm hii, sehemu iliyobaki ya mgawanyiko inabaki kwenye rejista, ambayo ni CRC checksum.
Takwimu inaonyesha mgawanyiko wa mlolongo wa asili kidogo na nambari (1) 00000111, au polynomial x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Hatua ya 4
Kuna miguso kadhaa ya nyongeza iliyoachwa. Kama unavyoona, ujumbe unaweza kugawanywa na nambari yoyote. Jinsi ya kuichagua? Kuna idadi kubwa ya polynomials ambayo hutumiwa kuhesabu CRC. Kwa mfano, kwa CRC32 inaweza kuwa 0x04C11DB7, na kwa CRC16 inaweza kuwa 0x8005.
Kwa kuongezea, katika rejista mwanzoni mwa hesabu, unaweza kuandika sio zero, lakini nambari nyingine.
Pia, wakati wa mahesabu, mara moja kabla ya kutoa hundi ya mwisho ya CRC, zinaweza kugawanywa na nambari nyingine.
Na jambo la mwisho. Baiti za ujumbe wakati wa kuandika kwa rejista zinaweza kuwekwa kama "mbele" muhimu zaidi, na kinyume chake, muhimu zaidi.
Hatua ya 5
Kulingana na yote yaliyo hapo juu, wacha tuandike kazi ya Msingi. NET ambayo huhesabu CRC checksum kwa kuchukua vigezo kadhaa ambavyo nimeelezea hapo juu na kurudisha dhamana ya CRC kama nambari isiyosainiwa 32-bit.
Kazi ya Kushirikiwa Umma GetCrc (ByVal byte As Byte (), ByVal poly As UInteger, Hiari ByVal upana Kama Integer = 32, Hiari ByVal initReg As UInteger = & HFFFFFFFFUI, Hiari ByVal finalXor As UInteger = & HFFFFFFFFUI, Hiari ByValBy reverseCrc As Boolean = True) Kama UInteger
Upana wa InBytes Kama Kamili = upana / 8
'Ongeza upana wa ujumbe na zero (hesabu katika ka):
ReDim Hifadhi ka (baiti. Urefu - 1 + upanaInBytes)
Unda foleni kidogo kutoka kwa ujumbe:
Dim msgFifo Kama Foleni Mpya (Ya Boolean) (ka. Hesabu * 8 - 1)
Kwa Kila b Kama Baiti Katika ka
Fifisha kama BitArray Mpya ({b})
Ikiwa reverseBytes Basi
Kwangu mimi kama Nambari kamili = 0 hadi 7
msgFifo. Enqueue (ba (i))
Ifuatayo
Kingine
Kwangu mimi kama Nambari kamili = 7 Hadi 0 Hatua -1
msgFifo. Enqueue (ba (i))
Ifuatayo
Mwisho Ikiwa
Ifuatayo
Unda foleni kutoka kwa sehemu ya kwanza ya kujaza ya rejista:
Punguza InitBytes Kama Byte () = BitConverter. GetBytes (initReg)
Dim initBytes Imebadilishwa kama isiyohesabika (Ya Byte) = (Kutoka b Kama Byte Katika initBytes Chukua upanaInBytes).
Dim initFifo Kama Foleni Mpya (Ya Boolean) (upana - 1)
Kwa Kila b Kama Byte InitBytesImegeuzwa
Fifisha kama BitArray Mpya ({b})
Ikiwa Sio reverseBytes Basi
Kwangu mimi kama Nambari kamili = 0 hadi 7
initFifo. Enqueue (ba (i))
Ifuatayo
Kingine
Kwangu mimi kama Nambari kamili = 7 Hadi 0 Hatua -1
initFifo. Enqueue (ba (i))
Ifuatayo
Mwisho Ikiwa
Ifuatayo
Shift na XOR:
Sajili ndogo kama UInteger = 0 'jaza rejista ya upana na zero.
Fanya Wakati msgFifo. Count> 0
Dim poppedBit As Integer = CInt (rejista >> (upana - 1)) Na 1 'fafanua kabla ya sajili ya zamu.
Punguza shiftingBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Ikiwa initFifo. Count> 0 Basi
Punguza b kama Byte = Badilisha. ToByte (initFifo. Deueue)
shiftedBit = iliyobadilishwaBit Xor b
Mwisho Ikiwa
kujiandikisha = kujiandikisha << 1
rejista = rejista au shiftedBit
Ikiwa poppedBit = 1 Basi
rejista = kujiandikisha Xor poly
Mwisho Ikiwa
Kitanzi
Mabadiliko ya mwisho:
Dim crc Kama UInteger = rejista 'Rejista ina sehemu iliyobaki ya mgawanyiko == checksum.
Ikiwa reverseCrc Basi
crc = tafakari (crc, upana)
Mwisho Ikiwa
crc = crc Xor ya mwishoXor
crc = crc Na (& HFFFFFFFFUI >> (32 - upana)) 'mask bits muhimu zaidi.
Rudisha crc
Maliza Kazi
