decimal.go

Documentation: go.mongodb.org/mongo-driver/bson/primitive

     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  		return new(big.Int), 0, nil
   168  	}
   169  
   170  	bi := big.NewInt(0)
   171  	const host32bit = ^uint(0)>>32 == 0
   172  	if host32bit {
   173  		bi.SetBits([]big.Word{big.Word(low), big.Word(low >> 32), big.Word(high), big.Word(high >> 32)})
   174  	} else {
   175  		bi.SetBits([]big.Word{big.Word(low), big.Word(high)})
   176  	}
   177  
   178  	if !posSign {
   179  		return bi.Neg(bi), exp, nil
   180  	}
   181  	return bi, exp, nil
   182  }
   183  
   184  // IsNaN returns whether d is NaN.
   185  func (d Decimal128) IsNaN() bool {
   186  	return d.h>>58&(1<<5-1) == 0x1F
   187  }
   188  
   189  // IsInf returns:
   190  //
   191  //	+1 d == Infinity
   192  //	 0 other case
   193  //	-1 d == -Infinity
   194  func (d Decimal128) IsInf() int {
   195  	if d.h>>58&(1<<5-1) != 0x1E {
   196  		return 0
   197  	}
   198  
   199  	if d.h>>63&1 == 0 {
   200  		return 1
   201  	}
   202  	return -1
   203  }
   204  
   205  // IsZero returns true if d is the empty Decimal128.
   206  func (d Decimal128) IsZero() bool {
   207  	return d.h == 0 && d.l == 0
   208  }
   209  
   210  // MarshalJSON returns Decimal128 as a string.
   211  func (d Decimal128) MarshalJSON() ([]byte, error) {
   212  	return json.Marshal(d.String())
   213  }
   214  
   215  // UnmarshalJSON creates a primitive.Decimal128 from a JSON string, an extended JSON $numberDecimal value, or the string
   216  // "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
   217  // be unchanged.
   218  func (d *Decimal128) UnmarshalJSON(b []byte) error {
   219  	// Ignore "null" to keep parity with the standard library. Decoding a JSON null into a non-pointer Decimal128 field
   220  	// will leave the field unchanged. For pointer values, encoding/json will set the pointer to nil and will not
   221  	// enter the UnmarshalJSON hook.
   222  	if string(b) == "null" {
   223  		return nil
   224  	}
   225  
   226  	var res interface{}
   227  	err := json.Unmarshal(b, &res)
   228  	if err != nil {
   229  		return err
   230  	}
   231  	str, ok := res.(string)
   232  
   233  	// Extended JSON
   234  	if !ok {
   235  		m, ok := res.(map[string]interface{})
   236  		if !ok {
   237  			return errors.New("not an extended JSON Decimal128: expected document")
   238  		}
   239  		d128, ok := m["$numberDecimal"]
   240  		if !ok {
   241  			return errors.New("not an extended JSON Decimal128: expected key $numberDecimal")
   242  		}
   243  		str, ok = d128.(string)
   244  		if !ok {
   245  			return errors.New("not an extended JSON Decimal128: expected decimal to be string")
   246  		}
   247  	}
   248  
   249  	*d, err = ParseDecimal128(str)
   250  	return err
   251  }
   252  
   253  func divmod(h, l uint64, div uint32) (qh, ql uint64, rem uint32) {
   254  	div64 := uint64(div)
   255  	a := h >> 32
   256  	aq := a / div64
   257  	ar := a % div64
   258  	b := ar<<32 + h&(1<<32-1)
   259  	bq := b / div64
   260  	br := b % div64
   261  	c := br<<32 + l>>32
   262  	cq := c / div64
   263  	cr := c % div64
   264  	d := cr<<32 + l&(1<<32-1)
   265  	dq := d / div64
   266  	dr := d % div64
   267  	return (aq<<32 | bq), (cq<<32 | dq), uint32(dr)
   268  }
   269  
   270  var dNaN = Decimal128{0x1F << 58, 0}
   271  var dPosInf = Decimal128{0x1E << 58, 0}
   272  var dNegInf = Decimal128{0x3E << 58, 0}
   273  
   274  func dErr(s string) (Decimal128, error) {
   275  	return dNaN, fmt.Errorf("cannot parse %q as a decimal128", s)
   276  }
   277  
   278  // match scientific notation number, example -10.15e-18
   279  var normalNumber = regexp.MustCompile(`^(?P<int>[-+]?\d*)?(?:\.(?P<dec>\d*))?(?:[Ee](?P<exp>[-+]?\d+))?$`)
   280  
   281  // ParseDecimal128 takes the given string and attempts to parse it into a valid
   282  // Decimal128 value.
   283  func ParseDecimal128(s string) (Decimal128, error) {
   284  	if s == "" {
   285  		return dErr(s)
   286  	}
   287  
   288  	matches := normalNumber.FindStringSubmatch(s)
   289  	if len(matches) == 0 {
   290  		orig := s
   291  		neg := s[0] == '-'
   292  		if neg || s[0] == '+' {
   293  			s = s[1:]
   294  		}
   295  
   296  		if s == "NaN" || s == "nan" || strings.EqualFold(s, "nan") {
   297  			return dNaN, nil
   298  		}
   299  		if s == "Inf" || s == "inf" || strings.EqualFold(s, "inf") || strings.EqualFold(s, "infinity") {
   300  			if neg {
   301  				return dNegInf, nil
   302  			}
   303  			return dPosInf, nil
   304  		}
   305  		return dErr(orig)
   306  	}
   307  
   308  	intPart := matches[1]
   309  	decPart := matches[2]
   310  	expPart := matches[3]
   311  
   312  	var err error
   313  	exp := 0
   314  	if expPart != "" {
   315  		exp, err = strconv.Atoi(expPart)
   316  		if err != nil {
   317  			return dErr(s)
   318  		}
   319  	}
   320  	if decPart != "" {
   321  		exp -= len(decPart)
   322  	}
   323  
   324  	if len(strings.Trim(intPart+decPart, "-0")) > 35 {
   325  		return dErr(s)
   326  	}
   327  
   328  	// Parse the significand (i.e. the non-exponent part) as a big.Int.
   329  	bi, ok := new(big.Int).SetString(intPart+decPart, 10)
   330  	if !ok {
   331  		return dErr(s)
   332  	}
   333  
   334  	d, ok := ParseDecimal128FromBigInt(bi, exp)
   335  	if !ok {
   336  		return dErr(s)
   337  	}
   338  
   339  	if bi.Sign() == 0 && s[0] == '-' {
   340  		d.h |= 1 << 63
   341  	}
   342  
   343  	return d, nil
   344  }
   345  
   346  var (
   347  	ten  = big.NewInt(10)
   348  	zero = new(big.Int)
   349  
   350  	maxS, _ = new(big.Int).SetString("9999999999999999999999999999999999", 10)
   351  )
   352  
   353  // ParseDecimal128FromBigInt attempts to parse the given significand and exponent into a valid Decimal128 value.
   354  func ParseDecimal128FromBigInt(bi *big.Int, exp int) (Decimal128, bool) {
   355  	//copy
   356  	bi = new(big.Int).Set(bi)
   357  
   358  	q := new(big.Int)
   359  	r := new(big.Int)
   360  
   361  	// If the significand is zero, the logical value will always be zero, independent of the
   362  	// exponent. However, the loops for handling out-of-range exponent values below may be extremely
   363  	// slow for zero values because the significand never changes. Limit the exponent value to the
   364  	// supported range here to prevent entering the loops below.
   365  	if bi.Cmp(zero) == 0 {
   366  		if exp > MaxDecimal128Exp {
   367  			exp = MaxDecimal128Exp
   368  		}
   369  		if exp < MinDecimal128Exp {
   370  			exp = MinDecimal128Exp
   371  		}
   372  	}
   373  
   374  	for bigIntCmpAbs(bi, maxS) == 1 {
   375  		bi, _ = q.QuoRem(bi, ten, r)
   376  		if r.Cmp(zero) != 0 {
   377  			return Decimal128{}, false
   378  		}
   379  		exp++
   380  		if exp > MaxDecimal128Exp {
   381  			return Decimal128{}, false
   382  		}
   383  	}
   384  
   385  	for exp < MinDecimal128Exp {
   386  		// Subnormal.
   387  		bi, _ = q.QuoRem(bi, ten, r)
   388  		if r.Cmp(zero) != 0 {
   389  			return Decimal128{}, false
   390  		}
   391  		exp++
   392  	}
   393  	for exp > MaxDecimal128Exp {
   394  		// Clamped.
   395  		bi.Mul(bi, ten)
   396  		if bigIntCmpAbs(bi, maxS) == 1 {
   397  			return Decimal128{}, false
   398  		}
   399  		exp--
   400  	}
   401  
   402  	b := bi.Bytes()
   403  	var h, l uint64
   404  	for i := 0; i < len(b); i++ {
   405  		if i < len(b)-8 {
   406  			h = h<<8 | uint64(b[i])
   407  			continue
   408  		}
   409  		l = l<<8 | uint64(b[i])
   410  	}
   411  
   412  	h |= uint64(exp-MinDecimal128Exp) & uint64(1<<14-1) << 49
   413  	if bi.Sign() == -1 {
   414  		h |= 1 << 63
   415  	}
   416  
   417  	return Decimal128{h: h, l: l}, true
   418  }
   419  
   420  // bigIntCmpAbs computes big.Int.Cmp(absoluteValue(x), absoluteValue(y)).
   421  func bigIntCmpAbs(x, y *big.Int) int {
   422  	xAbs := bigIntAbsValue(x)
   423  	yAbs := bigIntAbsValue(y)
   424  	return xAbs.Cmp(yAbs)
   425  }
   426  
   427  // bigIntAbsValue returns a big.Int containing the absolute value of b.
   428  // If b is already a non-negative number, it is returned without any changes or copies.
   429  func bigIntAbsValue(b *big.Int) *big.Int {
   430  	if b.Sign() >= 0 {
   431  		return b // already positive
   432  	}
   433  	return new(big.Int).Abs(b)
   434  }
   435
View as plain text