include/qemu/host-utils.h

   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 #ifndef HOST_UTILS_H
  26 #define HOST_UTILS_H 1
  27
  28 #include "qemu/bswap.h"
  29
  30 #ifdef CONFIG_INT128
  31 static inline void mulu64(uint64_t *plow, uint64_t *phigh,
  32                           uint64_t a, uint64_t b)
  33 {
  34     __uint128_t r = (__uint128_t)a * b;
  35     *plow = r;
  36     *phigh = r >> 64;
  37 }
  38
  39 static inline void muls64(uint64_t *plow, uint64_t *phigh,
  40                           int64_t a, int64_t b)
  41 {
  42     __int128_t r = (__int128_t)a * b;
  43     *plow = r;
  44     *phigh = r >> 64;
  45 }
  46
  47 /* compute with 96 bit intermediate result: (a*b)/c */
  48 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
  49 {
  50     return (__int128_t)a * b / c;
  51 }
  52
  53 static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
  54 {
  55     if (divisor == 0) {
  56         return 1;
  57     } else {
  58         __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
  59         __uint128_t result = dividend / divisor;
  60         *plow = result;
  61         *phigh = dividend % divisor;
  62         return result > UINT64_MAX;
  63     }
  64 }
  65
  66 static inline int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
  67 {
  68     if (divisor == 0) {
  69         return 1;
  70     } else {
  71         __int128_t dividend = ((__int128_t)*phigh << 64) | *plow;
  72         __int128_t result = dividend / divisor;
  73         *plow = result;
  74         *phigh = dividend % divisor;
  75         return result != *plow;
  76     }
  77 }
  78 #else
  79 void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
  80 void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
  81 int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
  82 int divs128(int64_t *plow, int64_t *phigh, int64_t divisor);
  83
  84 static inline uint64_t muldiv64(uint64_t a, uint32_t b, uint32_t c)
  85 {
  86     union {
  87         uint64_t ll;
  88         struct {
  89 #ifdef HOST_WORDS_BIGENDIAN
  90             uint32_t high, low;
  91 #else
  92             uint32_t low, high;
  93 #endif
  94         } l;
  95     } u, res;
  96     uint64_t rl, rh;
  97
  98     u.ll = a;
  99     rl = (uint64_t)u.l.low * (uint64_t)b;
 100     rh = (uint64_t)u.l.high * (uint64_t)b;
 101     rh += (rl >> 32);
 102     res.l.high = rh / c;
 103     res.l.low = (((rh % c) << 32) + (rl & 0xffffffff)) / c;
 104     return res.ll;
 105 }
 106 #endif
 107
 108 /**
 109  * clz32 - count leading zeros in a 32-bit value.
 110  * @val: The value to search
 111  *
 112  * Returns 32 if the value is zero.  Note that the GCC builtin is
 113  * undefined if the value is zero.
 114  */
 115 static inline int clz32(uint32_t val)
 116 {
 117 #if QEMU_GNUC_PREREQ(3, 4)
 118     return val ? __builtin_clz(val) : 32;
 119 #else
 120     /* Binary search for the leading one bit.  */
 121     int cnt = 0;
 122
 123     if (!(val & 0xFFFF0000U)) {
 124         cnt += 16;
 125         val <<= 16;
 126     }
 127     if (!(val & 0xFF000000U)) {
 128         cnt += 8;
 129         val <<= 8;
 130     }
 131     if (!(val & 0xF0000000U)) {
 132         cnt += 4;
 133         val <<= 4;
 134     }
 135     if (!(val & 0xC0000000U)) {
 136         cnt += 2;
 137         val <<= 2;
 138     }
 139     if (!(val & 0x80000000U)) {
 140         cnt++;
 141         val <<= 1;
 142     }
 143     if (!(val & 0x80000000U)) {
 144         cnt++;
 145     }
 146     return cnt;
 147 #endif
 148 }
 149
 150 /**
 151  * clo32 - count leading ones in a 32-bit value.
 152  * @val: The value to search
 153  *
 154  * Returns 32 if the value is -1.
 155  */
 156 static inline int clo32(uint32_t val)
 157 {
 158     return clz32(~val);
 159 }
 160
 161 /**
 162  * clz64 - count leading zeros in a 64-bit value.
 163  * @val: The value to search
 164  *
 165  * Returns 64 if the value is zero.  Note that the GCC builtin is
 166  * undefined if the value is zero.
 167  */
 168 static inline int clz64(uint64_t val)
 169 {
 170 #if QEMU_GNUC_PREREQ(3, 4)
 171     return val ? __builtin_clzll(val) : 64;
 172 #else
 173     int cnt = 0;
 174
 175     if (!(val >> 32)) {
 176         cnt += 32;
 177     } else {
 178         val >>= 32;
 179     }
 180
 181     return cnt + clz32(val);
 182 #endif
 183 }
 184
 185 /**
 186  * clo64 - count leading ones in a 64-bit value.
 187  * @val: The value to search
 188  *
 189  * Returns 64 if the value is -1.
 190  */
 191 static inline int clo64(uint64_t val)
 192 {
 193     return clz64(~val);
 194 }
 195
 196 /**
 197  * ctz32 - count trailing zeros in a 32-bit value.
 198  * @val: The value to search
 199  *
 200  * Returns 32 if the value is zero.  Note that the GCC builtin is
 201  * undefined if the value is zero.
 202  */
 203 static inline int ctz32(uint32_t val)
 204 {
 205 #if QEMU_GNUC_PREREQ(3, 4)
 206     return val ? __builtin_ctz(val) : 32;
 207 #else
 208     /* Binary search for the trailing one bit.  */
 209     int cnt;
 210
 211     cnt = 0;
 212     if (!(val & 0x0000FFFFUL)) {
 213         cnt += 16;
 214         val >>= 16;
 215     }
 216     if (!(val & 0x000000FFUL)) {
 217         cnt += 8;
 218         val >>= 8;
 219     }
 220     if (!(val & 0x0000000FUL)) {
 221         cnt += 4;
 222         val >>= 4;
 223     }
 224     if (!(val & 0x00000003UL)) {
 225         cnt += 2;
 226         val >>= 2;
 227     }
 228     if (!(val & 0x00000001UL)) {
 229         cnt++;
 230         val >>= 1;
 231     }
 232     if (!(val & 0x00000001UL)) {
 233         cnt++;
 234     }
 235
 236     return cnt;
 237 #endif
 238 }
 239
 240 /**
 241  * cto32 - count trailing ones in a 32-bit value.
 242  * @val: The value to search
 243  *
 244  * Returns 32 if the value is -1.
 245  */
 246 static inline int cto32(uint32_t val)
 247 {
 248     return ctz32(~val);
 249 }
 250
 251 /**
 252  * ctz64 - count trailing zeros in a 64-bit value.
 253  * @val: The value to search
 254  *
 255  * Returns 64 if the value is zero.  Note that the GCC builtin is
 256  * undefined if the value is zero.
 257  */
 258 static inline int ctz64(uint64_t val)
 259 {
 260 #if QEMU_GNUC_PREREQ(3, 4)
 261     return val ? __builtin_ctzll(val) : 64;
 262 #else
 263     int cnt;
 264
 265     cnt = 0;
 266     if (!((uint32_t)val)) {
 267         cnt += 32;
 268         val >>= 32;
 269     }
 270
 271     return cnt + ctz32(val);
 272 #endif
 273 }
 274
 275 /**
 276  * cto64 - count trailing ones in a 64-bit value.
 277  * @val: The value to search
 278  *
 279  * Returns 64 if the value is -1.
 280  */
 281 static inline int cto64(uint64_t val)
 282 {
 283     return ctz64(~val);
 284 }
 285
 286 /**
 287  * clrsb32 - count leading redundant sign bits in a 32-bit value.
 288  * @val: The value to search
 289  *
 290  * Returns the number of bits following the sign bit that are equal to it.
 291  * No special cases; output range is [0-31].
 292  */
 293 static inline int clrsb32(uint32_t val)
 294 {
 295 #if QEMU_GNUC_PREREQ(4, 7)
 296     return __builtin_clrsb(val);
 297 #else
 298     return clz32(val ^ ((int32_t)val >> 1)) - 1;
 299 #endif
 300 }
 301
 302 /**
 303  * clrsb64 - count leading redundant sign bits in a 64-bit value.
 304  * @val: The value to search
 305  *
 306  * Returns the number of bits following the sign bit that are equal to it.
 307  * No special cases; output range is [0-63].
 308  */
 309 static inline int clrsb64(uint64_t val)
 310 {
 311 #if QEMU_GNUC_PREREQ(4, 7)
 312     return __builtin_clrsbll(val);
 313 #else
 314     return clz64(val ^ ((int64_t)val >> 1)) - 1;
 315 #endif
 316 }
 317
 318 /**
 319  * ctpop8 - count the population of one bits in an 8-bit value.
 320  * @val: The value to search
 321  */
 322 static inline int ctpop8(uint8_t val)
 323 {
 324 #if QEMU_GNUC_PREREQ(3, 4)
 325     return __builtin_popcount(val);
 326 #else
 327     val = (val & 0x55) + ((val >> 1) & 0x55);
 328     val = (val & 0x33) + ((val >> 2) & 0x33);
 329     val = (val & 0x0f) + ((val >> 4) & 0x0f);
 330
 331     return val;
 332 #endif
 333 }
 334
 335 /**
 336  * ctpop16 - count the population of one bits in a 16-bit value.
 337  * @val: The value to search
 338  */
 339 static inline int ctpop16(uint16_t val)
 340 {
 341 #if QEMU_GNUC_PREREQ(3, 4)
 342     return __builtin_popcount(val);
 343 #else
 344     val = (val & 0x5555) + ((val >> 1) & 0x5555);
 345     val = (val & 0x3333) + ((val >> 2) & 0x3333);
 346     val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
 347     val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
 348
 349     return val;
 350 #endif
 351 }
 352
 353 /**
 354  * ctpop32 - count the population of one bits in a 32-bit value.
 355  * @val: The value to search
 356  */
 357 static inline int ctpop32(uint32_t val)
 358 {
 359 #if QEMU_GNUC_PREREQ(3, 4)
 360     return __builtin_popcount(val);
 361 #else
 362     val = (val & 0x55555555) + ((val >>  1) & 0x55555555);
 363     val = (val & 0x33333333) + ((val >>  2) & 0x33333333);
 364     val = (val & 0x0f0f0f0f) + ((val >>  4) & 0x0f0f0f0f);
 365     val = (val & 0x00ff00ff) + ((val >>  8) & 0x00ff00ff);
 366     val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff);
 367
 368     return val;
 369 #endif
 370 }
 371
 372 /**
 373  * ctpop64 - count the population of one bits in a 64-bit value.
 374  * @val: The value to search
 375  */
 376 static inline int ctpop64(uint64_t val)
 377 {
 378 #if QEMU_GNUC_PREREQ(3, 4)
 379     return __builtin_popcountll(val);
 380 #else
 381     val = (val & 0x5555555555555555ULL) + ((val >>  1) & 0x5555555555555555ULL);
 382     val = (val & 0x3333333333333333ULL) + ((val >>  2) & 0x3333333333333333ULL);
 383     val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >>  4) & 0x0f0f0f0f0f0f0f0fULL);
 384     val = (val & 0x00ff00ff00ff00ffULL) + ((val >>  8) & 0x00ff00ff00ff00ffULL);
 385     val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL);
 386     val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL);
 387
 388     return val;
 389 #endif
 390 }
 391
 392 /**
 393  * revbit8 - reverse the bits in an 8-bit value.
 394  * @x: The value to modify.
 395  */
 396 static inline uint8_t revbit8(uint8_t x)
 397 {
 398     /* Assign the correct nibble position.  */
 399     x = ((x & 0xf0) >> 4)
 400       | ((x & 0x0f) << 4);
 401     /* Assign the correct bit position.  */
 402     x = ((x & 0x88) >> 3)
 403       | ((x & 0x44) >> 1)
 404       | ((x & 0x22) << 1)
 405       | ((x & 0x11) << 3);
 406     return x;
 407 }
 408
 409 /**
 410  * revbit16 - reverse the bits in a 16-bit value.
 411  * @x: The value to modify.
 412  */
 413 static inline uint16_t revbit16(uint16_t x)
 414 {
 415     /* Assign the correct byte position.  */
 416     x = bswap16(x);
 417     /* Assign the correct nibble position.  */
 418     x = ((x & 0xf0f0) >> 4)
 419       | ((x & 0x0f0f) << 4);
 420     /* Assign the correct bit position.  */
 421     x = ((x & 0x8888) >> 3)
 422       | ((x & 0x4444) >> 1)
 423       | ((x & 0x2222) << 1)
 424       | ((x & 0x1111) << 3);
 425     return x;
 426 }
 427
 428 /**
 429  * revbit32 - reverse the bits in a 32-bit value.
 430  * @x: The value to modify.
 431  */
 432 static inline uint32_t revbit32(uint32_t x)
 433 {
 434     /* Assign the correct byte position.  */
 435     x = bswap32(x);
 436     /* Assign the correct nibble position.  */
 437     x = ((x & 0xf0f0f0f0u) >> 4)
 438       | ((x & 0x0f0f0f0fu) << 4);
 439     /* Assign the correct bit position.  */
 440     x = ((x & 0x88888888u) >> 3)
 441       | ((x & 0x44444444u) >> 1)
 442       | ((x & 0x22222222u) << 1)
 443       | ((x & 0x11111111u) << 3);
 444     return x;
 445 }
 446
 447 /**
 448  * revbit64 - reverse the bits in a 64-bit value.
 449  * @x: The value to modify.
 450  */
 451 static inline uint64_t revbit64(uint64_t x)
 452 {
 453     /* Assign the correct byte position.  */
 454     x = bswap64(x);
 455     /* Assign the correct nibble position.  */
 456     x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
 457       | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
 458     /* Assign the correct bit position.  */
 459     x = ((x & 0x8888888888888888ull) >> 3)
 460       | ((x & 0x4444444444444444ull) >> 1)
 461       | ((x & 0x2222222222222222ull) << 1)
 462       | ((x & 0x1111111111111111ull) << 3);
 463     return x;
 464 }
 465
 466 /* Host type specific sizes of these routines.  */
 467
 468 #if ULONG_MAX == UINT32_MAX
 469 # define clzl   clz32
 470 # define ctzl   ctz32
 471 # define clol   clo32
 472 # define ctol   cto32
 473 # define ctpopl ctpop32
 474 # define revbitl revbit32
 475 #elif ULONG_MAX == UINT64_MAX
 476 # define clzl   clz64
 477 # define ctzl   ctz64
 478 # define clol   clo64
 479 # define ctol   cto64
 480 # define ctpopl ctpop64
 481 # define revbitl revbit64
 482 #else
 483 # error Unknown sizeof long
 484 #endif
 485
 486 static inline bool is_power_of_2(uint64_t value)
 487 {
 488     if (!value) {
 489         return false;
 490     }
 491
 492     return !(value & (value - 1));
 493 }
 494
 495 /* round down to the nearest power of 2*/
 496 static inline int64_t pow2floor(int64_t value)
 497 {
 498     if (!is_power_of_2(value)) {
 499         value = 0x8000000000000000ULL >> clz64(value);
 500     }
 501     return value;
 502 }
 503
 504 /* round up to the nearest power of 2 (0 if overflow) */
 505 static inline uint64_t pow2ceil(uint64_t value)
 506 {
 507     uint8_t nlz = clz64(value);
 508
 509     if (is_power_of_2(value)) {
 510         return value;
 511     }
 512     if (!nlz) {
 513         return 0;
 514     }
 515     return 1ULL << (64 - nlz);
 516 }
 517
 518 #endif