drivers/filesystems/ext2/inc/linux/log2.h

   1 /* Integer base 2 logarithm calculation
   2  *
   3  * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
   4  * Written by David Howells (dhowells@redhat.com)
   5  *
   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.
  10  */
  11
  12 #ifndef _LINUX_LOG2_H
  13 #define _LINUX_LOG2_H
  14
  15 #include <linux/types.h>
  16 #include <linux/bitops.h>
  17
  18 /*
  19  * deal with unrepresentable constant logarithms
  20  */
  21 int ____ilog2_NaN(void);
  22
  23 /*
  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
  28  */
  29 #ifndef CONFIG_ARCH_HAS_ILOG2_U32
  30 static inline __attribute__((const))
  31 int __ilog2_u32(u32 n)
  32 {
  33     return fls(n) - 1;
  34 }
  35 #endif
  36
  37 #ifndef CONFIG_ARCH_HAS_ILOG2_U64
  38 static inline __attribute__((const))
  39 int __ilog2_u64(u64 n)
  40 {
  41     return fls64(n) - 1;
  42 }
  43 #endif
  44
  45 /*
  46  *  Determine whether some value is a power of two, where zero is
  47  * *not* considered a power of two.
  48  */
  49
  50 static inline __attribute__((const))
  51 bool is_power_of_2(unsigned long n)
  52 {
  53     return (n != 0 && ((n & (n - 1)) == 0));
  54 }
  55
  56 /*
  57  * round up to nearest power of two
  58  */
  59 static inline __attribute__((const))
  60 unsigned long __roundup_pow_of_two(unsigned long n)
  61 {
  62     return 1UL << fls_long(n - 1);
  63 }
  64
  65 /*
  66  * round down to nearest power of two
  67  */
  68 static inline __attribute__((const))
  69 unsigned long __rounddown_pow_of_two(unsigned long n)
  70 {
  71     return 1UL << (fls_long(n) - 1);
  72 }
  73
  74 /**
  75  * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
  76  * @n - parameter
  77  *
  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
  81  *
  82  * selects the appropriately-sized optimised version depending on sizeof(n)
  83  */
  84 #define ilog2(n)                                \
  85 (                                               \
  86         (sizeof(n) <= 4) ?                      \
  87         __ilog2_u32(n) :                        \
  88         __ilog2_u64(n)                          \
  89  )
  90
  91 /**
  92  * roundup_pow_of_two - round the given value up to nearest power of two
  93  * @n - parameter
  94  *
  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
  98  */
  99 #define roundup_pow_of_two(n)                   \
 100 (                                               \
 101         __builtin_constant_p(n) ? (             \
 102                 (n == 1) ? 1 :                  \
 103                 (1UL << (ilog2((n) - 1) + 1))   \
 104                                    ) :          \
 105         __roundup_pow_of_two(n)                 \
 106  )
 107
 108 /**
 109  * rounddown_pow_of_two - round the given value down to nearest power of two
 110  * @n - parameter
 111  *
 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
 115  */
 116 #define rounddown_pow_of_two(n)                 \
 117 (                                               \
 118         __builtin_constant_p(n) ? (             \
 119                 (n == 1) ? 0 :                  \
 120                 (1UL << ilog2(n))) :            \
 121         __rounddown_pow_of_two(n)               \
 122  )
 123
 124 /**
 125  * order_base_2 - calculate the (rounded up) base 2 order of the argument
 126  * @n: parameter
 127  *
 128  * The first few values calculated by this routine:
 129  *  ob2(0) = 0
 130  *  ob2(1) = 0
 131  *  ob2(2) = 1
 132  *  ob2(3) = 2
 133  *  ob2(4) = 2
 134  *  ob2(5) = 3
 135  *  ... and so on.
 136  */
 137
 138 #define order_base_2(n) ilog2(roundup_pow_of_two(n))
 139
 140 #endif /* _LINUX_LOG2_H */