MENU

溶けかけてるうさぎ HP GALLERY BLOG TOP RECENT ARTICLES POPULAR ARTICLES ABOUT THIS BLOG

CATEGORY

大学 (140) 仕事 (17) 航空宇宙 (104) 写真 (78) 旅行 (32) 飯・酒 (17) コンピュータ (119) その他 (44)

TAG

ARCHIVE

RECENT

【写真】撮影写真を Map 上に表示できるようにした 【カメラ】X100 シリーズが好きすぎる(主にリーフシャッタ) 【カメラ】X100V から X100VI に買い替えました 【自宅サーバー】Google Domains から Cloudflare にドメインを移管 【カメラ】FUJIFILM XF レンズのサイズ比較ができるようにしてみた

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

事象発生日:2022-01-31

記事公開日:2022-01-31

アクセス数:19483

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 定義(該当コード

 

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

 

C2A では,

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

Rust crate では,

 生成多項式 0x8005refin: true, refout: true,初期値 0x0000xorout: 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]
実行結果

となった.

 

0xa0010x8005 はビット列が反転していることに注意すると,

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

ことが確認できた.

 

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

 

ということなので,Rust の CRC crate をみて,refin: true, refout: truerefin: 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 をともに反転させる計算」の2つを比較する(注意:①②はともに計算結果は同じ).

 

まず,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 に変える』

関連記事

コメントを投稿

名前

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

コメント