div64.h 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef _ASM_GENERIC_DIV64_H
  3. #define _ASM_GENERIC_DIV64_H
  4. /*
  5. * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
  6. * Based on former asm-ppc/div64.h and asm-m68knommu/div64.h
  7. *
  8. * Optimization for constant divisors on 32-bit machines:
  9. * Copyright (C) 2006-2015 Nicolas Pitre
  10. *
  11. * The semantics of do_div() are:
  12. *
  13. * uint32_t do_div(uint64_t *n, uint32_t base)
  14. * {
  15. * uint32_t remainder = *n % base;
  16. * *n = *n / base;
  17. * return remainder;
  18. * }
  19. *
  20. * NOTE: macro parameter n is evaluated multiple times,
  21. * beware of side effects!
  22. */
  23. #include <linux/types.h>
  24. #include <linux/compiler.h>
  25. #if BITS_PER_LONG == 64
  26. /**
  27. * do_div - returns 2 values: calculate remainder and update new dividend
  28. * @n: uint64_t dividend (will be updated)
  29. * @base: uint32_t divisor
  30. *
  31. * Summary:
  32. * ``uint32_t remainder = n % base;``
  33. * ``n = n / base;``
  34. *
  35. * Return: (uint32_t)remainder
  36. *
  37. * NOTE: macro parameter @n is evaluated multiple times,
  38. * beware of side effects!
  39. */
  40. # define do_div(n,base) ({ \
  41. uint32_t __base = (base); \
  42. uint32_t __rem; \
  43. __rem = ((uint64_t)(n)) % __base; \
  44. (n) = ((uint64_t)(n)) / __base; \
  45. __rem; \
  46. })
  47. #elif BITS_PER_LONG == 32
  48. #include <linux/log2.h>
  49. /*
  50. * If the divisor happens to be constant, we determine the appropriate
  51. * inverse at compile time to turn the division into a few inline
  52. * multiplications which ought to be much faster. And yet only if compiling
  53. * with a sufficiently recent gcc version to perform proper 64-bit constant
  54. * propagation.
  55. *
  56. * (It is unfortunate that gcc doesn't perform all this internally.)
  57. */
  58. #ifndef __div64_const32_is_OK
  59. #define __div64_const32_is_OK (__GNUC__ >= 4)
  60. #endif
  61. #define __div64_const32(n, ___b) \
  62. ({ \
  63. /* \
  64. * Multiplication by reciprocal of b: n / b = n * (p / b) / p \
  65. * \
  66. * We rely on the fact that most of this code gets optimized \
  67. * away at compile time due to constant propagation and only \
  68. * a few multiplication instructions should remain. \
  69. * Hence this monstrous macro (static inline doesn't always \
  70. * do the trick here). \
  71. */ \
  72. uint64_t ___res, ___x, ___t, ___m, ___n = (n); \
  73. uint32_t ___p, ___bias; \
  74. \
  75. /* determine MSB of b */ \
  76. ___p = 1 << ilog2(___b); \
  77. \
  78. /* compute m = ((p << 64) + b - 1) / b */ \
  79. ___m = (~0ULL / ___b) * ___p; \
  80. ___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b; \
  81. \
  82. /* one less than the dividend with highest result */ \
  83. ___x = ~0ULL / ___b * ___b - 1; \
  84. \
  85. /* test our ___m with res = m * x / (p << 64) */ \
  86. ___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32; \
  87. ___t = ___res += (___m & 0xffffffff) * (___x >> 32); \
  88. ___res += (___x & 0xffffffff) * (___m >> 32); \
  89. ___t = (___res < ___t) ? (1ULL << 32) : 0; \
  90. ___res = (___res >> 32) + ___t; \
  91. ___res += (___m >> 32) * (___x >> 32); \
  92. ___res /= ___p; \
  93. \
  94. /* Now sanitize and optimize what we've got. */ \
  95. if (~0ULL % (___b / (___b & -___b)) == 0) { \
  96. /* special case, can be simplified to ... */ \
  97. ___n /= (___b & -___b); \
  98. ___m = ~0ULL / (___b / (___b & -___b)); \
  99. ___p = 1; \
  100. ___bias = 1; \
  101. } else if (___res != ___x / ___b) { \
  102. /* \
  103. * We can't get away without a bias to compensate \
  104. * for bit truncation errors. To avoid it we'd need an \
  105. * additional bit to represent m which would overflow \
  106. * a 64-bit variable. \
  107. * \
  108. * Instead we do m = p / b and n / b = (n * m + m) / p. \
  109. */ \
  110. ___bias = 1; \
  111. /* Compute m = (p << 64) / b */ \
  112. ___m = (~0ULL / ___b) * ___p; \
  113. ___m += ((~0ULL % ___b + 1) * ___p) / ___b; \
  114. } else { \
  115. /* \
  116. * Reduce m / p, and try to clear bit 31 of m when \
  117. * possible, otherwise that'll need extra overflow \
  118. * handling later. \
  119. */ \
  120. uint32_t ___bits = -(___m & -___m); \
  121. ___bits |= ___m >> 32; \
  122. ___bits = (~___bits) << 1; \
  123. /* \
  124. * If ___bits == 0 then setting bit 31 is unavoidable. \
  125. * Simply apply the maximum possible reduction in that \
  126. * case. Otherwise the MSB of ___bits indicates the \
  127. * best reduction we should apply. \
  128. */ \
  129. if (!___bits) { \
  130. ___p /= (___m & -___m); \
  131. ___m /= (___m & -___m); \
  132. } else { \
  133. ___p >>= ilog2(___bits); \
  134. ___m >>= ilog2(___bits); \
  135. } \
  136. /* No bias needed. */ \
  137. ___bias = 0; \
  138. } \
  139. \
  140. /* \
  141. * Now we have a combination of 2 conditions: \
  142. * \
  143. * 1) whether or not we need to apply a bias, and \
  144. * \
  145. * 2) whether or not there might be an overflow in the cross \
  146. * product determined by (___m & ((1 << 63) | (1 << 31))). \
  147. * \
  148. * Select the best way to do (m_bias + m * n) / (1 << 64). \
  149. * From now on there will be actual runtime code generated. \
  150. */ \
  151. ___res = __arch_xprod_64(___m, ___n, ___bias); \
  152. \
  153. ___res /= ___p; \
  154. })
  155. #ifndef __arch_xprod_64
  156. /*
  157. * Default C implementation for __arch_xprod_64()
  158. *
  159. * Prototype: uint64_t __arch_xprod_64(const uint64_t m, uint64_t n, bool bias)
  160. * Semantic: retval = ((bias ? m : 0) + m * n) >> 64
  161. *
  162. * The product is a 128-bit value, scaled down to 64 bits.
  163. * Assuming constant propagation to optimize away unused conditional code.
  164. * Architectures may provide their own optimized assembly implementation.
  165. */
  166. static inline uint64_t __arch_xprod_64(const uint64_t m, uint64_t n, bool bias)
  167. {
  168. uint32_t m_lo = m;
  169. uint32_t m_hi = m >> 32;
  170. uint32_t n_lo = n;
  171. uint32_t n_hi = n >> 32;
  172. uint64_t res;
  173. uint32_t res_lo, res_hi, tmp;
  174. if (!bias) {
  175. res = ((uint64_t)m_lo * n_lo) >> 32;
  176. } else if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
  177. /* there can't be any overflow here */
  178. res = (m + (uint64_t)m_lo * n_lo) >> 32;
  179. } else {
  180. res = m + (uint64_t)m_lo * n_lo;
  181. res_lo = res >> 32;
  182. res_hi = (res_lo < m_hi);
  183. res = res_lo | ((uint64_t)res_hi << 32);
  184. }
  185. if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
  186. /* there can't be any overflow here */
  187. res += (uint64_t)m_lo * n_hi;
  188. res += (uint64_t)m_hi * n_lo;
  189. res >>= 32;
  190. } else {
  191. res += (uint64_t)m_lo * n_hi;
  192. tmp = res >> 32;
  193. res += (uint64_t)m_hi * n_lo;
  194. res_lo = res >> 32;
  195. res_hi = (res_lo < tmp);
  196. res = res_lo | ((uint64_t)res_hi << 32);
  197. }
  198. res += (uint64_t)m_hi * n_hi;
  199. return res;
  200. }
  201. #endif
  202. #ifndef __div64_32
  203. extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
  204. #endif
  205. /* The unnecessary pointer compare is there
  206. * to check for type safety (n must be 64bit)
  207. */
  208. # define do_div(n,base) ({ \
  209. uint32_t __base = (base); \
  210. uint32_t __rem; \
  211. (void)(((typeof((n)) *)0) == ((uint64_t *)0)); \
  212. if (__builtin_constant_p(__base) && \
  213. is_power_of_2(__base)) { \
  214. __rem = (n) & (__base - 1); \
  215. (n) >>= ilog2(__base); \
  216. } else if (__div64_const32_is_OK && \
  217. __builtin_constant_p(__base) && \
  218. __base != 0) { \
  219. uint32_t __res_lo, __n_lo = (n); \
  220. (n) = __div64_const32(n, __base); \
  221. /* the remainder can be computed with 32-bit regs */ \
  222. __res_lo = (n); \
  223. __rem = __n_lo - __res_lo * __base; \
  224. } else if (likely(((n) >> 32) == 0)) { \
  225. __rem = (uint32_t)(n) % __base; \
  226. (n) = (uint32_t)(n) / __base; \
  227. } else \
  228. __rem = __div64_32(&(n), __base); \
  229. __rem; \
  230. })
  231. #else /* BITS_PER_LONG == ?? */
  232. # error do_div() does not yet support the C64
  233. #endif /* BITS_PER_LONG */
  234. #endif /* _ASM_GENERIC_DIV64_H */