aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorBrian Behlendorf <behlendorf1@llnl.gov>2010-10-26 17:23:10 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2010-10-26 19:52:19 -0400
commit658716d19f8f155c67d4677ba68034b8e492dfbe (patch)
tree8743b9a16606a63dc33f93c580367baf36692454 /lib
parent5d051decfc27cdf33fbbd2bfca958d0d2c903569 (diff)
div64_u64(): improve precision on 32bit platforms
The current implementation of div64_u64 for 32bit systems returns an approximately correct result when the divisor exceeds 32bits. Since doing 64bit division using 32bit hardware is a long since solved problem we just use one of the existing proven methods. Additionally, add a div64_s64 function to correctly handle doing signed 64bit division. Addresses https://bugzilla.redhat.com/show_bug.cgi?id=616105 Signed-off-by: Brian Behlendorf <behlendorf1@llnl.gov> Signed-off-by: Oleg Nesterov <oleg@redhat.com> Cc: Ben Woodard <bwoodard@llnl.gov> Cc: Jeremy Fitzhardinge <jeremy@goop.org> Cc: Mark Grondona <mgrondona@llnl.gov> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/div64.c52
1 files changed, 42 insertions, 10 deletions
diff --git a/lib/div64.c b/lib/div64.c
index a111eb8de9cf..5b4919191778 100644
--- a/lib/div64.c
+++ b/lib/div64.c
@@ -77,26 +77,58 @@ s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
77EXPORT_SYMBOL(div_s64_rem); 77EXPORT_SYMBOL(div_s64_rem);
78#endif 78#endif
79 79
80/* 64bit divisor, dividend and result. dynamic precision */ 80/**
81 * div64_u64 - unsigned 64bit divide with 64bit divisor
82 * @dividend: 64bit dividend
83 * @divisor: 64bit divisor
84 *
85 * This implementation is a modified version of the algorithm proposed
86 * by the book 'Hacker's Delight'. The original source and full proof
87 * can be found here and is available for use without restriction.
88 *
89 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c'
90 */
81#ifndef div64_u64 91#ifndef div64_u64
82u64 div64_u64(u64 dividend, u64 divisor) 92u64 div64_u64(u64 dividend, u64 divisor)
83{ 93{
84 u32 high, d; 94 u32 high = divisor >> 32;
95 u64 quot;
85 96
86 high = divisor >> 32; 97 if (high == 0) {
87 if (high) { 98 quot = div_u64(dividend, divisor);
88 unsigned int shift = fls(high); 99 } else {
100 int n = 1 + fls(high);
101 quot = div_u64(dividend >> n, divisor >> n);
89 102
90 d = divisor >> shift; 103 if (quot != 0)
91 dividend >>= shift; 104 quot--;
92 } else 105 if ((dividend - quot * divisor) >= divisor)
93 d = divisor; 106 quot++;
107 }
94 108
95 return div_u64(dividend, d); 109 return quot;
96} 110}
97EXPORT_SYMBOL(div64_u64); 111EXPORT_SYMBOL(div64_u64);
98#endif 112#endif
99 113
114/**
115 * div64_s64 - signed 64bit divide with 64bit divisor
116 * @dividend: 64bit dividend
117 * @divisor: 64bit divisor
118 */
119#ifndef div64_s64
120s64 div64_s64(s64 dividend, s64 divisor)
121{
122 s64 quot, t;
123
124 quot = div64_u64(abs64(dividend), abs64(divisor));
125 t = (dividend ^ divisor) >> 63;
126
127 return (quot ^ t) - t;
128}
129EXPORT_SYMBOL(div64_s64);
130#endif
131
100#endif /* BITS_PER_LONG == 32 */ 132#endif /* BITS_PER_LONG == 32 */
101 133
102/* 134/*