diff options
Diffstat (limited to 'src/pkg/math/big')
-rw-r--r-- | src/pkg/math/big/arith.go | 14 | ||||
-rw-r--r-- | src/pkg/math/big/arith_amd64p32.s | 41 | ||||
-rw-r--r-- | src/pkg/math/big/arith_arm.s | 109 | ||||
-rw-r--r-- | src/pkg/math/big/int.go | 37 | ||||
-rw-r--r-- | src/pkg/math/big/int_test.go | 66 | ||||
-rw-r--r-- | src/pkg/math/big/nat.go | 11 | ||||
-rw-r--r-- | src/pkg/math/big/nat_test.go | 27 | ||||
-rw-r--r-- | src/pkg/math/big/rat.go | 21 | ||||
-rw-r--r-- | src/pkg/math/big/rat_test.go | 65 |
9 files changed, 283 insertions, 108 deletions
diff --git a/src/pkg/math/big/arith.go b/src/pkg/math/big/arith.go index f316806d7..3d5a8682d 100644 --- a/src/pkg/math/big/arith.go +++ b/src/pkg/math/big/arith.go @@ -131,12 +131,11 @@ func divWW_g(u1, u0, v Word) (q, r Word) { q1 := un32 / vn1 rhat := un32 - q1*vn1 -again1: - if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { + for q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { q1-- rhat += vn1 - if rhat < _B2 { - goto again1 + if rhat >= _B2 { + break } } @@ -144,12 +143,11 @@ again1: q0 := un21 / vn1 rhat = un21 - q0*vn1 -again2: - if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 { + for q0 >= _B2 || q0*vn0 > _B2*rhat+un0 { q0-- rhat += vn1 - if rhat < _B2 { - goto again2 + if rhat >= _B2 { + break } } diff --git a/src/pkg/math/big/arith_amd64p32.s b/src/pkg/math/big/arith_amd64p32.s new file mode 100644 index 000000000..227870a00 --- /dev/null +++ b/src/pkg/math/big/arith_amd64p32.s @@ -0,0 +1,41 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +#include "../../../cmd/ld/textflag.h" + +TEXT ·mulWW(SB),NOSPLIT,$0 + JMP ·mulWW_g(SB) + +TEXT ·divWW(SB),NOSPLIT,$0 + JMP ·divWW_g(SB) + +TEXT ·addVV(SB),NOSPLIT,$0 + JMP ·addVV_g(SB) + +TEXT ·subVV(SB),NOSPLIT,$0 + JMP ·subVV_g(SB) + +TEXT ·addVW(SB),NOSPLIT,$0 + JMP ·addVW_g(SB) + +TEXT ·subVW(SB),NOSPLIT,$0 + JMP ·subVW_g(SB) + +TEXT ·shlVU(SB),NOSPLIT,$0 + JMP ·shlVU_g(SB) + +TEXT ·shrVU(SB),NOSPLIT,$0 + JMP ·shrVU_g(SB) + +TEXT ·mulAddVWW(SB),NOSPLIT,$0 + JMP ·mulAddVWW_g(SB) + +TEXT ·addMulVVW(SB),NOSPLIT,$0 + JMP ·addMulVVW_g(SB) + +TEXT ·divWVW(SB),NOSPLIT,$0 + JMP ·divWVW_g(SB) + +TEXT ·bitLen(SB),NOSPLIT,$0 + JMP ·bitLen_g(SB) diff --git a/src/pkg/math/big/arith_arm.s b/src/pkg/math/big/arith_arm.s index ecf55b344..8d36761c4 100644 --- a/src/pkg/math/big/arith_arm.s +++ b/src/pkg/math/big/arith_arm.s @@ -7,31 +7,26 @@ // This file provides fast assembly versions for the elementary // arithmetic operations on vectors implemented in arith.go. -#define CFLAG 29 // bit position of carry flag - // func addVV(z, x, y []Word) (c Word) TEXT ·addVV(SB),NOSPLIT,$0 - MOVW $0, R0 + ADD.S $0, R0 // clear carry flag MOVW z+0(FP), R1 + MOVW z_len+4(FP), R4 MOVW x+12(FP), R2 MOVW y+24(FP), R3 - MOVW z_len+4(FP), R4 - MOVW R4<<2, R4 - ADD R1, R4 + ADD R4<<2, R1, R4 B E1 L1: MOVW.P 4(R2), R5 MOVW.P 4(R3), R6 - MOVW R0, CPSR ADC.S R6, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 E1: - CMP R1, R4 + TEQ R1, R4 BNE L1 - MOVW R0>>CFLAG, R0 - AND $1, R0 + MOVW $0, R0 + MOVW.CS $1, R0 MOVW R0, c+36(FP) RET @@ -39,28 +34,24 @@ E1: // func subVV(z, x, y []Word) (c Word) // (same as addVV except for SBC instead of ADC and label names) TEXT ·subVV(SB),NOSPLIT,$0 - MOVW $(1<<CFLAG), R0 + SUB.S $0, R0 // clear borrow flag MOVW z+0(FP), R1 + MOVW z_len+4(FP), R4 MOVW x+12(FP), R2 MOVW y+24(FP), R3 - MOVW z_len+4(FP), R4 - MOVW R4<<2, R4 - ADD R1, R4 + ADD R4<<2, R1, R4 B E2 L2: MOVW.P 4(R2), R5 MOVW.P 4(R3), R6 - MOVW R0, CPSR SBC.S R6, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 E2: - CMP R1, R4 + TEQ R1, R4 BNE L2 - MOVW R0>>CFLAG, R0 - AND $1, R0 - EOR $1, R0 + MOVW $0, R0 + MOVW.CC $1, R0 MOVW R0, c+36(FP) RET @@ -68,12 +59,11 @@ E2: // func addVW(z, x []Word, y Word) (c Word) TEXT ·addVW(SB),NOSPLIT,$0 MOVW z+0(FP), R1 + MOVW z_len+4(FP), R4 MOVW x+12(FP), R2 MOVW y+24(FP), R3 - MOVW z_len+4(FP), R4 - MOVW R4<<2, R4 - ADD R1, R4 - CMP R1, R4 + ADD R4<<2, R1, R4 + TEQ R1, R4 BNE L3a MOVW R3, c+28(FP) RET @@ -81,20 +71,17 @@ L3a: MOVW.P 4(R2), R5 ADD.S R3, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 B E3 L3: MOVW.P 4(R2), R5 - MOVW R0, CPSR ADC.S $0, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 E3: - CMP R1, R4 + TEQ R1, R4 BNE L3 - MOVW R0>>CFLAG, R0 - AND $1, R0 + MOVW $0, R0 + MOVW.CS $1, R0 MOVW R0, c+28(FP) RET @@ -102,12 +89,11 @@ E3: // func subVW(z, x []Word, y Word) (c Word) TEXT ·subVW(SB),NOSPLIT,$0 MOVW z+0(FP), R1 + MOVW z_len+4(FP), R4 MOVW x+12(FP), R2 MOVW y+24(FP), R3 - MOVW z_len+4(FP), R4 - MOVW R4<<2, R4 - ADD R1, R4 - CMP R1, R4 + ADD R4<<2, R1, R4 + TEQ R1, R4 BNE L4a MOVW R3, c+28(FP) RET @@ -115,21 +101,17 @@ L4a: MOVW.P 4(R2), R5 SUB.S R3, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 B E4 L4: MOVW.P 4(R2), R5 - MOVW R0, CPSR SBC.S $0, R5 MOVW.P R5, 4(R1) - MOVW CPSR, R0 E4: - CMP R1, R4 + TEQ R1, R4 BNE L4 - MOVW R0>>CFLAG, R0 - AND $1, R0 - EOR $1, R0 + MOVW $0, R0 + MOVW.CC $1, R0 MOVW R0, c+28(FP) RET @@ -137,16 +119,15 @@ E4: // func shlVU(z, x []Word, s uint) (c Word) TEXT ·shlVU(SB),NOSPLIT,$0 MOVW z_len+4(FP), R5 - CMP $0, R5 + TEQ $0, R5 BEQ X7 MOVW z+0(FP), R1 MOVW x+12(FP), R2 - MOVW R5<<2, R5 - ADD R5, R2 - ADD R1, R5 + ADD R5<<2, R2, R2 + ADD R5<<2, R1, R5 MOVW s+24(FP), R3 - CMP $0, R3 // shift 0 is special + TEQ $0, R3 // shift 0 is special BEQ Y7 ADD $4, R1 // stop one word early MOVW $32, R4 @@ -165,7 +146,7 @@ L7: MOVW.W R7, -4(R5) MOVW R6<<R3, R7 E7: - CMP R1, R5 + TEQ R1, R5 BNE L7 MOVW R7, -4(R5) @@ -174,7 +155,7 @@ E7: Y7: // copy loop, because shift 0 == shift 32 MOVW.W -4(R2), R6 MOVW.W R6, -4(R5) - CMP R1, R5 + TEQ R1, R5 BNE Y7 X7: @@ -186,15 +167,14 @@ X7: // func shrVU(z, x []Word, s uint) (c Word) TEXT ·shrVU(SB),NOSPLIT,$0 MOVW z_len+4(FP), R5 - CMP $0, R5 + TEQ $0, R5 BEQ X6 MOVW z+0(FP), R1 MOVW x+12(FP), R2 - MOVW R5<<2, R5 - ADD R1, R5 + ADD R5<<2, R1, R5 MOVW s+24(FP), R3 - CMP $0, R3 // shift 0 is special + TEQ $0, R3 // shift 0 is special BEQ Y6 SUB $4, R5 // stop one word early MOVW $32, R4 @@ -215,7 +195,7 @@ L6: MOVW.P R7, 4(R1) MOVW R6>>R3, R7 E6: - CMP R1, R5 + TEQ R1, R5 BNE L6 MOVW R7, 0(R1) @@ -224,7 +204,7 @@ E6: Y6: // copy loop, because shift 0 == shift 32 MOVW.P 4(R2), R6 MOVW.P R6, 4(R1) - CMP R1, R5 + TEQ R1, R5 BNE Y6 X6: @@ -237,12 +217,11 @@ X6: TEXT ·mulAddVWW(SB),NOSPLIT,$0 MOVW $0, R0 MOVW z+0(FP), R1 + MOVW z_len+4(FP), R5 MOVW x+12(FP), R2 MOVW y+24(FP), R3 MOVW r+28(FP), R4 - MOVW z_len+4(FP), R5 - MOVW R5<<2, R5 - ADD R1, R5 + ADD R5<<2, R1, R5 B E8 // word loop @@ -254,7 +233,7 @@ L8: MOVW.P R6, 4(R1) MOVW R7, R4 E8: - CMP R1, R5 + TEQ R1, R5 BNE L8 MOVW R4, c+32(FP) @@ -265,11 +244,10 @@ E8: TEXT ·addMulVVW(SB),NOSPLIT,$0 MOVW $0, R0 MOVW z+0(FP), R1 + MOVW z_len+4(FP), R5 MOVW x+12(FP), R2 MOVW y+24(FP), R3 - MOVW z_len+4(FP), R5 - MOVW R5<<2, R5 - ADD R1, R5 + ADD R5<<2, R1, R5 MOVW $0, R4 B E9 @@ -285,7 +263,7 @@ L9: MOVW.P R6, 4(R1) MOVW R7, R4 E9: - CMP R1, R5 + TEQ R1, R5 BNE L9 MOVW R4, c+28(FP) @@ -317,7 +295,6 @@ TEXT ·mulWW(SB),NOSPLIT,$0 TEXT ·bitLen(SB),NOSPLIT,$0 MOVW x+0(FP), R0 CLZ R0, R0 - MOVW $32, R1 - SUB.S R0, R1 - MOVW R1, n+4(FP) + RSB $32, R0 + MOVW R0, n+4(FP) RET diff --git a/src/pkg/math/big/int.go b/src/pkg/math/big/int.go index 7bbb152d7..269949d61 100644 --- a/src/pkg/math/big/int.go +++ b/src/pkg/math/big/int.go @@ -576,21 +576,22 @@ func (x *Int) BitLen() int { } // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. -// If y <= 0, the result is 1; if m == nil or m == 0, z = x**y. +// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. // See Knuth, volume 2, section 4.6.3. func (z *Int) Exp(x, y, m *Int) *Int { - if y.neg || len(y.abs) == 0 { - return z.SetInt64(1) + var yWords nat + if !y.neg { + yWords = y.abs } - // y > 0 + // y >= 0 var mWords nat if m != nil { mWords = m.abs // m.abs may be nil for m == 0 } - z.abs = z.abs.expNN(x.abs, y.abs, mWords) - z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 // 0 has no sign + z.abs = z.abs.expNN(x.abs, yWords, mWords) + z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign return z } @@ -982,17 +983,29 @@ func (z *Int) GobDecode(buf []byte) error { } // MarshalJSON implements the json.Marshaler interface. -func (x *Int) MarshalJSON() ([]byte, error) { +func (z *Int) MarshalJSON() ([]byte, error) { // TODO(gri): get rid of the []byte/string conversions - return []byte(x.String()), nil + return []byte(z.String()), nil } // UnmarshalJSON implements the json.Unmarshaler interface. -func (z *Int) UnmarshalJSON(x []byte) error { +func (z *Int) UnmarshalJSON(text []byte) error { // TODO(gri): get rid of the []byte/string conversions - _, ok := z.SetString(string(x), 0) - if !ok { - return fmt.Errorf("math/big: cannot unmarshal %s into a *big.Int", x) + if _, ok := z.SetString(string(text), 0); !ok { + return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) + } + return nil +} + +// MarshalText implements the encoding.TextMarshaler interface +func (z *Int) MarshalText() (text []byte, err error) { + return []byte(z.String()), nil +} + +// UnmarshalText implements the encoding.TextUnmarshaler interface +func (z *Int) UnmarshalText(text []byte) error { + if _, ok := z.SetString(string(text), 0); !ok { + return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) } return nil } diff --git a/src/pkg/math/big/int_test.go b/src/pkg/math/big/int_test.go index 87b975d5c..299dc72fb 100644 --- a/src/pkg/math/big/int_test.go +++ b/src/pkg/math/big/int_test.go @@ -9,6 +9,7 @@ import ( "encoding/gob" "encoding/hex" "encoding/json" + "encoding/xml" "fmt" "math/rand" "testing" @@ -767,6 +768,19 @@ var expTests = []struct { x, y, m string out string }{ + // y <= 0 + {"0", "0", "", "1"}, + {"1", "0", "", "1"}, + {"-10", "0", "", "1"}, + {"1234", "-1", "", "1"}, + + // m == 1 + {"0", "0", "1", "0"}, + {"1", "0", "1", "0"}, + {"-10", "0", "1", "0"}, + {"1234", "-1", "1", "0"}, + + // misc {"5", "-7", "", "1"}, {"-5", "-7", "", "1"}, {"5", "0", "", "1"}, @@ -1528,6 +1542,58 @@ func TestIntJSONEncoding(t *testing.T) { } } +var intVals = []string{ + "-141592653589793238462643383279502884197169399375105820974944592307816406286", + "-1415926535897932384626433832795028841971", + "-141592653589793", + "-1", + "0", + "1", + "141592653589793", + "1415926535897932384626433832795028841971", + "141592653589793238462643383279502884197169399375105820974944592307816406286", +} + +func TestIntJSONEncodingTextMarshaller(t *testing.T) { + for _, num := range intVals { + var tx Int + tx.SetString(num, 0) + b, err := json.Marshal(&tx) + if err != nil { + t.Errorf("marshaling of %s failed: %s", &tx, err) + continue + } + var rx Int + if err := json.Unmarshal(b, &rx); err != nil { + t.Errorf("unmarshaling of %s failed: %s", &tx, err) + continue + } + if rx.Cmp(&tx) != 0 { + t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx) + } + } +} + +func TestIntXMLEncodingTextMarshaller(t *testing.T) { + for _, num := range intVals { + var tx Int + tx.SetString(num, 0) + b, err := xml.Marshal(&tx) + if err != nil { + t.Errorf("marshaling of %s failed: %s", &tx, err) + continue + } + var rx Int + if err := xml.Unmarshal(b, &rx); err != nil { + t.Errorf("unmarshaling of %s failed: %s", &tx, err) + continue + } + if rx.Cmp(&tx) != 0 { + t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx) + } + } +} + func TestIssue2607(t *testing.T) { // This code sequence used to hang. n := NewInt(10) diff --git a/src/pkg/math/big/nat.go b/src/pkg/math/big/nat.go index 6874900d0..16a87f5c5 100644 --- a/src/pkg/math/big/nat.go +++ b/src/pkg/math/big/nat.go @@ -1233,10 +1233,15 @@ func (z nat) expNN(x, y, m nat) nat { z = nil } + // x**y mod 1 == 0 + if len(m) == 1 && m[0] == 1 { + return z.setWord(0) + } + // m == 0 || m > 1 + + // x**0 == 1 if len(y) == 0 { - z = z.make(1) - z[0] = 1 - return z + return z.setWord(1) } // y > 0 diff --git a/src/pkg/math/big/nat_test.go b/src/pkg/math/big/nat_test.go index 1d4dfe80d..a2ae53385 100644 --- a/src/pkg/math/big/nat_test.go +++ b/src/pkg/math/big/nat_test.go @@ -437,20 +437,11 @@ func BenchmarkStringPiParallel(b *testing.B) { if x.decimalString() != pi { panic("benchmark incorrect: conversion failed") } - n := runtime.GOMAXPROCS(0) - m := b.N / n // n*m <= b.N due to flooring, but the error is neglibible (n is not very large) - c := make(chan int, n) - for i := 0; i < n; i++ { - go func() { - for j := 0; j < m; j++ { - x.decimalString() - } - c <- 0 - }() - } - for i := 0; i < n; i++ { - <-c - } + b.RunParallel(func(pb *testing.PB) { + for pb.Next() { + x.decimalString() + } + }) } func BenchmarkScan10Base2(b *testing.B) { ScanHelper(b, 2, 10, 10) } @@ -723,6 +714,12 @@ var expNNTests = []struct { x, y, m string out string }{ + {"0", "0", "0", "1"}, + {"0", "0", "1", "0"}, + {"1", "1", "1", "0"}, + {"2", "1", "1", "0"}, + {"2", "2", "1", "0"}, + {"10", "100000000000", "1", "0"}, {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"}, {"0x8000000000000000", "2", "6719", "4944"}, {"0x8000000000000000", "3", "6719", "5447"}, @@ -750,7 +747,7 @@ func TestExpNN(t *testing.T) { z := nat(nil).expNN(x, y, m) if z.cmp(out) != 0 { - t.Errorf("#%d got %v want %v", i, z, out) + t.Errorf("#%d got %s want %s", i, z.decimalString(), out.decimalString()) } } } diff --git a/src/pkg/math/big/rat.go b/src/pkg/math/big/rat.go index 7faee61a4..f0973b390 100644 --- a/src/pkg/math/big/rat.go +++ b/src/pkg/math/big/rat.go @@ -47,7 +47,7 @@ func (z *Rat) SetFloat64(f float64) *Rat { shift := 52 - exp - // Optimisation (?): partially pre-normalise. + // Optimization (?): partially pre-normalise. for mantissa&1 == 0 && shift > 0 { mantissa >>= 1 shift-- @@ -477,7 +477,7 @@ func (z *Rat) SetString(s string) (*Rat, bool) { return z, true } -// String returns a string representation of z in the form "a/b" (even if b == 1). +// String returns a string representation of x in the form "a/b" (even if b == 1). func (x *Rat) String() string { s := "/1" if len(x.b.abs) != 0 { @@ -486,7 +486,7 @@ func (x *Rat) String() string { return x.a.String() + s } -// RatString returns a string representation of z in the form "a/b" if b != 1, +// RatString returns a string representation of x in the form "a/b" if b != 1, // and in the form "a" if b == 1. func (x *Rat) RatString() string { if x.IsInt() { @@ -495,7 +495,7 @@ func (x *Rat) RatString() string { return x.String() } -// FloatString returns a string representation of z in decimal form with prec +// FloatString returns a string representation of x in decimal form with prec // digits of precision after the decimal point and the last digit rounded. func (x *Rat) FloatString(prec int) string { if x.IsInt() { @@ -585,3 +585,16 @@ func (z *Rat) GobDecode(buf []byte) error { z.b.abs = z.b.abs.setBytes(buf[i:]) return nil } + +// MarshalText implements the encoding.TextMarshaler interface +func (r *Rat) MarshalText() (text []byte, err error) { + return []byte(r.RatString()), nil +} + +// UnmarshalText implements the encoding.TextUnmarshaler interface +func (r *Rat) UnmarshalText(text []byte) error { + if _, ok := r.SetString(string(text)); !ok { + return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Rat", text) + } + return nil +} diff --git a/src/pkg/math/big/rat_test.go b/src/pkg/math/big/rat_test.go index 0d432637b..414a67d41 100644 --- a/src/pkg/math/big/rat_test.go +++ b/src/pkg/math/big/rat_test.go @@ -7,6 +7,8 @@ package big import ( "bytes" "encoding/gob" + "encoding/json" + "encoding/xml" "fmt" "math" "strconv" @@ -433,6 +435,69 @@ func TestGobEncodingNilRatInSlice(t *testing.T) { } } +var ratNums = []string{ + "-141592653589793238462643383279502884197169399375105820974944592307816406286", + "-1415926535897932384626433832795028841971", + "-141592653589793", + "-1", + "0", + "1", + "141592653589793", + "1415926535897932384626433832795028841971", + "141592653589793238462643383279502884197169399375105820974944592307816406286", +} + +var ratDenoms = []string{ + "1", + "718281828459045", + "7182818284590452353602874713526624977572", + "718281828459045235360287471352662497757247093699959574966967627724076630353", +} + +func TestRatJSONEncoding(t *testing.T) { + for _, num := range ratNums { + for _, denom := range ratDenoms { + var tx Rat + tx.SetString(num + "/" + denom) + b, err := json.Marshal(&tx) + if err != nil { + t.Errorf("marshaling of %s failed: %s", &tx, err) + continue + } + var rx Rat + if err := json.Unmarshal(b, &rx); err != nil { + t.Errorf("unmarshaling of %s failed: %s", &tx, err) + continue + } + if rx.Cmp(&tx) != 0 { + t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx) + } + } + } +} + +func TestRatXMLEncoding(t *testing.T) { + for _, num := range ratNums { + for _, denom := range ratDenoms { + var tx Rat + tx.SetString(num + "/" + denom) + b, err := xml.Marshal(&tx) + if err != nil { + t.Errorf("marshaling of %s failed: %s", &tx, err) + continue + } + var rx Rat + if err := xml.Unmarshal(b, &rx); err != nil { + t.Errorf("unmarshaling of %s failed: %s", &tx, err) + continue + } + if rx.Cmp(&tx) != 0 { + t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx) + } + } + } +} + func TestIssue2379(t *testing.T) { // 1) no aliasing q := NewRat(3, 2) |