試圖瞭解不同的CRC實現

在數學上，對應於給定的MAC幀的CRC值是由下列方法定義的：

a）第一個32的位框架是補充。 b）然後將保護字段的n位認爲是度爲n-1的多項式M（x）的係數。（目的地地址字段的第一位對應於x（n-1 ）項和MAC客戶機數據字段（或填充字段，如果存在）的最後一個位對應於 x0項。）
c）M（x）乘以x32併除以G（x），產生d）餘數R（x）的度數≤31.
d）R（x）的係數被認爲是32位序列。 e）位序列被補充，結果是CRC。

https://www.kernel.org/doc/Documentation/crc32.txt

這樣寫的大端CRC的代碼應該像：

for (i = 0; i < input_bits; i++) { 
    multiple = remainder & 0x80000000 ? CRCPOLY : 0; 
    remainder = (remainder << 1 | next_input_bit())^multiple; 
}

哪裏是部分C）M（X）爲x^32乘以？ 我沒有看到32個零附加到任何數字。

此外，下面的一段代碼對我沒有任何意義。代碼和數學並不匹配。

Evaluating the differences in CRC-32 implementations 和

unsigned short 
crc16_update(unsigned short crc, unsigned char nextByte) 
{ 
    crc ^= nextByte; 

    for (int i = 0; i < 8; ++i) { 
     if (crc & 1) 
      crc = (crc >> 1)^0xA001; 
     else 
      crc = (crc >> 1); 
    } 

    return crc; 
}

這些是什麼人的實現做什麼？他們中沒有一個真的像原來的程序。

即使閱讀的盡頭後，它仍然是沒有意義的： http://www.relisoft.com/science/crcmath.html

來源

2014-06-20 mrbean

1.描述中的多項式在有限域GF（2）中具有係數。有關這意味着什麼的詳細信息，請參閱https://en.wikipedia.org/wiki/Finite_field_arithmetic#Effective_polynomial_representation。 2.第二個實現'crc16_update'是little-endian，它解釋了它和第一個實現之間的區別（第一個實現檢查'餘數＆0x80000000'並左移，第二個檢查'crc＆1'並右移）。 3.乘以x^32實際上是初始化;你只顯示了更新。 – Pseudonym

好極了，這樣做更有意義。那麼從大端CRC來說，x^32的乘法是在開始時初始化爲0xFFFFFFFF（未顯示）？當你說只顯示更新時，你的意思是我忽略了初始化步驟是否正確？只是想確保我明白。 – mrbean

其實，乘以x^32可能是最後一步，現在我想到了。但是，初始化和定稿非常重要。 – Pseudonym

This tutorial（也here，here和here對於那些誰都會抱怨鏈接腐爛），尤其是「10略Mangled Table-Driven Implementation「，並解釋了爲避免在最後輸入額外的32位零的優化。

底線是您將位送入寄存器的末尾而不是起始位，這與在末尾提供寄存器長度值爲零的效果相同。

該教程還很好地顯示了您引用的實現如何實現GF（2）的長分割。

來源

2014-06-21 17:12:15

試圖瞭解不同的CRC實現

回答

相關問題