本物の形式

gzip を round-trip できれば圧縮が動くことは証明できるが、gzip は配管だ —— 圧縮ストリームを保持する だけが仕事の容れ物。より面白い問いは、同じ中核が人々の実際に使う形式に —— DEFLATE が要点でなく 部品である形式に —— 仕えられるかだ。PNG がその形式だ。その画像データは zlib で包まれた DEFLATE なので、前二回の圧縮器と解凍器がそのまま嵌まる。PNG probe が測るのはそれ以外のすべて、圧縮の周りに 組まれた形式であり、言語の手がそれを持つのにすでに十分足りていたかだ。

初めての big-endian

gzip は長さもチェックサムも little-endian、下位バイトから格納し、これまでのすべてのバイト組み立て ルーチンはそう書かれていた。PNG は big-endian だ。chunk の長さ、ヘッダの寸法、各 chunk 末尾の CRC が すべて最上位バイトから届く。これは小さくて、そして本物のことだ —— コードが複数バイトの整数を逆順で 読み書きせねばならなかった最初の箇所 —— そして浮かび上がったのは、バイトを逆の並びで書く必要だけ だった。chunk 構造そのもの、長さに続いて 4 文字の型、続いてデータ、続いて型とデータにかかる CRC-32 は、 仕様からバイト vector 上の入れ子ループへ直に転写できる。

別のコンテナ、別のチェックサム

画像 chunk の中では、画素データは生の DEFLATE でなく zlib で包まれた DEFLATE だ。2 バイトのヘッダ、 圧縮ストリーム、そして Adler-32 チェックサム —— gzip も PNG の chunk 枠組みも使う CRC-32 とは別の アルゴリズムだ。復号は DEFLATE ペイロードを読むだけでいいので decoder はその検証を省けるが、encoder は 省けない。正しい Adler-32 を欠いた PNG は拒否される。Adler-32 の実装 —— 素数を法とする二つの走る和、 一つはバイトの、一つは最初の和の —— は数行だったが、この一つの形式がいくつの別々のチェックサムを 要求したかは記す価値がある。コンテナでは chunk ごとの CRC-32、zlib 層では非圧縮画素にかかる Adler-32。 本物の形式は小さな取り決めの積み重ねで、それぞれが独自の算術を持つ。

scanline filter は二次元のバイト算術

gzip に対応物のない部分が filter だ。圧縮の前に、各画素行は予測子で変換される —— すでに見た隣接、 左の画素、上の行の画素、左上の画素から作った推定を差し引き、生の色値よりはるかによく圧縮される小さな 残差を残す。そうした filter は五つあり、本物の encoder は行ごとに選ぶ。decoder は選ばれたどれであれ それを反転し、各 scanline の先頭の filter バイトを読み、予測を画素ごとに戻さねばならない。これはアーク 全体で初の本当に二次元のバイト計算だ —— 各出力バイトはその上と左のバイトに依存する —— そしてまさに、 微妙に間違えやすい index の多いループだ。検証は、参照ライブラリが書いた PNG を、その適応的な行ごとの filter 選択ごと復号し、画素を既知のチェックサムと照合することだった。一致した。

両方向が閉じた。decoder は filter を五種すべて巡回させた自作 RGB 画像、自作 RGBA 画像、参照ライブラリが 適応 filter で符号化した画像を読み —— すべて一致する画素チェックサムへ、interp でも C backend でも。 encoder は、自作 decoder・参照ライブラリ・元データがすべて一致し、OS が有効な PNG と認識する グラデーションを書いた。このどれも言語への変更を要さなかった。圧縮の中核は変わらず持ち越され、 big-endian バイト、二つ目のチェックサム、二次元予測がすべてすでにあるものの中に嵌まった。gzip アークは 本物の形式に届いた。encode も decode も純 Mere で、みなが使うツールとバイト互換で。