]>
Commit | Line | Data |
---|---|---|
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 "compiler.h" /* QEMU_GNUC_PREREQ */ | |
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 | } |