1 /* SPDX-License-Identifier: GPL-2.0 */ 1
2 #ifndef _ASM_GENERIC_DIV64_H
3 #define _ASM_GENERIC_DIV64_H
4 /*
5 * Copyright (C) 2003 Bernardo Innocenti <bern
6 * Based on former asm-ppc/div64.h and asm-m68
7 *
8 * Optimization for constant divisors on 32-bi
9 * Copyright (C) 2006-2015 Nicolas Pitre
10 *
11 * The semantics of do_div() is, in C++ notati
12 * is a function-like macro and the n paramete
13 * reference:
14 *
15 * uint32_t do_div(uint64_t &n, uint32_t base)
16 * {
17 * uint32_t remainder = n % base;
18 * n = n / base;
19 * return remainder;
20 * }
21 *
22 * NOTE: macro parameter n is evaluated multip
23 * beware of side effects!
24 */
25
26 #include <linux/types.h>
27 #include <linux/compiler.h>
28
29 #if BITS_PER_LONG == 64
30
31 /**
32 * do_div - returns 2 values: calculate remain
33 * @n: uint64_t dividend (will be updated)
34 * @base: uint32_t divisor
35 *
36 * Summary:
37 * ``uint32_t remainder = n % base;``
38 * ``n = n / base;``
39 *
40 * Return: (uint32_t)remainder
41 *
42 * NOTE: macro parameter @n is evaluated multi
43 * beware of side effects!
44 */
45 # define do_div(n,base) ({
46 uint32_t __base = (base);
47 uint32_t __rem;
48 __rem = ((uint64_t)(n)) % __base;
49 (n) = ((uint64_t)(n)) / __base;
50 __rem;
51 })
52
53 #elif BITS_PER_LONG == 32
54
55 #include <linux/log2.h>
56
57 /*
58 * If the divisor happens to be constant, we d
59 * inverse at compile time to turn the divisio
60 * multiplications which ought to be much fast
61 *
62 * (It is unfortunate that gcc doesn't perform
63 */
64
65 #define __div64_const32(n, ___b)
66 ({
67 /*
68 * Multiplication by reciprocal of b:
69 *
70 * We rely on the fact that most of th
71 * away at compile time due to constan
72 * a few multiplication instructions s
73 * Hence this monstrous macro (static
74 * do the trick here).
75 */
76 uint64_t ___res, ___x, ___t, ___m, ___
77 uint32_t ___p, ___bias;
78
79 /* determine MSB of b */
80 ___p = 1 << ilog2(___b);
81
82 /* compute m = ((p << 64) + b - 1) / b
83 ___m = (~0ULL / ___b) * ___p;
84 ___m += (((~0ULL % ___b + 1) * ___p) +
85
86 /* one less than the dividend with hig
87 ___x = ~0ULL / ___b * ___b - 1;
88
89 /* test our ___m with res = m * x / (p
90 ___res = ((___m & 0xffffffff) * (___x
91 ___t = ___res += (___m & 0xffffffff) *
92 ___res += (___x & 0xffffffff) * (___m
93 ___t = (___res < ___t) ? (1ULL << 32)
94 ___res = (___res >> 32) + ___t;
95 ___res += (___m >> 32) * (___x >> 32);
96 ___res /= ___p;
97
98 /* Now sanitize and optimize what we'v
99 if (~0ULL % (___b / (___b & -___b)) ==
100 /* special case, can be simpli
101 ___n /= (___b & -___b);
102 ___m = ~0ULL / (___b / (___b &
103 ___p = 1;
104 ___bias = 1;
105 } else if (___res != ___x / ___b) {
106 /*
107 * We can't get away without a
108 * for bit truncation errors.
109 * additional bit to represent
110 * a 64-bit variable.
111 *
112 * Instead we do m = p / b and
113 */
114 ___bias = 1;
115 /* Compute m = (p << 64) / b *
116 ___m = (~0ULL / ___b) * ___p;
117 ___m += ((~0ULL % ___b + 1) *
118 } else {
119 /*
120 * Reduce m / p, and try to cl
121 * possible, otherwise that'll
122 * handling later.
123 */
124 uint32_t ___bits = -(___m & -_
125 ___bits |= ___m >> 32;
126 ___bits = (~___bits) << 1;
127 /*
128 * If ___bits == 0 then settin
129 * Simply apply the maximum po
130 * case. Otherwise the MSB of
131 * best reduction we should ap
132 */
133 if (!___bits) {
134 ___p /= (___m & -___m)
135 ___m /= (___m & -___m)
136 } else {
137 ___p >>= ilog2(___bits
138 ___m >>= ilog2(___bits
139 }
140 /* No bias needed. */
141 ___bias = 0;
142 }
143
144 /*
145 * Now we have a combination of 2 cond
146 *
147 * 1) whether or not we need to apply
148 *
149 * 2) whether or not there might be an
150 * product determined by (___m & ((
151 *
152 * Select the best way to do (m_bias +
153 * From now on there will be actual ru
154 */
155 ___res = __arch_xprod_64(___m, ___n, _
156
157 ___res /= ___p;
158 })
159
160 #ifndef __arch_xprod_64
161 /*
162 * Default C implementation for __arch_xprod_6
163 *
164 * Prototype: uint64_t __arch_xprod_64(const u
165 * Semantic: retval = ((bias ? m : 0) + m * n
166 *
167 * The product is a 128-bit value, scaled down
168 * Assuming constant propagation to optimize a
169 * Architectures may provide their own optimiz
170 */
171 static inline uint64_t __arch_xprod_64(const u
172 {
173 uint32_t m_lo = m;
174 uint32_t m_hi = m >> 32;
175 uint32_t n_lo = n;
176 uint32_t n_hi = n >> 32;
177 uint64_t res;
178 uint32_t res_lo, res_hi, tmp;
179
180 if (!bias) {
181 res = ((uint64_t)m_lo * n_lo)
182 } else if (!(m & ((1ULL << 63) | (1ULL
183 /* there can't be any overflow
184 res = (m + (uint64_t)m_lo * n_
185 } else {
186 res = m + (uint64_t)m_lo * n_l
187 res_lo = res >> 32;
188 res_hi = (res_lo < m_hi);
189 res = res_lo | ((uint64_t)res_
190 }
191
192 if (!(m & ((1ULL << 63) | (1ULL << 31)
193 /* there can't be any overflow
194 res += (uint64_t)m_lo * n_hi;
195 res += (uint64_t)m_hi * n_lo;
196 res >>= 32;
197 } else {
198 res += (uint64_t)m_lo * n_hi;
199 tmp = res >> 32;
200 res += (uint64_t)m_hi * n_lo;
201 res_lo = res >> 32;
202 res_hi = (res_lo < tmp);
203 res = res_lo | ((uint64_t)res_
204 }
205
206 res += (uint64_t)m_hi * n_hi;
207
208 return res;
209 }
210 #endif
211
212 #ifndef __div64_32
213 extern uint32_t __div64_32(uint64_t *dividend,
214 #endif
215
216 /* The unnecessary pointer compare is there
217 * to check for type safety (n must be 64bit)
218 */
219 # define do_div(n,base) ({
220 uint32_t __base = (base);
221 uint32_t __rem;
222 (void)(((typeof((n)) *)0) == ((uint64_
223 if (__builtin_constant_p(__base) &&
224 is_power_of_2(__base)) {
225 __rem = (n) & (__base - 1);
226 (n) >>= ilog2(__base);
227 } else if (__builtin_constant_p(__base
228 __base != 0) {
229 uint32_t __res_lo, __n_lo = (n
230 (n) = __div64_const32(n, __bas
231 /* the remainder can be comput
232 __res_lo = (n);
233 __rem = __n_lo - __res_lo * __
234 } else if (likely(((n) >> 32) == 0)) {
235 __rem = (uint32_t)(n) % __base
236 (n) = (uint32_t)(n) / __base;
237 } else {
238 __rem = __div64_32(&(n), __bas
239 }
240 __rem;
241 })
242
243 #else /* BITS_PER_LONG == ?? */
244
245 # error do_div() does not yet support the C64
246
247 #endif /* BITS_PER_LONG */
248
249 #endif /* _ASM_GENERIC_DIV64_H */
250
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.