Use builtin_clz log2 for x86 architectures.
authorGodfrey van der Linden <gvdl@google.com>
Thu, 15 Jan 2015 18:42:34 +0000 (10:42 -0800)
committerGodfrey van der Linden <gvdl@google.com>
Tue, 20 Jan 2015 16:09:25 +0000 (08:09 -0800)
Also fix LOG2_UP which would fail if n > 2^32.  (1 << (uintptr_t) 33) ==
0 unfortunately, the << operator does not promote the one to uint64_t.

Then I booted the kernel using both old and new versions and paniced if
they didn't agree. This code has also been tested using a clang compiler
on x86_64 using the following loop in a standalone app.

for (i = 0; i < 64; i++) {
uintptr_t v = (uintptr_t) 1 << i;
assert(new_log2_up(v) == old_log2_up(v));
assert(new_log2_up(v-1) == old_log2_up(v-1));
assert(new_log2_up(v+1) == old_log2_up(v+1));
assert(new_log2_down(v) == old_log2_down(v));
assert(new_log2_down(v-1) == old_log2_down(v-1));
assert(new_log2_down(v+1) == old_log2_down(v+1));
}

kern/include/ros/common.h

index af460a5..ce6d7b7 100644 (file)
@@ -107,22 +107,34 @@ typedef unsigned long uintreg_t;
 })
 
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
+
 // Return the integer logarithm of the value provided rounded down
+#if __x86_64__ || __i386__
+// Should be __has_builtin(__builtin_clz) but gcc doesn't support it
+// x86 compiler intrinsic supported by both > gcc4.6 and LLVM > 1.5
+static inline uintptr_t LOG2_DOWN(uintptr_t value)
+{
+       value |= 1;
+       return (sizeof(value) == 8) ? 63 - __builtin_clzll(value)
+                                   : 31 - __builtin_clz(value);
+}
+#else
+// TODO(gvdl): Does the gcc on riscv support __builtin_clz?
+#warning "Using loop based LOG2_DOWN, no __builtin_clz?"
 static inline uintptr_t LOG2_DOWN(uintptr_t value)
 {
        uintptr_t l = 0;
        while( (value >> l) > 1 ) ++l;
        return l;
 }
+#endif
 
 // Return the integer logarithm of the value provided rounded up
 static inline uintptr_t LOG2_UP(uintptr_t value)
 {
-       uintptr_t _v = LOG2_DOWN(value);
-       if (value ^ (1 << _v))
-               return _v + 1;
-       else
-               return _v;
+       uintptr_t ret = LOG2_DOWN(value);
+       ret += 0 != (value ^ ((uintptr_t) 1 << ret));  // Add 1 if a lower bit set
+       return ret;
 }
 
 static inline uintptr_t ROUNDUPPWR2(uintptr_t value)