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

このコミットは、Go言語の標準ライブラリ crypto/sha1 パッケージにおけるSHA-1ハッシュアルゴリズムの実装を最適化するものです。具体的には、SHA-1のブロック処理において、メッセージスケジュールを「インプレース（in-place）」で計算するように変更することで、メモリ使用量を削減し、パフォーマンスを向上させています。ベンチマーク結果が示すように、この変更によりハッシュ計算の速度が大幅に改善されています。

コミット

• コミットハッシュ: f8892fb39522b3d075d134036df5d2859b3c095d
• 作者: Carl Mastrangelo notcarl@google.com
• コミット日時: 2012年11月7日 水曜日 13:41:02 +1100

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

https://github.com/golang/go/commit/f8892fb39522b3d075d134036df5d2859b3c095d

元コミット内容

crypto/sha1: Make sha-1 do block mixup in place

Benchmarks:

benchmark              old ns/op    new ns/op    delta
BenchmarkHash8Bytes          762          674  -11.55%
BenchmarkHash1K             8791         7375  -16.11%
BenchmarkHash8K            65094        54881  -15.69%

benchmark               old MB/s     new MB/s  speedup
BenchmarkHash8Bytes        10.50        11.86    1.13x
BenchmarkHash1K           116.48       138.84    1.19x
BenchmarkHash8K           125.85       149.27    1.19x

R=dave, rsc, iant
CC=golang-dev
https://golang.org/cl/6820096

変更の背景

SHA-1ハッシュアルゴリズムは、入力データを固定長のハッシュ値に変換する暗号学的ハッシュ関数です。その計算過程では、入力ブロックを拡張して80個の32ビットワード（w[0]からw[79]）を生成する「メッセージスケジュール」というステップがあります。従来のSHA-1実装では、この80個のワードを格納するためにwという配列を確保し、事前に全てのワードを計算していました。

このコミットの背景には、このメッセージスケジュールの計算方法に改善の余地があるという認識がありました。特に、SHA-1のメッセージスケジュールは、過去のいくつかのワードにのみ依存して新しいワードを生成するという特性を持っています。この特性を利用すれば、全ての80ワードを一度にメモリに保持する必要はなく、必要なワードをオンデマンドで計算し、再利用することで、メモリ使用量を削減し、キャッシュ効率を向上させ、結果としてパフォーマンスを改善できると考えられました。

ベンチマーク結果が示すように、この「インプレース」での計算への変更は、特に大きなデータブロックのハッシュ計算において顕著な速度向上（最大19%のスピードアップ）をもたらしています。これは、メモリ割り当ての削減と、CPUキャッシュの利用効率の向上によるものです。

前提知識の解説

SHA-1 (Secure Hash Algorithm 1)

SHA-1は、NIST（アメリカ国立標準技術研究所）によって開発された暗号学的ハッシュ関数の一つです。任意の長さの入力データ（メッセージ）を受け取り、160ビット（20バイト）の固定長のハッシュ値（メッセージダイジェスト）を出力します。主な用途は、データの完全性検証、デジタル署名、パスワードの保存などです。

SHA-1の基本的な処理は以下のステップで構成されます。

1. パディング: 入力メッセージを512ビット（64バイト）の倍数になるようにパディングします。
2. メッセージブロックの処理: パディングされたメッセージを512ビットのブロックに分割し、各ブロックを順番に処理します。
3. メッセージスケジュール: 各512ビットブロックは、16個の32ビットワード（w[0]からw[15]）として解釈されます。SHA-1のコアとなる圧縮関数では、これらの16ワードを基に、さらに64個のワード（w[16]からw[79]）を生成し、合計80個のワードを使用します。この生成プロセスが「メッセージスケジュール」です。
   • w[i] (for 16 <= i <= 79) は、w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16] を左に1ビットローテートした値として計算されます。
4. 圧縮関数: 80個のワードと、現在のハッシュ値（5つの32ビットレジスタA, B, C, D, E）を用いて、80回のラウンド計算を行います。各ラウンドでは、非線形関数、定数、ワード、そしてレジスタ値が組み合わされて新しいレジスタ値が計算されます。
5. ハッシュ値の更新: 各ブロックの処理後、レジスタの最終値が累積ハッシュ値に加算されます。

インプレース (In-place) 処理

プログラミングにおける「インプレース」とは、追加のメモリ領域をほとんど、あるいは全く使用せずに、既存のデータ構造内で直接操作を行うことを指します。対義語は「アウトオブプレース（out-of-place）」で、これは操作のために新しいデータ構造を作成し、結果をそこに格納することを意味します。

インプレース処理の利点は以下の通りです。

• メモリ効率: 新しいメモリ割り当てが不要なため、メモリ使用量が削減されます。これは、特に大規模なデータセットを扱う場合に重要です。
• キャッシュ効率: データが既存のメモリ位置で処理されるため、CPUキャッシュのヒット率が向上し、パフォーマンスが改善される可能性があります。
• ガベージコレクションの負荷軽減: 新しいオブジェクトの生成が少ないため、ガベージコレクタの作業が減り、アプリケーションの応答性が向上します。

