Maraming mga pagpipilian para sa pagkalkula ng CRC Checksum sa Internet. Ngunit ano nga ba ang isang tsekum at kung bakit ito kinakalkula sa ganitong paraan? Alamin natin ito.
Panuto
Hakbang 1
Una, kumuha tayo ng kaunting teorya. Kaya't ano talaga ang CRC? Sa madaling salita, ito ay isa sa mga pagkakaiba-iba ng pagkalkula ng tsekum. Ang Checksum ay isang paraan ng pagsuri sa integridad ng natanggap na impormasyon sa panig ng tatanggap kapag nagpapadala sa mga channel ng komunikasyon. Halimbawa, ang isa sa pinakasimpleng tseke ay ang paggamit ng parity bit. Ito ay kapag ang lahat ng mga piraso ng naihatid na mensahe ay naibuo, at kung ang kabuuan ay naging pantay, pagkatapos ang 0 ay idinagdag sa dulo ng mensahe, kung ito ay kakaiba, pagkatapos ay 1. Kapag tumatanggap, ang kabuuan ng Ang mga piraso ng mensahe ay binibilang din at inihambing sa natanggap na parity bit. Kung magkakaiba ang mga ito, naganap ang mga pagkakamali sa panahon ng paghahatid at ang naihatid na impormasyon ay napangit.
Ngunit ang pamamaraang ito ng pagtuklas ng pagkakaroon ng mga pagkakamali ay napaka hindi nakakaalam at hindi palaging gumagana, dahil kung maraming mga piraso ng mensahe ang napangit, ang pagkakapareho ng kabuuan ay maaaring hindi mabago. Samakatuwid, maraming iba pang mga "advanced" na tseke, kasama ang CRC.
Sa katunayan, ang CRC ay hindi isang kabuuan, ngunit ang resulta ng paghati ng isang tiyak na dami ng impormasyon (mensahe ng impormasyon) ng isang pare-pareho, o sa halip, ang natitirang paghahati ng isang mensahe sa pamamagitan ng isang pare-pareho. Gayunpaman, ang CRC ay kasaysayan ding tinukoy bilang isang "checkum". Ang bawat piraso ng mensahe ay nag-aambag sa halaga ng CRC. Iyon ay, kung hindi bababa sa isang piraso ng orihinal na mensahe ang nagbabago sa panahon ng paghahatid, magbabago rin ang tsekum, at malaki. Ito ay isang malaking plus ng naturang tseke, dahil pinapayagan kang hindi malinaw na matukoy kung ang orihinal na mensahe ay napangit sa panahon ng paghahatid o hindi.
Hakbang 2
Bago namin simulang kalkulahin ang CRC, kailangan ng kaunti pang teorya.
Ano ang dapat na malinaw na ang orihinal na mensahe. Ito ay isang magkadugtong na pagkakasunud-sunod ng mga piraso ng di-makatwirang haba.
Ano ang pare-pareho kung saan natin dapat hatiin ang orihinal na mensahe? Ang bilang na ito ay mayroon ding anumang haba, ngunit kadalasan ang mga multiply ng 1 byte ay ginagamit - 8, 16 at 32 na piraso. Mas madali lang itong bilangin, dahil gumagana ang mga computer sa mga byte, hindi sa mga piraso.
Ang pare-pareho ng divisor ay karaniwang nakasulat bilang isang polynomial (polynomial) tulad nito: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Dito, ang degree ng bilang na "x" ay nangangahulugang ang posisyon ng one-bit sa numero, simula sa zero, at ang pinaka-makabuluhang bit ay nagpapahiwatig ng antas ng polynomial at itinapon kapag binibigyang kahulugan ang numero. Iyon ay, ang dating nakasulat na numero ay walang hihigit sa (1) 00000111 sa binary, o 7 sa decimal. Sa panaklong, ipinahiwatig ko ang ipinahiwatig na pinaka makabuluhang digit ng numero.
Narito ang isa pang halimbawa: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Kadalasan ang ilang karaniwang mga polynomial ay ginagamit para sa iba't ibang uri ng CRCs.
Hakbang 3
Kaya paano mo makakalkula ang tsekum? Mayroong pangunahing pamamaraan - paghahati ng isang mensahe sa isang "pangunahin" - at mga pagbabago nito upang mabawasan ang bilang ng mga kalkulasyon at, nang naaayon, mapabilis ang pagkalkula ng CRC. Titingnan namin ang pangunahing pamamaraan.
Sa pangkalahatan, ang paghahati ng isang numero ng isang polynomial ay ginaganap ayon sa sumusunod na algorithm:
1) isang array (rehistro) ay nilikha, puno ng mga zero, pantay ang haba sa haba ng lapad ng polynomial;
2) ang orihinal na mensahe ay pupunan ng mga zero sa hindi gaanong makabuluhang mga piraso, sa halagang katumbas ng bilang ng mga piraso ng polynomial;
3) ang isang pinaka-makabuluhang piraso ng mensahe ay ipinasok sa hindi gaanong makabuluhang piraso ng pagrehistro, at ang isang piraso ay inilipat mula sa pinaka-makabuluhang piraso ng rehistro;
4) kung ang pinahabang bit ay katumbas ng "1", kung gayon ang mga piraso ay baligtad (operasyon ng XOR, eksklusibong O) sa mga rehistro na piraso na tumutugma sa mga nasa polynomial;
5) kung may mga piraso pa rin sa mensahe, pumunta sa hakbang 3);
6) kapag ang lahat ng mga piraso ng mensahe ay pumasok sa rehistro at naproseso ng algorithm na ito, ang natitirang bahagi ng dibisyon ay mananatili sa rehistro, na kung saan ay ang CRC checkum.
Inilalarawan ng pigura ang paghahati ng orihinal na pagkakasunud-sunod ng bit sa pamamagitan ng bilang (1) 00000111, o ng polynomial x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Hakbang 4
Mayroong isang pares ng mga karagdagang mga touch na natitira. Tulad ng napansin mo, ang mensahe ay maaaring nahahati sa anumang numero. Paano ito pipiliin? Mayroong isang bilang ng mga karaniwang polynomial na ginagamit upang makalkula ang CRC. Halimbawa, para sa CRC32 maaaring ito ay 0x04C11DB7, at para sa CRC16 maaaring ito ay 0x8005.
Bilang karagdagan, sa pagrehistro sa simula ng pagkalkula, maaari kang magsulat hindi mga zero, ngunit ilang iba pang numero.
Gayundin, sa mga pagkalkula, kaagad bago mag-isyu ng pangwakas na CRC checkum, maaari silang hatiin sa ilang iba pang numero.
At ang huling bagay. Ang mga byte ng mensahe kapag ang pagsusulat sa rehistro ay maaaring ilagay bilang ang pinaka makabuluhang bit na "pasulong", at sa kabaligtaran, ang hindi gaanong makabuluhan.
Hakbang 5
Batay sa lahat ng nasa itaas, magsulat tayo ng isang Basic. NET function na kinakalkula ang CRC checkum sa pamamagitan ng pagkuha ng isang bilang ng mga parameter na inilarawan ko sa itaas at ibalik ang halaga ng CRC bilang isang 32-bit na hindi naka-sign na numero.
Public Shared Function GetCrc (ByVal bytes Bilang Byte (), ByVal poly Bilang UInteger, Opsyonal na ByVal na lapad Bilang Integer = 32, Opsyonal na ByVal initReg Bilang UInteger = & HFFFFFFFFUI, Opsyonal na ByVal finalXor Bilang UInteger = & HFFFFFFFFUI, Optional ByVal ByVal reverseCrc Bilang Boolean = Totoo) Bilang UInteger
Dim lapadInBytes Bilang Integer = lapad / 8
'Karagdagan ang lapad ng mensahe ng mga zero (pagkalkula sa mga byte):
Pinapanatili ang ReDim bytes (bytes. Haba - 1 + lapadInBytes)
'Lumikha ng kaunting pila mula sa mensahe:
Malabo ang msgFifo Bilang Bagong Queue (Ng Boolean) (bytes. Count * 8 - 1)
Para sa bawat b Bilang Byte Sa byte
Dim ba Bilang Bagong BitArray ({b})
Kung reverseBytes Pagkatapos
Para sa i Bilang Integer = 0 hanggang 7
msgFifo. Enqueue (ba (i))
Susunod
Iba pa
Para sa i Bilang Integer = 7 Sa 0 Hakbang -1
msgFifo. Enqueue (ba (i))
Susunod
Tapusin kung
Susunod
'Lumikha ng isang pila mula sa paunang mga piraso ng pagpuno ng rehistro:
Dim initBytes Bilang Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (Mula sa b As Byte In initBytes Kumuha ng widthInBytes). Readse
Dim initFifo Bilang Bagong pila (Ng Boolean) (lapad - 1)
Para sa bawat b Bilang Byte Sa initBytesReversed
Dim ba Bilang Bagong BitArray ({b})
Kung Hindi baligtarin Pagkatapos
Para sa i Bilang Integer = 0 hanggang 7
initFifo. Enqueue (ba (i))
Susunod
Iba pa
Para sa i Bilang Integer = 7 Sa 0 Hakbang -1
initFifo. Enqueue (ba (i))
Susunod
Tapusin kung
Susunod
'Shift at XOR:
Dim magparehistro Bilang UInteger = 0 'punan ang lapad-bit na pagrehistro sa mga zero.
Gawin Habang msgFifo. Count> 0
Dim poppedBit As Integer = CInt (rehistro >> (lapad - 1)) At 1 'tukuyin bago ang rehistro ng shift.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Kung initFifo. Count> 0 Pagkatapos
Dim b Bilang Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Tapusin kung
magparehistro = magparehistro << 1
magparehistro = magparehistro O shiftedBit
Kung poppedBit = 1 Kung gayon
magparehistro = magparehistro Xor poly
Tapusin kung
Loop
'Pangwakas na mga conversion:
Dim crc Bilang UInteger = magparehistro 'Naglalaman ang rehistro ng natitirang bahagi ng == checkum.
Kung reverseCrc Pagkatapos
crc = sumasalamin (crc, lapad)
Tapusin kung
crc = crc Xor finalXor
crc = crc At (& HFFFFFFFFUI >> (32 - lapad)) 'takpan ang hindi gaanong makabuluhang mga piraso.
Ibalik ang crc
Tapusin ang Pag-andar
