1package v1 2 3/** 4 * Copyright 2015 Paul Querna, Klaus Post 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 */ 19 20/* Most of this file are on Go stdlib's strconv/ftoa.go */ 21// Copyright 2009 The Go Authors. All rights reserved. 22// Use of this source code is governed by a BSD-style 23// license that can be found in the LICENSE file. 24 25import "math" 26 27// TODO: move elsewhere? 28type floatInfo struct { 29 mantbits uint 30 expbits uint 31 bias int 32} 33 34var optimize = true // can change for testing 35 36var float32info = floatInfo{23, 8, -127} 37var float64info = floatInfo{52, 11, -1023} 38 39// AppendFloat appends the string form of the floating-point number f, 40// as generated by FormatFloat 41func AppendFloat(dst EncodingBuffer, val float64, fmt byte, prec, bitSize int) { 42 var bits uint64 43 var flt *floatInfo 44 switch bitSize { 45 case 32: 46 bits = uint64(math.Float32bits(float32(val))) 47 flt = &float32info 48 case 64: 49 bits = math.Float64bits(val) 50 flt = &float64info 51 default: 52 panic("strconv: illegal AppendFloat/FormatFloat bitSize") 53 } 54 55 neg := bits>>(flt.expbits+flt.mantbits) != 0 56 exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1) 57 mant := bits & (uint64(1)<<flt.mantbits - 1) 58 59 switch exp { 60 case 1<<flt.expbits - 1: 61 // Inf, NaN 62 var s string 63 switch { 64 case mant != 0: 65 s = "NaN" 66 case neg: 67 s = "-Inf" 68 default: 69 s = "+Inf" 70 } 71 dst.WriteString(s) 72 return 73 74 case 0: 75 // denormalized 76 exp++ 77 78 default: 79 // add implicit top bit 80 mant |= uint64(1) << flt.mantbits 81 } 82 exp += flt.bias 83 84 // Pick off easy binary format. 85 if fmt == 'b' { 86 fmtB(dst, neg, mant, exp, flt) 87 return 88 } 89 90 if !optimize { 91 bigFtoa(dst, prec, fmt, neg, mant, exp, flt) 92 return 93 } 94 95 var digs decimalSlice 96 ok := false 97 // Negative precision means "only as much as needed to be exact." 98 shortest := prec < 0 99 if shortest { 100 // Try Grisu3 algorithm. 101 f := new(extFloat) 102 lower, upper := f.AssignComputeBounds(mant, exp, neg, flt) 103 var buf [32]byte 104 digs.d = buf[:] 105 ok = f.ShortestDecimal(&digs, &lower, &upper) 106 if !ok { 107 bigFtoa(dst, prec, fmt, neg, mant, exp, flt) 108 return 109 } 110 // Precision for shortest representation mode. 111 switch fmt { 112 case 'e', 'E': 113 prec = max(digs.nd-1, 0) 114 case 'f': 115 prec = max(digs.nd-digs.dp, 0) 116 case 'g', 'G': 117 prec = digs.nd 118 } 119 } else if fmt != 'f' { 120 // Fixed number of digits. 121 digits := prec 122 switch fmt { 123 case 'e', 'E': 124 digits++ 125 case 'g', 'G': 126 if prec == 0 { 127 prec = 1 128 } 129 digits = prec 130 } 131 if digits <= 15 { 132 // try fast algorithm when the number of digits is reasonable. 133 var buf [24]byte 134 digs.d = buf[:] 135 f := extFloat{mant, exp - int(flt.mantbits), neg} 136 ok = f.FixedDecimal(&digs, digits) 137 } 138 } 139 if !ok { 140 bigFtoa(dst, prec, fmt, neg, mant, exp, flt) 141 return 142 } 143 formatDigits(dst, shortest, neg, digs, prec, fmt) 144 return 145} 146 147// bigFtoa uses multiprecision computations to format a float. 148func bigFtoa(dst EncodingBuffer, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) { 149 d := new(decimal) 150 d.Assign(mant) 151 d.Shift(exp - int(flt.mantbits)) 152 var digs decimalSlice 153 shortest := prec < 0 154 if shortest { 155 roundShortest(d, mant, exp, flt) 156 digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp} 157 // Precision for shortest representation mode. 158 switch fmt { 159 case 'e', 'E': 160 prec = digs.nd - 1 161 case 'f': 162 prec = max(digs.nd-digs.dp, 0) 163 case 'g', 'G': 164 prec = digs.nd 165 } 166 } else { 167 // Round appropriately. 168 switch fmt { 169 case 'e', 'E': 170 d.Round(prec + 1) 171 case 'f': 172 d.Round(d.dp + prec) 173 case 'g', 'G': 174 if prec == 0 { 175 prec = 1 176 } 177 d.Round(prec) 178 } 179 digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp} 180 } 181 formatDigits(dst, shortest, neg, digs, prec, fmt) 182 return 183} 184 185func formatDigits(dst EncodingBuffer, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) { 186 switch fmt { 187 case 'e', 'E': 188 fmtE(dst, neg, digs, prec, fmt) 189 return 190 case 'f': 191 fmtF(dst, neg, digs, prec) 192 return 193 case 'g', 'G': 194 // trailing fractional zeros in 'e' form will be trimmed. 195 eprec := prec 196 if eprec > digs.nd && digs.nd >= digs.dp { 197 eprec = digs.nd 198 } 199 // %e is used if the exponent from the conversion 200 // is less than -4 or greater than or equal to the precision. 201 // if precision was the shortest possible, use precision 6 for this decision. 202 if shortest { 203 eprec = 6 204 } 205 exp := digs.dp - 1 206 if exp < -4 || exp >= eprec { 207 if prec > digs.nd { 208 prec = digs.nd 209 } 210 fmtE(dst, neg, digs, prec-1, fmt+'e'-'g') 211 return 212 } 213 if prec > digs.dp { 214 prec = digs.nd 215 } 216 fmtF(dst, neg, digs, max(prec-digs.dp, 0)) 217 return 218 } 219 220 // unknown format 221 dst.Write([]byte{'%', fmt}) 222 return 223} 224 225// Round d (= mant * 2^exp) to the shortest number of digits 226// that will let the original floating point value be precisely 227// reconstructed. Size is original floating point size (64 or 32). 228func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) { 229 // If mantissa is zero, the number is zero; stop now. 230 if mant == 0 { 231 d.nd = 0 232 return 233 } 234 235 // Compute upper and lower such that any decimal number 236 // between upper and lower (possibly inclusive) 237 // will round to the original floating point number. 238 239 // We may see at once that the number is already shortest. 240 // 241 // Suppose d is not denormal, so that 2^exp <= d < 10^dp. 242 // The closest shorter number is at least 10^(dp-nd) away. 243 // The lower/upper bounds computed below are at distance 244 // at most 2^(exp-mantbits). 245 // 246 // So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits), 247 // or equivalently log2(10)*(dp-nd) > exp-mantbits. 248 // It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32). 249 minexp := flt.bias + 1 // minimum possible exponent 250 if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) { 251 // The number is already shortest. 252 return 253 } 254 255 // d = mant << (exp - mantbits) 256 // Next highest floating point number is mant+1 << exp-mantbits. 257 // Our upper bound is halfway between, mant*2+1 << exp-mantbits-1. 258 upper := new(decimal) 259 upper.Assign(mant*2 + 1) 260 upper.Shift(exp - int(flt.mantbits) - 1) 261 262 // d = mant << (exp - mantbits) 263 // Next lowest floating point number is mant-1 << exp-mantbits, 264 // unless mant-1 drops the significant bit and exp is not the minimum exp, 265 // in which case the next lowest is mant*2-1 << exp-mantbits-1. 266 // Either way, call it mantlo << explo-mantbits. 267 // Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1. 268 var mantlo uint64 269 var explo int 270 if mant > 1<<flt.mantbits || exp == minexp { 271 mantlo = mant - 1 272 explo = exp 273 } else { 274 mantlo = mant*2 - 1 275 explo = exp - 1 276 } 277 lower := new(decimal) 278 lower.Assign(mantlo*2 + 1) 279 lower.Shift(explo - int(flt.mantbits) - 1) 280 281 // The upper and lower bounds are possible outputs only if 282 // the original mantissa is even, so that IEEE round-to-even 283 // would round to the original mantissa and not the neighbors. 284 inclusive := mant%2 == 0 285 286 // Now we can figure out the minimum number of digits required. 287 // Walk along until d has distinguished itself from upper and lower. 288 for i := 0; i < d.nd; i++ { 289 var l, m, u byte // lower, middle, upper digits 290 if i < lower.nd { 291 l = lower.d[i] 292 } else { 293 l = '0' 294 } 295 m = d.d[i] 296 if i < upper.nd { 297 u = upper.d[i] 298 } else { 299 u = '0' 300 } 301 302 // Okay to round down (truncate) if lower has a different digit 303 // or if lower is inclusive and is exactly the result of rounding down. 304 okdown := l != m || (inclusive && l == m && i+1 == lower.nd) 305 306 // Okay to round up if upper has a different digit and 307 // either upper is inclusive or upper is bigger than the result of rounding up. 308 okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd) 309 310 // If it's okay to do either, then round to the nearest one. 311 // If it's okay to do only one, do it. 312 switch { 313 case okdown && okup: 314 d.Round(i + 1) 315 return 316 case okdown: 317 d.RoundDown(i + 1) 318 return 319 case okup: 320 d.RoundUp(i + 1) 321 return 322 } 323 } 324} 325 326type decimalSlice struct { 327 d []byte 328 nd, dp int 329 neg bool 330} 331 332// %e: -d.ddddde±dd 333func fmtE(dst EncodingBuffer, neg bool, d decimalSlice, prec int, fmt byte) { 334 // sign 335 if neg { 336 dst.WriteByte('-') 337 } 338 339 // first digit 340 ch := byte('0') 341 if d.nd != 0 { 342 ch = d.d[0] 343 } 344 dst.WriteByte(ch) 345 346 // .moredigits 347 if prec > 0 { 348 dst.WriteByte('.') 349 i := 1 350 m := min(d.nd, prec+1) 351 if i < m { 352 dst.Write(d.d[i:m]) 353 i = m 354 } 355 for i <= prec { 356 dst.WriteByte('0') 357 i++ 358 } 359 } 360 361 // e± 362 dst.WriteByte(fmt) 363 exp := d.dp - 1 364 if d.nd == 0 { // special case: 0 has exponent 0 365 exp = 0 366 } 367 if exp < 0 { 368 ch = '-' 369 exp = -exp 370 } else { 371 ch = '+' 372 } 373 dst.WriteByte(ch) 374 375 // dd or ddd 376 switch { 377 case exp < 10: 378 dst.WriteByte('0') 379 dst.WriteByte(byte(exp) + '0') 380 case exp < 100: 381 dst.WriteByte(byte(exp/10) + '0') 382 dst.WriteByte(byte(exp%10) + '0') 383 default: 384 dst.WriteByte(byte(exp/100) + '0') 385 dst.WriteByte(byte(exp/10)%10 + '0') 386 dst.WriteByte(byte(exp%10) + '0') 387 } 388 389 return 390} 391 392// %f: -ddddddd.ddddd 393func fmtF(dst EncodingBuffer, neg bool, d decimalSlice, prec int) { 394 // sign 395 if neg { 396 dst.WriteByte('-') 397 } 398 399 // integer, padded with zeros as needed. 400 if d.dp > 0 { 401 m := min(d.nd, d.dp) 402 dst.Write(d.d[:m]) 403 for ; m < d.dp; m++ { 404 dst.WriteByte('0') 405 } 406 } else { 407 dst.WriteByte('0') 408 } 409 410 // fraction 411 if prec > 0 { 412 dst.WriteByte('.') 413 for i := 0; i < prec; i++ { 414 ch := byte('0') 415 if j := d.dp + i; 0 <= j && j < d.nd { 416 ch = d.d[j] 417 } 418 dst.WriteByte(ch) 419 } 420 } 421 422 return 423} 424 425// %b: -ddddddddp±ddd 426func fmtB(dst EncodingBuffer, neg bool, mant uint64, exp int, flt *floatInfo) { 427 // sign 428 if neg { 429 dst.WriteByte('-') 430 } 431 432 // mantissa 433 formatBits(dst, mant, 10, false) 434 435 // p 436 dst.WriteByte('p') 437 438 // ±exponent 439 exp -= int(flt.mantbits) 440 if exp >= 0 { 441 dst.WriteByte('+') 442 } 443 formatBits(dst, uint64(exp), 10, exp < 0) 444 445 return 446} 447 448func min(a, b int) int { 449 if a < b { 450 return a 451 } 452 return b 453} 454 455func max(a, b int) int { 456 if a > b { 457 return a 458 } 459 return b 460} 461 462// formatBits computes the string representation of u in the given base. 463// If neg is set, u is treated as negative int64 value. 464func formatBits(dst EncodingBuffer, u uint64, base int, neg bool) { 465 if base < 2 || base > len(digits) { 466 panic("strconv: illegal AppendInt/FormatInt base") 467 } 468 // 2 <= base && base <= len(digits) 469 470 var a [64 + 1]byte // +1 for sign of 64bit value in base 2 471 i := len(a) 472 473 if neg { 474 u = -u 475 } 476 477 // convert bits 478 if base == 10 { 479 // common case: use constants for / because 480 // the compiler can optimize it into a multiply+shift 481 482 if ^uintptr(0)>>32 == 0 { 483 for u > uint64(^uintptr(0)) { 484 q := u / 1e9 485 us := uintptr(u - q*1e9) // us % 1e9 fits into a uintptr 486 for j := 9; j > 0; j-- { 487 i-- 488 qs := us / 10 489 a[i] = byte(us - qs*10 + '0') 490 us = qs 491 } 492 u = q 493 } 494 } 495 496 // u guaranteed to fit into a uintptr 497 us := uintptr(u) 498 for us >= 10 { 499 i-- 500 q := us / 10 501 a[i] = byte(us - q*10 + '0') 502 us = q 503 } 504 // u < 10 505 i-- 506 a[i] = byte(us + '0') 507 508 } else if s := shifts[base]; s > 0 { 509 // base is power of 2: use shifts and masks instead of / and % 510 b := uint64(base) 511 m := uintptr(b) - 1 // == 1<<s - 1 512 for u >= b { 513 i-- 514 a[i] = digits[uintptr(u)&m] 515 u >>= s 516 } 517 // u < base 518 i-- 519 a[i] = digits[uintptr(u)] 520 521 } else { 522 // general case 523 b := uint64(base) 524 for u >= b { 525 i-- 526 q := u / b 527 a[i] = digits[uintptr(u-q*b)] 528 u = q 529 } 530 // u < base 531 i-- 532 a[i] = digits[uintptr(u)] 533 } 534 535 // add sign, if any 536 if neg { 537 i-- 538 a[i] = '-' 539 } 540 541 dst.Write(a[i:]) 542} 543