ことの経緯

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_left):
    if is_left:
        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_left: "+ str(is_left) + "]"
    )


# ビット列の反転
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_left で「送り」を切り替えている．（Gist）

実行結果は，

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

実行結果

となった．

 

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

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

ことが確認できた．

 

自分で 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 ，ちょいちょいはまる．

2022/08/18 追記: エンディアンについて

CRC は mod なので，「メッセージ + CRC」というデータを受信した側は，メッセージの CRC を計算して，付与された CRC と突き合わせてもよいが，「メッセージ + CRC」をまるっと CRC 計算にかけて，答え（mod）が 0 になるかでチェックするのが一般的かなと思う．

このとき付与する CRC のエンディアンを，実は気にしなくてはいけないじゃん... という気づきを得たので，追記しておく．

>>> # IBM
>>> data = [0xDE, 0xAD, 0xBE, 0xEF]
>>>
>>> calc_crc16("IBM", data, 0xA001, 0x0000, 0, 0, 0x0000, 0)
IBM: e59b [poly: a001, init: 0000,refin: 0, refout: 0, xorout: 0000, is_left: 0]
>>>
>>> data_with_crc_big_endian = data + [0xE5, 0x9B]
>>> data_with_crc_lit_endian = data + [0x9B, 0xE5]
>>>
>>> calc_crc16("IBM", data_with_crc_big_endian, 0xA001, 0x0000, 0, 0, 0x0000, 0)
IBM: 80a1 [poly: a001, init: 0000,refin: 0, refout: 0, xorout: 0000, is_left: 0]
>>> calc_crc16("IBM", data_with_crc_lit_endian, 0xA001, 0x0000, 0, 0, 0x0000, 0)
IBM: 0000 [poly: a001, init: 0000,refin: 0, refout: 0, xorout: 0000, is_left: 0]
>>>
>>>
>>> # CCITT
>>> data = [0xDE, 0xAD, 0xBE, 0xEF]
>>>
>>> calc_crc16("CCITT", data, 0x1021, 0xFFFF, 0, 0, 0x0000, 1)
CCITT: 4097 [poly: 1021, init: ffff,refin: 0, refout: 0, xorout: 0000, is_left: 1]
>>>
>>> data_with_crc_big_endian = data + [0x40, 0x97]
>>> data_with_crc_lit_endian = data + [0x97, 0x40]
>>>
>>> calc_crc16("CCITT", data_with_crc_big_endian, 0x1021, 0xFFFF, 0, 0, 0x0000, 1)
CCITT: 0000 [poly: 1021, init: ffff,refin: 0, refout: 0, xorout: 0000, is_left: 1]
>>> calc_crc16("CCITT", data_with_crc_lit_endian, 0x1021, 0xFFFF, 0, 0, 0x0000, 1)
CCITT: 372a [poly: 1021, init: ffff,refin: 0, refout: 0, xorout: 0000, is_left: 1]

CRC を付与したビット列で，付与する CRC のエンディアンを変えて計算した結果

っていうね．

はい．

 

直感的な CRC 計算は，左送り（普通に我々がやる割り算と同じ）．

右送りというのはどういうイメージになるかを考えてみる．ただただ送りを逆にしてしまうと，計算結果が変わってしまい，混乱を招くので，「右送りにする」 = 「生成多項式のビット列を反転させ，かつ， refin, xorout をともに反転させること」を思い出し，「① 通常の左送りの計算」と「② 右送りにし，かつ，生成多項式のビット列を反転させ，かつ， refin, refout をともに反転させる計算」の２つを比較する（注意：①②はともに計算結果は同じ）．

 

まず，CRC16 の場合，8 bit の単位を 2 つ合わせて（上の _calc_crc16_right での 変数 crc） 16 bit 整数として計算する．新しい受信データ (8 bit) をその 16 bit 整数に詰め込むときに，左送りである①では，筆算は左の桁から計算するので，最も左の 8 bit に詰め込む（割り算では割られる数の最上位桁が最も重要．そこを消すよう操作する）．一方で右送りでは，最も右の 8 bit に格納することになり，さらに最下位桁を消すように演算していく．その上で，新しい受信データをビット列反転して詰め込み， 16 bit の生成多項式もビット列反転し，そして結果もビット列反転して出力する．

つまり，②は①を鏡に写しながら（左右逆転しながら）計算してることと同値になる（計算結果も鏡像になるが，refout で戻してるので，結果としては①と一致）．

 

では本題に．

「③ 送りだけを反転した CRC 計算」（これは計算結果は元とは異なる）がどうなるかというと，②と比較すると，（CRC計算自体が違うので生成多項式は無視して，）refin, xorout の反転がないだけ，とる．

これがない，ということは，入出力時のエンディアンが変わることになるわけ．

送信側で計算する 16 bit の CRC は xorout によって 16 bit の単位でビット列反転し，それを送られた受信側では， 8 bit 単位で逐次処理するため， 8 bit 単位で refin でビット列反転される（＝ことと同じ意味になる）．これはエンディアン変更と同値．

0b 1011 0101 1101 1111
↓ 16 bit 単位での ビット列反転
0b 1111 1011 1010 1101
↓ 8 bit 単位での ビット列反転
0b 1101 1111 1011 0101
↓ エンディアン変更
0b 1011 0101 1101 1111 < 最初と同じ

別の言い方をすると，右送りにすると，計算途中の CRC (mod) がビット列反転（エンディアン変更した後にバイト内ビット列反転してる状態）ので，mod を 0 にしようと加算する mod （メッセージに付与される CRC）のエンディアンも反転させておかないとだめだよね，ということ．

 

 

うー，，，，我々は，通信パケットではビッグエンディアンを使うので，そもそも C2A での CRC-16-IBM という技術選定は間違ってたね...．

 

しゃあないので↓

GitHub: c2a-core issue #390 『C2A標準CRCを，IBM ではなくビッグエンディアンと相性のいい CCITT に変える』

関連記事