float_conversion.cc | Explore in Territory

// Copyright 2020 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#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/optimization.h"
#include "absl/functional/function_ref.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/bits.h"
#include "absl/numeric/int128.h"
#include "absl/numeric/internal/representation.h"
#include "absl/strings/numbers.h"
#include "absl/types/optional.h"
#include "absl/types/span.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace str_format_internal {

namespace {

IsDoubleDouble;

// 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 { … };

// Calculates `10 * (*v) + carry` and stores the result in `*v` and returns
// the carry.
// Requires: `0 <= carry <= 9`
template <typename Int>
inline char MultiplyBy10WithCarry(Int* v, char carry) { … }

// Calculates `(2^64 * carry + *v) / 10`.
// Stores the quotient in `*v` and returns the remainder.
// Requires: `0 <= carry <= 9`
inline char DivideBy10WithCarry(uint64_t* v, char carry) { … }

MaxFloatType;

// 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<MaxFloatType>::max_exponent`.
class BinaryToDecimal { … };

// Converts a value of the form `x * 2^-exp` into a sequence of decimal digits.
// Requires `-exp < 0` and
// `-exp >= limits<MaxFloatType>::min_exponent - limits<MaxFloatType>::digits`.
class FractionalDigitGenerator { … };

// Count the number of leading zero bits.
int LeadingZeros(uint64_t v) { … }
int LeadingZeros(uint128 v) { … }

// 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) { … }

// Check the previous digit and round up or down to follow the round-to-even
// policy.
void RoundToEven(char *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) { … }

// 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) { … }

// 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,
                                size_t precision) { … }

// 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,
                                size_t precision) { … }

struct FormatState { … };

struct Padding { … };

Padding ExtraWidthToPadding(size_t total_size, const FormatState &state) { … }

void FinalPrint(const FormatState& state,
                absl::string_view data,
                size_t padding_offset,
                size_t trailing_zeros,
                absl::string_view data_postfix) { … }

// 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) { … }

// 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) { … }

// 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) { … }

template <typename Int>
void FormatF(Int mantissa, int exp, const FormatState &state) { … }

// Grab the group of four bits (nibble) from `n`. E.g., nibble 1 corresponds to
// bits 4-7.
template <typename Int>
uint8_t GetNibble(Int n, size_t nibble_index) { … }

// Add one to the given nibble, applying carry to higher nibbles. Returns true
// if overflow, false otherwise.
template <typename Int>
bool IncrementNibble(size_t nibble_index, Int* n) { … }

// Return a mask with 1's in the given nibble and all lower nibbles.
template <typename Int>
Int MaskUpToNibbleInclusive(size_t nibble_index) { … }

// Return a mask with 1's below the given nibble.
template <typename Int>
Int MaskUpToNibbleExclusive(size_t nibble_index) { … }

template <typename Int>
Int MoveToNibble(uint8_t nibble, size_t nibble_index) { … }

// Given mantissa size, find optimal # of mantissa bits to put in initial digit.
//
// In the hex representation we keep a single hex digit to the left of the dot.
// However, the question as to how many bits of the mantissa should be put into
// that hex digit in theory is arbitrary, but in practice it is optimal to
// choose based on the size of the mantissa. E.g., for a `double`, there are 53
// mantissa bits, so that means that we should put 1 bit to the left of the dot,
// thereby leaving 52 bits to the right, which is evenly divisible by four and
// thus all fractional digits represent actual precision. For a `long double`,
// on the other hand, there are 64 bits of mantissa, thus we can use all four
// bits for the initial hex digit and still have a number left over (60) that is
// a multiple of four. Once again, the goal is to have all fractional digits
// represent real precision.
template <typename Float>
constexpr size_t HexFloatLeadingDigitSizeInBits() { … }

// This function captures the rounding behavior of glibc for hex float
// representations. E.g. when rounding 0x1.ab800000 to a precision of .2
// ("%.2a") glibc will round up because it rounds toward the even number (since
// 0xb is an odd number, it will round up to 0xc). However, when rounding at a
// point that is not followed by 800000..., it disregards the parity and rounds
// up if > 8 and rounds down if < 8.
template <typename Int>
bool HexFloatNeedsRoundUp(Int mantissa,
                          size_t final_nibble_displayed,
                          uint8_t leading) { … }

// Stores values associated with a Float type needed by the FormatA
// implementation in order to avoid templatizing that function by the Float
// type.
struct HexFloatTypeParams { … };

// Hex Float Rounding. First check if we need to round; if so, then we do that
// by manipulating (incrementing) the mantissa, that way we can later print the
// mantissa digits by iterating through them in the same way regardless of
// whether a rounding happened.
template <typename Int>
void FormatARound(bool precision_specified, const FormatState &state,
                  uint8_t *leading, Int *mantissa, int *exp) { … }

template <typename Int>
void FormatANormalize(const HexFloatTypeParams float_traits, uint8_t *leading,
                      Int *mantissa, int *exp) { … }

template <typename Int>
void FormatA(const HexFloatTypeParams float_traits, Int mantissa, int exp,
             bool uppercase, const FormatState &state) { … }

char *CopyStringTo(absl::string_view v, char *out) { … }

template <typename Float>
bool FallbackToSnprintf(const Float v, const FormatConversionSpecImpl &conv,
                        FormatSinkImpl *sink) { … }

// 128-bits in decimal: ceil(128*log(2)/log(10))
//   or std::numeric_limits<__uint128_t>::digits10
constexpr size_t kMaxFixedPrecision = …;

constexpr size_t kBufferLength = …/*sign*/ 1 +
                                 /*integer*/ kMaxFixedPrecision +
                                 /*point*/ 1 +
                                 /*fraction*/ kMaxFixedPrecision +
                                 /*exponent e+123*/ 5;

struct Buffer { … };

enum class FormatStyle { … };

// 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) { … }

// 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) { … }

void PrintExponent(int exp, char e, Buffer *out) { … }

template <typename Float, typename Int>
constexpr bool CanFitMantissa() { … }

template <typename Float>
struct Decomposed { … };

// Decompose the double into an integer mantissa and an exponent.
template <typename Float>
Decomposed<Float> Decompose(Float v) { … }

// 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>
size_t PrintIntegralDigits(Int digits, Buffer* out) { … }

// Back out 'extra_digits' digits and round up if necessary.
void RemoveExtraPrecision(size_t extra_digits,
                          bool has_leftover_value,
                          Buffer* out,
                          int* exp_out) { … }

// 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,
                       size_t precision,
                       Buffer* out,
                       int* exp_out) { … }

template <FormatStyle mode, typename Float>
bool FloatToBuffer(Decomposed<Float> decomposed,
                   size_t precision,
                   Buffer* out,
                   int* exp) { … }

void WriteBufferToSink(char sign_char, absl::string_view str,
                       const FormatConversionSpecImpl &conv,
                       FormatSinkImpl *sink) { … }

template <typename Float>
bool FloatToSink(const Float v, const FormatConversionSpecImpl &conv,
                 FormatSinkImpl *sink) { … }

}  // namespace

bool ConvertFloatImpl(long double v, const FormatConversionSpecImpl &conv,
                      FormatSinkImpl *sink) { … }

bool ConvertFloatImpl(float v, const FormatConversionSpecImpl &conv,
                      FormatSinkImpl *sink) { … }

bool ConvertFloatImpl(double v, const FormatConversionSpecImpl &conv,
                      FormatSinkImpl *sink) { … }

}  // namespace str_format_internal
ABSL_NAMESPACE_END
}  // namespace absl
chromium/third_party/abseil-cpp/absl/strings/internal/str_format/float_conversion.cc
