1#include "types/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(ui128, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "iters",
6 });
7
8/* These are runtime functions the compiler wants to exist, so we can
9 * support 128 bit integers. Each 128 bit integer is two 64 bit halves,
10 * so we want to test things that cross the "word-seam" between the two */
11#define U128(hi, lo) (((uint128_t) (uint64_t) (hi) << 64) | (uint64_t) (lo))
12
13static uint128_t ref_shl(uint128_t a, int b) {
14 return b == 0 ? a : a << b;
15}
16
17TEST_DECLARE_UNIT(ui128, shift_left) {
18 static const uint128_t vals[] = {
19 0,
20 1,
21 U128(0, UINT64_MAX),
22 U128(UINT64_MAX, 0),
23 U128(0x0123456789ABCDEFULL, 0xFEDCBA9876543210ULL),
24 UINT128_MAX,
25 };
26
27 for (size_t i = 0; i < TEST_ARRAY_LEN(vals); i++)
28 for (int b = 0; b < 128; b++)
29 TEST_ASSERT(__ashlti3(vals[i], b) == ref_shl(vals[i], b));
30
31 return TEST_SUCCESS;
32}
33
34TEST_DECLARE_UNIT(ui128, shift_left_seam) {
35 uint128_t one = 1;
36
37 TEST_ASSERT(__ashlti3(one, 0) == one);
38 TEST_ASSERT(__ashlti3(one, 63) == U128(0, 1ULL << 63));
39 TEST_ASSERT(__ashlti3(one, 64) == U128(1, 0));
40 TEST_ASSERT(__ashlti3(one, 65) == U128(2, 0));
41 TEST_ASSERT(__ashlti3(one, 127) == U128(1ULL << 63, 0));
42
43 /* Bits shifted past the top are dropped */
44 TEST_ASSERT(__ashlti3(U128(UINT64_MAX, 0), 1) == U128(UINT64_MAX << 1, 0));
45
46 return TEST_SUCCESS;
47}
48
49TEST_DECLARE_UNIT(ui128, shift_right_logical) {
50 static const uint128_t vals[] = {
51 0,
52 1,
53 U128(0, UINT64_MAX),
54 U128(UINT64_MAX, 0),
55 U128(0x0123456789ABCDEFULL, 0xFEDCBA9876543210ULL),
56 UINT128_MAX,
57 };
58
59 for (size_t i = 0; i < TEST_ARRAY_LEN(vals); i++)
60 for (int b = 0; b < 128; b++) {
61 uint128_t want = b == 0 ? vals[i] : vals[i] >> b;
62 TEST_ASSERT(__lshrti3(vals[i], b) == want);
63 }
64
65 return TEST_SUCCESS;
66}
67
68TEST_DECLARE_UNIT(ui128, shift_right_logical_seam) {
69 uint128_t top = U128(1ULL << 63, 0);
70
71 TEST_ASSERT(__lshrti3(top, 0) == top);
72 TEST_ASSERT(__lshrti3(top, 64) == U128(0, 1ULL << 63));
73 TEST_ASSERT(__lshrti3(top, 127) == 1);
74 TEST_ASSERT(__lshrti3(UINT128_MAX, 64) == U128(0, UINT64_MAX));
75
76 /* Check for no sign extension */
77 TEST_ASSERT(__lshrti3(UINT128_MAX, 127) == 1);
78
79 return TEST_SUCCESS;
80}
81
82/* The arithmetic shift is the one with a sign to preserve; a logical shift
83 * substituted here would pass every non-negative case in the sweep above. */
84TEST_DECLARE_UNIT(ui128, shift_right_arithmetic) {
85 static const int128_t vals[] = {
86 0, 1, -1, 12345, -12345, INT128_MAX, INT128_MIN,
87 };
88
89 for (size_t i = 0; i < TEST_ARRAY_LEN(vals); i++)
90 for (int b = 0; b < 128; b++) {
91 int128_t want = b == 0 ? vals[i] : vals[i] >> b;
92 TEST_ASSERT(__ashrti3(vals[i], b) == want);
93 }
94
95 return TEST_SUCCESS;
96}
97
98TEST_DECLARE_UNIT(ui128, shift_right_arithmetic_signs) {
99 /* -1 stays -1 at every shift; that is the whole point of sign fill. */
100 for (int b = 0; b < 128; b++)
101 TEST_ASSERT(__ashrti3((int128_t) -1, b) == (int128_t) -1);
102
103 TEST_ASSERT(__ashrti3((int128_t) -2, 1) == (int128_t) -1);
104 TEST_ASSERT(__ashrti3(INT128_MIN, 127) == (int128_t) -1);
105 TEST_ASSERT(__ashrti3(INT128_MAX, 127) == 0);
106
107 /* Crossing the 64-bit seam must carry the fill into the high half. */
108 TEST_ASSERT(__ashrti3(INT128_MIN, 64) ==
109 (int128_t) U128(UINT64_MAX, 1ULL << 63));
110
111 return TEST_SUCCESS;
112}
113
114TEST_DECLARE_UNIT(ui128, negate, TEST_INTENSITY(16, 64, 1024)) {
115 size_t iters = ctx->intensity_val ? ctx->intensity_val : 64;
116 TEST_ASSERT(__negti2(0) == 0);
117 TEST_ASSERT(__negti2(1) == (int128_t) -1);
118 TEST_ASSERT(__negti2((int128_t) -1) == 1);
119 TEST_ASSERT(__negti2(INT128_MAX) == INT128_MIN + 1);
120
121 /* The carry out of the low half is the part worth checking. */
122 TEST_ASSERT(__negti2((int128_t) U128(0, 1)) ==
123 (int128_t) U128(UINT64_MAX, UINT64_MAX));
124 TEST_ASSERT(__negti2((int128_t) U128(1, 0)) ==
125 (int128_t) U128(UINT64_MAX, 0));
126
127 for (int128_t v = -(int128_t) iters; v <= (int128_t) iters; v++)
128 TEST_ASSERT(__negti2(__negti2(v)) == v);
129
130 return TEST_SUCCESS;
131}
132
133TEST_DECLARE_UNIT(ui128, multiply, TEST_INTENSITY(8, 32, 256)) {
134 size_t bound = ctx->intensity_val ? ctx->intensity_val : 32;
135 TEST_ASSERT(__multi3(0, 12345) == 0);
136 TEST_ASSERT(__multi3(1, 12345) == 12345);
137 TEST_ASSERT(__multi3(-1, 12345) == -12345);
138 TEST_ASSERT(__multi3(-3, -4) == 12);
139
140 /* 2^32 squared is 2^64, which lands exactly on the seam between the two
141 * halves -- the point where the partial products have to carry across. */
142 TEST_ASSERT(__multi3((int128_t) U128(0, 1ULL << 32),
143 (int128_t) U128(0, 1ULL << 32)) ==
144 (int128_t) U128(1, 0));
145
146 /* Anything at or above 2^64 squared overflows the result away entirely. */
147 TEST_ASSERT(__multi3((int128_t) U128(1, 0), (int128_t) U128(1, 0)) == 0);
148
149 for (int128_t a = -(int128_t) bound; a <= (int128_t) bound; a++)
150 for (int128_t b = -(int128_t) bound; b <= (int128_t) bound; b++)
151 TEST_ASSERT(__multi3(a, b) == a * b);
152
153 return TEST_SUCCESS;
154}
155
156/* Division is checked through its own contract rather than a table: whatever
157 * the quotient is, q*d + r must reproduce n and r must stay below d. */
158TEST_DECLARE_UNIT(ui128, divmod_identity) {
159 static const uint128_t nums[] = {
160 0, 1,
161 12345, U128(0, UINT64_MAX),
162 U128(1, 0), U128(0x0123456789ABCDEFULL, 0xFEDCBA9876543210ULL),
163 UINT128_MAX,
164 };
165 static const uint128_t dens[] = {
166 1, 2, 3, 10, 12345, U128(0, UINT64_MAX), U128(1, 0), UINT128_MAX,
167 };
168
169 for (size_t i = 0; i < TEST_ARRAY_LEN(nums); i++) {
170 for (size_t j = 0; j < TEST_ARRAY_LEN(dens); j++) {
171 uint128_t n = nums[i], d = dens[j], rem = 0;
172 uint128_t q = __udivmodti4(n, d, rem: &rem);
173
174 TEST_ASSERT(rem < d);
175 TEST_ASSERT(q * d + rem == n);
176 TEST_ASSERT(__udivti3(n, d) == q);
177 TEST_ASSERT(__umodti3(n, d) == rem);
178 }
179 }
180
181 return TEST_SUCCESS;
182}
183
184TEST_DECLARE_UNIT(ui128, divmod_edges) {
185 uint128_t rem = 0;
186
187 /* A numerator smaller than the divisor is all remainder. */
188 TEST_ASSERT(__udivmodti4(5, 10, &rem) == 0);
189 TEST_ASSERT(rem == 5);
190
191 TEST_ASSERT(__udivmodti4(0, 1, &rem) == 0 && rem == 0);
192 TEST_ASSERT(__udivmodti4(UINT128_MAX, 1, &rem) == UINT128_MAX && rem == 0);
193 TEST_ASSERT(__udivmodti4(UINT128_MAX, UINT128_MAX, &rem) == 1 && rem == 0);
194
195 return TEST_SUCCESS;
196}
197
198/* C rounds signed division toward zero, which makes the remainder take the
199 * sign of the dividend -- not the divisor. Both directions are easy to invert.
200 */
201TEST_DECLARE_UNIT(ui128, signed_divmod, TEST_INTENSITY(10, 40, 512)) {
202 size_t bound = ctx->intensity_val ? ctx->intensity_val : 40;
203 int128_t rem;
204
205 TEST_ASSERT(__divmodti4(7, 2, &rem) == 3 && rem == 1);
206 TEST_ASSERT(__divmodti4(-7, 2, &rem) == -3 && rem == -1);
207 TEST_ASSERT(__divmodti4(7, -2, &rem) == -3 && rem == 1);
208 TEST_ASSERT(__divmodti4(-7, -2, &rem) == 3 && rem == -1);
209
210 TEST_ASSERT(__divti3(7, 2) == 3);
211 TEST_ASSERT(__divti3(-7, 2) == -3);
212 TEST_ASSERT(__divti3(7, -2) == -3);
213 TEST_ASSERT(__divti3(-7, -2) == 3);
214
215 TEST_ASSERT(__modti3(7, 2) == 1);
216 TEST_ASSERT(__modti3(-7, 2) == -1);
217 TEST_ASSERT(__modti3(7, -2) == 1);
218 TEST_ASSERT(__modti3(-7, -2) == -1);
219
220 for (int128_t a = -(int128_t) bound; a <= (int128_t) bound; a++)
221 for (int128_t b = -7; b <= 7; b++) {
222 if (b == 0)
223 continue;
224 int128_t r;
225 int128_t q = __divmodti4(a, b, rem: &r);
226 TEST_ASSERT(q == a / b);
227 TEST_ASSERT(r == a % b);
228 TEST_ASSERT(__divti3(a, b) == a / b);
229 TEST_ASSERT(__modti3(a, b) == a % b);
230 TEST_ASSERT(q * b + r == a);
231 }
232
233 return TEST_SUCCESS;
234}
235
236TEST_DECLARE_UNIT(ui128, popcount_parity) {
237 TEST_ASSERT_EQ(__popcountti2(0), 0);
238 TEST_ASSERT_EQ(__popcountti2(UINT128_MAX), 128);
239 TEST_ASSERT_EQ(__popcountti2(U128(UINT64_MAX, 0)), 64);
240 TEST_ASSERT_EQ(__popcountti2(U128(0, UINT64_MAX)), 64);
241
242 /* Every single bit must be seen exactly once, in both halves. */
243 for (int b = 0; b < 128; b++)
244 TEST_ASSERT_EQ(__popcountti2(__ashlti3(1, b)), 1);
245
246 TEST_ASSERT_EQ(__parityti2(0), 0);
247 TEST_ASSERT_EQ(__parityti2(1), 1);
248 TEST_ASSERT_EQ(__parityti2(3), 0);
249 TEST_ASSERT_EQ(__parityti2(UINT128_MAX), 0);
250
251 return TEST_SUCCESS;
252}
253
254TEST_DECLARE_UNIT(ui128, count_zeros) {
255 for (int b = 0; b < 128; b++) {
256 uint128_t v = __ashlti3(a: 1, b);
257 TEST_ASSERT_EQ(__clzti2(v), 127 - b);
258 TEST_ASSERT_EQ(__ctzti2(v), b);
259 TEST_ASSERT_EQ(__ffsti2((int128_t) v), b + 1);
260 }
261
262 TEST_ASSERT_EQ(__ffsti2(0), 0);
263 TEST_ASSERT_EQ(__clzti2(UINT128_MAX), 0);
264 TEST_ASSERT_EQ(__ctzti2(UINT128_MAX), 0);
265
266 return TEST_SUCCESS;
267}
268
269/* Test the overflow checks in __negvti2 and similar functions */
270TEST_DECLARE_UNIT(ui128, limits) {
271 TEST_ASSERT(INT128_MAX > 0);
272 TEST_ASSERT(INT128_MIN < 0);
273 TEST_ASSERT(INT128_MAX == (int128_t) (UINT128_MAX >> 1));
274 TEST_ASSERT(INT128_MIN == -INT128_MAX - 1);
275
276 /* Signed overflow can get optimized away by the compiler, use uint128_t */
277 TEST_ASSERT((int128_t) ((uint128_t) INT128_MAX + 1) == INT128_MIN);
278 TEST_ASSERT((uint128_t) (UINT128_MAX + 1) == 0);
279
280 return TEST_SUCCESS;
281}
282