X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=tests%2Ftest-util.c;h=6bf8ed52c4b741afc807d3a15e3de69a388373dc;hb=77d14d9c7f9ce7245eff56aacd420646577892d0;hp=45ea8f29feb8f69281d6821db4f055064873e10b;hpb=ddc4f8e27f231b35df0c73a16bacc17396fb00f3;p=sliver-openvswitch.git diff --git a/tests/test-util.c b/tests/test-util.c index 45ea8f29f..6bf8ed52c 100644 --- a/tests/test-util.c +++ b/tests/test-util.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, 2012 Nicira Networks. + * Copyright (c) 2011, 2012, 2013 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,14 +16,20 @@ #include +#include #include #include #include #include #include "byte-order.h" +#include "command-line.h" #include "random.h" #include "util.h" +#include "vlog.h" + +#undef NDEBUG +#include static void check_log_2_floor(uint32_t x, int n) @@ -35,6 +41,25 @@ check_log_2_floor(uint32_t x, int n) } } +static void +test_log_2_floor(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + int n; + + for (n = 0; n < 32; n++) { + /* Check minimum x such that f(x) == n. */ + check_log_2_floor(1 << n, n); + + /* Check maximum x such that f(x) == n. */ + check_log_2_floor((1 << n) | ((1 << n) - 1), n); + + /* Check a random value in the middle. */ + check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n); + } + + /* log_2_floor(0) is undefined, so don't check it. */ +} + static void check_ctz(uint32_t x, int n) { @@ -45,6 +70,142 @@ check_ctz(uint32_t x, int n) } } +static void +test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + int n; + + for (n = 0; n < 32; n++) { + /* Check minimum x such that f(x) == n. */ + check_ctz(1 << n, n); + + /* Check maximum x such that f(x) == n. */ + check_ctz(UINT32_MAX << n, n); + + /* Check a random value in the middle. */ + check_ctz((random_uint32() | 1) << n, n); + } + + /* Check ctz(0). */ + check_ctz(0, 32); +} + +/* Returns a random number in the range 'min'...'max' inclusive. */ +static uint32_t +random_in_range(uint32_t min, uint32_t max) +{ + return min == max ? min : min + random_range(max - min + 1); +} + +static void +check_rup2(uint32_t x, int n) +{ + uint32_t rup2 = ROUND_UP_POW2(x); + if (rup2 != n) { + fprintf(stderr, "ROUND_UP_POW2(%#"PRIx32") is %#"PRIx32" " + "but should be %#"PRIx32"\n", x, rup2, n); + abort(); + } +} + +static void +test_round_up_pow2(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + int n; + + for (n = 0; n < 32; n++) { + /* Min, max value for which ROUND_UP_POW2 should yield (1 << n). */ + uint32_t min = ((1u << n) >> 1) + 1; + uint32_t max = 1u << n; + + check_rup2(min, 1u << n); + check_rup2(max, 1u << n); + check_rup2(random_in_range(min, max), 1u << n); + } + check_rup2(0, 0); +} + +static void +check_rdp2(uint32_t x, int n) +{ + uint32_t rdp2 = ROUND_DOWN_POW2(x); + if (rdp2 != n) { + fprintf(stderr, "ROUND_DOWN_POW2(%#"PRIx32") is %#"PRIx32" " + "but should be %#"PRIx32"\n", x, rdp2, n); + abort(); + } +} + +static void +test_round_down_pow2(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + int n; + + for (n = 0; n < 32; n++) { + /* Min, max value for which ROUND_DOWN_POW2 should yield (1 << n). */ + uint32_t min = 1u << n; + uint32_t max = ((1u << n) << 1) - 1; + + check_rdp2(min, 1u << n); + check_rdp2(max, 1u << n); + check_rdp2(random_in_range(min, max), 1u << n); + } + check_rdp2(0, 0); +} + +static void +shuffle(unsigned int *p, size_t n) +{ + for (; n > 1; n--, p++) { + unsigned int *q = &p[random_range(n)]; + unsigned int tmp = *p; + *p = *q; + *q = tmp; + } +} + +static void +check_popcount(uint32_t x, int n) +{ + if (popcount(x) != n) { + fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n", + x, popcount(x), n); + abort(); + } +} + +static void +test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + unsigned int bits[32]; + int i; + + for (i = 0; i < ARRAY_SIZE(bits); i++) { + bits[i] = 1u << i; + } + + check_popcount(0, 0); + + for (i = 0; i < 1000; i++) { + uint32_t x = 0; + int j; + + shuffle(bits, ARRAY_SIZE(bits)); + for (j = 0; j < 32; j++) { + x |= bits[j]; + check_popcount(x, j + 1); + } + assert(x == UINT32_MAX); + + shuffle(bits, ARRAY_SIZE(bits)); + for (j = 31; j >= 0; j--) { + x &= ~bits[j]; + check_popcount(x, j); + } + assert(x == 0); + } +} + /* Returns the sum of the squares of the first 'n' positive integers. */ static unsigned int sum_of_squares(int n) @@ -53,7 +214,7 @@ sum_of_squares(int n) } static void -check_bitwise_copy(void) +test_bitwise_copy(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) { unsigned int n_loops; int src_ofs; @@ -102,30 +263,201 @@ check_bitwise_copy(void) } } -int -main(void) +static void +test_bitwise_zero(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) { - int n; + unsigned int n_loops; + int dst_ofs; + int n_bits; - for (n = 0; n < 32; n++) { - /* Check minimum x such that f(x) == n. */ - check_log_2_floor(1 << n, n); - check_ctz(1 << n, n); + n_loops = 0; + for (n_bits = 0; n_bits <= 64; n_bits++) { + for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) { + ovs_be64 dst = htonll(random_uint64()); + ovs_be64 orig_dst = dst; + ovs_be64 expect; - /* Check maximum x such that f(x) == n. */ - check_log_2_floor((1 << n) | ((1 << n) - 1), n); - check_ctz(UINT32_MAX << n, n); + if (n_bits == 64) { + expect = htonll(0); + } else { + uint64_t mask = (UINT64_C(1) << n_bits) - 1; + expect = orig_dst & ~htonll(mask << dst_ofs); + } - /* Check a random value in the middle. */ - check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n); - check_ctz((random_uint32() | 1) << n, n); + bitwise_zero(&dst, sizeof dst, dst_ofs, n_bits); + if (expect != dst) { + fprintf(stderr,"bitwise_zero(0x%016"PRIx64",8,%d, %d) " + "yielded 0x%016"PRIx64" " + "instead of the expected 0x%016"PRIx64"\n", + ntohll(orig_dst), dst_ofs, + n_bits, + ntohll(dst), ntohll(expect)); + abort(); + } + + n_loops++; + } } - /* Check ctz(0). - * (log_2_floor(0) is undefined.) */ - check_ctz(0, 32); + if (n_loops != 64 * (64 + 1) / 2) { + abort(); + } +} + +static void +test_bitwise_one(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + unsigned int n_loops; + int dst_ofs; + int n_bits; - check_bitwise_copy(); + n_loops = 0; + for (n_bits = 0; n_bits <= 64; n_bits++) { + for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) { + ovs_be64 dst = htonll(random_uint64()); + ovs_be64 orig_dst = dst; + ovs_be64 expect; + + if (n_bits == 64) { + expect = htonll(UINT64_MAX); + } else { + uint64_t mask = (UINT64_C(1) << n_bits) - 1; + expect = orig_dst | htonll(mask << dst_ofs); + } + + bitwise_one(&dst, sizeof dst, dst_ofs, n_bits); + if (expect != dst) { + fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) " + "yielded 0x%016"PRIx64" " + "instead of the expected 0x%016"PRIx64"\n", + ntohll(orig_dst), dst_ofs, + n_bits, + ntohll(dst), ntohll(expect)); + abort(); + } + n_loops++; + } + } + + if (n_loops != 64 * (64 + 1) / 2) { + abort(); + } +} + +static void +test_bitwise_is_all_zeros(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + int n_loops; + + for (n_loops = 0; n_loops < 100; n_loops++) { + ovs_be64 x = htonll(0); + int i; + + for (i = 0; i < 64; i++) { + ovs_be64 bit; + int ofs, n; + + /* Change a random 0-bit into a 1-bit. */ + do { + bit = htonll(UINT64_C(1) << (random_range(64))); + } while (x & bit); + x |= bit; + + for (ofs = 0; ofs < 64; ofs++) { + for (n = 0; n <= 64 - ofs; n++) { + bool expect; + bool answer; + + expect = (n == 64 + ? x == 0 + : !(x & htonll(((UINT64_C(1) << n) - 1) + << ofs))); + answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n); + if (expect != answer) { + fprintf(stderr, + "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d " + "returned %s instead of %s\n", + ntohll(x), ofs, n, + answer ? "true" : "false", + expect ? "true" : "false"); + abort(); + } + } + } + } + } +} + +static void +test_follow_symlinks(int argc, char *argv[]) +{ + int i; + + for (i = 1; i < argc; i++) { + char *target = follow_symlinks(argv[i]); + puts(target); + free(target); + } +} + +static void +test_assert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + ovs_assert(false); +} + +static const struct command commands[] = { + {"ctz", 0, 0, test_ctz}, + {"round_up_pow2", 0, 0, test_round_up_pow2}, + {"round_down_pow2", 0, 0, test_round_down_pow2}, + {"popcount", 0, 0, test_popcount}, + {"log_2_floor", 0, 0, test_log_2_floor}, + {"bitwise_copy", 0, 0, test_bitwise_copy}, + {"bitwise_zero", 0, 0, test_bitwise_zero}, + {"bitwise_one", 0, 0, test_bitwise_one}, + {"bitwise_is_all_zeros", 0, 0, test_bitwise_is_all_zeros}, + {"follow-symlinks", 1, INT_MAX, test_follow_symlinks}, + {"assert", 0, 0, test_assert}, + {NULL, 0, 0, NULL}, +}; + +static void +parse_options(int argc, char *argv[]) +{ + enum { + VLOG_OPTION_ENUMS + }; + static const struct option long_options[] = { + VLOG_LONG_OPTIONS, + {NULL, 0, NULL, 0}, + }; + char *short_options = long_options_to_short_options(long_options); + + for (;;) { + int c = getopt_long(argc, argv, short_options, long_options, NULL); + if (c == -1) { + break; + } + + switch (c) { + VLOG_OPTION_HANDLERS + + case '?': + exit(EXIT_FAILURE); + + default: + abort(); + } + } + free(short_options); +} + +int +main(int argc, char *argv[]) +{ + set_program_name(argv[0]); + parse_options(argc, argv); + run_command(argc - optind, argv + optind, commands); return 0; }