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