diff options
| -rw-r--r-- | lib/util.c | 35 | ||||
| -rw-r--r-- | lib/util.h | 1 | ||||
| -rw-r--r-- | tests/automake.mk | 4 | ||||
| -rw-r--r-- | tests/library.at | 4 | ||||
| -rw-r--r-- | tests/test-util.c | 52 |
5 files changed, 96 insertions, 0 deletions
@@ -16,8 +16,11 @@ #include <config.h> #include "util.h" +#include <assert.h> #include <errno.h> +#include <limits.h> #include <stdarg.h> +#include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -607,3 +610,35 @@ english_list_delimiter(size_t index, size_t total) : total > 2 ? ", and " : " and "); } + +/* Given a 32 bit word 'n', calculates floor(log_2('n')). This is equivalent + * to finding the bit position of the most significant one bit in 'n'. It is + * an error to call this function with 'n' == 0. */ +int +log_2_floor(uint32_t n) +{ + assert(n); + +#if !defined(UINT_MAX) || !defined(UINT32_MAX) +#error "Someone screwed up the #includes." +#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX + return 31 - __builtin_clz(n); +#else + { + int log = 0; + +#define BIN_SEARCH_STEP(BITS) \ + if (n >= (1 << BITS)) { \ + log += BITS; \ + n >>= BITS; \ + } + BIN_SEARCH_STEP(16); + BIN_SEARCH_STEP(8); + BIN_SEARCH_STEP(4); + BIN_SEARCH_STEP(2); + BIN_SEARCH_STEP(1); +#undef BIN_SEARCH_STEP + return log; + } +#endif +} @@ -194,6 +194,7 @@ char *base_name(const char *file_name); char *abs_file_name(const char *dir, const char *file_name); void ignore(bool x OVS_UNUSED); +int log_2_floor(uint32_t n); #ifdef __cplusplus } diff --git a/tests/automake.mk b/tests/automake.mk index be09b4a6..33307ccc 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -297,6 +297,10 @@ tests_test_strtok_r_SOURCES = tests/test-strtok_r.c noinst_PROGRAMS += tests/test-type-props tests_test_type_props_SOURCES = tests/test-type-props.c +noinst_PROGRAMS += tests/test-util +tests_test_util_SOURCES = tests/test-util.c +tests_test_util_LDADD = lib/libopenvswitch.a + noinst_PROGRAMS += tests/test-uuid tests_test_uuid_SOURCES = tests/test-uuid.c tests_test_uuid_LDADD = lib/libopenvswitch.a diff --git a/tests/library.at b/tests/library.at index ec50e23a..ca5f29ca 100644 --- a/tests/library.at +++ b/tests/library.at @@ -100,6 +100,10 @@ nibble 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ]) AT_CLEANUP +AT_SETUP([test log_2_floor]) +AT_CHECK([test-util]) +AT_CLEANUP + AT_SETUP([test unix socket -- short pathname]) AT_CHECK([test-unix-socket x]) AT_CLEANUP diff --git a/tests/test-util.c b/tests/test-util.c new file mode 100644 index 00000000..e9a827a4 --- /dev/null +++ b/tests/test-util.c @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2011 Nicira Networks. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <config.h> + +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> + +#include "random.h" +#include "util.h" + +static void +check(uint32_t x, int n) +{ + if (log_2_floor(x) != n) { + fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n", + x, log_2_floor(x), n); + abort(); + } +} + +int +main(void) +{ + int n; + + for (n = 0; n < 32; n++) { + /* Check minimum x that has log2(x) == n. */ + check(1 << n, n); + + /* Check maximum x that has log2(x) == n. */ + check((1 << n) | ((1 << n) - 1), n); + + /* Check a random value in the middle. */ + check((random_uint32() & ((1 << n) - 1)) | (1 << n), n); + } + return 0; +} |