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
32static 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
40static 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#else
48void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
49void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
50#endif
51
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 */
59static inline int clz32(uint32_t val)
60{
61#if QEMU_GNUC_PREREQ(3, 4)
62    return val ? __builtin_clz(val) : 32;
63#else
64    /* Binary search for the leading one bit.  */
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;
91#endif
92}
93
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 */
100static inline int clo32(uint32_t val)
101{
102    return clz32(~val);
103}
104
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 */
112static inline int clz64(uint64_t val)
113{
114#if QEMU_GNUC_PREREQ(3, 4)
115    return val ? __builtin_clzll(val) : 64;
116#else
117    int cnt = 0;
118
119    if (!(val >> 32)) {
120        cnt += 32;
121    } else {
122        val >>= 32;
123    }
124
125    return cnt + clz32(val);
126#endif
127}
128
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 */
135static inline int clo64(uint64_t val)
136{
137    return clz64(~val);
138}
139
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 */
147static inline int ctz32(uint32_t val)
148{
149#if QEMU_GNUC_PREREQ(3, 4)
150    return val ? __builtin_ctz(val) : 32;
151#else
152    /* Binary search for the trailing one bit.  */
153    int cnt;
154
155    cnt = 0;
156    if (!(val & 0x0000FFFFUL)) {
157        cnt += 16;
158        val >>= 16;
159    }
160    if (!(val & 0x000000FFUL)) {
161        cnt += 8;
162        val >>= 8;
163    }
164    if (!(val & 0x0000000FUL)) {
165        cnt += 4;
166        val >>= 4;
167    }
168    if (!(val & 0x00000003UL)) {
169        cnt += 2;
170        val >>= 2;
171    }
172    if (!(val & 0x00000001UL)) {
173        cnt++;
174        val >>= 1;
175    }
176    if (!(val & 0x00000001UL)) {
177        cnt++;
178    }
179
180    return cnt;
181#endif
182}
183
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 */
190static inline int cto32(uint32_t val)
191{
192    return ctz32(~val);
193}
194
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 */
202static inline int ctz64(uint64_t val)
203{
204#if QEMU_GNUC_PREREQ(3, 4)
205    return val ? __builtin_ctzll(val) : 64;
206#else
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);
216#endif
217}
218
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 */
225static inline int cto64(uint64_t val)
226{
227    return ctz64(~val);
228}
229
230/**
231 * ctpop8 - count the population of one bits in an 8-bit value.
232 * @val: The value to search
233 */
234static inline int ctpop8(uint8_t val)
235{
236#if QEMU_GNUC_PREREQ(3, 4)
237    return __builtin_popcount(val);
238#else
239    val = (val & 0x55) + ((val >> 1) & 0x55);
240    val = (val & 0x33) + ((val >> 2) & 0x33);
241    val = (val & 0x0f) + ((val >> 4) & 0x0f);
242
243    return val;
244#endif
245}
246
247/**
248 * ctpop16 - count the population of one bits in a 16-bit value.
249 * @val: The value to search
250 */
251static inline int ctpop16(uint16_t val)
252{
253#if QEMU_GNUC_PREREQ(3, 4)
254    return __builtin_popcount(val);
255#else
256    val = (val & 0x5555) + ((val >> 1) & 0x5555);
257    val = (val & 0x3333) + ((val >> 2) & 0x3333);
258    val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
259    val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
260
261    return val;
262#endif
263}
264
265/**
266 * ctpop32 - count the population of one bits in a 32-bit value.
267 * @val: The value to search
268 */
269static inline int ctpop32(uint32_t val)
270{
271#if QEMU_GNUC_PREREQ(3, 4)
272    return __builtin_popcount(val);
273#else
274    val = (val & 0x55555555) + ((val >>  1) & 0x55555555);
275    val = (val & 0x33333333) + ((val >>  2) & 0x33333333);
276    val = (val & 0x0f0f0f0f) + ((val >>  4) & 0x0f0f0f0f);
277    val = (val & 0x00ff00ff) + ((val >>  8) & 0x00ff00ff);
278    val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff);
279
280    return val;
281#endif
282}
283
284/**
285 * ctpop64 - count the population of one bits in a 64-bit value.
286 * @val: The value to search
287 */
288static inline int ctpop64(uint64_t val)
289{
290#if QEMU_GNUC_PREREQ(3, 4)
291    return __builtin_popcountll(val);
292#else
293    val = (val & 0x5555555555555555ULL) + ((val >>  1) & 0x5555555555555555ULL);
294    val = (val & 0x3333333333333333ULL) + ((val >>  2) & 0x3333333333333333ULL);
295    val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >>  4) & 0x0f0f0f0f0f0f0f0fULL);
296    val = (val & 0x00ff00ff00ff00ffULL) + ((val >>  8) & 0x00ff00ff00ff00ffULL);
297    val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL);
298    val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL);
299
300    return val;
301#endif
302}
303
304/* Host type specific sizes of these routines.  */
305
306#if ULONG_MAX == UINT32_MAX
307# define clzl   clz32
308# define ctzl   ctz32
309# define clol   clo32
310# define ctol   cto32
311# define ctpopl ctpop32
312#elif ULONG_MAX == UINT64_MAX
313# define clzl   clz64
314# define ctzl   ctz64
315# define clol   clo64
316# define ctol   cto64
317# define ctpopl ctpop64
318#else
319# error Unknown sizeof long
320#endif
321
322#endif
323