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

このコミットは、Go言語のcompress/bzip2パッケージにおける、ハフマンツリーのデコード処理の堅牢性を向上させるものです。具体的には、不正な形式のBzip2ファイル、特に「余分なハフマンレベル (superfluous Huffman levels)」を含むファイルに対するハンドリングを改善し、公式のbzip2実装との互換性を高めています。

コミット

commit 9f0008bb93694410ccde7f44a86648ef1117e069
Author: Adam Langley <agl@golang.org>
Date:   Fri Feb 14 17:17:19 2014 -0500

    compress/bzip2: support superfluous Huffman levels.
    
    These should never be found in a bzip2 file but it does appear that
    there's a buggy encoder that is producing them. Since the official
    bzip2 handles this case, this change makes the Go code do likewise.
    
    With this change, the code produces the same output as the official
    bzip2 code on the invalid example given in the bug.
    
    Fixes #7279.
    
    LGTM=r
    R=golang-codereviews, r
    CC=golang-codereviews
    https://golang.org/cl/64010043

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

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

元コミット内容

compress/bzip2: support superfluous Huffman levels.

このコミットは、compress/bzip2パッケージが「余分なハフマンレベル」をサポートするようにするものです。これらのレベルはBzip2ファイル内に存在すべきではありませんが、バグのあるエンコーダがこれらを生成しているようです。公式のbzip2実装がこのケースを処理するため、Goのコードも同様に処理するように変更されます。この変更により、バグで与えられた不正な例に対して、Goのコードは公式のbzip2コードと同じ出力を生成するようになります。これはIssue #7279を修正します。

変更の背景

この変更の背景には、特定の「バグのあるエンコーダ」によって生成されたBzip2ファイルが、標準的なBzip2仕様に厳密には準拠していないにもかかわらず、広く利用されているという現実問題があります。Goのcompress/bzip2パッケージは、これらの非標準的なファイルをデコードする際にエラーを発生させていました。

コミットメッセージによると、この問題はGoのIssue #7279で報告されています。このIssueでは、不正なハフマンツリー構造を持つBzip2ファイルが提示され、Goのデコーダがこれを処理できないことが指摘されていました。しかし、公式のbzip2実装（C言語で書かれたリファレンス実装）は、このような「余分なハフマンレベル」が存在する場合でも、適切にデコードできる堅牢性を持っていました。

Goの設計哲学の一つに「実用性」があります。たとえ仕様から逸脱したファイルであっても、それが「in the wild」（現実世界）で広く使われており、他の主要な実装がそれを処理できるのであれば、Goのライブラリも同様に処理できるべきであるという考え方です。このコミットは、この哲学に基づき、Goのbzip2デコーダの互換性と堅牢性を向上させることを目的としています。これにより、Goアプリケーションがより広範なBzip2ファイルを問題なく扱えるようになります。

前提知識の解説

Bzip2圧縮アルゴリズム

Bzip2は、Burrows-Wheeler変換 (BWT) とMove-To-Front (MTF) 変換、ランレングス符号化 (RLE)、そしてハフマン符号化を組み合わせたブロックソートベースの可逆データ圧縮アルゴリズムです。

1. Burrows-Wheeler変換 (BWT): 入力データをブロックに分割し、各ブロックに対してBWTを適用します。BWTはデータを並べ替えることで、同じ文字が連続して出現する傾向を高め、後続の圧縮アルゴリズムがより効率的に機能するようにします。BWTは可逆変換であり、元のデータを完全に復元できます。
2. Move-To-Front (MTF) 変換: BWTの出力は、同じ文字が近くに集まる傾向がありますが、MTF変換はこれをさらに改善します。MTFは、最近出現した文字に小さな数値（インデックス）を割り当てることで、データ中のシンボルをより小さな値に変換します。これにより、後続のRLEやハフマン符号化がより効率的になります。
3. ランレングス符号化 (RLE): MTF変換の出力には、0が連続して出現するパターンが多く見られます。RLEは、これらの連続する0を効率的に符号化します。
4. ハフマン符号化 (Huffman Coding): 最終的に、RLEの出力に対してハフマン符号化が適用されます。ハフマン符号化は、出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、データ全体のビット数を削減する可逆圧縮手法です。デコード時には、ハフマンツリーと呼ばれる二分木構造を使用して、ビット列から元のシンボルを復元します。

