Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0-or-later */
       2             : /* Integer base 2 logarithm calculation
       3             :  *
       4             :  * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
       5             :  * Written by David Howells (dhowells@redhat.com)
       6             :  */
       7             : 
       8             : #ifndef _LINUX_LOG2_H
       9             : #define _LINUX_LOG2_H
      10             : 
      11             : #include <linux/types.h>
      12             : #include <linux/bitops.h>
      13             : 
      14             : /*
      15             :  * non-constant log of base 2 calculators
      16             :  * - the arch may override these in asm/bitops.h if they can be implemented
      17             :  *   more efficiently than using fls() and fls64()
      18             :  * - the arch is not required to handle n==0 if implementing the fallback
      19             :  */
      20             : #ifndef CONFIG_ARCH_HAS_ILOG2_U32
      21             : static __always_inline __attribute__((const))
      22             : int __ilog2_u32(u32 n)
      23             : {
      24  6815903781 :         return fls(n) - 1;
      25             : }
      26             : #endif
      27             : 
      28             : #ifndef CONFIG_ARCH_HAS_ILOG2_U64
      29             : static __always_inline __attribute__((const))
      30             : int __ilog2_u64(u64 n)
      31             : {
      32   149323842 :         return fls64(n) - 1;
      33             : }
      34             : #endif
      35             : 
      36             : /**
      37             :  * is_power_of_2() - check if a value is a power of two
      38             :  * @n: the value to check
      39             :  *
      40             :  * Determine whether some value is a power of two, where zero is
      41             :  * *not* considered a power of two.
      42             :  * Return: true if @n is a power of 2, otherwise false.
      43             :  */
      44             : static inline __attribute__((const))
      45             : bool is_power_of_2(unsigned long n)
      46             : {
      47   799820661 :         return (n != 0 && ((n & (n - 1)) == 0));
      48             : }
      49             : 
      50             : /**
      51             :  * __roundup_pow_of_two() - round up to nearest power of two
      52             :  * @n: value to round up
      53             :  */
      54             : static inline __attribute__((const))
      55    15792707 : unsigned long __roundup_pow_of_two(unsigned long n)
      56             : {
      57    23735625 :         return 1UL << fls_long(n - 1);
      58             : }
      59             : 
      60             : /**
      61             :  * __rounddown_pow_of_two() - round down to nearest power of two
      62             :  * @n: value to round down
      63             :  */
      64             : static inline __attribute__((const))
      65     1453476 : unsigned long __rounddown_pow_of_two(unsigned long n)
      66             : {
      67     1453476 :         return 1UL << (fls_long(n) - 1);
      68             : }
      69             : 
      70             : /**
      71             :  * const_ilog2 - log base 2 of 32-bit or a 64-bit constant unsigned value
      72             :  * @n: parameter
      73             :  *
      74             :  * Use this where sparse expects a true constant expression, e.g. for array
      75             :  * indices.
      76             :  */
      77             : #define const_ilog2(n)                          \
      78             : (                                               \
      79             :         __builtin_constant_p(n) ? (             \
      80             :                 (n) < 2 ? 0 :                        \
      81             :                 (n) & (1ULL << 63) ? 63 :     \
      82             :                 (n) & (1ULL << 62) ? 62 :     \
      83             :                 (n) & (1ULL << 61) ? 61 :     \
      84             :                 (n) & (1ULL << 60) ? 60 :     \
      85             :                 (n) & (1ULL << 59) ? 59 :     \
      86             :                 (n) & (1ULL << 58) ? 58 :     \
      87             :                 (n) & (1ULL << 57) ? 57 :     \
      88             :                 (n) & (1ULL << 56) ? 56 :     \
      89             :                 (n) & (1ULL << 55) ? 55 :     \
      90             :                 (n) & (1ULL << 54) ? 54 :     \
      91             :                 (n) & (1ULL << 53) ? 53 :     \
      92             :                 (n) & (1ULL << 52) ? 52 :     \
      93             :                 (n) & (1ULL << 51) ? 51 :     \
      94             :                 (n) & (1ULL << 50) ? 50 :     \
      95             :                 (n) & (1ULL << 49) ? 49 :     \
      96             :                 (n) & (1ULL << 48) ? 48 :     \
      97             :                 (n) & (1ULL << 47) ? 47 :     \
      98             :                 (n) & (1ULL << 46) ? 46 :     \
      99             :                 (n) & (1ULL << 45) ? 45 :     \
     100             :                 (n) & (1ULL << 44) ? 44 :     \
     101             :                 (n) & (1ULL << 43) ? 43 :     \
     102             :                 (n) & (1ULL << 42) ? 42 :     \
     103             :                 (n) & (1ULL << 41) ? 41 :     \
     104             :                 (n) & (1ULL << 40) ? 40 :     \
     105             :                 (n) & (1ULL << 39) ? 39 :     \
     106             :                 (n) & (1ULL << 38) ? 38 :     \
     107             :                 (n) & (1ULL << 37) ? 37 :     \
     108             :                 (n) & (1ULL << 36) ? 36 :     \
     109             :                 (n) & (1ULL << 35) ? 35 :     \
     110             :                 (n) & (1ULL << 34) ? 34 :     \
     111             :                 (n) & (1ULL << 33) ? 33 :     \
     112             :                 (n) & (1ULL << 32) ? 32 :     \
     113             :                 (n) & (1ULL << 31) ? 31 :     \
     114             :                 (n) & (1ULL << 30) ? 30 :     \
     115             :                 (n) & (1ULL << 29) ? 29 :     \
     116             :                 (n) & (1ULL << 28) ? 28 :     \
     117             :                 (n) & (1ULL << 27) ? 27 :     \
     118             :                 (n) & (1ULL << 26) ? 26 :     \
     119             :                 (n) & (1ULL << 25) ? 25 :     \
     120             :                 (n) & (1ULL << 24) ? 24 :     \
     121             :                 (n) & (1ULL << 23) ? 23 :     \
     122             :                 (n) & (1ULL << 22) ? 22 :     \
     123             :                 (n) & (1ULL << 21) ? 21 :     \
     124             :                 (n) & (1ULL << 20) ? 20 :     \
     125             :                 (n) & (1ULL << 19) ? 19 :     \
     126             :                 (n) & (1ULL << 18) ? 18 :     \
     127             :                 (n) & (1ULL << 17) ? 17 :     \
     128             :                 (n) & (1ULL << 16) ? 16 :     \
     129             :                 (n) & (1ULL << 15) ? 15 :     \
     130             :                 (n) & (1ULL << 14) ? 14 :     \
     131             :                 (n) & (1ULL << 13) ? 13 :     \
     132             :                 (n) & (1ULL << 12) ? 12 :     \
     133             :                 (n) & (1ULL << 11) ? 11 :     \
     134             :                 (n) & (1ULL << 10) ? 10 :     \
     135             :                 (n) & (1ULL <<  9) ?  9 :     \
     136             :                 (n) & (1ULL <<  8) ?  8 :     \
     137             :                 (n) & (1ULL <<  7) ?  7 :     \
     138             :                 (n) & (1ULL <<  6) ?  6 :     \
     139             :                 (n) & (1ULL <<  5) ?  5 :     \
     140             :                 (n) & (1ULL <<  4) ?  4 :     \
     141             :                 (n) & (1ULL <<  3) ?  3 :     \
     142             :                 (n) & (1ULL <<  2) ?  2 :     \
     143             :                 1) :                            \
     144             :         -1)
     145             : 
     146             : /**
     147             :  * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value
     148             :  * @n: parameter
     149             :  *
     150             :  * constant-capable log of base 2 calculation
     151             :  * - this can be used to initialise global variables from constant data, hence
     152             :  * the massive ternary operator construction
     153             :  *
     154             :  * selects the appropriately-sized optimised version depending on sizeof(n)
     155             :  */
     156             : #define ilog2(n) \
     157             : ( \
     158             :         __builtin_constant_p(n) ?       \
     159             :         ((n) < 2 ? 0 :                       \
     160             :          63 - __builtin_clzll(n)) :     \
     161             :         (sizeof(n) <= 4) ?           \
     162             :         __ilog2_u32(n) :                \
     163             :         __ilog2_u64(n)                  \
     164             :  )
     165             : 
     166             : /**
     167             :  * roundup_pow_of_two - round the given value up to nearest power of two
     168             :  * @n: parameter
     169             :  *
     170             :  * round the given value up to the nearest power of two
     171             :  * - the result is undefined when n == 0
     172             :  * - this can be used to initialise global variables from constant data
     173             :  */
     174             : #define roundup_pow_of_two(n)                   \
     175             : (                                               \
     176             :         __builtin_constant_p(n) ? (             \
     177             :                 ((n) == 1) ? 1 :                \
     178             :                 (1UL << (ilog2((n) - 1) + 1))     \
     179             :                                    ) :          \
     180             :         __roundup_pow_of_two(n)                 \
     181             :  )
     182             : 
     183             : /**
     184             :  * rounddown_pow_of_two - round the given value down to nearest power of two
     185             :  * @n: parameter
     186             :  *
     187             :  * round the given value down to the nearest power of two
     188             :  * - the result is undefined when n == 0
     189             :  * - this can be used to initialise global variables from constant data
     190             :  */
     191             : #define rounddown_pow_of_two(n)                 \
     192             : (                                               \
     193             :         __builtin_constant_p(n) ? (             \
     194             :                 (1UL << ilog2(n))) :              \
     195             :         __rounddown_pow_of_two(n)               \
     196             :  )
     197             : 
     198             : static inline __attribute_const__
     199     1062302 : int __order_base_2(unsigned long n)
     200             : {
     201     1062302 :         return n > 1 ? ilog2(n - 1) + 1 : 0;
     202             : }
     203             : 
     204             : /**
     205             :  * order_base_2 - calculate the (rounded up) base 2 order of the argument
     206             :  * @n: parameter
     207             :  *
     208             :  * The first few values calculated by this routine:
     209             :  *  ob2(0) = 0
     210             :  *  ob2(1) = 0
     211             :  *  ob2(2) = 1
     212             :  *  ob2(3) = 2
     213             :  *  ob2(4) = 2
     214             :  *  ob2(5) = 3
     215             :  *  ... and so on.
     216             :  */
     217             : #define order_base_2(n)                         \
     218             : (                                               \
     219             :         __builtin_constant_p(n) ? (             \
     220             :                 ((n) == 0 || (n) == 1) ? 0 :    \
     221             :                 ilog2((n) - 1) + 1) :           \
     222             :         __order_base_2(n)                       \
     223             : )
     224             : 
     225             : static inline __attribute__((const))
     226             : int __bits_per(unsigned long n)
     227             : {
     228             :         if (n < 2)
     229             :                 return 1;
     230             :         if (is_power_of_2(n))
     231             :                 return order_base_2(n) + 1;
     232             :         return order_base_2(n);
     233             : }
     234             : 
     235             : /**
     236             :  * bits_per - calculate the number of bits required for the argument
     237             :  * @n: parameter
     238             :  *
     239             :  * This is constant-capable and can be used for compile time
     240             :  * initializations, e.g bitfields.
     241             :  *
     242             :  * The first few values calculated by this routine:
     243             :  * bf(0) = 1
     244             :  * bf(1) = 1
     245             :  * bf(2) = 2
     246             :  * bf(3) = 2
     247             :  * bf(4) = 3
     248             :  * ... and so on.
     249             :  */
     250             : #define bits_per(n)                             \
     251             : (                                               \
     252             :         __builtin_constant_p(n) ? (             \
     253             :                 ((n) == 0 || (n) == 1)          \
     254             :                         ? 1 : ilog2(n) + 1      \
     255             :         ) :                                     \
     256             :         __bits_per(n)                           \
     257             : )
     258             : #endif /* _LINUX_LOG2_H */