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__
mulu64(uint64_t * plow,uint64_t * phigh,uint64_t a,uint64_t b)30 static 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__
muls64(uint64_t * plow,uint64_t * phigh,int64_t a,int64_t b)38 static 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
46 void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
47 void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
48 #endif
49
50 /* Binary search for leading zeros. */
51
clz32(uint32_t val)52 static 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
clo32(uint32_t val)89 static inline int clo32(uint32_t val)
90 {
91 return clz32(~val);
92 }
93
clz64(uint64_t val)94 static 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
clo64(uint64_t val)114 static inline int clo64(uint64_t val)
115 {
116 return clz64(~val);
117 }
118
ctz32(uint32_t val)119 static 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
cto32(uint32_t val)158 static inline int cto32(uint32_t val)
159 {
160 return ctz32(~val);
161 }
162
ctz64(uint64_t val)163 static 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
cto64(uint64_t val)183 static inline int cto64(uint64_t val)
184 {
185 return ctz64(~val);
186 }
187
ctpop8(uint8_t val)188 static 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
ctpop16(uint16_t val)197 static 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
ctpop32(uint32_t val)207 static 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
ctpop64(uint64_t val)222 static 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