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

このコミットは、Go言語の標準ライブラリ compress/bzip2 パッケージにおいて、連結されたbzip2ファイルのサポートを追加し、既存の compress/gzip パッケージの同様の機能に対するテストを追加するものです。また、bzip2のCRCチェック機能も実装されています。

コミット

commit 8a0779f9b91e3392d90dab9217be7fdbee08f523
Author: Russ Cox <rsc@golang.org>
Date:   Mon Aug 5 16:08:08 2013 -0400

    compress/bzip2: support concatenated files
    
    While we're here, add a test for the same functionality in gzip,
    which was already implemented, and add bzip2 CRC checks.
    
    Fixes #5772.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/12387044

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

https://github.com/golang/go/commit/8a0779f9b91e3392d90dab9217be7fdbee08f523

元コミット内容

compress/bzip2: support concatenated files

このコミットは、compress/bzip2 パッケージが連結されたbzip2ファイルを処理できるようにするものです。また、gzip パッケージに既に実装されている同様の機能のテストを追加し、bzip2のCRCチェック機能も追加します。

この変更の背景には、Issue #5772 があります。このIssueは、compress/bzip2 リーダーが複数のbzip2ストリームが連結されたファイルを正しく処理できないという問題点を指摘していました。多くの圧縮フォーマット（gzipなど）と同様に、bzip2も複数の圧縮ストリームを連結して一つのファイルとして扱うことが可能です。このようなファイルは、例えば複数の小さなファイルを個別に圧縮し、それらを結合して一つのアーカイブとして配布する際などに生成されます。

Goの標準ライブラリである compress/bzip2 がこの連結されたファイルをサポートしていなかったため、ユーザーはこのようなファイルを扱う際に手動でストリームを分割するなどの追加処理が必要でした。このコミットは、この問題を解決し、compress/bzip2 がより堅牢で使いやすいものになることを目指しています。

また、このコミットでは、bzip2のCRC（Cyclic Redundancy Check）チェック機能も追加されています。CRCはデータ転送や保存におけるエラー検出のために広く用いられる技術であり、圧縮されたデータの整合性を保証するために重要です。bzip2フォーマットにはファイル全体およびブロックごとのCRCが含まれており、これらを検証することでデータの破損を検出できます。

さらに、compress/gzip パッケージに既に連結ファイルサポートがあるにもかかわらず、その機能に対する明示的なテストが存在しなかったため、このコミットでそのテストも追加されています。これにより、既存の機能の堅牢性が向上します。

前提知識の解説

bzip2圧縮フォーマット

bzip2は、Burrows-Wheeler変換（BWT）とMove-to-Front（MTF）変換、ランレングス符号化（RLE）、ハフマン符号化を組み合わせたブロックソートベースのデータ圧縮アルゴリズムです。高い圧縮率を誇りますが、gzip（DEFLATEアルゴリズム）と比較して圧縮・展開速度は遅い傾向にあります。

bzip2ファイルは、通常、以下の構造を持っています。

ファイルヘッダ: マジックナンバー（"BZ"）、バージョン情報、ブロックサイズなど。
ブロック: bzip2はデータを固定サイズのブロックに分割して圧縮します。各ブロックは独立して解凍できます。
- ブロックヘッダ: ブロックのマジックナンバー、CRCチェックサム、ランダム化フラグなど。
- 圧縮データ: BWT、MTF、RLE、ハフマン符号化が適用されたデータ。
ファイルフッタ: ファイル全体のCRCチェックサム、マジックナンバーなど。

連結された圧縮ファイル

多くの圧縮フォーマット（gzip, bzip2など）では、複数の圧縮されたデータストリームを単純に連結することで、一つの有効な圧縮ファイルとして扱うことができます。例えば、file1.bz2 と file2.bz2 がある場合、cat file1.bz2 file2.bz2 > combined.bz2 のように結合しても、多くのデコンプレッサは combined.bz2 を正しく解凍し、file1 の内容に続いて file2 の内容を出力します。これは、各圧縮ストリームが自身のヘッダとフッタを持っているため、デコンプレッサがストリームの終わりと次のストリームの始まりを識別できるためです。

CRC (Cyclic Redundancy Check)