ハフマンツリーとデコード

ハフマンツリーは、各リーフノードが元のシンボルに対応し、各内部ノードがその子ノードのシンボルを結合したものを表す二分木です。各シンボルには、ツリーのルートからそのシンボルに対応するリーフノードまでのパスによって定義される一意のビット列（ハフマンコード）が割り当てられます。

デコードプロセスでは、圧縮されたビットストリームを読み込み、ハフマンツリーをトラバースします。ビットが0であれば左の子ノードへ、1であれば右の子ノードへ移動します。リーフノードに到達すると、対応するシンボルがデコードされ、ツリーのルートに戻って次のシンボルのデコードを開始します。

「余分なハフマンレベル (Superfluous Huffman Levels)」

通常、ハフマンツリーは、すべてのシンボルがリーフノードとして表現され、ツリーの深さが適切に構築されるように設計されます。しかし、バグのあるエンコーダは、デコードには不要な、あるいは到達不可能なレベル（深さ）を持つハフマンツリーを生成することがあります。これを「余分なハフマンレベル」と呼びます。

例えば、あるハフマンコードが特定の深さで完全に一意に識別できるにもかかわらず、エンコーダがそのコードをさらに深いレベルまで拡張してしまったり、あるいはツリーの片側が完全に空になってしまったりするケースが考えられます。このような構造は、厳密なデコーダにとっては「構造エラー」と見なされ、処理を中断する原因となります。しかし、堅牢なデコーダは、このような異常な構造を検出し、適切にスキップしたり、無視したりして、可能な限りデコードを続行しようとします。

このコミットは、Goのbzip2デコーダが、このような「余分なハフマンレベル」を検出した場合に、エラーとして処理するのではなく、公式のbzip2実装と同様に、ツリーの適切な部分を再帰的に探索し続けることで、デコードを継続できるようにするものです。

技術的詳細

このコミットの技術的詳細は、compress/bzip2パッケージ内のhuffman.goファイルにあるbuildHuffmanNode関数の変更に集約されます。この関数は、ハフマンツリーを構築する際に再帰的に呼び出されます。

元の実装では、buildHuffmanNode関数内で、ハフマンツリーの左右の子ノードを構築する際に、どちらかのリスト（leftまたはright）が空になった場合、つまり、そのレベルでこれ以上有効なコードが存在しないにもかかわらず、ツリーの構築が続行されようとした場合に、StructuralError("superfluous level in Huffman tree")というエラーを返していました。これは、仕様に厳密に従えば正しい挙動ですが、バグのあるエンコーダが生成する不正なファイルに対しては、デコード失敗の原因となっていました。

変更後のコードでは、このエラーハンドリングが大幅に修正されています。

1. エラーではなく再帰の継続: len(left) == 0 || len(right) == 0 の条件が満たされた場合でも、即座にエラーを返すのではなく、コメントで「エンコーダのバグによって余分なレベルが存在するが、現実世界で観測されているため処理する」と説明されています。
2. 初期呼び出しの検証: len(codes) < 2 の場合、つまりハフマンツリーが空であるか、または単一のシンボルしかエンコードできない（EOFのみなど）場合は、StructuralError("empty Huffman tree")を返します。これは、ツリーとして意味をなさないため、妥当なエラーチェックです。
3. 無限再帰の防止: level == 31 という条件が追加されています。ハフマンツリーの深さは通常、最大32ビット（レベル0から31）までとされています。この条件は、再帰が無限に続くのを防ぐためのものです。もし31レベルに達しても左右どちらかのリストが空のままであれば、それは「等しいシンボルがハフマンツリーに存在する」という、より深刻な構造エラーと見なし、StructuralError("equal symbols in Huffman tree")を返します。これは、ハフマンコードが一意であるべきという原則に反するため、妥当なエラーです。
4. 再帰呼び出しの変更: len(left) == 0 の場合、つまり左の子ノードが空の場合、buildHuffmanNode(t, right, level+1)を呼び出し、右の子ノードのみで再帰を続行します。同様に、len(right) == 0 の場合（これはelseブロックで処理される）、buildHuffmanNode(t, left, level+1)を呼び出し、左の子ノードのみで再帰を続行します。これにより、余分なレベルをスキップして、有効なハフマンコードが存在するパスを探索し続けることができます。

