簡(jiǎn)而言之，CRC是一個(gè)數(shù)值。該數(shù)值被用于校驗(yàn)數(shù)據(jù)的正確性。CRC數(shù)值簡(jiǎn)單地說(shuō)就是通過(guò)讓你需要做處理的數(shù)據(jù)除以一個(gè)常數(shù)而得到的余數(shù)。當(dāng)你得到這個(gè)數(shù)值后你可以將這個(gè)數(shù)值附加到你的數(shù)據(jù)后，當(dāng)數(shù)據(jù)被傳送到其他地方后，取出原始數(shù)據(jù)(可能在傳送過(guò)程中被破壞)與附加的CRC數(shù)值，然后將這里的原始數(shù)據(jù)除以之前那個(gè)常數(shù)(約定好的)然后得到新的CRC值。比較兩個(gè)CRC值是否相等即可確認(rèn)你的數(shù)據(jù)是否在傳送過(guò)程中出現(xiàn)錯(cuò)誤。
那么，如何讓你的數(shù)據(jù)除以一個(gè)常數(shù)？方法是對(duì)你的數(shù)據(jù)進(jìn)行必要的編碼處理，逐字節(jié)處理成數(shù)字。
那么這個(gè)常數(shù)是什么？你不必關(guān)注它是什么，也不需要關(guān)注它是如何獲得的。當(dāng)你真的要?jiǎng)邮謱?xiě)一個(gè)CRC的實(shí)現(xiàn)算法時(shí)，我可以告訴你，CRC的理論學(xué)家會(huì)告訴你。不同長(zhǎng)度的常數(shù)對(duì)應(yīng)著不同的CRC實(shí)現(xiàn)算法。當(dāng)這個(gè)常數(shù)為32位時(shí)，也就是這里所說(shuō)的CRC32。
以上內(nèi)容你不必全部理解，因?yàn)槟阈枰殚喥渌Y料來(lái)獲取CRC完整的理論介紹。
The mathematics behind CRC ?
很多教科書(shū)會(huì)把CRC與多項(xiàng)式關(guān)聯(lián)起來(lái)。這里的多項(xiàng)式指的是系數(shù)為0或1的式子，例如：a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么為0要么為1。我們并不關(guān)注x取什么值。
(如果你要關(guān)注，你可以簡(jiǎn)單地認(rèn)為x為2) 這里把a(bǔ)0, a1, ..., an的值取出來(lái)排列起來(lái)，就可以表示比特流。例如 1 + x + x^3所表示的比特流就為：1101。部分資料會(huì)將這個(gè)順序顛倒，這個(gè)很正常。
什么是生成多項(xiàng)式？
所謂的生成多項(xiàng)式，就是上面我所說(shuō)的常數(shù)。注意，在這里，一個(gè)多項(xiàng)式就表示了一個(gè)比特流，也就是一堆1、0，組合起來(lái)最終就是一個(gè)數(shù)值。例如CRC32算法中，這個(gè)生成多項(xiàng)式為：c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。其對(duì)應(yīng)的數(shù)字就為：11101101101110001000001100100000(x^32在實(shí)際計(jì)算時(shí)隱含給出，因此這里沒(méi)有包含它的系數(shù))，也就是0xEDB88320(多項(xiàng)式對(duì)應(yīng)的數(shù)字可能顛倒，顛倒后得到的是0x04C11DB7，其實(shí)也是正確的)。
由此可以看出，CRC值也可以看成我們的數(shù)據(jù)除以一個(gè)生成多項(xiàng)式而得到的余數(shù)。
如何做這個(gè)除法？
套用大部分教科書(shū)給出的計(jì)算方法，因?yàn)槿魏螖?shù)據(jù)都可以被處理成純數(shù)字，因此，在某種程度上說(shuō)，我們可以直接開(kāi)始這個(gè)除法。盡管事實(shí)上這并不是標(biāo)準(zhǔn)的除法。例如，我們的數(shù)據(jù)為1101011011(方便起見(jiàn)我直接給二進(jìn)制表示了，從這里也可以看出，CRC是按bit進(jìn)行計(jì)算的)，給定的生成多項(xiàng)式(對(duì)應(yīng)的值)為10011。通常的教科書(shū)會(huì)告訴我們?cè)谶M(jìn)行這個(gè)除法前，會(huì)把我們的數(shù)據(jù)左移幾位(生成多項(xiàng)式位數(shù)-1位)，從而可以容納將來(lái)計(jì)算得到的CRC值(我上面所說(shuō)的將CRC值附加到原始數(shù)據(jù)后)。但是為什么要這樣做？我也不知道。(不知道的東西不能含糊過(guò))那么，除法就為：
1100001010
_______________
10011 ) 11010110110000 附加了幾個(gè)零的新數(shù)據(jù)
10011......... 這里的減法(希望你不至于忘掉小學(xué)算術(shù))是一個(gè)異或操作
-----.........
10011........
10011........
-----........
00001....... 逐bit計(jì)算
00000.......
-----.......
00010......
00000......
-----......
00101.....
00000.....
-----.....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = 這個(gè)余數(shù)也就是所謂的CRC值，通常又被稱(chēng)為校驗(yàn)值。
希望進(jìn)行到這里，你可以獲取更多關(guān)于CRC的感性認(rèn)識(shí)。而我們所要做的，也就是實(shí)現(xiàn)一個(gè)CRC的計(jì)算算法。說(shuō)白了，就是提供一個(gè)程序，給定一段數(shù)據(jù)，以及一個(gè)生成多項(xiàng)式(對(duì)于CRC32算法而言該值固定)，然后計(jì)算得出上面的1110余數(shù)。
The simplest algorithm.
那么，如何讓你的數(shù)據(jù)除以一個(gè)常數(shù)？方法是對(duì)你的數(shù)據(jù)進(jìn)行必要的編碼處理，逐字節(jié)處理成數(shù)字。
那么這個(gè)常數(shù)是什么？你不必關(guān)注它是什么，也不需要關(guān)注它是如何獲得的。當(dāng)你真的要?jiǎng)邮謱?xiě)一個(gè)CRC的實(shí)現(xiàn)算法時(shí)，我可以告訴你，CRC的理論學(xué)家會(huì)告訴你。不同長(zhǎng)度的常數(shù)對(duì)應(yīng)著不同的CRC實(shí)現(xiàn)算法。當(dāng)這個(gè)常數(shù)為32位時(shí)，也就是這里所說(shuō)的CRC32。
以上內(nèi)容你不必全部理解，因?yàn)槟阈枰殚喥渌Y料來(lái)獲取CRC完整的理論介紹。
The mathematics behind CRC ?
很多教科書(shū)會(huì)把CRC與多項(xiàng)式關(guān)聯(lián)起來(lái)。這里的多項(xiàng)式指的是系數(shù)為0或1的式子，例如：a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么為0要么為1。我們并不關(guān)注x取什么值。
(如果你要關(guān)注，你可以簡(jiǎn)單地認(rèn)為x為2) 這里把a(bǔ)0, a1, ..., an的值取出來(lái)排列起來(lái)，就可以表示比特流。例如 1 + x + x^3所表示的比特流就為：1101。部分資料會(huì)將這個(gè)順序顛倒，這個(gè)很正常。
什么是生成多項(xiàng)式？
所謂的生成多項(xiàng)式，就是上面我所說(shuō)的常數(shù)。注意，在這里，一個(gè)多項(xiàng)式就表示了一個(gè)比特流，也就是一堆1、0，組合起來(lái)最終就是一個(gè)數(shù)值。例如CRC32算法中，這個(gè)生成多項(xiàng)式為：c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。其對(duì)應(yīng)的數(shù)字就為：11101101101110001000001100100000(x^32在實(shí)際計(jì)算時(shí)隱含給出，因此這里沒(méi)有包含它的系數(shù))，也就是0xEDB88320(多項(xiàng)式對(duì)應(yīng)的數(shù)字可能顛倒，顛倒后得到的是0x04C11DB7，其實(shí)也是正確的)。
由此可以看出，CRC值也可以看成我們的數(shù)據(jù)除以一個(gè)生成多項(xiàng)式而得到的余數(shù)。
如何做這個(gè)除法？
套用大部分教科書(shū)給出的計(jì)算方法，因?yàn)槿魏螖?shù)據(jù)都可以被處理成純數(shù)字，因此，在某種程度上說(shuō)，我們可以直接開(kāi)始這個(gè)除法。盡管事實(shí)上這并不是標(biāo)準(zhǔn)的除法。例如，我們的數(shù)據(jù)為1101011011(方便起見(jiàn)我直接給二進(jìn)制表示了，從這里也可以看出，CRC是按bit進(jìn)行計(jì)算的)，給定的生成多項(xiàng)式(對(duì)應(yīng)的值)為10011。通常的教科書(shū)會(huì)告訴我們?cè)谶M(jìn)行這個(gè)除法前，會(huì)把我們的數(shù)據(jù)左移幾位(生成多項(xiàng)式位數(shù)-1位)，從而可以容納將來(lái)計(jì)算得到的CRC值(我上面所說(shuō)的將CRC值附加到原始數(shù)據(jù)后)。但是為什么要這樣做？我也不知道。(不知道的東西不能含糊過(guò))那么，除法就為：
1100001010
_______________
10011 ) 11010110110000 附加了幾個(gè)零的新數(shù)據(jù)
10011......... 這里的減法(希望你不至于忘掉小學(xué)算術(shù))是一個(gè)異或操作
-----.........
10011........
10011........
-----........
00001....... 逐bit計(jì)算
00000.......
-----.......
00010......
00000......
-----......
00101.....
00000.....
-----.....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = 這個(gè)余數(shù)也就是所謂的CRC值，通常又被稱(chēng)為校驗(yàn)值。
希望進(jìn)行到這里，你可以獲取更多關(guān)于CRC的感性認(rèn)識(shí)。而我們所要做的，也就是實(shí)現(xiàn)一個(gè)CRC的計(jì)算算法。說(shuō)白了，就是提供一個(gè)程序，給定一段數(shù)據(jù)，以及一個(gè)生成多項(xiàng)式(對(duì)于CRC32算法而言該值固定)，然后計(jì)算得出上面的1110余數(shù)。
The simplest algorithm.