CRC

CRC ：calculate sum¶

Basic Idea¶

用加減法計算太過於簡單，需要更複雜的算法，故使用除法對資料進行計算 CRC將資料視為巨大的二進位數字，並使用異或(xor)代替除法進行運算

          ...0000010101101 = 00AD =  173 = QUOTIENT
         ____-___-___-___-
9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND
DIVISOR   0000.,,....,.,,,
          ----.,,....,.,,,
           0000,,....,.,,,
           0000,,....,.,,,
           ----,,....,.,,,
            0001,....,.,,,
            0000,....,.,,,
            ----,....,.,,,
             0011....,.,,,
             0000....,.,,,
             ----....,.,,,
              0110...,.,,,
              0000...,.,,,
              ----...,.,,,
               1100..,.,,,
               1001..,.,,,
               ====..,.,,,
                0110.,.,,,
                0000.,.,,,
                ----.,.,,,
                 1100,.,,,
                 1001,.,,,
                 ====,.,,,
                  0111.,,,
                  0000.,,,
                  ----.,,,
                   1110,,,
                   1001,,,
                   ====,,,
                    1011,,
                    1001,,
                    ====,,
                     0101,
                     0000,
                     ----
                      1011
                      1001
                      ====
                      0010 = 02 = 2 = REMAINDER

對於CRC算法而言，重要的是商數多項式 polynomial 與餘數 remainder，在CRC算法內，所有加減法都是xor運算

數學例子如下，以下為設定參數

   Original message                : 1101011011
   Poly                            :      10011
   Message after appending W zeros : 11010110110000

為了也計算到最後一位，需要對原資料進行補零，原因為我們為從最大的bit開始進行 xor。

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

CRC加密有兩種驗證方式 1. 將原資料與CRC數進行xor後，需要跟多項式整除為零 2. 原資料與多項式再進行一次CRC，與已有的CRC數進行比較

CRC選擇多項式的方法有很多方式與數學基礎，列出以下幾點

Single bit error: 要偵測出E=1000…0000這類型的錯誤，只需要確保多項式G有兩個bit設為1即可
Two bit errors 要偵測出E=100…000100…000這類型，需確保多項式G沒有11, 101, 1001, 10001, 100001等類型
Error with an odd number of bits 選擇多項式為偶數bit即可
burst errors 錯誤為E=000…000111…11110000…00，亦即中間有一段區間的錯誤，將多項式最低bit設為1即可

在程式上，一個直觀例子如下假設多項式有5位數，那麼我們只要關注前4位bit與多項式xor，以及CRC第5位數是否為1，當CRC第5位數為1，代表需要做一次xor運算，進而拿到餘數

                  3   2   1   0   Bits
                +---+---+---+---+
       Pop! <-- |   |   |   |   | <----- Augmented message
                +---+---+---+---+

             1    0   1   1   1   = The Poly

Pseudo code

Load the register with zero bits.
Augment the message by appending W zero bits to the end of it.
While (more message bits)
    Begin
    Shift the register left by one bit, reading the next bit of the
        augmented message into register bit position 0.
    If (a 1 bit popped out of the register during step 3)
        Register = Register XOR Poly.
    End
The register now contains the remainder.

但每次對一個bit運算相當費時，數據在程式上都是至少一次讀取一個Byte(char)，故我們可以提前將一個Byte內所有可能的數值(0~255)先算成一個CRC table，透過byte查表後再將算出的數值進行xor運算

由於 xor具有交換率，故先計算前8個位元再xor與每個位元進行xor是相同的

算法可以簡化成下列

While (augmented message is not exhausted)
    Begin
    Examine the top byte of the register
    Calculate the control byte from the top byte of the register
    Sum all the Polys at various offsets that are to be XORed into
        the register in accordance with the control byte
    Shift the register left by one byte, reading a new message byte
        into the rightmost byte of the register
    XOR the summed polys to the register
    End

用C語言的實現

uint32_t r=0;
while (len--)
    {
    byte t = (r >> 24) & 0xFF;
    r = (r << 8) | *p++;
    r^=table[t];
    }

CRC設定參數 * Width of the poly (polynomial). * Value of the poly. * Initial value for the register. * Whether the bits of each byte are reflected before being processed. * Whether the algorithm feeds input bytes through the register or xors them with a byte from one end and then straight into the table. * Whether the final register value should be reversed (as in reflected versions). * Value to XOR with the final register value.

以CRC32為例：

   Name   : "CRC-32"
   Width  : 32
   Poly   : 04C11DB7
   Init   : FFFFFFFF
   RefIn  : True
   RefOut : True
   XorOut : FFFFFFFF
   Check  : CBF43926

C code implementation

要注意的是，與其對input 與output作reflect，不如直接對多項式進行reflect，故在這邊的多項式才會是EDB88320

#include <stdio.h>
#include <cstdint>

uint32_t table[256];

void CRC32_Table()
{
    uint32_t poly = 0xedb88320; 

    for (uint16_t num = 0; num < 256; num++)
    {
        uint32_t crc = 0x0;
        crc = num;
        printf("input crc is %x \n", crc);
        for (int i = 0; i < 8; i++)
        {
            if (crc & 1)
                crc = (crc >> 1) ^ poly;
            else
                crc = crc >> 1;
        }
        printf("output crc is %x \n", crc);
        printf("\n\n");

        table[num] = crc;
    }
    return;
}