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