[インデックス 16803] ファイルの概要

このコミットは、Go言語の標準ライブラリ image/gif パッケージ内の writer.go ファイルに対する変更です。writer.go は、GIF画像をエンコードし、ファイルに書き出すためのロジックを実装しています。具体的には、GIFファイルのヘッダ、論理画面記述子、イメージ記述子、カラーテーブル、画像データなどをGIFフォーマットの仕様に従って書き込む役割を担っています。

コミット

image/gif: don't write superfluous global color table

R=r, nigeltao
CC=golang-dev
https://golang.org/cl/11446043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/a6f95ad34ea6b8c450a126d5fd783a8fc6e9d953

元コミット内容

このコミットは、Go言語の image/gif パッケージにおいて、GIF画像を書き出す際に「不要なグローバルカラーテーブル (Global Color Table, GCT) を書き出さない」ようにする変更を導入しています。これにより、生成されるGIFファイルのサイズを削減し、より効率的なファイル出力を行うことが目的です。

変更の背景

GIFフォーマットでは、画像の色情報を定義するためにカラーテーブルを使用します。カラーテーブルには大きく分けて2種類あります。

1. グローバルカラーテーブル (GCT): GIFファイル全体に適用されるデフォルトのカラーテーブルです。論理画面記述子 (Logical Screen Descriptor) の直後に配置されます。
2. ローカルカラーテーブル (LCT): 各イメージブロック（フレーム）に個別に適用されるカラーテーブルです。イメージ記述子 (Image Descriptor) の直後に配置され、そのイメージブロックにのみ有効です。LCTが存在する場合、GCTよりも優先されます。

GIFアニメーションのように複数のフレームを持つGIFファイルでは、各フレームが独自のカラーパレットを持つことが一般的です。この場合、各フレームは通常、自身のローカルカラーテーブル (LCT) を持ちます。もしすべてのフレームがLCTを持っている場合、ファイル全体に適用されるグローバルカラーテーブル (GCT) は冗長となり、ファイルサイズを不必要に増加させる原因となります。

このコミット以前の image/gif パッケージの実装では、たとえすべてのフレームがLCTを持つ場合でも、最初のフレームのパレットに基づいてGCTを書き出していました。これはGIFの仕様上必須ではなく、ファイルサイズを最適化する観点からは「superfluous（余分な、不必要な）」なデータでした。この変更は、この冗長なGCTの書き出しを停止することで、生成されるGIFファイルの効率性を向上させることを目的としています。

前提知識の解説

GIF (Graphics Interchange Format) フォーマットの基本構造

GIFは、主にウェブ上でアニメーションや透過画像を扱うために広く利用されているビットマップ画像フォーマットです。その構造はブロックベースで、以下のような主要な要素で構成されます。

• ヘッダ (Header): GIFファイルの先頭に位置し、GIFのバージョン（例: GIF89a）を示します。
• 論理画面記述子 (Logical Screen Descriptor): GIF画像の全体的なキャンバスサイズ（幅と高さ）、背景色、ピクセルアスペクト比、そしてグローバルカラーテーブル (GCT) の有無とそのサイズに関する情報を含みます。
• グローバルカラーテーブル (Global Color Table, GCT): 論理画面記述子でGCTが存在すると示された場合に、その直後に配置されます。最大256色のRGB値を定義するパレット情報です。ファイル内のすべての画像ブロックに適用されるデフォルトのカラーパレットとして機能します。
• アプリケーション拡張ブロック (Application Extension Block): アニメーションのループ回数など、アプリケーション固有の情報を格納するために使用されます（例: Netscape 2.0 Extension）。
• グラフィックコントロール拡張ブロック (Graphic Control Extension Block): 各イメージブロックの表示方法（遅延時間、透過色の指定、破棄方法など）を制御します。
• イメージ記述子 (Image Descriptor): 各画像ブロックの開始を示し、その画像の左上座標、幅、高さ、そしてローカルカラーテーブル (LCT) の有無とそのサイズに関する情報を含みます。
• ローカルカラーテーブル (Local Color Table, LCT): イメージ記述子でLCTが存在すると示された場合に、その直後に配置されます。そのイメージブロックにのみ適用されるカラーパレットです。LCTが存在する場合、GCTよりも優先されます。
• 画像データ (Image Data): LZW (Lempel-Ziv-Welch) 圧縮された実際のピクセルデータです。
• トレーラ (Trailer): GIFファイルの終端を示す単一のバイト (0x3B) です。

グローバルカラーテーブル (GCT) とローカルカラーテーブル (LCT) の役割

