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

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

このコミットは、Go言語のcrypto/rc4パッケージにARMアーキテクチャ向けのRC4暗号のネイティブアセンブリ実装を追加するものです。これにより、ARMプロセッサ上でのRC4のパフォーマンスが大幅に向上します。

コミット

commit 80e1cf73eb673b352a7888141c42ab9ab16488df
Author: Shenghou Ma <minux.ma@gmail.com>
Date:   Thu Feb 7 18:54:21 2013 +0800

    crypto/rc4: naïve ARM assembly implementation

    On 800MHz Cortex-A8:
    benchmark           old ns/op    new ns/op    delta
    BenchmarkRC4_128         9395         2838  -69.79%
    BenchmarkRC4_1K         74497        22120  -70.31%
    BenchmarkRC4_8K        587243       171435  -70.81%

    benchmark            old MB/s     new MB/s  speedup
    BenchmarkRC4_128        13.62        45.09    3.31x
    BenchmarkRC4_1K         13.75        46.29    3.37x
    BenchmarkRC4_8K         13.79        47.22    3.42x

    Result for "OpenSSL 1.0.1c 10 May 2012" from Debian/armhf sid:
    type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
    rc4              39553.81k    46522.39k    49336.11k    50085.63k    50258.06k

    R=golang-dev, agl, dave
    CC=golang-dev
    https://golang.org/cl/7310051

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

https://github.com/golang/go/commit/80e1cf73eb673b352a7888141c42ab9ab16488df

元コミット内容

このコミットは、Go言語のcrypto/rc4パッケージにARMアーキテクチャ向けのRC4暗号のネイティブアセンブリ実装を追加します。これにより、800MHz Cortex-A8プロセッサ上でRC4のベンチマークが約70%高速化され、スループットが3.3倍以上向上したことが報告されています。OpenSSLのRC4ベンチマーク結果も比較のために示されています。

変更の背景

Go言語はクロスプラットフォーム対応を重視しており、様々なアーキテクチャで効率的に動作することが求められます。特にモバイルデバイスや組み込みシステムで広く利用されているARMアーキテクチャにおいて、暗号処理のような計算負荷の高い操作のパフォーマンスは非常に重要です。

RC4はストリーム暗号の一種であり、その特性上、バイト単位の操作が頻繁に発生します。Go言語の標準ライブラリにおけるRC4の実装は、通常、ポータビリティのためにGo言語で記述されたリファレンス実装（純粋なGoコード）が提供されます。しかし、特定のアーキテクチャ（この場合はARM）において、Go言語のコンパイラが生成するコードよりも、そのアーキテクチャの命令セットに最適化されたアセンブリコードの方が、より高いパフォーマンスを発揮できる場合があります。

このコミットの背景には、ARMプロセッサ上でのRC4暗号化/復号化のボトルネックを解消し、全体的なシステムパフォーマンスを向上させるという目的があります。特に、モバイル環境などリソースが限られた環境では、このような低レベルの最適化がアプリケーションの応答性やバッテリー寿命に大きな影響を与える可能性があります。

前提知識の解説

RC4 (Rivest Cipher 4)

RC4は、Ron Rivestによって開発されたストリーム暗号です。非常にシンプルで高速なことで知られており、かつてはSSL/TLSやWEPなどの多くのプロトコルで広く利用されていました。しかし、いくつかの脆弱性が発見されたため、現在では推奨されていません。

RC4の動作原理は以下の2つのフェーズに分けられます。

  1. 鍵スケジューリングアルゴリズム (KSA: Key-Scheduling Algorithm):

    • 256バイトのS-box（状態配列）を初期化します。S-boxは0から255までの順列で初期化されます。
    • 与えられた秘密鍵を使ってS-boxをシャッフルします。このシャッフルは、S-boxの各要素を鍵のバイトと組み合わせて交換することで行われます。

  2. 擬似乱数生成アルゴリズム (PRGA: Pseudo-Random Generation Algorithm):

    • KSAで初期化されたS-boxと、2つのポインタiとj（初期値は0）を使用します。
    • 各ステップで、iをインクリメントし、jをj + S[i]で更新します（いずれも256のモジュロ演算）。
    • S[i]とS[j]の値を交換します。
    • t = (S[i] + S[j]) mod 256を計算し、S[t]の値をキーストリームのバイトとして出力します。
    • このキーストリームのバイトは、平文のバイトとXOR演算されることで暗号化（または復号化）されます。

