math64.h 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257
  1. #ifndef _LINUX_MATH64_H
  2. #define _LINUX_MATH64_H
  3. #include <div64.h>
  4. #include <linux/bitops.h>
  5. #include <linux/types.h>
  6. #if BITS_PER_LONG == 64
  7. #define div64_long(x, y) div64_s64((x), (y))
  8. #define div64_ul(x, y) div64_u64((x), (y))
  9. /**
  10. * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
  11. *
  12. * This is commonly provided by 32bit archs to provide an optimized 64bit
  13. * divide.
  14. */
  15. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
  16. {
  17. *remainder = dividend % divisor;
  18. return dividend / divisor;
  19. }
  20. /**
  21. * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
  22. */
  23. static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
  24. {
  25. *remainder = dividend % divisor;
  26. return dividend / divisor;
  27. }
  28. /**
  29. * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
  30. */
  31. static inline u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
  32. {
  33. *remainder = dividend % divisor;
  34. return dividend / divisor;
  35. }
  36. /**
  37. * div64_u64 - unsigned 64bit divide with 64bit divisor
  38. */
  39. static inline u64 div64_u64(u64 dividend, u64 divisor)
  40. {
  41. return dividend / divisor;
  42. }
  43. /**
  44. * div64_s64 - signed 64bit divide with 64bit divisor
  45. */
  46. static inline s64 div64_s64(s64 dividend, s64 divisor)
  47. {
  48. return dividend / divisor;
  49. }
  50. #elif BITS_PER_LONG == 32
  51. #define div64_long(x, y) div_s64((x), (y))
  52. #define div64_ul(x, y) div_u64((x), (y))
  53. #ifndef div_u64_rem
  54. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
  55. {
  56. *remainder = do_div(dividend, divisor);
  57. return dividend;
  58. }
  59. #endif
  60. #ifndef div_s64_rem
  61. extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
  62. #endif
  63. #ifndef div64_u64_rem
  64. extern u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder);
  65. #endif
  66. #ifndef div64_u64
  67. extern u64 div64_u64(u64 dividend, u64 divisor);
  68. #endif
  69. #ifndef div64_s64
  70. extern s64 div64_s64(s64 dividend, s64 divisor);
  71. #endif
  72. #endif /* BITS_PER_LONG */
  73. /**
  74. * div_u64 - unsigned 64bit divide with 32bit divisor
  75. *
  76. * This is the most common 64bit divide and should be used if possible,
  77. * as many 32bit archs can optimize this variant better than a full 64bit
  78. * divide.
  79. */
  80. #ifndef div_u64
  81. static inline u64 div_u64(u64 dividend, u32 divisor)
  82. {
  83. u32 remainder;
  84. return div_u64_rem(dividend, divisor, &remainder);
  85. }
  86. #endif
  87. /**
  88. * div_s64 - signed 64bit divide with 32bit divisor
  89. */
  90. #ifndef div_s64
  91. static inline s64 div_s64(s64 dividend, s32 divisor)
  92. {
  93. s32 remainder;
  94. return div_s64_rem(dividend, divisor, &remainder);
  95. }
  96. #endif
  97. u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder);
  98. static __always_inline u32
  99. __iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
  100. {
  101. u32 ret = 0;
  102. while (dividend >= divisor) {
  103. /* The following asm() prevents the compiler from
  104. optimising this loop into a modulo operation. */
  105. asm("" : "+rm"(dividend));
  106. dividend -= divisor;
  107. ret++;
  108. }
  109. *remainder = dividend;
  110. return ret;
  111. }
  112. #ifndef mul_u32_u32
  113. /*
  114. * Many a GCC version messes this up and generates a 64x64 mult :-(
  115. */
  116. static inline u64 mul_u32_u32(u32 a, u32 b)
  117. {
  118. return (u64)a * b;
  119. }
  120. #endif
  121. #if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
  122. #ifndef mul_u64_u32_shr
  123. static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
  124. {
  125. return (u64)(((unsigned __int128)a * mul) >> shift);
  126. }
  127. #endif /* mul_u64_u32_shr */
  128. #ifndef mul_u64_u64_shr
  129. static inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift)
  130. {
  131. return (u64)(((unsigned __int128)a * mul) >> shift);
  132. }
  133. #endif /* mul_u64_u64_shr */
  134. #else
  135. #ifndef mul_u64_u32_shr
  136. static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
  137. {
  138. u32 ah, al;
  139. u64 ret;
  140. al = a;
  141. ah = a >> 32;
  142. ret = mul_u32_u32(al, mul) >> shift;
  143. if (ah)
  144. ret += mul_u32_u32(ah, mul) << (32 - shift);
  145. return ret;
  146. }
  147. #endif /* mul_u64_u32_shr */
  148. #ifndef mul_u64_u64_shr
  149. static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift)
  150. {
  151. union {
  152. u64 ll;
  153. struct {
  154. #ifdef __BIG_ENDIAN
  155. u32 high, low;
  156. #else
  157. u32 low, high;
  158. #endif
  159. } l;
  160. } rl, rm, rn, rh, a0, b0;
  161. u64 c;
  162. a0.ll = a;
  163. b0.ll = b;
  164. rl.ll = mul_u32_u32(a0.l.low, b0.l.low);
  165. rm.ll = mul_u32_u32(a0.l.low, b0.l.high);
  166. rn.ll = mul_u32_u32(a0.l.high, b0.l.low);
  167. rh.ll = mul_u32_u32(a0.l.high, b0.l.high);
  168. /*
  169. * Each of these lines computes a 64-bit intermediate result into "c",
  170. * starting at bits 32-95. The low 32-bits go into the result of the
  171. * multiplication, the high 32-bits are carried into the next step.
  172. */
  173. rl.l.high = c = (u64)rl.l.high + rm.l.low + rn.l.low;
  174. rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low;
  175. rh.l.high = (c >> 32) + rh.l.high;
  176. /*
  177. * The 128-bit result of the multiplication is in rl.ll and rh.ll,
  178. * shift it right and throw away the high part of the result.
  179. */
  180. if (shift == 0)
  181. return rl.ll;
  182. if (shift < 64)
  183. return (rl.ll >> shift) | (rh.ll << (64 - shift));
  184. return rh.ll >> (shift & 63);
  185. }
  186. #endif /* mul_u64_u64_shr */
  187. #endif
  188. #ifndef mul_u64_u32_div
  189. static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 divisor)
  190. {
  191. union {
  192. u64 ll;
  193. struct {
  194. #ifdef __BIG_ENDIAN
  195. u32 high, low;
  196. #else
  197. u32 low, high;
  198. #endif
  199. } l;
  200. } u, rl, rh;
  201. u.ll = a;
  202. rl.ll = mul_u32_u32(u.l.low, mul);
  203. rh.ll = mul_u32_u32(u.l.high, mul) + rl.l.high;
  204. /* Bits 32-63 of the result will be in rh.l.low. */
  205. rl.l.high = do_div(rh.ll, divisor);
  206. /* Bits 0-31 of the result will be in rl.l.low. */
  207. do_div(rl.ll, divisor);
  208. rl.l.high = rh.l.low;
  209. return rl.ll;
  210. }
  211. #endif /* mul_u64_u32_div */
  212. #endif /* _LINUX_MATH64_H */