d0iの連絡帳

気がむいたら書く

[EXI][技術] データ型とその符号化

[EXI][技術] EXIとは何か？ (準備編) - doiの連絡帳 の続きです。本節では、EXIにおいて整数などの単純な型をどのように符号化するかについて説明します。なお、文字列についても触れるつもりでしたが、長くなってしまったので次回に分けます。

  1. [EXI][技術] EXIとは何か？ (準備編) - doiの連絡帳 (EXI Primer Primer)
  2. データ型とその符号化 (その1: 文字列以外) ← 今日はこれ
  3. データ型とその符号化 (その2: 文字列) ← こっちも書く気でしたが、長くなったので次回に…
  4. Schema-Informed Grammarと状態機械
  5. ポリモーフィズムの実現: xsi:any と String Table
  6. EXI by Example を読み解く

準備

前回の説明では、0b000 とか 0_3b (3ビットで値が0) とかいう表現を導入しましたが、今回は組み込みEXI型が登場するので、この表現も追加します(仮に、参照表現と呼ぶことにします)。例えば、"Int(0)"といったら、符号あり整数の0、となり、実際には0_9b(9ビットで値が0) となります(何故そうなるかは後述します)。また、結合(concatenation)の記号は"|"で表します。"Int(0)|Int(1)"とあったら、"0_9b|1_9b"すなわち"1_18b"(0b000000000000000001)となります。

参照表現まとめ:

  • True/False : ブール型(真/偽)
  • uInt(v) : 符号なし整数(値v)
  • nInt(v, n): nビット符号なし整数(値v, ビット長n)
  • Int(v): 符号あり整数(値v)
  • Float(m, e): 浮動小数点数(仮数部m, 指数部e)

概要

