1 | // SPDX-License-Identifier: GPL-2.0 |
---|---|

2 | /* |

3 | * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com> |

4 | * |

5 | * Based on former do_div() implementation from asm-parisc/div64.h: |

6 | * Copyright (C) 1999 Hewlett-Packard Co |

7 | * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com> |

8 | * |

9 | * |

10 | * Generic C version of 64bit/32bit division and modulo, with |

11 | * 64bit result and 32bit remainder. |

12 | * |

13 | * The fast case for (n>>32 == 0) is handled inline by do_div(). |

14 | * |

15 | * Code generated for this function might be very inefficient |

16 | * for some CPUs. __div64_32() can be overridden by linking arch-specific |

17 | * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S |

18 | * or by defining a preprocessor macro in arch/include/asm/div64.h. |

19 | */ |

20 | |

21 | #include <linux/export.h> |

22 | #include <linux/kernel.h> |

23 | #include <linux/math64.h> |

24 | |

25 | /* Not needed on 64bit architectures */ |

26 | #if BITS_PER_LONG == 32 |

27 | |

28 | #ifndef __div64_32 |

29 | uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base) |

30 | { |

31 | uint64_t rem = *n; |

32 | uint64_t b = base; |

33 | uint64_t res, d = 1; |

34 | uint32_t high = rem >> 32; |

35 | |

36 | /* Reduce the thing a bit first */ |

37 | res = 0; |

38 | if (high >= base) { |

39 | high /= base; |

40 | res = (uint64_t) high << 32; |

41 | rem -= (uint64_t) (high*base) << 32; |

42 | } |

43 | |

44 | while ((int64_t)b > 0 && b < rem) { |

45 | b = b+b; |

46 | d = d+d; |

47 | } |

48 | |

49 | do { |

50 | if (rem >= b) { |

51 | rem -= b; |

52 | res += d; |

53 | } |

54 | b >>= 1; |

55 | d >>= 1; |

56 | } while (d); |

57 | |

58 | *n = res; |

59 | return rem; |

60 | } |

61 | EXPORT_SYMBOL(__div64_32); |

62 | #endif |

63 | |

64 | /** |

65 | * div_s64_rem - signed 64bit divide with 64bit divisor and remainder |

66 | * @dividend: 64bit dividend |

67 | * @divisor: 64bit divisor |

68 | * @remainder: 64bit remainder |

69 | */ |

70 | #ifndef div_s64_rem |

71 | s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) |

72 | { |

73 | u64 quotient; |

74 | |

75 | if (dividend < 0) { |

76 | quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder); |

77 | *remainder = -*remainder; |

78 | if (divisor > 0) |

79 | quotient = -quotient; |

80 | } else { |

81 | quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder); |

82 | if (divisor < 0) |

83 | quotient = -quotient; |

84 | } |

85 | return quotient; |

86 | } |

87 | EXPORT_SYMBOL(div_s64_rem); |

88 | #endif |

89 | |

90 | /** |

91 | * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder |

92 | * @dividend: 64bit dividend |

93 | * @divisor: 64bit divisor |

94 | * @remainder: 64bit remainder |

95 | * |

96 | * This implementation is a comparable to algorithm used by div64_u64. |

97 | * But this operation, which includes math for calculating the remainder, |

98 | * is kept distinct to avoid slowing down the div64_u64 operation on 32bit |

99 | * systems. |

100 | */ |

101 | #ifndef div64_u64_rem |

102 | u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) |

103 | { |

104 | u32 high = divisor >> 32; |

105 | u64 quot; |

106 | |

107 | if (high == 0) { |

108 | u32 rem32; |

109 | quot = div_u64_rem(dividend, divisor, &rem32); |

110 | *remainder = rem32; |

111 | } else { |

112 | int n = fls(high); |

113 | quot = div_u64(dividend >> n, divisor >> n); |

114 | |

115 | if (quot != 0) |

116 | quot--; |

117 | |

118 | *remainder = dividend - quot * divisor; |

119 | if (*remainder >= divisor) { |

120 | quot++; |

121 | *remainder -= divisor; |

122 | } |

123 | } |

124 | |

125 | return quot; |

126 | } |

127 | EXPORT_SYMBOL(div64_u64_rem); |

128 | #endif |

129 | |

130 | /** |

131 | * div64_u64 - unsigned 64bit divide with 64bit divisor |

132 | * @dividend: 64bit dividend |

133 | * @divisor: 64bit divisor |

134 | * |

135 | * This implementation is a modified version of the algorithm proposed |

136 | * by the book 'Hacker's Delight'. The original source and full proof |

137 | * can be found here and is available for use without restriction. |

138 | * |

139 | * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt' |

140 | */ |

141 | #ifndef div64_u64 |

142 | u64 div64_u64(u64 dividend, u64 divisor) |

143 | { |

144 | u32 high = divisor >> 32; |

145 | u64 quot; |

146 | |

147 | if (high == 0) { |

148 | quot = div_u64(dividend, divisor); |

149 | } else { |

150 | int n = fls(high); |

151 | quot = div_u64(dividend >> n, divisor >> n); |

152 | |

153 | if (quot != 0) |

154 | quot--; |

155 | if ((dividend - quot * divisor) >= divisor) |

156 | quot++; |

157 | } |

158 | |

159 | return quot; |

160 | } |

161 | EXPORT_SYMBOL(div64_u64); |

162 | #endif |

163 | |

164 | /** |

165 | * div64_s64 - signed 64bit divide with 64bit divisor |

166 | * @dividend: 64bit dividend |

167 | * @divisor: 64bit divisor |

168 | */ |

169 | #ifndef div64_s64 |

170 | s64 div64_s64(s64 dividend, s64 divisor) |

171 | { |

172 | s64 quot, t; |

173 | |

174 | quot = div64_u64(abs(dividend), abs(divisor)); |

175 | t = (dividend ^ divisor) >> 63; |

176 | |

177 | return (quot ^ t) - t; |

178 | } |

179 | EXPORT_SYMBOL(div64_s64); |

180 | #endif |

181 | |

182 | #endif /* BITS_PER_LONG == 32 */ |

183 | |

184 | /* |

185 | * Iterative div/mod for use when dividend is not expected to be much |

186 | * bigger than divisor. |

187 | */ |

188 | u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder) |

189 | { |

190 | return __iter_div_u64_rem(dividend, divisor, remainder); |

191 | } |

192 | EXPORT_SYMBOL(iter_div_u64_rem); |

193 |