如何計算CRC32校驗和？

也許我只是沒有看到它，但CRC32似乎不必要地複雜，或沒有充分解釋我可以在網上找到任何地方。如何計算CRC32校驗和？

我知道這是來自消息值的非進位算術除法的餘數除以（發生器）多項式，但其實際執行情況卻逃脫了我。

我讀過A Painless Guide To CRC Error Detection Algorithms，我必須說這不是無痛的。它很好地理解了這個理論，但是作者從來沒有做過簡單的「這就是它」。他確實說過標準CRC32算法的參數是什麼，但他忽略了清楚地說明如何實現它。

得到我的部分是當他說「這就是它」，然後加上「哦，順便說一下，它可以顛倒或從不同的初始條件開始」，並沒有給出明確的答案考慮到他剛剛添加的所有更改，計算CRC32校驗和的最終方式是什麼？

對CRC32的計算方式有一個簡單的解釋嗎？

我試圖用C編寫的表是如何形成的：

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; 
}

但這似乎產生值與值不符我已經在互聯網上的其他地方找到。我可能使用我在網上找到的值，但我想了解它們是如何創建的。

任何幫助清理這些令人難以置信的混亂數字將是非常讚賞。

來源

2010-04-06 aquanar

您的用於生成CRC32表的代碼看起來是正確的。您的lsbit優先（* reverse *）CRC32多項式'0xEDB88320'也可以寫爲msbit-first（* normal *）作爲「0x04C11DB7」。您使用相同的CRC多項式生成的表值是否在其他地方生成？ – jschmier 2011-01-27 20:23:06

CRC很簡單;你可以將多項式表示爲比特和數據，並將多項式分解爲數據（或者將數據表示爲多項式並執行相同的操作）。餘數在0和多項式之間是CRC。你的代碼有點難以理解，部分原因是它不完整：temp和testcrc沒有聲明，所以不清楚索引什麼，以及算法中運行的數據量。

理解CRC的方法是嘗試使用短多項式（16位左右）和短多項式--4位來計算一些數據，也許。如果你這樣練習，你就會真正理解你如何編碼它。

如果你經常這樣做，在軟件中計算CRC是相當慢的。硬件計算效率更高，只需要幾個門。

來源

2010-04-06 19:56:05 WhirlWind

爲CRC32的多項式是：

0X 04 C1 1D B7

X + X + X + X + X + X + X + X + X + X + X + X + X + 1

其中工程以在二進制：

隨意數1和0，但你會發現它們匹配了多項式，其中1是0位（或第一位）和x是位1（或第二位）。

爲什麼這個多項式？因爲需要一個給定多項式的標準，並且標準由IEEE 802.3設置。此外，找到能夠有效檢測不同位錯誤的多項式非常困難。

你可以把CRC-32的一系列的「二進制運算與無懷揣」，或基本上是「XOR和移位操作」。這在技術上被稱爲多項式算術。

CRC primer, Chapter 5

爲了更好地理解它，認爲這乘法：

(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

如果我們假設x是基礎2，那麼我們得到：

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

CRC primer Chp.5

爲什麼？由於3X^3^11倍11（但我們只需要1或0前位），所以我們延續：

=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

但數學家改變了規則，所以它是國防部2所以基本上任何二進制多項式模2只是加法，不帶進位或XOR。所以，我們原來的公式是這樣的：

=(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)

我知道這是信仰的飛躍，但是這超出了我的能力，作爲一個行程序員。如果你是一名核心的CS學生或工程師，我挑戰打破這一點。每個人都會從這個分析中受益。

所以制定出一個完整的例子：

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

現在，我們通過使用CRC算術保利劃分擴充消息。這是因爲以前一樣分工：

  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!!!!

分裂產生的商，這是我們扔掉，和餘數，它是計算校驗和。這結束了計算。通常，校驗和會附加到消息中並傳輸結果。在這種情況下，傳輸將是：11010110111110.

CRC primer, Chapter 7

僅使用一個32位的號碼作爲除數，並使用你的整個流作爲分紅。拋出商並保留餘數。將剩下的部分放在郵件末尾，並且您有一個CRC32。

普通人回顧：

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

取前32位。
移位位
如果32位爲小於DIVISOR，去通過DIVISOR步驟2
XOR 32位。轉到步驟2.

（請注意，該流必須可以被32位分割，或者它應該被填充。例如，一個8位ANSI流將不得不被填充。流，該師被暫停。）

來源

2011-01-27 00:21:32

最後爲「平均人評論」+1 - 也許考慮將這個權利移到最高層 - 一種TL; DR：P – aaronsnoswell 2013-11-29 05:56:09

爲什麼在長分區部分使用XOR而不是減法？你能否解釋一下 – abstractnature 2015-09-17 10:35:11

@abstractnature請記住，我們除了多項式，不僅僅是二進制數。我們不能做「正常」減法，因爲我們不能從$ x^{n + 1} $中「借」$ x^n $;他們是不同種類的東西。另外，由於比特只是0或1，甚至會是-1？實際上，我們在多項式環中工作，其係數爲$ Z/2Z $，它只有兩個元素0和1，其中$ 1 + 1 = 0 $。通過把科學家放在一個領域，然後多項式形成所謂的歐幾里得領域，它基本上只允許我們試圖做的事情，以便首先定義好。 – calavicci 2015-11-10 23:11:43

除了維基百科Cyclic redundancy check和Computation of CRC文章中，我發現了一個題爲Reversing CRC - Theory and Practice^*是一個很好的參考文件。基本上有三種計算CRC的方法：代數方法，位方法和表驅動方法。在Reversing CRC - Theory and Practice^*中，這三種算法/方法中的每一種在理論上都是在附錄中通過在C編程語言中的CRC32的實現來解釋的。

^{* PDF鏈接
倒車CRC - 理論與實踐。
胡柏林公開報告
SAR-PR-2006-05
2006年5月
作者：
馬丁Stigge亨裏克Plötz，狼穆勒，延斯·彼得·雷德利希}

來源

2011-01-27 03:55:43 jschmier

對於IEEE802.3， CRC-32。將整個消息視爲一個串行比特流，將32個零附加到消息的末尾。接下來，你必須翻轉消息的每個字節的位，並對前32位進行1的補碼。現在除以CRC-32多項式，0x104C11DB7。最後，你必須對這個除法的32位餘數進行補碼 - 反轉餘數的4個字節中的每一個。這將成爲消息結尾附加的32位CRC。

這個奇怪的過程的原因是，第一個以太網實現將一次一個字節地串行化消息並且首先傳輸每個字節的最低有效位。串行比特流然後通過串行CRC-32移位寄存器計算，在消息完成之後，串行比特流被簡單地補充併發送出去。補充消息的前32位的原因是，即使消息全部爲零，也不會獲得全零CRC。

來源

2017-06-28 14:26:04

這是迄今爲止最好的答案，雖然我會替換'位反轉每個4字節'，'位 - 反過來4個字節，把它們看作一個實體'，例如'abcdefgh ijklmnop qrstuvwx yzABCDEF'to'FEDCBAzy xwvutsrq ponmlkji hgfedcba'。另請參閱：[CRC-32哈希教程 - AutoHotkey社區]（https://autohotkey.com/boards/viewtopic.php?f=7&t=35671）。 – vafylec 2017-08-09 23:28:06

我花了一段時間試圖揭開這個問題的答案，我終於出版了一本教程今天CRC-32： CRC-32 hash tutorial - AutoHotkey Community

在這個例子中，從它，我演示瞭如何計算的CRC-32對於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

來源

2017-08-09 23:39:45 vafylec

如何計算CRC32校驗和？

回答

相關問題