1 #include "test/jemalloc_test.h" 2 3 #include "jemalloc/internal/fxp.h" 4 5 static double 6 fxp2double(fxp_t a) { 7 double intpart = (double)(a >> 16); 8 double fracpart = (double)(a & ((1U << 16) - 1)) / (1U << 16); 9 return intpart + fracpart; 10 } 11 12 /* Is a close to b? */ 13 static bool 14 double_close(double a, double b) { 15 /* 16 * Our implementation doesn't try for precision. Correspondingly, don't 17 * enforce it too strenuously here; accept values that are close in 18 * either relative or absolute terms. 19 */ 20 return fabs(a - b) < 0.01 || fabs(a - b) / a < 0.01; 21 } 22 23 static bool 24 fxp_close(fxp_t a, fxp_t b) { 25 return double_close(fxp2double(a), fxp2double(b)); 26 } 27 28 static fxp_t 29 xparse_fxp(const char *str) { 30 fxp_t result; 31 bool err = fxp_parse(&result, str, NULL); 32 assert_false(err, "Invalid fxp string: %s", str); 33 return result; 34 } 35 36 static void 37 expect_parse_accurate(const char *str, const char *parse_str) { 38 double true_val = strtod(str, NULL); 39 fxp_t fxp_val; 40 char *end; 41 bool err = fxp_parse(&fxp_val, parse_str, &end); 42 expect_false(err, "Unexpected parse failure"); 43 expect_ptr_eq(parse_str + strlen(str), end, 44 "Didn't parse whole string"); 45 expect_true(double_close(fxp2double(fxp_val), true_val), 46 "Misparsed %s", str); 47 } 48 49 static void 50 parse_valid_trial(const char *str) { 51 /* The value it parses should be correct. */ 52 expect_parse_accurate(str, str); 53 char buf[100]; 54 snprintf(buf, sizeof(buf), "%swith_some_trailing_text", str); 55 expect_parse_accurate(str, buf); 56 snprintf(buf, sizeof(buf), "%s with a space", str); 57 expect_parse_accurate(str, buf); 58 snprintf(buf, sizeof(buf), "%s,in_a_malloc_conf_string:1", str); 59 expect_parse_accurate(str, buf); 60 } 61 62 TEST_BEGIN(test_parse_valid) { 63 parse_valid_trial("0"); 64 parse_valid_trial("1"); 65 parse_valid_trial("2"); 66 parse_valid_trial("100"); 67 parse_valid_trial("345"); 68 parse_valid_trial("00000000123"); 69 parse_valid_trial("00000000987"); 70 71 parse_valid_trial("0.0"); 72 parse_valid_trial("0.00000000000456456456"); 73 parse_valid_trial("100.00000000000456456456"); 74 75 parse_valid_trial("123.1"); 76 parse_valid_trial("123.01"); 77 parse_valid_trial("123.001"); 78 parse_valid_trial("123.0001"); 79 parse_valid_trial("123.00001"); 80 parse_valid_trial("123.000001"); 81 parse_valid_trial("123.0000001"); 82 83 parse_valid_trial(".0"); 84 parse_valid_trial(".1"); 85 parse_valid_trial(".01"); 86 parse_valid_trial(".001"); 87 parse_valid_trial(".0001"); 88 parse_valid_trial(".00001"); 89 parse_valid_trial(".000001"); 90 91 parse_valid_trial(".1"); 92 parse_valid_trial(".10"); 93 parse_valid_trial(".100"); 94 parse_valid_trial(".1000"); 95 parse_valid_trial(".100000"); 96 } 97 TEST_END 98 99 static void 100 expect_parse_failure(const char *str) { 101 fxp_t result = FXP_INIT_INT(333); 102 char *end = (void *)0x123; 103 bool err = fxp_parse(&result, str, &end); 104 expect_true(err, "Expected a parse error on: %s", str); 105 expect_ptr_eq((void *)0x123, end, 106 "Parse error shouldn't change results"); 107 expect_u32_eq(result, FXP_INIT_INT(333), 108 "Parse error shouldn't change results"); 109 } 110 111 TEST_BEGIN(test_parse_invalid) { 112 expect_parse_failure("123."); 113 expect_parse_failure("3.a"); 114 expect_parse_failure(".a"); 115 expect_parse_failure("a.1"); 116 expect_parse_failure("a"); 117 /* A valid string, but one that overflows. */ 118 expect_parse_failure("123456789"); 119 expect_parse_failure("0000000123456789"); 120 expect_parse_failure("1000000"); 121 } 122 TEST_END 123 124 static void 125 expect_init_percent(unsigned percent, const char *str) { 126 fxp_t result_init = FXP_INIT_PERCENT(percent); 127 fxp_t result_parse = xparse_fxp(str); 128 expect_u32_eq(result_init, result_parse, 129 "Expect representations of FXP_INIT_PERCENT(%u) and " 130 "fxp_parse(\"%s\") to be equal; got %x and %x", 131 percent, str, result_init, result_parse); 132 133 } 134 135 /* 136 * Every other test uses either parsing or FXP_INIT_INT; it gets tested in those 137 * ways. We need a one-off for the percent-based initialization, though. 138 */ 139 TEST_BEGIN(test_init_percent) { 140 expect_init_percent(100, "1"); 141 expect_init_percent(75, ".75"); 142 expect_init_percent(1, ".01"); 143 expect_init_percent(50, ".5"); 144 } 145 TEST_END 146 147 static void 148 expect_add(const char *astr, const char *bstr, const char* resultstr) { 149 fxp_t a = xparse_fxp(astr); 150 fxp_t b = xparse_fxp(bstr); 151 fxp_t result = xparse_fxp(resultstr); 152 expect_true(fxp_close(fxp_add(a, b), result), 153 "Expected %s + %s == %s", astr, bstr, resultstr); 154 } 155 156 TEST_BEGIN(test_add_simple) { 157 expect_add("0", "0", "0"); 158 expect_add("0", "1", "1"); 159 expect_add("1", "1", "2"); 160 expect_add("1.5", "1.5", "3"); 161 expect_add("0.1", "0.1", "0.2"); 162 expect_add("123", "456", "579"); 163 } 164 TEST_END 165 166 static void 167 expect_sub(const char *astr, const char *bstr, const char* resultstr) { 168 fxp_t a = xparse_fxp(astr); 169 fxp_t b = xparse_fxp(bstr); 170 fxp_t result = xparse_fxp(resultstr); 171 expect_true(fxp_close(fxp_sub(a, b), result), 172 "Expected %s - %s == %s", astr, bstr, resultstr); 173 } 174 175 TEST_BEGIN(test_sub_simple) { 176 expect_sub("0", "0", "0"); 177 expect_sub("1", "0", "1"); 178 expect_sub("1", "1", "0"); 179 expect_sub("3.5", "1.5", "2"); 180 expect_sub("0.3", "0.1", "0.2"); 181 expect_sub("456", "123", "333"); 182 } 183 TEST_END 184 185 static void 186 expect_mul(const char *astr, const char *bstr, const char* resultstr) { 187 fxp_t a = xparse_fxp(astr); 188 fxp_t b = xparse_fxp(bstr); 189 fxp_t result = xparse_fxp(resultstr); 190 expect_true(fxp_close(fxp_mul(a, b), result), 191 "Expected %s * %s == %s", astr, bstr, resultstr); 192 } 193 194 TEST_BEGIN(test_mul_simple) { 195 expect_mul("0", "0", "0"); 196 expect_mul("1", "0", "0"); 197 expect_mul("1", "1", "1"); 198 expect_mul("1.5", "1.5", "2.25"); 199 expect_mul("100.0", "10", "1000"); 200 expect_mul(".1", "10", "1"); 201 } 202 TEST_END 203 204 static void 205 expect_div(const char *astr, const char *bstr, const char* resultstr) { 206 fxp_t a = xparse_fxp(astr); 207 fxp_t b = xparse_fxp(bstr); 208 fxp_t result = xparse_fxp(resultstr); 209 expect_true(fxp_close(fxp_div(a, b), result), 210 "Expected %s / %s == %s", astr, bstr, resultstr); 211 } 212 213 TEST_BEGIN(test_div_simple) { 214 expect_div("1", "1", "1"); 215 expect_div("0", "1", "0"); 216 expect_div("2", "1", "2"); 217 expect_div("3", "2", "1.5"); 218 expect_div("3", "1.5", "2"); 219 expect_div("10", ".1", "100"); 220 expect_div("123", "456", ".2697368421"); 221 } 222 TEST_END 223 224 static void 225 expect_round(const char *str, uint32_t rounded_down, uint32_t rounded_nearest) { 226 fxp_t fxp = xparse_fxp(str); 227 uint32_t fxp_rounded_down = fxp_round_down(fxp); 228 uint32_t fxp_rounded_nearest = fxp_round_nearest(fxp); 229 expect_u32_eq(rounded_down, fxp_rounded_down, 230 "Mistake rounding %s down", str); 231 expect_u32_eq(rounded_nearest, fxp_rounded_nearest, 232 "Mistake rounding %s to nearest", str); 233 } 234 235 TEST_BEGIN(test_round_simple) { 236 expect_round("1.5", 1, 2); 237 expect_round("0", 0, 0); 238 expect_round("0.1", 0, 0); 239 expect_round("0.4", 0, 0); 240 expect_round("0.40000", 0, 0); 241 expect_round("0.5", 0, 1); 242 expect_round("0.6", 0, 1); 243 expect_round("123", 123, 123); 244 expect_round("123.4", 123, 123); 245 expect_round("123.5", 123, 124); 246 } 247 TEST_END 248 249 static void 250 expect_mul_frac(size_t a, const char *fracstr, size_t expected) { 251 fxp_t frac = xparse_fxp(fracstr); 252 size_t result = fxp_mul_frac(a, frac); 253 expect_true(double_close(expected, result), 254 "Expected %zu * %s == %zu (fracmul); got %zu", a, fracstr, 255 expected, result); 256 } 257 258 TEST_BEGIN(test_mul_frac_simple) { 259 expect_mul_frac(SIZE_MAX, "1.0", SIZE_MAX); 260 expect_mul_frac(SIZE_MAX, ".75", SIZE_MAX / 4 * 3); 261 expect_mul_frac(SIZE_MAX, ".5", SIZE_MAX / 2); 262 expect_mul_frac(SIZE_MAX, ".25", SIZE_MAX / 4); 263 expect_mul_frac(1U << 16, "1.0", 1U << 16); 264 expect_mul_frac(1U << 30, "0.5", 1U << 29); 265 expect_mul_frac(1U << 30, "0.25", 1U << 28); 266 expect_mul_frac(1U << 30, "0.125", 1U << 27); 267 expect_mul_frac((1U << 30) + 1, "0.125", 1U << 27); 268 expect_mul_frac(100, "0.25", 25); 269 expect_mul_frac(1000 * 1000, "0.001", 1000); 270 } 271 TEST_END 272 273 static void 274 expect_print(const char *str) { 275 fxp_t fxp = xparse_fxp(str); 276 char buf[FXP_BUF_SIZE]; 277 fxp_print(fxp, buf); 278 expect_d_eq(0, strcmp(str, buf), "Couldn't round-trip print %s", str); 279 } 280 281 TEST_BEGIN(test_print_simple) { 282 expect_print("0.0"); 283 expect_print("1.0"); 284 expect_print("2.0"); 285 expect_print("123.0"); 286 /* 287 * We hit the possibility of roundoff errors whenever the fractional 288 * component isn't a round binary number; only check these here (we 289 * round-trip properly in the stress test). 290 */ 291 expect_print("1.5"); 292 expect_print("3.375"); 293 expect_print("0.25"); 294 expect_print("0.125"); 295 /* 1 / 2**14 */ 296 expect_print("0.00006103515625"); 297 } 298 TEST_END 299 300 TEST_BEGIN(test_stress) { 301 const char *numbers[] = { 302 "0.0", "0.1", "0.2", "0.3", "0.4", 303 "0.5", "0.6", "0.7", "0.8", "0.9", 304 305 "1.0", "1.1", "1.2", "1.3", "1.4", 306 "1.5", "1.6", "1.7", "1.8", "1.9", 307 308 "2.0", "2.1", "2.2", "2.3", "2.4", 309 "2.5", "2.6", "2.7", "2.8", "2.9", 310 311 "17.0", "17.1", "17.2", "17.3", "17.4", 312 "17.5", "17.6", "17.7", "17.8", "17.9", 313 314 "18.0", "18.1", "18.2", "18.3", "18.4", 315 "18.5", "18.6", "18.7", "18.8", "18.9", 316 317 "123.0", "123.1", "123.2", "123.3", "123.4", 318 "123.5", "123.6", "123.7", "123.8", "123.9", 319 320 "124.0", "124.1", "124.2", "124.3", "124.4", 321 "124.5", "124.6", "124.7", "124.8", "124.9", 322 323 "125.0", "125.1", "125.2", "125.3", "125.4", 324 "125.5", "125.6", "125.7", "125.8", "125.9"}; 325 size_t numbers_len = sizeof(numbers)/sizeof(numbers[0]); 326 for (size_t i = 0; i < numbers_len; i++) { 327 fxp_t fxp_a = xparse_fxp(numbers[i]); 328 double double_a = strtod(numbers[i], NULL); 329 330 uint32_t fxp_rounded_down = fxp_round_down(fxp_a); 331 uint32_t fxp_rounded_nearest = fxp_round_nearest(fxp_a); 332 uint32_t double_rounded_down = (uint32_t)double_a; 333 uint32_t double_rounded_nearest = (uint32_t)round(double_a); 334 335 expect_u32_eq(double_rounded_down, fxp_rounded_down, 336 "Incorrectly rounded down %s", numbers[i]); 337 expect_u32_eq(double_rounded_nearest, fxp_rounded_nearest, 338 "Incorrectly rounded-to-nearest %s", numbers[i]); 339 340 for (size_t j = 0; j < numbers_len; j++) { 341 fxp_t fxp_b = xparse_fxp(numbers[j]); 342 double double_b = strtod(numbers[j], NULL); 343 344 fxp_t fxp_sum = fxp_add(fxp_a, fxp_b); 345 double double_sum = double_a + double_b; 346 expect_true( 347 double_close(fxp2double(fxp_sum), double_sum), 348 "Miscomputed %s + %s", numbers[i], numbers[j]); 349 350 if (double_a > double_b) { 351 fxp_t fxp_diff = fxp_sub(fxp_a, fxp_b); 352 double double_diff = double_a - double_b; 353 expect_true( 354 double_close(fxp2double(fxp_diff), 355 double_diff), 356 "Miscomputed %s - %s", numbers[i], 357 numbers[j]); 358 } 359 360 fxp_t fxp_prod = fxp_mul(fxp_a, fxp_b); 361 double double_prod = double_a * double_b; 362 expect_true( 363 double_close(fxp2double(fxp_prod), double_prod), 364 "Miscomputed %s * %s", numbers[i], numbers[j]); 365 366 if (double_b != 0.0) { 367 fxp_t fxp_quot = fxp_div(fxp_a, fxp_b); 368 double double_quot = double_a / double_b; 369 expect_true( 370 double_close(fxp2double(fxp_quot), 371 double_quot), 372 "Miscomputed %s / %s", numbers[i], 373 numbers[j]); 374 } 375 } 376 } 377 } 378 TEST_END 379 380 int 381 main(void) { 382 return test_no_reentrancy( 383 test_parse_valid, 384 test_parse_invalid, 385 test_init_percent, 386 test_add_simple, 387 test_sub_simple, 388 test_mul_simple, 389 test_div_simple, 390 test_round_simple, 391 test_mul_frac_simple, 392 test_print_simple, 393 test_stress); 394 } 395