Fragments of Reality

さて、IP/TCP/UDPのチェックサムの導出方法ですが、ずばり「1の補数和の1の補数」を計算すればいいのです…って、じゃあ「1の補数和の1の補数」ってなんやねん、と。 まあそうなりますよね、普通。 というわけで、こいつの謎を解明するのがこのエントリの主な目的です。

それではまず、「補数」から見ていきましょう。

補数ってなんだ

補数の詳しい定義は情報処理の教科書とかこのへんを見ていただきたいのですが、要するにN進数のある数値αに対して、

Nの補数

αに足して桁がひとつ増えるような最小の自然数

(N-1)の補数

Nの補数より1小さい自然数（αとの和が「αと桁数が同じ自然数のうち最大のもの」になるような自然数）

ということです。たとえば、十進数26の10の補数は74です。 両者の和をとると100で桁がちょうど3桁になりますね。 ということは、上記から1を引いた数、すなわち73が26の9の補数ということになります。 もうひとつ例をあげておきましょう。二進数101bの2の補数は011bです。 両者の和をとると1000bでちょうど桁がひとつ増えることが確認できます。 さらに、ここから1を引いた010bが101bの1の補数です。

このふたつの例から、補数の直感的な求め方がなんとなくわかるでしょうか。

まず、N進数αの(N-1)の補数を考えてみましょう。 「αと桁数が同じ自然数のうち最大のもの」は(N-1)を桁数だけ並べたものになります。 たとえば、十進数26に対しては99、二進数101bに対しては111bです。 (N-1)の補数は合計してこれになるような正数、すなわち、これからαを引いた正数になるわけですが、各桁が(N-1)ですから位をまたがる引き算は発生しません。 つまり、(N-1)から各桁をそれぞれ引いたものを並べればいいわけです。 十進数26では、9-2=7、9-6=3ですから73、二進数101bでは1-1=0、1-0=1、1-1=0ですから010bになります。

ところで、この例からもわかるように、二進数に対する1の補数は簡単に求められます。 αのある桁が0であれば1の補数では1-0=1に、1であれば1-1=0になりますが、これは明らかにαのビット単位否定をとったものです。 つまり、単純に0と1を入れ替えるだけでいいのです。

ここまで来れば簡単。 N進数αのNの補数は(N-1)の補数に1加えたものとして求めることができます。 十進数26では73+1=74、二進数101bでは010b+1=011bです。

2の補数と負数の内部表現

さて、2の補数は計算機内で負数を表すための表現に応用されています。 このため、「2の補数＝計算機における内部表現」と覚えている人もいるかもしれませんが、上記の通り、補数というのは単なる定義です。 では、なぜ2の補数を負数の内部表現に使うのでしょうか。 その前に、計算機における「2の補数」について説明しなければなりません。

計算機では、整数を表すためにある決まったビット数の表現を使います。 たとえば、C言語で云うshortは16ビットの整数表現です。 計算機では、この整数を(内部にどんな値が格納されていようと)16桁と考えます。 そして、2の補数は16桁に対して計算するのです。

例えば、0xFF0Eという16ビットの値があったとしましょう。 これに対する(二進数の)2の補数は…そうですね、0x00F2です。 これらの和をとると0x10000で17ビットになりました。 それでは、0x00F2という16ビットの値に対する2の補数はどうでしょうか。 答えは、0xFF0Eです！ 0x00F2は8桁の二進数で、0xEを加えれば0x100と9桁になりますから、上記の定義によればこの値が2の補数になりそうなものです。 しかし、ここでは0x00F2を16ビット(16桁)の二進数と考えていますので、17桁になる最小の整数である0xFF0Eが0x00F2の2の補数になるわけです。 ちなみに、0x0000にどんな16ビットの整数を加えても16ビットで収まりますから、16ビット整数0x0000に対する2の補数は存在しません。

