1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/bit_util.h" 4 5 #define TEST_POW2_CEIL(t, suf, pri) do { \ 6 unsigned i, pow2; \ 7 t x; \ 8 \ 9 expect_##suf##_eq(pow2_ceil_##suf(0), 0, "Unexpected result"); \ 10 \ 11 for (i = 0; i < sizeof(t) * 8; i++) { \ 12 expect_##suf##_eq(pow2_ceil_##suf(((t)1) << i), ((t)1) \ 13 << i, "Unexpected result"); \ 14 } \ 15 \ 16 for (i = 2; i < sizeof(t) * 8; i++) { \ 17 expect_##suf##_eq(pow2_ceil_##suf((((t)1) << i) - 1), \ 18 ((t)1) << i, "Unexpected result"); \ 19 } \ 20 \ 21 for (i = 0; i < sizeof(t) * 8 - 1; i++) { \ 22 expect_##suf##_eq(pow2_ceil_##suf((((t)1) << i) + 1), \ 23 ((t)1) << (i+1), "Unexpected result"); \ 24 } \ 25 \ 26 for (pow2 = 1; pow2 < 25; pow2++) { \ 27 for (x = (((t)1) << (pow2-1)) + 1; x <= ((t)1) << pow2; \ 28 x++) { \ 29 expect_##suf##_eq(pow2_ceil_##suf(x), \ 30 ((t)1) << pow2, \ 31 "Unexpected result, x=%"pri, x); \ 32 } \ 33 } \ 34 } while (0) 35 36 TEST_BEGIN(test_pow2_ceil_u64) { 37 TEST_POW2_CEIL(uint64_t, u64, FMTu64); 38 } 39 TEST_END 40 41 TEST_BEGIN(test_pow2_ceil_u32) { 42 TEST_POW2_CEIL(uint32_t, u32, FMTu32); 43 } 44 TEST_END 45 46 TEST_BEGIN(test_pow2_ceil_zu) { 47 TEST_POW2_CEIL(size_t, zu, "zu"); 48 } 49 TEST_END 50 51 void 52 expect_lg_ceil_range(size_t input, unsigned answer) { 53 if (input == 1) { 54 expect_u_eq(0, answer, "Got %u as lg_ceil of 1", answer); 55 return; 56 } 57 expect_zu_le(input, (ZU(1) << answer), 58 "Got %u as lg_ceil of %zu", answer, input); 59 expect_zu_gt(input, (ZU(1) << (answer - 1)), 60 "Got %u as lg_ceil of %zu", answer, input); 61 } 62 63 void 64 expect_lg_floor_range(size_t input, unsigned answer) { 65 if (input == 1) { 66 expect_u_eq(0, answer, "Got %u as lg_floor of 1", answer); 67 return; 68 } 69 expect_zu_ge(input, (ZU(1) << answer), 70 "Got %u as lg_floor of %zu", answer, input); 71 expect_zu_lt(input, (ZU(1) << (answer + 1)), 72 "Got %u as lg_floor of %zu", answer, input); 73 } 74 75 TEST_BEGIN(test_lg_ceil_floor) { 76 for (size_t i = 1; i < 10 * 1000 * 1000; i++) { 77 expect_lg_ceil_range(i, lg_ceil(i)); 78 expect_lg_ceil_range(i, LG_CEIL(i)); 79 expect_lg_floor_range(i, lg_floor(i)); 80 expect_lg_floor_range(i, LG_FLOOR(i)); 81 } 82 for (int i = 10; i < 8 * (1 << LG_SIZEOF_PTR) - 5; i++) { 83 for (size_t j = 0; j < (1 << 4); j++) { 84 size_t num1 = ((size_t)1 << i) 85 - j * ((size_t)1 << (i - 4)); 86 size_t num2 = ((size_t)1 << i) 87 + j * ((size_t)1 << (i - 4)); 88 expect_zu_ne(num1, 0, "Invalid lg argument"); 89 expect_zu_ne(num2, 0, "Invalid lg argument"); 90 expect_lg_ceil_range(num1, lg_ceil(num1)); 91 expect_lg_ceil_range(num1, LG_CEIL(num1)); 92 expect_lg_ceil_range(num2, lg_ceil(num2)); 93 expect_lg_ceil_range(num2, LG_CEIL(num2)); 94 95 expect_lg_floor_range(num1, lg_floor(num1)); 96 expect_lg_floor_range(num1, LG_FLOOR(num1)); 97 expect_lg_floor_range(num2, lg_floor(num2)); 98 expect_lg_floor_range(num2, LG_FLOOR(num2)); 99 } 100 } 101 } 102 TEST_END 103 104 #define TEST_FFS(t, suf, test_suf, pri) do { \ 105 for (unsigned i = 0; i < sizeof(t) * 8; i++) { \ 106 for (unsigned j = 0; j <= i; j++) { \ 107 for (unsigned k = 0; k <= j; k++) { \ 108 t x = (t)1 << i; \ 109 x |= (t)1 << j; \ 110 x |= (t)1 << k; \ 111 expect_##test_suf##_eq(ffs_##suf(x), k, \ 112 "Unexpected result, x=%"pri, x); \ 113 } \ 114 } \ 115 } \ 116 } while(0) 117 118 TEST_BEGIN(test_ffs_u) { 119 TEST_FFS(unsigned, u, u,"u"); 120 } 121 TEST_END 122 123 TEST_BEGIN(test_ffs_lu) { 124 TEST_FFS(unsigned long, lu, lu, "lu"); 125 } 126 TEST_END 127 128 TEST_BEGIN(test_ffs_llu) { 129 TEST_FFS(unsigned long long, llu, qd, "llu"); 130 } 131 TEST_END 132 133 TEST_BEGIN(test_ffs_u32) { 134 TEST_FFS(uint32_t, u32, u32, FMTu32); 135 } 136 TEST_END 137 138 TEST_BEGIN(test_ffs_u64) { 139 TEST_FFS(uint64_t, u64, u64, FMTu64); 140 } 141 TEST_END 142 143 TEST_BEGIN(test_ffs_zu) { 144 TEST_FFS(size_t, zu, zu, "zu"); 145 } 146 TEST_END 147 148 #define TEST_FLS(t, suf, test_suf, pri) do { \ 149 for (unsigned i = 0; i < sizeof(t) * 8; i++) { \ 150 for (unsigned j = 0; j <= i; j++) { \ 151 for (unsigned k = 0; k <= j; k++) { \ 152 t x = (t)1 << i; \ 153 x |= (t)1 << j; \ 154 x |= (t)1 << k; \ 155 expect_##test_suf##_eq(fls_##suf(x), i, \ 156 "Unexpected result, x=%"pri, x); \ 157 } \ 158 } \ 159 } \ 160 } while(0) 161 162 TEST_BEGIN(test_fls_u) { 163 TEST_FLS(unsigned, u, u,"u"); 164 } 165 TEST_END 166 167 TEST_BEGIN(test_fls_lu) { 168 TEST_FLS(unsigned long, lu, lu, "lu"); 169 } 170 TEST_END 171 172 TEST_BEGIN(test_fls_llu) { 173 TEST_FLS(unsigned long long, llu, qd, "llu"); 174 } 175 TEST_END 176 177 TEST_BEGIN(test_fls_u32) { 178 TEST_FLS(uint32_t, u32, u32, FMTu32); 179 } 180 TEST_END 181 182 TEST_BEGIN(test_fls_u64) { 183 TEST_FLS(uint64_t, u64, u64, FMTu64); 184 } 185 TEST_END 186 187 TEST_BEGIN(test_fls_zu) { 188 TEST_FLS(size_t, zu, zu, "zu"); 189 } 190 TEST_END 191 192 TEST_BEGIN(test_fls_u_slow) { 193 TEST_FLS(unsigned, u_slow, u,"u"); 194 } 195 TEST_END 196 197 TEST_BEGIN(test_fls_lu_slow) { 198 TEST_FLS(unsigned long, lu_slow, lu, "lu"); 199 } 200 TEST_END 201 202 TEST_BEGIN(test_fls_llu_slow) { 203 TEST_FLS(unsigned long long, llu_slow, qd, "llu"); 204 } 205 TEST_END 206 207 static unsigned 208 popcount_byte(unsigned byte) { 209 int count = 0; 210 for (int i = 0; i < 8; i++) { 211 if ((byte & (1 << i)) != 0) { 212 count++; 213 } 214 } 215 return count; 216 } 217 218 static uint64_t 219 expand_byte_to_mask(unsigned byte) { 220 uint64_t result = 0; 221 for (int i = 0; i < 8; i++) { 222 if ((byte & (1 << i)) != 0) { 223 result |= ((uint64_t)0xFF << (i * 8)); 224 } 225 } 226 return result; 227 } 228 229 #define TEST_POPCOUNT(t, suf, pri_hex) do { \ 230 t bmul = (t)0x0101010101010101ULL; \ 231 for (unsigned i = 0; i < (1 << sizeof(t)); i++) { \ 232 for (unsigned j = 0; j < 256; j++) { \ 233 /* \ 234 * Replicate the byte j into various \ 235 * bytes of the integer (as indicated by the \ 236 * mask in i), and ensure that the popcount of \ 237 * the result is popcount(i) * popcount(j) \ 238 */ \ 239 t mask = (t)expand_byte_to_mask(i); \ 240 t x = (bmul * j) & mask; \ 241 expect_u_eq( \ 242 popcount_byte(i) * popcount_byte(j), \ 243 popcount_##suf(x), \ 244 "Unexpected result, x=0x%"pri_hex, x); \ 245 } \ 246 } \ 247 } while (0) 248 249 TEST_BEGIN(test_popcount_u) { 250 TEST_POPCOUNT(unsigned, u, "x"); 251 } 252 TEST_END 253 254 TEST_BEGIN(test_popcount_u_slow) { 255 TEST_POPCOUNT(unsigned, u_slow, "x"); 256 } 257 TEST_END 258 259 TEST_BEGIN(test_popcount_lu) { 260 TEST_POPCOUNT(unsigned long, lu, "lx"); 261 } 262 TEST_END 263 264 TEST_BEGIN(test_popcount_lu_slow) { 265 TEST_POPCOUNT(unsigned long, lu_slow, "lx"); 266 } 267 TEST_END 268 269 TEST_BEGIN(test_popcount_llu) { 270 TEST_POPCOUNT(unsigned long long, llu, "llx"); 271 } 272 TEST_END 273 274 TEST_BEGIN(test_popcount_llu_slow) { 275 TEST_POPCOUNT(unsigned long long, llu_slow, "llx"); 276 } 277 TEST_END 278 279 int 280 main(void) { 281 return test_no_reentrancy( 282 test_pow2_ceil_u64, 283 test_pow2_ceil_u32, 284 test_pow2_ceil_zu, 285 test_lg_ceil_floor, 286 test_ffs_u, 287 test_ffs_lu, 288 test_ffs_llu, 289 test_ffs_u32, 290 test_ffs_u64, 291 test_ffs_zu, 292 test_fls_u, 293 test_fls_lu, 294 test_fls_llu, 295 test_fls_u32, 296 test_fls_u64, 297 test_fls_zu, 298 test_fls_u_slow, 299 test_fls_lu_slow, 300 test_fls_llu_slow, 301 test_popcount_u, 302 test_popcount_u_slow, 303 test_popcount_lu, 304 test_popcount_lu_slow, 305 test_popcount_llu, 306 test_popcount_llu_slow); 307 } 308