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)
}
參考資料:
沒有留言:
張貼留言