さて、ではどうして上記のような2の補数が計算機で負数の内部表現に応用されているのでしょうか。 それは、2の補数があらわす負数をうまく決めると非常に計算に都合がいいからです。 たとえば、16ビットのある整数α(≠0x0000)とその2の補数βを考えましょう。 この場合、任意のαに対してα+β=0x10000になりますね。 これを16ビットで表現するためにあふれた桁を無視すると、0x0000です。 つまり、βはαの符号を反転させた整数であると定義すれば、加算してオーバーフローした桁を無視することで、減算処理を負数の加算処理に変換することができるのです。

計算機内部ではこのような性質を利用し、最上位ビットが0のものを正数とし、それに対応する2の補数(最上位ビットは必ず1)を対応する負数として扱っています。 たとえば、0x0001 (=1)に対する2の補数0xFFFFは-1を表しますし、以下同様に、0x0002 (=2)に対する2の補数0xFFFEは-2を表すわけです。

最大の正数と最小の負数 (ぐるぐるまわる！)

ところで、計算機内部の整数表現は有限の桁数ですから、最大値と最小値が存在します。 たとえば、16ビットの正数表現では0xFFFF (=65535)が最大値で0x0000 (=0)が最小値です。 それでは、16ビットの整数表現の最大値と最小値はなにになるでしょうか。 答えは、最大値が0x7FFF (=32767)、最小値が0x8000 (=-32768)です。

おっと、なにか違和感を感じませんか？ そうです、和をとると0になる2の補数が必ず存在するはずなのに、最大値と最小値が違います！ 0x8000に対応する2の補数はどこにいってしまったのでしょうか… と、少し考えるとさらに驚くことに気がつきます。 0x8000の2の補数は自分自身なのです！ そのため、0x8000は「最上位ビットが1のものは負数を表現するものとする」という定義に基づいて-32768を表し、和をとって0になるものは存在しないのです。

と、違和感が解消したところで次の疑問。 16ビットの正数表現であれば、最大値である0xFFFFに1を加えるとオーバーフローして0x0000に戻りました。 それでは、16ビットの整数表現における最大値0x7FFFに1を加えると何が起きるでしょうか? ここは実際にコードを書いて実験してみましょう。

#include <stdio.h>

int
main(void)
{
  int i = 0x7fff;

  printf("i = %hd(0x%04x)\n", i, i);
  printf("i + 1 = %hd(0x%04x)\n", i + 1, i + 1);

  return 0;
}

このコードを実行してみると、次のようになるはずです。

i = 32767(0x7fff)
i + 1 = -32768(0x8000)

なんと、計算機内部の整数表現では、最大値に1を加えると最小値になるのです。 これが計算機内部における負数表現と2の補数の、もうひとつの秘密です。 そもそも内部的にはただの16ビット正数ですから、0x7FFFに1を加えると0x8000になるのは当然なのです。 それを符号付き整数のときにも拡張して、最大正数に1を加えると最小負数になるというふうに決めましょう、ということです。

今まで説明してきた計算機内部の整数表現を図に描くと右のようになります。 これまでの説明とあわせるために16ビット整数の場合のようすを示しています。 一応、2の補数を負数の表現として利用するという説明に基づいて描いてありますが、 この図ははっきり云って負数とかなんとかはもうどうでもいい世界です。 大事なことは、

• 加算して16ビットからあふれるとオーバーフローは無視
• (この性質から) 0xFFFFに1加えると0x0000
• 0x7FFFと0x8000の間は最小の負数と最大の正数の境界とはいえ実際はただの整数なので、0x7FFFに1を加えると0x8000

ということです。 このような、2の補数を内部表現として使った場合の加算を、「2の補数和」と云います。

内部表現として1の補数をつかってみると

さて、ここまでは計算機の内部表現として一般的に利用されている、2の補数を説明してきました。 しかし、ふと疑問が過ぎります。過ぎらない？いや、過ぎってください、過ぎらないと話が続きません。 内部表現として1の補数を使うと何が起きるんでしょうか?

