X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Futil.c;h=cd4019eb7c4059f0d5f027834fa30461a51ae9dd;hb=4816a18f33380a33d381b77d41df39113c94500d;hp=cd99142c16effa07316e5bc1f9f9c25d7a14b17c;hpb=e368cad8ecf6dbf272b2a3775b2e3e5e2dc6a5cf;p=sliver-openvswitch.git

diff --git a/lib/util.c b/lib/util.c
index cd99142c1..cd4019eb7 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -16,7 +16,6 @@
 
 #include <config.h>
 #include "util.h"
-#include <assert.h>
 #include <errno.h>
 #include <limits.h>
 #include <stdarg.h>
@@ -45,6 +44,30 @@ const char *subprogram_name = "";
 /* --version option output. */
 static char *program_version;
 
+void
+ovs_assert_failure(const char *where, const char *function,
+                   const char *condition)
+{
+    /* Prevent an infinite loop (or stack overflow) in case VLOG_ABORT happens
+     * to trigger an assertion failure of its own. */
+    static int reentry = 0;
+
+    switch (reentry++) {
+    case 0:
+        VLOG_ABORT("%s: assertion %s failed in %s()",
+                   where, condition, function);
+        NOT_REACHED();
+
+    case 1:
+        fprintf(stderr, "%s: assertion %s failed in %s()",
+                where, condition, function);
+        abort();
+
+    default:
+        abort();
+    }
+}
+
 void
 out_of_memory(void)
 {
@@ -756,7 +779,7 @@ english_list_delimiter(size_t index, size_t total)
 int
 log_2_floor(uint32_t n)
 {
-    assert(n);
+    ovs_assert(n);
 
 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 #error "Someone screwed up the #includes."
@@ -787,40 +810,70 @@ log_2_floor(uint32_t n)
 int
 log_2_ceil(uint32_t n)
 {
-    return log_2_floor(n) + !IS_POW2(n);
+    return log_2_floor(n) + !is_pow2(n);
 }
 
-/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
-int
-ctz(uint32_t n)
-{
-    if (!n) {
-        return 32;
-    } else {
+/* Returns the number of trailing 0-bits in 'n'.  Undefined if 'n' == 0. */
 #if !defined(UINT_MAX) || !defined(UINT32_MAX)
 #error "Someone screwed up the #includes."
 #elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
-        return __builtin_ctz(n);
+/* Defined inline in util.h. */
 #else
-        unsigned int k;
-        int count = 31;
+static int
+raw_ctz(uint32_t n)
+{
+    unsigned int k;
+    int count = 31;
 
 #define CTZ_STEP(X)                             \
-        k = n << (X);                           \
-        if (k) {                                \
-            count -= X;                         \
-            n = k;                              \
-        }
-        CTZ_STEP(16);
-        CTZ_STEP(8);
-        CTZ_STEP(4);
-        CTZ_STEP(2);
-        CTZ_STEP(1);
+    k = n << (X);                               \
+    if (k) {                                    \
+        count -= X;                             \
+        n = k;                                  \
+    }
+    CTZ_STEP(16);
+    CTZ_STEP(8);
+    CTZ_STEP(4);
+    CTZ_STEP(2);
+    CTZ_STEP(1);
 #undef CTZ_STEP
 
-        return count;
+    return count;
+}
 #endif
-    }
+
+/* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */
+unsigned int
+popcount(uint32_t x)
+{
+    /* In my testing, this implementation is over twice as fast as any other
+     * portable implementation that I tried, including GCC 4.4
+     * __builtin_popcount(), although nonportable asm("popcnt") was over 50%
+     * faster. */
+#define INIT1(X)                                \
+    ((((X) & (1 << 0)) != 0) +                  \
+     (((X) & (1 << 1)) != 0) +                  \
+     (((X) & (1 << 2)) != 0) +                  \
+     (((X) & (1 << 3)) != 0) +                  \
+     (((X) & (1 << 4)) != 0) +                  \
+     (((X) & (1 << 5)) != 0) +                  \
+     (((X) & (1 << 6)) != 0) +                  \
+     (((X) & (1 << 7)) != 0))
+#define INIT2(X)   INIT1(X),  INIT1((X) +  1)
+#define INIT4(X)   INIT2(X),  INIT2((X) +  2)
+#define INIT8(X)   INIT4(X),  INIT4((X) +  4)
+#define INIT16(X)  INIT8(X),  INIT8((X) +  8)
+#define INIT32(X) INIT16(X), INIT16((X) + 16)
+#define INIT64(X) INIT32(X), INIT32((X) + 32)
+
+    static const uint8_t popcount8[256] = {
+        INIT64(0), INIT64(64), INIT64(128), INIT64(192)
+    };
+
+    return (popcount8[x & 0xff] +
+            popcount8[(x >> 8) & 0xff] +
+            popcount8[(x >> 16) & 0xff] +
+            popcount8[x >> 24]);
 }
 
 /* Returns true if the 'n' bytes starting at 'p' are zeros. */