バイナリパッキングは楽しい

なぜ誰もこんなことをするのだろうか？バイナリパッキングとは何か？スキーマ構文の構築 実装の時間 データエンコーディングとデコーディング コンパイラの構築 問題点 字句解析器（Lexer）の構築 AST（抽象構文木）とは？ ASTの構築 パーサーの構築 意味解析器（Semantic Analyzer）の構築 動的パッカー コード生成（Codegen） ビジターパターン CLIの構築 結論 なぜ誰もこんなことをするのだろうか？Twitterで、JSONでデータを保存するのは「本物の™開発者」のやり方ではないと主張する人がいるのを見かけました。当然、私も「本物の™開発者」になる必要がありました。調べてみると、答えはバイナリでした。当然、私は「自分のバイナリフォーマットを作るのは、どれほど難しいだろうか？」という素晴らしいアイデアを思いつきました。きっと少しの作業で済むはずです。( ˶ˆᗜˆ˵ ) 残念ながら、それは少しの作業では済みませんでした。結局、JSONペイロードを80%も削減できる、完全なバイナリスキーマ言語を構築することになりました。 jBin バイナリパッキングとは何か？ 例えば、「hello world」というデータがあるとします。これはASCIIでは104 101 108 108 111 32 119 111 114 108 100、つまり h e l l o [スペース] w o r l d と変換されます。hはASCIIで104になります。これらのASCII値は8ビットに収まるため、各文字は1バイトを消費します。 h e l 01101000 01100101 01101100 l o [SPACE] 01101100 01101111 00100000 w o r 01110111 01101111 01110010 l d 01101100 01100100 なので、C言語で簡単に書けます。 FILE *f = fopen("file.bin", "wb"); unsigned char data[] = "hello world"; fwrite(data, 1, sizeof(data) - 1, f); fclose(f); シンプルですね。では、104を書き込んでみましょう。明らかに、104をASCII文字として書き込むことができます：「1」「0」「4」→ 49 48 52。しかし、これは1バイトで十分な数に対して3バイトもかかります。そのため、これらの2バイトを節約したい場合は、デコーダーに「これは文字列ではなく整数です」と伝える方法が必要です。ヘッダーを追加できます。追加するのはわずか1バイトです（まあ、タイプがいくつあるかによりますが…128種類以上のタイプがないことを願います…もしあれば、もっと大きな問題があります。素晴らしい！最初のバイトをタイプ、2番目のバイトをデータとして使用しましょう。 [タイプ][データ] 例えば、0が整数、1が文字列だとすると、104は 00000000 01101000 となり、文字列は… 00000001 01101000。おっと…これではhしか表現できません。異なる長さのデータを表現する方法が必要です。まあ、もう1バイト追加しましょう。それは文字列の長さを表すはずです。これで、バイナリは [タイプ][長さ][データ] となります。 素晴らしい！これで文字列と整数を一緒にパックできます！例えば、「userid」: 123 を表現したいとします。これで、すべてを一緒にパッケージ化できます。 [タイプ:文字列][長さ:6][単語:userid][タイプ:整数][長さ:-][データ:123] 素晴らしい！123を2バイトのヘッダーで1バイトの数値として表現できます。しかし、整数にはLENGTHフィールドを実際には使用していないことに注意してください。なぜそれが必要なのでしょうか？無駄なバイトですよね？さて…もしそれを削除したら、バイナリリーダーはヘッダーがどこで終わるのかを知る方法はどうなるでしょうか？ヘッダーの終端を伝える方法が必要です。「ヘッダーは終わり、実際のデータの読み取りを開始してください」と。うーん。バイトの終端を表すために何を使えばいいでしょうか？ヘッダー用の長さバイト、例えば？ええ。それは冗長です。長さフィールドを削除して、別の長さフィールドを追加することになります。しかし、ヘッダー自体にビットを使用できるかもしれません。1つのビットで「私はヘッダーの最後のバイトではありません。まだあります」と伝えることができます。あなたは思うかもしれません、なぜLSB（最下位ビット）を使わないのか？そうすれば、偶数しか表現できなくなります。それは…理想的ではありません。そのため、MSB（最上位ビット）を使用します。 これで、タグは次のようになります。 [継続ビット][7ビットのデータ] 継続ビットが1の場合、ヘッダーバイトがもう1つあります。0の場合は、ヘッダーは終了です。 これを使用すると、123は次のようになります。 [タイプ=0][データ=123] 文字列の場合は、 [タイプ=1][長さ=11][データ=104]... つまり、タイプ1、長さ11ですが、待ってください…長さが127を超える場合はどうでしょうか？7ビットでは最大127までしか表現できません！同じことを整数にも使用します！最初のビットが1の場合、整数は続きます。 128は次のように書き込めます。 10000001 00000000 ^ MSB / 継続ビット（ビッグエンディアン） バイナリリーダーは次のように動作します。 最初のバイトを読み取ります。MSBは1なので、もう1バイトあります。残りの7ビットは1です。2番目のバイトを読み取ります。MSBは0なので、これが最後のバイトです。残りの7ビットは0です。2つの7ビット値を組み合わせて128を取得します。これは一種のvarint（可変長整数）です。使用しているエンコーディングはリトルエンディアンです。最も重要でない7ビットが最初にきます。 10000000 00000001 これは素晴らしいですね？同じバイナリで異なるタイプを表現でき、バイナリパーサーはそれらをすべて正しく読み取ることができます。 しかし、注意してください。データをフィールドごとに保存しています。 [タイプ][データ] [タイプ][データ] [タイプ][データ] そして、ほとんどのデータはランダムな値が浮遊しているだけではありません。通常は構造化されています。Cの構造体を見てみましょう。 struct { int i; char *s; int a[10]; } これは32ビットシステムでは次のようになります。 [32ビット整数] [32ビットポインタ] [10 × 32ビット整数] そして、毎回ヘッダーを追加する必要はありませんでした。なぜなら、構造体自体からデータのタイプを知っているからです。 うーん。これをバイナリデータにも応用できるのではないかと思います… そして、はい、できます。それがスキーマです！ そのため、構造体の場合、スキーマは次のようになります。 i: int s: char * a: list(int) スキーマにより、タイプを各値と一緒に保存することなく、タイプを知ることができます。 これで、バイナリフォーマットはタイプを気にする必要がなくなりました！データサイズだけを気にする必要があります！それがプロトバフが行っていることです。 では、さまざまなデータサイズを考えてみましょう。整数、浮動小数点数、ブール値、文字列があります。整数とブール値はvarintとして扱い、浮動小数点数は固定幅：f32またはf64です。文字列は異なります。バイトをvarintとしてエンコードすることはできません。なぜなら、バイト自体が保存する必要のある実際のデータだからです。そのため、文字列のバイト数を読み取る前に知る必要があります。 これで、エンコーディングタイプは次のようになります。 varint f32 f64 delimited（区切り文字付き） しかし待ってください…フィールドにどのようにアクセスしますか？「文字列をちょうだい」と言うだけではいけません。どれかを指定する必要があります。問題ありません。それぞれを数値で表現しましょう。インデックスを付けるか、ユーザーに独自の番号を割り当ててアドレス指定できるようにします。これがフィールド番号が必要な理由です。 そして、もう1つ注目してください。可能なタイプは4つだけです。4つの値は2ビットにぴったり収まります。 00 - varint 01 - f32 10 - f64 11 - delimited これは素晴らしいですね。 では、それをエンコードしましょう…フィールド番号の中へ！ どうやって？バイナリのトリックです…いや、実際には違います。それらを一緒に詰め込むだけです。フィールド番号を左に2ビットシフトして、2ビットのタイプのためのスペースを作り、その空きビットにタイプをORします。 フィールド番号が10で、それがdelimitedタイプだとします。 00001010 (10) それを2ビット左シフトします。 00101000 タイプとORします！ 00101011 見てください！1バイトの数値が、タイプとフィールド番号の両方を教えてくれます！ しかし、さらに進むことはできませんか？すでにフィールド番号にタイプをパックしました。なぜそこで止まるのですか？長さをパックすることもできたらどうでしょうか？できます。 これで、ヘッダーは次のようになります。 [フィールド番号][長さ][タイプ] すべて1つのvarintの中に！！！！ ◝(ᵔᗜᵔ)◜ クール。ただし、1つのこと以外は、非常に手間のかかる作業です。文字列をパックするには、「これはdelimitedである」と伝え、長さを指定し、バイトを指定する必要があります。毎回。毎回。農民はそうします。下層民。私たちはそうしません。したがって、明らかに、解決策は完全なスキーマ言語を書くことです。スキーマファイルにデータを宣言し、プログラムにすべての面倒なフォーマットとエンコーディングのナンセンスを処理させます。 スキーマ構文の構築 さて…魂を吸い取らない構文を決定する必要があります（プロトバフを見ているよ）。 フィールド番号…それらは何ですか？インデックスですよね。食料品リストの項目にどのようにインデックスを付けますか？番号を書きます。アイテム。なぜ同じものを使わないのですか？だから、このようなものです。 1. 名前 スキーマはタイプを表現する必要があります。他の言語がどのように行うかを盗んで、次のようにしましょう。 1. 名前: タイプ いいね？しかし、待ってください。メッセージ（構造体）の終わりを示すにはどうすればよいでしょうか？まあ、d