Go の Signed Int の gob バイナリエンコーディングアルゴリズムを理解する

Terraform のプラグイン機構を理解したかったのだが、その過程で、gob を理解しないといけないことがわかった。その時に、解説を読むと、エンコーディングアルゴリズムが出てきたのだが、さっぱり意味がわからなかった。だから、それを理解してみた。結局これを理解するだけで一日ぶち潰れた。その理由として、この辺りの英語を理解する能力がなかったことと、コンピューターサイエンスの基礎となる数学が理解できていなかったことにある。

理解したいアルゴリズム

これは、Package gobの解説に出てくる表現で最初はナンノコッチャと思った。ここは英語力のなさの問題。

An unsigned integer is sent one of two ways. If it is less than 128, it is sent as a byte with that value. Otherwise it is sent as a minimal-length big-endian (high byte first) byte stream holding the value, preceded by one byte holding the byte count, negated. Thus 0 is transmitted as (00), 7 is transmitted as (07) and 256 is transmitted as (FE 01 00).

翻訳をするとこんな感じ。

Unsigned integer は、２通りのうち、１通りの方法で送られる。もし、それが128以下なら、バイトの値で送られる。そうでなければ、最短のビッグエンディアンの値を持ったバイトストリームで送られる。最初の１バイトは、バイトカウントで、無視される。そのため、0 は、(00), 7 は、(07), 256 は、(FE 01 00) として転送される。

英文でうまく理解できなかったのは、 proceded (To begin to carry on an action or a process:) の意味で、最初のバイトという意味合い。negrected は無視されるという意味。おそらくこんな感じ。256 は２バイト必要なので、FEは 16bit だと下記のような２進数になるので、おそらく、Unsigned Int の-2 を表す。２の補数に関してはあとで説明する。

-2 byte     = 0000 0000 0000 0010　の２の補数
              1111 1111 1111 1110 = FE

ううむスッキリしない。バイトカウントはマイナスで表現するとは書いてないし。困ったときはコードだ。

gob のソースを拝見する

ここのソースを参考に自分なりにサンプルを書いてみる。該当部分のコードを書いてみた。
encode.go

ポイントは下記の部分。ここをしっかり理解する。

func getUnsignedInt(x uint64) ([]byte, []byte) {
	buf := make([]byte, 9)　　// 1. 配列の確保
	var data []byte
	if x <= 0x7F {          // 128 以下のケース
		b := make([]byte, 1)
		b[0] = byte(uint8(x))
		return b, b
	}
	binary.BigEndian.PutUint64(buf[1:], x)  // 2. ビックエンディアンでバイト化
	a := bits.LeadingZeros64(x)             // 3. 先頭の0のビットを取得
	bc := a >> 3                            // 4. 8 で割って 先頭バイトを取得
	buf[bc] = uint8(bc - uint64Size)        // 5. 先頭バイトにバイトサイズを格納
	data = buf[bc : uint64Size+1]           // 6. 別のバイトに、先頭バイトからのスライスを移送
	return buf, data
}

の部分。こいつをデバッガで動作をみながら理解する。128 以下のケースは単純に８ビットに格納しているだけなので、難しさはない。

1. 配列の確保

最初に配列の確保をしている。これは、Int が様々なサイズがあるが、そのサイズ+1 の配列を確保している。例えば、64bit のUnsigned Int なら、8バイトだが、それプラス１バイトにしている。つまり、バイトサイズを入れるところを確保している

□　□□□□　□□□□
↑先頭はバイトサイズ＋Int64 の最大値8バイトを確保

2. ビックエンディアンでバイト化

今回、256 を代入するとどうなるかを考える。

256 を 16ビットで考えるとこんな感じ。Int64 はこれで、先頭に、0000 が埋められれている感じ。

0b`0000 0001 0000 0000` 0x0100

[binary.BigEndian.PutUint64(buf[1:], x) ](binary.BigEndian.PutUint64(buf[1:], x) )は、64ビットの1バイト目から、バッファに、値を詰める。最初の１バイトは、バイトサイズだから故意にスキップしている。

□　□□□□　□□■■

0x00  0x00 0x00 0x00 0x00  0x00 0x00 0x01 0x00

といった感じでデータがセットされる。

3. 先頭の0のビットを取得

