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

このコミットは、Go言語の crypto/cipher パッケージにおけるXOR操作のパフォーマンス改善を目的としています。特に、CBC、CFB、OFB、CTR、およびGCMといった主要な暗号モードにおけるXOR処理を、386およびamd64アーキテクチャ向けに最適化しています。これにより、これらの暗号モードの暗号化・復号化処理が大幅に高速化されました。

コミット

commit 5744be9fe44f77010840f52eaca1b654fd19d00d
Author: Han-Wen Nienhuys <hanwen@google.com>
Date:   Wed Dec 11 16:05:02 2013 -0500

    crypto/cipher: speed up xor operations in CBC, CFB, OBF, CTR
    and GCM on 386 and amd64
    
    Intel(R) Core(TM) i5-2540M CPU @ 2.60GHz:
    
    benchmark                    old MB/s     new MB/s  speedup
    BenchmarkAESGCMSeal1K           82.39        92.05    1.12x
    BenchmarkAESGCMOpen1K           82.28        91.88    1.12x
    BenchmarkAESCFBEncrypt1K       141.54       277.59    1.96x
    BenchmarkAESCFBDecrypt1K       133.06       278.07    2.09x
    BenchmarkAESOFB1K              160.51       380.24    2.37x
    BenchmarkAESCTR1K              164.07       429.25    2.62x
    BenchmarkAESCBCEncrypt1K       170.99       263.74    1.54x
    BenchmarkAESCBCDecrypt1K       124.96       249.14    1.99x
    
    Fixes #6741.
    
    R=agl, dave, agl
    CC=golang-dev
    https://golang.org/cl/24250044

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

https://github.com/golang/go/commit/5744be9fe44f77010840f52eaca1b654fd19d00d

元コミット内容

このコミットの元の内容は、crypto/cipher パッケージにおけるXOR操作の高速化です。特に、CBC、CFB、OFB、CTR、GCMといった暗号モードにおいて、386およびamd64アーキテクチャでのパフォーマンス向上を図っています。コミットメッセージには、具体的なベンチマーク結果が示されており、各暗号モードで1.12倍から2.62倍の速度向上が達成されたことが報告されています。

変更の背景

この変更の背景には、Go言語の暗号ライブラリにおけるパフォーマンスのボトルネックがありました。特に、ブロック暗号のモード（CBC, CFB, OFB, CTR, GCM）では、データの暗号化・復号化の過程でXOR演算が頻繁に行われます。これらのXOR演算がバイト単位で逐次的に行われる場合、CPUのレジスタ幅やキャッシュ効率を十分に活用できず、パフォーマンスが低下する可能性があります。

コミットメッセージに記載されている Fixes #6741 から、この変更がGoのIssue 6741を解決するために行われたことがわかります。Issue 6741は「crypto/cipher: speed up xor operations」というタイトルで、まさにXOR操作のパフォーマンス改善を求めるものでした。当時のGoの暗号ライブラリは、特にIntel 386やAMD64のような64ビットアーキテクチャにおいて、XOR操作が最適化されておらず、その結果として暗号化・復号化の速度が期待よりも遅いという問題が指摘されていました。

このコミットは、これらのアーキテクチャの特性を活かし、より効率的なXOR処理を導入することで、暗号処理全体の高速化を実現し、Go言語の暗号ライブラリの実用性を向上させることを目的としています。

前提知識の解説

1. ブロック暗号のモード

ブロック暗号は、固定長のブロック単位でデータを暗号化・復号化する暗号アルゴリズムです（例: AES）。しかし、実際のアプリケーションでは、任意の長さのデータを扱う必要があるため、ブロック暗号を連続的に適用するための「モード」が定義されています。このコミットで言及されているモードは以下の通りです。

• CBC (Cipher Block Chaining): 各ブロックが前のブロックの暗号文とXORされてから暗号化されるモード。連鎖的な依存関係があり、エラー伝播の特性を持つ。
• CFB (Cipher Feedback): ブロック暗号をストリーム暗号のように扱うモード。前の暗号文ブロックを暗号化し、その結果を平文とXORして暗号文を生成する。
• OFB (Output Feedback): ブロック暗号をストリーム暗号のように扱うモード。ブロック暗号の出力をフィードバックしてキーストリームを生成し、それを平文とXORする。
• CTR (Counter): ブロック暗号をストリーム暗号のように扱うモード。カウンターをブロック暗号で暗号化し、その結果をキーストリームとして平文とXORする。並列処理が可能で、高速化しやすい。
• GCM (Galois/Counter Mode): CTRモードをベースにした認証付き暗号モード。データの機密性（暗号化）と完全性・認証（改ざん検知）を同時に提供する。

