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 | #ifndef CONFIG_INT128 |
30 | /* Long integer helpers */ |
31 | static inline void mul64(uint64_t *plow, uint64_t *phigh, |
32 | uint64_t a, uint64_t b) |
33 | { |
34 | typedef union { |
35 | uint64_t ll; |
36 | struct { |
37 | #ifdef HOST_WORDS_BIGENDIAN |
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; |
46 | |
47 | a0.ll = a; |
48 | b0.ll = b; |
49 | |
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; |
54 | |
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); |
61 | |
62 | *plow = rl.ll; |
63 | *phigh = rh.ll; |
64 | } |
65 | |
66 | /* Unsigned 64x64 -> 128 multiplication */ |
67 | void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b) |
68 | { |
69 | mul64(plow, phigh, a, b); |
70 | } |
71 | |
72 | /* Signed 64x64 -> 128 multiplication */ |
73 | void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b) |
74 | { |
75 | uint64_t rh; |
76 | |
77 | mul64(plow, &rh, a, b); |
78 | |
79 | /* Adjust for signs. */ |
80 | if (b < 0) { |
81 | rh -= a; |
82 | } |
83 | if (a < 0) { |
84 | rh -= b; |
85 | } |
86 | *phigh = rh; |
87 | } |
88 | |
89 | /* Unsigned 128x64 division. Returns 1 if overflow (divide by zero or */ |
90 | /* quotient exceeds 64 bits). Otherwise returns quotient via plow and */ |
91 | /* remainder via phigh. */ |
92 | int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) |
93 | { |
94 | uint64_t dhi = *phigh; |
95 | uint64_t dlo = *plow; |
96 | unsigned i; |
97 | uint64_t carry = 0; |
98 | |
99 | if (divisor == 0) { |
100 | return 1; |
101 | } else if (dhi == 0) { |
102 | *plow = dlo / divisor; |
103 | *phigh = dlo % divisor; |
104 | return 0; |
105 | } else if (dhi > divisor) { |
106 | return 1; |
107 | } else { |
108 | |
109 | for (i = 0; i < 64; i++) { |
110 | carry = dhi >> 63; |
111 | dhi = (dhi << 1) | (dlo >> 63); |
112 | if (carry || (dhi >= divisor)) { |
113 | dhi -= divisor; |
114 | carry = 1; |
115 | } else { |
116 | carry = 0; |
117 | } |
118 | dlo = (dlo << 1) | carry; |
119 | } |
120 | |
121 | *plow = dlo; |
122 | *phigh = dhi; |
123 | return 0; |
124 | } |
125 | } |
126 | |
127 | int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) |
128 | { |
129 | int sgn_dvdnd = *phigh < 0; |
130 | int sgn_divsr = divisor < 0; |
131 | int overflow = 0; |
132 | |
133 | if (sgn_dvdnd) { |
134 | *plow = ~(*plow); |
135 | *phigh = ~(*phigh); |
136 | if (*plow == (int64_t)-1) { |
137 | *plow = 0; |
138 | (*phigh)++; |
139 | } else { |
140 | (*plow)++; |
141 | } |
142 | } |
143 | |
144 | if (sgn_divsr) { |
145 | divisor = 0 - divisor; |
146 | } |
147 | |
148 | overflow = divu128((uint64_t *)plow, (uint64_t *)phigh, (uint64_t)divisor); |
149 | |
150 | if (sgn_dvdnd ^ sgn_divsr) { |
151 | *plow = 0 - *plow; |
152 | } |
153 | |
154 | if (!overflow) { |
155 | if ((*plow < 0) ^ (sgn_dvdnd ^ sgn_divsr)) { |
156 | overflow = 1; |
157 | } |
158 | } |
159 | |
160 | return overflow; |
161 | } |
162 | #endif |
163 | |
164 | /** |
165 | * urshift - 128-bit Unsigned Right Shift. |
166 | * @plow: in/out - lower 64-bit integer. |
167 | * @phigh: in/out - higher 64-bit integer. |
168 | * @shift: in - bytes to shift, between 0 and 127. |
169 | * |
170 | * Result is zero-extended and stored in plow/phigh, which are |
171 | * input/output variables. Shift values outside the range will |
172 | * be mod to 128. In other words, the caller is responsible to |
173 | * verify/assert both the shift range and plow/phigh pointers. |
174 | */ |
175 | void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift) |
176 | { |
177 | shift &= 127; |
178 | if (shift == 0) { |
179 | return; |
180 | } |
181 | |
182 | uint64_t h = *phigh >> (shift & 63); |
183 | if (shift >= 64) { |
184 | *plow = h; |
185 | *phigh = 0; |
186 | } else { |
187 | *plow = (*plow >> (shift & 63)) | (*phigh << (64 - (shift & 63))); |
188 | *phigh = h; |
189 | } |
190 | } |
191 | |
192 | /** |
193 | * ulshift - 128-bit Unsigned Left Shift. |
194 | * @plow: in/out - lower 64-bit integer. |
195 | * @phigh: in/out - higher 64-bit integer. |
196 | * @shift: in - bytes to shift, between 0 and 127. |
197 | * @overflow: out - true if any 1-bit is shifted out. |
198 | * |
199 | * Result is zero-extended and stored in plow/phigh, which are |
200 | * input/output variables. Shift values outside the range will |
201 | * be mod to 128. In other words, the caller is responsible to |
202 | * verify/assert both the shift range and plow/phigh pointers. |
203 | */ |
204 | void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow) |
205 | { |
206 | uint64_t low = *plow; |
207 | uint64_t high = *phigh; |
208 | |
209 | shift &= 127; |
210 | if (shift == 0) { |
211 | return; |
212 | } |
213 | |
214 | /* check if any bit will be shifted out */ |
215 | urshift(&low, &high, 128 - shift); |
216 | if (low | high) { |
217 | *overflow = true; |
218 | } |
219 | |
220 | if (shift >= 64) { |
221 | *phigh = *plow << (shift & 63); |
222 | *plow = 0; |
223 | } else { |
224 | *phigh = (*plow >> (64 - (shift & 63))) | (*phigh << (shift & 63)); |
225 | *plow = *plow << shift; |
226 | } |
227 | } |
228 | |