1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_bigint128.h
28 #ifndef VOGL_BIGINT128_H
29 #define VOGL_BIGINT128_H
31 #include "vogl_core.h"
32 #include "vogl_rand.h"
36 // Straightforward, portable 128-bit signed integer class.
37 // Mostly intended to simplifying dealing with either signed or unsigned 64-bit values in a universal way.
38 // Not particularly fast or flexible, it can't return 256 bits from 128*128 muls yet which is annoying.
39 class bigint128 : public utils::relative_ops<bigint128>
53 inline bigint128(int32 x)
58 inline bigint128(int64_t x)
63 inline bigint128(uint32 x)
68 inline bigint128(uint64_t x)
73 inline bigint128(uint64_t l, uint64_t h)
78 inline bigint128 &set(uint64_t l, uint64_t h)
85 bigint128(const void *p, uint type_size_in_bytes, bool type_is_signed)
87 set_from_ptr(p, type_size_in_bytes, type_is_signed);
90 inline uint64_t get_qword(uint index) const
92 return m_v[math::open_range_check<uint>(index, cMaxQWORDs)];
94 inline bigint128 &set_qword(uint index, uint64_t val)
96 m_v[math::open_range_check<uint>(index, cMaxQWORDs)] = val;
100 inline uint32 get_dword(uint index) const
102 VOGL_ASSERT(index < cMaxDWORDs);
103 uint64_t x = get_qword(index >> 1);
106 return static_cast<uint32>(x);
109 inline bigint128 &set_dword(uint index, uint32 val)
111 VOGL_ASSERT(index < cMaxDWORDs);
112 uint qword_index = index >> 1U;
113 uint shift = (index & 1) ? 32U : 0U;
115 uint64_t mask = cUINT32_MAX;
118 m_v[qword_index] &= ~mask;
119 m_v[qword_index] |= (static_cast<uint64_t>(val) << shift);
130 inline bigint128 &operator=(int64_t x)
137 inline bigint128 &operator=(int32 x)
139 *this = static_cast<int64_t>(x);
143 inline bigint128 &operator=(uint64_t x)
150 inline bigint128 &operator=(uint32 x)
152 *this = static_cast<uint64_t>(x);
156 inline operator int8() const
158 return static_cast<int8>(m_v[0]);
161 inline operator int16() const
163 return static_cast<int16>(m_v[0]);
166 inline operator int32() const
168 return static_cast<int32>(m_v[0]);
171 inline operator int64_t() const
173 return static_cast<int64_t>(m_v[0]);
176 inline operator uint8() const
178 return static_cast<uint8>(m_v[0]);
181 inline operator uint16() const
183 return static_cast<uint16>(m_v[0]);
186 inline operator uint32() const
188 return static_cast<uint32>(m_v[0]);
191 inline operator uint64_t() const
193 return static_cast<uint64_t>(m_v[0]);
196 inline bool is_zero() const
198 return (m_v[0] == 0) && (m_v[1] == 0);
201 inline operator bool() const
206 // FIXME: not endian safe, assumes little endian
207 bigint128 &set_from_ptr(const void *p, uint type_size_in_bytes, bool type_is_signed)
209 if (type_size_in_bytes == 0)
214 else if (type_size_in_bytes > cMaxBYTEs)
221 const uint8 *pSrc = reinterpret_cast<const uint8 *>(p);
222 uint8 *pDst = reinterpret_cast<uint8 *>(m_v);
223 memcpy(pDst, pSrc, type_size_in_bytes);
225 if (type_size_in_bytes < cMaxBYTEs)
230 bool is_signed = (pSrc[type_size_in_bytes - 1] & 0x80) != 0;
231 z = is_signed ? 0xFF : 0;
233 memset(pDst + type_size_in_bytes, z, cMaxBYTEs - type_size_in_bytes);
239 static inline void get_type_range(uint type_size_in_bytes, bool type_is_signed, bigint128 &min_val, bigint128 &max_val)
241 if ((!type_size_in_bytes) || (type_size_in_bytes > 16))
250 max_val <<= (type_size_in_bytes * 8U);
256 max_val = unsigned_shift_right(max_val, 1);
257 min_val = -max_val - 1U;
261 inline bool range_check(uint type_size_in_bytes, bool type_is_signed) const
263 if (!type_size_in_bytes)
268 else if (type_size_in_bytes > 16)
271 bigint128 min_val, max_val;
272 get_type_range(type_size_in_bytes, type_is_signed, min_val, max_val);
274 return (*this >= min_val) && (*this <= max_val);
276 return unsigned_less_equal(max_val);
279 inline bool is_negative() const
281 return static_cast<int64_t>(m_v[1]) < 0;
284 inline bool is_positive() const
286 return static_cast<int64_t>(m_v[1]) >= 0;
289 inline bigint128 operator+() const
294 inline bool operator==(const bigint128 &other) const
296 return (m_v[0] == other.m_v[0]) && (m_v[1] == other.m_v[1]);
298 inline bool operator==(int32 x) const
300 return *this == bigint128(x);
302 inline bool operator==(uint32 x) const
304 return *this == bigint128(x);
306 inline bool operator==(int64_t x) const
308 return *this == bigint128(x);
310 inline bool operator==(uint64_t x) const
312 return *this == bigint128(x);
315 inline bool unsigned_less(const bigint128 &other) const
317 if (m_v[1] < other.m_v[1])
319 else if (m_v[1] == other.m_v[1])
320 return m_v[0] < other.m_v[0];
324 inline bool unsigned_greater(const bigint128 &other) const
326 return other.unsigned_less(*this);
328 inline bool unsigned_less_equal(const bigint128 &other) const
330 return !other.unsigned_less(*this);
332 inline bool unsigned_greater_equal(const bigint128 &other) const
334 return !unsigned_less(other);
337 inline bool operator<(const bigint128 &other) const
339 if (static_cast<int64_t>(m_v[1]) < static_cast<int64_t>(other.m_v[1]))
341 else if (m_v[1] == other.m_v[1])
342 return m_v[0] < other.m_v[0];
346 inline bool operator<(int32 x) const
348 return *this < bigint128(x);
350 inline bool operator<(uint32 x) const
352 return *this < bigint128(x);
354 inline bool operator<(int64_t x) const
356 return *this < bigint128(x);
358 inline bool operator<(uint64_t x) const
360 return *this < bigint128(x);
362 inline bigint128 &operator-=(const bigint128 &other)
364 *this = *this - other;
367 inline bool operator<=(int32 x) const
369 return *this <= bigint128(x);
371 inline bool operator<=(uint32 x) const
373 return *this <= bigint128(x);
375 inline bool operator<=(int64_t x) const
377 return *this <= bigint128(x);
379 inline bool operator<=(uint64_t x) const
381 return *this <= bigint128(x);
384 inline bool operator>(int32 x) const
386 return *this > bigint128(x);
388 inline bool operator>(uint32 x) const
390 return *this > bigint128(x);
392 inline bool operator>(int64_t x) const
394 return *this > bigint128(x);
396 inline bool operator>(uint64_t x) const
398 return *this > bigint128(x);
401 inline bool operator>=(int32 x) const
403 return *this >= bigint128(x);
405 inline bool operator>=(uint32 x) const
407 return *this >= bigint128(x);
409 inline bool operator>=(int64_t x) const
411 return *this >= bigint128(x);
413 inline bool operator>=(uint64_t x) const
415 return *this >= bigint128(x);
418 inline bigint128 operator~() const
421 result.m_v[0] = ~m_v[0];
422 result.m_v[1] = ~m_v[1];
426 inline bigint128 &operator++()
428 bool carry = (m_v[0] == cUINT64_MAX);
434 inline bigint128 operator++(int)
436 bigint128 result(*this);
437 bool carry = (m_v[0] == cUINT64_MAX);
443 inline bigint128 &operator--()
445 bool carry = (m_v[0] == 0);
451 inline bigint128 operator--(int)
453 bigint128 result(*this);
454 bool carry = (m_v[0] == 0);
460 inline bigint128 &operator|=(const bigint128 &other)
462 *this = *this | other;
466 inline bigint128 &operator^=(const bigint128 &other)
468 *this = *this ^ other;
472 inline bigint128 &operator&=(const bigint128 &other)
474 *this = *this & other;
478 inline bigint128 &operator>>=(uint n)
484 inline bigint128 &operator<<=(uint n)
490 inline bigint128 get_abs() const
492 return is_negative() ? (-(*this)) : (*this);
495 friend inline bigint128 operator|(const bigint128 &lhs, const bigint128 &rhs)
497 return bigint128(lhs.m_v[0] | rhs.m_v[0], lhs.m_v[1] | rhs.m_v[1]);
500 friend inline bigint128 operator^(const bigint128 &lhs, const bigint128 &rhs)
502 return bigint128(lhs.m_v[0] ^ rhs.m_v[0], lhs.m_v[1] ^ rhs.m_v[1]);
505 friend inline bigint128 operator&(const bigint128 &lhs, const bigint128 &rhs)
507 return bigint128(lhs.m_v[0] & rhs.m_v[0], lhs.m_v[1] & rhs.m_v[1]);
510 friend inline bigint128 operator+(const bigint128 &lhs, const bigint128 &rhs)
514 result.m_v[0] = lhs.m_v[0] + rhs.m_v[0];
516 // Being careful here to avoid known gcc overflow bugs
517 uint64_t max_to_add_before_overflow = cUINT64_MAX - lhs.m_v[0];
518 bool carry = rhs.m_v[0] > max_to_add_before_overflow;
520 result.m_v[1] = lhs.m_v[1] + rhs.m_v[1] + carry;
524 inline bigint128 &operator+=(const bigint128 &other)
526 *this = *this + other;
530 friend inline bigint128 operator-(const bigint128 &lhs, const bigint128 &rhs)
534 result.m_v[0] = lhs.m_v[0] - rhs.m_v[0];
536 bool carry = rhs.m_v[0] > lhs.m_v[0];
538 result.m_v[1] = lhs.m_v[1] - rhs.m_v[1] - carry;
542 inline bigint128 operator-() const
545 result.m_v[0] = ~m_v[0];
546 result.m_v[1] = ~m_v[1];
548 if (result.m_v[0] != cUINT64_MAX)
558 friend inline bigint128 operator+(const bigint128 &lhs, int32 x)
560 return lhs + bigint128(x);
562 friend inline bigint128 operator+(const bigint128 &lhs, int64_t x)
564 return lhs + bigint128(x);
566 friend inline bigint128 operator+(const bigint128 &lhs, uint32 x)
568 return lhs + bigint128(x);
570 friend inline bigint128 operator+(const bigint128 &lhs, uint64_t x)
572 return lhs + bigint128(x);
575 friend inline bigint128 operator-(const bigint128 &lhs, int32 x)
577 return lhs - bigint128(x);
579 friend inline bigint128 operator-(const bigint128 &lhs, int64_t x)
581 return lhs - bigint128(x);
583 friend inline bigint128 operator-(const bigint128 &lhs, uint32 x)
585 return lhs - bigint128(x);
587 friend inline bigint128 operator-(const bigint128 &lhs, uint64_t x)
589 return lhs - bigint128(x);
592 // signed shift right
593 friend inline bigint128 operator>>(const bigint128 &lhs, uint n)
598 return lhs.is_negative() ? bigint128(-1) : bigint128(UINT64_C(0));
600 uint64_t l = lhs.m_v[0];
601 uint64_t h = lhs.m_v[1];
606 h = lhs.is_negative() ? cUINT64_MAX : 0;
610 // n can be 0-63 here
614 l |= ((h & ((UINT64_C(1) << n) - UINT64_C(1))) << (64 - static_cast<int>(n)));
615 h = static_cast<uint64_t>(static_cast<int64_t>(h) >> static_cast<int>(n));
618 return bigint128(l, h);
621 static inline bigint128 unsigned_shift_right(const bigint128 &lhs, uint n)
626 return bigint128(UINT64_C(0));
628 uint64_t l = lhs.m_v[0];
629 uint64_t h = lhs.m_v[1];
638 // n can be 0-63 here
642 l |= ((h & ((UINT64_C(1) << n) - UINT64_C(1))) << (64 - static_cast<int>(n)));
646 return bigint128(l, h);
650 friend inline bigint128 operator<<(const bigint128 &lhs, uint n)
655 return bigint128(UINT64_C(0));
657 uint64_t l = lhs.m_v[0];
658 uint64_t h = lhs.m_v[1];
667 // n can be 0-63 here
671 h |= (l >> (64 - static_cast<int>(n)));
675 return bigint128(l, h);
679 uint get_num_significant_bits() const
686 d = d.unsigned_shift_right(d, 1);
691 // true if overflowed (returns lower 128 bits of result)
692 static bool unsigned_multiply(bigint128 x, bigint128 y, bigint128 &result)
694 // Shortcut if both are 32-bit.
695 if ((x.m_v[1] | y.m_v[1]) == 0)
697 if (((x.m_v[0] | y.m_v[0]) >> 32U) == 0)
699 result = x.m_v[0] * y.m_v[0];
704 // Minor optimization: ensure x <= y.
710 bool overflow_flag = false;
714 // Seems most portable to use unsigned mul of 32x32=64 bits as the underlying primitive.
715 for (uint i = 0; i < cMaxDWORDs; ++i)
717 const uint64_t m = static_cast<uint64_t>(x.get_dword(i));
720 for (uint j = 0; j < cMaxDWORDs; ++j)
724 uint64_t product = m * y.get_dword(j);
729 overflow_flag = true;
733 product += value.get_dword(k);
734 value.set_dword(k, static_cast<uint32>(product));
742 return overflow_flag;
745 // true if overflowed
746 static bool signed_multiply(bigint128 a, bigint128 b, bigint128 &result)
748 bool a_is_negative = a.is_negative();
749 bool b_is_negative = b.is_negative();
751 bool overflow_flag = unsigned_multiply(a.get_abs(), b.get_abs(), result);
753 if (a_is_negative != b_is_negative)
755 if (result.unsigned_greater(bigint128(0, UINT64_C(0x8000000000000000))))
756 overflow_flag = true;
760 else if (result.is_negative())
761 overflow_flag = true;
763 return overflow_flag;
767 static bool unsigned_divide(const bigint128 &a, const bigint128 &b, bigint128 &q, bigint128 &r)
769 // Shortcut if both are 64-bit.
770 if ((!a.m_v[1]) && (!b.m_v[1]))
772 q = a.m_v[0] / b.m_v[0];
773 r = a.m_v[0] % b.m_v[0];
777 int num_a = a.get_num_significant_bits();
778 int num_b = b.get_num_significant_bits();
787 int cur_pos = num_a - num_b;
789 // Good old fashioned non-restoring division 1 bit at a time. Hope you're not busy!
795 k = b << static_cast<uint>(cur_pos);
801 if (c.unsigned_greater_equal(k))
807 k = unsigned_shift_right(k, 1U);
809 } while (cur_pos >= 0);
815 VOGL_ASSERT(r.unsigned_less(b));
819 static bool signed_divide(const bigint128 &a, const bigint128 &b, bigint128 &q, bigint128 &r)
829 bool a_is_negative = a.is_negative();
830 bool b_is_negative = b.is_negative();
832 // abs()'s are safe here, the min 128-bit signed value can be represented as an unsigned 128-bit value
833 unsigned_divide(a.get_abs(), b.get_abs(), q, r);
835 if (a_is_negative != b_is_negative)
844 friend inline bigint128 operator*(const bigint128 &lhs, const bigint128 &rhs)
847 signed_multiply(lhs, rhs, result);
850 friend inline bigint128 operator*(const bigint128 &lhs, int32 x)
852 return lhs * bigint128(x);
854 friend inline bigint128 operator*(const bigint128 &lhs, int64_t x)
856 return lhs * bigint128(x);
858 friend inline bigint128 operator*(const bigint128 &lhs, uint32 x)
860 return lhs * bigint128(x);
862 friend inline bigint128 operator*(const bigint128 &lhs, uint64_t x)
864 return lhs * bigint128(x);
867 bigint128 &operator*=(const bigint128 &other)
869 *this = *this * other;
872 bigint128 &operator*=(int32 other)
874 *this = *this * other;
877 bigint128 &operator*=(uint32 other)
879 *this = *this * other;
882 bigint128 &operator*=(int64_t other)
884 *this = *this * other;
887 bigint128 &operator*=(uint64_t other)
889 *this = *this * other;
893 friend inline bigint128 operator/(const bigint128 &lhs, const bigint128 &rhs)
896 signed_divide(lhs, rhs, q, r);
899 friend inline bigint128 operator/(const bigint128 &lhs, int32 x)
901 return lhs / bigint128(x);
903 friend inline bigint128 operator/(const bigint128 &lhs, int64_t x)
905 return lhs / bigint128(x);
907 friend inline bigint128 operator/(const bigint128 &lhs, uint32 x)
909 return lhs / bigint128(x);
911 friend inline bigint128 operator/(const bigint128 &lhs, uint64_t x)
913 return lhs / bigint128(x);
916 bigint128 &operator/=(const bigint128 &other)
918 *this = *this / other;
921 bigint128 &operator/=(int32 other)
923 *this = *this / other;
926 bigint128 &operator/=(uint32 other)
928 *this = *this / other;
931 bigint128 &operator/=(int64_t other)
933 *this = *this / other;
936 bigint128 &operator/=(uint64_t other)
938 *this = *this / other;
942 friend inline bigint128 operator%(const bigint128 &lhs, const bigint128 &rhs)
945 signed_divide(lhs, rhs, q, r);
948 friend inline bigint128 operator%(const bigint128 &lhs, int32 x)
950 return lhs % bigint128(x);
952 friend inline bigint128 operator%(const bigint128 &lhs, int64_t x)
954 return lhs % bigint128(x);
956 friend inline bigint128 operator%(const bigint128 &lhs, uint32 x)
958 return lhs % bigint128(x);
960 friend inline bigint128 operator%(const bigint128 &lhs, uint64_t x)
962 return lhs % bigint128(x);
965 bigint128 &operator%=(const bigint128 &other)
967 *this = *this % other;
970 bigint128 &operator%=(int32 other)
972 *this = *this % other;
975 bigint128 &operator%=(uint32 other)
977 *this = *this % other;
980 bigint128 &operator%=(int64_t other)
982 *this = *this % other;
985 bigint128 &operator%=(uint64_t other)
987 *this = *this % other;
991 static bigint128 get_random(random &r)
993 return bigint128(r.urand64(), r.urand64());
996 static bigint128 get_smallest()
998 return bigint128(0, cINT64_MIN);
1001 static bigint128 get_largest()
1003 return bigint128(cUINT64_MAX, cINT64_MAX);
1006 static bigint128 unsigned_get_largest()
1008 return bigint128(cUINT64_MAX, cUINT64_MAX);
1011 static bigint128 get_all_zeros()
1013 return bigint128(0U, 0U);
1016 static bigint128 get_all_ones()
1018 return bigint128(cUINT64_MAX, cUINT64_MAX);
1025 VOGL_DEFINE_BITWISE_COPYABLE(bigint128);
1027 inline void bigint128_check(bool success, uint &num_failures)
1036 inline bool bigint128_test(uint seed = 5)
1038 VOGL_NOTE_UNUSED(seed);
1039 VOGL_ASSUME(sizeof(bigint128) == sizeof(uint64_t) * 2U);
1041 uint num_failures = 0;
1045 bigint128 neg_one(-1);
1047 #define BIGINT128_CHECK(x) bigint128_check(x, num_failures)
1048 BIGINT128_CHECK(neg_one.get_qword(0) == cUINT64_MAX);
1049 BIGINT128_CHECK(neg_one.get_qword(1) == cUINT64_MAX);
1050 BIGINT128_CHECK(neg_one + 2 == 1);
1051 BIGINT128_CHECK(zero.is_zero());
1052 BIGINT128_CHECK(one.is_positive() && !one.is_zero() && !one.is_negative());
1053 BIGINT128_CHECK(neg_one.is_negative() && !neg_one.is_zero() && !neg_one.is_positive());
1054 BIGINT128_CHECK(one > zero);
1055 BIGINT128_CHECK(!(zero > one));
1056 BIGINT128_CHECK(zero < one);
1057 BIGINT128_CHECK(one > neg_one);
1058 BIGINT128_CHECK(neg_one < zero);
1059 BIGINT128_CHECK(zero > neg_one);
1060 BIGINT128_CHECK(neg_one < zero);
1061 BIGINT128_CHECK(bigint128(zero)++ == zero);
1062 BIGINT128_CHECK(++bigint128(zero) == one);
1063 BIGINT128_CHECK(bigint128(one)-- == one);
1064 BIGINT128_CHECK(--bigint128(one) == zero);
1065 BIGINT128_CHECK(--bigint128(zero) < zero);
1066 BIGINT128_CHECK(--bigint128(zero) == -1);
1067 BIGINT128_CHECK(++bigint128(zero) == 1);
1068 BIGINT128_CHECK(++bigint128(cUINT64_MAX) == bigint128(0, 1));
1069 BIGINT128_CHECK(--bigint128(0, 1) == cUINT64_MAX);
1070 BIGINT128_CHECK(++bigint128(cUINT64_MAX, cUINT64_MAX) == zero);
1071 BIGINT128_CHECK(bigint128(0, 0) - bigint128(1, 0) == bigint128(-1));
1072 BIGINT128_CHECK(bigint128(1, 0) + bigint128(cUINT64_MAX, cUINT64_MAX) == bigint128(0));
1074 BIGINT128_CHECK(bigint128(0, 1) < bigint128(0, 2));
1075 BIGINT128_CHECK(bigint128(0, 2) > bigint128(0, 1));
1076 BIGINT128_CHECK(bigint128(0, cUINT64_MAX) < -1);
1077 BIGINT128_CHECK(bigint128(0, cUINT64_MAX) > bigint128::get_smallest());
1079 BIGINT128_CHECK(bigint128::get_smallest() < bigint128::get_largest());
1080 BIGINT128_CHECK(bigint128::get_largest() > bigint128::get_smallest());
1081 BIGINT128_CHECK(bigint128::get_smallest() < 0);
1082 BIGINT128_CHECK(bigint128::get_largest() > 0);
1083 BIGINT128_CHECK(bigint128::get_smallest() < (bigint128::get_smallest() + 1));
1084 BIGINT128_CHECK(bigint128::get_largest() > (bigint128::get_largest() - 1));
1086 BIGINT128_CHECK(bigint128::get_smallest() < bigint128(0, cINT64_MAX));
1087 BIGINT128_CHECK(bigint128::get_largest() > bigint128(0, cUINT64_MAX));
1089 BIGINT128_CHECK((bigint128::get_smallest() - 1) == bigint128::get_largest());
1090 BIGINT128_CHECK((bigint128::get_largest() + 1) == bigint128::get_smallest());
1092 BIGINT128_CHECK((bigint128::get_smallest() - 2) == (bigint128::get_largest() - 1));
1093 BIGINT128_CHECK((bigint128::get_largest() + 2) == (bigint128::get_smallest() + 1));
1095 BIGINT128_CHECK(~bigint128(0) == bigint128(-1));
1096 BIGINT128_CHECK(~~bigint128(0) == bigint128(0));
1097 BIGINT128_CHECK((bigint128(0xDEADBEEF, 0xDEADBEEF) ^ bigint128(0xDEADBEEF, 0xDEADBEEF) ^ bigint128(0xDEADBEEF, 0xDEADBEEF) ^ bigint128(0xDEADBEEF, 0xDEADBEEF)) == 0);
1099 bigint128 zz(bigint128(0xDEADBEEF, 0xDEADBEEF));
1100 BIGINT128_CHECK((zz ^= zz) == 0);
1101 BIGINT128_CHECK((bigint128(0) | bigint128(1)) == 1);
1103 BIGINT128_CHECK(bigint128(0, 1) - bigint128(1) == cUINT64_MAX);
1104 BIGINT128_CHECK(bigint128(0, 50) - bigint128(0, 50) == 0);
1105 BIGINT128_CHECK(bigint128(0, 50) - bigint128(1, 50) == -1);
1106 BIGINT128_CHECK(bigint128(-1) - bigint128(-1) == 0);
1107 BIGINT128_CHECK(bigint128(-1) + bigint128(1) == 0);
1109 BIGINT128_CHECK(bigint128(0).range_check(1, false));
1110 BIGINT128_CHECK(bigint128(UINT64_C(0xFF)).range_check(1, false));
1112 BIGINT128_CHECK(bigint128(0).range_check(2, false));
1113 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFF)).range_check(2, false));
1115 BIGINT128_CHECK(bigint128(0).range_check(3, false));
1116 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFF)).range_check(3, false));
1118 BIGINT128_CHECK(bigint128(0).range_check(4, false));
1119 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFF)).range_check(4, false));
1121 BIGINT128_CHECK(bigint128(0).range_check(5, false));
1122 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFF)).range_check(5, false));
1124 BIGINT128_CHECK(bigint128(0).range_check(6, false));
1125 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFFFF)).range_check(6, false));
1127 BIGINT128_CHECK(bigint128(0).range_check(7, false));
1128 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFFFFFF)).range_check(7, false));
1130 BIGINT128_CHECK(bigint128(0).range_check(8, false));
1131 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFFFFFFFF)).range_check(8, false));
1133 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFFFFFF80), cUINT64_MAX).range_check(1, true));
1134 BIGINT128_CHECK(!bigint128(UINT64_C(0xFFFFFFFFFFFFFF7F), cUINT64_MAX).range_check(1, true));
1135 BIGINT128_CHECK(bigint128(UINT64_C(0x000000000000007F), 0).range_check(1, true));
1136 BIGINT128_CHECK(!bigint128(UINT64_C(0x0000000000000080), 0).range_check(1, true));
1138 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFFFFFF8000), cUINT64_MAX).range_check(2, true));
1139 BIGINT128_CHECK(!bigint128(UINT64_C(0xFFFFFFFFFFFF7FFF), cUINT64_MAX).range_check(2, true));
1140 BIGINT128_CHECK(bigint128(UINT64_C(0x0000000000007FFF), 0).range_check(2, true));
1141 BIGINT128_CHECK(!bigint128(UINT64_C(0x0000000000008000), 0).range_check(2, true));
1143 BIGINT128_CHECK(bigint128(UINT64_C(0xFFFFFFFF80000000), cUINT64_MAX).range_check(4, true));
1144 BIGINT128_CHECK(!bigint128(UINT64_C(0xFFFFFFFF7FFFFFFF), cUINT64_MAX).range_check(4, true));
1145 BIGINT128_CHECK(bigint128(UINT64_C(0x000000007FFFFFFF), 0).range_check(4, true));
1146 BIGINT128_CHECK(!bigint128(UINT64_C(0x0000000080000000), 0).range_check(4, true));
1148 BIGINT128_CHECK(bigint128(UINT64_C(0x8000000000000000), cUINT64_MAX).range_check(8, true));
1149 BIGINT128_CHECK(!bigint128(UINT64_C(0x7FFFFFFFFFFFFFFF), cUINT64_MAX).range_check(8, true));
1150 BIGINT128_CHECK(!(bigint128(UINT64_C(0x7FFFFFFFFFFFFFFF), cUINT64_MAX) - 1000).range_check(8, true));
1151 BIGINT128_CHECK(bigint128(UINT64_C(0x7FFFFFFFFFFFFFFF), 0).range_check(8, true));
1152 BIGINT128_CHECK(!bigint128(UINT64_C(0x8000000000000000), 0).range_check(8, true));
1153 BIGINT128_CHECK(!(bigint128(UINT64_C(0x8000000000000000), 0) + 1000).range_check(8, true));
1155 BIGINT128_CHECK(bigint128(cUINT64_MAX, UINT64_C(0x8000000000000000)).range_check(16, true));
1156 BIGINT128_CHECK(bigint128(cUINT64_MAX, UINT64_C(0x7FFFFFFFFFFFFFFF)).range_check(16, true));
1158 BIGINT128_CHECK(bigint128(0, 0).range_check(16, false));
1159 BIGINT128_CHECK(bigint128(cUINT64_MAX, 0).range_check(16, false));
1160 BIGINT128_CHECK(bigint128(cUINT64_MAX, cUINT64_MAX).range_check(16, false));
1164 BIGINT128_CHECK(x == 0);
1165 BIGINT128_CHECK(x.is_zero());
1166 BIGINT128_CHECK(!(x < 0));
1167 BIGINT128_CHECK(!(x > 0));
1170 #if defined(VOGL_PLATFORM_PC_X64) && defined(__GNUC__)
1173 for (uint i = 0; i < 1000000000; i++)
1175 __int128 x(0), y(0), z(0);
1177 uint n0 = r.irand_inclusive(1, 16);
1178 for (uint j = 0; j < n0; j++)
1179 ((uint8 *)&x)[j] = r.urand32() >> 8;
1182 if (r.urand32() & 1)
1186 uint n1 = r.irand_inclusive(1, 16);
1187 for (uint j = 0; j < n1; j++)
1188 ((uint8 *)&y)[j] = r.urand32() >> 8;
1191 if (r.urand32() & 1)
1195 if (!r.irand(0, 100))
1197 if (!r.irand(0, 100))
1200 uint op = r.irand_inclusive(0, 24);
1202 bigint128 bx((uint64_t)x, (uint64_t)(x >> 64U));
1203 bigint128 by((uint64_t)y, (uint64_t)(y >> 64U));
1206 if ((op >= 21) && (op <= 24))
1208 if (!r.irand(0, 30))
1210 bx = bigint128::get_smallest();
1211 memcpy(&x, &bx, sizeof(x));
1213 if (!r.irand(0, 30))
1215 bx = bigint128::get_largest();
1216 memcpy(&x, &bx, sizeof(x));
1218 if (!r.irand(0, 30))
1220 by = bigint128::get_smallest();
1221 memcpy(&y, &by, sizeof(y));
1223 if (!r.irand(0, 30))
1225 by = bigint128::get_largest();
1226 memcpy(&y, &by, sizeof(y));
1230 uint shift = r.irand_inclusive(0, 127);
1343 z = (__uint128_t)x < (__uint128_t)y;
1344 bz = bx.unsigned_less(by);
1349 z = (__uint128_t)x <= (__uint128_t)y;
1350 bz = bx.unsigned_less_equal(by);
1355 z = (__uint128_t)x > (__uint128_t)y;
1356 bz = bx.unsigned_greater(by);
1361 z = (__uint128_t)x >= (__uint128_t)y;
1362 bz = bx.unsigned_greater_equal(by);
1369 z = (__uint128_t)x / (__uint128_t)y;
1370 __int128 m = (__uint128_t)x % (__uint128_t)y;
1373 VOGL_VERIFY(bigint128::unsigned_divide(bx, by, bz, r));
1375 BIGINT128_CHECK((uint64_t)m == r.get_qword(0));
1376 BIGINT128_CHECK((uint64_t)(m >> 64) == r.get_qword(1));
1388 VOGL_VERIFY(bigint128::signed_divide(bx, by, bz, r));
1390 VOGL_NOTE_UNUSED(nr);
1392 BIGINT128_CHECK((uint64_t)m == r.get_qword(0));
1393 BIGINT128_CHECK((uint64_t)(m >> 64) == r.get_qword(1));
1399 z = (__uint128_t)x * (__uint128_t)y;
1400 bigint128::unsigned_multiply(bx, by, bz);
1406 bigint128::signed_multiply(bx, by, bz);
1410 // TODO: unsigned comps, signed/unsigned division
1416 BIGINT128_CHECK((uint64_t)z == bz.get_qword(0));
1417 BIGINT128_CHECK((uint64_t)(z >> 64) == bz.get_qword(1));
1421 #undef BIGINT128_CHECK
1423 return !num_failures;
1428 #endif // VOGL_BIGINT128_H