GIF Format入出力に関する覚書。特にLZW部分

GIFフォーマットを入出力しようとして、LZWあたりで悩んだ人（自分）のための覚書。

■GIFフォーマット

まず、GIFフォーマットに関してはざっくり以下のページで理解できるが、LZW部分はあまり紹介されていない。

資料１）GIFフォーマットの解説（日本語）
http://www.tohoho-web.com/wwwgif.htm

資料２）GIFフォーマットの解説（日本語）
http://www.mars.dti.ne.jp/~torao/program/appendix/gif.html

■LZWの基本

LZWの基本をまず把握しておいた方がよい。但し、以下のページだけではGIF書き出しのための情報としては不足。

資料３）LZWの説明（日本語）
http://www2.starcat.ne.jp/~fussy/algo/algo8-5.htm

資料４）wikipediaでLZWをざっくり説明（英語）
http://en.wikipedia.org/wiki/LZW

■GIF用LZWの詳細

で、GIFのフォーマットと、LZWの基本が理解できたら、以下の仕様書らしき物を読むと一応必要な情報が得られる。

資料５）GIF89aの仕様書（英語）
http://www.martinreddy.net/gfx/2d/GIF89a.txt

資料６）GIFのLZWの詳細（英語）
http://www.martinreddy.net/gfx/2d/GIF-comp.txt

■サンプルデータの用意

GIFのサンプルデータを書き出してバイナリエディタでチェックすると徐々になぞが解けてくる。
Photoshop等で、非常に小さなGIFデータを何パターンか書き出し、バイナリエディタで確認、比較するとよいかと。

■引っかかりやすい点（悩んだ点）

※勉強段階で書いているので、勘違いが含まれているかも知れません！！！！

・LZWの辞書は保存しないですむ。データから辞書を生成し、生成したものを参照していく。読み込む（書き出す）につれて、辞書がドンドン膨らんでいく。

・色数に応じて、最初にLZWの辞書を初期化するが、さらに「Clear Code(CC)」と、「End of infomation code(EOI)」 が辞書にあらかじめ登録される！！
・CC,EOIが辞書に入るため、色数が N bit/pixel のとき、最初の出力コードのビット数は N+1。CCは辞書の(2**N)番、EOIは(2**N+1)番に登録される。
・読み込み（書き出し）過程で辞書に追加していくとき、 (2**N+2)番からとなる。
・LZWの出力コードのビット数は辞書の中身が増えるにつれて増えていく。
※つまり、同じ辞書の番号をあらわす場合でも、表現するビット数が変わっていく。辞書の1番目なら 001 >> 0001 >> 00001のようになっていく(例は最初に3bitの場合)

・X bit/pixel のとき、N=Xだが、1 bit/pixel のときは、N=2とする　＜自信なし

・書き出されていくビットの並びは、一見ややこしい。１バイト単位で、右詰め（左詰めじゃない）。資料５のｐ.３３あたりをジックリ読むと見えてくる。

・読み込み時にCC（Clear Code）に遭遇したときは、辞書を初期化しなおす。このあたりは資料６のｐ.４あたり。
・逆に書き込み時に辞書番号が4095(16進でFFF)に到達した場合には、CCの番号を書き出して、辞書をクリアする。最大で12bitしか使わない
・書き出しの最初にもCCを書き出す！

・データの終わりに来たときは、残った文字をあらわす辞書番号を書き出し、その後にEOIの番号を書き出す。ビットがあまったら０でよい。＜＜自信なし