]>
Commit | Line | Data |
---|---|---|
05f778c8 TS |
1 | /* |
2 | * Utility compute operations used by translated code. | |
3 | * | |
4 | * Copyright (c) 2007 Thiemo Seufer | |
5 | * Copyright (c) 2007 Jocelyn Mayer | |
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 | */ | |
cb9c377f PB |
25 | #ifndef HOST_UTILS_H |
26 | #define HOST_UTILS_H 1 | |
05f778c8 | 27 | |
1de7afc9 | 28 | #include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */ |
4c37ef02 | 29 | #include <string.h> /* ffsl */ |
cebdff77 | 30 | |
7a51ad82 JM |
31 | #if defined(__x86_64__) |
32 | #define __HAVE_FAST_MULU64__ | |
facd2857 BS |
33 | static inline void mulu64(uint64_t *plow, uint64_t *phigh, |
34 | uint64_t a, uint64_t b) | |
7a51ad82 JM |
35 | { |
36 | __asm__ ("mul %0\n\t" | |
37 | : "=d" (*phigh), "=a" (*plow) | |
38 | : "a" (a), "0" (b)); | |
39 | } | |
40 | #define __HAVE_FAST_MULS64__ | |
facd2857 BS |
41 | static inline void muls64(uint64_t *plow, uint64_t *phigh, |
42 | int64_t a, int64_t b) | |
7a51ad82 JM |
43 | { |
44 | __asm__ ("imul %0\n\t" | |
45 | : "=d" (*phigh), "=a" (*plow) | |
46 | : "a" (a), "0" (b)); | |
47 | } | |
48 | #else | |
05e1d830 | 49 | void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b); |
7a51ad82 JM |
50 | void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); |
51 | #endif | |
52 | ||
05f778c8 TS |
53 | /* Binary search for leading zeros. */ |
54 | ||
facd2857 | 55 | static inline int clz32(uint32_t val) |
05f778c8 | 56 | { |
bad5b1ec | 57 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
58 | if (val) |
59 | return __builtin_clz(val); | |
60 | else | |
61 | return 32; | |
62 | #else | |
05f778c8 TS |
63 | int cnt = 0; |
64 | ||
65 | if (!(val & 0xFFFF0000U)) { | |
66 | cnt += 16; | |
67 | val <<= 16; | |
68 | } | |
69 | if (!(val & 0xFF000000U)) { | |
70 | cnt += 8; | |
71 | val <<= 8; | |
72 | } | |
73 | if (!(val & 0xF0000000U)) { | |
74 | cnt += 4; | |
75 | val <<= 4; | |
76 | } | |
77 | if (!(val & 0xC0000000U)) { | |
78 | cnt += 2; | |
79 | val <<= 2; | |
80 | } | |
81 | if (!(val & 0x80000000U)) { | |
82 | cnt++; | |
83 | val <<= 1; | |
84 | } | |
85 | if (!(val & 0x80000000U)) { | |
86 | cnt++; | |
87 | } | |
88 | return cnt; | |
7d019980 | 89 | #endif |
05f778c8 TS |
90 | } |
91 | ||
facd2857 | 92 | static inline int clo32(uint32_t val) |
05f778c8 TS |
93 | { |
94 | return clz32(~val); | |
95 | } | |
96 | ||
facd2857 | 97 | static inline int clz64(uint64_t val) |
05f778c8 | 98 | { |
bad5b1ec | 99 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
100 | if (val) |
101 | return __builtin_clzll(val); | |
102 | else | |
103 | return 64; | |
104 | #else | |
05f778c8 TS |
105 | int cnt = 0; |
106 | ||
7a51ad82 | 107 | if (!(val >> 32)) { |
05f778c8 | 108 | cnt += 32; |
7a51ad82 JM |
109 | } else { |
110 | val >>= 32; | |
05f778c8 | 111 | } |
7a51ad82 JM |
112 | |
113 | return cnt + clz32(val); | |
7d019980 | 114 | #endif |
05f778c8 TS |
115 | } |
116 | ||
facd2857 | 117 | static inline int clo64(uint64_t val) |
05f778c8 TS |
118 | { |
119 | return clz64(~val); | |
120 | } | |
b9ef45ff | 121 | |
facd2857 | 122 | static inline int ctz32(uint32_t val) |
b9ef45ff | 123 | { |
bad5b1ec | 124 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
125 | if (val) |
126 | return __builtin_ctz(val); | |
127 | else | |
128 | return 32; | |
129 | #else | |
b9ef45ff JM |
130 | int cnt; |
131 | ||
132 | cnt = 0; | |
133 | if (!(val & 0x0000FFFFUL)) { | |
c8906845 | 134 | cnt += 16; |
b9ef45ff | 135 | val >>= 16; |
c8906845 | 136 | } |
b9ef45ff | 137 | if (!(val & 0x000000FFUL)) { |
c8906845 | 138 | cnt += 8; |
b9ef45ff | 139 | val >>= 8; |
c8906845 | 140 | } |
b9ef45ff | 141 | if (!(val & 0x0000000FUL)) { |
c8906845 | 142 | cnt += 4; |
b9ef45ff | 143 | val >>= 4; |
c8906845 | 144 | } |
b9ef45ff | 145 | if (!(val & 0x00000003UL)) { |
c8906845 | 146 | cnt += 2; |
b9ef45ff | 147 | val >>= 2; |
c8906845 | 148 | } |
b9ef45ff | 149 | if (!(val & 0x00000001UL)) { |
c8906845 | 150 | cnt++; |
b9ef45ff | 151 | val >>= 1; |
c8906845 | 152 | } |
b9ef45ff | 153 | if (!(val & 0x00000001UL)) { |
c8906845 AZ |
154 | cnt++; |
155 | } | |
b9ef45ff | 156 | |
c8906845 | 157 | return cnt; |
7d019980 | 158 | #endif |
c8906845 AZ |
159 | } |
160 | ||
facd2857 | 161 | static inline int cto32(uint32_t val) |
c8906845 | 162 | { |
b9ef45ff JM |
163 | return ctz32(~val); |
164 | } | |
165 | ||
facd2857 | 166 | static inline int ctz64(uint64_t val) |
b9ef45ff | 167 | { |
bad5b1ec | 168 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 | 169 | if (val) |
06445248 | 170 | return __builtin_ctzll(val); |
7d019980 AJ |
171 | else |
172 | return 64; | |
173 | #else | |
b9ef45ff JM |
174 | int cnt; |
175 | ||
176 | cnt = 0; | |
177 | if (!((uint32_t)val)) { | |
178 | cnt += 32; | |
179 | val >>= 32; | |
180 | } | |
181 | ||
182 | return cnt + ctz32(val); | |
7d019980 | 183 | #endif |
b9ef45ff JM |
184 | } |
185 | ||
facd2857 | 186 | static inline int cto64(uint64_t val) |
b9ef45ff JM |
187 | { |
188 | return ctz64(~val); | |
189 | } | |
190 | ||
facd2857 | 191 | static inline int ctpop8(uint8_t val) |
b9ef45ff JM |
192 | { |
193 | val = (val & 0x55) + ((val >> 1) & 0x55); | |
194 | val = (val & 0x33) + ((val >> 2) & 0x33); | |
195 | val = (val & 0x0f) + ((val >> 4) & 0x0f); | |
196 | ||
197 | return val; | |
198 | } | |
199 | ||
facd2857 | 200 | static inline int ctpop16(uint16_t val) |
b9ef45ff JM |
201 | { |
202 | val = (val & 0x5555) + ((val >> 1) & 0x5555); | |
203 | val = (val & 0x3333) + ((val >> 2) & 0x3333); | |
204 | val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f); | |
205 | val = (val & 0x00ff) + ((val >> 8) & 0x00ff); | |
206 | ||
207 | return val; | |
208 | } | |
209 | ||
facd2857 | 210 | static inline int ctpop32(uint32_t val) |
b9ef45ff | 211 | { |
bad5b1ec | 212 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
213 | return __builtin_popcount(val); |
214 | #else | |
b9ef45ff JM |
215 | val = (val & 0x55555555) + ((val >> 1) & 0x55555555); |
216 | val = (val & 0x33333333) + ((val >> 2) & 0x33333333); | |
217 | val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f); | |
218 | val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff); | |
219 | val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff); | |
220 | ||
221 | return val; | |
7d019980 | 222 | #endif |
b9ef45ff JM |
223 | } |
224 | ||
facd2857 | 225 | static inline int ctpop64(uint64_t val) |
b9ef45ff | 226 | { |
bad5b1ec | 227 | #if QEMU_GNUC_PREREQ(3, 4) |
7d019980 AJ |
228 | return __builtin_popcountll(val); |
229 | #else | |
b9ef45ff JM |
230 | val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL); |
231 | val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL); | |
232 | val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL); | |
233 | val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL); | |
234 | val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL); | |
235 | val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL); | |
236 | ||
237 | return val; | |
7d019980 | 238 | #endif |
3800af9e | 239 | } |
cb9c377f | 240 | |
4c37ef02 PB |
241 | /* glibc does not provide an inline version of ffsl, so always define |
242 | * ours. We need to give it a different name, however. | |
243 | */ | |
244 | #ifdef __GLIBC__ | |
245 | #define ffsl qemu_ffsl | |
246 | #endif | |
247 | static inline int ffsl(long val) | |
248 | { | |
249 | if (!val) { | |
250 | return 0; | |
251 | } | |
252 | ||
253 | #if QEMU_GNUC_PREREQ(3, 4) | |
254 | return __builtin_ctzl(val) + 1; | |
255 | #else | |
256 | if (sizeof(long) == 4) { | |
257 | return ctz32(val) + 1; | |
258 | } else if (sizeof(long) == 8) { | |
259 | return ctz64(val) + 1; | |
260 | } else { | |
261 | abort(); | |
262 | } | |
263 | #endif | |
264 | } | |
265 | ||
cb9c377f | 266 | #endif |