CRCは、デジタルデータの誤り検出符号の一種です。データブロックのチェックサムを生成し、そのチェックサムをデータと共に送信または保存します。受信側または読み出し側で同じアルゴリズムでチェックサムを再計算し、元のチェックサムと比較することで、データが転送中または保存中に破損していないかを確認できます。bzip2では、各ブロックとファイル全体の整合性を保証するためにCRCが使用されます。

Go言語の `io.Reader` インターフェース

Go言語では、データの読み込みは io.Reader インターフェースによって抽象化されています。Read(p []byte) (n int, err error) メソッドを持ち、データを p に読み込み、読み込んだバイト数 n とエラー err を返します。連結されたファイルをサポートするということは、Read メソッドが現在のストリームの終わりに達したときに、次のストリームのヘッダを自動的に検出し、透過的に読み込みを継続できることを意味します。

技術的詳細

このコミットの主要な変更点は、compress/bzip2 パッケージの reader 型の Read メソッドのロジックにあります。

reader 構造体の変更:
- fileCRC, blockCRC, wantBlockCRC フィールドが追加されました。これらはそれぞれ、ファイル全体のCRC、現在のブロックの計算済みCRC、現在のブロックの期待されるCRCを保持します。
setup メソッドの変更:
- setup メソッドは、bzip2ファイルのヘッダを解析する役割を担います。このコミットでは、needMagic という新しい引数が追加されました。これにより、連結されたファイルの2番目以降のストリームを処理する際に、最初の "BZ" マジックナンバーの読み込みをスキップできるようになります。これは、連結されたストリームの開始が必ずしも "BZ" で始まるとは限らないためです（前のストリームのフッタの直後に続くため）。
- bz2.fileCRC = 0 が追加され、新しいファイルのCRC計算がリセットされるようになりました。
- bz2.tt スライスの初期化ロジックが変更され、bz2.blockSize が bz2.tt の現在の容量よりも大きい場合にのみ再割り当てが行われるようになりました。これにより、不要なメモリ再割り当てが削減されます。
read メソッドの再構築:
- 元の read メソッドは、RLEデータが残っているか、または新しいブロックを読み込む必要があるかを判断していました。このコミットでは、readFromBlock という新しいヘルパーメソッドが導入され、RLEデータの処理とバッファへの書き込みを担当するようになりました。
- 新しい read メソッドは、readFromBlock を呼び出してデータを取得し、ブロックの終わりに達したときにCRCチェックを実行します。
- 連結ファイルサポートのロジック:
  - bzip2FinalMagic (ファイルの終わりを示すマジックナンバー) を検出した場合、ファイル全体のCRCチェックを実行します。
  - CRCが一致しない場合、StructuralError("file checksum mismatch") を返します。
  - CRCチェック後、バイト境界にスキップし、次の2バイトが 'B' と 'Z' であるかを確認します。これは、次のbzip2ストリームの開始を示します。
  - もし 'B' と 'Z' が検出された場合、bz2.setup(false) を呼び出して次のストリームのヘッダを解析し、読み込みを継続します。false を渡すことで、最初の "BZ" マジックナンバーの再読み込みをスキップします。
  - io.EOF が検出された場合、ファイルの終わりに到達したと判断します。
- bzip2BlockMagic (ブロックの開始を示すマジックナンバー) を検出した場合、readBlock を呼び出して新しいブロックを読み込みます。
readBlock メソッドの変更:
- ブロックのCRC (wantBlockCRC) を読み込み、bz2.blockCRC をリセットします。
- bz2.fileCRC を更新するロジックが追加されました。bzip2のファイルCRCは、各ブロックのCRCを特定のビット操作（ローテートXOR）で結合して計算されます。
CRC計算関数の追加:
- crctab というCRCテーブルが init 関数で初期化されます。これは、bzip2で使用される特定のCRC32アルゴリズム（通常のCRC32とはビットシフトの方向が逆）のためのルックアップテーブルです。
- updateCRC(val uint32, b []byte) uint32 関数が追加されました。この関数は、与えられたバイトスライス b を使用してCRC値を更新します。これは、bzip2のブロックCRCとファイルCRCの計算に使用されます。

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

`src/pkg/compress/bzip2/bzip2.go`

reader 構造体に fileCRC, blockCRC, wantBlockCRC フィールドを追加。
setup 関数に needMagic 引数を追加し、マジックナンバーの読み込みを制御。
Read メソッドのロジックを大幅に修正し、readFromBlock を導入。
read メソッド内で、bzip2FinalMagic (ファイルの終わり) と bzip2BlockMagic (ブロックの開始) の検出ロジックを強化し、連結ファイルの処理とCRCチェックを追加。
readBlock メソッドで、ブロックCRCの読み込みとファイルCRCの更新ロジックを追加。
crctab と updateCRC 関数を追加し、bzip2のCRC計算を実装。

`src/pkg/compress/bzip2/bzip2_test.go`

TestConcat 関数を追加。これは、2つの helloWorldBZ2Hex を連結したものを解凍し、元のデータが2回繰り返されていることを確認するテストです。

`src/pkg/compress/gzip/gzip_test.go`

TestConcat 関数を追加。これは、2つのgzipストリームを連結して書き込み、それを読み込んで元のデータが正しく結合されていることを確認するテストです。

コアとなるコードの解説

`src/pkg/compress/bzip2/bzip2.go` の変更点

// reader 構造体に追加されたCRC関連のフィールド
type reader struct {
	br           bitReader
	fileCRC      uint32       // ファイル全体のCRC
	blockCRC     uint32       // 現在のブロックの計算済みCRC
	wantBlockCRC uint32       // 現在のブロックの期待されるCRC
	setupDone    bool
	blockSize    int
	eof          bool
	buf          []byte
	c            [256]uint
	tt           []uint32
	tPos         uint32
	preRLE      []uint32
	preRLEUsed  int
	repeats     int
	ch          byte
}

// setup メソッドの変更
func (bz2 *reader) setup(needMagic bool) error {
	br := &bz2.br

	if needMagic { // 連結ファイルの2番目以降のストリームではfalseになる
		magic := br.ReadBits(16)
		if magic != bzip2FileMagic {
			return StructuralError("bad magic value")
		}
	}

	// ... (既存の圧縮レベルの読み込みなど)

	bz2.fileCRC = 0 // 新しいファイルのCRCをリセット
	// ... (bz2.tt のサイズ調整ロジック)
	return nil
}

// readFromBlock: RLEデータを処理し、バッファに書き込む新しいヘルパー関数
func (bz2 *reader) readFromBlock(buf []byte) int {
	n := 0
	for (bz2.repeats > 0 || bz2.preRLEUsed < len(bz2.preRLE)) && n < len(buf) {
		// ... (RLEデータの処理ロジック)
		n++
	}
	return n
}

// read メソッドの主要な変更点
func (bz2 *reader) read(buf []byte) (int, error) {
	for {
		n := bz2.readFromBlock(buf) // まずRLEデータを読み込む
		if n > 0 {
			bz2.blockCRC = updateCRC(bz2.blockCRC, buf[:n]) // 読み込んだデータでブロックCRCを更新
			return n, nil
		}

		// RLEデータがない場合、ブロックの終わりまたはファイルの終わりを処理

		// ブロックの終わり。CRCをチェック。
		if bz2.blockCRC != bz2.wantBlockCRC {
			bz2.br.err = StructuralError("block checksum mismatch")
			return 0, bz2.br.err
		}

		// 次のブロックを探す
		br := &bz2.br
		switch br.ReadBits64(48) { // 48ビットのマジックナンバーを読み込む
		default:
			return 0, StructuralError("bad magic value found")

		case bzip2BlockMagic: // ブロックの開始
			err := bz2.readBlock() // 新しいブロックを読み込む
			if err != nil {
				return 0, err
			}

		case bzip2FinalMagic: // ファイルの終わり
			wantFileCRC := uint32(br.ReadBits64(32)) // ファイル全体の期待されるCRCを読み込む
			if br.err != nil {
				return 0, br.err
			}
			if bz2.fileCRC != wantFileCRC { // ファイルCRCをチェック
				br.err = StructuralError("file checksum mismatch")
				return 0, br.err
			}

			// バイト境界にスキップ
			if br.bits%8 != 0 {
				br.ReadBits(br.bits % 8)
			}

			// 連結されたファイルがあるかチェック (次の "BZ" マジックナンバーを探す)
			b, err := br.r.ReadByte()
			if err == io.EOF {
				br.err = io.EOF
				bz2.eof = true
				return 0, io.EOF
			}
			if err != nil {
				br.err = err
				return 0, err
			}
			z, err := br.r.ReadByte()
			if err != nil {
				if err == io.EOF {
					err = io.ErrUnexpectedEOF
				}
				br.err = err
				return 0, err
			}
			if b != 'B' || z != 'Z' { // "BZ" が見つからない場合はエラー
				return 0, StructuralError("bad magic value in continuation file")
			}
			if err := bz2.setup(false); err != nil { // 次のストリームのセットアップ (needMagic=false)
				return 0, err
			}
		}
	}
}

// readBlock メソッドの変更点
func (bz2 *reader) readBlock() (err error) {
	br := &bz2.br
	bz2.wantBlockCRC = uint32(br.ReadBits64(32)) // ブロックの期待されるCRCを読み込む
	bz2.blockCRC = 0                             // ブロックCRCをリセット
	// ファイルCRCを更新 (ブロックCRCをローテートXORで結合)
	bz2.fileCRC = (bz2.fileCRC<<1 | bz2.fileCRC>>31) ^ bz2.wantBlockCRC
	// ... (既存のブロック読み込みロジック)
	return nil
}

// CRC計算関連の関数
var crctab [256]uint32

func init() {
	const poly = 0x04C11DB7 // bzip2で使用されるCRC多項式
	for i := range crctab {
		crc := uint32(i) << 24
		for j := 0; j < 8; j++ {
			if crc&0x80000000 != 0 {
				crc = (crc << 1) ^ poly
			} else {
				crc <<= 1
			}
		}
		crctab[i] = crc
	}
}

// updateCRC はCRC値を更新する
func updateCRC(val uint32, b []byte) uint32 {
	crc := ^val // 初期値はビット反転
	for _, v := range b {
		crc = crctab[byte(crc>>24)^v] ^ (crc << 8)
	}
	return ^crc // 最終結果もビット反転
}

`src/pkg/compress/bzip2/bzip2_test.go` の変更点

func TestConcat(t *testing.T) {
	// 2つのbzip2圧縮された"hello world"を連結
	out, err := decompressHex(helloWorldBZ2Hex + helloWorldBZ2Hex)
	if err != nil {
		t.Errorf("error from Read: %s", err)
		return
	}

	// 期待される結果は"hello world"が2回繰り返されたもの
	hello2 := bytes.Repeat(helloWorld, 2)
	if !bytes.Equal(hello2, out) {
		t.Errorf("got %x, want %x", out, hello2)
	}
}

`src/pkg/compress/gzip/gzip_test.go` の変更点

// 複数のgzipファイルが連結されても有効なgzipファイルとなることをテスト
func TestConcat(t *testing.T) {
	var buf bytes.Buffer
	w := NewWriter(&buf)
	w.Write([]byte("hello "))
	w.Close() // 最初のgzipストリームを閉じる

	w = NewWriter(&buf) // 新しいgzipストリームを開始
	w.Write([]byte("world\n"))
	w.Close() // 2番目のgzipストリームを閉じる

	r, err := NewReader(&buf) // 連結されたストリームを読み込む
	data, err := ioutil.ReadAll(r)
	if string(data) != "hello world\n" || err != nil {
		t.Fatalf("ReadAll = %q, %v, want %q, nil", data, err, "hello world")
	}
}

これらの変更により、compress/bzip2 は連結されたファイルを透過的に処理できるようになり、データの整合性を保証するためのCRCチェックも行われるようになりました。また、compress/gzip の既存の連結ファイルサポートに対するテストが追加され、ライブラリ全体の堅牢性が向上しています。

参考にした情報源リンク

bzip2公式ウェブサイト: http://www.bzip.org/
bzip2フォーマット仕様 (非公式): https://en.wikipedia.org/wiki/Bzip2#File_format
CRC (Cyclic Redundancy Check) - Wikipedia: https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF
Go言語 io.Reader ドキュメント: https://pkg.go.dev/io#Reader
Go言語 compress/bzip2 ドキュメント: https://pkg.go.dev/compress/bzip2
Go言語 compress/gzip ドキュメント: https://pkg.go.dev/compress/gzip

comemo