任意の CRC値を導出する

この文書は次の要目について解説している。

• 任意のマジックナンバーを導出するCRCを求める。
• データ中の任意の位置にCRCを埋め込む。

文書中のサンプルコード例はperl言語で示しているが、記法はともあれ文脈はC言語と同等なので任意の言語に適宜読み替えて頂きたい。

前説

一般的な CRC（巡回冗長検査）の使い方は、データ塊の損傷を検出することだ。選択したアルゴリズムと「初期値」でデータ塊先頭から末尾までを走査し、最後に導かれる値が予め決められた「マジックナンバー」と合致するか調べる。合致しなければそのデータ塊は信用できないので破棄し、再送を要求したりする。

          +-------+-------+      +---------+-------+-------+
Stream -> | DATA1 | DATA2 | .... | DATAn-1 | DATAn |  CRC  |     EOF
          +-------+-------+      +---------+-------+-------+
Register        \       \                \        \      \           Magic
    Init   ->   update  update ....      update   update  update ?== number

CRCの計算は暗号論的ハッシュ関数より高速な計算かつ結果がコンパクトなので、数百バイト〜数十KiBオーダーのデータ塊で、チェックサムの代わりに重用される。特に書き換え寿命が存在する不揮発メモリのエラー検出用途には有用だ。しかし一般に CRC検査値は、データ塊の最後に付加する。

一般的なチェックサムは情報理論で言うハミング距離が十分でないため、せいぜい数十バイト程度までが本来の実用範囲である。

近代の MCUには Flashメモリ改竄検出用途で CRC走査検証機能（CRCSCAN）をハードウェアとして備えていることが多いが、それらは一般に Flashメモリ領域全体を走査する。すると Flashメモリに格納するプログラムコードを改訂するたびに Flash領域の特定位置に CRC値を書き込む必要がある。ところがこれだとプログラムコードのバイナリと連続した位置にないために、CRCは別のバイナリに分けねばならない。個別のファイルに分けたりそれぞれのアドレス情報を不可分で管理するのは難しくはないものの少々面倒だ。

How to use CRCSCAN
+--------------+-----    -----+------------+
| Program code | unused space |     CRC    | -> Magicnumber ?
+--------------+-----    -----+------------+
|<-  File-1  ->|              |<- File-2 ->|

そこでプログラムコードの直後に直接「まとめて」CRC計算値を付加することを考える。
この時、CRCSCANはその CRC値が書かれている本来の終了位置を全く知らないと仮定する。CRCSCAN はプログラムコード領域を超えて未使用領域（一般にそれは全て0xFFで初期化されているはずだ）も続けて走査し、実装されている Flash領域全体を走査し終えるまでは停止しないだろう。そして最終結果の「マジックナンバー」が期待値と合致しなければ「改竄検出」となって例外割り込みを吐くことになる。では最終的に得られる「マジックナンバー」が矛盾することなく、走査対象領域の途中に「正しいCRC計算結果に導く」値を埋め込むことはできるだろうか、というのが本書の主題だ。

I want to do this
+--------------+------+-----          -----+
| Program code | CRC? |    unused space    | -> Magicnumber ?
+--------------+------+-----          -----+
|<-    One File     ->|

CRC 計算のおさらい

バイトストリームの CRCを計算する関数の例をあげる。

CRC算出は大雑把に説明すると多項式（Plynomial）で定まる値で数百数千桁に及ぶ入力データ全体を除し、その剰余を求める計算だ。ただし普通の除算が「引き算の繰り返し」であるところを「排他的論理和」で置き換えている。

ここでは計算速度を重視しないのでよくある計算済テーブル参照ではなく、見やすさを優先して多項式（Plynomial）とビットシフトループを組み合わせた記述とする。入力されるデータ塊を MSB/LSBどちらから処理するかによってシフト方向も変わるため、この関数も 2種類が書ける。計算結果の CRC値のバイト並びも、LSB優先ならリトルエンディアン、MSB優先ならビッグエンディアンとなる。

