1#include "math/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(bit_ops, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "iters",
6 });
7
8TEST_DECLARE_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_DECLARE_UNIT(bit_ops, next_pow2_edges) {
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_DECLARE_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_DECLARE_UNIT(bit_ops, prev_pow2_edges) {
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_DECLARE_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_DECLARE_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_DECLARE_UNIT(bit_ops, ilog2_edges) {
111 TEST_ASSERT_EQ(ilog2(0), 0);
112 TEST_ASSERT_EQ(ilog2(UINT64_MAX), 63);
113
114 return TEST_SUCCESS;
115}
116
117TEST_DECLARE_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