[PATCH] LOG2: Implement a general integer log2 facility in the kernel
This facility provides three entry points:
ilog2() Log base 2 of unsigned long
ilog2_u32() Log base 2 of u32
ilog2_u64() Log base 2 of u64
These facilities can either be used inside functions on dynamic data:
int do_something(long q)
{
...;
y = ilog2(x)
...;
}
Or can be used to statically initialise global variables with constant values:
unsigned n = ilog2(27);
When performing static initialisation, the compiler will report "error:
initializer element is not constant" if asked to take a log of zero or of
something not reducible to a constant. They treat negative numbers as
unsigned.
When not dealing with a constant, they fall back to using fls() which permits
them to use arch-specific log calculation instructions - such as BSR on
x86/x86_64 or SCAN on FRV - if available.
[akpm@osdl.org: MMC fix]
Signed-off-by: David Howells <dhowells@redhat.com>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: David Howells <dhowells@redhat.com>
Cc: Wojtek Kaniewski <wojtekka@toxygen.net>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 1f70d47..f8560ed 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -256,6 +256,50 @@
return 31 - bit;
}
+/*
+ * special slimline version of fls() for calculating ilog2_u32()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+ int bit;
+ asm("scan %1,gr0,%0" : "=r"(bit) : "r"(n));
+ return 31 - bit;
+}
+
+/*
+ * special slimline version of fls64() for calculating ilog2_u64()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_ILOG2_U64
+static inline __attribute__((const))
+int __ilog2_u64(u64 n)
+{
+ union {
+ u64 ll;
+ struct { u32 h, l; };
+ } _;
+ int bit, x, y;
+
+ _.ll = n;
+
+ asm(" subcc %3,gr0,gr0,icc0 \n"
+ " ckeq icc0,cc4 \n"
+ " cscan.p %3,gr0,%0 ,cc4,0 \n"
+ " setlos #63,%1 \n"
+ " cscan.p %4,gr0,%0 ,cc4,1 \n"
+ " setlos #31,%2 \n"
+ " csub.p %1,%0,%0 ,cc4,0 \n"
+ " csub %2,%0,%0 ,cc4,1 \n"
+ : "=&r"(bit), "=r"(x), "=r"(y)
+ : "0r"(_.h), "r"(_.l)
+ : "icc0", "cc4"
+ );
+ return bit;
+}
+
#include <asm-generic/bitops/sched.h>
#include <asm-generic/bitops/hweight.h>