500バイトの画像:Haikuのベクターアイコン形式 – 後編

パス

パスのセクションは以下の部分です。

02 0a 0c 2b b3 da 2b b5 72 30 b5 72 30 b3 da 31
b3 da 31 b7 70 30 b7 70 30 b5 d8 2b b5 d8 2b b7
70 2a b7 70 2a b3 da 06 08 de 6e 40 24 28 28 b8
18 b3 6d b4 47 b8 f2 40 2c 54 b5 79 c6 39 ba 16
c9 36 3c 58 50 54 4c 54 c7 3d 54 58 40 24

上記がこのファイルで最大のセクションとなっている主な理由は、各パスの各点がエンコードされる必要があり、加えてブロブのパスの曲線セクションにはもっと多くの点があるからです。

パスは線セグメントから成っており、各セグメントは直線または曲線です。Hのパスは直線のみですが、ブロブのパスは直線と曲線が混ざっています。このため、パスのエンコード方法については2種類説明します。複雑さを増している他のエンコード方法と同様、このような区別があることで、スペースの節約が可能になっています。

最初のバイト02は、2つのパスがあることを示しています。それぞれのパスは、パスのフラグバイトと、点の数から始まっています。最初のパスでは、0aがフラグ、0cが点の数です。フラグでは、値ではなくビットのパターンに注目します。16進数の0aは、2進数では0000 1010となります。(1が2つあるので)フラグのうち2つがセットされていますが、その意味を解読するためには別のenumが必要です。

PATH_FLAG_CLOSED            = 1 << 1,
PATH_FLAG_USES_COMMANDS     = 1 << 2,
PATH_FLAG_NO_CURVES         = 1 << 3,

このフラグバイトには、グラデーションスタイルのフラグバイトと同様の働きがあります。つまり、このパスではPATH_FLAG_CLOSEDPATH_FLAG_NO_CURVESが当てはまります。PATH_FLAG_CLOSEDはレンダラーへの指示で、「最後の点を最初の点に線でつないでください」という意味です。このフラグは、パースには影響を及ぼしません。PATH_FLAG_NO_CURVESは、このパスには直線しかないということを表します。セットされているフラグと同じくらい重要なことなのですが、PATH_FLAG_USES_COMMANDSが偽の場合、このパスは点のリストとしてエンコードされるという意味です(コマンドについてはまだ気にする必要はありません)。このパスには直線しかありませんので、各セグメントは1つの点(x, y)で定義されることになります。

点の数は16進数で0cなので、12です。最初の点は2b b3 daです。これは、x座標(2b)とy座標(b3 da)から構成されています。各座標は1バイトか2バイトですので、各点は2バイトか3バイトか4バイトとなります。この最初のパスでは、たまたま全ての点でx座標は1バイト、y座標は2バイトとなっています。

各座標は、HVIF形式用に設計された特別な数値形式でエンコードされています。これによって、-32から+95までの整数値は1バイトで、-128から+192までの整数値は2バイトで表現されます。非整数値は全て2バイトで表現され、-128から+192までの範囲に含まれます。座標の最初のバイトの第1ビットは、その座標が1バイトなら0、2バイトなら1となります。1バイトの座標の値を得るには、そのバイトをuint8と解釈してから、32を引きます。2バイトの座標の値を得るには、第1ビットを0にセットし、その2バイトをuint16と解釈し、その結果を102で割ってから、128を引きます。

下記は1座標を読み取るコードです。

// read_coord
bool
read_coord(LittleEndianBuffer& buffer, float& coord)
{
    uint8 value;
    if (!buffer.Read(value))
        return false;

    if (value & 128) {
        // high bit set, the next byte is part of the coord
        uint8 lowValue;
        if (!buffer.Read(lowValue))
            return false;
        value &= 127;
        uint16 coordValue = (value << 8) | lowValue;
        coord = (float)coordValue / 102.0 - 128.0;
    } else {
        // simple coord
        coord = (float)value - 32.0;
    }
    return true;
}

