Ada banyak opsi untuk menghitung checksum CRC di Internet. Tapi apa sebenarnya checksum itu dan mengapa dihitung dengan cara ini? Mari kita cari tahu.
instruksi
Langkah 1
Pertama, mari kita mendapatkan sedikit teori. Jadi apa sebenarnya CRC itu? Singkatnya, ini adalah salah satu jenis perhitungan checksum. Checksum adalah metode untuk memeriksa integritas informasi yang diterima di sisi penerima saat mengirim melalui saluran komunikasi. Misalnya, salah satu pemeriksaan paling sederhana adalah dengan menggunakan bit paritas. Ini adalah ketika semua bit dari pesan yang dikirimkan dijumlahkan, dan jika jumlahnya ternyata genap, maka 0 ditambahkan ke akhir pesan, jika ganjil, maka 1. Saat menerima, jumlah dari bit pesan juga dihitung dan dibandingkan dengan bit paritas yang diterima. Jika berbeda, maka kesalahan terjadi selama transmisi dan informasi yang dikirimkan terdistorsi.
Tetapi metode mendeteksi adanya kesalahan ini sangat tidak informatif dan tidak selalu berhasil, karena jika beberapa bit pesan terdistorsi, paritas jumlah mungkin tidak berubah. Oleh karena itu, masih banyak lagi pemeriksaan "lanjutan", termasuk CRC.
Sebenarnya, CRC bukanlah penjumlahan, melainkan hasil pembagian sejumlah informasi (pesan informasi) dengan suatu konstanta, atau lebih tepatnya, sisa pembagian pesan dengan suatu konstanta. Namun, CRC juga secara historis disebut sebagai "checksum". Setiap bit pesan berkontribusi pada nilai CRC. Artinya, jika setidaknya satu bit dari pesan asli berubah selama transmisi, checksum juga akan berubah, dan secara signifikan. Ini adalah nilai tambah yang besar dari pemeriksaan semacam itu, karena memungkinkan Anda untuk menentukan dengan jelas apakah pesan asli terdistorsi selama transmisi atau tidak.
Langkah 2
Sebelum kita mulai menghitung CRC, diperlukan sedikit teori lagi.
Apa pesan aslinya harus jelas. Ini adalah urutan bit yang berdekatan dengan panjang sewenang-wenang.
Apa konstanta yang dengannya kita harus membagi pesan asli? Angka ini juga memiliki panjang berapa pun, tetapi biasanya kelipatan 1 byte digunakan - 8, 16 dan 32 bit. Hanya saja lebih mudah untuk menghitung, karena komputer bekerja dengan byte, bukan dengan bit.
Konstanta pembagi biasanya ditulis dalam bentuk polinomial (polinomial) seperti ini: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Di sini, derajat angka "x" berarti posisi satu bit dalam angka, mulai dari nol, dan bit paling signifikan menunjukkan derajat polinomial dan dibuang saat menafsirkan angka. Artinya, angka yang ditulis sebelumnya tidak lebih dari (1) 00000111 dalam biner, atau 7 dalam desimal. Dalam tanda kurung, saya menunjukkan angka paling signifikan yang tersirat dari angka tersebut.
Berikut contoh lain: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Biasanya beberapa polinomial standar digunakan untuk berbagai jenis CRC.
Langkah 3
Jadi bagaimana Anda menghitung checksum? Ada metode dasar - membagi pesan menjadi polinomial "langsung" - dan modifikasinya untuk mengurangi jumlah perhitungan dan, karenanya, mempercepat perhitungan CRC. Kami akan melihat metode dasar.
Secara umum, pembagian angka dengan polinomial dilakukan sesuai dengan algoritma berikut:
1) sebuah array (register) dibuat, diisi dengan nol, panjangnya sama dengan panjang lebar polinomial;
2) pesan asli dilengkapi dengan nol dalam bit paling tidak signifikan, dalam jumlah yang sama dengan jumlah bit polinomial;
3) satu bit paling signifikan dari pesan dimasukkan ke dalam bit paling signifikan dari register, dan satu bit dipindahkan dari bit paling signifikan dari register;
4) jika bit yang diperluas sama dengan "1", maka bit tersebut dibalik (operasi XOR, eksklusif OR) pada bit register yang sesuai dengan bit dalam polinomial;
5) jika masih ada bit dalam pesan, lanjutkan ke langkah 3);
6) ketika semua bit pesan masuk ke register dan diproses oleh algoritma ini, sisa pembagian tetap di register, yang merupakan checksum CRC.
Gambar tersebut menggambarkan pembagian urutan bit asli dengan angka (1) 00000111, atau polinomial x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Langkah 4
Ada beberapa sentuhan tambahan yang tersisa. Seperti yang mungkin Anda perhatikan, pesan dapat dibagi dengan nomor berapa pun. Bagaimana cara memilihnya? Ada sejumlah polinomial standar yang digunakan untuk menghitung CRC. Misalnya, untuk CRC32 mungkin 0x04C11DB7, dan untuk CRC16 mungkin 0x8005.
Selain itu, dalam register di awal perhitungan, Anda tidak dapat menulis angka nol, tetapi beberapa angka lainnya.
Juga, selama perhitungan, segera sebelum mengeluarkan checksum CRC akhir, mereka dapat dibagi dengan beberapa nomor lain.
Dan hal terakhir. Byte pesan saat menulis ke register dapat ditempatkan sebagai bit paling signifikan "maju", dan sebaliknya, yang paling tidak signifikan.
Langkah 5
Berdasarkan semua hal di atas, mari kita tulis fungsi. NET Basic yang menghitung checksum CRC dengan mengambil sejumlah parameter yang saya jelaskan di atas dan mengembalikan nilai CRC sebagai angka 32-bit yang tidak ditandatangani.
Fungsi Bersama Publik GetCrc (ByVal byte Sebagai Byte (), ByVal poli Sebagai UInteger, Lebar ByVal Opsional As Integer = 32, Opsional ByVal initReg As UInteger = & HFFFFFFFFUI, Opsional ByVal finalXor As UInteger = & HFFFFFFFFUI, Opsional ByVal ReverseBytes reverseCrc Sebagai Boolean = Benar) Sebagai UInteger
Dim widthInBytes Sebagai Integer = lebar / 8
'Tambahan lebar pesan dengan nol (perhitungan dalam byte):
ReDim Pertahankan byte (bytes. Length - 1 + widthInBytes)
'Buat sedikit antrian dari pesan:
Redupkan msgFifo Sebagai Antrian Baru (Dari Boolean) (bytes. Count * 8 - 1)
Untuk Setiap b Sebagai Byte Dalam byte
Redupkan Sebagai BitArray Baru ({b})
Jika reverseBytes Kemudian
Untuk i As Integer = 0 Sampai 7
msgFifo. Enqueue (ba (i))
Berikutnya
Lain
Untuk i As Integer = 7 Ke 0 Langkah -1
msgFifo. Enqueue (ba (i))
Berikutnya
Berakhir jika
Berikutnya
'Buat antrian dari bit pengisian awal register:
Redupkan initBytes Sebagai Byte () = BitConverter. GetBytes (initReg)
Dim initBytesDibalik Sebagai IEnumerable (Dari Byte) = (Dari b Sebagai Byte Dalam initBytes Ambil widthInBytes). Reverse
Redupkan initFifo Sebagai Antrian Baru (Dari Boolean) (lebar - 1)
Untuk Setiap b Sebagai Byte Di initBytesReversed
Redupkan Sebagai BitArray Baru ({b})
Jika Tidak reverseBytes Kemudian
Untuk i As Integer = 0 Sampai 7
initFifo. Enqueue (ba (i))
Berikutnya
Lain
Untuk i As Integer = 7 Ke 0 Langkah -1
initFifo. Enqueue (ba (i))
Berikutnya
Berakhir jika
Berikutnya
'Shift dan XOR:
Dim register As UInteger = 0 'isi lebar-bit register dengan nol.
Lakukan Sementara msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) Dan 1 'define before shift register.
Dim shiftBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Jika initFifo. Count> 0 Kemudian
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftBit = shiftBit Xor b
Berakhir jika
daftar = daftar << 1
register = register Atau shiftBit
Jika poppedBit = 1 Kemudian
register = register X atau poli
Berakhir jika
Lingkaran
'Konversi akhir:
Dim crc As UInteger = register 'Register berisi sisa pembagian == checksum.
Jika reverseCrc Maka
crc = mencerminkan (crc, lebar)
Berakhir jika
crc = crc Xatau finalXor
crc = crc Dan (& HFFFFFFFFUI >> (32 - lebar)) 'menutupi bit yang paling tidak signifikan.
Kembalikan crc
Fungsi Akhir
