[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/arch/alpha/Kconfig b/arch/alpha/Kconfig
index 7e55ea6..84caf50 100644
--- a/arch/alpha/Kconfig
+++ b/arch/alpha/Kconfig
@@ -25,6 +25,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index 8c05d43..aa1d400 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -74,6 +74,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/arm26/Kconfig b/arch/arm26/Kconfig
index c14fe91..74eba8b 100644
--- a/arch/arm26/Kconfig
+++ b/arch/arm26/Kconfig
@@ -41,6 +41,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/avr32/Kconfig b/arch/avr32/Kconfig
index 5f1694e..bb059a4 100644
--- a/arch/avr32/Kconfig
+++ b/arch/avr32/Kconfig
@@ -45,6 +45,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_BUST_SPINLOCK
bool
diff --git a/arch/cris/Kconfig b/arch/cris/Kconfig
index 6a1238a..3474309 100644
--- a/arch/cris/Kconfig
+++ b/arch/cris/Kconfig
@@ -16,6 +16,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/frv/Kconfig b/arch/frv/Kconfig
index cf1c446..7561d7b 100644
--- a/arch/frv/Kconfig
+++ b/arch/frv/Kconfig
@@ -41,6 +41,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default y
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default y
+
mainmenu "Fujitsu FR-V Kernel Configuration"
source "init/Kconfig"
diff --git a/arch/h8300/Kconfig b/arch/h8300/Kconfig
index cabf0bf..34a84bc 100644
--- a/arch/h8300/Kconfig
+++ b/arch/h8300/Kconfig
@@ -29,6 +29,14 @@
bool
default n
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/i386/Kconfig.cpu b/arch/i386/Kconfig.cpu
index 821fd26..2aecfba 100644
--- a/arch/i386/Kconfig.cpu
+++ b/arch/i386/Kconfig.cpu
@@ -248,6 +248,14 @@
depends on !M386
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_CALIBRATE_DELAY
bool
default y
diff --git a/arch/ia64/Kconfig b/arch/ia64/Kconfig
index 75d8397..fcacfe2 100644
--- a/arch/ia64/Kconfig
+++ b/arch/ia64/Kconfig
@@ -34,6 +34,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/m32r/Kconfig b/arch/m32r/Kconfig
index 41fd490..f383dab 100644
--- a/arch/m32r/Kconfig
+++ b/arch/m32r/Kconfig
@@ -214,6 +214,14 @@
bool
default n
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
index 7bc1446..70a577c 100644
--- a/arch/m68k/Kconfig
+++ b/arch/m68k/Kconfig
@@ -17,6 +17,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/m68knommu/Kconfig b/arch/m68knommu/Kconfig
index aa70dde..25993c2 100644
--- a/arch/m68knommu/Kconfig
+++ b/arch/m68knommu/Kconfig
@@ -25,6 +25,14 @@
bool
default n
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/mips/Kconfig b/arch/mips/Kconfig
index d8af858f..57af8d8 100644
--- a/arch/mips/Kconfig
+++ b/arch/mips/Kconfig
@@ -819,6 +819,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/parisc/Kconfig b/arch/parisc/Kconfig
index d210123..0f9ff61 100644
--- a/arch/parisc/Kconfig
+++ b/arch/parisc/Kconfig
@@ -25,6 +25,14 @@
config RWSEM_XCHGADD_ALGORITHM
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_FIND_NEXT_BIT
bool
default y
diff --git a/arch/powerpc/Kconfig b/arch/powerpc/Kconfig
index 291c95a..97c7a21 100644
--- a/arch/powerpc/Kconfig
+++ b/arch/powerpc/Kconfig
@@ -41,6 +41,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/ppc/Kconfig b/arch/ppc/Kconfig
index f76a146..692b5ba 100644
--- a/arch/ppc/Kconfig
+++ b/arch/ppc/Kconfig
@@ -19,6 +19,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default y
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index 583d9ff..45e47bf 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig
@@ -22,6 +22,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config GENERIC_HWEIGHT
bool
default y
diff --git a/arch/sh/Kconfig b/arch/sh/Kconfig
index d83d64a..8e24c40 100644
--- a/arch/sh/Kconfig
+++ b/arch/sh/Kconfig
@@ -59,6 +59,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
source "init/Kconfig"
menu "System type"
diff --git a/arch/sh64/Kconfig b/arch/sh64/Kconfig
index 58c678e..7bc0744 100644
--- a/arch/sh64/Kconfig
+++ b/arch/sh64/Kconfig
@@ -39,6 +39,14 @@
config GENERIC_ISA_DMA
bool
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
source init/Kconfig
menu "System type"
diff --git a/arch/sparc/Kconfig b/arch/sparc/Kconfig
index 92a7c8a..d0dec1e 100644
--- a/arch/sparc/Kconfig
+++ b/arch/sparc/Kconfig
@@ -166,6 +166,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config SUN_PM
bool
default y
diff --git a/arch/sparc64/Kconfig b/arch/sparc64/Kconfig
index b627f8d..d391d11 100644
--- a/arch/sparc64/Kconfig
+++ b/arch/sparc64/Kconfig
@@ -34,6 +34,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
config AUDIT_ARCH
bool
default y
diff --git a/arch/v850/Kconfig b/arch/v850/Kconfig
index 37ec644..bcf8258 100644
--- a/arch/v850/Kconfig
+++ b/arch/v850/Kconfig
@@ -38,6 +38,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
# Turn off some random 386 crap that can affect device config
config ISA
bool
diff --git a/arch/x86_64/Kconfig b/arch/x86_64/Kconfig
index 3254a61..3ac581d 100644
--- a/arch/x86_64/Kconfig
+++ b/arch/x86_64/Kconfig
@@ -101,6 +101,14 @@
default y
depends on BUG
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
source "init/Kconfig"
diff --git a/arch/xtensa/Kconfig b/arch/xtensa/Kconfig
index c1e69a1..9eccfbd 100644
--- a/arch/xtensa/Kconfig
+++ b/arch/xtensa/Kconfig
@@ -34,6 +34,14 @@
bool
default y
+config ARCH_HAS_ILOG2_U32
+ bool
+ default n
+
+config ARCH_HAS_ILOG2_U64
+ bool
+ default n
+
source "init/Kconfig"
menu "Processor type and features"