# LSB first, right rotation, result CRC is little endian
sub update_crc_ror {
  my($crc, $data) = @_;
  $crc ^= $data;
  for (my $i = 0; $i < 8; $i++) {
    $crc = ($crc >> 1) ^ ($polynomial & -($crc & 1));
  }
  return $crc;
}

# MSB first, left rotation, result CRC is big endian
sub update_crc_rol {
  my($crc, $data) = @_;
  my $ls = $bitwidth - 8;
  my $rs = $bitwidth - 1;
  $crc ^= ($data << $ls);
  for (my $i = 0; $i < 8; $i++) {
    $crc = ($crc << 1) ^ ($polynomial & -(($crc >> $rs) & 1));
  }
  return $mask & $crc;
}

それぞれのループ内部は1行になっているが、より饒舌に記述するなら以下の条件式に等価である。いずれもビットシフトによって追い出される端ビットの真偽によって多項式値を Xorするかどうか決めるものだ。-($crc & 1)あるいは-(($crc >> $rs) & 1)は結果が0か-1（0の1の補数:全ビットが1）に定まることを用いて論理和に置き換え、条件式を消している。

### LSB first
# $crc = ($crc >> 1) ^ ($polynomial & -($crc & 1));
if ($crc & 1) { $crc = ($crc >> 1) ^ $polynomial; }
else          { $crc >>= 1;                       }

### MSB first
# $crc = ($crc << 1) ^ ($polynomial & -(($crc >> $rs) & 1));
if (($crc >> $rs) & 1) { $crc = ($crc << 1) ^ $polynomial; }
else                   { $crc <<= 1;                       }

さらなる最適化でテーブル参照に頼らずとも 8ビットループを消すこともできるが、ここではそこまで踏み込まない。付録を参照。

これらをメモリ上のバイトストリームに適用するには、以下のラッパー関数を用いる。さらに幾つかの補助関数も定義しよう。

# $buff を $stop 位置まで走査する
sub encoder {
  my($buff, $stop) = @_;
  my $crc = $initialize;
  my $index = 0;
  while ($index < $stop) {
    $crc = &$encoder($crc, get_byte($buff, $index));
    $index++;
  }
  return $crc;
}

# $buff の $index 位置を1バイト読み取る
sub get_byte {
  my($buff, $index) = @_;
  return vec($buff, $index, 8);
}

# エンディアンによって異なるバイト並びを読み書きするpack/unpackフォーマット指示子
my $fmt = ${["v","n","V","N"]}[$endian | ($bitwidth == 32 ? 2 : 0)];

# $buff の $index 位置から 2または 4バイトを読み取る
sub get_word {
  my($buff, $index) = @_;
  return unpack $fmt, substr($buff, $index, ($bitwidth >> 3));
}

# $buff の $index 位置から 2または 4バイトを書き込む
sub set_word {
  my($buff, $index, $data) = @_;
  substr $$buff, $index, ($bitwidth >> 3), pack($fmt, $data);
}

これらを用いて文字列"123456789"から「普通の」CRC32を求めてみよう。

### CRC32 パラメータ
my $mask       = 0xFFFFFFFF;        # ビット溢れマスク
my $initialize = 0xFFFFFFFF;        # 初期値
my $polynomial = 0xEDB88320;        # 多項式値
my $encoder    = \&update_crc_ror;  # CRC計算関数
my $endian     = 0;                 # リトルエンディアン=0
my $bitwidth   = 32;                # CRCビット幅

my $test = "123456789";
my $crc = encoder($test, 9);  # 先頭から9文字を入力
printf "0x%08X\n", $crc;      # 結果

# 0xCBF43926

この結果が正しいかどうかは、オンラインCRC計算サイトなどで検算してみてほしい。

https://crccalc.com/?crc=123456789&method=crc32&datatype=ascii&outtype=0

次に得られた結果を元の文字列に加えて、正しい「マジックナンバー」が得られるかを確認する。前述のテストコードは次のように書き変わる。

my $test = "123456789";
my $crc = encoder($test, 9);  # 先頭から9文字を入力
set_word(\$test, 9, $crc);    # 結果を入力末尾に加える（エンディアンに注意）

