|
#ifndef __INT128_H_
|
|
#define __INT128_H_
|
|
|
|
#include <cctype>
|
|
#include <limits>
|
|
#include <sstream>
|
|
#include <stdexcept>
|
|
|
|
// NOTE: These 128 bit types are GCC specific; see:
|
|
// https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html
|
|
typedef __int128 int128_t;
|
|
typedef unsigned __int128 uint128_t;
|
|
|
|
|
|
std::ostream& operator<<(std::ostream& dest, uint128_t value);
|
|
|
|
std::ostream& operator<<(std::ostream& dest, int128_t value);
|
|
|
|
constexpr uint128_t max_tab[]
|
|
{
|
|
std::numeric_limits<uint128_t>::max() / 2,
|
|
std::numeric_limits<uint128_t>::max() / 3,
|
|
std::numeric_limits<uint128_t>::max() / 4,
|
|
std::numeric_limits<uint128_t>::max() / 5,
|
|
std::numeric_limits<uint128_t>::max() / 6,
|
|
std::numeric_limits<uint128_t>::max() / 7,
|
|
std::numeric_limits<uint128_t>::max() / 8,
|
|
std::numeric_limits<uint128_t>::max() / 9,
|
|
std::numeric_limits<uint128_t>::max() / 10,
|
|
std::numeric_limits<uint128_t>::max() / 11,
|
|
std::numeric_limits<uint128_t>::max() / 12,
|
|
std::numeric_limits<uint128_t>::max() / 13,
|
|
std::numeric_limits<uint128_t>::max() / 14,
|
|
std::numeric_limits<uint128_t>::max() / 15,
|
|
std::numeric_limits<uint128_t>::max() / 16,
|
|
std::numeric_limits<uint128_t>::max() / 17,
|
|
std::numeric_limits<uint128_t>::max() / 18,
|
|
std::numeric_limits<uint128_t>::max() / 19,
|
|
std::numeric_limits<uint128_t>::max() / 20,
|
|
std::numeric_limits<uint128_t>::max() / 21,
|
|
std::numeric_limits<uint128_t>::max() / 22,
|
|
std::numeric_limits<uint128_t>::max() / 23,
|
|
std::numeric_limits<uint128_t>::max() / 24,
|
|
std::numeric_limits<uint128_t>::max() / 25,
|
|
std::numeric_limits<uint128_t>::max() / 26,
|
|
std::numeric_limits<uint128_t>::max() / 27,
|
|
std::numeric_limits<uint128_t>::max() / 28,
|
|
std::numeric_limits<uint128_t>::max() / 29,
|
|
std::numeric_limits<uint128_t>::max() / 31,
|
|
std::numeric_limits<uint128_t>::max() / 32,
|
|
std::numeric_limits<uint128_t>::max() / 33,
|
|
std::numeric_limits<uint128_t>::max() / 34,
|
|
std::numeric_limits<uint128_t>::max() / 35,
|
|
std::numeric_limits<uint128_t>::max() / 36,
|
|
std::numeric_limits<uint128_t>::max() / 37,
|
|
std::numeric_limits<uint128_t>::max() / 38
|
|
};
|
|
|
|
constexpr uint32_t rem_tab[]
|
|
{
|
|
std::numeric_limits<uint128_t>::max() % 2,
|
|
std::numeric_limits<uint128_t>::max() % 3,
|
|
std::numeric_limits<uint128_t>::max() % 4,
|
|
std::numeric_limits<uint128_t>::max() % 5,
|
|
std::numeric_limits<uint128_t>::max() % 6,
|
|
std::numeric_limits<uint128_t>::max() % 7,
|
|
std::numeric_limits<uint128_t>::max() % 8,
|
|
std::numeric_limits<uint128_t>::max() % 9,
|
|
std::numeric_limits<uint128_t>::max() % 10,
|
|
std::numeric_limits<uint128_t>::max() % 11,
|
|
std::numeric_limits<uint128_t>::max() % 12,
|
|
std::numeric_limits<uint128_t>::max() % 13,
|
|
std::numeric_limits<uint128_t>::max() % 14,
|
|
std::numeric_limits<uint128_t>::max() % 15,
|
|
std::numeric_limits<uint128_t>::max() % 16,
|
|
std::numeric_limits<uint128_t>::max() % 17,
|
|
std::numeric_limits<uint128_t>::max() % 18,
|
|
std::numeric_limits<uint128_t>::max() % 19,
|
|
std::numeric_limits<uint128_t>::max() % 20,
|
|
std::numeric_limits<uint128_t>::max() % 21,
|
|
std::numeric_limits<uint128_t>::max() % 22,
|
|
std::numeric_limits<uint128_t>::max() % 23,
|
|
std::numeric_limits<uint128_t>::max() % 24,
|
|
std::numeric_limits<uint128_t>::max() % 25,
|
|
std::numeric_limits<uint128_t>::max() % 26,
|
|
std::numeric_limits<uint128_t>::max() % 27,
|
|
std::numeric_limits<uint128_t>::max() % 28,
|
|
std::numeric_limits<uint128_t>::max() % 29,
|
|
std::numeric_limits<uint128_t>::max() % 31,
|
|
std::numeric_limits<uint128_t>::max() % 32,
|
|
std::numeric_limits<uint128_t>::max() % 33,
|
|
std::numeric_limits<uint128_t>::max() % 34,
|
|
std::numeric_limits<uint128_t>::max() % 35,
|
|
std::numeric_limits<uint128_t>::max() % 36,
|
|
std::numeric_limits<uint128_t>::max() % 37,
|
|
std::numeric_limits<uint128_t>::max() % 38
|
|
};
|
|
|
|
int128_t strtoll_128(const char* nptr, char** endptr, int base);
|
|
uint128_t strtoull_128(const char* nptr, char** endptr, int base);
|
|
int128_t strtoll_128_b10opt(const char* nptr, char** endptr, int base=10);
|
|
uint128_t strtoull_128_b10opt(const char* nptr, char** endptr, int base=10);
|
|
|
|
// Source: https://github.com/jbapple/128-bit-literals/blob/master/suffix128.hpp
|
|
namespace suffix128 {
|
|
|
|
// Returns the value of the hexadecimal character
|
|
constexpr unsigned __int128 CharValue(char c) {
|
|
return (c >= '0' && c <= '9')
|
|
? (c - '0')
|
|
: ((c >= 'a' && c <= 'f') ? (10 + (c - 'a')) : (10 + (c - 'A')));
|
|
}
|
|
|
|
static constexpr unsigned __int128 MAX128 = ~static_cast<unsigned __int128>(0);
|
|
|
|
// ValidateU128Helper<BASE, c1, c2, ... , cn>(v) returns true iff cn + ... + c2
|
|
// * BASE^(n-2) + c1 * BASE^(n-1) + v * BASE^n is a valid 128-bit unsigned
|
|
// number when interpreted in base BASE.
|
|
template <int BASE>
|
|
constexpr bool ValidateU128Helper(unsigned __int128) {
|
|
return true;
|
|
}
|
|
|
|
template <int BASE, char C, char... CS>
|
|
constexpr bool ValidateU128Helper(unsigned __int128 accumulate) {
|
|
return (C == '\'') ? ValidateU128Helper<BASE, CS...>(accumulate)
|
|
: ((accumulate <= MAX128 / BASE) &&
|
|
(BASE * accumulate <= MAX128 - CharValue(C)) &&
|
|
ValidateU128Helper<BASE, CS...>(accumulate * BASE +
|
|
CharValue(C)));
|
|
}
|
|
|
|
// ValidateU128<BASE, c1, c2, ... , cn>(v) returns true iff cn + ... + c2 *
|
|
// BASE^(n-2) + c1 * BASE^(n-1) is a valid 128-bit unsigned number when
|
|
// interpreted in base BASE.
|
|
template <int BASE, char... CS>
|
|
constexpr bool ValidateU128() {
|
|
return ValidateU128Helper<BASE, CS...>(0);
|
|
}
|
|
|
|
// MakeU128Helper<BASE, c1, c2, ... , cn>(v) returns cn + ... + c2 *
|
|
// BASE^(n-2) + c1 * BASE^(n-1) + result * BASE^n.
|
|
template <int BASE>
|
|
constexpr unsigned __int128 MakeU128Helper(unsigned __int128 result) {
|
|
return result;
|
|
}
|
|
|
|
template <int BASE, char C, char... CS>
|
|
constexpr unsigned __int128 MakeU128Helper(unsigned __int128 result) {
|
|
return MakeU128Helper<BASE, CS...>(
|
|
(C == '\'') ? result : (result * BASE + CharValue(C)));
|
|
}
|
|
|
|
// MakeU128<BASE, c1, c2, ... , cn>(v) returns cn + ... + c2 * BASE^(n-2) + c1 *
|
|
// BASE^(n-1).
|
|
template <int BASE, char... CS>
|
|
constexpr unsigned __int128 MakeU128() {
|
|
return MakeU128Helper<BASE, CS...>(0);
|
|
}
|
|
|
|
template <char... CS>
|
|
struct StaticU128 {
|
|
static constexpr bool IS_VALID = ValidateU128<10, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<10, CS...>();
|
|
};
|
|
|
|
template <char... CS>
|
|
struct StaticU128<'0', 'x', CS...> {
|
|
static constexpr bool IS_VALID = ValidateU128<16, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<16, CS...>();
|
|
};
|
|
|
|
template <char... CS>
|
|
struct StaticU128<'0', 'X', CS...> {
|
|
static constexpr bool IS_VALID = ValidateU128<16, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<16, CS...>();
|
|
};
|
|
|
|
template <char... CS>
|
|
struct StaticU128<'0', 'b', CS...> {
|
|
static constexpr bool IS_VALID = ValidateU128<2, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<2, CS...>();
|
|
};
|
|
|
|
template <char... CS>
|
|
struct StaticU128<'0', 'B', CS...> {
|
|
static constexpr bool IS_VALID = ValidateU128<2, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<2, CS...>();
|
|
};
|
|
|
|
template <char... CS>
|
|
struct StaticU128<'0', CS...> {
|
|
static constexpr bool IS_VALID = ValidateU128<8, CS...>();
|
|
static constexpr unsigned __int128 PAYLOAD = MakeU128<8, CS...>();
|
|
};
|
|
|
|
static constexpr unsigned __int128 SIGNED_LIMIT =
|
|
(static_cast<unsigned __int128>(1) << 127) - 1;
|
|
|
|
template <char... CS>
|
|
struct Static128 {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<10, CS...>() && (MakeU128<10, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<10, CS...>());
|
|
};
|
|
|
|
template <char... CS>
|
|
struct Static128<'0', 'x', CS...> {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<16, CS...>() && (MakeU128<16, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<16, CS...>());
|
|
};
|
|
|
|
template <char... CS>
|
|
struct Static128<'0', 'X', CS...> {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<16, CS...>() && (MakeU128<16, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<16, CS...>());
|
|
};
|
|
|
|
template <char... CS>
|
|
struct Static128<'0', 'b', CS...> {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<2, CS...>() && (MakeU128<2, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<2, CS...>());
|
|
};
|
|
|
|
template <char... CS>
|
|
struct Static128<'0', 'B', CS...> {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<2, CS...>() && (MakeU128<2, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<2, CS...>());
|
|
};
|
|
|
|
template <char... CS>
|
|
struct Static128<'0', CS...> {
|
|
static constexpr bool IS_VALID =
|
|
ValidateU128<8, CS...>() && (MakeU128<8, CS...>() <= SIGNED_LIMIT);
|
|
static constexpr __int128 PAYLOAD =
|
|
static_cast<__int128>(MakeU128<8, CS...>());
|
|
};
|
|
|
|
} // namespace suffix128
|
|
|
|
template <char... CS>
|
|
constexpr unsigned __int128 operator"" _u128() {
|
|
static_assert(suffix128::StaticU128<CS...>::IS_VALID,
|
|
"Invalid characters or number too large");
|
|
return suffix128::StaticU128<CS...>::PAYLOAD;
|
|
}
|
|
|
|
template <char... CS>
|
|
constexpr __int128 operator"" _128() {
|
|
static_assert(suffix128::Static128<CS...>::IS_VALID,
|
|
"Invalid characters or number too large");
|
|
return suffix128::Static128<CS...>::PAYLOAD;
|
|
}
|
|
|
|
#endif
|