log2.h 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. /* SPDX-License-Identifier: GPL-2.0+ */
  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. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public License
  9. * as published by the Free Software Foundation; either version
  10. * 2 of the License, or (at your option) any later version.
  11. */
  12. #ifndef _LINUX_LOG2_H
  13. #define _LINUX_LOG2_H
  14. #include <linux/types.h>
  15. #include <linux/bitops.h>
  16. /*
  17. * non-constant log of base 2 calculators
  18. * - the arch may override these in asm/bitops.h if they can be implemented
  19. * more efficiently than using fls() and fls64()
  20. * - the arch is not required to handle n==0 if implementing the fallback
  21. */
  22. #ifndef CONFIG_ARCH_HAS_ILOG2_U32
  23. static inline __attribute__((const))
  24. int __ilog2_u32(u32 n)
  25. {
  26. return fls(n) - 1;
  27. }
  28. #endif
  29. #ifndef CONFIG_ARCH_HAS_ILOG2_U64
  30. static inline __attribute__((const))
  31. int __ilog2_u64(u64 n)
  32. {
  33. return fls64(n) - 1;
  34. }
  35. #endif
  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. return (n != 0 && ((n & (n - 1)) == 0));
  48. }
  49. /**
  50. * __roundup_pow_of_two() - round up to nearest power of two
  51. * @n: value to round up
  52. */
  53. static inline __attribute__((const))
  54. unsigned long __roundup_pow_of_two(unsigned long n)
  55. {
  56. return 1UL << fls_long(n - 1);
  57. }
  58. /**
  59. * __rounddown_pow_of_two() - round down to nearest power of two
  60. * @n: value to round down
  61. */
  62. static inline __attribute__((const))
  63. unsigned long __rounddown_pow_of_two(unsigned long n)
  64. {
  65. return 1UL << (fls_long(n) - 1);
  66. }
  67. /**
  68. * ilog2 - log base 2 of 32-bit or a 64-bit unsigned value
  69. * @n: parameter
  70. *
  71. * constant-capable log of base 2 calculation
  72. * - this can be used to initialise global variables from constant data, hence
  73. * the massive ternary operator construction
  74. *
  75. * selects the appropriately-sized optimised version depending on sizeof(n)
  76. */
  77. #define 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. (sizeof(n) <= 4) ? \
  145. __ilog2_u32(n) : \
  146. __ilog2_u64(n) \
  147. )
  148. /**
  149. * roundup_pow_of_two - round the given value up to nearest power of two
  150. * @n: parameter
  151. *
  152. * round the given value up to the nearest power of two
  153. * - the result is undefined when n == 0
  154. * - this can be used to initialise global variables from constant data
  155. */
  156. #define roundup_pow_of_two(n) \
  157. ( \
  158. __builtin_constant_p(n) ? ( \
  159. (n == 1) ? 1 : \
  160. (1UL << (ilog2((n) - 1) + 1)) \
  161. ) : \
  162. __roundup_pow_of_two(n) \
  163. )
  164. /**
  165. * rounddown_pow_of_two - round the given value down to nearest power of two
  166. * @n: parameter
  167. *
  168. * round the given value down to the nearest power of two
  169. * - the result is undefined when n == 0
  170. * - this can be used to initialise global variables from constant data
  171. */
  172. #define rounddown_pow_of_two(n) \
  173. ( \
  174. __builtin_constant_p(n) ? ( \
  175. (1UL << ilog2(n))) : \
  176. __rounddown_pow_of_two(n) \
  177. )
  178. static inline __attribute_const__
  179. int __order_base_2(unsigned long n)
  180. {
  181. return n > 1 ? ilog2(n - 1) + 1 : 0;
  182. }
  183. /**
  184. * order_base_2 - calculate the (rounded up) base 2 order of the argument
  185. * @n: parameter
  186. *
  187. * The first few values calculated by this routine:
  188. * ob2(0) = 0
  189. * ob2(1) = 0
  190. * ob2(2) = 1
  191. * ob2(3) = 2
  192. * ob2(4) = 2
  193. * ob2(5) = 3
  194. * ... and so on.
  195. */
  196. #define order_base_2(n) \
  197. ( \
  198. __builtin_constant_p(n) ? ( \
  199. ((n) == 0 || (n) == 1) ? 0 : \
  200. ilog2((n) - 1) + 1) : \
  201. __order_base_2(n) \
  202. )
  203. #endif /* _LINUX_LOG2_H */