<util/crc16.h>: CRC計算

関数
static __inline__ uint16_t	_crc16_update (uint16_t __crc, uint8_t __data)
static __inline__ uint16_t	_crc_xmodem_update (uint16_t __crc, uint8_t __data)
static __inline__ uint16_t	_crc_ccitt_update (uint16_t __crc, uint8_t __data)
static __inline__ uint8_t	_crc_ibutton_update (uint8_t __crc, uint8_t __data)
static __inline__ uint8_t	_crc8_ccitt_update (uint8_t __crc, uint8_t __data)

説明詳細

#include <util/crc16.h>

このヘッダファイルは、一般的な多項式を用いた巡回冗長検査（CRC:cyclic redundancy checks）計算のために最適化されたインライン関数を提供します。

参考文献:

Dallas Semiconductorの、8051アセンブラ例と一般的なCRC最適化提案であるアプリケーションノート27を参照してください。アプリケーションノートの最後のページの表は、これらの実装を理解するうえで重要となります。

Jack Crenshawの"Implementing CRCs" Embedded Systems Programming1992年1月号の記事。これを見つけるのは難しいかもしれないですが、とても明確かつ簡潔な用語で、CRCを説明しています。コピーを入手するための努力の価値があります。

典型的なアプリケーションは、次のようになります。

// Dallas iButton test vector.
uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };

int
checkcrc(void)
{
uint8_t crc = 0, i;

for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
    crc = _crc_ibutton_update(crc, serno[i]);

return crc; // must be 0
}

関数説明

static __inline__ uint16_t _crc16_update ( uint16_t  __crc, uint8_t  __data  )

static

最適化されたCRC-16計算

多項式: x^16 + x^15 + x^2 + 1 (0xa001)
初期化値: 0xffff

このCRCは、通常ディスクドライブコントローラで用いられます。

次は、Cで書かれた同等の関数です。

uint16_t
crc16_update(uint16_t crc, uint8_t a)
{
int i;

crc ^= a;
for (i = 0; i < 8; ++i)
{
    if (crc & 1)
   crc = (crc >> 1) ^ 0xA001;
    else
   crc = (crc >> 1);
}

return crc;
}

static __inline__ uint8_t _crc8_ccitt_update ( uint8_t  __crc, uint8_t  __data  )

static

最適化されたCRC-8-CCITT計算

多項式: x^8 + x^2 + x + 1 (0xE0)

シンプルなCRC-8で使用
初期値: 0x0

CRC-8-ROHCで使用
初期値: 0xff
参考: http://tools.ietf.org/html/rfc3095#section-5.9.1

CRC-8-ATM/ITUで使用
初期値: 0xff
最終XOR値: 0x55
参考: http://www.itu.int/rec/T-REC-I.432.1-199902-I/en

C言語の同等のオリジナルは、Dave Hylandsにより書かれました。アセンブラコードは、_crc_ibutton_update最適化をベースにしています。

次は、Cで書かれた同等の関数です。

uint8_t
_crc8_ccitt_update (uint8_t inCrc, uint8_t inData)
{
    uint8_t   i;
    uint8_t   data;

    data = inCrc ^ inData;

    for ( i = 0; i < 8; i++ )
    {
        if (( data & 0x80 ) != 0 )
        {
            data <<= 1;
            data ^= 0x07;
        }
        else
        {
            data <<= 1;
        }
    }
    return data;
}

static __inline__ uint16_t _crc_ccitt_update ( uint16_t  __crc, uint8_t  __data  )

static

最適化されたCRC-CCITT計算

多項式: x^16 + x^12 + x^5 + 1 (0x8408)
初期値: 0xffff

このCRCは、PPPやIrDAで使用されています。

RFC1171（PPPプロトコル）やIrDA IrLAP 1.1を参照してください。

注意

CCIT多項式は、Xmodemプロトコルで使用されるものと同じですが、これらは全く異なります。違いは、アルゴリズムを介してビットをどのようにシフトさせるかです。Xmodemは、CRCと最初の入力のMSBをシフトし、CCITは、CRCと最初の入力のLSBをシフトします。

次は、Cで書かれた同等の関数です。

uint16_t
crc_ccitt_update (uint16_t crc, uint8_t data)
{
    data ^= lo8 (crc);
    data ^= data << 4;

    return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) 
            ^ ((uint16_t)data << 3));
}

static __inline__ uint8_t _crc_ibutton_update ( uint8_t  __crc, uint8_t  __data  )

static

最適化されたDallas（現Maxim） iButton 8-bit CRC計算

多項式: x^8 + x^5 + x^4 + 1 (0x8C)
初期値: 0x0

http://www.maxim-ic.com/appnotes.cfm/appnote_number/27を参照してください。

次は、Cで書かれた同等の関数です。

uint8_t
_crc_ibutton_update(uint8_t crc, uint8_t data)
{
uint8_t i;

crc = crc ^ data;
for (i = 0; i < 8; i++)
{
    if (crc & 0x01)
        crc = (crc >> 1) ^ 0x8C;
    else
        crc >>= 1;
}

return crc;
}

static __inline__ uint16_t _crc_xmodem_update ( uint16_t  __crc, uint8_t  __data  )

static

最適化されたCRC-XMODEM計算

多項式: x^16 + x^12 + x^5 + 1 (0x1021)
初期値: 0x0

このCRCは、Xmodem-CRCプロトコルで使用されています。

次は、Cで書かれた同等の関数です。

uint16_t
crc_xmodem_update (uint16_t crc, uint8_t data)
{
    int i;

    crc = crc ^ ((uint16_t)data << 8);
    for (i=0; i<8; i++)
    {
        if (crc & 0x8000)
            crc = (crc << 1) ^ 0x1021;
        else
            crc <<= 1;
    }

    return crc;
}