Bagaimana cara menghitung checksum CRC32?

Mungkin saya hanya tidak melihatnya, tetapi CRC32 tampaknya rumit, atau tidak cukup dijelaskan di mana pun yang dapat saya temukan di web.

Saya mengerti bahwa itu adalah sisa dari pembagian aritmatika berbasis non-carry dari nilai pesan, dibagi dengan polinomial (generator), tetapi implementasi sebenarnya dari itu luput dari saya.

Saya telah membaca A Painless Guide To CRC Error Detection Algorithms , dan saya harus mengatakan itu bukan tanpa rasa sakit. Ini membahas teori dengan cukup baik, tetapi penulis tidak pernah sampai pada pertanyaan sederhana "ini dia." Dia memang mengatakan apa parameter untuk algoritma CRC32 standar, tetapi dia lalai menjelaskan dengan jelas bagaimana Anda mendapatkannya.

Bagian yang membuat saya tertarik adalah ketika dia mengatakan "ini dia" dan kemudian menambahkan, "oh ngomong-ngomong, ini bisa dibalik atau dimulai dengan kondisi awal yang berbeda," dan tidak memberikan jawaban yang jelas tentang cara akhirnya menghitung checksum CRC32 mengingat semua perubahan yang baru saja dia tambahkan.

• Apakah ada penjelasan yang lebih sederhana tentang bagaimana CRC32 dihitung?

Saya mencoba membuat kode dalam C bagaimana tabel terbentuk:

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

tetapi ini tampaknya menghasilkan nilai yang tidak sesuai dengan nilai yang saya temukan di tempat lain di Internet. Saya dapat menggunakan nilai yang saya temukan online, tetapi saya ingin memahami bagaimana nilai itu dibuat.

Bantuan apa pun untuk menyelesaikan angka-angka yang sangat membingungkan ini akan sangat kami hargai.

Polinomial untuk CRC32 adalah:

x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

• Wikipedia
• Perhitungan CRC

Atau dalam hex dan biner:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

Istilah tertinggi (x ³² ) biasanya tidak ditulis secara eksplisit, sehingga dapat direpresentasikan dalam hex seperti

0x 04 C1 1D B7

Jangan ragu untuk menghitung 1 dan 0, tetapi Anda akan menemukannya cocok dengan polinomial, di mana 1bit 0 (atau bit pertama) danx bit 1 (atau bit kedua).

Mengapa polinomial ini? Karena perlu ada polinomial standar yang diberikan dan standar itu ditetapkan oleh IEEE 802.3. Juga sangat sulit untuk menemukan polinomial yang mendeteksi kesalahan bit berbeda secara efektif.

Anda dapat menganggap CRC-32 sebagai rangkaian "Aritmatika Biner tanpa Pengangkutan", atau pada dasarnya "operasi XOR dan shift". Ini secara teknis disebut Aritmatika Polinomial.

• CRC primer, Bab 5

Untuk lebih memahaminya, pikirkan perkalian ini:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Jika kita mengasumsikan x adalah basis 2 maka kita mendapatkan:

x^7 + x^3 + x^2 + x^1 + x^0

• CRC primer Chp.5

Mengapa? Karena 3x ^ 3 adalah 11x ^ 11 (tapi kita hanya membutuhkan 1 atau 0 digit awal) jadi kita bawa:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

Tetapi ahli matematika mengubah aturan tersebut sehingga menjadi mod 2. Jadi pada dasarnya semua polinomial biner mod 2 hanyalah penjumlahan tanpa membawa atau XOR. Jadi persamaan asli kita terlihat seperti ini:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

Saya tahu ini adalah lompatan keyakinan tetapi ini di luar kemampuan saya sebagai programmer garis. Jika Anda adalah siswa atau insinyur CS inti, saya menantang untuk memecahnya. Semua orang akan mendapat manfaat dari analisis ini.

Jadi untuk mengerjakan contoh lengkap:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Sekarang kita membagi Pesan yang ditambah dengan Poly menggunakan aritmatika CRC. Ini adalah divisi yang sama seperti sebelumnya:

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

Pembagian menghasilkan hasil bagi, yang kita buang, dan sisanya, yang merupakan checksum yang dihitung. Ini mengakhiri perhitungan. Biasanya, checksum kemudian ditambahkan ke pesan dan hasilnya dikirim. Dalam hal ini transmisi akan menjadi: 11010110111110.

• CRC primer, Bab 7

Gunakan hanya angka 32-bit sebagai pembagi Anda dan gunakan seluruh aliran Anda sebagai dividen. Buang hasil bagi dan simpan sisanya. Tack sisanya di akhir pesan Anda dan Anda memiliki CRC32.

Ulasan pria rata-rata:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER

1. Ambil 32 bit pertama.
2. Ganti bit
3. Jika 32 bit kurang dari DIVISOR, lanjutkan ke langkah 2.
4. XOR 32 bit oleh DIVISOR. Lanjutkan ke langkah 2.

(Perhatikan bahwa aliran harus dapat dibagi dengan 32 bit atau harus diisi. Misalnya, aliran ANSI 8-bit harus di-padded. Juga di akhir aliran, pembagian dihentikan.)

