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

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

<img width="1115" alt="Screen Shot 2017-09-25 at 1.11.04 AM.png" src="https://qiita-image-store.s3.amazonaws.com/0/3470/a91157c6-9b67-d251-c976-20031db95b79.png">


# 理解したいアルゴリズム

これは、[Package gob](https://golang.org/pkg/encoding/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以下なら、バイトの値で送られる。そうでなければ、最短の[ビッグエンディアン](http://www.ertl.jp/~takayuki/readings/info/no05.html)の値を持ったバイトストリームで送られる。最初の１バイトは、バイトカウントで、無視される。そのため、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](https://github.com/golang/go/blob/master/src/encoding/gob/encode.go)

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

```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) ](https://godoc.org/math/bits#LeadingZeros64) は、先頭の使っていないビットを取得する。例えば、

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

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

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

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

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

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

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

```go
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 の位置から、最後までを移送している

```go
data = buf[bc : uint64Size+1]
```

```
buf
□　□□□□　□○■■ 0x00  0x00 0x00 0x00 0x00  0x00 0xFE 0x01 0x00
　　　　　 ↑ここ
data
○■■ 0xFE 0x01 0x00
```
これで、この仕様のエンコードの方法が理解できました。


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

```go

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ビット目とそれ以上は、値を持っています。ビット０は、補数にするかいなかを決めます。アルゴリズムは次のようです。

```go
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)](http://d.hatena.ne.jp/simply-k/20100824/1282743815)

## 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)
+1111 1111 1111 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)
 +1111 1111 1000 0000 (-128)
--------------------------
1 1111 1111 0111 1111 (-129) 
```

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

* [2の補数を理解する (2)](http://d.hatena.ne.jp/simply-k/20100825/1282743815) 

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

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

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

* [Go - Operators](https://www.tutorialspoint.com/go/go_operators.htm) 

これを見ると

> ^	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)` になるのよ。

* [算術シフト演算](http://www.geocities.jp/zaqzaqpa/2sinsuu11.htm)

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

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

```go
// 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](https://www.tutorialspoint.com/go/go_operators.htm) 

とあります。つまり、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](https://golang.org/pkg/encoding/gob/)
* [ビッグエンディアン](http://www.ertl.jp/~takayuki/readings/info/no05.html)
* [encode.go](https://github.com/golang/go/blob/master/src/encoding/gob/encode.go)
* [2の補数を理解する (1)](http://d.hatena.ne.jp/simply-k/20100824/1282743815)
* [2の補数を理解する (2)](http://d.hatena.ne.jp/simply-k/20100825/1282743815) 
* [Go - Operators](https://www.tutorialspoint.com/go/go_operators.htm) 
* [算術シフト演算](http://www.geocities.jp/zaqzaqpa/2sinsuu11.htm)
* [自分が格闘したコード Gistに置いた](https://gist.github.com/TsuyoshiUshio/22fc9f3af0b927d6191ef1bf7e77b46e)

# 補足

Takashi Okawa さんが、単項の `^` 演算子の仕様について、Go の言語仕様に書いてあることを教えてくれました。ここのページで、`^` で検索するといいです。
* [Go プログラミング言語仕様](http://golang.jp/go_spec#Operators)