負数を計算機の内部でどのように表現するかは、計算機の黎明期にかなり議論されたようです。 結局、いくつかの方式が生き残ったのですが、2の補数も1の補数も生き残った候補のひとつです。 2の補数を利用した場合、ある整数αの2の補数βは、αの符号を反転したものであるという定義でした。 同様に、1の補数を利用した場合は、ある整数αの1の補数β'は、αの符号を反転したものであるという定義です。 既に述べたように、αとβの和が(オーバーフローを無視して)0になる利点によって、今日では負数表現といえば2の補数、というふうになっています。 しかし、歴史的には1の補数を負数表現に使おうと思っていたひともいたでしょうし、実際、IP/TCP/UDPのチェックサムには1の補数が応用されているわけです。

さて、1の補数の例を挙げてみましょう。 0x0001 (=1)の符号を反転させた-1は、2の補数表現では0xFFFFであったのに対し、1の補数表現では0xFFFEです。 同様に、0x0002 (=2)の符号を反転させた-2は、2の補数表現0xFFFEに対して1の補数表現0xFFFDです。

1の補数表現では、いくつかおもしろい現象が見られます。 まず、0x0000に対する2の補数が存在しなかったのに対し、1の補数は0xFFFFとして存在します。 1の補数表現の世界では、0x0000を+0、0xFFFFを-0と書くこともありますが、いずれにしても0を表現する値がふたつ存在するわけです。

整数αとその1の補数の和はどうなるでしょうか。 考えるまでもなく、1の補数の定義から常に「αと桁数が同じ自然数のうち最大のもの」になります。 αが16ビット正数であれば、常に0xFFFFになるわけです。 先ほど見たように0xFFFFもまた0を表す値ですから、特に矛盾はありません。

もうひとつ、最大の正数と最小の負数についてです。 1の補数表現における符号付き16ビット整数での最大の正数は0x7FFF (=32767)で、これは2の補数表現とかわりません。 一方、最小の負数は0x8000 (=-32767)で、2の補数表現と異なります。 2の補数表現のときに存在しなかった、0x8000の相方が1の補数の世界では存在するのですね。 ただし、最大の正数0x7FFFに1を加えると最小の負数0x8000になるのは、2の補数の世界とかわりはありません。

以上を図に描くと右のようになります。 ここでもまた、正数とか負数という話はどうでもよくなって、重要なのは以下の点になります。

• 0x0000の1の補数表現である0xFFFFもまた0を表す
• ある整数とその1の補数の和は0xFFFF (=0)
• 0x7FFFと0x8000の間は最小の負数と最大の正数の境界とはいえ実際はただの整数なので、0x7FFFに1を加えると0x8000

1の補数の世界におけるオーバーフロー

さきほど、1の補数で重要な点を3つ挙げました。 しかし、もうひとつ、意図的に書かなかった重要な点があります。 それは、オーバーフローの扱いです。 すなわち、16ビット整数同士を加算して桁があふれた場合の処理ですが、 ここではいろんなパターンを見ながらどのようになっているかを見てみましょう。

まず、符号付き16ビット整数の正数aとb (0x0000≦{a, b}≦0x7FFF)の加算です。 この場合、明らかに桁あふれは起こりませんから除外してよさそうです。 次に、正数a (0x0000≦a≦0x7FFF)と負数b (0x8000≦b≦0xFFFF)の場合。 a≦(0xFFFF-b)であれば桁あふれは起こりませんから、この場合も除外します。 そしていよいよ、本日のその時桁あふれするときがやって参りました。 a>(0xFFFF-b)の場合です。

わかりやすさのために、具体例を挙げながら説明しましょう。 a=0x0004(=4)、b=0xFFFE(=-1)とします。 正しい答えは明らかに3ですね。

