GIFデコーダ: Goインターフェースの練習（A GIF decoder: an exercise in Go interfaces）

2011-05-25

GIFデコーダ: Goインターフェースの練習 #

A GIF decoder: an exercise in Go interfaces by Rob Pike

はじめに #

2011年5月10日にサンフランシスコで行われたGoogle I/Oのカンファレンスで、私たちはGo言語がGoogle App Engineで利用可能になったことを発表しました。Goは機械語に直接コンパイルするApp Engine上で利用可能となった最初の言語で、画像処理のようなCPUに負荷をかけるタスクにとってそれは良い選択でした。

その流れで、私たちは以下のような画像を手軽により良くする Moustachio と呼ばれるプログラムを実演しました:

髭を加えて、その結果を共有しましょう:

アンチエイリアスが施された髭の描画を含む全てのグラフィック処理は、App Engine上で動作しているGoプログラムで完結します。（そのソースコードは appengine-goプロジェクト で利用可能です。）

Web上のほとんどの画像 - 少なくとも髭加工される可能性のある - がJPEGであるにも関わらず、ほかにも数えきれないほど広まっている画像形式があり、そしてアップロードされた数種類の画像形式を受け入れるのでそれは髭にとってもの分かりが良いように見えます。JPEGとPNGのデコーダはすでにGoの画像ライブラリの中にありましたが、昔からあるGIF形式のデコーダはなかったので、私たちは発表に間に合うようにGIFデコーダを書くとこにしました。そのデコーダは、問題解決のためにGoのインターフェースがどのようにしてその問題をより扱いやすくしているのかを示すいくつかのピースを含んでいます。このブログ記事の残りの部分ではその2、3個の例を述べています。

GIFのフォーマット #

まず初めに、GIFの形式について簡単に見ていきましょう。GIFの画像ファイルはパレット化されており、つまりそれぞれのピクセル値はファイルに含まれているある決まったカラーマップにインデックス付けされています。ディスプレイの1ピクセルがたった8ビットで表されていた頃からGIF形式はあり、カラーマップは値の制限された組をスクリーンを明るくするために必要なRGB（赤、緑、青）の3値に変換するために使われていました。（これはJPEGとは対称的で、例えば、JPEGはエンコーダが直接カラー信号の分離を表現するためJPEGにはカラーマップはありません。）

GIF画像は1ピクセル当たり1から8ビットの値をとることができ、包括的ですが、1ピクセルあたり8ビットが最も使われています。

少し単純化すると、GIFファイルはピクセル深度、画像の次元、カラーマップ（1枚の8ビット画像あたり256色のRGB値）をそれぞれ定義するヘッダーと、次いでピクセルデータを含んでいます。ピクセルデータは1次元のビットストリームとして格納され、写真には向きませんがコンピュータが生成するグラフィックスにとってはかなり効率的なLZWアルゴリズムを使って圧縮されます。そのとき圧縮データはある長さで区切られ、1バイトのカウント（0-255）とそれに続くバイト列という構成のブロックに分割されます:

ピクセルデータのデブロッキング #

GIFのピクセルデータをGoでデコードするために、compress/lzw パッケージからLZWデコンプレッサを使うことができます。そのパッケージには、ドキュメント曰く、「rから読み出したデータを解凍することによって読み出し可能となる」オブジェクトを返すNewReader関数があります。

func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser

ここで、orderはビットデータをパックする順番を定義し、litWidthはGIFファイルとピクセル深度（典型的には8）を対応させる際に使用するビット単位のワードサイズを意味しています。

しかし、NewReader の最初の引数として入力ファイルを与えることはできません。それはデコンプレッサがバイトストリームを要求しているにも関わらずGIFデータはアンパックが必要なブロックストリームになっているからです。この問題を扱うために、それをデブロッキングするためのちょっとしたコードにより入力 io.Reader をラップすることができます。さらにそのコードを再び Reader として実装することもできます。つまり、デブロッキングするコードを blockReader と呼ばれる新しい型の Read メソッドの中で実装します。

以下は blockReader のデータ構造です。

type blockReader struct {
    r     reader    // Input source; implements io.Reader and io.ByteReader.
    slice []byte    // Buffer of unread data.
    tmp   [256]byte // Storage for slice.
}

リーダー r は画像データのソースであり、そのソースは恐らくファイルかHTTP接続でしょう。slice と tmp フィールドはデブロッキングを管理するために使われます。以下は Read メソッドの全体像です。