diff options
Diffstat (limited to 'btest.c')
| -rw-r--r-- | btest.c | 636 |
1 files changed, 636 insertions, 0 deletions
@@ -0,0 +1,636 @@ +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <signal.h> +#include <setjmp.h> +#include <math.h> +#include "btest.h" + +/* Not declared in some stdlib.h files, so define here */ +float strtof(const char* nptr, char** endptr); + +/************************* + * Configuration Constants + *************************/ + +/* Handle infinite loops by setting upper limit on execution time, in + seconds */ +#define TIMEOUT_LIMIT 10 + +/* For functions with a single argument, generate TEST_RANGE values + above and below the min and max test values, and above and below + zero. Functions with two or three args will use square and cube + roots of this value, respectively, to avoid combinatorial + explosion */ +#define TEST_RANGE 500000 + +/* This defines the maximum size of any test value array. The + gen_vals() routine creates k test values for each value of + TEST_RANGE, thus MAX_TEST_VALS must be at least k*TEST_RANGE */ +#define MAX_TEST_VALS 13 * TEST_RANGE + +/********************************** + * Globals defined in other modules + **********************************/ +/* This characterizes the set of puzzles to test. + Defined in decl.c and generated from templates in ./puzzles dir */ +extern test_rec test_set[]; + +/************************************************ + * Write-once globals defined by command line args + ************************************************/ + +/* Emit results in a format for autograding, without showing + and counter-examples */ +static int grade = 0; + +/* Time out after this number of seconds */ +static int timeout_limit = TIMEOUT_LIMIT; /* -T */ + +/* If non-NULL, test only one function (-f) */ +static char* test_fname = NULL; + +/* Special case when only use fixed argument(s) (-1, -2, or -3) */ +static int has_arg[3] = {0, 0, 0}; +static unsigned argval[3] = {0, 0, 0}; + +/* Use fixed weight for rating, and if so, what should it be? (-r) */ +static int global_rating = 0; + +/****************** + * Helper functions + ******************/ + +/* + * Signal - installs a signal handler + */ +typedef void handler_t(int); + +handler_t* Signal(int signum, handler_t* handler) { + struct sigaction action, old_action; + + action.sa_handler = handler; + sigemptyset(&action.sa_mask); /* block sigs of type being handled */ + action.sa_flags = SA_RESTART; /* restart syscalls if possible */ + + if (sigaction(signum, &action, &old_action) < 0) + perror("Signal error"); + return (old_action.sa_handler); +} + +/* + * timeout_handler - SIGALARM hander + */ +sigjmp_buf envbuf; +void timeout_handler(int sig) { + siglongjmp(envbuf, 1); +} + +/* + * random_val - Return random integer value between min and max + */ +static int random_val(int min, int max) { + double weight = rand() / (double)RAND_MAX; + int result = min * (1 - weight) + max * weight; + return result; +} + +void pack_store(int test_vals_low[], int test_vals_high[], int* test_count, int64_t value) { + test_vals_low[*test_count] = value & 0xFFFFFFFF; + test_vals_high[*test_count] = (value >> 32) & 0xFFFFFFFF; + (*test_count)++; +} + +/* + * gen_float64_vals - 生成 64 位 float 的测试数据，分别填充到 test_vals_low 和 test_vals_high 中 + */ +static int gen_float64_vals(int test_vals_low[], int test_vals_high[], int test_range, int arg_low, int arg_high) { + int64_t i; + int test_count = 0; + if (has_arg[arg_low] && has_arg[arg_high]) { + test_vals_low[0] = argval[arg_low]; + test_vals_high[0] = argval[arg_high]; + return 1; + } else if (has_arg[arg_low] || has_arg[arg_high]) { + printf("Configuration error: You can't set only one of the two float arguments, as they are a pair.\n"); + exit(1); + } + + int64_t smallest_norm = 0x0010000000000000; + int64_t one = 0x3ff0000000000000; + int64_t largest_norm = 0x7fefffffffffffff; + + int64_t inf = 0x7ff0000000000000; + int64_t nan = 0x7ff8000000000000; + int64_t sign = 0x8000000000000000; + + for (i = 0; i < test_range; i++) { + /* Denorms around zero */ + pack_store(test_vals_low, test_vals_high, &test_count, i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | i); + + /* Region around norm to denorm transition */ + pack_store(test_vals_low, test_vals_high, &test_count, smallest_norm + i); + pack_store(test_vals_low, test_vals_high, &test_count, smallest_norm - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (smallest_norm + i)); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (smallest_norm - i)); + + /* Region around one */ + pack_store(test_vals_low, test_vals_high, &test_count, one + i); + pack_store(test_vals_low, test_vals_high, &test_count, one - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (one + i)); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (one - i)); + + /* Region below largest norm */ + pack_store(test_vals_low, test_vals_high, &test_count, largest_norm - i); + pack_store(test_vals_low, test_vals_high, &test_count, sign | (largest_norm - i)); + } + + /* special vals */ + pack_store(test_vals_low, test_vals_high, &test_count, inf); /* inf */ + pack_store(test_vals_low, test_vals_high, &test_count, sign | inf); /* -inf */ + pack_store(test_vals_low, test_vals_high, &test_count, nan); /* nan */ + pack_store(test_vals_low, test_vals_high, &test_count, sign | nan); /* -nan */ + return test_count; +} + +/* + * gen_vals - Generate the integer values we'll use to test a function + */ +static int gen_vals(int test_vals[], int min, int max, int test_range, int arg) { + int i; + int test_count = 0; + + /* Special case: If the user has specified a specific function + argument using the -1, -2, or -3 flags, then simply use this + argument and return */ + if (has_arg[arg]) { + test_vals[0] = argval[arg]; + return 1; + } + + /* + * Special case: Generate test vals for floating point functions + * where the input argument is an unsigned bit-level + * representation of a float. For this case we want to test the + * regions around zero, the smallest normalized and largest + * denormalized numbers, one, and the largest normalized number, + * as well as inf and nan. + */ + if ((min == 1 && max == 1)) { + unsigned smallest_norm = 0x00800000; + unsigned one = 0x3f800000; + unsigned largest_norm = 0x7f000000; + + unsigned inf = 0x7f800000; + unsigned nan = 0x7fc00000; + unsigned sign = 0x80000000; + + /* Test range should be at most 1/2 the range of one exponent + value */ + if (test_range > (1 << 23)) { + test_range = 1 << 23; + } + + /* Functions where the input argument is an unsigned bit-level + representation of a float. The number of tests generated + inside this loop body is the value k referenced in the + comment for the global variable MAX_TEST_VALS. */ + + for (i = 0; i < test_range; i++) { + /* Denorms around zero */ + test_vals[test_count++] = i; + test_vals[test_count++] = sign | i; + + /* Region around norm to denorm transition */ + test_vals[test_count++] = smallest_norm + i; + test_vals[test_count++] = smallest_norm - i; + test_vals[test_count++] = sign | (smallest_norm + i); + test_vals[test_count++] = sign | (smallest_norm - i); + + /* Region around one */ + test_vals[test_count++] = one + i; + test_vals[test_count++] = one - i; + test_vals[test_count++] = sign | (one + i); + test_vals[test_count++] = sign | (one - i); + + /* Region below largest norm */ + test_vals[test_count++] = largest_norm - i; + test_vals[test_count++] = sign | (largest_norm - i); + } + + /* special vals */ + test_vals[test_count++] = inf; /* inf */ + test_vals[test_count++] = sign | inf; /* -inf */ + test_vals[test_count++] = nan; /* nan */ + test_vals[test_count++] = sign | nan; /* -nan */ + + return test_count; + } + + /* + * Normal case: Generate test vals for integer functions + */ + + /* If the range is small enough, then do exhaustively */ + if (max - MAX_TEST_VALS <= min) { + for (i = min; i <= max; i++) + test_vals[test_count++] = i; + return test_count; + } + + /* Otherwise, need to sample. Do so near the boundaries, around + zero, and for some random cases. */ + for (i = 0; i < test_range; i++) { + /* Test around the boundaries */ + test_vals[test_count++] = min + i; + test_vals[test_count++] = max - i; + + /* If zero falls between min and max, then also test around zero */ + if (i >= min && i <= max) + test_vals[test_count++] = i; + if (-i >= min && -i <= max) + test_vals[test_count++] = -i; + + /* Random case between min and max */ + test_vals[test_count++] = random_val(min, max); + } + return test_count; +} + +/* + * test_0_arg - Test a function with zero arguments + */ +static int test_0_arg(funct_t f, funct_t ft, char* name) { + int r = f(); + int rt = ft(); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s() failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, r, r, rt, rt); + + return error; +} + +/* + * test_1_arg - Test a function with one argument + */ +static int test_1_arg(funct_t f, funct_t ft, int arg1, char* name) { + funct1_t f1 = (funct1_t)f; + funct1_t f1t = (funct1_t)ft; + int r, rt, error; + + r = f1(arg1); + rt = f1t(arg1); + error = (r != rt); + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, r, r, rt, rt); + + return error; +} + +/* + * test_2_arg - Test a function with two arguments + */ +static int test_2_arg(funct_t f, funct_t ft, int arg1, int arg2, char* name) { + funct2_t f2 = (funct2_t)f; + funct2_t f2t = (funct2_t)ft; + int r = f2(arg1, arg2); + int rt = f2t(arg1, arg2); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, r, r, rt, rt); + + return error; +} + +/* + * test_3_arg - Test a function with three arguments + */ +static int test_3_arg(funct_t f, funct_t ft, int arg1, int arg2, int arg3, char* name) { + funct3_t f3 = (funct3_t)f; + funct3_t f3t = (funct3_t)ft; + int r = f3(arg1, arg2, arg3); + int rt = f3t(arg1, arg2, arg3); + int error = (r != rt); + + if (error && !grade) + printf("ERROR: Test %s(%d[0x%x],%d[0x%x],%d[0x%x]) failed...\n...Gives %d[0x%x]. Should be %d[0x%x]\n", name, arg1, arg1, arg2, arg2, arg3, arg3, r, r, rt, rt); + + return error; +} + +/* + * test_function - Test a function. Return number of errors + */ +static int test_function(test_ptr t, int arg_low, int arg_high) { + int test_counts[3]; /* number of test values for each arg */ + int args = t->args; /* number of function arguments */ + int arg_test_range[3] = {0}; /* test range for each argument */ + int i, a1, a2, a3; + int errors __attribute__((unused)) = 0; + + /* These are the test values for each arg. Declared with the + static attribute so that the array will be allocated in bss + rather than the stack */ + static int arg_test_vals[3][MAX_TEST_VALS]; + + /* Sanity check on the number of args */ + if (args < 0 || args > 3) { + printf("Configuration error: invalid number of args (%d) for function %s\n", args, t->name); + exit(1); + } + + /* Assign range of argument test vals so as to conserve the total + number of tests, independent of the number of arguments */ + if (args == 1) { + arg_test_range[0] = TEST_RANGE; + } else if (args == 2) { + arg_test_range[0] = pow((double)TEST_RANGE, 0.5); /* sqrt */ + arg_test_range[1] = arg_test_range[0]; + } else { + arg_test_range[0] = pow((double)TEST_RANGE, 0.333); /* cbrt */ + arg_test_range[1] = arg_test_range[0]; + arg_test_range[2] = arg_test_range[0]; + } + + /* Sanity check on the ranges */ + if (arg_test_range[0] < 1) + arg_test_range[0] = 1; + if (arg_test_range[1] < 1) + arg_test_range[1] = 1; + if (arg_test_range[2] < 1) + arg_test_range[2] = 1; + + /* Create a test set for each argument */ + for (i = 0; i < args; i++) { + if (i == arg_low || i == arg_high) + continue; + test_counts[i] = gen_vals(arg_test_vals[i], + t->arg_ranges[i][0], /* min */ + t->arg_ranges[i][1], /* max */ + arg_test_range[i], + i); + } + + if (arg_low != -1 && arg_high != -1) { + if (args != 2) { + printf("Configuration error: invalid number of args (%d) for function %s. Support only two arguments for now.\n", args, t->name); + exit(1); + } + int test_count = gen_float64_vals(arg_test_vals[arg_low], arg_test_vals[arg_high], TEST_RANGE, arg_low, arg_high); + test_counts[arg_low] = test_count; + test_counts[arg_high] = test_count; + } + + /* Handle timeouts in the test code */ + if (timeout_limit > 0) { + int rc; + rc = sigsetjmp(envbuf, 1); + if (rc) { + /* control will reach here if there is a timeout */ + errors = 1; + printf("ERROR: Test %s failed.\n Timed out after %d secs (probably infinite loop)\n", t->name, timeout_limit); + return errors; + } + alarm(timeout_limit); + } + + /* Test function has no arguments */ + if (args == 0) { + errors += test_0_arg(t->solution_funct, t->test_funct, t->name); + return errors; + } + + /* + * Test function has at least one argument + */ + + /* Iterate over the values for first argument */ + + if (arg_low != -1 && arg_high != -1) { + for (a1 = 0; a1 < test_counts[0]; a1++) { + errors += test_2_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a1], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } + return errors; + } + + for (a1 = 0; a1 < test_counts[0]; a1++) { + if (args == 1) { + errors += test_1_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } else { + /* if necessary, iterate over values for second argument */ + for (a2 = 0; a2 < test_counts[1]; a2++) { + if (args == 2) { + errors += test_2_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } else { + /* if necessary, iterate over vals for third arg */ + for (a3 = 0; a3 < test_counts[2]; a3++) { + errors += test_3_arg(t->solution_funct, + t->test_funct, + arg_test_vals[0][a1], + arg_test_vals[1][a2], + arg_test_vals[2][a3], + t->name); + + /* Stop testing if there is an error */ + if (errors) + return errors; + } /* a3 */ + } + } /* a2 */ + } + } /* a1 */ + + return errors; +} + +/* + * run_tests - Run series of tests. Return number of errors + */ +static int run_tests() { + int i; + int errors = 0; + double points = 0.0; + double max_points = 0.0; + + // printf("Score\tRating\tErrors\tFunction\n"); + + for (i = 0; test_set[i].solution_funct; i++) { + int terrors; + double tscore; + double tpoints; + if (!test_fname || strcmp(test_set[i].name, test_fname) == 0) { + int rating = global_rating ? global_rating : test_set[i].rating; + if (strcmp(test_set[i].name, "float64_f2i") == 0) { // special case for float64_f2i + terrors = test_function(&test_set[i], 0, 1); + } else { + terrors = test_function(&test_set[i], -1, -1); + } + errors += terrors; + tscore = terrors == 0 ? 1.0 : 0.0; + tpoints = rating * tscore; + points += tpoints; + max_points += rating; + + if (grade || terrors < 1) + printf(" %.0f\t%d\t%d\t%s\n", + tpoints, rating, terrors, test_set[i].name); + } + } + + // printf("Total points: %.0f/%.0f\n", points, max_points); + return errors; +} + +/* + * get_num_val - Extract hex/decimal/or float value from string + */ +static int get_num_val(char* sval, unsigned* valp) { + char* endp; + + /* See if it's an integer or floating point */ + int ishex = 0; + int isfloat = 0; + int i; + for (i = 0; sval[i]; i++) { + switch (sval[i]) { + case 'x': + case 'X': + ishex = 1; + break; + case 'e': + case 'E': + if (!ishex) + isfloat = 1; + break; + case '.': + isfloat = 1; + break; + default: + break; + } + } + if (isfloat) { + float fval = strtof(sval, &endp); + if (!*endp) { + *valp = *(unsigned*)&fval; + return 1; + } + return 0; + } else { + long long int llval = strtoll(sval, &endp, 0); + long long int upperbits = llval >> 31; + /* will give -1 for negative, 0 or 1 for positive */ + if (!*valp && (upperbits == 0 || upperbits == -1 || upperbits == 1)) { + *valp = (unsigned)llval; + return 1; + } + return 0; + } +} + +/* + * usage - Display usage info + */ +static void usage(char* cmd) { + printf("Usage: %s [-hg] [-r <n>] [-f <name> [-1|-2|-3 <val>]*] [-T <time limit>]\n", cmd); + printf(" -1 <val> Specify first function argument\n"); + printf(" -2 <val> Specify second function argument\n"); + printf(" -3 <val> Specify third function argument\n"); + printf(" -f <name> Test only the named function\n"); + printf(" -g Compact output for grading (with no error msgs)\n"); + printf(" -h Print this message\n"); + printf(" -r <n> Give uniform weight of n for all problems\n"); + printf(" -T <lim> Set timeout limit to lim\n"); + exit(1); +} + +/************** + * Main routine + **************/ + +int main(int argc, char* argv[]) { + int __attribute__((unused)) errors; + char c; + + /* parse command line args */ + while ((c = getopt(argc, argv, "hgf:r:T:1:2:3:")) != -1) + switch (c) { + case 'h': /* help */ + usage(argv[0]); + break; + case 'g': /* grading option for autograder */ + grade = 1; + break; + case 'f': /* test only one function */ + test_fname = strdup(optarg); + break; + case 'r': /* set global rating for each problem */ + global_rating = atoi(optarg); + if (global_rating < 0) + usage(argv[0]); + break; + case '1': /* Get first argument */ + has_arg[0] = get_num_val(optarg, &argval[0]); + if (!has_arg[0]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case '2': /* Get first argument */ + has_arg[1] = get_num_val(optarg, &argval[1]); + if (!has_arg[1]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case '3': /* Get first argument */ + has_arg[2] = get_num_val(optarg, &argval[2]); + if (!has_arg[2]) { + printf("Bad argument '%s'\n", optarg); + exit(0); + } + break; + case 'T': /* Set timeout limit */ + timeout_limit = atoi(optarg); + break; + default: + usage(argv[0]); + } + + if (timeout_limit > 0) { + Signal(SIGALRM, timeout_handler); + } + + /* test each function */ + errors = run_tests(); + + return 0; +} |