decimal.go raw
1 // Copyright (C) MongoDB, Inc. 2017-present.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may
4 // not use this file except in compliance with the License. You may obtain
5 // a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
6 //
7 // Based on gopkg.in/mgo.v2/bson by Gustavo Niemeyer
8 // See THIRD-PARTY-NOTICES for original license terms.
9
10 package primitive
11
12 import (
13 "encoding/json"
14 "errors"
15 "fmt"
16 "math/big"
17 "regexp"
18 "strconv"
19 "strings"
20 )
21
22 // These constants are the maximum and minimum values for the exponent field in a decimal128 value.
23 const (
24 MaxDecimal128Exp = 6111
25 MinDecimal128Exp = -6176
26 )
27
28 // These errors are returned when an invalid value is parsed as a big.Int.
29 var (
30 ErrParseNaN = errors.New("cannot parse NaN as a *big.Int")
31 ErrParseInf = errors.New("cannot parse Infinity as a *big.Int")
32 ErrParseNegInf = errors.New("cannot parse -Infinity as a *big.Int")
33 )
34
35 // Decimal128 holds decimal128 BSON values.
36 type Decimal128 struct {
37 h, l uint64
38 }
39
40 // NewDecimal128 creates a Decimal128 using the provide high and low uint64s.
41 func NewDecimal128(h, l uint64) Decimal128 {
42 return Decimal128{h: h, l: l}
43 }
44
45 // GetBytes returns the underlying bytes of the BSON decimal value as two uint64 values. The first
46 // contains the most first 8 bytes of the value and the second contains the latter.
47 func (d Decimal128) GetBytes() (uint64, uint64) {
48 return d.h, d.l
49 }
50
51 // String returns a string representation of the decimal value.
52 func (d Decimal128) String() string {
53 var posSign int // positive sign
54 var exp int // exponent
55 var high, low uint64 // significand high/low
56
57 if d.h>>63&1 == 0 {
58 posSign = 1
59 }
60
61 switch d.h >> 58 & (1<<5 - 1) {
62 case 0x1F:
63 return "NaN"
64 case 0x1E:
65 return "-Infinity"[posSign:]
66 }
67
68 low = d.l
69 if d.h>>61&3 == 3 {
70 // Bits: 1*sign 2*ignored 14*exponent 111*significand.
71 // Implicit 0b100 prefix in significand.
72 exp = int(d.h >> 47 & (1<<14 - 1))
73 //high = 4<<47 | d.h&(1<<47-1)
74 // Spec says all of these values are out of range.
75 high, low = 0, 0
76 } else {
77 // Bits: 1*sign 14*exponent 113*significand
78 exp = int(d.h >> 49 & (1<<14 - 1))
79 high = d.h & (1<<49 - 1)
80 }
81 exp += MinDecimal128Exp
82
83 // Would be handled by the logic below, but that's trivial and common.
84 if high == 0 && low == 0 && exp == 0 {
85 return "-0"[posSign:]
86 }
87
88 var repr [48]byte // Loop 5 times over 9 digits plus dot, negative sign, and leading zero.
89 var last = len(repr)
90 var i = len(repr)
91 var dot = len(repr) + exp
92 var rem uint32
93 Loop:
94 for d9 := 0; d9 < 5; d9++ {
95 high, low, rem = divmod(high, low, 1e9)
96 for d1 := 0; d1 < 9; d1++ {
97 // Handle "-0.0", "0.00123400", "-1.00E-6", "1.050E+3", etc.
98 if i < len(repr) && (dot == i || low == 0 && high == 0 && rem > 0 && rem < 10 && (dot < i-6 || exp > 0)) {
99 exp += len(repr) - i
100 i--
101 repr[i] = '.'
102 last = i - 1
103 dot = len(repr) // Unmark.
104 }
105 c := '0' + byte(rem%10)
106 rem /= 10
107 i--
108 repr[i] = c
109 // Handle "0E+3", "1E+3", etc.
110 if low == 0 && high == 0 && rem == 0 && i == len(repr)-1 && (dot < i-5 || exp > 0) {
111 last = i
112 break Loop
113 }
114 if c != '0' {
115 last = i
116 }
117 // Break early. Works without it, but why.
118 if dot > i && low == 0 && high == 0 && rem == 0 {
119 break Loop
120 }
121 }
122 }
123 repr[last-1] = '-'
124 last--
125
126 if exp > 0 {
127 return string(repr[last+posSign:]) + "E+" + strconv.Itoa(exp)
128 }
129 if exp < 0 {
130 return string(repr[last+posSign:]) + "E" + strconv.Itoa(exp)
131 }
132 return string(repr[last+posSign:])
133 }
134
135 // BigInt returns significand as big.Int and exponent, bi * 10 ^ exp.
136 func (d Decimal128) BigInt() (*big.Int, int, error) {
137 high, low := d.GetBytes()
138 posSign := high>>63&1 == 0 // positive sign
139
140 switch high >> 58 & (1<<5 - 1) {
141 case 0x1F:
142 return nil, 0, ErrParseNaN
143 case 0x1E:
144 if posSign {
145 return nil, 0, ErrParseInf
146 }
147 return nil, 0, ErrParseNegInf
148 }
149
150 var exp int
151 if high>>61&3 == 3 {
152 // Bits: 1*sign 2*ignored 14*exponent 111*significand.
153 // Implicit 0b100 prefix in significand.
154 exp = int(high >> 47 & (1<<14 - 1))
155 //high = 4<<47 | d.h&(1<<47-1)
156 // Spec says all of these values are out of range.
157 high, low = 0, 0
158 } else {
159 // Bits: 1*sign 14*exponent 113*significand
160 exp = int(high >> 49 & (1<<14 - 1))
161 high = high & (1<<49 - 1)
162 }
163 exp += MinDecimal128Exp
164
165 // Would be handled by the logic below, but that's trivial and common.
166 if high == 0 && low == 0 && exp == 0 {
167 if posSign {
168 return new(big.Int), 0, nil
169 }
170 return new(big.Int), 0, nil
171 }
172
173 bi := big.NewInt(0)
174 const host32bit = ^uint(0)>>32 == 0
175 if host32bit {
176 bi.SetBits([]big.Word{big.Word(low), big.Word(low >> 32), big.Word(high), big.Word(high >> 32)})
177 } else {
178 bi.SetBits([]big.Word{big.Word(low), big.Word(high)})
179 }
180
181 if !posSign {
182 return bi.Neg(bi), exp, nil
183 }
184 return bi, exp, nil
185 }
186
187 // IsNaN returns whether d is NaN.
188 func (d Decimal128) IsNaN() bool {
189 return d.h>>58&(1<<5-1) == 0x1F
190 }
191
192 // IsInf returns:
193 //
194 // +1 d == Infinity
195 // 0 other case
196 // -1 d == -Infinity
197 func (d Decimal128) IsInf() int {
198 if d.h>>58&(1<<5-1) != 0x1E {
199 return 0
200 }
201
202 if d.h>>63&1 == 0 {
203 return 1
204 }
205 return -1
206 }
207
208 // IsZero returns true if d is the empty Decimal128.
209 func (d Decimal128) IsZero() bool {
210 return d.h == 0 && d.l == 0
211 }
212
213 // MarshalJSON returns Decimal128 as a string.
214 func (d Decimal128) MarshalJSON() ([]byte, error) {
215 return json.Marshal(d.String())
216 }
217
218 // UnmarshalJSON creates a primitive.Decimal128 from a JSON string, an extended JSON $numberDecimal value, or the string
219 // "null". If b is a JSON string or extended JSON value, d will have the value of that string, and if b is "null", d will
220 // be unchanged.
221 func (d *Decimal128) UnmarshalJSON(b []byte) error {
222 // Ignore "null" to keep parity with the standard library. Decoding a JSON null into a non-pointer Decimal128 field
223 // will leave the field unchanged. For pointer values, encoding/json will set the pointer to nil and will not
224 // enter the UnmarshalJSON hook.
225 if string(b) == "null" {
226 return nil
227 }
228
229 var res interface{}
230 err := json.Unmarshal(b, &res)
231 if err != nil {
232 return err
233 }
234 str, ok := res.(string)
235
236 // Extended JSON
237 if !ok {
238 m, ok := res.(map[string]interface{})
239 if !ok {
240 return errors.New("not an extended JSON Decimal128: expected document")
241 }
242 d128, ok := m["$numberDecimal"]
243 if !ok {
244 return errors.New("not an extended JSON Decimal128: expected key $numberDecimal")
245 }
246 str, ok = d128.(string)
247 if !ok {
248 return errors.New("not an extended JSON Decimal128: expected decimal to be string")
249 }
250 }
251
252 *d, err = ParseDecimal128(str)
253 return err
254 }
255
256 func divmod(h, l uint64, div uint32) (qh, ql uint64, rem uint32) {
257 div64 := uint64(div)
258 a := h >> 32
259 aq := a / div64
260 ar := a % div64
261 b := ar<<32 + h&(1<<32-1)
262 bq := b / div64
263 br := b % div64
264 c := br<<32 + l>>32
265 cq := c / div64
266 cr := c % div64
267 d := cr<<32 + l&(1<<32-1)
268 dq := d / div64
269 dr := d % div64
270 return (aq<<32 | bq), (cq<<32 | dq), uint32(dr)
271 }
272
273 var dNaN = Decimal128{0x1F << 58, 0}
274 var dPosInf = Decimal128{0x1E << 58, 0}
275 var dNegInf = Decimal128{0x3E << 58, 0}
276
277 func dErr(s string) (Decimal128, error) {
278 return dNaN, fmt.Errorf("cannot parse %q as a decimal128", s)
279 }
280
281 // match scientific notation number, example -10.15e-18
282 var normalNumber = regexp.MustCompile(`^(?P<int>[-+]?\d*)?(?:\.(?P<dec>\d*))?(?:[Ee](?P<exp>[-+]?\d+))?$`)
283
284 // ParseDecimal128 takes the given string and attempts to parse it into a valid
285 // Decimal128 value.
286 func ParseDecimal128(s string) (Decimal128, error) {
287 if s == "" {
288 return dErr(s)
289 }
290
291 matches := normalNumber.FindStringSubmatch(s)
292 if len(matches) == 0 {
293 orig := s
294 neg := s[0] == '-'
295 if neg || s[0] == '+' {
296 s = s[1:]
297 }
298
299 if s == "NaN" || s == "nan" || strings.EqualFold(s, "nan") {
300 return dNaN, nil
301 }
302 if s == "Inf" || s == "inf" || strings.EqualFold(s, "inf") || strings.EqualFold(s, "infinity") {
303 if neg {
304 return dNegInf, nil
305 }
306 return dPosInf, nil
307 }
308 return dErr(orig)
309 }
310
311 intPart := matches[1]
312 decPart := matches[2]
313 expPart := matches[3]
314
315 var err error
316 exp := 0
317 if expPart != "" {
318 exp, err = strconv.Atoi(expPart)
319 if err != nil {
320 return dErr(s)
321 }
322 }
323 if decPart != "" {
324 exp -= len(decPart)
325 }
326
327 if len(strings.Trim(intPart+decPart, "-0")) > 35 {
328 return dErr(s)
329 }
330
331 // Parse the significand (i.e. the non-exponent part) as a big.Int.
332 bi, ok := new(big.Int).SetString(intPart+decPart, 10)
333 if !ok {
334 return dErr(s)
335 }
336
337 d, ok := ParseDecimal128FromBigInt(bi, exp)
338 if !ok {
339 return dErr(s)
340 }
341
342 if bi.Sign() == 0 && s[0] == '-' {
343 d.h |= 1 << 63
344 }
345
346 return d, nil
347 }
348
349 var (
350 ten = big.NewInt(10)
351 zero = new(big.Int)
352
353 maxS, _ = new(big.Int).SetString("9999999999999999999999999999999999", 10)
354 )
355
356 // ParseDecimal128FromBigInt attempts to parse the given significand and exponent into a valid Decimal128 value.
357 func ParseDecimal128FromBigInt(bi *big.Int, exp int) (Decimal128, bool) {
358 //copy
359 bi = new(big.Int).Set(bi)
360
361 q := new(big.Int)
362 r := new(big.Int)
363
364 // If the significand is zero, the logical value will always be zero, independent of the
365 // exponent. However, the loops for handling out-of-range exponent values below may be extremely
366 // slow for zero values because the significand never changes. Limit the exponent value to the
367 // supported range here to prevent entering the loops below.
368 if bi.Cmp(zero) == 0 {
369 if exp > MaxDecimal128Exp {
370 exp = MaxDecimal128Exp
371 }
372 if exp < MinDecimal128Exp {
373 exp = MinDecimal128Exp
374 }
375 }
376
377 for bigIntCmpAbs(bi, maxS) == 1 {
378 bi, _ = q.QuoRem(bi, ten, r)
379 if r.Cmp(zero) != 0 {
380 return Decimal128{}, false
381 }
382 exp++
383 if exp > MaxDecimal128Exp {
384 return Decimal128{}, false
385 }
386 }
387
388 for exp < MinDecimal128Exp {
389 // Subnormal.
390 bi, _ = q.QuoRem(bi, ten, r)
391 if r.Cmp(zero) != 0 {
392 return Decimal128{}, false
393 }
394 exp++
395 }
396 for exp > MaxDecimal128Exp {
397 // Clamped.
398 bi.Mul(bi, ten)
399 if bigIntCmpAbs(bi, maxS) == 1 {
400 return Decimal128{}, false
401 }
402 exp--
403 }
404
405 b := bi.Bytes()
406 var h, l uint64
407 for i := 0; i < len(b); i++ {
408 if i < len(b)-8 {
409 h = h<<8 | uint64(b[i])
410 continue
411 }
412 l = l<<8 | uint64(b[i])
413 }
414
415 h |= uint64(exp-MinDecimal128Exp) & uint64(1<<14-1) << 49
416 if bi.Sign() == -1 {
417 h |= 1 << 63
418 }
419
420 return Decimal128{h: h, l: l}, true
421 }
422
423 // bigIntCmpAbs computes big.Int.Cmp(absoluteValue(x), absoluteValue(y)).
424 func bigIntCmpAbs(x, y *big.Int) int {
425 xAbs := bigIntAbsValue(x)
426 yAbs := bigIntAbsValue(y)
427 return xAbs.Cmp(yAbs)
428 }
429
430 // bigIntAbsValue returns a big.Int containing the absolute value of b.
431 // If b is already a non-negative number, it is returned without any changes or copies.
432 func bigIntAbsValue(b *big.Int) *big.Int {
433 if b.Sign() >= 0 {
434 return b // already positive
435 }
436 return new(big.Int).Abs(b)
437 }
438