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__
|
---|
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__
|
---|
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 |
|
---|
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 |
|
---|
89 | static inline int clo32(uint32_t val)
|
---|
90 | {
|
---|
91 | return clz32(~val);
|
---|
92 | }
|
---|
93 |
|
---|
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 |
|
---|
114 | static inline int clo64(uint64_t val)
|
---|
115 | {
|
---|
116 | return clz64(~val);
|
---|
117 | }
|
---|
118 |
|
---|
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 |
|
---|
158 | static inline int cto32(uint32_t val)
|
---|
159 | {
|
---|
160 | return ctz32(~val);
|
---|
161 | }
|
---|
162 |
|
---|
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 |
|
---|
183 | static inline int cto64(uint64_t val)
|
---|
184 | {
|
---|
185 | return ctz64(~val);
|
---|
186 | }
|
---|
187 |
|
---|
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 |
|
---|
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 |
|
---|
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 |
|
---|
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 | }
|
---|