これらのモードの多くは、暗号化・復号化の過程でデータのXOR演算を頻繁に利用します。

2. XOR演算とパフォーマンス

XOR（排他的論理和）演算は、ビット単位の論理演算であり、暗号化において非常に重要な役割を果たします。特にストリーム暗号やブロック暗号のモードでは、キーストリームと平文（または暗号文）をXORすることで、暗号化・復号化を行います。

CPUにおけるXOR演算のパフォーマンスは、一度に処理できるデータの量（レジスタ幅）や、メモリからのデータ読み書きの効率（アライメント、キャッシュ）に大きく依存します。

• バイト単位のXOR: 1バイトずつXOR演算を行う場合、ループ処理がオーバーヘッドとなり、CPUの持つ高速なワード単位（例: 32ビット、64ビット）での演算能力を十分に活用できません。
• ワード単位のXOR: CPUのネイティブなワードサイズ（uintptrのサイズ）に合わせて、複数のバイトをまとめて（例: 4バイトや8バイト）XOR演算を行うことで、処理速度を大幅に向上させることができます。これは、CPUが一度に多くのデータをレジスタにロードし、並列に演算できるためです。

3. unsafe パッケージとポインタ操作

Go言語の unsafe パッケージは、Goの型安全性をバイパスして、低レベルのメモリ操作を可能にするためのものです。通常、Goではポインタ演算は厳しく制限されていますが、unsafe パッケージを使用することで、C言語のようにポインタを直接操作したり、異なる型のポインタ間で変換したりすることができます。

• unsafe.Pointer: 任意の型のポインタを保持できる特殊なポインタ型。
• unsafe.Sizeof(uintptr(0)): uintptr 型のサイズ（バイト単位）を返します。uintptr は、ポインタを保持できる符号なし整数型であり、そのサイズは実行環境のアーキテクチャ（32ビットか64ビットか）に依存します。これにより、CPUのネイティブなワードサイズを取得できます。

4. runtime.GOARCH

runtime.GOARCH は、Goプログラムが実行されているターゲットアーキテクチャを示す文字列定数です（例: "amd64", "386", "arm" など）。この定数を利用することで、特定のアーキテクチャに特化したコードパスを選択することができます。このコミットでは、386 と amd64 アーキテクチャに特化した高速なXOR処理を適用するために使用されています。

5. アライメント (Alignment)

メモリのアライメントとは、データがメモリ上で特定のバイト境界に配置されることを指します。多くのCPUアーキテクチャでは、ワード単位のデータ（例: 4バイト整数、8バイト整数）がそのワードサイズと同じ境界に配置されている場合に、最も効率的にアクセスできます。アライメントされていないアドレスからの読み書きは、パフォーマンスが低下したり、一部のアーキテクチャではエラーになったりする可能性があります。

このコミットでは、supportsUnaligned というフラグが導入されており、386およびamd64アーキテクチャが非アライメントアクセスをサポートしていることを示しています。これにより、メモリ上のデータがワード境界に揃っていなくても、高速なワード単位のXOR操作を適用できる利点があります。

技術的詳細

このコミットの主要な技術的詳細は、crypto/cipher パッケージに xor.go という新しいファイルを追加し、CPUのアーキテクチャに最適化されたXOR操作を導入した点にあります。

1. xor.go の導入

新しく追加された src/pkg/crypto/cipher/xor.go ファイルには、以下の主要な関数が定義されています。