• GCT: ファイル全体で共通のカラーパレットを使用する場合に効率的です。例えば、単一の静止画GIFや、すべてのアニメーションフレームが同じパレットを共有する場合に利用されます。
• LCT: 各フレームが異なる色セットを持つアニメーションGIFで特に有用です。LCTを使用することで、各フレームに最適なパレットを適用でき、画質を維持しつつファイルサイズを最適化できます。LCTはGCTよりも優先されるため、LCTが存在するフレームではGCTは無視されます。

LZW (Lempel-Ziv-Welch) 圧縮と最小コードサイズ

GIFの画像データはLZWアルゴリズムで圧縮されます。LZW圧縮では、画像内の連続するピクセルパターンを「コード」に置き換えてデータを削減します。このコードの初期サイズ（最小コードサイズ）は、カラーテーブルのエントリ数に基づいて決定されます。通常、カラーテーブルのエントリ数 N に対して、最小コードサイズは ceil(log2(N)) ビットとなります。例えば、256色（8ビット）のパレットの場合、最小コードサイズは8ビットです。この最小コードサイズは、LZWエンコーダが使用する初期のコードワードのビット幅を決定します。

技術的詳細

このコミットの技術的な変更点は、主に src/pkg/image/gif/writer.go 内の encoder 構造体と、writeHeader および writeImageBlock メソッドに集中しています。

1. encoder 構造体からの bitsPerPixel フィールドの削除:

   • 変更前: bitsPerPixel フィールドは、グローバルカラーテーブルのサイズを決定するために使用されていました。
   • 変更後: グローバルカラーテーブルを書き出さない方針になったため、このフィールドは不要となり削除されました。

2. writeHeader メソッドにおけるグローバルカラーテーブル関連の変更:

   • e.bitsPerPixel の計算と使用の削除: 以前は、最初のイメージのパレットから bitsPerPixel を計算し、GCTのサイズを示すために使用していました。これが削除されました。
   • 論理画面記述子のフラグバイト (e.buf[0]) の変更:
     • 変更前: e.buf[0] = 0x80 | ((uint8(e.bitsPerPixel) - 1) << 4) | (uint8(e.bitsPerPixel) - 1)
       • 0x80 (ビット7をセット): グローバルカラーテーブルが存在することを示します。
       • ((uint8(e.bitsPerPixel) - 1) << 4) (ビット4-6): GCTのサイズを示します。
       • (uint8(e.bitsPerPixel) - 1) (ビット0-2): GCTのソートフラグとGCTのサイズを示します。
     • 変更後: e.buf[0] = 0x00
       • 0x00: グローバルカラーテーブルが存在しないことを示します（ビット7が0）。これにより、GCTのサイズやソートフラグも無効になります。
   • グローバルカラーテーブルの書き出し処理の削除:
     • 変更前: e.writeColorTable(pm.Palette, e.bitsPerPixel-1) が呼び出され、GCTがファイルに書き込まれていました。
     • 変更後: この行が完全に削除され、GCTが書き出されなくなりました。

3. writeImageBlock メソッドにおける litWidth の計算変更:

   • litWidth はLZW圧縮の最小コードサイズを指します。
   • 変更前: litWidth := e.bitsPerPixel
     • これは、グローバルカラーテーブルの bitsPerPixel を再利用していました。
   • 変更後: litWidth := paddedSize + 1
     • paddedSize は、現在のイメージブロックのローカルカラーテーブルのサイズ (log2(len(pm.Palette))) です。
     • paddedSize + 1 は、そのローカルカラーテーブルに対応する正しいLZW最小コードサイズを計算します。これにより、GCTの bitsPerPixel に依存することなく、各フレームのLCTに基づいて適切な最小コードサイズが設定されます。

これらの変更により、image/gif パッケージは、すべてのフレームがLCTを持つ場合に冗長なGCTを書き出すことを停止し、よりコンパクトなGIFファイルを生成するようになりました。

コアとなるコードの変更箇所

diff --git a/src/pkg/image/gif/writer.go b/src/pkg/image/gif/writer.go
index 23f8b1b3ad..645f8340ae 100644
--- a/src/pkg/image/gif/writer.go
+++ b/src/pkg/image/gif/writer.go
@@ -52,9 +52,6 @@ type encoder struct {
 	err error
 	// g is a reference to the data that is being encoded.
 	g *GIF
-	// bitsPerPixel is the number of bits required to represent each color
-	// in the image.
-	bitsPerPixel int
 	// buf is a scratch buffer. It must be at least 768 so we can write the color map.
 	buf [1024]byte
 }
