1 #ifndef INT128_H 2 #define INT128_H 3 4 #include <assert.h> 5 #include <stdint.h> 6 #include <stdbool.h> 7 8 typedef struct Int128 Int128; 9 10 struct Int128 { 11 uint64_t lo; 12 int64_t hi; 13 }; 14 15 static inline Int128 int128_make64(uint64_t a) 16 { 17 return (Int128) { a, 0 }; 18 } 19 20 static inline uint64_t int128_get64(Int128 a) 21 { 22 assert(!a.hi); 23 return a.lo; 24 } 25 26 static inline Int128 int128_zero(void) 27 { 28 return int128_make64(0); 29 } 30 31 static inline Int128 int128_one(void) 32 { 33 return int128_make64(1); 34 } 35 36 static inline Int128 int128_2_64(void) 37 { 38 return (Int128) { 0, 1 }; 39 } 40 41 static inline Int128 int128_exts64(int64_t a) 42 { 43 return (Int128) { .lo = a, .hi = (a < 0) ? -1 : 0 }; 44 } 45 46 static inline Int128 int128_and(Int128 a, Int128 b) 47 { 48 return (Int128) { a.lo & b.lo, a.hi & b.hi }; 49 } 50 51 static inline Int128 int128_rshift(Int128 a, int n) 52 { 53 int64_t h; 54 if (!n) { 55 return a; 56 } 57 h = a.hi >> (n & 63); 58 if (n >= 64) { 59 return (Int128) { h, h >> 63 }; 60 } else { 61 return (Int128) { (a.lo >> n) | ((uint64_t)a.hi << (64 - n)), h }; 62 } 63 } 64 65 static inline Int128 int128_add(Int128 a, Int128 b) 66 { 67 uint64_t lo = a.lo + b.lo; 68 69 /* a.lo <= a.lo + b.lo < a.lo + k (k is the base, 2^64). Hence, 70 * a.lo + b.lo >= k implies 0 <= lo = a.lo + b.lo - k < a.lo. 71 * Similarly, a.lo + b.lo < k implies a.lo <= lo = a.lo + b.lo < k. 72 * 73 * So the carry is lo < a.lo. 74 */ 75 return (Int128) { lo, (uint64_t)a.hi + b.hi + (lo < a.lo) }; 76 } 77 78 static inline Int128 int128_neg(Int128 a) 79 { 80 uint64_t lo = -a.lo; 81 return (Int128) { lo, ~(uint64_t)a.hi + !lo }; 82 } 83 84 static inline Int128 int128_sub(Int128 a, Int128 b) 85 { 86 return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) }; 87 } 88 89 static inline bool int128_nonneg(Int128 a) 90 { 91 return a.hi >= 0; 92 } 93 94 static inline bool int128_eq(Int128 a, Int128 b) 95 { 96 return a.lo == b.lo && a.hi == b.hi; 97 } 98 99 static inline bool int128_ne(Int128 a, Int128 b) 100 { 101 return !int128_eq(a, b); 102 } 103 104 static inline bool int128_ge(Int128 a, Int128 b) 105 { 106 return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo); 107 } 108 109 static inline bool int128_lt(Int128 a, Int128 b) 110 { 111 return !int128_ge(a, b); 112 } 113 114 static inline bool int128_le(Int128 a, Int128 b) 115 { 116 return int128_ge(b, a); 117 } 118 119 static inline bool int128_gt(Int128 a, Int128 b) 120 { 121 return !int128_le(a, b); 122 } 123 124 static inline bool int128_nz(Int128 a) 125 { 126 return a.lo || a.hi; 127 } 128 129 static inline Int128 int128_min(Int128 a, Int128 b) 130 { 131 return int128_le(a, b) ? a : b; 132 } 133 134 static inline Int128 int128_max(Int128 a, Int128 b) 135 { 136 return int128_ge(a, b) ? a : b; 137 } 138 139 static inline void int128_addto(Int128 *a, Int128 b) 140 { 141 *a = int128_add(*a, b); 142 } 143 144 static inline void int128_subfrom(Int128 *a, Int128 b) 145 { 146 *a = int128_sub(*a, b); 147 } 148 149 #endif 150