[U-Boot] [PATCH v9 1/4] include: Add log2 and generic bitops header files

Fabio Estevam fabio.estevam at freescale.com
Tue Oct 20 15:03:26 CEST 2015


Use the log2 and generic bitops header files directly from the kernel.

Based on the headers froom kernel 4.2.3.

Signed-off-by: Fabio Estevam <fabio.estevam at freescale.com>
---
Changes since v8:
- Do not mix generic versus arch specific header (Jagan)
- Build tested on ARM, m68k, powerpc, bfin, microblaze, sh and x86

 arch/arm/include/asm/bitops.h        |  98 +++++++++++++++++
 arch/blackfin/include/asm/bitops.h   |   4 +
 arch/m68k/include/asm/bitops.h       |   4 +
 arch/microblaze/include/asm/bitops.h |   4 +
 arch/powerpc/cpu/mpc83xx/law.c       |   4 +-
 arch/powerpc/cpu/mpc85xx/tlb.c       |   2 +
 arch/powerpc/cpu/mpc8xxx/law.c       |   5 +-
 arch/powerpc/include/asm/bitops.h    |  43 +-------
 arch/sh/include/asm/bitops.h         |   5 +
 arch/x86/include/asm/bitops.h        |   6 +-
 drivers/pci/fsl_pci_init.c           |   1 +
 include/asm-generic/bitops/__ffs.h   |  43 ++++++++
 include/asm-generic/bitops/__fls.h   |  43 ++++++++
 include/asm-generic/bitops/ffs.h     |  41 +++++++
 include/asm-generic/bitops/fls.h     |  41 +++++++
 include/asm-generic/bitops/fls64.h   |  36 ++++++
 include/linux/bitops.h               |  26 +++++
 include/linux/log2.h                 | 205 +++++++++++++++++++++++++++++++++++
 18 files changed, 566 insertions(+), 45 deletions(-)
 create mode 100644 include/asm-generic/bitops/__ffs.h
 create mode 100644 include/asm-generic/bitops/__fls.h
 create mode 100644 include/asm-generic/bitops/ffs.h
 create mode 100644 include/asm-generic/bitops/fls.h
 create mode 100644 include/asm-generic/bitops/fls64.h
 create mode 100644 include/linux/log2.h

diff --git a/arch/arm/include/asm/bitops.h b/arch/arm/include/asm/bitops.h
index 9b78043..cbc07ae 100644
--- a/arch/arm/include/asm/bitops.h
+++ b/arch/arm/include/asm/bitops.h
@@ -190,4 +190,102 @@ found_middle:
 
 #endif /* __KERNEL__ */
 
+#if __LINUX_ARM_ARCH__ < 5
+
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/__ffs.h>
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/ffs.h>
+
+#else
+
+static inline int constant_fls(int x)
+{
+	int r = 32;
+
+	if (!x)
+		return 0;
+	if (!(x & 0xffff0000u)) {
+		x <<= 16;
+		r -= 16;
+	}
+	if (!(x & 0xff000000u)) {
+		x <<= 8;
+		r -= 8;
+	}
+	if (!(x & 0xf0000000u)) {
+		x <<= 4;
+		r -= 4;
+	}
+	if (!(x & 0xc0000000u)) {
+		x <<= 2;
+		r -= 2;
+	}
+	if (!(x & 0x80000000u)) {
+		x <<= 1;
+		r -= 1;
+	}
+	return r;
+}
+
+/*
+ * On ARMv5 and above those functions can be implemented around the
+ * clz instruction for much better code efficiency.  __clz returns
+ * the number of leading zeros, zero input will return 32, and
+ * 0x80000000 will return 0.
+ */
+static inline unsigned int __clz(unsigned int x)
+{
+	unsigned int ret;
+
+	asm("clz\t%0, %1" : "=r" (ret) : "r" (x));
+
+	return ret;
+}
+
+/*
+ * fls() returns zero if the input is zero, otherwise returns the bit
+ * position of the last set bit, where the LSB is 1 and MSB is 32.
+ */
+static inline int fls(int x)
+{
+	if (__builtin_constant_p(x))
+	       return constant_fls(x);
+
+	return 32 - __clz(x);
+}
+
+/*
+ * __fls() returns the bit position of the last bit set, where the
+ * LSB is 0 and MSB is 31.  Zero input is undefined.
+ */
+static inline unsigned long __fls(unsigned long x)
+{
+	return fls(x) - 1;
+}
+
+/*
+ * ffs() returns zero if the input was zero, otherwise returns the bit
+ * position of the first set bit, where the LSB is 1 and MSB is 32.
+ */
+static inline int ffs(int x)
+{
+	return fls(x & -x);
+}
+
+/*
+ * __ffs() returns the bit position of the first bit set, where the
+ * LSB is 0 and MSB is 31.  Zero input is undefined.
+ */
+static inline unsigned long __ffs(unsigned long x)
+{
+	return ffs(x) - 1;
+}
+
+#define ffz(x) __ffs( ~(x) )
+
+#endif
+
+#include <asm-generic/bitops/fls64.h>
+
 #endif /* _ARM_BITOPS_H */
