ftoa.mx raw
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // Binary to decimal floating point conversion.
6 // Algorithm:
7 // 1) store mantissa in multiprecision decimal
8 // 2) shift decimal by exponent
9 // 3) read digits out & format
10
11 package strconv
12
13 import "math"
14
15 // TODO: move elsewhere?
16 type floatInfo struct {
17 mantbits uint
18 expbits uint
19 bias int
20 }
21
22 var float32info = floatInfo{23, 8, -127}
23 var float64info = floatInfo{52, 11, -1023}
24
25 // FormatFloat converts the floating-point number f to a string,
26 // according to the format fmt and precision prec. It rounds the
27 // result assuming that the original was obtained from a floating-point
28 // value of bitSize bits (32 for float32, 64 for float64).
29 //
30 // The format fmt is one of
31 // - 'b' (-ddddp±ddd, a binary exponent),
32 // - 'e' (-d.dddde±dd, a decimal exponent),
33 // - 'E' (-d.ddddE±dd, a decimal exponent),
34 // - 'f' (-ddd.dddd, no exponent),
35 // - 'g' ('e' for large exponents, 'f' otherwise),
36 // - 'G' ('E' for large exponents, 'f' otherwise),
37 // - 'x' (-0xd.ddddp±ddd, a hexadecimal fraction and binary exponent), or
38 // - 'X' (-0Xd.ddddP±ddd, a hexadecimal fraction and binary exponent).
39 //
40 // The precision prec controls the number of digits (excluding the exponent)
41 // printed by the 'e', 'E', 'f', 'g', 'G', 'x', and 'X' formats.
42 // For 'e', 'E', 'f', 'x', and 'X', it is the number of digits after the decimal point.
43 // For 'g' and 'G' it is the maximum number of significant digits (trailing
44 // zeros are removed).
45 // The special precision -1 uses the smallest number of digits
46 // necessary such that ParseFloat will return f exactly.
47 // The exponent is written as a decimal integer;
48 // for all formats other than 'b', it will be at least two digits.
49 func FormatFloat(f float64, fmt byte, prec, bitSize int) []byte {
50 return []byte(genericFtoa([]byte{:0:max(prec+4, 24)}, f, fmt, prec, bitSize))
51 }
52
53 // AppendFloat appends the string form of the floating-point number f,
54 // as generated by [FormatFloat], to dst and returns the extended buffer.
55 func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
56 return genericFtoa(dst, f, fmt, prec, bitSize)
57 }
58
59 func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
60 var bits uint64
61 var flt *floatInfo
62 switch bitSize {
63 case 32:
64 bits = uint64(math.Float32bits(float32(val)))
65 flt = &float32info
66 case 64:
67 bits = math.Float64bits(val)
68 flt = &float64info
69 default:
70 panic("strconv: illegal AppendFloat/FormatFloat bitSize")
71 }
72
73 neg := bits>>(flt.expbits+flt.mantbits) != 0
74 exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
75 mant := bits & (uint64(1)<<flt.mantbits - 1)
76
77 switch exp {
78 case 1<<flt.expbits - 1:
79 // Inf, NaN
80 var s []byte
81 switch {
82 case mant != 0:
83 s = "NaN"
84 case neg:
85 s = "-Inf"
86 default:
87 s = "+Inf"
88 }
89 return append(dst, s...)
90
91 case 0:
92 // denormalized
93 exp++
94
95 default:
96 // add implicit top bit
97 mant |= uint64(1) << flt.mantbits
98 }
99 exp += flt.bias
100
101 // Pick off easy binary, hex formats.
102 if fmt == 'b' {
103 return fmtB(dst, neg, mant, exp, flt)
104 }
105 if fmt == 'x' || fmt == 'X' {
106 return fmtX(dst, prec, fmt, neg, mant, exp, flt)
107 }
108
109 if !optimize {
110 return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
111 }
112
113 var digs decimalSlice
114 ok := false
115 // Negative precision means "only as much as needed to be exact."
116 shortest := prec < 0
117 if shortest {
118 // Use Ryu algorithm.
119 var buf [32]byte
120 digs.d = buf[:]
121 ryuFtoaShortest(&digs, mant, exp-int(flt.mantbits), flt)
122 ok = true
123 // Precision for shortest representation mode.
124 switch fmt {
125 case 'e', 'E':
126 prec = max(digs.nd-1, 0)
127 case 'f':
128 prec = max(digs.nd-digs.dp, 0)
129 case 'g', 'G':
130 prec = digs.nd
131 }
132 } else if fmt != 'f' {
133 // Fixed number of digits.
134 digits := prec
135 switch fmt {
136 case 'e', 'E':
137 digits++
138 case 'g', 'G':
139 if prec == 0 {
140 prec = 1
141 }
142 digits = prec
143 default:
144 // Invalid mode.
145 digits = 1
146 }
147 var buf [24]byte
148 if bitSize == 32 && digits <= 9 {
149 digs.d = buf[:]
150 ryuFtoaFixed32(&digs, uint32(mant), exp-int(flt.mantbits), digits)
151 ok = true
152 } else if digits <= 18 {
153 digs.d = buf[:]
154 ryuFtoaFixed64(&digs, mant, exp-int(flt.mantbits), digits)
155 ok = true
156 }
157 }
158 if !ok {
159 return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
160 }
161 return formatDigits(dst, shortest, neg, digs, prec, fmt)
162 }
163
164 // bigFtoa uses multiprecision computations to format a float.
165 func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
166 d := &decimal{}
167 d.Assign(mant)
168 d.Shift(exp - int(flt.mantbits))
169 var digs decimalSlice
170 shortest := prec < 0
171 if shortest {
172 roundShortest(d, mant, exp, flt)
173 digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
174 // Precision for shortest representation mode.
175 switch fmt {
176 case 'e', 'E':
177 prec = digs.nd - 1
178 case 'f':
179 prec = max(digs.nd-digs.dp, 0)
180 case 'g', 'G':
181 prec = digs.nd
182 }
183 } else {
184 // Round appropriately.
185 switch fmt {
186 case 'e', 'E':
187 d.Round(prec + 1)
188 case 'f':
189 d.Round(d.dp + prec)
190 case 'g', 'G':
191 if prec == 0 {
192 prec = 1
193 }
194 d.Round(prec)
195 }
196 digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
197 }
198 return formatDigits(dst, shortest, neg, digs, prec, fmt)
199 }
200
201 func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
202 switch fmt {
203 case 'e', 'E':
204 return fmtE(dst, neg, digs, prec, fmt)
205 case 'f':
206 return fmtF(dst, neg, digs, prec)
207 case 'g', 'G':
208 // trailing fractional zeros in 'e' form will be trimmed.
209 eprec := prec
210 if eprec > digs.nd && digs.nd >= digs.dp {
211 eprec = digs.nd
212 }
213 // %e is used if the exponent from the conversion
214 // is less than -4 or greater than or equal to the precision.
215 // if precision was the shortest possible, use precision 6 for this decision.
216 if shortest {
217 eprec = 6
218 }
219 exp := digs.dp - 1
220 if exp < -4 || exp >= eprec {
221 if prec > digs.nd {
222 prec = digs.nd
223 }
224 return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
225 }
226 if prec > digs.dp {
227 prec = digs.nd
228 }
229 return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
230 }
231
232 // unknown format
233 return append(dst, '%', fmt)
234 }
235
236 // roundShortest rounds d (= mant * 2^exp) to the shortest number of digits
237 // that will let the original floating point value be precisely reconstructed.
238 func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
239 // If mantissa is zero, the number is zero; stop now.
240 if mant == 0 {
241 d.nd = 0
242 return
243 }
244
245 // Compute upper and lower such that any decimal number
246 // between upper and lower (possibly inclusive)
247 // will round to the original floating point number.
248
249 // We may see at once that the number is already shortest.
250 //
251 // Suppose d is not denormal, so that 2^exp <= d < 10^dp.
252 // The closest shorter number is at least 10^(dp-nd) away.
253 // The lower/upper bounds computed below are at distance
254 // at most 2^(exp-mantbits).
255 //
256 // So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
257 // or equivalently log2(10)*(dp-nd) > exp-mantbits.
258 // It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
259 minexp := flt.bias + 1 // minimum possible exponent
260 if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
261 // The number is already shortest.
262 return
263 }
264
265 // d = mant << (exp - mantbits)
266 // Next highest floating point number is mant+1 << exp-mantbits.
267 // Our upper bound is halfway between, mant*2+1 << exp-mantbits-1.
268 upper := &decimal{}
269 upper.Assign(mant*2 + 1)
270 upper.Shift(exp - int(flt.mantbits) - 1)
271
272 // d = mant << (exp - mantbits)
273 // Next lowest floating point number is mant-1 << exp-mantbits,
274 // unless mant-1 drops the significant bit and exp is not the minimum exp,
275 // in which case the next lowest is mant*2-1 << exp-mantbits-1.
276 // Either way, call it mantlo << explo-mantbits.
277 // Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1.
278 var mantlo uint64
279 var explo int
280 if mant > 1<<flt.mantbits || exp == minexp {
281 mantlo = mant - 1
282 explo = exp
283 } else {
284 mantlo = mant*2 - 1
285 explo = exp - 1
286 }
287 lower := &decimal{}
288 lower.Assign(mantlo*2 + 1)
289 lower.Shift(explo - int(flt.mantbits) - 1)
290
291 // The upper and lower bounds are possible outputs only if
292 // the original mantissa is even, so that IEEE round-to-even
293 // would round to the original mantissa and not the neighbors.
294 inclusive := mant%2 == 0
295
296 // As we walk the digits we want to know whether rounding up would fall
297 // within the upper bound. This is tracked by upperdelta:
298 //
299 // If upperdelta == 0, the digits of d and upper are the same so far.
300 //
301 // If upperdelta == 1, we saw a difference of 1 between d and upper on a
302 // previous digit and subsequently only 9s for d and 0s for upper.
303 // (Thus rounding up may fall outside the bound, if it is exclusive.)
304 //
305 // If upperdelta == 2, then the difference is greater than 1
306 // and we know that rounding up falls within the bound.
307 var upperdelta uint8
308
309 // Now we can figure out the minimum number of digits required.
310 // Walk along until d has distinguished itself from upper and lower.
311 for ui := 0; ; ui++ {
312 // lower, d, and upper may have the decimal points at different
313 // places. In this case upper is the longest, so we iterate from
314 // ui==0 and start li and mi at (possibly) -1.
315 mi := ui - upper.dp + d.dp
316 if mi >= d.nd {
317 break
318 }
319 li := ui - upper.dp + lower.dp
320 l := byte('0') // lower digit
321 if li >= 0 && li < lower.nd {
322 l = lower.d[li]
323 }
324 m := byte('0') // middle digit
325 if mi >= 0 {
326 m = d.d[mi]
327 }
328 u := byte('0') // upper digit
329 if ui < upper.nd {
330 u = upper.d[ui]
331 }
332
333 // Okay to round down (truncate) if lower has a different digit
334 // or if lower is inclusive and is exactly the result of rounding
335 // down (i.e., and we have reached the final digit of lower).
336 okdown := l != m || inclusive && li+1 == lower.nd
337
338 switch {
339 case upperdelta == 0 && m+1 < u:
340 // Example:
341 // m = 12345xxx
342 // u = 12347xxx
343 upperdelta = 2
344 case upperdelta == 0 && m != u:
345 // Example:
346 // m = 12345xxx
347 // u = 12346xxx
348 upperdelta = 1
349 case upperdelta == 1 && (m != '9' || u != '0'):
350 // Example:
351 // m = 1234598x
352 // u = 1234600x
353 upperdelta = 2
354 }
355 // Okay to round up if upper has a different digit and either upper
356 // is inclusive or upper is bigger than the result of rounding up.
357 okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd)
358
359 // If it's okay to do either, then round to the nearest one.
360 // If it's okay to do only one, do it.
361 switch {
362 case okdown && okup:
363 d.Round(mi + 1)
364 return
365 case okdown:
366 d.RoundDown(mi + 1)
367 return
368 case okup:
369 d.RoundUp(mi + 1)
370 return
371 }
372 }
373 }
374
375 type decimalSlice struct {
376 d []byte
377 nd, dp int
378 }
379
380 // %e: -d.ddddde±dd
381 func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
382 // sign
383 if neg {
384 dst = append(dst, '-')
385 }
386
387 // first digit
388 ch := byte('0')
389 if d.nd != 0 {
390 ch = d.d[0]
391 }
392 dst = append(dst, ch)
393
394 // .moredigits
395 if prec > 0 {
396 dst = append(dst, '.')
397 i := 1
398 m := min(d.nd, prec+1)
399 if i < m {
400 dst = append(dst, d.d[i:m]...)
401 i = m
402 }
403 for ; i <= prec; i++ {
404 dst = append(dst, '0')
405 }
406 }
407
408 // e±
409 dst = append(dst, fmt)
410 exp := d.dp - 1
411 if d.nd == 0 { // special case: 0 has exponent 0
412 exp = 0
413 }
414 if exp < 0 {
415 ch = '-'
416 exp = -exp
417 } else {
418 ch = '+'
419 }
420 dst = append(dst, ch)
421
422 // dd or ddd
423 switch {
424 case exp < 10:
425 dst = append(dst, '0', byte(exp)+'0')
426 case exp < 100:
427 dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
428 default:
429 dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
430 }
431
432 return dst
433 }
434
435 // %f: -ddddddd.ddddd
436 func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
437 // sign
438 if neg {
439 dst = append(dst, '-')
440 }
441
442 // integer, padded with zeros as needed.
443 if d.dp > 0 {
444 m := min(d.nd, d.dp)
445 dst = append(dst, d.d[:m]...)
446 for ; m < d.dp; m++ {
447 dst = append(dst, '0')
448 }
449 } else {
450 dst = append(dst, '0')
451 }
452
453 // fraction
454 if prec > 0 {
455 dst = append(dst, '.')
456 for i := 0; i < prec; i++ {
457 ch := byte('0')
458 if j := d.dp + i; 0 <= j && j < d.nd {
459 ch = d.d[j]
460 }
461 dst = append(dst, ch)
462 }
463 }
464
465 return dst
466 }
467
468 // %b: -ddddddddp±ddd
469 func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
470 // sign
471 if neg {
472 dst = append(dst, '-')
473 }
474
475 // mantissa
476 dst, _ = formatBits(dst, mant, 10, false, true)
477
478 // p
479 dst = append(dst, 'p')
480
481 // ±exponent
482 exp -= int(flt.mantbits)
483 if exp >= 0 {
484 dst = append(dst, '+')
485 }
486 dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)
487
488 return dst
489 }
490
491 // %x: -0x1.yyyyyyyyp±ddd or -0x0p+0. (y is hex digit, d is decimal digit)
492 func fmtX(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
493 if mant == 0 {
494 exp = 0
495 }
496
497 // Shift digits so leading 1 (if any) is at bit 1<<60.
498 mant <<= 60 - flt.mantbits
499 for mant != 0 && mant&(1<<60) == 0 {
500 mant <<= 1
501 exp--
502 }
503
504 // Round if requested.
505 if prec >= 0 && prec < 15 {
506 shift := uint(prec * 4)
507 extra := (mant << shift) & (1<<60 - 1)
508 mant >>= 60 - shift
509 if extra|(mant&1) > 1<<59 {
510 mant++
511 }
512 mant <<= 60 - shift
513 if mant&(1<<61) != 0 {
514 // Wrapped around.
515 mant >>= 1
516 exp++
517 }
518 }
519
520 hex := lowerhex
521 if fmt == 'X' {
522 hex = upperhex
523 }
524
525 // sign, 0x, leading digit
526 if neg {
527 dst = append(dst, '-')
528 }
529 dst = append(dst, '0', fmt, '0'+byte((mant>>60)&1))
530
531 // .fraction
532 mant <<= 4 // remove leading 0 or 1
533 if prec < 0 && mant != 0 {
534 dst = append(dst, '.')
535 for mant != 0 {
536 dst = append(dst, hex[(mant>>60)&15])
537 mant <<= 4
538 }
539 } else if prec > 0 {
540 dst = append(dst, '.')
541 for i := 0; i < prec; i++ {
542 dst = append(dst, hex[(mant>>60)&15])
543 mant <<= 4
544 }
545 }
546
547 // p±
548 ch := byte('P')
549 if fmt == lower(fmt) {
550 ch = 'p'
551 }
552 dst = append(dst, ch)
553 if exp < 0 {
554 ch = '-'
555 exp = -exp
556 } else {
557 ch = '+'
558 }
559 dst = append(dst, ch)
560
561 // dd or ddd or dddd
562 switch {
563 case exp < 100:
564 dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
565 case exp < 1000:
566 dst = append(dst, byte(exp/100)+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
567 default:
568 dst = append(dst, byte(exp/1000)+'0', byte(exp/100)%10+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
569 }
570
571 return dst
572 }
573