1// BSON library for Go
2//
3// Copyright (c) 2010-2012 - Gustavo Niemeyer <gustavo@niemeyer.net>
4//
5// All rights reserved.
6//
7// Redistribution and use in source and binary forms, with or without
8// modification, are permitted provided that the following conditions are met:
9//
10// 1. Redistributions of source code must retain the above copyright notice, this
11//    list of conditions and the following disclaimer.
12// 2. Redistributions in binary form must reproduce the above copyright notice,
13//    this list of conditions and the following disclaimer in the documentation
14//    and/or other materials provided with the distribution.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
20// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27package bson
28
29import (
30	"fmt"
31	"strconv"
32	"strings"
33)
34
35// Decimal128 holds decimal128 BSON values.
36type Decimal128 struct {
37	h, l uint64
38}
39
40func (d Decimal128) String() string {
41	var pos int     // positive sign
42	var e int       // exponent
43	var h, l uint64 // significand high/low
44
45	if d.h>>63&1 == 0 {
46		pos = 1
47	}
48
49	switch d.h >> 58 & (1<<5 - 1) {
50	case 0x1F:
51		return "NaN"
52	case 0x1E:
53		return "-Inf"[pos:]
54	}
55
56	l = d.l
57	if d.h>>61&3 == 3 {
58		// Bits: 1*sign 2*ignored 14*exponent 111*significand.
59		// Implicit 0b100 prefix in significand.
60		e = int(d.h>>47&(1<<14-1)) - 6176
61		//h = 4<<47 | d.h&(1<<47-1)
62		// Spec says all of these values are out of range.
63		h, l = 0, 0
64	} else {
65		// Bits: 1*sign 14*exponent 113*significand
66		e = int(d.h>>49&(1<<14-1)) - 6176
67		h = d.h & (1<<49 - 1)
68	}
69
70	// Would be handled by the logic below, but that's trivial and common.
71	if h == 0 && l == 0 && e == 0 {
72		return "-0"[pos:]
73	}
74
75	var repr [48]byte // Loop 5 times over 9 digits plus dot, negative sign, and leading zero.
76	var last = len(repr)
77	var i = len(repr)
78	var dot = len(repr) + e
79	var rem uint32
80Loop:
81	for d9 := 0; d9 < 5; d9++ {
82		h, l, rem = divmod(h, l, 1e9)
83		for d1 := 0; d1 < 9; d1++ {
84			// Handle "-0.0", "0.00123400", "-1.00E-6", "1.050E+3", etc.
85			if i < len(repr) && (dot == i || l == 0 && h == 0 && rem > 0 && rem < 10 && (dot < i-6 || e > 0)) {
86				e += len(repr) - i
87				i--
88				repr[i] = '.'
89				last = i - 1
90				dot = len(repr) // Unmark.
91			}
92			c := '0' + byte(rem%10)
93			rem /= 10
94			i--
95			repr[i] = c
96			// Handle "0E+3", "1E+3", etc.
97			if l == 0 && h == 0 && rem == 0 && i == len(repr)-1 && (dot < i-5 || e > 0) {
98				last = i
99				break Loop
100			}
101			if c != '0' {
102				last = i
103			}
104			// Break early. Works without it, but why.
105			if dot > i && l == 0 && h == 0 && rem == 0 {
106				break Loop
107			}
108		}
109	}
110	repr[last-1] = '-'
111	last--
112
113	if e > 0 {
114		return string(repr[last+pos:]) + "E+" + strconv.Itoa(e)
115	}
116	if e < 0 {
117		return string(repr[last+pos:]) + "E" + strconv.Itoa(e)
118	}
119	return string(repr[last+pos:])
120}
121
122func divmod(h, l uint64, div uint32) (qh, ql uint64, rem uint32) {
123	div64 := uint64(div)
124	a := h >> 32
125	aq := a / div64
126	ar := a % div64
127	b := ar<<32 + h&(1<<32-1)
128	bq := b / div64
129	br := b % div64
130	c := br<<32 + l>>32
131	cq := c / div64
132	cr := c % div64
133	d := cr<<32 + l&(1<<32-1)
134	dq := d / div64
135	dr := d % div64
136	return (aq<<32 | bq), (cq<<32 | dq), uint32(dr)
137}
138
139var dNaN = Decimal128{0x1F << 58, 0}
140var dPosInf = Decimal128{0x1E << 58, 0}
141var dNegInf = Decimal128{0x3E << 58, 0}
142
143func dErr(s string) (Decimal128, error) {
144	return dNaN, fmt.Errorf("cannot parse %q as a decimal128", s)
145}
146
147// ParseDecimal128 parse a string and return the corresponding value as
148// a decimal128
149func ParseDecimal128(s string) (Decimal128, error) {
150	orig := s
151	if s == "" {
152		return dErr(orig)
153	}
154	neg := s[0] == '-'
155	if neg || s[0] == '+' {
156		s = s[1:]
157	}
158
159	if (len(s) == 3 || len(s) == 8) && (s[0] == 'N' || s[0] == 'n' || s[0] == 'I' || s[0] == 'i') {
160		if s == "NaN" || s == "nan" || strings.EqualFold(s, "nan") {
161			return dNaN, nil
162		}
163		if s == "Inf" || s == "inf" || strings.EqualFold(s, "inf") || strings.EqualFold(s, "infinity") {
164			if neg {
165				return dNegInf, nil
166			}
167			return dPosInf, nil
168		}
169		return dErr(orig)
170	}
171
172	var h, l uint64
173	var e int
174
175	var add, ovr uint32
176	var mul uint32 = 1
177	var dot = -1
178	var digits = 0
179	var i = 0
180	for i < len(s) {
181		c := s[i]
182		if mul == 1e9 {
183			h, l, ovr = muladd(h, l, mul, add)
184			mul, add = 1, 0
185			if ovr > 0 || h&((1<<15-1)<<49) > 0 {
186				return dErr(orig)
187			}
188		}
189		if c >= '0' && c <= '9' {
190			i++
191			if c > '0' || digits > 0 {
192				digits++
193			}
194			if digits > 34 {
195				if c == '0' {
196					// Exact rounding.
197					e++
198					continue
199				}
200				return dErr(orig)
201			}
202			mul *= 10
203			add *= 10
204			add += uint32(c - '0')
205			continue
206		}
207		if c == '.' {
208			i++
209			if dot >= 0 || i == 1 && len(s) == 1 {
210				return dErr(orig)
211			}
212			if i == len(s) {
213				break
214			}
215			if s[i] < '0' || s[i] > '9' || e > 0 {
216				return dErr(orig)
217			}
218			dot = i
219			continue
220		}
221		break
222	}
223	if i == 0 {
224		return dErr(orig)
225	}
226	if mul > 1 {
227		h, l, ovr = muladd(h, l, mul, add)
228		if ovr > 0 || h&((1<<15-1)<<49) > 0 {
229			return dErr(orig)
230		}
231	}
232	if dot >= 0 {
233		e += dot - i
234	}
235	if i+1 < len(s) && (s[i] == 'E' || s[i] == 'e') {
236		i++
237		eneg := s[i] == '-'
238		if eneg || s[i] == '+' {
239			i++
240			if i == len(s) {
241				return dErr(orig)
242			}
243		}
244		n := 0
245		for i < len(s) && n < 1e4 {
246			c := s[i]
247			i++
248			if c < '0' || c > '9' {
249				return dErr(orig)
250			}
251			n *= 10
252			n += int(c - '0')
253		}
254		if eneg {
255			n = -n
256		}
257		e += n
258		for e < -6176 {
259			// Subnormal.
260			var div uint32 = 1
261			for div < 1e9 && e < -6176 {
262				div *= 10
263				e++
264			}
265			var rem uint32
266			h, l, rem = divmod(h, l, div)
267			if rem > 0 {
268				return dErr(orig)
269			}
270		}
271		for e > 6111 {
272			// Clamped.
273			var mul uint32 = 1
274			for mul < 1e9 && e > 6111 {
275				mul *= 10
276				e--
277			}
278			h, l, ovr = muladd(h, l, mul, 0)
279			if ovr > 0 || h&((1<<15-1)<<49) > 0 {
280				return dErr(orig)
281			}
282		}
283		if e < -6176 || e > 6111 {
284			return dErr(orig)
285		}
286	}
287
288	if i < len(s) {
289		return dErr(orig)
290	}
291
292	h |= uint64(e+6176) & uint64(1<<14-1) << 49
293	if neg {
294		h |= 1 << 63
295	}
296	return Decimal128{h, l}, nil
297}
298
299func muladd(h, l uint64, mul uint32, add uint32) (resh, resl uint64, overflow uint32) {
300	mul64 := uint64(mul)
301	a := mul64 * (l & (1<<32 - 1))
302	b := a>>32 + mul64*(l>>32)
303	c := b>>32 + mul64*(h&(1<<32-1))
304	d := c>>32 + mul64*(h>>32)
305
306	a = a&(1<<32-1) + uint64(add)
307	b = b&(1<<32-1) + a>>32
308	c = c&(1<<32-1) + b>>32
309	d = d&(1<<32-1) + c>>32
310
311	return (d<<32 | c&(1<<32-1)), (b<<32 | a&(1<<32-1)), uint32(d >> 32)
312}
313