何の話？

　Sixel Graphics の ormode についての話です。
　以前から忘れないうちに書いておこうと思いつつずっと手をつけられないでいましたが、果てしなく続く NetBSD on xm6i での mlterm のビルドを眺めている間に急にやる気が湧いてきたので、まとめてみます。

Sixel Graphics の ormode とは

　NetBSD/x68k 及び twitter クライントの sayaka においてサポートされている Sixel Graphics の独自拡張です。
　NetBSD/x68k では、以下のパッチを当てることで、カーネルレベルで Sixel Graphics に対応し、コンソール上で画像表示が可能となるのですが、NetBSD/x68k での Sixel Graphics の表示を更に高速化するため、2016年に ormode という独自拡張が考案されました。

・NetBSD/x68k パッチ: https://github.com/isaki68k/misc/blob/master/NetBSD/patch/x68k-ite-sixel.diff
・sayaka: https://github.com/isaki68k/sayaka/ (2020/1/5リリースの3.4.0でフィルタストリームによる擬似ホームタイムラインに対応！)

　Sixel Graphics に初めて対応した VT240 が登場したのが1984年、NetBSD/x68k が動作する X68030 が登場したのが1993年ですが、この2つが数十年の時を経て融合し、新たな方法が生み出されたわけです。
　ormode については、今のところ NetBSD/x68k 以外では使われておらず、ドキュメントもほとんどないのですが、x68k に限らず古いマシンで Sixel Graphics を使う場合に、効果的な方法だと思いますので、簡単にその内容をまとめてみたいと思います。

前提となる知識

