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