Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリ crypto/aes パッケージにおけるAES暗号化・復号処理のパフォーマンス改善を目的としています。具体的には、配列のインデックス計算において、手動で行っていた境界チェックと値の切り捨て（& 0xff）を、uint8型への型変換に置き換えることで、コードの簡潔化と実行速度の向上を実現しています。この変更により、aes.BenchmarkEncryptのベンチマークで約25%の高速化（363 ns/opから273 ns/opへ）が報告されています。

コミット

commit 3538d40ab5f57db77b3a76822c555a76020588f0
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Dec 5 13:30:25 2011 -0500

    crypto/aes: eliminate some bounds checking and manual truncation.
    
    By converting array indices to uint8, they are automatically
    constrained in the array range, and the binary AND with 0xff
    is no longer needed anymore.
    
    Before:  aes.BenchmarkEncrypt    363 ns/op
    After:   aes.BenchmarkEncrypt    273 ns/op
    
    R=golang-dev, gri, agl
    CC=golang-dev, remy
    https://golang.org/cl/5450084

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

https://github.com/golang/go/commit/3538d40ab5f57db77b3a76822c555a76020588f0

元コミット内容

crypto/aes: いくつかの境界チェックと手動での切り捨てを排除。

配列のインデックスをuint8に変換することで、それらは自動的に配列の範囲内に制約され、0xffとのビットAND演算が不要になりました。

変更前: aes.BenchmarkEncrypt 363 ns/op 変更後: aes.BenchmarkEncrypt 273 ns/op

変更の背景

この変更の主な背景は、AES暗号化・復号処理のパフォーマンス最適化です。AESアルゴリズムの実装では、S-box（Substitution box）と呼ばれる置換表へのルックアップが頻繁に行われます。このルックアップには、計算された値がS-boxの配列インデックスとして使用されます。

従来のコードでは、このインデックスがバイト値（0-255）の範囲に収まることを保証するために、ビットシフト演算の後に明示的に& 0xff（255とのビットAND）を行っていました。これは、Go言語の整数型が通常より広いビット幅を持つため、インデックスとして使用する前に下位8ビットのみを抽出する必要があったためです。

また、Go言語のランタイムは、配列アクセス時にインデックスが配列の有効な範囲内にあるかをチェックする「境界チェック（bounds checking）」を自動的に行います。このチェックは安全性を高めますが、わずかながら実行時のオーバーヘッドを発生させます。

このコミットは、これらの手動での切り捨てと、潜在的な境界チェックのオーバーヘッドを削減することで、AES処理の効率を向上させることを目指しました。

前提知識の解説

AES (Advanced Encryption Standard)

AESは、現代において最も広く使用されている対称鍵ブロック暗号の一つです。128ビットのブロックサイズを持ち、鍵長に応じて128ビット、192ビット、256ビットの3つのバリエーションがあります。AESの暗号化・復号プロセスは、複数のラウンドで構成され、各ラウンドで以下の主要な変換が行われます。

  1. SubBytes (バイト置換): 各バイトを非線形なS-box（Substitution box）を用いて置換します。S-boxは256エントリのルックアップテーブルであり、入力バイトを対応する出力バイトにマッピングします。この操作がAESの非線形性を提供し、暗号の強度に不可欠です。
  2. ShiftRows (行シフト): 状態行列の各行を異なる量だけ左に循環シフトします。
  3. MixColumns (列混合): 各列を有限体GF(2^8)上の多項式乗算によって混合します。
  4. AddRoundKey (ラウンド鍵加算): 現在のラウンド鍵を状態行列にXORします。

このコミットで変更された部分は、主にSubBytes操作に関連するS-boxのルックアップインデックスの計算です。

Go言語の整数型と型変換

Go言語には、符号付き整数型（int8, int16, int32, int64, int）と符号なし整数型（uint8, uint16, uint32, uint64, uint）があります。

  • uint8型は、8ビットの符号なし整数であり、0から255までの値を表現できます。
  • Go言語では、より大きな整数型からより小さな整数型への型変換を行うと、値は自動的に切り捨てられます（上位ビットが破棄されます）。例えば、int32の値をuint8に変換すると、その値の下位8ビットのみが保持されます。これは、& 0xff演算と同じ効果を持ちます。

境界チェック (Bounds Checking)

Go言語のコンパイラとランタイムは、配列やスライスへのアクセス時に、インデックスがそのデータ構造の有効な範囲内にあることを自動的に確認します。例えば、長さ10の配列aに対してa[10]のようなアクセスを試みると、ランタイムパニックが発生します。このチェックは、C/C++のような言語で発生しがちなバッファオーバーフローなどのメモリ安全性の問題を防止するために重要です。

しかし、この自動的な境界チェックは、わずかながら実行時のオーバーヘッドを伴います。Goコンパイラは、静的解析によってインデックスが常に有効な範囲内にあることを証明できる場合、この境界チェックを省略する最適化（bounds check elimination）を行うことがあります。

技術的詳細

このコミットの技術的な核心は、Go言語の型システムとコンパイラの最適化能力を巧みに利用して、AESのS-boxルックアップ処理を効率化している点にあります。