SHA-1のメッセージスケジュールにおいてインプレース処理を適用するということは、80個のワード全てを格納する大きな配列を用意するのではなく、必要な16個のワードだけを保持し、残りのワードは必要に応じて計算し、その16ワードの配列を再利用（上書き）しながら処理を進めることを意味します。

技術的詳細

SHA-1のメッセージスケジュールは、w[i] = (w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]) <<< 1 という漸化式で定義されます。ここで <<< 1 は左1ビットローテートです。この式を見ると、w[i] の計算には、現在のiから16個前のワードまでしか必要ないことがわかります。つまり、常に最新の16個のワードがあれば、次のワードを計算できるのです。

従来のGo言語のSHA-1実装では、w配列を[80]uint32として宣言し、最初の16ワードを読み込んだ後、残りの64ワードを事前に計算して配列に格納していました。

var w [80]uint32
// ... 最初の16ワードの読み込み ...
for i := 16; i < 80; i++ {
    tmp := w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]
    w[i] = tmp<<1 | tmp>>(32-1)
}
// ... 80ワード全てを使ってラウンド計算 ...

このコミットでは、このアプローチを変更し、w配列のサイズを[16]uint32に削減しました。そして、80回のラウンド計算を行うメインループの中で、メッセージスケジュールの計算をインプレースで行うようにしました。

具体的には、w[i&0xf]というインデックスを使用しています。0xfは16進数で15を意味し、i&0xfはiを16で割った余りを計算するビット演算です（i % 16と同じ効果）。これにより、w配列のインデックスは常に0から15の範囲に収まります。

SHA-1の80ラウンドは、4つのフェーズ（各20ラウンド）に分かれています。

• ラウンド0-19: f = (b & c) | (^b & d)
• ラウンド20-39: f = b ^ c ^ d
• ラウンド40-59: f = (b & c) | (b & d) | (c & d) (コミットで ((b | c) & d) | (b & c) に変更)
• ラウンド60-79: f = b ^ c ^ d

変更後、各ラウンドの開始時に、必要に応じて新しいwワードを計算し、w[i&0xf]に格納します。例えば、iが16以上になった場合、w[i&0xf]はw[i-16]の役割を果たし、その位置に新しいwワードが計算されて上書きされます。これにより、常に16個のワードだけをメモリに保持し、それらを循環的に再利用しながら80ラウンドの計算を進めることが可能になります。

また、f関数の計算式が b&c | b&d | c&d から ((b | c) & d) | (b & c) に変更されています。これは論理的には等価な表現ですが、コンパイラによる最適化やCPUの命令セットによっては、後者の方が効率的なコードを生成する可能性があります。

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

変更は src/pkg/crypto/sha1/sha1block.go ファイルの block 関数内で行われています。