• fastXORBytes(dst, a, b []byte) int: 386およびamd64アーキテクチャのように非アライメントアクセスをサポートする環境で、ワード単位でXOR演算を高速に行う関数。unsafe パッケージを使用して []byte スライスを []uintptr スライスにキャストし、CPUのネイティブワードサイズで一括XOR演算を行います。残りのバイトはバイト単位で処理します。
• safeXORBytes(dst, a, b []byte) int: 汎用的なバイト単位のXOR演算を行う関数。アライメントやアーキテクチャに依存せず、安全に動作します。
• xorBytes(dst, a, b []byte) int: runtime.GOARCH の値に基づいて、fastXORBytes または safeXORBytes のどちらを呼び出すかを決定するラッパー関数。supportsUnaligned 定数（runtime.GOARCH == "386" || runtime.GOARCH == "amd64"）によって分岐します。
• fastXORWords(dst, a, b []byte): fastXORBytes と同様にワード単位でXORを行うが、引数が既にワードサイズの倍数であることを前提とし、残りのバイト処理を行わない。主にGCMモードで使用される。
• xorWords(dst, a, b []byte): fastXORWords と safeXORBytes を選択するラッパー関数。

2. ワード単位のXOR演算

fastXORBytes および fastXORWords 関数は、Goの unsafe パッケージを利用して、[]byte 型のスライスを []uintptr 型のスライスとして解釈します。

dw := *(*[]uintptr)(unsafe.Pointer(&dst))
aw := *(*[]uintptr)(unsafe.Pointer(&a))
bw := *(*[]uintptr)(unsafe.Pointer(&b))

これにより、バイトの配列をCPUのネイティブワード（32ビットまたは64ビット）の配列として扱うことができ、ループ内で dw[i] = aw[i] ^ bw[i] のようにワード単位でXOR演算を実行します。これは、CPUが一度に多くのビットを処理できるため、バイト単位のループよりもはるかに高速です。

wordSize は unsafe.Sizeof(uintptr(0)) で計算され、実行環境のポインタサイズ（通常、32ビットシステムでは4バイト、64ビットシステムでは8バイト）に等しくなります。これにより、コードが異なるアーキテクチャでコンパイルされても、適切なワードサイズでXOR演算が行われます。

3. バッファリングの改善 (CTR, OFB)

CTR (Counter) および OFB (Output Feedback) モードでは、キーストリームを生成し、それを平文とXORします。このコミットでは、これらのモードの XORKeyStream メソッドにおいて、キーストリームの生成とXOR演算の効率を向上させるために、内部バッファリングのロジックが変更されています。

• streamBufferSize (512バイト) という定数が導入され、キーストリームを一度に大量に生成し、バッファに格納するようになりました。
• refill() メソッドが追加され、バッファが少なくなった場合に、ブロック暗号の Encrypt メソッドを呼び出してキーストリームをまとめて生成し、バッファを補充します。
• XORKeyStream メソッドは、このバッファからキーストリームを取得し、新しく導入された xorBytes 関数を使って効率的にXOR演算を行います。

これにより、ブロック暗号の Encrypt 呼び出し回数を減らし、XOR演算をバッチ処理することで、全体的なスループットが向上します。

4. GCMモードの最適化

GCM (Galois/Counter Mode) では、counterCrypt および auth メソッド内でXOR演算が行われます。このコミットでは、これらのメソッド内のバイト単位のXORループが、新しく導入された xorWords または xorBytes 関数に置き換えられています。

• counterCrypt 内の for i := range mask { out[i] = in[i] ^ mask[i] } が xorWords(out, in, mask[:]) に変更。
• auth 内の for i := range tagMask { out[i] ^= tagMask[i] } が xorWords(out, out, tagMask[:]) に変更。

これにより、GCMモードの暗号化・復号化および認証タグ生成のパフォーマンスが向上します。

5. ベンチマークの追加

src/pkg/crypto/cipher/benchmark_test.go という新しいベンチマークファイルが追加されました。このファイルには、AESをベースとしたGCM、CFB、OFB、CTR、CBCの各モードにおける1KBデータの暗号化・復号化のベンチマーク関数が含まれています。これにより、変更前後のパフォーマンスを定量的に比較し、最適化の効果を検証できるようになりました。コミットメッセージに記載されているベンチマーク結果は、このテストによって得られたものです。

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

このコミットにおけるコアとなるコードの変更箇所は以下のファイルに集中しています。

1. src/pkg/crypto/cipher/xor.go (新規追加):

   • fastXORBytes, safeXORBytes, xorBytes 関数を定義。
   • fastXORWords, xorWords 関数を定義。
   • wordSize と supportsUnaligned 定数を定義。
   • これがXOR高速化の主要なロジックをカプセル化する。