AESのS-boxは通常、256エントリのバイト配列（[256]byte）またはバイト値のテーブルとして実装されます。したがって、S-boxへのインデックスは0から255の範囲である必要があります。

変更前のコードでは、S-boxのインデックスを計算するために、例えばs1>>16&0xffのような式が使われていました。

  • s1>>16: s1という32ビット（またはそれ以上）の整数から、特定のバイトを抽出するために16ビット右シフトしています。
  • &0xff: シフト結果が32ビット整数であるため、その下位8ビット（つまりバイト値）のみを確実に取得するために、0xff（バイナリで11111111）とのビットAND演算を行っていました。これにより、結果が0から255の範囲に収まることが保証されます。

変更後のコードでは、この&0xffを削除し、代わりにuint8()への型変換を行っています。例えば、uint8(s1>>16)。

  • Go言語の仕様により、より大きな整数型（例: intやuint32）からuint8への型変換は、自動的に値の下位8ビットを保持し、上位ビットを破棄します。これは、&0xff演算と全く同じ効果を持ちます。

この変更がパフォーマンス向上に寄与する理由は以下の通りです。

  1. 冗長な演算の排除: &0xffという明示的なビットAND演算が不要になります。コンパイラはuint8への型変換が本質的にこの切り捨てを行うことを認識しているため、余分なCPUサイクルを消費する演算が削減されます。
  2. 境界チェックの最適化: Goコンパイラは、uint8型が0から255の範囲に限定されることを知っています。S-boxの配列が256エントリ（インデックス0-255）である場合、uint8型の変数をインデックスとして使用すると、コンパイラはインデックスが常に有効な範囲内にあることを静的に証明しやすくなります。これにより、ランタイムでの境界チェックを省略する最適化（bounds check elimination）がより頻繁に適用される可能性が高まります。境界チェックのオーバーヘッドは小さいですが、暗号化のような計算集約的な処理で何度も繰り返されると、その累積的な影響は無視できません。

結果として、コードはより簡潔になり、コンパイラがより効率的な機械語を生成できるようになるため、AES暗号化のベンチマークで顕著な速度向上が見られました。

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

src/pkg/crypto/aes/block.go ファイル内の encryptBlock 関数と decryptBlock 関数におけるS-boxルックアップのインデックス計算部分が変更されています。

