CRCアルゴリズムの導出とc++コードの実現(エッセンス)

26017 ワード
アルゴリズム
CRCアルゴリズムの導出とc++コードの実現(エッセンス)
背景知識:
ウィキペディア
CRC計算の関係式:
M(x)∗(x n)＝Q(x)∗K(x)−R(x)M(x)＊(x^n)＝Q(x)＊K(x)−R(x)M(x)∗(xn)＝Q(x)∗K(x)−R(x)のうち:
  • M(x)は元の情報多項式であり、元の情報は2進数で表される.例えば101は多項式に対応する係数1∗(x 2)+0∗(x 1)+1∗(x 0)=x 2+1∗(x^2)+0*(x^1)+1*(x^0)=x^2+1∗(x 2)+0∗(x 0)=x^2+1
  • K(x)はn次の特徴多項式である.すなわち、K(x)の最上位はnであり、CRC 16,n=16のようなx n x^n xn項を必ず含む.最上位はx 16 x^{16}x 16
    • を含む.
  • R(x)は、剰余多項式、すなわちCRC検査結果
    • である.
  • Q(x)はM(x)∗(x)/K(x)M(x)*(x^n)/K(x)M(x)∗(xn)/K(x)の商
    • である
    送信側送信データ:M(x)∗(x n)+R(x)M(x)*(x^n)+R(x)M(x)∗(xn)+R(x)、すなわちM(x)左シフトnビット+CRCチェックR(x)
    受信者検証データ:
  • 1計算M(x)∗(xn)+R(x)M(x)*(x^{n})+R(x)M(x)∗(xn)+R(x)がK(x)で割り切れるかどうか、残数は0、正しいデータが受信され、残数は0ではなく、エラーデータ
    • が受信される
  • 2計算M(x)のCRC検査結果がR(x)であるかどうか、検査は同じ、データは正しい、検査は異なるデータエラー
    • である.
    例CRC-16-BM、Modbusプロトコル:
  • 特徴多項式x 16+x 15+x 2+1 x^{16}+x^{15}+x^{2}+1 x 16+x 15+x 25+x 2+1対応多項式係数=1 1,000,000,000,000,0101すなわち2進法16,15,22 0位それぞれ1 16進式特徴多項式係数POLY=0 x 18005 CRC-16-つまり16ビット2進法を採用して16ビット下を切り取るのでPOLY=0 x 8005
  • 入力データ:0x7e 0x01 0x11 0x00
    • 以下は通信双方の約束です.
  • 計算の初期値:0 xFFFF
  • 結果排他的論理和値:0 x 0000で計算された(CRC-16)排他的論理和0 x 0000
  • 入力データ反転:true ( ， , 1100 0100 0010 0011)
  • 出力データ(CRC-16)反転:true (16 ) ( ， , 1010 0010 0011 1001 1001 1100 0100 0101 )
    • 分析計算:
  • 入力データ:M(x)=0x7e 0x01 0x11 0x00バイト毎反転M(x)=0x7e 0x80 0x88 0x00 2進数表示:M(x)=0111 1110 - 1000 0000 -1000 1000 - 0000 0000
  • 特徴多項式:K(x)=0x80 0x05 2進数表現:K(x)=1000 0000 - 0000 0101
  • nの値:K(x)の最高次n=16
  • M(x)∗x n=M(x)∗x 16 M(x)*x^{n}=M(x)*x^{16}M(x)*x^{16}M(x)∗xn=M(x)∗x 16は、M(x)左シフト16ビットに相当する:M(x)∗x 16 M(x)*x^{16}M(x)*x^{16}M(x)∗x 16=0x7e 0x80 0x88 0x00 0x00 0x00 2進数をM(x)*x^{16}M(x)*x^{16}M(x)*x^{16}M(x)M(x(x)*x^{16}M(x)M(x(x)x^x^∗x 16=0111 1110 - 1000 0000 - 1000 1000 - 0000 0000 - 0000 0000 - 0000 0000
  • 型2除算:M(x)∗x 16<型2÷>K(x)*x^{16}<型2÷>K(x)M(x)∗x 16<型2÷>K(x)=0111 1110 - 1000 0000 - 1000 1000 - 0000 0000 - 0000 0000 - 0000 0000/1000 0000 - 0000 0101=0 xfcae 141 a+0 xa 239
  • 商Q(x)=0 xfcae 141 a
  • 剰余R(x)=0 xa 239
  • 出力データ0 xa 239反転=0 x 9 c 45
  • 結果(0 x 9 c 45異または0 x 0000)=0 x 9 c 45、すなわち最終的なCRC結果
    • 多項式除算の例
    入力データM(x)=1111 M(x)=1111 M(x)=1111 M(x)=1111除数K(x)=1101 K(x)=1101 K(x)=1101は最高次n=3次であり、x 3 x^{3}x 3 n=3 n=3 n=3 n=3を含むので、左シフト3ビット被除数M(x){8727; x 3)=1111000 M(x)*(x^{3})=1111 000 M(x){8727; x 3)=111000
    111 1000  ----     M(x)=1111 ，n=3   ,  3      M(x)*(x^3) = 1111 000 
110 1	  ----   K(x)，    n=3 ，   x^{3} 
001 0000	      	      1  1 ，    （ 2     ），    1 
----------------------------------------------------------------------
-01 0000
-11 01
-01 0000		      0  0 ，     （ 2     ），    ，  1 
----------------------------------------------------------------------
--1 0000
--1 101
--0 1010		      1  1 ，    （ 2     ），      1 
----------------------------------------------------------------------
--- 1010
--- 1101
--- 0111		      1  1 ，    （ 2     ），    


  ：   1011 ，    0111

    したがって、CRCは、剰余CRC=01111(2進)=0 x 07(16進)である
    C++コードは以下の通りです.
    //--creater by wmx 2020 - 6 -14

#include 
#include 



typedef signed char qint8;         /* 8 bit signed */
typedef unsigned char quint8;      /* 8 bit unsigned */
typedef short qint16;              /* 16 bit signed */
typedef unsigned short quint16;    /* 16 bit unsigned */
typedef int qint32;                /* 32 bit signed */
typedef unsigned int quint32;      /* 32 bit unsigned */


/*!
 * \brief calculate_crc16      16 CRC    
 * \param CRC_INIT          CRC16      
 * \param CRC_POLY               
 * \param CRC_RESULT_XOR         
 * \param input_invert             
 * \param ouput_invert             
 * \param inputData                  
 * \param inputDataLen             
 * \return                  16 CRC    
 */
quint16 calculate_crc16(quint16 CRC_INIT,quint16 CRC_POLY,quint16 CRC_RESULT_XOR,bool input_invert,bool ouput_invert,const char *inputData, int inputDataLen)
{   
    quint8 data_item = 0;

    //-- 
    quint32 ans = 0;


    while (inputDataLen--)
    {
        data_item = *(inputData++);

        //      (       ，       , 1100 0100    0010 0011)
        if(input_invert)
        {
            printf("        data_item = %02x 
    "    ,data_item);
            quint8 temp_char = data_item;
            data_item=0;
            for(int i=0;i<8;++i)
            {
                if(temp_char&0x01)
                    data_item|=0x01<<(7-i);
                temp_char>>=1;
            }
            printf("       data_item = %02x 
    "    ,data_item);
        }

        //---     ----------------------
        //--- 2         
        //--- 2      CRC     

        //        R(x)=CRC，   CRC_INIT,           
        //data_item   16 ，     ,
        CRC_INIT ^= (data_item << 8);

        //--             2  
        for (int i = 0; i < 8; i++)
        {
            //--    16    2  
            if (CRC_INIT & 0x8000){//--    1,  1,   2  
                CRC_INIT = (CRC_INIT << 1) ^ CRC_POLY;
                ans += 1;
            }
            else{//--    0,  0,    ,    2  
                CRC_INIT = CRC_INIT << 1;
                ans += 0;
            }
            ans = ans<<1;
        }  
        ans<<1;
    }
    printf("  ans = %02x 
    "    ,ans);
    printf("   CRC_INIT = %02x 
    "    ,CRC_INIT);

    //   (16 )   (       ，       , 1010 0010 0011 1001    1001 1100 0100 0101 )
    if(ouput_invert)
    {
        printf("        CRC_INIT = %02x 
    "    ,CRC_INIT);
        quint16 temp_short = CRC_INIT;
        CRC_INIT=0;
        for(int i=0;i<16;++i)
        {
            if(temp_short&0x01)
                CRC_INIT|=0x01<<(15-i);
            temp_short>>=1;
        }
        printf("        CRC_INIT = %02x 
    "    ,CRC_INIT);
    }
    printf("      CRC_INIT^CRC_RESULT_XOR = %02x 
    "    ,CRC_INIT^CRC_RESULT_XOR);
    return (CRC_INIT^CRC_RESULT_XOR);
}

using namespace std;
int main(int argc, char *argv[])
{
    char buf4[4]={0x7e,0x01,0x11,0x00};
    char buf5[4]={0x7e,0x80,0x88,0x00};
    quint16 result4 =calculate_crc16(0xFFFF,0x8005,0x0000,true,true,buf4,sizeof (buf4));
//    quint16 result5 =calculate_crc16(0xFFFF,0x8005,0x0000,false,true,buf5,sizeof (buf5));
    printf("result4 = %04x 
    "    ,result4);
//    printf("result5 = %04x 
    ",result5);    
    return 0;
}
    [Kotlin]扱いやすいenum
    C++の参照の詳細