1バイトの整数と2バイトの整数の範囲についてはドキュメントに記載されていますが、上記のコードは、2バイトの座標を解釈する方法について唯一のよりどころとなるものでしょう。実装上、座標は全て32ビット浮動小数点数ですが、それはこの形式にとって不可欠なことではないと思います。

1バイトの座標の範囲について、私は当初混乱しました。なぜ、ゼロが中心でなく-32から+95のような範囲になるのか、と疑問だったのです。ここで思い出すべき重要なポイントは、核となる範囲が0~64だということです。つまり、座標は実際には元の64×64のキャンバス上にあるので、その範囲の中心は座標系の中心として当然のものなのです。1バイトでは7ビットが使えますので(8からフラグビットを引くため)、127の値を取ることができます。核となる範囲0~64の両側に32、31をそれぞれ加えると、-32から+95となります(ある範囲が一定ビット数のサイズになっているか確認する簡単な方法は、両端の値を足し合わせることです。つまり、+32 + +95 = 127のように確認できます)。

実はこの形式では、x座標やy座標を手作業でパースするのがかなり簡単です。私は一つ一つの数字を全て理解しようとしているわけではなく、それぞれの部分の意味を突き止めようとしているにすぎません。第1ビットは、この座標が1バイトか2バイトかを表します。バイナリエディタでは、これは8、9、A~Fの1文字のいずれかで始まる2文字となります。よって座標を読む時には、それが1バイトか2バイトかをすぐに認識して先へ進むことができます。全ての数字の意味を突き止めようとしないのは、それに興味がなく、私にとって役にも立たないことだからです。

12の点は以下のようになっています。

点番号 x1 x2 y1 y2
1 2b b3 da
2 2b b5 72
3 30 b5 72
4 30 b3 da
5 31 b3 da
6 31 b7 70
7 30 b7 70
8 30 b5 d8
9 2b b5 d8
10 2b b7 70
11 2a b7 70
12 2a b3 da

バイトを10進数に変換しなくても、線セグメントの多くが垂直線か水平線であることは明らかです。HVIFには水平線セグメントや垂直線セグメントを格納するための特別なスペース節約方法があるにもかかわらず、Icon-O-Maticがパスをこの方法で格納するようになっている理由はよく分かりません。その特別な線セグメントは、基本的な線セグメントに対する2座標ではなく、1座標のみとして格納されます。

水平線セグメントのタイプと垂直線セグメントのタイプを使うには、パスのタイプを変更する必要があります。線のみのパスと曲線のみのパスは、一度に全体のセグメントを持ちますが、コマンドパスでは、パスの各セグメントが異なるタイプを持てるようになっています。セグメントのタイプとしては、線、3次曲線、水平線、垂直線の4種類がサポートされています。パスの最初の方、つまり点の数と最初の点の間にあるコマンドバイトは、そのパスの各セグメントに対する2ビットのタグを含んでいます。12点のパスなら、3つのコマンドバイトが必要となるでしょう。1点につき2ビット×12点÷1バイトにつき8ビット=3バイトという計算です。

線のみの単純なパスでは、点を表現するには、(12点×1点につき3バイト=)36バイトが必要です。コマンドパスなら、セグメントのタイプを表現するのに3バイトが必要ですが、点を表現するには6+7+7=20バイトしか必要ありません。

点番号 セグメントのタイプ x1 x2 y1 y2
1 2b b3 da
2 垂直線 b5 72
3 水平線 30
4 垂直線 b3 da
5 水平線 31
6 垂直線 b7 70
7 水平線 30
8 垂直線 b5 d8
9 水平線 2b
10 垂直線 b7 70
11 水平線 2a
12 垂直線 b3 da
合計使用バイト数 6 0 7 7

異なるパスのタイプを使えば、(36-23=)13バイトを節約できるのです。大きな違いではありませんが、スペース節約用に設計されたファイル形式としてはもっともな実装でしょう。コマンドパスがファイル内で表現される方法を自分がきちんと理解できているか確かめるため、この1つのパスの表現だけを変更するよう、ファイルを編集したいと思います。なお、編集作業に入る前に、もう1つ把握しておくべきことがあります。コマンドバイトの形式です。