RC4のシンプルさと高速性は、そのバイト単位の操作と、比較的少ないレジスタとメモリ操作で実現されることに起因します。

ARMアセンブリ言語

ARM（Advanced RISC Machine）は、モバイルデバイス、組み込みシステム、IoTデバイスなどで広く使用されているRISC（Reduced Instruction Set Computer）アーキテクチャです。ARMプロセッサは、電力効率と性能のバランスが優れていることで知られています。

ARMアセンブリ言語は、ARMプロセッサのネイティブ命令セットを直接操作するための低レベル言語です。Go言語のような高水準言語で書かれたコードは、コンパイラによって最終的にアセンブリ言語に変換され、実行可能な機械語になります。

アセンブリ言語でコードを記述する主な理由は、特定の処理において最大限のパフォーマンスを引き出すためです。これは、コンパイラが生成する汎用的なコードよりも、プロセッサのアーキテクチャ特性（レジスタの利用、パイプライン処理、キャッシュの挙動など）を直接考慮した手書きのアセンブリコードの方が、より効率的な命令シーケンスを生成できる場合があるためです。

このコミットでは、Go言語のcrypto/rc4パッケージのxorKeyStream関数がARMアセンブリで再実装されています。これは、RC4のPRGAフェーズにおけるバイト操作とXOR演算を、ARMプロセッサの命令セットに最適化することで、処理速度を向上させることを目的としています。

ARMアセンブリの基本的な命令には以下のようなものがあります。

  • MOVW: レジスタに即値または別のレジスタの値を移動します。
  • ADD: 加算を行います。
  • AND: ビット単位のAND演算を行います。
  • MOVBU: メモリからバイトを符号なしでレジスタにロードします。
  • MOVB: レジスタのバイトをメモリにストアします。
  • EOR: ビット単位のXOR演算を行います。
  • CMP: 2つの値を比較し、フラグを設定します。
  • BNE: 比較結果に基づいて条件分岐します（Not Equalの場合に分岐）。
  • TEXT: 関数の開始を宣言します。
  • RET: 関数から戻ります。

Go言語のアセンブリは、Plan 9アセンブラの文法に基づいています。これは一般的なGAS (GNU Assembler) 構文とは異なる点があります。例えば、レジスタの表記（R(dst)など）、メモリ参照の構文（R(i)<<0(R(state))など）が特徴的です。

ビルドタグ (+build)

Go言語のソースファイルには、ファイルの先頭に+buildディレクティブを記述することで、特定のビルド条件を指定できます。これは、異なるオペレーティングシステムやアーキテクチャ、または特定の機能が有効な場合にのみ、そのファイルをコンパイルに含めるために使用されます。

  • // +build amd64 arm: このタグが付いたファイルは、amd64またはarmアーキテクチャ向けにビルドされる場合にのみコンパイルされます。
  • // +build !amd64,!arm: このタグが付いたファイルは、amd64でもarmでもないアーキテクチャ向けにビルドされる場合にのみコンパイルされます。これは、汎用的なGo言語実装（リファレンス実装）が使用されるケースを指します。

このコミットでは、rc4_asm.goにarmタグが追加され、rc4_ref.goからarmタグが除外されることで、ARMアーキテクチャではアセンブリ実装が、それ以外のアーキテクチャではGo言語のリファレンス実装が使用されるように切り替えが行われています。

技術的詳細

このコミットの主要な変更点は、src/pkg/crypto/rc4/rc4_arm.sという新しいファイルを追加し、RC4のキーストリーム生成とXOR処理をARMアセンブリで実装したことです。これにより、Go言語のランタイムがARMプロセッサ上でRC4を使用する際に、この最適化されたアセンブリコードが利用されるようになります。

rc4_arm.sの追加

このファイルは、RC4のxorKeyStream関数をARMアセンブリで実装しています。この関数は、RC4のPRGA（擬似乱数生成アルゴリズム）フェーズと、生成されたキーストリームと入力データのXOR演算を効率的に行います。

アセンブリコードでは、Go言語の関数呼び出し規約に従って引数がレジスタにマッピングされ、RC4の内部状態（S-box、ポインタiとj）が効率的に操作されます。