2. src/pkg/crypto/cipher/cbc.go:

   • cbcEncrypter.CryptBlocks および cbcDecrypter.CryptBlocks 内のバイト単位のXORループを xorBytes 関数呼び出しに置き換え。
     • 例: for i := 0; i < x.blockSize; i++ { x.iv[i] ^= src[i] } が xorBytes(x.iv, x.iv, src[:x.blockSize]) に。
     • 例: for i := 0; i < x.blockSize; i++ { x.tmp[i] ^= x.iv[i] } が xorBytes(x.tmp, x.tmp, x.iv) に。
   • copy 関数を直接使用することで、バイト単位のコピーループを削除。

3. src/pkg/crypto/cipher/cfb.go:

   • cfb.XORKeyStream メソッドのロジックを大幅に変更。
   • バイト単位のループ内で xorBytes を使用するように変更。
   • 内部バッファリング (next, out, outUsed) の管理方法を変更し、より効率的なキーストリーム生成とXOR処理を可能に。
   • newCFB 関数での初期化ロジックも変更。

4. src/pkg/crypto/cipher/ctr.go:

   • ctr.XORKeyStream メソッドのロジックを大幅に変更。
   • streamBufferSize 定数を導入し、キーストリームのバッファリングを改善。
   • refill() メソッドを導入し、キーストリームの生成をバッチ処理。
   • xorBytes を使用してXOR演算を実行。

5. src/pkg/crypto/cipher/gcm.go:

   • gcm.counterCrypt および gcm.auth メソッド内のバイト単位のXORループを xorWords または xorBytes 関数呼び出しに置き換え。
     • 例: for i := range mask { out[i] = in[i] ^ mask[i] } が xorWords(out, in, mask[:]) に。

6. src/pkg/crypto/cipher/ofb.go:

   • ofb.XORKeyStream メソッドのロジックを大幅に変更。
   • streamBufferSize 定数を導入し、キーストリームのバッファリングを改善。
   • refill() メソッドを導入し、キーストリームの生成をバッチ処理。
   • xorBytes を使用してXOR演算を実行。

7. src/pkg/crypto/cipher/benchmark_test.go (新規追加):

   • 各暗号モードのパフォーマンスを測定するためのベンチマーク関数を追加。

8. src/pkg/crypto/cipher/gcm_test.go:

   • 古い BenchmarkAESGCM 関数を削除。新しい benchmark_test.go に統合されたため。

9. src/pkg/crypto/cipher/xor_test.go (新規追加):

   • xorBytes および safeXORBytes の動作を検証するためのテスト関数 TestXOR を追加。アライメントの異なる入力に対しても正しく動作することを確認。

コアとなるコードの解説

src/pkg/crypto/cipher/xor.go

このファイルは、XOR操作の最適化の中核をなします。

// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package cipher

import (
	"runtime"
	"unsafe"
)

const wordSize = int(unsafe.Sizeof(uintptr(0)))
const supportsUnaligned = runtime.GOARCH == "386" || runtime.GOARCH == "amd64"

// fastXORBytes xors in bulk. It only works on architectures that
// support unaligned read/writes.
func fastXORBytes(dst, a, b []byte) int {
	n := len(a)
	if len(b) < n {
		n = len(b)
	}

	w := n / wordSize
	if w > 0 {
		dw := *(*[]uintptr)(unsafe.Pointer(&dst))
		aw := *(*[]uintptr)(unsafe.Pointer(&a))
		bw := *(*[]uintptr)(unsafe.Pointer(&b))
		for i := 0; i < w; i++ {
			dw[i] = aw[i] ^ bw[i]
		}
	}

	for i := (n - n%wordSize); i < n; i++ {
		dst[i] = a[i] ^ b[i]
	}

	return n
}

func safeXORBytes(dst, a, b []byte) int {
	n := len(a)
	if len(b) < n {
		n = len(b)
	}
	for i := 0; i < n; i++ {
		dst[i] = a[i] ^ b[i]
	}
	return n
}

// xorBytes xors the bytes in a and b. The destination is assumed to have enough
// space. Returns the number of bytes xor'd.
func xorBytes(dst, a, b []byte) int {
	if supportsUnaligned {
		return fastXORBytes(dst, a, b)
	} else {
		// TODO(hanwen): if (dst, a, b) have common alignment
		// we could still try fastXORBytes. It is not clear
		// how often this happens, and it's only worth it if
		// the block encryption itself is hardware
		// accelerated.
		return safeXORBytes(dst, a, b)
	}
}