コマンドバイトの構文解析コードを見たところ、コマンドはバイト内で右から左へと読み取られるようです。

ビットの各ペアは、セグメントのタイプと照合されます。

PATH_COMMAND_H_LINE = 0,
PATH_COMMAND_V_LINE = 1,
PATH_COMMAND_LINE   = 2,
PATH_COMMAND_CURVE  = 3,

よってコマンドバイトは、(バイト内のビットは右から左へと読み取られますが)バイトが左から右へと読み取られると仮定すると、0100 01100100 01000100 0100、つまり16進数で46 44 44となるでしょう。

また、フラグバイトを0a(曲線なし、クローズド)から06(コマンド、クローズド)に変更する必要もあります。私は0e(曲線なし、コマンド、クローズド)にセットしたかったのですが、構文解析コードのif文の順序が原因でうまくいかないのです。

if (pathFlags & PATH_FLAG_NO_CURVES) {
    if (!read_path_no_curves(buffer, path, pointCount))
        error = true;
} else if (pathFlags & PATH_FLAG_USES_COMMANDS) {
    if (!read_path_with_commands(buffer, path, pointCount))
        error = true;
} else {
    if (!read_path_curves(buffer, path, pointCount))
        error = true;
}

下記はHのパスに対するコードです。

0a 0c 2b b3 da 2b b5 72 30 b5 72 30 b3 da 31 b3
da 31 b7 70 30 b7 70 30 b5 d8 2b b5 d8 2b b7 70
2a b7 70 2a b3 da

それが以下のように変わりました。

06 0c 46 44 44 2b b3 da b5 72 30 b3 da 31 b7 70
30 b5 d8 2b b7 70 2a b3 da

同じパス(つまり一続きの線セグメントに対する同じ端点)を論理的に表現できただけでなく、このパスが変更されたファイルは、元のアイコンと見た目もそっくりになります。このパスを格納するのにもっとスペースを要する方法を使うと、Icon-O-Maticではバグ(このケースでは重大でないバグ)が発生するようです。Icon-O-Maticは(Haikuの他の部分と同様)オープンソースなので、そのバグはおそらく自分で修正できそうなのですが、本記事の趣旨である画像形式の理解の話に戻りたいと思います。

コマンドパスを見てきましたので、2番目のパスは理解しやすいでしょう。2番目のパスはコマンドパスで、唯一新しい特徴となっているのは曲線です。HVIFにおける曲線は全て3次曲線で、各曲線は3つの点(x, y)で定義されます。それらは構文解析コードでx、y、x_in、y_in、x_out、y_outと表されます。この6つの値は、今挙げた順番で記述されます。

2番目のパスは以下の部分です。

06 08 de 6e 40 24 28 28 b8 18 b3 6d b4 47 b8 f2
40 2c 54 b5 79 c6 39 ba 16 c9 36 3c 58 50 54 4c
54 c7 3d 54 58 40 24

最初のバイト(06、つまり0000 0110)はフラグで、コマンドを用いたクローズドパスです。今回は、「曲線なし」フラグはゼロが正しい値です。このパスには曲線があるからです。2番目のバイト(08)は点の数ですので、このパスには8つの点があるということです。このパスが、点の数は前のパスの60%しかないのにより多くのバイトを取っている理由は、曲線を表現するには多くのバイト(6)を使うからです。「6バイトは多い」と言う時が来るとは考えてもいませんでした。

コマンドバイトはde 6eで、セグメントはdeのコマンド(1101 1110)、6eのコマンド(0110 1110)の順に照合されます。各バイト内のコマンドは右から左へと読み取られます。その結果、コマンドは以下のようになります。

ビット 10進法 意味
10 2
11 3 曲線
01 1 垂直線
11 3 曲線
10 2
11 3 曲線
10 2
01 1 垂直線

