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/compiler.h"   /* QEMU_GNUC_PREREQ */
  29 #include <limits.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 static inline int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
  49 {
  50     if (divisor == 0) {
  51         return 1;
  52     } else {
  53         __uint128_t dividend = ((__uint128_t)*phigh << 64) | *plow;
  54         __uint128_t result = dividend / divisor;
  55         *plow = result;
  56         *phigh = dividend % divisor;
  57         return result > UINT64_MAX;
  58     }
  59 }
  60 #else
  61 void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
  62 void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
  63 int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor);
  64 #endif
  65
  66 /**
  67  * clz32 - count leading zeros in a 32-bit value.
  68  * @val: The value to search
  69  *
  70  * Returns 32 if the value is zero.  Note that the GCC builtin is
  71  * undefined if the value is zero.
  72  */
  73 static inline int clz32(uint32_t val)
  74 {
  75 #if QEMU_GNUC_PREREQ(3, 4)
  76     return val ? __builtin_clz(val) : 32;
  77 #else
  78     /* Binary search for the leading one bit.  */
  79     int cnt = 0;
  80
  81     if (!(val & 0xFFFF0000U)) {
  82         cnt += 16;
  83         val <<= 16;
  84     }
  85     if (!(val & 0xFF000000U)) {
  86         cnt += 8;
  87         val <<= 8;
  88     }
  89     if (!(val & 0xF0000000U)) {
  90         cnt += 4;
  91         val <<= 4;
  92     }
  93     if (!(val & 0xC0000000U)) {
  94         cnt += 2;
  95         val <<= 2;
  96     }
  97     if (!(val & 0x80000000U)) {
  98         cnt++;
  99         val <<= 1;
 100     }
 101     if (!(val & 0x80000000U)) {
 102         cnt++;
 103     }
 104     return cnt;
 105 #endif
 106 }
 107
 108 /**
 109  * clo32 - count leading ones in a 32-bit value.
 110  * @val: The value to search
 111  *
 112  * Returns 32 if the value is -1.
 113  */
 114 static inline int clo32(uint32_t val)
 115 {
 116     return clz32(~val);
 117 }
 118
 119 /**
 120  * clz64 - count leading zeros in a 64-bit value.
 121  * @val: The value to search
 122  *
 123  * Returns 64 if the value is zero.  Note that the GCC builtin is
 124  * undefined if the value is zero.
 125  */
 126 static inline int clz64(uint64_t val)
 127 {
 128 #if QEMU_GNUC_PREREQ(3, 4)
 129     return val ? __builtin_clzll(val) : 64;
 130 #else
 131     int cnt = 0;
 132
 133     if (!(val >> 32)) {
 134         cnt += 32;
 135     } else {
 136         val >>= 32;
 137     }
 138
 139     return cnt + clz32(val);
 140 #endif
 141 }
 142
 143 /**
 144  * clo64 - count leading ones in a 64-bit value.
 145  * @val: The value to search
 146  *
 147  * Returns 64 if the value is -1.
 148  */
 149 static inline int clo64(uint64_t val)
 150 {
 151     return clz64(~val);
 152 }
 153
 154 /**
 155  * ctz32 - count trailing zeros in a 32-bit value.
 156  * @val: The value to search
 157  *
 158  * Returns 32 if the value is zero.  Note that the GCC builtin is
 159  * undefined if the value is zero.
 160  */
 161 static inline int ctz32(uint32_t val)
 162 {
 163 #if QEMU_GNUC_PREREQ(3, 4)
 164     return val ? __builtin_ctz(val) : 32;
 165 #else
 166     /* Binary search for the trailing one bit.  */
 167     int cnt;
 168
 169     cnt = 0;
 170     if (!(val & 0x0000FFFFUL)) {
 171         cnt += 16;
 172         val >>= 16;
 173     }
 174     if (!(val & 0x000000FFUL)) {
 175         cnt += 8;
 176         val >>= 8;
 177     }
 178     if (!(val & 0x0000000FUL)) {
 179         cnt += 4;
 180         val >>= 4;
 181     }
 182     if (!(val & 0x00000003UL)) {
 183         cnt += 2;
 184         val >>= 2;
 185     }
 186     if (!(val & 0x00000001UL)) {
 187         cnt++;
 188         val >>= 1;
 189     }
 190     if (!(val & 0x00000001UL)) {
 191         cnt++;
 192     }
 193
 194     return cnt;
 195 #endif
 196 }
 197
 198 /**
 199  * cto32 - count trailing ones in a 32-bit value.
 200  * @val: The value to search
 201  *
 202  * Returns 32 if the value is -1.
 203  */
 204 static inline int cto32(uint32_t val)
 205 {
 206     return ctz32(~val);
 207 }
 208
 209 /**
 210  * ctz64 - count trailing zeros in a 64-bit value.
 211  * @val: The value to search
 212  *
 213  * Returns 64 if the value is zero.  Note that the GCC builtin is
 214  * undefined if the value is zero.
 215  */
 216 static inline int ctz64(uint64_t val)
 217 {
 218 #if QEMU_GNUC_PREREQ(3, 4)
 219     return val ? __builtin_ctzll(val) : 64;
 220 #else
 221     int cnt;
 222
 223     cnt = 0;
 224     if (!((uint32_t)val)) {
 225         cnt += 32;
 226         val >>= 32;
 227     }
 228
 229     return cnt + ctz32(val);
 230 #endif
 231 }
 232
 233 /**
 234  * cto64 - count trailing ones in a 64-bit value.
 235  * @val: The value to search
 236  *
 237  * Returns 64 if the value is -1.
 238  */
 239 static inline int cto64(uint64_t val)
 240 {
 241     return ctz64(~val);
 242 }
 243
 244 /**
 245  * clrsb32 - count leading redundant sign bits in a 32-bit value.
 246  * @val: The value to search
 247  *
 248  * Returns the number of bits following the sign bit that are equal to it.
 249  * No special cases; output range is [0-31].
 250  */
 251 static inline int clrsb32(uint32_t val)
 252 {
 253 #if QEMU_GNUC_PREREQ(4, 7)
 254     return __builtin_clrsb(val);
 255 #else
 256     return clz32(val ^ ((int32_t)val >> 1)) - 1;
 257 #endif
 258 }
 259
 260 /**
 261  * clrsb64 - count leading redundant sign bits in a 64-bit value.
 262  * @val: The value to search
 263  *
 264  * Returns the number of bits following the sign bit that are equal to it.
 265  * No special cases; output range is [0-63].
 266  */
 267 static inline int clrsb64(uint64_t val)
 268 {
 269 #if QEMU_GNUC_PREREQ(4, 7)
 270     return __builtin_clrsbll(val);
 271 #else
 272     return clz64(val ^ ((int64_t)val >> 1)) - 1;
 273 #endif
 274 }
 275
 276 /**
 277  * ctpop8 - count the population of one bits in an 8-bit value.
 278  * @val: The value to search
 279  */
 280 static inline int ctpop8(uint8_t val)
 281 {
 282 #if QEMU_GNUC_PREREQ(3, 4)
 283     return __builtin_popcount(val);
 284 #else
 285     val = (val & 0x55) + ((val >> 1) & 0x55);
 286     val = (val & 0x33) + ((val >> 2) & 0x33);
 287     val = (val & 0x0f) + ((val >> 4) & 0x0f);
 288
 289     return val;
 290 #endif
 291 }
 292
 293 /**
 294  * ctpop16 - count the population of one bits in a 16-bit value.
 295  * @val: The value to search
 296  */
 297 static inline int ctpop16(uint16_t val)
 298 {
 299 #if QEMU_GNUC_PREREQ(3, 4)
 300     return __builtin_popcount(val);
 301 #else
 302     val = (val & 0x5555) + ((val >> 1) & 0x5555);
 303     val = (val & 0x3333) + ((val >> 2) & 0x3333);
 304     val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
 305     val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
 306
 307     return val;
 308 #endif
 309 }
 310
 311 /**
 312  * ctpop32 - count the population of one bits in a 32-bit value.
 313  * @val: The value to search
 314  */
 315 static inline int ctpop32(uint32_t val)
 316 {
 317 #if QEMU_GNUC_PREREQ(3, 4)
 318     return __builtin_popcount(val);
 319 #else
 320     val = (val & 0x55555555) + ((val >>  1) & 0x55555555);
 321     val = (val & 0x33333333) + ((val >>  2) & 0x33333333);
 322     val = (val & 0x0f0f0f0f) + ((val >>  4) & 0x0f0f0f0f);
 323     val = (val & 0x00ff00ff) + ((val >>  8) & 0x00ff00ff);
 324     val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff);
 325
 326     return val;
 327 #endif
 328 }
 329
 330 /**
 331  * ctpop64 - count the population of one bits in a 64-bit value.
 332  * @val: The value to search
 333  */
 334 static inline int ctpop64(uint64_t val)
 335 {
 336 #if QEMU_GNUC_PREREQ(3, 4)
 337     return __builtin_popcountll(val);
 338 #else
 339     val = (val & 0x5555555555555555ULL) + ((val >>  1) & 0x5555555555555555ULL);
 340     val = (val & 0x3333333333333333ULL) + ((val >>  2) & 0x3333333333333333ULL);
 341     val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >>  4) & 0x0f0f0f0f0f0f0f0fULL);
 342     val = (val & 0x00ff00ff00ff00ffULL) + ((val >>  8) & 0x00ff00ff00ff00ffULL);
 343     val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL);
 344     val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL);
 345
 346     return val;
 347 #endif
 348 }
 349
 350 /* Host type specific sizes of these routines.  */
 351
 352 #if ULONG_MAX == UINT32_MAX
 353 # define clzl   clz32
 354 # define ctzl   ctz32
 355 # define clol   clo32
 356 # define ctol   cto32
 357 # define ctpopl ctpop32
 358 #elif ULONG_MAX == UINT64_MAX
 359 # define clzl   clz64
 360 # define ctzl   ctz64
 361 # define clol   clo64
 362 # define ctol   cto64
 363 # define ctpopl ctpop64
 364 #else
 365 # error Unknown sizeof long
 366 #endif
 367
 368 #endif