diff options
author | Ian Lance Taylor <iant@golang.org> | 2017-09-14 17:11:35 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2017-09-14 17:11:35 +0000 |
commit | bc998d034f45d1828a8663b2eed928faf22a7d01 (patch) | |
tree | 8d262a22ca7318f4bcd64269fe8fe9e45bcf8d0f /libgo/go/math | |
parent | a41a6142df74219f596e612d3a7775f68ca6e96f (diff) | |
download | gcc-bc998d034f45d1828a8663b2eed928faf22a7d01.zip gcc-bc998d034f45d1828a8663b2eed928faf22a7d01.tar.gz gcc-bc998d034f45d1828a8663b2eed928faf22a7d01.tar.bz2 |
libgo: update to go1.9
Reviewed-on: https://go-review.googlesource.com/63753
From-SVN: r252767
Diffstat (limited to 'libgo/go/math')
39 files changed, 2291 insertions, 360 deletions
diff --git a/libgo/go/math/acosh.go b/libgo/go/math/acosh.go index dce21b2..97e84d0 100644 --- a/libgo/go/math/acosh.go +++ b/libgo/go/math/acosh.go @@ -40,6 +40,13 @@ package math // Acosh(x) = NaN if x < 1 // Acosh(NaN) = NaN func Acosh(x float64) float64 { + return libc_acosh(x) +} + +//extern acosh +func libc_acosh(float64) float64 + +func acosh(x float64) float64 { const ( Ln2 = 6.93147180559945286227e-01 // 0x3FE62E42FEFA39EF Large = 1 << 28 // 2**28 diff --git a/libgo/go/math/all_test.go b/libgo/go/math/all_test.go index 3d8cd722..39a3a49 100644 --- a/libgo/go/math/all_test.go +++ b/libgo/go/math/all_test.go @@ -947,6 +947,11 @@ var vfexpSC = []float64{ 2000, Inf(1), NaN(), + // smallest float64 that overflows Exp(x) + 7.097827128933841e+02, + // Issue 18912 + 1.48852223e+09, + 1.4885222e+09, } var expSC = []float64{ 0, @@ -954,6 +959,27 @@ var expSC = []float64{ Inf(1), Inf(1), NaN(), + Inf(1), + Inf(1), + Inf(1), +} + +var vfexp2SC = []float64{ + Inf(-1), + -2000, + 2000, + Inf(1), + NaN(), + // smallest float64 that overflows Exp2(x) + 1024, +} +var exp2SC = []float64{ + 0, + 0, + Inf(1), + Inf(1), + NaN(), + Inf(1), } var vfexpm1SC = []float64{ @@ -1620,16 +1646,38 @@ var powSC = []float64{ var vfpow10SC = []int{ MinInt32, - MaxInt32, - -325, + -324, + -323, + -50, + -22, + -1, + 0, + 1, + 22, + 50, + 100, + 200, + 308, 309, + MaxInt32, } var pow10SC = []float64{ - 0, // pow10(MinInt32) - Inf(1), // pow10(MaxInt32) - 0, // pow10(-325) - Inf(1), // pow10(309) + 0, // pow10(MinInt32) + 0, // pow10(-324) + 1.0e-323, // pow10(-323) + 1.0e-50, // pow10(-50) + 1.0e-22, // pow10(-22) + 1.0e-1, // pow10(-1) + 1.0e0, // pow10(0) + 1.0e1, // pow10(1) + 1.0e22, // pow10(22) + 1.0e50, // pow10(50) + 1.0e100, // pow10(100) + 1.0e200, // pow10(200) + 1.0e308, // pow10(308) + Inf(1), // pow10(309) + Inf(1), // pow10(MaxInt32) } var vfsignbitSC = []float64{ @@ -1716,30 +1764,35 @@ var vfy0SC = []float64{ 0, Inf(1), NaN(), + -1, } var y0SC = []float64{ NaN(), Inf(-1), 0, NaN(), + NaN(), } var y1SC = []float64{ NaN(), Inf(-1), 0, NaN(), + NaN(), } var y2SC = []float64{ NaN(), Inf(-1), 0, NaN(), + NaN(), } var yM3SC = []float64{ NaN(), Inf(1), 0, NaN(), + NaN(), } // arguments and expected results for boundary cases @@ -2089,8 +2142,8 @@ func testExp2(t *testing.T, Exp2 func(float64) float64, name string) { t.Errorf("%s(%g) = %g, want %g", name, vf[i], f, exp2[i]) } } - for i := 0; i < len(vfexpSC); i++ { - if f := Exp2(vfexpSC[i]); !alike(expSC[i], f) { + for i := 0; i < len(vfexp2SC); i++ { + if f := Exp2(vfexp2SC[i]); !alike(exp2SC[i], f) { t.Errorf("%s(%g) = %g, want %g", name, vfexpSC[i], f, expSC[i]) } } @@ -2690,6 +2743,9 @@ func TestYn(t *testing.T) { t.Errorf("Yn(-3, %g) = %g, want %g", vfy0SC[i], f, yM3SC[i]) } } + if f := Yn(0, 0); !alike(Inf(-1), f) { + t.Errorf("Yn(0, 0) = %g, want %g", f, Inf(-1)) + } } // Check that math functions of high angle values @@ -2768,327 +2824,452 @@ func TestFloatMinMax(t *testing.T) { // Benchmarks +// Global exported variables are used to store the +// return values of functions measured in the benchmarks. +// Storing the results in these variables prevents the compiler +// from completely optimizing the benchmarked functions away. +var ( + GlobalI int + GlobalB bool + GlobalF float64 +) + func BenchmarkAcos(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Acos(.5) + x = Acos(.5) } + GlobalF = x } func BenchmarkAcosh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Acosh(1.5) + x = Acosh(1.5) } + GlobalF = x } func BenchmarkAsin(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Asin(.5) + x = Asin(.5) } + GlobalF = x } func BenchmarkAsinh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Asinh(.5) + x = Asinh(.5) } + GlobalF = x } func BenchmarkAtan(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Atan(.5) + x = Atan(.5) } + GlobalF = x } func BenchmarkAtanh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Atanh(.5) + x = Atanh(.5) } + GlobalF = x } func BenchmarkAtan2(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Atan2(.5, 1) + x = Atan2(.5, 1) } + GlobalF = x } func BenchmarkCbrt(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Cbrt(10) + x = Cbrt(10) } + GlobalF = x } func BenchmarkCeil(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Ceil(.5) + x = Ceil(.5) } + GlobalF = x } func BenchmarkCopysign(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Copysign(.5, -1) + x = Copysign(.5, -1) } + GlobalF = x } func BenchmarkCos(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Cos(.5) + x = Cos(.5) } + GlobalF = x } func BenchmarkCosh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Cosh(2.5) + x = Cosh(2.5) } + GlobalF = x } func BenchmarkErf(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Erf(.5) + x = Erf(.5) } + GlobalF = x } func BenchmarkErfc(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Erfc(.5) + x = Erfc(.5) } + GlobalF = x } func BenchmarkExp(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Exp(.5) + x = Exp(.5) } + GlobalF = x } func BenchmarkExpGo(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - ExpGo(.5) + x = ExpGo(.5) } + GlobalF = x } func BenchmarkExpm1(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Expm1(.5) + x = Expm1(.5) } + GlobalF = x } func BenchmarkExp2(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Exp2(.5) + x = Exp2(.5) } + GlobalF = x } func BenchmarkExp2Go(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Exp2Go(.5) + x = Exp2Go(.5) } + GlobalF = x } func BenchmarkAbs(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Abs(.5) + x = Abs(.5) } + GlobalF = x + } func BenchmarkDim(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Dim(10, 3) + x = Dim(10, 3) } + GlobalF = x } func BenchmarkFloor(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Floor(.5) + x = Floor(.5) } + GlobalF = x } func BenchmarkMax(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Max(10, 3) + x = Max(10, 3) } + GlobalF = x } func BenchmarkMin(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Min(10, 3) + x = Min(10, 3) } + GlobalF = x } func BenchmarkMod(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Mod(10, 3) + x = Mod(10, 3) } + GlobalF = x } func BenchmarkFrexp(b *testing.B) { + x := 0.0 + y := 0 for i := 0; i < b.N; i++ { - Frexp(8) + x, y = Frexp(8) } + GlobalF = x + GlobalI = y } func BenchmarkGamma(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Gamma(2.5) + x = Gamma(2.5) } + GlobalF = x } func BenchmarkHypot(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Hypot(3, 4) + x = Hypot(3, 4) } + GlobalF = x } func BenchmarkHypotGo(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - HypotGo(3, 4) + x = HypotGo(3, 4) } + GlobalF = x } func BenchmarkIlogb(b *testing.B) { + x := 0 for i := 0; i < b.N; i++ { - Ilogb(.5) + x = Ilogb(.5) } + GlobalI = x } func BenchmarkJ0(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - J0(2.5) + x = J0(2.5) } + GlobalF = x } func BenchmarkJ1(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - J1(2.5) + x = J1(2.5) } + GlobalF = x } func BenchmarkJn(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Jn(2, 2.5) + x = Jn(2, 2.5) } + GlobalF = x } func BenchmarkLdexp(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Ldexp(.5, 2) + x = Ldexp(.5, 2) } + GlobalF = x } func BenchmarkLgamma(b *testing.B) { + x := 0.0 + y := 0 for i := 0; i < b.N; i++ { - Lgamma(2.5) + x, y = Lgamma(2.5) } + GlobalF = x + GlobalI = y } func BenchmarkLog(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Log(.5) + x = Log(.5) } + GlobalF = x } func BenchmarkLogb(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Logb(.5) + x = Logb(.5) } + GlobalF = x } func BenchmarkLog1p(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Log1p(.5) + x = Log1p(.5) } + GlobalF = x } func BenchmarkLog10(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Log10(.5) + x = Log10(.5) } + GlobalF = x } func BenchmarkLog2(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Log2(.5) + x = Log2(.5) } + GlobalF += x } func BenchmarkModf(b *testing.B) { + x := 0.0 + y := 0.0 for i := 0; i < b.N; i++ { - Modf(1.5) + x, y = Modf(1.5) } + GlobalF += x + GlobalF += y } func BenchmarkNextafter32(b *testing.B) { + x := float32(0.0) for i := 0; i < b.N; i++ { - Nextafter32(.5, 1) + x = Nextafter32(.5, 1) } + GlobalF = float64(x) } func BenchmarkNextafter64(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Nextafter(.5, 1) + x = Nextafter(.5, 1) } + GlobalF = x } func BenchmarkPowInt(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Pow(2, 2) + x = Pow(2, 2) } + GlobalF = x } func BenchmarkPowFrac(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Pow(2.5, 1.5) + x = Pow(2.5, 1.5) } + GlobalF = x } +var pow10pos = int(300) + func BenchmarkPow10Pos(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Pow10(300) + x = Pow10(pow10pos) } + GlobalF = x } +var pow10neg = int(-300) + func BenchmarkPow10Neg(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Pow10(-300) + x = Pow10(pow10neg) } + GlobalF = x } func BenchmarkRemainder(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Remainder(10, 3) + x = Remainder(10, 3) } + GlobalF = x } func BenchmarkSignbit(b *testing.B) { + x := false for i := 0; i < b.N; i++ { - Signbit(2.5) + x = Signbit(2.5) } + GlobalB = x } func BenchmarkSin(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Sin(.5) + x = Sin(.5) } + GlobalF = x } func BenchmarkSincos(b *testing.B) { + x := 0.0 + y := 0.0 for i := 0; i < b.N; i++ { - Sincos(.5) + x, y = Sincos(.5) } + GlobalF += x + GlobalF += y } func BenchmarkSinh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Sinh(2.5) + x = Sinh(2.5) } + GlobalF = x } -var Global float64 - func BenchmarkSqrtIndirect(b *testing.B) { x, y := 0.0, 10.0 f := Sqrt for i := 0; i < b.N; i++ { x += f(y) } - Global = x + GlobalF = x } func BenchmarkSqrtLatency(b *testing.B) { @@ -3096,7 +3277,7 @@ func BenchmarkSqrtLatency(b *testing.B) { for i := 0; i < b.N; i++ { x = Sqrt(x) } - Global = x + GlobalF = x } func BenchmarkSqrtIndirectLatency(b *testing.B) { @@ -3105,7 +3286,7 @@ func BenchmarkSqrtIndirectLatency(b *testing.B) { for i := 0; i < b.N; i++ { x = f(x) } - Global = x + GlobalF = x } func BenchmarkSqrtGoLatency(b *testing.B) { @@ -3113,7 +3294,7 @@ func BenchmarkSqrtGoLatency(b *testing.B) { for i := 0; i < b.N; i++ { x = SqrtGo(x) } - Global = x + GlobalF = x } func isPrime(i int) bool { @@ -3131,48 +3312,56 @@ func isPrime(i int) bool { } func BenchmarkSqrtPrime(b *testing.B) { - any := false + x := false for i := 0; i < b.N; i++ { - if isPrime(100003) { - any = true - } - } - if any { - Global = 1 + x = isPrime(100003) } + GlobalB = x } func BenchmarkTan(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Tan(.5) + x = Tan(.5) } + GlobalF = x } func BenchmarkTanh(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Tanh(2.5) + x = Tanh(2.5) } + GlobalF = x } func BenchmarkTrunc(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Trunc(.5) + x = Trunc(.5) } + GlobalF = x } func BenchmarkY0(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Y0(2.5) + x = Y0(2.5) } + GlobalF = x } func BenchmarkY1(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Y1(2.5) + x = Y1(2.5) } + GlobalF = x } func BenchmarkYn(b *testing.B) { + x := 0.0 for i := 0; i < b.N; i++ { - Yn(2, 2.5) + x = Yn(2, 2.5) } + GlobalF = x } diff --git a/libgo/go/math/arith_s390x.go b/libgo/go/math/arith_s390x.go index 937f25f..8d1fa6a 100644 --- a/libgo/go/math/arith_s390x.go +++ b/libgo/go/math/arith_s390x.go @@ -24,6 +24,54 @@ func sinhAsm(x float64) float64 func tanhTrampolineSetup(x float64) float64 func tanhAsm(x float64) float64 +func log1pTrampolineSetup(x float64) float64 +func log1pAsm(x float64) float64 + +func atanhTrampolineSetup(x float64) float64 +func atanhAsm(x float64) float64 + +func acosTrampolineSetup(x float64) float64 +func acosAsm(x float64) float64 + +func acoshTrampolineSetup(x float64) float64 +func acoshAsm(x float64) float64 + +func asinTrampolineSetup(x float64) float64 +func asinAsm(x float64) float64 + +func asinhTrampolineSetup(x float64) float64 +func asinhAsm(x float64) float64 + +func erfTrampolineSetup(x float64) float64 +func erfAsm(x float64) float64 + +func erfcTrampolineSetup(x float64) float64 +func erfcAsm(x float64) float64 + +func atanTrampolineSetup(x float64) float64 +func atanAsm(x float64) float64 + +func atan2TrampolineSetup(x, y float64) float64 +func atan2Asm(x, y float64) float64 + +func cbrtTrampolineSetup(x float64) float64 +func cbrtAsm(x float64) float64 + +func logTrampolineSetup(x float64) float64 +func logAsm(x float64) float64 + +func tanTrampolineSetup(x float64) float64 +func tanAsm(x float64) float64 + +func expTrampolineSetup(x float64) float64 +func expAsm(x float64) float64 + +func expm1TrampolineSetup(x float64) float64 +func expm1Asm(x float64) float64 + +func powTrampolineSetup(x, y float64) float64 +func powAsm(x, y float64) float64 + // hasVectorFacility reports whether the machine has the z/Architecture // vector facility installed and enabled. func hasVectorFacility() bool diff --git a/libgo/go/math/arith_s390x_test.go b/libgo/go/math/arith_s390x_test.go index fd3e8ca..23e5245 100644 --- a/libgo/go/math/arith_s390x_test.go +++ b/libgo/go/math/arith_s390x_test.go @@ -108,6 +108,37 @@ func TestLargeSinNovec(t *testing.T) { } } +func TestLargeTanNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + large := float64(100000 * Pi) + for i := 0; i < len(vf); i++ { + f1 := tanLarge[i] + f2 := TanNovec(vf[i] + large) + if !close(f1, f2) { + t.Errorf("Tan(%g) = %g, want %g", vf[i]+large, f2, f1) + } + } +} + +func TestTanNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := TanNovec(vf[i]); !veryclose(tan[i], f) { + t.Errorf("Tan(%g) = %g, want %g", vf[i], f, tan[i]) + } + } + // same special cases as Sin + for i := 0; i < len(vfsinSC); i++ { + if f := TanNovec(vfsinSC[i]); !alike(sinSC[i], f) { + t.Errorf("Tan(%g) = %g, want %g", vfsinSC[i], f, sinSC[i]) + } + } +} + func TestTanhNovec(t *testing.T) { if !HasVX { t.Skipf("no vector support") @@ -144,3 +175,270 @@ func TestLog10Novec(t *testing.T) { } } } + +func TestLog1pNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 100 + if f := Log1pNovec(a); !veryclose(log1p[i], f) { + t.Errorf("Log1p(%g) = %g, want %g", a, f, log1p[i]) + } + } + a := 9.0 + if f := Log1pNovec(a); f != Ln10 { + t.Errorf("Log1p(%g) = %g, want %g", a, f, Ln10) + } + for i := 0; i < len(vflogSC); i++ { + if f := Log1pNovec(vflog1pSC[i]); !alike(log1pSC[i], f) { + t.Errorf("Log1p(%g) = %g, want %g", vflog1pSC[i], f, log1pSC[i]) + } + } +} + +func TestAtanhNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 10 + if f := AtanhNovec(a); !veryclose(atanh[i], f) { + t.Errorf("Atanh(%g) = %g, want %g", a, f, atanh[i]) + } + } + for i := 0; i < len(vfatanhSC); i++ { + if f := AtanhNovec(vfatanhSC[i]); !alike(atanhSC[i], f) { + t.Errorf("Atanh(%g) = %g, want %g", vfatanhSC[i], f, atanhSC[i]) + } + } +} + +func TestAcosNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 10 + if f := AcosNovec(a); !close(acos[i], f) { + t.Errorf("Acos(%g) = %g, want %g", a, f, acos[i]) + } + } + for i := 0; i < len(vfacosSC); i++ { + if f := AcosNovec(vfacosSC[i]); !alike(acosSC[i], f) { + t.Errorf("Acos(%g) = %g, want %g", vfacosSC[i], f, acosSC[i]) + } + } +} + +func TestAsinNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 10 + if f := AsinNovec(a); !veryclose(asin[i], f) { + t.Errorf("Asin(%g) = %g, want %g", a, f, asin[i]) + } + } + for i := 0; i < len(vfasinSC); i++ { + if f := AsinNovec(vfasinSC[i]); !alike(asinSC[i], f) { + t.Errorf("Asin(%g) = %g, want %g", vfasinSC[i], f, asinSC[i]) + } + } +} + +func TestAcoshNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := 1 + Abs(vf[i]) + if f := AcoshNovec(a); !veryclose(acosh[i], f) { + t.Errorf("Acosh(%g) = %g, want %g", a, f, acosh[i]) + } + } + for i := 0; i < len(vfacoshSC); i++ { + if f := AcoshNovec(vfacoshSC[i]); !alike(acoshSC[i], f) { + t.Errorf("Acosh(%g) = %g, want %g", vfacoshSC[i], f, acoshSC[i]) + } + } +} + +func TestAsinhNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := AsinhNovec(vf[i]); !veryclose(asinh[i], f) { + t.Errorf("Asinh(%g) = %g, want %g", vf[i], f, asinh[i]) + } + } + for i := 0; i < len(vfasinhSC); i++ { + if f := AsinhNovec(vfasinhSC[i]); !alike(asinhSC[i], f) { + t.Errorf("Asinh(%g) = %g, want %g", vfasinhSC[i], f, asinhSC[i]) + } + } +} + +func TestErfNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 10 + if f := ErfNovec(a); !veryclose(erf[i], f) { + t.Errorf("Erf(%g) = %g, want %g", a, f, erf[i]) + } + } + for i := 0; i < len(vferfSC); i++ { + if f := ErfNovec(vferfSC[i]); !alike(erfSC[i], f) { + t.Errorf("Erf(%g) = %g, want %g", vferfSC[i], f, erfSC[i]) + } + } +} + +func TestErfcNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 10 + if f := ErfcNovec(a); !veryclose(erfc[i], f) { + t.Errorf("Erfc(%g) = %g, want %g", a, f, erfc[i]) + } + } + for i := 0; i < len(vferfcSC); i++ { + if f := ErfcNovec(vferfcSC[i]); !alike(erfcSC[i], f) { + t.Errorf("Erfc(%g) = %g, want %g", vferfcSC[i], f, erfcSC[i]) + } + } +} + +func TestAtanNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := AtanNovec(vf[i]); !veryclose(atan[i], f) { + t.Errorf("Atan(%g) = %g, want %g", vf[i], f, atan[i]) + } + } + for i := 0; i < len(vfatanSC); i++ { + if f := AtanNovec(vfatanSC[i]); !alike(atanSC[i], f) { + t.Errorf("Atan(%g) = %g, want %g", vfatanSC[i], f, atanSC[i]) + } + } +} + +func TestAtan2Novec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := Atan2Novec(10, vf[i]); !veryclose(atan2[i], f) { + t.Errorf("Atan2(10, %g) = %g, want %g", vf[i], f, atan2[i]) + } + } + for i := 0; i < len(vfatan2SC); i++ { + if f := Atan2Novec(vfatan2SC[i][0], vfatan2SC[i][1]); !alike(atan2SC[i], f) { + t.Errorf("Atan2(%g, %g) = %g, want %g", vfatan2SC[i][0], vfatan2SC[i][1], f, atan2SC[i]) + } + } +} + +func TestCbrtNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := CbrtNovec(vf[i]); !veryclose(cbrt[i], f) { + t.Errorf("Cbrt(%g) = %g, want %g", vf[i], f, cbrt[i]) + } + } + for i := 0; i < len(vfcbrtSC); i++ { + if f := CbrtNovec(vfcbrtSC[i]); !alike(cbrtSC[i], f) { + t.Errorf("Cbrt(%g) = %g, want %g", vfcbrtSC[i], f, cbrtSC[i]) + } + } +} + +func TestLogNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := Abs(vf[i]) + if f := LogNovec(a); log[i] != f { + t.Errorf("Log(%g) = %g, want %g", a, f, log[i]) + } + } + if f := LogNovec(10); f != Ln10 { + t.Errorf("Log(%g) = %g, want %g", 10.0, f, Ln10) + } + for i := 0; i < len(vflogSC); i++ { + if f := LogNovec(vflogSC[i]); !alike(logSC[i], f) { + t.Errorf("Log(%g) = %g, want %g", vflogSC[i], f, logSC[i]) + } + } +} + +func TestExpNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + testExpNovec(t, Exp, "Exp") + testExpNovec(t, ExpGo, "ExpGo") +} + +func testExpNovec(t *testing.T, Exp func(float64) float64, name string) { + for i := 0; i < len(vf); i++ { + if f := ExpNovec(vf[i]); !veryclose(exp[i], f) { + t.Errorf("%s(%g) = %g, want %g", name, vf[i], f, exp[i]) + } + } + for i := 0; i < len(vfexpSC); i++ { + if f := ExpNovec(vfexpSC[i]); !alike(expSC[i], f) { + t.Errorf("%s(%g) = %g, want %g", name, vfexpSC[i], f, expSC[i]) + } + } +} + +func TestExpm1Novec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := vf[i] / 100 + if f := Expm1Novec(a); !veryclose(expm1[i], f) { + t.Errorf("Expm1(%g) = %g, want %g", a, f, expm1[i]) + } + } + for i := 0; i < len(vf); i++ { + a := vf[i] * 10 + if f := Expm1Novec(a); !close(expm1Large[i], f) { + t.Errorf("Expm1(%g) = %g, want %g", a, f, expm1Large[i]) + } + } + for i := 0; i < len(vfexpm1SC); i++ { + if f := Expm1Novec(vfexpm1SC[i]); !alike(expm1SC[i], f) { + t.Errorf("Expm1(%g) = %g, want %g", vfexpm1SC[i], f, expm1SC[i]) + } + } +} + +func TestPowNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := PowNovec(10, vf[i]); !close(pow[i], f) { + t.Errorf("Pow(10, %g) = %g, want %g", vf[i], f, pow[i]) + } + } + for i := 0; i < len(vfpowSC); i++ { + if f := PowNovec(vfpowSC[i][0], vfpowSC[i][1]); !alike(powSC[i], f) { + t.Errorf("Pow(%g, %g) = %g, want %g", vfpowSC[i][0], vfpowSC[i][1], f, powSC[i]) + } + } +} diff --git a/libgo/go/math/asinh.go b/libgo/go/math/asinh.go index 3b793b0..d5e6512 100644 --- a/libgo/go/math/asinh.go +++ b/libgo/go/math/asinh.go @@ -37,6 +37,13 @@ package math // Asinh(±Inf) = ±Inf // Asinh(NaN) = NaN func Asinh(x float64) float64 { + return libc_asinh(x) +} + +//extern asinh +func libc_asinh(float64) float64 + +func asinh(x float64) float64 { const ( Ln2 = 6.93147180559945286227e-01 // 0x3FE62E42FEFA39EF NearZero = 1.0 / (1 << 28) // 2**-28 diff --git a/libgo/go/math/atanh.go b/libgo/go/math/atanh.go index d59a847..c62c1c0 100644 --- a/libgo/go/math/atanh.go +++ b/libgo/go/math/atanh.go @@ -45,6 +45,13 @@ package math // Atanh(x) = NaN if x < -1 or x > 1 // Atanh(NaN) = NaN func Atanh(x float64) float64 { + return libc_atanh(x) +} + +//extern atanh +func libc_atanh(float64) float64 + +func atanh(x float64) float64 { const NearZero = 1.0 / (1 << 28) // 2**-28 // special cases switch { diff --git a/libgo/go/math/big/arith.go b/libgo/go/math/big/arith.go index d7ea838..ad35240 100644 --- a/libgo/go/math/big/arith.go +++ b/libgo/go/math/big/arith.go @@ -8,18 +8,17 @@ package big +import "math/bits" + // A Word represents a single digit of a multi-precision unsigned integer. -type Word uintptr +type Word uint const ( - // Compute the size _S of a Word in bytes. - _m = ^Word(0) - _logS = _m>>8&1 + _m>>16&1 + _m>>32&1 - _S = 1 << _logS + _S = _W / 8 // word size in bytes - _W = _S << 3 // word size in bits - _B = 1 << _W // digit base - _M = _B - 1 // digit mask + _W = bits.UintSize // word size in bits + _B = 1 << _W // digit base + _M = _B - 1 // digit mask _W2 = _W / 2 // half word size in bits _B2 = 1 << _W2 // half digit base @@ -77,54 +76,10 @@ func mulAddWWW_g(x, y, c Word) (z1, z0 Word) { return } -// Length of x in bits. -func bitLen_g(x Word) (n int) { - for ; x >= 0x8000; x >>= 16 { - n += 16 - } - if x >= 0x80 { - x >>= 8 - n += 8 - } - if x >= 0x8 { - x >>= 4 - n += 4 - } - if x >= 0x2 { - x >>= 2 - n += 2 - } - if x >= 0x1 { - n++ - } - return -} - -// log2 computes the integer binary logarithm of x. -// The result is the integer n for which 2^n <= x < 2^(n+1). -// If x == 0, the result is -1. -func log2(x Word) int { - return bitLen(x) - 1 -} - // nlz returns the number of leading zeros in x. +// Wraps bits.LeadingZeros call for convenience. func nlz(x Word) uint { - return uint(_W - bitLen(x)) -} - -// nlz64 returns the number of leading zeros in x. -func nlz64(x uint64) uint { - switch _W { - case 32: - w := x >> 32 - if w == 0 { - return 32 + nlz(Word(x)) - } - return nlz(Word(w)) - case 64: - return nlz(Word(x)) - } - panic("unreachable") + return uint(bits.LeadingZeros(uint(x))) } // q = (u1<<_W + u0 - r)/y diff --git a/libgo/go/math/big/arith_decl.go b/libgo/go/math/big/arith_decl.go index 5538833..61df0df 100644 --- a/libgo/go/math/big/arith_decl.go +++ b/libgo/go/math/big/arith_decl.go @@ -19,4 +19,3 @@ 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_decl_pure.go b/libgo/go/math/big/arith_decl_pure.go index 5c04414..0988419 100644 --- a/libgo/go/math/big/arith_decl_pure.go +++ b/libgo/go/math/big/arith_decl_pure.go @@ -49,7 +49,3 @@ func addMulVVW(z, x []Word, y Word) (c Word) { func divWVW(z []Word, xn Word, x []Word, y Word) (r Word) { return divWVW_g(z, xn, x, y) } - -func bitLen(x Word) (n int) { - return bitLen_g(x) -} diff --git a/libgo/go/math/big/arith_s390x_test.go b/libgo/go/math/big/arith_s390x_test.go index ee127a4..0e8ac85 100644 --- a/libgo/go/math/big/arith_s390x_test.go +++ b/libgo/go/math/big/arith_s390x_test.go @@ -3,7 +3,7 @@ // license that can be found in the LICENSE file. // +build ignore -// +build s390x !math_big_pure_go +// +build s390x,!math_big_pure_go package big diff --git a/libgo/go/math/big/arith_test.go b/libgo/go/math/big/arith_test.go index f2b3083..13b0436 100644 --- a/libgo/go/math/big/arith_test.go +++ b/libgo/go/math/big/arith_test.go @@ -395,32 +395,3 @@ func BenchmarkAddMulVVW(b *testing.B) { }) } } - -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 BenchmarkBitLen(b *testing.B) { - // Individual bitLen tests. Numbers chosen to examine both sides - // of powers-of-two boundaries. - for _, nbits := range []uint{0, 1, 2, 3, 4, 5, 8, 9, 16, 17, 31} { - testword := Word((uint64(1) << nbits) - 1) - b.Run(fmt.Sprint(nbits), func(b *testing.B) { - for i := 0; i < b.N; i++ { - bitLen(testword) - } - }) - } -} diff --git a/libgo/go/math/big/float.go b/libgo/go/math/big/float.go index aabd7b4..7e11f1a 100644 --- a/libgo/go/math/big/float.go +++ b/libgo/go/math/big/float.go @@ -14,6 +14,7 @@ package big import ( "fmt" "math" + "math/bits" ) const debugFloat = false // enable for debugging @@ -97,7 +98,7 @@ const ( // the slice may (but doesn't have to) be shorter if the mantissa contains // trailing 0 bits. x.mant is normalized if the msb of x.mant == 1 (i.e., // the msb is shifted all the way "to the left"). Thus, if the mantissa has -// trailing 0 bits or x.prec is not a multiple of the the Word size _W, +// trailing 0 bits or x.prec is not a multiple of the Word size _W, // x.mant[0] has trailing zero bits. The msb of the mantissa corresponds // to the value 0.5; the exponent x.exp shifts the binary point as needed. // @@ -498,8 +499,8 @@ func (z *Float) setBits64(neg bool, x uint64) *Float { } // x != 0 z.form = finite - s := nlz64(x) - z.mant = z.mant.setUint64(x << s) + s := bits.LeadingZeros64(x) + z.mant = z.mant.setUint64(x << uint(s)) z.exp = int32(64 - s) // always fits if z.prec < 64 { z.round(0) @@ -1438,8 +1439,16 @@ func (z *Float) Add(x, y *Float) *Float { if x.form == finite && y.form == finite { // x + y (common case) + + // Below we set z.neg = x.neg, and when z aliases y this will + // change the y operand's sign. This is fine, because if an + // operand aliases the receiver it'll be overwritten, but we still + // want the original x.neg and y.neg values when we evaluate + // x.neg != y.neg, so we need to save y.neg before setting z.neg. + yneg := y.neg + z.neg = x.neg - if x.neg == y.neg { + if x.neg == yneg { // x + y == x + y // (-x) + (-y) == -(x + y) z.uadd(x, y) @@ -1501,8 +1510,9 @@ func (z *Float) Sub(x, y *Float) *Float { if x.form == finite && y.form == finite { // x - y (common case) + yneg := y.neg z.neg = x.neg - if x.neg != y.neg { + if x.neg != yneg { // x - (-y) == x + y // (-x) - y == -(x + y) z.uadd(x, y) diff --git a/libgo/go/math/big/float_test.go b/libgo/go/math/big/float_test.go index 7d4bd31..5fd49bb 100644 --- a/libgo/go/math/big/float_test.go +++ b/libgo/go/math/big/float_test.go @@ -1325,6 +1325,34 @@ func TestFloatAdd64(t *testing.T) { } } +func TestIssue20490(t *testing.T) { + var tests = []struct { + a, b float64 + }{ + {4, 1}, + {-4, 1}, + {4, -1}, + {-4, -1}, + } + + for _, test := range tests { + a, b := NewFloat(test.a), NewFloat(test.b) + diff := new(Float).Sub(a, b) + b.Sub(a, b) + if b.Cmp(diff) != 0 { + t.Errorf("got %g - %g = %g; want %g\n", a, NewFloat(test.b), b, diff) + } + + b = NewFloat(test.b) + sum := new(Float).Add(a, b) + b.Add(a, b) + if b.Cmp(sum) != 0 { + t.Errorf("got %g + %g = %g; want %g\n", a, NewFloat(test.b), b, sum) + } + + } +} + // TestFloatMul tests Float.Mul/Quo by comparing the result of a "manual" // multiplication/division of arguments represented by Bits values with the // respective Float multiplication/division for a variety of precisions diff --git a/libgo/go/math/big/floatconv_test.go b/libgo/go/math/big/floatconv_test.go index edcb2eb..6d0f17d 100644 --- a/libgo/go/math/big/floatconv_test.go +++ b/libgo/go/math/big/floatconv_test.go @@ -8,10 +8,13 @@ import ( "bytes" "fmt" "math" + "math/bits" "strconv" "testing" ) +var zero_ float64 + func TestFloatSetFloat64String(t *testing.T) { inf := math.Inf(0) nan := math.NaN() @@ -22,7 +25,7 @@ func TestFloatSetFloat64String(t *testing.T) { }{ // basics {"0", 0}, - {"-0", -0}, + {"-0", -zero_}, {"+0", 0}, {"1", 1}, {"-1", -1}, @@ -36,10 +39,10 @@ func TestFloatSetFloat64String(t *testing.T) { // various zeros {"0e100", 0}, - {"-0e+100", 0}, + {"-0e+100", -zero_}, {"+0e-100", 0}, {"0E100", 0}, - {"-0E+100", 0}, + {"-0E+100", -zero_}, {"+0E-100", 0}, // various decimal exponent formats @@ -78,7 +81,7 @@ func TestFloatSetFloat64String(t *testing.T) { // decimal mantissa, binary exponent {"0p0", 0}, - {"-0p0", -0}, + {"-0p0", -zero_}, {"1p10", 1 << 10}, {"1p+10", 1 << 10}, {"+1p-10", 1.0 / (1 << 10)}, @@ -88,9 +91,9 @@ func TestFloatSetFloat64String(t *testing.T) { // binary mantissa, decimal exponent {"0b0", 0}, - {"-0b0", -0}, + {"-0b0", -zero_}, {"0b0e+10", 0}, - {"-0b0e-10", -0}, + {"-0b0e-10", -zero_}, {"0b1010", 10}, {"0B1010E2", 1000}, {"0b.1", 0.5}, @@ -99,7 +102,7 @@ func TestFloatSetFloat64String(t *testing.T) { // binary mantissa, binary exponent {"0b0p+10", 0}, - {"-0b0p-10", -0}, + {"-0b0p-10", -zero_}, {"0b.1010p4", 10}, {"0b1p-1", 0.5}, {"0b001p-3", 0.125}, @@ -108,9 +111,9 @@ func TestFloatSetFloat64String(t *testing.T) { // hexadecimal mantissa and exponent {"0x0", 0}, - {"-0x0", -0}, + {"-0x0", -zero_}, {"0x0p+10", 0}, - {"-0x0p-10", -0}, + {"-0x0p-10", -zero_}, {"0xff", 255}, {"0X.8p1", 1}, {"-0X0.00008p16", -0.5}, @@ -134,8 +137,8 @@ func TestFloatSetFloat64String(t *testing.T) { } f, _ := x.Float64() want := new(Float).SetFloat64(test.x) - if x.Cmp(want) != 0 { - t.Errorf("%s: got %s (%v); want %v", test.s, &x, f, test.x) + if x.Cmp(want) != 0 || x.Signbit() != want.Signbit() { + t.Errorf("%s: got %v (%v); want %v", test.s, &x, f, test.x) } } } @@ -326,9 +329,9 @@ func TestFloat64Text(t *testing.T) { // actualPrec returns the number of actually used mantissa bits. func actualPrec(x float64) uint { - if bits := math.Float64bits(x); x != 0 && bits&(0x7ff<<52) == 0 { + if mant := math.Float64bits(x); x != 0 && mant&(0x7ff<<52) == 0 { // x is denormalized - return 64 - nlz64(bits&(1<<52-1)) + return 64 - uint(bits.LeadingZeros64(mant&(1<<52-1))) } return 53 } diff --git a/libgo/go/math/big/int.go b/libgo/go/math/big/int.go index 1d8dabc..62f7fc5 100644 --- a/libgo/go/math/big/int.go +++ b/libgo/go/math/big/int.go @@ -324,22 +324,22 @@ func (x *Int) Cmp(y *Int) (r int) { return } -// low32 returns the least significant 32 bits of z. -func low32(z nat) uint32 { - if len(z) == 0 { +// low32 returns the least significant 32 bits of x. +func low32(x nat) uint32 { + if len(x) == 0 { return 0 } - return uint32(z[0]) + return uint32(x[0]) } -// low64 returns the least significant 64 bits of z. -func low64(z nat) uint64 { - if len(z) == 0 { +// low64 returns the least significant 64 bits of x. +func low64(x nat) uint64 { + if len(x) == 0 { return 0 } - v := uint64(z[0]) - if _W == 32 && len(z) > 1 { - v |= uint64(z[1]) << 32 + v := uint64(x[0]) + if _W == 32 && len(x) > 1 { + return uint64(x[1])<<32 | v } return v } @@ -360,6 +360,20 @@ func (x *Int) Uint64() uint64 { return low64(x.abs) } +// IsInt64 reports whether x can be represented as an int64. +func (x *Int) IsInt64() bool { + if len(x.abs) <= 64/_W { + w := int64(low64(x.abs)) + return w >= 0 || x.neg && w == -w + } + return false +} + +// IsUint64 reports whether x can be represented as a uint64. +func (x *Int) IsUint64() bool { + return !x.neg && len(x.abs) <= 64/_W +} + // SetString sets z to the value of s, interpreted in the given base, // and returns z and a boolean indicating success. The entire string // (not just a prefix) must be valid for success. If SetString fails, @@ -556,7 +570,7 @@ func (z *Int) binaryGCD(a, b *Int) *Int { // Rand sets z to a pseudo-random number in [0, n) and returns z. func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { z.neg = false - if n.neg == true || len(n.abs) == 0 { + if n.neg || len(n.abs) == 0 { z.abs = nil return z } diff --git a/libgo/go/math/big/int_test.go b/libgo/go/math/big/int_test.go index b8e0778..42e810b 100644 --- a/libgo/go/math/big/int_test.go +++ b/libgo/go/math/big/int_test.go @@ -7,8 +7,8 @@ package big import ( "bytes" "encoding/hex" - "fmt" "math/rand" + "strconv" "strings" "testing" "testing/quick" @@ -260,7 +260,7 @@ func BenchmarkBinomial(b *testing.B) { var divisionSignsTests = []struct { x, y int64 q, r int64 // T-division - d, m int64 // Euclidian division + d, m int64 // Euclidean division }{ {5, 3, 1, 2, 1, 2}, {-5, 3, -1, -2, -2, 1}, @@ -903,56 +903,105 @@ func TestLshRsh(t *testing.T) { } } -var int64Tests = []int64{ - 0, - 1, - -1, - 4294967295, - -4294967295, - 4294967296, - -4294967296, - 9223372036854775807, - -9223372036854775807, - -9223372036854775808, +var int64Tests = []string{ + // int64 + "0", + "1", + "-1", + "4294967295", + "-4294967295", + "4294967296", + "-4294967296", + "9223372036854775807", + "-9223372036854775807", + "-9223372036854775808", + + // not int64 + "0x8000000000000000", + "-0x8000000000000001", + "38579843757496759476987459679745", + "-38579843757496759476987459679745", } func TestInt64(t *testing.T) { - for i, testVal := range int64Tests { - in := NewInt(testVal) - out := in.Int64() + for _, s := range int64Tests { + var x Int + _, ok := x.SetString(s, 0) + if !ok { + t.Errorf("SetString(%s, 0) failed", s) + continue + } + + want, err := strconv.ParseInt(s, 0, 64) + if err != nil { + if err.(*strconv.NumError).Err == strconv.ErrRange { + if x.IsInt64() { + t.Errorf("IsInt64(%s) succeeded unexpectedly", s) + } + } else { + t.Errorf("ParseInt(%s) failed", s) + } + continue + } + + if !x.IsInt64() { + t.Errorf("IsInt64(%s) failed unexpectedly", s) + } - if out != testVal { - t.Errorf("#%d got %d want %d", i, out, testVal) + got := x.Int64() + if got != want { + t.Errorf("Int64(%s) = %d; want %d", s, got, want) } } } -var uint64Tests = []uint64{ - 0, - 1, - 4294967295, - 4294967296, - 8589934591, - 8589934592, - 9223372036854775807, - 9223372036854775808, - 18446744073709551615, // 1<<64 - 1 +var uint64Tests = []string{ + // uint64 + "0", + "1", + "4294967295", + "4294967296", + "8589934591", + "8589934592", + "9223372036854775807", + "9223372036854775808", + "0x08000000000000000", + + // not uint64 + "0x10000000000000000", + "-0x08000000000000000", + "-1", } func TestUint64(t *testing.T) { - in := new(Int) - for i, testVal := range uint64Tests { - in.SetUint64(testVal) - out := in.Uint64() + for _, s := range uint64Tests { + var x Int + _, ok := x.SetString(s, 0) + if !ok { + t.Errorf("SetString(%s, 0) failed", s) + continue + } + + want, err := strconv.ParseUint(s, 0, 64) + if err != nil { + // check for sign explicitly (ErrRange doesn't cover signed input) + if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange { + if x.IsUint64() { + t.Errorf("IsUint64(%s) succeeded unexpectedly", s) + } + } else { + t.Errorf("ParseUint(%s) failed", s) + } + continue + } - if out != testVal { - t.Errorf("#%d got %d want %d", i, out, testVal) + if !x.IsUint64() { + t.Errorf("IsUint64(%s) failed unexpectedly", s) } - str := fmt.Sprint(testVal) - strOut := in.String() - if strOut != str { - t.Errorf("#%d.String got %s want %s", i, strOut, str) + got := x.Uint64() + if got != want { + t.Errorf("Uint64(%s) = %d; want %d", s, got, want) } } } diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go index 9b1a626..889eacb 100644 --- a/libgo/go/math/big/nat.go +++ b/libgo/go/math/big/nat.go @@ -9,6 +9,7 @@ package big import ( + "math/bits" "math/rand" "sync" ) @@ -67,24 +68,14 @@ func (z nat) setWord(x Word) nat { } func (z nat) setUint64(x uint64) nat { - // single-digit values + // single-word value if w := Word(x); uint64(w) == x { return z.setWord(w) } - - // compute number of words n required to represent x - n := 0 - for t := x; t > 0; t >>= _W { - n++ - } - - // split x into n words - z = z.make(n) - for i := range z { - z[i] = Word(x & _M) - x >>= _W - } - + // 2-word value + z = z.make(2) + z[1] = Word(x >> 32) + z[0] = Word(x) return z } @@ -653,49 +644,11 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { // Length of x in bits. x must be normalized. func (x nat) bitLen() int { if i := len(x) - 1; i >= 0 { - return i*_W + bitLen(x[i]) + return i*_W + bits.Len(uint(x[i])) } return 0 } -const deBruijn32 = 0x077CB531 - -var deBruijn32Lookup = [...]byte{ - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, -} - -const deBruijn64 = 0x03f79d71b4ca8b09 - -var deBruijn64Lookup = [...]byte{ - 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, - 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, - 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, - 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, -} - -// trailingZeroBits returns the number of consecutive least significant zero -// bits of x. -func trailingZeroBits(x Word) uint { - // x & -x leaves only the right-most bit set in the word. Let k be the - // index of that bit. Since only a single bit is set, the value is two - // to the power of k. Multiplying by a power of two is equivalent to - // left shifting, in this case by k bits. The de Bruijn constant is - // such that all six bit, consecutive substrings are distinct. - // Therefore, if we have a left shifted version of this constant we can - // find by how many bits it was shifted by looking at which six bit - // substring ended up at the top of the word. - // (Knuth, volume 4, section 7.3.1) - switch _W { - case 32: - return uint(deBruijn32Lookup[((x&-x)*deBruijn32)>>27]) - case 64: - return uint(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58]) - default: - panic("unknown word size") - } -} - // trailingZeroBits returns the number of consecutive least significant zero // bits of x. func (x nat) trailingZeroBits() uint { @@ -707,7 +660,7 @@ func (x nat) trailingZeroBits() uint { i++ } // x[i] != 0 - return i*_W + trailingZeroBits(x[i]) + return i*_W + uint(bits.TrailingZeros(uint(x[i]))) } // z = x << s diff --git a/libgo/go/math/big/nat_test.go b/libgo/go/math/big/nat_test.go index ebb2985..200a247 100644 --- a/libgo/go/math/big/nat_test.go +++ b/libgo/go/math/big/nat_test.go @@ -303,36 +303,6 @@ func TestModW(t *testing.T) { } } -func TestTrailingZeroBits(t *testing.T) { - // test 0 case explicitly - if n := trailingZeroBits(0); n != 0 { - t.Errorf("got trailingZeroBits(0) = %d; want 0", n) - } - - x := Word(1) - for i := uint(0); i < _W; i++ { - n := trailingZeroBits(x) - if n != i { - t.Errorf("got trailingZeroBits(%#x) = %d; want %d", x, n, i%_W) - } - x <<= 1 - } - - // test 0 case explicitly - if n := nat(nil).trailingZeroBits(); n != 0 { - t.Errorf("got nat(nil).trailingZeroBits() = %d; want 0", n) - } - - y := nat(nil).set(natOne) - for i := uint(0); i <= 3*_W; i++ { - n := y.trailingZeroBits() - if n != i { - t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.utoa(16), n, i) - } - y = y.shl(y, 1) - } -} - var montgomeryTests = []struct { x, y, m string k0 uint64 diff --git a/libgo/go/math/big/natconv.go b/libgo/go/math/big/natconv.go index 4454784..25a345e 100644 --- a/libgo/go/math/big/natconv.go +++ b/libgo/go/math/big/natconv.go @@ -11,6 +11,7 @@ import ( "fmt" "io" "math" + "math/bits" "sync" ) @@ -262,7 +263,7 @@ func (x nat) itoa(neg bool, base int) []byte { // convert power of two and non power of two bases separately if b := Word(base); b == b&-b { // shift is base b digit size in bits - shift := trailingZeroBits(b) // shift > 0 because b >= 2 + shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2 mask := Word(1<<shift - 1) w := x[0] // current word nbits := uint(_W) // number of unprocessed bits in w diff --git a/libgo/go/math/big/natconv_test.go b/libgo/go/math/big/natconv_test.go index bdb60e6..898a39f 100644 --- a/libgo/go/math/big/natconv_test.go +++ b/libgo/go/math/big/natconv_test.go @@ -8,10 +8,18 @@ import ( "bytes" "fmt" "io" + "math/bits" "strings" "testing" ) +// log2 computes the integer binary logarithm of x. +// The result is the integer n for which 2^n <= x < 2^(n+1). +// If x == 0, the result is -1. +func log2(x Word) int { + return bits.Len(uint(x)) - 1 +} + func itoa(x nat, base int) []byte { // special cases switch { diff --git a/libgo/go/math/big/prime_test.go b/libgo/go/math/big/prime_test.go index a2d3d18..7760519 100644 --- a/libgo/go/math/big/prime_test.go +++ b/libgo/go/math/big/prime_test.go @@ -200,7 +200,7 @@ func testPseudoprimes(t *testing.T, name string, cond func(nat) bool, want []int n[0] = Word(i) pseudo := cond(n) if pseudo && (len(want) == 0 || i != want[0]) { - t.Errorf("%s(%v, base=2) = %v, want false", name, i) + t.Errorf("%s(%v, base=2) = true, want false", name, i) } else if !pseudo && len(want) >= 1 && i == want[0] { t.Errorf("%s(%v, base=2) = false, want true", name, i) } diff --git a/libgo/go/math/big/ratconv.go b/libgo/go/math/big/ratconv.go index a6a401c..4bc6ef7 100644 --- a/libgo/go/math/big/ratconv.go +++ b/libgo/go/math/big/ratconv.go @@ -40,8 +40,8 @@ func (z *Rat) Scan(s fmt.ScanState, ch rune) error { // SetString sets z to the value of s and returns z and a boolean indicating // success. s can be given as a fraction "a/b" or as a floating-point number // optionally followed by an exponent. The entire string (not just a prefix) -// must be valid for success. If the operation failed, the value of z is un- -// defined but the returned value is nil. +// must be valid for success. If the operation failed, the value of z is +// undefined but the returned value is nil. func (z *Rat) SetString(s string) (*Rat, bool) { if len(s) == 0 { return nil, false diff --git a/libgo/go/math/bits/bits.go b/libgo/go/math/bits/bits.go new file mode 100644 index 0000000..989baac --- /dev/null +++ b/libgo/go/math/bits/bits.go @@ -0,0 +1,330 @@ +// Copyright 2017 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. + +//go:generate go run make_tables.go + +// Package bits implements bit counting and manipulation +// functions for the predeclared unsigned integer types. +package bits + +const uintSize = 32 << (^uint(0) >> 32 & 1) // 32 or 64 + +// UintSize is the size of a uint in bits. +const UintSize = uintSize + +// --- LeadingZeros --- + +// LeadingZeros returns the number of leading zero bits in x; the result is UintSize for x == 0. +func LeadingZeros(x uint) int { return UintSize - Len(x) } + +// LeadingZeros8 returns the number of leading zero bits in x; the result is 8 for x == 0. +func LeadingZeros8(x uint8) int { return 8 - Len8(x) } + +// LeadingZeros16 returns the number of leading zero bits in x; the result is 16 for x == 0. +func LeadingZeros16(x uint16) int { return 16 - Len16(x) } + +// LeadingZeros32 returns the number of leading zero bits in x; the result is 32 for x == 0. +func LeadingZeros32(x uint32) int { return 32 - Len32(x) } + +// LeadingZeros64 returns the number of leading zero bits in x; the result is 64 for x == 0. +func LeadingZeros64(x uint64) int { return 64 - Len64(x) } + +// --- TrailingZeros --- + +// See http://supertech.csail.mit.edu/papers/debruijn.pdf +const deBruijn32 = 0x077CB531 + +var deBruijn32tab = [32]byte{ + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, +} + +const deBruijn64 = 0x03f79d71b4ca8b09 + +var deBruijn64tab = [64]byte{ + 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, + 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, + 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, + 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6, +} + +// TrailingZeros returns the number of trailing zero bits in x; the result is UintSize for x == 0. +func TrailingZeros(x uint) int { + if UintSize == 32 { + return TrailingZeros32(uint32(x)) + } + return TrailingZeros64(uint64(x)) +} + +// TrailingZeros8 returns the number of trailing zero bits in x; the result is 8 for x == 0. +func TrailingZeros8(x uint8) int { + return int(ntz8tab[x]) +} + +// TrailingZeros16 returns the number of trailing zero bits in x; the result is 16 for x == 0. +func TrailingZeros16(x uint16) (n int) { + if x == 0 { + return 16 + } + // see comment in TrailingZeros64 + return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)]) +} + +// TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0. +func TrailingZeros32(x uint32) int { + if x == 0 { + return 32 + } + // see comment in TrailingZeros64 + return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)]) +} + +// TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0. +func TrailingZeros64(x uint64) int { + if x == 0 { + return 64 + } + // If popcount is fast, replace code below with return popcount(^x & (x - 1)). + // + // x & -x leaves only the right-most bit set in the word. Let k be the + // index of that bit. Since only a single bit is set, the value is two + // to the power of k. Multiplying by a power of two is equivalent to + // left shifting, in this case by k bits. The de Bruijn (64 bit) constant + // is such that all six bit, consecutive substrings are distinct. + // Therefore, if we have a left shifted version of this constant we can + // find by how many bits it was shifted by looking at which six bit + // substring ended up at the top of the word. + // (Knuth, volume 4, section 7.3.1) + return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)]) +} + +// --- OnesCount --- + +const m0 = 0x5555555555555555 // 01010101 ... +const m1 = 0x3333333333333333 // 00110011 ... +const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ... +const m3 = 0x00ff00ff00ff00ff // etc. +const m4 = 0x0000ffff0000ffff + +// OnesCount returns the number of one bits ("population count") in x. +func OnesCount(x uint) int { + if UintSize == 32 { + return OnesCount32(uint32(x)) + } + return OnesCount64(uint64(x)) +} + +// OnesCount8 returns the number of one bits ("population count") in x. +func OnesCount8(x uint8) int { + return int(pop8tab[x]) +} + +// OnesCount16 returns the number of one bits ("population count") in x. +func OnesCount16(x uint16) int { + return int(pop8tab[x>>8] + pop8tab[x&0xff]) +} + +// OnesCount32 returns the number of one bits ("population count") in x. +func OnesCount32(x uint32) int { + return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff]) +} + +// OnesCount64 returns the number of one bits ("population count") in x. +func OnesCount64(x uint64) int { + // Implementation: Parallel summing of adjacent bits. + // See "Hacker's Delight", Chap. 5: Counting Bits. + // The following pattern shows the general approach: + // + // x = x>>1&(m0&m) + x&(m0&m) + // x = x>>2&(m1&m) + x&(m1&m) + // x = x>>4&(m2&m) + x&(m2&m) + // x = x>>8&(m3&m) + x&(m3&m) + // x = x>>16&(m4&m) + x&(m4&m) + // x = x>>32&(m5&m) + x&(m5&m) + // return int(x) + // + // Masking (& operations) can be left away when there's no + // danger that a field's sum will carry over into the next + // field: Since the result cannot be > 64, 8 bits is enough + // and we can ignore the masks for the shifts by 8 and up. + // Per "Hacker's Delight", the first line can be simplified + // more, but it saves at best one instruction, so we leave + // it alone for clarity. + const m = 1<<64 - 1 + x = x>>1&(m0&m) + x&(m0&m) + x = x>>2&(m1&m) + x&(m1&m) + x = (x>>4 + x) & (m2 & m) + x += x >> 8 + x += x >> 16 + x += x >> 32 + return int(x) & (1<<7 - 1) +} + +// --- RotateLeft --- + +// RotateLeft returns the value of x rotated left by (k mod UintSize) bits. +// To rotate x right by k bits, call RotateLeft(x, -k). +func RotateLeft(x uint, k int) uint { + if UintSize == 32 { + return uint(RotateLeft32(uint32(x), k)) + } + return uint(RotateLeft64(uint64(x), k)) +} + +// RotateLeft8 returns the value of x rotated left by (k mod 8) bits. +// To rotate x right by k bits, call RotateLeft8(x, -k). +func RotateLeft8(x uint8, k int) uint8 { + const n = 8 + s := uint(k) & (n - 1) + return x<<s | x>>(n-s) +} + +// RotateLeft16 returns the value of x rotated left by (k mod 16) bits. +// To rotate x right by k bits, call RotateLeft16(x, -k). +func RotateLeft16(x uint16, k int) uint16 { + const n = 16 + s := uint(k) & (n - 1) + return x<<s | x>>(n-s) +} + +// RotateLeft32 returns the value of x rotated left by (k mod 32) bits. +// To rotate x right by k bits, call RotateLeft32(x, -k). +func RotateLeft32(x uint32, k int) uint32 { + const n = 32 + s := uint(k) & (n - 1) + return x<<s | x>>(n-s) +} + +// RotateLeft64 returns the value of x rotated left by (k mod 64) bits. +// To rotate x right by k bits, call RotateLeft64(x, -k). +func RotateLeft64(x uint64, k int) uint64 { + const n = 64 + s := uint(k) & (n - 1) + return x<<s | x>>(n-s) +} + +// --- Reverse --- + +// Reverse returns the value of x with its bits in reversed order. +func Reverse(x uint) uint { + if UintSize == 32 { + return uint(Reverse32(uint32(x))) + } + return uint(Reverse64(uint64(x))) +} + +// Reverse8 returns the value of x with its bits in reversed order. +func Reverse8(x uint8) uint8 { + return rev8tab[x] +} + +// Reverse16 returns the value of x with its bits in reversed order. +func Reverse16(x uint16) uint16 { + return uint16(rev8tab[x>>8]) | uint16(rev8tab[x&0xff])<<8 +} + +// Reverse32 returns the value of x with its bits in reversed order. +func Reverse32(x uint32) uint32 { + const m = 1<<32 - 1 + x = x>>1&(m0&m) | x&(m0&m)<<1 + x = x>>2&(m1&m) | x&(m1&m)<<2 + x = x>>4&(m2&m) | x&(m2&m)<<4 + x = x>>8&(m3&m) | x&(m3&m)<<8 + return x>>16 | x<<16 +} + +// Reverse64 returns the value of x with its bits in reversed order. +func Reverse64(x uint64) uint64 { + const m = 1<<64 - 1 + x = x>>1&(m0&m) | x&(m0&m)<<1 + x = x>>2&(m1&m) | x&(m1&m)<<2 + x = x>>4&(m2&m) | x&(m2&m)<<4 + x = x>>8&(m3&m) | x&(m3&m)<<8 + x = x>>16&(m4&m) | x&(m4&m)<<16 + return x>>32 | x<<32 +} + +// --- ReverseBytes --- + +// ReverseBytes returns the value of x with its bytes in reversed order. +func ReverseBytes(x uint) uint { + if UintSize == 32 { + return uint(ReverseBytes32(uint32(x))) + } + return uint(ReverseBytes64(uint64(x))) +} + +// ReverseBytes16 returns the value of x with its bytes in reversed order. +func ReverseBytes16(x uint16) uint16 { + return x>>8 | x<<8 +} + +// ReverseBytes32 returns the value of x with its bytes in reversed order. +func ReverseBytes32(x uint32) uint32 { + const m = 1<<32 - 1 + x = x>>8&(m3&m) | x&(m3&m)<<8 + return x>>16 | x<<16 +} + +// ReverseBytes64 returns the value of x with its bytes in reversed order. +func ReverseBytes64(x uint64) uint64 { + const m = 1<<64 - 1 + x = x>>8&(m3&m) | x&(m3&m)<<8 + x = x>>16&(m4&m) | x&(m4&m)<<16 + return x>>32 | x<<32 +} + +// --- Len --- + +// Len returns the minimum number of bits required to represent x; the result is 0 for x == 0. +func Len(x uint) int { + if UintSize == 32 { + return Len32(uint32(x)) + } + return Len64(uint64(x)) +} + +// Len8 returns the minimum number of bits required to represent x; the result is 0 for x == 0. +func Len8(x uint8) int { + return int(len8tab[x]) +} + +// Len16 returns the minimum number of bits required to represent x; the result is 0 for x == 0. +func Len16(x uint16) (n int) { + if x >= 1<<8 { + x >>= 8 + n = 8 + } + return n + int(len8tab[x]) +} + +// Len32 returns the minimum number of bits required to represent x; the result is 0 for x == 0. +func Len32(x uint32) (n int) { + if x >= 1<<16 { + x >>= 16 + n = 16 + } + if x >= 1<<8 { + x >>= 8 + n += 8 + } + return n + int(len8tab[x]) +} + +// Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0. +func Len64(x uint64) (n int) { + if x >= 1<<32 { + x >>= 32 + n = 32 + } + if x >= 1<<16 { + x >>= 16 + n += 16 + } + if x >= 1<<8 { + x >>= 8 + n += 8 + } + return n + int(len8tab[x]) +} diff --git a/libgo/go/math/bits/bits_tables.go b/libgo/go/math/bits/bits_tables.go new file mode 100644 index 0000000..f1e15a0 --- /dev/null +++ b/libgo/go/math/bits/bits_tables.go @@ -0,0 +1,83 @@ +// Copyright 2017 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. + +// Code generated by go run make_tables.go. DO NOT EDIT. + +package bits + +var ntz8tab = [256]uint8{ + 0x08, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x07, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, + 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, +} + +var pop8tab = [256]uint8{ + 0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03, 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, + 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, + 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, + 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, + 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, + 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, + 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, + 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08, +} + +var rev8tab = [256]uint8{ + 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, + 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, + 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, + 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, + 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, + 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, + 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, + 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, + 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, + 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, + 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, + 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, + 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, + 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, + 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, + 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, +} + +var len8tab = [256]uint8{ + 0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, + 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, + 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, + 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, +} diff --git a/libgo/go/math/bits/bits_test.go b/libgo/go/math/bits/bits_test.go new file mode 100644 index 0000000..ba05210 --- /dev/null +++ b/libgo/go/math/bits/bits_test.go @@ -0,0 +1,747 @@ +// Copyright 2017 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 bits + +import ( + "testing" + "unsafe" +) + +func TestUintSize(t *testing.T) { + var x uint + if want := unsafe.Sizeof(x) * 8; UintSize != want { + t.Fatalf("UintSize = %d; want %d", UintSize, want) + } +} + +func TestLeadingZeros(t *testing.T) { + for i := 0; i < 256; i++ { + nlz := tab[i].nlz + for k := 0; k < 64-8; k++ { + x := uint64(i) << uint(k) + if x <= 1<<8-1 { + got := LeadingZeros8(uint8(x)) + want := nlz - k + (8 - 8) + if x == 0 { + want = 8 + } + if got != want { + t.Fatalf("LeadingZeros8(%#02x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<16-1 { + got := LeadingZeros16(uint16(x)) + want := nlz - k + (16 - 8) + if x == 0 { + want = 16 + } + if got != want { + t.Fatalf("LeadingZeros16(%#04x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<32-1 { + got := LeadingZeros32(uint32(x)) + want := nlz - k + (32 - 8) + if x == 0 { + want = 32 + } + if got != want { + t.Fatalf("LeadingZeros32(%#08x) == %d; want %d", x, got, want) + } + if UintSize == 32 { + got = LeadingZeros(uint(x)) + if got != want { + t.Fatalf("LeadingZeros(%#08x) == %d; want %d", x, got, want) + } + } + } + + if x <= 1<<64-1 { + got := LeadingZeros64(uint64(x)) + want := nlz - k + (64 - 8) + if x == 0 { + want = 64 + } + if got != want { + t.Fatalf("LeadingZeros64(%#016x) == %d; want %d", x, got, want) + } + if UintSize == 64 { + got = LeadingZeros(uint(x)) + if got != want { + t.Fatalf("LeadingZeros(%#016x) == %d; want %d", x, got, want) + } + } + } + } + } +} + +// Exported (global) variable serving as input for some +// of the benchmarks to ensure side-effect free calls +// are not optimized away. +var Input uint64 = deBruijn64 + +// Exported (global) variable to store function results +// during benchmarking to ensure side-effect free calls +// are not optimized away. +var Output int + +func BenchmarkLeadingZeros(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += LeadingZeros(uint(Input) >> (uint(i) % UintSize)) + } + Output = s +} + +func BenchmarkLeadingZeros8(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += LeadingZeros8(uint8(Input) >> (uint(i) % 8)) + } + Output = s +} + +func BenchmarkLeadingZeros16(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += LeadingZeros16(uint16(Input) >> (uint(i) % 16)) + } + Output = s +} + +func BenchmarkLeadingZeros32(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += LeadingZeros32(uint32(Input) >> (uint(i) % 32)) + } + Output = s +} + +func BenchmarkLeadingZeros64(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += LeadingZeros64(uint64(Input) >> (uint(i) % 64)) + } + Output = s +} + +func TestTrailingZeros(t *testing.T) { + for i := 0; i < 256; i++ { + ntz := tab[i].ntz + for k := 0; k < 64-8; k++ { + x := uint64(i) << uint(k) + want := ntz + k + if x <= 1<<8-1 { + got := TrailingZeros8(uint8(x)) + if x == 0 { + want = 8 + } + if got != want { + t.Fatalf("TrailingZeros8(%#02x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<16-1 { + got := TrailingZeros16(uint16(x)) + if x == 0 { + want = 16 + } + if got != want { + t.Fatalf("TrailingZeros16(%#04x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<32-1 { + got := TrailingZeros32(uint32(x)) + if x == 0 { + want = 32 + } + if got != want { + t.Fatalf("TrailingZeros32(%#08x) == %d; want %d", x, got, want) + } + if UintSize == 32 { + got = TrailingZeros(uint(x)) + if got != want { + t.Fatalf("TrailingZeros(%#08x) == %d; want %d", x, got, want) + } + } + } + + if x <= 1<<64-1 { + got := TrailingZeros64(uint64(x)) + if x == 0 { + want = 64 + } + if got != want { + t.Fatalf("TrailingZeros64(%#016x) == %d; want %d", x, got, want) + } + if UintSize == 64 { + got = TrailingZeros(uint(x)) + if got != want { + t.Fatalf("TrailingZeros(%#016x) == %d; want %d", x, got, want) + } + } + } + } + } +} + +func BenchmarkTrailingZeros(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += TrailingZeros(uint(Input) << (uint(i) % UintSize)) + } + Output = s +} + +func BenchmarkTrailingZeros8(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += TrailingZeros8(uint8(Input) << (uint(i) % 8)) + } + Output = s +} + +func BenchmarkTrailingZeros16(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += TrailingZeros16(uint16(Input) << (uint(i) % 16)) + } + Output = s +} + +func BenchmarkTrailingZeros32(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += TrailingZeros32(uint32(Input) << (uint(i) % 32)) + } + Output = s +} + +func BenchmarkTrailingZeros64(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += TrailingZeros64(uint64(Input) << (uint(i) % 64)) + } + Output = s +} + +func TestOnesCount(t *testing.T) { + var x uint64 + for i := 0; i <= 64; i++ { + testOnesCount(t, x, i) + x = x<<1 | 1 + } + + for i := 64; i >= 0; i-- { + testOnesCount(t, x, i) + x = x << 1 + } + + for i := 0; i < 256; i++ { + for k := 0; k < 64-8; k++ { + testOnesCount(t, uint64(i)<<uint(k), tab[i].pop) + } + } +} + +func testOnesCount(t *testing.T, x uint64, want int) { + if x <= 1<<8-1 { + got := OnesCount8(uint8(x)) + if got != want { + t.Fatalf("OnesCount8(%#02x) == %d; want %d", uint8(x), got, want) + } + } + + if x <= 1<<16-1 { + got := OnesCount16(uint16(x)) + if got != want { + t.Fatalf("OnesCount16(%#04x) == %d; want %d", uint16(x), got, want) + } + } + + if x <= 1<<32-1 { + got := OnesCount32(uint32(x)) + if got != want { + t.Fatalf("OnesCount32(%#08x) == %d; want %d", uint32(x), got, want) + } + if UintSize == 32 { + got = OnesCount(uint(x)) + if got != want { + t.Fatalf("OnesCount(%#08x) == %d; want %d", uint32(x), got, want) + } + } + } + + if x <= 1<<64-1 { + got := OnesCount64(uint64(x)) + if got != want { + t.Fatalf("OnesCount64(%#016x) == %d; want %d", x, got, want) + } + if UintSize == 64 { + got = OnesCount(uint(x)) + if got != want { + t.Fatalf("OnesCount(%#016x) == %d; want %d", x, got, want) + } + } + } +} + +func BenchmarkOnesCount(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += OnesCount(uint(Input)) + } + Output = s +} + +func BenchmarkOnesCount8(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += OnesCount8(uint8(Input)) + } + Output = s +} + +func BenchmarkOnesCount16(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += OnesCount16(uint16(Input)) + } + Output = s +} + +func BenchmarkOnesCount32(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += OnesCount32(uint32(Input)) + } + Output = s +} + +func BenchmarkOnesCount64(b *testing.B) { + var s int + for i := 0; i < b.N; i++ { + s += OnesCount64(uint64(Input)) + } + Output = s +} + +func TestRotateLeft(t *testing.T) { + var m uint64 = deBruijn64 + + for k := uint(0); k < 128; k++ { + x8 := uint8(m) + got8 := RotateLeft8(x8, int(k)) + want8 := x8<<(k&0x7) | x8>>(8-k&0x7) + if got8 != want8 { + t.Fatalf("RotateLeft8(%#02x, %d) == %#02x; want %#02x", x8, k, got8, want8) + } + got8 = RotateLeft8(want8, -int(k)) + if got8 != x8 { + t.Fatalf("RotateLeft8(%#02x, -%d) == %#02x; want %#02x", want8, k, got8, x8) + } + + x16 := uint16(m) + got16 := RotateLeft16(x16, int(k)) + want16 := x16<<(k&0xf) | x16>>(16-k&0xf) + if got16 != want16 { + t.Fatalf("RotateLeft16(%#04x, %d) == %#04x; want %#04x", x16, k, got16, want16) + } + got16 = RotateLeft16(want16, -int(k)) + if got16 != x16 { + t.Fatalf("RotateLeft16(%#04x, -%d) == %#04x; want %#04x", want16, k, got16, x16) + } + + x32 := uint32(m) + got32 := RotateLeft32(x32, int(k)) + want32 := x32<<(k&0x1f) | x32>>(32-k&0x1f) + if got32 != want32 { + t.Fatalf("RotateLeft32(%#08x, %d) == %#08x; want %#08x", x32, k, got32, want32) + } + got32 = RotateLeft32(want32, -int(k)) + if got32 != x32 { + t.Fatalf("RotateLeft32(%#08x, -%d) == %#08x; want %#08x", want32, k, got32, x32) + } + if UintSize == 32 { + x := uint(m) + got := RotateLeft(x, int(k)) + want := x<<(k&0x1f) | x>>(32-k&0x1f) + if got != want { + t.Fatalf("RotateLeft(%#08x, %d) == %#08x; want %#08x", x, k, got, want) + } + got = RotateLeft(want, -int(k)) + if got != x { + t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x) + } + } + + x64 := uint64(m) + got64 := RotateLeft64(x64, int(k)) + want64 := x64<<(k&0x3f) | x64>>(64-k&0x3f) + if got64 != want64 { + t.Fatalf("RotateLeft64(%#016x, %d) == %#016x; want %#016x", x64, k, got64, want64) + } + got64 = RotateLeft64(want64, -int(k)) + if got64 != x64 { + t.Fatalf("RotateLeft64(%#016x, -%d) == %#016x; want %#016x", want64, k, got64, x64) + } + if UintSize == 64 { + x := uint(m) + got := RotateLeft(x, int(k)) + want := x<<(k&0x3f) | x>>(64-k&0x3f) + if got != want { + t.Fatalf("RotateLeft(%#016x, %d) == %#016x; want %#016x", x, k, got, want) + } + got = RotateLeft(want, -int(k)) + if got != x { + t.Fatalf("RotateLeft(%#08x, -%d) == %#08x; want %#08x", want, k, got, x) + } + } + } +} + +func BenchmarkRotateLeft(b *testing.B) { + var s uint + for i := 0; i < b.N; i++ { + s += RotateLeft(uint(Input), i) + } + Output = int(s) +} + +func BenchmarkRotateLeft8(b *testing.B) { + var s uint8 + for i := 0; i < b.N; i++ { + s += RotateLeft8(uint8(Input), i) + } + Output = int(s) +} + +func BenchmarkRotateLeft16(b *testing.B) { + var s uint16 + for i := 0; i < b.N; i++ { + s += RotateLeft16(uint16(Input), i) + } + Output = int(s) +} + +func BenchmarkRotateLeft32(b *testing.B) { + var s uint32 + for i := 0; i < b.N; i++ { + s += RotateLeft32(uint32(Input), i) + } + Output = int(s) +} + +func BenchmarkRotateLeft64(b *testing.B) { + var s uint64 + for i := 0; i < b.N; i++ { + s += RotateLeft64(uint64(Input), i) + } + Output = int(s) +} + +func TestReverse(t *testing.T) { + // test each bit + for i := uint(0); i < 64; i++ { + testReverse(t, uint64(1)<<i, uint64(1)<<(63-i)) + } + + // test a few patterns + for _, test := range []struct { + x, r uint64 + }{ + {0, 0}, + {0x1, 0x8 << 60}, + {0x2, 0x4 << 60}, + {0x3, 0xc << 60}, + {0x4, 0x2 << 60}, + {0x5, 0xa << 60}, + {0x6, 0x6 << 60}, + {0x7, 0xe << 60}, + {0x8, 0x1 << 60}, + {0x9, 0x9 << 60}, + {0xa, 0x5 << 60}, + {0xb, 0xd << 60}, + {0xc, 0x3 << 60}, + {0xd, 0xb << 60}, + {0xe, 0x7 << 60}, + {0xf, 0xf << 60}, + {0x5686487, 0xe12616a000000000}, + {0x0123456789abcdef, 0xf7b3d591e6a2c480}, + } { + testReverse(t, test.x, test.r) + testReverse(t, test.r, test.x) + } +} + +func testReverse(t *testing.T, x64, want64 uint64) { + x8 := uint8(x64) + got8 := Reverse8(x8) + want8 := uint8(want64 >> (64 - 8)) + if got8 != want8 { + t.Fatalf("Reverse8(%#02x) == %#02x; want %#02x", x8, got8, want8) + } + + x16 := uint16(x64) + got16 := Reverse16(x16) + want16 := uint16(want64 >> (64 - 16)) + if got16 != want16 { + t.Fatalf("Reverse16(%#04x) == %#04x; want %#04x", x16, got16, want16) + } + + x32 := uint32(x64) + got32 := Reverse32(x32) + want32 := uint32(want64 >> (64 - 32)) + if got32 != want32 { + t.Fatalf("Reverse32(%#08x) == %#08x; want %#08x", x32, got32, want32) + } + if UintSize == 32 { + x := uint(x32) + got := Reverse(x) + want := uint(want32) + if got != want { + t.Fatalf("Reverse(%#08x) == %#08x; want %#08x", x, got, want) + } + } + + got64 := Reverse64(x64) + if got64 != want64 { + t.Fatalf("Reverse64(%#016x) == %#016x; want %#016x", x64, got64, want64) + } + if UintSize == 64 { + x := uint(x64) + got := Reverse(x) + want := uint(want64) + if got != want { + t.Fatalf("Reverse(%#08x) == %#016x; want %#016x", x, got, want) + } + } +} + +func BenchmarkReverse(b *testing.B) { + var s uint + for i := 0; i < b.N; i++ { + s += Reverse(uint(i)) + } + Output = int(s) +} + +func BenchmarkReverse8(b *testing.B) { + var s uint8 + for i := 0; i < b.N; i++ { + s += Reverse8(uint8(i)) + } + Output = int(s) +} + +func BenchmarkReverse16(b *testing.B) { + var s uint16 + for i := 0; i < b.N; i++ { + s += Reverse16(uint16(i)) + } + Output = int(s) +} + +func BenchmarkReverse32(b *testing.B) { + var s uint32 + for i := 0; i < b.N; i++ { + s += Reverse32(uint32(i)) + } + Output = int(s) +} + +func BenchmarkReverse64(b *testing.B) { + var s uint64 + for i := 0; i < b.N; i++ { + s += Reverse64(uint64(i)) + } + Output = int(s) +} + +func TestReverseBytes(t *testing.T) { + for _, test := range []struct { + x, r uint64 + }{ + {0, 0}, + {0x01, 0x01 << 56}, + {0x0123, 0x2301 << 48}, + {0x012345, 0x452301 << 40}, + {0x01234567, 0x67452301 << 32}, + {0x0123456789, 0x8967452301 << 24}, + {0x0123456789ab, 0xab8967452301 << 16}, + {0x0123456789abcd, 0xcdab8967452301 << 8}, + {0x0123456789abcdef, 0xefcdab8967452301 << 0}, + } { + testReverseBytes(t, test.x, test.r) + testReverseBytes(t, test.r, test.x) + } +} + +func testReverseBytes(t *testing.T, x64, want64 uint64) { + x16 := uint16(x64) + got16 := ReverseBytes16(x16) + want16 := uint16(want64 >> (64 - 16)) + if got16 != want16 { + t.Fatalf("ReverseBytes16(%#04x) == %#04x; want %#04x", x16, got16, want16) + } + + x32 := uint32(x64) + got32 := ReverseBytes32(x32) + want32 := uint32(want64 >> (64 - 32)) + if got32 != want32 { + t.Fatalf("ReverseBytes32(%#08x) == %#08x; want %#08x", x32, got32, want32) + } + if UintSize == 32 { + x := uint(x32) + got := ReverseBytes(x) + want := uint(want32) + if got != want { + t.Fatalf("ReverseBytes(%#08x) == %#08x; want %#08x", x, got, want) + } + } + + got64 := ReverseBytes64(x64) + if got64 != want64 { + t.Fatalf("ReverseBytes64(%#016x) == %#016x; want %#016x", x64, got64, want64) + } + if UintSize == 64 { + x := uint(x64) + got := ReverseBytes(x) + want := uint(want64) + if got != want { + t.Fatalf("ReverseBytes(%#016x) == %#016x; want %#016x", x, got, want) + } + } +} + +func BenchmarkReverseBytes(b *testing.B) { + var s uint + for i := 0; i < b.N; i++ { + s += ReverseBytes(uint(i)) + } + Output = int(s) +} + +func BenchmarkReverseBytes16(b *testing.B) { + var s uint16 + for i := 0; i < b.N; i++ { + s += ReverseBytes16(uint16(i)) + } + Output = int(s) +} + +func BenchmarkReverseBytes32(b *testing.B) { + var s uint32 + for i := 0; i < b.N; i++ { + s += ReverseBytes32(uint32(i)) + } + Output = int(s) +} + +func BenchmarkReverseBytes64(b *testing.B) { + var s uint64 + for i := 0; i < b.N; i++ { + s += ReverseBytes64(uint64(i)) + } + Output = int(s) +} + +func TestLen(t *testing.T) { + for i := 0; i < 256; i++ { + len := 8 - tab[i].nlz + for k := 0; k < 64-8; k++ { + x := uint64(i) << uint(k) + want := 0 + if x != 0 { + want = len + k + } + if x <= 1<<8-1 { + got := Len8(uint8(x)) + if got != want { + t.Fatalf("Len8(%#02x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<16-1 { + got := Len16(uint16(x)) + if got != want { + t.Fatalf("Len16(%#04x) == %d; want %d", x, got, want) + } + } + + if x <= 1<<32-1 { + got := Len32(uint32(x)) + if got != want { + t.Fatalf("Len32(%#08x) == %d; want %d", x, got, want) + } + if UintSize == 32 { + got := Len(uint(x)) + if got != want { + t.Fatalf("Len(%#08x) == %d; want %d", x, got, want) + } + } + } + + if x <= 1<<64-1 { + got := Len64(uint64(x)) + if got != want { + t.Fatalf("Len64(%#016x) == %d; want %d", x, got, want) + } + if UintSize == 64 { + got := Len(uint(x)) + if got != want { + t.Fatalf("Len(%#016x) == %d; want %d", x, got, want) + } + } + } + } + } +} + +// ---------------------------------------------------------------------------- +// Testing support + +type entry = struct { + nlz, ntz, pop int +} + +// tab contains results for all uint8 values +var tab [256]entry + +func init() { + tab[0] = entry{8, 8, 0} + for i := 1; i < len(tab); i++ { + // nlz + x := i // x != 0 + n := 0 + for x&0x80 == 0 { + n++ + x <<= 1 + } + tab[i].nlz = n + + // ntz + x = i // x != 0 + n = 0 + for x&1 == 0 { + n++ + x >>= 1 + } + tab[i].ntz = n + + // pop + x = i // x != 0 + n = 0 + for x != 0 { + n += int(x & 1) + x >>= 1 + } + tab[i].pop = n + } +} diff --git a/libgo/go/math/bits/example_test.go b/libgo/go/math/bits/example_test.go new file mode 100644 index 0000000..78750da --- /dev/null +++ b/libgo/go/math/bits/example_test.go @@ -0,0 +1,80 @@ +// Copyright 2017 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 ignore + +package bits_test + +import ( + "fmt" + "math/bits" +) + +func ExampleLeadingZeros16() { + fmt.Println(bits.LeadingZeros16(0)) + fmt.Println(bits.LeadingZeros16(1)) + fmt.Println(bits.LeadingZeros16(256)) + fmt.Println(bits.LeadingZeros16(65535)) + // Output: + // 16 + // 15 + // 7 + // 0 +} + +func ExampleLeadingZeros32() { + fmt.Println(bits.LeadingZeros32(0)) + fmt.Println(bits.LeadingZeros32(1)) + // Output: + // 32 + // 31 +} + +func ExampleLeadingZeros64() { + fmt.Println(bits.LeadingZeros64(0)) + fmt.Println(bits.LeadingZeros64(1)) + // Output: + // 64 + // 63 +} + +func ExampleOnesCount() { + fmt.Printf("%b\n", 14) + fmt.Println(bits.OnesCount(14)) + // Output: + // 1110 + // 3 +} + +func ExampleOnesCount8() { + fmt.Printf("%b\n", 14) + fmt.Println(bits.OnesCount8(14)) + // Output: + // 1110 + // 3 +} + +func ExampleOnesCount16() { + fmt.Printf("%b\n", 14) + fmt.Println(bits.OnesCount16(14)) + // Output: + // 1110 + // 3 +} + +func ExampleOnesCount32() { + fmt.Printf("%b\n", 14) + fmt.Println(bits.OnesCount32(14)) + // Output: + // 1110 + // 3 +} + +func ExampleOnesCount64() { + fmt.Printf("%b\n", 14) + fmt.Println(bits.OnesCount64(14)) + // Output: + // 1110 + // 3 +} diff --git a/libgo/go/math/bits/make_tables.go b/libgo/go/math/bits/make_tables.go new file mode 100644 index 0000000..ff2fe2e --- /dev/null +++ b/libgo/go/math/bits/make_tables.go @@ -0,0 +1,92 @@ +// Copyright 2017 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 ignore + +// This program generates bits_tables.go. + +package main + +import ( + "bytes" + "fmt" + "go/format" + "io" + "io/ioutil" + "log" +) + +var header = []byte(`// Copyright 2017 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. + +// Code generated by go run make_tables.go. DO NOT EDIT. + +package bits + +`) + +func main() { + buf := bytes.NewBuffer(header) + + gen(buf, "ntz8tab", ntz8) + gen(buf, "pop8tab", pop8) + gen(buf, "rev8tab", rev8) + gen(buf, "len8tab", len8) + + out, err := format.Source(buf.Bytes()) + if err != nil { + log.Fatal(err) + } + + err = ioutil.WriteFile("bits_tables.go", out, 0666) + if err != nil { + log.Fatal(err) + } +} + +func gen(w io.Writer, name string, f func(uint8) uint8) { + fmt.Fprintf(w, "var %s = [256]uint8{", name) + for i := 0; i < 256; i++ { + if i%16 == 0 { + fmt.Fprint(w, "\n\t") + } else { + fmt.Fprint(w, " ") + } + fmt.Fprintf(w, "%#02x,", f(uint8(i))) + } + fmt.Fprint(w, "\n}\n\n") +} + +func ntz8(x uint8) (n uint8) { + for x&1 == 0 && n < 8 { + x >>= 1 + n++ + } + return +} + +func pop8(x uint8) (n uint8) { + for x != 0 { + x &= x - 1 + n++ + } + return +} + +func rev8(x uint8) (r uint8) { + for i := 8; i > 0; i-- { + r = r<<1 | x&1 + x >>= 1 + } + return +} + +func len8(x uint8) (n uint8) { + for x != 0 { + x >>= 1 + n++ + } + return +} diff --git a/libgo/go/math/cbrt.go b/libgo/go/math/cbrt.go index f009faf..374ab6d 100644 --- a/libgo/go/math/cbrt.go +++ b/libgo/go/math/cbrt.go @@ -23,6 +23,13 @@ package math // Cbrt(±Inf) = ±Inf // Cbrt(NaN) = NaN func Cbrt(x float64) float64 { + return libc_cbrt(x) +} + +//extern cbrt +func libc_cbrt(float64) float64 + +func cbrt(x float64) float64 { const ( B1 = 715094163 // (682-0.03306235651)*2**20 B2 = 696219795 // (664-0.03306235651)*2**20 diff --git a/libgo/go/math/const.go b/libgo/go/math/const.go index b440538..20b7065 100644 --- a/libgo/go/math/const.go +++ b/libgo/go/math/const.go @@ -3,6 +3,8 @@ // license that can be found in the LICENSE file. // Package math provides basic constants and mathematical functions. +// +// This package does not guarantee bit-identical results across architectures. package math // Mathematical constants. diff --git a/libgo/go/math/erf.go b/libgo/go/math/erf.go index 8ddd5f9..e2a0422 100644 --- a/libgo/go/math/erf.go +++ b/libgo/go/math/erf.go @@ -186,6 +186,13 @@ const ( // Erf(-Inf) = -1 // Erf(NaN) = NaN func Erf(x float64) float64 { + return libc_erf(x) +} + +//extern erf +func libc_erf(float64) float64 + +func erf(x float64) float64 { const ( VeryTiny = 2.848094538889218e-306 // 0x0080000000000000 Small = 1.0 / (1 << 28) // 2**-28 @@ -263,6 +270,13 @@ func Erf(x float64) float64 { // Erfc(-Inf) = 2 // Erfc(NaN) = NaN func Erfc(x float64) float64 { + return libc_erfc(x) +} + +//extern erfc +func libc_erfc(float64) float64 + +func erfc(x float64) float64 { const Tiny = 1.0 / (1 << 56) // 2**-56 // special cases switch { diff --git a/libgo/go/math/example_test.go b/libgo/go/math/example_test.go new file mode 100644 index 0000000..12e9876 --- /dev/null +++ b/libgo/go/math/example_test.go @@ -0,0 +1,20 @@ +// Copyright 2017 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 math_test + +import ( + "fmt" + "math" +) + +func ExampleSqrt() { + const ( + a = 3 + b = 4 + ) + c := math.Sqrt(a*a + b*b) + fmt.Printf("%.1f", c) + // Output: 5.0 +} diff --git a/libgo/go/math/export_s390x_test.go b/libgo/go/math/export_s390x_test.go index 2e7f584..3a52d6b 100644 --- a/libgo/go/math/export_s390x_test.go +++ b/libgo/go/math/export_s390x_test.go @@ -13,4 +13,21 @@ var CoshNoVec = cosh var SinNoVec = sin var SinhNoVec = sinh var TanhNoVec = tanh +var Log1pNovec = log1p +var AtanhNovec = atanh +var AcosNovec = acos +var AcoshNovec = acosh +var AsinNovec = asin +var AsinhNovec = asinh +var ErfNovec = erf +var ErfcNovec = erfc +var AtanNovec = atan +var Atan2Novec = atan2 +var CbrtNovec = cbrt +var LogNovec = log +var TanNovec = tan +var ExpNovec = exp +var Expm1Novec = expm1 +var PowNovec = pow +var HypotNovec = hypot var HasVX = hasVX diff --git a/libgo/go/math/floor_asm.go b/libgo/go/math/floor_asm.go index 9a2487a..761349a 100644 --- a/libgo/go/math/floor_asm.go +++ b/libgo/go/math/floor_asm.go @@ -7,7 +7,6 @@ package math -//defined in floor_amd64.s -func hasSSE4() bool +import "internal/cpu" -var useSSE4 = hasSSE4() +var useSSE41 = cpu.X86.HasSSE41 diff --git a/libgo/go/math/jn.go b/libgo/go/math/jn.go index 3422782..4a8ddfa 100644 --- a/libgo/go/math/jn.go +++ b/libgo/go/math/jn.go @@ -226,10 +226,10 @@ func Jn(n int, x float64) float64 { // // Special cases are: // Yn(n, +Inf) = 0 -// Yn(n > 0, 0) = -Inf +// Yn(n ≥ 0, 0) = -Inf // Yn(n < 0, 0) = +Inf if n is odd, -Inf if n is even -// Y1(n, x < 0) = NaN -// Y1(n, NaN) = NaN +// Yn(n, x < 0) = NaN +// Yn(n, NaN) = NaN func Yn(n int, x float64) float64 { const Two302 = 1 << 302 // 2**302 0x52D0000000000000 // special cases diff --git a/libgo/go/math/pow.go b/libgo/go/math/pow.go index 77af256..7ba426f4 100644 --- a/libgo/go/math/pow.go +++ b/libgo/go/math/pow.go @@ -36,6 +36,13 @@ func isOddInt(x float64) bool { // Pow(-Inf, y) = Pow(-0, -y) // Pow(x, y) = NaN for finite x < 0 and finite non-integer y func Pow(x, y float64) float64 { + return libc_pow(x, y) +} + +//extern pow +func libc_pow(float64, float64) float64 + +func pow(x, y float64) float64 { switch { case y == 0 || x == 1: return 1 diff --git a/libgo/go/math/pow10.go b/libgo/go/math/pow10.go index f5ad28b..1234e20 100644 --- a/libgo/go/math/pow10.go +++ b/libgo/go/math/pow10.go @@ -4,37 +4,43 @@ package math -// This table might overflow 127-bit exponent representations. -// In that case, truncate it after 1.0e38. -var pow10tab [70]float64 +// pow10tab stores the pre-computed values 10**i for i < 32. +var pow10tab = [...]float64{ + 1e00, 1e01, 1e02, 1e03, 1e04, 1e05, 1e06, 1e07, 1e08, 1e09, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, + 1e20, 1e21, 1e22, 1e23, 1e24, 1e25, 1e26, 1e27, 1e28, 1e29, + 1e30, 1e31, +} + +// pow10postab32 stores the pre-computed value for 10**(i*32) at index i. +var pow10postab32 = [...]float64{ + 1e00, 1e32, 1e64, 1e96, 1e128, 1e160, 1e192, 1e224, 1e256, 1e288, +} + +// pow10negtab32 stores the pre-computed value for 10**(-i*32) at index i. +var pow10negtab32 = [...]float64{ + 1e-00, 1e-32, 1e-64, 1e-96, 1e-128, 1e-160, 1e-192, 1e-224, 1e-256, 1e-288, 1e-320, +} -// Pow10 returns 10**e, the base-10 exponential of e. +// Pow10 returns 10**n, the base-10 exponential of n. // // Special cases are: -// Pow10(e) = +Inf for e > 309 -// Pow10(e) = 0 for e < -324 -func Pow10(e int) float64 { - if e <= -325 { - return 0 - } else if e > 309 { - return Inf(1) +// Pow10(n) = 0 for n < -323 +// Pow10(n) = +Inf for n > 308 +func Pow10(n int) float64 { + if 0 <= n && n <= 308 { + return pow10postab32[uint(n)/32] * pow10tab[uint(n)%32] } - if e < 0 { - return 1 / Pow10(-e) - } - if e < len(pow10tab) { - return pow10tab[e] + if -323 <= n && n <= 0 { + return pow10negtab32[uint(-n)/32] / pow10tab[uint(-n)%32] } - m := e / 2 - return Pow10(m) * Pow10(e-m) -} -func init() { - pow10tab[0] = 1.0e0 - pow10tab[1] = 1.0e1 - for i := 2; i < len(pow10tab); i++ { - m := i / 2 - pow10tab[i] = pow10tab[m] * pow10tab[i-m] + // n < -323 || 308 < n + if n > 0 { + return Inf(1) } + + // n < -323 + return 0 } diff --git a/libgo/go/math/rand/rand.go b/libgo/go/math/rand/rand.go index 9fe1cbd..fe99c94 100644 --- a/libgo/go/math/rand/rand.go +++ b/libgo/go/math/rand/rand.go @@ -8,7 +8,8 @@ // Float64 and Int, use a default shared Source that produces a deterministic // sequence of values each time a program is run. Use the Seed function to // initialize the default Source if different behavior is required for each run. -// The default Source is safe for concurrent use by multiple goroutines. +// The default Source is safe for concurrent use by multiple goroutines, but +// Sources created by NewSource are not. // // For random numbers suitable for security-sensitive work, see the crypto/rand // package. diff --git a/libgo/go/math/sincos.go b/libgo/go/math/sincos.go index 89db81e..65f3790 100644 --- a/libgo/go/math/sincos.go +++ b/libgo/go/math/sincos.go @@ -2,6 +2,8 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. +// -build !386 + package math // Coefficients _sin[] and _cos[] are found in pkg/math/sin.go. @@ -13,10 +15,6 @@ package math // Sincos(±Inf) = NaN, NaN // Sincos(NaN) = NaN, NaN func Sincos(x float64) (sin, cos float64) { - return sincos(x) -} - -func sincos(x float64) (sin, cos float64) { const ( PI4A = 7.85398125648498535156E-1 // 0x3fe921fb40000000, Pi/4 split into three parts PI4B = 3.77489470793079817668E-8 // 0x3e64442d00000000, diff --git a/libgo/go/math/sincos_386.go b/libgo/go/math/sincos_386.go new file mode 100644 index 0000000..d5c2457 --- /dev/null +++ b/libgo/go/math/sincos_386.go @@ -0,0 +1,15 @@ +// Copyright 2017 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 ignore + +package math + +// Sincos returns Sin(x), Cos(x). +// +// Special cases are: +// Sincos(±0) = ±0, 1 +// Sincos(±Inf) = NaN, NaN +// Sincos(NaN) = NaN, NaN +func Sincos(x float64) (sin, cos float64) |