最初のパスを編集した時に、コマンドバイトの解釈は確認できています。このことが重要な理由は、コマンドの順序が誤りでタイプが正しい場合、ファイルは問題なさそうに見えてもレンダリング結果は異なったものになるからです。各セグメントのタイプに対する座標の数はセットされますが、誤った順序でパースされたら、座標のグループ分けは異なったものになるでしょう。

このコマンドのリストを使うと、パスを以下のように解釈できます。

タイプ X Y Xin Yin Xout Yout
40 24
曲線 28 28 b8 18 b3 6d b4 47 b8 f2
垂直線 <28> 40
曲線 2c 54 b5 79 c6 39 ba 16 c9 36
3c 58
曲線 50 54 4c 54 c7 3d 54
58 40
垂直線 <58> 24

表中の<28><58>は、垂直線セグメントに対する暗黙の値です。垂直線では、xの値が前の点と同じになるためです。このパスは、線セグメントのタイプをできるだけ多くしようと私が手描きしたので、タイプが妙に混ざっています。最後のパスは水平線です。シェイプがクローズドというのは、最後の点(58, 24)が最初の点(40, 24)に線セグメントでつながっていることを意味するからです。私はそのセグメントを意図的に水平線にしたのですが、ファイル内の水平線セグメントとして出現しないことは分かっていませんでした。

シェイプ

シェイプのセクションは、レンダラーが実際に何を描画するかを示します。それぞれのシェイプには、1つのスタイルと1つ以上のパスがあります。パス内部(またはパス間)のスペースは、スタイルで満たされることになります。シェイプは後ろから前へと配置されますので、最初にパースするシェイプは、画像の中で最も後ろにあるレイヤになります。したがって、今分析しているロゴでは、ブロブのシェイプが1番目、Hのシェイプが2番目になります。

シェイプのセクションは、シェイプの数から始まります。2つのシェイプがありますので02です。次からすぐ、1番目のシェイプが始まります。それに対するバイトは0a 01 01 01 00と、パスに比べてかなり少なくなっています。

シェイプのタイプは1つしかありませんので、このファイルにあるどちらのシェイプも、SHAPE_TYPE_PATH_SOURCE(別のenum)に対するシェイプのタイプ0aから始まっています。この意味はよく分かりませんが、シェイプのタイプは1つしかないので、ほとんど意味はありません。シェイプの次のバイトはスタイルのインデックスです。01とあるのは、このシェイプがこのファイルの2番目のスタイル(インデックスはゼロから始まるため)を使っていることを表します。ここでは、赤から青へのグラデーションです。次の2バイト(01 01)は、パスの数とパスのインデックスです。このブロブのシェイプはパスが1つで、ファイル中の2番目のシェイプとなっています。最後のバイト(00)はシェイプのフラグです。何もセットされていないので、フラグの意味については次のシェイプで見てみましょう。ただ言えるのは、何らかのフラグがセットされていれば、このシェイプに対してさらに読み取るべきものがあるということです。

シェイプはスタイル(とパス)を1バイトで表すので、1つのアイコンやファイルにおけるスタイルとパスはそれぞれ、最大で256種類ということになります(256は8ビット内で区別できる値の最大数)。おそらくアイコン向けには十分な数でしょうが、複雑なベクターグラフィックス向けの数としては必ずしも十分というわけではありません。特にアイコンを対象にして、このように複雑さを制限することで、HVIFでは生成されるファイルのサイズを抑えられるようになっているのです。

2番目のシェイプの方が、0a 00 01 00 02 44 00 00 00 00 00 00 00 00 44 47 1c c9 00 00 be 6a aaと多くのバイトを占めています。最初のセクションは1番目のシェイプとよく似ています。唯一有効なシェイプのタイプ0a、1番目のスタイル(フラットな白)、1つのパス、1番目のシェイプ(H)という意味です。以上が最初の4バイトですので、シェイプのフラグバイトは02であることが分かります。フラグバイトにおける各ビットは、シェイプが持つことのできる様々な追加的特徴を表します。

