ちりもつもればミルキーウェイ

好奇心に可処分時間が奪われる

バイナリのbit表現を得られるencodingパッケージ作った

Go エンコーディング

動機

連休中はバイナリとダンスして遊んでたんですが、Goプログラムから柔軟にバイナリをbit表現で出力できないのがちょっと不便でした。

たとえば標準の機能で

for i := 0; i < len(src); i++ {
    fmt.Printf("%08b", src[i])
}

のようにすれば、1byteごとにpadding付きbit表現を得ることができます。
これで充分なケースも多いですが、個人的には以下のような課題を感じていました。

  • ioが柔軟でない
    • io.Reader / io.Writer を実装してストリームに対しても使えるとgood
  • fmtパッケージを使った formatted io に依存しててそこそこコストがつきそう
    • ちゃんと書いたほうがよさげ
  • xxd -b での出力のような、読みやすい出力をサポートしたい

これらの実装は都度やるにはちょっと面倒だけどそんな難しくなさそうで、いっちょオレオレencodingパッケージ書いたるかとなった次第です。

作ったもの

レポジトリはこれです

github.com

先程あげた課題を解決するために作ったので、単純な Encode() / Decode() 機能のみでなく以下の特徴を備えています

  • io.Writer を満たしたencoderの提供
  • io.Reader を満たしたdecoderの提供
  • xxd -b のようなdump出力のための Dump() 関数の提供
  • io.WriteCloser を実装したdumperの提供

exampleいくつか書いたので、このへんをみれば雰囲気わかるはず https://pkg.go.dev/github.com/convto/bit#pkg-examples

イチオシはdump出力機能です

dump := Dump([]byte("dump test"))
fmt.Printf("%s\n", dump)

// Output:
// 00000000: 01100100 01110101 01101101 01110000 00100000 01110100  dump t
// 00000006: 01100101 01110011 01110100                             est

hexとの類似点

そもそも実現したいこと自体が標準パッケージの encoding/hex とハチャメチャ近いです。ここではどのようにhexと近いのか軽く説明します。

hexは16進数を0~fにマッピングすることで、1文字あたり4bitを表現できるencodingです。今回つくりたいものは1文字あたり1bit表現するencodingです。
大きい共通点として hexと今回作りたいencodingは1文字が表現するbit数がともに8の約数 ということです。これはどういうことかというと、特段考慮せずともencodeした文字がbyteで整うということです！

たとえば []byte{255, 255} というbyte列があるとして、hexのほうに便宜上bit幅分のpaddingとして _ をとると

hex: f___f___ f___f___
bit: 11111111 11111111

のように表現できます。これが1文字6bitのbase64とかだと

base64: /_____/_ ____8___ __=_____ (最後の=はbyte単位に出力するためのpadding)
bit:    11111111 11111111          (0とpaddingのみの不要なbyteは捨てられる)

みたいな感じになります。6bitは8の約数ではないのでbyte単位で揃わずにズレて面倒なことになります。base64の標準パッケージではそのあたりの考慮が入っており、encode/decodeともに少し面倒な感じの処理になってます。

それと比較してかんがえると、hexと今回作るbit単位のencodingはともに8の約数であり、byteが揃わないことを考慮しなくていいという点で非常に似ています。

1byteを4bitごとに2文字に分けたものがhexであり、今回つくるものはそれを更に細分化して1byteを8文字に分けるだけ、どっちも共通してbyte単位で揃わない場合を考慮する必要はなさげ！と考えると、hexの実装が全面的に参考にできそうなことがわかります。

encoding/hexを読んで実装！

結論をいうとencoding/hexの処理全部よんでやってることを完全に理解したので、ほぼそのとおりに実装したという感じです。

コードの書き方とかコメントの振り方とかはかなり参考にしていて、半ばコピペなのではというくらい構成含めマネしています。
(テストとかは実際コピペしたあとテストコードを直してます。io絡むテストの書き方の参考になった)

あんまり言うことは無いのでみんなもhex読んでね！

一応軽く符号化部分だけ触れておくとこんな感じです。筋肉の力を感じますね。

const (
    bitTable = "01"
    b1       = 0b00000001
    b2       = 0b00000010
    b3       = 0b00000100
    b4       = 0b00001000
    b5       = 0b00010000
    b6       = 0b00100000
    b7       = 0b01000000
)

func Encode(dst, src []byte) int {
    j := 0
    for _, v := range src {
        dst[j] = bitTable[v>>7]
        dst[j+1] = bitTable[(v&b7)>>6]
        dst[j+2] = bitTable[(v&b6)>>5]
        dst[j+3] = bitTable[(v&b5)>>4]
        dst[j+4] = bitTable[(v&b4)>>3]
        dst[j+5] = bitTable[(v&b3)>>2]
        dst[j+6] = bitTable[(v&b2)>>1]
        dst[j+7] = bitTable[(v & b1)]
        j += 8
    }
    return len(src) * 8
}

すげー素朴に各bitを一個ずつ取り出してるだけっすね。あんまり考えてなくて適当に書いたけど、流石に fmt.Printf() とかで実現するよりマシなはず。

シフト演算を減らす案として

if v&b7 != 0 {
    dst[i+1] = '1'
} else {
    dst[i+1] = '0'
}

的なのも思いついたけど、条件分岐のコストとシフト演算ってどっちが軽いんだっけみたいなベンチとるのが面倒だったのと、bitのぶんだけこの分岐が入って見た目がグオ〜となりそうだったので見送っている

面白かったこととか参考になったこととか

  • 標準パッケージのEncode系の処理はだいたい呼び出し側に必要なサイズを持ったdstを作る義務を負わせていて、dstが小さかったら普通にpanicさせてる
    • 各エンコーディングライブラリが EncodedLen(srcLen int) int みたいな、元の長さからどれくらいdstが必要か返す関数みたいなのを持ってるのでそれで呼び出し側はdstに必要な長さを把握できる
    • encoding/base64使うときにそういう処理書いたことあるけど、全体的にそういうデザインになってるのはほえ〜となった
  • Goのhex実装はdecodeのときにhex charactersが偶数長であることを呼び出し側で保証しないとエラーになる
    • それ用のエラー がある
    • stream decodeのときは io.ErrUnexpectedEOF が返る。これは固定長ioでブロック長がおかしいときのエラー。しらなくて勉強になった
    • この挙動を参考にして、今回作ったbit encodingではbit charactersが8の倍数長でなければエラーを返すようにしている
  • encoding/hexには hexdump -C 相当の出力をする機能がサポートされてる！

最後に

バイナリとダンスしてるひとはぜひ使ってください〜！

実際エンコーディングとしては1文字あたりの表現力に乏しくて元データと比較して8倍に膨らんじゃうのであんまり使いみちは無いんですが、いい感じのdump出力をサポートしてるのでデバッグとかの用途でぜひ！