CRC是什麼？
一個數值(整數)
長度：
CRC-8 ： 8 bit
CRC-16：16 bit
CRC-32：32 bit
CRC的用途？
檢查傳過來的資料是不是正確的
有沒有因為傳輸過程中的干擾而使資料出錯
如何計算CRC？
用除法
被除數 除以 除數 → 得到 商 和 餘數
(資料 + 補0) (多項式) (CRC)
多項式：
x3 + x + 1
↓
23 + 21 + 20
↓
1011
長度：4 bit
所以，資料後面要補 (4 - 1 = 3)個 0
資料：
10010011
被除數：
資料 + 補 3個 0
10010011 000
↓
10010011000
除數(多項式)：
1011
開始算：
10101101
__________________
1011 )10010011000
1011
__________________
00100
0000
__________________
01000
1011
__________________
00111
0000
__________________
01111
1011
__________________
01000
1011
__________________
00110
0000
__________________
01100
1011
__________________
0111 → 最後4 bit 是 CRC
除法特別的地方
0 - 1 = 1
每bit運算各自獨立。不向旁邊借 1
事實上，就是在做XOR運算
每次減法完之後，最左邊會變成 0 、不再參與計算
從「資料區」or「補0區」取 1 bit 下來參加下一次的減法
被減數：
「被減數」的最左邊如果是 1 , 「商」就寫1
「被減數」的最左邊如果是 0 , 「商」就寫0
也就是，在進行減法時，就是減掉 1011 或 0000
因為減 0000 ，「被減數」沒有發生改變，
所以，在進行減法時，尋找「被減數」最左邊的 1 對齊
10010011000
1011
00100011000
1011
00001111000
1011
00000100000
1011
00000001100
1011
00000000111 → 最後4 bit 是 CRC
進行XOR運算時：
最左邊那 1 bit的結果：
一定是 0 可以不用計算
每次計算完的結果，可以看作是「暫時的CRC」
在「暫時的CRC」後面補 1 bit ，作為下一次的被減數
等到沒有資料可以補 1 bit時，就是「最後的CRC」
CRC16的規格
Polynomial(多項式)： X16 + X12 + X5 + 1
Initial Value(初始值)：0xFFFF
Input reflected：否
Result reflected：否
Final XOR：否
Polynomial(多項式)：
X16 + X12 + X5 + 1
可以看成 216 + 212 + 25 + 1
1 00010000 00100001
總共 17 bit
所以，要在資料後面補 (17 - 1 = 16) bit 0
Polynomial的值：0x1021
原本有17bit，最左邊那 1 bit 略過不記
initial(初始值)：
0xFFFF
已經計算完成的CRC值
可以把它想像成「某些資料 + 補 16bit的0」所產生的CRC值
可是，還沒有開始計算，怎麼會有CRC值？
CRC16的演算法(1)：當資料只有 1 byte 時
開始計算前：
「某些資料」 + 0x00 0x00
CRC16是 0xFFFF
現在要計算0xD1的CRC值：
「某些資料」 + 0xD1 0x00 0x00
多了 1 byte 資料，「補0區」往後移
先看前 2 byte：
開始計算前：
「某些資料」 + 0x00 0x00
現在要計算：
「某些資料」 + 0xD1 0x00
第一個 0x00 變成 0xD1
產生「修改版CRC16值」：
「CRC16值的左邊那 1 byte」 和 「0xD1」進行XOR運算
得到 「修改版CRC16值」
因為「是從0x00 變成 0xD1」，所以可以這樣計算
處理「最後一個 0x00」：
「修改版CRC16值」 + 「0x00」 → 計算「最後的CRC16值」
public static ushort Crc16Ccitt(byte[] bytes){
const ushort poly = 0x1021; //多項式
ushort initialValue = 0xFFFF; //初始值
ushort crc = initialValue;
for (int i = 0; i < bytes.Length; ++i)
{
crc = (ushort)(crc ^ (bytes[i] << 8)); //修改CRC16值的左邊那 1 byte
for (int j = 0; j < 8; ++j) //處理「最後一個 0x00」共 8 bit
{
if ((crc & 0x8000) != 0) //尋找「被減數」最左邊的 1 對齊
crc = (ushort)((crc << 1) ^ poly);
else
crc <<= 1;
}
}
return crc;
}
CRC16的演算法(2)：查表
以下的 C1 C2 D1 E1 只是代號，不是數字
C → crc D → data E → edit
「原本的CRC16值」：
C1 C2
「資料」：
D1
產生「修改版CRC16值」：
C1 XOR運算 D1 得到 E1
「修改版CRC16值」：
E1 C2
E1 有256種可能
C2 先假設它是 0x00
事先計算「CRC16值」：
0x00 0x00 + 「0x00」
0x01 0x00 + 「0x00」
0x02 0x00 + 「0x00」
略
0xE1 0x00 + 「0x00」
略
0xFF 0x00 + 「0x00」
把各種情形的CRC16值存在陣列裡
查表：
索引值：E1
值：CRC16值
計算「最後的CRC16值」：
把 「C2 00」 和「查表得到的CRC16值」進行 XOR 運算
總結：
就是分開計算、然後再把兩者進行XOR運算
E1 00 + 0x00 → 查表
00 C2 + 0x00 → C2 00
public static ushort Crc16Ccitt(byte[] bytes){
const ushort poly = 0x1021; //多項式
ushort[] table = new ushort[256]; //表格大小為 256
ushort initialValue = 0xFFFF; //初始值
ushort a;
ushort crc = initialValue;
for (int i = 0; i < table.Length; ++i) //製表。共256回
{
a = (ushort)(i << 8); // 0x00 0x00 到 0xFF 0x00
for (int j = 0; j < 8; ++j) //處理「最後一個 0x00」共 8 bit
{
if ((a & 0x8000) != 0) //尋找「被減數」最左邊的 1 對齊
a = (ushort)((a << 1) ^ poly);
else
a <<= 1;
}
table[i] = a;
}
for (int i = 0; i < bytes.Length; ++i) //使用表格
{
crc = (ushort)((crc << 8) ^ table[(crc >> 8) ^ bytes[i]]);
}
return crc;
}
CRC16的演算法(3)：一次計算 16 bytes
資料：
D1 D2 D3 D4 … D15 D16
修改CRC：
C1 XOR運算 D1 得到 E1
C2 XOR運算 D2 得到 E2
製表：
表格大小為 16 * 256
左移的byte數 vs 索引值的範圍：
左移 1 byte補0 → (0 到 255)
左移 2 byte補0 → (0 到 255) + 1 * 256
左移 3 byte補0 → (0 到 255) + 2 * 256
左移 4 byte補0 → (0 到 255) + 3 * 256
略
左移 15 byte補0 → (0 到 255) + 14 * 256
左移 16 byte補0 → (0 到 255) + 15 * 256
分開計算：
E1 00 + 16個0x00
00 E2 00 + 15個0x00
00 00 D3 00 + 14個0x00
00 00 00 D4 00 + 13個0x00
00 00 00 00 D5 00 + 12個0x00
00 00 00 00 00 D6 00 + 11個0x00
略
「14個00」 D15 00 + 2個0x00
「15個00」 D16 00 + 1個0x00
計算CRC：
把以上16個結果進行XOR運算
//learn from https://github.com/force-net/Crc32.NET/blob/develop/Crc32.NET/SafeProxy.cs
public static ushort Crc16Ccitt(byte[] bytes){
const ushort poly = 0x1021; //多項式
ushort[] table = new ushort[16*256]; //表格大小為 16 * 256
ushort initialValue = 0xFFFF; //初始值
ushort a;
ushort crc = initialValue;
int i = 0;
for (i = 0; i < 256; ++i) //製表
{
a = (ushort)(i << 8); //0x00 0x00 到 0xFF 0x00
for (int g = 0; g < 16; ++g) //左移 1 到 16個 0x00
{
for (int j = 0; j < 8; ++j) //處理每次的 0x00 共 8 bit
{
if ((a & 0x8000) != 0) //尋找「被減數」最左邊的 1 對齊
a = (ushort)((a << 1) ^ poly);
else
a <<= 1;
}
table[g*256 + i] = a;
}
}
for (i = 0; i + 15 < bytes.Length; i=i+16) //每找到16 bytes資料，就處理一次
{
crc = (ushort)(table[15*256 + ((crc >> 8) ^ bytes[i])] ^
table[14*256 + ((byte)crc ^ bytes[i+1])] ^
table[13*256 + bytes[i+2]] ^
table[12*256 + bytes[i+3]] ^
table[11*256 + bytes[i+4]] ^
table[10*256 + bytes[i+5]] ^
table[ 9*256 + bytes[i+6]] ^
table[ 8*256 + bytes[i+7]] ^
table[ 7*256 + bytes[i+8]] ^
table[ 6*256 + bytes[i+9]] ^
table[ 5*256 + bytes[i+10]] ^
table[ 4*256 + bytes[i+11]] ^
table[ 3*256 + bytes[i+12]] ^
table[ 2*256 + bytes[i+13]] ^
table[ 256 + bytes[i+14]] ^
table[bytes[i+15]]);
}
for (; i < bytes.Length; ++i) // 還沒處理的資料(長度小於 16 bytes)
{
crc = (ushort)((crc << 8) ^ table[(crc >> 8) ^ bytes[i]]);
}
return crc;
}
CRC32的規格
Polynomial(多項式)：X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
Initial Value(初始值)：0xFFFFFFFF
Input reflected：是
Result reflected：是
Final XOR：是
Polynomial(多項式)：
X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
↓
可以看成232 + 226 + 223 + 222 + 216 + 212 + 211 + 210 + 28 + 27 + 25 + 24 + 22 + 21 + 1
↓
1 00000100 11000001 00011101 10110111
總共 33 bit
所以，要在資料後面補 (33 - 1 = 32) bit 0
Input reflected：
處理每個byte時，從低位元(右邊的bit)開始處理。
所以，處理的時候，是往右移(shift)
為了配合往右移，Polynomial(多項式)每個bit的順序左右相反
最左邊的bit → 放到最右邊
最右邊的bit → 放到最左邊
原本的Polynomial(多項式)：0x04C11DB7
原本有33bit，最左邊那 1 bit 略過不記
bit順序左右相反的Polynomial(多項式)：0xEDB88320
把剩餘的32bit 順序相反放置
不看多項式、只看數字的話，
會不確定是「原本的」？還是「bit順序左右相反的」？
Result reflected：
計算完成的CRC，維持「每個bit的順序左右相反」的狀態
並沒有把順序改回來
Final XOR：
把「計算完成的CRC」每個bit「1 變成 0」、「0 變成 1」
得到了「最後的CRC」，就可以把CRC傳回給使用者了
如果計算完 1GB的資料，得到「最後的CRC」
發現後面還有 20MB的資料還沒有計算
把「最後的CRC」每個bit「1 變成 0」、「0 變成 1」
然後，再繼續計算 20MB的資料
CRC32的演算法(查表)
以下的 C1 C2 C3 C4 D1 E1 只是代號，不是數字
C → crc D → data E → edit
「原本的CRC32值」：
C4 C3 C2 C1
「資料」：
D1
產生「修改版CRC32值」：
C1 XOR運算 D1 得到 E1
「修改版CRC32值」：
C4 C3 C2 E1
E1 有256種可能
C4 C3 C2 先假設它是 0x00
事先計算「CRC32值」：
「0x00」 + 00 00 00 00
「0x00」 + 00 00 00 01
「0x00」 + 00 00 00 02
略
「0x00」 + 00 00 00 E1
略
「0x00」 + 00 00 00 FF
把各種情形的CRC32值存在陣列裡
查表：
索引值：E1
值：CRC32值
計算「CRC32值」：
把 「00 C4 C3 C2」 和「查表得到的CRC32值」進行 XOR 運算
總結：
就是分開計算、然後再把兩者進行XOR運算
「0x00」 + 00 00 00 E1 → 查表
「0x00」 + C4 C3 C2 00 → 00 C4 C3 C2
public static uint Crc32(byte[] bytes){
const uint poly = 0xEDB88320; //多項式
uint[] table = new uint[256]; //表格大小為 256
uint initialValue = 0xFFFFFFFF; //初始值
uint a;
uint crc = initialValue;
for (int i = 0; i < table.Length; ++i) //製表。共256回
{
a = (uint)i; // 從「00 00 00 00」 到 「00 00 00 FF」
for (int j = 0; j < 8; ++j) //處理「 0x00」共 8 bit
{
if ((a & 1) != 0) //尋找「被減數」最右邊的 1 對齊。 在最左邊補0
a = (uint)((a >> 1) ^ poly);
else
a >>= 1;
}
table[i] = a;
}
for (int i = 0; i < bytes.Length; ++i) //使用表格
{
crc = (uint)((crc >> 8) ^ table[(byte)crc ^ bytes[i]]);
}
return ~crc; // 最後 XOR (1變0 0變1)
}
參考資料：
沒有留言:
張貼留言