sched: Slightly fix up tests/prov
[akaros.git] / kern / include / math64.h
1 /* Copyright (C) 1991-2016, the Linux Kernel authors
2  *
3  * This source code is licensed under the GNU General Public License
4  * Version 2. See the file COPYING for more details.
5  */
6
7 #pragma once
8
9 #include <sys/types.h>
10 #include <arch/div64.h>
11
12 #if BITS_PER_LONG == 64
13
14 #define div64_long(x, y) div64_s64((x), (y))
15 #define div64_ul(x, y)   div64_u64((x), (y))
16
17 /**
18  * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
19  *
20  * This is commonly provided by 32bit archs to provide an optimized 64bit
21  * divide.
22  */
23 static inline uint64_t div_u64_rem(uint64_t dividend, uint32_t divisor,
24                                    uint32_t *remainder)
25 {
26         *remainder = dividend % divisor;
27         return dividend / divisor;
28 }
29
30 /**
31  * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
32  */
33 static inline int64_t div_s64_rem(int64_t dividend, int32_t divisor,
34                                   int32_t *remainder)
35 {
36         *remainder = dividend % divisor;
37         return dividend / divisor;
38 }
39
40 /**
41  * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
42  */
43 static inline uint64_t div64_u64_rem(uint64_t dividend, uint64_t divisor,
44                                      uint64_t *remainder)
45 {
46         *remainder = dividend % divisor;
47         return dividend / divisor;
48 }
49
50 /**
51  * div64_u64 - unsigned 64bit divide with 64bit divisor
52  */
53 static inline uint64_t div64_u64(uint64_t dividend, uint64_t divisor)
54 {
55         return dividend / divisor;
56 }
57
58 /**
59  * div64_s64 - signed 64bit divide with 64bit divisor
60  */
61 static inline int64_t div64_s64(int64_t dividend, int64_t divisor)
62 {
63         return dividend / divisor;
64 }
65
66 #elif BITS_PER_LONG == 32
67
68 #define div64_long(x, y) div_s64((x), (y))
69 #define div64_ul(x, y)   div_u64((x), (y))
70
71 #ifndef div_u64_rem
72 static inline uint64_t div_u64_rem(uint64_t dividend, uint32_t divisor,
73                                    uint32_t *remainder)
74 {
75         *remainder = do_div(dividend, divisor);
76         return dividend;
77 }
78 #endif
79
80 #ifndef div_s64_rem
81 extern int64_t div_s64_rem(int64_t dividend, int32_t divisor,
82                            int32_t *remainder);
83 #endif
84
85 #ifndef div64_u64_rem
86 extern uint64_t div64_u64_rem(uint64_t dividend, uint64_t divisor,
87                               uint64_t *remainder);
88 #endif
89
90 #ifndef div64_u64
91 extern uint64_t div64_u64(uint64_t dividend, uint64_t divisor);
92 #endif
93
94 #ifndef div64_s64
95 extern int64_t div64_s64(int64_t dividend, int64_t divisor);
96 #endif
97
98 #endif /* BITS_PER_LONG */
99
100 /**
101  * div_u64 - unsigned 64bit divide with 32bit divisor
102  *
103  * This is the most common 64bit divide and should be used if possible,
104  * as many 32bit archs can optimize this variant better than a full 64bit
105  * divide.
106  */
107 #ifndef div_u64
108 static inline uint64_t div_u64(uint64_t dividend, uint32_t divisor)
109 {
110         uint32_t remainder;
111         return div_u64_rem(dividend, divisor, &remainder);
112 }
113 #endif
114
115 /**
116  * div_s64 - signed 64bit divide with 32bit divisor
117  */
118 #ifndef div_s64
119 static inline int64_t div_s64(int64_t dividend, int32_t divisor)
120 {
121         int32_t remainder;
122         return div_s64_rem(dividend, divisor, &remainder);
123 }
124 #endif
125
126 uint32_t iter_div_u64_rem(uint64_t dividend, uint32_t divisor,
127                           uint64_t *remainder);
128
129 static __always_inline uint32_t
130 __iter_div_u64_rem(uint64_t dividend, uint32_t divisor, uint64_t *remainder)
131 {
132         uint32_t ret = 0;
133
134         while (dividend >= divisor) {
135                 /* The following asm() prevents the compiler from
136                    optimising this loop into a modulo operation.  */
137                 asm("" : "+rm"(dividend));
138
139                 dividend -= divisor;
140                 ret++;
141         }
142
143         *remainder = dividend;
144
145         return ret;
146 }
147
148 #ifndef mul_u32_u32
149 /*
150  * Many a GCC version messes this up and generates a 64x64 mult :-(
151  */
152 static inline uint64_t mul_u32_u32(uint32_t a, uint32_t b)
153 {
154         return (uint64_t)a * b;
155 }
156 #endif
157
158 #if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
159
160 #ifndef mul_u64_u32_shr
161 static inline uint64_t mul_u64_u32_shr(uint64_t a, uint32_t mul,
162                                        unsigned int shift)
163 {
164         return (uint64_t)(((unsigned __int128)a * mul) >> shift);
165 }
166 #endif /* mul_u64_u32_shr */
167
168 #ifndef mul_u64_u64_shr
169 static inline uint64_t mul_u64_u64_shr(uint64_t a, uint64_t mul,
170                                        unsigned int shift)
171 {
172         return (uint64_t)(((unsigned __int128)a * mul) >> shift);
173 }
174 #endif /* mul_u64_u64_shr */
175
176 #else
177
178 #ifndef mul_u64_u32_shr
179 static inline uint64_t mul_u64_u32_shr(uint64_t a, uint32_t mul,
180                                        unsigned int shift)
181 {
182         uint32_t ah, al;
183         uint64_t ret;
184
185         al = a;
186         ah = a >> 32;
187
188         ret = mul_u32_u32(al, mul) >> shift;
189         if (ah)
190                 ret += mul_u32_u32(ah, mul) << (32 - shift);
191
192         return ret;
193 }
194 #endif /* mul_u64_u32_shr */
195
196 #ifndef mul_u64_u64_shr
197 static inline uint64_t mul_u64_u64_shr(uint64_t a, uint64_t b,
198                                        unsigned int shift)
199 {
200         union {
201                 uint64_t ll;
202                 struct {
203 #ifdef __BIG_ENDIAN
204                         uint32_t high, low;
205 #else
206                         uint32_t low, high;
207 #endif
208                 } l;
209         } rl, rm, rn, rh, a0, b0;
210         uint64_t c;
211
212         a0.ll = a;
213         b0.ll = b;
214
215         rl.ll = mul_u32_u32(a0.l.low, b0.l.low);
216         rm.ll = mul_u32_u32(a0.l.low, b0.l.high);
217         rn.ll = mul_u32_u32(a0.l.high, b0.l.low);
218         rh.ll = mul_u32_u32(a0.l.high, b0.l.high);
219
220         /*
221          * Each of these lines computes a 64-bit intermediate result into "c",
222          * starting at bits 32-95.  The low 32-bits go into the result of the
223          * multiplication, the high 32-bits are carried into the next step.
224          */
225         rl.l.high = c = (uint64_t)rl.l.high + rm.l.low + rn.l.low;
226         rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low;
227         rh.l.high = (c >> 32) + rh.l.high;
228
229         /*
230          * The 128-bit result of the multiplication is in rl.ll and rh.ll,
231          * shift it right and throw away the high part of the result.
232          */
233         if (shift == 0)
234                 return rl.ll;
235         if (shift < 64)
236                 return (rl.ll >> shift) | (rh.ll << (64 - shift));
237         return rh.ll >> (shift & 63);
238 }
239 #endif /* mul_u64_u64_shr */
240
241 #endif
242
243 #ifndef mul_u64_u32_div
244 static inline uint64_t mul_u64_u32_div(uint64_t a, uint32_t mul,
245                                        uint32_t divisor)
246 {
247         union {
248                 uint64_t ll;
249                 struct {
250 #ifdef __BIG_ENDIAN
251                         uint32_t high, low;
252 #else
253                         uint32_t low, high;
254 #endif
255                 } l;
256         } u, rl, rh;
257
258         u.ll = a;
259         rl.ll = mul_u32_u32(u.l.low, mul);
260         rh.ll = mul_u32_u32(u.l.high, mul) + rl.l.high;
261
262         /* Bits 32-63 of the result will be in rh.l.low. */
263         rl.l.high = do_div(rh.ll, divisor);
264
265         /* Bits 0-31 of the result will be in rl.l.low. */
266         do_div(rl.ll, divisor);
267
268         rl.l.high = rh.l.low;
269         return rl.ll;
270 }
271 #endif /* mul_u64_u32_div */