div64.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185
  1. /*
  2. * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
  3. *
  4. * Based on former do_div() implementation from asm-parisc/div64.h:
  5. * Copyright (C) 1999 Hewlett-Packard Co
  6. * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
  7. *
  8. *
  9. * Generic C version of 64bit/32bit division and modulo, with
  10. * 64bit result and 32bit remainder.
  11. *
  12. * The fast case for (n>>32 == 0) is handled inline by do_div().
  13. *
  14. * Code generated for this function might be very inefficient
  15. * for some CPUs. __div64_32() can be overridden by linking arch-specific
  16. * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S
  17. * or by defining a preprocessor macro in arch/include/asm/div64.h.
  18. */
  19. #include <linux/compat.h>
  20. #include <linux/kernel.h>
  21. #include <linux/math64.h>
  22. /* Not needed on 64bit architectures */
  23. #if BITS_PER_LONG == 32
  24. #ifndef __div64_32
  25. u32 __attribute__((weak)) __div64_32(u64 *n, u32 base)
  26. {
  27. u64 rem = *n;
  28. u64 b = base;
  29. u64 res, d = 1;
  30. u32 high = rem >> 32;
  31. /* Reduce the thing a bit first */
  32. res = 0;
  33. if (high >= base) {
  34. high /= base;
  35. res = (u64)high << 32;
  36. rem -= (u64)(high * base) << 32;
  37. }
  38. while ((int64_t)b > 0 && b < rem) {
  39. b = b+b;
  40. d = d+d;
  41. }
  42. do {
  43. if (rem >= b) {
  44. rem -= b;
  45. res += d;
  46. }
  47. b >>= 1;
  48. d >>= 1;
  49. } while (d);
  50. *n = res;
  51. return rem;
  52. }
  53. EXPORT_SYMBOL(__div64_32);
  54. #endif
  55. #ifndef div_s64_rem
  56. s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
  57. {
  58. u64 quotient;
  59. if (dividend < 0) {
  60. quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
  61. *remainder = -*remainder;
  62. if (divisor > 0)
  63. quotient = -quotient;
  64. } else {
  65. quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
  66. if (divisor < 0)
  67. quotient = -quotient;
  68. }
  69. return quotient;
  70. }
  71. EXPORT_SYMBOL(div_s64_rem);
  72. #endif
  73. /**
  74. * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
  75. * @dividend: 64bit dividend
  76. * @divisor: 64bit divisor
  77. * @remainder: 64bit remainder
  78. *
  79. * This implementation is a comparable to algorithm used by div64_u64.
  80. * But this operation, which includes math for calculating the remainder,
  81. * is kept distinct to avoid slowing down the div64_u64 operation on 32bit
  82. * systems.
  83. */
  84. #ifndef div64_u64_rem
  85. u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
  86. {
  87. u32 high = divisor >> 32;
  88. u64 quot;
  89. if (high == 0) {
  90. u32 rem32;
  91. quot = div_u64_rem(dividend, divisor, &rem32);
  92. *remainder = rem32;
  93. } else {
  94. int n = 1 + fls(high);
  95. quot = div_u64(dividend >> n, divisor >> n);
  96. if (quot != 0)
  97. quot--;
  98. *remainder = dividend - quot * divisor;
  99. if (*remainder >= divisor) {
  100. quot++;
  101. *remainder -= divisor;
  102. }
  103. }
  104. return quot;
  105. }
  106. EXPORT_SYMBOL(div64_u64_rem);
  107. #endif
  108. /**
  109. * div64_u64 - unsigned 64bit divide with 64bit divisor
  110. * @dividend: 64bit dividend
  111. * @divisor: 64bit divisor
  112. *
  113. * This implementation is a modified version of the algorithm proposed
  114. * by the book 'Hacker's Delight'. The original source and full proof
  115. * can be found here and is available for use without restriction.
  116. *
  117. * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt'
  118. */
  119. #ifndef div64_u64
  120. u64 div64_u64(u64 dividend, u64 divisor)
  121. {
  122. u32 high = divisor >> 32;
  123. u64 quot;
  124. if (high == 0) {
  125. quot = div_u64(dividend, divisor);
  126. } else {
  127. int n = 1 + fls(high);
  128. quot = div_u64(dividend >> n, divisor >> n);
  129. if (quot != 0)
  130. quot--;
  131. if ((dividend - quot * divisor) >= divisor)
  132. quot++;
  133. }
  134. return quot;
  135. }
  136. EXPORT_SYMBOL(div64_u64);
  137. #endif
  138. /**
  139. * div64_s64 - signed 64bit divide with 64bit divisor
  140. * @dividend: 64bit dividend
  141. * @divisor: 64bit divisor
  142. */
  143. #ifndef div64_s64
  144. s64 div64_s64(s64 dividend, s64 divisor)
  145. {
  146. s64 quot, t;
  147. quot = div64_u64(abs(dividend), abs(divisor));
  148. t = (dividend ^ divisor) >> 63;
  149. return (quot ^ t) - t;
  150. }
  151. EXPORT_SYMBOL(div64_s64);
  152. #endif
  153. #endif /* BITS_PER_LONG == 32 */
  154. /*
  155. * Iterative div/mod for use when dividend is not expected to be much
  156. * bigger than divisor.
  157. */
  158. u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
  159. {
  160. return __iter_div_u64_rem(dividend, divisor, remainder);
  161. }
  162. EXPORT_SYMBOL(iter_div_u64_rem);