chromium/third_party/fast_float/src/include/fast_float/bigint.h

#ifndef FASTFLOAT_BIGINT_H
#define FASTFLOAT_BIGINT_H

#include <algorithm>
#include <cstdint>
#include <climits>
#include <cstring>

#include "float_common.h"

namespace fast_float {

// the limb width: we want efficient multiplication of double the bits in
// limb, or for 64-bit limbs, at least 64-bit multiplication where we can
// extract the high and low parts efficiently. this is every 64-bit
// architecture except for sparc, which emulates 128-bit multiplication.
// we might have platforms where `CHAR_BIT` is not 8, so let's avoid
// doing `8 * sizeof(limb)`.
#if defined(FASTFLOAT_64BIT) && !defined(__sparc)
#define FASTFLOAT_64BIT_LIMB …
limb;
constexpr size_t limb_bits = …;
#else
#define FASTFLOAT_32BIT_LIMB
typedef uint32_t limb;
constexpr size_t limb_bits = 32;
#endif

limb_span;

// number of bits in a bigint. this needs to be at least the number
// of bits required to store the largest bigint, which is
// `log2(10**(digits + max_exp))`, or `log2(10**(767 + 342))`, or
// ~3600 bits, so we round to 4000.
constexpr size_t bigint_bits = …;
constexpr size_t bigint_limbs = …;

// vector-like type that is allocated on the stack. the entire
// buffer is pre-allocated, and only the length changes.
template <uint16_t size> struct stackvec { … };

fastfloat_really_inline FASTFLOAT_CONSTEXPR14 uint64_t
empty_hi64(bool &truncated) noexcept { … }

fastfloat_really_inline FASTFLOAT_CONSTEXPR20 uint64_t
uint64_hi64(uint64_t r0, bool &truncated) noexcept { … }

fastfloat_really_inline FASTFLOAT_CONSTEXPR20 uint64_t
uint64_hi64(uint64_t r0, uint64_t r1, bool &truncated) noexcept { … }

fastfloat_really_inline FASTFLOAT_CONSTEXPR20 uint64_t
uint32_hi64(uint32_t r0, bool &truncated) noexcept { … }

fastfloat_really_inline FASTFLOAT_CONSTEXPR20 uint64_t
uint32_hi64(uint32_t r0, uint32_t r1, bool &truncated) noexcept { … }

fastfloat_really_inline FASTFLOAT_CONSTEXPR20 uint64_t
uint32_hi64(uint32_t r0, uint32_t r1, uint32_t r2, bool &truncated) noexcept { … }

// add two small integers, checking for overflow.
// we want an efficient operation. for msvc, where
// we don't have built-in intrinsics, this is still
// pretty fast.
fastfloat_really_inline FASTFLOAT_CONSTEXPR20 limb
scalar_add(limb x, limb y, bool &overflow) noexcept { … }

// multiply two small integers, getting both the high and low bits.
fastfloat_really_inline FASTFLOAT_CONSTEXPR20 limb
scalar_mul(limb x, limb y, limb &carry) noexcept { … }

// add scalar value to bigint starting from offset.
// used in grade school multiplication
template <uint16_t size>
inline FASTFLOAT_CONSTEXPR20 bool small_add_from(stackvec<size> &vec, limb y,
                                                 size_t start) noexcept { … }

// add scalar value to bigint.
template <uint16_t size>
fastfloat_really_inline FASTFLOAT_CONSTEXPR20 bool
small_add(stackvec<size> &vec, limb y) noexcept { … }

// multiply bigint by scalar value.
template <uint16_t size>
inline FASTFLOAT_CONSTEXPR20 bool small_mul(stackvec<size> &vec,
                                            limb y) noexcept { … }

// add bigint to bigint starting from index.
// used in grade school multiplication
template <uint16_t size>
FASTFLOAT_CONSTEXPR20 bool large_add_from(stackvec<size> &x, limb_span y,
                                          size_t start) noexcept { … }

// add bigint to bigint.
template <uint16_t size>
fastfloat_really_inline FASTFLOAT_CONSTEXPR20 bool
large_add_from(stackvec<size> &x, limb_span y) noexcept { … }

// grade-school multiplication algorithm
template <uint16_t size>
FASTFLOAT_CONSTEXPR20 bool long_mul(stackvec<size> &x, limb_span y) noexcept { … }

// grade-school multiplication algorithm
template <uint16_t size>
FASTFLOAT_CONSTEXPR20 bool large_mul(stackvec<size> &x, limb_span y) noexcept { … }

template <typename = void> struct pow5_tables { … };

template <typename T> constexpr uint32_t pow5_tables<T>::large_step;

template <typename T> constexpr uint64_t pow5_tables<T>::small_power_of_5[];

template <typename T> constexpr limb pow5_tables<T>::large_power_of_5[];

// big integer type. implements a small subset of big integer
// arithmetic, using simple algorithms since asymptotically
// faster algorithms are slower for a small number of limbs.
// all operations assume the big-integer is normalized.
struct bigint : pow5_tables<> { … };

} // namespace fast_float

#endif