单片机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个字节的程序存储空间，但对于PIC单片机来说还是太大了，需要再进行压缩。思路是这样的： 将Ta00＝[a 0 0 ]分解成Te00＝[e 0 0 ]和Tf00＝[f 0 0 ]，并使字节e的上半字节内容与a的上半字节相同但下半字节为零，同时使字节f的下半字节内容与a的下半字节相同但上半字节为零，然后用Te00和Tf00生成余式表来代替Ta00余式表。由于Te00和Tf00中只有半个字节不为零，所以，每个余式表只需16个单元（32个字节），两个余式表总共只占用64个字节，这样就可满足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。这样，三字节序列[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单片机来说，三字节序列[ a b c ]的计算需要综合图2和图3 所示的两种办法来进行，下面就给出一个这样的PIC子程序，它的使用与上面所述的51系列单片机子程序基本相同，即，在第一次被调用之前，先将m1、 m2和m3分别存入通用寄存器BYTEa、BYTEb和BYTEc中；从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入BYTEc即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。每次子程序返回时，计算结果将存放在BYTEa和BYTEb中，最后一次调用返回后，BYTEa和BYTEb分别存放的就是最终结果h和l。子程序中，除BYTEa、BYTEb和BYTEc外，ADDR、RESULTh和RESULTl也是通用寄存器。

图3 三字节序列[ a 0 0 ]的计算办法

START MOVLW DATAe

MOVWF ADDR ；将[e 0 0]余式表首地址DATAe存入ADDR
SWAPF BYTEa，0
ANDLW 0FH ；求e和e指定的[e 0 0] 余式高字节的相对地址
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]余式低字节的绝对地址
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]余式高字节的相对地址
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]余式低字节的绝对地址
CALL TABLE ；查表,返回时lf00放在W中
XORWF RESULTl，0 ；le00与lf00异或，得la00，存入W
XORWF BYTEc，0 ；la00与c异或，得labc，存入W
MOVF BYTEb ；labc存入BYTEb
RETLW 0