CRC-tarkistussumman laskemiseksi Internetissä on monia vaihtoehtoja. Mutta mikä tarkalleen tarkalleen on ja miksi se lasketaan tällä tavalla? Selvitetään se.
Ohjeet
Vaihe 1
Ensinnäkin, saamme vähän teoriaa. Joten mikä on CRC? Lyhyesti sanottuna tämä on yksi tarkistussumman laskennan muunnelmista. Tarkistussumma on menetelmä vastaanotetun informaation eheyden tarkistamiseksi vastaanottopuolella lähetettäessä viestintäkanavien yli. Esimerkiksi yksi yksinkertaisimmista tarkistuksista on käyttää pariteettibittiä. Tällöin kaikki lähetetyn viestin bitit summataan ja jos summa osoittautuu parilliseksi, lisätään 0 viestin loppuun, jos se on pariton, sitten 1. Vastaanotettaessa myös viestibitit lasketaan ja verrataan vastaanotettuun pariteettibitiin. Jos ne eroavat toisistaan, lähetyksen aikana tapahtui virheitä ja lähetetty tieto vääristyi.
Mutta tämä menetelmä virheiden havaitsemiseksi on hyvin epätietoinen eikä se aina toimi, koska jos sanoman useita bittejä vääristyy, summan pariteetti ei välttämättä muutu. Siksi on olemassa paljon enemmän "edistyneitä" tarkastuksia, mukaan lukien CRC.
Itse asiassa CRC ei ole summa, vaan tulos tietyn määrän informaation (informaatiosanoman) jakamisesta vakiolla tai pikemminkin loput jakamalla viesti vakiolla. CRC: tä kutsutaan kuitenkin myös historiallisesti "tarkistussummaksi". Jokainen sanoman bitti vaikuttaa CRC-arvoon. Toisin sanoen, jos ainakin yksi bitti alkuperäisestä sanomasta muuttuu lähetyksen aikana, myös tarkistussumma muuttuu ja merkittävästi. Tämä on suuri plus tällaisesta tarkistuksesta, koska sen avulla voit yksiselitteisesti määrittää, vääristyikö alkuperäinen viesti lähetyksen aikana vai ei.
Vaihe 2
Ennen kuin aloitamme CRC: n laskemisen, tarvitaan hieman enemmän teoriaa.
Alkuperäisen viestin pitäisi olla selvä. Se on mielivaltaisen pituinen bittisarja.
Mikä on vakio, jolla meidän pitäisi jakaa alkuperäinen viesti? Tämä luku on myös minkä tahansa pituinen, mutta yleensä käytetään 1 tavun kerrannaisia - 8, 16 ja 32 bittiä. Laskeminen on vain helpompaa, koska tietokoneet toimivat tavuilla, ei bitillä.
Jakajavakio kirjoitetaan yleensä polynomina (polynomina) näin: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Tällöin luvun "x" aste tarkoittaa yhden bitin sijaintia luvussa, nollasta alkaen, ja merkittävin bitti osoittaa polynomin asteen ja hylätään lukua tulkittaessa. Toisin sanoen aiemmin kirjoitettu luku on vain (1) 00000111 binäärisenä tai 7 desimaalina. Suluissa ilmoitin luvun implisiittisen merkittävimmän numeron.
Tässä on toinen esimerkki: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Yleensä joitain standardipolynomeja käytetään erityyppisiin CRC-soluihin.
Vaihe 3
Joten miten lasket tarkistussumman? On olemassa perusmenetelmä - sanoman jakaminen polynomiksi "head-on" - ja sen muutokset laskelmien määrän vähentämiseksi ja vastaavasti CRC-laskennan nopeuttamiseksi. Tarkastelemme perusmenetelmää.
Yleensä luvun jakaminen polynomilla suoritetaan seuraavan algoritmin mukaisesti:
1) luodaan taulukko (rekisteri), joka on täynnä nollia, yhtä pitkä kuin polynomileveyden pituus;
2) alkuperäistä sanomaa täydennetään nollilla vähiten merkitsevinä bitteinä määränä, joka on yhtä suuri kuin polynomin bittien lukumäärä;
3) yksi sanoman merkittävin bitti syötetään rekisterin vähiten merkitsevään bittiin ja yksi bitti siirretään rekisterin merkittävimmästä bitistä;
4) jos laajennettu bitti on yhtä suuri kuin "1", niin bitit käännetään (XOR-operaatio, yksinomainen OR) niissä rekisteribiteissä, jotka vastaavat polynomissa olevia;
5) Jos viestissä on vielä bittejä, siirry vaiheeseen 3);
6) Kun kaikki sanoman bitit tulivat rekisteriin ja käsiteltiin tällä algoritmilla, loput jaosta pysyvät rekisterissä, mikä on CRC-tarkistussumma.
Kuva havainnollistaa alkuperäisen bittisekvenssin jakamista numerolla (1) 00000111 tai polynomilla x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Vaihe 4
Muutama kosketus on jäljellä. Kuten olet ehkä huomannut, viesti voidaan jakaa mihin tahansa numeroon. Kuinka valita se? CRC: n laskemiseksi käytetään useita standardipolynomeja. Esimerkiksi CRC32: lle se voi olla 0x04C11DB7 ja CRC16: lle 0x8005.
Lisäksi laskutoimituksen alussa olevaan rekisteriin ei voi kirjoittaa nollia, vaan jonkin muun numeron.
Lisäksi laskelmien aikana, välittömästi ennen lopullisen CRC-tarkistussumman julkaisemista, ne voidaan jakaa jollakin muulla luvulla.
Ja viimeinen asia. Rekisteriin kirjoitettaessa viestin tavut voidaan sijoittaa merkittävimmäksi bitiksi "eteenpäin" ja päinvastoin vähiten merkitseväksi bitiksi.
Vaihe 5
Kaiken edellä olevan perusteella kirjoitetaan Basic. NET -funktio, joka laskee CRC-tarkistussumman ottamalla useita edellä kuvattuja parametreja ja palauttamalla CRC-arvon 32-bittisenä allekirjoittamattomana numerona.
Julkinen jaettu toiminto GetCrc (ByVal-tavut tavuina (), ByVal poly kuin UInteger, valinnainen ByVal-leveys kokonaislukuna = 32, valinnainen ByVal initReg nimellä UInteger = & HFFFFFFFFUI, valinnainen ByVal finalXor kuten UInteger = & HFFFFFFalFal Byby, valinnainen By reverseCrc As Boolean = True) Kuten UInteger
Himmennä leveysInBytes kokonaislukuna = leveys / 8
'Täydennä viestin leveys nollilla (laskenta tavuina):
ReDim Säilytä tavut (tavua. Pituus - 1 + leveysInBytes)
'Luo pieni jono viestistä:
Himmennä msgFifo uutena jonona (Of Boolean) (tavua, määrä * 8-1)
Jokaiselle b tavuksi tavuina
Dim ba uutena BitArrayna ({b})
Jos käänteinen tavua sitten
Sillä i kokonaislukuna = 0 - 7
msgFifo. Enqueue (ba (i))
Seuraava
Muu
Luku i Kokonaisluku = 7 - 0 Vaihe -1
msgFifo. Enqueue (ba (i))
Seuraava
Loppu Jos
Seuraava
'Luo jono rekisterin alkuperäisistä täyttöbiteistä:
Himmennä tavua initBytes tavuna () = BitConverter. GetBytes (initReg)
Himmennä initBytesReversed as IEnumerable (tavua) = (b: stä tavuna initBytes ottaa leveysInBytes).
Himmennä initFifo uutena jonona (Of Boolean) (leveys - 1)
Kullekin b tavulle initBytesReversed
Dim ba uutena BitArrayna ({b})
Jos ei ole reverseBytes Sitten
Sillä i kokonaislukuna = 0 - 7
initFifo. Enqueue (ba (i))
Seuraava
Muu
Luvulle i kokonaislukuna = 7 - 0 vaihe -1
initFifo. Enqueue (ba (i))
Seuraava
Loppu Jos
Seuraava
'Vaihto ja XOR:
Hämärärekisteri Koska UInteger = 0 ', täytä leveysbittirekisteri nollilla.
Tee kun msgFifo. Count> 0
Dim poppedBit As Integer = CInt (rekisteröi >> (leveys - 1)) ja 1 'määrittelee ennen siirtorekisteriä.
Dim shiftedBit As Byte = Muunna ToByte (msgFifo. Dequeue)
Jos initFifo. Count> 0 Sitten
Dim b tavuina = Muunna ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit X tai b
Loppu Jos
register = rekisteröidy << 1
register = register Tai shiftedBit
Jos poppedBit = 1 Sitten
register = rekisteröi Xor poly
Loppu Jos
Silmukka
'Lopulliset tulokset:
Dim crc As UInteger = register 'Rekisteri sisältää loput osastosta == tarkistussumma.
Jos käänteinenCrc Sitten
crc = heijastava (crc, leveys)
Loppu Jos
crc = crc Xor finalXor
crc = crc Ja (& HFFFFFFFFUU >> (32 - leveys)) 'peittää vähiten merkitsevät bitit.
Palaa pp
Lopeta toiminto
