]>
Commit | Line | Data |
---|---|---|
69d35728 TS |
1 | /* |
2 | * Utility compute operations used by translated code. | |
3 | * | |
e494ead5 | 4 | * Copyright (c) 2003 Fabrice Bellard |
69d35728 TS |
5 | * Copyright (c) 2007 Aurelien Jarno |
6 | * | |
7 | * Permission is hereby granted, free of charge, to any person obtaining a copy | |
8 | * of this software and associated documentation files (the "Software"), to deal | |
9 | * in the Software without restriction, including without limitation the rights | |
10 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
11 | * copies of the Software, and to permit persons to whom the Software is | |
12 | * furnished to do so, subject to the following conditions: | |
13 | * | |
14 | * The above copyright notice and this permission notice shall be included in | |
15 | * all copies or substantial portions of the Software. | |
16 | * | |
17 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
18 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
19 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
20 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
21 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
22 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
23 | * THE SOFTWARE. | |
24 | */ | |
25 | ||
aafd7584 | 26 | #include "qemu/osdep.h" |
1de7afc9 | 27 | #include "qemu/host-utils.h" |
69d35728 | 28 | |
6758c192 | 29 | #ifndef CONFIG_INT128 |
e494ead5 | 30 | /* Long integer helpers */ |
ff7a1eb0 RH |
31 | static inline void mul64(uint64_t *plow, uint64_t *phigh, |
32 | uint64_t a, uint64_t b) | |
69d35728 | 33 | { |
ff7a1eb0 RH |
34 | typedef union { |
35 | uint64_t ll; | |
36 | struct { | |
e03b5686 | 37 | #if HOST_BIG_ENDIAN |
ff7a1eb0 RH |
38 | uint32_t high, low; |
39 | #else | |
40 | uint32_t low, high; | |
41 | #endif | |
42 | } l; | |
43 | } LL; | |
44 | LL rl, rm, rn, rh, a0, b0; | |
45 | uint64_t c; | |
e494ead5 | 46 | |
ff7a1eb0 RH |
47 | a0.ll = a; |
48 | b0.ll = b; | |
e494ead5 | 49 | |
ff7a1eb0 RH |
50 | rl.ll = (uint64_t)a0.l.low * b0.l.low; |
51 | rm.ll = (uint64_t)a0.l.low * b0.l.high; | |
52 | rn.ll = (uint64_t)a0.l.high * b0.l.low; | |
53 | rh.ll = (uint64_t)a0.l.high * b0.l.high; | |
e494ead5 | 54 | |
ff7a1eb0 RH |
55 | c = (uint64_t)rl.l.high + rm.l.low + rn.l.low; |
56 | rl.l.high = c; | |
57 | c >>= 32; | |
58 | c = c + rm.l.high + rn.l.high + rh.l.low; | |
59 | rh.l.low = c; | |
60 | rh.l.high += (uint32_t)(c >> 32); | |
e494ead5 | 61 | |
ff7a1eb0 RH |
62 | *plow = rl.ll; |
63 | *phigh = rh.ll; | |
69d35728 TS |
64 | } |
65 | ||
66 | /* Unsigned 64x64 -> 128 multiplication */ | |
e494ead5 | 67 | void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b) |
69d35728 | 68 | { |
e494ead5 | 69 | mul64(plow, phigh, a, b); |
e494ead5 | 70 | } |
69d35728 | 71 | |
e494ead5 TS |
72 | /* Signed 64x64 -> 128 multiplication */ |
73 | void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b) | |
74 | { | |
ff7a1eb0 | 75 | uint64_t rh; |
69d35728 | 76 | |
ff7a1eb0 RH |
77 | mul64(plow, &rh, a, b); |
78 | ||
79 | /* Adjust for signs. */ | |
80 | if (b < 0) { | |
81 | rh -= a; | |
e494ead5 | 82 | } |
ff7a1eb0 RH |
83 | if (a < 0) { |
84 | rh -= b; | |
85 | } | |
86 | *phigh = rh; | |
69d35728 | 87 | } |
98d1eb27 | 88 | |
9276a31c | 89 | /* |
40f3e79a LP |
90 | * Unsigned 128-by-64 division. |
91 | * Returns the remainder. | |
92 | * Returns quotient via plow and phigh. | |
93 | * Also returns the remainder via the function return value. | |
9276a31c | 94 | */ |
40f3e79a | 95 | uint64_t divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) |
98d1eb27 TM |
96 | { |
97 | uint64_t dhi = *phigh; | |
98 | uint64_t dlo = *plow; | |
40f3e79a LP |
99 | uint64_t rem, dhighest; |
100 | int sh; | |
98d1eb27 | 101 | |
9276a31c | 102 | if (divisor == 0 || dhi == 0) { |
98d1eb27 | 103 | *plow = dlo / divisor; |
40f3e79a LP |
104 | *phigh = 0; |
105 | return dlo % divisor; | |
98d1eb27 | 106 | } else { |
40f3e79a LP |
107 | sh = clz64(divisor); |
108 | ||
109 | if (dhi < divisor) { | |
110 | if (sh != 0) { | |
111 | /* normalize the divisor, shifting the dividend accordingly */ | |
112 | divisor <<= sh; | |
113 | dhi = (dhi << sh) | (dlo >> (64 - sh)); | |
114 | dlo <<= sh; | |
115 | } | |
98d1eb27 | 116 | |
40f3e79a LP |
117 | *phigh = 0; |
118 | *plow = udiv_qrnnd(&rem, dhi, dlo, divisor); | |
119 | } else { | |
120 | if (sh != 0) { | |
121 | /* normalize the divisor, shifting the dividend accordingly */ | |
122 | divisor <<= sh; | |
123 | dhighest = dhi >> (64 - sh); | |
124 | dhi = (dhi << sh) | (dlo >> (64 - sh)); | |
125 | dlo <<= sh; | |
126 | ||
127 | *phigh = udiv_qrnnd(&dhi, dhighest, dhi, divisor); | |
98d1eb27 | 128 | } else { |
40f3e79a LP |
129 | /** |
130 | * dhi >= divisor | |
131 | * Since the MSB of divisor is set (sh == 0), | |
132 | * (dhi - divisor) < divisor | |
133 | * | |
134 | * Thus, the high part of the quotient is 1, and we can | |
135 | * calculate the low part with a single call to udiv_qrnnd | |
136 | * after subtracting divisor from dhi | |
137 | */ | |
138 | dhi -= divisor; | |
139 | *phigh = 1; | |
98d1eb27 | 140 | } |
40f3e79a LP |
141 | |
142 | *plow = udiv_qrnnd(&rem, dhi, dlo, divisor); | |
98d1eb27 TM |
143 | } |
144 | ||
40f3e79a LP |
145 | /* |
146 | * since the dividend/divisor might have been normalized, | |
147 | * the remainder might also have to be shifted back | |
148 | */ | |
149 | return rem >> sh; | |
98d1eb27 TM |
150 | } |
151 | } | |
e44259b6 | 152 | |
9276a31c | 153 | /* |
40f3e79a LP |
154 | * Signed 128-by-64 division. |
155 | * Returns quotient via plow and phigh. | |
156 | * Also returns the remainder via the function return value. | |
9276a31c | 157 | */ |
40f3e79a | 158 | int64_t divs128(uint64_t *plow, int64_t *phigh, int64_t divisor) |
e44259b6 | 159 | { |
40f3e79a LP |
160 | bool neg_quotient = false, neg_remainder = false; |
161 | uint64_t unsig_hi = *phigh, unsig_lo = *plow; | |
162 | uint64_t rem; | |
163 | ||
164 | if (*phigh < 0) { | |
165 | neg_quotient = !neg_quotient; | |
166 | neg_remainder = !neg_remainder; | |
167 | ||
168 | if (unsig_lo == 0) { | |
169 | unsig_hi = -unsig_hi; | |
170 | } else { | |
171 | unsig_hi = ~unsig_hi; | |
172 | unsig_lo = -unsig_lo; | |
173 | } | |
e44259b6 TM |
174 | } |
175 | ||
40f3e79a LP |
176 | if (divisor < 0) { |
177 | neg_quotient = !neg_quotient; | |
178 | ||
179 | divisor = -divisor; | |
e44259b6 TM |
180 | } |
181 | ||
40f3e79a | 182 | rem = divu128(&unsig_lo, &unsig_hi, (uint64_t)divisor); |
e44259b6 | 183 | |
40f3e79a LP |
184 | if (neg_quotient) { |
185 | if (unsig_lo == 0) { | |
186 | *phigh = -unsig_hi; | |
187 | *plow = 0; | |
188 | } else { | |
189 | *phigh = ~unsig_hi; | |
190 | *plow = -unsig_lo; | |
191 | } | |
192 | } else { | |
193 | *phigh = unsig_hi; | |
194 | *plow = unsig_lo; | |
195 | } | |
196 | ||
197 | if (neg_remainder) { | |
198 | return -rem; | |
199 | } else { | |
200 | return rem; | |
e44259b6 | 201 | } |
e44259b6 | 202 | } |
6758c192 | 203 | #endif |
e44259b6 | 204 | |
f539fbe3 JRZ |
205 | /** |
206 | * urshift - 128-bit Unsigned Right Shift. | |
207 | * @plow: in/out - lower 64-bit integer. | |
208 | * @phigh: in/out - higher 64-bit integer. | |
209 | * @shift: in - bytes to shift, between 0 and 127. | |
210 | * | |
211 | * Result is zero-extended and stored in plow/phigh, which are | |
212 | * input/output variables. Shift values outside the range will | |
213 | * be mod to 128. In other words, the caller is responsible to | |
214 | * verify/assert both the shift range and plow/phigh pointers. | |
215 | */ | |
216 | void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift) | |
217 | { | |
218 | shift &= 127; | |
219 | if (shift == 0) { | |
220 | return; | |
221 | } | |
222 | ||
223 | uint64_t h = *phigh >> (shift & 63); | |
224 | if (shift >= 64) { | |
225 | *plow = h; | |
226 | *phigh = 0; | |
227 | } else { | |
228 | *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); | |
229 | *phigh = h; | |
230 | } | |
231 | } | |
232 | ||
233 | /** | |
234 | * ulshift - 128-bit Unsigned Left Shift. | |
235 | * @plow: in/out - lower 64-bit integer. | |
236 | * @phigh: in/out - higher 64-bit integer. | |
237 | * @shift: in - bytes to shift, between 0 and 127. | |
238 | * @overflow: out - true if any 1-bit is shifted out. | |
239 | * | |
240 | * Result is zero-extended and stored in plow/phigh, which are | |
241 | * input/output variables. Shift values outside the range will | |
242 | * be mod to 128. In other words, the caller is responsible to | |
243 | * verify/assert both the shift range and plow/phigh pointers. | |
244 | */ | |
245 | void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow) | |
246 | { | |
247 | uint64_t low = *plow; | |
248 | uint64_t high = *phigh; | |
249 | ||
250 | shift &= 127; | |
251 | if (shift == 0) { | |
252 | return; | |
253 | } | |
254 | ||
255 | /* check if any bit will be shifted out */ | |
256 | urshift(&low, &high, 128 - shift); | |
257 | if (low | high) { | |
258 | *overflow = true; | |
259 | } | |
260 | ||
261 | if (shift >= 64) { | |
262 | *phigh = *plow << (shift & 63); | |
263 | *plow = 0; | |
264 | } else { | |
265 | *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); | |
266 | *plow = *plow << shift; | |
267 | } | |
268 | } | |
4724bbd2 LMC |
269 | |
270 | /* | |
271 | * Unsigned 256-by-128 division. | |
272 | * Returns the remainder via r. | |
273 | * Returns lower 128 bit of quotient. | |
274 | * Needs a normalized divisor (most significant bit set to 1). | |
275 | * | |
276 | * Adapted from include/qemu/host-utils.h udiv_qrnnd, | |
277 | * from the GNU Multi Precision Library - longlong.h __udiv_qrnnd | |
278 | * (https://gmplib.org/repo/gmp/file/tip/longlong.h) | |
279 | * | |
280 | * Licensed under the GPLv2/LGPLv3 | |
281 | */ | |
282 | static Int128 udiv256_qrnnd(Int128 *r, Int128 n1, Int128 n0, Int128 d) | |
283 | { | |
284 | Int128 d0, d1, q0, q1, r1, r0, m; | |
285 | uint64_t mp0, mp1; | |
286 | ||
287 | d0 = int128_make64(int128_getlo(d)); | |
288 | d1 = int128_make64(int128_gethi(d)); | |
289 | ||
290 | r1 = int128_remu(n1, d1); | |
291 | q1 = int128_divu(n1, d1); | |
292 | mp0 = int128_getlo(q1); | |
293 | mp1 = int128_gethi(q1); | |
294 | mulu128(&mp0, &mp1, int128_getlo(d0)); | |
295 | m = int128_make128(mp0, mp1); | |
296 | r1 = int128_make128(int128_gethi(n0), int128_getlo(r1)); | |
297 | if (int128_ult(r1, m)) { | |
298 | q1 = int128_sub(q1, int128_one()); | |
299 | r1 = int128_add(r1, d); | |
300 | if (int128_uge(r1, d)) { | |
301 | if (int128_ult(r1, m)) { | |
302 | q1 = int128_sub(q1, int128_one()); | |
303 | r1 = int128_add(r1, d); | |
304 | } | |
305 | } | |
306 | } | |
307 | r1 = int128_sub(r1, m); | |
308 | ||
309 | r0 = int128_remu(r1, d1); | |
310 | q0 = int128_divu(r1, d1); | |
311 | mp0 = int128_getlo(q0); | |
312 | mp1 = int128_gethi(q0); | |
313 | mulu128(&mp0, &mp1, int128_getlo(d0)); | |
314 | m = int128_make128(mp0, mp1); | |
315 | r0 = int128_make128(int128_getlo(n0), int128_getlo(r0)); | |
316 | if (int128_ult(r0, m)) { | |
317 | q0 = int128_sub(q0, int128_one()); | |
318 | r0 = int128_add(r0, d); | |
319 | if (int128_uge(r0, d)) { | |
320 | if (int128_ult(r0, m)) { | |
321 | q0 = int128_sub(q0, int128_one()); | |
322 | r0 = int128_add(r0, d); | |
323 | } | |
324 | } | |
325 | } | |
326 | r0 = int128_sub(r0, m); | |
327 | ||
328 | *r = r0; | |
329 | return int128_or(int128_lshift(q1, 64), q0); | |
330 | } | |
331 | ||
332 | /* | |
333 | * Unsigned 256-by-128 division. | |
334 | * Returns the remainder. | |
335 | * Returns quotient via plow and phigh. | |
336 | * Also returns the remainder via the function return value. | |
337 | */ | |
338 | Int128 divu256(Int128 *plow, Int128 *phigh, Int128 divisor) | |
339 | { | |
340 | Int128 dhi = *phigh; | |
341 | Int128 dlo = *plow; | |
342 | Int128 rem, dhighest; | |
343 | int sh; | |
344 | ||
345 | if (!int128_nz(divisor) || !int128_nz(dhi)) { | |
346 | *plow = int128_divu(dlo, divisor); | |
347 | *phigh = int128_zero(); | |
348 | return int128_remu(dlo, divisor); | |
349 | } else { | |
350 | sh = clz128(divisor); | |
351 | ||
352 | if (int128_ult(dhi, divisor)) { | |
353 | if (sh != 0) { | |
354 | /* normalize the divisor, shifting the dividend accordingly */ | |
355 | divisor = int128_lshift(divisor, sh); | |
356 | dhi = int128_or(int128_lshift(dhi, sh), | |
357 | int128_urshift(dlo, (128 - sh))); | |
358 | dlo = int128_lshift(dlo, sh); | |
359 | } | |
360 | ||
361 | *phigh = int128_zero(); | |
362 | *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); | |
363 | } else { | |
364 | if (sh != 0) { | |
365 | /* normalize the divisor, shifting the dividend accordingly */ | |
366 | divisor = int128_lshift(divisor, sh); | |
367 | dhighest = int128_rshift(dhi, (128 - sh)); | |
368 | dhi = int128_or(int128_lshift(dhi, sh), | |
369 | int128_urshift(dlo, (128 - sh))); | |
370 | dlo = int128_lshift(dlo, sh); | |
371 | ||
372 | *phigh = udiv256_qrnnd(&dhi, dhighest, dhi, divisor); | |
373 | } else { | |
374 | /* | |
375 | * dhi >= divisor | |
376 | * Since the MSB of divisor is set (sh == 0), | |
377 | * (dhi - divisor) < divisor | |
378 | * | |
379 | * Thus, the high part of the quotient is 1, and we can | |
380 | * calculate the low part with a single call to udiv_qrnnd | |
381 | * after subtracting divisor from dhi | |
382 | */ | |
383 | dhi = int128_sub(dhi, divisor); | |
384 | *phigh = int128_one(); | |
385 | } | |
386 | ||
387 | *plow = udiv256_qrnnd(&rem, dhi, dlo, divisor); | |
388 | } | |
389 | ||
390 | /* | |
391 | * since the dividend/divisor might have been normalized, | |
392 | * the remainder might also have to be shifted back | |
393 | */ | |
394 | rem = int128_urshift(rem, sh); | |
395 | return rem; | |
396 | } | |
397 | } | |
62c9947f LMC |
398 | |
399 | /* | |
400 | * Signed 256-by-128 division. | |
401 | * Returns quotient via plow and phigh. | |
402 | * Also returns the remainder via the function return value. | |
403 | */ | |
404 | Int128 divs256(Int128 *plow, Int128 *phigh, Int128 divisor) | |
405 | { | |
406 | bool neg_quotient = false, neg_remainder = false; | |
407 | Int128 unsig_hi = *phigh, unsig_lo = *plow; | |
408 | Int128 rem; | |
409 | ||
410 | if (!int128_nonneg(*phigh)) { | |
411 | neg_quotient = !neg_quotient; | |
412 | neg_remainder = !neg_remainder; | |
413 | ||
414 | if (!int128_nz(unsig_lo)) { | |
415 | unsig_hi = int128_neg(unsig_hi); | |
416 | } else { | |
417 | unsig_hi = int128_not(unsig_hi); | |
418 | unsig_lo = int128_neg(unsig_lo); | |
419 | } | |
420 | } | |
421 | ||
422 | if (!int128_nonneg(divisor)) { | |
423 | neg_quotient = !neg_quotient; | |
424 | ||
425 | divisor = int128_neg(divisor); | |
426 | } | |
427 | ||
428 | rem = divu256(&unsig_lo, &unsig_hi, divisor); | |
429 | ||
430 | if (neg_quotient) { | |
431 | if (!int128_nz(unsig_lo)) { | |
432 | *phigh = int128_neg(unsig_hi); | |
433 | *plow = int128_zero(); | |
434 | } else { | |
435 | *phigh = int128_not(unsig_hi); | |
436 | *plow = int128_neg(unsig_lo); | |
437 | } | |
438 | } else { | |
439 | *phigh = unsig_hi; | |
440 | *plow = unsig_lo; | |
441 | } | |
442 | ||
443 | if (neg_remainder) { | |
444 | return int128_neg(rem); | |
445 | } else { | |
446 | return rem; | |
447 | } | |
448 | } |