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 */ 25 26 #ifndef HOST_UTILS_H 27 #define HOST_UTILS_H 28 29 #include "qemu/bswap.h" 30 31 #ifdef CONFIG_INT128 32 static inline void mulu64(uint64_t *plow, uint64_t *phigh, 33 uint64_t a, uint64_t b) 34 { 35 __uint128_t r = (__uint128_t)a * b; 36 *plow = r; 37 *phigh = r >> 64; 38 } 39 40 static inline void muls64(uint64_t *plow, uint64_t *phigh, 41 int64_t a, int64_t b) 42 { 43 __int128_t r = (__int128_t)a * b; 44 *plow = r; 45 *phigh = r >> 64; 46 } 47 48 /* compute with 96 bit intermediate result: (a*b)/c */ 49 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) 50 { 51 return (__int128_t)a * b / c; 52 } 53 54 static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor) 55 { 56 if (divisor == 0) { 57 return 1; 58 } else { 59 __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow; 60 __uint128_t result = dividend / divisor; 61 *plow = result; 62 *phigh = dividend % divisor; 63 return result > UINT64_MAX; 64 } 65 } 66 67 static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor) 68 { 69 if (divisor == 0) { 70 return 1; 71 } else { 72 __int128_t dividend = ((__int128_t)*phigh << 64) | *plow; 73 __int128_t result = dividend / divisor; 74 *plow = result; 75 *phigh = dividend % divisor; 76 return result != *plow; 77 } 78 } 79 #else 80 void muls64(uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b); 81 void mulu64(uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b); 82 int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor); 83 int divs128(int64_t *plow, int64_t *phigh, int64_t divisor); 84 85 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c) 86 { 87 union { 88 uint64_t ll; 89 struct { 90 #ifdef HOST_WORDS_BIGENDIAN 91 uint32_t high, low; 92 #else 93 uint32_t low, high; 94 #endif 95 } l; 96 } u, res; 97 uint64_t rl, rh; 98 99 u.ll = a; 100 rl = (uint64_t)u.l.low * (uint64_t)b; 101 rh = (uint64_t)u.l.high * (uint64_t)b; 102 rh += (rl >> 32); 103 res.l.high = rh / c; 104 res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c; 105 return res.ll; 106 } 107 #endif 108 109 /** 110 * clz32 - count leading zeros in a 32-bit value. 111 * @val: The value to search 112 * 113 * Returns 32 if the value is zero. Note that the GCC builtin is 114 * undefined if the value is zero. 115 */ 116 static inline int clz32(uint32_t val) 117 { 118 return val ? __builtin_clz(val) : 32; 119 } 120 121 /** 122 * clo32 - count leading ones in a 32-bit value. 123 * @val: The value to search 124 * 125 * Returns 32 if the value is -1. 126 */ 127 static inline int clo32(uint32_t val) 128 { 129 return clz32(~val); 130 } 131 132 /** 133 * clz64 - count leading zeros in a 64-bit value. 134 * @val: The value to search 135 * 136 * Returns 64 if the value is zero. Note that the GCC builtin is 137 * undefined if the value is zero. 138 */ 139 static inline int clz64(uint64_t val) 140 { 141 return val ? __builtin_clzll(val) : 64; 142 } 143 144 /** 145 * clo64 - count leading ones in a 64-bit value. 146 * @val: The value to search 147 * 148 * Returns 64 if the value is -1. 149 */ 150 static inline int clo64(uint64_t val) 151 { 152 return clz64(~val); 153 } 154 155 /** 156 * ctz32 - count trailing zeros in a 32-bit value. 157 * @val: The value to search 158 * 159 * Returns 32 if the value is zero. Note that the GCC builtin is 160 * undefined if the value is zero. 161 */ 162 static inline int ctz32(uint32_t val) 163 { 164 return val ? __builtin_ctz(val) : 32; 165 } 166 167 /** 168 * cto32 - count trailing ones in a 32-bit value. 169 * @val: The value to search 170 * 171 * Returns 32 if the value is -1. 172 */ 173 static inline int cto32(uint32_t val) 174 { 175 return ctz32(~val); 176 } 177 178 /** 179 * ctz64 - count trailing zeros in a 64-bit value. 180 * @val: The value to search 181 * 182 * Returns 64 if the value is zero. Note that the GCC builtin is 183 * undefined if the value is zero. 184 */ 185 static inline int ctz64(uint64_t val) 186 { 187 return val ? __builtin_ctzll(val) : 64; 188 } 189 190 /** 191 * cto64 - count trailing ones in a 64-bit value. 192 * @val: The value to search 193 * 194 * Returns 64 if the value is -1. 195 */ 196 static inline int cto64(uint64_t val) 197 { 198 return ctz64(~val); 199 } 200 201 /** 202 * clrsb32 - count leading redundant sign bits in a 32-bit value. 203 * @val: The value to search 204 * 205 * Returns the number of bits following the sign bit that are equal to it. 206 * No special cases; output range is [0-31]. 207 */ 208 static inline int clrsb32(uint32_t val) 209 { 210 #if __has_builtin(__builtin_clrsb) || !defined(__clang__) 211 return __builtin_clrsb(val); 212 #else 213 return clz32(val ^ ((int32_t)val >> 1)) - 1; 214 #endif 215 } 216 217 /** 218 * clrsb64 - count leading redundant sign bits in a 64-bit value. 219 * @val: The value to search 220 * 221 * Returns the number of bits following the sign bit that are equal to it. 222 * No special cases; output range is [0-63]. 223 */ 224 static inline int clrsb64(uint64_t val) 225 { 226 #if __has_builtin(__builtin_clrsbll) || !defined(__clang__) 227 return __builtin_clrsbll(val); 228 #else 229 return clz64(val ^ ((int64_t)val >> 1)) - 1; 230 #endif 231 } 232 233 /** 234 * ctpop8 - count the population of one bits in an 8-bit value. 235 * @val: The value to search 236 */ 237 static inline int ctpop8(uint8_t val) 238 { 239 return __builtin_popcount(val); 240 } 241 242 /** 243 * ctpop16 - count the population of one bits in a 16-bit value. 244 * @val: The value to search 245 */ 246 static inline int ctpop16(uint16_t val) 247 { 248 return __builtin_popcount(val); 249 } 250 251 /** 252 * ctpop32 - count the population of one bits in a 32-bit value. 253 * @val: The value to search 254 */ 255 static inline int ctpop32(uint32_t val) 256 { 257 return __builtin_popcount(val); 258 } 259 260 /** 261 * ctpop64 - count the population of one bits in a 64-bit value. 262 * @val: The value to search 263 */ 264 static inline int ctpop64(uint64_t val) 265 { 266 return __builtin_popcountll(val); 267 } 268 269 /** 270 * revbit8 - reverse the bits in an 8-bit value. 271 * @x: The value to modify. 272 */ 273 static inline uint8_t revbit8(uint8_t x) 274 { 275 /* Assign the correct nibble position. */ 276 x = ((x & 0xf0) >> 4) 277 | ((x & 0x0f) << 4); 278 /* Assign the correct bit position. */ 279 x = ((x & 0x88) >> 3) 280 | ((x & 0x44) >> 1) 281 | ((x & 0x22) << 1) 282 | ((x & 0x11) << 3); 283 return x; 284 } 285 286 /** 287 * revbit16 - reverse the bits in a 16-bit value. 288 * @x: The value to modify. 289 */ 290 static inline uint16_t revbit16(uint16_t x) 291 { 292 /* Assign the correct byte position. */ 293 x = bswap16(x); 294 /* Assign the correct nibble position. */ 295 x = ((x & 0xf0f0) >> 4) 296 | ((x & 0x0f0f) << 4); 297 /* Assign the correct bit position. */ 298 x = ((x & 0x8888) >> 3) 299 | ((x & 0x4444) >> 1) 300 | ((x & 0x2222) << 1) 301 | ((x & 0x1111) << 3); 302 return x; 303 } 304 305 /** 306 * revbit32 - reverse the bits in a 32-bit value. 307 * @x: The value to modify. 308 */ 309 static inline uint32_t revbit32(uint32_t x) 310 { 311 /* Assign the correct byte position. */ 312 x = bswap32(x); 313 /* Assign the correct nibble position. */ 314 x = ((x & 0xf0f0f0f0u) >> 4) 315 | ((x & 0x0f0f0f0fu) << 4); 316 /* Assign the correct bit position. */ 317 x = ((x & 0x88888888u) >> 3) 318 | ((x & 0x44444444u) >> 1) 319 | ((x & 0x22222222u) << 1) 320 | ((x & 0x11111111u) << 3); 321 return x; 322 } 323 324 /** 325 * revbit64 - reverse the bits in a 64-bit value. 326 * @x: The value to modify. 327 */ 328 static inline uint64_t revbit64(uint64_t x) 329 { 330 /* Assign the correct byte position. */ 331 x = bswap64(x); 332 /* Assign the correct nibble position. */ 333 x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4) 334 | ((x & 0x0f0f0f0f0f0f0f0full) << 4); 335 /* Assign the correct bit position. */ 336 x = ((x & 0x8888888888888888ull) >> 3) 337 | ((x & 0x4444444444444444ull) >> 1) 338 | ((x & 0x2222222222222222ull) << 1) 339 | ((x & 0x1111111111111111ull) << 3); 340 return x; 341 } 342 343 /* Host type specific sizes of these routines. */ 344 345 #if ULONG_MAX == UINT32_MAX 346 # define clzl clz32 347 # define ctzl ctz32 348 # define clol clo32 349 # define ctol cto32 350 # define ctpopl ctpop32 351 # define revbitl revbit32 352 #elif ULONG_MAX == UINT64_MAX 353 # define clzl clz64 354 # define ctzl ctz64 355 # define clol clo64 356 # define ctol cto64 357 # define ctpopl ctpop64 358 # define revbitl revbit64 359 #else 360 # error Unknown sizeof long 361 #endif 362 363 static inline bool is_power_of_2(uint64_t value) 364 { 365 if (!value) { 366 return false; 367 } 368 369 return !(value & (value - 1)); 370 } 371 372 /** 373 * Return @value rounded down to the nearest power of two or zero. 374 */ 375 static inline uint64_t pow2floor(uint64_t value) 376 { 377 if (!value) { 378 /* Avoid undefined shift by 64 */ 379 return 0; 380 } 381 return 0x8000000000000000ull >> clz64(value); 382 } 383 384 /* 385 * Return @value rounded up to the nearest power of two modulo 2^64. 386 * This is *zero* for @value > 2^63, so be careful. 387 */ 388 static inline uint64_t pow2ceil(uint64_t value) 389 { 390 int n = clz64(value - 1); 391 392 if (!n) { 393 /* 394 * @value - 1 has no leading zeroes, thus @value - 1 >= 2^63 395 * Therefore, either @value == 0 or @value > 2^63. 396 * If it's 0, return 1, else return 0. 397 */ 398 return !value; 399 } 400 return 0x8000000000000000ull >> (n - 1); 401 } 402 403 static inline uint32_t pow2roundup32(uint32_t x) 404 { 405 x |= (x >> 1); 406 x |= (x >> 2); 407 x |= (x >> 4); 408 x |= (x >> 8); 409 x |= (x >> 16); 410 return x + 1; 411 } 412 413 /** 414 * urshift - 128-bit Unsigned Right Shift. 415 * @plow: in/out - lower 64-bit integer. 416 * @phigh: in/out - higher 64-bit integer. 417 * @shift: in - bytes to shift, between 0 and 127. 418 * 419 * Result is zero-extended and stored in plow/phigh, which are 420 * input/output variables. Shift values outside the range will 421 * be mod to 128. In other words, the caller is responsible to 422 * verify/assert both the shift range and plow/phigh pointers. 423 */ 424 void urshift(uint64_t *plow, uint64_t *phigh, int32_t shift); 425 426 /** 427 * ulshift - 128-bit Unsigned Left Shift. 428 * @plow: in/out - lower 64-bit integer. 429 * @phigh: in/out - higher 64-bit integer. 430 * @shift: in - bytes to shift, between 0 and 127. 431 * @overflow: out - true if any 1-bit is shifted out. 432 * 433 * Result is zero-extended and stored in plow/phigh, which are 434 * input/output variables. Shift values outside the range will 435 * be mod to 128. In other words, the caller is responsible to 436 * verify/assert both the shift range and plow/phigh pointers. 437 */ 438 void ulshift(uint64_t *plow, uint64_t *phigh, int32_t shift, bool *overflow); 439 440 #endif 441