1 /* 2 * 128-bit division and remainder for compilers not supporting __int128 3 * 4 * Copyright (c) 2021 Frédéric Pétrot <frederic.petrot@univ-grenoble-alpes.fr> 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to deal 8 * in the Software without restriction, including without limitation the rights 9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in 14 * all copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 22 * THE SOFTWARE. 23 */ 24 25 #include "qemu/osdep.h" 26 #include "qemu/host-utils.h" 27 #include "qemu/int128.h" 28 29 #ifndef CONFIG_INT128 30 31 /* 32 * Division and remainder algorithms for 128-bit due to Stefan Kanthak, 33 * https://skanthak.homepage.t-online.de/integer.html#udivmodti4 34 * Preconditions: 35 * - function should never be called with v equals to 0, it has to 36 * be dealt with beforehand 37 * - quotien pointer must be valid 38 */ 39 static Int128 divrem128(Int128 u, Int128 v, Int128 *q) 40 { 41 Int128 qq; 42 uint64_t hi, lo, tmp; 43 int s = clz64(v.hi); 44 45 if (s == 64) { 46 /* we have uu÷0v => let's use divu128 */ 47 hi = u.hi; 48 lo = u.lo; 49 tmp = divu128(&lo, &hi, v.lo); 50 *q = int128_make128(lo, hi); 51 return int128_make128(tmp, 0); 52 } else { 53 hi = int128_gethi(int128_lshift(v, s)); 54 55 if (hi > u.hi) { 56 lo = u.lo; 57 tmp = u.hi; 58 divu128(&lo, &tmp, hi); 59 lo = int128_gethi(int128_lshift(int128_make128(lo, 0), s)); 60 } else { /* prevent overflow */ 61 lo = u.lo; 62 tmp = u.hi - hi; 63 divu128(&lo, &tmp, hi); 64 lo = int128_gethi(int128_lshift(int128_make128(lo, 1), s)); 65 } 66 67 qq = int128_make64(lo); 68 69 tmp = lo * v.hi; 70 mulu64(&lo, &hi, lo, v.lo); 71 hi += tmp; 72 73 if (hi < tmp /* quotient * divisor >= 2**128 > dividend */ 74 || hi > u.hi /* quotient * divisor > dividend */ 75 || (hi == u.hi && lo > u.lo)) { 76 qq.lo -= 1; 77 mulu64(&lo, &hi, qq.lo, v.lo); 78 hi += qq.lo * v.hi; 79 } 80 81 *q = qq; 82 u.hi -= hi + (u.lo < lo); 83 u.lo -= lo; 84 return u; 85 } 86 } 87 88 Int128 int128_divu(Int128 a, Int128 b) 89 { 90 Int128 q; 91 divrem128(a, b, &q); 92 return q; 93 } 94 95 Int128 int128_remu(Int128 a, Int128 b) 96 { 97 Int128 q; 98 return divrem128(a, b, &q); 99 } 100 101 Int128 int128_divs(Int128 a, Int128 b) 102 { 103 Int128 q; 104 bool sgna = !int128_nonneg(a); 105 bool sgnb = !int128_nonneg(b); 106 107 if (sgna) { 108 a = int128_neg(a); 109 } 110 111 if (sgnb) { 112 b = int128_neg(b); 113 } 114 115 divrem128(a, b, &q); 116 117 if (sgna != sgnb) { 118 q = int128_neg(q); 119 } 120 121 return q; 122 } 123 124 Int128 int128_rems(Int128 a, Int128 b) 125 { 126 Int128 q, r; 127 bool sgna = !int128_nonneg(a); 128 bool sgnb = !int128_nonneg(b); 129 130 if (sgna) { 131 a = int128_neg(a); 132 } 133 134 if (sgnb) { 135 b = int128_neg(b); 136 } 137 138 r = divrem128(a, b, &q); 139 140 if (sgna) { 141 r = int128_neg(r); 142 } 143 144 return r; 145 } 146 147 #endif 148