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 + (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 + (val >> 4)) & 0x0f0f;
 348     val = (val + (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 + (val >> 4)) & 0x0f0f0f0f;
 366     val = (val * 0x01010101) >> 24;
 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 + (val >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
 384     val = (val * 0x0101010101010101ULL) >> 56;
 385
 386     return val;
 387 #endif
 388 }
 389
 390 /**
 391  * revbit8 - reverse the bits in an 8-bit value.
 392  * @x: The value to modify.
 393  */
 394 static inline uint8_t revbit8(uint8_t x)
 395 {
 396     /* Assign the correct nibble position.  */
 397     x = ((x & 0xf0) >> 4)
 398       | ((x & 0x0f) << 4);
 399     /* Assign the correct bit position.  */
 400     x = ((x & 0x88) >> 3)
 401       | ((x & 0x44) >> 1)
 402       | ((x & 0x22) << 1)
 403       | ((x & 0x11) << 3);
 404     return x;
 405 }
 406
 407 /**
 408  * revbit16 - reverse the bits in a 16-bit value.
 409  * @x: The value to modify.
 410  */
 411 static inline uint16_t revbit16(uint16_t x)
 412 {
 413     /* Assign the correct byte position.  */
 414     x = bswap16(x);
 415     /* Assign the correct nibble position.  */
 416     x = ((x & 0xf0f0) >> 4)
 417       | ((x & 0x0f0f) << 4);
 418     /* Assign the correct bit position.  */
 419     x = ((x & 0x8888) >> 3)
 420       | ((x & 0x4444) >> 1)
 421       | ((x & 0x2222) << 1)
 422       | ((x & 0x1111) << 3);
 423     return x;
 424 }
 425
 426 /**
 427  * revbit32 - reverse the bits in a 32-bit value.
 428  * @x: The value to modify.
 429  */
 430 static inline uint32_t revbit32(uint32_t x)
 431 {
 432     /* Assign the correct byte position.  */
 433     x = bswap32(x);
 434     /* Assign the correct nibble position.  */
 435     x = ((x & 0xf0f0f0f0u) >> 4)
 436       | ((x & 0x0f0f0f0fu) << 4);
 437     /* Assign the correct bit position.  */
 438     x = ((x & 0x88888888u) >> 3)
 439       | ((x & 0x44444444u) >> 1)
 440       | ((x & 0x22222222u) << 1)
 441       | ((x & 0x11111111u) << 3);
 442     return x;
 443 }
 444
 445 /**
 446  * revbit64 - reverse the bits in a 64-bit value.
 447  * @x: The value to modify.
 448  */
 449 static inline uint64_t revbit64(uint64_t x)
 450 {
 451     /* Assign the correct byte position.  */
 452     x = bswap64(x);
 453     /* Assign the correct nibble position.  */
 454     x = ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4)
 455       | ((x & 0x0f0f0f0f0f0f0f0full) << 4);
 456     /* Assign the correct bit position.  */
 457     x = ((x & 0x8888888888888888ull) >> 3)
 458       | ((x & 0x4444444444444444ull) >> 1)
 459       | ((x & 0x2222222222222222ull) << 1)
 460       | ((x & 0x1111111111111111ull) << 3);
 461     return x;
 462 }
 463
 464 /* Host type specific sizes of these routines.  */
 465
 466 #if ULONG_MAX == UINT32_MAX
 467 # define clzl   clz32
 468 # define ctzl   ctz32
 469 # define clol   clo32
 470 # define ctol   cto32
 471 # define ctpopl ctpop32
 472 # define revbitl revbit32
 473 #elif ULONG_MAX == UINT64_MAX
 474 # define clzl   clz64
 475 # define ctzl   ctz64
 476 # define clol   clo64
 477 # define ctol   cto64
 478 # define ctpopl ctpop64
 479 # define revbitl revbit64
 480 #else
 481 # error Unknown sizeof long
 482 #endif
 483
 484 static inline bool is_power_of_2(uint64_t value)
 485 {
 486     if (!value) {
 487         return false;
 488     }
 489
 490     return !(value & (value - 1));
 491 }
 492
 493 /* round down to the nearest power of 2*/
 494 static inline int64_t pow2floor(int64_t value)
 495 {
 496     if (!is_power_of_2(value)) {
 497         value = 0x8000000000000000ULL >> clz64(value);
 498     }
 499     return value;
 500 }
 501
 502 /* round up to the nearest power of 2 (0 if overflow) */
 503 static inline uint64_t pow2ceil(uint64_t value)
 504 {
 505     uint8_t nlz = clz64(value);
 506
 507     if (is_power_of_2(value)) {
 508         return value;
 509     }
 510     if (!nlz) {
 511         return 0;
 512     }
 513     return 1ULL << (64 - nlz);
 514 }
 515
 516 #endif