CRC 的計算方式 @ 拾人牙慧

CRC 的計算方式

CRC 為校驗和的一種，是兩個位元組資料流採用二進制除法（沒有進位，使用XOR來代替減法）相除所得到的餘數。其中被除數是需要計算校驗和的資訊資料流的二進制表示；除數是一個長度為 (n+1) 的預定義（短）的二進制數，通常用多項式的係數來表示。在做除法之前，要在資訊資料之後先加上 n 個 0。

舉例來說，除數為 "1011"，資訊資料為 "11100110"，在做除法之前，已在資訊資料之後先加上 3 個 0，計算過程如下圖所示，：

圖右邊是長除法的計算過程，圖中間列出詳細的分解，可以視為：

     111 0011 0000
   ^ 101 1000 0000
    ^ 10 1100 0000
        ^ 101 1000
         ^ 10 1100
------------------
               100

也就是說 111 0011 0000 ^ 101 1000 0000 ^ 10 1100 0000 ^ 101 1000 ^ 10 1100 = 100
又因為 XOR 運算可以符合結合律，也就是說：
A ^ B ^ C = (A ^ B) ^ C = A ^ (B ^ C)
所以下式同樣會成立：
111 0011 0000 ^ (101 1000 0000 ^ 10 1100 0000 ^ 101 1000 ^ 10 1100) = 100
這樣的話，又因為資訊資料會補 3 個 0，所以只需要計算 (101 1000 0000 ^ 10 1100 0000 ^ 101 1000 ^ 10 1100) 的後三位，就可以得到 100。

接下來是重點部分，該如何決定要拿哪些資料來作 XOR 運算？
為方便解釋，先作一些數值設定：
regs 用於儲存 XOR 的計算結果，初始值為：0000。
msb 為資訊資料的第一個位元。
regs_msb 為 regs 的第一個位元。
polynomial 為除數。

運算的方式為：

如果 msb 跟 regs_msb 只有一個為 1，則：
regs = regs ^ polynomial
regs = (regs << 1)
跳到第一步，msb 跳到資訊資料的下一個位元，資訊資料如果沒有下一個位元，則結束

最關鍵的部分是第一步，只有在 msb 跟 regs_msb 不一樣的情況下，才需要對 regs 作 ^ polynomial 的運算，如果兩者剛好都為 0 或都為 1，則剛好抵消，不需要作運算。
原因就是如果 msb 跟 regs_msb 如果都為 1 或 0，則彼此相抵消，可以搭配上圖來看，來瞭解這邊要表達的意思，不然不好懂。

再進一步來看：
regs 的第一個 bit，總是會被位移去掉，所以可以不要列入計算，但還是需要拿來作判斷使用，於是運算的方式就變成：
此時 polynomial 也要把第一個 1 的位元去除。

從 regs 取出 regs_msb，接著
regs = (regs << 1)
如果 msb 跟 regs_msb 只有一個為 1，則：
regs = regs ^ polynomial
跳到第一步，msb 跳到資訊資料的下一個位元，資訊資料如果沒有下一個位元，則結束

用 C 語言來計算 CRC

用程式來撰寫計算 CRC32 的方式，如下所示：

static uint32_t calculate_crc32(void *buf, uint32_t len)
{
    uint32_t i, j;
    uint32_t byte_length = 8;       /*length of unit (i.e. byte) */
    int msb = 0;
    int polynomial = 0x04C11DB7;    /* IEEE 32bit polynomial */
    unsigned int regs = 0xFFFFFFFF; /* init to all ones */
    int regs_mask = 0xFFFFFFFF;     /* ensure only 32 bit answer */
    int regs_msb = 0;
    unsigned int reflected_regs;
    for (i = 0; i < len; i++) {
        int data_byte = *((uint8_t *)buf + i);
        data_byte = reflect(data_byte, 8);
        for (j = 0; j < byte_length; j++) {
            // 取得資訊資料的 msb
            msb = data_byte >> (byte_length - 1); /* get MSB */
            msb &= 1;                             /* ensure just 1 bit */
            // regs 的 msb
            regs_msb = (regs >> 31) & 1;          /* MSB of regs */
            // 去除 regs 的 msb，並補 0
            regs = regs << 1;                     /* shift regs for CRC-CCITT */
            // 如果 regs_msb 及 msb 其中，只有 1 組值為 1
            if (regs_msb ^ msb) {                 /* MSB is a 1 */
                // 對 regs 與 polynomial 做 XOR 運算
                regs = regs ^ polynomial;         /* XOR with generator poly */
            }
            regs = regs & regs_mask;              /* Mask off excess upper bits */
            // 資訊資料位移 1 個位元
            data_byte <<= 1;                      /* get to next bit */
        }
    }
    regs = regs & regs_mask;
    reflected_regs = reflect(regs, 32) ^ 0xFFFFFFFF;
    return reflected_regs;
}

以上的算法是 CRC-32-IEEE 802.3 的算法，它的參數模型是：

Width :	32	CRC 的長度
Poly :	04C11DB7	polynomial 的值
Initial value :	0xFFFFFFFF	reg 计算前的初始值
RefIn :	True	輸入資訊資料要進行反轉
RefOut :	True	輸出結果(CRC)要進行反轉
XorOut :	FFFFFFFF	對輸出結果(CRC)要運行 XOR 運算