// fastXORWords XORs multiples of 4 or 8 bytes (depending on architecture.)
// The arguments are assumed to be of equal length.
func fastXORWords(dst, a, b []byte) {
	dw := *(*[]uintptr)(unsafe.Pointer(&dst))
	aw := *(*[]uintptr)(unsafe.Pointer(&a))
	bw := *(*[]uintptr)(unsafe.Pointer(&b))
	n := len(b) / wordSize
	for i := 0; i < n; i++ {
		dw[i] = aw[i] ^ bw[i]
	}
}

func xorWords(dst, a, b []byte) {
	if supportsUnaligned {
		fastXORWords(dst, a, b)
	} else {
		safeXORBytes(dst, a, b)
	}
}

• wordSize: uintptr のサイズ（バイト単位）を定義します。これは、CPUのネイティブなワードサイズ（32ビットまたは64ビット）に対応します。
• supportsUnaligned: runtime.GOARCH が "386" または "amd64" の場合に true となります。これらのアーキテクチャは非アライメントアクセスを効率的にサポートするため、高速なワード単位のXORが可能です。
• fastXORBytes: unsafe.Pointer を用いて []byte スライスを []uintptr スライスに変換し、ワード単位でXOR演算を行います。これにより、CPUのレジスタを最大限に活用し、一度に多くのビットを処理できます。残りのバイトは通常のバイト単位のループで処理されます。
• safeXORBytes: 汎用的なバイト単位のXOR関数で、アライメントの考慮は不要です。
• xorBytes: supportsUnaligned に基づいて fastXORBytes と safeXORBytes を切り替えるラッパーです。これにより、特定のアーキテクチャでのみ高速パスが有効になります。
• fastXORWords と xorWords: fastXORBytes と同様の原理で、ワード単位のXORを行います。こちらは主にGCMのようにブロックサイズがワードサイズの倍数である場合に利用され、残りのバイト処理は行いません。

各暗号モードの変更

各暗号モード（CBC, CFB, CTR, GCM, OFB）の XORKeyStream や CryptBlocks メソッドでは、これまでバイト単位でXORループを回していた箇所が、新しく導入された xorBytes や xorWords 関数に置き換えられています。

例: src/pkg/crypto/cipher/cbc.go の変更

変更前:

for i := 0; i < x.blockSize; i++ {
	x.iv[i] ^= src[i]
}

変更後:

xorBytes(x.iv, x.iv, src[:x.blockSize])

この変更により、Goコンパイラは xorBytes の内部でアーキテクチャに最適化された fastXORBytes を選択し、ワード単位でのXOR演算を実行できるようになります。これにより、ループのオーバーヘッドが削減され、CPUのデータ処理能力が最大限に引き出されます。

また、CTRやOFBモードでは、キーストリームの生成とXOR演算のバッファリング戦略が改善されました。これにより、ブロック暗号の Encrypt 呼び出し回数を減らし、XOR演算をより大きなチャンクで実行できるようになり、キャッシュ効率と全体的なスループットが向上します。

関連リンク

• Go Issue 6741: https://code.google.com/p/go/issues/detail?id=6741 (現在はGitHubに移行)
• Go CL 24250044: https://golang.org/cl/24250044 (Gerrit Code Review)
• Go言語 crypto/cipher パッケージのドキュメント: https://pkg.go.dev/crypto/cipher
• Go言語 unsafe パッケージのドキュメント: https://pkg.go.dev/unsafe
• Go言語 runtime パッケージのドキュメント: https://pkg.go.dev/runtime

参考にした情報源リンク

• Go言語の公式ドキュメント（crypto/cipher, unsafe, runtime パッケージ）
• Go言語のIssueトラッカー（Issue 6741）
• Go言語のGerrit Code Review (CL 24250044)
• ブロック暗号のモードに関する一般的な暗号学の資料（CBC, CFB, OFB, CTR, GCMなど）
• CPUアーキテクチャにおけるメモリのアライメントとパフォーマンスに関する資料
• XOR演算の最適化に関するプログラミング記事や論文