CRCでぐちゃったので備忘録

事象発生日：2022-01-31

記事公開日：2022-01-31

アクセス数：776

CRC ，パラメタ多すぎ...．

だれか圧倒的標準を作ってくれ...．

CRC ，理解してもすぐ忘れるので，この際，備忘録を残しておく．

ことの経緯

Rust で衛星フライトソフトウェアを開発していて， CRC を使いたくなった．

そういえば， C で開発しているもう一つの衛星フライトソフトウェアである C2A （詳しくは「こちら」の過去記事）では，標準となる CRC を定義してたよなと思い，コードを確認すると，

uint16_t DS_ISSLFMT_calc_crc(const unsigned char* c, size_t n)
{
  return crc_16_ibm_right(0x0000, c, n, 0);
}

C2A 標準 CRC 呼び出し（該当コード）

/**
 * @brief CRC-16-IBM
 *
 *        生成多項式: x^16 + x^15 + x^2 + 1
 *        ビット送り: 右送り, POLLY: 0xa001
 *        読み出し:   1byte(8 bit)
 * @param[in] crc: CRC初期値
 * @param[in] c: CRCを計算するbyte列
 * @param[in] n: 列の長さ
 * @param[in] rev_flag: 反転するかどうか
 * @return uint16_t: 計算結果
 */
uint16_t crc_16_ibm_right(uint16_t crc, const unsigned char* c, size_t n, int rev_flag);

C2A 標準 CRC 定義（該当コード）

とあるので，そうだそうだ， CRC-16-IBM の右送りだったね，と．

Rust の CRC の Crate をみると， IBM の名が付いてるのは明らかに別物で，色々見る限りは CRC_16_ARC がそれっぽそう．

pub const CRC_16_ARC: Algorithm<u16> = Algorithm { poly: 0x8005, init: 0x0000, refin: true, refout: true, xorout: 0x0000, check: 0xbb3d, residue: 0x0000 };

crc_catalog crate の CRC 定義（該当コード）

生成多項式が 0xa001 と 0x8005 で異なる（ビット列反転してる）が， C2A 上のコードと， Rust のコードと，別で衛星フライトソフトウェアの全再プロ用に昔作った Perl スニペット内部の CRC16 標準（標準 CRC16 とは？）とで，3つともすべて結果が一致したので，ほ～～～．と．

C2A では，

　生成多項式 0xa001，右送り，初期値 0x0000，結果反転なし．

Rust crate では，

　生成多項式 0x8005，refin: true, refout: true，初期値 0x0000，xorout: 0x0000．

結果反転なし と xorout: 0x0000 は同値なのでそれは良いとして，反転周りが謎．

生成多項式違うじゃん？？どっちか嘘ついてない？？

実装して検証

日本では，右送り，左送りはよく聞くけれど，refin, refout （反転）はあまり聞かないなぁ，とか，CRC の原理から考えて，ここらへんが "送り" と同じような意味を持っているんだろうなぁと思い，「反転」と「送り」の両対応した CRC スクリプトを書いてみた．

# coding: UTF-8

def main():
    data = [0xDE, 0xAD, 0xBE, 0xEF]
    calc_crc16("IBM", data, 0x8005, 0x0000, 0, 0, 0x0000, 1)
    calc_crc16("IBM", data, 0x8005, 0x0000, 0, 1, 0x0000, 1)
    calc_crc16("IBM", data, 0x8005, 0x0000, 1, 0, 0x0000, 1)
    calc_crc16("IBM", data, 0x8005, 0x0000, 1, 1, 0x0000, 1)    # 標準
    calc_crc16("IBM", data, 0x8005, 0x0000, 0, 0, 0x0000, 0)
    calc_crc16("IBM", data, 0x8005, 0x0000, 0, 1, 0x0000, 0)
    calc_crc16("IBM", data, 0x8005, 0x0000, 1, 0, 0x0000, 0)
    calc_crc16("IBM", data, 0x8005, 0x0000, 1, 1, 0x0000, 0)
    calc_crc16("IBM", data, 0xA001, 0x0000, 0, 0, 0x0000, 1)
    calc_crc16("IBM", data, 0xA001, 0x0000, 0, 1, 0x0000, 1)
    calc_crc16("IBM", data, 0xA001, 0x0000, 1, 0, 0x0000, 1)
    calc_crc16("IBM", data, 0xA001, 0x0000, 1, 1, 0x0000, 1)
    calc_crc16("IBM", data, 0xA001, 0x0000, 0, 0, 0x0000, 0)
    calc_crc16("IBM", data, 0xA001, 0x0000, 0, 1, 0x0000, 0)
    calc_crc16("IBM", data, 0xA001, 0x0000, 1, 0, 0x0000, 0)
    calc_crc16("IBM", data, 0xA001, 0x0000, 1, 1, 0x0000, 0)

    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 0, 0, 0x0000, 1)    # 標準
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 0, 1, 0x0000, 1)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 1, 0, 0x0000, 1)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 1, 1, 0x0000, 1)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 0, 0, 0x0000, 0)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 0, 1, 0x0000, 0)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 1, 0, 0x0000, 0)
    calc_crc16("CCITT", data, 0x1021, 0xFFFF, 1, 1, 0x0000, 0)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 0, 0, 0x0000, 1)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 0, 1, 0x0000, 1)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 1, 0, 0x0000, 1)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 1, 1, 0x0000, 1)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 0, 0, 0x0000, 0)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 0, 1, 0x0000, 0)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 1, 0, 0x0000, 0)
    calc_crc16("CCITT", data, 0x8408, 0xFFFF, 1, 1, 0x0000, 0)


