[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>

1 files changed, 44 insertions, 0 deletions

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 1f70d47148bd..f8560edf59ff 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -256,6 +256,50 @@ int __ffs(unsigned long x)
         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>