include/linux/log2.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 /* Integer base 2 logarithm calculation
0003  *
0004  * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
0005  * Written by David Howells (dhowells@redhat.com)
0006  */
0007
0008 #ifndef _TOOLS_LINUX_LOG2_H
0009 #define _TOOLS_LINUX_LOG2_H
0010
0011 #include <linux/bitops.h>
0012 #include <linux/types.h>
0013
0014 /*
0015  * non-constant log of base 2 calculators
0016  * - the arch may override these in asm/bitops.h if they can be implemented
0017  *   more efficiently than using fls() and fls64()
0018  * - the arch is not required to handle n==0 if implementing the fallback
0019  */
0020 static inline __attribute__((const))
0021 int __ilog2_u32(u32 n)
0022 {
0023     return fls(n) - 1;
0024 }
0025
0026 static inline __attribute__((const))
0027 int __ilog2_u64(u64 n)
0028 {
0029     return fls64(n) - 1;
0030 }
0031
0032 /*
0033  *  Determine whether some value is a power of two, where zero is
0034  * *not* considered a power of two.
0035  */
0036
0037 static inline __attribute__((const))
0038 bool is_power_of_2(unsigned long n)
0039 {
0040     return (n != 0 && ((n & (n - 1)) == 0));
0041 }
0042
0043 /*
0044  * round up to nearest power of two
0045  */
0046 static inline __attribute__((const))
0047 unsigned long __roundup_pow_of_two(unsigned long n)
0048 {
0049     return 1UL << fls_long(n - 1);
0050 }
0051
0052 /*
0053  * round down to nearest power of two
0054  */
0055 static inline __attribute__((const))
0056 unsigned long __rounddown_pow_of_two(unsigned long n)
0057 {
0058     return 1UL << (fls_long(n) - 1);
0059 }
0060
0061 /**
0062  * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
0063  * @n - parameter
0064  *
0065  * constant-capable log of base 2 calculation
0066  * - this can be used to initialise global variables from constant data, hence
0067  *   the massive ternary operator construction
0068  *
0069  * selects the appropriately-sized optimised version depending on sizeof(n)
0070  */
0071 #define ilog2(n)                \
0072 (                       \
0073     __builtin_constant_p(n) ? (     \
0074         (n) < 2 ? 0 :           \
0075         (n) & (1ULL << 63) ? 63 :   \
0076         (n) & (1ULL << 62) ? 62 :   \
0077         (n) & (1ULL << 61) ? 61 :   \
0078         (n) & (1ULL << 60) ? 60 :   \
0079         (n) & (1ULL << 59) ? 59 :   \
0080         (n) & (1ULL << 58) ? 58 :   \
0081         (n) & (1ULL << 57) ? 57 :   \
0082         (n) & (1ULL << 56) ? 56 :   \
0083         (n) & (1ULL << 55) ? 55 :   \
0084         (n) & (1ULL << 54) ? 54 :   \
0085         (n) & (1ULL << 53) ? 53 :   \
0086         (n) & (1ULL << 52) ? 52 :   \
0087         (n) & (1ULL << 51) ? 51 :   \
0088         (n) & (1ULL << 50) ? 50 :   \
0089         (n) & (1ULL << 49) ? 49 :   \
0090         (n) & (1ULL << 48) ? 48 :   \
0091         (n) & (1ULL << 47) ? 47 :   \
0092         (n) & (1ULL << 46) ? 46 :   \
0093         (n) & (1ULL << 45) ? 45 :   \
0094         (n) & (1ULL << 44) ? 44 :   \
0095         (n) & (1ULL << 43) ? 43 :   \
0096         (n) & (1ULL << 42) ? 42 :   \
0097         (n) & (1ULL << 41) ? 41 :   \
0098         (n) & (1ULL << 40) ? 40 :   \
0099         (n) & (1ULL << 39) ? 39 :   \
0100         (n) & (1ULL << 38) ? 38 :   \
0101         (n) & (1ULL << 37) ? 37 :   \
0102         (n) & (1ULL << 36) ? 36 :   \
0103         (n) & (1ULL << 35) ? 35 :   \
0104         (n) & (1ULL << 34) ? 34 :   \
0105         (n) & (1ULL << 33) ? 33 :   \
0106         (n) & (1ULL << 32) ? 32 :   \
0107         (n) & (1ULL << 31) ? 31 :   \
0108         (n) & (1ULL << 30) ? 30 :   \
0109         (n) & (1ULL << 29) ? 29 :   \
0110         (n) & (1ULL << 28) ? 28 :   \
0111         (n) & (1ULL << 27) ? 27 :   \
0112         (n) & (1ULL << 26) ? 26 :   \
0113         (n) & (1ULL << 25) ? 25 :   \
0114         (n) & (1ULL << 24) ? 24 :   \
0115         (n) & (1ULL << 23) ? 23 :   \
0116         (n) & (1ULL << 22) ? 22 :   \
0117         (n) & (1ULL << 21) ? 21 :   \
0118         (n) & (1ULL << 20) ? 20 :   \
0119         (n) & (1ULL << 19) ? 19 :   \
0120         (n) & (1ULL << 18) ? 18 :   \
0121         (n) & (1ULL << 17) ? 17 :   \
0122         (n) & (1ULL << 16) ? 16 :   \
0123         (n) & (1ULL << 15) ? 15 :   \
0124         (n) & (1ULL << 14) ? 14 :   \
0125         (n) & (1ULL << 13) ? 13 :   \
0126         (n) & (1ULL << 12) ? 12 :   \
0127         (n) & (1ULL << 11) ? 11 :   \
0128         (n) & (1ULL << 10) ? 10 :   \
0129         (n) & (1ULL <<  9) ?  9 :   \
0130         (n) & (1ULL <<  8) ?  8 :   \
0131         (n) & (1ULL <<  7) ?  7 :   \
0132         (n) & (1ULL <<  6) ?  6 :   \
0133         (n) & (1ULL <<  5) ?  5 :   \
0134         (n) & (1ULL <<  4) ?  4 :   \
0135         (n) & (1ULL <<  3) ?  3 :   \
0136         (n) & (1ULL <<  2) ?  2 :   \
0137         1 ) :               \
0138     (sizeof(n) <= 4) ?          \
0139     __ilog2_u32(n) :            \
0140     __ilog2_u64(n)              \
0141  )
0142
0143 /**
0144  * roundup_pow_of_two - round the given value up to nearest power of two
0145  * @n - parameter
0146  *
0147  * round the given value up to the nearest power of two
0148  * - the result is undefined when n == 0
0149  * - this can be used to initialise global variables from constant data
0150  */
0151 #define roundup_pow_of_two(n)           \
0152 (                       \
0153     __builtin_constant_p(n) ? (     \
0154         (n == 1) ? 1 :          \
0155         (1UL << (ilog2((n) - 1) + 1))   \
0156                    ) :      \
0157     __roundup_pow_of_two(n)         \
0158  )
0159
0160 /**
0161  * rounddown_pow_of_two - round the given value down to nearest power of two
0162  * @n - parameter
0163  *
0164  * round the given value down to the nearest power of two
0165  * - the result is undefined when n == 0
0166  * - this can be used to initialise global variables from constant data
0167  */
0168 #define rounddown_pow_of_two(n)         \
0169 (                       \
0170     __builtin_constant_p(n) ? (     \
0171         (1UL << ilog2(n))) :        \
0172     __rounddown_pow_of_two(n)       \
0173  )
0174
0175 #endif /* _TOOLS_LINUX_LOG2_H */