Belki de ben göremiyorum, ancak CRC32 ya gereksiz yere karmaşık görünüyor ya da web'de bulabildiğim her yerde yeterince açıklanmamış.
Bunun, mesaj değerinin taşıma tabanlı olmayan aritmetik bölünmesinden elde edilen kalanın (üreteç) polinomuna bölünmesi olduğunu anlıyorum, ancak bunun gerçek uygulaması beni şaşırtıyor.
A Painless Guide To CRC Error Detection Algorithms]1 kitabını okudum ve acısız olmadığını söylemeliyim. Teorinin üzerinden oldukça iyi geçiyor, ancak yazar asla basit bir "işte bu " Standart CRC32 algoritması için parametrelerin ne olduğunu söylüyor, ancak buna nasıl ulaşacağınızı açıkça ortaya koymayı ihmal ediyor.
Beni etkileyen kısım, "işte bu" dedikten sonra "bu arada, tersine çevrilebilir veya farklı başlangıç koşullarıyla başlatılabilir" diye eklemesi ve eklediği tüm değişiklikler göz önüne alındığında CRC32 sağlama toplamını hesaplamanın nihai yolunun ne olduğuna dair net bir cevap vermemesi.
Tablonun nasıl oluşturulduğunu C'de kodlamaya çalıştım:
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;
}
ancak bu, internette başka bir yerde bulduğum değerlerle tutarsız değerler üretiyor gibi görünüyor. İnternette bulduğum değerleri kullanabilirim, ancak bunların nasıl oluşturulduğunu anlamak istiyorum.
Bu inanılmaz derecede kafa karıştırıcı rakamları açıklığa kavuşturmak için herhangi bir yardım çok takdir edilecektir.
CRC32 için polinom şöyledir:
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Ya da hex ve binary olarak:
0x 01 04 C1 1D B7 1 0000 0100 1100 0001 0001 1101 1011 0111
En yüksek terim (x32) genellikle açıkça yazılmaz, bu nedenle bunun yerine hex cinsinden şu şekilde gösterilebilir
0x 04 C1 1D B7
1leri ve 0
ları saymaktan çekinmeyin, ancak 1
in bit 0 (veya ilk bit) ve x
in bit 1 (veya ikinci bit) olduğu polinomla eşleştiklerini göreceksiniz.
Neden bu polinom? Çünkü verilen bir polinomun standart olması gerekir ve standart IEEE 802.3 tarafından belirlenmiştir. Ayrıca farklı bit hatalarını etkili bir şekilde tespit eden bir polinom bulmak son derece zordur.
CRC-32'yi bir dizi "Taşımasız İkili Aritmetik" ya da temel olarak "XOR ve kaydırma işlemleri" olarak düşünebilirsiniz. Buna teknik olarak Polinom Aritmetiği denir.
Bunu daha iyi anlamak için şu çarpımı düşünün:
(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
Eğer x'in 2 tabanı olduğunu varsayarsak o zaman şunu elde ederiz:
x^7 + x^3 + x^2 + x^1 + x^0
Neden mi? Çünkü 3x^3, 11x^11'dir (ancak sadece 1 veya 0 ön basamağına ihtiyacımız vardır), bu yüzden taşırız:
=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
Ancak matematikçiler kuralları mod 2 olacak şekilde değiştirdiler. Yani temelde herhangi bir ikili polinom mod 2, taşıma veya XOR olmadan sadece toplamadır. Yani orijinal denklemimiz şöyle görünüyor:
=( 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)
Bunun bir inanç sıçraması olduğunu biliyorum, ancak bu bir satır programcısı olarak yeteneğimin ötesinde. Eğer sıkı bir CS öğrencisi ya da mühendisi iseniz, bunu çözmek için meydan okuyorum. Bu analizden herkes faydalanacaktır.
Yani tam bir örnek üzerinde çalışmak için:
Original message : 1101011011
Polynomial of (W)idth 4 : 10011
Message after appending W zeros : 11010110110000
Şimdi CRC aritmetiği kullanarak artırılmış Mesajı Poli'ye böleriz. Bu daha önce yaptığımız bölme işleminin aynısıdır:
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!!!!
Bölme işlemi, atacağımız bir bölüm ve hesaplanan sağlama toplamı olan bir kalan verir. Böylece hesaplama sona erer. Genellikle, sağlama toplamı mesaja eklenir ve sonuç iletilir. Bu durumda iletim şöyle olacaktır: 11010110111110.
Bölen olarak yalnızca 32 bitlik bir sayı kullanın ve tüm akışınızı kar payınız olarak kullanın. Bölümü atın ve kalanı saklayın. Kalanı mesajınızın sonuna ekleyin ve bir CRC32 elde edin.
Ortalama bir adam yorumu:
QUOTIENT
----------
DIVISOR ) DIVIDEND
= REMAINDER
(Akışın 32 bite bölünebilir olması gerektiğini ya da dolgulanması gerektiğini unutmayın. Örneğin, 8 bitlik bir ANSI akışı doldurulmalıdır. Ayrıca akışın sonunda bölme işlemi durdurulur).
CRC oldukça basittir; bitler ve veri olarak temsil edilen bir polinom alırsınız ve polinomu veriye bölersiniz (veya veriyi bir polinom olarak temsil eder ve aynı şeyi yaparsınız). Kalan, 0 ile polinom arasında kalan CRC'dir. Kodunuzu anlamak biraz zor, çünkü kısmen eksik: temp ve testcrc bildirilmemiş, bu yüzden neyin indekslendiği ve algoritma boyunca ne kadar veri çalıştığı belirsiz.
CRC'leri anlamanın yolu, kısa bir polinomla - belki 4 bit - kısa bir veri parçası (16 bit ya da daha fazla) kullanarak birkaç tane hesaplamaya çalışmaktır. Bu şekilde pratik yaparsanız, nasıl kodlama yapabileceğinizi gerçekten anlayacaksınız.
Eğer sık sık yapıyorsanız, bir CRC'nin yazılımda hesaplanması oldukça yavaştır. Donanım hesaplaması çok daha verimlidir ve sadece birkaç kapı gerektirir.
Wikipedia'daki Cyclic redundancy check ve Computation of CRC makalelerine ek olarak, Reversing CRC - Theory and Practice* başlıklı bir makalenin iyi bir referans olduğunu gördüm.
CRC hesaplamak için temelde üç yaklaşım vardır: cebirsel yaklaşım, bit odaklı yaklaşım ve tablo odaklı yaklaşım. CRC'yi Tersine Çevirmek - Teori ve Uygulama**]3 kitabında, bu üç algoritma/yaklaşımın her biri teorik olarak açıklanmış ve EK'te CRC32 için C programlama dilinde bir uygulama verilmiştir.
* PDF Link
CRC'nin Tersine Çevrilmesi - Teori ve Uygulama
HU Berlin Kamu Raporu
SAR-PR-2006-05
Mayıs 2006
Yazarlar:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich