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

このコミットは、Go言語の標準ライブラリに含まれるhash/adler32パッケージにおけるAdler-32チェックサム計算ロジックの改善を目的としています。具体的には、Digest構造体から不要なフィールドを削除し、チェックサム計算中のモジュロ演算の適用条件をより効率的かつ正確に修正することで、コードの「クリーンさ」と堅牢性を向上させています。

コミット

commit 658ca49898b024753603f8f0a9194312469d466e
Author: Tom Szymanski <tgs@google.com>
Date:   Wed Mar 18 14:57:55 2009 -0700

    Make adler32 cleaner.
    
    R=rsc
    APPROVED=rsc
    DELTA=22  (9 added, 6 deleted, 7 changed)
    OCL=26498
    CL=26500

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

https://github.com/golang/go/commit/658ca49898b024753603f8f0a9194312469d466e

元コミット内容

Make adler32 cleaner.

R=rsc
APPROVED=rsc
DELTA=22  (9 added, 6 deleted, 7 changed)
OCL=26498
CL=26500

変更の背景

Adler-32チェックサムは、データの整合性を確認するための高速なハッシュ関数です。その計算は、2つの32ビットの和（aとb）を維持し、各バイトが処理されるたびにこれらを更新し、特定のモジュロ（mod）で剰余を取ることで行われます。

このコミット以前のadler32の実装では、Digest構造体にnというフィールドがあり、これはモジュロ演算を適用するまでのバイト数をカウントするために使用されていました。また、maxIterという定数があり、これはaとbがオーバーフローする前にモジュロ演算なしで処理できる最大バイト数を示していました。

しかし、Adler-32のアルゴリズムの特性上、aとbの和が32ビット符号なし整数の最大値（0xffffffff）を超える可能性がある場合にのみモジュロ演算を適用すれば十分です。nとmaxIterを使ったアプローチは、このオーバーフロー条件を間接的に管理しようとするものでしたが、より直接的かつ効率的な方法が存在します。

このコミットの背景には、コードの簡素化、不要な状態の削除、そしてAdler-32アルゴリズムの数学的特性に基づいたより堅牢なオーバーフローチェックの実装という意図があります。これにより、コードの可読性と保守性が向上し、潜在的なバグのリスクが低減されます。

前提知識の解説

Adler-32 チェックサム

Adler-32は、Zlibで広く使用されているチェックサムアルゴリズムで、CRC32よりも高速に計算できることで知られています。これは、以下の2つの32ビットの和を維持することで計算されます。

a: データの各バイトを累積的に加算し、modで剰余を取ったもの。初期値は1。
b: aの累積和をさらに累積的に加算し、modで剰余を取ったもの。初期値は0。

各バイトbyteが処理されるたびに、以下の計算が行われます。

a = (a + byte) % mod
b = (b + a) % mod

最終的なAdler-32チェックサムは、(b << 16) | aとして計算されます。

モジュロ演算とオーバーフロー

Adler-32の計算では、aとbがmod（65521、最大の素数）を超えないようにモジュロ演算が適用されます。しかし、毎バイトごとにモジュロ演算を行うのは計算コストが高いため、通常はaとbが32ビット符号なし整数の範囲内でオーバーフローする可能性が出てきた場合にのみモジュロ演算を適用する最適化が行われます。

aとbはそれぞれ最大でmod - 1の値を取ります。新しいバイトが追加されると、aは最大でmod - 1 + 255（バイトの最大値）まで増加し、bは最大でmod - 1 + (mod - 1 + 255)まで増加します。これらの値が32ビット符号なし整数の最大値0xffffffffを超える可能性がある場合に、モジュロ演算を適用する必要があります。

Go言語のuint32型は、32ビットの符号なし整数を表します。その範囲は0から2^32 - 1（0xffffffff）までです。この型で計算を行う際、加算結果が0xffffffffを超えるとオーバーフローが発生し、結果はモジュロ2^32でラップアラウンドされます。Adler-32の計算では、このラップアラウンドを避けるために、明示的にmodでのモジュロ演算を行う必要があります。

技術的詳細

このコミットの主要な変更点は以下の通りです。

Digest構造体からのnフィールドの削除:
- 変更前: type Digest struct { a, b uint32; n int; }
- 変更後: type Digest struct { a, b uint32; }
- nフィールドは、モジュロ演算を適用するまでのバイト数をカウントするために使用されていましたが、これは不要になりました。
maxIter定数の削除:
- maxIterは、nフィールドと組み合わせてオーバーフローを管理するための定数でしたが、nの削除に伴いこれも不要になりました。
NewDigest関数の簡素化:
- NewDigest関数は、nフィールドの初期化が不要になったため、return &Digest{1, 0, 0};からreturn &Digest{1, 0};へと簡素化されました。
Writeメソッドにおけるモジュロ演算の条件変更:
- 変更前は、n == maxIterという条件でモジュロ演算が適用されていました。これは、maxIterバイト処理するごとにaとbがオーバーフローする可能性があるという仮定に基づいていました。
- 変更後: if b > (0xffffffff - 255) / 2 { ... }
  - この新しい条件は、aとbの和が32ビット符号なし整数の最大値に近づき、次の加算でオーバーフローする可能性を直接チェックします。
  - aは最大でmod - 1 + 255（約65775）まで増加します。
  - bは最大でb_current + a_newまで増加します。
  - 最悪の場合、aとbがそれぞれmod-1に近い値で、次のバイトが255の場合、aはa + 255となり、bはb + (a + 255)となります。
  - a + b + 255 <= 0xffffffffという不変条件を維持するために、bが (0xffffffff - 255) / 2を超える場合にモジュロ演算を適用します。これは、aとbの最大値がそれぞれmod-1であることを考慮すると、a + b + 255が0xffffffffを超える可能性があるかを効率的にチェックする条件です。
  - この条件により、aとbの合計が0xffffffffに近づいたときにのみモジュロ演算が実行され、不要なモジュロ演算が削減されます。
Sum32メソッドにおけるモジュロ演算の条件変更:
- 変更前: if a >= mod || b >= mod { ... }
- 変更後: if b >= mod { ... }
- aは常にbよりも小さいか等しい（a <= b）という不変条件がWriteメソッド内で維持されるため、bがmodを超えていればaもmodを超える可能性があるか、あるいは最終的なaとbの組み合わせでオーバーフローが発生する可能性があるため、b >= modのチェックだけで十分です。これにより、条件が簡素化されました。

これらの変更により、Adler-32の実装は、アルゴリズムの数学的特性により忠実になり、不要な状態管理が排除され、より効率的で「クリーン」なコードになっています。

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

`src/lib/hash/adler32.go`

--- a/src/lib/hash/adler32.go
+++ b/src/lib/hash/adler32.go
@@ -13,44 +13,46 @@ package adler32
 
 import "os"
 
+const (
+	mod = 65521;
+)
+
 // Digest represents the partial evaluation of a checksum.
 type Digest struct {
+\t// invariant: (a < mod && b < mod) || a <= b
+\t// invariant: a + b + 255 <= 0xffffffff
 \ta, b uint32;
-\tn int;
 }\
 
