From f0d1b0b30d250a07627ad8b9fbbb5c7cc08422e8 Mon Sep 17 00:00:00 2001 From: David Howells Date: Fri, 8 Dec 2006 02:37:49 -0800 Subject: [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 Cc: Benjamin Herrenschmidt Cc: Paul Mackerras Cc: Herbert Xu Cc: David Howells Cc: Wojtek Kaniewski Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- arch/alpha/Kconfig | 8 ++++++++ arch/arm/Kconfig | 8 ++++++++ arch/arm26/Kconfig | 8 ++++++++ arch/avr32/Kconfig | 8 ++++++++ arch/cris/Kconfig | 8 ++++++++ arch/frv/Kconfig | 8 ++++++++ arch/h8300/Kconfig | 8 ++++++++ arch/i386/Kconfig.cpu | 8 ++++++++ arch/ia64/Kconfig | 8 ++++++++ arch/m32r/Kconfig | 8 ++++++++ arch/m68k/Kconfig | 8 ++++++++ arch/m68knommu/Kconfig | 8 ++++++++ arch/mips/Kconfig | 8 ++++++++ arch/parisc/Kconfig | 8 ++++++++ arch/powerpc/Kconfig | 8 ++++++++ arch/ppc/Kconfig | 8 ++++++++ arch/s390/Kconfig | 8 ++++++++ arch/sh/Kconfig | 8 ++++++++ arch/sh64/Kconfig | 8 ++++++++ arch/sparc/Kconfig | 8 ++++++++ arch/sparc64/Kconfig | 8 ++++++++ arch/v850/Kconfig | 8 ++++++++ arch/x86_64/Kconfig | 8 ++++++++ arch/xtensa/Kconfig | 8 ++++++++ 24 files changed, 192 insertions(+) (limited to 'arch') diff --git a/arch/alpha/Kconfig b/arch/alpha/Kconfig index 7e55ea66c6d..84caf50725b 100644 --- a/arch/alpha/Kconfig +++ b/arch/alpha/Kconfig @@ -25,6 +25,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 8c05d4321ae..aa1d400d721 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -74,6 +74,14 @@ config RWSEM_GENERIC_SPINLOCK 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 c14fe918bc4..74eba8b5a8c 100644 --- a/arch/arm26/Kconfig +++ b/arch/arm26/Kconfig @@ -41,6 +41,14 @@ config RWSEM_GENERIC_SPINLOCK 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 5f1694eea84..bb059a4e1df 100644 --- a/arch/avr32/Kconfig +++ b/arch/avr32/Kconfig @@ -45,6 +45,14 @@ config GENERIC_TIME 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 6a1238a29d6..3474309e049 100644 --- a/arch/cris/Kconfig +++ b/arch/cris/Kconfig @@ -16,6 +16,14 @@ config RWSEM_GENERIC_SPINLOCK 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 cf1c446e003..7561d7b72e7 100644 --- a/arch/frv/Kconfig +++ b/arch/frv/Kconfig @@ -41,6 +41,14 @@ config TIME_LOW_RES 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 cabf0bfffc5..34a84bc4baf 100644 --- a/arch/h8300/Kconfig +++ b/arch/h8300/Kconfig @@ -29,6 +29,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 821fd269ca5..2aecfba4ac4 100644 --- a/arch/i386/Kconfig.cpu +++ b/arch/i386/Kconfig.cpu @@ -248,6 +248,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 75d839715b2..fcacfe291b9 100644 --- a/arch/ia64/Kconfig +++ b/arch/ia64/Kconfig @@ -34,6 +34,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 41fd490af3b..f383dab973f 100644 --- a/arch/m32r/Kconfig +++ b/arch/m32r/Kconfig @@ -214,6 +214,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 7bc14461a6a..70a577c89c7 100644 --- a/arch/m68k/Kconfig +++ b/arch/m68k/Kconfig @@ -17,6 +17,14 @@ config RWSEM_GENERIC_SPINLOCK 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 aa70dde5422..25993c2a8fb 100644 --- a/arch/m68knommu/Kconfig +++ b/arch/m68knommu/Kconfig @@ -25,6 +25,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 d8af858fe3f..57af8d8cf46 100644 --- a/arch/mips/Kconfig +++ b/arch/mips/Kconfig @@ -819,6 +819,14 @@ config RWSEM_GENERIC_SPINLOCK 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 d2101237442..0f9ff618c6d 100644 --- a/arch/parisc/Kconfig +++ b/arch/parisc/Kconfig @@ -25,6 +25,14 @@ config RWSEM_GENERIC_SPINLOCK 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 291c95ac4b3..97c7a212cdd 100644 --- a/arch/powerpc/Kconfig +++ b/arch/powerpc/Kconfig @@ -41,6 +41,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 f76a146cff1..692b5ba5320 100644 --- a/arch/ppc/Kconfig +++ b/arch/ppc/Kconfig @@ -19,6 +19,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 583d9ff0a57..45e47bfb68a 100644 --- a/arch/s390/Kconfig +++ b/arch/s390/Kconfig @@ -22,6 +22,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 d83d64af31f..8e24c40662e 100644 --- a/arch/sh/Kconfig +++ b/arch/sh/Kconfig @@ -59,6 +59,14 @@ config LOCKDEP_SUPPORT 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 58c678e0666..7bc0744b7ab 100644 --- a/arch/sh64/Kconfig +++ b/arch/sh64/Kconfig @@ -39,6 +39,14 @@ config RWSEM_XCHGADD_ALGORITHM 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 92a7c8a636d..d0dec1ea2ee 100644 --- a/arch/sparc/Kconfig +++ b/arch/sparc/Kconfig @@ -166,6 +166,14 @@ config ARCH_MAY_HAVE_PC_FDC 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 b627f8dbcaa..d391d11f245 100644 --- a/arch/sparc64/Kconfig +++ b/arch/sparc64/Kconfig @@ -34,6 +34,14 @@ config ARCH_MAY_HAVE_PC_FDC 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 37ec644603a..bcf825875d1 100644 --- a/arch/v850/Kconfig +++ b/arch/v850/Kconfig @@ -38,6 +38,14 @@ config TIME_LOW_RES 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 3254a616c69..3ac581d1720 100644 --- a/arch/x86_64/Kconfig +++ b/arch/x86_64/Kconfig @@ -101,6 +101,14 @@ config GENERIC_BUG 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 c1e69a1f92a..9eccfbd1b53 100644 --- a/arch/xtensa/Kconfig +++ b/arch/xtensa/Kconfig @@ -34,6 +34,14 @@ config GENERIC_HARDIRQS 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" -- cgit v1.2.3