具体的には、以下のRC4のコアロジックがアセンブリで実装されています。

  1. iのインクリメントと256のモジュロ演算 (i = (i + 1) % 256)
  2. jの更新と256のモジュロ演算 (j = (j + S[i]) % 256)
  3. S[i]とS[j]の交換 (swap(S[i], S[j]))
  4. キーストリームバイトの生成 (k = S[(S[i] + S[j]) % 256])
  5. 入力バイトとキーストリームバイトのXOR (dst[k] = src[k] ^ k)

これらの操作は、ARMのロード/ストア命令（MOVBU, MOVB）、算術/論理命令（ADD, AND, EOR）を直接使用することで、Go言語のコンパイラが生成する汎用的なコードよりも少ないサイクルで実行されるように最適化されています。特に、配列アクセス（S-boxへのアクセス）やバイト操作が効率的に行われるように設計されています。

ビルドタグの変更

  • src/pkg/crypto/rc4/rc4_asm.go:

    • 変更前: // +build amd64
    • 変更後: // +build amd64 arm
    • この変更により、rc4_asm.go（アセンブリ実装へのGoラッパー）がamd64だけでなくarmアーキテクチャでもビルドされるようになります。

  • src/pkg/crypto/rc4/rc4_ref.go:

    • 変更前: // +build !amd64
    • 変更後: // +build !amd64,!arm
    • この変更により、rc4_ref.go（Go言語によるリファレンス実装）は、amd64でもarmでもないアーキテクチャでのみビルドされるようになります。

これらのビルドタグの変更により、Goのビルドシステムは、ターゲットアーキテクチャがARMの場合に自動的にアセンブリ実装を選択し、それ以外の場合はGo言語のリファレンス実装を使用するようになります。

パフォーマンスベンチマーク

コミットメッセージには、800MHz Cortex-A8プロセッサ上でのベンチマーク結果が示されています。

  • ns/op (ナノ秒/操作): 処理にかかる時間が約70%削減されています。これは、同じ操作を完了するのに必要な時間が大幅に短縮されたことを意味します。
  • MB/s (メガバイト/秒): スループットが約3.3倍から3.4倍に向上しています。これは、単位時間あたりに処理できるデータ量が増加したことを意味します。

これらの結果は、アセンブリ実装による最適化が非常に効果的であったことを明確に示しています。OpenSSLのRC4ベンチマーク結果も比較のために示されており、Goのアセンブリ実装がOpenSSLのパフォーマンスに近づいていることが示唆されます。

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

このコミットによる主要なコード変更は以下の3つのファイルにわたります。

  1. src/pkg/crypto/rc4/rc4_arm.s (新規追加):

    • RC4のxorKeyStream関数のARMアセンブリ実装が記述されています。
    • このファイルは、RC4のキーストリーム生成とXOR処理のコアロジックを、ARMプロセッサの命令セットに最適化して記述しています。

  2. src/pkg/crypto/rc4/rc4_asm.go (変更):

    • ビルドタグが// +build amd64から// +build amd64 armに変更されました。
    • これにより、このファイルがamd64アーキテクチャだけでなく、armアーキテクチャでもコンパイルされるようになります。このファイルは、アセンブリ実装されたxorKeyStream関数をGo言語から呼び出すためのラッパーを提供します。

  3. src/pkg/crypto/rc4/rc4_ref.go (変更):

    • ビルドタグが// +build !amd64から// +build !amd64,!armに変更されました。
    • これにより、このファイル（Go言語によるリファレンス実装）は、amd64でもarmでもないアーキテクチャでのみコンパイルされるようになります。

コアとなるコードの解説

src/pkg/crypto/rc4/rc4_arm.s

このファイルは、RC4のxorKeyStream関数のARMアセンブリ実装です。

// 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.

// Registers
dst = 0
src = 1
n = 2
state = 3
pi = 4
pj = 5
i = 6
j = 7
k = 8
t = 11
t2 = 12

// func xorKeyStream(dst, src *byte, n int, state *[256]byte, i, j *uint8)
TEXT ·xorKeyStream(SB),7,$0
	MOVW 0(FP), R(dst)   // dst (出力バッファ) をレジスタにロード
	MOVW 4(FP), R(src)   // src (入力バッファ) をレジスタにロード
	MOVW 8(FP), R(n)     // n (処理バイト数) をレジスタにロード
	MOVW 12(FP), R(state) // state (S-box) をレジスタにロード
	MOVW 16(FP), R(pi)   // pi (iポインタのアドレス) をレジスタにロード
	MOVW 20(FP), R(pj)   // pj (jポインタのアドレス) をレジスタにロード
	MOVBU (R(pi)), R(i)  // *pi (iの値) をレジスタiにロード
	MOVBU (R(pj)), R(j)  // *pj (jの値) をレジスタjにロード
	MOVW $0, R(k)        // k (ループカウンタ/オフセット) を0に初期化

