<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)

---

詳しい説明

 #include <util/crc16.h>

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

参考文献:

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

Jack Crenshawの"Implementing CRCs" Embedded Systems Programming 1992年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__ uint16_t _crc_ccitt_update	(	uint16_t	__crc,
		uint8_t	__data
	)		[static]

最適化されたCRC-CCITT計算

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

これは、PPPやIrDAで使用されるCRCです。

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

これは、Xmodem-CRCプロトコルで使用される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;
    }