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

このコミットは、Go言語の標準ライブラリ compress/lzw パッケージ内の reader.go ファイルに対する変更です。このファイルは、LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムのデコーダを実装しており、主にGIFやPDFなどのファイル形式で使用されるLZWデータを読み込む役割を担っています。

コミット

commit 9f08c5c3830d42de9bf18b80b79516c61e1ea360
Author: Nigel Tao <nigeltao@golang.org>
Date:   Fri Jun 13 17:44:29 2014 +1000

    compress/lzw: add commentary that TIFF's LZW differs from the standard
    algorithm.
    
    See https://golang.org/cl/105750045/ for an implementation of
    TIFF's LZW.
    
    LGTM=r
    R=r
    CC=golang-codereviews
    https://golang.org/cl/102940043

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

https://github.com/golang/go/commit/9f08c5c3830d42de9bf18b80b79516c61e1ea360

元コミット内容

このコミットの目的は、compress/lzw パッケージのドキュメントに、TIFFファイル形式で使用されるLZWアルゴリズムが、このパッケージが実装している「標準的な」LZWアルゴリズムとは互換性がないことを示す注釈を追加することです。

変更の背景

LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムは、可逆データ圧縮手法として広く知られています。GIF、TIFF、PDFなど、多くの画像およびドキュメント形式で採用されています。しかし、これらの形式が採用しているLZWの実装には微妙な違いが存在することがあります。

compress/lzw パッケージは、主にGIFやPDFで使われるLZWの「標準的な」バリアントを実装しています。この「標準的な」バリアントは、Welchの論文で記述されたアルゴリズムに基づいています。しかし、TIFFファイル形式で使われるLZWは、この標準的な実装とは異なる挙動を示すことが知られていました。具体的には、コードテーブルの管理方法や、新しいコードの追加タイミングに「オフバイワン」エラーのような違いが存在し、これが互換性の問題を引き起こしていました。

このコミットの背景には、ユーザーが compress/lzw パッケージをTIFFファイルのLZW圧縮解除に利用しようとした際に、予期せぬエラーや不正なデータ解凍が発生する可能性があったという問題意識があります。そのため、開発者は、このパッケージがTIFFのLZWとは互換性がないことを明示的にドキュメントに記載する必要があると判断しました。これにより、ユーザーはTIFFのLZWを扱う際には、専用のパッケージ（例: golang.org/x/image/tiff/lzw）を使用する必要があることを明確に理解できるようになります。

なお、コミットメッセージに記載されている https://golang.org/cl/105750045/ は、実際にはGoランタイムのスタックオーバーフローに関する修正のCLであり、TIFFのLZW実装とは直接関係がありません。これはコミットメッセージの誤記であると考えられます。TIFFのLZW実装は、現在 golang.org/x/image/tiff/lzw パッケージで提供されています。

前提知識の解説

LZW (Lempel-Ziv-Welch) 圧縮アルゴリズム

LZWは、データ内の繰り返しパターンを辞書に登録し、そのパターンをより短いコードに置き換えることでデータを圧縮する可逆圧縮アルゴリズムです。

1. 辞書初期化: 最初に、0から255までの単一バイト（ASCII文字など）が辞書に登録されます。これらは「リテラルコード」と呼ばれます。
2. コードの生成: 圧縮中に、既に見つかったバイトシーケンス（文字列）が辞書に追加されます。新しいシーケンスが見つかると、それに新しいコードが割り当てられます。
3. 可変長コード: LZWは通常、可変長のコードを使用します。最初は短いビット数（例: 9ビット）でコードを表現し、辞書が大きくなるにつれてビット数を増やしていきます（例: 最大12ビット）。
4. クリアコード (Clear Code): 辞書を初期状態に戻すための特殊なコードです。これにより、圧縮効率の低下を防ぎ、特定のデータパターンに最適化された辞書を再構築できます。
5. EOFコード (End Of File Code): データストリームの終わりを示す特殊なコードです。

LZWのバリアントと互換性

LZWアルゴリズムの基本的な概念は共通していますが、特定のファイル形式（GIF, TIFF, PDFなど）に組み込まれる際に、以下のような点で微妙な違いが生じることがあります。

• 初期辞書サイズと内容: 辞書の初期状態が異なる場合があります。
• コードテーブルの管理: 新しいコードを辞書に追加するタイミングや、辞書がいっぱいになった際の挙動が異なることがあります。
• クリアコードとEOFコードの割り当て: これらの特殊コードに割り当てられる値が異なる場合があります。
• ビットオーダー: コードのビットが最上位ビットから（MSB）または最下位ビットから（LSB）パックされるかが異なる場合があります。

