CRC Sağlama Toplamını Hesaplamak Ne Kadar Kolay (CRC32 - CRC16 - CRC8)

İçindekiler:

CRC Sağlama Toplamını Hesaplamak Ne Kadar Kolay (CRC32 - CRC16 - CRC8)
CRC Sağlama Toplamını Hesaplamak Ne Kadar Kolay (CRC32 - CRC16 - CRC8)

Video: CRC Sağlama Toplamını Hesaplamak Ne Kadar Kolay (CRC32 - CRC16 - CRC8)

Video: CRC Sağlama Toplamını Hesaplamak Ne Kadar Kolay (CRC32 - CRC16 - CRC8)
Video: 57. CRC алгоритм (Урок 48. Теория) 2024, Mart
Anonim

İnternette CRC sağlama toplamını hesaplamak için birçok seçenek vardır. Ancak, sağlama toplamı tam olarak nedir ve neden bu şekilde hesaplanır? Anlayalım.

CRC sağlama toplamını hesaplamak ne kadar kolay (CRC32 - CRC16 - CRC8)
CRC sağlama toplamını hesaplamak ne kadar kolay (CRC32 - CRC16 - CRC8)

Talimatlar

Aşama 1

İlk olarak, biraz teori alalım. Peki CRC tam olarak nedir? Kısacası, bu sağlama toplamı hesaplama çeşitlerinden biridir. Sağlama toplamı, iletişim kanalları üzerinden iletirken alıcı tarafında alınan bilgilerin bütünlüğünü kontrol etme yöntemidir. Örneğin, en basit kontrollerden biri eşlik bitini kullanmaktır. Bu, iletilen mesajın tüm bitlerinin toplandığı ve toplamın çift olduğu ortaya çıkarsa, mesajın sonuna 0, tek ise 1 eklenir. mesaj bitleri de sayılır ve alınan eşlik biti ile karşılaştırılır. Farklılarsa, iletim sırasında hatalar meydana geldi ve iletilen bilgiler bozuldu.

Ancak hataların varlığını tespit etmenin bu yöntemi çok bilgilendirici değildir ve her zaman çalışmaz, çünkü mesajın birkaç biti bozulursa, toplamın paritesi değişmeyebilir. Bu nedenle, CRC dahil olmak üzere daha birçok "gelişmiş" kontrol vardır.

Aslında, CRC bir toplam değil, belirli bir miktardaki bilginin (bilgi mesajı) bir sabite bölünmesinin veya daha doğrusu bir mesajın bir sabite bölünmesinin geri kalanının sonucudur. Bununla birlikte, CRC'ye tarihsel olarak "sağlama toplamı" da denir. Mesajın her biti CRC değerine katkıda bulunur. Yani, iletim sırasında orijinal mesajın en az bir biti değişirse, sağlama toplamı da önemli ölçüde değişecektir. Bu, böyle bir kontrolün büyük bir artısıdır, çünkü orijinal mesajın iletim sırasında bozulup bozulmadığını net bir şekilde belirlemenize izin verir.

Adım 2

CRC'yi hesaplamaya başlamadan önce, biraz daha teoriye ihtiyaç var.

Orijinal mesajın ne olduğu açık olmalıdır. Bu, keyfi uzunluktaki bitlerin bitişik bir dizisidir.

Orijinal mesajı bölmemiz gereken sabit nedir? Bu sayı da herhangi bir uzunluktadır, ancak genellikle 1 baytın katları kullanılır - 8, 16 ve 32 bit. Saymak daha kolay çünkü bilgisayarlar bitlerle değil baytlarla çalışır.

Bölen sabiti genellikle şu şekilde bir polinom (polinom) olarak yazılır: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Burada, "x" sayısının derecesi, sıfırdan başlayarak sayıdaki bir bitin konumu anlamına gelir ve en önemli bit, polinomun derecesini belirtir ve sayı yorumlanırken atılır. Yani, daha önce yazılan sayı ikili olarak (1) 00000111 veya ondalık olarak 7'den başka bir şey değildir. Parantez içinde, sayının ima edilen en anlamlı basamağını belirttim.

İşte başka bir örnek: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.

Genellikle farklı CRC türleri için bazı standart polinomlar kullanılır.

Aşama 3

Peki, sağlama toplamını nasıl hesaplarsınız? Temel bir yöntem var - bir mesajı bir polinom "kafaya" bölmek - ve hesaplama sayısını azaltmak ve buna bağlı olarak CRC hesaplamasını hızlandırmak için modifikasyonları. Temel yönteme bakacağız.

Genel olarak, bir sayının bir polinomla bölünmesi aşağıdaki algoritmaya göre yapılır:

1) polinom genişliğinin uzunluğuna eşit uzunlukta sıfırlarla doldurulmuş bir dizi (kayıt) oluşturulur;

2) orijinal mesaj, polinomun bit sayısına eşit bir miktarda, en az anlamlı bitlerde sıfırlarla tamamlanır;

3) mesajın en anlamlı biti kaydın en az anlamlı bitine girilir ve bir bit kaydın en anlamlı bitinden taşınır;

