MENU

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

CATEGORY

大学 (130) 仕事 (11) 航空宇宙 (91) 写真 (64) 旅行 (28) 飯・酒 (14) コンピュータ (111) その他 (42)

TAG

ARCHIVE

RECENT

生誕10000日目 記念日 【Archive】「フィルムカメラのススメ」発表スライド (ArkEdge Space LT会) 新卒入社したCookpadを退職しました(後編) ―社会人博士としての2年間― 新卒入社したCookpadを退職しました(前編) ―D進とIT企業への入社と退社― 【資格】第二種電気工事士 取得

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

 

生成多項式が 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_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]
実行結果

となった.

 

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

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

ことが確認できた.

 

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

関連記事

コメントを投稿

名前

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

コメント