この変更により、Goのbzip2デコーダは、不正なハフマンツリー構造を持つファイルに対しても、より寛容になり、公式のbzip2実装と同様にデコードを試みるようになります。

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

変更はsrc/pkg/compress/bzip2/huffman.goファイル内のbuildHuffmanNode関数に集中しています。

--- a/src/pkg/compress/bzip2/huffman.go
+++ b/src/pkg/compress/bzip2/huffman.go
@@ -190,7 +190,37 @@ func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIn
 	right := codes[firstRightIndex:]
 
 	if len(left) == 0 || len(right) == 0 {
-		return 0, StructuralError("superfluous level in Huffman tree")
+		// There is a superfluous level in the Huffman tree indicating
+		// a bug in the encoder. However, this bug has been observed in
+		// the wild so we handle it.
+
+		// If this function was called recursively then we know that
+		// len(codes) >= 2 because, otherwise, we would have hit the
+		// "leaf node" case, below, and not recursed.
+		//
+		// However, for the initial call it's possible that len(codes)
+		// is zero or one. Both cases are invalid because a zero length
+		// tree cannot encode anything and a length-1 tree can only
+		// encode EOF and so is superfluous. We reject both.
+		if len(codes) < 2 {
+			return 0, StructuralError("empty Huffman tree")
+		}
+
+		// In this case the recursion doesn't always reduce the length
+		// of codes so we need to ensure termination via another
+		// mechanism.
+		if level == 31 {
+			// Since len(codes) >= 2 the only way that the values
+			// can match at all 32 bits is if they are equal, which
+			// is invalid. This ensures that we never enter
+			// infinite recursion.
+			return 0, StructuralError("equal symbols in Huffman tree")
+		}
+
+		if len(left) == 0 {
+			return buildHuffmanNode(t, right, level+1)
+		}
+		return buildHuffmanNode(t, left, level+1)
 	}
 
 	nodeIndex = uint16(t.nextNode)

コアとなるコードの解説

buildHuffmanNode関数は、ハフマンツリーのノードを再帰的に構築する役割を担っています。この関数は、与えられたハフマンコードのリスト（codes）と現在のツリーのレベル（level）に基づいて、左右の子ノードを決定します。

変更前のコードでは、if len(left) == 0 || len(right) == 0という条件が、ハフマンツリーに「余分なレベル」が存在することを示すものとして扱われ、即座にStructuralError("superfluous level in Huffman tree")を返していました。これは、ハフマンツリーの構築において、あるレベルで左右どちらかの分岐が完全に空になることは、通常、不正な状態であるという前提に基づいています。

変更後のコードでは、この部分が以下のように修正・拡張されています。

1. コメントの追加: 「余分なレベルはエンコーダのバグを示すが、現実世界で観測されているため処理する」という説明が追加され、この変更の意図が明確にされています。
2. len(codes) < 2 のチェック:
   • これは、buildHuffmanNodeが再帰的に呼び出される場合（len(codes) >= 2）と、最初の呼び出しの場合（len(codes)が0または1の可能性）を区別しています。
   • len(codes)が0または1の場合、ツリーとして意味をなさないため、StructuralError("empty Huffman tree")を返して処理を中断します。これは、有効なハフマンツリーが少なくとも2つの異なるシンボルをエンコードできる必要があるためです。
3. level == 31 のチェック:
   • ハフマンツリーの深さが最大レベル（31、つまり32ビットのコード長）に達した場合のチェックです。
   • この深さに達してもまだ左右どちらかの分岐が空である場合、それは「等しいシンボルがハフマンツリーに存在する」という、より深刻なエラーを示します。ハフマンコードは一意であるべきであり、同じコードが異なるシンボルに割り当てられることはありません。このチェックは無限再帰を防ぐ役割も果たします。
