Don Newton | 379ae25 | 2019-04-01 12:17:06 -0400 | [diff] [blame^] | 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 | "fmt" |
| 14 | "strconv" |
| 15 | "strings" |
| 16 | ) |
| 17 | |
| 18 | // Decimal128 holds decimal128 BSON values. |
| 19 | type Decimal128 struct { |
| 20 | h, l uint64 |
| 21 | } |
| 22 | |
| 23 | // NewDecimal128 creates a Decimal128 using the provide high and low uint64s. |
| 24 | func NewDecimal128(h, l uint64) Decimal128 { |
| 25 | return Decimal128{h: h, l: l} |
| 26 | } |
| 27 | |
| 28 | // GetBytes returns the underlying bytes of the BSON decimal value as two uint16 values. The first |
| 29 | // contains the most first 8 bytes of the value and the second contains the latter. |
| 30 | func (d Decimal128) GetBytes() (uint64, uint64) { |
| 31 | return d.h, d.l |
| 32 | } |
| 33 | |
| 34 | // String returns a string representation of the decimal value. |
| 35 | func (d Decimal128) String() string { |
| 36 | var pos int // positive sign |
| 37 | var e int // exponent |
| 38 | var h, l uint64 // significand high/low |
| 39 | |
| 40 | if d.h>>63&1 == 0 { |
| 41 | pos = 1 |
| 42 | } |
| 43 | |
| 44 | switch d.h >> 58 & (1<<5 - 1) { |
| 45 | case 0x1F: |
| 46 | return "NaN" |
| 47 | case 0x1E: |
| 48 | return "-Infinity"[pos:] |
| 49 | } |
| 50 | |
| 51 | l = d.l |
| 52 | if d.h>>61&3 == 3 { |
| 53 | // Bits: 1*sign 2*ignored 14*exponent 111*significand. |
| 54 | // Implicit 0b100 prefix in significand. |
| 55 | e = int(d.h>>47&(1<<14-1)) - 6176 |
| 56 | //h = 4<<47 | d.h&(1<<47-1) |
| 57 | // Spec says all of these values are out of range. |
| 58 | h, l = 0, 0 |
| 59 | } else { |
| 60 | // Bits: 1*sign 14*exponent 113*significand |
| 61 | e = int(d.h>>49&(1<<14-1)) - 6176 |
| 62 | h = d.h & (1<<49 - 1) |
| 63 | } |
| 64 | |
| 65 | // Would be handled by the logic below, but that's trivial and common. |
| 66 | if h == 0 && l == 0 && e == 0 { |
| 67 | return "-0"[pos:] |
| 68 | } |
| 69 | |
| 70 | var repr [48]byte // Loop 5 times over 9 digits plus dot, negative sign, and leading zero. |
| 71 | var last = len(repr) |
| 72 | var i = len(repr) |
| 73 | var dot = len(repr) + e |
| 74 | var rem uint32 |
| 75 | Loop: |
| 76 | for d9 := 0; d9 < 5; d9++ { |
| 77 | h, l, rem = divmod(h, l, 1e9) |
| 78 | for d1 := 0; d1 < 9; d1++ { |
| 79 | // Handle "-0.0", "0.00123400", "-1.00E-6", "1.050E+3", etc. |
| 80 | if i < len(repr) && (dot == i || l == 0 && h == 0 && rem > 0 && rem < 10 && (dot < i-6 || e > 0)) { |
| 81 | e += len(repr) - i |
| 82 | i-- |
| 83 | repr[i] = '.' |
| 84 | last = i - 1 |
| 85 | dot = len(repr) // Unmark. |
| 86 | } |
| 87 | c := '0' + byte(rem%10) |
| 88 | rem /= 10 |
| 89 | i-- |
| 90 | repr[i] = c |
| 91 | // Handle "0E+3", "1E+3", etc. |
| 92 | if l == 0 && h == 0 && rem == 0 && i == len(repr)-1 && (dot < i-5 || e > 0) { |
| 93 | last = i |
| 94 | break Loop |
| 95 | } |
| 96 | if c != '0' { |
| 97 | last = i |
| 98 | } |
| 99 | // Break early. Works without it, but why. |
| 100 | if dot > i && l == 0 && h == 0 && rem == 0 { |
| 101 | break Loop |
| 102 | } |
| 103 | } |
| 104 | } |
| 105 | repr[last-1] = '-' |
| 106 | last-- |
| 107 | |
| 108 | if e > 0 { |
| 109 | return string(repr[last+pos:]) + "E+" + strconv.Itoa(e) |
| 110 | } |
| 111 | if e < 0 { |
| 112 | return string(repr[last+pos:]) + "E" + strconv.Itoa(e) |
| 113 | } |
| 114 | return string(repr[last+pos:]) |
| 115 | } |
| 116 | |
| 117 | func divmod(h, l uint64, div uint32) (qh, ql uint64, rem uint32) { |
| 118 | div64 := uint64(div) |
| 119 | a := h >> 32 |
| 120 | aq := a / div64 |
| 121 | ar := a % div64 |
| 122 | b := ar<<32 + h&(1<<32-1) |
| 123 | bq := b / div64 |
| 124 | br := b % div64 |
| 125 | c := br<<32 + l>>32 |
| 126 | cq := c / div64 |
| 127 | cr := c % div64 |
| 128 | d := cr<<32 + l&(1<<32-1) |
| 129 | dq := d / div64 |
| 130 | dr := d % div64 |
| 131 | return (aq<<32 | bq), (cq<<32 | dq), uint32(dr) |
| 132 | } |
| 133 | |
| 134 | var dNaN = Decimal128{0x1F << 58, 0} |
| 135 | var dPosInf = Decimal128{0x1E << 58, 0} |
| 136 | var dNegInf = Decimal128{0x3E << 58, 0} |
| 137 | |
| 138 | func dErr(s string) (Decimal128, error) { |
| 139 | return dNaN, fmt.Errorf("cannot parse %q as a decimal128", s) |
| 140 | } |
| 141 | |
| 142 | //ParseDecimal128 takes the given string and attempts to parse it into a valid |
| 143 | // Decimal128 value. |
| 144 | func ParseDecimal128(s string) (Decimal128, error) { |
| 145 | orig := s |
| 146 | if s == "" { |
| 147 | return dErr(orig) |
| 148 | } |
| 149 | neg := s[0] == '-' |
| 150 | if neg || s[0] == '+' { |
| 151 | s = s[1:] |
| 152 | } |
| 153 | |
| 154 | if (len(s) == 3 || len(s) == 8) && (s[0] == 'N' || s[0] == 'n' || s[0] == 'I' || s[0] == 'i') { |
| 155 | if s == "NaN" || s == "nan" || strings.EqualFold(s, "nan") { |
| 156 | return dNaN, nil |
| 157 | } |
| 158 | if s == "Inf" || s == "inf" || strings.EqualFold(s, "inf") || strings.EqualFold(s, "infinity") { |
| 159 | if neg { |
| 160 | return dNegInf, nil |
| 161 | } |
| 162 | return dPosInf, nil |
| 163 | } |
| 164 | return dErr(orig) |
| 165 | } |
| 166 | |
| 167 | var h, l uint64 |
| 168 | var e int |
| 169 | |
| 170 | var add, ovr uint32 |
| 171 | var mul uint32 = 1 |
| 172 | var dot = -1 |
| 173 | var digits = 0 |
| 174 | var i = 0 |
| 175 | for i < len(s) { |
| 176 | c := s[i] |
| 177 | if mul == 1e9 { |
| 178 | h, l, ovr = muladd(h, l, mul, add) |
| 179 | mul, add = 1, 0 |
| 180 | if ovr > 0 || h&((1<<15-1)<<49) > 0 { |
| 181 | return dErr(orig) |
| 182 | } |
| 183 | } |
| 184 | if c >= '0' && c <= '9' { |
| 185 | i++ |
| 186 | if c > '0' || digits > 0 { |
| 187 | digits++ |
| 188 | } |
| 189 | if digits > 34 { |
| 190 | if c == '0' { |
| 191 | // Exact rounding. |
| 192 | e++ |
| 193 | continue |
| 194 | } |
| 195 | return dErr(orig) |
| 196 | } |
| 197 | mul *= 10 |
| 198 | add *= 10 |
| 199 | add += uint32(c - '0') |
| 200 | continue |
| 201 | } |
| 202 | if c == '.' { |
| 203 | i++ |
| 204 | if dot >= 0 || i == 1 && len(s) == 1 { |
| 205 | return dErr(orig) |
| 206 | } |
| 207 | if i == len(s) { |
| 208 | break |
| 209 | } |
| 210 | if s[i] < '0' || s[i] > '9' || e > 0 { |
| 211 | return dErr(orig) |
| 212 | } |
| 213 | dot = i |
| 214 | continue |
| 215 | } |
| 216 | break |
| 217 | } |
| 218 | if i == 0 { |
| 219 | return dErr(orig) |
| 220 | } |
| 221 | if mul > 1 { |
| 222 | h, l, ovr = muladd(h, l, mul, add) |
| 223 | if ovr > 0 || h&((1<<15-1)<<49) > 0 { |
| 224 | return dErr(orig) |
| 225 | } |
| 226 | } |
| 227 | if dot >= 0 { |
| 228 | e += dot - i |
| 229 | } |
| 230 | if i+1 < len(s) && (s[i] == 'E' || s[i] == 'e') { |
| 231 | i++ |
| 232 | eneg := s[i] == '-' |
| 233 | if eneg || s[i] == '+' { |
| 234 | i++ |
| 235 | if i == len(s) { |
| 236 | return dErr(orig) |
| 237 | } |
| 238 | } |
| 239 | n := 0 |
| 240 | for i < len(s) && n < 1e4 { |
| 241 | c := s[i] |
| 242 | i++ |
| 243 | if c < '0' || c > '9' { |
| 244 | return dErr(orig) |
| 245 | } |
| 246 | n *= 10 |
| 247 | n += int(c - '0') |
| 248 | } |
| 249 | if eneg { |
| 250 | n = -n |
| 251 | } |
| 252 | e += n |
| 253 | for e < -6176 { |
| 254 | // Subnormal. |
| 255 | var div uint32 = 1 |
| 256 | for div < 1e9 && e < -6176 { |
| 257 | div *= 10 |
| 258 | e++ |
| 259 | } |
| 260 | var rem uint32 |
| 261 | h, l, rem = divmod(h, l, div) |
| 262 | if rem > 0 { |
| 263 | return dErr(orig) |
| 264 | } |
| 265 | } |
| 266 | for e > 6111 { |
| 267 | // Clamped. |
| 268 | var mul uint32 = 1 |
| 269 | for mul < 1e9 && e > 6111 { |
| 270 | mul *= 10 |
| 271 | e-- |
| 272 | } |
| 273 | h, l, ovr = muladd(h, l, mul, 0) |
| 274 | if ovr > 0 || h&((1<<15-1)<<49) > 0 { |
| 275 | return dErr(orig) |
| 276 | } |
| 277 | } |
| 278 | if e < -6176 || e > 6111 { |
| 279 | return dErr(orig) |
| 280 | } |
| 281 | } |
| 282 | |
| 283 | if i < len(s) { |
| 284 | return dErr(orig) |
| 285 | } |
| 286 | |
| 287 | h |= uint64(e+6176) & uint64(1<<14-1) << 49 |
| 288 | if neg { |
| 289 | h |= 1 << 63 |
| 290 | } |
| 291 | return Decimal128{h, l}, nil |
| 292 | } |
| 293 | |
| 294 | func muladd(h, l uint64, mul uint32, add uint32) (resh, resl uint64, overflow uint32) { |
| 295 | mul64 := uint64(mul) |
| 296 | a := mul64 * (l & (1<<32 - 1)) |
| 297 | b := a>>32 + mul64*(l>>32) |
| 298 | c := b>>32 + mul64*(h&(1<<32-1)) |
| 299 | d := c>>32 + mul64*(h>>32) |
| 300 | |
| 301 | a = a&(1<<32-1) + uint64(add) |
| 302 | b = b&(1<<32-1) + a>>32 |
| 303 | c = c&(1<<32-1) + b>>32 |
| 304 | d = d&(1<<32-1) + c>>32 |
| 305 | |
| 306 | return (d<<32 | c&(1<<32-1)), (b<<32 | a&(1<<32-1)), uint32(d >> 32) |
| 307 | } |