diff --git a/arch/blackfin/include/asm/bitops.h b/arch/blackfin/include/asm/bitops.h
index cd7e356..6cde6db 100644
--- a/arch/blackfin/include/asm/bitops.h
+++ b/arch/blackfin/include/asm/bitops.h
@@ -15,6 +15,10 @@
 
 #include <asm/byteorder.h>
 #include <asm/system.h>
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/fls64.h>
+#include <asm-generic/bitops/__ffs.h>
 
 #ifdef __KERNEL__
 /*
diff --git a/arch/m68k/include/asm/bitops.h b/arch/m68k/include/asm/bitops.h
index f9c434b..69ea26a 100644
--- a/arch/m68k/include/asm/bitops.h
+++ b/arch/m68k/include/asm/bitops.h
@@ -6,6 +6,10 @@
 #define _M68K_BITOPS_H
 
 #include <asm/byteorder.h>
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/fls64.h>
+#include <asm-generic/bitops/__ffs.h>
 
 extern void set_bit(int nr, volatile void *addr);
 extern void clear_bit(int nr, volatile void *addr);
diff --git a/arch/microblaze/include/asm/bitops.h b/arch/microblaze/include/asm/bitops.h
index 0ac78d7..d24f2cf 100644
--- a/arch/microblaze/include/asm/bitops.h
+++ b/arch/microblaze/include/asm/bitops.h
@@ -7,6 +7,10 @@
 
 #include <asm/byteorder.h>	/* swab32 */
 #include <asm/system.h>		/* save_flags */
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/fls64.h>
+#include <asm-generic/bitops/__ffs.h>
 
 #ifdef __KERNEL__
 /*
diff --git a/arch/powerpc/cpu/mpc83xx/law.c b/arch/powerpc/cpu/mpc83xx/law.c
index 66c88b6..d8173f4 100644
--- a/arch/powerpc/cpu/mpc83xx/law.c
+++ b/arch/powerpc/cpu/mpc83xx/law.c
@@ -20,7 +20,7 @@ int set_ddr_laws(u64 start, u64 sz, enum law_trgt_if id)
 	if (start == 0)
 		start_align = 1ull << (LAW_SIZE_2G + 1);
 	else
-		start_align = 1ull << (ffs64(start) - 1);
+		start_align = 1ull << (__ffs64(start) - 1);
 	law_sz = min(start_align, sz);
 	law_sz_enc = __ilog2_u64(law_sz) - 1;
 
@@ -40,7 +40,7 @@ int set_ddr_laws(u64 start, u64 sz, enum law_trgt_if id)
 	if (sz) {
 		start += law_sz;
 
-		start_align = 1ull << (ffs64(start) - 1);
+		start_align = 1ull << (__ffs64(start) - 1);
 		law_sz = min(start_align, sz);
 		law_sz_enc = __ilog2_u64(law_sz) - 1;
 		ecm = &immap->sysconf.ddrlaw[1];
diff --git a/arch/powerpc/cpu/mpc85xx/tlb.c b/arch/powerpc/cpu/mpc85xx/tlb.c
index 8e0508f..cf31eb2 100644
--- a/arch/powerpc/cpu/mpc85xx/tlb.c
+++ b/arch/powerpc/cpu/mpc85xx/tlb.c
@@ -14,6 +14,8 @@
 #include <addr_map.h>
 #endif
 
+#include <linux/log2.h>
+
 DECLARE_GLOBAL_DATA_PTR;
 
 void invalidate_tlb(u8 tlb)
diff --git a/arch/powerpc/cpu/mpc8xxx/law.c b/arch/powerpc/cpu/mpc8xxx/law.c
index 33d53a8..24baad4 100644
--- a/arch/powerpc/cpu/mpc8xxx/law.c
+++ b/arch/powerpc/cpu/mpc8xxx/law.c
@@ -11,6 +11,7 @@
 #include <linux/compiler.h>
 #include <asm/fsl_law.h>
 #include <asm/io.h>
+#include <linux/log2.h>
 
 DECLARE_GLOBAL_DATA_PTR;
 
@@ -187,7 +188,7 @@ int set_ddr_laws(u64 start, u64 sz, enum law_trgt_if id)
 	if (start == 0)
 		start_align = 1ull << (LAW_SIZE_32G + 1);
 	else
-		start_align = 1ull << (ffs64(start) - 1);
+		start_align = 1ull << (__ffs64(start) - 1);
 	law_sz = min(start_align, sz);
 	law_sz_enc = __ilog2_u64(law_sz) - 1;
 
@@ -202,7 +203,7 @@ int set_ddr_laws(u64 start, u64 sz, enum law_trgt_if id)
 	if (sz) {
 		start += law_sz;
 
-		start_align = 1ull << (ffs64(start) - 1);
+		start_align = 1ull << (__ffs64(start) - 1);
 		law_sz = min(start_align, sz);
 		law_sz_enc = __ilog2_u64(law_sz) - 1;
 
diff --git a/arch/powerpc/include/asm/bitops.h b/arch/powerpc/include/asm/bitops.h
index a6bcf3c..a70bbba 100644
--- a/arch/powerpc/include/asm/bitops.h
+++ b/arch/powerpc/include/asm/bitops.h
@@ -6,6 +6,7 @@
 #define _PPC_BITOPS_H
 
 #include <asm/byteorder.h>
+#include <asm-generic/bitops/__ffs.h>
 
 extern void set_bit(int nr, volatile void *addr);
 extern void clear_bit(int nr, volatile void *addr);
@@ -179,46 +180,6 @@ static __inline__ int fls(unsigned int x)
 }
 #define PLATFORM_FLS
 
-/**
- * fls64 - find last set bit in a 64-bit word
- * @x: the word to search
- *
- * This is defined in a similar way as the libc and compiler builtin
- * ffsll, but returns the position of the most significant set bit.
- *
- * fls64(value) returns 0 if value is 0 or the position of the last
- * set bit if value is nonzero. The last (most significant) bit is
- * at position 64.
- */
-#if BITS_PER_LONG == 32
-static inline int fls64(__u64 x)
-{
-	__u32 h = x >> 32;
-	if (h)
-		return fls(h) + 32;
-	return fls(x);
-}
-#elif BITS_PER_LONG == 64
-static inline int fls64(__u64 x)
-{
-	if (x == 0)
-		return 0;
-	return __ilog2(x) + 1;
-}
-#else
-#error BITS_PER_LONG not 32 or 64
-#endif
-
-static inline int __ilog2_u64(u64 n)
-{
-	return fls64(n) - 1;
-}
-
-static inline int ffs64(u64 x)
-{
-	return __ilog2_u64(x & -x) + 1ull;
-}
-
 #ifdef __KERNEL__
 
 /*
@@ -232,6 +193,8 @@ extern __inline__ int ffs(int x)
 }
 #define PLATFORM_FFS
 
+#include <asm-generic/bitops/fls64.h>
+
 /*
  * hweightN: returns the hamming weight (i.e. the number
  * of bits set) of a N-bit word
diff --git a/arch/sh/include/asm/bitops.h b/arch/sh/include/asm/bitops.h
index c57d628..8cb8385 100644
--- a/arch/sh/include/asm/bitops.h
+++ b/arch/sh/include/asm/bitops.h
@@ -1,6 +1,11 @@
 #ifndef __ASM_SH_BITOPS_H
 #define __ASM_SH_BITOPS_H
 
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/fls64.h>
+#include <asm-generic/bitops/__ffs.h>
+
 #ifdef __KERNEL__
 #include <asm/irqflags.h>
 /* For __swab32 */