1. w配列のサイズ変更:

   --- a/src/pkg/crypto/sha1/sha1block.go
   +++ b/src/pkg/crypto/sha1/sha1block.go
   @@ -16,7 +16,7 @@ const (
    )
   
    func block(dig *digest, p []byte) {
   -	var w [80]uint32
   +	var w [16]uint32
   

   w配列のサイズが80から16に削減されました。

2. メッセージスケジュールの計算ロジックの変更:

   --- a/src/pkg/crypto/sha1/sha1block.go
   +++ b/src/pkg/crypto/sha1/sha1block.go
   @@ -26,42 +26,56 @@ func block(dig *digest, p []byte) {
    		j := i * 4
    		w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])
    	}
   -	for i := 16; i < 80; i++ {
   -		tmp := w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]
   -		w[i] = tmp<<1 | tmp>>(32-1)
   -	}
   
    	a, b, c, d, e := h0, h1, h2, h3, h4
   
    	// Each of the four 20-iteration rounds
    	// differs only in the computation of f and
    	// the choice of K (_K0, _K1, etc).
   -	for i := 0; i < 20; i++ {
   +	i := 0
   +	for ; i < 16; i++ {
   +		f := b&c | (^b)&d
   +		a5 := a<<5 | a>>(32-5)
   +		b30 := b<<30 | b>>(32-30)
   +		t := a5 + f + e + w[i&0xf] + _K0
   +		a, b, c, d, e = t, a, b30, c, d
   +	}
   +	for ; i < 20; i++ {
   +		tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
   +		w[i&0xf] = tmp<<1 | tmp>>(32-1)
   +
    		f := b&c | (^b)&d
    		a5 := a<<5 | a>>(32-5)
    		b30 := b<<30 | b>>(32-30)
   -		t := a5 + f + e + w[i] + _K0
   +		t := a5 + f + e + w[i&0xf] + _K0
    		a, b, c, d, e = t, a, b30, c, d
    	}
   -	for i := 20; i < 40; i++ {
   +	for ; i < 40; i++ {
   +		tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
   +		w[i&0xf] = tmp<<1 | tmp>>(32-1)
    		f := b ^ c ^ d
    		a5 := a<<5 | a>>(32-5)
    		b30 := b<<30 | b>>(32-30)
   -		t := a5 + f + e + w[i] + _K1
   +		t := a5 + f + e + w[i&0xf] + _K1
    		a, b, c, d, e = t, a, b30, c, d
    	}
   -	for i := 40; i < 60; i++ {
   -		f := b&c | b&d | c&d
   +	for ; i < 60; i++ {
   +		tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
   +		w[i&0xf] = tmp<<1 | tmp>>(32-1)
   +		f := ((b | c) & d) | (b & c)
   +
    		a5 := a<<5 | a>>(32-5)
    		b30 := b<<30 | b>>(32-30)
   -		t := a5 + f + e + w[i] + _K2
   +		t := a5 + f + e + w[i&0xf] + _K2
    		a, b, c, d, e = t, a, b30, c, d
    	}
   -	for i := 60; i < 80; i++ {
   +	for ; i < 80; i++ {
   +		tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
   +		w[i&0xf] = tmp<<1 | tmp>>(32-1)
    		f := b ^ c ^ d
    		a5 := a<<5 | a>>(32-5)
    		b30 := b<<30 | b>>(32-30)
   -		t := a5 + f + e + w[i] + _K3
   +		t := a5 + f + e + w[i&0xf] + _K3
    		a, b, c, d, e = t, a, b30, c, d
    	}
   

   • for i := 16; i < 80; i++ のループが削除されました。
   • 各ラウンドのループ（for ; i < 20; i++ など）の内部で、tmpの計算とw[i&0xf]への代入が行われるようになりました。
   • w[i] の代わりに w[i&0xf] が使用されるようになりました。
   • ラウンド40-59のf関数の計算式が変更されました。

コアとなるコードの解説

block関数は、SHA-1の圧縮関数の中心的な部分であり、512ビットの入力ブロックを処理してハッシュ値を更新します。

変更前のコードでは、まず入力ブロックから最初の16個のワードをw[0]からw[15]に読み込み、その後、for i := 16; i < 80; i++ のループで残りの64個のワードをw配列の適切な位置に計算して格納していました。これにより、80個全てのワードがメモリ上に存在した状態で、その後の80回のラウンド計算が行われていました。

変更後のコードでは、w配列のサイズが[16]uint32に縮小されました。最初の16個のワードの読み込みは変わりませんが、その後の64個のワードを事前に計算して格納するループはなくなりました。

代わりに、80回のラウンド計算を行うメインループ（for ; i < 20; i++、for ; i < 40; i++ など）の内部で、メッセージスケジュールの計算がインプレースで行われるようになりました。

• i := 0 から i < 16 のループ: この最初の16ラウンドでは、入力ブロックから直接読み込まれたw[0]からw[15]のワードが使用されます。w[i&0xf]は単にw[i]と同じです。
• i := 16 から i < 80 のループ: この範囲のラウンドでは、各ラウンドの開始時に以下の行が追加されました。

  tmp := w[(i-3)&0xf] ^ w[(i-8)&0xf] ^ w[(i-14)&0xf] ^ w[(i)&0xf]
  w[i&0xf] = tmp<<1 | tmp>>(32-1)
  

  このコードは、SHA-1のメッセージスケジュールの漸化式を実装しています。w[(i-3)&0xf]のように&0xfを使用することで、w配列のインデックスが常に0から15の範囲に収まるようにしています。例えば、i=16の場合、w[(16-16)&0xf]はw[0]を指し、w[(16-14)&0xf]はw[2]を指す、といった具合です。これにより、新しいwワードが計算され、w配列内の古いワードが上書きされます。この上書きされる位置は、その後の計算で必要とされない最も古いワードの位置になります。

この変更により、w配列は常に最新の16個のワードのみを保持し、それらを循環バッファのように再利用しながら、必要なワードをオンデマンドで計算するようになりました。これにより、メモリ使用量が大幅に削減され、CPUキャッシュの利用効率が向上し、結果としてベンチマークで示されたパフォーマンス改善が実現されました。

ラウンド40-59におけるf関数の変更 f := ((b | c) & d) | (b & c) は、論理的には f := b&c | b&d | c&d と等価です。これは、b, c, d のうち少なくとも2つが真であれば真となる多数決関数です。この変更は、特定のCPUアーキテクチャやコンパイラの最適化において、より効率的なビット演算命令に変換される可能性を考慮したものと考えられます。

関連リンク

• Go CL 6820096: https://golang.org/cl/6820096

参考にした情報源リンク

• Secure Hash Algorithm 1 (SHA-1): https://en.wikipedia.org/wiki/SHA-1
• SHA-1 Algorithm Explained: https://www.rfc-editor.org/rfc/rfc3174 (RFC 3174 - US Secure Hash Algorithm 1 (SHA1))
• In-place algorithm: https://en.wikipedia.org/wiki/In-place_algorithm