Obstaja veliko možnosti za izračun kontrolne vsote CRC na internetu. Kaj pa je pravzaprav kontrolna vsota in zakaj se izračuna na ta način? Ugotovimo.
Navodila
Korak 1
Najprej pojdimo malo v teorijo. Kaj je pravzaprav CRC? Skratka, to je ena od sort izračuna kontrolne vsote. Kontrolna vsota je metoda preverjanja celovitosti prejetih informacij na strani sprejemnika pri prenosu prek komunikacijskih kanalov. Na primer, eno najpreprostejših preverjanj je uporaba paritetnega bita. Takrat se sestavijo vsi bitji poslanega sporočila in če se vsota izkaže za sodo, se na koncu sporočila doda 0, če je nenavadna, pa 1. Ko prejme, se vsota sporočila bitov se prav tako prešteje in primerja s prejetim bitom parnosti. Če se razlikujejo, je med prenosom prišlo do napak in poslane informacije so bile izkrivljene.
Toda ta metoda odkrivanja prisotnosti napak je zelo neinformativna in ne deluje vedno, ker če je več bitov sporočila izkrivljeno, se pariteta vsote morda ne bo spremenila. Zato obstaja veliko več "naprednih" pregledov, vključno s CRC.
Pravzaprav CRC ni vsota, temveč rezultat delitve določene količine informacij (informacijskega sporočila) s konstanto, oziroma preostanek delitve sporočila s konstanto. Vendar se CRC v preteklosti imenuje tudi "kontrolna vsota". Vsak bit sporočila prispeva k vrednosti CRC. To pomeni, da če se med prenosom spremeni vsaj en bit prvotnega sporočila, se bo spremenila tudi kontrolna vsota in to bistveno. To je velik plus takega preverjanja, saj omogoča nedvoumno ugotovitev, ali je bilo izvirno sporočilo med prenosom popačeno ali ne.
2. korak
Preden začnemo izračunati CRC, je potrebno malo več teorije.
Kaj je prvotno sporočilo, mora biti jasno. Je sosednje zaporedje bitov poljubne dolžine.
Kaj je konstanta, po kateri bi morali deliti izvirno sporočilo? Tudi to število je poljubne dolžine, vendar se običajno uporabljajo večkratniki 1 bajta - 8, 16 in 32 bitov. Preprosto je šteti, saj računalniki delujejo z bajti, ne z bitami.
Deliteljna konstanta je običajno zapisana kot polinom (polinom), kot je ta: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Tu stopnja števila "x" pomeni položaj enobita v številu, začenši z nič, najpomembnejši bit pa označuje stopnjo polinoma in se pri interpretaciji števila zavrže. To pomeni, da predhodno zapisana številka ni nič več kot (1) 00000111 v binarni ali 7 v decimalni obliki. V oklepajih sem navedel implicitno najpomembnejšo številko števila.
Tu je še en primer: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Običajno se za različne vrste CRC uporabljajo nekateri standardni polinomi.
3. korak
Torej, kako izračunate kontrolno vsoto? Obstaja osnovna metoda - razdelitev sporočila na polinom "čelno" - in njene spremembe, da se zmanjša število izračunov in s tem pospeši izračun CRC. Ogledali si bomo osnovno metodo.
Na splošno se delitev števila s polinomom izvede po naslednjem algoritmu:
1) ustvari se matrika (register), napolnjena z ničlami, ki so po dolžini enake dolžini širine polinoma;
2) izvirno sporočilo je dopolnjeno z ničlami v najmanj pomembnih bitih, v količini, ki je enaka številu bitov polinoma;
3) en najpomembnejši bit sporočila se vnese v najmanj pomemben bit registra in en bit se premakne iz najpomembnejšega bita registra;
4) če je razširjeni bit enak "1", so biti obrnjeni (operacija XOR, izključno ALI) v tistih registrskih bitih, ki ustrezajo tistim v polinomu;
5) če so v sporočilu še bitji, pojdite na korak 3);
6) ko so vsi deli sporočila vstopili v register in so bili obdelani s tem algoritmom, ostane ostanek delitve v registru, ki je kontrolna vsota CRC.
Slika prikazuje delitev prvotnega zaporedja bitov s številom (1) 00000111 ali polinoma x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
4. korak
Ostalo je še nekaj dodatkov. Kot ste morda že opazili, lahko sporočilo delite s poljubno številko. Kako ga izbrati? Obstajajo številni standardni polinomi, ki se uporabljajo za izračun CRC. Na primer, za CRC32 je lahko 0x04C11DB7, za CRC16 pa 0x8005.
Poleg tega lahko v register na začetku izračuna ne pišete ničle, ampak neko drugo številko.
Med izračuni jih je mogoče neposredno pred izdajo končne kontrolne vsote CRC deliti z neko drugo številko.
In zadnja stvar. Bajte sporočila pri zapisovanju v register lahko postavimo kot najpomembnejši bit »naprej« in obratno, najmanj pomembnega.
5. korak
Na podlagi vsega zgoraj napišimo osnovno funkcijo. NET, ki izračuna kontrolno vsoto CRC tako, da vzame številne parametre, ki sem jih opisal zgoraj, in vrne vrednost CRC kot 32-bitno nepodpisano številko.
Javna funkcija v skupni rabi GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Neobvezno ByVal width As Integer = 32, Neobvezno ByVal initReg As UInteger = & HFFFFFFFFUI, Izbirno ByVal finalXor As UInteger = & HFFFFFFFFUI, Optional ByVal Optional ByVal Bowal reverseCrc As Boolean = True) Kot UInteger
Zaširi širinoInBytes kot celo število = širina / 8
'Širino sporočila dopolnite z ničlami (izračun v bajtih):
ReDim Preserve bytes (bytes. Length - 1 + widthInBytes)
'Ustvari bitno vrsto iz sporočila:
Zatemni msgFifo kot nova čakalna vrsta (od logične vrednosti) (bajtov. Število * 8 - 1)
Za vsak b kot bajt v bajtih
Zatemni kot nov BitArray ({b})
Če reverseBytes Potem
Za i kot celo število = 0 do 7
msgFifo. Enqueue (ba (i))
Naslednji
Drugače
Za i kot celo število = 7 do 0 Korak -1
msgFifo. Enqueue (ba (i))
Naslednji
Končaj če
Naslednji
'Ustvari čakalno vrsto iz začetnih polnilnih bitov registra:
Zatemni initBytes kot bajt () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes).
Zatemni initFifo kot novo čakalno vrsto (od logične vrednosti) (širina - 1)
Za vsak b kot bajt v initBytesReversed
Zatemni kot nov BitArray ({b})
Če ne obrne bajtov, potem
Za i kot celo število = 0 do 7
initFifo. Enqueue (ba (i))
Naslednji
Drugače
Za i kot celo število = 7 do 0 Korak -1
initFifo. Enqueue (ba (i))
Naslednji
Končaj če
Naslednji
'Shift in XOR:
Dim register Kot UInteger = 0 'zapolni širok-bitni register z ničlami.
Do While msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (širina - 1)) In 1 'definirajte pred registrom premika.
Zatemni premikBit kot bajt = Pretvori. Bot (msgFifo. Dequeue)
Če je initFifo. Count> 0, potem
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shift_bit = shift_bit Xor b
Končaj če
register = register << 1
register = register Ali shiftBit
Če je poppedBit = 1 Potem
register = registriraj Xor poli
Končaj če
Loop
'Končne pretvorbe:
Dim crc Kot UInteger = register 'Register vsebuje preostanek kontrolne vsote delitve ==.
Če reverseCrc Potem
crc = odsev (crc, širina)
Končaj če
crc = crc Xor končniXor
crc = crc In (& HFFFFFFFFUI >> (32 - širina)) 'prikrije najmanj pomembne bite.
Vrni crc
Končna funkcija
