Branch data     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 inline __attribute__((const))
      22                 :            : int __ilog2_u32(u32 n)
      23                 :            : {
      24                 :    1154178 :         return fls(n) - 1;
      25                 :            : }
      26                 :            : #endif
      27                 :            : 
      28                 :            : #ifndef CONFIG_ARCH_HAS_ILOG2_U64
      29                 :            : static inline __attribute__((const))
      30                 :            : int __ilog2_u64(u64 n)
      31                 :            : {
      32                 :   15021882 :         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   [ +  +  +  +  :   15940028 :         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                 :            : unsigned long __roundup_pow_of_two(unsigned long n)
      56                 :            : {
      57                 :    1280256 :         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                 :            : unsigned long __rounddown_pow_of_two(unsigned long n)
      66                 :            : {
      67                 :       2424 :         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                 :            :         const_ilog2(n) :                \
     160                 :            :         (sizeof(n) <= 4) ?           \
     161                 :            :         __ilog2_u32(n) :                \
     162                 :            :         __ilog2_u64(n)                  \
     163                 :            :  )
     164                 :            : 
     165                 :            : /**
     166                 :            :  * roundup_pow_of_two - round the given value up to nearest power of two
     167                 :            :  * @n: parameter
     168                 :            :  *
     169                 :            :  * round the given value up to the nearest power of two
     170                 :            :  * - the result is undefined when n == 0
     171                 :            :  * - this can be used to initialise global variables from constant data
     172                 :            :  */
     173                 :            : #define roundup_pow_of_two(n)                   \
     174                 :            : (                                               \
     175                 :            :         __builtin_constant_p(n) ? (             \
     176                 :            :                 (n == 1) ? 1 :                  \
     177                 :            :                 (1UL << (ilog2((n) - 1) + 1))     \
     178                 :            :                                    ) :          \
     179                 :            :         __roundup_pow_of_two(n)                 \
     180                 :            :  )
     181                 :            : 
     182                 :            : /**
     183                 :            :  * rounddown_pow_of_two - round the given value down to nearest power of two
     184                 :            :  * @n: parameter
     185                 :            :  *
     186                 :            :  * round the given value down to the nearest power of two
     187                 :            :  * - the result is undefined when n == 0
     188                 :            :  * - this can be used to initialise global variables from constant data
     189                 :            :  */
     190                 :            : #define rounddown_pow_of_two(n)                 \
     191                 :            : (                                               \
     192                 :            :         __builtin_constant_p(n) ? (             \
     193                 :            :                 (1UL << ilog2(n))) :              \
     194                 :            :         __rounddown_pow_of_two(n)               \
     195                 :            :  )
     196                 :            : 
     197                 :            : static inline __attribute_const__
     198                 :       1212 : int __order_base_2(unsigned long n)
     199                 :            : {
     200   [ +  -  -  +  :       2424 :         return n > 1 ? ilog2(n - 1) + 1 : 0;
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     201                 :            : }
     202                 :            : 
     203                 :            : /**
     204                 :            :  * order_base_2 - calculate the (rounded up) base 2 order of the argument
     205                 :            :  * @n: parameter
     206                 :            :  *
     207                 :            :  * The first few values calculated by this routine:
     208                 :            :  *  ob2(0) = 0
     209                 :            :  *  ob2(1) = 0
     210                 :            :  *  ob2(2) = 1
     211                 :            :  *  ob2(3) = 2
     212                 :            :  *  ob2(4) = 2
     213                 :            :  *  ob2(5) = 3
     214                 :            :  *  ... and so on.
     215                 :            :  */
     216                 :            : #define order_base_2(n)                         \
     217                 :            : (                                               \
     218                 :            :         __builtin_constant_p(n) ? (             \
     219                 :            :                 ((n) == 0 || (n) == 1) ? 0 :    \
     220                 :            :                 ilog2((n) - 1) + 1) :           \
     221                 :            :         __order_base_2(n)                       \
     222                 :            : )
     223                 :            : 
     224                 :            : static inline __attribute__((const))
     225                 :            : int __bits_per(unsigned long n)
     226                 :            : {
     227                 :            :         if (n < 2)
     228                 :            :                 return 1;
     229                 :            :         if (is_power_of_2(n))
     230                 :            :                 return order_base_2(n) + 1;
     231                 :            :         return order_base_2(n);
     232                 :            : }
     233                 :            : 
     234                 :            : /**
     235                 :            :  * bits_per - calculate the number of bits required for the argument
     236                 :            :  * @n: parameter
     237                 :            :  *
     238                 :            :  * This is constant-capable and can be used for compile time
     239                 :            :  * initializations, e.g bitfields.
     240                 :            :  *
     241                 :            :  * The first few values calculated by this routine:
     242                 :            :  * bf(0) = 1
     243                 :            :  * bf(1) = 1
     244                 :            :  * bf(2) = 2
     245                 :            :  * bf(3) = 2
     246                 :            :  * bf(4) = 3
     247                 :            :  * ... and so on.
     248                 :            :  */
     249                 :            : #define bits_per(n)                             \
     250                 :            : (                                               \
     251                 :            :         __builtin_constant_p(n) ? (             \
     252                 :            :                 ((n) == 0 || (n) == 1)          \
     253                 :            :                         ? 1 : ilog2(n) + 1      \
     254                 :            :         ) :                                     \
     255                 :            :         __bits_per(n)                           \
     256                 :            : )
     257                 :            : #endif /* _LINUX_LOG2_H */