diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -134,6 +134,7 @@ libc.src.__support.FPUtil.fenv_impl libc.src.__support.FPUtil.fp_bits libc.src.__support.FPUtil.rounding_mode + libc.src.__support.FPUtil.dyadic_float libc.src.__support.builtin_wrappers libc.src.__support.common libc.src.errno.errno diff --git a/libc/src/__support/FPUtil/generic/sqrt.h b/libc/src/__support/FPUtil/generic/sqrt.h --- a/libc/src/__support/FPUtil/generic/sqrt.h +++ b/libc/src/__support/FPUtil/generic/sqrt.h @@ -137,7 +137,7 @@ } // We compute one more iteration in order to round correctly. - bool lsb = y & 1; // Least significant bit + bool lsb = static_cast(y & 1); // Least significant bit bool rb = false; // Round bit r <<= 2; UIntType tmp = (y << 2) + 1; diff --git a/libc/src/__support/FPUtil/generic/sqrt_80_bit_long_double.h b/libc/src/__support/FPUtil/generic/sqrt_80_bit_long_double.h --- a/libc/src/__support/FPUtil/generic/sqrt_80_bit_long_double.h +++ b/libc/src/__support/FPUtil/generic/sqrt_80_bit_long_double.h @@ -101,7 +101,7 @@ } // We compute one more iteration in order to round correctly. - bool lsb = y & 1; // Least significant bit + bool lsb = static_cast(y & 1); // Least significant bit bool rb = false; // Round bit r <<= 2; UIntType tmp = (y << 2) + 1; diff --git a/libc/src/__support/FPUtil/x86_64/LongDoubleBits.h b/libc/src/__support/FPUtil/x86_64/LongDoubleBits.h --- a/libc/src/__support/FPUtil/x86_64/LongDoubleBits.h +++ b/libc/src/__support/FPUtil/x86_64/LongDoubleBits.h @@ -130,6 +130,10 @@ return bits & MASK; } + LIBC_INLINE long double get_val() const { + return cpp::bit_cast(bits); + } + LIBC_INLINE int get_exponent() const { if (get_unbiased_exponent() == 0) return int(1) - EXPONENT_BIAS; diff --git a/libc/src/__support/UInt.h b/libc/src/__support/UInt.h --- a/libc/src/__support/UInt.h +++ b/libc/src/__support/UInt.h @@ -23,10 +23,10 @@ namespace __llvm_libc::cpp { -template struct UInt { +template struct BigInt { static_assert(Bits > 0 && Bits % 64 == 0, - "Number of bits in UInt should be a multiple of 64."); + "Number of bits in BigInt should be a multiple of 64."); static constexpr size_t WORDCOUNT = Bits / 64; uint64_t val[WORDCOUNT]{}; @@ -35,11 +35,12 @@ static constexpr uint64_t low(uint64_t v) { return v & MASK32; } static constexpr uint64_t high(uint64_t v) { return (v >> 32) & MASK32; } - constexpr UInt() = default; + constexpr BigInt() = default; - constexpr UInt(const UInt &other) = default; + constexpr BigInt(const BigInt &other) = default; - template constexpr UInt(const UInt &other) { + template + constexpr BigInt(const BigInt &other) { if (OtherBits >= Bits) { for (size_t i = 0; i < WORDCOUNT; ++i) val[i] = other[i]; @@ -47,14 +48,19 @@ size_t i = 0; for (; i < OtherBits / 64; ++i) val[i] = other[i]; + uint64_t sign = 0; + if constexpr (Signed && OtherSigned) { + sign = static_cast( + -static_cast(other[OtherBits / 64 - 1] >> 63)); + } for (; i < WORDCOUNT; ++i) - val[i] = 0; + val[i] = sign; } } - // Construct a UInt from a C array. + // Construct a BigInt from a C array. template = 0> - constexpr UInt(const uint64_t (&nums)[N]) { + constexpr BigInt(const uint64_t (&nums)[N]) { size_t min_wordcount = N < WORDCOUNT ? N : WORDCOUNT; size_t i = 0; for (; i < min_wordcount; ++i) @@ -66,40 +72,57 @@ } // Initialize the first word to |v| and the rest to 0. - constexpr UInt(uint64_t v) { - val[0] = v; - for (size_t i = 1; i < WORDCOUNT; ++i) { - val[i] = 0; + template && sizeof(T) <= 16>> + constexpr BigInt(T v) { + val[0] = static_cast(v); + + if constexpr (Bits == 64) + return; + + // Bits is at least 128. + size_t i = 1; + if constexpr (sizeof(T) == 16) { + val[1] = static_cast(v >> 64); + i = 2; } - } - constexpr explicit UInt(const cpp::array &words) { - for (size_t i = 0; i < WORDCOUNT; ++i) - val[i] = words[i]; - } - constexpr explicit operator unsigned long long() const { - return static_cast(val[0]); + uint64_t sign = (Signed && (v < 0)) ? 0xffff'ffff'ffff'ffff : 0; + for (; i < WORDCOUNT; ++i) { + val[i] = sign; + } } - constexpr explicit operator unsigned long() const { - return static_cast(val[0]); + constexpr explicit BigInt(const cpp::array &words) { + for (size_t i = 0; i < WORDCOUNT; ++i) + val[i] = words[i]; } - constexpr explicit operator unsigned int() const { - return static_cast(val[0]); - } + template && + sizeof(T) <= 16 && + !cpp::is_same_v>> + constexpr explicit operator T() const { + if constexpr (sizeof(T) <= 8) + return static_cast(val[0]); - constexpr explicit operator unsigned short() const { - return static_cast(val[0]); - } + // T is 128-bit. + T lo = static_cast(val[0]); - constexpr explicit operator unsigned char() const { - return static_cast(val[0]); + if constexpr (Bits == 64) { + if constexpr (Signed) { + // Extend sign for negative numbers. + return (val[0] >> 63) ? ((T(-1) << 64) + lo) : lo; + } else { + return lo; + } + } else { + return (static_cast(val[1]) << 64) + lo; + } } constexpr explicit operator bool() const { return !is_zero(); } - UInt &operator=(const UInt &other) = default; + BigInt &operator=(const BigInt &other) = default; constexpr bool is_zero() const { for (size_t i = 0; i < WORDCOUNT; ++i) { @@ -111,7 +134,7 @@ // Add x to this number and store the result in this number. // Returns the carry value produced by the addition operation. - constexpr uint64_t add(const UInt &x) { + constexpr uint64_t add(const BigInt &x) { SumCarry s{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { s = add_with_carry(val[i], x.val[i], s.carry); @@ -120,8 +143,8 @@ return s.carry; } - UInt operator+(const UInt &other) const { - UInt result; + BigInt operator+(const BigInt &other) const { + BigInt result; SumCarry s{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { s = add_with_carry(val[i], other.val[i], s.carry); @@ -132,8 +155,8 @@ // This will only apply when initializing a variable from constant values, so // it will always use the constexpr version of add_with_carry. - constexpr UInt operator+(UInt &&other) const { - UInt result; + constexpr BigInt operator+(BigInt &&other) const { + BigInt result; SumCarry s{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { s = add_with_carry_const(val[i], other.val[i], s.carry); @@ -142,14 +165,15 @@ return result; } - constexpr UInt &operator+=(const UInt &other) { + constexpr BigInt & + operator+=(const BigInt &other) { add(other); // Returned carry value is ignored. return *this; } // Subtract x to this number and store the result in this number. // Returns the carry value produced by the subtraction operation. - constexpr uint64_t sub(const UInt &x) { + constexpr uint64_t sub(const BigInt &x) { DiffBorrow d{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { d = sub_with_borrow(val[i], x.val[i], d.borrow); @@ -158,8 +182,8 @@ return d.borrow; } - UInt operator-(const UInt &other) const { - UInt result; + BigInt operator-(const BigInt &other) const { + BigInt result; DiffBorrow d{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { d = sub_with_borrow(val[i], other.val[i], d.borrow); @@ -168,8 +192,8 @@ return result; } - constexpr UInt operator-(UInt &&other) const { - UInt result; + constexpr BigInt operator-(BigInt &&other) const { + BigInt result; DiffBorrow d{0, 0}; for (size_t i = 0; i < WORDCOUNT; ++i) { d = sub_with_borrow_const(val[i], other.val[i], d.borrow); @@ -178,7 +202,8 @@ return result; } - constexpr UInt &operator-=(const UInt &other) { + constexpr BigInt & + operator-=(const BigInt &other) { // TODO(lntue): Set overflow flag / errno when carry is true. sub(other); return *this; @@ -191,11 +216,11 @@ // carry bits. // Returns the carry value produced by the multiplication operation. constexpr uint64_t mul(uint64_t x) { - UInt<128> partial_sum(0); + BigInt<128, Signed> partial_sum(0); uint64_t carry = 0; for (size_t i = 0; i < WORDCOUNT; ++i) { NumberPair prod = full_mul(val[i], x); - UInt<128> tmp({prod.lo, prod.hi}); + BigInt<128, Signed> tmp({prod.lo, prod.hi}); carry += partial_sum.add(tmp); val[i] = partial_sum.val[0]; partial_sum.val[0] = partial_sum.val[1]; @@ -205,42 +230,60 @@ return partial_sum.val[1]; } - constexpr UInt operator*(const UInt &other) const { - if constexpr (WORDCOUNT == 1) { - return {val[0] * other.val[0]}; + constexpr BigInt + operator*(const BigInt &other) const { + if constexpr (Signed) { + BigInt a(*this); + BigInt b(other); + bool a_neg = (a.val[WORDCOUNT - 1] >> 63); + bool b_neg = (b.val[WORDCOUNT - 1] >> 63); + if (a_neg) + a = -a; + if (b_neg) + b = -b; + BigInt prod = a * b; + if (a_neg != b_neg) + prod = -prod; + return static_cast>(prod); } else { - UInt result(0); - UInt<128> partial_sum(0); - uint64_t carry = 0; - for (size_t i = 0; i < WORDCOUNT; ++i) { - for (size_t j = 0; j <= i; j++) { - NumberPair prod = full_mul(val[j], other.val[i - j]); - UInt<128> tmp({prod.lo, prod.hi}); - carry += partial_sum.add(tmp); + + if constexpr (WORDCOUNT == 1) { + return {val[0] * other.val[0]}; + } else { + BigInt result(0); + BigInt<128, Signed> partial_sum(0); + uint64_t carry = 0; + for (size_t i = 0; i < WORDCOUNT; ++i) { + for (size_t j = 0; j <= i; j++) { + NumberPair prod = full_mul(val[j], other.val[i - j]); + BigInt<128, Signed> tmp({prod.lo, prod.hi}); + carry += partial_sum.add(tmp); + } + result.val[i] = partial_sum.val[0]; + partial_sum.val[0] = partial_sum.val[1]; + partial_sum.val[1] = carry; + carry = 0; } - result.val[i] = partial_sum.val[0]; - partial_sum.val[0] = partial_sum.val[1]; - partial_sum.val[1] = carry; - carry = 0; + return result; } - return result; } } - // Return the full product. + // Return the full product, only unsigned for now. template - constexpr UInt ful_mul(const UInt &other) const { - UInt result(0); - UInt<128> partial_sum(0); + constexpr BigInt + ful_mul(const BigInt &other) const { + BigInt result(0); + BigInt<128, Signed> partial_sum(0); uint64_t carry = 0; - constexpr size_t OTHER_WORDCOUNT = UInt::WORDCOUNT; + constexpr size_t OTHER_WORDCOUNT = BigInt::WORDCOUNT; for (size_t i = 0; i <= WORDCOUNT + OTHER_WORDCOUNT - 2; ++i) { const size_t lower_idx = i < OTHER_WORDCOUNT ? 0 : i - OTHER_WORDCOUNT + 1; const size_t upper_idx = i < WORDCOUNT ? i : WORDCOUNT - 1; for (size_t j = lower_idx; j <= upper_idx; ++j) { NumberPair prod = full_mul(val[j], other.val[i - j]); - UInt<128> tmp({prod.lo, prod.hi}); + BigInt<128, Signed> tmp({prod.lo, prod.hi}); carry += partial_sum.add(tmp); } result.val[i] = partial_sum.val[0]; @@ -273,16 +316,17 @@ // 196 3 9 6 2 // 256 4 16 10 3 // 512 8 64 36 7 - constexpr UInt quick_mul_hi(const UInt &other) const { - UInt result(0); - UInt<128> partial_sum(0); + constexpr BigInt + quick_mul_hi(const BigInt &other) const { + BigInt result(0); + BigInt<128, Signed> partial_sum(0); uint64_t carry = 0; // First round of accumulation for those at WORDCOUNT - 1 in the full // product. for (size_t i = 0; i < WORDCOUNT; ++i) { NumberPair prod = full_mul(val[i], other.val[WORDCOUNT - 1 - i]); - UInt<128> tmp({prod.lo, prod.hi}); + BigInt<128, Signed> tmp({prod.lo, prod.hi}); carry += partial_sum.add(tmp); } for (size_t i = WORDCOUNT; i < 2 * WORDCOUNT - 1; ++i) { @@ -291,7 +335,7 @@ carry = 0; for (size_t j = i - WORDCOUNT + 1; j < WORDCOUNT; ++j) { NumberPair prod = full_mul(val[j], other.val[i - j]); - UInt<128> tmp({prod.lo, prod.hi}); + BigInt<128, Signed> tmp({prod.lo, prod.hi}); carry += partial_sum.add(tmp); } result.val[i - WORDCOUNT] = partial_sum.val[0]; @@ -303,8 +347,8 @@ // pow takes a power and sets this to its starting value to that power. Zero // to the zeroth power returns 1. constexpr void pow_n(uint64_t power) { - UInt result = 1; - UInt cur_power = *this; + BigInt result = 1; + BigInt cur_power = *this; while (power > 0) { if ((power % 2) > 0) { @@ -316,13 +360,16 @@ *this = result; } - // div takes another UInt of the same size and divides this by it. The value + // TODO: Make division work correctly for signed integers. + + // div takes another BigInt of the same size and divides this by it. The value // of this will be set to the quotient, and the return value is the remainder. - constexpr optional> div(const UInt &other) { - UInt remainder(0); + constexpr optional> + div(const BigInt &other) { + BigInt remainder(0); if (*this < other) { remainder = *this; - *this = UInt(0); + *this = BigInt(0); return remainder; } if (other == 1) { @@ -332,15 +379,15 @@ return nullopt; } - UInt quotient(0); - UInt subtractor = other; + BigInt quotient(0); + BigInt subtractor = other; int cur_bit = subtractor.clz() - this->clz(); subtractor.shift_left(cur_bit); for (; cur_bit >= 0 && *this > 0; --cur_bit, subtractor.shift_right(1)) { if (*this >= subtractor) { this->sub(subtractor); - quotient = quotient | (UInt(1) << cur_bit); + quotient = quotient | (BigInt(1) << cur_bit); } } remainder = *this; @@ -348,9 +395,8 @@ return remainder; } - // Efficiently perform UInt / (x * 2^e), where x is a 32-bit unsigned integer, - // and return the remainder. - // The main idea is as follow: + // Efficiently perform BigInt / (x * 2^e), where x is a 32-bit unsigned + // integer, and return the remainder. The main idea is as follow: // Let q = y / (x * 2^e) be the quotient, and // r = y % (x * 2^e) be the remainder. // First, notice that: @@ -361,19 +407,20 @@ // Since the remainder of each division step < x < 2^32, the computation of // each step is now properly contained within uint64_t. // And finally we perform some extra alignment steps for the remaining bits. - constexpr optional> div_uint32_times_pow_2(uint32_t x, size_t e) { - UInt remainder(0); + constexpr optional> div_uint32_times_pow_2(uint32_t x, + size_t e) { + BigInt remainder(0); if (x == 0) { return nullopt; } if (e >= Bits) { remainder = *this; - *this = UInt(0); + *this = BigInt(0); return remainder; } - UInt quotient(0); + BigInt quotient(0); uint64_t x64 = static_cast(x); // lower64 = smallest multiple of 64 that is >= e. size_t lower64 = ((e >> 6) + ((e & 63) != 0)) << 6; @@ -468,18 +515,27 @@ return remainder; } - constexpr UInt operator/(const UInt &other) const { - UInt result(*this); + constexpr BigInt + operator/(const BigInt &other) const { + BigInt result(*this); result.div(other); return result; } - constexpr UInt operator%(const UInt &other) const { - UInt result(*this); + constexpr BigInt & + operator/=(const BigInt &other) { + div(other); + return *this; + } + + constexpr BigInt + operator%(const BigInt &other) const { + BigInt result(*this); return *result.div(other); } - constexpr UInt &operator*=(const UInt &other) { + constexpr BigInt & + operator*=(const BigInt &other) { *this = *this * other; return *this; } @@ -540,13 +596,13 @@ } } - constexpr UInt operator<<(size_t s) const { - UInt result(*this); + constexpr BigInt operator<<(size_t s) const { + BigInt result(*this); result.shift_left(s); return result; } - constexpr UInt &operator<<=(size_t s) { + constexpr BigInt &operator<<=(size_t s) { shift_left(s); return *this; } @@ -561,7 +617,11 @@ return; } __uint128_t tmp = __uint128_t(val[0]) + (__uint128_t(val[1]) << 64); - tmp >>= s; + if constexpr (Signed) { + tmp = static_cast<__uint128_t>(static_cast<__int128_t>(tmp) >> s); + } else { + tmp >>= s; + } val[0] = uint64_t(tmp); val[1] = uint64_t(tmp >> 64); return; @@ -574,13 +634,19 @@ const size_t shift = s % 64; // Bit shift in the remaining words. size_t i = 0; + uint64_t sign = Signed ? (val[WORDCOUNT - 1] >> 63) : 0; if (drop < WORDCOUNT) { if (shift > 0) { for (size_t j = drop; j < WORDCOUNT - 1; ++i, ++j) { val[i] = (val[j] >> shift) | (val[j + 1] << (64 - shift)); } - val[i] = val[WORDCOUNT - 1] >> shift; + if constexpr (Signed) { + val[i] = static_cast( + static_cast(val[WORDCOUNT - 1]) >> shift); + } else { + val[i] = val[WORDCOUNT - 1] >> shift; + } ++i; } else { for (size_t j = drop; j < WORDCOUNT; ++i, ++j) { @@ -590,68 +656,80 @@ } for (; i < WORDCOUNT; ++i) { - val[i] = 0; + val[i] = sign; } } - constexpr UInt operator>>(size_t s) const { - UInt result(*this); + constexpr BigInt operator>>(size_t s) const { + BigInt result(*this); result.shift_right(s); return result; } - constexpr UInt &operator>>=(size_t s) { + constexpr BigInt &operator>>=(size_t s) { shift_right(s); return *this; } - constexpr UInt operator&(const UInt &other) const { - UInt result; + constexpr BigInt + operator&(const BigInt &other) const { + BigInt result; for (size_t i = 0; i < WORDCOUNT; ++i) result.val[i] = val[i] & other.val[i]; return result; } - constexpr UInt &operator&=(const UInt &other) { + constexpr BigInt & + operator&=(const BigInt &other) { for (size_t i = 0; i < WORDCOUNT; ++i) val[i] &= other.val[i]; return *this; } - constexpr UInt operator|(const UInt &other) const { - UInt result; + constexpr BigInt + operator|(const BigInt &other) const { + BigInt result; for (size_t i = 0; i < WORDCOUNT; ++i) result.val[i] = val[i] | other.val[i]; return result; } - constexpr UInt &operator|=(const UInt &other) { + constexpr BigInt & + operator|=(const BigInt &other) { for (size_t i = 0; i < WORDCOUNT; ++i) val[i] |= other.val[i]; return *this; } - constexpr UInt operator^(const UInt &other) const { - UInt result; + constexpr BigInt + operator^(const BigInt &other) const { + BigInt result; for (size_t i = 0; i < WORDCOUNT; ++i) result.val[i] = val[i] ^ other.val[i]; return result; } - constexpr UInt &operator^=(const UInt &other) { + constexpr BigInt & + operator^=(const BigInt &other) { for (size_t i = 0; i < WORDCOUNT; ++i) val[i] ^= other.val[i]; return *this; } - constexpr UInt operator~() const { - UInt result; + constexpr BigInt operator~() const { + BigInt result; for (size_t i = 0; i < WORDCOUNT; ++i) result.val[i] = ~val[i]; return result; } - constexpr bool operator==(const UInt &other) const { + constexpr BigInt operator-() const { + BigInt result = ~(*this); + result.add(BigInt(1)); + return result; + } + + constexpr bool operator==(const BigInt &other) const { for (size_t i = 0; i < WORDCOUNT; ++i) { if (val[i] != other.val[i]) return false; @@ -659,7 +737,7 @@ return true; } - constexpr bool operator!=(const UInt &other) const { + constexpr bool operator!=(const BigInt &other) const { for (size_t i = 0; i < WORDCOUNT; ++i) { if (val[i] != other.val[i]) return true; @@ -667,7 +745,15 @@ return false; } - constexpr bool operator>(const UInt &other) const { + constexpr bool operator>(const BigInt &other) const { + if constexpr (Signed) { + // Check for different signs; + bool a_sign = val[WORDCOUNT - 1] >> 63; + bool b_sign = other.val[WORDCOUNT - 1] >> 63; + if (a_sign != b_sign) { + return b_sign; + } + } for (size_t i = WORDCOUNT; i > 0; --i) { uint64_t word = val[i - 1]; uint64_t other_word = other.val[i - 1]; @@ -680,7 +766,15 @@ return false; } - constexpr bool operator>=(const UInt &other) const { + constexpr bool operator>=(const BigInt &other) const { + if constexpr (Signed) { + // Check for different signs; + bool a_sign = val[WORDCOUNT - 1] >> 63; + bool b_sign = other.val[WORDCOUNT - 1] >> 63; + if (a_sign != b_sign) { + return b_sign; + } + } for (size_t i = WORDCOUNT; i > 0; --i) { uint64_t word = val[i - 1]; uint64_t other_word = other.val[i - 1]; @@ -693,7 +787,16 @@ return true; } - constexpr bool operator<(const UInt &other) const { + constexpr bool operator<(const BigInt &other) const { + if constexpr (Signed) { + // Check for different signs; + bool a_sign = val[WORDCOUNT - 1] >> 63; + bool b_sign = other.val[WORDCOUNT - 1] >> 63; + if (a_sign != b_sign) { + return a_sign; + } + } + for (size_t i = WORDCOUNT; i > 0; --i) { uint64_t word = val[i - 1]; uint64_t other_word = other.val[i - 1]; @@ -706,7 +809,15 @@ return false; } - constexpr bool operator<=(const UInt &other) const { + constexpr bool operator<=(const BigInt &other) const { + if constexpr (Signed) { + // Check for different signs; + bool a_sign = val[WORDCOUNT - 1] >> 63; + bool b_sign = other.val[WORDCOUNT - 1] >> 63; + if (a_sign != b_sign) { + return a_sign; + } + } for (size_t i = WORDCOUNT; i > 0; --i) { uint64_t word = val[i - 1]; uint64_t other_word = other.val[i - 1]; @@ -719,12 +830,32 @@ return true; } - constexpr UInt &operator++() { - UInt one(1); + constexpr BigInt &operator++() { + BigInt one(1); add(one); return *this; } + constexpr BigInt operator++(int) { + BigInt oldval(*this); + BigInt one(1); + add(one); + return oldval; + } + + constexpr BigInt &operator--() { + BigInt one(1); + sub(one); + return *this; + } + + constexpr BigInt operator--(int) { + BigInt oldval(*this); + BigInt one(1); + sub(one); + return oldval; + } + // Return the i-th 64-bit word of the number. constexpr const uint64_t &operator[](size_t i) const { return val[i]; } @@ -736,17 +867,34 @@ const uint64_t *data() const { return val; } }; -// Provides limits of UInt<128>. +template using UInt = BigInt; + +template using Int = BigInt; + +// Provides limits of U/Int<128>. template <> class numeric_limits> { public: - static constexpr UInt<128> max() { return ~UInt<128>(0); } - static constexpr UInt<128> min() { return 0; } + static constexpr UInt<128> max() { + return UInt<128>({0xffff'ffff'ffff'ffff, 0xffff'ffff'ffff'ffff}); + } + static constexpr UInt<128> min() { return UInt<128>(0); } }; -// Provides is_integral of UInt<128>, UInt<192>, UInt<256>. -template struct is_integral> : public cpp::true_type { +template <> class numeric_limits> { +public: + static constexpr Int<128> max() { + return Int<128>({0xffff'ffff'ffff'ffff, 0x7fff'ffff'ffff'ffff}); + } + static constexpr Int<128> min() { + return Int<128>({0, 0x8000'0000'0000'0000}); + } +}; + +// Provides is_integral of U/Int<128>, U/Int<192>, U/Int<256>. +template +struct is_integral> : cpp::true_type { static_assert(Bits > 0 && Bits % 64 == 0, - "Number of bits in UInt should be a multiple of 64."); + "Number of bits in BigInt should be a multiple of 64."); }; // Provides is_unsigned of UInt<128>, UInt<192>, UInt<256>. @@ -755,6 +903,12 @@ "Number of bits in UInt should be a multiple of 64."); }; +template +struct make_unsigned> : type_identity> { + static_assert(Bits > 0 && Bits % 64 == 0, + "Number of bits in Int should be a multiple of 64."); +}; + } // namespace __llvm_libc::cpp #endif // LLVM_LIBC_SRC_SUPPORT_UINT_H diff --git a/libc/src/__support/UInt128.h b/libc/src/__support/UInt128.h --- a/libc/src/__support/UInt128.h +++ b/libc/src/__support/UInt128.h @@ -1,4 +1,4 @@ -//===-- A 128 bit unsigned int type -----------------------------*- C++ -*-===// +//===-- 128-bit signed and unsigned int types -------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -13,8 +13,10 @@ #if !defined(__SIZEOF_INT128__) using UInt128 = __llvm_libc::cpp::UInt<128>; +using Int128 = __llvm_libc::cpp::Int<128>; #else using UInt128 = __uint128_t; +using Int128 = __int128_t; #endif #endif // LLVM_LIBC_SRC_SUPPORT_UINT128_H diff --git a/libc/src/__support/builtin_wrappers.h b/libc/src/__support/builtin_wrappers.h --- a/libc/src/__support/builtin_wrappers.h +++ b/libc/src/__support/builtin_wrappers.h @@ -23,51 +23,55 @@ // compiler match for us. namespace __internal { -template LIBC_INLINE int correct_zero(T val, int bits) { +template LIBC_INLINE int constexpr correct_zero(T val, int bits) { if (val == T(0)) return sizeof(T(0)) * 8; else return bits; } -template LIBC_INLINE int clz(T val); +template LIBC_INLINE constexpr int clz(T val); template <> LIBC_INLINE int clz(unsigned int val) { return __builtin_clz(val); } -template <> LIBC_INLINE int clz(unsigned long int val) { +template <> +LIBC_INLINE constexpr int clz(unsigned long int val) { return __builtin_clzl(val); } template <> -LIBC_INLINE int clz(unsigned long long int val) { +LIBC_INLINE constexpr int +clz(unsigned long long int val) { return __builtin_clzll(val); } -template LIBC_INLINE int ctz(T val); +template LIBC_INLINE constexpr int ctz(T val); template <> LIBC_INLINE int ctz(unsigned int val) { return __builtin_ctz(val); } -template <> LIBC_INLINE int ctz(unsigned long int val) { +template <> +LIBC_INLINE constexpr int ctz(unsigned long int val) { return __builtin_ctzl(val); } template <> -LIBC_INLINE int ctz(unsigned long long int val) { +LIBC_INLINE constexpr int +ctz(unsigned long long int val) { return __builtin_ctzll(val); } } // namespace __internal -template LIBC_INLINE int safe_ctz(T val) { +template LIBC_INLINE constexpr int safe_ctz(T val) { return __internal::correct_zero(val, __internal::ctz(val)); } -template LIBC_INLINE int unsafe_ctz(T val) { +template LIBC_INLINE constexpr int unsafe_ctz(T val) { return __internal::ctz(val); } -template LIBC_INLINE int safe_clz(T val) { +template LIBC_INLINE constexpr int safe_clz(T val) { return __internal::correct_zero(val, __internal::clz(val)); } -template LIBC_INLINE int unsafe_clz(T val) { +template LIBC_INLINE constexpr int unsafe_clz(T val) { return __internal::clz(val); } diff --git a/libc/src/__support/float_to_string.h b/libc/src/__support/float_to_string.h --- a/libc/src/__support/float_to_string.h +++ b/libc/src/__support/float_to_string.h @@ -386,8 +386,8 @@ cpp::UInt val(large); // TODO: Find a better way to force __uint128_t to be UInt<128> cpp::UInt wide_mant(0); - wide_mant[0] = mantissa & (uint64_t(-1)); - wide_mant[1] = mantissa >> 64; + wide_mant[0] = static_cast(mantissa & (uint64_t(-1))); + wide_mant[1] = static_cast(mantissa >> 64); val = (val * wide_mant) >> shift_amount; return val.div_uint32_times_pow_2(1000000000, 0).value()[0]; diff --git a/libc/src/__support/integer_to_string.h b/libc/src/__support/integer_to_string.h --- a/libc/src/__support/integer_to_string.h +++ b/libc/src/__support/integer_to_string.h @@ -165,11 +165,10 @@ return convert<16>(val, buffer, lowercase); } - template && cpp::is_unsigned_v && - (sizeof(T) > sizeof(uintmax_t)) && - sizeof(T) % sizeof(uintmax_t) == 0, - int> = 0> + template && + (sizeof(T) > sizeof(uintmax_t)) && + sizeof(T) % sizeof(uintmax_t) == 0, + int> = 0> LIBC_INLINE static cpp::optional hex(T val, cpp::span buffer, bool lowercase = true) { // We will assume the buffer is exactly sized, which will be the case if diff --git a/libc/src/__support/str_to_float.h b/libc/src/__support/str_to_float.h --- a/libc/src/__support/str_to_float.h +++ b/libc/src/__support/str_to_float.h @@ -13,6 +13,7 @@ #include "src/__support/CPP/optional.h" #include "src/__support/FPUtil/FEnvImpl.h" #include "src/__support/FPUtil/FPBits.h" +#include "src/__support/FPUtil/dyadic_float.h" #include "src/__support/FPUtil/rounding_mode.h" #include "src/__support/UInt128.h" #include "src/__support/builtin_wrappers.h" @@ -301,7 +302,8 @@ } // Shifting to 65 bits for 80 bit floats and 113 bits for 128 bit floats - BitsType msb = final_approx_upper >> (BITS_IN_MANTISSA - 1); + uint32_t msb = + static_cast(final_approx_upper >> (BITS_IN_MANTISSA - 1)); BitsType final_mantissa = final_approx_upper >> (msb + BITS_IN_MANTISSA - @@ -571,7 +573,16 @@ } fputil::FPBits result; - T float_mantissa = static_cast(mantissa); + T float_mantissa; + if constexpr (cpp::is_same_v::UIntType, + cpp::UInt<128>>) { + float_mantissa = static_cast(fputil::DyadicFloat<128>( + false, 0, + fputil::DyadicFloat<128>::MantissaType( + {uint64_t(mantissa), uint64_t(mantissa >> 64)}))); + } else { + float_mantissa = static_cast(mantissa); + } if (exp10 == 0) { result = fputil::FPBits(float_mantissa); @@ -806,7 +817,7 @@ BitsType round_bit_mask = BitsType(1) << (amount_to_shift_right - 1); BitsType sticky_mask = round_bit_mask - 1; - bool round_bit = mantissa & round_bit_mask; + bool round_bit = static_cast(mantissa & round_bit_mask); bool sticky_bit = static_cast(mantissa & sticky_mask) || truncated; if (amount_to_shift_right < NUMBITS) { @@ -816,7 +827,7 @@ } else { mantissa = 0; } - bool least_significant_bit = mantissa & BitsType(1); + bool least_significant_bit = static_cast(mantissa & BitsType(1)); // TODO: check that this rounding behavior is correct. diff --git a/libc/src/math/generic/CMakeLists.txt b/libc/src/math/generic/CMakeLists.txt --- a/libc/src/math/generic/CMakeLists.txt +++ b/libc/src/math/generic/CMakeLists.txt @@ -780,6 +780,7 @@ log_range_reduction.h DEPENDS .common_constants + libc.src.__support.uint128 libc.src.__support.FPUtil.dyadic_float ) diff --git a/libc/src/math/generic/log_range_reduction.h b/libc/src/math/generic/log_range_reduction.h --- a/libc/src/math/generic/log_range_reduction.h +++ b/libc/src/math/generic/log_range_reduction.h @@ -11,6 +11,7 @@ #include "common_constants.h" #include "src/__support/FPUtil/dyadic_float.h" +#include "src/__support/UInt128.h" namespace __llvm_libc { @@ -59,9 +60,9 @@ int64_t s3 = static_cast(S3[idx3]); // |s| < 2^-13, ulp = 2^-21 int64_t spv3 = (s3 << 55) + vv2; // |s + v| < 2^-21, ulp = 2^-76 // |s*v| < 2^-27, ulp = 2^(-76-21) = 2^-97 - __int128_t sv3 = static_cast<__int128_t>(s3) * static_cast<__int128_t>(vv2); + Int128 sv3 = static_cast(s3) * static_cast(vv2); // |vv3| < 2^-21, ulp = 2^-97 - __int128_t vv3 = (static_cast<__int128_t>(spv3) << 21) + sv3; + Int128 vv3 = (static_cast(spv3) << 21) + sv3; // Range reduction - Step 4 // Output range: vv4 in [-0x1.0002143p-29 , 0x1p-29] @@ -70,13 +71,13 @@ sum = fputil::quick_add(sum, log_table.step_4[idx4]); - __int128_t s4 = static_cast<__int128_t>(S4[idx4]); // |s| < 2^-21, ulp = 2^-28 + Int128 s4 = static_cast(S4[idx4]); // |s| < 2^-21, ulp = 2^-28 // |s + v| < 2^-28, ulp = 2^-97 - __int128_t spv4 = (s4 << 69) + vv3; + Int128 spv4 = (s4 << 69) + vv3; // |s*v| < 2^-42, ulp = 2^(-97-28) = 2^-125 - __int128_t sv4 = s4 * vv3; + Int128 sv4 = s4 * vv3; // |vv4| < 2^-28, ulp = 2^-125 - __int128_t vv4 = (spv4 << 28) + sv4; + Int128 vv4 = (spv4 << 28) + sv4; return (vv4 < 0) ? Float128(true, -125, MType({static_cast(-vv4), diff --git a/libc/src/stdio/printf_core/char_converter.h b/libc/src/stdio/printf_core/char_converter.h --- a/libc/src/stdio/printf_core/char_converter.h +++ b/libc/src/stdio/printf_core/char_converter.h @@ -19,7 +19,7 @@ namespace printf_core { LIBC_INLINE int convert_char(Writer *writer, const FormatSection &to_conv) { - char c = to_conv.conv_val_raw; + char c = static_cast(to_conv.conv_val_raw); constexpr int string_len = 1; diff --git a/libc/src/stdio/printf_core/float_dec_converter.h b/libc/src/stdio/printf_core/float_dec_converter.h --- a/libc/src/stdio/printf_core/float_dec_converter.h +++ b/libc/src/stdio/printf_core/float_dec_converter.h @@ -34,9 +34,10 @@ using MantissaInt = fputil::FPBits::UIntType; // Returns true if value is divisible by 2^p. -LIBC_INLINE constexpr bool multiple_of_power_of_2(const uint64_t value, - const uint32_t p) { - return (value & ((uint64_t(1) << p) - 1)) == 0; +template +LIBC_INLINE constexpr cpp::enable_if_t, bool> +multiple_of_power_of_2(T value, uint32_t p) { + return (value & ((T(1) << p) - 1)) == 0; } constexpr size_t BLOCK_SIZE = 9; @@ -1148,7 +1149,8 @@ float_bits); } } else { - fputil::FPBits::UIntType float_raw = to_conv.conv_val_raw; + fputil::FPBits::UIntType float_raw = + static_cast::UIntType>(to_conv.conv_val_raw); fputil::FPBits float_bits(float_raw); if (!float_bits.is_inf_or_nan()) { return convert_float_decimal_typed(writer, to_conv, float_bits); @@ -1168,7 +1170,8 @@ float_bits); } } else { - fputil::FPBits::UIntType float_raw = to_conv.conv_val_raw; + fputil::FPBits::UIntType float_raw = + static_cast::UIntType>(to_conv.conv_val_raw); fputil::FPBits float_bits(float_raw); if (!float_bits.is_inf_or_nan()) { return convert_float_dec_exp_typed(writer, to_conv, float_bits); @@ -1188,7 +1191,8 @@ float_bits); } } else { - fputil::FPBits::UIntType float_raw = to_conv.conv_val_raw; + fputil::FPBits::UIntType float_raw = + static_cast::UIntType>(to_conv.conv_val_raw); fputil::FPBits float_bits(float_raw); if (!float_bits.is_inf_or_nan()) { return convert_float_dec_auto_typed(writer, to_conv, float_bits); diff --git a/libc/src/stdio/printf_core/float_hex_converter.h b/libc/src/stdio/printf_core/float_hex_converter.h --- a/libc/src/stdio/printf_core/float_hex_converter.h +++ b/libc/src/stdio/printf_core/float_hex_converter.h @@ -52,7 +52,8 @@ } else { mantissa_width = fputil::MantissaWidth::VALUE; exponent_bias = fputil::FPBits::EXPONENT_BIAS; - fputil::FPBits::UIntType float_raw = to_conv.conv_val_raw; + fputil::FPBits::UIntType float_raw = + static_cast::UIntType>(to_conv.conv_val_raw); fputil::FPBits float_bits(float_raw); is_negative = float_bits.get_sign(); exponent = float_bits.get_exponent(); @@ -146,9 +147,10 @@ size_t mant_cur = mant_len; size_t first_non_zero = 1; - for (; mant_cur > 0; --mant_cur, mantissa /= 16) { - char new_digit = ((mantissa % 16) > 9) ? ((mantissa % 16) - 10 + a) - : ((mantissa % 16) + '0'); + for (; mant_cur > 0; --mant_cur, mantissa >>= 4) { + char mant_mod_16 = static_cast(mantissa) & 15; + char new_digit = + (mant_mod_16 > 9) ? (mant_mod_16 - 10 + a) : (mant_mod_16 + '0'); mant_buffer[mant_cur - 1] = new_digit; if (new_digit != '0' && first_non_zero < mant_cur) first_non_zero = mant_cur; diff --git a/libc/src/stdio/printf_core/float_inf_nan_converter.h b/libc/src/stdio/printf_core/float_inf_nan_converter.h --- a/libc/src/stdio/printf_core/float_inf_nan_converter.h +++ b/libc/src/stdio/printf_core/float_inf_nan_converter.h @@ -36,7 +36,8 @@ is_negative = float_bits.get_sign(); mantissa = float_bits.get_explicit_mantissa(); } else { - fputil::FPBits::UIntType float_raw = to_conv.conv_val_raw; + fputil::FPBits::UIntType float_raw = + static_cast::UIntType>(to_conv.conv_val_raw); fputil::FPBits float_bits(float_raw); is_negative = float_bits.get_sign(); mantissa = float_bits.get_explicit_mantissa(); diff --git a/libc/src/stdio/printf_core/int_converter.h b/libc/src/stdio/printf_core/int_converter.h --- a/libc/src/stdio/printf_core/int_converter.h +++ b/libc/src/stdio/printf_core/int_converter.h @@ -43,7 +43,7 @@ static constexpr size_t BITS_IN_BYTE = 8; static constexpr size_t BITS_IN_NUM = sizeof(uintmax_t) * BITS_IN_BYTE; - uintmax_t num = to_conv.conv_val_raw; + uintmax_t num = static_cast(to_conv.conv_val_raw); bool is_negative = false; FormatFlags flags = to_conv.flags; diff --git a/libc/test/UnitTest/LibcTest.cpp b/libc/test/UnitTest/LibcTest.cpp --- a/libc/test/UnitTest/LibcTest.cpp +++ b/libc/test/UnitTest/LibcTest.cpp @@ -31,8 +31,7 @@ // When the value is UInt128, __uint128_t or wider, show its hexadecimal digits. template -cpp::enable_if_t && cpp::is_unsigned_v && - (sizeof(T) > sizeof(uint64_t)), +cpp::enable_if_t && (sizeof(T) > sizeof(uint64_t)), cpp::string> describeValue(T Value) { static_assert(sizeof(T) % 8 == 0, "Unsupported size of UInt"); @@ -226,6 +225,13 @@ const char *RHSStr, Location Loc); #endif +template bool test<__llvm_libc::cpp::Int<128>>(RunContext *Ctx, TestCond Cond, + __llvm_libc::cpp::Int<128> LHS, + __llvm_libc::cpp::Int<128> RHS, + const char *LHSStr, + const char *RHSStr, + Location Loc); + template bool test<__llvm_libc::cpp::UInt<128>>(RunContext *Ctx, TestCond Cond, __llvm_libc::cpp::UInt<128> LHS, __llvm_libc::cpp::UInt<128> RHS, diff --git a/libc/test/src/__support/uint_test.cpp b/libc/test/src/__support/uint_test.cpp --- a/libc/test/src/__support/uint_test.cpp +++ b/libc/test/src/__support/uint_test.cpp @@ -21,6 +21,9 @@ using LL_UInt512 = __llvm_libc::cpp::UInt<512>; using LL_UInt1024 = __llvm_libc::cpp::UInt<1024>; +using LL_Int128 = __llvm_libc::cpp::Int<128>; +using LL_Int192 = __llvm_libc::cpp::Int<192>; + TEST(LlvmLibcUIntClassTest, BasicInit) { LL_UInt128 empty; LL_UInt128 half_val(12345); @@ -560,3 +563,75 @@ TEST_QUICK_DIV_UINT32_POW2(1000000000, 75); TEST_QUICK_DIV_UINT32_POW2(1000000000, 101); } + +TEST(LlvmLibcUIntClassTest, ComparisonInt128Tests) { + LL_Int128 a(123); + LL_Int128 b(0); + LL_Int128 c(-1); + + ASSERT_TRUE(a == a); + ASSERT_TRUE(b == b); + ASSERT_TRUE(c == c); + + ASSERT_TRUE(a != b); + ASSERT_TRUE(a != c); + ASSERT_TRUE(b != a); + ASSERT_TRUE(b != c); + ASSERT_TRUE(c != a); + ASSERT_TRUE(c != b); + + ASSERT_TRUE(a > b); + ASSERT_TRUE(a >= b); + ASSERT_TRUE(a > c); + ASSERT_TRUE(a >= c); + ASSERT_TRUE(b > c); + ASSERT_TRUE(b >= c); + + ASSERT_TRUE(b < a); + ASSERT_TRUE(b <= a); + ASSERT_TRUE(c < a); + ASSERT_TRUE(c <= a); + ASSERT_TRUE(c < b); + ASSERT_TRUE(c <= b); +} + +TEST(LlvmLibcUIntClassTest, BasicArithmeticInt128Tests) { + LL_Int128 a(123); + LL_Int128 b(0); + LL_Int128 c(-3); + + ASSERT_EQ(a * a, LL_Int128(123 * 123)); + ASSERT_EQ(a * c, LL_Int128(-369)); + ASSERT_EQ(c * a, LL_Int128(-369)); + ASSERT_EQ(c * c, LL_Int128(9)); + ASSERT_EQ(a * b, b); + ASSERT_EQ(b * a, b); + ASSERT_EQ(b * c, b); + ASSERT_EQ(c * b, b); +} + +#ifdef __SIZEOF_INT128__ + +TEST(LlvmLibcUIntClassTest, ConstructorFromUInt128Tests) { + __uint128_t a = (__uint128_t(123) << 64) + 1; + __int128_t b = -static_cast<__int128_t>(a); + LL_Int128 c(a); + LL_Int128 d(b); + + LL_Int192 e(a); + LL_Int192 f(b); + + ASSERT_EQ(static_cast(c), 1); + ASSERT_EQ(static_cast(c >> 64), 123); + ASSERT_EQ(static_cast(d), static_cast(b)); + ASSERT_EQ(static_cast(d >> 64), static_cast(b >> 64)); + ASSERT_EQ(c + d, LL_Int128(a + b)); + + ASSERT_EQ(static_cast(e), 1); + ASSERT_EQ(static_cast(e >> 64), 123); + ASSERT_EQ(static_cast(f), static_cast(b)); + ASSERT_EQ(static_cast(f >> 64), static_cast(b >> 64)); + ASSERT_EQ(LL_UInt192(e + f), LL_UInt192(a + b)); +} + +#endif // __SIZEOF_INT128__ diff --git a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/libc/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/libc/BUILD.bazel @@ -445,6 +445,7 @@ ":__support_fputil_fenv_impl", ":__support_fputil_fp_bits", ":__support_fputil_rounding_mode", + ":__support_fputil_dyadic_float", ":__support_str_to_integer", ":__support_str_to_num_result", ":__support_uint128", @@ -1140,6 +1141,7 @@ hdrs = ["src/math/generic/log_range_reduction.h"], deps = [ ":__support_common", + ":__support_uint128", ":__support_fputil_dyadic_float", ":common_constants", ],