4) genişletilmiş bit "1"e eşitse, o zaman polinomdakilere karşılık gelen kayıt bitlerinde bitler ters çevrilir (XOR işlemi, özel VEYA);

5) mesajda hala bitler varsa, adım 3'e gidin);

6) Mesajın tüm bitleri kayıt defterine girdiğinde ve bu algoritma tarafından işlendiğinde, bölümün geri kalanı, CRC sağlama toplamı olan kayıtta kalır.

Şekil, orijinal bit dizisinin (1) 00000111 sayısına veya x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0 polinomuna bölünmesini göstermektedir.

CRC hesaplamasının şematik gösterimi
CRC hesaplamasının şematik gösterimi

4. Adım

Birkaç ek dokunuş kaldı. Fark etmiş olabileceğiniz gibi, mesaj herhangi bir sayıya bölünebilir. Nasıl seçilir? CRC'yi hesaplamak için kullanılan bir dizi standart polinom vardır. Örneğin, CRC32 için 0x04C11DB7 ve CRC16 için 0x8005 olabilir.

Ayrıca, hesaplamanın başlangıcındaki kayıt defterine sıfır değil, başka bir sayı yazabilirsiniz.

Ayrıca, hesaplamalar sırasında, son CRC sağlama toplamının yayınlanmasından hemen önce, bunlar başka bir sayıya bölünebilir.

Ve son şey. Kayda yazarken mesajın baytları, en önemli "ileri" biti olarak yerleştirilebilir ve bunun tersi, en az anlamlı olanı olabilir.

Adım 5

Yukarıdakilerin hepsinden yola çıkarak, yukarıda anlattığım bir dizi parametreyi alıp CRC değerini 32-bit işaretsiz sayı olarak döndürerek CRC sağlama toplamını hesaplayan bir Basic. NET fonksiyonu yazalım.

Genel Paylaşılan İşlev GetCrc (ByVal bayt As Byte (), ByVal poly As UInteger, Opsiyonel ByVal genişlik As Integer = 32, Opsiyonel ByVal initReg As UInteger = & HFFFFFFFFUI, Opsiyonel ByVal finalXor As UInteger = & HFFFFFFFFUI, Opsiyonel ByVal reverseBytes, Opsiyonel Boolean ByV ReverseCrc As Boolean = True) As UInteger

Dim widthInBytes As Integer = genişlik / 8

'Mesaj genişliğini sıfırlarla tamamlayın (bayt cinsinden hesaplama):

ReDim Baytları koru (bytes. Length - 1 + widthInBytes)

'Mesajdan bir bit kuyruğu oluşturun:

Dim msgFifo As New Queue (Boolean) (bytes. Count * 8 - 1)

Her b için Bayt Olarak Bayt Olarak

Yeni BitArray Olarak Dim ba ({b})

Eğer tersBytes ise

i için Tamsayı = 0 - 7

msgFifo. Enqueue (ba (i))

Sonraki

Başka

i için As Tamsayı = 7'den 0'a Adım -1

msgFifo. Enqueue (ba (i))

Sonraki

Bitir

Sonraki

'Kaydın ilk doldurma bitlerinden bir sıra oluşturun:

Bayt Olarak Dim initBytes () = BitConverter. GetBytes (initReg)

Dim initBytesReversed As IEnumerable (Of Byte) = (initBytes'ta B As Byte'dan widthInBytes Al). Reverse

Dim initFifo As New Queue (Boolean) (genişlik - 1)

Her b için initBytesReversed Olarak Bayt Olarak

Yeni BitArray Olarak Dim ba ({b})

ReverseBytes Değilse O Zaman

i için Tamsayı = 0 - 7

initFifo. Enqueue (ba (i))

Sonraki

Başka

i için As Tamsayı = 7'den 0'a Adım -1

initFifo. Enqueue (ba (i))

Sonraki

Bitir

Sonraki

'Üst Karakter ve XOR:

Dim register UInteger = 0 olarak genişlik-bit registerını sıfırlarla doldurun.

msgFifo. Count> 0 iken yapın

Dim poppedBit As Integer = CInt (kayıt >> (genişlik - 1)) Ve vardiya kaydından önce 1 'tanımlayın.

Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)

Eğer initFifo. Count> 0 ise

Dim b As Byte = Convert. ToByte (initFifo. Dequeue)

shiftedBit = shiftedBit Xor b

Bitir

kayıt = kayıt << 1

register = register Veya shiftedBit

Eğer poppedBit = 1 ise

register = Xor poly'i kaydet

Bitir

Döngü

'Son dönüşümler:

Dim crc As UInteger = register 'Kayıt bölümü == sağlama toplamının geri kalanını içerir.

Eğer tersCrc ise

crc = yansıt (crc, genişlik)

Bitir

crc = crc Xor finalXor

crc = crc Ve (& HFFFFFFFFUI >> (32 - genişlik)) 'en az anlamlı bitleri maskeleyin.

dönüş crc

Bitiş İşlevi

Önerilen: