IP のチェックサム -- 1の補数演算

問題設定

IP チェックサムは以下の方法で計算されることになっています:

この計算で不思議な点が 2点あります:

本稿では、この 2点についての謎を説き明かしたいと思います。

1の補数というもの

まずは、「補数」について、数学的な準備をしましょう。ちょっと長いかも知れません。単に補数といいますと、実は符号を取り替えた数を示したりしますが、本稿では n の補数を考える必要があります。

n の補数を考えるときには、何進数を使うかと、桁数をあらかじめ指定しておく必要があります。元ネタが IP なので、2進数 16ビットを使うことにします。進数が変化すると、表現が変わってきます。面倒さをさけるため、16進表現を使用します。

定義

正の整数 x の「1 の補数」とは、「0xFFFF - x」のことです。

1の補数の性質

1の補数演算には、定義からわかる、次の性質があります。

性質

この性質をもっと使いやすくするため、以下の拡張をします:

定義 (補数の拡張)

これにより、1 の補数を全部の数に拡張できます。

足し算の定義は普通の通りなのですが、計算は有限ビットですので、どこかでオーバーフローを起こします。ここの処理がポイントになります。

定義 (オーバーフロー)

以上の定義とオーバーフローの処理により、以下の性質が導かれます。

性質 (和に関するもの)

ごちゃごちゃ書きましたが、和が 0 になる結果を齎すのは、最後の場合だけだということに注目してください。

性質

IP チェックサムの場合

ようやくチェックサムの場合まで来ましたが、ここまでくると話が簡単になります。

結論

ということで、udp のように 0 を「サムなし」に使うのならば、パケットの総和が 0xFFFF になる場合、サムのフィールドには 0x0000 ではなく、0xFFFFを書いておけば、偶然の一致によりサムが 0 になることはないので、安全に「総和は 0xFFFF」ということを伝達できる、となります。

結論

IP のチェックサムはよくできてます。でも計算方法を書いておいてほしかったな。


おまけ

普通は、上記のような計算をするのではなく、2の補数を使って計算します。2の補数を使う場合は、16ビットの値を無符号として足し算し、あとから補正を書けることで 1の補数を計算することができます。すなはち、

後者は、0x8000 + 0xFFFE = 0x7FFF の実装です。通常計算すると、0x8000 +0xFFFE = 0x17FFE になります (計算してみること) が、16 ビット目が立っているときは、そのビットを最下位ビットに足しこんでやります。するとあらふしぎ、1の補数での補正ができました。

これをまとめて実施することもできます。すなはち、2の補数演算で、全パケットの値をあらかじめ足し込んでおき、オーバフローが起きた回数を数えて足し込むことで補正できます (補正を行ったときにオーバフローが起きたら、もう一回足し込む必要があります)。32ビット計算を使って行う場合、オーバフローが起きる回数は、単に上位 16ビットで表現されていますので、「シフト2発、足し算2発」(2発なのは補正の補正) で計算できてしまいます。おしまい。