llvm/libc/src/__support/big_int.h

//===-- A class to manipulate wide integers. --------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC___SUPPORT_UINT_H
#define LLVM_LIBC_SRC___SUPPORT_UINT_H

#include "src/__support/CPP/array.h"
#include "src/__support/CPP/bit.h" // countl_zero
#include "src/__support/CPP/limits.h"
#include "src/__support/CPP/optional.h"
#include "src/__support/CPP/type_traits.h"
#include "src/__support/macros/attributes.h"          // LIBC_INLINE
#include "src/__support/macros/config.h"
#include "src/__support/macros/optimization.h"        // LIBC_UNLIKELY
#include "src/__support/macros/properties/compiler.h" // LIBC_COMPILER_IS_CLANG
#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128, LIBC_TYPES_HAS_INT64
#include "src/__support/math_extras.h" // add_with_carry, sub_with_borrow
#include "src/__support/number_pair.h"

#include <stddef.h> // For size_t
#include <stdint.h>

namespace LIBC_NAMESPACE_DECL {

multiword // namespace multiword

template <size_t Bits, bool Signed, typename WordType = uint64_t>
struct BigInt { … };

namespace internal {
// We default BigInt's WordType to 'uint64_t' or 'uint32_t' depending on type
// availability.
template <size_t Bits>
struct WordTypeSelector : cpp::type_identity<
#ifdef LIBC_TYPES_HAS_INT64
                              uint64_t
#else
                              uint32_t
#endif // LIBC_TYPES_HAS_INT64
                              > { … };
// Except if we request 16 or 32 bits explicitly.
template <> struct WordTypeSelector<16> : cpp::type_identity<uint16_t> { … };
template <> struct WordTypeSelector<32> : cpp::type_identity<uint32_t> { … };
WordTypeSelectorT;
} // namespace internal

UInt;

Int;

// Provides limits of BigInt.
numeric_limits<BigInt<Bits, Signed, T>>;

// type traits to determine whether a T is a BigInt.
template <typename T> struct is_big_int : cpp::false_type { … };

is_big_int<BigInt<Bits, Signed, T>>;

is_big_int_v;

// extensions of type traits to include BigInt

// is_integral_or_big_int
template <typename T>
struct is_integral_or_big_int
    : cpp::bool_constant<(cpp::is_integral_v<T> || is_big_int_v<T>)> { … };

is_integral_or_big_int_v;

// make_big_int_unsigned
template <typename T> struct make_big_int_unsigned;

make_big_int_unsigned<BigInt<Bits, Signed, T>>;

make_big_int_unsigned_t;

// make_big_int_signed
template <typename T> struct make_big_int_signed;

make_big_int_signed<BigInt<Bits, Signed, T>>;

make_big_int_signed_t;

// make_integral_or_big_int_unsigned
template <typename T, class = void> struct make_integral_or_big_int_unsigned;

make_integral_or_big_int_unsigned<T, cpp::enable_if_t<cpp::is_integral_v<T>>>;

make_integral_or_big_int_unsigned<T, cpp::enable_if_t<is_big_int_v<T>>>;

make_integral_or_big_int_unsigned_t;

// make_integral_or_big_int_signed
template <typename T, class = void> struct make_integral_or_big_int_signed;

make_integral_or_big_int_signed<T, cpp::enable_if_t<cpp::is_integral_v<T>>>;

make_integral_or_big_int_signed<T, cpp::enable_if_t<is_big_int_v<T>>>;

make_integral_or_big_int_signed_t;

// is_unsigned_integral_or_big_int
template <typename T>
struct is_unsigned_integral_or_big_int
    : cpp::bool_constant<
          cpp::is_same_v<T, make_integral_or_big_int_unsigned_t<T>>> { … };

is_unsigned_integral_or_big_int_v;

namespace cpp {

// Specialization of cpp::bit_cast ('bit.h') from T to BigInt.
template <typename To, typename From>
LIBC_INLINE constexpr cpp::enable_if_t<
    (sizeof(To) == sizeof(From)) && cpp::is_trivially_copyable<To>::value &&
        cpp::is_trivially_copyable<From>::value && is_big_int<To>::value,
    To>
bit_cast(const From &from) { … }

// Specialization of cpp::bit_cast ('bit.h') from BigInt to T.
template <typename To, size_t Bits>
LIBC_INLINE constexpr cpp::enable_if_t<
    sizeof(To) == sizeof(UInt<Bits>) &&
        cpp::is_trivially_constructible<To>::value &&
        cpp::is_trivially_copyable<To>::value &&
        cpp::is_trivially_copyable<UInt<Bits>>::value,
    To>
bit_cast(const UInt<Bits> &from) { … }

// Specialization of cpp::popcount ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
popcount(T value) { … }

// Specialization of cpp::has_single_bit ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, bool>
has_single_bit(T value) { … }

// Specialization of cpp::countr_zero ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
countr_zero(const T &value) { … }

// Specialization of cpp::countl_zero ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
countl_zero(const T &value) { … }

// Specialization of cpp::countl_one ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
countl_one(T value) { … }

// Specialization of cpp::countr_one ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
countr_one(T value) { … }

// Specialization of cpp::bit_width ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
bit_width(T value) { … }

// Forward-declare rotr so that rotl can use it.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
rotr(T value, int rotate);

// Specialization of cpp::rotl ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
rotl(T value, int rotate) { … }

// Specialization of cpp::rotr ('bit.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
rotr(T value, int rotate) { … }

} // namespace cpp

// Specialization of mask_trailing_ones ('math_extras.h') for BigInt.
template <typename T, size_t count>
LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
mask_trailing_ones() { … }

// Specialization of mask_leading_ones ('math_extras.h') for BigInt.
template <typename T, size_t count>
LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T> mask_leading_ones() { … }

// Specialization of mask_trailing_zeros ('math_extras.h') for BigInt.
template <typename T, size_t count>
LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
mask_trailing_zeros() { … }

// Specialization of mask_leading_zeros ('math_extras.h') for BigInt.
template <typename T, size_t count>
LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, T>
mask_leading_zeros() { … }

// Specialization of count_zeros ('math_extras.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
count_zeros(T value) { … }

// Specialization of first_leading_zero ('math_extras.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
first_leading_zero(T value) { … }

// Specialization of first_leading_one ('math_extras.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
first_leading_one(T value) { … }

// Specialization of first_trailing_zero ('math_extras.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
first_trailing_zero(T value) { … }

// Specialization of first_trailing_one ('math_extras.h') for BigInt.
template <typename T>
[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<is_big_int_v<T>, int>
first_trailing_one(T value) { … }

} // namespace LIBC_NAMESPACE_DECL

#endif // LLVM_LIBC_SRC___SUPPORT_UINT_H