4. 再帰呼び出しの変更:
   • if len(left) == 0 の場合、つまり左の子ノードに対応するコードが空の場合、buildHuffmanNode(t, right, level+1)を呼び出します。これは、左の分岐を無視し、右の分岐のみでツリー構築を続行することを意味します。
   • elseブロック（この場合はlen(right) == 0の場合）では、buildHuffmanNode(t, left, level+1)を呼び出します。これは、右の分岐を無視し、左の分岐のみでツリー構築を続行することを意味します。

これらの変更により、buildHuffmanNode関数は、不正なハフマンツリー構造（特に「余分なハフマンレベル」）を持つBzip2ファイルに対しても、エラーで中断することなく、可能な限りデコードを試みるようになります。これは、Goのbzip2デコーダが、より多くの現実世界のBzip2ファイルを処理できるようになるための重要な改善です。

関連リンク

• Go Issue #7279: https://github.com/golang/go/issues/7279
• Go CL 64010043: https://golang.org/cl/64010043 (Gerrit Code Review)

参考にした情報源リンク

• Bzip2 (Wikipedia): https://ja.wikipedia.org/wiki/Bzip2
• ハフマン符号 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7
• Burrows-Wheeler変換 (Wikipedia): https://ja.wikipedia.org/wiki/Burrows-Wheeler%E5%A4%89%E6%8F%9B
• Move-to-front変換 (Wikipedia): https://ja.wikipedia.org/wiki/Move-to-front%E5%A4%89%E6%8F%9B
• Go言語のIssueトラッカー: https://github.com/golang/go/issues
• Go言語のGerrit Code Review: https://go-review.googlesource.com/
• bzip2公式ウェブサイト: http://www.bzip.org/
• bzip2のソースコード (例: bzip2-1.0.6/bzip2.c): 公式実装のハフマンデコード部分を参考に、どのように不正なツリーを処理しているかを確認できます。# [インデックス 18534] ファイルの概要

このコミットは、Go言語のcompress/bzip2パッケージにおける、ハフマンツリーのデコード処理の堅牢性を向上させるものです。具体的には、不正な形式のBzip2ファイル、特に「余分なハフマンレベル (superfluous Huffman levels)」を含むファイルに対するハンドリングを改善し、公式のbzip2実装との互換性を高めています。

コミット

commit 9f0008bb93694410ccde7f44a86648ef1117e069
Author: Adam Langley <agl@golang.org>
Date:   Fri Feb 14 17:17:19 2014 -0500

    compress/bzip2: support superfluous Huffman levels.
    
    These should never be found in a bzip2 file but it does appear that
    there's a buggy encoder that is producing them. Since the official
    bzip2 handles this case, this change makes the Go code do likewise.
    
    With this change, the code produces the same output as the official
    bzip2 code on the invalid example given in the bug.
    
    Fixes #7279.
    
    LGTM=r
    R=golang-codereviews, r
    CC=golang-codereviews
    https://golang.org/cl/64010043

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

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

元コミット内容

compress/bzip2: support superfluous Huffman levels.

このコミットは、compress/bzip2パッケージが「余分なハフマンレベル」をサポートするようにするものです。これらのレベルはBzip2ファイル内に存在すべきではありませんが、バグのあるエンコーダがこれらを生成しているようです。公式のbzip2実装がこのケースを処理するため、Goのコードも同様に処理するように変更されます。この変更により、バグで与えられた不正な例に対して、Goのコードは公式のbzip2コードと同じ出力を生成するようになります。これはIssue #7279を修正します。

変更の背景

この変更の背景には、特定の「バグのあるエンコーダ」によって生成されたBzip2ファイルが、標準的なBzip2仕様に厳密には準拠していないにもかかわらず、広く利用されているという現実問題があります。Goのcompress/bzip2パッケージは、これらの非標準的なファイルをデコードする際にエラーを発生させていました。

