]>
Commit | Line | Data |
---|---|---|
b7cd3db6 AK |
1 | #ifndef INT128_H |
2 | #define INT128_H | |
3 | ||
6046c620 PB |
4 | #include <assert.h> |
5 | #include <stdint.h> | |
6 | #include <stdbool.h> | |
7 | ||
b7cd3db6 AK |
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 | ||
052e87b0 PB |
41 | static inline Int128 int128_and(Int128 a, Int128 b) |
42 | { | |
43 | return (Int128) { a.lo & b.lo, a.hi & b.hi }; | |
44 | } | |
45 | ||
46 | static 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 | ||
b7cd3db6 AK |
60 | static inline Int128 int128_add(Int128 a, Int128 b) |
61 | { | |
6046c620 PB |
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) }; | |
b7cd3db6 AK |
71 | } |
72 | ||
73 | static inline Int128 int128_neg(Int128 a) | |
74 | { | |
6046c620 PB |
75 | uint64_t lo = -a.lo; |
76 | return (Int128) { lo, ~(uint64_t)a.hi + !lo }; | |
b7cd3db6 AK |
77 | } |
78 | ||
79 | static inline Int128 int128_sub(Int128 a, Int128 b) | |
80 | { | |
6046c620 | 81 | return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) }; |
b7cd3db6 AK |
82 | } |
83 | ||
84 | static inline bool int128_nonneg(Int128 a) | |
85 | { | |
86 | return a.hi >= 0; | |
87 | } | |
88 | ||
89 | static inline bool int128_eq(Int128 a, Int128 b) | |
90 | { | |
91 | return a.lo == b.lo && a.hi == b.hi; | |
92 | } | |
93 | ||
94 | static inline bool int128_ne(Int128 a, Int128 b) | |
95 | { | |
96 | return !int128_eq(a, b); | |
97 | } | |
98 | ||
99 | static inline bool int128_ge(Int128 a, Int128 b) | |
100 | { | |
6046c620 | 101 | return a.hi > b.hi || (a.hi == b.hi && a.lo >= b.lo); |
b7cd3db6 AK |
102 | } |
103 | ||
104 | static inline bool int128_lt(Int128 a, Int128 b) | |
105 | { | |
106 | return !int128_ge(a, b); | |
107 | } | |
108 | ||
109 | static inline bool int128_le(Int128 a, Int128 b) | |
110 | { | |
111 | return int128_ge(b, a); | |
112 | } | |
113 | ||
114 | static inline bool int128_gt(Int128 a, Int128 b) | |
115 | { | |
116 | return !int128_le(a, b); | |
117 | } | |
118 | ||
119 | static inline bool int128_nz(Int128 a) | |
120 | { | |
121 | return a.lo || a.hi; | |
122 | } | |
123 | ||
124 | static inline Int128 int128_min(Int128 a, Int128 b) | |
125 | { | |
126 | return int128_le(a, b) ? a : b; | |
127 | } | |
128 | ||
129 | static inline Int128 int128_max(Int128 a, Int128 b) | |
130 | { | |
131 | return int128_ge(a, b) ? a : b; | |
132 | } | |
133 | ||
134 | static inline void int128_addto(Int128 *a, Int128 b) | |
135 | { | |
136 | *a = int128_add(*a, b); | |
137 | } | |
138 | ||
139 | static inline void int128_subfrom(Int128 *a, Int128 b) | |
140 | { | |
141 | *a = int128_sub(*a, b); | |
142 | } | |
143 | ||
144 | #endif |