a := bits.LeadingZeros64(x) は、先頭の使っていないビットを取得する。例えば、

bits.LeadingZero64(0) = 64
bits.LeadingZero63(0) = 63

こんな感じ。ちなみに、x=256 の時の値は55になっている。

4. 8 で割って 先頭バイトを取得

これは、あくまで２進数なので、今欲しいのは、先頭の空きバイト数が欲しい。８で割っても良いが、>> 3 のシフトを使って、それを表現する。すると、値は、6 になる。

□　□□□□　□□■■
　　　　　　↑ここ

つまり、先頭のバイトサイズを格納する領域をのぞいて、先頭バイトの位置を出している。

5. 先頭バイトにバイトサイズを格納

uint64Size は、uint64 のバイトサイズ。つまり８バイト。ここで、先ほど取得した、先頭のバイト（６バイト目）から、全体のバイト数（８バイト）を引いている。つまり、-2 になる。バイトサイズは、つまり、UnsignInt の全体バイト数から、使っているバイト数を引いた値になるので、マイナス値になる。

buf[bc] = uint8(bc - uint64Size) 

バイトサイズは

-2 = 2 の 2 の補数 = 
2:       0000 0010
2の補数:  1111 1110　 (0xFE)

さらに、もう一点、ポイントがあって、そのバイトサイズの値を、bc (先頭からのバイト数）のバッファに格納している。 つまり格納されたサイズの一つ手前のバイトに格納している。

□　□□□□　□○■■ 0x00  0x00 0x00 0x00 0x00  0x00 0xFE 0x01 0x00
　　　　　 ↑ここ

6. 別のバイトに、先頭バイトからのスライスを移送

bc の位置から、最後までを移送している

data = buf[bc : uint64Size+1]

buf
□　□□□□　□○■■ 0x00  0x00 0x00 0x00 0x00  0x00 0xFE 0x01 0x00
　　　　　 ↑ここ
data
○■■ 0xFE 0x01 0x00

これで、この仕様のエンコードの方法が理解できました。

全体のコードを書いておきます。

func main() {
	b, _ := getUnsignedInt(3)
	for _, v := range b {
		fmt.Printf("%x", v)
		fmt.Println("")
	}
	c, d := getUnsignedInt(256)
	for _, v := range c {
		fmt.Printf("%x", v)
		fmt.Println("")
	}
	for _, v := range d {
		fmt.Printf("%x", v)
		fmt.Println("")
	}
}

const uint64Size = 8

func getUnsignedInt(x uint64) ([]byte, []byte) {
	buf := make([]byte, 9)
	var data []byte
	if x <= 0x7F {
		b := make([]byte, 1)
		b[0] = byte(uint8(x))
		return b, b
	}
	binary.BigEndian.PutUint64(buf[1:], x)
	a := bits.LeadingZeros64(x)
	bc := a >> 3
	buf[bc] = uint8(bc - uint64Size)
	data = buf[bc : uint64Size+1]
	return buf, data
}

Signed Int のエンコーディング

次がもっとも辛かったパート。やっと理解できましたので、解説します。

A signed integer, i, is encoded within an unsigned integer, u. Within u, bits 1 upward contain the value; bit 0 says whether they should be complemented upon receipt. The encode algorithm looks like this:

Signed Integer i は、Unsigned Integer u として、エンコードされます。uの中で、1ビット目とそれ以上は、値を持っています。ビット０は、補数にするかいなかを決めます。アルゴリズムは次のようです。

var u uint
if i < 0 {
	u = (^uint(i) << 1) | 1 // complement i, bit 0 is 1
} else {
	u = (uint(i) << 1) // do not complement i, bit 0 is 0
}
encodeUnsigned(u)

The low bit is therefore analogous to a sign bit, but making it the complement bit instead guarantees that the largest negative integer is not a special case. For example, -129=^128=(^256>>1) encodes as (FE 01 01).

０ビット目はだから、符号ビットのようなものです。しかし、補数化することによって、最大の負の整数が、スペシャルケースにならないようにしています。例えば、-129は^128であり、^256>>1でエンコード化した結果は (FE 01 01)です。

なんだこれは、、、ガチで意味がわからない、、、文書を読んでも全くわからない。Facebook の友達とやりとりして、私は、そもそも、２の歩数がわかっていないとわかりました。

補数について学ぶ

ちなみに、補数に関しては、この方のブログが最高でした。

• 2の補数を理解する (1)

1 の補数　(1s complement)

補数には２種類あります。例えば８ビットの表現での１の補数は、ビットを反転した値になります。１の補数の意味は、ある値に対して、その補数を足すと、ギリギリ桁が増えないという値です。

例えば

0010 1110 0x0A 0xBA

の１の補数は

1101 0001 0xB1 0x01

になります。２つを足すと

1111 1111 0xFF 0xFF

になり、桁あふれしない最大数になっています。

2 の補数 (2s complement)

２の補数は、足したら、桁あふれする数です。つまり

0010 1110

の２の補数は、先ほどの１の補数に対して、１を足せば求められます。

1101 0001 + 1 = 
1101 0010

二つを足すと

1 0000 0000

になります。これは、2のn(ビットの桁数）ここでは、２の８乗になります。この値になるようなものが、２の補数です。

2 の補数の用途

２の補数は、Signed Int　でマイナスの値を表すのに使われます。SignedInt では、先頭１ビットが、符号ビットになり、0 ならば、正の数、1ならば負の数としてバイナリが表現されます。

例えばこんな感じ

-127 のバイナリを求めたい時は、127 の２の補数を求めます。

0111 1111 (127)
1000 0001 (-127) ２の補数

とても、簡単です。さらに、なぜこんなことをするかというと、色々都合が良いのです。例えば、計算をするとすると

10 - 127 を計算するとすると 10 + (-127) になりますので、

  0000 1010 (10)
+ 1000 0001 (-127)
-------------------
  1000 1011 (-117)

ちなみに、性質上、２の補数から、その２の補数を求めると、元の数になります。１の補数も同じです。

だからこの場合、あっているかは、２の補数を求めてみましょう。

  1000 1011 (-127)
  0111 0101 (117)

完璧ですね。このため、この表現を使うことによって、電子回路で演算子を作るときに、マイナスの回路を組まなくてもよくなります。

１６ビットの演算

For example, -129=^128=(^256>>1) encodes as (FE 01 01).

とか言っていましたが、上記の理屈が理解できても、この理屈はさっぱり理解できません。なんで、-129 が、01 01 になるんだろう、、、、補数は、何ビットで考えるを考えないと、値は変わってきますので、多分おそらく、この作者は、16 bit を想定して考えているのだと思います。そして、補数を計算してみましょう。特に、-129なんてどうやって表すんだろう、、、８ビットならわかるけど。だって、先頭ビットの符号をどう考えるのよ。

苦しんでいたら、友人が助けてくれました。

Harada Kiro 0b1111 1111 1111 1111 = -1 なので、そこから128ひけばよろしい。

なんでそもそも、これが、-1 やねん、、、普通に１６ビットで補数を考えてみよう。

0000 0000 0000 0001 (1)
1111 1111 1111 1111 (-1)

あ、ほんまや、反転して、１を足したらこれになる。さらに彼は

Harada Kiro 0b0000000000000000 から、1引くと？

１の補数をとって、足せばいいから

0000 0000 0000 0001 (1)
1111 1111 1111 1111 (-1)

 0000 0000 0000 0000 (0)
[phone] 1111 (-1)
---------------------
 1111 1111 1111 1111 (-1)

なるほど。

彼は最初に

Harada Kiro 0b1111111111111111 = -1 なので、そこから128ひけばよろしい。

と言っていたので、その通りにしてみよう。

  0000 0000 1000 0000 (128)
  1111 1111 1000 0000 (-128)

  1111 1111 1111 1111 (-1)
 [phone] 0000 (-128)
--------------------------
1 1111 1111 0111 1111 (-129) 

ややこしいですが、先頭の桁が上がりますが、この先頭のビットが同じなので、補数の計算ルールにより、先頭の１は無視できます。これもこのブログが最高

• 2の補数を理解する (2)

つまり、-129 の二進数表現は、0x 1111 1111 0111 1111

For example, -129=^128=(^256>>1) encodes as (FE 01 01).

さて、これに戻ると、色々謎が出てきます。^128 ってなんやねん。という話です。プログラミングの演算の^ は、XOR ですが、XOR には、何ビットに対して XOR やねんという問題が生じます。リファレンスを読んでみましょう。

• Go - Operators

これを見ると

^ Binary XOR Operator copies the bit if it is set in one operand but not both. (A ^ B) will give 49, which is 0011 0001

と書いてあります。単独で使った場合は、よくわかりませんが、Int32 ならその範囲、Int64 ならその範囲で XOR と思われます。つまりこの場合は、筆者は、１６ビットを想定しているはず。

1111 1111 0111 1111 (-129)
0000 0000 1000 0000 (128)
1111 1111 0111 1111 (^128 = 128 XOR 0x FFFFFFFF)

0000 0001 0000 0000 (256)
1111 1110 1111 1111 (^256) 
1111 1111 0111 1111 (^256 >> 1)

確かに。で、なんで、それが、(FE 01 01) になるのよ。

• 算術シフト演算

Signed Integer i は、Unsigned Integer u として、エンコードされます。uの中で、1ビット目とそれ以上は、値を持っています。ビット０は、補数にするかいなかを決めます。アルゴリズムは次のようです。

と言っていますので、普通と反対で、このエンコーディングでは、０ビット目が符号ビットみたいな役割になっている様子です。ちなみに、先ほど添付したコードは動きませんので、本家のコードをみてみました。

// encodeInt writes an encoded signed integer to state.w.
// The low bit of the encoding says whether to bit complement the (other bits of the)
// uint to recover the int.
func (state *encoderState) encodeInt(i int64) {
	var x uint64
	if i < 0 {
		x = uint64(^i<<1) | 1
	} else {
		x = uint64(i << 1)
	}
	state.encodeUint(x)
}

プラスの場合は簡単で、 値を、単に左シフトしています。一番右のビットが０だと正の数なので例えば、129 だと

0000 0000 1000 0001 (129)
を左シフトするので
0000 0001 0000 0010 (シフト後)

なるほど、これだと、デコードの時も、シフトしたら終わりですね。

じゃあ次に、負の数。

x = uint64(^i<<1) | 1

をまず理解する必要があります。実験により、^ は、１の補数とわかりました。それに対して、<<1シフトをしています。ここは、先ほどと同じです。 | 1 はなんでしょうか？

Bitwise OR |

• Go - Operators

とあります。つまり、1 のORなので、意味合いとしては、０のビットを１にするということですね。
やってみましょう。

1111 1111 0111 1111 (-129)
0000 0000 1000 0000 (^-129)
0000 0001 0000 0000 (<< 1)
0000 0001 0000 0001 (| 1) = OR 1

= 0x01 01

おー、やっとわかったわー。しかし長すぎた、、、、わしは、terraform のアーキテクチャを理解したいだけなのに、何故こうなった、、、

まとめ

１日丸々深夜まで、たった一つのことを理解するのに時間を費やしてしまいました。なんでこんなことになったのでしょう。１つは英語力です。日本で数学を学んだので、数学の用語がわからなかったので、意味が取れていなかったということがあります。もう一方で、数学の知識です。２の補数とか、そんなの習ったかなぁぐらい、少なくともさっぱり忘れていました。もしくは知りませんでした。
　最後に、Kiro さんをはじめ、助けてくださった人のおかげなのですが、ここまで困ったときは、もっと素直に人に相談すればよかったかもしれません。最後のTipsなのですが、最終的にここのgob のマニュアルに書いてあったことを理解できたのは、上記の全てももちろん重要ですが、最後は、コードを読みました。やっぱコードが一番確実です。色々試行錯誤コードを書いたり、何故FEになるのかの確信が持てたのも、コードを書いて、デバッグツールを使って、値を確かめたから、意味が理解できました。デバッガ最高！やっぱりコードだけは嘘つきません。

次はやっと、gob に到達できる、、、（本当は、terraform の pluginの仕組みを理解したかったりするだけなのですが)

Resource

• Package gob
• ビッグエンディアン
• encode.go
• 2の補数を理解する (1)
• 2の補数を理解する (2)
• Go - Operators
• 算術シフト演算
• 自分が格闘したコード Gistに置いた

補足

Takashi Okawa さんが、単項の ^ 演算子の仕様について、Go の言語仕様に書いてあることを教えてくれました。ここのページで、^ で検索するといいです。

• Go プログラミング言語仕様