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), or
36// 'G' ('E' for large exponents, 'f' otherwise).
37//
38// The precision prec controls the number of digits
39// (excluding the exponent) printed by the 'e', 'E', 'f', 'g', and 'G' formats.
40// For 'e', 'E', and 'f' it is the number of digits after the decimal point.
41// For 'g' and 'G' it is the total number of digits.
42// The special precision -1 uses the smallest number of digits
43// necessary such that ParseFloat will return f exactly.
44func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
45	return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))
46}
47
48// AppendFloat appends the string form of the floating-point number f,
49// as generated by FormatFloat, to dst and returns the extended buffer.
50func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
51	return genericFtoa(dst, f, fmt, prec, bitSize)
52}
53
54func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
55	var bits uint64
56	var flt *floatInfo
57	switch bitSize {
58	case 32:
59		bits = uint64(math.Float32bits(float32(val)))
60		flt = &float32info
61	case 64:
62		bits = math.Float64bits(val)
63		flt = &float64info
64	default:
65		panic("strconv: illegal AppendFloat/FormatFloat bitSize")
66	}
67
68	neg := bits>>(flt.expbits+flt.mantbits) != 0
69	exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
70	mant := bits & (uint64(1)<<flt.mantbits - 1)
71
72	switch exp {
73	case 1<<flt.expbits - 1:
74		// Inf, NaN
75		var s string
76		switch {
77		case mant != 0:
78			s = "NaN"
79		case neg:
80			s = "-Inf"
81		default:
82			s = "+Inf"
83		}
84		return append(dst, s...)
85
86	case 0:
87		// denormalized
88		exp++
89
90	default:
91		// add implicit top bit
92		mant |= uint64(1) << flt.mantbits
93	}
94	exp += flt.bias
95
96	// Pick off easy binary format.
97	if fmt == 'b' {
98		return fmtB(dst, neg, mant, exp, flt)
99	}
100
101	if !optimize {
102		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
103	}
104
105	var digs decimalSlice
106	ok := false
107	// Negative precision means "only as much as needed to be exact."
108	shortest := prec < 0
109	if shortest {
110		// Try Grisu3 algorithm.
111		f := new(extFloat)
112		lower, upper := f.AssignComputeBounds(mant, exp, neg, flt)
113		var buf [32]byte
114		digs.d = buf[:]
115		ok = f.ShortestDecimal(&digs, &lower, &upper)
116		if !ok {
117			return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
118		}
119		// Precision for shortest representation mode.
120		switch fmt {
121		case 'e', 'E':
122			prec = max(digs.nd-1, 0)
123		case 'f':
124			prec = max(digs.nd-digs.dp, 0)
125		case 'g', 'G':
126			prec = digs.nd
127		}
128	} else if fmt != 'f' {
129		// Fixed number of digits.
130		digits := prec
131		switch fmt {
132		case 'e', 'E':
133			digits++
134		case 'g', 'G':
135			if prec == 0 {
136				prec = 1
137			}
138			digits = prec
139		}
140		if digits <= 15 {
141			// try fast algorithm when the number of digits is reasonable.
142			var buf [24]byte
143			digs.d = buf[:]
144			f := extFloat{mant, exp - int(flt.mantbits), neg}
145			ok = f.FixedDecimal(&digs, digits)
146		}
147	}
148	if !ok {
149		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
150	}
151	return formatDigits(dst, shortest, neg, digs, prec, fmt)
152}
153
154// bigFtoa uses multiprecision computations to format a float.
155func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
156	d := new(decimal)
157	d.Assign(mant)
158	d.Shift(exp - int(flt.mantbits))
159	var digs decimalSlice
160	shortest := prec < 0
161	if shortest {
162		roundShortest(d, mant, exp, flt)
163		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
164		// Precision for shortest representation mode.
165		switch fmt {
166		case 'e', 'E':
167			prec = digs.nd - 1
168		case 'f':
169			prec = max(digs.nd-digs.dp, 0)
170		case 'g', 'G':
171			prec = digs.nd
172		}
173	} else {
174		// Round appropriately.
175		switch fmt {
176		case 'e', 'E':
177			d.Round(prec + 1)
178		case 'f':
179			d.Round(d.dp + prec)
180		case 'g', 'G':
181			if prec == 0 {
182				prec = 1
183			}
184			d.Round(prec)
185		}
186		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
187	}
188	return formatDigits(dst, shortest, neg, digs, prec, fmt)
189}
190
191func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
192	switch fmt {
193	case 'e', 'E':
194		return fmtE(dst, neg, digs, prec, fmt)
195	case 'f':
196		return fmtF(dst, neg, digs, prec)
197	case 'g', 'G':
198		// trailing fractional zeros in 'e' form will be trimmed.
199		eprec := prec
200		if eprec > digs.nd && digs.nd >= digs.dp {
201			eprec = digs.nd
202		}
203		// %e is used if the exponent from the conversion
204		// is less than -4 or greater than or equal to the precision.
205		// if precision was the shortest possible, use precision 6 for this decision.
206		if shortest {
207			eprec = 6
208		}
209		exp := digs.dp - 1
210		if exp < -4 || exp >= eprec {
211			if prec > digs.nd {
212				prec = digs.nd
213			}
214			return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
215		}
216		if prec > digs.dp {
217			prec = digs.nd
218		}
219		return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
220	}
221
222	// unknown format
223	return append(dst, '%', fmt)
224}
225
226// roundShortest rounds d (= mant * 2^exp) to the shortest number of digits
227// that will let the original floating point value be precisely reconstructed.
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		l := byte('0') // lower digit
290		if i < lower.nd {
291			l = lower.d[i]
292		}
293		m := d.d[i]    // middle digit
294		u := byte('0') // upper digit
295		if i < upper.nd {
296			u = upper.d[i]
297		}
298
299		// Okay to round down (truncate) if lower has a different digit
300		// or if lower is inclusive and is exactly the result of rounding
301		// down (i.e., and we have reached the final digit of lower).
302		okdown := l != m || inclusive && i+1 == lower.nd
303
304		// Okay to round up if upper has a different digit and either upper
305		// is inclusive or upper is bigger than the result of rounding up.
306		okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd)
307
308		// If it's okay to do either, then round to the nearest one.
309		// If it's okay to do only one, do it.
310		switch {
311		case okdown && okup:
312			d.Round(i + 1)
313			return
314		case okdown:
315			d.RoundDown(i + 1)
316			return
317		case okup:
318			d.RoundUp(i + 1)
319			return
320		}
321	}
322}
323
324type decimalSlice struct {
325	d      []byte
326	nd, dp int
327	neg    bool
328}
329
330// %e: -d.ddddde±dd
331func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
332	// sign
333	if neg {
334		dst = append(dst, '-')
335	}
336
337	// first digit
338	ch := byte('0')
339	if d.nd != 0 {
340		ch = d.d[0]
341	}
342	dst = append(dst, ch)
343
344	// .moredigits
345	if prec > 0 {
346		dst = append(dst, '.')
347		i := 1
348		m := min(d.nd, prec+1)
349		if i < m {
350			dst = append(dst, d.d[i:m]...)
351			i = m
352		}
353		for ; i <= prec; i++ {
354			dst = append(dst, '0')
355		}
356	}
357
358	// e±
359	dst = append(dst, fmt)
360	exp := d.dp - 1
361	if d.nd == 0 { // special case: 0 has exponent 0
362		exp = 0
363	}
364	if exp < 0 {
365		ch = '-'
366		exp = -exp
367	} else {
368		ch = '+'
369	}
370	dst = append(dst, ch)
371
372	// dd or ddd
373	switch {
374	case exp < 10:
375		dst = append(dst, '0', byte(exp)+'0')
376	case exp < 100:
377		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
378	default:
379		dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
380	}
381
382	return dst
383}
384
385// %f: -ddddddd.ddddd
386func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
387	// sign
388	if neg {
389		dst = append(dst, '-')
390	}
391
392	// integer, padded with zeros as needed.
393	if d.dp > 0 {
394		m := min(d.nd, d.dp)
395		dst = append(dst, d.d[:m]...)
396		for ; m < d.dp; m++ {
397			dst = append(dst, '0')
398		}
399	} else {
400		dst = append(dst, '0')
401	}
402
403	// fraction
404	if prec > 0 {
405		dst = append(dst, '.')
406		for i := 0; i < prec; i++ {
407			ch := byte('0')
408			if j := d.dp + i; 0 <= j && j < d.nd {
409				ch = d.d[j]
410			}
411			dst = append(dst, ch)
412		}
413	}
414
415	return dst
416}
417
418// %b: -ddddddddp±ddd
419func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
420	// sign
421	if neg {
422		dst = append(dst, '-')
423	}
424
425	// mantissa
426	dst, _ = formatBits(dst, mant, 10, false, true)
427
428	// p
429	dst = append(dst, 'p')
430
431	// ±exponent
432	exp -= int(flt.mantbits)
433	if exp >= 0 {
434		dst = append(dst, '+')
435	}
436	dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)
437
438	return dst
439}
440
441func min(a, b int) int {
442	if a < b {
443		return a
444	}
445	return b
446}
447
448func max(a, b int) int {
449	if a > b {
450		return a
451	}
452	return b
453}
454