まず、bをa'+b'に分解します。 ここで、a'はaと加算して0xFFFFになる値(仮に0xFFFF-aと表記します)、すなわち、aの1の補数です。 0xFFFFは0を表すのでしたから、上記の分割は「aと加算して0になる部分a'と加算の答えb'に分割する」とも云えます。 なぜb'が加算の答えかというと、a+b=a+(a'+b')=(a+a')+b'=b'だからですね。 上記の例では、a'=0xFFFBですからb=0xFFFB+0x0003と分解することになり、 確かにb'が答えである0x0003になっています。

では、実際に計算してみるとどうなるでしょうか。 明らかにa+b=0x0004+0xFFFE=0x0002(オーバーフロー無視)ですから… あれれ！答えが合いません! これは一体どういうことでしょうか？

答えは、図の中にあります。 a+bをa+a'+b'に分解して前者の和をとると、0xFFFFになりますね。 0xFFFFは0を表しますから、本来はそれに1を加えると1にならなければなりません。 しかし実際には、0xFFFFの次もまた0をあらわす0x0000なのです。 すなわち、1の補数における加算では、オーバーフローするとひとつ多い0のために答えが1だけ小さくなってしまうので、1を加えて補正しなければならないのです。 この補正は、図の円における12時の部分(0xFFFF/0x0000)の部分を通過するたびに必要になります。

最後のパターンは負数同士の加算です。これはかならずオーバーフローすることになりますが、補正が必要なのは先ほどと同じなので、省略することにします。

というわけで、1の補数表現における加算では、前述の3つに加えて以下も非常に重要なポイントになります。

• 加算時にオーバーフローした場合は、図の円における12時の部分を通過する度に1を加えて補正する

これらの規則に基づき、 1の補数を内部表現として使った場合の加算を、「1の補数和」と云います。

1の補数和の計算を簡単に

ああすっきり…と云いたいところですが、実際に加算する場合に円とにらめっこするわけにはいきません。 もうちょっといい方法はないのでしょうか。

上記のオーバーフローの規則は「12時を越えるたびに1を加算する」ですから、12時の部分を通過した回数を加算結果に加える、とも云えます。 つまり、12時を越えた回数をうまく数えることができればいいわけですね。 なんと、なんの苦労もなく自動的にこの回数を数える方法があるのです。

12時をこえる、ということはなにを意味するでしょうか。 これは、現在の桁数では表現ができなくなるために、ひとつうえの桁を利用すると云うことです。 これは、一度越えるとひとつうえの桁に1を加算するということです。 先ほどの例では0x0004+0xFFFE=0x10002となっていて、12時を越えたことを17ビット目が表しています。 このまま加算してもう一度12時を越えると… 同様に上位の桁に1が加えられるので、0x2XXXXという値になるはずです。 すなわち、桁あふれの部分の数値がそのまま12時を越えた回数を表すわけです。

ここまでくれば、もうわかりますね。 1の補数和を求めるためには、単純に和をとってから、オーバーフローしたぶんを和に足し込めばいいわけです。

チェックサムを求めよう

長い道のりでした。 ようやく、IP/TCP/UDPのチェックサムを求めることができます。 このチェックサムは、16ビットごとの1の補数和の補数と定義されており、対象のデータが奇数バイトの場合は最後に0を補うことになっています。 これを表すと以下のようなコードになります。

u_int16_t
in_checksum(data, len)
        void *data;
        size_t len;
{
  u_int32_t sum = 0;
  union {
    u_int8_t ch[2];
    u_int16_t si;
  } *s_data = data, s_data0 = { .ch[1] = 0 };

#define CARRY(x)        (x = (x & 0xffff) + (x >> 16))
  for ( ; len > 0; s_data++, len -= 2, CARRY(sum))
    sum += s_data->si;

  if (len > 0) {
    s_data0.ch[0] = s_data->ch[0];
    sum += s_data0.si;
    CARRY(sum);
  }

  return ~(u_int16_t)sum;
}

forループの中で加算と補正をおこなっているのがわかるとおもいます。 なお、説明の通り、最後にまとめて補正をかけることもできますが、 sumが32ビットなので、32ビットがあふれる前に補正してあげないといけません。 その判定が面倒なので毎回補正をかけています。 速度が必要な場面では、可能なだけ和をとって補正という処理を繰り返すといいでしょう。

ああ、そうそう、速度といえば、1の補数和の性質を使うと以下のようなおもしろいこともできます。 16ビットの1の補数和を求める際、

• 最初に32ビットの1の補数和を計算
• その答えを16ビットに分割し、16ビットの1の補数和を計算

という手順を踏むこともできるのです。 これは、32ビットじゃなくて64ビットで和をとってもいいですし、128ビットでもかまいません。 なぜこれが可能なのかは今までの説明を元にみなさんで考えていただくとして (下の方にもかなりいろいろヒントがありますし)、速度が必要な場合はこんな性質もうまく利用するといいかもしれません。

それで、なんで「1の補数和の1の補数」やねん？

ではなぜ、チェックサムは「1の補数和の1の補数」なんでしょうか。 まず、1の補数和から考えましょう。 ひとつには、1の補数和はバイトオーダに非依存であるということがあります。

右の図は、16ビット整数を異なるバイトオーダで保持して加算した場合を表しています。 例えば、上側の図はをホスト・バイトオーダです。 直感的にはビッグ・エンディアンのアーキテクチャに見えると思いますが、どちらでもかまいません。というのは、ここでは加算だけを問題としているからです。 この場合、LSBの和でオーバーフローするとその分はMSBに桁上がりします。 一方、MSBの和でオーバーフローした場合は、2の補数和か1の補数和かによって処理が異なるのでした。 前者は無視し、後者はLSBにもどって桁上がり(?)します。

下の図は、ホスト・バイトオーダと逆のエンディアンで保持している場合を表しています。 この場合、MSBの和のオーバーフローはLSBに加算されます。一方、LSBのオーバーフローは、2の補数和で無視、1の補数和でMSBに加算です。

これらをまとめると、1の補数和の場合は、いずれのエンディアンでも、LSBのオーバーフローはMSBへ、MSBのオーバーフローはLSBへ加算されます。 すなわち、エンディアンによる影響はありません。 一方、2の補数の場合は、ホスト・バイトオーダと逆のエンディアンで保持して和をとると、誤ったった結果になる可能性があることがわかります。

1の補数和を利用するもうひとつの理由は、1の補数和では加算結果が0x0000になることがほぼない、ということでしょう。 今まで見てきたように、加算和が0になる場合、内部的にはほぼ0xFFFFになります。 正確には、0x0000同士以外で和が0x0000になるものはありません。 UDPではこの性質を利用して、 チェックサムが0x0000であればチェックサムを計算していないこととして扱うよう決められています (個人的には、後で述べる理由により0xFFFFをこの目的に使った方がいいと思うのですけれど)。

さて、次に、どうして最後に「1の補数」をとるのか、です。 これは、受信側でチェックサムの検証を簡単にするためです。

送信側がチェックサムを計算するときは、チェックサムのフィールド自体を0にして1の補数和を計算します。 この値をαとしましょう。 そして、その1の補数和の1の補数をチェックサム・フィールドに埋めるわけです。 これをβと呼ぶことにします。 一方、受信側はそのまま全体の1の補数和の1の補数を計算します。 データが正しく受信されているとすれば、算出された値は、 チェックサム・フィールド以外の1の補数和αにチェックサム・フィールドの値βを加えたものになるはずです。 βはαの1の補数和ですから、この値は必ず0xFFFFになりますね。 そして最後に、この値を1の補数をとると…結果は0x0000です。 すなわち、受信側は送信側と全く同じ手順で(チェックサム・フィールドを特別扱いすることなく)チェックサムを計算し、その結果が0になることで検証できるのです。

ところで、現実的に送信するデータの1の補数和が0x0000になることがない、というのは前述の通りです。 そのため、1の補数和の1の補数であるチェックサム・フィールドの値は、0xFFFFになることはありません。 これが、「UDPでチェックサムを利用しないことを示すために、0xFFFFのほうがよさそうなのにな」と書いた理由だったわけです。 現在の仕様では、チェックサムの計算結果が0x0000になったら0xFFFFに置き換える、というふうに決まっています。 ただ、このように置き換えても所詮0のままですから、検証側ではなんら気にすることはありません。

以上、とてもとても長いエントリになりましたが、IP/TCP/UDPチェックサムにまつわるお話でした。