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