http://d.hatena.ne.jp/propella/20091016/p1 で書いた逆転可能バイナリパーサについて、ここで実際にどんな事がしたいのか書いてみます。
avm2 では整数は次のようなルールでエンコードされます。
- 整数が 7 ビットの範囲に収まる場合、
- 0-6 ビットを 1 バイトのデータとして書き出す。最上位ビットを 0 にする。
- 整数が 14 ビットの範囲に収まる場合、
- 0-6 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 7-13 ビットを 1 バイトのデータとして書き出す。最上位ビットを 0 にする。
- 整数が 21 ビットの範囲に収まる場合、
- 0-6 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 7-13 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 14-20 ビットを 1 バイトのデータとして書き出す。最上位ビットを 0 にする。
- 整数が 28 ビットの範囲に収まる場合、
- 0-6 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 7-13 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 14-20 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 21-27 ビットを 1 バイトのデータとして書き出す。最上位ビットを 0 にする。
- 整数が 32 ビットの範囲に収まる場合、
- 0-6 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 7-13 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 14-20 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 21-27 ビットを 1 バイトのデータとして書き出す。最上位ビットを 1 にする。
- 28-31 ビットを 1 バイトのデータとして書き出す。最上位 4 ビットは常に 0。
これで、32 ビットの整数が最大 5 バイトの可変長データになります。読む時は最上位ビットが 0 になるまで読み進んで低位ビットから組み立てます。大して難しいアルゴリズムじゃ無いけど、そのまま書き下すと条件文が連なってひどく見にくいし、読み書きに二度同じようなプログラムを書くのもばかばかしいです。という事でこういうのをすっきり書ける文法が欲しいです。Erlang のビットストリング記法を真似てでっち上げるとこんな感じでしょうか。
vint = 0:1 Num0:7 -> 0:25 Num0:7
/ 1:1 Num0:7 0:1 Num1:7 -> 0:18 Num1:7 Num0:7
/ 1:1 Num0:7 1:1 Num1:7 1:0 Num2:7 -> 0:11 Num2:7 Num1:7 Num0:7
/ 1:1 Num0:7 1:1 Num1:7 1:1 Num2:7 1:0 Num3:7 -> 0:4 Num3:7 Num2:7 Num1:7 Num0:7
/ 1:1 Num0:7 1:1 Num1:7 1:1 Num2:7 1:1 Num3:7 0:4 Num4:4 -> Num4:4 Num3:7 Num2:7 Num1:7 Num0:7これは読み込みの立場から見た文法を表しています。最初の vint はルールの名前で、= の後にルールの内容が続きます。
ルールは二つのパターン列を -> でつなげた形をしています。左側のパターンにマッチすれば右側のパターンを使って結果が出力されます。
一つ一つのパターンは名前:ビット数という形をしています。名前は変数名か定数で例えば最初の 0:1 Num0:7 は 1 ビットのゼロ の後に 7 ビットのデータが続き、データが Num0 に格納される事を意味します。
マッチすれば今度は -> の右側が構築されます。この場合 0:25 Num0:7 なので、25 ビット分ゼロで埋めた後見つけた Num0 を入れます。結果 127 までの 32 ビット整数が生成されます。
/ は順序付き選択で、入力の最初のビットが 0 で無かった場合は次の行、/ の後ろに進みます。もしもマッチするルールが無ければ文法エラーです。
- > の左右を入れ替えるとそのまま今度は書き込みに使えます。
これは我ながらすごい恐ろしく便利なアイデアでは無いだろうか。。。