diff --git a/arch/x86/include/asm/bitops.h b/arch/x86/include/asm/bitops.h
index 5a7e4cb..a1622ae 100644
--- a/arch/x86/include/asm/bitops.h
+++ b/arch/x86/include/asm/bitops.h
@@ -22,6 +22,11 @@
 
 #define ADDR (*(volatile long *) addr)
 
+#include <asm-generic/bitops/fls.h>
+#include <asm-generic/bitops/__fls.h>
+#include <asm-generic/bitops/fls64.h>
+#include <asm-generic/bitops/__ffs.h>
+
 /**
  * set_bit - Atomically set a bit in memory
  * @nr: the bit to set
@@ -349,7 +354,6 @@ static __inline__ int ffs(int x)
 		"1:" : "=r" (r) : "g" (x));
 	return r+1;
 }
-#define PLATFORM_FFS
 
 static inline int __ilog2(unsigned int x)
 {
diff --git a/drivers/pci/fsl_pci_init.c b/drivers/pci/fsl_pci_init.c
index 52792dc..27daf6d 100644
--- a/drivers/pci/fsl_pci_init.c
+++ b/drivers/pci/fsl_pci_init.c
@@ -7,6 +7,7 @@
 #include <common.h>
 #include <malloc.h>
 #include <asm/fsl_serdes.h>
+#include <linux/log2.h>
 
 DECLARE_GLOBAL_DATA_PTR;
 
diff --git a/include/asm-generic/bitops/__ffs.h b/include/asm-generic/bitops/__ffs.h
new file mode 100644
index 0000000..9a3274a
--- /dev/null
+++ b/include/asm-generic/bitops/__ffs.h
@@ -0,0 +1,43 @@
+#ifndef _ASM_GENERIC_BITOPS___FFS_H_
+#define _ASM_GENERIC_BITOPS___FFS_H_
+
+#include <asm/types.h>
+
+/**
+ * __ffs - find first bit in word.
+ * @word: The word to search
+ *
+ * Undefined if no bit exists, so code should check against 0 first.
+ */
+static inline unsigned long __ffs(unsigned long word)
+{
+	int num = 0;
+
+#if BITS_PER_LONG == 64
+	if ((word & 0xffffffff) == 0) {
+		num += 32;
+		word >>= 32;
+	}
+#endif
+	if ((word & 0xffff) == 0) {
+		num += 16;
+		word >>= 16;
+	}
+	if ((word & 0xff) == 0) {
+		num += 8;
+		word >>= 8;
+	}
+	if ((word & 0xf) == 0) {
+		num += 4;
+		word >>= 4;
+	}
+	if ((word & 0x3) == 0) {
+		num += 2;
+		word >>= 2;
+	}
+	if ((word & 0x1) == 0)
+		num += 1;
+	return num;
+}
+
+#endif /* _ASM_GENERIC_BITOPS___FFS_H_ */
diff --git a/include/asm-generic/bitops/__fls.h b/include/asm-generic/bitops/__fls.h
new file mode 100644
index 0000000..be24465
--- /dev/null
+++ b/include/asm-generic/bitops/__fls.h
@@ -0,0 +1,43 @@
+#ifndef _ASM_GENERIC_BITOPS___FLS_H_
+#define _ASM_GENERIC_BITOPS___FLS_H_
+
+#include <asm/types.h>
+
+/**
+ * __fls - find last (most-significant) set bit in a long word
+ * @word: the word to search
+ *
+ * Undefined if no set bit exists, so code should check against 0 first.
+ */
+static inline unsigned long __fls(unsigned long word)
+{
+	int num = BITS_PER_LONG - 1;
+
+#if BITS_PER_LONG == 64
+	if (!(word & (~0ul << 32))) {
+		num -= 32;
+		word <<= 32;
+	}
+#endif
+	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
+		num -= 16;
+		word <<= 16;
+	}
+	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
+		num -= 8;
+		word <<= 8;
+	}
+	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
+		num -= 4;
+		word <<= 4;
+	}
+	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
+		num -= 2;
+		word <<= 2;
+	}
+	if (!(word & (~0ul << (BITS_PER_LONG-1))))
+		num -= 1;
+	return num;
+}
+
+#endif /* _ASM_GENERIC_BITOPS___FLS_H_ */
diff --git a/include/asm-generic/bitops/ffs.h b/include/asm-generic/bitops/ffs.h
new file mode 100644
index 0000000..fbbb43a
--- /dev/null
+++ b/include/asm-generic/bitops/ffs.h
@@ -0,0 +1,41 @@
+#ifndef _ASM_GENERIC_BITOPS_FFS_H_
+#define _ASM_GENERIC_BITOPS_FFS_H_
+
+/**
+ * ffs - find first bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as
+ * the libc and compiler builtin ffs routines, therefore
+ * differs in spirit from the above ffz (man ffs).
+ */
+static inline int ffs(int x)
+{
+	int r = 1;
+
+	if (!x)
+		return 0;
+	if (!(x & 0xffff)) {
+		x >>= 16;
+		r += 16;
+	}
+	if (!(x & 0xff)) {
+		x >>= 8;
+		r += 8;
+	}
+	if (!(x & 0xf)) {
+		x >>= 4;
+		r += 4;
+	}
+	if (!(x & 3)) {
+		x >>= 2;
+		r += 2;
+	}
+	if (!(x & 1)) {
+		x >>= 1;
+		r += 1;
+	}
+	return r;
+}
+
+#endif /* _ASM_GENERIC_BITOPS_FFS_H_ */
diff --git a/include/asm-generic/bitops/fls.h b/include/asm-generic/bitops/fls.h
new file mode 100644
index 0000000..850859b
--- /dev/null
+++ b/include/asm-generic/bitops/fls.h
@@ -0,0 +1,41 @@
+#ifndef _ASM_GENERIC_BITOPS_FLS_H_
+#define _ASM_GENERIC_BITOPS_FLS_H_
+
+/**
+ * fls - find last (most-significant) bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as ffs.
+ * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
+ */
+
+static inline int fls(int x)
+{
+	int r = 32;
+
+	if (!x)
+		return 0;
+	if (!(x & 0xffff0000u)) {
+		x <<= 16;
+		r -= 16;
+	}
+	if (!(x & 0xff000000u)) {
+		x <<= 8;
+		r -= 8;
+	}
+	if (!(x & 0xf0000000u)) {
+		x <<= 4;
+		r -= 4;
+	}
+	if (!(x & 0xc0000000u)) {
+		x <<= 2;
+		r -= 2;
+	}
+	if (!(x & 0x80000000u)) {
+		x <<= 1;
+		r -= 1;
+	}
+	return r;
+}
+
+#endif /* _ASM_GENERIC_BITOPS_FLS_H_ */
diff --git a/include/asm-generic/bitops/fls64.h b/include/asm-generic/bitops/fls64.h
new file mode 100644
index 0000000..86d403f
--- /dev/null
+++ b/include/asm-generic/bitops/fls64.h
@@ -0,0 +1,36 @@
+#ifndef _ASM_GENERIC_BITOPS_FLS64_H_
+#define _ASM_GENERIC_BITOPS_FLS64_H_
+
+#include <asm/types.h>
+
+/**
+ * fls64 - find last set bit in a 64-bit word
+ * @x: the word to search
+ *
+ * This is defined in a similar way as the libc and compiler builtin
+ * ffsll, but returns the position of the most significant set bit.
+ *
+ * fls64(value) returns 0 if value is 0 or the position of the last
+ * set bit if value is nonzero. The last (most significant) bit is
+ * at position 64.
+ */
+#if BITS_PER_LONG == 32
+static inline int fls64(__u64 x)
+{
+	__u32 h = x >> 32;
+	if (h)
+		return fls(h) + 32;
+	return fls(x);
+}
+#elif BITS_PER_LONG == 64
+static inline int fls64(__u64 x)
+{
+	if (x == 0)
+		return 0;
+	return __fls(x) + 1;
+}
+#else
+#error BITS_PER_LONG not 32 or 64
+#endif
+
+#endif /* _ASM_GENERIC_BITOPS_FLS64_H_ */
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 7d30ace..31d4d4d 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -129,6 +129,32 @@ static inline unsigned int generic_hweight8(unsigned int w)
 # define fls generic_fls
 #endif
 
