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#include "osdep.h"
27
28#if defined(__x86_64__)
29#define __HAVE_FAST_MULU64__
30static inline void mulu64(uint64_t *plow, uint64_t *phigh,
31                          uint64_t a, uint64_t b)
32{
33    __asm__ ("mul %0\n\t"
34             : "=d" (*phigh), "=a" (*plow)
35             : "a" (a), "0" (b));
36}
37#define __HAVE_FAST_MULS64__
38static inline void muls64(uint64_t *plow, uint64_t *phigh,
39                          int64_t a, int64_t b)
40{
41    __asm__ ("imul %0\n\t"
42             : "=d" (*phigh), "=a" (*plow)
43             : "a" (a), "0" (b));
44}
45#else
46void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
47void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
48#endif
49
50/* Binary search for leading zeros.  */
51
52static inline int clz32(uint32_t val)
53{
54#if QEMU_GNUC_PREREQ(3, 4)
55    if (val)
56        return __builtin_clz(val);
57    else
58        return 32;
59#else
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;
86#endif
87}
88
89static inline int clo32(uint32_t val)
90{
91    return clz32(~val);
92}
93
94static inline int clz64(uint64_t val)
95{
96#if QEMU_GNUC_PREREQ(3, 4)
97    if (val)
98        return __builtin_clzll(val);
99    else
100        return 64;
101#else
102    int cnt = 0;
103
104    if (!(val >> 32)) {
105        cnt += 32;
106    } else {
107        val >>= 32;
108    }
109
110    return cnt + clz32(val);
111#endif
112}
113
114static inline int clo64(uint64_t val)
115{
116    return clz64(~val);
117}
118
119static inline int ctz32(uint32_t val)
120{
121#if QEMU_GNUC_PREREQ(3, 4)
122    if (val)
123        return __builtin_ctz(val);
124    else
125        return 32;
126#else
127    int cnt;
128
129    cnt = 0;
130    if (!(val & 0x0000FFFFUL)) {
131        cnt += 16;
132        val >>= 16;
133    }
134    if (!(val & 0x000000FFUL)) {
135        cnt += 8;
136        val >>= 8;
137    }
138    if (!(val & 0x0000000FUL)) {
139        cnt += 4;
140        val >>= 4;
141    }
142    if (!(val & 0x00000003UL)) {
143        cnt += 2;
144        val >>= 2;
145    }
146    if (!(val & 0x00000001UL)) {
147        cnt++;
148        val >>= 1;
149    }
150    if (!(val & 0x00000001UL)) {
151        cnt++;
152    }
153
154    return cnt;
155#endif
156}
157
158static inline int cto32(uint32_t val)
159{
160    return ctz32(~val);
161}
162
163static inline int ctz64(uint64_t val)
164{
165#if QEMU_GNUC_PREREQ(3, 4)
166    if (val)
167        return __builtin_ctzll(val);
168    else
169        return 64;
170#else
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);
180#endif
181}
182
183static inline int cto64(uint64_t val)
184{
185    return ctz64(~val);
186}
187
188static inline int ctpop8(uint8_t val)
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
197static inline int ctpop16(uint16_t val)
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
207static inline int ctpop32(uint32_t val)
208{
209#if QEMU_GNUC_PREREQ(3, 4)
210    return __builtin_popcount(val);
211#else
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;
219#endif
220}
221
222static inline int ctpop64(uint64_t val)
223{
224#if QEMU_GNUC_PREREQ(3, 4)
225    return __builtin_popcountll(val);
226#else
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;
235#endif
236}
237