CRC kontrolsummas aprēķināšanai internetā ir daudz iespēju. Bet kas īsti ir kontrolsumma un kāpēc tā tiek aprēķināta šādā veidā? Izdomāsim.
Instrukcijas
1. solis
Pirmkārt, pieņemsim mazliet teorijas. Kas tad īsti ir CRC? Īsāk sakot, šī ir viena no kontrolsummas aprēķināšanas šķirnēm. Kontrolsumma ir metode, kā pārbaudīt saņemtās informācijas integritāti uztvērēja pusē, pārsūtot pa sakaru kanāliem. Piemēram, viena no vienkāršākajām pārbaudēm ir izmantot paritātes bitu. Tas ir, kad visi pārsūtītā ziņojuma biti tiek summēti, un, ja summa izrādās vienmērīga, tad ziņojuma beigām 0 tiek pievienots 0, ja tas ir nepāra, tad 1. Saņemot, tiek skaitīti arī ziņu biti un salīdzināti ar saņemto paritātes bitu. Ja tie atšķiras, tad pārsūtīšanas laikā radās kļūdas, un pārsūtītā informācija tika sagrozīta.
Bet šī kļūdu klātbūtnes noteikšanas metode ir ļoti neinformatīva un ne vienmēr darbojas, jo ja tiek sagrozīti vairāki ziņojuma biti, summas paritāte var nemainīties. Tāpēc ir daudz vairāk "uzlabotu" pārbaužu, ieskaitot CRC.
Patiesībā CRC nav summa, bet rezultāts, sadalot noteiktu informācijas daudzumu (informācijas ziņojumu) ar konstanti, pareizāk sakot, atlikušo daļu dalot ar konstanti. Tomēr CRC vēsturiski tiek saukta arī par "kontrolsummu". Katrs ziņojuma bits veicina CRC vērtību. Tas ir, ja pārsūtīšanas laikā mainās vismaz viens sākotnējā ziņojuma bits, mainīsies arī kontrolsumma un ievērojami. Tas ir liels šādas pārbaudes plus, jo tas ļauj nepārprotami noteikt, vai sākotnējais ziņojums sūtīšanas laikā ir sagrozīts vai nē.
2. solis
Pirms mēs sākam aprēķināt CRC, ir nepieciešama nedaudz vairāk teorijas.
Kādam sākotnējam ziņojumam jābūt skaidram. Tā ir blakus esoša patvaļīga garuma bitu secība.
Kas ir konstante, ar kuru mums jāsadala sākotnējais ziņojums? Šis skaitlis ir arī jebkura garuma, taču parasti tiek izmantoti 1 baita daudzkārtņi - 8, 16 un 32 biti. Skaitīt ir vienkārši vieglāk, jo datori strādā ar baitiem, nevis ar bitiem.
Dalītāja konstante parasti tiek rakstīta kā polinoms (polinoms) šādi: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Šeit skaitļa "x" pakāpe nozīmē viena bita pozīciju skaitlim, sākot no nulles, un visnozīmīgākais bits norāda polinoma pakāpi un tiek izmests, interpretējot skaitli. Tas ir, iepriekš uzrakstītais skaitlis ir nekas vairāk kā (1) 00000111 binārā vai 7 aiz komata. Iekavās es norādīju netieši nozīmīgāko skaitļa ciparu.
Šeit ir vēl viens piemērs: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Dažādu tipu CRC parasti izmanto dažus standarta polinomus.
3. solis
Tātad, kā jūs aprēķināt kontrolsummu? Lai samazinātu aprēķinu skaitu un attiecīgi paātrinātu CRC aprēķinu, ir pamatmetode - ziņu sadalīšana polinomā “head-on” - un tās modifikācijas. Mēs izskatīsim pamata metodi.
Parasti skaitļa dalīšanu ar polinomu veic saskaņā ar šādu algoritmu:
1) tiek izveidots masīvs (reģistrs), kas piepildīts ar nullēm, vienāda garuma ar polinoma platuma garumu;
2) sākotnējais ziņojums tiek papildināts ar nullēm vismazāk nozīmīgajos bitos tādā daudzumā, kas vienāds ar polinoma bitu skaitu;
3) viens nozīmīgākais ziņojuma bits tiek ievadīts reģistra maznozīmīgākajā bitā un viens bits tiek pārvietots no nozīmīgākā reģistra bita;
4) ja paplašinātais bits ir vienāds ar "1", tad biti tiek apgriezti (XOR darbība, ekskluzīva VAI) tajos reģistra bitos, kas atbilst polinomā esošajiem;
5) ja ziņojumā joprojām ir biti, pārejiet pie 3. darbības);
6) kad visi ziņojuma biti ienāca reģistrā un tika apstrādāti ar šo algoritmu, atlikusī sadalījuma daļa paliek reģistrā, kas ir CRC kontrolsumma.
Attēlā parādīts sākotnējās bitu secības sadalījums ar skaitli (1) 00000111 vai polinomu x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
4. solis
Ir palikuši pāris papildu pieskārieni. Kā jūs, iespējams, pamanījāt, ziņojumu var sadalīt ar jebkuru skaitli. Kā to izvēlēties? CRC aprēķināšanai tiek izmantoti vairāki standarta polinomi. Piemēram, CRC32 var būt 0x04C11DB7, bet CRC16 - 0x8005.
Turklāt reģistrā aprēķina sākumā varat ierakstīt nevis nulles, bet kādu citu skaitli.
Arī aprēķinu laikā, tieši pirms CRC galīgās kontrolsummas izdošanas, tos var sadalīt ar kādu citu skaitli.
Un pēdējā lieta. Rakstot reģistram, ziņojuma baitus var ievietot kā nozīmīgāko bitu "uz priekšu" un otrādi - vismazāk nozīmīgo bitu.
5. solis
Pamatojoties uz visu iepriekš minēto, uzrakstīsim Basic. NET funkciju, kas aprēķina CRC kontrolsummu, ņemot vairākus iepriekš aprakstītos parametrus un atgriežot CRC vērtību kā 32 bitu neparakstītu skaitli.
Publiska koplietojama funkcija GetCrc (ByVal baiti kā baits (), ByVal poli kā UInteger, pēc izvēles ByVal platums kā veselais skaitlis = 32, pēc izvēles ByVal initReg kā UInteger = & HFFFFFFFFUI, pēc izvēles ByVal finalXor kā UInteger = & HFFFFFFalFal, Reverse By, pēc izvēles reverseCrc As Būla = True) Kā UInteger
Blāvuma platumsInBytes As Integer = platums / 8
Papildiniet ziņojuma platumu ar nullēm (aprēķins baitos):
ReDim Saglabāt baitus (baiti. Garums - 1 + widthInBytes)
'Izveidojiet mazliet rindu no ziņojuma:
Dim msgFifo kā jauna rinda (no Būla) (baiti. Skaits * 8 - 1)
Katram b kā baits baitos
Dim ba kā jauns BitArray ({b})
Ja reverseBytes Tad
Par i kā vesels skaitlis = 0 līdz 7
msgFifo. Enqueue (ba (i))
Nākamais
Cits
Par i kā vesels skaitlis = 7 līdz 0 -1. Solis
msgFifo. Enqueue (ba (i))
Nākamais
Beigt Ja
Nākamais
'Izveidojiet rindu no reģistra sākotnējiem aizpildīšanas bitiem:
Dim initBytes kā baits () = BitConverter. GetBytes (initReg)
Dim initBytesReversed as IEnumerable (Of Byte) = (No b kā Byte In InitBytes ņem widthInBytes). Reverss
Dim initFifo kā jauna rinda (no Būla) (platums - 1)
Katram b kā baits initBytesReversed
Dim ba kā jauns BitArray ({b})
Ja nav reverseBytes Tad
Par i kā vesels skaitlis = 0 līdz 7
initFifo. Enqueue (ba (i))
Nākamais
Cits
Par i kā vesels skaitlis = 7 līdz 0 -1. Solis
initFifo. Enqueue (ba (i))
Nākamais
Beigt Ja
Nākamais
'Shift un XOR:
Aptumšot reģistru Tā kā UInteger = 0 ', aizpildiet platuma bitu reģistru ar nullēm.
Dariet, kamēr msgFifo. Count> 0
Dim poppedBit As Integer = CInt (reģistrēties >> (platums - 1)) un 1 'definēt pirms maiņu reģistra.
Dim shiftedBit kā baits = Convert. ToByte (msgFifo. Dequeue)
Ja initFifo. Count> 0 Tad
Dim b kā baits = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Beigt Ja
reģistrēties = reģistrēties << 1
register = register Vai shiftedBit
Ja poppedBit = 1 Tad
register = reģistrēt Xor poly
Beigt Ja
Loop
'Pēdējie reklāmguvumi:
Dim crc As UInteger = register 'Reģistrā ir atlikusī dalījuma == kontrolsumma daļa.
Ja reverseCrc Tad
crc = atstarot (crc, platums)
Beigt Ja
crc = crc Xor finalXor
crc = crc Un (& HFFFFFFFFUU >> (32 - platums)) 'maskē vismazāk nozīmīgos bitus.
Atgriezties crc
Beigu funkcija
