解凍器を書く
bytes の物語は断片で出荷されてきた —— bitwise 演算子、hex リテラル、binary-safe なファイル reader と writer —— が、それらを本物のフォーマットで協働させるものは無かった。gzip 解凍器がそれをやった: int vector 上の bit reader、stored/fixed/dynamic を一本で捌く canonical Huffman デコーダ、以前の example から再利用した CRC-32 検査。system gzip が作ったファイルを byte 単位で展開する。この dogfood が書けたのは前提が全部先に着地していたからで、そして元は二重に取ることになる。
近頃のいくつかの話は、bytes 処理の物語の部品を、組み立てないまま足してきた: ALU 用の bitwise 演算子、マスクが仕様どおりに読めるための hex リテラル、binary-safe なファイル reader とその 書き手の双子。各々が小さな probe に強制され、各々が単独では動いた。この Part は、それらを協働 させたプログラム —— 本物の gzip 解凍器 —— であり、dogfood の常として、出かけた用事より多くを 持って帰ってきた。
3 つの block type を一本のデコーダで
gzip の中身のアルゴリズム DEFLATE は大きくないが容赦がない: 1 ビットずれれば全ストリームが ノイズになり、部分点は無い。解凍器は、バイト境界を越えて最下位ビットから引く bit reader を要する —— ここでは 3 スロットの状態 vector（位置・ビットバッファ・ビット数）を入力の int vector 上に 築いた。その上に、自慢に値する部分が乗る: DEFLATE の 3 つの block type 全てを捌く単一の canonical Huffman デコーダだ。stored ブロックは生バイト。fixed-Huffman ブロックは組み込みの コード表。dynamic ブロックは自分のコード長を、さらに別の Huffman コードで圧縮して運ぶ。これを 3 本でなく 1 本のデコーダに保つ洞察は、fixed の表は「特定の」コード長集合にすぎないという こと —— だから「長さ配列からデコーダを組む」「1 シンボルを decode する」という同じ関数が fixed も dynamic も同一に捌き、stored は長さ前置きの run をコピーする短い特例だ。全体は周りの gzip コンテナも読み（任意の name / comment / extra フィールドを飛ばし）、trailer の CRC-32 —— 2 つ前の probe のチェックサム example からそのまま再利用 —— を展開後の出力に対して検証する。
なぜ今書けたか、そして何を炙り出したか
立ち止まる価値があるのは、このプログラムが一週間前には書けなかったことだ。bit reader は bitwise
シフトとマスクを要する。範囲表が hex で読めるのは hex リテラルがあるから。入力が
read_file_bytes 経由で来るのは、NUL 終端の文字列なら圧縮データを最初のゼロバイトで truncate
するからで、出力は write_file_bytes で出ていく。それぞれが自分の話を持つ別々の probe だった。
解凍器は、それらがついに協働して system の gzip/gunzip と握手する何かになる場所だ。それらの
出力 —— 1 バイトのファイル、1 メガバイトのファイル、stored も fixed も dynamic も —— を毎回
byte 単位で同一に展開する。
そしてそれから、dogfood がやることをやった。密にネストし、深く再帰し、capture の多い 300 行を 書くことは、どのテストよりも遥かにコンパイラの closure 機構を酷使し、まず 3 つの異なるコード 生成バグを炙り出した —— どれも、コンパイラが emit した C を C コンパイラに渡して初めて現れる エラーで、interpreter は一度も踏んでいなかった。それが次の話だ。その次の話は、解凍器が印字した、 あり得ないはずの数についてだ: 1 メガバイトを展開するのに 484 メガバイト。