$crc = encoder($test, 13);    # 先頭から末尾まで再計算
printf "0x%08X\n", $crc;      # 結果

# 0x00000000

CRC32の「マジックナンバー」はゼロなので、この結果は正しい。

CRC 巻き戻し計算

今度は、対象バイトストリームを末尾から逆回しで CRCを計算することを考える。計算手順が逆になる訳だから「マジックナンバー」から計算を始め、バイトストリームのビットシフト方向も逆になり、最終的に「初期値」が合致すれば正しい結果になるはずだ。前述のupdate_crc_ro*と見比べてほしい。

# LSB first, right rotation, result CRC is little endian
# Unwind : MSB first, left rotation, result CRC is little endian
sub unwind_crc_ror {
  my($crc, $data) = @_;
  my $rs = $bitwidth - 1;
  for (my $i = 0; $i < 8; $i++) {
    $crc = ($crc << 1) ^ ($unwinding & -(($crc >> $rs) & 1));
  }
  return $mask & $crc ^ $data;
}

# MSB first, left rotation, result CRC is big endian
# Unwind : LSB first, right rotation, result CRC is little endian
sub unwind_crc_rol {
  my($crc, $data) = @_;
  my $ls = $bitwidth - 8;
  for (my $i = 0; $i < 8; $i++) {
    $crc = ($crc >> 1) ^ ($unwinding & -($crc & 1));
  }
  return $crc ^ ($data << $ls);
}

$dataを Xor する位置が最後になる以外の記述は、処理ループ内の MSB/LSBシフト方向が逆になる。少し違うのは多項式値$polynomialの代わりに定数$unwindingを使う点だ。これは次のように定義される値で、updateでは「シフトで追い出されるビットを評価」していたのと対になっており、1ビット未来の（正順では過去の）ビットを評価して多項式値を Xor するものだ。

LSB first : Unwinding = (Polynomial << 1) | LSB
MSB first : Unwinding = (Polynomial >> 1) | MSB

多項式Polynomialの定義値は LSB優先用では MSBが、MSB優先用では LSBが、必ず1であることに留意。従ってUnwindingは追い出される側のビットが常に1であり、よって逆側のビットが必ず1になる。

以上の逆計算関数をバイトストリームに対して逆走査を行うには、以下のラッパー関数を使用する。

# $buff を $length-1 から $stop 位置まで逆走査する
sub decoder {
  my($buff, $stop, $length) = @_;
  my $crc = $finalize;
  while (--$length >= $stop) {
    $crc = &$decoder($crc, get_byte($buff, $length));
  }
  return $crc;
}

先述のテストコードを書き換えて、その挙動を見てみよう。

### CRC32 パラメータ
my $mask       = 0xFFFFFFFF;        # ビット溢れマスク
my $initialize = 0xFFFFFFFF;        # 初期値
my $polynomial = 0xEDB88320;        # 多項式値
my $finalize   = 0;                 # 追加：マジックナンバー
my $unwinding  = 0xDB710641;        # 追加：逆多項式値 (Polynomial << 1) | LSB
my $encoder    = \&update_crc_ror;  # CRC計算関数
my $decoder    = \&unwind_crc_ror;  # 追加：CRC逆計算関数
my $endian     = 0;                 # リトルエンディアン=0
my $bitwidth   = 32;                # CRCビット幅

my $test = "123456789";
my $crc = encoder($test, 9);  # 先頭から9文字を入力
set_word(\$test, 9, $crc);    # 結果を入力末尾に加える

$crc = encoder($test, 13);    # 先頭から末尾まで順計算
printf "0x%08X\n", $crc;      # 結果

$crc = decoder($test, 0, 13); # 末尾から先頭まで逆計算
printf "0x%08X\n", $crc;      # 結果

# 結果 # CRC32 の場合
# 0x00000000  == マジックナンバー
# 0xFFFFFFFF  == 初期値

先頭までの逆回転の結果0xFFFFFFFFが得られたが、これは初期値$initializeと正しく一致する。

ではこれをデータ塊の任意の中間位置まで、前後からそれぞれ計算させてみよう。

