11
\$\begingroup\$

I made a simple uint128_t implementation for a project that I'm working on. The reason for not using for example boost::uint128_t is that it is not fully constexpr like I would like it to be.

For this reason, I only implemented the operators that I'm going to use. I'm for example not interested in operator*, as I will never multiply 2 such numbers. Same for operator/ and others.

Any comments will be welcome! :)

#ifndef UINT128_HPP
#define UINT128_HPP

#include <type_traits>
#include <cstdint>
#include <array>
#include <ostream>



namespace types {

// special class to represent a 128 bit unsigned number
// some shortcuts were taken to not make it too unnecessary complex
struct uint128_t final {
    constexpr uint128_t() = default;

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t(T&& num) noexcept : array{ static_cast<std::uint64_t>(num), 0ull } {}

    template<typename T>
    friend constexpr uint128_t operator&(uint128_t lhs, T&& rhs) noexcept {
        return lhs &= rhs;
    }

    constexpr uint128_t& operator&=(const uint128_t& rhs) noexcept {
        array[0] &= rhs.array[0];
        array[1] &= rhs.array[1];
        return *this;
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator&=(T&& rhs) noexcept {
        array[0] &= rhs;
        array[1] = 0;
        return *this;
    }



    template<typename T>
    friend constexpr uint128_t operator|(uint128_t lhs, T&& rhs) noexcept {
        return lhs |= rhs;
    }

    constexpr uint128_t& operator|=(const uint128_t& rhs) noexcept {
        array[0] |= rhs.array[0];
        array[1] |= rhs.array[1];
        return *this;
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator|=(T&& rhs) noexcept {
        array[0] |= rhs;
        return *this;
    }



    template<typename T>
    friend constexpr uint128_t operator^(uint128_t lhs, T&& rhs) noexcept {
        return lhs ^= rhs;
    }

    constexpr uint128_t& operator^=(const uint128_t& rhs) noexcept {
        array[0] ^= rhs.array[0];
        array[1] ^= rhs.array[1];
        return *this;
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator^=(T&& rhs) noexcept {
        array[0] ^= rhs;
        return *this;
    }



    friend constexpr uint128_t operator~(uint128_t value) noexcept {
        value.array = { ~value.array[0], ~value.array[1] };
        return value;
    }



    template<typename T>
    friend constexpr uint128_t operator<<(uint128_t lhs, T&& rhs) noexcept {
        return lhs <<= rhs;
    }

    constexpr uint128_t& operator<<=(const uint128_t& rhs) noexcept {
        if (rhs.array[1] > 0)
            return array = {}, *this;
        return *this <<= rhs.array[0];
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator<<=(T&& rhs) noexcept {
        if (rhs == 0)
            return *this;

        const auto backup = array[1];
        array[1] = array[0];
        if (rhs < 64) {
            array[0] <<= rhs;
            array[1] >>= 64 - rhs;
            array[1] |= backup << rhs;
        }
        else {
            array[0] = 0;
            array[1] <<= rhs - 64;
        }

        return *this;
    }



    template<typename T>
    friend constexpr uint128_t operator>>(uint128_t lhs, T&& rhs) noexcept {
        return lhs >>= rhs;
    }

    constexpr uint128_t& operator>>=(const uint128_t& rhs) noexcept {
        if (rhs.array[1] > 0)
            return array = {}, *this;
        return *this >>= rhs.array[0];
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator>>=(T&& rhs) noexcept {
        if (rhs == 0)
            return *this;

        const auto backup = array[0];
        array[0] = array[1];
        if (rhs < 64) {
            array[1] >>= rhs;
            array[0] <<= 64 - rhs;
            array[0] |= backup >> rhs;
        }
        else {
            array[1] = 0;
            array[0] >>= rhs - 64;
        }

        return *this;
    }



    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr bool operator==(T&& rhs) const noexcept {
        return array[0] == static_cast<std::uint64_t>(rhs) && array[1] == 0;
    }

    constexpr bool operator==(const uint128_t& rhs) const noexcept {
        return array[0] == rhs.array[0] && array[1] == rhs.array[1];
    }

    template<typename T>
    constexpr bool operator!=(T&& rhs) const noexcept {
        return !(*this == rhs);
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr bool operator<(T&& rhs) const noexcept {
        return array[0] < static_cast<std::uint64_t>(rhs) && array[1] == 0;
    }

    constexpr bool operator<(const uint128_t& rhs) const noexcept {
        if (array[1] == rhs.array[1])
            return array[0] < rhs.array[0];
        return array[1] < rhs.array[1];
    }

    template<typename T>
    constexpr bool operator>(T&& rhs) const noexcept {
        return *this >= rhs && *this != rhs;
    }

    template<typename T>
    constexpr bool operator<=(T&& rhs) const noexcept {
        return !(*this > rhs);
    }

    template<typename T>
    constexpr bool operator>=(T&& rhs) const noexcept {
        return !(*this < rhs);
    }



    template<typename T>
    friend constexpr uint128_t operator+(uint128_t lhs, T&& rhs) noexcept {
        return lhs += rhs;
    }

    constexpr uint128_t& operator+=(const uint128_t& rhs) noexcept {
        *this += rhs.array[0];
        array[1] += rhs.array[1];
        return *this;
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator+=(T&& rhs) noexcept {
        // overflow guard
        if (array[0] + rhs < array[0])
            ++array[1];
        array[0] += rhs;
        return *this;
    }



    template<typename T>
    friend constexpr uint128_t operator-(uint128_t lhs, T&& rhs) noexcept {
        return lhs -= rhs;
    }

    constexpr uint128_t& operator-=(const uint128_t& rhs) noexcept {
        *this -= rhs.array[0];
        array[1] -= rhs.array[1];
        return *this;
    }

    template<typename T, typename = std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator-=(T&& rhs) noexcept {
        // overflow guard
        if (array[0] - rhs > array[0])
            --array[1];
        array[0] -= rhs;
        return *this;
    }



    friend std::ostream& operator<<(std::ostream& stream, const uint128_t& num) noexcept {
        return stream << '[' << num.array[0] << " + " << "2**64 * " << num.array[1] << ']';
    }
private:
    std::array<uint64_t, 2> array{};
};

}

#endif
\$\endgroup\$
  • \$\begingroup\$ Note: I marked this review as C++17, although I think it should be able to compile under C++14. The reason being is that I would like to leverage newer features if possible :) \$\endgroup\$ – Rakete1111 May 27 '17 at 20:29
  • 4
    \$\begingroup\$ Why not take boost::uint128_t upgrade it. Then you can submit it back to boost. \$\endgroup\$ – Martin York May 28 '17 at 2:16
3
\$\begingroup\$

Avoid Simple Header Guard Collisions

#ifndef UINT128_HPP
#define UINT128_HPP

Don't just name the guard after the filename. Append differentiators (file path, GUID, date, etc) to minimize the chance of collision. An example

<project>_<path_part1>_..._<path_partN>_<file>_<extension>_<guid>

// include/pet/project/file.hpp
#ifndef PET_PROJECT_FILE_HPP_68B24FD6E49248409028D9814FE4CD515

Negative Values

    template<typename T, typename = 
      std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t(T&& num) noexcept 
      : array{ static_cast<std::uint64_t>(num), 0ull } {}

The integral conversion rules for values with an unsigned destination is defined. From the C++ standard (n4659 §7.8.2):

If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer (modulo \$2^n\$ where n is the number of bits used to represent the unsigned type). [Note: In a two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation). — end note]

Say we want to the maximum value of uint128_t. For the built-in integral types, we can construct them with the value -1. Constructing a uint128_t with a value of -1 only sets the low bits. You should check to see if num is negative and set the high bits appropriately.

    template<typename T, typename = 
      std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t(T&& num) noexcept 
      : array{ static_cast<std::uint64_t>(num)
             , static_cast<std::uint64_t>((num >= 0) ? 0 : -1) } {}

Your functions that take a templated integral argument need to be corrected.


Undefined Behavior

    template<typename T, typename = 
        std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator<<=(T&& rhs) noexcept {
        if (rhs == 0)
            return *this;

        const auto backup = array[1];
        array[1] = array[0];
        if (rhs < 64) {
            array[0] <<= rhs;
            array[1] >>= 64 - rhs;
            array[1] |= backup << rhs;
        }
        else {
            array[0] = 0;
            array[1] <<= rhs - 64;
        }

        return *this;
    }

In your final else block, you have undefined behavior if rhs >= 128 (n4659 §8.8.1).

The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

    template<typename T, typename = 
        std::enable_if_t<std::is_integral_v<std::decay_t<T>>>>
    constexpr uint128_t& operator<<=(T&& rhs) noexcept {
        if (rhs < 64) {
            if (rhs != 0) {
                array[1] = (array[1] << rhs) | (array[0] >> (64 - rhs));
                array[0] = array[0] << rhs;
            }
        }                
        else if (rhs < 128) {
            array[0] = 0;
            array[1] = array[1] << (rhs - 64);
        }
        else {
            array = {};
        }
        return *this;
    }

Don't Abuse the Comma Operator

    constexpr uint128_t& operator>>=(const uint128_t& rhs) noexcept {
        if (rhs.array[1] > 0)
            return array = {}, *this;
        return *this >>= rhs.array[0];
    }

Simplifying The Comparators

    constexpr bool operator==(const uint128_t& rhs) const noexcept {
        return array[0] == rhs.array[0] && array[1] == rhs.array[1];
    }

std::tuple (requires <tuple>) provides simple lexicographical comparisons that works at compile-time (unlike std::arrays comparators). We can create std::tuples on the fly with std::tie().

    constexpr auto tie() const noexcept {
        return std::tie(array[1], array[0]);
    }

    constexpr bool operator==(const uint128_t& rhs) const noexcept {
        return tie() == rhs.tie();
    }

    constexpr bool operator<(const uint128_t& rhs) const noexcept {
        return tie() < rhs.tie();
    }

    // ...

You'll notice that many of your functions have the same boilerplate. You can use the pre-processor to generate all of the comparators.

    #define COMP128(op)                                               \
    constexpr bool operator op(const uint128_t& rhs) const noexcept { \
        return tie() op rhs.tie();                                    \
    }

    COMP128(==)
    COMP128(!=)
    COMP128(>=)
    COMP128(<=)
    COMP128(>)
    COMP128(<)

    #undef COMP128

Similarly, the preprocessor could also be used to generate the logic/logic-assignment operators.


    std::array<uint64_t, 2> array{};

The use of std::array<> feels like unnecessary obfuscation. I'd recommend using two variables with descriptive names (like lo and hi).

\$\endgroup\$
  • \$\begingroup\$ Thanks! lo and hi aren't very descriptive though :) \$\endgroup\$ – Rakete1111 May 31 '17 at 14:24
  • \$\begingroup\$ @Rakete1111, I'm afraid you're not old enough to understand them :) I'm pretty young too though. \$\endgroup\$ – Incomputable May 31 '17 at 22:49
  • \$\begingroup\$ Just as a heads-up, your point about undefined behavior relies on the existence of 128bit numbers on a specific platform. Ignoring the fact that there is probably no platform having that behavior, a lot of my other code would also be wrong as a result of 128bit intergers. \$\endgroup\$ – Rakete1111 Jun 1 '17 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.