def calc_crc16(msg, data, poly, init, refin, refout, xorout, is_reft):
    if is_reft:
        crc = _calc_crc16_left(data, poly, init, refin, refout, xorout)
    else:
        crc = _calc_crc16_right(data, poly, init, refin, refout, xorout)
    print(
        msg + ": " + "{:04x}".format(crc)
        + " [poly: "+ "{:04x}".format(poly) + ", init: "+ "{:04x}".format(init) + ",refin: "+ str(refin)
        + ", refout: "+ str(refout) + ", xorout: "+ "{:04x}".format(xorout) + ", is_reft: "+ str(is_reft) + "]"
    )


# ビット列の反転
def _reflect(input, bit_len):
    output = 0
    for i in range(bit_len):
        output = (output << 1) | ((input >> i) & 1)
    return output


# 左送り CRC
def _calc_crc16_left(data, poly, init, refin, refout, xorout):
    if refin:
        init = _reflect(init, 16)
    crc = init

    for x in data:
        if refin:
            x = _reflect(x, 8)
        crc = crc ^ (x << 8)
        for j in range(0, 8):
            if crc & 0x8000:
                crc = poly ^ (crc << 1)
            else:
                crc = crc << 1

    crc = crc & 0xFFFF
    if refout:
        crc = _reflect(crc, 16)
    return crc ^ xorout


# 右送り CRC
def _calc_crc16_right(data, poly, init, refin, refout, xorout):
    if refin:
        init = _reflect(init, 16)
    crc = init

    for x in data:
        if refin:
            x = _reflect(x, 8)
        crc = crc ^ x
        for j in range(0, 8):
            if crc & 0x0001:
                crc = poly ^ (crc >> 1)
            else:
                crc = crc >> 1

    crc = crc & 0xFFFF
    if refout:
        crc = _reflect(crc, 16)
    return crc ^ xorout


if __name__ == "__main__":
    main()

「反転」と「送り」の両対応の CRC 計算コード． `is_reft` で「送り」を切り替えている．（Gist）

実行結果は，