--- a/src/pkg/crypto/aes/block.go
+++ b/src/pkg/crypto/aes/block.go
@@ -56,10 +56,10 @@ func encryptBlock(xk []uint32, dst, src []byte) {
 	nr := len(xk)/4 - 2 // - 2: one above, one more below
 	k := 4
 	for r := 0; r < nr; r++ {
-		t0 = xk[k+0] ^ te[0][s0>>24] ^ te[1][s1>>16&0xff] ^ te[2][s2>>8&0xff] ^ te[3][s3&0xff]
-		t1 = xk[k+1] ^ te[0][s1>>24] ^ te[1][s2>>16&0xff] ^ te[2][s3>>8&0xff] ^ te[3][s0&0xff]
-		t2 = xk[k+2] ^ te[0][s2>>24] ^ te[1][s3>>16&0xff] ^ te[2][s0>>8&0xff] ^ te[3][s1&0xff]
-		t3 = xk[k+3] ^ te[0][s3>>24] ^ te[1][s0>>16&0xff] ^ te[2][s1>>8&0xff] ^ te[3][s2&0xff]
+		t0 = xk[k+0] ^ te[0][uint8(s0>>24)] ^ te[1][uint8(s1>>16)] ^ te[2][uint8(s2>>8)] ^ te[3][uint8(s3)]
+		t1 = xk[k+1] ^ te[0][uint8(s1>>24)] ^ te[1][uint8(s2>>16)] ^ te[2][uint8(s3>>8)] ^ te[3][uint8(s0)]
+		t2 = xk[k+2] ^ te[0][uint8(s2>>24)] ^ te[1][uint8(s3>>16)] ^ te[2][uint8(s0>>8)] ^ te[3][uint8(s1)]
+		t3 = xk[k+3] ^ te[0][uint8(s3>>24)] ^ te[1][uint8(s0>>16)] ^ te[2][uint8(s1>>8)] ^ te[3][uint8(s2)]
 		k += 4
 		s0, s1, s2, s3 = t0, t1, t2, t3
 	}
@@ -101,10 +101,10 @@ func decryptBlock(xk []uint32, dst, src []byte) {
 	nr := len(xk)/4 - 2 // - 2: one above, one more below
 	k := 4
 	for r := 0; r < nr; r++ {
-		t0 = xk[k+0] ^ td[0][s0>>24] ^ td[1][s3>>16&0xff] ^ td[2][s2>>8&0xff] ^ td[3][s1&0xff]
-		t1 = xk[k+1] ^ td[0][s1>>24] ^ td[1][s0>>16&0xff] ^ td[2][s3>>8&0xff] ^ td[3][s2&0xff]
-		t2 = xk[k+2] ^ td[0][s2>>24] ^ td[1][s1>>16&0xff] ^ td[2][s0>>8&0xff] ^ td[3][s3&0xff]
-		t3 = xk[k+3] ^ td[0][s3>>24] ^ td[1][s2>>16&0xff] ^ td[2][s1>>8&0xff] ^ td[3][s0&0xff]
+		t0 = xk[k+0] ^ td[0][uint8(s0>>24)] ^ td[1][uint8(s3>>16)] ^ td[2][uint8(s2>>8)] ^ td[3][uint8(s1)]
+		t1 = xk[k+1] ^ td[0][uint8(s1>>24)] ^ td[1][uint8(s0>>16)] ^ td[2][uint8(s3>>8)] ^ td[3][uint8(s2)]
+		t2 = xk[k+2] ^ td[0][uint8(s2>>24)] ^ td[1][uint8(s1>>16)] ^ td[2][uint8(s0>>8)] ^ td[3][uint8(s3)]
+		t3 = xk[k+3] ^ td[0][uint8(s3>>24)] ^ td[1][uint8(s2>>16)] ^ td[2][uint8(s1>>8)] ^ td[3][uint8(s0)]
 		k += 4
 		s0, s1, s2, s3 = t0, t1, t2, t3
 	}

また、src/pkg/crypto/aes/aes_test.go には、ベンチマーク測定用の BenchmarkEncrypt 関数が追加されています。これは、変更によるパフォーマンス改善を定量的に評価するために導入されたものです。

--- a/src/pkg/crypto/aes/aes_test.go
+++ b/src/pkg/crypto/aes/aes_test.go
@@ -348,3 +348,17 @@ func TestCipherDecrypt(t *testing.T) {
 		}
 	}\n}\n+\n+func BenchmarkEncrypt(b *testing.B) {
+\tb.StopTimer()\n+\ttt := encryptTests[0]\n+\tc, err := NewCipher(tt.key)\n+\tif err != nil {\n+\t\tpanic("NewCipher")\n+\t}\n+\tout := make([]byte, len(tt.in))\n+\tb.StartTimer()\n+\tfor i := 0; i < b.N; i++ {\n+\t\tc.Encrypt(out, tt.in)\n+\t}\n+}\n```

## コアとなるコードの解説

変更の核心は、`block.go`内の`encryptBlock`および`decryptBlock`関数における、`te`（暗号化用S-boxテーブル）および`td`（復号用S-boxテーブル）へのインデックス計算です。

例えば、暗号化処理の以下の行を見てみましょう。

**変更前:**
`t0 = xk[k+0] ^ te[0][s0>>24] ^ te[1][s1>>16&0xff] ^ te[2][s2>>8&0xff] ^ te[3][s3&0xff]`

ここで、`s1>>16&0xff` の部分がS-boxのインデックスを計算しています。
*   `s1`は32ビットのワードであり、`>>16`で16ビット右シフトすることで、特定のバイトが最下位バイトに移動します。
*   `&0xff`は、その結果を8ビットに切り捨て、0から255の範囲に収めるためのビットマスクです。

**変更後:**
`t0 = xk[k+0] ^ te[0][uint8(s0>>24)] ^ te[1][uint8(s1>>16)] ^ te[2][uint8(s2>>8)] ^ te[3][uint8(s3)]`

変更後では、`s1>>16&0xff`が`uint8(s1>>16)`に置き換えられています。
*   Go言語では、`uint32`などの大きな整数型を`uint8`に型変換すると、自動的に上位ビットが破棄され、下位8ビットのみが保持されます。これは、`&0xff`演算と全く同じ論理的な効果を持ちます。

この変更により、以下のメリットが生まれます。
1.  **コードの簡潔性**: `&0xff`という冗長なビットマスクが不要になり、コードがより読みやすくなります。
2.  **コンパイラの最適化の促進**: Goコンパイラは、`uint8`型が0から255の範囲に限定されることを認識しています。これにより、S-boxの配列（通常256エントリ）へのアクセスにおいて、インデックスが常に有効な範囲内にあることをより容易に推論できます。その結果、コンパイラはランタイムの境界チェックを省略する最適化（bounds check elimination）を適用しやすくなり、実行時のオーバーヘッドが削減されます。

この最適化は、AESのような計算集約的なアルゴリズムにおいて、小さな改善が積み重なって大きなパフォーマンス向上につながる典型的な例です。ベンチマーク結果が示すように、約25%の高速化は、暗号処理の効率にとって非常に重要な改善と言えます。

## 関連リンク

*   Go CL (Code Review) 5450084: [https://golang.org/cl/5450084](https://golang.org/cl/5450084)

## 参考にした情報源リンク

*   Advanced Encryption Standard (AES) - Wikipedia: [https://ja.wikipedia.org/wiki/Advanced_Encryption_Standard](https://ja.wikipedia.org/wiki/Advanced_Encryption_Standard)
*   Go言語の型変換 - Go言語の公式ドキュメントやチュートリアル (具体的なURLはGoのバージョンによって異なるため、一般的な参照として記載)
*   Goコンパイラの最適化、特に境界チェックの省略に関する情報 (Goのコンパイラ設計に関するブログ記事やドキュメントを参照)