div64.h 6.9 KB

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