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