1 /* 2 * Utility compute operations used by translated code. 3 * 4 * Copyright (c) 2003 Fabrice Bellard 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 26 #include "qemu/osdep.h" 27 #include "qemu/host-utils.h" 28 29 /* Long integer helpers */ 30 static inline void mul64(uint64_t *plow, uint64_t *phigh, 31 uint64_t a, uint64_t b) 32 { 33 typedef union { 34 uint64_t ll; 35 struct { 36 #ifdef HOST_WORDS_BIGENDIAN 37 uint32_t high, low; 38 #else 39 uint32_t low, high; 40 #endif 41 } l; 42 } LL; 43 LL rl, rm, rn, rh, a0, b0; 44 uint64_t c; 45 46 a0.ll = a; 47 b0.ll = b; 48 49 rl.ll = (uint64_t)a0.l.low * b0.l.low; 50 rm.ll = (uint64_t)a0.l.low * b0.l.high; 51 rn.ll = (uint64_t)a0.l.high * b0.l.low; 52 rh.ll = (uint64_t)a0.l.high * b0.l.high; 53 54 c = (uint64_t)rl.l.high + rm.l.low + rn.l.low; 55 rl.l.high = c; 56 c >>= 32; 57 c = c + rm.l.high + rn.l.high + rh.l.low; 58 rh.l.low = c; 59 rh.l.high += (uint32_t)(c >> 32); 60 61 *plow = rl.ll; 62 *phigh = rh.ll; 63 } 64 65 /* Unsigned 64x64 -> 128 multiplication */ 66 void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b) 67 { 68 mul64(plow, phigh, a, b); 69 } 70 71 /* Signed 64x64 -> 128 multiplication */ 72 void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b) 73 { 74 uint64_t rh; 75 76 mul64(plow, &rh, a, b); 77 78 /* Adjust for signs. */ 79 if (b < 0) { 80 rh -= a; 81 } 82 if (a < 0) { 83 rh -= b; 84 } 85 *phigh = rh; 86 } 87 88 /* Unsigned 128x64 division. Returns 1 if overflow (divide by zero or */ 89 /* quotient exceeds 64 bits). Otherwise returns quotient via plow and */ 90 /* remainder via phigh. */ 91 int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) 92 { 93 uint64_t dhi = *phigh; 94 uint64_t dlo = *plow; 95 unsigned i; 96 uint64_t carry = 0; 97 98 if (divisor == 0) { 99 return 1; 100 } else if (dhi == 0) { 101 *plow = dlo / divisor; 102 *phigh = dlo % divisor; 103 return 0; 104 } else if (dhi > divisor) { 105 return 1; 106 } else { 107 108 for (i = 0; i < 64; i++) { 109 carry = dhi >> 63; 110 dhi = (dhi << 1) | (dlo >> 63); 111 if (carry || (dhi >= divisor)) { 112 dhi -= divisor; 113 carry = 1; 114 } else { 115 carry = 0; 116 } 117 dlo = (dlo << 1) | carry; 118 } 119 120 *plow = dlo; 121 *phigh = dhi; 122 return 0; 123 } 124 } 125 126 int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) 127 { 128 int sgn_dvdnd = *phigh < 0; 129 int sgn_divsr = divisor < 0; 130 int overflow = 0; 131 132 if (sgn_dvdnd) { 133 *plow = ~(*plow); 134 *phigh = ~(*phigh); 135 if (*plow == (int64_t)-1) { 136 *plow = 0; 137 (*phigh)++; 138 } else { 139 (*plow)++; 140 } 141 } 142 143 if (sgn_divsr) { 144 divisor = 0 - divisor; 145 } 146 147 overflow = divu128((uint64_t *)plow, (uint64_t *)phigh, (uint64_t)divisor); 148 149 if (sgn_dvdnd ^ sgn_divsr) { 150 *plow = 0 - *plow; 151 } 152 153 if (!overflow) { 154 if ((*plow < 0) ^ (sgn_dvdnd ^ sgn_divsr)) { 155 overflow = 1; 156 } 157 } 158 159 return overflow; 160 } 161 162