Untuk IEEE802.3, CRC-32. Pikirkan seluruh pesan sebagai aliran bit serial, tambahkan 32 angka nol di akhir pesan. Selanjutnya, Anda HARUS membalik bit SETIAP byte pesan dan melakukan 1 untuk melengkapi 32 bit pertama. Sekarang bagi dengan polinomial CRC-32, 0x104C11DB7. Akhirnya, Anda harus 1 melengkapi sisa 32-bit dari pembagian ini bit-reverse masing-masing dari 4 byte sisanya. Ini menjadi CRC 32-bit yang ditambahkan ke akhir pesan.

Alasan untuk prosedur aneh ini adalah bahwa implementasi Ethernet pertama akan membuat pesan menjadi serial satu byte pada satu waktu dan mengirimkan bit paling signifikan dari setiap byte terlebih dahulu. Aliran bit serial kemudian melewati komputasi register geser CRC-32 serial, yang hanya dilengkapi dan dikirim melalui kabel setelah pesan selesai. Alasan untuk melengkapi 32 bit pertama dari pesan tersebut adalah agar Anda tidak mendapatkan CRC nol semua meskipun pesan tersebut semuanya nol.

CRC sangat sederhana; Anda mengambil polinomial yang direpresentasikan sebagai bit dan data, dan membagi polinomial tersebut menjadi data (atau Anda merepresentasikan data sebagai polinomial dan melakukan hal yang sama). Sisanya, antara 0 dan polinomial adalah CRC. Kode Anda agak sulit dipahami, sebagian karena tidak lengkap: temp dan testcrc tidak dideklarasikan, jadi tidak jelas apa yang diindeks, dan berapa banyak data yang berjalan melalui algoritme.

Cara untuk memahami CRC adalah dengan mencoba menghitung beberapa menggunakan potongan data pendek (16 bit atau lebih) dengan polinomial pendek - 4 bit, mungkin. Jika Anda berlatih dengan cara ini, Anda akan benar-benar memahami bagaimana Anda bisa melakukan pengkodeannya.

Jika Anda sering melakukannya, CRC cukup lambat untuk dihitung dalam perangkat lunak. Komputasi perangkat keras jauh lebih efisien, dan hanya membutuhkan beberapa gerbang.

Selain pemeriksaan redundansi Siklik Wikipedia dan artikel Perhitungan CRC , saya menemukan sebuah makalah berjudul Reversing CRC - Theory and Practice ^* untuk menjadi referensi yang baik.

Pada dasarnya ada tiga pendekatan untuk menghitung CRC: pendekatan aljabar, pendekatan berorientasi bit, dan pendekatan berbasis tabel. Dalam Reversing CRC - Theory and Practice ^* , masing-masing dari tiga algoritma / pendekatan ini dijelaskan dalam teori disertai dalam LAMPIRAN dengan implementasi untuk CRC32 dalam bahasa pemrograman C.

^{* PDF Link
CRC Pembalik - Teori dan Praktek.
Laporan Publik HU Berlin
SAR-PR-2006-05
Mei 2006
Penulis:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich}

Saya menghabiskan waktu untuk mencoba mengungkap jawaban atas pertanyaan ini, dan akhirnya saya menerbitkan tutorial tentang CRC-32 hari ini: tutorial hash CRC-32 - Komunitas AutoHotkey

Dalam contoh ini, saya menunjukkan cara menghitung hash CRC-32 untuk string ASCII 'abc':

calculate the CRC-32 hash for the ASCII string 'abc':

inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000

'CRC division':
01111001101110010011100111111111000000000000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111000100010010111111010010010110
  100000100110000010001110110110111
  ---------------------------------
   110000001000101011101001001000010
   100000100110000010001110110110111
   ---------------------------------
    100001011101010011001111111101010
    100000100110000010001110110110111
    ---------------------------------
         111101101000100000100101110100000
         100000100110000010001110110110111
         ---------------------------------
          111010011101000101010110000101110
          100000100110000010001110110110111
          ---------------------------------
           110101110110001110110001100110010
           100000100110000010001110110110111
           ---------------------------------
            101010100000011001111110100001010
            100000100110000010001110110110111
            ---------------------------------
              101000011001101111000001011110100
              100000100110000010001110110110111
              ---------------------------------
                100011111110110100111110100001100
                100000100110000010001110110110111
                ---------------------------------
                    110110001101101100000101110110000
                    100000100110000010001110110110111
                    ---------------------------------
                     101101010111011100010110000001110
                     100000100110000010001110110110111
                     ---------------------------------
                       110111000101111001100011011100100
                       100000100110000010001110110110111
                       ---------------------------------
                        10111100011111011101101101010011

remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2

Lalu selalu ada Rosetta Code, yang menunjukkan crc32 diimplementasikan dalam banyak bahasa komputer. https://rosettacode.org/wiki/CRC-32 dan memiliki tautan ke banyak penjelasan dan implementasi.

Untuk mengurangi crc32 untuk menerima pengingat, Anda perlu:

1. Balikkan bit pada setiap byte
2. xor empat byte pertama dengan 0xFF (ini untuk menghindari kesalahan pada 0 di depan)
3. Tambahkan padding di akhir (ini untuk membuat 4 byte terakhir mengambil bagian dalam hash)
4. Hitung pengingat
5. Balikkan bit lagi
6. atau hasilnya lagi.

Dalam kode ini adalah:

func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

di mana reminderIEEE adalah pengingat murni di GF (2) [x]