Terdapat banyak pilihan untuk mengira checksum CRC di Internet. Tetapi apa sebenarnya checksum dan mengapa dikira dengan cara ini? Mari kita fikirkan.
Arahan
Langkah 1
Pertama, mari kita dapatkan sedikit teori. Jadi apa sebenarnya CRC? Ringkasnya, ini adalah salah satu jenis pengiraan checksum. Checksum adalah kaedah memeriksa integriti maklumat yang diterima di sisi penerima semasa menghantar melalui saluran komunikasi. Sebagai contoh, salah satu pemeriksaan paling mudah adalah menggunakan bit parity. Ini adalah ketika semua bit mesej yang dikirim dijumlahkan, dan jika jumlahnya berubah menjadi genap, maka 0 ditambahkan ke akhir pesan, jika itu ganjil, maka 1. Semasa menerima, jumlah bit mesej juga dikira dan dibandingkan dengan bit pariti yang diterima. Sekiranya mereka berbeza, maka kesalahan berlaku semasa penghantaran dan maklumat yang dihantar diputarbelitkan.
Tetapi kaedah ini untuk mengesan kehadiran kesalahan sangat tidak berinformasi dan tidak selalu berfungsi, kerana jika beberapa bit mesej diputarbelitkan, paritas jumlahnya mungkin tidak berubah. Oleh itu, terdapat banyak lagi pemeriksaan "lanjutan", termasuk CRC.
Sebenarnya, CRC bukan jumlah, tetapi hasil membagi sejumlah maklumat (mesej maklumat) dengan pemalar, atau lebih tepatnya, selebihnya membagi mesej dengan pemalar. Walau bagaimanapun, CRC juga secara historis disebut sebagai "checksum". Setiap bit mesej menyumbang kepada nilai CRC. Iaitu, jika sekurang-kurangnya satu bit mesej asal berubah semasa penghantaran, checksum juga akan berubah, dan ketara. Ini adalah nilai tambah yang besar, kerana ia membolehkan anda menentukan dengan jelas bahawa mesej asal telah diputarbelitkan semasa penghantaran atau tidak.
Langkah 2
Sebelum kita mula mengira CRC, sedikit lagi teori diperlukan.
Apakah mesej asal harus jelas. Ini adalah urutan bersebelahan panjang panjang sewenang-wenangnya.
Apakah pemalar di mana kita harus membahagikan mesej asal? Nombor ini juga panjangnya, tetapi biasanya gandaan 1 bait digunakan - 8, 16 dan 32 bit. Cukup mudah untuk dikira, kerana komputer berfungsi dengan bait, bukan dengan bit.
Pemalar pembahagi biasanya ditulis sebagai polinomial (polinomial) seperti ini: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Di sini, darjah nombor "x" bermaksud kedudukan satu-bit dalam nombor, bermula dari sifar, dan bit yang paling ketara menunjukkan tahap polinomial dan dibuang ketika menafsirkan nombor tersebut. Maksudnya, nombor yang ditulis sebelumnya tidak lebih daripada (1) 00000111 dalam perduaan, atau 7 dalam perpuluhan. Dalam tanda kurung, saya menunjukkan digit nombor paling signifikan tersirat.
Inilah contoh lain: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Biasanya beberapa polinomial standard digunakan untuk pelbagai jenis CRC.
Langkah 3
Jadi bagaimana anda mengira checksum? Terdapat kaedah asas - membahagikan mesej menjadi "head-on" polinomial - dan pengubahsuaiannya untuk mengurangkan jumlah pengiraan dan, dengan itu, mempercepat pengiraan CRC. Kami akan melihat kaedah asas.
Secara umum, pembahagian nombor dengan polinomial dilakukan mengikut algoritma berikut:
1) tatasusunan (register) dibuat, diisi dengan angka nol, panjangnya sama dengan panjang lebar polinomial;
2) mesej asal ditambah dengan angka nol dalam bit paling kecil, dalam jumlah yang sama dengan bilangan bit polinomial;
3) satu bit mesej yang paling penting dimasukkan ke dalam bit yang paling tidak penting, dan satu bit dipindahkan dari bit yang paling penting;
4) jika bit yang diperpanjang sama dengan "1", maka bit terbalik (operasi XOR, eksklusif ATAU) pada bit register yang sesuai dengan bit di polinomial;
5) jika masih ada bit dalam mesej, pergi ke langkah 3);
6) apabila semua bit pesan masuk ke daftar dan diproses oleh algoritma ini, bahagian yang tinggal selebihnya tetap dalam daftar, yang merupakan checksum CRC.
Rajah menggambarkan pembahagian urutan bit asal dengan nombor (1) 00000111, atau polinomial x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Langkah 4
Terdapat beberapa sentuhan tambahan yang tersisa. Seperti yang anda perhatikan, mesej boleh dibahagi dengan nombor apa pun. Bagaimana memilihnya? Terdapat sebilangan polinomial standard yang digunakan untuk mengira CRC. Sebagai contoh, untuk CRC32 mungkin 0x04C11DB7, dan untuk CRC16 mungkin 0x8005.
Di samping itu, dalam daftar pada awal pengiraan, anda boleh menulis bukan angka nol, tetapi beberapa nombor lain.
Juga, semasa pengiraan, tepat sebelum mengeluarkan checksum CRC terakhir, mereka dapat dibahagi dengan beberapa nombor lain.
Dan perkara terakhir. Bytes mesej semasa menulis ke daftar boleh diletakkan sebagai bit "ke depan" yang paling penting, dan sebaliknya, yang paling penting.
Langkah 5
Berdasarkan semua perkara di atas, mari tulis fungsi. NET Asas yang mengira checksum CRC dengan mengambil sebilangan parameter yang saya jelaskan di atas dan mengembalikan nilai CRC sebagai nombor tanpa tanda 32-bit.
Fungsi Dikongsi Umum GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Opsional ByVal width As Integer = 32, Opsyen ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF reverseCrc As Boolean = True) Sebagai UInteger
Dim lebarInBytes Sebagai Integer = lebar / 8
'Lengkapkan lebar mesej dengan angka nol (pengiraan dalam bait):
ReDim Preserve bytes (byte. Panjang - 1 + lebarInBytes)
'Buat sedikit barisan dari mesej:
Dim msgFifo Sebagai Barisan Baru (Of Boolean) (byte. Jumlah * 8 - 1)
Untuk Setiap b Byte By Byte
Dim ba Sebagai BitArray Baru ({b})
Sekiranya terbalikBait Kemudian
Untuk i Sebagai Integer = 0 Hingga 7
msgFifo. Enqueue (ba (i))
Seterusnya
Lain
Untuk i As Integer = 7 Hingga 0 Langkah -1
msgFifo. Enqueue (ba (i))
Seterusnya
Tamat Sekiranya
Seterusnya
'Buat barisan dari bit pengisian awal daftar:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (Dari b As Byte In inBytes Ambil lebarInBytes).
Dim initFifo Sebagai Barisan Baru (Of Boolean) (lebar - 1)
Untuk Setiap b Sebagai Bait Dalam InitBytesReversed
Dim ba Sebagai BitArray Baru ({b})
Sekiranya Tidak Membalikkan Kemudian
Untuk i Sebagai Integer = 0 Hingga 7
initFifo. Enqueue (ba (i))
Seterusnya
Lain
Untuk i As Integer = 7 Hingga 0 Langkah -1
initFifo. Enqueue (ba (i))
Seterusnya
Tamat Sekiranya
Seterusnya
'Shift dan XOR:
Dim register Sebagai UInteger = 0 'isi register lebar-bit dengan angka nol.
Lakukan Semasa msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) Dan 1 'tentukan sebelum shift shift.
Dim shiftBit As Byte = Tukar. ToByte (msgFifo. Dequeue)
Sekiranya initFifo. Count> 0 Kemudian
Dim b As Byte = Tukar. ToByte (initFifo. Dequeue)
shiftBit = shiftBit Xor b
Tamat Sekiranya
daftar = daftar << 1
register = register Atau shiftBit
Sekiranya poppedBit = 1 Kemudian
daftar = daftar Xor poly
Tamat Sekiranya
Gelung
'Penukaran akhir:
Dim crc Sebagai UInteger = register 'Daftar mengandungi bahagian lain == checksum.
Sekiranya terbalikCrc Kemudian
crc = pantulan (crc, lebar)
Tamat Sekiranya
crc = crc Xor finalXor
crc = crc Dan (& HFFFFFFFFUI >> (32 - lebar)) 'tutup bit yang paling tidak signifikan.
Pulangkan crc
Fungsi Akhir
