チェックサム計算のデバッグ

はじめに

CRC:sは、正しい結果を得ることが難しいことで有名です。正しいバイトシーケンスが正しい順序で処理される場合もあれば、そうでない場合もあります。その問題の一つは、一般的なCRCアルゴリズムでは正しい答えに近づいてるかどうかを把握する方法がないことです。

多項式0x1021を使用して0x1000～0x3FFFのチェックサムを計算するはずのところで、実際には多項式0x1201を使用して0x0100～0x3FFFのチェックサムを計算した場合、本来の結果とは異なる結果が得られることになります。2箇所ある誤りのうち1箇所に気付いて新たな結果を取得しても、その結果は間違ったままであり、その結果が本来の結果に近づいたものになっているのかや、その結果が本来の結果と一致していないことを示すものは何もなく、得られる情報としては計算結果しかありません。

以下に、よくある落とし穴とその対処方法をまとめました。

1.外部のチェックサム範囲を確認し、プログラムのチェックサムがどの範囲に対応するかを確認する

チェックサムを生成するプログラムは、そのチェックサムを生成するのに使用した範囲を報告します。IAR XLINKリンカとielftoolツールのいずれも、この情報を提供します。報告された範囲が、例えば0x40～0x3FFB、0x4000～0x7FFFであった場合、0x40～0x7FFFのチェックサムではなく、厳密なバイト数に対してチェックサムを計算する必要があります。または、0x3FFC～0x3FFFがCRCの計算から除外されていることを確認する必要があります。

2.チェックサムの計算で同じ多項式が使用されているか確認する

同じチェックサム範囲に対して異なる多項式を用いて計算した2つのチェックサムは、同じ値にはなりません。CRC-16は、多項式0x1021を使用します。この多項式は、実際には0x11021ですが、最上位の1は16ビットに収まらないため、通常は捨てられます。これは、規格化された他のCRC値にも当てはまります。Xビットの多項式においてビットXがセットされたとしても、ビットXは多項式のビット範囲に収まらないため、多項式のXビット表現には含まれません(ビット0～ビットXを表すにはX+1ビットが必要なため、ビットXはXビットに収まりません)。

この多項式は、従来の数学的な多項式(Xのn乗 + Xのn-1乗 + ...)で表される場合があります。この場合、多項式は、各xの指数をビットインデックスとして使用し、そのビットを1にセットすることで、対応する16進数に変換できます。例: x ^ 16 + x ^ 12 + x ^ 5 + 1。この式では、ビット16、12、5、0が使用されています。0x10000 + 0x1000 + 0x20 + 0x1 = 0x11021 = 0x1021 = CRC-16

3.チェックサムが反転/ミラーを同じ方法で扱っているか確認する

CRCアルゴリズムにおいて、反転/ミラーが使用されることがあります。ミラー/反転を行うには、1つのバイトに含まれるビットの順序を逆にします。

例:
ミラー(0x1) = 0x80
ミラー(0x17) = 0xE8
ミラー(0xE2) = 0x47
ミラー(ミラー(x)) = x

あるチェックサムでは反転が行われ、別のチェックサムでは反転が行われない場合、CRCアルゴリズムでは事実上異なるバイトシーケンスであるとみなされるため、それらのチェックサムは、通常、同じ値にはなりません(バイトシーケンスは、ビットシーケンスが回文となるバイトの並びで構成される場合があります)。反転/ミラーは、通常、ミラーテーブルを使用して処理されます。このミラーテーブルは256バイトの配列で、各インデックスのバイトには、そのインデックスを反転したものが格納されます。その後、CRCコードによってミラーテーブルが参照され、実際のバイトではなく各バイトに対応するミラーテーブルのエントリがCRCの計算で使用されます。

ミラー/反転の問題の一つは、CRCを使用するユーザが、CRCの計算においてミラー/反転が行われるかどうかを把握する方法がないことです。反転/ミラーが使用されるかどうかをテストする最も簡単な方法は、2つの手法を実行してその結果が一致するかどうかを確認するというものです。

4.アルゴリズムに追加のバイトが与えられる場合がある

テーブル駆動型のアルゴリズムを使用しない場合、通常、バイトシーケンスの後ろに追加された値が0のバイトを処理する必要があります。チェックサムシンボルでは、各バイトについて値が0のバイトが1つずつ必要になります。テーブル駆動型のアルゴリズムを使用する場合、追加のバイトは必要ありません。詳細については、Ross N. Williamsによる『A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS』を参照してください。

5.正しいアドレス範囲からバイトを読み込んでいるか確認する

注: これは、プロセッサに複数のアドレス空間が存在する場合のみ問題となります。

正しいアドレス範囲を処理したとしても、アドレス空間が間違っていれば、それは、エラーが発生する原因の一つとなる可能性があります。CRCアルゴリズムで使用されているポインタの型が正しいか確認してください。使用されているポインタは正しいアドレス空間を指していなければなりません。場合によっては、以下のように、ポインタの宣言にメモリ指定子を追加する必要があります。

