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 _LINUX_LOG2_H
0009 #define _LINUX_LOG2_H
0010
0011 #include <linux/types.h>
0012 #include <linux/bitops.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 #ifndef CONFIG_ARCH_HAS_ILOG2_U32
0021 static __always_inline __attribute__((const))
0022 int __ilog2_u32(u32 n)
0023 {
0024     return fls(n) - 1;
0025 }
0026 #endif
0027
0028 #ifndef CONFIG_ARCH_HAS_ILOG2_U64
0029 static __always_inline __attribute__((const))
0030 int __ilog2_u64(u64 n)
0031 {
0032     return fls64(n) - 1;
0033 }
0034 #endif
0035
0036 /**
0037  * is_power_of_2() - check if a value is a power of two
0038  * @n: the value to check
0039  *
0040  * Determine whether some value is a power of two, where zero is
0041  * *not* considered a power of two.
0042  * Return: true if @n is a power of 2, otherwise false.
0043  */
0044 static inline __attribute__((const))
0045 bool is_power_of_2(unsigned long n)
0046 {
0047     return (n != 0 && ((n & (n - 1)) == 0));
0048 }
0049
0050 /**
0051  * __roundup_pow_of_two() - round up to nearest power of two
0052  * @n: value to round up
0053  */
0054 static inline __attribute__((const))
0055 unsigned long __roundup_pow_of_two(unsigned long n)
0056 {
0057     return 1UL << fls_long(n - 1);
0058 }
0059
0060 /**
0061  * __rounddown_pow_of_two() - round down to nearest power of two
0062  * @n: value to round down
0063  */
0064 static inline __attribute__((const))
0065 unsigned long __rounddown_pow_of_two(unsigned long n)
0066 {
0067     return 1UL << (fls_long(n) - 1);
0068 }
0069
0070 /**
0071  * const_ilog2 - log base 2 of 32-bit or a 64-bit constant unsigned value
0072  * @n: parameter
0073  *
0074  * Use this where sparse expects a true constant expression, e.g. for array
0075  * indices.
0076  */
0077 #define const_ilog2(n)              \
0078 (                       \
0079     __builtin_constant_p(n) ? (     \
0080         (n) < 2 ? 0 :           \
0081         (n) & (1ULL << 63) ? 63 :   \
0082         (n) & (1ULL << 62) ? 62 :   \
0083         (n) & (1ULL << 61) ? 61 :   \
0084         (n) & (1ULL << 60) ? 60 :   \
0085         (n) & (1ULL << 59) ? 59 :   \
0086         (n) & (1ULL << 58) ? 58 :   \
0087         (n) & (1ULL << 57) ? 57 :   \
0088         (n) & (1ULL << 56) ? 56 :   \
0089         (n) & (1ULL << 55) ? 55 :   \
0090         (n) & (1ULL << 54) ? 54 :   \
0091         (n) & (1ULL << 53) ? 53 :   \
0092         (n) & (1ULL << 52) ? 52 :   \
0093         (n) & (1ULL << 51) ? 51 :   \
0094         (n) & (1ULL << 50) ? 50 :   \
0095         (n) & (1ULL << 49) ? 49 :   \
0096         (n) & (1ULL << 48) ? 48 :   \
0097         (n) & (1ULL << 47) ? 47 :   \
0098         (n) & (1ULL << 46) ? 46 :   \
0099         (n) & (1ULL << 45) ? 45 :   \
0100         (n) & (1ULL << 44) ? 44 :   \
0101         (n) & (1ULL << 43) ? 43 :   \
0102         (n) & (1ULL << 42) ? 42 :   \
0103         (n) & (1ULL << 41) ? 41 :   \
0104         (n) & (1ULL << 40) ? 40 :   \
0105         (n) & (1ULL << 39) ? 39 :   \
0106         (n) & (1ULL << 38) ? 38 :   \
0107         (n) & (1ULL << 37) ? 37 :   \
0108         (n) & (1ULL << 36) ? 36 :   \
0109         (n) & (1ULL << 35) ? 35 :   \
0110         (n) & (1ULL << 34) ? 34 :   \
0111         (n) & (1ULL << 33) ? 33 :   \
0112         (n) & (1ULL << 32) ? 32 :   \
0113         (n) & (1ULL << 31) ? 31 :   \
0114         (n) & (1ULL << 30) ? 30 :   \
0115         (n) & (1ULL << 29) ? 29 :   \
0116         (n) & (1ULL << 28) ? 28 :   \
0117         (n) & (1ULL << 27) ? 27 :   \
0118         (n) & (1ULL << 26) ? 26 :   \
0119         (n) & (1ULL << 25) ? 25 :   \
0120         (n) & (1ULL << 24) ? 24 :   \
0121         (n) & (1ULL << 23) ? 23 :   \
0122         (n) & (1ULL << 22) ? 22 :   \
0123         (n) & (1ULL << 21) ? 21 :   \
0124         (n) & (1ULL << 20) ? 20 :   \
0125         (n) & (1ULL << 19) ? 19 :   \
0126         (n) & (1ULL << 18) ? 18 :   \
0127         (n) & (1ULL << 17) ? 17 :   \
0128         (n) & (1ULL << 16) ? 16 :   \
0129         (n) & (1ULL << 15) ? 15 :   \
0130         (n) & (1ULL << 14) ? 14 :   \
0131         (n) & (1ULL << 13) ? 13 :   \
0132         (n) & (1ULL << 12) ? 12 :   \
0133         (n) & (1ULL << 11) ? 11 :   \
0134         (n) & (1ULL << 10) ? 10 :   \
0135         (n) & (1ULL <<  9) ?  9 :   \
0136         (n) & (1ULL <<  8) ?  8 :   \
0137         (n) & (1ULL <<  7) ?  7 :   \
0138         (n) & (1ULL <<  6) ?  6 :   \
0139         (n) & (1ULL <<  5) ?  5 :   \
0140         (n) & (1ULL <<  4) ?  4 :   \
0141         (n) & (1ULL <<  3) ?  3 :   \
0142         (n) & (1ULL <<  2) ?  2 :   \
0143         1) :                \
0144     -1)
0145
0146 /**
0147  * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value
0148  * @n: parameter
0149  *
0150  * constant-capable log of base 2 calculation
0151  * - this can be used to initialise global variables from constant data, hence
0152  * the massive ternary operator construction
0153  *
0154  * selects the appropriately-sized optimised version depending on sizeof(n)
0155  */
0156 #define ilog2(n) \
0157 ( \
0158     __builtin_constant_p(n) ?   \
0159     ((n) < 2 ? 0 :          \
0160      63 - __builtin_clzll(n)) : \
0161     (sizeof(n) <= 4) ?      \
0162     __ilog2_u32(n) :        \
0163     __ilog2_u64(n)          \
0164  )
0165
0166 /**
0167  * roundup_pow_of_two - round the given value up to nearest power of two
0168  * @n: parameter
0169  *
0170  * round the given value up to the nearest power of two
0171  * - the result is undefined when n == 0
0172  * - this can be used to initialise global variables from constant data
0173  */
0174 #define roundup_pow_of_two(n)           \
0175 (                       \
0176     __builtin_constant_p(n) ? (     \
0177         ((n) == 1) ? 1 :        \
0178         (1UL << (ilog2((n) - 1) + 1))   \
0179                    ) :      \
0180     __roundup_pow_of_two(n)         \
0181  )
0182
0183 /**
0184  * rounddown_pow_of_two - round the given value down to nearest power of two
0185  * @n: parameter
0186  *
0187  * round the given value down to the nearest power of two
0188  * - the result is undefined when n == 0
0189  * - this can be used to initialise global variables from constant data
0190  */
0191 #define rounddown_pow_of_two(n)         \
0192 (                       \
0193     __builtin_constant_p(n) ? (     \
0194         (1UL << ilog2(n))) :        \
0195     __rounddown_pow_of_two(n)       \
0196  )
0197
0198 static inline __attribute_const__
0199 int __order_base_2(unsigned long n)
0200 {
0201     return n > 1 ? ilog2(n - 1) + 1 : 0;
0202 }
0203
0204 /**
0205  * order_base_2 - calculate the (rounded up) base 2 order of the argument
0206  * @n: parameter
0207  *
0208  * The first few values calculated by this routine:
0209  *  ob2(0) = 0
0210  *  ob2(1) = 0
0211  *  ob2(2) = 1
0212  *  ob2(3) = 2
0213  *  ob2(4) = 2
0214  *  ob2(5) = 3
0215  *  ... and so on.
0216  */
0217 #define order_base_2(n)             \
0218 (                       \
0219     __builtin_constant_p(n) ? (     \
0220         ((n) == 0 || (n) == 1) ? 0 :    \
0221         ilog2((n) - 1) + 1) :       \
0222     __order_base_2(n)           \
0223 )
0224
0225 static inline __attribute__((const))
0226 int __bits_per(unsigned long n)
0227 {
0228     if (n < 2)
0229         return 1;
0230     if (is_power_of_2(n))
0231         return order_base_2(n) + 1;
0232     return order_base_2(n);
0233 }
0234
0235 /**
0236  * bits_per - calculate the number of bits required for the argument
0237  * @n: parameter
0238  *
0239  * This is constant-capable and can be used for compile time
0240  * initializations, e.g bitfields.
0241  *
0242  * The first few values calculated by this routine:
0243  * bf(0) = 1
0244  * bf(1) = 1
0245  * bf(2) = 2
0246  * bf(3) = 2
0247  * bf(4) = 3
0248  * ... and so on.
0249  */
0250 #define bits_per(n)             \
0251 (                       \
0252     __builtin_constant_p(n) ? (     \
0253         ((n) == 0 || (n) == 1)      \
0254             ? 1 : ilog2(n) + 1  \
0255     ) :                 \
0256     __bits_per(n)               \
0257 )
0258 #endif /* _LINUX_LOG2_H */