SHAPE_FLAG_TRANSFORM            = 1 << 1,
SHAPE_FLAG_HINTING          = 1 << 2,
SHAPE_FLAG_LOD_SCALE            = 1 << 3,
SHAPE_FLAG_HAS_TRANSFORMERS     = 1 << 4,
SHAPE_FLAG_TRANSLATION          = 1 << 5,

本記事はHVIF形式についての詳細なマニュアルではありませんので、1つの例にだけ触れておきましょう。他のフラグの説明は省略します。02でセットされるフラグはSHAPE_FLAG_TRANSFORMです。これは、パスの伸縮、移動、傾斜、回転に使われる、6つの値の行列があるという意味です。確信はありませんが、このフラグとSHAPE_FLAG_HAS_TRANSFORMERSの違いは、このフラグは「変換行列が1つしかない」ことを意味するという点だと思います。

このシェイプで残るのは、6つの数値です。この行列中の数値は、HVIF向けに作られた形式による24ビット浮動小数点数です。アイコンには、32ビット浮動小数点数の精度は必要がないので、より小さな形式を使うことで大きなスペースの節約につながるのです。しかし、なぜ(より標準的な形式の)16ビット浮動小数点数ではなく24ビット浮動小数点数が採用されたのかは分かりません。ともかく、6つの数値は以下のとおりです。

バイト1 バイト2 バイト3
1 44 00 00
2 00 00 00
3 00 00 00
4 44 47 1c
5 c9 00 00
6 be 6a aa

これは、この形式の中で可変長でない限られた部分の1つです。したがって、シェイプのフラグが02であると読み取ったらすぐに、次の(1浮動小数点数につき3バイト×6浮動小数点数=)18バイトは変換行列であると分かるでしょう。

1つのフラグビットしかセットされていなかったので、このシェイプはこれで終わりです。この行列は、Hのパスを拡大して、画像の中央に移動します。このHはテキストをIcon-O-Maticにコピー&ペーストしたものですが、最初の形状が自分の好みより小さかったため、拡大したのです。

まとめ

私はHaikuをいじるのが好きです。LinuxよりマイナーなOSをいくつか試した中では、Haikuが最も安定していて有用です。また、Linuxと大きく異なるので、面白い見方をすることもできます。今回のベクターアイコン形式は、そのほんの一例です。

私がこのベクター形式に興味を持っている理由は、バイナリ形式であり(それまでバイナリファイルをパースしたことがなかった)、ベクター画像形式であり(それまでベクター画像形式を詳しく見たことがなかった)、色々な最適化に明確な制約があり(設計の決め手を推測しやすい)、概ね独りで作れたからです(つまり自分でも理解できる難易度のはず)。手作業でパースを行った結果、16進数と2進数を相互に変換してバイトをビットの集まりと見る作業がずいぶん楽にできるようになりました。また、ファイルを編集してコマンドバイトの仕組みを調べたことで、大変自信がつきました。バイナリエディタを使って手作業でファイルを編集しましたが、それでもうまくいったのです! そんなことは、低水準プログラミングの達人にしかできないだろうと思っていました。

オープンソースのパーサーでバイナリファイル形式を詳しく研究してみることはお勧めです。16進数を解釈する時に具体的なソースコードで見ていく作業は、非常に貴重な経験となりました。例となるコードがなければ、解釈するのがずっと難しかったことでしょう。HVIFの特徴を読み取って知り、その実際の仕組みを興味のままに調べることができて大変満足しましたし、その過程で新しいスキルを得ることができました(たとえHVIFに詳しいということが役に立つ場面は非常に限られているとしても)。

謝辞

本稿にコメントをくれると共に「ディスクからの読み出しがどれほど遅いか?」の計算に協力してくれたDan Luu、ぎこちない表現や多くのスペルミスを見つけてくれたDavid Turner、もっと多くの記事を書きたくなるような建設的なコメントをくれたBert Muthalaly、そして紛らわしい部分を指摘してくれたJulia Evansに感謝します。誤植を見つけてくれた@davecporterに感謝します。:)