float_conversion.cc
Go to the documentation of this file.
00001 #include "absl/strings/internal/str_format/float_conversion.h"
00002 
00003 #include <string.h>
00004 #include <algorithm>
00005 #include <cassert>
00006 #include <cmath>
00007 #include <string>
00008 
00009 namespace absl {
00010 namespace str_format_internal {
00011 
00012 namespace {
00013 
00014 char *CopyStringTo(string_view v, char *out) {
00015   std::memcpy(out, v.data(), v.size());
00016   return out + v.size();
00017 }
00018 
00019 template <typename Float>
00020 bool FallbackToSnprintf(const Float v, const ConversionSpec &conv,
00021                         FormatSinkImpl *sink) {
00022   int w = conv.width() >= 0 ? conv.width() : 0;
00023   int p = conv.precision() >= 0 ? conv.precision() : -1;
00024   char fmt[32];
00025   {
00026     char *fp = fmt;
00027     *fp++ = '%';
00028     fp = CopyStringTo(conv.flags().ToString(), fp);
00029     fp = CopyStringTo("*.*", fp);
00030     if (std::is_same<long double, Float>()) {
00031       *fp++ = 'L';
00032     }
00033     *fp++ = conv.conv().Char();
00034     *fp = 0;
00035     assert(fp < fmt + sizeof(fmt));
00036   }
00037   std::string space(512, '\0');
00038   string_view result;
00039   while (true) {
00040     int n = snprintf(&space[0], space.size(), fmt, w, p, v);
00041     if (n < 0) return false;
00042     if (static_cast<size_t>(n) < space.size()) {
00043       result = string_view(space.data(), n);
00044       break;
00045     }
00046     space.resize(n + 1);
00047   }
00048   sink->Append(result);
00049   return true;
00050 }
00051 
00052 // 128-bits in decimal: ceil(128*log(2)/log(10))
00053 //   or std::numeric_limits<__uint128_t>::digits10
00054 constexpr int kMaxFixedPrecision = 39;
00055 
00056 constexpr int kBufferLength = /*sign*/ 1 +
00057                               /*integer*/ kMaxFixedPrecision +
00058                               /*point*/ 1 +
00059                               /*fraction*/ kMaxFixedPrecision +
00060                               /*exponent e+123*/ 5;
00061 
00062 struct Buffer {
00063   void push_front(char c) {
00064     assert(begin > data);
00065     *--begin = c;
00066   }
00067   void push_back(char c) {
00068     assert(end < data + sizeof(data));
00069     *end++ = c;
00070   }
00071   void pop_back() {
00072     assert(begin < end);
00073     --end;
00074   }
00075 
00076   char &back() {
00077     assert(begin < end);
00078     return end[-1];
00079   }
00080 
00081   char last_digit() const { return end[-1] == '.' ? end[-2] : end[-1]; }
00082 
00083   int size() const { return static_cast<int>(end - begin); }
00084 
00085   char data[kBufferLength];
00086   char *begin;
00087   char *end;
00088 };
00089 
00090 enum class FormatStyle { Fixed, Precision };
00091 
00092 // If the value is Inf or Nan, print it and return true.
00093 // Otherwise, return false.
00094 template <typename Float>
00095 bool ConvertNonNumericFloats(char sign_char, Float v,
00096                              const ConversionSpec &conv, FormatSinkImpl *sink) {
00097   char text[4], *ptr = text;
00098   if (sign_char) *ptr++ = sign_char;
00099   if (std::isnan(v)) {
00100     ptr = std::copy_n(conv.conv().upper() ? "NAN" : "nan", 3, ptr);
00101   } else if (std::isinf(v)) {
00102     ptr = std::copy_n(conv.conv().upper() ? "INF" : "inf", 3, ptr);
00103   } else {
00104     return false;
00105   }
00106 
00107   return sink->PutPaddedString(string_view(text, ptr - text), conv.width(), -1,
00108                                conv.flags().left);
00109 }
00110 
00111 // Round up the last digit of the value.
00112 // It will carry over and potentially overflow. 'exp' will be adjusted in that
00113 // case.
00114 template <FormatStyle mode>
00115 void RoundUp(Buffer *buffer, int *exp) {
00116   char *p = &buffer->back();
00117   while (p >= buffer->begin && (*p == '9' || *p == '.')) {
00118     if (*p == '9') *p = '0';
00119     --p;
00120   }
00121 
00122   if (p < buffer->begin) {
00123     *p = '1';
00124     buffer->begin = p;
00125     if (mode == FormatStyle::Precision) {
00126       std::swap(p[1], p[2]);  // move the .
00127       ++*exp;
00128       buffer->pop_back();
00129     }
00130   } else {
00131     ++*p;
00132   }
00133 }
00134 
00135 void PrintExponent(int exp, char e, Buffer *out) {
00136   out->push_back(e);
00137   if (exp < 0) {
00138     out->push_back('-');
00139     exp = -exp;
00140   } else {
00141     out->push_back('+');
00142   }
00143   // Exponent digits.
00144   if (exp > 99) {
00145     out->push_back(exp / 100 + '0');
00146     out->push_back(exp / 10 % 10 + '0');
00147     out->push_back(exp % 10 + '0');
00148   } else {
00149     out->push_back(exp / 10 + '0');
00150     out->push_back(exp % 10 + '0');
00151   }
00152 }
00153 
00154 template <typename Float, typename Int>
00155 constexpr bool CanFitMantissa() {
00156   return
00157 #if defined(__clang__) && !defined(__SSE3__)
00158       // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289
00159       // Casting from long double to uint64_t is miscompiled and drops bits.
00160       (!std::is_same<Float, long double>::value ||
00161        !std::is_same<Int, uint64_t>::value) &&
00162 #endif
00163       std::numeric_limits<Float>::digits <= std::numeric_limits<Int>::digits;
00164 }
00165 
00166 template <typename Float>
00167 struct Decomposed {
00168   Float mantissa;
00169   int exponent;
00170 };
00171 
00172 // Decompose the double into an integer mantissa and an exponent.
00173 template <typename Float>
00174 Decomposed<Float> Decompose(Float v) {
00175   int exp;
00176   Float m = std::frexp(v, &exp);
00177   m = std::ldexp(m, std::numeric_limits<Float>::digits);
00178   exp -= std::numeric_limits<Float>::digits;
00179   return {m, exp};
00180 }
00181 
00182 // Print 'digits' as decimal.
00183 // In Fixed mode, we add a '.' at the end.
00184 // In Precision mode, we add a '.' after the first digit.
00185 template <FormatStyle mode, typename Int>
00186 int PrintIntegralDigits(Int digits, Buffer *out) {
00187   int printed = 0;
00188   if (digits) {
00189     for (; digits; digits /= 10) out->push_front(digits % 10 + '0');
00190     printed = out->size();
00191     if (mode == FormatStyle::Precision) {
00192       out->push_front(*out->begin);
00193       out->begin[1] = '.';
00194     } else {
00195       out->push_back('.');
00196     }
00197   } else if (mode == FormatStyle::Fixed) {
00198     out->push_front('0');
00199     out->push_back('.');
00200     printed = 1;
00201   }
00202   return printed;
00203 }
00204 
00205 // Back out 'extra_digits' digits and round up if necessary.
00206 bool RemoveExtraPrecision(int extra_digits, bool has_leftover_value,
00207                           Buffer *out, int *exp_out) {
00208   if (extra_digits <= 0) return false;
00209 
00210   // Back out the extra digits
00211   out->end -= extra_digits;
00212 
00213   bool needs_to_round_up = [&] {
00214     // We look at the digit just past the end.
00215     // There must be 'extra_digits' extra valid digits after end.
00216     if (*out->end > '5') return true;
00217     if (*out->end < '5') return false;
00218     if (has_leftover_value || std::any_of(out->end + 1, out->end + extra_digits,
00219                                           [](char c) { return c != '0'; }))
00220       return true;
00221 
00222     // Ends in ...50*, round to even.
00223     return out->last_digit() % 2 == 1;
00224   }();
00225 
00226   if (needs_to_round_up) {
00227     RoundUp<FormatStyle::Precision>(out, exp_out);
00228   }
00229   return true;
00230 }
00231 
00232 // Print the value into the buffer.
00233 // This will not include the exponent, which will be returned in 'exp_out' for
00234 // Precision mode.
00235 template <typename Int, typename Float, FormatStyle mode>
00236 bool FloatToBufferImpl(Int int_mantissa, int exp, int precision, Buffer *out,
00237                        int *exp_out) {
00238   assert((CanFitMantissa<Float, Int>()));
00239 
00240   const int int_bits = std::numeric_limits<Int>::digits;
00241 
00242   // In precision mode, we start printing one char to the right because it will
00243   // also include the '.'
00244   // In fixed mode we put the dot afterwards on the right.
00245   out->begin = out->end =
00246       out->data + 1 + kMaxFixedPrecision + (mode == FormatStyle::Precision);
00247 
00248   if (exp >= 0) {
00249     if (std::numeric_limits<Float>::digits + exp > int_bits) {
00250       // The value will overflow the Int
00251       return false;
00252     }
00253     int digits_printed = PrintIntegralDigits<mode>(int_mantissa << exp, out);
00254     int digits_to_zero_pad = precision;
00255     if (mode == FormatStyle::Precision) {
00256       *exp_out = digits_printed - 1;
00257       digits_to_zero_pad -= digits_printed - 1;
00258       if (RemoveExtraPrecision(-digits_to_zero_pad, false, out, exp_out)) {
00259         return true;
00260       }
00261     }
00262     for (; digits_to_zero_pad-- > 0;) out->push_back('0');
00263     return true;
00264   }
00265 
00266   exp = -exp;
00267   // We need at least 4 empty bits for the next decimal digit.
00268   // We will multiply by 10.
00269   if (exp > int_bits - 4) return false;
00270 
00271   const Int mask = (Int{1} << exp) - 1;
00272 
00273   // Print the integral part first.
00274   int digits_printed = PrintIntegralDigits<mode>(int_mantissa >> exp, out);
00275   int_mantissa &= mask;
00276 
00277   int fractional_count = precision;
00278   if (mode == FormatStyle::Precision) {
00279     if (digits_printed == 0) {
00280       // Find the first non-zero digit, when in Precision mode.
00281       *exp_out = 0;
00282       if (int_mantissa) {
00283         while (int_mantissa <= mask) {
00284           int_mantissa *= 10;
00285           --*exp_out;
00286         }
00287       }
00288       out->push_front(static_cast<char>(int_mantissa >> exp) + '0');
00289       out->push_back('.');
00290       int_mantissa &= mask;
00291     } else {
00292       // We already have a digit, and a '.'
00293       *exp_out = digits_printed - 1;
00294       fractional_count -= *exp_out;
00295       if (RemoveExtraPrecision(-fractional_count, int_mantissa != 0, out,
00296                                exp_out)) {
00297         // If we had enough digits, return right away.
00298         // The code below will try to round again otherwise.
00299         return true;
00300       }
00301     }
00302   }
00303 
00304   auto get_next_digit = [&] {
00305     int_mantissa *= 10;
00306     int digit = static_cast<int>(int_mantissa >> exp);
00307     int_mantissa &= mask;
00308     return digit;
00309   };
00310 
00311   // Print fractional_count more digits, if available.
00312   for (; fractional_count > 0; --fractional_count) {
00313     out->push_back(get_next_digit() + '0');
00314   }
00315 
00316   int next_digit = get_next_digit();
00317   if (next_digit > 5 ||
00318       (next_digit == 5 && (int_mantissa || out->last_digit() % 2 == 1))) {
00319     RoundUp<mode>(out, exp_out);
00320   }
00321 
00322   return true;
00323 }
00324 
00325 template <FormatStyle mode, typename Float>
00326 bool FloatToBuffer(Decomposed<Float> decomposed, int precision, Buffer *out,
00327                    int *exp) {
00328   if (precision > kMaxFixedPrecision) return false;
00329 
00330   // Try with uint64_t.
00331   if (CanFitMantissa<Float, std::uint64_t>() &&
00332       FloatToBufferImpl<std::uint64_t, Float, mode>(
00333           static_cast<std::uint64_t>(decomposed.mantissa),
00334           static_cast<std::uint64_t>(decomposed.exponent), precision, out, exp))
00335     return true;
00336 
00337 #if defined(__SIZEOF_INT128__)
00338   // If that is not enough, try with __uint128_t.
00339   return CanFitMantissa<Float, __uint128_t>() &&
00340          FloatToBufferImpl<__uint128_t, Float, mode>(
00341              static_cast<__uint128_t>(decomposed.mantissa),
00342              static_cast<__uint128_t>(decomposed.exponent), precision, out,
00343              exp);
00344 #endif
00345   return false;
00346 }
00347 
00348 void WriteBufferToSink(char sign_char, string_view str,
00349                        const ConversionSpec &conv, FormatSinkImpl *sink) {
00350   int left_spaces = 0, zeros = 0, right_spaces = 0;
00351   int missing_chars =
00352       conv.width() >= 0 ? std::max(conv.width() - static_cast<int>(str.size()) -
00353                                        static_cast<int>(sign_char != 0),
00354                                    0)
00355                         : 0;
00356   if (conv.flags().left) {
00357     right_spaces = missing_chars;
00358   } else if (conv.flags().zero) {
00359     zeros = missing_chars;
00360   } else {
00361     left_spaces = missing_chars;
00362   }
00363 
00364   sink->Append(left_spaces, ' ');
00365   if (sign_char) sink->Append(1, sign_char);
00366   sink->Append(zeros, '0');
00367   sink->Append(str);
00368   sink->Append(right_spaces, ' ');
00369 }
00370 
00371 template <typename Float>
00372 bool FloatToSink(const Float v, const ConversionSpec &conv,
00373                  FormatSinkImpl *sink) {
00374   // Print the sign or the sign column.
00375   Float abs_v = v;
00376   char sign_char = 0;
00377   if (std::signbit(abs_v)) {
00378     sign_char = '-';
00379     abs_v = -abs_v;
00380   } else if (conv.flags().show_pos) {
00381     sign_char = '+';
00382   } else if (conv.flags().sign_col) {
00383     sign_char = ' ';
00384   }
00385 
00386   // Print nan/inf.
00387   if (ConvertNonNumericFloats(sign_char, abs_v, conv, sink)) {
00388     return true;
00389   }
00390 
00391   int precision = conv.precision() < 0 ? 6 : conv.precision();
00392 
00393   int exp = 0;
00394 
00395   auto decomposed = Decompose(abs_v);
00396 
00397   Buffer buffer;
00398 
00399   switch (conv.conv().id()) {
00400     case ConversionChar::f:
00401     case ConversionChar::F:
00402       if (!FloatToBuffer<FormatStyle::Fixed>(decomposed, precision, &buffer,
00403                                              nullptr)) {
00404         return FallbackToSnprintf(v, conv, sink);
00405       }
00406       if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back();
00407       break;
00408 
00409     case ConversionChar::e:
00410     case ConversionChar::E:
00411       if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
00412                                                  &exp)) {
00413         return FallbackToSnprintf(v, conv, sink);
00414       }
00415       if (!conv.flags().alt && buffer.back() == '.') buffer.pop_back();
00416       PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer);
00417       break;
00418 
00419     case ConversionChar::g:
00420     case ConversionChar::G:
00421       precision = std::max(0, precision - 1);
00422       if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
00423                                                  &exp)) {
00424         return FallbackToSnprintf(v, conv, sink);
00425       }
00426       if (precision + 1 > exp && exp >= -4) {
00427         if (exp < 0) {
00428           // Have 1.23456, needs 0.00123456
00429           // Move the first digit
00430           buffer.begin[1] = *buffer.begin;
00431           // Add some zeros
00432           for (; exp < -1; ++exp) *buffer.begin-- = '0';
00433           *buffer.begin-- = '.';
00434           *buffer.begin = '0';
00435         } else if (exp > 0) {
00436           // Have 1.23456, needs 1234.56
00437           // Move the '.' exp positions to the right.
00438           std::rotate(buffer.begin + 1, buffer.begin + 2,
00439                       buffer.begin + exp + 2);
00440         }
00441         exp = 0;
00442       }
00443       if (!conv.flags().alt) {
00444         while (buffer.back() == '0') buffer.pop_back();
00445         if (buffer.back() == '.') buffer.pop_back();
00446       }
00447       if (exp) PrintExponent(exp, conv.conv().upper() ? 'E' : 'e', &buffer);
00448       break;
00449 
00450     case ConversionChar::a:
00451     case ConversionChar::A:
00452       return FallbackToSnprintf(v, conv, sink);
00453 
00454     default:
00455       return false;
00456   }
00457 
00458   WriteBufferToSink(sign_char,
00459                     string_view(buffer.begin, buffer.end - buffer.begin), conv,
00460                     sink);
00461 
00462   return true;
00463 }
00464 
00465 }  // namespace
00466 
00467 bool ConvertFloatImpl(long double v, const ConversionSpec &conv,
00468                       FormatSinkImpl *sink) {
00469   return FloatToSink(v, conv, sink);
00470 }
00471 
00472 bool ConvertFloatImpl(float v, const ConversionSpec &conv,
00473                       FormatSinkImpl *sink) {
00474   return FloatToSink(v, conv, sink);
00475 }
00476 
00477 bool ConvertFloatImpl(double v, const ConversionSpec &conv,
00478                       FormatSinkImpl *sink) {
00479   return FloatToSink(v, conv, sink);
00480 }
00481 
00482 }  // namespace str_format_internal
00483 }  // namespace absl


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:14