[インデックス 18182] ファイルの概要
このコミットは、Go言語のcrypto/sha512パッケージにおけるSHA-512ハッシュアルゴリズムのブロック処理を、AMD64アーキテクチャ向けのアセンブリ言語で実装することで、パフォーマンスを大幅に向上させるものです。特に、Intel Xeon X5650 CPUでのベンチマーク結果が示されており、最大で2倍以上の速度向上が達成されています。
コミット
commit 0a37002367502fc24d7753e360954da290ffb71a
Author: Joel Sing <jsing@google.com>
Date: Tue Jan 7 23:16:46 2014 +1100
crypto/sha512: block implementation in amd64 assembly
Benchmark on Intel(R) Xeon(R) CPU X5650 @ 2.67GHz
benchmark old ns/op new ns/op delta
BenchmarkHash8Bytes 1779 1114 -37.38%
BenchmarkHash1K 9848 4894 -50.30%
BenchmarkHash8K 68513 32187 -53.02%
benchmark old MB/s new MB/s speedup
BenchmarkHash8Bytes 4.50 7.18 1.60x
BenchmarkHash1K 103.97 209.19 2.01x
BenchmarkHash8K 119.57 254.51 2.13x
R=agl
CC=golang-codereviews
https://golang.org/cl/37150044
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/0a37002367502fc24d7753e360954da290ffb71a
元コミット内容
このコミットの目的は、Go言語のcrypto/sha512パッケージにおけるSHA-512ハッシュ関数のブロック処理部分を、AMD64アーキテクチャ向けのアセンブリ言語で最適化することです。これにより、純粋なGo言語実装と比較して、ハッシュ計算のパフォーマンスが大幅に向上しました。コミットメッセージには、Intel Xeon X5650 CPUでの具体的なベンチマーク結果が示されており、特に大きなデータサイズ（8KB）でのハッシュ計算において、処理時間が約53%短縮され、スループットが2.13倍に向上したことが報告されています。
変更の背景
暗号学的ハッシュ関数は、データの完全性検証、デジタル署名、パスワードストレージなど、多くのセキュリティ関連アプリケーションで不可欠な要素です。SHA-512は、NISTによって標準化されたセキュアハッシュアルゴリズムの一つであり、512ビットのハッシュ値を生成します。これらのハッシュ関数は、大量のデータを処理する際に計算コストが高くなる傾向があります。
Go言語の標準ライブラリにおける暗号関数のパフォーマンスは、Goアプリケーション全体の性能に直接影響します。特に、ネットワーク通信やファイルI/Oなど、データ処理が頻繁に行われる場面では、ハッシュ計算のボトルネックが顕在化することがあります。
このコミットの背景には、Go言語の暗号ライブラリの性能を向上させ、より高速なデータ処理を可能にしたいという明確な動機があります。Go言語はクロスプラットフォーム対応を重視していますが、特定のアーキテクチャ（この場合はAMD64）に特化したアセンブリ実装を提供することで、そのアーキテクチャ上での実行時に最大限のパフォーマンスを引き出すことができます。これにより、Go言語がより広範な高性能アプリケーションで利用される基盤が強化されます。
前提知識の解説
SHA-512 (Secure Hash Algorithm 512)
SHA-512は、NIST (National Institute of Standards and Technology) によってFIPS 180-4として標準化された暗号学的ハッシュ関数です。入力された任意の長さのデータから、512ビット（64バイト）の固定長のハッシュ値（メッセージダイジェスト）を生成します。主な特徴は以下の通りです。
- 一方向性: ハッシュ値から元のデータを復元することは計算上困難です。
- 衝突耐性: 異なる入力から同じハッシュ値が生成されること（衝突）は計算上困難です。
- 雪崩効果: 入力データのごくわずかな変更でも、ハッシュ値が大きく変化します。
SHA-512の処理は、主に以下のステップで構成されます。
- パディング: 入力メッセージを512ビットの倍数にパディングします。
- メッセージブロックの処理: パディングされたメッセージを1024ビット（128バイト）のブロックに分割し、各ブロックを順次処理します。
- 圧縮関数: 各1024ビットブロックは、80ラウンドの処理を行う圧縮関数に入力されます。この関数は、8つの64ビットワード（H0からH7）からなる内部状態を更新します。
- メッセージスケジュール: 1024ビットの入力ブロックから、80ラウンドで使用される80個の64ビットワード（Wt）を生成します。最初の16ワードは入力ブロックから直接導出され、残りの64ワードは複雑なビット演算（右回転、右シフト、XOR、加算）によって前のワードから生成されます。
- ラウンド関数: 各ラウンドでは、現在の内部状態（a, b, c, d, e, f, g, h）と、メッセージスケジュールから得られたWt、そしてラウンド定数Ktを用いて、新しい内部状態を計算します。この計算には、以下の非線形関数が使用されます。
Ch(x, y, z) = (x AND y) XOR (NOT x AND z)(Choose function)Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)(Majority function)Σ0(x)(Big Sigma 0): 64ビットワードxに対するビット演算（右回転、右シフト、XOR）Σ1(x)(Big Sigma 1): 64ビットワードxに対するビット演算（右回転、右シフト、XOR）
- 最終ハッシュ値: 全てのメッセージブロックが処理された後、最終的な内部状態がハッシュ値となります。
Go言語のアセンブリ
Go言語は、一部のパフォーマンスクリティカルな部分でアセンブリ言語を使用することをサポートしています。Goのアセンブリは、一般的なアセンブリ言語とは異なる独自の構文（Plan 9アセンブラの構文）を持っています。これは、Goコンパイラが生成する中間表現と密接に連携するように設計されており、レジスタの割り当てやスタックフレームの管理など、Goランタイムとの統合が容易になっています。
Goアセンブリの主な特徴は以下の通りです。
- 擬似レジスタ:
FP(Frame Pointer),SP(Stack Pointer),SB(Static Base) などの擬似レジスタを使用します。これらは実際のCPUレジスタとは異なり、メモリ上の位置を示します。 - 関数宣言:
TEXTディレクティブで関数を宣言し、SBを基準としたオフセットでグローバルシンボルを参照します。 - レジスタの利用: x86-64アーキテクチャでは、
AX,BX,CX,DX,SI,DI,BP,SP,R8からR15までの汎用レジスタが利用可能です。 go:noescape: このディレクティブは、関数がポインタをヒープにエスケープさせないことをコンパイラに伝えます。これにより、スタック割り当てが可能になり、ガベージコレクションのオーバーヘッドを削減できます。
アセンブリ言語を使用する主な理由は、Goコンパイラが生成するコードよりもさらに細粒度な最適化を行い、特定のCPU命令（例: ビット操作、SIMD命令）を最大限に活用して、パフォーマンスを極限まで引き出すためです。
技術的詳細
このコミットの核となる技術的詳細は、SHA-512の圧縮関数をAMD64アセンブリで効率的に実装した点にあります。SHA-512は64ビットワードを扱うため、AMD64の64ビットレジスタを直接利用できるアセンブリは、Go言語の純粋な実装よりも高いパフォーマンスを発揮する可能性を秘めています。
SHA-512アルゴリズムの再確認
SHA-512の圧縮関数は、80ラウンドのループで構成されます。各ラウンドでは、以下の計算が行われます。
-
メッセージスケジュール (Wt):
Wt = Mt(0 <= t <= 15): 最初の16ワードは入力メッセージブロックから直接取得されます。Wt = SIGMA1(Wt-2) + Wt-7 + SIGMA0(Wt-15) + Wt-16(16 <= t <= 79): 残りの64ワードは、以前のワードから導出されます。ここで、SIGMA0とSIGMA1は特定のビット回転とシフト操作を含む関数です。
-
ラウンド計算:
T1 = h + BIGSIGMA1(e) + Ch(e,f,g) + Kt + WtT2 = BIGSIGMA0(a) + Maj(a,b,c)h = gg = ff = ee = d + T1d = cc = bb = aa = T1 + T2
これらの計算は、8つの内部状態変数（a, b, c, d, e, f, g, h）を更新します。
アセンブリ実装の最適化ポイント
sha512block_amd64.sファイルでは、上記のアルゴリズムをAMD64の命令セットにマッピングしています。主な最適化戦略は以下の通りです。
-
レジスタの最大限の活用: SHA-512の8つの内部状態変数（a-h）は、AMD64の汎用レジスタ（R8-R15）に割り当てられています。これにより、メモリへのアクセスを最小限に抑え、CPUのレジスタを直接操作することで高速な計算を実現しています。
R8= a,R9= b,R10= c,R11= d,R12= e,R13= f,R14= g,R15= h
-
マクロの利用: SHA-512のメッセージスケジュールとラウンド計算は、繰り返し行われる定型的な処理です。アセンブリコードでは、これらの処理を
MSGSCHEDULE0,MSGSCHEDULE1,SHA512T1,SHA512T2,SHA512ROUNDなどのマクロとして定義し、コードの可読性と再利用性を高めています。これらのマクロは、特定のレジスタ（AX,CX,DX,DI,BXなど）を一時的に使用して計算を行います。 -
ビット操作命令の直接利用: SHA-512の
SIGMA関数やCh,Maj関数は、ビット単位のAND, OR, XOR, NOT, 回転 (RORQ), シフト (SHRQ) などの操作を多用します。アセンブリでは、これらの操作をCPUのネイティブ命令（ANDQ,XORQ,NOTQ,RORQ,SHRQ）で直接実行できるため、Go言語のコードでこれらの操作をエミュレートするよりもはるかに高速です。特に、RORQ(Rotate Right) 命令は、Go言語では複数のシフトとOR操作の組み合わせで実現する必要があるため、アセンブリの優位性が際立ちます。 -
データロードとストアの最適化: メッセージブロックのワード（Wt）は、スタック上のメッセージスケジュール領域（
BPをベースとする）に格納され、必要に応じてレジスタにロードされます。BSWAPQ命令は、バイトオーダーの変換（ビッグエンディアンからリトルエンディアン、またはその逆）を効率的に行い、データの準備を高速化します。 -
ループ処理の効率化: 複数のメッセージブロックを処理するために、
loopラベルとJMP命令を使用してループが実装されています。各ブロックの処理後、入力ポインタSIが128バイト（1024ビット）進められ、次のブロックが処理されます。
+build !amd64 と +build 386 amd64
src/pkg/crypto/sha512/sha512block.goに追加された// +build !amd64は、このGoファイルがAMD64アーキテクチャ以外の場合にのみコンパイルされることを意味します。つまり、AMD64環境では、このGoファイル内のblock関数はコンパイルされず、代わりにアセンブリ実装が使用されます。src/pkg/crypto/sha512/sha512block_decl.goに追加された// +build 386 amd64は、このファイルが386およびAMD64アーキテクチャでコンパイルされることを意味します。このファイルは、アセンブリで実装されたblock関数のGo言語側の宣言（シグネチャ）を提供し、Goコンパイラがアセンブリ関数を呼び出せるようにします。//go:noescapeディレクティブは、この関数がポインタをヒープにエスケープさせないことをコンパイラに伝え、最適化を助けます。
これらのビルドタグと宣言ファイルにより、Goのビルドシステムは、ターゲットアーキテクチャに応じて最適な実装（純粋なGoまたはアセンブリ）を自動的に選択できるようになります。
コアとなるコードの変更箇所
このコミットによる主要なコード変更は、以下の3つのファイルにわたります。
-
src/pkg/crypto/sha512/sha512block.go:- 既存のGo言語による
block関数の実装ファイルに、// +build !amd64というビルドタグが追加されました。 - これにより、AMD64アーキテクチャでビルドする際には、このファイルはコンパイル対象から外され、後述のアセンブリ実装が優先的に使用されるようになります。
- 既存のGo言語による
-
src/pkg/crypto/sha512/sha512block_amd64.s:- このコミットで新規に追加されたファイルです。
- SHA-512ハッシュアルゴリズムのブロック処理（圧縮関数）が、AMD64アーキテクチャ向けのアセンブリ言語（GoのPlan 9アセンブラ構文）で記述されています。
- SHA-512のメッセージスケジュールと80ラウンドの計算ロジックが、レジスタを最大限に活用し、CPUのネイティブビット操作命令（
RORQ,SHRQ,ANDQ,XORQなど）を直接使用して実装されています。 MSGSCHEDULE0,MSGSCHEDULE1,SHA512T1,SHA512T2,SHA512ROUNDなどのマクロが定義され、コードの構造化と再利用が図られています。
-
src/pkg/crypto/sha512/sha512block_decl.go:- このコミットで新規に追加されたファイルです。
// +build 386 amd64というビルドタグが追加されており、32ビットおよび64ビットのx86系アーキテクチャでコンパイルされることを示します。func block(dig *digest, p []byte)というGo言語の関数シグネチャが宣言されています。//go:noescapeディレクティブが付与されており、この関数がヒープにポインタをエスケープさせないことをコンパイラに伝えます。- このファイルは、Go言語のコードがアセンブリで実装された
block関数を型安全に呼び出すためのインターフェースを提供します。
これらの変更により、Goのビルドシステムは、AMD64環境ではアセンブリ実装を、それ以外の環境では既存のGo言語実装を自動的に選択するようになります。
コアとなるコードの解説
src/pkg/crypto/sha512/sha512block_amd64.sがこのコミットの核心です。以下にその主要部分を解説します。
関数エントリと初期化
TEXT ·block(SB),0,$648-24
MOVQ p_base+8(FP), SI
MOVQ p_len+16(FP), DX
SHRQ $7, DX
SHLQ $7, DX
LEAQ (SI)(DX*1), DI
MOVQ DI, 640(SP)
CMPQ SI, DI
JEQ end
MOVQ dig+0(FP), BP
MOVQ (0*8)(BP), R8 // a = H0
MOVQ (1*8)(BP), R9 // b = H1
MOVQ (2*8)(BP), R10 // c = H2
MOVQ (3*8)(BP), R11 // d = H3
MOVQ (4*8)(BP), R12 // e = H4
MOVQ (5*8)(BP), R13 // f = H5
MOVQ (6*8)(BP), R14 // g = H6
MOVQ (7*8)(BP), R15 // h = H7
TEXT ·block(SB),0,$648-24:block関数の宣言。SBは静的ベースレジスタで、グローバルシンボルを参照します。$648-24はスタックフレームサイズを示します。p_base+8(FP): 入力バイトスライスpのデータポインタをSIレジスタにロードします。FPはフレームポインタで、引数へのオフセットを示します。p_len+16(FP):pの長さをDXにロードし、メッセージブロックの数（128バイト単位）を計算します。dig+0(FP), BP: ダイジェスト構造体digのポインタをBPレジスタにロードします。これは、SHA-512の内部状態（H0-H7）が格納されている場所です。MOVQ (X*8)(BP), R_:BPをベースとして、ダイジェストの各64ビットワード（H0-H7）をR8からR15までの汎用レジスタにロードします。これらのレジスタが、SHA-512の内部状態変数aからhに対応します。
メッセージスケジュールとラウンド計算のマクロ
アセンブリコードでは、SHA-512の複雑な計算を簡潔に記述するためにマクロが多用されています。
MSGSCHEDULE0(index)
最初の16ワード（Wt, t=0..15）のメッセージスケジュールを処理します。
#define MSGSCHEDULE0(index) \
MOVQ (index*8)(SI), AX; \
BSWAPQ AX; \
MOVQ AX, (index*8)(BP)
MOVQ (index*8)(SI), AX: 入力メッセージブロックからindex番目の64ビットワードをAXにロードします。BSWAPQ AX: バイトオーダーをスワップします。SHA-512はビッグエンディアンで定義されていますが、x86-64はリトルエンディアンであるため、この変換が必要です。MOVQ AX, (index*8)(BP): 変換されたワードをスタック上のメッセージスケジュール領域に格納します。ここでBPは一時的にメッセージスケジュール領域のベースとして使われます。
MSGSCHEDULE1(index)
残りの64ワード（Wt, t=16..79）のメッセージスケジュールを処理します。
#define MSGSCHEDULE1(index) \
MOVQ ((index-2)*8)(BP), AX; \
MOVQ AX, CX; \
RORQ $19, AX; \
MOVQ CX, DX; \
RORQ $61, CX; \
XORQ CX, AX; \
SHRQ $6, DX; \
MOVQ ((index-15)*8)(BP), BX; \
XORQ DX, AX; \
MOVQ BX, CX; \
RORQ $1, BX; \
MOVQ CX, DX; \
SHRQ $7, DX; \
RORQ $8, CX; \
ADDQ ((index-7)*8)(BP), AX; \
XORQ CX, BX; \
XORQ DX, BX; \
ADDQ ((index-16)*8)(BP), BX; \
ADDQ BX, AX; \
MOVQ AX, ((index)*8)(BP)
このマクロは、Wt = SIGMA1(Wt-2) + Wt-7 + SIGMA0(Wt-15) + Wt-16の計算を直接アセンブリ命令に展開します。RORQ (Rotate Right Quadword) やSHRQ (Shift Right Quadword) 命令が、Go言語では複数の操作を必要とするビット回転・シフトを単一命令で実行できるため、効率的です。
SHA512T1(const, e, f, g, h)
ラウンド計算におけるT1の計算を行います。
T1 = h + BIGSIGMA1(e) + Ch(e,f,g) + Kt + Wt
#define SHA512T1(const, e, f, g, h) \
MOVQ $const, DX; \
ADDQ AX, h; \
MOVQ e, AX; \
ADDQ DX, h; \
MOVQ e, CX; \
RORQ $14, AX; \
MOVQ e, DX; \
RORQ $18, CX; \
XORQ CX, AX; \
MOVQ e, CX; \
RORQ $41, DX; \
ANDQ f, CX; \
XORQ AX, DX; \
MOVQ e, AX; \
NOTQ AX; \
ADDQ DX, h; \
ANDQ g, AX; \
XORQ CX, AX; \
ADDQ h, AX
このマクロは、BIGSIGMA1(e)とCh(e,f,g)の計算を、AX, CX, DXレジスタを一時的に使用して行います。constはラウンド定数Ktです。
SHA512T2(a, b, c)
ラウンド計算におけるT2の計算を行います。
T2 = BIGSIGMA0(a) + Maj(a,b,c)
#define SHA512T2(a, b, c) \
MOVQ a, DI; \
MOVQ c, BX; \
RORQ $28, DI; \
MOVQ a, DX; \
ANDQ b, BX; \
RORQ $34, DX; \
MOVQ a, CX; \
ANDQ c, CX; \
XORQ DX, DI; \
XORQ CX, BX; \
MOVQ a, DX; \
MOVQ b, CX; \
RORQ $39, DX; \
ANDQ a, CX; \
XORQ CX, BX; \
XORQ DX, DI; \
ADDQ DI, BX
このマクロは、BIGSIGMA0(a)とMaj(a,b,c)の計算を、BX, CX, DX, DIレジスタを一時的に使用して行います。
SHA512ROUND(index, const, a, b, c, d, e, f, g, h)
単一のSHA-512ラウンドの計算を行います。
#define SHA512ROUND(index, const, a, b, c, d, e, f, g, h) \
SHA512T1(const, e, f, g, h); \
SHA512T2(a, b, c); \
MOVQ BX, h; \
ADDQ AX, d; \
ADDQ AX, h
このマクロは、T1とT2を計算し、それらを使って内部状態変数aからhを更新します。
メインループ
loop:
MOVQ SP, BP // message schedule
// SHA512ROUND0 for t = 0 to 15
SHA512ROUND0(0, 0x428a2f98d728ae22, R8, R9, R10, R11, R12, R13, R14, R15)
// ... (省略) ...
SHA512ROUND0(15, 0xc19bf174cf692694, R9, R10, R11, R12, R13, R14, R15, R8)
// SHA512ROUND1 for t = 16 to 79
SHA512ROUND1(16, 0xe49b69c19ef14ad2, R8, R9, R10, R11, R12, R13, R14, R15)
// ... (省略) ...
SHA512ROUND1(79, 0x6c44198c4a475817, R9, R10, R11, R12, R13, R14, R15, R8)
MOVQ dig+0(FP), BP
ADDQ (0*8)(BP), R8 // H0 = a + H0
MOVQ R8, (0*8)(BP)
// ... (省略) ...
ADDQ (7*8)(BP), R15 // H7 = h + H7
MOVQ R15, (7*8)(BP)
ADDQ $128, SI
CMPQ SI, 640(SP)
JB loop
end:
RET
MOVQ SP, BP: メッセージスケジュールを格納するために、スタックポインタSPをBPにコピーします。SHA512ROUND0とSHA512ROUND1の呼び出し: 80ラウンドの計算が、それぞれのラウンド定数Ktと内部状態レジスタを引数としてマクロ呼び出しによって展開されます。各ラウンドでレジスタのローテーションが行われるため、引数のレジスタの順番が変化している点に注目してください。ADDQ (X*8)(BP), R_: 80ラウンドの計算が終了した後、最終的な内部状態レジスタ（R8からR15）の値を、元のダイジェスト状態（BPをベースとするメモリ上のH0-H7）に加算します。これはSHA-512の仕様の一部です。ADDQ $128, SI: 入力メッセージポインタSIを128バイト（1ブロック）進めます。CMPQ SI, 640(SP)とJB loop: 全てのメッセージブロックが処理されるまでループを続けます。640(SP)は、処理すべきメッセージの終端アドレスが格納されている場所です。RET: 関数からリターンします。
このアセンブリ実装は、SHA-512の計算ロジックをCPUのネイティブ命令に直接マッピングすることで、Go言語の純粋な実装では避けられないオーバーヘッド（例: 関数呼び出し、メモリアクセス、ビット操作のエミュレーション）を排除し、大幅なパフォーマンス向上を実現しています。
関連リンク
- Go言語の暗号パッケージ: https://pkg.go.dev/crypto
- SHA-512のFIPS標準 (FIPS 180-4): https://csrc.nist.gov/publications/detail/fips/180/4/archive/2012-03-06
- Go言語のアセンブリに関するドキュメント:
- Go Assembly Language (by Rob Pike): https://go.dev/doc/asm
- A Quick Guide to Go's Assembler: https://go.dev/doc/articles/go_assembler.html
参考にした情報源リンク
- FIPS PUB 180-4: Secure Hash Standard (SHS) - SHA-512アルゴリズムの公式仕様。
- Go言語の公式ドキュメントおよびソースコード。
- x86-64 Instruction Set Architecture (ISA) リファレンス。
- 暗号学的ハッシュ関数の実装に関する一般的な知識。
- Go言語のアセンブリに関するコミュニティの議論や解説記事。