#include "absl/strings/internal/str_format/float_conversion.h"
#include <string.h>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <string>
#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/bits.h"
#include "absl/base/optimization.h"
#include "absl/functional/function_ref.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/int128.h"
#include "absl/types/optional.h"
#include "absl/types/span.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace str_format_internal {
namespace {
// The code below wants to avoid heap allocations.
// To do so it needs to allocate memory on the stack.
// `StackArray` will allocate memory on the stack in the form of a uint32_t
// array and call the provided callback with said memory.
// It will allocate memory in increments of 512 bytes. We could allocate the
// largest needed unconditionally, but that is more than we need in most of
// cases. This way we use less stack in the common cases.
class StackArray {
using Func = absl::FunctionRef<void(absl::Span<uint32_t>)>;
static constexpr size_t kStep = 512 / sizeof(uint32_t);
// 5 steps is 2560 bytes, which is enough to hold a long double with the
// largest/smallest exponents.
// The operations below will static_assert their particular maximum.
static constexpr size_t kNumSteps = 5;
// We do not want this function to be inlined.
// Otherwise the caller will allocate the stack space unnecessarily for all
// the variants even though it only calls one.
template <size_t steps>
ABSL_ATTRIBUTE_NOINLINE static void RunWithCapacityImpl(Func f) {
uint32_t values[steps * kStep]{};
f(absl::MakeSpan(values));
}
public:
static constexpr size_t kMaxCapacity = kStep * kNumSteps;
static void RunWithCapacity(size_t capacity, Func f) {
assert(capacity <= kMaxCapacity);
const size_t step = (capacity + kStep - 1) / kStep;
assert(step <= kNumSteps);
switch (step) {
case 1:
return RunWithCapacityImpl<1>(f);
case 2:
return RunWithCapacityImpl<2>(f);
case 3:
return RunWithCapacityImpl<3>(f);
case 4:
return RunWithCapacityImpl<4>(f);
case 5:
return RunWithCapacityImpl<5>(f);
}
assert(false && "Invalid capacity");
}
};
// Calculates `10 * (*v) + carry` and stores the result in `*v` and returns
// the carry.
template <typename Int>
inline Int MultiplyBy10WithCarry(Int *v, Int carry) {
using BiggerInt = absl::conditional_t<sizeof(Int) == 4, uint64_t, uint128>;
BiggerInt tmp = 10 * static_cast<BiggerInt>(*v) + carry;
*v = static_cast<Int>(tmp);
return static_cast<Int>(tmp >> (sizeof(Int) * 8));
}
// Calculates `(2^64 * carry + *v) / 10`.
// Stores the quotient in `*v` and returns the remainder.
// Requires: `0 <= carry <= 9`
inline uint64_t DivideBy10WithCarry(uint64_t *v, uint64_t carry) {
constexpr uint64_t divisor = 10;
// 2^64 / divisor = chunk_quotient + chunk_remainder / divisor
constexpr uint64_t chunk_quotient = (uint64_t{1} << 63) / (divisor / 2);
constexpr uint64_t chunk_remainder = uint64_t{} - chunk_quotient * divisor;
const uint64_t mod = *v % divisor;
const uint64_t next_carry = chunk_remainder * carry + mod;
*v = *v / divisor + carry * chunk_quotient + next_carry / divisor;
return next_carry % divisor;
}
// Generates the decimal representation for an integer of the form `v * 2^exp`,
// where `v` and `exp` are both positive integers.
// It generates the digits from the left (ie the most significant digit first)
// to allow for direct printing into the sink.
//
// Requires `0 <= exp` and `exp <= numeric_limits<long double>::max_exponent`.
class BinaryToDecimal {
static constexpr int ChunksNeeded(int exp) {
// We will left shift a uint128 by `exp` bits, so we need `128+exp` total
// bits. Round up to 32.
// See constructor for details about adding `10%` to the value.
return (128 + exp + 31) / 32 * 11 / 10;
}
public:
// Run the conversion for `v * 2^exp` and call `f(binary_to_decimal)`.
// This function will allocate enough stack space to perform the conversion.
static void RunConversion(uint128 v, int exp,
absl::FunctionRef<void(BinaryToDecimal)> f) {
assert(exp > 0);
assert(exp <= std::numeric_limits<long double>::max_exponent);
static_assert(
StackArray::kMaxCapacity >=
ChunksNeeded(std::numeric_limits<long double>::max_exponent),
"");
StackArray::RunWithCapacity(
ChunksNeeded(exp),
[=](absl::Span<uint32_t> input) { f(BinaryToDecimal(input, v, exp)); });
}
int TotalDigits() const {
return static_cast<int>((decimal_end_ - decimal_start_) * kDigitsPerChunk +
CurrentDigits().size());
}
// See the current block of digits.
absl::string_view CurrentDigits() const {
return absl::string_view(digits_ + kDigitsPerChunk - size_, size_);
}
// Advance the current view of digits.
// Returns `false` when no more digits are available.
bool AdvanceDigits() {
if (decimal_start_ >= decimal_end_) return false;
uint32_t w = data_[decimal_start_++];
for (size_ = 0; size_ < kDigitsPerChunk; w /= 10) {
digits_[kDigitsPerChunk - ++size_] = w % 10 + '0';
}
return true;
}
private:
BinaryToDecimal(absl::Span<uint32_t> data, uint128 v, int exp) : data_(data) {
// We need to print the digits directly into the sink object without
// buffering them all first. To do this we need two things:
// - to know the total number of digits to do padding when necessary
// - to generate the decimal digits from the left.
//
// In order to do this, we do a two pass conversion.
// On the first pass we convert the binary representation of the value into
// a decimal representation in which each uint32_t chunk holds up to 9
// decimal digits. In the second pass we take each decimal-holding-uint32_t
// value and generate the ascii decimal digits into `digits_`.
//
// The binary and decimal representations actually share the same memory
// region. As we go converting the chunks from binary to decimal we free
// them up and reuse them for the decimal representation. One caveat is that
// the decimal representation is around 7% less efficient in space than the
// binary one. We allocate an extra 10% memory to account for this. See
// ChunksNeeded for this calculation.
int chunk_index = exp / 32;
decimal_start_ = decimal_end_ = ChunksNeeded(exp);
const int offset = exp % 32;
// Left shift v by exp bits.
data_[chunk_index] = static_cast<uint32_t>(v << offset);
for (v >>= (32 - offset); v; v >>= 32)
data_[++chunk_index] = static_cast<uint32_t>(v);
while (chunk_index >= 0) {
// While we have more than one chunk available, go in steps of 1e9.
// `data_[chunk_index]` holds the highest non-zero binary chunk, so keep
// the variable updated.
uint32_t carry = 0;
for (int i = chunk_index; i >= 0; --i) {
uint64_t tmp = uint64_t{data_[i]} + (uint64_t{carry} << 32);
data_[i] = static_cast<uint32_t>(tmp / uint64_t{1000000000});
carry = static_cast<uint32_t>(tmp % uint64_t{1000000000});
}
// If the highest chunk is now empty, remove it from view.
if (data_[chunk_index] == 0) --chunk_index;
--decimal_start_;
assert(decimal_start_ != chunk_index);
data_[decimal_start_] = carry;
}
// Fill the first set of digits. The first chunk might not be complete, so
// handle differently.
for (uint32_t first = data_[decimal_start_++]; first != 0; first /= 10) {
digits_[kDigitsPerChunk - ++size_] = first % 10 + '0';
}
}
private:
static constexpr size_t kDigitsPerChunk = 9;
int decimal_start_;
int decimal_end_;
char digits_[kDigitsPerChunk];
int size_ = 0;
absl::Span<uint32_t> data_;
};
// Converts a value of the form `x * 2^-exp` into a sequence of decimal digits.
// Requires `-exp < 0` and
// `-exp >= limits<long double>::min_exponent - limits<long double>::digits`.
class FractionalDigitGenerator {
public:
// Run the conversion for `v * 2^exp` and call `f(generator)`.
// This function will allocate enough stack space to perform the conversion.
static void RunConversion(
uint128 v, int exp, absl::FunctionRef<void(FractionalDigitGenerator)> f) {
assert(-exp < 0);
assert(-exp >= std::numeric_limits<long double>::min_exponent - 128);
static_assert(
StackArray::kMaxCapacity >=
(128 - std::numeric_limits<long double>::min_exponent + 31) / 32,
"");
StackArray::RunWithCapacity((exp + 31) / 32,
[=](absl::Span<uint32_t> input) {
f(FractionalDigitGenerator(input, v, exp));
});
}
// Returns true if there are any more non-zero digits left.
bool HasMoreDigits() const { return next_digit_ != 0 || chunk_index_ >= 0; }
// Returns true if the remainder digits are greater than 5000...
bool IsGreaterThanHalf() const {
return next_digit_ > 5 || (next_digit_ == 5 && chunk_index_ >= 0);
}
// Returns true if the remainder digits are exactly 5000...
bool IsExactlyHalf() const { return next_digit_ == 5 && chunk_index_ < 0; }
struct Digits {
int digit_before_nine;
int num_nines;
};
// Get the next set of digits.
// They are composed by a non-9 digit followed by a runs of zero or more 9s.
Digits GetDigits() {
Digits digits{next_digit_, 0};
next_digit_ = GetOneDigit();
while (next_digit_ == 9) {
++digits.num_nines;
next_digit_ = GetOneDigit();
}
return digits;
}
private:
// Return the next digit.
int GetOneDigit() {
if (chunk_index_ < 0) return 0;
uint32_t carry = 0;
for (int i = chunk_index_; i >= 0; --i) {
carry = MultiplyBy10WithCarry(&data_[i], carry);
}
// If the lowest chunk is now empty, remove it from view.
if (data_[chunk_index_] == 0) --chunk_index_;
return carry;
}
FractionalDigitGenerator(absl::Span<uint32_t> data, uint128 v, int exp)
: chunk_index_(exp / 32), data_(data) {
const int offset = exp % 32;
// Right shift `v` by `exp` bits.
data_[chunk_index_] = static_cast<uint32_t>(v << (32 - offset));
v >>= offset;
// Make sure we don't overflow the data. We already calculated that
// non-zero bits fit, so we might not have space for leading zero bits.
for (int pos = chunk_index_; v; v >>= 32)
data_[--pos] = static_cast<uint32_t>(v);
// Fill next_digit_, as GetDigits expects it to be populated always.
next_digit_ = GetOneDigit();
}
int next_digit_;
int chunk_index_;
absl::Span<uint32_t> data_;
};
// Count the number of leading zero bits.
int LeadingZeros(uint64_t v) { return base_internal::CountLeadingZeros64(v); }
int LeadingZeros(uint128 v) {
auto high = static_cast<uint64_t>(v >> 64);
auto low = static_cast<uint64_t>(v);
return high != 0 ? base_internal::CountLeadingZeros64(high)
: 64 + base_internal::CountLeadingZeros64(low);
}
// Round up the text digits starting at `p`.
// The buffer must have an extra digit that is known to not need rounding.
// This is done below by having an extra '0' digit on the left.
void RoundUp(char *p) {
while (*p == '9' || *p == '.') {
if (*p == '9') *p = '0';
--p;
}
++*p;
}
// Check the previous digit and round up or down to follow the round-to-even
// policy.
void RoundToEven(char *p) {
if (*p == '.') --p;
if (*p % 2 == 1) RoundUp(p);
}
// Simple integral decimal digit printing for values that fit in 64-bits.
// Returns the pointer to the last written digit.
char *PrintIntegralDigitsFromRightFast(uint64_t v, char *p) {
do {
*--p = DivideBy10WithCarry(&v, 0) + '0';
} while (v != 0);
return p;
}
// Simple integral decimal digit printing for values that fit in 128-bits.
// Returns the pointer to the last written digit.
char *PrintIntegralDigitsFromRightFast(uint128 v, char *p) {
auto high = static_cast<uint64_t>(v >> 64);
auto low = static_cast<uint64_t>(v);
while (high != 0) {
uint64_t carry = DivideBy10WithCarry(&high, 0);
carry = DivideBy10WithCarry(&low, carry);
*--p = carry + '0';
}
return PrintIntegralDigitsFromRightFast(low, p);
}
// Simple fractional decimal digit printing for values that fir in 64-bits after
// shifting.
// Performs rounding if necessary to fit within `precision`.
// Returns the pointer to one after the last character written.
char *PrintFractionalDigitsFast(uint64_t v, char *start, int exp,
int precision) {
char *p = start;
v <<= (64 - exp);
while (precision > 0) {
if (!v) return p;
*p++ = MultiplyBy10WithCarry(&v, uint64_t{0}) + '0';
--precision;
}
// We need to round.
if (v < 0x8000000000000000) {
// We round down, so nothing to do.
} else if (v > 0x8000000000000000) {
// We round up.
RoundUp(p - 1);
} else {
RoundToEven(p - 1);
}
assert(precision == 0);
// Precision can only be zero here.
return p;
}
// Simple fractional decimal digit printing for values that fir in 128-bits
// after shifting.
// Performs rounding if necessary to fit within `precision`.
// Returns the pointer to one after the last character written.
char *PrintFractionalDigitsFast(uint128 v, char *start, int exp,
int precision) {
char *p = start;
v <<= (128 - exp);
auto high = static_cast<uint64_t>(v >> 64);
auto low = static_cast<uint64_t>(v);
// While we have digits to print and `low` is not empty, do the long
// multiplication.
while (precision > 0 && low != 0) {
uint64_t carry = MultiplyBy10WithCarry(&low, uint64_t{0});
carry = MultiplyBy10WithCarry(&high, carry);
*p++ = carry + '0';
--precision;
}
// Now `low` is empty, so use a faster approach for the rest of the digits.
// This block is pretty much the same as the main loop for the 64-bit case
// above.
while (precision > 0) {
if (!high) return p;
*p++ = MultiplyBy10WithCarry(&high, uint64_t{0}) + '0';
--precision;
}
// We need to round.
if (high < 0x8000000000000000) {
// We round down, so nothing to do.
} else if (high > 0x8000000000000000 || low != 0) {
// We round up.
RoundUp(p - 1);
} else {
RoundToEven(p - 1);
}
assert(precision == 0);
// Precision can only be zero here.
return p;
}
struct FormatState {
char sign_char;
int precision;
const FormatConversionSpecImpl &conv;
FormatSinkImpl *sink;
// In `alt` mode (flag #) we keep the `.` even if there are no fractional
// digits. In non-alt mode, we strip it.
bool ShouldPrintDot() const { return precision != 0 || conv.has_alt_flag(); }
};
struct Padding {
int left_spaces;
int zeros;
int right_spaces;
};
Padding ExtraWidthToPadding(int total_size, const FormatState &state) {
int missing_chars = std::max(state.conv.width() - total_size, 0);
if (state.conv.has_left_flag()) {
return {0, 0, missing_chars};
} else if (state.conv.has_zero_flag()) {
return {0, missing_chars, 0};
} else {
return {missing_chars, 0, 0};
}
}
void FinalPrint(absl::string_view data, int trailing_zeros,
const FormatState &state) {
if (state.conv.width() < 0) {
// No width specified. Fast-path.
if (state.sign_char != '\0') state.sink->Append(1, state.sign_char);
state.sink->Append(data);
state.sink->Append(trailing_zeros, '0');
return;
}
auto padding =
ExtraWidthToPadding((state.sign_char != '\0' ? 1 : 0) +
static_cast<int>(data.size()) + trailing_zeros,
state);
state.sink->Append(padding.left_spaces, ' ');
if (state.sign_char != '\0') state.sink->Append(1, state.sign_char);
state.sink->Append(padding.zeros, '0');
state.sink->Append(data);
state.sink->Append(trailing_zeros, '0');
state.sink->Append(padding.right_spaces, ' ');
}
// Fastpath %f formatter for when the shifted value fits in a simple integral
// type.
// Prints `v*2^exp` with the options from `state`.
template <typename Int>
void FormatFFast(Int v, int exp, const FormatState &state) {
constexpr int input_bits = sizeof(Int) * 8;
static constexpr size_t integral_size =
/* in case we need to round up an extra digit */ 1 +
/* decimal digits for uint128 */ 40 + 1;
char buffer[integral_size + /* . */ 1 + /* max digits uint128 */ 128];
buffer[integral_size] = '.';
char *const integral_digits_end = buffer + integral_size;
char *integral_digits_start;
char *const fractional_digits_start = buffer + integral_size + 1;
char *fractional_digits_end = fractional_digits_start;
if (exp >= 0) {
const int total_bits = input_bits - LeadingZeros(v) + exp;
integral_digits_start =
total_bits <= 64
? PrintIntegralDigitsFromRightFast(static_cast<uint64_t>(v) << exp,
integral_digits_end)
: PrintIntegralDigitsFromRightFast(static_cast<uint128>(v) << exp,
integral_digits_end);
} else {
exp = -exp;
integral_digits_start = PrintIntegralDigitsFromRightFast(
exp < input_bits ? v >> exp : 0, integral_digits_end);
// PrintFractionalDigits may pull a carried 1 all the way up through the
// integral portion.
integral_digits_start[-1] = '0';
fractional_digits_end =
exp <= 64 ? PrintFractionalDigitsFast(v, fractional_digits_start, exp,
state.precision)
: PrintFractionalDigitsFast(static_cast<uint128>(v),
fractional_digits_start, exp,
state.precision);
// There was a carry, so include the first digit too.
if (integral_digits_start[-1] != '0') --integral_digits_start;
}
size_t size = fractional_digits_end - integral_digits_start;
// In `alt` mode (flag #) we keep the `.` even if there are no fractional
// digits. In non-alt mode, we strip it.
if (!state.ShouldPrintDot()) --size;
FinalPrint(absl::string_view(integral_digits_start, size),
static_cast<int>(state.precision - (fractional_digits_end -
fractional_digits_start)),
state);
}
// Slow %f formatter for when the shifted value does not fit in a uint128, and
// `exp > 0`.
// Prints `v*2^exp` with the options from `state`.
// This one is guaranteed to not have fractional digits, so we don't have to
// worry about anything after the `.`.
void FormatFPositiveExpSlow(uint128 v, int exp, const FormatState &state) {
BinaryToDecimal::RunConversion(v, exp, [&](BinaryToDecimal btd) {
const int total_digits =
btd.TotalDigits() + (state.ShouldPrintDot() ? state.precision + 1 : 0);
const auto padding = ExtraWidthToPadding(
total_digits + (state.sign_char != '\0' ? 1 : 0), state);
state.sink->Append(padding.left_spaces, ' ');
if (state.sign_char != '\0') state.sink->Append(1, state.sign_char);
state.sink->Append(padding.zeros, '0');
do {
state.sink->Append(btd.CurrentDigits());
} while (btd.AdvanceDigits());
if (state.ShouldPrintDot()) state.sink->Append(1, '.');
state.sink->Append(state.precision, '0');
state.sink->Append(padding.right_spaces, ' ');
});
}
// Slow %f formatter for when the shifted value does not fit in a uint128, and
// `exp < 0`.
// Prints `v*2^exp` with the options from `state`.
// This one is guaranteed to be < 1.0, so we don't have to worry about integral
// digits.
void FormatFNegativeExpSlow(uint128 v, int exp, const FormatState &state) {
const int total_digits =
/* 0 */ 1 + (state.ShouldPrintDot() ? state.precision + 1 : 0);
auto padding =
ExtraWidthToPadding(total_digits + (state.sign_char ? 1 : 0), state);
padding.zeros += 1;
state.sink->Append(padding.left_spaces, ' ');
if (state.sign_char != '\0') state.sink->Append(1, state.sign_char);
state.sink->Append(padding.zeros, '0');
if (state.ShouldPrintDot()) state.sink->Append(1, '.');
// Print digits
int digits_to_go = state.precision;
FractionalDigitGenerator::RunConversion(
v, exp, [&](FractionalDigitGenerator digit_gen) {
// There are no digits to print here.
if (state.precision == 0) return;
// We go one digit at a time, while keeping track of runs of nines.
// The runs of nines are used to perform rounding when necessary.
while (digits_to_go > 0 && digit_gen.HasMoreDigits()) {
auto digits = digit_gen.GetDigits();
// Now we have a digit and a run of nines.
// See if we can print them all.
if (digits.num_nines + 1 < digits_to_go) {
// We don't have to round yet, so print them.
state.sink->Append(1, digits.digit_before_nine + '0');
state.sink->Append(digits.num_nines, '9');
digits_to_go -= digits.num_nines + 1;
} else {
// We can't print all the nines, see where we have to truncate.
bool round_up = false;
if (digits.num_nines + 1 > digits_to_go) {
// We round up at a nine. No need to print them.
round_up = true;
} else {
// We can fit all the nines, but truncate just after it.
if (digit_gen.IsGreaterThanHalf()) {
round_up = true;
} else if (digit_gen.IsExactlyHalf()) {
// Round to even
round_up =
digits.num_nines != 0 || digits.digit_before_nine % 2 == 1;
}
}
if (round_up) {
state.sink->Append(1, digits.digit_before_nine + '1');
--digits_to_go;
// The rest will be zeros.
} else {
state.sink->Append(1, digits.digit_before_nine + '0');
state.sink->Append(digits_to_go - 1, '9');
digits_to_go = 0;
}
return;
}
}
});
state.sink->Append(digits_to_go, '0');
state.sink->Append(padding.right_spaces, ' ');
}
template <typename Int>
void FormatF(Int mantissa, int exp, const FormatState &state) {
if (exp >= 0) {
const int total_bits = sizeof(Int) * 8 - LeadingZeros(mantissa) + exp;
// Fallback to the slow stack-based approach if we can't do it in a 64 or
// 128 bit state.
if (ABSL_PREDICT_FALSE(total_bits > 128)) {
return FormatFPositiveExpSlow(mantissa, exp, state);
}
} else {
// Fallback to the slow stack-based approach if we can't do it in a 64 or
// 128 bit state.
if (ABSL_PREDICT_FALSE(exp < -128)) {
return FormatFNegativeExpSlow(mantissa, -exp, state);
}
}
return FormatFFast(mantissa, exp, state);
}
char *CopyStringTo(absl::string_view v, char *out) {
std::memcpy(out, v.data(), v.size());
return out + v.size();
}
template <typename Float>
bool FallbackToSnprintf(const Float v, const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
int w = conv.width() >= 0 ? conv.width() : 0;
int p = conv.precision() >= 0 ? conv.precision() : -1;
char fmt[32];
{
char *fp = fmt;
*fp++ = '%';
fp = CopyStringTo(FormatConversionSpecImplFriend::FlagsToString(conv), fp);
fp = CopyStringTo("*.*", fp);
if (std::is_same<long double, Float>()) {
*fp++ = 'L';
}
*fp++ = FormatConversionCharToChar(conv.conversion_char());
*fp = 0;
assert(fp < fmt + sizeof(fmt));
}
std::string space(512, '\0');
absl::string_view result;
while (true) {
int n = snprintf(&space[0], space.size(), fmt, w, p, v);
if (n < 0) return false;
if (static_cast<size_t>(n) < space.size()) {
result = absl::string_view(space.data(), n);
break;
}
space.resize(n + 1);
}
sink->Append(result);
return true;
}
// 128-bits in decimal: ceil(128*log(2)/log(10))
// or std::numeric_limits<__uint128_t>::digits10
constexpr int kMaxFixedPrecision = 39;
constexpr int kBufferLength = /*sign*/ 1 +
/*integer*/ kMaxFixedPrecision +
/*point*/ 1 +
/*fraction*/ kMaxFixedPrecision +
/*exponent e+123*/ 5;
struct Buffer {
void push_front(char c) {
assert(begin > data);
*--begin = c;
}
void push_back(char c) {
assert(end < data + sizeof(data));
*end++ = c;
}
void pop_back() {
assert(begin < end);
--end;
}
char &back() {
assert(begin < end);
return end[-1];
}
char last_digit() const { return end[-1] == '.' ? end[-2] : end[-1]; }
int size() const { return static_cast<int>(end - begin); }
char data[kBufferLength];
char *begin;
char *end;
};
enum class FormatStyle { Fixed, Precision };
// If the value is Inf or Nan, print it and return true.
// Otherwise, return false.
template <typename Float>
bool ConvertNonNumericFloats(char sign_char, Float v,
const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
char text[4], *ptr = text;
if (sign_char != '\0') *ptr++ = sign_char;
if (std::isnan(v)) {
ptr = std::copy_n(
FormatConversionCharIsUpper(conv.conversion_char()) ? "NAN" : "nan", 3,
ptr);
} else if (std::isinf(v)) {
ptr = std::copy_n(
FormatConversionCharIsUpper(conv.conversion_char()) ? "INF" : "inf", 3,
ptr);
} else {
return false;
}
return sink->PutPaddedString(string_view(text, ptr - text), conv.width(), -1,
conv.has_left_flag());
}
// Round up the last digit of the value.
// It will carry over and potentially overflow. 'exp' will be adjusted in that
// case.
template <FormatStyle mode>
void RoundUp(Buffer *buffer, int *exp) {
char *p = &buffer->back();
while (p >= buffer->begin && (*p == '9' || *p == '.')) {
if (*p == '9') *p = '0';
--p;
}
if (p < buffer->begin) {
*p = '1';
buffer->begin = p;
if (mode == FormatStyle::Precision) {
std::swap(p[1], p[2]); // move the .
++*exp;
buffer->pop_back();
}
} else {
++*p;
}
}
void PrintExponent(int exp, char e, Buffer *out) {
out->push_back(e);
if (exp < 0) {
out->push_back('-');
exp = -exp;
} else {
out->push_back('+');
}
// Exponent digits.
if (exp > 99) {
out->push_back(exp / 100 + '0');
out->push_back(exp / 10 % 10 + '0');
out->push_back(exp % 10 + '0');
} else {
out->push_back(exp / 10 + '0');
out->push_back(exp % 10 + '0');
}
}
template <typename Float, typename Int>
constexpr bool CanFitMantissa() {
return
#if defined(__clang__) && !defined(__SSE3__)
// Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289
// Casting from long double to uint64_t is miscompiled and drops bits.
(!std::is_same<Float, long double>::value ||
!std::is_same<Int, uint64_t>::value) &&
#endif
std::numeric_limits<Float>::digits <= std::numeric_limits<Int>::digits;
}
template <typename Float>
struct Decomposed {
using MantissaType =
absl::conditional_t<std::is_same<long double, Float>::value, uint128,
uint64_t>;
static_assert(std::numeric_limits<Float>::digits <= sizeof(MantissaType) * 8,
"");
MantissaType mantissa;
int exponent;
};
// Decompose the double into an integer mantissa and an exponent.
template <typename Float>
Decomposed<Float> Decompose(Float v) {
int exp;
Float m = std::frexp(v, &exp);
m = std::ldexp(m, std::numeric_limits<Float>::digits);
exp -= std::numeric_limits<Float>::digits;
return {static_cast<typename Decomposed<Float>::MantissaType>(m), exp};
}
// Print 'digits' as decimal.
// In Fixed mode, we add a '.' at the end.
// In Precision mode, we add a '.' after the first digit.
template <FormatStyle mode, typename Int>
int PrintIntegralDigits(Int digits, Buffer *out) {
int printed = 0;
if (digits) {
for (; digits; digits /= 10) out->push_front(digits % 10 + '0');
printed = out->size();
if (mode == FormatStyle::Precision) {
out->push_front(*out->begin);
out->begin[1] = '.';
} else {
out->push_back('.');
}
} else if (mode == FormatStyle::Fixed) {
out->push_front('0');
out->push_back('.');
printed = 1;
}
return printed;
}
// Back out 'extra_digits' digits and round up if necessary.
bool RemoveExtraPrecision(int extra_digits, bool has_leftover_value,
Buffer *out, int *exp_out) {
if (extra_digits <= 0) return false;
// Back out the extra digits
out->end -= extra_digits;
bool needs_to_round_up = [&] {
// We look at the digit just past the end.
// There must be 'extra_digits' extra valid digits after end.
if (*out->end > '5') return true;
if (*out->end < '5') return false;
if (has_leftover_value || std::any_of(out->end + 1, out->end + extra_digits,
[](char c) { return c != '0'; }))
return true;
// Ends in ...50*, round to even.
return out->last_digit() % 2 == 1;
}();
if (needs_to_round_up) {
RoundUp<FormatStyle::Precision>(out, exp_out);
}
return true;
}
// Print the value into the buffer.
// This will not include the exponent, which will be returned in 'exp_out' for
// Precision mode.
template <typename Int, typename Float, FormatStyle mode>
bool FloatToBufferImpl(Int int_mantissa, int exp, int precision, Buffer *out,
int *exp_out) {
assert((CanFitMantissa<Float, Int>()));
const int int_bits = std::numeric_limits<Int>::digits;
// In precision mode, we start printing one char to the right because it will
// also include the '.'
// In fixed mode we put the dot afterwards on the right.
out->begin = out->end =
out->data + 1 + kMaxFixedPrecision + (mode == FormatStyle::Precision);
if (exp >= 0) {
if (std::numeric_limits<Float>::digits + exp > int_bits) {
// The value will overflow the Int
return false;
}
int digits_printed = PrintIntegralDigits<mode>(int_mantissa << exp, out);
int digits_to_zero_pad = precision;
if (mode == FormatStyle::Precision) {
*exp_out = digits_printed - 1;
digits_to_zero_pad -= digits_printed - 1;
if (RemoveExtraPrecision(-digits_to_zero_pad, false, out, exp_out)) {
return true;
}
}
for (; digits_to_zero_pad-- > 0;) out->push_back('0');
return true;
}
exp = -exp;
// We need at least 4 empty bits for the next decimal digit.
// We will multiply by 10.
if (exp > int_bits - 4) return false;
const Int mask = (Int{1} << exp) - 1;
// Print the integral part first.
int digits_printed = PrintIntegralDigits<mode>(int_mantissa >> exp, out);
int_mantissa &= mask;
int fractional_count = precision;
if (mode == FormatStyle::Precision) {
if (digits_printed == 0) {
// Find the first non-zero digit, when in Precision mode.
*exp_out = 0;
if (int_mantissa) {
while (int_mantissa <= mask) {
int_mantissa *= 10;
--*exp_out;
}
}
out->push_front(static_cast<char>(int_mantissa >> exp) + '0');
out->push_back('.');
int_mantissa &= mask;
} else {
// We already have a digit, and a '.'
*exp_out = digits_printed - 1;
fractional_count -= *exp_out;
if (RemoveExtraPrecision(-fractional_count, int_mantissa != 0, out,
exp_out)) {
// If we had enough digits, return right away.
// The code below will try to round again otherwise.
return true;
}
}
}
auto get_next_digit = [&] {
int_mantissa *= 10;
int digit = static_cast<int>(int_mantissa >> exp);
int_mantissa &= mask;
return digit;
};
// Print fractional_count more digits, if available.
for (; fractional_count > 0; --fractional_count) {
out->push_back(get_next_digit() + '0');
}
int next_digit = get_next_digit();
if (next_digit > 5 ||
(next_digit == 5 && (int_mantissa || out->last_digit() % 2 == 1))) {
RoundUp<mode>(out, exp_out);
}
return true;
}
template <FormatStyle mode, typename Float>
bool FloatToBuffer(Decomposed<Float> decomposed, int precision, Buffer *out,
int *exp) {
if (precision > kMaxFixedPrecision) return false;
// Try with uint64_t.
if (CanFitMantissa<Float, std::uint64_t>() &&
FloatToBufferImpl<std::uint64_t, Float, mode>(
static_cast<std::uint64_t>(decomposed.mantissa),
static_cast<std::uint64_t>(decomposed.exponent), precision, out, exp))
return true;
#if defined(ABSL_HAVE_INTRINSIC_INT128)
// If that is not enough, try with __uint128_t.
return CanFitMantissa<Float, __uint128_t>() &&
FloatToBufferImpl<__uint128_t, Float, mode>(
static_cast<__uint128_t>(decomposed.mantissa),
static_cast<__uint128_t>(decomposed.exponent), precision, out,
exp);
#endif
return false;
}
void WriteBufferToSink(char sign_char, absl::string_view str,
const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
int left_spaces = 0, zeros = 0, right_spaces = 0;
int missing_chars =
conv.width() >= 0 ? std::max(conv.width() - static_cast<int>(str.size()) -
static_cast<int>(sign_char != 0),
0)
: 0;
if (conv.has_left_flag()) {
right_spaces = missing_chars;
} else if (conv.has_zero_flag()) {
zeros = missing_chars;
} else {
left_spaces = missing_chars;
}
sink->Append(left_spaces, ' ');
if (sign_char != '\0') sink->Append(1, sign_char);
sink->Append(zeros, '0');
sink->Append(str);
sink->Append(right_spaces, ' ');
}
template <typename Float>
bool FloatToSink(const Float v, const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
// Print the sign or the sign column.
Float abs_v = v;
char sign_char = 0;
if (std::signbit(abs_v)) {
sign_char = '-';
abs_v = -abs_v;
} else if (conv.has_show_pos_flag()) {
sign_char = '+';
} else if (conv.has_sign_col_flag()) {
sign_char = ' ';
}
// Print nan/inf.
if (ConvertNonNumericFloats(sign_char, abs_v, conv, sink)) {
return true;
}
int precision = conv.precision() < 0 ? 6 : conv.precision();
int exp = 0;
auto decomposed = Decompose(abs_v);
Buffer buffer;
FormatConversionChar c = conv.conversion_char();
if (c == FormatConversionCharInternal::f ||
c == FormatConversionCharInternal::F) {
FormatF(decomposed.mantissa, decomposed.exponent,
{sign_char, precision, conv, sink});
return true;
} else if (c == FormatConversionCharInternal::e ||
c == FormatConversionCharInternal::E) {
if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
&exp)) {
return FallbackToSnprintf(v, conv, sink);
}
if (!conv.has_alt_flag() && buffer.back() == '.') buffer.pop_back();
PrintExponent(
exp, FormatConversionCharIsUpper(conv.conversion_char()) ? 'E' : 'e',
&buffer);
} else if (c == FormatConversionCharInternal::g ||
c == FormatConversionCharInternal::G) {
precision = std::max(0, precision - 1);
if (!FloatToBuffer<FormatStyle::Precision>(decomposed, precision, &buffer,
&exp)) {
return FallbackToSnprintf(v, conv, sink);
}
if (precision + 1 > exp && exp >= -4) {
if (exp < 0) {
// Have 1.23456, needs 0.00123456
// Move the first digit
buffer.begin[1] = *buffer.begin;
// Add some zeros
for (; exp < -1; ++exp) *buffer.begin-- = '0';
*buffer.begin-- = '.';
*buffer.begin = '0';
} else if (exp > 0) {
// Have 1.23456, needs 1234.56
// Move the '.' exp positions to the right.
std::rotate(buffer.begin + 1, buffer.begin + 2, buffer.begin + exp + 2);
}
exp = 0;
}
if (!conv.has_alt_flag()) {
while (buffer.back() == '0') buffer.pop_back();
if (buffer.back() == '.') buffer.pop_back();
}
if (exp) {
PrintExponent(
exp, FormatConversionCharIsUpper(conv.conversion_char()) ? 'E' : 'e',
&buffer);
}
} else if (c == FormatConversionCharInternal::a ||
c == FormatConversionCharInternal::A) {
return FallbackToSnprintf(v, conv, sink);
} else {
return false;
}
WriteBufferToSink(sign_char,
absl::string_view(buffer.begin, buffer.end - buffer.begin),
conv, sink);
return true;
}
} // namespace
bool ConvertFloatImpl(long double v, const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
if (std::numeric_limits<long double>::digits ==
2 * std::numeric_limits<double>::digits) {
// This is the `double-double` representation of `long double`.
// We do not handle it natively. Fallback to snprintf.
return FallbackToSnprintf(v, conv, sink);
}
return FloatToSink(v, conv, sink);
}
bool ConvertFloatImpl(float v, const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
return FloatToSink(v, conv, sink);
}
bool ConvertFloatImpl(double v, const FormatConversionSpecImpl &conv,
FormatSinkImpl *sink) {
return FloatToSink(v, conv, sink);
}
} // namespace str_format_internal
ABSL_NAMESPACE_END
} // namespace absl