[ovs-dev] [bundle 4/7] util: New function log_2_floor().

[Ben Pfaff]

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 <ethan at nicira.com>
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