1#include "absl/strings/internal/str_format/float_conversion.h"
2
3#include <string.h>
4#include <algorithm>
5#include <cassert>
6#include <cmath>
7#include <string>
8
9#include "absl/base/config.h"
10
11namespace absl {
12namespace str_format_internal {
13
14namespace {
15
16char *CopyStringTo(string_view v, char *out) {
17 std::memcpy(out, v.data(), v.size());
18 return out + v.size();
19}
20
21template <typename Float>
22bool FallbackToSnprintf(const Float v, const ConversionSpec &conv,
23 FormatSinkImpl *sink) {
24 int w = conv.width() >= 0 ? conv.width() : 0;
25 int p = conv.precision() >= 0 ? conv.precision() : -1;
26 char fmt[32];
27 {
28 char *fp = fmt;
29 *fp++ = '%';
30 fp = CopyStringTo(conv.flags().ToString(), fp);
31 fp = CopyStringTo("*.*", fp);
32 if (std::is_same<long double, Float>()) {
33 *fp++ = 'L';
34 }
35 *fp++ = conv.conv().Char();
36 *fp = 0;
37 assert(fp < fmt + sizeof(fmt));
38 }
39 std::string space(512, '\0');
40 string_view result;
41 while (true) {
42 int n = snprintf(&space[0], space.size(), fmt, w, p, v);
43 if (n < 0) return false;
44 if (static_cast<size_t>(n) < space.size()) {
45 result = string_view(space.data(), n);
46 break;
47 }
48 space.resize(n + 1);
49 }
50 sink->Append(result);
51 return true;
52}
53
54// 128-bits in decimal: ceil(128*log(2)/log(10))
55// or std::numeric_limits<__uint128_t>::digits10
56constexpr int kMaxFixedPrecision = 39;
57
58constexpr int kBufferLength = /*sign*/ 1 +
59 /*integer*/ kMaxFixedPrecision +
60 /*point*/ 1 +
61 /*fraction*/ kMaxFixedPrecision +
62 /*exponent e+123*/ 5;
63
64struct Buffer {
65 void push_front(char c) {
66 assert(begin > data);
67 *--begin = c;
68 }
69 void push_back(char c) {
70 assert(end < data + sizeof(data));
71 *end++ = c;
72 }
73 void pop_back() {
74 assert(begin < end);
75 --end;
76 }
77
78 char &back() {
79 assert(begin < end);
80 return end[-1];
81 }
82
83 char last_digit() const { return end[-1] == '.' ? end[-2] : end[-1]; }
84
85 int size() const { return static_cast<int>(end - begin); }
86
87 char data[kBufferLength];
88 char *begin;
89 char *end;
90};
91
92enum class FormatStyle { Fixed, Precision };
93
94// If the value is Inf or Nan, print it and return true.
95// Otherwise, return false.
96template <typename Float>
97bool ConvertNonNumericFloats(char sign_char, Float v,
98 const ConversionSpec &conv, FormatSinkImpl *sink) {
99 char text[4], *ptr = text;
100 if (sign_char) *ptr++ = sign_char;
101 if (std::isnan(v)) {
102 ptr = std::copy_n(conv.conv().upper() ? "NAN" : "nan", 3, ptr);
103 } else if (std::isinf(v)) {
104 ptr = std::copy_n(conv.conv().upper() ? "INF" : "inf", 3, ptr);
105 } else {
106 return false;
107 }
108
109 return sink->PutPaddedString(string_view(text, ptr - text), conv.width(), -1,
110 conv.flags().left);
111}
112
113// Round up the last digit of the value.
114// It will carry over and potentially overflow. 'exp' will be adjusted in that
115// case.
116template <FormatStyle mode>
117void RoundUp(Buffer *buffer, int *exp) {
118 char *p = &buffer->back();
119 while (p >= buffer->begin && (*p == '9' || *p == '.')) {
120 if (*p == '9') *p = '0';
121 --p;
122 }
123
124 if (p < buffer->begin) {
125 *p = '1';
126 buffer->begin = p;
127 if (mode == FormatStyle::Precision) {
128 std::swap(p[1], p[2]); // move the .
129 ++*exp;
130 buffer->pop_back();
131 }
132 } else {
133 ++*p;
134 }
135}
136
137void PrintExponent(int exp, char e, Buffer *out) {
138 out->push_back(e);
139 if (exp < 0) {
140 out->push_back('-');
141 exp = -exp;
142 } else {
143 out->push_back('+');
144 }
145 // Exponent digits.
146 if (exp > 99) {
147 out->push_back(exp / 100 + '0');
148 out->push_back(exp / 10 % 10 + '0');
149 out->push_back(exp % 10 + '0');
150 } else {
151 out->push_back(exp / 10 + '0');
152 out->push_back(exp % 10 + '0');
153 }
154}
155
156template <typename Float, typename Int>
157constexpr bool CanFitMantissa() {
158 return
159#if defined(__clang__) && !defined(__SSE3__)
160 // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289
161 // Casting from long double to uint64_t is miscompiled and drops bits.
162 (!std::is_same<Float, long double>::value ||
163 !std::is_same<Int, uint64_t>::value) &&
164#endif
165 std::numeric_limits<Float>::digits <= std::numeric_limits<Int>::digits;
166}
167
168template <typename Float>
169struct Decomposed {
170 Float mantissa;
171 int exponent;
172};
173
174// Decompose the double into an integer mantissa and an exponent.
175template <typename Float>
176Decomposed<Float> Decompose(Float v) {
177 int exp;
178 Float m = std::frexp(v, &exp);
179 m = std::ldexp(m, std::numeric_limits<Float>::digits);
180 exp -= std::numeric_limits<Float>::digits;
181 return {m, exp};
182}
183
184// Print 'digits' as decimal.
185// In Fixed mode, we add a '.' at the end.
186// In Precision mode, we add a '.' after the first digit.
187template <FormatStyle mode, typename Int>
188int PrintIntegralDigits(Int digits, Buffer *out) {
189 int printed = 0;
190 if (digits) {
191 for (; digits; digits /= 10) out->push_front(digits % 10 + '0');
192 printed = out->size();
193 if (mode == FormatStyle::Precision) {
194 out->push_front(*out->begin);
195 out->begin[1] = '.';
196 } else {
197 out->push_back('.');
198 }
199 } else if (mode == FormatStyle::Fixed) {
200 out->push_front('0');
201 out->push_back('.');
202 printed = 1;
203 }
204 return printed;
205}
206
207// Back out 'extra_digits' digits and round up if necessary.
208bool RemoveExtraPrecision(int extra_digits, bool has_leftover_value,
209 Buffer *out, int *exp_out) {
210 if (extra_digits <= 0) return false;
211
212 // Back out the extra digits
213 out->end -= extra_digits;
214
215 bool needs_to_round_up = [&] {
216 // We look at the digit just past the end.
217 // There must be 'extra_digits' extra valid digits after end.
218 if (*out->end > '5') return true;
219 if (*out->end < '5') return false;
220 if (has_leftover_value || std::any_of(out->end + 1, out->end + extra_digits,
221 [](char c) { return c != '0'; }))
222 return true;
223
224 // Ends in ...50*, round to even.
225 return out->last_digit() % 2 == 1;
226 }();
227
228 if (needs_to_round_up) {
229 RoundUp<FormatStyle::Precision>(out, exp_out);
230 }
231 return true;
232}
233
234// Print the value into the buffer.
235// This will not include the exponent, which will be returned in 'exp_out' for
236// Precision mode.
237template <typename Int, typename Float, FormatStyle mode>
238bool FloatToBufferImpl(Int int_mantissa, int exp, int precision, Buffer *out,
239 int *exp_out) {
240 assert((CanFitMantissa<Float, Int>()));
241
242 const int int_bits = std::numeric_limits<Int>::digits;
243
244 // In precision mode, we start printing one char to the right because it will
245 // also include the '.'
246 // In fixed mode we put the dot afterwards on the right.
247 out->begin = out->end =
248 out->data + 1 + kMaxFixedPrecision + (mode == FormatStyle::Precision);
249
250 if (exp >= 0) {
251 if (std::numeric_limits<Float>::digits + exp > int_bits) {
252 // The value will overflow the Int
253 return false;
254 }
255 int digits_printed = PrintIntegralDigits<mode>(int_mantissa << exp, out);
256 int digits_to_zero_pad = precision;
257 if (mode == FormatStyle::Precision) {
258 *exp_out = digits_printed - 1;
259 digits_to_zero_pad -= digits_printed - 1;
260 if (RemoveExtraPrecision(-digits_to_zero_pad, false, out, exp_out)) {
261 return true;
262 }
263 }
264 for (; digits_to_zero_pad-- > 0;) out->push_back('0');
265 return true;
266 }
267
268 exp = -exp;
269 // We need at least 4 empty bits for the next decimal digit.
270 // We will multiply by 10.
271 if (exp > int_bits - 4) return false;
272
273 const Int mask = (Int{1} << exp) - 1;
274
275 // Print the integral part first.
276 int digits_printed = PrintIntegralDigits<mode>(int_mantissa >> exp, out);
277 int_mantissa &= mask;
278
279 int fractional_count = precision;
280 if (mode == FormatStyle::Precision) {
281 if (digits_printed == 0) {
282 // Find the first non-zero digit, when in Precision mode.
283 *exp_out = 0;
284 if (int_mantissa) {
285 while (int_mantissa <= mask) {
286 int_mantissa *= 10;
287 --*exp_out;
288 }
289 }
290 out->push_front(static_cast<char>(int_mantissa >> exp) + '0');
291 out->push_back('.');
292 int_mantissa &= mask;
293 } else {
294 // We already have a digit, and a '.'
295 *exp_out = digits_printed - 1;
296 fractional_count -= *exp_out;
297 if (RemoveExtraPrecision(-fractional_count, int_mantissa != 0, out,
298 exp_out)) {
299 // If we had enough digits, return right away.
300 // The code below will try to round again otherwise.
301 return true;
302 }
303 }
304 }
305
306 auto get_next_digit = [&] {
307 int_mantissa *= 10;
308 int digit = static_cast<int>(int_mantissa >> exp);
309 int_mantissa &= mask;
310 return digit;
311 };
312
313 // Print fractional_count more digits, if available.
314 for (; fractional_count > 0; --fractional_count) {
315 out->push_back(get_next_digit() + '0');
316 }
317
318 int next_digit = get_next_digit();
319 if (next_digit > 5 ||
320 (next_digit == 5 && (int_mantissa || out->last_digit() % 2 == 1))) {
321 RoundUp<mode>(out, exp_out);
322 }
323
324 return true;
325}
326
327template <FormatStyle mode, typename Float>
328bool FloatToBuffer(Decomposed<Float> decomposed, int precision, Buffer *out,
329 int *exp) {
330 if (precision > kMaxFixedPrecision) return false;
331
332 // Try with uint64_t.
333 if (CanFitMantissa<Float, std::uint64_t>() &&
334 FloatToBufferImpl<std::uint64_t, Float, mode>(
335 static_cast<std::uint64_t>(decomposed.mantissa),
336 static_cast<std::uint64_t>(decomposed.exponent), precision, out, exp))
337 return true;
338
339#if defined(ABSL_HAVE_INTRINSIC_INT128)
340 // If that is not enough, try with __uint128_t.
341 return CanFitMantissa<Float, __uint128_t>() &&
342 FloatToBufferImpl<__uint128_t, Float, mode>(
343 static_cast<__uint128_t>(decomposed.mantissa),
344 static_cast<__uint128_t>(decomposed.exponent), precision, out,
345 exp);
346#endif
347 return false;
348}
349
350void WriteBufferToSink(char sign_char, string_view str,
351 const ConversionSpec &conv, FormatSinkImpl *sink) {
352 int left_spaces = 0, zeros = 0, right_spaces = 0;
353 int missing_chars =
354 conv.width() >= 0 ? std::max(conv.width() - static_cast<int>(str.size()) -
355 static_cast<int>(sign_char != 0),
356 0)
357 : 0;
358 if (conv.flags().left) {
359 right_spaces = missing_chars;
360 } else if (conv.flags().zero) {
361 zeros = missing_chars;
362 } else {
363 left_spaces = missing_chars;
364 }
365
366 sink->Append(left_spaces, ' ');
367 if (sign_char) sink->Append(1, sign_char);
368 sink->Append(zeros, '0');
369 sink->Append(str);
370 sink->Append(right_spaces, ' ');
371}
372
373template <typename Float>
374bool FloatToSink(const Float v, const ConversionSpec &conv,
375 FormatSinkImpl *sink) {
376 // Print the sign or the sign column.
377 Float abs_v = v;
378 char sign_char = 0;
379 if (std::signbit(abs_v)) {
380 sign_char = '-';
381 abs_v = -abs_v;
382 } else if (conv.flags().show_pos) {
383 sign_char = '+';
384 } else if (conv.flags().sign_col) {
385 sign_char = ' ';
386 }
387
388 // Print nan/inf.
389 if (ConvertNonNumericFloats(sign_char, abs_v, conv, sink)) {
390 return true;
391 }
392
393 int precision = conv.precision() < 0 ? 6 : conv.precision();
394
395 int exp = 0;
396
397 auto decomposed = Decompose(abs_v);
398
399 Buffer buffer;
400
401 switch (conv.conv().id()) {
402 case ConversionChar::f:
403 case ConversionChar::F:
404 if (!FloatToBuffer<FormatStyle::Fixed>(decomposed, precision, &buffer,
405 nullptr)) {
406 return FallbackToSnprintf(v, conv, sink);
407 }
408 if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back();
409 break;
410
411 case ConversionChar::e:
412 case ConversionChar::E:
413 if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
414 &exp)) {
415 return FallbackToSnprintf(v, conv, sink);
416 }
417 if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back();
418 PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer);
419 break;
420
421 case ConversionChar::g:
422 case ConversionChar::G:
423 precision = std::max(0, precision - 1);
424 if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
425 &exp)) {
426 return FallbackToSnprintf(v, conv, sink);
427 }
428 if (precision + 1 > exp && exp >= -4) {
429 if (exp < 0) {
430 // Have 1.23456, needs 0.00123456
431 // Move the first digit
432 buffer.begin[1] = *buffer.begin;
433 // Add some zeros
434 for (; exp < -1; ++exp) *buffer.begin-- = '0';
435 *buffer.begin-- = '.';
436 *buffer.begin = '0';
437 } else if (exp > 0) {
438 // Have 1.23456, needs 1234.56
439 // Move the '.' exp positions to the right.
440 std::rotate(buffer.begin + 1, buffer.begin + 2,
441 buffer.begin + exp + 2);
442 }
443 exp = 0;
444 }
445 if (!conv.flags().alt) {
446 while (buffer.back() == '0') buffer.pop_back();
447 if (buffer.back() == '.') buffer.pop_back();
448 }
449 if (exp) PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer);
450 break;
451
452 case ConversionChar::a:
453 case ConversionChar::A:
454 return FallbackToSnprintf(v, conv, sink);
455
456 default:
457 return false;
458 }
459
460 WriteBufferToSink(sign_char,
461 string_view(buffer.begin, buffer.end - buffer.begin), conv,
462 sink);
463
464 return true;
465}
466
467} // namespace
468
469bool ConvertFloatImpl(long double v, const ConversionSpec &conv,
470 FormatSinkImpl *sink) {
471 return FloatToSink(v, conv, sink);
472}
473
474bool ConvertFloatImpl(float v, const ConversionSpec &conv,
475 FormatSinkImpl *sink) {
476 return FloatToSink(v, conv, sink);
477}
478
479bool ConvertFloatImpl(double v, const ConversionSpec &conv,
480 FormatSinkImpl *sink) {
481 return FloatToSink(v, conv, sink);
482}
483
484} // namespace str_format_internal
485} // namespace absl
486