diff options
Diffstat (limited to 'util/int128.c')
| -rw-r--r-- | util/int128.c | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/util/int128.c b/util/int128.c new file mode 100644 index 0000000000..ed8f25fef1 --- /dev/null +++ b/util/int128.c @@ -0,0 +1,147 @@ +/* + * 128-bit division and remainder for compilers not supporting __int128 + * + * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "qemu/osdep.h" +#include "qemu/host-utils.h" +#include "qemu/int128.h" + +#ifndef CONFIG_INT128 + +/* + * Division and remainder algorithms for 128-bit due to Stefan Kanthak, + * https://skanthak.homepage.t-online.de/integer.html#udivmodti4 + * Preconditions: + * - function should never be called with v equals to 0, it has to + * be dealt with beforehand + * - quotien pointer must be valid + */ +static Int128 divrem128(Int128 u, Int128 v, Int128 *q) +{ + Int128 qq; + uint64_t hi, lo, tmp; + int s = clz64(v.hi); + + if (s == 64) { + /* we have uu÷0v => let's use divu128 */ + hi = u.hi; + lo = u.lo; + tmp = divu128(&lo, &hi, v.lo); + *q = int128_make128(lo, hi); + return int128_make128(tmp, 0); + } else { + hi = int128_gethi(int128_lshift(v, s)); + + if (hi > u.hi) { + lo = u.lo; + tmp = u.hi; + divu128(&lo, &tmp, hi); + lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s)); + } else { /* prevent overflow */ + lo = u.lo; + tmp = u.hi - hi; + divu128(&lo, &tmp, hi); + lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s)); + } + + qq = int128_make64(lo); + + tmp = lo * v.hi; + mulu64(&lo, &hi, lo, v.lo); + hi += tmp; + + if (hi < tmp /* quotient * divisor >= 2**128 > dividend */ + || hi > u.hi /* quotient * divisor > dividend */ + || (hi == u.hi && lo > u.lo)) { + qq.lo -= 1; + mulu64(&lo, &hi, qq.lo, v.lo); + hi += qq.lo * v.hi; + } + + *q = qq; + u.hi -= hi + (u.lo < lo); + u.lo -= lo; + return u; + } +} + +Int128 int128_divu(Int128 a, Int128 b) +{ + Int128 q; + divrem128(a, b, &q); + return q; +} + +Int128 int128_remu(Int128 a, Int128 b) +{ + Int128 q; + return divrem128(a, b, &q); +} + +Int128 int128_divs(Int128 a, Int128 b) +{ + Int128 q; + bool sgna = !int128_nonneg(a); + bool sgnb = !int128_nonneg(b); + + if (sgna) { + a = int128_neg(a); + } + + if (sgnb) { + b = int128_neg(b); + } + + divrem128(a, b, &q); + + if (sgna != sgnb) { + q = int128_neg(q); + } + + return q; +} + +Int128 int128_rems(Int128 a, Int128 b) +{ + Int128 q, r; + bool sgna = !int128_nonneg(a); + bool sgnb = !int128_nonneg(b); + + if (sgna) { + a = int128_neg(a); + } + + if (sgnb) { + b = int128_neg(b); + } + + r = divrem128(a, b, &q); + + if (sgna) { + r = int128_neg(r); + } + + return r; +} + +#endif |