libgo: Update to weekly.2012-01-27.

From-SVN: r183810

3 files changed, 56 insertions, 3 deletions

diff --git a/libgo/go/math/big/arith.go b/libgo/go/math/big/arith.go
index 242bd1e..41de17b 100644
--- a/libgo/go/math/big/arith.go
+++ b/libgo/go/math/big/arith.go
@@ -54,6 +54,7 @@ func subWW_g(x, y, c Word) (z1, z0 Word) {
 
 // z1<<_W + z0 = x*y
 func mulWW(x, y Word) (z1, z0 Word) { return mulWW_g(x, y) }
+
 // Adapted from Warren, Hacker's Delight, p. 132.
 func mulWW_g(x, y Word) (z1, z0 Word) {
 	x0 := x & _M2
@@ -80,11 +81,24 @@ func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
 }
 
 // Length of x in bits.
-func bitLen(x Word) (n int) {
-	for ; x >= 0x100; x >>= 8 {
+func bitLen(x Word) (n int) { return bitLen_g(x) }
+func bitLen_g(x Word) (n int) {
+	for ; x >= 0x8000; x >>= 16 {
+		n += 16
+	}
+	if x >= 0x80 {
+		x >>= 8
 		n += 8
 	}
-	for ; x > 0; x >>= 1 {
+	if x >= 0x8 {
+		x >>= 4
+		n += 4
+	}
+	if x >= 0x2 {
+		x >>= 2
+		n += 2
+	}
+	if x >= 0x1 {
 		n++
 	}
 	return
@@ -104,6 +118,7 @@ func leadingZeros(x Word) uint {
 
 // q = (u1<<_W + u0 - r)/y
 func divWW(x1, x0, y Word) (q, r Word) { return divWW_g(x1, x0, y) }
+
 // Adapted from Warren, Hacker's Delight, p. 152.
 func divWW_g(u1, u0, v Word) (q, r Word) {
 	if u1 >= v {
diff --git a/libgo/go/math/big/arith_decl.go b/libgo/go/math/big/arith_decl.go
index 95fcd8b..068cc8d 100644
--- a/libgo/go/math/big/arith_decl.go
+++ b/libgo/go/math/big/arith_decl.go
@@ -16,3 +16,4 @@ func shrVU(z, x []Word, s uint) (c Word)
 func mulAddVWW(z, x []Word, y, r Word) (c Word)
 func addMulVVW(z, x []Word, y Word) (c Word)
 func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
+func bitLen(x Word) (n int)
diff --git a/libgo/go/math/big/arith_test.go b/libgo/go/math/big/arith_test.go
index b6c56c3..c7e3d28 100644
--- a/libgo/go/math/big/arith_test.go
+++ b/libgo/go/math/big/arith_test.go
@@ -333,3 +333,40 @@ func TestMulAddWWW(t *testing.T) {
 		}
 	}
 }
+
+func testWordBitLen(t *testing.T, fname string, f func(Word) int) {
+	for i := 0; i <= _W; i++ {
+		x := Word(1) << uint(i-1) // i == 0 => x == 0
+		n := f(x)
+		if n != i {
+			t.Errorf("got %d; want %d for %s(%#x)", n, i, fname, x)
+		}
+	}
+}
+
+func TestWordBitLen(t *testing.T) {
+	testWordBitLen(t, "bitLen", bitLen)
+	testWordBitLen(t, "bitLen_g", bitLen_g)
+}
+
+// runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1.
+func benchmarkBitLenN(b *testing.B, nbits uint) {
+	testword := Word((uint64(1) << nbits) - 1)
+	for i := 0; i < b.N; i++ {
+		bitLen(testword)
+	}
+}
+
+// Individual bitLen tests.  Numbers chosen to examine both sides
+// of powers-of-two boundaries.
+func BenchmarkBitLen0(b *testing.B)  { benchmarkBitLenN(b, 0) }
+func BenchmarkBitLen1(b *testing.B)  { benchmarkBitLenN(b, 1) }
+func BenchmarkBitLen2(b *testing.B)  { benchmarkBitLenN(b, 2) }
+func BenchmarkBitLen3(b *testing.B)  { benchmarkBitLenN(b, 3) }
+func BenchmarkBitLen4(b *testing.B)  { benchmarkBitLenN(b, 4) }
+func BenchmarkBitLen5(b *testing.B)  { benchmarkBitLenN(b, 5) }
+func BenchmarkBitLen8(b *testing.B)  { benchmarkBitLenN(b, 8) }
+func BenchmarkBitLen9(b *testing.B)  { benchmarkBitLenN(b, 9) }
+func BenchmarkBitLen16(b *testing.B) { benchmarkBitLenN(b, 16) }
+func BenchmarkBitLen17(b *testing.B) { benchmarkBitLenN(b, 17) }
+func BenchmarkBitLen31(b *testing.B) { benchmarkBitLenN(b, 31) }