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