　Sixel Graphics について、頭に入れておく必要がある事項は、次の3点です。
　(詳細は http://www.vt100.net/docs/vt3xx-gp/chapter14.html や https://github.com/fumiyas/translation-ja/blob/master/vt3xx-sixel.md を参照ください。)

(1) 縦6×横1ピクセルごとに，どのピクセルに色を塗るかを1バイトの文字で表現します。

(2) 最大256色のパレットから'#パレット番号'により指定した1色について，(1)の文字を使って色を塗ります(パレットの色は，パレット番号に続けて';2;R;G;B'のようにすることで定義できます。)。
(3) 縦6ピクセル×画像幅を1行として色を塗っていきますが，縦6×横1ピクセルに(1)の文字を使って1色分塗ると，まだ塗れていないピクセルがあっても次の縦6×横1ピクセルに移動します。'$'で行の最初に戻り，'-'で次の行に移ることができます。

　また、x68kのような古のマシンで色を扱う場合、機種により様々な違いはあるものの、単に色数が少ないというだけでなく、次の点に注意する必要があります。
(a) 使いたい色をパレットに設定し、パレット番号(通常1ビット(2色)～8ビット(256色))を VRAM に書き込むことで表示する。
(b) VRAM への書き込みについては、多くの場合、次表(16色の場合)のように、パレット番号を1ビットずつ分割し、それぞれ別々のプレーン(VRAM 領域)に書き込む必要がある。

　このうち (a) は上記 (2) と同じことですが、(b) の VRAM への書き込み方法についても Sixel Graphics に応用できないか考えてみます。

ormode の基本的な考え方

　6×3=18ピクセルで16色の次のような画像を考えてみます。

　まず、パレットを次のとおり定義します。

　このパレットに基づき、各ピクセルの色を Sixel Graphics に変換すると次のようなシーケンスになります。

　色塗りの順番を工夫することで、行頭に戻る回数は5回に留めることができますが、縦方向に最大6ピクセルをまとめて色塗りできるにもかかわらず、縦方向に同じ色がないため、6x3ピクセルの色を塗るのに61バイトもかかっています。

　ここで、上記 (b) の方法を応用し、各ピクセルの色ではなく、各ピクセルの色(パレット番号)を1ビットずつプレーンに分け、プレーンごとのビットの並びを上記 (1) の方法で Sixel Graphics に変換するとどうなるでしょうか。

　プレーンの数は、色数に対し logN(N=色数) となるため、行頭に戻って塗り直す回数を更に減らせますし、プレーンごとのビットの並びは、縦6ピクセル分の0か1のパターンを上記 (1) の1バイトの文字に変換することになり、データを無駄なく埋め込むことができます。

　上記の画像の色を4つのプレーンに分け、Sixel Graphics に変換すると、次のとおりたった23バイトになります。

　これが ormode の基本的な考え方です。
　(ちなみに、上図の plane0～plane3 の色を示す(#で始まる)数字は、2を0～3乗したものです。上図では、各プレーンごとのピクセルにその数字を記載していますが、各プレーンの同じ位置にあるピクセルの数字を OR すると、左側の元画像のパレット番号になります。確かに "or"mode ですね。)。

　この方法は、縦6ピクセル×画像幅の中であまり多くの色が使われていない(logN 色未満の)画像などでは、あまり効果がありませんが、通常、少ない色しか使えない環境では、ディザリングを行い、できるだけ多くの色を組み合わせて表現力を上げることが多いと考えられるため、多くのケースで一定の効果が期待できそうです。
　(なお、https://qiita.com/arakiken/items/4a216af6547d2574d283 の 3(2) で書いた重ね塗りによる最適化手法 (img2sixel -E size) は、ormode と相容れないため、どちらか一方しか適用することはできません。)

　また、Sixel Graphics は、改行('-')がくるまで、VRAM に書き込む縦6ピクセル×画像幅分の色が確定しませんが、ormode であれば、プレーンごとに、縦6ピクセル×画像幅分のビットの並びを一気に受け取ります。
　このため、VRAM に上記 (b) の方法で書き込む必要があるマシンの場合、パレット番号を各プレーンに分割する処理を行わず、受け止ったビット列をそのまますぐに VRAM に書き込むことも可能です(ただし、NetBSD/x68k のコンソールや、後述する ormode 対応の mlterm は、今のところそこまではしていません。)。

　従来の Sixel Graphics との互換性は失われるものの、色をプレーンに変えただけですので、ormode に対応していないターミナルに ormode のシーケンスを流した場合、色はおかしくなりますが、画像のサイズは正しく表示され、画面の乱れを最小限に抑えられます。

　(上：ormode に対応していない mlterm 上で ormode のシーケンスを流した場合
　下：通常の Sixel Graphics のシーケンスを流した場合)

　ormode は、X68030 単体で Twitter ユーザストリームしようという無謀(?)ともいえる取組において、https://twitter.com/isaki68k さんや https://twitter.com/moveccr さんが画像表示の高速化の一つとして考案されたものです。

　詳しくは、OSC2016広島で発表された資料を参照ください。
　http://www.pastel-flower.jp/~isaki/NetBSD/osc16hi/
※ ormode の関係はここ→ http://www.pastel-flower.jp/~isaki/NetBSD/osc16hi/page40.html
　「6ピクセル分の展開を乗算1回で行う」というのも参考になります(多分これ→https://github.com/isaki68k/misc/blob/a5eb89a/NetBSD/patch/x68k-ite-sixel.diff#L313)
※ ormode とは直接関係ありませんが、上記の前編となる OSC2015 広島の発表資料はここ→ http://www.pastel-flower.jp/~isaki/NetBSD/osc15hi/

ormode の仕様

　まず、通常の Sixel Grgaphics でなく ormode な Sixel Graphics だと分かるよう、ヘッダの仕様を拡張する必要があります。
　Sixel Grgaphics のシーケンスは次のように定められています。
　(詳しくは https://github.com/fumiyas/translation-ja/blob/master/vt3xx-sixel.md#%E3%83%87%E3%83%90%E3%82%A4%E3%82%B9%E5%88%B6%E5%BE%A1%E6%96%87%E5%AD%97%E5%88%97 を参照してください。)

　DCS P1;P2;P3;q s..s ST

　ormode かどうかを示すフラグを追加するため、P1、P2、P3 の3つのパラメータのどれかを拡張する必要がありますが、P1 はピクセルのアスペクト比、P3 は水平グリッドサイズを示すパラメータであり、ormode にはあまり馴染みません。
　そこで、背景色の描画方式を選択する P2 を拡張し、5 の場合に ormode であると定義しています。

　P2 が 5 の場合、上記の (2) について、'#パレット番号'は、'#2^プレーン番号'(2の「プレーン番号」乗)となり、それに、各プレーンのビット列が、縦6ビット分を上記 (1) の方法で1バイトの文字に変換されて続きます。
　(上記 (2) の括弧内に記載しているパレットの色の定義方法については、ormode でも変わりません。)

　通常の Sixel Graphics との違いはこの2点だけです。

　なお、プレーンは最大8個(256色)あるので、2^プレーン番号は、
　1 (=2^0)
　2 (=2^1)
　4 (=2^2)
　8 (=2^3)
　16(=2^4)
　32(=2^5)
　64(=2^6)
　128(=2^7)
の最大8種類となります。

　また、ormode な Sixel Graphics を受け取った側では、下図のとおり、各プレーンの
　0か1のビット列 × 2^プレーン番号(＝下図の各ピクセルに記載の数値)
を OR することにより、各ピクセルの色を示すパレット番号が分かります。

　つまり、通常の Sixel Graphics のパレット番号であれ、ormode の2^プレーン番号であれ、Sixel Graphics をパースして各ピクセルの色を保存する際に、

pixels[y * width + x] |= sixel_color

のように OR で保存するようにしておけば、通常の Sixel Graphics 用と ormode 用の2種類のコードを書く必要はなく、1つのコードで両方処理することも可能です(ただし、https://qiita.com/arakiken/items/4a216af6547d2574d283 の 3(2) のような重ね塗りには対応できなくなります。)。
　(参考: https://github.com/isaki68k/misc/blob/a5eb89a/NetBSD/patch/x68k-ite-sixel.diff#L314)

ormode の使い方

　ormode な Sixel Grgaphics は、sayaka に --ormode 又は --x68k オプションを付けることで出力されます。
　また、ormode な Sixel Grgaphics を解釈できるのは、上記のパッチを当てた NetBSD/x68k カーネルのコンソールだけでした。

　NetBSD/x68k 以外の環境でももっと手軽に扱えるよう、libsixel (img2sixel) に、ormode な Sixel Graphics を出力する-O オプションを追加してみました(上述のとおり -E size オプションとは両立できないため、-O オプションを指定すると、-E size オプションは無視されます。)。
　https://github.com/arakiken/libsixel/archive/ormode.zip

$ img2sixel -O -p 16 images/snake.png > snake-16.six
$ img2sixel -p 16 images/snake.png > snake-16-ormode.six
を比べると、snake-16.six 118452bytes に対し、snake-16-ormode.six 97955bytes と、20% 近く縮減できています。

$ img2sixel -O -p 256 images/snake.png > snake-256.six
$ img2sixel -p 256 images/snake.png > snake-256-ormode.six
では、snake-256.six 349789bytes に対し、snake-16-ormode.six 267789bytes と、25% 近く縮減できています。

　併せて、mlterm も、3.9.0 以降において、デフォルトで ormode に対応する予定です。
　https://github.com/arakiken/mlterm/commit/8be829dcf6dfe33d19181a7e9921af92617035bc#diff-027fc59f4d4bf7d82b78fd7a72dd3d05L22

おわりに

　そもそも、古いマシンのコンソールで画像を表示する場合に、あまり効率のよくない Sixel Graphics というフォーマットは適さないようにも思いますが、ormode は、こうした環境であえて Sixel Graphics を使うという選択をしてくれたからこそ生まれたものであり、このまま NetBSD/x68k の中だけで眠らせてしまうのはもったいないなあと思っていました。
　ormode は、既存の仕様ともある程度互換性がありますし、もし、libsixel に正式対応いただけ(るかどうか分かりませんが)れば、利用する敷居も大きく下がります。将来的に、ormode に対応した端末エミュレータが増える可能性もあると思います。
　往年の名機 X68030 から生まれたアイデアとして、ormode が広まることを期待してやみません。