-const (
-	mod = 65521;
-	maxIter = 5552;  // max mod-free iterations before would overflow uint32
-)
-\
 // NewDigest creates a new Digest.
 func NewDigest() *Digest {\
-\treturn &Digest{1, 0, 0};\
+\treturn &Digest{1, 0};\
 }\
 
 // Write updates the Digest with the incremental checksum generated by p.\
 // It returns the number of bytes written; err is always nil.\
 func (d *Digest) Write(p []byte) (nn int, err *os.Error) {\
-\ta, b, n := d.a, d.b, d.n;\
+\ta, b := d.a, d.b;\
 \tfor i := 0; i < len(p); i++ {\
 \t\ta += uint32(p[i]);
 \t\tb += a;
-\t\tn++;
-\t\tif n == maxIter {\
+\t\t// invariant: a <= b
+\t\tif b > (0xffffffff - 255) / 2 {\
 \t\t\ta %= mod;
 \t\t\tb %= mod;
-\t\t\tn = 0;\
+\t\t\t// invariant: a < mod && b < mod
+\t\t} else {\
+\t\t\t// invariant: a + b + 255 <= 2 * b + 255 <= 0xffffffff
 \t\t}\
 \t}\
-\td.a, d.b, d.n = a, b, n;\
+\td.a, d.b = a, b;\
 \treturn len(p), nil
 }\
 
 // Sum32 returns the 32-bit Adler-32 checksum of the data written to the Digest.\
 func (d *Digest) Sum32() uint32 {\
 \ta, b := d.a, d.b;\
-\tif a >= mod || b >= mod {\
+\tif b >= mod {\
 \t\ta %= mod;\
 \t\tb %= mod;\
 \t}\

`src/lib/hash/adler32_test.go`

--- a/src/lib/hash/adler32_test.go
+++ b/src/lib/hash/adler32_test.go
@@ -47,6 +47,7 @@ var golden = []_Adler32Test {
 	_Adler32Test{ 0x39111dd0, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley" },
 	_Adler32Test{ 0x91dd304f, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule" },
 	_Adler32Test{ 0x2e5d1316, "How can you write a big system without C++?  -Paul Glick" },
+\t_Adler32Test{ 0xd0201df6, "'Invariant assertions' is the most elegant programming technique!  -Tom Szymanski" },
 }\
 
 func TestGolden(t *testing.T) {\

コアとなるコードの解説

`src/lib/hash/adler32.go`

Digest構造体:
- n int;フィールドが削除されました。これにより、Digest構造体はaとbの2つのuint32フィールドのみを持つようになり、状態がよりシンプルになりました。
- 新しいコメント// invariant: (a < mod && b < mod) || a <= bと// invariant: a + b + 255 <= 0xffffffffが追加され、aとbの間の関係性およびオーバーフローに関する不変条件が明示されました。これは、コードの意図を明確にし、将来の保守性を高めます。
NewDigest関数:
- nフィールドの初期化が不要になったため、return &Digest{1, 0, 0};からreturn &Digest{1, 0};に変更されました。
Writeメソッド:
- a, b, n := d.a, d.b, d.n;からa, b := d.a, d.b;に変更され、n変数の使用がなくなりました。
- モジュロ演算の条件がif n == maxIter { ... }からif b > (0xffffffff - 255) / 2 { ... }に変更されました。
  - この新しい条件は、bの値が特定の閾値を超えた場合にモジュロ演算を実行します。この閾値は、aとbの合計が次のバイトの加算によってuint32の最大値0xffffffffを超える可能性を考慮して設定されています。具体的には、a + b + 255が0xffffffffを超えないようにするために、bが (0xffffffff - 255) / 2を超えたらモジュロ演算を行うというロジックです。これにより、オーバーフローをより正確に検出し、必要な場合にのみモジュロ演算を実行することで効率を向上させています。
  - 新しいコメント// invariant: a <= bと// invariant: a < mod && b < modが追加され、ループ内の不変条件が明確にされました。
Sum32メソッド:
- モジュロ演算の条件がif a >= mod || b >= mod { ... }からif b >= mod { ... }に変更されました。
- Writeメソッド内でa <= bという不変条件が維持されているため、bがmodを超えていれば、aもmodを超えるか、あるいは最終的なチェックサムの計算に影響を与える可能性があるため、bのチェックだけで十分であると判断されました。これにより、条件が簡素化されました。

`src/lib/hash/adler32_test.go`

新しいテストケースがgoldenスライスに追加されました。
- _Adler32Test{ 0xd0201df6, "'Invariant assertions' is the most elegant programming technique! -Tom Szymanski" },
- このテストケースは、変更されたロジックが正しく機能することを確認するためのものです。特に、Writeメソッド内の不変条件の導入と関連している可能性があります。

これらの変更は、Adler-32チェックサムの実装をより堅牢で、効率的で、理解しやすいものにすることを目的としています。不要な状態を削除し、オーバーフローチェックをより直接的に行うことで、コードの品質が向上しています。

参考にした情報源リンク

Go言語のコミット履歴: https://github.com/golang/go/commits/master
Adler-32アルゴリズムに関する一般的な情報源 (例: Zlibドキュメントなど)
Go言語のuint32型の挙動に関する情報

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

Adler-32 チェックサム

モジュロ演算とオーバーフロー

Go言語の`uint32`型

技術的詳細

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

`src/lib/hash/adler32.go`

`src/lib/hash/adler32_test.go`

コアとなるコードの解説

`src/lib/hash/adler32.go`

`src/lib/hash/adler32_test.go`

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo