Sounds good, I pulled your patch into the series as a replacement for mine.
Ethan On Fri, Jul 22, 2011 at 10:25, Ben Pfaff <[email protected]> wrote: > 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
