1 /* Integer base 2 logarithm calculation
3 * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
15 #include <linux/types.h>
16 #include <linux/bitops.h>
19 * deal with unrepresentable constant logarithms
21 int ____ilog2_NaN(void);
24 * non-constant log of base 2 calculators
25 * - the arch may override these in asm/bitops.h if they can be implemented
26 * more efficiently than using fls() and fls64()
27 * - the arch is not required to handle n==0 if implementing the fallback
29 #ifndef CONFIG_ARCH_HAS_ILOG2_U32
30 static inline __attribute__((const))
31 int __ilog2_u32(u32 n
)
37 #ifndef CONFIG_ARCH_HAS_ILOG2_U64
38 static inline __attribute__((const))
39 int __ilog2_u64(u64 n
)
46 * Determine whether some value is a power of two, where zero is
47 * *not* considered a power of two.
50 static inline __attribute__((const))
51 bool is_power_of_2(unsigned long n
)
53 return (n
!= 0 && ((n
& (n
- 1)) == 0));
57 * round up to nearest power of two
59 static inline __attribute__((const))
60 unsigned long __roundup_pow_of_two(unsigned long n
)
62 return 1UL << fls_long(n
- 1);
66 * round down to nearest power of two
68 static inline __attribute__((const))
69 unsigned long __rounddown_pow_of_two(unsigned long n
)
71 return 1UL << (fls_long(n
) - 1);
75 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
78 * constant-capable log of base 2 calculation
79 * - this can be used to initialise global variables from constant data, hence
80 * the massive ternary operator construction
82 * selects the appropriately-sized optimised version depending on sizeof(n)
92 * roundup_pow_of_two - round the given value up to nearest power of two
95 * round the given value up to the nearest power of two
96 * - the result is undefined when n == 0
97 * - this can be used to initialise global variables from constant data
99 #define roundup_pow_of_two(n) \
101 __builtin_constant_p(n) ? ( \
103 (1UL << (ilog2((n) - 1) + 1)) \
105 __roundup_pow_of_two(n) \
109 * rounddown_pow_of_two - round the given value down to nearest power of two
112 * round the given value down to the nearest power of two
113 * - the result is undefined when n == 0
114 * - this can be used to initialise global variables from constant data
116 #define rounddown_pow_of_two(n) \
118 __builtin_constant_p(n) ? ( \
120 (1UL << ilog2(n))) : \
121 __rounddown_pow_of_two(n) \
125 * order_base_2 - calculate the (rounded up) base 2 order of the argument
128 * The first few values calculated by this routine:
138 #define order_base_2(n) ilog2(roundup_pow_of_two(n))
140 #endif /* _LINUX_LOG2_H */