blob: 0ddc17658295a9f9d4c1a05e45c8489efdfa5a7a [file] [log] [blame]
ths05f778c2007-10-27 13:05:54 +00001/*
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
thscebdff72008-06-05 22:55:54 +000026#include "osdep.h"
27
j_mayer7a51ad82007-11-04 02:24:58 +000028#if defined(__x86_64__)
29#define __HAVE_FAST_MULU64__
Blue Swirlfacd2852009-08-16 08:03:26 +000030static inline void mulu64(uint64_t *plow, uint64_t *phigh,
31 uint64_t a, uint64_t b)
j_mayer7a51ad82007-11-04 02:24:58 +000032{
33 __asm__ ("mul %0\n\t"
34 : "=d" (*phigh), "=a" (*plow)
35 : "a" (a), "0" (b));
36}
37#define __HAVE_FAST_MULS64__
Blue Swirlfacd2852009-08-16 08:03:26 +000038static inline void muls64(uint64_t *plow, uint64_t *phigh,
39 int64_t a, int64_t b)
j_mayer7a51ad82007-11-04 02:24:58 +000040{
41 __asm__ ("imul %0\n\t"
42 : "=d" (*phigh), "=a" (*plow)
43 : "a" (a), "0" (b));
44}
45#else
j_mayer05e1d832007-11-05 13:16:23 +000046void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
j_mayer7a51ad82007-11-04 02:24:58 +000047void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
48#endif
49
ths05f778c2007-10-27 13:05:54 +000050/* Binary search for leading zeros. */
51
Blue Swirlfacd2852009-08-16 08:03:26 +000052static inline int clz32(uint32_t val)
ths05f778c2007-10-27 13:05:54 +000053{
aurel32bad5b1e2008-10-12 16:15:04 +000054#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +000055 if (val)
56 return __builtin_clz(val);
57 else
58 return 32;
59#else
ths05f778c2007-10-27 13:05:54 +000060 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;
aurel327d019982008-10-12 00:53:08 +000086#endif
ths05f778c2007-10-27 13:05:54 +000087}
88
Blue Swirlfacd2852009-08-16 08:03:26 +000089static inline int clo32(uint32_t val)
ths05f778c2007-10-27 13:05:54 +000090{
91 return clz32(~val);
92}
93
Blue Swirlfacd2852009-08-16 08:03:26 +000094static inline int clz64(uint64_t val)
ths05f778c2007-10-27 13:05:54 +000095{
aurel32bad5b1e2008-10-12 16:15:04 +000096#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +000097 if (val)
98 return __builtin_clzll(val);
99 else
100 return 64;
101#else
ths05f778c2007-10-27 13:05:54 +0000102 int cnt = 0;
103
j_mayer7a51ad82007-11-04 02:24:58 +0000104 if (!(val >> 32)) {
ths05f778c2007-10-27 13:05:54 +0000105 cnt += 32;
j_mayer7a51ad82007-11-04 02:24:58 +0000106 } else {
107 val >>= 32;
ths05f778c2007-10-27 13:05:54 +0000108 }
j_mayer7a51ad82007-11-04 02:24:58 +0000109
110 return cnt + clz32(val);
aurel327d019982008-10-12 00:53:08 +0000111#endif
ths05f778c2007-10-27 13:05:54 +0000112}
113
Blue Swirlfacd2852009-08-16 08:03:26 +0000114static inline int clo64(uint64_t val)
ths05f778c2007-10-27 13:05:54 +0000115{
116 return clz64(~val);
117}
j_mayerb9ef45f2007-10-28 12:52:38 +0000118
Blue Swirlfacd2852009-08-16 08:03:26 +0000119static inline int ctz32(uint32_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000120{
aurel32bad5b1e2008-10-12 16:15:04 +0000121#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +0000122 if (val)
123 return __builtin_ctz(val);
124 else
125 return 32;
126#else
j_mayerb9ef45f2007-10-28 12:52:38 +0000127 int cnt;
128
129 cnt = 0;
130 if (!(val & 0x0000FFFFUL)) {
balrogc8906842008-11-12 17:18:41 +0000131 cnt += 16;
j_mayerb9ef45f2007-10-28 12:52:38 +0000132 val >>= 16;
balrogc8906842008-11-12 17:18:41 +0000133 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000134 if (!(val & 0x000000FFUL)) {
balrogc8906842008-11-12 17:18:41 +0000135 cnt += 8;
j_mayerb9ef45f2007-10-28 12:52:38 +0000136 val >>= 8;
balrogc8906842008-11-12 17:18:41 +0000137 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000138 if (!(val & 0x0000000FUL)) {
balrogc8906842008-11-12 17:18:41 +0000139 cnt += 4;
j_mayerb9ef45f2007-10-28 12:52:38 +0000140 val >>= 4;
balrogc8906842008-11-12 17:18:41 +0000141 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000142 if (!(val & 0x00000003UL)) {
balrogc8906842008-11-12 17:18:41 +0000143 cnt += 2;
j_mayerb9ef45f2007-10-28 12:52:38 +0000144 val >>= 2;
balrogc8906842008-11-12 17:18:41 +0000145 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000146 if (!(val & 0x00000001UL)) {
balrogc8906842008-11-12 17:18:41 +0000147 cnt++;
j_mayerb9ef45f2007-10-28 12:52:38 +0000148 val >>= 1;
balrogc8906842008-11-12 17:18:41 +0000149 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000150 if (!(val & 0x00000001UL)) {
balrogc8906842008-11-12 17:18:41 +0000151 cnt++;
152 }
j_mayerb9ef45f2007-10-28 12:52:38 +0000153
balrogc8906842008-11-12 17:18:41 +0000154 return cnt;
aurel327d019982008-10-12 00:53:08 +0000155#endif
balrogc8906842008-11-12 17:18:41 +0000156}
157
Blue Swirlfacd2852009-08-16 08:03:26 +0000158static inline int cto32(uint32_t val)
balrogc8906842008-11-12 17:18:41 +0000159{
j_mayerb9ef45f2007-10-28 12:52:38 +0000160 return ctz32(~val);
161}
162
Blue Swirlfacd2852009-08-16 08:03:26 +0000163static inline int ctz64(uint64_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000164{
aurel32bad5b1e2008-10-12 16:15:04 +0000165#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +0000166 if (val)
Richard Henderson06445242009-12-13 17:47:25 -0800167 return __builtin_ctzll(val);
aurel327d019982008-10-12 00:53:08 +0000168 else
169 return 64;
170#else
j_mayerb9ef45f2007-10-28 12:52:38 +0000171 int cnt;
172
173 cnt = 0;
174 if (!((uint32_t)val)) {
175 cnt += 32;
176 val >>= 32;
177 }
178
179 return cnt + ctz32(val);
aurel327d019982008-10-12 00:53:08 +0000180#endif
j_mayerb9ef45f2007-10-28 12:52:38 +0000181}
182
Blue Swirlfacd2852009-08-16 08:03:26 +0000183static inline int cto64(uint64_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000184{
185 return ctz64(~val);
186}
187
Blue Swirlfacd2852009-08-16 08:03:26 +0000188static inline int ctpop8(uint8_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000189{
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 Swirlfacd2852009-08-16 08:03:26 +0000197static inline int ctpop16(uint16_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000198{
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 Swirlfacd2852009-08-16 08:03:26 +0000207static inline int ctpop32(uint32_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000208{
aurel32bad5b1e2008-10-12 16:15:04 +0000209#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +0000210 return __builtin_popcount(val);
211#else
j_mayerb9ef45f2007-10-28 12:52:38 +0000212 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;
aurel327d019982008-10-12 00:53:08 +0000219#endif
j_mayerb9ef45f2007-10-28 12:52:38 +0000220}
221
Blue Swirlfacd2852009-08-16 08:03:26 +0000222static inline int ctpop64(uint64_t val)
j_mayerb9ef45f2007-10-28 12:52:38 +0000223{
aurel32bad5b1e2008-10-12 16:15:04 +0000224#if QEMU_GNUC_PREREQ(3, 4)
aurel327d019982008-10-12 00:53:08 +0000225 return __builtin_popcountll(val);
226#else
j_mayerb9ef45f2007-10-28 12:52:38 +0000227 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;
aurel327d019982008-10-12 00:53:08 +0000235#endif
ths3800af92007-12-18 01:58:05 +0000236}