typedef __code unsigned char * CodePtr;

uint16_t
crc(uint16_t sum, CodePtr p, uint32_t len)
{
 .
.
.
}

6.「広い」範囲に対して「小さな」ポインタを使用する場合は注意が必要

注: これは、複数の型のポインタが存在し、それらの少なくとも1つ以上が他の1つ以上のポインタより狭いメモリ範囲しか指定できない場合のみ問題となります。

メモリ全体を指定できないポインタを使用する場合(通常、アドレス指定可能な64kを超えるメモリ空間を持つシステムにおける__nearポインタ)、最終アドレスに到達したときに問題が発生します。16ビットのポインタの値が0xFFFFのとき、このポインタをインクリメントすると、0x10000ではなく0x0となります。その結果、当然ながら、間違ったバイト範囲のチェックサムが計算されます。

0x4000～0x27FFFの範囲のチェックサムを計算したい場合、そのアドレス範囲をすべて指定可能なポインタを使用する必要があります。小さなポインタを0x24000回インクリメントして間接参照するだけでは不十分です。0x4000から始まる__nearポインタを使用すると、期待する0x4000～0x27FFFの範囲ではなく、0x4000～0xFFFF、0x0～0xFFFF、0x0～0x7FFFの範囲のチェックサムが計算されます。通常、__farポインタまたは__hugeポインタを使用すれば十分です。__nearポインタを使用し、0x10000および0x20000において何らかの方法で切り替えを行うことも可能ですが、どちらかといえば、大きなポインタを使用する方が安全です。

しかしながら、64kバイトを超える範囲のチェックサムを計算したい場合、何らかの方法で64kの境界を越えて処理する必要があります。

7.小さく始める

可能であれば、チェックサムの突合せの際に小さいサンプルを使用してください。単一のバイトは、通常は扱うのが最も簡単です。テーブル駆動型の場合はテーブルを1回だけ参照すれば済み、従来型の場合はビット操作を1回だけ行えば済みます。また、境界をまたがることもなく、大抵の場合、同じバイト値を用いて計算された2つのチェックサムを簡単に確認できます。

多項式、初期値、ミラー/反転手法、アドレス空間が同じであれば、チェックサムは同じになります。ただし、場合によっては、最終的なチェックサムに対して特定の値とのXOR演算が行われたり、最終的なチェックサムに対して1の補数(または2の補数)が計算される場合があります。

1バイトの範囲に対するチェックサムが一致したら、チェックサムの計算対象を数バイトの範囲まで拡張してください。これにより、計算で使用した単一バイトが特殊な性質を持っているためにチェックサムが偶然一致するというリスクを最小限に抑えることができます(例えば値が0の場合、反転によるミスマッチを検出することはできません)。多バイトに対するチェックサムが一致しないものの、単一バイトに対するチェックサムが一致する場合は、再度単一バイトに対するチェックサムを計算してください。ただしその場合、前回とは異なる値を使用してください。

範囲を少し拡張したときのチェックサムが一致したら、対象範囲全体のチェックサムを計算してみてください。狭い範囲の結果が一致するものの、広い範囲の結果が一致しない場合、ページ境界の問題がないかどうか(16ビットのアドレス境界を超えていないかどうか)を調べたり、チェックサムの場所を調べたり(通常、チェックサム自身はチェックサムの計算対象から除外されます)、いずれかのアドレスに予期せぬ値が含まれていないか調べたりする必要があります(そのようなアドレスはチェックサムの計算から除外する必要があります)。

8.特殊なケース

当然ながら、標準の手法(char型のポインタによって2つのアドレスにあるバイトがそれぞれ読み込まれる手法)を「そのままの状態」では適用できない特殊なケースが存在します。そのような場合、アセンブラを使用してそれらのバイトを期待どおりの順序でアクセスする必要があります。

また、異なるフィルパターンを使用するのも有効です。多くの場合、フィルパターンとして0xFFが使用されます。アーキテクチャによって4バイトごとに必ず0が読み込まれる場合(アーキテクチャによっては「ゴーストバイト」が使用される場合があります)、あるチェックサム(オブジェクトファイルから生成されたチェックサム)はゴーストバイトとして0xFFを使用するのに対し、ハードウェア上のバイトを実際に読み込んで生成されたチェックサムではゴーストバイトとして0x0を使用するため、両者は絶対に一致しません。この場合、フィル文字列として0xFFFFFF00を使用し、なおかつこのフィル文字列が4バイトのアドレス境界から開始されるようにすれば、いずれのチェックサムアルゴリズムでも同じバイトが使われるようにすることができます。

チェックサムの計算範囲に、(何らかの理由で)値が予期できないバイトが含まれている場合、そのバイトをチェックサムの計算から除外する必要があります。

全ての製品名は、それぞれの所有者の商標または登録商標です。