my $test = "123456789";
my $crc = encoder($test, 9);  # 先頭から9文字を入力
set_word(\$test, 9, $crc);    # 結果を入力末尾に加える

$crc = encoder($test, 5);     # 先頭から先頭5文字目までを順計算
printf "0x%08X\n", $crc;      # 結果

$crc = decoder($test, 5, 13); # 末尾から先頭5文字目までを逆計算
printf "0x%08X\n", $crc;      # 結果

# 結果 # CRC32 の場合
# 0x340AC5E3
# 0x340AC5E3

両者はぴったり同じ値を導き出す。中間位置の指定を（このデータ塊の場合は0〜9の範囲で）どのように変化させても、同様に両者の結果が等しくなるはずだ。

任意の位置に CRC を埋め込む

以上で材料は揃った。今度はデータ塊の任意の位置に CRC を埋め込み、全体の CRC が「マジックナンバー」に合致するか検証してみよう。埋め込み予定位置には適当なプレースホルダーを用意しておく。

my $test = "12345____6789";         # 5文字目からがプレースホルダー（PH）

my $crcA = encoder($test, 5);       # 先頭から PH までの CRC(A)を求める
printf "0x%08X\n", $crcA;

my $crcB = decoder($test, 5, 13);   # 末尾から PH までの CRC(B)を求める
printf "0x%08X\n", $crcB;

my $base = get_word($test, 5);      # PH の現在値(BASE)を取得する
printf "0x%08X\n", $base;

my $crcC = $crcA ^ $crcB ^ $base;   # CRC(C) = CRC(A) ^ CRC(B) ^ BASE
printf "0x%08X\n", $crcC;

set_word(\$test, 5, $crcC);         # 求めた CRC(C) を PH に上書きする

my $crc = encoder($test, 13);       # 先頭から末尾までの CRC（マジックナンバー）を検算
printf "0x%08X\n", $crc;

# 結果 # CRC32 の場合
# 0x340AC5E3  index=5 までの正順 $crcA
# 0xE837DD1E  index=5 までの逆順 $crcB
# 0x5F5F5F5F  index=5 取得 -> $base "____"
# 0x836247A2  index=5 上書 <- $crcA ^ $crcB ^ $base
# 0x00000000  検算結果 == マジックナンバーに一致

全体CRCが間違っている状態では、前後からプレースホルダーの位置までの CRC／逆CRC を求めても当然合致することはない。両者が合致するよう補正するには両者の Xor 値にさらに現在のプレースホルダー値を Xor した上で、プレースホルダー位置の情報を書き換える。こうするとうまい具合にプレースホルダー位置で内部計算値が補正され、全体を走査して最終的に得られる「マジックナンバー」が正しく導出されるようになる。

逆順の計算ではプレースホルダーまで含めて走査していることに注意したい。その影響を打ち消すため、CRC(B) に当該プレースホルダー値を Xor する。そして CRC(A) との Xor 結果がゼロになるよう、さらなる Xor を求めると、それが（プレースホルダー位置にあるべき）正しい中間埋め込み CRC値になるわけだ。

プレースホルダー位置を事前にゼロで埋めているなら、計算量は1ステップ減らせる。

CRC の弱点

ここまでに述べた手段を使うと、バイトストリーム最後の本来 CRCが示されるべき値を、任意の自由な値に変更することができる。前説で述べたような常に全バイトが0xFFで充填されている Flashメモリの未使用領域を想定する用途以外にも、常に独自の同じ値に固定したり、はたまた独自の「マジックナンバー」を算出させたりすることで、エラー検出のダブルチェックに応用することもできる。

当然データの途中を差し替えつつ最後の CRC値をうまく誤魔化したりもできる。そもそもエラー検出用途の CRC を改竄検出に使うこと自体が間違いなので、これはどうしようもない。そういう用途では暗号論的ハッシュ関数を使うべきだし、CRCは計算が単純すぎてその代用にはならないのだ。

実のところ一旦 CRC値がゼロに定まった後の、連続する0x00バイトストリームはもはや内部計算値を変化させない。原理的に「除算の剰余」を求める計算なので、100も 1000も 10000 も等しく 10で割ったら同じゼロが求まるのと同じ理屈だ。