loop:
	// i += 1; j += state[i]
	ADD $1, R(i)         // iをインクリメント
	AND $0xff, R(i)      // iを256のモジュロ演算 (i = (i + 1) % 256)
	MOVBU R(i)<<0(R(state)), R(t) // S[i]をレジスタtにロード
	ADD R(t), R(j)       // jにS[i]を加算
	AND $0xff, R(j)      // jを256のモジュロ演算 (j = (j + S[i]) % 256)

	// swap state[i] <-> state[j]
	MOVBU R(j)<<0(R(state)), R(t2) // S[j]をレジスタt2にロード
	MOVB R(t2), R(i)<<0(R(state)) // S[i]にS[j]の値をストア (S[i] = S[j])
	MOVB R(t), R(j)<<0(R(state))  // S[j]にS[i]の元の値をストア (S[j] = S[i]_original)

	// dst[k] = src[k] ^ state[state[i] + state[j]]
	ADD R(t2), R(t)      // tにt2を加算 (S[i]_original + S[j]_original)
	AND $0xff, R(t)      // 結果を256のモジュロ演算
	MOVBU R(t)<<0(R(state)), R(t) // S[(S[i] + S[j]) % 256] をレジスタtにロード (キーストリームバイト)
	MOVBU R(k)<<0(R(src)), R(t2)  // src[k] (入力バイト) をレジスタt2にロード
	EOR R(t), R(t2)      // t2とtをXOR (src[k] ^ ki)
	MOVB R(t2), R(k)<<0(R(dst))   // 結果をdst[k]にストア

	ADD $1, R(k)         // kをインクリメント
	CMP R(k), R(n)       // kとnを比較
	BNE loop             // kがnと等しくなければloopへ分岐

done:
	MOVB R(i), (R(pi))   // 最終的なiの値を*piにストア
	MOVB R(j), (R(pj))   // 最終的なjの値を*pjにストア
	RET                  // 関数から戻る

このアセンブリコードは、RC4のPRGAループを効率的に実装しています。各レジスタはRC4の内部状態やポインタ、一時的な値を保持するために割り当てられています。特に、S-boxへのアクセスはベースレジスタとオフセット（R(i)<<0(R(state))のような形式）を使って直接行われ、メモリ操作のオーバーヘッドを最小限に抑えています。ループはnバイトが処理されるまで継続し、最後に更新されたiとjの値が呼び出し元に書き戻されます。

src/pkg/crypto/rc4/rc4_asm.go

このファイルは、アセンブリで実装されたxorKeyStream関数をGo言語から呼び出すためのGoラッパーです。

// 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.

// +build amd64 arm // <-- 変更点: armタグが追加された

package rc4

// xorKeyStream is implemented in assembly.
// func xorKeyStream(dst, src []byte, n int, state *[256]byte, i, j *uint8)
func xorKeyStream(dst, src []byte, n int, state *[256]byte, i, j *uint8)

+build amd64 armタグにより、このファイルはamd64またはarmアーキテクチャでビルドされる場合にのみコンパイルされます。xorKeyStream関数の宣言は、Go言語の関数シグネチャと一致していますが、実装はアセンブリファイル（rc4_arm.s）に委ねられています。Goコンパイラは、この宣言を見て、対応するアセンブリ関数をリンクします。

src/pkg/crypto/rc4/rc4_ref.go

このファイルは、Go言語で書かれたRC4のリファレンス実装です。

// 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.

// +build !amd64,!arm // <-- 変更点: !armタグが追加された

package rc4

// xorKeyStream is the Go implementation of RC4's xorKeyStream.
// It is used when no assembly implementation is available.
func xorKeyStream(dst, src []byte, n int, state *[256]byte, i, j *uint8) {
	// ... Go言語によるRC4の実装 ...
}

+build !amd64,!armタグにより、このファイルはamd64でもarmでもないアーキテクチャでビルドされる場合にのみコンパイルされます。これにより、ARMアーキテクチャではアセンブリ実装が優先され、他のアーキテクチャ（例えば386やmipsなど）ではこのGo言語のリファレンス実装がフォールバックとして使用されるようになります。

関連リンク

参考にした情報源リンク