單片機CRC快速算法

表1 [ a 0 0 ] 余式表

a 0 1 2 3 4 5 6 7 8 9 A B C D E F
0× 0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF
1× 1231 0210 3273 2252 52B5 4294 72F7 62D6 9339 8318 B37B A35A D3BD C39C F3FF E3DE
2× 2462 3443 0420 1401 64E6 74C7 44A4 5485 A56A B54B 8528 9509 E5EE F5CF C5AC D58D
3× 3653 2672 1611 0630 76D7 66F6 5695 46B4 B75B A77A 9719 8738 F7DF E7FE D79D C7BC
4× 48C4 58E5 6886 78A7 0840 1861 2802 3823 C9CC D9ED E98E F9AF 8948 9969 A90A B92B
5× 5AF5 4AD4 7AB7 6A96 1A71 0A50 3A33 2A12 DBFD CBDC FBBF EB9E 9B79 8B58 BB3B AB1A
6× 6CA6 7C87 4CE4 5CC5 2C22 3C03 0C60 1C41 EDAE FD8F CDEC DDCD AD2A BD0B 8D68 9D49
7× 7E97 6EB6 5ED5 4EF4 3E13 2E32 1E51 0E70 FF9F EFBE DFDD CFFC BF1B AF3A 9F59 8F78
8× 9188 81A9 B1CA A1EB D10C C12D F14E E16F 1080 00A1 30C2 20E3 5004 4025 7046 6067
9× 83B9 9398 A3FB B3DA C33D D31C E37F F35E 02B1 1290 22F3 32D2 4235 5214 6277 7256
A× B5EA A5CB 95A8 8589 F56E E54F D52C C50D 34E2 24C3 14A0 0481 7466 6447 5424 4405
B× A7DB B7FA 8799 97B8 E75F F77E C71D D73C 26D3 36F2 0691 16B0 6657 7676 4615 5634
C× D94C C96D F90E E92F 99C8 89E9 B98A A9AB 5844 4865 7806 6827 18C0 08E1 3882 28A3
D× CB7D DB5C EB3F FB1E 8BF9 9BD8 ABBB BB9A 4A75 5A54 6A37 7A16 0AF1 1AD0 2AB3 3A92
E× FD2E ED0F DD6C CD4D BDAA AD8B 9DE8 8DC9 7C26 6C07 5C64 4C45 3CA2 2C83 1CE0 0CC1
F× EF1F FF3E CF5D DF7C AF9B BFBA 8FD9 9FF8 6E17 7E36 4E55 5E74 2E93 3EB2 0ED1 1EF0

5 適用于PIC單片機的算法 表1所示的余式表雖然只占用512個字節(jié)的程序存儲空間，但對于PIC單片機來說還是太大了，需要再進行壓縮。思路是這樣的： 將Ta00＝[a 0 0 ]分解成Te00＝[e 0 0 ]和Tf00＝[f 0 0 ]，并使字節(jié)e的上半字節(jié)內容與a的上半字節(jié)相同但下半字節(jié)為零，同時使字節(jié)f的下半字節(jié)內容與a的下半字節(jié)相同但上半字節(jié)為零，然后用Te00和Tf00生成余式表來代替Ta00余式表。由于Te00和Tf00中只有半個字節(jié)不為零，所以，每個余式表只需16個單元（32個字節(jié)），兩個余式表總共只占用64個字節(jié)，這樣就可滿足PIC單片機的要求了。 由上述思路可知，e＝a∧0F0H ，f＝a∧0FH ，因此可得，Ta00＝Te00? Tf00，同時，還可以證明它們余式的關系為Ra00＝Re00? Rf00，也就是說，如果設Ra00＝[ ha00 la00 ]、Re00＝[ he00 le00 ]和Rf00＝[ hf00 lf00 ]，則ha00＝he00? hf00 ，la00＝le00? lf00。這樣，三字節(jié)序列[a 0 0 ] 的計算可由圖3所示的方法來進行，其中，[e 0 0 ]和[f 0 0 ]余式表見表2和表3。

表2 [ e 0 0 ] 余式表

00 　10 　20 　30 　40　 50　 60　 70　 80　 90　 A0　 B0　 C0　 D0　 E0　 F0
0000 1231 2462 3653 48C4 5AF5 6CA6 7E97 9188 83B9 B5EA A7DB D94C CB7D FD2E EF1F
表3 [ f 0 0 ] 余式表

00　　01 　02 　03　 04　 05　 06　 07　 08　 09　 0A　 0B　 0C　 0D　 0E　 0F
0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF

顯然，對于PIC單片機來說，三字節(jié)序列[ a b c ]的計算需要綜合圖2和圖3 所示的兩種辦法來進行，下面就給出一個這樣的PIC子程序，它的使用與上面所述的51系列單片機子程序基本相同，即，在第一次被調用之前，先將m1、 m2和m3分別存入通用寄存器BYTEa、BYTEb和BYTEc中；從第二次調用時開始，每次在調用之前只需先將參與本次運算的字節(jié)存入BYTEc即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。每次子程序返回時，計算結果將存放在BYTEa和BYTEb中，最后一次調用返回后，BYTEa和BYTEb分別存放的就是最終結果h和l。子程序中，除BYTEa、BYTEb和BYTEc外，ADDR、RESULTh和RESULTl也是通用寄存器。

圖3 三字節(jié)序列[ a 0 0 ]的計算辦法

START MOVLW DATAe

MOVWF ADDR ；將[e 0 0]余式表首地址DATAe存入ADDR
SWAPF BYTEa，0
ANDLW 0FH ；求e和e指定的[e 0 0] 余式高字節(jié)的相對地址
ADDWF ADDR，1 ；取其絕對地址，存入ADDR
START MOVLW DATAe
MOVF ADDR，0 ；把這一絕對地址再存入W

CALL TABLE ；查表，返回時he00放在W中
MOVWF RESULTh ；把he00存入RESULTh
MOVLW 16
ADDWF ADDR，0 ；求e指定的[e 0 0]余式低字節(jié)的絕對地址
CALL TABLE ；查表，返回時le00放在W中
MOVWF RESULTl ；把le00存入RESULTl
MOVLW DATAf
MOVWF ADDR ；將[f 0 0]余式表首地址DATAf存入ADDR
MOVF BYTEa，0
ANDLW 0FH ；求f和f指定的[f 0 0]余式高字節(jié)的相對地址
ADDWF ADDR，1 ；取其絕對地址，存入ADDR
MOVF ADDR，0 ；把這一絕對地址再存入W
CALL TABLE ；查表，返回時hf00放在W中
XORWF RESULTh，0 ；he00與hf00異或，得ha00，存入W
XORWF BYTEb，0 ；ha00與b異或，得habc，存入W
MOVF BYTEa ；habc存入BYTEa
MOVLW 16
ADDWF ADDR，0 ；求f指定的[f 0 0]余式低字節(jié)的絕對地址
CALL TABLE ；查表,返回時lf00放在W中
XORWF RESULTl，0 ；le00與lf00異或，得la00，存入W
XORWF BYTEc，0 ；la00與c異或，得labc，存入W
MOVF BYTEb ；labc存入BYTEb
RETLW 0