Yra daug galimybių apskaičiuoti CRC kontrolinę sumą internete. Bet kas tiksliai yra kontrolinė suma ir kodėl ji apskaičiuojama tokiu būdu? Išsiaiškinkime.
Nurodymai
1 žingsnis
Pirmiausia paimkime šiek tiek teorijos. Taigi, kas yra CRC? Trumpai tariant, tai yra viena iš kontrolinės sumos skaičiavimo atmainų. Kontrolinė suma yra metodas patikrinti gautos informacijos vientisumą imtuvo pusėje perduodant ryšio kanalais. Pavyzdžiui, vienas iš paprasčiausių patikrinimų yra pariteto bitų naudojimas. Tai yra tada, kai susumuojami visi perduoto pranešimo bitai, o jei suma pasirodo lygi, tada prie pranešimo pabaigos pridedama 0, jei ji nelyginė, tada 1. Gaunant pranešimo sumą, pranešimo bitai taip pat skaičiuojami ir lyginami su gautu pariteto bitu. Jei jie skiriasi, tada perduodant įvyko klaidų ir perduodama informacija buvo iškraipyta.
Tačiau šis klaidų nustatymo metodas yra labai neinformatyvus ir ne visada veikia, nes jei iškraipomi keli pranešimo bitai, sumos paritetas gali nesikeisti. Todėl yra daug daugiau „pažangių“patikrinimų, įskaitant CRC.
Tiesą sakant, CRC yra ne suma, o tam tikros informacijos (informacinio pranešimo) kiekio padalijimo iš konstantos, tiksliau, likusios žinutės padalijimo iš konstantos, rezultatas. Tačiau CRC istoriškai taip pat vadinamas „kontroline suma“. Kiekvienas pranešimo bitas prisideda prie CRC vertės. Tai yra, jei perdavimo metu pasikeičia bent vienas originalaus pranešimo bitas, kontrolinė suma taip pat pasikeis ir žymiai. Tai yra didelis tokio patikrinimo pliusas, nes jis leidžia jums nedviprasmiškai nustatyti, ar originalus pranešimas buvo iškraipytas perdavimo metu, ar ne.
2 žingsnis
Prieš pradedant skaičiuoti CRC, reikia šiek tiek daugiau teorijos.
Koks yra pirminis pranešimas, turėtų būti aišku. Tai gretima savavališko ilgio bitų seka.
Kas yra konstanta, pagal kurią turėtume padalyti pradinį pranešimą? Šis skaičius taip pat yra bet kokio ilgio, tačiau paprastai naudojami 1 baito kartotiniai - 8, 16 ir 32 bitai. Tiesiog paprasčiau suskaičiuoti, nes kompiuteriai dirba su baitais, o ne su bitais.
Daliklio konstanta paprastai rašoma kaip daugianario (daugianario) forma: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Čia skaičiaus „x“laipsnis reiškia vieno bito padėtį skaičiuje, pradedant nuo nulio, o reikšmingiausias bitas nurodo polinomo laipsnį ir yra atmetamas aiškinant skaičių. Tai reiškia, kad anksčiau užrašytas skaičius yra ne daugiau kaip (1) 00000111 dvejetainiu skaičiumi arba 7 dešimtainiu kableliu. Skliausteliuose nurodžiau numanomą reikšmingiausią skaičiaus skaitmenį.
Štai dar vienas pavyzdys: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Paprastai skirtingų tipų CRC naudojami kai kurie standartiniai polinomai.
3 žingsnis
Taigi, kaip apskaičiuoti kontrolinę sumą? Yra pagrindinis metodas - pranešimo padalijimas į daugianarį „galvą“ir jo modifikacijos, siekiant sumažinti skaičiavimų skaičių ir atitinkamai pagreitinti CRC skaičiavimus. Mes pažvelgsime į pagrindinį metodą.
Apskritai skaičiaus padalijimas iš polinomo atliekamas pagal šį algoritmą:
1) sukuriamas masyvas (registras), užpildytas nuliais, ilgio lygus polinomo pločio ilgiui;
2) pradinis pranešimas papildomas nuliais mažiausiai reikšmingais bitais, kurių suma lygi polinomo bitų skaičiui;
3) vienas reikšmingiausias pranešimo bitas įvedamas į mažiausiai reikšmingą registro bitą ir vienas bitas perkeliamas iš reikšmingiausio registro bitų;
4) jei išplėstasis bitas yra lygus „1“, tada bitai yra invertuojami (XOR operacija, išskirtinė ARBA) tuose registro bituose, kurie atitinka tuos, kurie yra polinome;
5) jei pranešime vis dar yra bitų, pereikite prie 3 žingsnio);
6) kai visi pranešimo bitai patenka į registrą ir buvo apdoroti šiuo algoritmu, likusi padalijimo dalis lieka registre, tai yra CRC kontrolinė suma.
Paveiksle parodytas pradinės bitų sekos padalijimas iš skaičiaus (1) 00000111 arba daugianario x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
4 žingsnis
Liko pora papildomų prisilietimų. Kaip jau pastebėjote, pranešimą galima padalyti iš bet kurio skaičiaus. Kaip jį pasirinkti? Yra keletas standartinių polinomų, kurie naudojami apskaičiuojant CRC. Pvz., CRC32 gali būti 0x04C11DB7, o CRC16 - 0x8005.
Be to, skaičiavimo pradžioje esančiame registre galite įrašyti ne nulius, bet kokį kitą skaičių.
Be to, atliekant skaičiavimus, prieš pat pateikiant galutinę CRC kontrolinę sumą, juos galima padalyti iš kito skaičiaus.
Ir paskutinis dalykas. Rašant į registrą pranešimo baitai gali būti dedami kaip reikšmingiausias bitas „į priekį“ir atvirkščiai - mažiausiai reikšmingas.
5 žingsnis
Remdamiesi tuo, kas išdėstyta pirmiau, parašykime pagrindinę. NET funkciją, kuri apskaičiuoja CRC kontrolinę sumą, paimdama keletą anksčiau aprašytų parametrų ir grąžindama CRC vertę kaip 32 bitų nepasirašytą skaičių.
Viešoji bendroji funkcija „GetCrc“(„ByVal“baitai kaip baitas (), „ByVal poly“kaip „UInteger“, pasirinktinis „ByVal“plotis kaip sveikasis skaičius = 32, pasirinktinis „ByVal“initReg kaip „UInteger = & HFFFFFFFFUI“, pasirinktinis „ByVal finalXor“kaip „UInteger =“ir „HFFFFFFal“, reverseCrc As Boolean = True) Kaip UInteger
Šviesos plotis „InBytes As Integer“= plotis / 8
„Papildykite pranešimo plotį nuliais (skaičiavimas baitais):
„ReDim Preserve“baitai (baitai. Ilgis - 1 + plotis „InBytes“)
'Sukurkite šiek tiek eilės iš pranešimo:
„Dim msgFifo“kaip nauja eilė (iš loginės) (baitai. Skaičius * 8 - 1)
Kiekvienam b baitui baitais
„Dim ba“kaip naujas „BitArray“({b})
Jei reverseBaitai tada
Skaičiui i kaip sveikasis skaičius nuo 0 iki 7
msgFifo. Enqueue (ba (i))
Kitas
Kitas
Už i As sveikasis skaičius = nuo 7 iki 0 -1 žingsnis
msgFifo. Equire (ba (i))
Kitas
Pabaiga jei
Kitas
„Sukurkite eilę iš pradinių registro užpildymo bitų:
„Dim initBytes As Byte“() = „BitConverter“. „GetBytes“(initReg)
„Dim initBytesReversed as IEnumerable (Byte) = (Iš b kaip Byte In InitBytes Paimkite widthInBytes).
„Dim initFifo“kaip nauja eilė (iš Boolean) (plotis - 1)
Kiekvienam b kaip baitui „InitBytesReversed“
„Dim ba“kaip naujas „BitArray“({b})
Jei ne reverseBytes Tada
Skaičiui i kaip sveikasis skaičius nuo 0 iki 7
initFifo. Enkeque (ba (i))
Kitas
Kitas
Už i As sveikasis skaičius = nuo 7 iki 0 -1 žingsnis
initFifo. Enkeque (ba (i))
Kitas
Pabaiga jei
Kitas
„Shift“ir „XOR“:
Užregistruotas registras Kadangi UInteger = 0 ', užpildykite bitų registrą nuliais.
Atlikite, kol msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registruoti >> (plotis - 1)) ir 1 'apibrėžti prieš pamainos registrą.
„Dim shiftedBit As Byte = Convert. ToByte“(msgFifo. Dequeue)
Jei initFifo. Count> 0 Tada
„Dim b“kaip baitas = konvertuoti į „ToByte“(initFifo. Dequeue)
„shiftedBit“= „shiftedBit“Xor b
Pabaiga jei
registruotis = registruotis << 1
register = register Arba „shiftedBit“
Jei poppedBit = 1 Tada
register = registruoti Xor poly
Pabaiga jei
Kilpa
„Paskutinės konversijos:
Dim crc As UInteger = register 'Registre yra likusi dalijimo == kontrolinė suma.
Jei atvirkštinisCrc Tada
crc = atspindėti (crc, plotis)
Pabaiga jei
crc = crc Xor finalXor
crc = crc Ir (& HFFFFFFFFUI >> (32 - plotis)) '' užmaskuoja mažiausiai reikšmingus bitus.
Grąžinti crc
Pabaigos funkcija
