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