summaryrefslogtreecommitdiff
path: root/src/pkg/big
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/big')
-rw-r--r--src/pkg/big/arith.go4
-rw-r--r--src/pkg/big/arith_386.s8
-rw-r--r--src/pkg/big/arith_amd64.s12
-rw-r--r--src/pkg/big/arith_arm.s12
-rw-r--r--src/pkg/big/arith_decl.go4
-rw-r--r--src/pkg/big/arith_test.go19
-rwxr-xr-xsrc/pkg/big/int.go104
-rwxr-xr-xsrc/pkg/big/int_test.go43
-rwxr-xr-xsrc/pkg/big/nat.go175
-rwxr-xr-xsrc/pkg/big/nat_test.go172
-rw-r--r--src/pkg/big/rat.go32
-rw-r--r--src/pkg/big/rat_test.go29
12 files changed, 496 insertions, 118 deletions
diff --git a/src/pkg/big/arith.go b/src/pkg/big/arith.go
index df3808f5e..b9aeea968 100644
--- a/src/pkg/big/arith.go
+++ b/src/pkg/big/arith.go
@@ -188,7 +188,7 @@ func subVW_g(z, x []Word, y Word) (c Word) {
}
-func shlVW_g(z, x []Word, s Word) (c Word) {
+func shlVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[n-1]
@@ -204,7 +204,7 @@ func shlVW_g(z, x []Word, s Word) (c Word) {
}
-func shrVW_g(z, x []Word, s Word) (c Word) {
+func shrVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[0]
diff --git a/src/pkg/big/arith_386.s b/src/pkg/big/arith_386.s
index 21521635b..07c07b02c 100644
--- a/src/pkg/big/arith_386.s
+++ b/src/pkg/big/arith_386.s
@@ -118,8 +118,8 @@ E4: CMPL BX, BP // i < n
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVL n+4(FP), BX // i = n
SUBL $1, BX // i--
JL X8b // i < 0 (n <= 0)
@@ -153,8 +153,8 @@ X8b: MOVL $0, c+28(FP)
RET
-// func shrVW(z, x []Word, s Word) (c Word)
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVL n+4(FP), BP
SUBL $1, BP // n--
JL X9b // n < 0 (n <= 0)
diff --git a/src/pkg/big/arith_amd64.s b/src/pkg/big/arith_amd64.s
index c740565a7..89b65f38a 100644
--- a/src/pkg/big/arith_amd64.s
+++ b/src/pkg/big/arith_amd64.s
@@ -120,8 +120,8 @@ E4: CMPQ BX, R11 // i < n
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVL n+8(FP), BX // i = n
SUBL $1, BX // i--
JL X8b // i < 0 (n <= 0)
@@ -129,7 +129,7 @@ TEXT ·shlVW(SB),7,$0
// n > 0
MOVQ z+0(FP), R10
MOVQ x+16(FP), R8
- MOVQ s+32(FP), CX
+ MOVL s+32(FP), CX
MOVQ (R8)(BX*8), AX // w1 = x[n-1]
MOVQ $0, DX
SHLQ CX, DX:AX // w1>>ŝ
@@ -155,8 +155,8 @@ X8b: MOVQ $0, c+40(FP)
RET
-// func shrVW(z, x []Word, s Word) (c Word)
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVL n+8(FP), R11
SUBL $1, R11 // n--
JL X9b // n < 0 (n <= 0)
@@ -164,7 +164,7 @@ TEXT ·shrVW(SB),7,$0
// n > 0
MOVQ z+0(FP), R10
MOVQ x+16(FP), R8
- MOVQ s+32(FP), CX
+ MOVL s+32(FP), CX
MOVQ (R8), AX // w1 = x[0]
MOVQ $0, DX
SHRQ CX, DX:AX // w1<<ŝ
diff --git a/src/pkg/big/arith_arm.s b/src/pkg/big/arith_arm.s
index e4a9a962c..60abe6eaa 100644
--- a/src/pkg/big/arith_arm.s
+++ b/src/pkg/big/arith_arm.s
@@ -97,6 +97,7 @@ E3:
RET
+// func subVW(z, x []Word, y Word) (c Word)
TEXT ·subVW(SB),7,$0
MOVW z+0(FP), R1
MOVW x+12(FP), R2
@@ -131,8 +132,8 @@ E4:
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVW n+4(FP), R5
CMP $0, R5
BEQ X7
@@ -180,7 +181,8 @@ X7:
RET
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVW n+4(FP), R5
CMP $0, R5
BEQ X6
@@ -229,6 +231,7 @@ X6:
RET
+// func mulAddVWW(z, x []Word, y, r Word) (c Word)
TEXT ·mulAddVWW(SB),7,$0
MOVW $0, R0
MOVW z+0(FP), R1
@@ -256,6 +259,7 @@ E8:
RET
+// func addMulVVW(z, x []Word, y Word) (c Word)
TEXT ·addMulVVW(SB),7,$0
MOVW $0, R0
MOVW z+0(FP), R1
@@ -286,11 +290,13 @@ E9:
RET
+// divWVW(z* Word, xn Word, x []Word, y Word) (r Word)
TEXT ·divWVW(SB),7,$0
// ARM has no multiword division, so use portable code.
B ·divWVW_g(SB)
+// func divWW(x1, x0, y Word) (q, r Word)
TEXT ·divWW(SB),7,$0
// ARM has no multiword division, so use portable code.
B ·divWW_g(SB)
diff --git a/src/pkg/big/arith_decl.go b/src/pkg/big/arith_decl.go
index c456d5f67..95fcd8b94 100644
--- a/src/pkg/big/arith_decl.go
+++ b/src/pkg/big/arith_decl.go
@@ -11,8 +11,8 @@ func addVV(z, x, y []Word) (c Word)
func subVV(z, x, y []Word) (c Word)
func addVW(z, x []Word, y Word) (c Word)
func subVW(z, x []Word, y Word) (c Word)
-func shlVW(z, x []Word, s Word) (c Word)
-func shrVW(z, x []Word, s Word) (c Word)
+func shlVU(z, x []Word, s uint) (c Word)
+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)
diff --git a/src/pkg/big/arith_test.go b/src/pkg/big/arith_test.go
index 934b302df..f3e2d4735 100644
--- a/src/pkg/big/arith_test.go
+++ b/src/pkg/big/arith_test.go
@@ -185,6 +185,13 @@ func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
}
+func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
+ return func(z, x []Word, s Word) (c Word) {
+ return f(z, x, uint(s))
+ }
+}
+
+
func TestFunVW(t *testing.T) {
for _, a := range sumVW {
arg := a
@@ -196,16 +203,20 @@ func TestFunVW(t *testing.T) {
testFunVW(t, "subVW", subVW, arg)
}
+ shlVW_g := makeFunVW(shlVU_g)
+ shlVW := makeFunVW(shlVU)
for _, a := range lshVW {
arg := a
- testFunVW(t, "shlVW_g", shlVW_g, arg)
- testFunVW(t, "shlVW", shlVW, arg)
+ testFunVW(t, "shlVU_g", shlVW_g, arg)
+ testFunVW(t, "shlVU", shlVW, arg)
}
+ shrVW_g := makeFunVW(shrVU_g)
+ shrVW := makeFunVW(shrVU)
for _, a := range rshVW {
arg := a
- testFunVW(t, "shrVW_g", shrVW_g, arg)
- testFunVW(t, "shrVW", shrVW, arg)
+ testFunVW(t, "shrVU_g", shrVW_g, arg)
+ testFunVW(t, "shrVU", shrVW, arg)
}
}
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go
index 74fbef48d..e66c34a83 100755
--- a/src/pkg/big/int.go
+++ b/src/pkg/big/int.go
@@ -8,8 +8,10 @@ package big
import (
"fmt"
+ "io"
"os"
"rand"
+ "strings"
)
// An Int represents a signed multi-precision integer.
@@ -325,7 +327,7 @@ func charset(ch int) string {
return lowercaseDigits[0:2]
case 'o':
return lowercaseDigits[0:8]
- case 'd', 'v':
+ case 'd', 's', 'v':
return lowercaseDigits[0:10]
case 'x':
return lowercaseDigits[0:16]
@@ -374,8 +376,69 @@ func (x *Int) Format(s fmt.State, ch int) {
}
-// Int64 returns the int64 representation of z.
-// If z cannot be represented in an int64, the result is undefined.
+// scan sets z to the integer value corresponding to the longest possible prefix
+// read from r representing a signed integer number in a given conversion base.
+// It returns z, the actual conversion base used, and an error, if any. In the
+// error case, the value of z is undefined. The syntax follows the syntax of
+// integer literals in Go.
+//
+// The base argument must be 0 or a value from 2 through MaxBase. If the base
+// is 0, the string prefix determines the actual conversion base. A prefix of
+// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
+// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
+//
+func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, os.Error) {
+ // determine sign
+ ch, _, err := r.ReadRune()
+ if err != nil {
+ return z, 0, err
+ }
+ neg := false
+ switch ch {
+ case '-':
+ neg = true
+ case '+': // nothing to do
+ default:
+ r.UnreadRune()
+ }
+
+ // determine mantissa
+ z.abs, base, err = z.abs.scan(r, base)
+ if err != nil {
+ return z, base, err
+ }
+ z.neg = len(z.abs) > 0 && neg // 0 has no sign
+
+ return z, base, nil
+}
+
+
+// Scan is a support routine for fmt.Scanner; it sets z to the value of
+// the scanned number. It accepts the formats 'b' (binary), 'o' (octal),
+// 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
+func (z *Int) Scan(s fmt.ScanState, ch int) os.Error {
+ base := 0
+ switch ch {
+ case 'b':
+ base = 2
+ case 'o':
+ base = 8
+ case 'd':
+ base = 10
+ case 'x', 'X':
+ base = 16
+ case 's', 'v':
+ // let scan determine the base
+ default:
+ return os.ErrorString("Int.Scan: invalid verb")
+ }
+ _, _, err := z.scan(s, base)
+ return err
+}
+
+
+// Int64 returns the int64 representation of x.
+// If x cannot be represented in an int64, the result is undefined.
func (x *Int) Int64() int64 {
if len(x.abs) == 0 {
return 0
@@ -395,32 +458,19 @@ func (x *Int) Int64() int64 {
// and returns z and a boolean indicating success. If SetString fails,
// the value of z is undefined.
//
-// If the base argument is 0, the string prefix determines the actual
-// conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the
-// ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects
-// base 2. Otherwise the selected base is 10.
+// The base argument must be 0 or a value from 2 through MaxBase. If the base
+// is 0, the string prefix determines the actual conversion base. A prefix of
+// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
+// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
//
func (z *Int) SetString(s string, base int) (*Int, bool) {
- if len(s) == 0 || base < 0 || base == 1 || 16 < base {
+ r := strings.NewReader(s)
+ _, _, err := z.scan(r, base)
+ if err != nil {
return z, false
}
-
- neg := s[0] == '-'
- if neg || s[0] == '+' {
- s = s[1:]
- if len(s) == 0 {
- return z, false
- }
- }
-
- var scanned int
- z.abs, _, scanned = z.abs.scan(s, base)
- if scanned != len(s) {
- return z, false
- }
- z.neg = len(z.abs) > 0 && neg // 0 has no sign
-
- return z, true
+ _, _, err = r.ReadRune()
+ return z, err == os.EOF // err == os.EOF => scan consumed all of s
}
@@ -784,11 +834,11 @@ func (z *Int) GobEncode() ([]byte, os.Error) {
// GobDecode implements the gob.GobDecoder interface.
func (z *Int) GobDecode(buf []byte) os.Error {
if len(buf) == 0 {
- return os.NewError("Int.GobDecode: no data")
+ return os.ErrorString("Int.GobDecode: no data")
}
b := buf[0]
if b>>1 != version {
- return os.NewError(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
+ return os.ErrorString(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
}
z.neg = b&1 != 0
z.abs = z.abs.setBytes(buf[1:])
diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go
index 595f04956..1a492925b 100755
--- a/src/pkg/big/int_test.go
+++ b/src/pkg/big/int_test.go
@@ -397,6 +397,49 @@ func TestFormat(t *testing.T) {
}
+var scanTests = []struct {
+ input string
+ format string
+ output string
+ remaining int
+}{
+ {"1010", "%b", "10", 0},
+ {"0b1010", "%v", "10", 0},
+ {"12", "%o", "10", 0},
+ {"012", "%v", "10", 0},
+ {"10", "%d", "10", 0},
+ {"10", "%v", "10", 0},
+ {"a", "%x", "10", 0},
+ {"0xa", "%v", "10", 0},
+ {"A", "%X", "10", 0},
+ {"-A", "%X", "-10", 0},
+ {"+0b1011001", "%v", "89", 0},
+ {"0xA", "%v", "10", 0},
+ {"0 ", "%v", "0", 1},
+ {"2+3", "%v", "2", 2},
+ {"0XABC 12", "%v", "2748", 3},
+}
+
+
+func TestScan(t *testing.T) {
+ var buf bytes.Buffer
+ for i, test := range scanTests {
+ x := new(Int)
+ buf.Reset()
+ buf.WriteString(test.input)
+ if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
+ t.Errorf("#%d error: %s", i, err.String())
+ }
+ if x.String() != test.output {
+ t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
+ }
+ if buf.Len() != test.remaining {
+ t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
+ }
+ }
+}
+
+
// Examples from the Go Language Spec, section "Arithmetic operators"
var divisionSignsTests = []struct {
x, y int64
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index c2b95e8a2..fa09d6531 100755
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -18,7 +18,11 @@ package big
// These are the building blocks for the operations on signed integers
// and rationals.
-import "rand"
+import (
+ "io"
+ "os"
+ "rand"
+)
// An unsigned integer x of the form
@@ -546,9 +550,14 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
u.clear()
// D1.
- shift := Word(leadingZeros(v[n-1]))
- shlVW(v, v, shift)
- u[len(uIn)] = shlVW(u[0:len(uIn)], uIn, shift)
+ shift := leadingZeros(v[n-1])
+ if shift > 0 {
+ // do not modify v, it may be used by another goroutine simultaneously
+ v1 := make(nat, n)
+ shlVU(v1, v, shift)
+ v = v1
+ }
+ u[len(uIn)] = shlVU(u[0:len(uIn)], uIn, shift)
// D2.
for j := m; j >= 0; j-- {
@@ -587,8 +596,7 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
}
q = q.norm()
- shrVW(u, u, shift)
- shrVW(v, v, shift)
+ shrVU(u, u, shift)
r = u.norm()
return q, r
@@ -604,68 +612,118 @@ func (x nat) bitLen() int {
}
-func hexValue(ch byte) int {
- var d byte
+// MaxBase is the largest number base accepted for string conversions.
+const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1
+
+func hexValue(ch int) Word {
+ d := MaxBase + 1 // illegal base
switch {
case '0' <= ch && ch <= '9':
d = ch - '0'
- case 'a' <= ch && ch <= 'f':
+ case 'a' <= ch && ch <= 'z':
d = ch - 'a' + 10
- case 'A' <= ch && ch <= 'F':
+ case 'A' <= ch && ch <= 'Z':
d = ch - 'A' + 10
- default:
- return -1
}
- return int(d)
+ return Word(d)
}
-// scan returns the natural number corresponding to the
-// longest possible prefix of s representing a natural number in a
-// given conversion base, the actual conversion base used, and the
-// prefix length. The syntax of natural numbers follows the syntax
-// of unsigned integer literals in Go.
+// scan sets z to the natural number corresponding to the longest possible prefix
+// read from r representing an unsigned integer in a given conversion base.
+// It returns z, the actual conversion base used, and an error, if any. In the
+// error case, the value of z is undefined. The syntax follows the syntax of
+// unsigned integer literals in Go.
//
-// If the base argument is 0, the string prefix determines the actual
-// conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the
-// ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects
-// base 2. Otherwise the selected base is 10.
+// The base argument must be 0 or a value from 2 through MaxBase. If the base
+// is 0, the string prefix determines the actual conversion base. A prefix of
+// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
+// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
//
-func (z nat) scan(s string, base int) (nat, int, int) {
+func (z nat) scan(r io.RuneScanner, base int) (nat, int, os.Error) {
+ // reject illegal bases
+ if base < 0 || base == 1 || MaxBase < base {
+ return z, 0, os.ErrorString("illegal number base")
+ }
+
+ // one char look-ahead
+ ch, _, err := r.ReadRune()
+ if err != nil {
+ return z, 0, err
+ }
+
// determine base if necessary
- i, n := 0, len(s)
+ b := Word(base)
if base == 0 {
- base = 10
- if n > 0 && s[0] == '0' {
- base, i = 8, 1
- if n > 1 {
- switch s[1] {
+ b = 10
+ if ch == '0' {
+ switch ch, _, err = r.ReadRune(); err {
+ case nil:
+ b = 8
+ switch ch {
case 'x', 'X':
- base, i = 16, 2
+ b = 16
case 'b', 'B':
- base, i = 2, 2
+ b = 2
+ }
+ if b == 2 || b == 16 {
+ if ch, _, err = r.ReadRune(); err != nil {
+ return z, 0, err
+ }
}
+ case os.EOF:
+ return z, 10, nil
+ default:
+ return z, 10, err
}
}
}
- // reject illegal bases or strings consisting only of prefix
- if base < 2 || 16 < base || (base != 8 && i >= n) {
- return z, 0, 0
- }
-
// convert string
+ // - group as many digits d as possible together into a "super-digit" dd with "super-base" bb
+ // - only when bb does not fit into a word anymore, do a full number mulAddWW using bb and dd
z = z.make(0)
- for ; i < n; i++ {
- d := hexValue(s[i])
- if 0 <= d && d < base {
- z = z.mulAddWW(z, Word(base), Word(d))
+ bb := Word(1)
+ dd := Word(0)
+ for max := _M / b; ; {
+ d := hexValue(ch)
+ if d >= b {
+ r.UnreadRune() // ch does not belong to number anymore
+ break
+ }
+
+ if bb <= max {
+ bb *= b
+ dd = dd*b + d
} else {
+ // bb * b would overflow
+ z = z.mulAddWW(z, bb, dd)
+ bb = b
+ dd = d
+ }
+
+ if ch, _, err = r.ReadRune(); err != nil {
+ if err != os.EOF {
+ return z, int(b), err
+ }
break
}
}
- return z.norm(), base, i
+ switch {
+ case bb > 1:
+ // there was at least one mantissa digit
+ z = z.mulAddWW(z, bb, dd)
+ case base == 0 && b == 8:
+ // there was only the octal prefix 0 (possibly followed by digits > 7);
+ // return base 10, not 8
+ return z, 10, nil
+ case base != 0 || b != 8:
+ // there was neither a mantissa digit nor the octal prefix 0
+ return z, int(b), os.ErrorString("syntax error scanning number")
+ }
+
+ return z.norm(), int(b), nil
}
@@ -766,7 +824,7 @@ func (z nat) shl(x nat, s uint) nat {
n := m + int(s/_W)
z = z.make(n + 1)
- z[n] = shlVW(z[n-m:n], x, Word(s%_W))
+ z[n] = shlVU(z[n-m:n], x, s%_W)
z[0 : n-m].clear()
return z.norm()
@@ -783,7 +841,7 @@ func (z nat) shr(x nat, s uint) nat {
// n > 0
z = z.make(n)
- shrVW(z, x[m-n:], Word(s%_W))
+ shrVU(z, x[m-n:], s%_W)
return z.norm()
}
@@ -914,25 +972,26 @@ func (x nat) modW(d Word) (r Word) {
}
-// powersOfTwoDecompose finds q and k such that q * 1<<k = n and q is odd.
-func (n nat) powersOfTwoDecompose() (q nat, k Word) {
- if len(n) == 0 {
- return n, 0
+// powersOfTwoDecompose finds q and k with x = q * 1<<k and q is odd, or q and k are 0.
+func (x nat) powersOfTwoDecompose() (q nat, k int) {
+ if len(x) == 0 {
+ return x, 0
}
- zeroWords := 0
- for n[zeroWords] == 0 {
- zeroWords++
+ // One of the words must be non-zero by definition,
+ // so this loop will terminate with i < len(x), and
+ // i is the number of 0 words.
+ i := 0
+ for x[i] == 0 {
+ i++
}
- // One of the words must be non-zero by invariant, therefore
- // zeroWords < len(n).
- x := trailingZeroBits(n[zeroWords])
+ n := trailingZeroBits(x[i]) // x[i] != 0
- q = q.make(len(n) - zeroWords)
- shrVW(q, n[zeroWords:], Word(x))
- q = q.norm()
+ q = make(nat, len(x)-i)
+ shrVU(q, x[i:], uint(n))
- k = Word(_W*zeroWords + x)
+ q = q.norm()
+ k = i*_W + n
return
}
@@ -1103,7 +1162,7 @@ NextRandom:
if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 {
continue
}
- for j := Word(1); j < k; j++ {
+ for j := 1; j < k; j++ {
y = y.mul(y, y)
quotient, y = quotient.div(y, y, n)
if y.cmp(nm1) == 0 {
diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go
index a29843a3f..50ea469be 100755
--- a/src/pkg/big/nat_test.go
+++ b/src/pkg/big/nat_test.go
@@ -4,7 +4,11 @@
package big
-import "testing"
+import (
+ "os"
+ "strings"
+ "testing"
+)
var cmpTests = []struct {
x, y nat
@@ -180,6 +184,8 @@ var strTests = []struct {
{nat{1234567890}, uppercaseDigits[0:10], "1234567890"},
{nat{0xdeadbeef}, lowercaseDigits[0:16], "deadbeef"},
{nat{0xdeadbeef}, uppercaseDigits[0:16], "DEADBEEF"},
+ {nat{0x229be7}, lowercaseDigits[0:17], "1a2b3c"},
+ {nat{0x309663e6}, uppercaseDigits[0:32], "O9COV6"},
}
@@ -190,20 +196,170 @@ func TestString(t *testing.T) {
t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
}
- x, b, n := nat(nil).scan(a.s, len(a.c))
+ x, b, err := nat(nil).scan(strings.NewReader(a.s), len(a.c))
if x.cmp(a.x) != 0 {
t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
}
if b != len(a.c) {
t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, len(a.c))
}
- if n != len(a.s) {
- t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s))
+ if err != nil {
+ t.Errorf("scan%+v\n\tgot error = %s", a, err)
}
}
}
+var natScanTests = []struct {
+ s string // string to be scanned
+ base int // input base
+ x nat // expected nat
+ b int // expected base
+ ok bool // expected success
+ next int // next character (or 0, if at EOF)
+}{
+ // error: illegal base
+ {base: -1},
+ {base: 1},
+ {base: 37},
+
+ // error: no mantissa
+ {},
+ {s: "?"},
+ {base: 10},
+ {base: 36},
+ {s: "?", base: 10},
+ {s: "0x"},
+ {s: "345", base: 2},
+
+ // no errors
+ {"0", 0, nil, 10, true, 0},
+ {"0", 10, nil, 10, true, 0},
+ {"0", 36, nil, 36, true, 0},
+ {"1", 0, nat{1}, 10, true, 0},
+ {"1", 10, nat{1}, 10, true, 0},
+ {"0 ", 0, nil, 10, true, ' '},
+ {"08", 0, nil, 10, true, '8'},
+ {"018", 0, nat{1}, 8, true, '8'},
+ {"0b1", 0, nat{1}, 2, true, 0},
+ {"0b11000101", 0, nat{0xc5}, 2, true, 0},
+ {"03271", 0, nat{03271}, 8, true, 0},
+ {"10ab", 0, nat{10}, 10, true, 'a'},
+ {"1234567890", 0, nat{1234567890}, 10, true, 0},
+ {"xyz", 36, nat{(33*36+34)*36 + 35}, 36, true, 0},
+ {"xyz?", 36, nat{(33*36+34)*36 + 35}, 36, true, '?'},
+ {"0x", 16, nil, 16, true, 'x'},
+ {"0xdeadbeef", 0, nat{0xdeadbeef}, 16, true, 0},
+ {"0XDEADBEEF", 0, nat{0xdeadbeef}, 16, true, 0},
+}
+
+
+func TestScanBase(t *testing.T) {
+ for _, a := range natScanTests {
+ r := strings.NewReader(a.s)
+ x, b, err := nat(nil).scan(r, a.base)
+ if err == nil && !a.ok {
+ t.Errorf("scan%+v\n\texpected error", a)
+ }
+ if err != nil {
+ if a.ok {
+ t.Errorf("scan%+v\n\tgot error = %s", a, err)
+ }
+ continue
+ }
+ if x.cmp(a.x) != 0 {
+ t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
+ }
+ if b != a.b {
+ t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.base)
+ }
+ next, _, err := r.ReadRune()
+ if err == os.EOF {
+ next = 0
+ err = nil
+ }
+ if err == nil && next != a.next {
+ t.Errorf("scan%+v\n\tgot next = %q; want %q", a, next, a.next)
+ }
+ }
+}
+
+
+var pi = "3" +
+ "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" +
+ "32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" +
+ "28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" +
+ "96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" +
+ "31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" +
+ "60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" +
+ "22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" +
+ "29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" +
+ "81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" +
+ "21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" +
+ "55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" +
+ "63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" +
+ "75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" +
+ "45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" +
+ "34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" +
+ "16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" +
+ "04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" +
+ "26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" +
+ "99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" +
+ "53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" +
+ "68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" +
+ "13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" +
+ "88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" +
+ "79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" +
+ "68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" +
+ "21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" +
+ "06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" +
+ "14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" +
+ "21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" +
+ "05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" +
+ "23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" +
+ "90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" +
+ "31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" +
+ "20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" +
+ "97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" +
+ "44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" +
+ "44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" +
+ "85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" +
+ "58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" +
+ "27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" +
+ "09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" +
+ "79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" +
+ "06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" +
+ "91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" +
+ "94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" +
+ "78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" +
+ "24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" +
+ "59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" +
+ "34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" +
+ "88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" +
+ "94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337"
+
+
+// Test case for BenchmarkScanPi.
+func TestScanPi(t *testing.T) {
+ var x nat
+ z, _, err := x.scan(strings.NewReader(pi), 10)
+ if err != nil {
+ t.Errorf("scanning pi: %s", err)
+ }
+ if s := z.decimalString(); s != pi {
+ t.Errorf("scanning pi: got %s", s)
+ }
+}
+
+
+func BenchmarkScanPi(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ var x nat
+ x.scan(strings.NewReader(pi), 10)
+ }
+}
+
+
func TestLeadingZeros(t *testing.T) {
var x Word = _B >> 1
for i := 0; i <= _W; i++ {
@@ -344,14 +500,14 @@ var expNNTests = []struct {
func TestExpNN(t *testing.T) {
for i, test := range expNNTests {
- x, _, _ := nat(nil).scan(test.x, 0)
- y, _, _ := nat(nil).scan(test.y, 0)
- out, _, _ := nat(nil).scan(test.out, 0)
+ x, _, _ := nat(nil).scan(strings.NewReader(test.x), 0)
+ y, _, _ := nat(nil).scan(strings.NewReader(test.y), 0)
+ out, _, _ := nat(nil).scan(strings.NewReader(test.out), 0)
var m nat
if len(test.m) > 0 {
- m, _, _ = nat(nil).scan(test.m, 0)
+ m, _, _ = nat(nil).scan(strings.NewReader(test.m), 0)
}
z := nat(nil).expNN(x, y, m)
diff --git a/src/pkg/big/rat.go b/src/pkg/big/rat.go
index 2adf316e6..f11c27425 100644
--- a/src/pkg/big/rat.go
+++ b/src/pkg/big/rat.go
@@ -6,7 +6,11 @@
package big
-import "strings"
+import (
+ "fmt"
+ "os"
+ "strings"
+)
// A Rat represents a quotient a/b of arbitrary precision. The zero value for
// a Rat, 0/0, is not a legal Rat.
@@ -209,6 +213,28 @@ func (z *Rat) Set(x *Rat) *Rat {
}
+func ratTok(ch int) bool {
+ return strings.IndexRune("+-/0123456789.eE", ch) >= 0
+}
+
+
+// Scan is a support routine for fmt.Scanner. It accepts the formats
+// 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.
+func (z *Rat) Scan(s fmt.ScanState, ch int) os.Error {
+ tok, err := s.Token(true, ratTok)
+ if err != nil {
+ return err
+ }
+ if strings.IndexRune("efgEFGv", ch) < 0 {
+ return os.ErrorString("Rat.Scan: invalid verb")
+ }
+ if _, ok := z.SetString(string(tok)); !ok {
+ return os.ErrorString("Rat.Scan: invalid syntax")
+ }
+ return nil
+}
+
+
// 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. If the operation failed, the value of z
@@ -225,8 +251,8 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
return z, false
}
s = s[sep+1:]
- var n int
- if z.b, _, n = z.b.scan(s, 10); n != len(s) {
+ var err os.Error
+ if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil {
return z, false
}
return z.norm(), true
diff --git a/src/pkg/big/rat_test.go b/src/pkg/big/rat_test.go
index 8f42949b0..ae5c7c993 100644
--- a/src/pkg/big/rat_test.go
+++ b/src/pkg/big/rat_test.go
@@ -4,7 +4,11 @@
package big
-import "testing"
+import (
+ "bytes"
+ "fmt"
+ "testing"
+)
var setStringTests = []struct {
@@ -53,6 +57,29 @@ func TestRatSetString(t *testing.T) {
}
+func TestRatScan(t *testing.T) {
+ var buf bytes.Buffer
+ for i, test := range setStringTests {
+ x := new(Rat)
+ buf.Reset()
+ buf.WriteString(test.in)
+
+ _, err := fmt.Fscanf(&buf, "%v", x)
+ if err == nil != test.ok {
+ if test.ok {
+ t.Errorf("#%d error: %s", i, err.String())
+ } else {
+ t.Errorf("#%d expected error", i)
+ }
+ continue
+ }
+ if err == nil && x.RatString() != test.out {
+ t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
+ }
+ }
+}
+
+
var floatStringTests = []struct {
in string
prec int
generated by cgit v1.2.3 (git 2.46.0) at 2025-10-22 21:36:59 +0000