On Thu, Jul 21, 2011 at 03:58:52PM -0700, Ethan Jackson wrote: > Calculates the position of the most significant bit in a 32 bit > word.
I see that you've been reading _Hacker's Delight_. This solution is unnecessarily slow on common machines (like 80x86) that can calculate log_2_floor() in one or two instructions. Here's a version that's faster. I changed the return type from "size_t" to "int" because the result is going to be in the range of int and doesn't represent a size in bytes or an array dimension. It also adds a test. What do you think? --8<--------------------------cut here-------------------------->8-- From: Ethan Jackson <[email protected]> Date: Fri, 22 Jul 2011 10:20:52 -0700 Subject: [PATCH] util: New function log_2_floor(). Calculates the position of the most significant bit in a 32 bit word. --- lib/util.c | 35 +++++++++++++++++++++++++++++++++++ lib/util.h | 1 + tests/automake.mk | 4 ++++ tests/library.at | 4 ++++ tests/test-util.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 96 insertions(+), 0 deletions(-) create mode 100644 tests/test-util.c diff --git a/lib/util.c b/lib/util.c index 1a42376..639424d 100644 --- a/lib/util.c +++ b/lib/util.c @@ -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 +} diff --git a/lib/util.h b/lib/util.h index 7615288..601f49f 100644 --- a/lib/util.h +++ b/lib/util.h @@ -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 be09b4a..33307cc 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 ec50e23..ca5f29c 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 0000000..e9a827a --- /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; +} -- 1.7.2.5 _______________________________________________ dev mailing list [email protected] http://openvswitch.org/mailman/listinfo/dev