IBM: 962b [poly: 8005, init: 0000, refin: 0, refout: 0, xorout: 0000, is_reft: 1]
IBM: d469 [poly: 8005, init: 0000, refin: 0, refout: 1, xorout: 0000, is_reft: 1]
IBM: d9a7 [poly: 8005, init: 0000, refin: 1, refout: 0, xorout: 0000, is_reft: 1]
IBM: e59b [poly: 8005, init: 0000, refin: 1, refout: 1, xorout: 0000, is_reft: 1]
IBM: dd22 [poly: 8005, init: 0000, refin: 0, refout: 0, xorout: 0000, is_reft: 0]
IBM: 44bb [poly: 8005, init: 0000, refin: 0, refout: 1, xorout: 0000, is_reft: 0]
IBM: 9773 [poly: 8005, init: 0000, refin: 1, refout: 0, xorout: 0000, is_reft: 0]
IBM: cee9 [poly: 8005, init: 0000, refin: 1, refout: 1, xorout: 0000, is_reft: 0]
IBM: cee9 [poly: a001, init: 0000, refin: 0, refout: 0, xorout: 0000, is_reft: 1]
IBM: 9773 [poly: a001, init: 0000, refin: 0, refout: 1, xorout: 0000, is_reft: 1]
IBM: 44bb [poly: a001, init: 0000, refin: 1, refout: 0, xorout: 0000, is_reft: 1]
IBM: dd22 [poly: a001, init: 0000, refin: 1, refout: 1, xorout: 0000, is_reft: 1]
IBM: e59b [poly: a001, init: 0000, refin: 0, refout: 0, xorout: 0000, is_reft: 0]
IBM: d9a7 [poly: a001, init: 0000, refin: 0, refout: 1, xorout: 0000, is_reft: 0]
IBM: d469 [poly: a001, init: 0000, refin: 1, refout: 0, xorout: 0000, is_reft: 0]
IBM: 962b [poly: a001, init: 0000, refin: 1, refout: 1, xorout: 0000, is_reft: 0]
CCITT: 4097 [poly: 1021, init: ffff, refin: 0, refout: 0, xorout: 0000, is_reft: 1]
CCITT: e902 [poly: 1021, init: ffff, refin: 0, refout: 1, xorout: 0000, is_reft: 1]
CCITT: 2c58 [poly: 1021, init: ffff, refin: 1, refout: 0, xorout: 0000, is_reft: 1]
CCITT: 1a34 [poly: 1021, init: ffff, refin: 1, refout: 1, xorout: 0000, is_reft: 1]
CCITT: 18d1 [poly: 1021, init: ffff, refin: 0, refout: 0, xorout: 0000, is_reft: 0]
CCITT: 8b18 [poly: 1021, init: ffff, refin: 0, refout: 1, xorout: 0000, is_reft: 0]
CCITT: 1835 [poly: 1021, init: ffff, refin: 1, refout: 0, xorout: 0000, is_reft: 0]
CCITT: ac18 [poly: 1021, init: ffff, refin: 1, refout: 1, xorout: 0000, is_reft: 0]
CCITT: ac18 [poly: 8408, init: ffff, refin: 0, refout: 0, xorout: 0000, is_reft: 1]
CCITT: 1835 [poly: 8408, init: ffff, refin: 0, refout: 1, xorout: 0000, is_reft: 1]
CCITT: 8b18 [poly: 8408, init: ffff, refin: 1, refout: 0, xorout: 0000, is_reft: 1]
CCITT: 18d1 [poly: 8408, init: ffff, refin: 1, refout: 1, xorout: 0000, is_reft: 1]
CCITT: 1a34 [poly: 8408, init: ffff, refin: 0, refout: 0, xorout: 0000, is_reft: 0]
CCITT: 2c58 [poly: 8408, init: ffff, refin: 0, refout: 1, xorout: 0000, is_reft: 0]
CCITT: e902 [poly: 8408, init: ffff, refin: 1, refout: 0, xorout: 0000, is_reft: 0]
CCITT: 4097 [poly: 8408, init: ffff, refin: 1, refout: 1, xorout: 0000, is_reft: 0]

実行結果

となった．

0xa001 と 0x8005 はビット列が反転していることに注意すると，

「「送り」を反転させるということは，生成多項式のビット列を反転させ，かつ， refin, xorout をともに反転させることに等しい」

ことが確認できた．

自分で CRC を実装すると，それはそう，という感じになるので，実装してみるとちゃんと気づいて理解できる．

ということなので，Rust の CRC crate をみて，refin: true, refout: true や refin: false, refout: false はあっても， refin: true, refout: false などがないのが納得できる．

CRC のライブラリとしては，この「反転」と「送り」のどちらかだけ指定してあげれば，計算するべきものは一意に決まるといわけか．

注意として，ここで言ってる反転は 0/1 のビット反転ではなく，ビット列の反転．結果のビット反転は xorout で制御される．

つまり，

↓ビット列反転
0x8005: 0b1000000000000101
0xa001: 0b1010000000000001

↓ビット反転
0x8005: 0b1000000000000101
0x7ffa: 0b0111111111111010

ってことね．

終わりに

表現が違うだけで，どっちも嘘ついてませんでした．

CRC ，ちょいちょいはまる．

コメントを投稿

名前

Email (※公開されることはありません)

MENU

CATEGORY

TAG

ARCHIVE

RECENT

CRCでぐちゃったので備忘録

ことの経緯

C2A 標準 CRC 呼び出し（該当コード）

C2A 標準 CRC 定義（該当コード）

crc_catalog crate の CRC 定義（該当コード）

実装して検証

「反転」と「送り」の両対応の CRC 計算コード． `is_reft` で「送り」を切り替えている．（Gist）

実行結果

終わりに

関連記事

コメントを投稿

MENU

CATEGORY

TAG

ARCHIVE

RECENT

CRCでぐちゃったので備忘録

ことの経緯

C2A 標準 CRC 呼び出し（該当コード）

C2A 標準 CRC 定義（該当コード）

crc_catalog crate の CRC 定義（該当コード）

実装して検証

「反転」と「送り」の両対応の CRC 計算コード． is_reft で「送り」を切り替えている．（Gist）

実行結果

終わりに

関連記事

コメントを投稿

「反転」と「送り」の両対応の CRC 計算コード． `is_reft` で「送り」を切り替えている．（Gist）