8 typedef struct Int128 Int128
;
15 static inline Int128
int128_make64(uint64_t a
)
17 return (Int128
) { a
, 0 };
20 static inline uint64_t int128_get64(Int128 a
)
26 static inline Int128
int128_zero(void)
28 return int128_make64(0);
31 static inline Int128
int128_one(void)
33 return int128_make64(1);
36 static inline Int128
int128_2_64(void)
38 return (Int128
) { 0, 1 };
41 static inline Int128
int128_exts64(int64_t a
)
43 return (Int128
) { .lo
= a
, .hi
= (a
< 0) ? -1 : 0 };
46 static inline Int128
int128_and(Int128 a
, Int128 b
)
48 return (Int128
) { a
.lo
& b
.lo
, a
.hi
& b
.hi
};
51 static inline Int128
int128_rshift(Int128 a
, int n
)
59 return (Int128
) { h
, h
>> 63 };
61 return (Int128
) { (a
.lo
>> n
) | ((uint64_t)a
.hi
<< (64 - n
)), h
};
65 static inline Int128
int128_add(Int128 a
, Int128 b
)
67 uint64_t lo
= a
.lo
+ b
.lo
;
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.
73 * So the carry is lo < a.lo.
75 return (Int128
) { lo
, (uint64_t)a
.hi
+ b
.hi
+ (lo
< a
.lo
) };
78 static inline Int128
int128_neg(Int128 a
)
81 return (Int128
) { lo
, ~(uint64_t)a
.hi
+ !lo
};
84 static inline Int128
int128_sub(Int128 a
, Int128 b
)
86 return (Int128
){ a
.lo
- b
.lo
, (uint64_t)a
.hi
- b
.hi
- (a
.lo
< b
.lo
) };
89 static inline bool int128_nonneg(Int128 a
)
94 static inline bool int128_eq(Int128 a
, Int128 b
)
96 return a
.lo
== b
.lo
&& a
.hi
== b
.hi
;
99 static inline bool int128_ne(Int128 a
, Int128 b
)
101 return !int128_eq(a
, b
);
104 static inline bool int128_ge(Int128 a
, Int128 b
)
106 return a
.hi
> b
.hi
|| (a
.hi
== b
.hi
&& a
.lo
>= b
.lo
);
109 static inline bool int128_lt(Int128 a
, Int128 b
)
111 return !int128_ge(a
, b
);
114 static inline bool int128_le(Int128 a
, Int128 b
)
116 return int128_ge(b
, a
);
119 static inline bool int128_gt(Int128 a
, Int128 b
)
121 return !int128_le(a
, b
);
124 static inline bool int128_nz(Int128 a
)
129 static inline Int128
int128_min(Int128 a
, Int128 b
)
131 return int128_le(a
, b
) ? a
: b
;
134 static inline Int128
int128_max(Int128 a
, Int128 b
)
136 return int128_ge(a
, b
) ? a
: b
;
139 static inline void int128_addto(Int128
*a
, Int128 b
)
141 *a
= int128_add(*a
, b
);
144 static inline void int128_subfrom(Int128
*a
, Int128 b
)
146 *a
= int128_sub(*a
, b
);