EXIにおいて、XML要素や属性などを表すための「イベント」*1は、以下の三つの要素からなります。

  1. イベント種別
  2. パラメータ (必要な場合、例えば SE(start element) イベントは、Element名のQName*2
  3. 値

これらの値を符号化する際に、本節で述べる EXI のプリミティブな値の符号化規則が活躍します。
例えば、「値」は、子要素などのイベントの列になる場合もありますが、プリミティブな「文字列」とか「符号付き整数」とかになる場合もあります。また、イベント型とパラメータは一組で状態遷移に対応するので、ストリーム上ではこれは一つの値(イベントコード)として符号化されます*3。この符号も「nビット符号なし整数 (n-bit unsigned integer)」という形式になります。

EXI仕様書の、Section 7が符号化の仕様です。まずTable 7-1が、XML Schemaにおけるプリミティブ型が、EXIにおけるプリミティブ型にどのように対応するかを示しています。なお、XMLスキーマで定義されている型システムについては、XML Schema Part 2: Datatypes Second Edition 特に Section 3 の図を参照してください。

スキーマが与えられた場合はスキーマ由来文法により、この型を活用して効率的に符号化されます。そうでない場合は通常のXMLと同様、記述されているままの文字列として符号化されます。なお、文字列については、同じ文字列を二度使わないように、文字列表 (String Table) をエンコーダ・デコーダ共に管理する必要があります*4。

プリミティブ型

以下、簡単なものから順番に説明します。以下、「実際の値」の説明ではなく、「型」の説明です。実際には、ある整数はn-bit unsigned integerで、別の整数はsigned integerで符号化する、などといった場合分けがあります(後述)。String Tableの説明が必要なので、QNameとStringについては後にまわします。なお、あるプリミティブ型は他のプリミティブ型に依存している場合もあります。図示すると以下のような感じでしょうか。

図中、矢印が依存関係を表しています。こうやって見ると、プリミティブ型だけでもなかなか複雑ですね。XMLスキーマが持つ組み込み型をできるだけコンパクトに表現すべく、工夫(苦労？)の跡が見て取れます*5。以下、できるだけ依存関係順に説明します*6。

ブール型 (7.1.2 Boolean)

基本的には1ビットで符号化します。0b0が偽で0b1が真です。簡単ですね! XMLSchemaのブール型に対応するだけじゃなく、整数の符号(正負)などにも使います。例外あり*7。

以下、表現を参照する必要がある場合は、False/Trueで表現します。

符号なし整数 (7.1.6 Unsigned Integer)

符号なし整数は7ビット単位で下位ビットから符号化されます。各バイトの最上位ビットが1のとき、次のバイトを読み、最上位ビットが0のときにこれを最終桁とします。

以下、参照の必要がある場合は、数値vを符号なし整数で符号化したものを、"uInt(v)"と表現します。

(位取りのために空白を挿入していますが、連続したビットです。以下同じ)

  • uInt(127): 0b0111 1111
  • uInt(128): 0b1000 0000 0000 0001
    • 例えば、上位1バイトの下位7桁と、下位1バイトの下位7桁を逆順に結合すると、"0b0000001|0b0000000" となり、0b00000010000000 = 128となります。

なお、EXIの仕様では、最低限サポートすべき符号なし整数の最大値は、2147483648とされています。

nビット符号なし整数 (7.1.9 n-bit Unsigned Integer)

値域が決まっている整数や、XML Schemaにおける列挙型 (Enumeration) 、イベントコードなどの表現に使われます。nビットで直接符号化します(bit-packedの場合)。つまり、符号化する、あるいは復号するタイミングで、次に来るnビット符号なし整数が何ビットで符号化されているのか (nがいくつなのか) 既知である必要があります*8。なお、EXIオプションがbyte-align(バイト単位符号化)の時は、nビットよりも大きい最小のバイト数で符号化します。その時は、LSBから順番にバイト単位で符号化します。

以下、参照の必要がある場合は、数値vをnビットで符号化したものを、"nInt(v, n)"と表現します。

  • 値域 0..3 における 3 = nInt(3, 2) = 0b11 (bit-packed) または 0b0000 0011 (byte-aligned)
  • 値域 0..14 における 3 = nInt(3, 4) = 0b0011 (bit-packed) または 0b0000 0011 (byte-aligned)
  • 値域 0..500 における 3 = nInt(3, 9) = 0b0 0000 0011 または 0b0000 0011 0000 0000 (byte-aligned)
符号あり整数 (7.1.5 Integer)

符号なし整数の前に、符号を表すブール型を追加したものです。符号が偽(ブール型の値が0)の時は正の数またはゼロを表し、真(ブール型の値が1)の時は負数を表します。ただし、負数については、実際の値よりも絶対値で1小さい値で符号化されます。

以下、参照の必要がある場合は、値vの符号あり整数を "Int(v)" で表現します。

(10進数: 対応する表現: ビット表現)

  • Int(2) = False|uInt(2) = 0b0 0000 0010
  • Int(1) = False|uInt(1) = 0b0 0000 0001
  • Int(0) = False|uInt(0) = 0b0 0000 0000
  • Int(-1) = True|uInt(0) = 0b1 0000 0000
  • Int(-2) = True|uInt(1) = 0b1 0000 0001
バイナリ (7.1.1 Binary)

長さLバイトのバイナリオブジェクトは、Unsigned Integerで長さLを符号化し、その後にLバイト、バイナリをそのまま書き込みます*9。

以下、参照の必要がある場合は、16進数表記の値vに対し、Bin(v)で表現します。

  • Bin(0xcafebabe) = uInt(4)|"0xcafebabe" = 0b00000100 (L=4) 0b11001010111111101011101010111110 (0xcafebabe)
十進数 (7.1.3 Decimal)

コンピュータは2進数で数値を表現するので、小数点以下について、10進数を正確に表現できないことはよく知られています*10。また、極端に大きな値についても浮動小数点数で表現すると誤差が発生します。元々のXMLは10進数のテキスト表現で数値を表現できるため、このような問題が発生させない数値表現として十進数型が用意されており、EXIにも対応する型としてEXIの十進数型が用意されています。

EXIの十進数は、符号を表すブール型の後に、整数部を表す符号なし整数、小数部を表す符号なし整数が続きます。ただし、小数部は、例えば"0.0001"のような数値を表現するのに"1"だけ書いてもしょうがないので、桁を逆順にしたものを符号なし整数として記述します。以下参照のため、値vの十進数型をDec(v)と表現します。

  • Dec(0) = False|uInt(0)|uInt(0) = 0b0 00000000 00000000
  • Dec(1.0001) = False|uInt(1)|uInt(1000) = 0b0 00000001 10000111 01101000
    • 小数部の"0001"が逆転して、"1000"として符号化されます。
浮動小数点数 (7.1.4 Float)

XMLの浮動小数点数(float, double)に対応します。EXIの浮動小数点数は、丸め誤差のない十進数にもとづく(基数を10とした)浮動小数点数です。以下、仮数部をm、指数部をeとして、値vは v = m \cdot 10^e*11 の関係にあるとします。このとき、浮動小数点数 Float(v) は以下のように符号化されます。

  • Float(v) = Integer(m)|Integer(e)

なお、仮数部mの値域は -2^{63} から 2^{63}-1 まで、指数部eの値域は -(2^{14}-1) から 2^{14}-1 までと定められており、これを逸脱することはできません。また、浮動小数点数の表現については以下のルールが存在します。

  • 指数部が -2^{14} の時は以下の特別な値を意味します
    • 仮数部が1、あるいは-1のときは、それぞれ無限大(INF)およびマイナスの無限大(-INF)を示します
    • 仮数部がそれ以外の値の時は、非数(NaN; Not a Number)を示します

なお、仮数部が整数で符号化されることから、元となる表現の仮数部に小数点が含まれる場合は、適切に位取りを変更する必要があります。

日付・時刻 (7.1.8 Date-Time)

XMLスキーマには、日付・時刻に関するいくつもの組み合わせが存在し、EXIにもこれに一対一で対応する表現があります。このさまざまな組み合わせを表現するために、EXIのDate-Timeでは以下の内部型を部品として持ちます。

  • Year(Y): 西暦年Yを、Int(Y-2000) で表現します。
  • MonthDay(M,D): 「M月D日」を、nInt(M*32+D, 9) で表現します。Mは1から12、Dは1から31です*12。
  • Time(h,m,s): 「h時m分s秒」を、nInt( (h*64+m)*64+s, 17) で表現します*13。
  • FractionalSecs(f): 1秒未満の値を、十進数型の小数点部と同様に、逆順で表現します。"0.021秒"であれば、uInt(120) になります。
  • TimeZone(z,y): UTCからのタイムゾーンのずれを「z時間y分」としたとき、nInt( (z*64+y)+896,11) で表現されます*14。なお、式中896は14*64ですが、14というのはUTCが+14まで存在することからと思われます*15。

XMLスキーマの各々の型に対応するEXIの表現は、以下の部品の組み合わせから成ります。ここでは、P[X]は、直前のpresence bit(P: ブール型)がTrueの時にのみXを登場させる、という意味です。PがFalseの時はXの存在自体が省略されます。

  • gYear = Year|P[TimeZone]
  • gYearMonth, date = Year|MonthDay|P[TimeZone]
  • dateTime = Year|MonthDay|Time|P[FractionalSecs]|P[TimeZone]
  • gMonth, gMonthDay, gDay = MonthDay|P[TimeZone]
  • time = Time|P[FractionalSecs]|P[TimeZone]
数の符号化の例外規則

基本的に、XMLスキーマで定義された型に応じてEXIで符号化する際のプリミティブ型は決まります(Table 7-1参照)。ただし、以下のような例外が存在します。

  • 浮動小数点数について、値域を外れる値については、「型無しの値(untyped value)」として符号化できる場合は行います。おおくの場合、文字列として送る、ということになると思いますが、詳細については私もちゃんと理解できていません*16。
  • XMLスキーマの整数型(xsd:integer)について、facetにより値域が決められていて、その値域の幅が4096以下のとき、この値域の幅をmとして、値域の下限からの距離vを n=floor(log_2 m) に対応するnビット符号なし整数 nInt(v, n) で表現する*17。
      • 値域 [5..10] における 7 = nInt(7-5, floor(log_2 (10-5+1))) = nInt(2, 3) = 0b010 (bit-packed) または 0x0000 0010 (byte-aligned)
      • 値域 [7..16] における 7 = nInt(7-7, floor(log_2 (16-7+1))) = nInt(0, 4) = 0b0000 (bit-packed) または 0x0000 0000 (byte-aligned)
  • 同様にfacetによる値域が決まっており、最低値が0よりも大きいとき、xsd:integerであっても符号なし整数として符号化する。この時は最小値からの距離ではなく、値をそのまま符号化する*18。

リスト型 (7.1.11 List)

リスト型は、リストの長さをLとして、uInt(L)に加えて値をL個連続で符号化します。

列挙型 (7.2 Enumerations)

EXIの符号化オプション*19のうち、Preserve.lexicalValue がfalseの時は、列挙型は、スキーマに定義された順序を、nビット符号なし整数の形で符号化します。なお順序は0から数えはじめます。なお、XMLの列挙型は重複を許すので、EXIの列挙型も重複を許します*20。

列挙型の表現については例外もありますが、この時点では説明し切れないので、原文を参照してください。

次回予告

本当は文字列型の説明までここで書くつもりだったのですが、力尽きました。次回はEXIの鬼門の一つであり、また、巧妙な仕掛けの一つである、文字列型およびQNameについて説明できたらなと思います。

*1:状態機械を駆動するための情報単位

*2:Qualified Name: 名前空間まで含めたタグの「正式名称」に相当するもの。ただし、XMLの文法でQNameを直接記述する手段はなかったりしてまたややこしいんだこれが。

*3:前回の解説のうち「EXIの文法と文書構造の符号化」を参照してください

*4:メモリが大変です…

*5:解釈して実装するほうもなかなか大変なんですが ^_^;

*6:EXIの仕様書が依存関係と無関係な順序になってしまっているので、一読して理解するのが大変なのですよね。ハイパーテキストというものの欠点かもしれません。

*7:pattern facetと呼ばれる方法で、XML Schemaで許されている4つの型 (true, false, 1, 0) を区別したい場合は、nビット符号なし整数をn=2で利用します。

*8:例えば、EXIのイベントコードは状態機械の各状態において、取り得る状態数から値域が決まります

*9:実装面での苦労を言うと、ここのバイナリコピーがbit-packだとバイト単位コピーできないので、大きいバイナリをコピーする時はちょっと泣けます。そういう用途にはbyte-alignedオプションを利用すればいいのですが。

*10:丸め誤差と呼ばれています

*11:v = m・10^e

*12:ところで、2月30日とか符号化されてたら受け手側はエラーを返すべきなんですかね。

*13:64で掛けてあるのは演算を簡単にするため、というのもあると思いますが、これでうるう秒も安心、というのもあるかもしれません。

*14:多分… 原文: 11-bit Unsigned Integer representing a signed integer offset by 896 の解釈を間違えていなければ。

*15:UTCはマイナス方向には12時間までしか定義されていないらしいので、13で十分な気もしなくもないですが…

*16:てか、strictの場合どうするんだろう…

*17:7.1.5 Integerより。結構頻出するのですが、実装者としては勘弁して頂きたい仕様の一つです（笑）

*18:多分…。

*19:詳細は本稿では説明していません -- どっかで説明したほうが良いですね。

*20:この仕様も困りものでして…内部的に #define などに落してしまうと、列挙型のどれとどれが実は同じ値なのか、ということを別途テーブルにする必要があります。まぁ実際はエンコード時にどう区別するんだよって話もあるんですが。