GIF

符号化の手順

1. パレット色を番号に
2. インターレース行の順を変える（選んだときだけ）
3. LZW番号の並びを可変長の符号に
4. サブブロック255 バイトずつに分ける

LZW

同じ並びを辞書の番号に置き換えます[1][2]。辞書そのものはファイルに入れず、符号を読みながら復号器が同じ辞書を作ります。

• 始まり: 最小符号サイズを $m$ として、0〜$2^m-1$ が 1 画素の符号、$2^m$ が Clear、その次が EOI、足す項目はその次の番号から
• 符号化: 辞書にある最長の列の符号を出し、「その列 + 次の画素」を足す
• 復号: 符号の列を出し、「前の列 + いまの列の先頭」を足す。符号化より 1 つ遅れる
• KwKwK: 符号化器が足した直後の番号を使うと、復号器にはまだない番号が来る。この番号の列は「前の列 + 前の列の先頭」と決まる
• 符号長: $m+1$ ビットから始め、番号が今の長さに入らなくなると 1 増やす。上限は 12 ビット
• Clear: 辞書と符号長を初めに戻す。このツールは番号が 4096 に達したら出す
• ビットの順: 符号をバイトの下位ビットから詰める

パレット

カラーテーブルは 2〜256 色で、画素は色の番号です[1]。色の多い画像は median cut で減色します[3]。誤差拡散は置き換えた誤差を隣の画素へ配ります[4]。階調は滑らかになりますが、同じ並びが減るので LZW は効きにくくなります。

インターレース

行を 4 つのパスに分けて送ります[1]。途中まで届いた時点で全体の荒い絵を出せます。上下の行が離れるので LZW は効きにくくなることがあります。

出典

1. ファイルの構成・インターレース（付録 E）・LZW の可変長符号（付録 F）CompuServe, Graphics Interchange Format, Version 89a, 1990
2. LZWT. A. Welch, “A Technique for High-Performance Data Compression,” IEEE Computer, vol. 17, no. 6, pp. 8–19, 1984。米国特許 4,558,302
3. median cutP. Heckbert, “Color Image Quantization for Frame Buffer Display,” SIGGRAPH ’82, 1982
4. 誤差拡散R. W. Floyd, L. Steinberg, “An Adaptive Algorithm for Spatial Greyscale,” Proceedings of the SID, vol. 17, no. 2, pp. 75–77, 1976

このツールで決めたこと

• 見本は式と文字の図から描く。写真風は PNG のページの見本を半分に縮めたもの
• 減色は 5 ビットのヒストグラムから median cut で作る。透明な画素（不透明度 128 未満）は透過色の 1 色にまとめる
• GIF ファイルはそのまま読む。ほかの画像は長い辺を 512 画素までに縮めて符号化する
• 壊れたファイルは読めた所まで出す
• 辞書の木は新しい 200 項目とその祖先だけを描く
• 開くフレームは 4,194,304 画素まで