1#include "math/tests/test_internal.h"
2
3TEST_GROUP_DEFINE(bit_ops, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "iters",
6 });
7
8TEST_DEFINE_UNIT(bit_ops, next_pow2_standard) {
9 TEST_ASSERT_EQ(next_pow2(1), 1);
10 TEST_ASSERT_EQ(next_pow2(2), 2);
11 TEST_ASSERT_EQ(next_pow2(3), 4);
12 TEST_ASSERT_EQ(next_pow2(4), 4);
13 TEST_ASSERT_EQ(next_pow2(5), 8);
14 TEST_ASSERT_EQ(next_pow2(4096), 4096);
15 TEST_ASSERT_EQ(next_pow2(4097), 8192);
16
17 /* Exact powers must be fixed points, and one past must step once,
18 * p - 1 only rounds up to p from shift 2 and on */
19 for (size_t shift = 0; shift < 63; shift++) {
20 size_t p = (size_t) 1 << shift;
21 TEST_ASSERT_EQ(next_pow2(p), p);
22 if (shift >= 2)
23 TEST_ASSERT_EQ(next_pow2(p - 1), p);
24 TEST_ASSERT_EQ(next_pow2(p + 1), p << 1);
25 }
26
27 return TEST_SUCCESS;
28}
29
30TEST_DEFINE_UNIT(bit_ops, next_pow2_edge) {
31 TEST_ASSERT_EQ(next_pow2(0), 1);
32
33 /* Must avoid infinite loop */
34 size_t top = (size_t) 1 << 63;
35 TEST_ASSERT_EQ(next_pow2(top), top);
36 TEST_ASSERT_EQ(next_pow2(top + 1), top);
37 TEST_ASSERT_EQ(next_pow2(SIZE_MAX), top);
38
39 return TEST_SUCCESS;
40}
41
42TEST_DEFINE_UNIT(bit_ops, prev_pow2_standard) {
43 TEST_ASSERT_EQ(prev_pow2(1), 1);
44 TEST_ASSERT_EQ(prev_pow2(2), 2);
45 TEST_ASSERT_EQ(prev_pow2(3), 2);
46 TEST_ASSERT_EQ(prev_pow2(4), 4);
47 TEST_ASSERT_EQ(prev_pow2(5), 4);
48 TEST_ASSERT_EQ(prev_pow2(4096), 4096);
49 TEST_ASSERT_EQ(prev_pow2(4095), 2048);
50
51 for (size_t shift = 1; shift < 63; shift++) {
52 size_t p = (size_t) 1 << shift;
53 TEST_ASSERT_EQ(prev_pow2(p), p);
54 TEST_ASSERT_EQ(prev_pow2(p - 1), p >> 1);
55 TEST_ASSERT_EQ(prev_pow2(p + 1), p);
56 }
57
58 return TEST_SUCCESS;
59}
60
61TEST_DEFINE_UNIT(bit_ops, prev_pow2_edge) {
62 TEST_ASSERT_EQ(prev_pow2(0), 1);
63
64 size_t top = (size_t) 1 << 63;
65 TEST_ASSERT_EQ(prev_pow2(top), top);
66 TEST_ASSERT_EQ(prev_pow2(SIZE_MAX), top);
67
68 return TEST_SUCCESS;
69}
70
71/* prev_pow2(x) <= x <= next_pow2(x) must always be true */
72TEST_DEFINE_UNIT(bit_ops, pow2_bracket_invariant,
73 TEST_INTENSITY(256, 4096, 65536)) {
74 size_t iters = ctx->intensity_val ? ctx->intensity_val : 4096;
75 for (size_t x = 1; x <= iters; x++) {
76 size_t lo = prev_pow2(x);
77 size_t hi = next_pow2(x);
78
79 TEST_ASSERT_IN_RANGE(x, lo, hi);
80 TEST_ASSERT_EQ((lo & (lo - 1)), 0);
81 TEST_ASSERT_EQ((hi & (hi - 1)), 0);
82 TEST_ASSERT_LE(hi, lo * 2);
83 }
84
85 return TEST_SUCCESS;
86}
87
88TEST_DEFINE_UNIT(bit_ops, ilog2_standard) {
89 TEST_ASSERT_EQ(ilog2(1), 0);
90 TEST_ASSERT_EQ(ilog2(2), 1);
91 TEST_ASSERT_EQ(ilog2(3), 1);
92 TEST_ASSERT_EQ(ilog2(4), 2);
93 TEST_ASSERT_EQ(ilog2(4096), 12);
94
95 /* p + 1 keeps same floor except at p == 1, where next int
96 * is itself the next pow2 */
97 for (uint8_t shift = 0; shift < 64; shift++) {
98 uint64_t p = (uint64_t) 1 << shift;
99 TEST_ASSERT_EQ(ilog2(p), shift);
100 if (shift > 0)
101 TEST_ASSERT_EQ(ilog2(p - 1), shift - 1);
102 if (shift >= 1 && shift < 63)
103 TEST_ASSERT_EQ(ilog2(p + 1), shift);
104 }
105
106 return TEST_SUCCESS;
107}
108
109/* ilog2(0) == 0, which is also ilog2(1) */
110TEST_DEFINE_UNIT(bit_ops, ilog2_edge) {
111 TEST_ASSERT_EQ(ilog2(0), 0);
112 TEST_ASSERT_EQ(ilog2(UINT64_MAX), 63);
113
114 return TEST_SUCCESS;
115}
116
117TEST_DEFINE_UNIT(bit_ops, popcount_standard) {
118 TEST_ASSERT_EQ(popcount(0), 0);
119 TEST_ASSERT_EQ(popcount(1), 1);
120 TEST_ASSERT_EQ(popcount(3), 2);
121 TEST_ASSERT_EQ(popcount(SIZE_MAX), 64);
122 TEST_ASSERT_EQ(popcount(0x5555555555555555ULL), 32);
123 TEST_ASSERT_EQ(popcount(0xAAAAAAAAAAAAAAAAULL), 32);
124
125 for (size_t shift = 0; shift < 64; shift++)
126 TEST_ASSERT_EQ(popcount((size_t) 1 << shift), 1);
127
128 return TEST_SUCCESS;
129}
130
131TEST_DEFINE_UNIT(bit_ops, bit_macros_standard) {
132 uint8_t u8 = 0;
133 u8 = BIT_SET(u8, 2);
134 TEST_ASSERT_EQ(u8, 4);
135 TEST_ASSERT_EQ(sizeof(BIT_SET(u8, 2)), sizeof(uint8_t));
136 TEST_ASSERT(BIT_TEST(u8, 2));
137 TEST_ASSERT(!BIT_TEST(u8, 3));
138
139 u8 = BIT_TOGGLE(u8, 2);
140 TEST_ASSERT_EQ(u8, 0);
141 TEST_ASSERT_EQ(sizeof(BIT_TOGGLE(u8, 2)), sizeof(uint8_t));
142
143 uint32_t u32 = 0x12345678;
144 u32 = BIT_CLEAR(u32, 3);
145 TEST_ASSERT_EQ(u32, 0x12345670);
146 TEST_ASSERT_EQ(sizeof(BIT_CLEAR(u32, 3)), sizeof(uint32_t));
147
148 TEST_ASSERT(BIT_ANY(u32, UINT32_C(0x70)));
149 TEST_ASSERT(!BIT_ANY(u32, UINT32_C(0x80)));
150 TEST_ASSERT(BIT_ALL(u32, UINT32_C(0x12345670)));
151 TEST_ASSERT(!BIT_ALL(u32, UINT32_C(0x12345678)));
152
153 return TEST_SUCCESS;
154}
155
156TEST_DEFINE_UNIT(bit_ops, bit_fields_and_ranges) {
157 uint32_t reg32 = 0;
158 reg32 = BIT_SET_FIELD(reg32, 0xA, 4, 7);
159 TEST_ASSERT_EQ(reg32, 0xA0);
160 TEST_ASSERT_EQ(sizeof(BIT_SET_FIELD(reg32, 0xA, 4, 7)), sizeof(uint32_t));
161 TEST_ASSERT_EQ(BIT_GET_FIELD(reg32, 4, 7), 0xA);
162 TEST_ASSERT_EQ(sizeof(BIT_GET_FIELD(reg32, 4, 7)), sizeof(uint32_t));
163
164 uint64_t reg64 = 0;
165 reg64 = BIT_SET_FIELD(reg64, 0xDEADBEEFULL, 32, 63);
166 TEST_ASSERT_EQ(BIT_GET_FIELD(reg64, 32, 63), 0xDEADBEEFULL);
167
168 TEST_ASSERT_EQ(BIT_MASK(0, 0), 1ULL);
169 TEST_ASSERT_EQ(BIT_MASK(4, 7), 0xF0ULL);
170 TEST_ASSERT_EQ(BIT_MASK(0, 63), UINT64_MAX);
171
172 TEST_ASSERT_EQ(BIT_RANGE(0xABCD, 4, 7), 0xC);
173 TEST_ASSERT_EQ(BIT_WIDTH(4, 7), 4);
174 TEST_ASSERT_EQ(BIT_WIDTH(0, 63), 64);
175
176 return TEST_SUCCESS;
177}
178
179TEST_DEFINE_UNIT(bit_ops, align_and_rounding) {
180 size_t value = 5;
181 size_t alignment = 4;
182 TEST_ASSERT_EQ(ALIGN_UP(value++, alignment++), 8);
183 TEST_ASSERT_EQ(value, 6);
184 TEST_ASSERT_EQ(alignment, 5);
185
186 value = 9;
187 alignment = 8;
188 TEST_ASSERT_EQ(ALIGN_DOWN(value++, alignment++), 8);
189 TEST_ASSERT_EQ(value, 10);
190 TEST_ASSERT_EQ(alignment, 9);
191
192 value = 8;
193 alignment = 8;
194 TEST_ASSERT(IS_ALIGNED(value++, alignment++));
195 TEST_ASSERT_EQ(value, 9);
196 TEST_ASSERT_EQ(alignment, 9);
197
198 value = 4;
199 alignment = 3;
200 TEST_ASSERT(!IS_ALIGNED_UNCHECKED(value++, alignment++));
201 TEST_ASSERT_EQ(value, 5);
202 TEST_ASSERT_EQ(alignment, 4);
203 alignment = 0;
204 TEST_ASSERT(!IS_ALIGNED_UNCHECKED(value, alignment));
205 TEST_ASSERT_EQ(ALIGN_UP_WRAPPING(SIZE_MAX, 2), 0);
206
207 size_t divisor = 4;
208 value = 5;
209 TEST_ASSERT_EQ(DIV_ROUND_UP(value++, divisor++), 2);
210 TEST_ASSERT_EQ(value, 6);
211 TEST_ASSERT_EQ(divisor, 5);
212 TEST_ASSERT_EQ(DIV_ROUND_UP(SIZE_MAX, 2), SIZE_MAX / 2 + 1);
213
214 return TEST_SUCCESS;
215}
216
217TEST_DEFINE_UNIT(bit_ops, abs_and_pow2_macros) {
218 int value = -3;
219 TEST_ASSERT_EQ(abs(value++), 3);
220 TEST_ASSERT_EQ(value, -2);
221 value = 0;
222 TEST_ASSERT_EQ(abs(value), 0);
223 value = 3;
224 TEST_ASSERT_EQ(abs(value), 3);
225
226 size_t alignment = 8;
227 TEST_ASSERT(IS_POW2(alignment++));
228 TEST_ASSERT_EQ(alignment, 9);
229 TEST_ASSERT(!IS_POW2(alignment));
230 TEST_ASSERT(IS_POW2(SIZE_MAX / 2 + 1));
231 TEST_ASSERT(!IS_POW2((size_t) 0));
232
233 int signed_align = -8;
234 TEST_ASSERT(!IS_POW2(signed_align));
235
236 return TEST_SUCCESS;
237}
238
239TEST_DEFINE_UNIT(bit_ops, common_domain_comparisons) {
240 uint32_t small = 5;
241 uint64_t big = 9;
242 TEST_ASSERT_EQ(MIN(small, big), 5);
243 TEST_ASSERT_EQ(MIN(big, small), 5);
244 TEST_ASSERT_EQ(MAX(small, big), 9);
245 TEST_ASSERT_EQ(MAX(big, small), 9);
246 TEST_ASSERT_EQ(sizeof(MIN(small, big)), sizeof(uint64_t));
247 TEST_ASSERT_EQ(sizeof(MIN(big, small)), sizeof(uint64_t));
248
249 int64_t wide_signed = -4;
250 TEST_ASSERT_EQ(MIN(small, wide_signed), -4);
251 TEST_ASSERT_EQ(sizeof(MIN(small, wide_signed)), sizeof(int64_t));
252
253 int32_t narrow_signed = -3;
254 TEST_ASSERT_EQ(MAX(narrow_signed, wide_signed), -3);
255
256 size_t len = 7;
257 TEST_ASSERT_EQ(MIN(len, 0), 0);
258 TEST_ASSERT_EQ(MIN(0, len), 0);
259 TEST_ASSERT_EQ(MAX(len, 1), 7);
260 TEST_ASSERT_EQ(sizeof(MIN(len, 0)), sizeof(size_t));
261
262 uint8_t a8 = 200;
263 uint8_t b8 = 100;
264 TEST_ASSERT_EQ(MIN(a8, b8), 100);
265 TEST_ASSERT_EQ(sizeof(MIN(a8, b8)), sizeof(uint8_t));
266 TEST_ASSERT_EQ(sizeof(MAX(a8, b8)), sizeof(uint8_t));
267
268 uint32_t left = 4;
269 uint32_t right = 6;
270 TEST_ASSERT_EQ(MIN(left++, right++), 4);
271 TEST_ASSERT_EQ(left, 5);
272 TEST_ASSERT_EQ(right, 7);
273
274 TEST_ASSERT_EQ(MAX(small, big, (uint64_t) 2), 9);
275 TEST_ASSERT_EQ(MIN(small, big, (uint64_t) 2), 2);
276
277 return TEST_SUCCESS;
278}
279
280TEST_DEFINE_UNIT(bit_ops, common_domain_range_and_clamp) {
281 uint64_t value = 40;
282 uint32_t low = 10;
283 TEST_ASSERT(IN_RANGE(value, low, 64));
284 TEST_ASSERT(!IN_RANGE(value, low, 32));
285 TEST_ASSERT(IN_RANGE(value, 0, value));
286
287 int32_t signed_value = -5;
288 TEST_ASSERT(IN_RANGE(signed_value, -19, 20));
289 TEST_ASSERT(!IN_RANGE(signed_value, 0, 20));
290
291 uint32_t narrow = 500;
292 uint64_t ceiling = 100;
293 narrow = CLAMP(narrow, 0, ceiling);
294 TEST_ASSERT_EQ(narrow, 100);
295 TEST_ASSERT_EQ(sizeof(narrow), sizeof(uint32_t));
296
297 int32_t delta = -80;
298 delta = CLAMP(delta, -20, 20);
299 TEST_ASSERT_EQ(delta, -20);
300
301 return TEST_SUCCESS;
302}
303
304TEST_DEFINE_UNIT(bit_ops, bit_macros_preserve_operand_type) {
305 uint32_t reg = 0x80000000u;
306 TEST_ASSERT_EQ(sizeof(BIT_TEST(reg, 31)), sizeof(bool));
307 TEST_ASSERT(BIT_TEST(reg, 31));
308 TEST_ASSERT(!BIT_TEST(reg, 30));
309
310 uint32_t index = 31;
311 TEST_ASSERT(BIT_TEST(reg, index++));
312 TEST_ASSERT_EQ(index, 32);
313
314 uint32_t packed = 0x0000ABCDu;
315 TEST_ASSERT_EQ(BIT_RANGE(packed, 4, 7), 0xC);
316 TEST_ASSERT_EQ(sizeof(BIT_RANGE(packed, 4, 7)), sizeof(uint32_t));
317
318 uint64_t wide = UINT64_C(0xDEADBEEF) << 32;
319 TEST_ASSERT_EQ(BIT_RANGE(wide, 32, 63), UINT64_C(0xDEADBEEF));
320 TEST_ASSERT_EQ(sizeof(BIT_RANGE(wide, 32, 63)), sizeof(uint64_t));
321
322 TEST_ASSERT(BIT_ANY(packed, 0xF0));
323 TEST_ASSERT(!BIT_ANY(packed, 0xF0000000u));
324 TEST_ASSERT(BIT_ALL(packed, 0xABCD));
325 TEST_ASSERT_EQ(sizeof(BIT_ANY(packed, 0xF0)), sizeof(bool));
326
327 uint32_t lo = 4;
328 TEST_ASSERT_EQ(BIT_MASK(lo++, 7), 0xF0ULL);
329 TEST_ASSERT_EQ(lo, 5);
330
331 return TEST_SUCCESS;
332}
333
334TEST_DEFINE_UNIT(bit_ops, compiler_wrappers_popcount_and_bswap) {
335 uint8_t u8 = 0b1011;
336 uint16_t u16 = 0x00FF;
337 uint32_t u32 = 0x00FF00FF;
338 uint64_t u64 = 0x5555555555555555ULL;
339
340 TEST_ASSERT_EQ(cw_popcount(u8), 3);
341 TEST_ASSERT_EQ(cw_popcount(u16), 8);
342 TEST_ASSERT_EQ(cw_popcount(u32), 16);
343 TEST_ASSERT_EQ(cw_popcount(u64), 32);
344
345 TEST_ASSERT_EQ(cw_bswap((uint16_t) 0x1234), 0x3412);
346 TEST_ASSERT_EQ(cw_bswap((uint32_t) 0x12345678), 0x78563412);
347 TEST_ASSERT_EQ(cw_bswap((uint64_t) 0x0102030405060708ULL),
348 0x0807060504030201ULL);
349
350 return TEST_SUCCESS;
351}
352
353TEST_DEFINE_UNIT(bit_ops, compiler_wrappers_clz_ctz_ffs_fls) {
354 TEST_ASSERT_EQ(cw_clz((uint8_t) 0), 8);
355 TEST_ASSERT_EQ(cw_clz((uint8_t) 1), 7);
356 TEST_ASSERT_EQ(cw_clz((uint8_t) 0x80), 0);
357
358 TEST_ASSERT_EQ(cw_clz((uint32_t) 0), 32);
359 TEST_ASSERT_EQ(cw_clz((uint32_t) 1), 31);
360 TEST_ASSERT_EQ(cw_clz((uint32_t) 0x80000000), 0);
361
362 TEST_ASSERT_EQ(cw_clz((uint64_t) 0), 64);
363 TEST_ASSERT_EQ(cw_clz((uint64_t) 1), 63);
364
365 TEST_ASSERT_EQ(cw_ctz((uint8_t) 0), 8);
366 TEST_ASSERT_EQ(cw_ctz((uint8_t) 2), 1);
367 TEST_ASSERT_EQ(cw_ctz((uint32_t) 0), 32);
368 TEST_ASSERT_EQ(cw_ctz((uint32_t) 8), 3);
369 TEST_ASSERT_EQ(cw_ctz((uint64_t) 0), 64);
370 TEST_ASSERT_EQ(cw_ctz((uint64_t) 16), 4);
371
372 TEST_ASSERT_EQ(cw_ffs((uint32_t) 0), 0);
373 TEST_ASSERT_EQ(cw_ffs((uint32_t) 1), 1);
374 TEST_ASSERT_EQ(cw_ffs((uint32_t) 0x10), 5);
375
376 TEST_ASSERT_EQ(cw_fls((uint32_t) 0), 0);
377 TEST_ASSERT_EQ(cw_fls((uint32_t) 1), 1);
378 TEST_ASSERT_EQ(cw_fls((uint32_t) 0x10), 5);
379 TEST_ASSERT_EQ(cw_fls((uint32_t) 0x80000000), 32);
380
381 TEST_ASSERT_EQ(cw_parity((uint32_t) 0), 0);
382 TEST_ASSERT_EQ(cw_parity((uint32_t) 1), 1);
383 TEST_ASSERT_EQ(cw_parity((uint32_t) 3), 0);
384 TEST_ASSERT_EQ(cw_parity((uint32_t) 7), 1);
385
386 return TEST_SUCCESS;
387}
388
389TEST_DEFINE_UNIT(bit_ops, compiler_wrappers_rotations_and_saturation) {
390 uint32_t val32 = 0x12345678;
391 TEST_ASSERT_EQ(cw_rol(val32, 4), 0x23456781);
392 TEST_ASSERT_EQ(cw_ror(val32, 4), 0x81234567);
393 TEST_ASSERT_EQ(cw_rol(val32, 0), val32);
394 TEST_ASSERT_EQ(cw_ror(val32, 0), val32);
395
396 /* Saturating arithmetic */
397 TEST_ASSERT_EQ(cw_sat_add((uint32_t) 10, (uint32_t) 20), 30);
398 TEST_ASSERT_EQ(cw_sat_add((uint32_t) (UINT32_MAX - 5), (uint32_t) 10),
399 UINT32_MAX);
400 TEST_ASSERT_EQ(cw_sat_sub((uint32_t) 10, (uint32_t) 20), 0);
401 TEST_ASSERT_EQ(cw_sat_sub((uint32_t) 20, (uint32_t) 10), 10);
402
403 TEST_ASSERT_EQ(cw_sat_add((int32_t) (INT32_MAX - 5), (int32_t) 10),
404 INT32_MAX);
405 TEST_ASSERT_EQ(cw_sat_add((int32_t) (INT32_MIN + 5), (int32_t) -10),
406 INT32_MIN);
407 TEST_ASSERT_EQ(cw_sat_sub((int32_t) (INT32_MIN + 5), (int32_t) 10),
408 INT32_MIN);
409 TEST_ASSERT_EQ(cw_sat_sub((int32_t) (INT32_MAX - 5), (int32_t) -10),
410 INT32_MAX);
411
412 return TEST_SUCCESS;
413}
414