+static inline unsigned fls_long(unsigned long l)
+{
+	if (sizeof(l) == 4)
+		return fls(l);
+	return fls64(l);
+}
+
+/**
+ * __ffs64 - find first set bit in a 64 bit word
+ * @word: The 64 bit word
+ *
+ * On 64 bit arches this is a synomyn for __ffs
+ * The result is not defined if no bits are set, so check that @word
+ * is non-zero before calling this.
+ */
+static inline unsigned long __ffs64(u64 word)
+{
+#if BITS_PER_LONG == 32
+	if (((u32)word) == 0UL)
+		return __ffs((u32)(word >> 32)) + 32;
+#elif BITS_PER_LONG != 64
+#error BITS_PER_LONG not 32 or 64
+#endif
+	return __ffs((unsigned long)word);
+}
+
 /**
  * __set_bit - Set a bit in memory
  * @nr: the bit to set
diff --git a/include/linux/log2.h b/include/linux/log2.h
new file mode 100644
index 0000000..aa1de63
--- /dev/null
+++ b/include/linux/log2.h
@@ -0,0 +1,205 @@
+/* Integer base 2 logarithm calculation
+ *
+ * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells at redhat.com)
+ *
+ * SPDX-License-Identifier:	GPL-2.0+
+ */
+
+#ifndef _LINUX_LOG2_H
+#define _LINUX_LOG2_H
+
+#include <linux/types.h>
+#include <linux/bitops.h>
+
+/*
+ * deal with unrepresentable constant logarithms
+ */
+extern __attribute__((const, noreturn))
+int ____ilog2_NaN(void);
+
+/*
+ * non-constant log of base 2 calculators
+ * - the arch may override these in asm/bitops.h if they can be implemented
+ *   more efficiently than using fls() and fls64()
+ * - the arch is not required to handle n==0 if implementing the fallback
+ */
+#ifndef CONFIG_ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+	return fls(n) - 1;
+}
+#endif
+
+#ifndef CONFIG_ARCH_HAS_ILOG2_U64
+static inline __attribute__((const))
+int __ilog2_u64(u64 n)
+{
+	return fls64(n) - 1;
+}
+#endif
+
+/*
+ *  Determine whether some value is a power of two, where zero is
+ * *not* considered a power of two.
+ */
+
+static inline __attribute__((const))
+bool is_power_of_2(unsigned long n)
+{
+	return (n != 0 && ((n & (n - 1)) == 0));
+}
+
+/*
+ * round up to nearest power of two
+ */
+static inline __attribute__((const))
+unsigned long __roundup_pow_of_two(unsigned long n)
+{
+	return 1UL << fls_long(n - 1);
+}
+
+/*
+ * round down to nearest power of two
+ */
+static inline __attribute__((const))
+unsigned long __rounddown_pow_of_two(unsigned long n)
+{
+	return 1UL << (fls_long(n) - 1);
+}
+
+/**
+ * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
+ * @n - parameter
+ *
+ * constant-capable log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ *
+ * selects the appropriately-sized optimised version depending on sizeof(n)
+ */
+#define ilog2(n)				\
+(						\
+	__builtin_constant_p(n) ? (		\
+		(n) < 1 ? ____ilog2_NaN() :	\
+		(n) & (1ULL << 63) ? 63 :	\
+		(n) & (1ULL << 62) ? 62 :	\
+		(n) & (1ULL << 61) ? 61 :	\
+		(n) & (1ULL << 60) ? 60 :	\
+		(n) & (1ULL << 59) ? 59 :	\
+		(n) & (1ULL << 58) ? 58 :	\
+		(n) & (1ULL << 57) ? 57 :	\
+		(n) & (1ULL << 56) ? 56 :	\
+		(n) & (1ULL << 55) ? 55 :	\
+		(n) & (1ULL << 54) ? 54 :	\
+		(n) & (1ULL << 53) ? 53 :	\
+		(n) & (1ULL << 52) ? 52 :	\
+		(n) & (1ULL << 51) ? 51 :	\
+		(n) & (1ULL << 50) ? 50 :	\
+		(n) & (1ULL << 49) ? 49 :	\
+		(n) & (1ULL << 48) ? 48 :	\
+		(n) & (1ULL << 47) ? 47 :	\
+		(n) & (1ULL << 46) ? 46 :	\
+		(n) & (1ULL << 45) ? 45 :	\
+		(n) & (1ULL << 44) ? 44 :	\
+		(n) & (1ULL << 43) ? 43 :	\
+		(n) & (1ULL << 42) ? 42 :	\
+		(n) & (1ULL << 41) ? 41 :	\
+		(n) & (1ULL << 40) ? 40 :	\
+		(n) & (1ULL << 39) ? 39 :	\
+		(n) & (1ULL << 38) ? 38 :	\
+		(n) & (1ULL << 37) ? 37 :	\
+		(n) & (1ULL << 36) ? 36 :	\
+		(n) & (1ULL << 35) ? 35 :	\
+		(n) & (1ULL << 34) ? 34 :	\
+		(n) & (1ULL << 33) ? 33 :	\
+		(n) & (1ULL << 32) ? 32 :	\
+		(n) & (1ULL << 31) ? 31 :	\
+		(n) & (1ULL << 30) ? 30 :	\
+		(n) & (1ULL << 29) ? 29 :	\
+		(n) & (1ULL << 28) ? 28 :	\
+		(n) & (1ULL << 27) ? 27 :	\
+		(n) & (1ULL << 26) ? 26 :	\
+		(n) & (1ULL << 25) ? 25 :	\
+		(n) & (1ULL << 24) ? 24 :	\
+		(n) & (1ULL << 23) ? 23 :	\
+		(n) & (1ULL << 22) ? 22 :	\
+		(n) & (1ULL << 21) ? 21 :	\
+		(n) & (1ULL << 20) ? 20 :	\
+		(n) & (1ULL << 19) ? 19 :	\
+		(n) & (1ULL << 18) ? 18 :	\
+		(n) & (1ULL << 17) ? 17 :	\
+		(n) & (1ULL << 16) ? 16 :	\
+		(n) & (1ULL << 15) ? 15 :	\
+		(n) & (1ULL << 14) ? 14 :	\
+		(n) & (1ULL << 13) ? 13 :	\
+		(n) & (1ULL << 12) ? 12 :	\
+		(n) & (1ULL << 11) ? 11 :	\
+		(n) & (1ULL << 10) ? 10 :	\
+		(n) & (1ULL <<  9) ?  9 :	\
+		(n) & (1ULL <<  8) ?  8 :	\
+		(n) & (1ULL <<  7) ?  7 :	\
+		(n) & (1ULL <<  6) ?  6 :	\
+		(n) & (1ULL <<  5) ?  5 :	\
+		(n) & (1ULL <<  4) ?  4 :	\
+		(n) & (1ULL <<  3) ?  3 :	\
+		(n) & (1ULL <<  2) ?  2 :	\
+		(n) & (1ULL <<  1) ?  1 :	\
+		(n) & (1ULL <<  0) ?  0 :	\
+		____ilog2_NaN()			\
+				   ) :		\
+	(sizeof(n) <= 4) ?			\
+	__ilog2_u32(n) :			\
+	__ilog2_u64(n)				\
+ )
+
+/**
+ * roundup_pow_of_two - round the given value up to nearest power of two
+ * @n - parameter
+ *
+ * round the given value up to the nearest power of two
+ * - the result is undefined when n == 0
+ * - this can be used to initialise global variables from constant data
+ */
+#define roundup_pow_of_two(n)			\
+(						\
+	__builtin_constant_p(n) ? (		\
+		(n == 1) ? 1 :			\
+		(1UL << (ilog2((n) - 1) + 1))	\
+				   ) :		\
+	__roundup_pow_of_two(n)			\
+ )
+
+/**
+ * rounddown_pow_of_two - round the given value down to nearest power of two
+ * @n - parameter
+ *
+ * round the given value down to the nearest power of two
+ * - the result is undefined when n == 0
+ * - this can be used to initialise global variables from constant data
+ */
+#define rounddown_pow_of_two(n)			\
+(						\
+	__builtin_constant_p(n) ? (		\
+		(1UL << ilog2(n))) :		\
+	__rounddown_pow_of_two(n)		\
+ )
+
+/**
+ * order_base_2 - calculate the (rounded up) base 2 order of the argument
+ * @n: parameter
+ *
+ * The first few values calculated by this routine:
+ *  ob2(0) = 0
+ *  ob2(1) = 0
+ *  ob2(2) = 1
+ *  ob2(3) = 2
+ *  ob2(4) = 2
+ *  ob2(5) = 3
+ *  ... and so on.
+ */
+
+#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+
+#endif /* _LINUX_LOG2_H */
-- 
1.9.1



More information about the U-Boot mailing list