[インデックス 1001] Go言語初期実装におけるビット演算とシフト機能の拡張
コミット
commit 7112dc1db729777e4102f2799a79ebd93e1b41f7
Author: Robert Griesemer <gri@golang.org>
Date: Wed Oct 29 22:05:42 2008 -0700
- implemented Shr
- removed shift work-arounds (6g code appears to work now)
- made similar routines more regular in structure
- more tests
R=r
OCL=18102
CL=18102
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/7112dc1db729777e4102f2799a79ebd93e1b41f7
元コミット内容
このコミットは2008年10月29日に、Go言語の主要開発者の一人であるRobert Griesemer氏によって実装されました。主要な変更点は以下の通りです：
- 右シフト演算（Shr）の実装: 未実装だった
Shr関数を完全に実装 - シフト演算の回避コードの削除: 6gコンパイラのシフト演算が正常に動作するようになったため、一時的な回避コードを削除
- コード構造の正規化: 類似する関数の構造を統一し、保守性を向上
- テストの追加: 新機能の動作を確認するためのテストケースを追加
このコミットでは、usr/gri/bignum/bignum.goの69行が変更され、usr/gri/bignum/bignum_test.goに21行が追加されました。
変更の背景
2008年10月当時、Go言語はまだ開発初期段階にあり、基本的な算術演算の実装が進められていました。特に、大きな数値（bignum）を扱う算術演算ライブラリの開発は重要な要素でした。
このコミットが行われた時期は、Go言語の設計が開始された2007年9月21日から約1年経過した時点で、言語仕様の策定と初期コンパイラの実装が並行して進められていた時期です。特に、6gコンパイラ（amd64アーキテクチャ向けGo コンパイラ）の開発においてシフト演算の実装に課題があり、一時的な回避策が必要でした。
前提知識の解説
Go言語の初期開発環境（2007-2008年）
Go言語は2007年9月21日にGoogle社でRobert Griesemer、Rob Pike、Ken Thompsonの3人によって設計が開始されました。2008年1月に初期コンパイラの開発が始まり、2008年4月には言語仕様が策定されました。
6gコンパイラとは
6gコンパイラは、Go言語のamd64アーキテクチャ向けコンパイラです。Go言語の初期実装では、以下のような命名規則が使われていました：
6g: amd64アーキテクチャ向けコンパイラ8g: i386アーキテクチャ向けコンパイラ5g: ARMアーキテクチャ向けコンパイラ
これらのコンパイラは、Plan 9オペレーティングシステムの開発ツールチェーンから派生したものです。
多精度演算（Bignum）とは
多精度演算（Arbitrary-precision arithmetic）は、コンピュータのメモリ制限内で任意の精度で数値計算を行う技術です。通常の固定精度整数型では表現できない大きな数値を扱う際に必要となります。
ビットシフト演算
ビットシフト演算は、数値のビット表現を左右に移動させる演算です：
- 左シフト（Shl）: ビットを左にシフトし、値を2倍にする効果
- 右シフト（Shr）: ビットを右にシフトし、値を半分にする効果
Go言語の仕様では、シフト演算は以下のように定義されています：
- 左オペランドが符号付き整数の場合：算術シフト
- 左オペランドが符号なし整数の場合：論理シフト
技術的詳細
実装された機能
-
Shr関数の完全実装
- 以前は
panic("incomplete")で未実装だった右シフト演算を完全に実装 - 多精度数値の右シフト演算を効率的に処理
- 以前は
-
シフト演算の回避コードの削除
shlおよびshrの一時的な回避関数を削除- 6gコンパイラのネイティブシフト演算を直接使用
-
コード構造の統一
- 複数のループ構造を統一的な
for文に変更 - 変数のスコープを適切に管理
- 複数のループ構造を統一的な
アルゴリズムの詳細
右シフト演算（Shr）の実装では、以下のアルゴリズムが使用されています：
- ワード単位のシフト:
si := int(s / LogB)でワード単位のシフト量を計算 - ビット単位のシフト:
s = s % LogBでワード内のビットシフト量を計算 - 逆順処理: 高位ワードから低位ワードへの順序で処理（キャリーの伝播を正確に処理）
最適化の考慮事項
- メモリ効率: 必要最小限のメモリ割り当てで処理
- キャリー処理: シフト演算時のキャリービットを正確に処理
- 正規化: 結果の正規化により不要な上位ゼロビットを削除
コアとなるコードの変更箇所
1. Shr関数の実装（bignum.go:109-123）
func (x *Natural) Shr(s uint) *Natural {
- panic("incomplete");
- return nil
+ n := len(x);
+ si := int(s / LogB);
+ if si >= n { si = n; }
+ s = s % LogB;
+ assert(si <= n);
+ z := new(Natural, n - si);
+
+ c := Word(0);
+ for i := n - 1; i >= si; i-- { c, z[i-si] = Shr1(x[i], c, s); }
+
+ return Normalize(z);
}
2. シフト演算の回避コードの削除（bignum.go:68-86）
-// BUG use these until 6g shifts are working properly
-func shl(x Word, s uint) Word {
- return x << s;
-}
-
-func shr(x Word, s uint) Word {
- return x >> s;
-}
func Shl1(x, c Word, s uint) (Word, Word) {
assert(s <= LogB);
- return shr(x, (LogB - s)), shl(x, s)&M | c
+ return x >> (LogB - s), x << s & M | c
}
+func Shr1(x, c Word, s uint) (Word, Word) {
+ assert(s <= LogB);
+ return x << (LogB - s) & M, x >> s | c
+}
3. ループ構造の統一（複数箇所）
// Add関数での変更例
- i := 0;
c := Word(0);
- for ; i < m; i++ { c, z[i] = Split(x[i] + y[i] + c); }
- for ; i < n; i++ { c, z[i] = Split(x[i] + c); }
- z[i] = c;
+ for i := 0; i < m; i++ { c, z[i] = Split(x[i] + y[i] + c); }
+ for i := m; i < n; i++ { c, z[i] = Split(x[i] + c); }
+ z[n] = c;
コアとなるコードの解説
Shr関数の実装詳細
func (x *Natural) Shr(s uint) *Natural {
n := len(x);
si := int(s / LogB);
if si >= n { si = n; }
s = s % LogB;
assert(si <= n);
z := new(Natural, n - si);
c := Word(0);
for i := n - 1; i >= si; i-- { c, z[i-si] = Shr1(x[i], c, s); }
return Normalize(z);
}
- ワード単位の処理:
si := int(s / LogB)で、シフト量をワード単位で計算 - 境界チェック:
if si >= n { si = n; }で、シフト量が数値の長さを超えないように制限 - ビット単位の処理:
s = s % LogBで、ワード内でのビットシフト量を計算 - 逆順処理:
for i := n - 1; i >= si; i--で、高位ワードから処理することでキャリーを正確に伝播
Shr1関数の実装
func Shr1(x, c Word, s uint) (Word, Word) {
assert(s <= LogB);
return x << (LogB - s) & M, x >> s | c
}
この関数は、単一ワードの右シフト演算を実装しています：
- 第1戻り値: 次のワードへのキャリー（シフトアウトされる上位ビット）
- 第2戻り値: シフト後の値（前のワードからのキャリーを含む）
テストケースの追加
test_msg = "TestShift1R";
TEST(0, b.Shr(0).Cmp(b) == 0);
TEST(1, c.Shr(1).Cmp(c) < 0);
test_msg = "TestShift2";
for i := 0; i < 100; i++ {
TEST(i, c.Shl(uint(i)).Shr(uint(i)).Cmp(c) == 0);
}
このテストでは、以下の性質を確認しています：
- 0ビットシフトは元の値と同じ
- 右シフトは値を小さくする
- 左シフト後の右シフトで元の値に戻る（可逆性）