これらの違いは、一見すると些細なものに見えますが、異なるバリアントで圧縮されたデータを別のバリアントのデコーダで解凍しようとすると、データ破損や解凍エラーにつながる可能性があります。

GIF、PDF、TIFFにおけるLZW

• GIF (Graphics Interchange Format): LZWを広く普及させた形式の一つです。8ビットカラー画像に適しており、LZWの標準的な実装を使用しています。
• PDF (Portable Document Format): 画像やストリームの圧縮にLZWを使用することがあります。GIFと同様に、標準的なLZWの実装に準拠しています。
• TIFF (Tagged Image File Format): 高品質な画像保存に適した形式で、LZW圧縮もサポートしています。しかし、TIFFのLZWは、標準的なLZWとは異なる「オフバイワン」の挙動を持つことが知られています。この違いは、主にコードテーブルのインデックス付けや、新しいコードの追加ロジックに起因します。

技術的詳細

このコミットの技術的な核心は、TIFFのLZWが「標準的な」LZWアルゴリズムと互換性がないという事実を明確にすることです。この「互換性のなさ」は、主に以下の点に起因します。

1. コードテーブルの管理と「オフバイワン」の違い: 標準的なLZW（GIFやPDFで使われるもの）では、新しいエントリが辞書に追加される際、そのエントリは次に利用可能なコードに割り当てられます。そして、そのコードは通常、現在の出力ストリームに書き込まれた後に、次の入力シーケンスの処理のために辞書に追加されます。 一方、TIFFのLZWでは、このコードの割り当てと辞書への追加のタイミングが微妙に異なります。具体的には、TIFFのLZWは、新しいコードを辞書に追加する際に、標準的なLZWとは異なるインデックス付けや、コードの生成タイミングのずれ（「オフバイワン」）が存在します。この違いにより、同じ入力データから生成されるコードストリームが異なったり、同じコードストリームを解釈する際に異なる辞書状態になったりします。

2. 初期辞書と特殊コードの扱い: 標準的なLZWでは、初期辞書は通常、256個のリテラルコード（0-255）と、クリアコード、EOFコードの2つの特殊コードで構成されます。これらの特殊コードは、通常、256と257に割り当てられます。 TIFFのLZWも同様の概念を持ちますが、これらの特殊コードの割り当てや、辞書が最大サイズに達した際の挙動に差異がある可能性があります。

これらの違いにより、compress/lzw パッケージが実装している標準的なLZWデコーダは、TIFF形式で圧縮されたLZWデータを正しく解凍できません。TIFFのLZWは、特定の状況下で、標準的なLZWデコーダが予期しないコードを読み込んだり、辞書の状態が同期しなくなったりする原因となります。

このコミットは、コードの動作を変更するものではなく、既存のコードがTIFFのLZWとは互換性がないことを明示的にドキュメントに追記することで、ユーザーの誤解を防ぎ、正しいTIFF LZWの実装（例: golang.org/x/image/tiff/lzw）への誘導を促すものです。

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

src/pkg/compress/lzw/reader.go ファイルの変更点です。

--- a/src/pkg/compress/lzw/reader.go
+++ b/src/pkg/compress/lzw/reader.go
@@ -6,12 +6,16 @@
  // described in T. A. Welch, ``A Technique for High-Performance Data
  // Compression\'\', Computer, 17(6) (June 1984), pp 8-19.
  //
-// In particular, it implements LZW as used by the GIF, TIFF and PDF file
+// In particular, it implements LZW as used by the GIF and PDF file
  // formats, which means variable-width codes up to 12 bits and the first
  // two non-literal codes are a clear code and an EOF code.\n
+//\n
+// The TIFF file format uses a similar but incompatible version of the LZW\n
+// algorithm. See the code.google.com/p/go.image/tiff/lzw package for an\n
+// implementation.\n
  package lzw
  
-// TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF,\n
+// TODO(nigeltao): check that PDF uses LZW in the same way as GIF,\n
 // modulo LSB/MSB packing order.\n
  
  import (

コアとなるコードの解説

変更は、reader.go ファイルのパッケージコメント部分に集中しています。

1. 既存コメントの修正: // In particular, it implements LZW as used by the GIF, TIFF and PDF file という行が、 // In particular, it implements LZW as used by the GIF and PDF file に変更されました。 これにより、「TIFF」がこのパッケージがサポートするファイル形式のリストから削除され、GIFとPDFのLZW実装に特化していることが明確にされました。

2. 新しいコメントの追加: // The TIFF file format uses a similar but incompatible version of the LZW // algorithm. See the code.google.com/p/go.image/tiff/lzw package for an // implementation. という3行が追加されました。 このコメントは、TIFFファイル形式がLZWの「類似しているが互換性のない」バージョンを使用していることを明示しています。さらに、TIFFのLZW実装が必要な場合は、code.google.com/p/go.image/tiff/lzw パッケージ（現在は golang.org/x/image/tiff/lzw に移行）を参照するよう促しています。これは、ユーザーが正しいツールを選択できるようにするための重要なガイダンスです。

3. TODOコメントの修正: // TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF, という行が、 // TODO(nigeltao): check that PDF uses LZW in the same way as GIF, に変更されました。 これにより、TIFFのLZWがGIFと同じであるかどうかの確認は不要となり、PDFのLZWがGIFと同じであるかどうかの確認のみが残されました。これは、TIFFのLZWがすでに互換性がないと判断されたため、その確認が不要になったことを示しています。

これらの変更は、コードの動作には影響を与えませんが、パッケージのドキュメントを改善し、ユーザーが compress/lzw パッケージの適用範囲と制限を正しく理解できるようにすることを目的としています。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/9f08c5c3830d42de9bf18b80b79516c61e1ea360
• Go言語 image/tiff/lzw パッケージ: https://pkg.go.dev/golang.org/x/image/tiff/lzw
• Go言語 compress/lzw パッケージ: https://pkg.go.dev/compress/lzw

参考にした情報源リンク

• LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムに関する一般的な情報源
• TIFFファイル形式の仕様に関する情報源（特にLZW圧縮セクション）
• Go言語の golang.org/x/image リポジトリのドキュメントとソースコード
• コミットメッセージに記載されていた golang.org/cl/105750045 の実際の目的（Goランタイムのスタックオーバーフロー修正）に関する情報
• T. A. Welch, ``A Technique for High-Performance Data Compression'', Computer, 17(6) (June 1984), pp 8-19. (LZWアルゴリズムの原典論文)

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

このコミットは、Go言語の標準ライブラリ compress/lzw パッケージ内の reader.go ファイルに対する変更です。このファイルは、LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムのデコーダを実装しており、主にGIFやPDFなどのファイル形式で使用されるLZWデータを読み込む役割を担っています。

コミット

commit 9f08c5c3830d42de9bf18b80b79516c61e1ea360
Author: Nigel Tao <nigeltao@golang.org>
Date:   Fri Jun 13 17:44:29 2014 +1000

    compress/lzw: add commentary that TIFF's LZW differs from the standard
    algorithm.
    
    See https://golang.org/cl/105750045/ for an implementation of
    TIFF's LZW.
    
    LGTM=r
    R=r
    CC=golang-codereviews
    https://golang.org/cl/102940043

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

https://github.com/golang/go/commit/9f08c5c3830d42de9bf18b80b79516c61e1ea360

元コミット内容

このコミットの目的は、compress/lzw パッケージのドキュメントに、TIFFファイル形式で使用されるLZWアルゴリズムが、このパッケージが実装している「標準的な」LZWアルゴリズムとは互換性がないことを示す注釈を追加することです。

変更の背景

LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムは、可逆データ圧縮手法として広く知られています。GIF、TIFF、PDFなど、多くの画像およびドキュメント形式で採用されています。しかし、これらの形式が採用しているLZWの実装には微妙な違いが存在することがあります。

compress/lzw パッケージは、主にGIFやPDFで使われるLZWの「標準的な」バリアントを実装しています。この「標準的な」バリアントは、Welchの論文で記述されたアルゴリズムに基づいています。しかし、TIFFファイル形式で使われるLZWは、この標準的な実装とは異なる挙動を示すことが知られていました。具体的には、コードテーブルの管理方法や、新しいコードの追加タイミングに「オフバイワン」エラーのような違いが存在し、これが互換性の問題を引き起こしていました。

このコミットの背景には、ユーザーが compress/lzw パッケージをTIFFファイルのLZW圧縮解除に利用しようとした際に、予期せぬエラーや不正なデータ解凍が発生する可能性があったという問題意識があります。そのため、開発者は、このパッケージがTIFFのLZWとは互換性がないことを明示的にドキュメントに記載する必要があると判断しました。これにより、ユーザーはTIFFのLZWを扱う際には、専用のパッケージ（例: golang.org/x/image/tiff/lzw）を使用する必要があることを明確に理解できるようになります。

なお、コミットメッセージに記載されている https://golang.org/cl/105750045/ は、実際にはGoランタイムのスタックオーバーフローに関する修正のCLであり、TIFFのLZW実装とは直接関係がありません。これはコミットメッセージの誤記であると考えられます。TIFFのLZW実装は、現在 golang.org/x/image/tiff/lzw パッケージで提供されています。

前提知識の解説

LZW (Lempel-Ziv-Welch) 圧縮アルゴリズム

LZWは、データ内の繰り返しパターンを辞書に登録し、そのパターンをより短いコードに置き換えることでデータを圧縮する可逆圧縮アルゴリズムです。

1. 辞書初期化: 最初に、0から255までの単一バイト（ASCII文字など）が辞書に登録されます。これらは「リテラルコード」と呼ばれます。
2. コードの生成: 圧縮中に、既に見つかったバイトシーケンス（文字列）が辞書に追加されます。新しいシーケンスが見つかると、それに新しいコードが割り当てられます。
3. 可変長コード: LZWは通常、可変長のコードを使用します。最初は短いビット数（例: 9ビット）でコードを表現し、辞書が大きくなるにつれてビット数を増やしていきます（例: 最大12ビット）。
4. クリアコード (Clear Code): 辞書を初期状態に戻すための特殊なコードです。これにより、圧縮効率の低下を防ぎ、特定のデータパターンに最適化された辞書を再構築できます。
5. EOFコード (End Of File Code): データストリームの終わりを示す特殊なコードです。

LZWのバリアントと互換性

LZWアルゴリズムの基本的な概念は共通していますが、特定のファイル形式（GIF, TIFF, PDFなど）に組み込まれる際に、以下のような点で微妙な違いが生じることがあります。

• 初期辞書サイズと内容: 辞書の初期状態が異なる場合があります。
• コードテーブルの管理: 新しいコードを辞書に追加するタイミングや、辞書がいっぱいになった際の挙動が異なることがあります。
• クリアコードとEOFコードの割り当て: これらの特殊コードに割り当てられる値が異なる場合があります。
• ビットオーダー: コードのビットが最上位ビットから（MSB）または最下位ビットから（LSB）パックされるかが異なる場合があります。

これらの違いは、一見すると些細なものに見えますが、異なるバリアントで圧縮されたデータを別のバリアントのデコーダで解凍しようとすると、データ破損や解凍エラーにつながる可能性があります。

GIF、PDF、TIFFにおけるLZW

• GIF (Graphics Interchange Format): LZWを広く普及させた形式の一つです。8ビットカラー画像に適しており、LZWの標準的な実装を使用しています。
• PDF (Portable Document Format): 画像やストリームの圧縮にLZWを使用することがあります。GIFと同様に、標準的なLZWの実装に準拠しています。
• TIFF (Tagged Image File Format): 高品質な画像保存に適した形式で、LZW圧縮もサポートしています。しかし、TIFFのLZWは、標準的なLZWとは異なる「オフバイワン」の挙動を持つことが知られています。この違いは、主にコードテーブルのインデックス付けや、新しいコードの追加ロジックに起因します。

技術的詳細

このコミットの技術的な核心は、TIFFのLZWが「標準的な」LZWアルゴリズムと互換性がないという事実を明確にすることです。この「互換性のなさ」は、主に以下の点に起因します。

1. コードテーブルの管理と「オフバイワン」の違い: 標準的なLZW（GIFやPDFで使われるもの）では、新しいエントリが辞書に追加される際、そのエントリは次に利用可能なコードに割り当てられます。そして、そのコードは通常、現在の出力ストリームに書き込まれた後に、次の入力シーケンスの処理のために辞書に追加されます。 一方、TIFFのLZWでは、このコードの割り当てと辞書への追加のタイミングが微妙に異なります。具体的には、TIFFのLZWは、新しいコードを辞書に追加する際に、標準的なLZWとは異なるインデックス付けや、コードの生成タイミングのずれ（「オフバイワン」）が存在します。この違いにより、同じ入力データから生成されるコードストリームが異なったり、同じコードストリームを解釈する際に異なる辞書状態になったりします。

2. 初期辞書と特殊コードの扱い: 標準的なLZWでは、初期辞書は通常、256個のリテラルコード（0-255）と、クリアコード、EOFコードの2つの特殊コードで構成されます。これらの特殊コードは、通常、256と257に割り当てられます。 TIFFのLZWも同様の概念を持ちますが、これらの特殊コードの割り当てや、辞書が最大サイズに達した際の挙動に差異がある可能性があります。

これらの違いにより、compress/lzw パッケージが実装している標準的なLZWデコーダは、TIFF形式で圧縮されたLZWデータを正しく解凍できません。TIFFのLZWは、特定の状況下で、標準的なLZWデコーダが予期しないコードを読み込んだり、辞書の状態が同期しなくなったりする原因となります。

このコミットは、コードの動作を変更するものではなく、既存のコードがTIFFのLZWとは互換性がないことを明示的にドキュメントに追記することで、ユーザーの誤解を防ぎ、正しいTIFF LZWの実装（例: golang.org/x/image/tiff/lzw）への誘導を促すものです。

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

src/pkg/compress/lzw/reader.go ファイルの変更点です。

--- a/src/pkg/compress/lzw/reader.go
+++ b/src/pkg/compress/lzw/reader.go
@@ -6,12 +6,16 @@
  // described in T. A. Welch, ``A Technique for High-Performance Data
  // Compression\'\', Computer, 17(6) (June 1984), pp 8-19.
  //
-// In particular, it implements LZW as used by the GIF, TIFF and PDF file
+// In particular, it implements LZW as used by the GIF and PDF file
  // formats, which means variable-width codes up to 12 bits and the first
  // two non-literal codes are a clear code and an EOF code.\n
+//\n
+// The TIFF file format uses a similar but incompatible version of the LZW\n
+// algorithm. See the code.google.com/p/go.image/tiff/lzw package for an\n
+// implementation.\n
  package lzw
  
-// TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF,\n
+// TODO(nigeltao): check that PDF uses LZW in the same way as GIF,\n
 // modulo LSB/MSB packing order.\n
  
  import (

コアとなるコードの解説

変更は、reader.go ファイルのパッケージコメント部分に集中しています。

1. 既存コメントの修正: // In particular, it implements LZW as used by the GIF, TIFF and PDF file という行が、 // In particular, it implements LZW as used by the GIF and PDF file に変更されました。 これにより、「TIFF」がこのパッケージがサポートするファイル形式のリストから削除され、GIFとPDFのLZW実装に特化していることが明確にされました。

2. 新しいコメントの追加: // The TIFF file format uses a similar but incompatible version of the LZW // algorithm. See the code.google.com/p/go.image/tiff/lzw package for an // implementation. という3行が追加されました。 このコメントは、TIFFファイル形式がLZWの「類似しているが互換性のない」バージョンを使用していることを明示しています。さらに、TIFFのLZW実装が必要な場合は、code.google.com/p/go.image/tiff/lzw パッケージ（現在は golang.org/x/image/tiff/lzw に移行）を参照するよう促しています。これは、ユーザーが正しいツールを選択できるようにするための重要なガイダンスです。

3. TODOコメントの修正: // TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF, という行が、 // TODO(nigeltao): check that PDF uses LZW in the same way as GIF, に変更されました。 これにより、TIFFのLZWがGIFと同じであるかどうかの確認は不要となり、PDFのLZWがGIFと同じであるかどうかの確認のみが残されました。これは、TIFFのLZWがすでに互換性がないと判断されたため、その確認が不要になったことを示しています。

これらの変更は、コードの動作には影響を与えませんが、パッケージのドキュメントを改善し、ユーザーが compress/lzw パッケージの適用範囲と制限を正しく理解できるようにすることを目的としています。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/9f08c5c3830d42de9bf18b80b79516c61e1ea360
• Go言語 image/tiff/lzw パッケージ: https://pkg.go.dev/golang.org/x/image/tiff/lzw
• Go言語 compress/lzw パッケージ: https://pkg.go.dev/compress/lzw

参考にした情報源リンク

• LZW (Lempel-Ziv-Welch) 圧縮アルゴリズムに関する一般的な情報源
• TIFFファイル形式の仕様に関する情報源（特にLZW圧縮セクション）
• Go言語の golang.org/x/image リポジトリのドキュメントとソースコード
• コミットメッセージに記載されていた golang.org/cl/105750045 の実際の目的（Goランタイムのスタックオーバーフロー修正）に関する情報
• T. A. Welch, ``A Technique for High-Performance Data Compression'', Computer, 17(6) (June 1984), pp 8-19. (LZWアルゴリズムの原典論文)