1 files changed, 270 insertions, 0 deletions
diff --git a/src/math/big/decimal.go b/src/math/big/decimal.go
new file mode 100644
index 0000000..716f03b
--- /dev/null
+++ b/src/math/big/decimal.go
@@ -0,0 +1,270 @@
+// Copyright 2015 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.
+
+// This file implements multi-precision decimal numbers.
+// The implementation is for float to decimal conversion only;
+// not general purpose use.
+// The only operations are precise conversion from binary to
+// decimal and rounding.
+//
+// The key observation and some code (shr) is borrowed from
+// strconv/decimal.go: conversion of binary fractional values can be done
+// precisely in multi-precision decimal because 2 divides 10 (required for
+// >> of mantissa); but conversion of decimal floating-point values cannot
+// be done precisely in binary representation.
+//
+// In contrast to strconv/decimal.go, only right shift is implemented in
+// decimal format - left shift can be done precisely in binary format.
+
+package big
+
+// A decimal represents an unsigned floating-point number in decimal representation.
+// The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1,
+// with the most-significant mantissa digit at index 0. For the zero decimal, the
+// mantissa length and exponent are 0.
+// The zero value for decimal represents a ready-to-use 0.0.
+type decimal struct {
+	mant []byte // mantissa ASCII digits, big-endian
+	exp  int    // exponent
+}
+
+// at returns the i'th mantissa digit, starting with the most significant digit at 0.
+func (d *decimal) at(i int) byte {
+	if 0 <= i && i < len(d.mant) {
+		return d.mant[i]
+	}
+	return '0'
+}
+
+// Maximum shift amount that can be done in one pass without overflow.
+// A Word has _W bits and (1<<maxShift - 1)*10 + 9 must fit into Word.
+const maxShift = _W - 4
+
+// TODO(gri) Since we know the desired decimal precision when converting
+// a floating-point number, we may be able to limit the number of decimal
+// digits that need to be computed by init by providing an additional
+// precision argument and keeping track of when a number was truncated early
+// (equivalent of "sticky bit" in binary rounding).
+
+// TODO(gri) Along the same lines, enforce some limit to shift magnitudes
+// to avoid "infinitely" long running conversions (until we run out of space).
+
+// Init initializes x to the decimal representation of m << shift (for
+// shift >= 0), or m >> -shift (for shift < 0).
+func (x *decimal) init(m nat, shift int) {
+	// special case 0
+	if len(m) == 0 {
+		x.mant = x.mant[:0]
+		x.exp = 0
+		return
+	}
+
+	// Optimization: If we need to shift right, first remove any trailing
+	// zero bits from m to reduce shift amount that needs to be done in
+	// decimal format (since that is likely slower).
+	if shift < 0 {
+		ntz := m.trailingZeroBits()
+		s := uint(-shift)
+		if s >= ntz {
+			s = ntz // shift at most ntz bits
+		}
+		m = nat(nil).shr(m, s)
+		shift += int(s)
+	}
+
+	// Do any shift left in binary representation.
+	if shift > 0 {
+		m = nat(nil).shl(m, uint(shift))
+		shift = 0
+	}
+
+	// Convert mantissa into decimal representation.
+	s := m.utoa(10)
+	n := len(s)
+	x.exp = n
+	// Trim trailing zeros; instead the exponent is tracking
+	// the decimal point independent of the number of digits.
+	for n > 0 && s[n-1] == '0' {
+		n--
+	}
+	x.mant = append(x.mant[:0], s[:n]...)
+
+	// Do any (remaining) shift right in decimal representation.
+	if shift < 0 {
+		for shift < -maxShift {
+			shr(x, maxShift)
+			shift += maxShift
+		}
+		shr(x, uint(-shift))
+	}
+}
+
+// shr implements x >> s, for s <= maxShift.
+func shr(x *decimal, s uint) {
+	// Division by 1<<s using shift-and-subtract algorithm.
+
+	// pick up enough leading digits to cover first shift
+	r := 0 // read index
+	var n Word
+	for n>>s == 0 && r < len(x.mant) {
+		ch := Word(x.mant[r])
+		r++
+		n = n*10 + ch - '0'
+	}
+	if n == 0 {
+		// x == 0; shouldn't get here, but handle anyway
+		x.mant = x.mant[:0]
+		return
+	}
+	for n>>s == 0 {
+		r++
+		n *= 10
+	}
+	x.exp += 1 - r
+
+	// read a digit, write a digit
+	w := 0 // write index
+	mask := Word(1)<<s - 1
+	for r < len(x.mant) {
+		ch := Word(x.mant[r])
+		r++
+		d := n >> s
+		n &= mask // n -= d << s
+		x.mant[w] = byte(d + '0')
+		w++
+		n = n*10 + ch - '0'
+	}
+
+	// write extra digits that still fit
+	for n > 0 && w < len(x.mant) {
+		d := n >> s
+		n &= mask
+		x.mant[w] = byte(d + '0')
+		w++
+		n = n * 10
+	}
+	x.mant = x.mant[:w] // the number may be shorter (e.g. 1024 >> 10)
+
+	// append additional digits that didn't fit
+	for n > 0 {
+		d := n >> s
+		n &= mask
+		x.mant = append(x.mant, byte(d+'0'))
+		n = n * 10
+	}
+
+	trim(x)
+}
+
+func (x *decimal) String() string {
+	if len(x.mant) == 0 {
+		return "0"
+	}
+
+	var buf []byte
+	switch {
+	case x.exp <= 0:
+		// 0.00ddd
+		buf = make([]byte, 0, 2+(-x.exp)+len(x.mant))
+		buf = append(buf, "0."...)
+		buf = appendZeros(buf, -x.exp)
+		buf = append(buf, x.mant...)
+
+	case /* 0 < */ x.exp < len(x.mant):
+		// dd.ddd
+		buf = make([]byte, 0, 1+len(x.mant))
+		buf = append(buf, x.mant[:x.exp]...)
+		buf = append(buf, '.')
+		buf = append(buf, x.mant[x.exp:]...)
+
+	default: // len(x.mant) <= x.exp
+		// ddd00
+		buf = make([]byte, 0, x.exp)
+		buf = append(buf, x.mant...)
+		buf = appendZeros(buf, x.exp-len(x.mant))
+	}
+
+	return string(buf)
+}
+
+// appendZeros appends n 0 digits to buf and returns buf.
+func appendZeros(buf []byte, n int) []byte {
+	for ; n > 0; n-- {
+		buf = append(buf, '0')
+	}
+	return buf
+}
+
+// shouldRoundUp reports if x should be rounded up
+// if shortened to n digits. n must be a valid index
+// for x.mant.
+func shouldRoundUp(x *decimal, n int) bool {
+	if x.mant[n] == '5' && n+1 == len(x.mant) {
+		// exactly halfway - round to even
+		return n > 0 && (x.mant[n-1]-'0')&1 != 0
+	}
+	// not halfway - digit tells all (x.mant has no trailing zeros)
+	return x.mant[n] >= '5'
+}
+
+// round sets x to (at most) n mantissa digits by rounding it
+// to the nearest even value with n (or fever) mantissa digits.
+// If n < 0, x remains unchanged.
+func (x *decimal) round(n int) {
+	if n < 0 || n >= len(x.mant) {
+		return // nothing to do
+	}
+
+	if shouldRoundUp(x, n) {
+		x.roundUp(n)
+	} else {
+		x.roundDown(n)
+	}
+}
+
+func (x *decimal) roundUp(n int) {
+	if n < 0 || n >= len(x.mant) {
+		return // nothing to do
+	}
+	// 0 <= n < len(x.mant)
+
+	// find first digit < '9'
+	for n > 0 && x.mant[n-1] >= '9' {
+		n--
+	}
+
+	if n == 0 {
+		// all digits are '9's => round up to '1' and update exponent
+		x.mant[0] = '1' // ok since len(x.mant) > n
+		x.mant = x.mant[:1]
+		x.exp++
+		return
+	}
+
+	// n > 0 && x.mant[n-1] < '9'
+	x.mant[n-1]++
+	x.mant = x.mant[:n]
+	// x already trimmed
+}
+
+func (x *decimal) roundDown(n int) {
+	if n < 0 || n >= len(x.mant) {
+		return // nothing to do
+	}
+	x.mant = x.mant[:n]
+	trim(x)
+}
+
+// trim cuts off any trailing zeros from x's mantissa;
+// they are meaningless for the value of x.
+func trim(x *decimal) {
+	i := len(x.mant)
+	for i > 0 && x.mant[i-1] == '0' {
+		i--
+	}
+	x.mant = x.mant[:i]
+	if i == 0 {
+		x.exp = 0
+	}
+}