@@ -118,23 +115,19 @@ func (e *encoder) writeHeader() {
 		return
 	}
 
-	// TODO: This bases the global color table on the first image
-	// only.
 	pm := e.g.Image[0]
 	// Logical screen width and height.
 	writeUint16(e.buf[0:2], uint16(pm.Bounds().Dx()))
 	writeUint16(e.buf[2:4], uint16(pm.Bounds().Dy()))
 	e.write(e.buf[:4])
 
-	e.bitsPerPixel = log2(len(pm.Palette)) + 1
-	e.buf[0] = 0x80 | ((uint8(e.bitsPerPixel) - 1) << 4) | (uint8(e.bitsPerPixel) - 1)
+	// All frames have a local color table, so a global color table
+	// is not needed.
+	e.buf[0] = 0x00
 	e.buf[1] = 0x00 // Background Color Index.
 	e.buf[2] = 0x00 // Pixel Aspect Ratio.
 	e.write(e.buf[:3])
 
-	// Global Color Table.
-	e.writeColorTable(pm.Palette, e.bitsPerPixel-1)
-
 	// Add animation info if necessary.
 	if len(e.g.Image) > 1 {
 		e.buf[0] = 0x21 // Extension Introducer.
@@ -232,7 +225,7 @@ func (e *encoder) writeImageBlock(pm *image.Paletted, delay int) {
 	// Local Color Table.
 	e.writeColorTable(pm.Palette, paddedSize)
 
-	litWidth := e.bitsPerPixel
+	litWidth := paddedSize + 1
 	if litWidth < 2 {
 		litWidth = 2
 	}

コアとなるコードの解説

type encoder struct の変更

 // bitsPerPixel is the number of bits required to represent each color
 // in the image.
-bitsPerPixel int

encoder 構造体から bitsPerPixel フィールドが削除されました。このフィールドは、グローバルカラーテーブルのサイズを管理するために使用されていましたが、グローバルカラーテーブルを書き出さない方針になったため、不要と判断されました。

func (e *encoder) writeHeader() の変更

-	e.bitsPerPixel = log2(len(pm.Palette)) + 1
-	e.buf[0] = 0x80 | ((uint8(e.bitsPerPixel) - 1) << 4) | (uint8(e.bitsPerPixel) - 1)
+	// All frames have a local color table, so a global color table
+	// is not needed.
+	e.buf[0] = 0x00

論理画面記述子のフラグバイト (e.buf[0]) の設定方法が変更されました。 変更前は、e.bitsPerPixel を計算し、それに基づいてGCTが存在することを示す 0x80 フラグとGCTのサイズ情報を設定していました。 変更後は、e.buf[0] を 0x00 に設定しています。これは、ビット7（グローバルカラーテーブルフラグ）が0であることを意味し、GCTが存在しないことを明示的に示します。これにより、GCTのサイズ情報も不要になります。

-	// Global Color Table.
-	e.writeColorTable(pm.Palette, e.bitsPerPixel-1)

グローバルカラーテーブルを書き出すための e.writeColorTable の呼び出しが削除されました。これにより、実際にGCTがファイルに書き込まれなくなります。

func (e *encoder) writeImageBlock(pm *image.Paletted, delay int) の変更

-	litWidth := e.bitsPerPixel
+	litWidth := paddedSize + 1

LZW圧縮の最小コードサイズ (litWidth) の計算方法が変更されました。 変更前は、encoder 構造体の e.bitsPerPixel を使用していました。これはGCTのサイズに関連する値でした。 変更後は、paddedSize + 1 を使用しています。paddedSize は現在のイメージブロックのローカルカラーテーブルのサイズ（パレットの色の数から計算されるビット数）です。paddedSize + 1 は、そのローカルカラーテーブルに対応する正しいLZW最小コードサイズを意味します。これにより、各フレームのLCTに基づいて適切な最小コードサイズが設定され、GCTの存在に依存しない独立した処理が可能になります。

これらの変更により、GIFエンコーダは、各フレームがローカルカラーテーブルを持つ場合に、冗長なグローバルカラーテーブルを書き出すことを避け、ファイルサイズを最適化するようになりました。

関連リンク

• Go Code Review: https://golang.org/cl/11446043

参考にした情報源リンク

• GIF89a Specification: https://www.w3.org/Graphics/GIF/spec-gif89a.txt
• Wikipedia - Graphics Interchange Format: https://ja.wikipedia.org/wiki/Graphics_Interchange_Format
• LZW compression: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch