1
\$\begingroup\$

Per feed back for this question, I have written an unsigned 128 bit integer for Windows. The class first determines if it is in a 64 bit environment. It only creates the class if it is in a Windows 64 bit environment that supports MS intrinsic functions. Else it falls back to 32 bit mode. It also checks if either GCC or Clang unsigned 128 bit numbers are supported.

My biggest concern is of I got the macro definitions correct. I have not really done much in that area before.

uint_128_t.h

#include <compare>
#include <limits>
#include <string>

#if SIZE_MAX > 0xFFFFFFFFUL
    #define ENV_64
#else
    #define ENV_32
#endif

#if defined(__SIZEOF_INT128__)
    #if (defined(__clang__) && !defined(_WIN32)) || (defined(__GNUC__) && !defined(__clang__)
        #define INT_128
    #endif

#elif defined(ENV_64)
    #if defined(_MSC_VER) && !defined(_M_ARM64EC)
        #define WIN_128
        #include <intrin.h>
        #include <immintrin.h>
        #pragma intrinsic(_umul128, _udiv128)
    #else
        #define ENV_32  // Fallback to a 32 bit environment.
    #endif
#endif

namespace Olly {

    #if defined(WIN_128)
    /********************************************************************************************/
    //
    //                                    'unsigned_int_128_t' class
    //
    //        The unsigned_int_128_t class implements a Microsoft intrinsic unsigned 128 bit
    //        integer. 
    //
    /********************************************************************************************/

    class uint_128_t {

    public:

        uint_128_t();
        uint_128_t(unsigned __int64 n);
        ~uint_128_t();

        uint_128_t(uint_128_t&& obj)                 = default;
        uint_128_t(const uint_128_t& obj)            = default;
        uint_128_t& operator=(uint_128_t&& obj)      = default;
        uint_128_t& operator=(const uint_128_t& obj) = default;

        friend void swap(uint_128_t& first, uint_128_t& second);

        operator unsigned __int64() const;

        operator bool() const;

        bool operator==(const uint_128_t& b) const;
        bool operator!=(const uint_128_t& b) const;

        std::partial_ordering operator<=>(const uint_128_t& b) const;

        uint_128_t& operator&=(const uint_128_t& other);
        uint_128_t& operator|=(const uint_128_t& other);
        uint_128_t& operator^=(const uint_128_t& other);

        uint_128_t operator&(const uint_128_t& b) const;
        uint_128_t operator|(const uint_128_t& b) const;
        uint_128_t operator^(const uint_128_t& b) const;
        uint_128_t operator~() const;

        friend uint_128_t operator&(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t operator|(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t operator^(uint_128_t&& a, const uint_128_t& b);

        uint_128_t& operator<<=(unsigned __int64 index);
        uint_128_t& operator>>=(unsigned __int64 index);

        uint_128_t operator<<(unsigned __int64 index) const;
        uint_128_t operator>>(unsigned __int64 index) const;

        friend uint_128_t operator<<(uint_128_t&& a, unsigned __int64 index);
        friend uint_128_t operator>>(uint_128_t&& a, unsigned __int64 index);

        uint_128_t& operator+=(const uint_128_t& other);
        uint_128_t& operator-=(const uint_128_t& other);
        uint_128_t& operator*=(const uint_128_t& other);
        uint_128_t& operator/=(const uint_128_t& other);
        uint_128_t& operator%=(const uint_128_t& other);

        uint_128_t operator+(const uint_128_t& b) const;
        uint_128_t operator-(const uint_128_t& b) const;
        uint_128_t operator*(const uint_128_t& b) const;
        uint_128_t operator/(const uint_128_t& b) const;
        uint_128_t operator%(const uint_128_t& b) const;

        friend uint_128_t&& operator+(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t&& operator-(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t&& operator*(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t&& operator/(uint_128_t&& a, const uint_128_t& b);
        friend uint_128_t&& operator%(uint_128_t&& a, const uint_128_t& b);

        uint_128_t& operator++();
        uint_128_t  operator++(int);

        uint_128_t& operator--();
        uint_128_t  operator--(int);

        unsigned __int64 upper() const;
        unsigned __int64 lower() const;

    private:

        unsigned __int64 _upper;
        unsigned __int64 _lower;

        static const unsigned __int64 half_word_size = 32;
        static const unsigned __int64 half_word_mask = (~unsigned __int64(0) >> half_word_size);
    };
    #endif

    #if defined(ENV_64)
        using word_t = uint_fast64_t;

        #if  defined(__GNUC__) && defined(INT_128)
            using double_word_t = unsigned __int128;

        #elif defined(__clang__) && defined(INT_128)
            using double_word_t = unsigned __int128_t;

        #elif defined(__xlC__) && defined(INT_128)
            using double_word_t = __uint128_t;

        #elif defined(WIN_128)
            using double_word_t = uint_128_t;

        #endif

    #elif defined(ENV_32)
        using        word_t = uint_fast32_t;
        using double_word_t = uint_fast64_t;
    #endif
}

uint_128_t.cpp

#include "./uint_128_t.h"

namespace Olly {

    #if defined(WIN_128)

    uint_128_t::uint_128_t() : _upper(0), _lower(0) {
    }

    uint_128_t::uint_128_t(unsigned __int64 n) : _upper(0), _lower(n) {
    }

    uint_128_t::~uint_128_t() {
    }

    void swap(uint_128_t& left, uint_128_t& right) {
        std::swap(left, right);
    }

    uint_128_t::operator unsigned __int64() const {
        return _lower;
    }

    uint_128_t::operator bool() const {
        return _upper || _lower;
    }

    bool uint_128_t::operator==(const uint_128_t& b) const {
        return _upper == _upper && _lower == _lower;
    }

    bool uint_128_t::operator!=(const uint_128_t& b) const {
        return !operator==(b);
    }

    std::partial_ordering uint_128_t::operator<=>(const uint_128_t& b) const {

        if (_upper > b._upper) {
            return std::partial_ordering::greater;
        }

        if (_upper < b._upper) {
            return std::partial_ordering::less;
        }

        if (_lower > b._lower) {
            return std::partial_ordering::greater;
        }

        if (_lower < b._lower) {
            return std::partial_ordering::less;
        }

        return std::partial_ordering::equivalent;
    }

    uint_128_t& uint_128_t::operator&=(const uint_128_t& other) {

        _upper &= other._upper;
        _lower &= other._lower;

        return *this;
    }

    uint_128_t& uint_128_t::operator|=(const uint_128_t& other) {

        _upper |= other._upper;
        _lower |= other._lower;

        return *this;
    }

    uint_128_t& uint_128_t::operator^=(const uint_128_t& other) {

        _upper ^= other._upper;
        _lower ^= other._lower;

        return *this;
    }

    uint_128_t uint_128_t::operator&(const uint_128_t& b) const {

        uint_128_t a(*this);

        a &= b;

        return a;
    }

    uint_128_t uint_128_t::operator|(const uint_128_t& b) const {

        uint_128_t a(*this);

        a |= b;

        return a;
    }

    uint_128_t uint_128_t::operator^(const uint_128_t& b) const {

        uint_128_t a(*this);

        a ^= b;

        return a;
    }

    uint_128_t uint_128_t::operator~() const {

        uint_128_t a;

        a._upper = ~_upper;
        a._lower = ~_lower;

        return a;
    }

    uint_128_t operator&(uint_128_t&& a, const uint_128_t& b) {
        return a &= b;
    }

    uint_128_t operator|(uint_128_t&& a, const uint_128_t& b) {
        return a |= b;
    }

    uint_128_t operator^(uint_128_t&& a, const uint_128_t& b) {
        return a ^= b;
    }

    uint_128_t& uint_128_t::operator<<=(unsigned __int64 index) {

        unsigned char i = static_cast<unsigned char>(index);

        unsigned char limit = 64;

        if (i == limit) {
            _upper = _lower;
            _lower = 0;
        }

        else if (i > limit) {

            _upper = _lower << (i - limit);

            _lower = 0;
        }

        else {

            auto mask = _lower >> (limit - i);

            _upper = (_upper << i) | mask;

            _lower <<= i;
        }

        return *this;
    }

    uint_128_t& uint_128_t::operator>>=(unsigned __int64 index) {

        unsigned char i = static_cast<unsigned char>(index);

        unsigned char limit = 64;

        if (i == limit) {
            _lower = _upper;
            _upper = 0;
        }

        else if (i > limit) {

            _lower = _upper >> (i - limit);

            _upper = 0;
        }

        else {

            auto mask = _upper >> (limit - i);

            _lower = (_lower >> i) | mask;

            _upper >>= i;
        }

        return *this;
    }

    uint_128_t uint_128_t::operator<<(unsigned __int64 index) const {

        uint_128_t a(*this);

        a <<= index;

        return a;
    }

    uint_128_t uint_128_t::operator>>(unsigned __int64 index) const {

        uint_128_t a(*this);

        a >>= index;

        return a;
    }

    uint_128_t operator<<(uint_128_t&& a, unsigned __int64 index) {
        return a <<= index;
    }

    uint_128_t operator>>(uint_128_t&& a, unsigned __int64 index) {
        return a >>= index;
    }

    uint_128_t& uint_128_t::operator+=(const uint_128_t& other) {

        unsigned __int64 n = _lower;

        _lower += other._lower;
        _upper += other._upper;

        if (_lower < n) {
            _upper += 1;
        }

        return *this;
    }

    uint_128_t& uint_128_t::operator-=(const uint_128_t& other) {

        unsigned __int64 n = _lower;

        _lower -= other._lower;
        _upper -= other._upper;

        if (other._lower > n) {
            _upper -= 1;
        }

        return *this;
    }

    uint_128_t& uint_128_t::operator*=(const uint_128_t& other) {

        unsigned __int64 carry;

        _lower = _umul128(_lower, other._lower, &carry);
        _upper = carry;

        return *this;
    }

    uint_128_t& uint_128_t::operator/=(const uint_128_t& other) {

        unsigned __int64 carry = 0;

        _lower = _udiv128(_upper, _lower, other._lower, &carry);
        _upper = carry;

        return *this;
    }

    uint_128_t& uint_128_t::operator%=(const uint_128_t& other) {

        unsigned __int64 carry = 0;

        _lower = _udiv128(_upper, _lower, other._lower, &carry);

        _lower = carry;
        _upper = 0;

        return *this;
    }

    uint_128_t uint_128_t::operator+(const uint_128_t& b) const {

        uint_128_t a(*this);

        a += b;

        return a;
    }

    uint_128_t uint_128_t::operator-(const uint_128_t& b) const {

        uint_128_t a(*this);

        a -= b;

        return a;
    }

    uint_128_t uint_128_t::operator*(const uint_128_t& b) const {

        uint_128_t a(*this);

        a *= b;

        return a;
    }

    uint_128_t uint_128_t::operator/(const uint_128_t& b) const {

        uint_128_t a(*this);

        a /= b;

        return a;
    }

    uint_128_t uint_128_t::operator%(const uint_128_t& b) const {

        uint_128_t a(*this);

        a %= b;

        return a;
    }

    uint_128_t&& operator+(uint_128_t&& a, const uint_128_t& b) {
        a += b;
        return std::move(a);
    }

    uint_128_t&& operator-(uint_128_t&& a, const uint_128_t& b) {
        a -= b;
        return std::move(a);
    }

    uint_128_t&& operator*(uint_128_t&& a, const uint_128_t& b) {
        a *= b;
        return std::move(a);
    }

    uint_128_t&& operator/(uint_128_t&& a, const uint_128_t& b) {
        a /= b;
        return std::move(a);
    }

    uint_128_t&& operator%(uint_128_t&& a, const uint_128_t& b) {
        a %= b;
        return std::move(a);
    }

    uint_128_t& uint_128_t::operator++() {

        uint_128_t one(1);

        operator+=(one);

        return *this;
    }

    uint_128_t uint_128_t::operator++(int) {

        uint_128_t a(*this);

        operator++();

        return a;
    }

    uint_128_t& uint_128_t::operator--() {

        uint_128_t one(1);

        operator-=(one);

        return *this;
    }

    uint_128_t uint_128_t::operator--(int) {

        uint_128_t a(*this);

        operator--();

        return a;
    }

    unsigned __int64 uint_128_t::upper() const {
        return _upper;
    }

    unsigned __int64 uint_128_t::lower() const {
        return _lower;
    }
#endif
}
\$\endgroup\$
5
  • \$\begingroup\$ What are your review goals? \$\endgroup\$ May 23, 2023 at 21:22
  • \$\begingroup\$ @chux - Reinstate Monica, the goal is to make sure it works as intended and to make sure I don’t have any major issues I’m not seeing. The class will be integrated in to a small rework of the bitvector class from the other question. I’m open to any feedback. I just do this stuff in my free time. So I am certain there are some misconceptions or bad habits I have. \$\endgroup\$
    – StormCrow
    May 23, 2023 at 21:31
  • \$\begingroup\$ StormCrow, I hope you feel the code that already works correctly (to the best of your knowledge) and not goal is to make sure it works as intended. \$\endgroup\$ May 24, 2023 at 1:13
  • \$\begingroup\$ BTW, Where is __int64 defined? Looks like a compiler specific keyword. I don't think it is standard C++. \$\endgroup\$ May 24, 2023 at 1:15
  • \$\begingroup\$ @chux - Reinstate Monica, I do feel that the code works as best as possible to my ability. I do have some concerns around the #ifdefs though. I don't have much experience using them in code definition, as they are used here. In a previous post, my use of them had been incorrect, due to a knowledge gap on my part. __int64 is compiler specific to Microsoft's compiler. The reason it is being used is that is what the intrinsic MS specific function use. Hence since the class relies on them, I want it to be apparent it is compiler specific. \$\endgroup\$
    – StormCrow
    May 24, 2023 at 11:54

2 Answers 2

2
\$\begingroup\$

Multiplication does not multiply 128-bit integers

Well that's a strange one. Only the low halves of the inputs are multiplied together, forming a 128-bit result. That's so obvious that it looks intentional.. and it's an entirely legitimate operation, but it's really strange to have it in this place, implementing the multiplication operator of a 128-bit integer.

Division/remainder implement 64-bit division with double-width dividend

They're not "real" 128-bit division and remainder either, since they ignore the upper half of the divisor. Once again they are useful operations (perhaps ironically, one thing they are useful for is to implement actual 128-bit division and remainder, but that's not what they are by themselves, it takes extra code), but should they be here, as implementations of /= and %= between two 128-bit integers?

Note that these can easily fail with a division error, if the quotient would not fit in 64 bits. That even applies to the remainder operation, where we discard the quotient (the remainder would fit in 64 bits by definition, which your code reflects by setting _upper = 0, but that's only because this isn't an actual 128-bit remainder operation). I would not expect such semantics from operator%= on a 128-bit integer.

Shift by too large shift count is possible

operator>>= and operator<<= do not prevent a too high shift count in _upper >> (i - limit) (and the similar code in the other operator). i could be as high as 255, i - limit would then be 191.

Maybe that's OK, following the idea that a too high shift count should not be passed anyway. It's easy to prevent though, for example you can set i = index & 0x7F.

By the way the cases where i is equal to the limit and where i is greater than the limit can be merged into one case where i >= limit. I'm not sure they should be, but it's possible at least.

\$\endgroup\$
6
  • \$\begingroup\$ Thank you very much for the feedback! The focus for the class is to be used within an arbitrary precision whole number class. The need for 128 bit is for handling 64 bit manipulation. Given you answer I probably should have included it here too. But I thought it would be better to look at the 128 bit class implementation first. I'll incorporate that in to a follow up combined post. \$\endgroup\$
    – StormCrow
    May 24, 2023 at 12:02
  • \$\begingroup\$ Duly noted on the shift operators. Thanks! \$\endgroup\$
    – StormCrow
    May 24, 2023 at 12:11
  • 1
    \$\begingroup\$ These multiplication and division operators would be useful in the context of implementing arbitrary precision whole numbers, but then IMO they are they wrong abstraction: from the interface that they expose to the world they look like something they're not (namely full 128-bit operations, instead of abstractions of 64*64->128 multiplication and 128/64->64 division) \$\endgroup\$
    – user555045
    May 24, 2023 at 12:23
  • \$\begingroup\$ Completely fair point. I was just trying to think of a better name that does not imply the same expectation of utility. Open to suggestion if you have any. \$\endgroup\$
    – StormCrow
    May 24, 2023 at 12:26
  • 1
    \$\begingroup\$ @StormCrow "better name" --> perhaps: uint_128_t mult64by64(uint64_t a, uint64_t b). \$\endgroup\$ May 24, 2023 at 13:41
1
\$\begingroup\$

Design: shift argument

I'd expect the type of the shift count to be an unsigned or int and not uint64. I expect this to match a future true uint128_t type.

// uint_128_t operator<<(uint_128_t&& a, unsigned __int64 index)
uint_128_t operator<<(uint_128_t&& a, unsigned index)

Suggested additional operators

Add (easy):

uint_128_t operator-() const;
uint_128_t operator+() const;
int operator!() const;

Add (hard): some to/from stream ones (decimal text conversion).

Name space

uint_128_t.h defines ENV_64 which can surprisingly collide with other code. Consider something along the lines of uint_128_ENV_64.

namespace Olly is unclear in uint_128_t.h. Use a better name.

Unneeded L

// #if SIZE_MAX > 0xFFFFFFFFUL
#if SIZE_MAX > 0xFFFFFFFFU

More meaningful

#if SIZE_MAX > UINT32_MAX

Portability

Consider moving to (u)int64_t instead of unsigned __int64.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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