my $test = "123456789";
my $crc = encoder($test, 9);  # 先頭から9文字を入力
set_word(\$test, 9, $crc);    # 得られた CRCを入力末尾に加える

$crc = encoder($test, 13);    # 先頭から末尾まで再計算
printf "0x%08X\n", $crc;      # 結果

$test .= "\0" x 1;            # 末尾に \0 を追加
$crc = encoder($test, 14);    # 先頭から末尾まで再計算
printf "0x%08X\n", $crc;      # 結果

$test .= "\0" x 4;            # 末尾に \0 を追加
$crc = encoder($test, 18);    # 先頭から末尾まで再計算
printf "0x%08X\n", $crc;      # 結果

# 結果 # CRC32 の場合
# 0x00000000
# 0x00000000
# 0x00000000

この場合「連続するゼロ」の最後に連なる CRC値もまた「ゼロ」なので、エラー検出の精度がその分劣ることになる。この問題を緩和するには次に挙げる方法がある。

CRC32/Ethernet の場合

CRC計算アルゴリズムにはいくつもの亜種があるが、データ塊の最後に CRCを付加する際、全ビット反転（1の補数との Xor）して出力する形式のものが多く見られる。CRC32/Ethernet（あるいはCRC32/BZIP2）はその代表例だ。その定義パラメーターは次のようになる。

### CRC32/BZIP2 (Ethernet) パラメータ
my $mask       = 0xFFFFFFFF;
my $initialize = 0xFFFFFFFF;
my $polynomial = 0x04C11DB7;  # Polynomial reflection 0xEDB88320
my $finalize   = 0xC704DD7B;  # Magicnumber
my $xor        = 0xFFFFFFFF;
my $unwinding  = 0x82608EDB;  # (Polynomial >> 1) | MSB
my $encoder    = \&update_crc_rol;
my $decoder    = \&unwind_crc_rol;
my $endian     = 1;           # ビッグエンディアン=1
my $bitwidth   = 32;

シフト方向が左送りかつビッグエンディアン記録なので、使用する$encoder/$decoder関数が異なるほか、多項式／逆多項式のビットパターンも右送りとは左右鏡像になる。そして「マジックナンバー」にゼロではない特別な値が出てくる。

このゼロでない「マジックナンバー」は「初期値の1の補数」に対する CRC値として求めることができる。

my $test = '';  # CRC の 1の補数だけを持つデータ塊を作る
set_word(\$test, 0, $initialize ^ $xor);

my $crc = encoder($test, 4);  # 全体を走査
printf "0x%08X\n", $crc;

# 結果 == CRC32/Ethernet のマジックナンバー
# 0xC704DD7B

全体の CRCの求め方は「1の補数でXorしない」通常の CRC計算と同じだが、データ末尾に加えるときには「1の補数でXor」して行う。そのデータ塊全体の再走査を行うと、それがどんなデータ塊であっても正しい（Xorされた）CRCを付加されているなら、件の「マジックナンバー」に必ず定まる。

my $test = "123456789";
my $crc = encoder($test, 9);      # 先頭から9文字を入力
set_word(\$test, 9, $crc ^ $xor); # 結果の1の補数を入力末尾に加える

$crc = encoder($test, 13);        # 先頭から末尾まで再計算
printf "0x%08X\n", $crc;          # 結果

$crc = encoder($test, 5);         # 先頭から先頭5文字目までを順計算
printf "0x%08X\n", $crc;          # 結果

$crc = decoder($test, 5, 13);     # 末尾から先頭5文字目までを逆計算
printf "0x%08X\n", $crc;          # 結果

# 結果 # CRC32/Ethernet の場合
# 0xC704DD7B    全体の結果 == マジックナンバーに一致
# 0xBD9AB747    先頭から途中まで走査 == 普通の CRC
# 0xBD9AB747    末尾から途中まで走査 == 普通の CRC（先頭からと一致）