コミットメッセージによると、この問題はGoのIssue #7279で報告されています。このIssueでは、不正なハフマンツリー構造を持つBzip2ファイルが提示され、Goのデコーダがこれを処理できないことが指摘されていました。しかし、公式のbzip2実装（C言語で書かれたリファレンス実装）は、このような「余分なハフマンレベル」が存在する場合でも、適切にデコードできる堅牢性を持っていました。

Goの設計哲学の一つに「実用性」があります。たとえ仕様から逸脱したファイルであっても、それが「in the wild」（現実世界）で広く使われており、他の主要な実装がそれを処理できるのであれば、Goのライブラリも同様に処理できるべきであるという考え方です。このコミットは、この哲学に基づき、Goのbzip2デコーダの互換性と堅牢性を向上させることを目的としています。これにより、Goアプリケーションがより広範なBzip2ファイルを問題なく扱えるようになります。

前提知識の解説

Bzip2圧縮アルゴリズム

Bzip2は、Burrows-Wheeler変換 (BWT) とMove-To-Front (MTF) 変換、ランレングス符号化 (RLE)、そしてハフマン符号化を組み合わせたブロックソートベースの可逆データ圧縮アルゴリズムです。

1. Burrows-Wheeler変換 (BWT): 入力データをブロックに分割し、各ブロックに対してBWTを適用します。BWTはデータを並べ替えることで、同じ文字が連続して出現する傾向を高め、後続の圧縮アルゴリズムがより効率的に機能するようにします。BWTは可逆変換であり、元のデータを完全に復元できます。
2. Move-To-Front (MTF) 変換: BWTの出力は、同じ文字が近くに集まる傾向がありますが、MTF変換はこれをさらに改善します。MTFは、最近出現した文字に小さな数値（インデックス）を割り当てることで、データ中のシンボルをより小さな値に変換します。これにより、後続のRLEやハフマン符号化がより効率的になります。
3. ランレングス符号化 (RLE): MTF変換の出力には、0が連続して出現するパターンが多く見られます。RLEは、これらの連続する0を効率的に符号化します。
4. ハフマン符号化 (Huffman Coding): 最終的に、RLEの出力に対してハフマン符号化が適用されます。ハフマン符号化は、出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、データ全体のビット数を削減する可逆圧縮手法です。デコード時には、ハフマンツリーと呼ばれる二分木構造を使用して、ビット列から元のシンボルを復元します。

ハフマンツリーとデコード

ハフマンツリーは、各リーフノードが元のシンボルに対応し、各内部ノードがその子ノードのシンボルを結合したものを表す二分木です。各シンボルには、ツリーのルートからそのシンボルに対応するリーフノードまでのパスによって定義される一意のビット列（ハフマンコード）が割り当てられます。

デコードプロセスでは、圧縮されたビットストリームを読み込み、ハフマンツリーをトラバースします。ビットが0であれば左の子ノードへ、1であれば右の子ノードへ移動します。リーフノードに到達すると、対応するシンボルがデコードされ、ツリーのルートに戻って次のシンボルのデコードを開始します。

「余分なハフマンレベル (Superfluous Huffman Levels)」

通常、ハフマンツリーは、すべてのシンボルがリーフノードとして表現され、ツリーの深さが適切に構築されるように設計されます。しかし、バグのあるエンコーダは、デコードには不要な、あるいは到達不可能なレベル（深さ）を持つハフマンツリーを生成することがあります。これを「余分なハフマンレベル」と呼びます。

例えば、あるハフマンコードが特定の深さで完全に一意に識別できるにもかかわらず、エンコーダがそのコードをさらに深いレベルまで拡張してしまったり、あるいはツリーの片側が完全に空になってしまったりするケースが考えられます。このような構造は、厳密なデコーダにとっては「構造エラー」と見なされ、処理を中断する原因となります。しかし、堅牢なデコーダは、このような異常な構造を検出し、適切にスキップしたり、無視したりして、可能な限りデコードを続行しようとします。

このコミットは、Goのbzip2デコーダが、このような「余分なハフマンレベル」を検出した場合に、エラーとして処理するのではなく、公式のbzip2実装と同様に、ツリーの適切な部分を再帰的に探索し続けることで、デコードを継続できるようにするものです。

