CRC計算簡明教程¶

CRC 是一個長除法的餘數。您將 CRC 新增到訊息中，整個內容（訊息 + CRC）是給定 CRC 多項式的倍數。要檢查 CRC，您可以檢查 CRC 是否與重新計算的值匹配，或者您可以檢查在訊息 + CRC 上計算的餘數是否為 0。後一種方法被許多硬體實現使用，這也是為什麼這麼多協議將幀結束標誌放在 CRC 之後的原因。

它實際上是您在學校學到的相同的長除法，只不過

我們正在使用二進位制，因此數字只有 0 和 1，並且
在除多項式時，沒有進位。我們只是異或，而不是加減。因此，我們傾向於對加法和減法之間的差異有點馬虎。

像所有除法一樣，餘數總是小於除數。要產生 32 位 CRC，除數實際上是一個 33 位 CRC 多項式。由於它是 33 位長，所以第 32 位總是會被設定，因此通常 CRC 以十六進位制寫入，省略最高有效位。（如果您熟悉 IEEE 754 浮點格式，它的想法是一樣的。）

請注意，CRC 是在位串上計算的，因此您必須決定每個位元組中位的位元組序。為了獲得最佳的錯誤檢測屬性，這應該對應於它們實際傳送的順序。例如，標準 RS-232 序列是小端序；最高有效位（有時用於奇偶校驗）最後傳送。並且當將 CRC 字附加到訊息時，您應該以正確的順序進行，與位元組序匹配。

就像普通的除法一樣，您一次處理一位數字（位）。除法的每一步，您都會獲取被除數的另一位數字（位）並將其附加到當前餘數。然後，您找出除數的適當倍數，以將其從餘數中減去，使其回到範圍內。在二進位制中，這很容易 - 它必須是 0 或 1，並且為了使 XOR 取消，它只是餘數的第 32 位的副本。

在計算 CRC 時，我們不關心商，因此我們可以丟棄商位，但從餘數中減去多項式的適當倍數，然後我們回到起點，準備處理下一位。

以這種方式編寫的大端 CRC 將被編碼為

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

請注意，為了獲得移位後的餘數的第 32 位，我們檢視之前移位的餘數的第 31 位。

但也要注意，我們移入餘數的 next_input_bit() 位實際上不會影響任何決策，直到 32 位之後。因此，這個過程的前 32 個週期非常無聊。此外，要將 CRC 新增到訊息中，我們需要在末尾為其提供一個 32 位長的孔，因此我們必須在每個訊息的末尾新增 32 個額外的週期來移入零。

這些細節導致了一個標準技巧：重新安排合併到 next_input_bit() 中，直到需要它的那一刻。然後可以預先計算前 32 個週期，並且可以完全跳過合併最終 32 個零位以為 CRC 騰出空間。這會將程式碼更改為

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

透過此最佳化，小端程式碼特別簡單

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

餘數多項式的最高有效係數儲存在二進位制“餘數”變數的最低有效位中。位元組序的其他細節已隱藏在 CRCPOLY（必須進行位反轉）和 next_input_bit() 中。

只要 next_input_bit 以合理的順序返回位，我們就不必等到最後一刻才合併其他位。我們可以一次做 8 位，而不是一次做 1 位

for (i = 0; i < input_bytes; i++) {
        remainder ^= next_input_byte() << 24;
        for (j = 0; j < 8; j++) {
                multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
                remainder = (remainder << 1) ^ multiple;
        }
}

或者用小端序

for (i = 0; i < input_bytes; i++) {
        remainder ^= next_input_byte();
        for (j = 0; j < 8; j++) {
                multiple = (remainder & 1) ? CRCPOLY : 0;
                remainder = (remainder >> 1) ^ multiple;
        }
}

如果輸入是 32 位的倍數，您甚至可以一次 XOR 一個 32 位字，並將內部迴圈計數增加到 32。

您還可以混合和匹配兩種迴圈樣式，例如一次對一個訊息位元組進行批次處理，併為末尾的任何非完整位元組新增一次一位的處理。

為了減少條件分支的數量，軟體通常使用一次一個位元組的表格方法，由 Dilip V. Sarwate 推廣，“透過表格查詢計算迴圈冗餘校驗”，Comm. ACM v.31 no.8 (August 1998) p. 1008-1013。

在這裡，我們不僅僅移位餘數的一位來決定要減去的正確倍數，我們可以一次移位一個位元組。這會產生一個 40 位（而不是 33 位）的中間餘數，並且使用一個 256 項的查詢表（由高 8 位索引）來找到要減去的多項式的正確倍數。

（表項只是給定單位元組訊息的 CRC-32。）

當空間更受限制時，可以使用較小的表格，例如兩次 4 位移位，然後查詢 16 項的表格。

使用這種技術一次處理超過 8 位是不切實際的，因為大於 256 項的表格會佔用太多記憶體，更重要的是，會佔用太多 L1 快取。

為了獲得更高的軟體效能，可以使用“切片”技術。請參閱“使用 Intel Slicing-by-8 演算法進行高辛烷值 CRC 生成”， ftp://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf

這不會改變表格查詢的次數，但會增加並行性。使用經典的 Sarwate 演算法，必須先完成每個表格查詢，然後才能計算下一個查詢的索引。

“切片 2”技術將一次移位餘數 16 位，從而產生一個 48 位的中間餘數。而不是在 65536 項的單個表格中查詢，而是在兩個不同的 256 項表格中查詢兩個高位元組。每個表格都包含取消相應位元組所需的餘數。這些表格是不同的，因為要取消的多項式是不同的。一個具有從 x^32 到 x^39 的非零係數，而另一個從 x^40 到 x^47。

由於現代處理器可以處理許多並行記憶體操作，因此這比單個表格查詢花費的時間長不了多少，因此執行速度幾乎是基本 Sarwate 演算法的兩倍。

可以使用 4 個 256 項的表格將其擴充套件到“切片 4”。每一步，獲取 32 位資料，與 CRC 進行異或運算，並將結果分解為位元組並在表格中查詢。由於 32 位移位使中間餘數的低位為零，因此最終 CRC 只是 4 個表格查詢的異或。

但這仍然強制執行順序執行：直到前一組的 4 個表格查詢全部完成後，才能開始第二組表格查詢。

為了最大限度地利用處理器，“切片 8”並行執行 8 次查詢。每一步，32 位 CRC 移位 64 位，並與 64 位輸入資料進行異或運算。需要注意的是，這 8 個位元組中的 4 個只是輸入資料的副本；它們根本不依賴於先前的 CRC。因此，這 4 個表格查詢可以立即開始，而無需等待先前的迴圈迭代。

透過始終保持 4 個載入在飛行中，可以使現代超標量處理器保持忙碌並充分利用其 L1 快取。

關於現實世界中 CRC 實現的另外兩個細節

通常，將零位附加到已經是多項式倍數的訊息會產生該多項式的更大倍數。因此，基本 CRC 將無法檢測到附加的零位（或位元組）。為了使 CRC 能夠檢測到這種情況，通常在附加 CRC 之前將其反轉。這使得訊息 + crc 的餘數不是零，而是一些固定的非零值。（反轉模式的 CRC，0xffffffff。）

同樣的問題適用於附加到訊息之前的零位，並且使用了類似的解決方案。不是以 0 的餘數開始 CRC 計算，而是使用全 1 的初始餘數。只要您以相同的方式開始解碼，就不會產生任何差異。

Linux 核心

目錄

本頁

CRC計算簡明教程¶