Calculates the position of the most significant bit in a 32 bit
word.
---
lib/util.c | 25 +++++++++++++++++++++++++
lib/util.h | 1 +
2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/lib/util.c b/lib/util.c
index 1a42376..b3455eb 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -16,6 +16,7 @@
#include <config.h>
#include "util.h"
+#include <assert.h>
#include <errno.h>
#include <stdarg.h>
#include <stdio.h>
@@ -607,3 +608,27 @@ 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. */
+size_t
+log_2_floor(uint32_t n)
+{
+ size_t log = 0;
+
+ assert(n);
+
+#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;
+}
diff --git a/lib/util.h b/lib/util.h
index 7615288..f688df9 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);
+size_t log_2_floor(uint32_t n);
#ifdef __cplusplus
}
--
1.7.6
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
