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 internal
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 int, 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 = digs.nd - 1
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// Round d (= mant * 2^exp) to the shortest number of digits
227// that will let the original floating point value be precisely
228// reconstructed.  Size is original floating point size (64 or 32).
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		var l, m, u byte // lower, middle, upper digits
291		if i < lower.nd {
292			l = lower.d[i]
293		} else {
294			l = '0'
295		}
296		m = d.d[i]
297		if i < upper.nd {
298			u = upper.d[i]
299		} else {
300			u = '0'
301		}
302
303		// Okay to round down (truncate) if lower has a different digit
304		// or if lower is inclusive and is exactly the result of rounding down.
305		okdown := l != m || (inclusive && l == m && i+1 == lower.nd)
306
307		// Okay to round up if upper has a different digit and
308		// either upper is inclusive or upper is bigger than the result of rounding up.
309		okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd)
310
311		// If it's okay to do either, then round to the nearest one.
312		// If it's okay to do only one, do it.
313		switch {
314		case okdown && okup:
315			d.Round(i + 1)
316			return
317		case okdown:
318			d.RoundDown(i + 1)
319			return
320		case okup:
321			d.RoundUp(i + 1)
322			return
323		}
324	}
325}
326
327type decimalSlice struct {
328	d      []byte
329	nd, dp int
330	neg    bool
331}
332
333// %e: -d.ddddde±dd
334func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
335	// sign
336	if neg {
337		dst = append(dst, '-')
338	}
339
340	// first digit
341	ch := byte('0')
342	if d.nd != 0 {
343		ch = d.d[0]
344	}
345	dst = append(dst, ch)
346
347	// .moredigits
348	if prec > 0 {
349		dst = append(dst, '.')
350		i := 1
351		m := d.nd + prec + 1 - max(d.nd, prec+1)
352		for i < m {
353			dst = append(dst, d.d[i])
354			i++
355		}
356		for i <= prec {
357			dst = append(dst, '0')
358			i++
359		}
360	}
361
362	// e±
363	dst = append(dst, fmt)
364	exp := d.dp - 1
365	if d.nd == 0 { // special case: 0 has exponent 0
366		exp = 0
367	}
368	if exp < 0 {
369		ch = '-'
370		exp = -exp
371	} else {
372		ch = '+'
373	}
374	dst = append(dst, ch)
375
376	// dddd
377	var buf [3]byte
378	i := len(buf)
379	for exp >= 10 {
380		i--
381		buf[i] = byte(exp%10 + '0')
382		exp /= 10
383	}
384	// exp < 10
385	i--
386	buf[i] = byte(exp + '0')
387
388	switch i {
389	case 0:
390		dst = append(dst, buf[0], buf[1], buf[2])
391	case 1:
392		dst = append(dst, buf[1], buf[2])
393	case 2:
394		// leading zeroes
395		dst = append(dst, '0', buf[2])
396	}
397	return dst
398}
399
400// %f: -ddddddd.ddddd
401func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
402	// sign
403	if neg {
404		dst = append(dst, '-')
405	}
406
407	// integer, padded with zeros as needed.
408	if d.dp > 0 {
409		var i int
410		for i = 0; i < d.dp && i < d.nd; i++ {
411			dst = append(dst, d.d[i])
412		}
413		for ; i < d.dp; i++ {
414			dst = append(dst, '0')
415		}
416	} else {
417		dst = append(dst, '0')
418	}
419
420	// fraction
421	if prec > 0 {
422		dst = append(dst, '.')
423		for i := 0; i < prec; i++ {
424			ch := byte('0')
425			if j := d.dp + i; 0 <= j && j < d.nd {
426				ch = d.d[j]
427			}
428			dst = append(dst, ch)
429		}
430	}
431
432	return dst
433}
434
435// %b: -ddddddddp+ddd
436func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
437	var buf [50]byte
438	w := len(buf)
439	exp -= int(flt.mantbits)
440	esign := byte('+')
441	if exp < 0 {
442		esign = '-'
443		exp = -exp
444	}
445	n := 0
446	for exp > 0 || n < 1 {
447		n++
448		w--
449		buf[w] = byte(exp%10 + '0')
450		exp /= 10
451	}
452	w--
453	buf[w] = esign
454	w--
455	buf[w] = 'p'
456	n = 0
457	for mant > 0 || n < 1 {
458		n++
459		w--
460		buf[w] = byte(mant%10 + '0')
461		mant /= 10
462	}
463	if neg {
464		w--
465		buf[w] = '-'
466	}
467	return append(dst, buf[w:]...)
468}
469
470func max(a, b int) int {
471	if a > b {
472		return a
473	}
474	return b
475}
476