技術的詳細

このコミットの技術的詳細は、compress/bzip2パッケージ内のhuffman.goファイルにあるbuildHuffmanNode関数の変更に集約されます。この関数は、ハフマンツリーを構築する際に再帰的に呼び出されます。

元の実装では、buildHuffmanNode関数内で、ハフマンツリーの左右の子ノードを構築する際に、どちらかのリスト（leftまたはright）が空になった場合、つまり、そのレベルでこれ以上有効なコードが存在しないにもかかわらず、ツリーの構築が続行されようとした場合に、StructuralError("superfluous level in Huffman tree")というエラーを返していました。これは、仕様に厳密に従えば正しい挙動ですが、バグのあるエンコーダが生成する不正なファイルに対しては、デコード失敗の原因となっていました。

変更後のコードでは、このエラーハンドリングが大幅に修正されています。

1. エラーではなく再帰の継続: len(left) == 0 || len(right) == 0 の条件が満たされた場合でも、即座にエラーを返すのではなく、コメントで「エンコーダのバグによって余分なレベルが存在するが、現実世界で観測されているため処理する」と説明されています。
2. 初期呼び出しの検証: len(codes) < 2 の場合、つまりハフマンツリーが空であるか、または単一のシンボルしかエンコードできない（EOFのみなど）場合は、StructuralError("empty Huffman tree")を返します。これは、ツリーとして意味をなさないため、妥当なエラーチェックです。
3. 無限再帰の防止: level == 31 という条件が追加されています。ハフマンツリーの深さは通常、最大32ビット（レベル0から31）までとされています。この条件は、再帰が無限に続くのを防ぐためのものです。もし31レベルに達しても左右どちらかのリストが空のままであれば、それは「等しいシンボルがハフマンツリーに存在する」という、より深刻な構造エラーと見なし、StructuralError("equal symbols in Huffman tree")を返します。これは、ハフマンコードが一意であるべきという原則に反するため、妥当なエラーです。
4. 再帰呼び出しの変更: len(left) == 0 の場合、つまり左の子ノードが空の場合、buildHuffmanNode(t, right, level+1)を呼び出し、右の子ノードのみで再帰を続行します。同様に、len(right) == 0 の場合（これはelseブロックで処理される）、buildHuffmanNode(t, left, level+1)を呼び出し、左の子ノードのみで再帰を続行します。これにより、余分なレベルをスキップして、有効なハフマンコードが存在するパスを探索し続けることができます。

この変更により、Goのbzip2デコーダは、不正なハフマンツリー構造を持つファイルに対しても、より寛容になり、公式のbzip2実装と同様にデコードを試みるようになります。

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

変更はsrc/pkg/compress/bzip2/huffman.goファイル内のbuildHuffmanNode関数に集中しています。

--- a/src/pkg/compress/bzip2/huffman.go
+++ b/src/pkg/compress/bzip2/huffman.go
@@ -190,7 +190,37 @@ func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIn
 	right := codes[firstRightIndex:]
 
 	if len(left) == 0 || len(right) == 0 {
-		return 0, StructuralError("superfluous level in Huffman tree")
+		// There is a superfluous level in the Huffman tree indicating
+		// a bug in the encoder. However, this bug has been observed in
+		// the wild so we handle it.
+
+		// If this function was called recursively then we know that
+		// len(codes) >= 2 because, otherwise, we would have hit the
+		// "leaf node" case, below, and not recursed.
+		//
+		// However, for the initial call it's possible that len(codes)
+		// is zero or one. Both cases are invalid because a zero length
+		// tree cannot encode anything and a length-1 tree can only
+		// encode EOF and so is superfluous. We reject both.
+		if len(codes) < 2 {
+			return 0, StructuralError("empty Huffman tree")
+		}
+
+		// In this case the recursion doesn't always reduce the length
+		// of codes so we need to ensure termination via another
+		// mechanism.
+		if level == 31 {
+			// Since len(codes) >= 2 the only way that the values
+			// can match at all 32 bits is if they are equal, which
+			// is invalid. This ensures that we never enter
+			// infinite recursion.
+			return 0, StructuralError("equal symbols in Huffman tree")
+		}
+
+		if len(left) == 0 {
+			return buildHuffmanNode(t, right, level+1)
+		}
+		return buildHuffmanNode(t, left, level+1)
 	}
 
 	nodeIndex = uint16(t.nextNode)

