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 | */ |
| 25 | |
ths | cebdff7 | 2008-06-05 22:55:54 +0000 | [diff] [blame] | 26 | #include "osdep.h" |
| 27 | |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 28 | #if defined(__x86_64__) |
| 29 | #define __HAVE_FAST_MULU64__ |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 30 | static inline void mulu64(uint64_t *plow, uint64_t *phigh, |
| 31 | uint64_t a, uint64_t b) |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 32 | { |
| 33 | __asm__ ("mul %0\n\t" |
| 34 | : "=d" (*phigh), "=a" (*plow) |
| 35 | : "a" (a), "0" (b)); |
| 36 | } |
| 37 | #define __HAVE_FAST_MULS64__ |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 38 | static inline void muls64(uint64_t *plow, uint64_t *phigh, |
| 39 | int64_t a, int64_t b) |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 40 | { |
| 41 | __asm__ ("imul %0\n\t" |
| 42 | : "=d" (*phigh), "=a" (*plow) |
| 43 | : "a" (a), "0" (b)); |
| 44 | } |
| 45 | #else |
j_mayer | 05e1d83 | 2007-11-05 13:16:23 +0000 | [diff] [blame] | 46 | 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] | 47 | void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); |
| 48 | #endif |
| 49 | |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 50 | /* Binary search for leading zeros. */ |
| 51 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 52 | static inline int clz32(uint32_t val) |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 53 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 54 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 55 | if (val) |
| 56 | return __builtin_clz(val); |
| 57 | else |
| 58 | return 32; |
| 59 | #else |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 60 | int cnt = 0; |
| 61 | |
| 62 | if (!(val & 0xFFFF0000U)) { |
| 63 | cnt += 16; |
| 64 | val <<= 16; |
| 65 | } |
| 66 | if (!(val & 0xFF000000U)) { |
| 67 | cnt += 8; |
| 68 | val <<= 8; |
| 69 | } |
| 70 | if (!(val & 0xF0000000U)) { |
| 71 | cnt += 4; |
| 72 | val <<= 4; |
| 73 | } |
| 74 | if (!(val & 0xC0000000U)) { |
| 75 | cnt += 2; |
| 76 | val <<= 2; |
| 77 | } |
| 78 | if (!(val & 0x80000000U)) { |
| 79 | cnt++; |
| 80 | val <<= 1; |
| 81 | } |
| 82 | if (!(val & 0x80000000U)) { |
| 83 | cnt++; |
| 84 | } |
| 85 | return cnt; |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 86 | #endif |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 87 | } |
| 88 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 89 | static inline int clo32(uint32_t val) |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 90 | { |
| 91 | return clz32(~val); |
| 92 | } |
| 93 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 94 | static inline int clz64(uint64_t val) |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 95 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 96 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 97 | if (val) |
| 98 | return __builtin_clzll(val); |
| 99 | else |
| 100 | return 64; |
| 101 | #else |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 102 | int cnt = 0; |
| 103 | |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 104 | if (!(val >> 32)) { |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 105 | cnt += 32; |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 106 | } else { |
| 107 | val >>= 32; |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 108 | } |
j_mayer | 7a51ad8 | 2007-11-04 02:24:58 +0000 | [diff] [blame] | 109 | |
| 110 | return cnt + clz32(val); |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 111 | #endif |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 112 | } |
| 113 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 114 | static inline int clo64(uint64_t val) |
ths | 05f778c | 2007-10-27 13:05:54 +0000 | [diff] [blame] | 115 | { |
| 116 | return clz64(~val); |
| 117 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 118 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 119 | static inline int ctz32(uint32_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 120 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 121 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 122 | if (val) |
| 123 | return __builtin_ctz(val); |
| 124 | else |
| 125 | return 32; |
| 126 | #else |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 127 | int cnt; |
| 128 | |
| 129 | cnt = 0; |
| 130 | if (!(val & 0x0000FFFFUL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 131 | cnt += 16; |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 132 | val >>= 16; |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 133 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 134 | if (!(val & 0x000000FFUL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 135 | cnt += 8; |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 136 | val >>= 8; |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 137 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 138 | if (!(val & 0x0000000FUL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 139 | cnt += 4; |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 140 | val >>= 4; |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 141 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 142 | if (!(val & 0x00000003UL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 143 | cnt += 2; |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 144 | val >>= 2; |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 145 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 146 | if (!(val & 0x00000001UL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 147 | cnt++; |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 148 | val >>= 1; |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 149 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 150 | if (!(val & 0x00000001UL)) { |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 151 | cnt++; |
| 152 | } |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 153 | |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 154 | return cnt; |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 155 | #endif |
balrog | c890684 | 2008-11-12 17:18:41 +0000 | [diff] [blame] | 156 | } |
| 157 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 158 | static inline int cto32(uint32_t val) |
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 | return ctz32(~val); |
| 161 | } |
| 162 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 163 | static inline int ctz64(uint64_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 164 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 165 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 166 | if (val) |
Richard Henderson | 0644524 | 2009-12-13 17:47:25 -0800 | [diff] [blame] | 167 | return __builtin_ctzll(val); |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 168 | else |
| 169 | return 64; |
| 170 | #else |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 171 | int cnt; |
| 172 | |
| 173 | cnt = 0; |
| 174 | if (!((uint32_t)val)) { |
| 175 | cnt += 32; |
| 176 | val >>= 32; |
| 177 | } |
| 178 | |
| 179 | return cnt + ctz32(val); |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 180 | #endif |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 181 | } |
| 182 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 183 | static inline int cto64(uint64_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 184 | { |
| 185 | return ctz64(~val); |
| 186 | } |
| 187 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 188 | static inline int ctpop8(uint8_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 189 | { |
| 190 | val = (val & 0x55) + ((val >> 1) & 0x55); |
| 191 | val = (val & 0x33) + ((val >> 2) & 0x33); |
| 192 | val = (val & 0x0f) + ((val >> 4) & 0x0f); |
| 193 | |
| 194 | return val; |
| 195 | } |
| 196 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 197 | static inline int ctpop16(uint16_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 198 | { |
| 199 | val = (val & 0x5555) + ((val >> 1) & 0x5555); |
| 200 | val = (val & 0x3333) + ((val >> 2) & 0x3333); |
| 201 | val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f); |
| 202 | val = (val & 0x00ff) + ((val >> 8) & 0x00ff); |
| 203 | |
| 204 | return val; |
| 205 | } |
| 206 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 207 | static inline int ctpop32(uint32_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 208 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 209 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 210 | return __builtin_popcount(val); |
| 211 | #else |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 212 | val = (val & 0x55555555) + ((val >> 1) & 0x55555555); |
| 213 | val = (val & 0x33333333) + ((val >> 2) & 0x33333333); |
| 214 | val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f); |
| 215 | val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff); |
| 216 | val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff); |
| 217 | |
| 218 | return val; |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 219 | #endif |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 220 | } |
| 221 | |
Blue Swirl | facd285 | 2009-08-16 08:03:26 +0000 | [diff] [blame] | 222 | static inline int ctpop64(uint64_t val) |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 223 | { |
aurel32 | bad5b1e | 2008-10-12 16:15:04 +0000 | [diff] [blame] | 224 | #if QEMU_GNUC_PREREQ(3, 4) |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 225 | return __builtin_popcountll(val); |
| 226 | #else |
j_mayer | b9ef45f | 2007-10-28 12:52:38 +0000 | [diff] [blame] | 227 | val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL); |
| 228 | val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL); |
| 229 | val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL); |
| 230 | val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL); |
| 231 | val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL); |
| 232 | val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL); |
| 233 | |
| 234 | return val; |
aurel32 | 7d01998 | 2008-10-12 00:53:08 +0000 | [diff] [blame] | 235 | #endif |
ths | 3800af9 | 2007-12-18 01:58:05 +0000 | [diff] [blame] | 236 | } |