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


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36