コアとなるコードの解説

buildHuffmanNode関数は、ハフマンツリーのノードを再帰的に構築する役割を担っています。この関数は、与えられたハフマンコードのリスト（codes）と現在のツリーのレベル（level）に基づいて、左右の子ノードを決定します。

変更前のコードでは、if len(left) == 0 || len(right) == 0という条件が、ハフマンツリーに「余分なレベル」が存在することを示すものとして扱われ、即座にStructuralError("superfluous level in Huffman tree")を返していました。これは、ハフマンツリーの構築において、あるレベルで左右どちらかの分岐が完全に空になることは、通常、不正な状態であるという前提に基づいています。

変更後のコードでは、この部分が以下のように修正・拡張されています。

1. コメントの追加: 「余分なレベルはエンコーダのバグを示すが、現実世界で観測されているため処理する」という説明が追加され、この変更の意図が明確にされています。
2. len(codes) < 2 のチェック:
   • これは、buildHuffmanNodeが再帰的に呼び出される場合（len(codes) >= 2）と、最初の呼び出しの場合（len(codes)が0または1の可能性）を区別しています。
   • len(codes)が0または1の場合、ツリーとして意味をなさないため、StructuralError("empty Huffman tree")を返して処理を中断します。これは、有効なハフマンツリーが少なくとも2つの異なるシンボルをエンコードできる必要があるためです。
3. level == 31 のチェック:
   • ハフマンツリーの深さが最大レベル（31、つまり32ビットのコード長）に達した場合のチェックです。
   • この深さに達してもまだ左右どちらかの分岐が空である場合、それは「等しいシンボルがハフマンツリーに存在する」という、より深刻なエラーを示します。ハフマンコードは一意であるべきであり、同じコードが異なるシンボルに割り当てられることはありません。このチェックは無限再帰を防ぐ役割も果たします。
4. 再帰呼び出しの変更:
   • if len(left) == 0 の場合、つまり左の子ノードに対応するコードが空の場合、buildHuffmanNode(t, right, level+1)を呼び出します。これは、左の分岐を無視し、右の分岐のみでツリー構築を続行することを意味します。
   • elseブロック（この場合はlen(right) == 0の場合）では、buildHuffmanNode(t, left, level+1)を呼び出します。これは、右の分岐を無視し、左の分岐のみでツリー構築を続行することを意味します。

これらの変更により、buildHuffmanNode関数は、不正なハフマンツリー構造（特に「余分なハフマンレベル」）を持つBzip2ファイルに対しても、エラーで中断することなく、可能な限りデコードを試みるようになります。これは、Goのbzip2デコーダが、より多くの現実世界のBzip2ファイルを処理できるようになるための重要な改善です。

関連リンク

• Go Issue #7279: https://github.com/golang/go/issues/7279
• Go CL 64010043: https://golang.org/cl/64010043 (Gerrit Code Review)

参考にした情報源リンク

• Bzip2 (Wikipedia): https://ja.wikipedia.org/wiki/Bzip2
• ハフマン符号 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7
• Burrows-Wheeler変換 (Wikipedia): https://ja.wikipedia.org/wiki/Burrows-Wheeler%E5%A4%89%E6%8F%9B
• Move-to-front変換 (Wikipedia): https://ja.wikipedia.org/wiki/Move-to-front%E5%A4%89%E6%8F%9B
• Go言語のIssueトラッカー: https://github.com/golang/go/issues
• Go言語のGerrit Code Review: https://go-review.googlesource.com/
• bzip2公式ウェブサイト: http://www.bzip.org/
• bzip2のソースコード (例: bzip2-1.0.6/bzip2.c): 公式実装のハフマンデコード部分を参考に、どのように不正なツリーを処理しているかを確認できます。