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); }
/** * @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);
とあるので,そうだそうだ, 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 };
生成多項式が 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()
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 (※公開されることはありません)
コメント