考えている事をだらだら書きます。
バイト列
前回取り上げた amv2 の 可変長整数の例があまりにも単純すぎたので、もうちょっと難しい例を考えてみます。ありがちなバイト列のエンコーディングとして、最初の 1 バイトが長さで、残りのバイトで 0 - 255 バイトのバイト列を現す事を考えます。構造体チックな書き方をすればこんな感じ。型名を小文字で、変数名を大文字で書きます。
bytes { char Size; char[Size] Data; } char { bit[8] Data; // bit はプリミティブ型 }
この記法が問題なのは、bytes の中で Data が Size に依存しているという事を上手く現せない事です。プログラマは頭の中でずっと Size は Data の長さだという事を意識しないと行けません。そこでちょっと記法を変えて、Data が主役なんだ!という事を強調します。内部的にバイト列をどう持とうが良くなって便利です。
Data:bytes := Size:char Data:[Size]char Data:char := Data:[8]bit
ついでに go 風に、変数名:[サイズ]型名 の順序で書くようにしてみました。どこかにこの順序だと良い事があると書いてありました。何となく prolog 風に書くのも良いかなと思って悩んでいます。
bytes(Data) :- seq(char(Size), char(Size, Data)). char(Data) :- bit(8, Data).
可変長整数
変数名:サイズ を 変数名:[サイズ]bit の略だという事にすれば、前回の可変長整数はこう書けます。ほとんど左右を逆にして、順序付き選択の記号 / を省略しただけです。
(0:25 Num0:7):u32 := 0:1 Num0:7 (0:18 Num1:7 Num0:7):u32 := 1:1 Num0:7 0:1 Num1:7 (0:11 Num2:7 Num1:7 Num0:7):u32 := 1:1 Num0:7 1:1 Num1:7 1:0 Num2:7 (0:4 Num3:7 Num2:7 Num1:7 Num0:7):u32 := 1:1 Num0:7 1:1 Num1:7 1:1 Num2:7 1:0 Num3:7 (Num4:4 Num3:7 Num2:7 Num1:7 Num0:7):u32 := 1:1 Num0:7 1:1 Num1:7 1:1 Num2:7 1:1 Num3:7 0:4 Num4:4
長方形
さて、今までは例えば Num0:8 Num1:8 のように書くとどういう訳か勝手に 16 ビットの整数が出来るかのように書いていましたが、8 ビットの整数二つが欲しい場合と区別しないといけません。そういう時はコンマで区切る事にしてみます。また、符号が必要な時もありますので別の原始型 sbit を用意します。すると swf の長方形オブジェクトはこんな感じで表現出来るでしょう。swf の長方形オブジェクトは次のようにエンコードされます。
- 最初の 5 ビットで要素のビット長 Nbits (0-31) を現す
- Nbits の分ずつ残りの要素 Xmin Xmax Ymin Ymax が置かれる。
これは素直にこう書けるでしょう。
(Xmin:[Nbits]sbit, Xmax:[Nbits]sbit, Ymin:[Nbits]sbit, Ymax:[Nbits]sbit):rectangle := Nbits:5 Xmin:[Nbits]sbit Xmax:[Nbits]sbit Ymin:[Nbits]sbit Ymax:[Nbits]sbit
これと、私が昔 erlang で書いた swf の長方形オブジェクトを書き込むプログラムを比べてみます。
nbits_unsigned(XS) -> % Necessary bits size for a list of integer values. Max = lists:max([abs(X) || X <- XS]), trunc(math:log(Max) / math:log(2)) + 1. nbits_signed(XS) -> nbits_unsigned(XS) + 1. rectangle({rectangle, Xmin, Xmax, Ymin, Ymax}) -> Nbits = nbits_signed([Xmin, Xmax, Ymin, Ymax]), padding(<< Nbits:5, Xmin:Nbits/signed-big, Xmax:Nbits/signed-big, Ymin:Nbits/signed-big, Ymax:Nbits/signed-big>>).
逆転パーサー版は何か情報が足りない事が分かります。Nibts というのは、長さを表現するのに最低限必要なビット数という意味なのですが、逆転パーサ版の定義からそれを読み取る事は出来ません。読み込みはともかく、書き込む際にそれぞれの要素から Nbits を推論する必要があります。このロジックをどう埋込むかというのが味噌だと思うのですが、良い方法を思い浮かばないので今日はこれでおしまいにします。