GIFデコード処理を作る際に、注意しなければいけないポイント
1. 終了コードに頼って、画像データの終わりを判断してはいけない
GIFデコード処理の中でメインとなるのは、LZW圧縮された符号化コードを読み込んで、ピクセルに展開して行く処理です。
僕は最初、下図のフローチャートのような方法で、処理を作成しました。
(※説明を簡単にするために、細かな点は、フローチャート内では省略してあります。)
この方法で、たいていのGIFファイルはデコードできるのですが、稀にデコードできないGIFファイルが発生してしまいました。
たとえば、11×6ピクセル・2色パレットで、画像全体をカラー0でベタ塗りしたGIFファイルをデコードしようとすると、「データ不足」の原因でデコードに失敗してしまいます。
正しいGIFファイルであるにもかかわらず、なぜ「データ不足」と判断してしまっているのか、調査するため、まず、GIFファイルの内容をHEXエディタでダンプしてみました。
上図の中で、緑色を付けた部分が、LZW圧縮された符号化コードを含む、画像データの部分です。
画像データの部分だけを抜き出して、説明を加えてみました。
各々の符号化コードは、数ビットづつの大きさで、びっちり詰め込まれています。
前述のフローチャートの方法で、各々の符号化コードを読み込んだときに、何が起きているかの説明を加えてみました。
LZW解凍アルゴリズムに従って、符号化コードを読み出すたびに辞書への登録を行い、次回に読み出す可能性のある符号化コードの最大値を、1ずつ増やしています。
符号化コード15を読み出した後も、次回に読み出す可能性のある符号化コードの最大値を、1増やして16としています。
16は4ビットでは表せないので、次回の読み込みビット長を5ビットに変更しています。
ところが、符号化コード15の後には、終了コードが4ビットの長さで格納されていて、それ以降には画像データが存在しません。
プログラムは、5ビット分の読み込みを行おうとしますが、4ビット分しか読み込めず、「データ不足」で失敗してしまうのです。
なぜ、終了コードが、5ビットの長さでなく、4ビットの長さで格納されているのでしょうか。
LZW圧縮アルゴリズムを再確認してみることにします。
時雨エノキオプトさんのGIFデコーダサンプルプログラム解説の中にある、「LZW圧縮アルゴリズム」の説明を使わせていただきました。
赤字の箇所は、僕が追記したテキストです。
1. 文字が1文字だけの語を全て登録した辞書を用意する．
最初の1文字を読込んでそれを変数wに入れる．
------ ループ開始 ------
2.1 1文字読込んで，変数kに入れる．
圧縮すべきデータがもう無い場合，3へ．
2.2 変数wの直後に変数kが続いている文字列を変数wkに入れる．すなわちwk=w+kとなる．
2.3 変数wkが辞書に登録されているかを調べる．
2.4 wkが登録されている場合：
2.1に戻る．
2.5 wkが登録されていない場合：
wkを辞書に登録する．辞書の符号化コードの最大値によって、書き出しビット長を増やす．
wを辞書の登録番号で符号化する．書き出しビット長に従って、符号化コードを書き出す．
kをwに入れ，2.1に戻る．
------ ループ終了 ------
3. 最後にwに語が残っている場合：
wに残っている語を符号化する．書き出しビット長に従って、符号化コードを書き出す．
この時点で，wに入っている語は辞書に登録されているはずなので，辞書の登録番号で符号化できる．
したがって、辞書に登録する処理は不要で、辞書の符号化コードの最大値は変わらず、書き出しビット長も増えない．
4. 書き出しビット長に従って、終了コードを書き出す．
符号化コードを書き出す処理は、2.5と3.の二か所にあります。
いま問題となっているGIFファイルのデータで言うと、最初のピクセル〜符号化コード14までは2.5最後の符号化コード15は3.で書き出されます。
2.5と3.の違いに注目すると、
2.5には、辞書に登録する処理と、書き出しビット長を増やす処理がありますが、3.には、それらの処理がありません。
つまり、最後の符号化コードを書き出した後、次回に読み出す可能性のある符号化コードの最大値は変化せず、書き出しビット長も増えません。
LZW圧縮アルゴリズムに対応して、もういちどLZW解凍アルゴリズムを考えてみると、各々の符号化コードを読み込んだときに、以下のように処理するのが正解となります。
プログラムは、最後のピクセルの展開時を特別扱いして、符号化コードの最大値を増やさないようにしなければなりません。
プログラムは、どうやって最後のピクセルかどうかを判断すれば良いのでしょうか。
実際のところ、常に展開したピクセル数を数えておいて、画像全体のピクセルを展開したかどうかで判断する方法しかありません。
いま問題となっているGIFファイルの場合、11×6ピクセルの画像ですので、プログラムは、合計66ピクセル展開した直後の処理を特別扱いすることになります。
各々の符号化コードと画像のピクセルの対応を図に表すと、符号化コード15が、最後のピクセルに対応しているのがわかります。
ところで、よく考えると、プログラム自身が画像全体のピクセルを展開したかどうかを把握しているのならば、終了コードに頼らなくても展開終了を判断できます。
もし、画像全体のピクセルを展開する前に、終了コードを読み出してしまったら、データが壊れているかプログラムが間違っているわけです。
公開されているGIFデコーダのソースをいくつか調べてみたところ、「終了コードを読み出したら即エラー」と判断しているものが多いようです。
ただし、もしかすると、画像全体のピクセルを格納する前に終了コードを格納して、残りは背景色と見なしてしまうようなGIFファイルが存在するかもしれません。
実際にそのようなGIFファイルを見たわけではないのですが、そういうデータの格納方法がOKなのかNGなのか、GIF仕様書から判断することができませんでした。
以上をまとめると、GIFデコード処理のフローチャートは、下図のようになります。
(※説明を簡単にするために、細かな点は、フローチャート内では省略してあります。)
Sun Apr 12 20:48:20 JST 2009 Naoyuki Sawa (nsawa@piece-me.org)