このデータ塊に対して、先頭から途中までの CRCを求めた場合は普通の CRCだ。末尾から途中まで逆順に求めた場合の CRCも矛盾なくそれに一致するが、これはdecoderラッパー関数が（最終結果の）「マジックナンバー」を初期値として逆順計算を始めるからである。

ここでは末尾の Xor 値を元に戻さないまま走査していることに留意。あえて元に戻して走査すると「マジックナンバー」はゼロが求まる。

当然、データ塊の途中に CRCを埋め込む場合の手順も、通常の場合と同じになる。

my $test = "12345____6789";         # 5文字目からがプレースホルダー（PH）

my $crcA = encoder($test, 5);       # 先頭から PH までの、初期値からの CRC(A)を求める
printf "0x%08X\n", $crc1;

my $crcB = decoder($test, 5, 13);   # 末尾から PH までの、マジックナンバーからの CRC(B)を求める
printf "0x%08X\n", $crc2;

my $base = get_word($test, 5);      # PH の現在値(BASE)を取得する
printf "0x%08X\n", $base;

my $crcC = $crcA ^ $crcB ^ $base;   # CRC(C) = CRC(A) ^ CRC(B) ^ BASE
printf "0x%08X\n", $crcC;

set_word(\$test, 5, $crcC);         # 求めた CRC(C) を PH に上書きする

my $crc = encoder($test, 13);       # 先頭から末尾までの CRC（マジックナンバー）を検算
printf "0x%08X\n", $crc;

# 結果 # CRC32/Ethernet の場合
# 0xBD9AB747  index=5 までの正順 $crcA
# 0x4647CE4E  index=5 までの逆順 $crcB
# 0x5F5F5F5F  index=5 取得 -> $base "____"
# 0xA4822656  index=5 上書 <- $crcA ^ $crcB ^ $base
# 0xC704DD7B  検算結果 == マジックナンバーに一致

まとめ

• CRC検証値の再計算は簡単。
• 普通は最後にある CRC値を自由に定め、途中に補正 CRCを埋め込むのも簡単。
• CRCは高速な計算かつコンパクトな結果を求められるが、容易に改竄できるので暗号論的ハッシュ関数の代用には到底ならない。

付録

CRC-16/MCRF4XXのupdate関数でビットシフトループを消す最適化の例を挙げよう。これはC言語で紹介する。（型キャストのない言語は記述が解りづらくなるので）

// 普通のビットシフトループ＋条件式
uint16_t _crc16_mcrf4xx_slow (uint16_t _crc, uint8_t _data) {
  _crc ^= _data;
  for (uint8_t i = 0; i < 8; i++) {
    if ((uint8_t)_crc & 1) _crc = (_crc >> 1) ^ 0x8408;
    else                   _crc >>= 1;
  }
  return _crc;
}

// 普通のビットシフトループ＋論理演算
uint16_t _crc16_mcrf4xx (uint16_t _crc, uint8_t _data) {
  _crc ^= _data;
  for (uint8_t i = 0; i < 8; i++) {
    _crc = (_crc >> 1) ^ (0x8408 & -(_crc & 1));
  }
  return _crc;
}

// 8bit単位で倫理演算してループを取り払った最適化
uint16_t _crc16_mcrf4xx_quick (uint16_t _crc, uint8_t _data) {
  _data ^= _crc & 0xff;
  _data ^= _data << 4;
  return (
      (((uint16_t)_data << 8) | (_crc >> 8)) 
    ^   (uint8_t)(_data >> 4) 
    ^  ((uint16_t)_data << 3)
  );
}

最後の最適化はループ処理がなくなっているので多段パイプラインと相性が良く、事前定義テーブル参照方式より早くなるほどだが、もはや多項式が式の中にどう埋め込まれているのか容易には読み取れない。各CRC計算方式別にこうした最適化演算式を考案してその証明を示すのは、一本の修士論文を書くのに十分なテーマだろう。

Copyright and Contact

Twitter(X): @askn37
GitHub: https://github.com/askn37/
Product: https://askn37.github.io/

Copyright (c) askn (K.Sato) multix.jp
Released under the MIT license
https://opensource.org/licenses/mit-license.php
https://www.oshwa.org/