1 | //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file contains some functions that are useful for math stuff. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | /* Capstone Disassembly Engine */ |
15 | /* By Nguyen Anh Quynh <aquynh@gmail.com>, 2013-2014 */ |
16 | |
17 | #ifndef CS_LLVM_SUPPORT_MATHEXTRAS_H |
18 | #define |
19 | |
20 | #if !defined(_MSC_VER) || !defined(_KERNEL_MODE) |
21 | #include <stdint.h> |
22 | #endif |
23 | |
24 | #ifdef _MSC_VER |
25 | # include <intrin.h> |
26 | #endif |
27 | |
28 | #ifndef __cplusplus |
29 | #if defined (WIN32) || defined (WIN64) || defined (_WIN32) || defined (_WIN64) |
30 | #define inline /* inline */ |
31 | #endif |
32 | #endif |
33 | |
34 | // NOTE: The following support functions use the _32/_64 extensions instead of |
35 | // type overloading so that signed and unsigned integers can be used without |
36 | // ambiguity. |
37 | |
38 | /// Hi_32 - This function returns the high 32 bits of a 64 bit value. |
39 | static inline uint32_t Hi_32(uint64_t Value) { |
40 | return (uint32_t)(Value >> 32); |
41 | } |
42 | |
43 | /// Lo_32 - This function returns the low 32 bits of a 64 bit value. |
44 | static inline uint32_t Lo_32(uint64_t Value) { |
45 | return (uint32_t)(Value); |
46 | } |
47 | |
48 | /// isUIntN - Checks if an unsigned integer fits into the given (dynamic) |
49 | /// bit width. |
50 | static inline bool isUIntN(unsigned N, uint64_t x) { |
51 | return x == (x & (~0ULL >> (64 - N))); |
52 | } |
53 | |
54 | /// isIntN - Checks if an signed integer fits into the given (dynamic) |
55 | /// bit width. |
56 | //static inline bool isIntN(unsigned N, int64_t x) { |
57 | // return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); |
58 | //} |
59 | |
60 | /// isMask_32 - This function returns true if the argument is a sequence of ones |
61 | /// starting at the least significant bit with the remainder zero (32 bit |
62 | /// version). Ex. isMask_32(0x0000FFFFU) == true. |
63 | static inline bool isMask_32(uint32_t Value) { |
64 | return Value && ((Value + 1) & Value) == 0; |
65 | } |
66 | |
67 | /// isMask_64 - This function returns true if the argument is a sequence of ones |
68 | /// starting at the least significant bit with the remainder zero (64 bit |
69 | /// version). |
70 | static inline bool isMask_64(uint64_t Value) { |
71 | return Value && ((Value + 1) & Value) == 0; |
72 | } |
73 | |
74 | /// isShiftedMask_32 - This function returns true if the argument contains a |
75 | /// sequence of ones with the remainder zero (32 bit version.) |
76 | /// Ex. isShiftedMask_32(0x0000FF00U) == true. |
77 | static inline bool isShiftedMask_32(uint32_t Value) { |
78 | return isMask_32((Value - 1) | Value); |
79 | } |
80 | |
81 | /// isShiftedMask_64 - This function returns true if the argument contains a |
82 | /// sequence of ones with the remainder zero (64 bit version.) |
83 | static inline bool isShiftedMask_64(uint64_t Value) { |
84 | return isMask_64((Value - 1) | Value); |
85 | } |
86 | |
87 | /// isPowerOf2_32 - This function returns true if the argument is a power of |
88 | /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) |
89 | static inline bool isPowerOf2_32(uint32_t Value) { |
90 | return Value && !(Value & (Value - 1)); |
91 | } |
92 | |
93 | /// CountLeadingZeros_32 - this function performs the platform optimal form of |
94 | /// counting the number of zeros from the most significant bit to the first one |
95 | /// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8. |
96 | /// Returns 32 if the word is zero. |
97 | static inline unsigned CountLeadingZeros_32(uint32_t Value) { |
98 | unsigned Count; // result |
99 | #if __GNUC__ >= 4 |
100 | // PowerPC is defined for __builtin_clz(0) |
101 | #if !defined(__ppc__) && !defined(__ppc64__) |
102 | if (!Value) return 32; |
103 | #endif |
104 | Count = __builtin_clz(Value); |
105 | #else |
106 | unsigned Shift; |
107 | if (!Value) return 32; |
108 | Count = 0; |
109 | // bisection method for count leading zeros |
110 | for (Shift = 32 >> 1; Shift; Shift >>= 1) { |
111 | uint32_t Tmp = Value >> Shift; |
112 | if (Tmp) { |
113 | Value = Tmp; |
114 | } else { |
115 | Count |= Shift; |
116 | } |
117 | } |
118 | #endif |
119 | return Count; |
120 | } |
121 | |
122 | /// CountLeadingOnes_32 - this function performs the operation of |
123 | /// counting the number of ones from the most significant bit to the first zero |
124 | /// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. |
125 | /// Returns 32 if the word is all ones. |
126 | static inline unsigned CountLeadingOnes_32(uint32_t Value) { |
127 | return CountLeadingZeros_32(~Value); |
128 | } |
129 | |
130 | /// CountLeadingZeros_64 - This function performs the platform optimal form |
131 | /// of counting the number of zeros from the most significant bit to the first |
132 | /// one bit (64 bit edition.) |
133 | /// Returns 64 if the word is zero. |
134 | static inline unsigned CountLeadingZeros_64(uint64_t Value) { |
135 | unsigned Count; // result |
136 | #if __GNUC__ >= 4 |
137 | // PowerPC is defined for __builtin_clzll(0) |
138 | #if !defined(__ppc__) && !defined(__ppc64__) |
139 | if (!Value) return 64; |
140 | #endif |
141 | Count = __builtin_clzll(Value); |
142 | #else |
143 | #ifndef _MSC_VER |
144 | unsigned Shift; |
145 | if (sizeof(long) == sizeof(int64_t)) |
146 | { |
147 | if (!Value) return 64; |
148 | Count = 0; |
149 | // bisection method for count leading zeros |
150 | for (Shift = 64 >> 1; Shift; Shift >>= 1) { |
151 | uint64_t Tmp = Value >> Shift; |
152 | if (Tmp) { |
153 | Value = Tmp; |
154 | } else { |
155 | Count |= Shift; |
156 | } |
157 | } |
158 | } |
159 | else |
160 | #endif |
161 | { |
162 | // get hi portion |
163 | uint32_t Hi = Hi_32(Value); |
164 | |
165 | // if some bits in hi portion |
166 | if (Hi) { |
167 | // leading zeros in hi portion plus all bits in lo portion |
168 | Count = CountLeadingZeros_32(Hi); |
169 | } else { |
170 | // get lo portion |
171 | uint32_t Lo = Lo_32(Value); |
172 | // same as 32 bit value |
173 | Count = CountLeadingZeros_32(Lo)+32; |
174 | } |
175 | } |
176 | #endif |
177 | return Count; |
178 | } |
179 | |
180 | /// CountLeadingOnes_64 - This function performs the operation |
181 | /// of counting the number of ones from the most significant bit to the first |
182 | /// zero bit (64 bit edition.) |
183 | /// Returns 64 if the word is all ones. |
184 | static inline unsigned CountLeadingOnes_64(uint64_t Value) { |
185 | return CountLeadingZeros_64(~Value); |
186 | } |
187 | |
188 | /// CountTrailingZeros_32 - this function performs the platform optimal form of |
189 | /// counting the number of zeros from the least significant bit to the first one |
190 | /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8. |
191 | /// Returns 32 if the word is zero. |
192 | static inline unsigned CountTrailingZeros_32(uint32_t Value) { |
193 | #if __GNUC__ >= 4 |
194 | return Value ? __builtin_ctz(Value) : 32; |
195 | #else |
196 | static const unsigned Mod37BitPosition[] = { |
197 | 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, |
198 | 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, |
199 | 5, 20, 8, 19, 18 |
200 | }; |
201 | // Replace "-Value" by "1+~Value" in the following commented code to avoid |
202 | // MSVC warning C4146 |
203 | // return Mod37BitPosition[(-Value & Value) % 37]; |
204 | return Mod37BitPosition[((1 + ~Value) & Value) % 37]; |
205 | #endif |
206 | } |
207 | |
208 | /// CountTrailingOnes_32 - this function performs the operation of |
209 | /// counting the number of ones from the least significant bit to the first zero |
210 | /// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. |
211 | /// Returns 32 if the word is all ones. |
212 | static inline unsigned CountTrailingOnes_32(uint32_t Value) { |
213 | return CountTrailingZeros_32(~Value); |
214 | } |
215 | |
216 | /// CountTrailingZeros_64 - This function performs the platform optimal form |
217 | /// of counting the number of zeros from the least significant bit to the first |
218 | /// one bit (64 bit edition.) |
219 | /// Returns 64 if the word is zero. |
220 | static inline unsigned CountTrailingZeros_64(uint64_t Value) { |
221 | #if __GNUC__ >= 4 |
222 | return Value ? __builtin_ctzll(Value) : 64; |
223 | #else |
224 | static const unsigned Mod67Position[] = { |
225 | 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, |
226 | 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, |
227 | 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, |
228 | 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, |
229 | 7, 48, 35, 6, 34, 33, 0 |
230 | }; |
231 | // Replace "-Value" by "1+~Value" in the following commented code to avoid |
232 | // MSVC warning C4146 |
233 | // return Mod67Position[(-Value & Value) % 67]; |
234 | return Mod67Position[((1 + ~Value) & Value) % 67]; |
235 | #endif |
236 | } |
237 | |
238 | /// CountTrailingOnes_64 - This function performs the operation |
239 | /// of counting the number of ones from the least significant bit to the first |
240 | /// zero bit (64 bit edition.) |
241 | /// Returns 64 if the word is all ones. |
242 | static inline unsigned CountTrailingOnes_64(uint64_t Value) { |
243 | return CountTrailingZeros_64(~Value); |
244 | } |
245 | |
246 | /// CountPopulation_32 - this function counts the number of set bits in a value. |
247 | /// Ex. CountPopulation(0xF000F000) = 8 |
248 | /// Returns 0 if the word is zero. |
249 | static inline unsigned CountPopulation_32(uint32_t Value) { |
250 | #if __GNUC__ >= 4 |
251 | return __builtin_popcount(Value); |
252 | #else |
253 | uint32_t v = Value - ((Value >> 1) & 0x55555555); |
254 | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); |
255 | return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; |
256 | #endif |
257 | } |
258 | |
259 | /// CountPopulation_64 - this function counts the number of set bits in a value, |
260 | /// (64 bit edition.) |
261 | static inline unsigned CountPopulation_64(uint64_t Value) { |
262 | #if __GNUC__ >= 4 |
263 | return __builtin_popcountll(Value); |
264 | #else |
265 | uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); |
266 | v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); |
267 | v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; |
268 | return (uint64_t)((v * 0x0101010101010101ULL) >> 56); |
269 | #endif |
270 | } |
271 | |
272 | /// Log2_32 - This function returns the floor log base 2 of the specified value, |
273 | /// -1 if the value is zero. (32 bit edition.) |
274 | /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 |
275 | static inline unsigned Log2_32(uint32_t Value) { |
276 | return 31 - CountLeadingZeros_32(Value); |
277 | } |
278 | |
279 | /// Log2_64 - This function returns the floor log base 2 of the specified value, |
280 | /// -1 if the value is zero. (64 bit edition.) |
281 | static inline unsigned Log2_64(uint64_t Value) { |
282 | return 63 - CountLeadingZeros_64(Value); |
283 | } |
284 | |
285 | /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified |
286 | /// value, 32 if the value is zero. (32 bit edition). |
287 | /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 |
288 | static inline unsigned Log2_32_Ceil(uint32_t Value) { |
289 | return 32-CountLeadingZeros_32(Value-1); |
290 | } |
291 | |
292 | /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified |
293 | /// value, 64 if the value is zero. (64 bit edition.) |
294 | static inline unsigned Log2_64_Ceil(uint64_t Value) { |
295 | return 64-CountLeadingZeros_64(Value-1); |
296 | } |
297 | |
298 | /// GreatestCommonDivisor64 - Return the greatest common divisor of the two |
299 | /// values using Euclid's algorithm. |
300 | static inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { |
301 | while (B) { |
302 | uint64_t T = B; |
303 | B = A % B; |
304 | A = T; |
305 | } |
306 | return A; |
307 | } |
308 | |
309 | /// BitsToDouble - This function takes a 64-bit integer and returns the bit |
310 | /// equivalent double. |
311 | static inline double BitsToDouble(uint64_t Bits) { |
312 | union { |
313 | uint64_t L; |
314 | double D; |
315 | } T; |
316 | T.L = Bits; |
317 | return T.D; |
318 | } |
319 | |
320 | /// BitsToFloat - This function takes a 32-bit integer and returns the bit |
321 | /// equivalent float. |
322 | static inline float BitsToFloat(uint32_t Bits) { |
323 | union { |
324 | uint32_t I; |
325 | float F; |
326 | } T; |
327 | T.I = Bits; |
328 | return T.F; |
329 | } |
330 | |
331 | /// DoubleToBits - This function takes a double and returns the bit |
332 | /// equivalent 64-bit integer. Note that copying doubles around |
333 | /// changes the bits of NaNs on some hosts, notably x86, so this |
334 | /// routine cannot be used if these bits are needed. |
335 | static inline uint64_t DoubleToBits(double Double) { |
336 | union { |
337 | uint64_t L; |
338 | double D; |
339 | } T; |
340 | T.D = Double; |
341 | return T.L; |
342 | } |
343 | |
344 | /// FloatToBits - This function takes a float and returns the bit |
345 | /// equivalent 32-bit integer. Note that copying floats around |
346 | /// changes the bits of NaNs on some hosts, notably x86, so this |
347 | /// routine cannot be used if these bits are needed. |
348 | static inline uint32_t FloatToBits(float Float) { |
349 | union { |
350 | uint32_t I; |
351 | float F; |
352 | } T; |
353 | T.F = Float; |
354 | return T.I; |
355 | } |
356 | |
357 | /// MinAlign - A and B are either alignments or offsets. Return the minimum |
358 | /// alignment that may be assumed after adding the two together. |
359 | static inline uint64_t MinAlign(uint64_t A, uint64_t B) { |
360 | // The largest power of 2 that divides both A and B. |
361 | // |
362 | // Replace "-Value" by "1+~Value" in the following commented code to avoid |
363 | // MSVC warning C4146 |
364 | // return (A | B) & -(A | B); |
365 | return (A | B) & (1 + ~(A | B)); |
366 | } |
367 | |
368 | /// NextPowerOf2 - Returns the next power of two (in 64-bits) |
369 | /// that is strictly greater than A. Returns zero on overflow. |
370 | static inline uint64_t NextPowerOf2(uint64_t A) { |
371 | A |= (A >> 1); |
372 | A |= (A >> 2); |
373 | A |= (A >> 4); |
374 | A |= (A >> 8); |
375 | A |= (A >> 16); |
376 | A |= (A >> 32); |
377 | return A + 1; |
378 | } |
379 | |
380 | /// Returns the next integer (mod 2**64) that is greater than or equal to |
381 | /// \p Value and is a multiple of \p Align. \p Align must be non-zero. |
382 | /// |
383 | /// Examples: |
384 | /// \code |
385 | /// RoundUpToAlignment(5, 8) = 8 |
386 | /// RoundUpToAlignment(17, 8) = 24 |
387 | /// RoundUpToAlignment(~0LL, 8) = 0 |
388 | /// \endcode |
389 | static inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) { |
390 | return ((Value + Align - 1) / Align) * Align; |
391 | } |
392 | |
393 | /// Returns the offset to the next integer (mod 2**64) that is greater than |
394 | /// or equal to \p Value and is a multiple of \p Align. \p Align must be |
395 | /// non-zero. |
396 | static inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) { |
397 | return RoundUpToAlignment(Value, Align) - Value; |
398 | } |
399 | |
400 | /// abs64 - absolute value of a 64-bit int. Not all environments support |
401 | /// "abs" on whatever their name for the 64-bit int type is. The absolute |
402 | /// value of the largest negative number is undefined, as with "abs". |
403 | static inline int64_t abs64(int64_t x) { |
404 | return (x < 0) ? -x : x; |
405 | } |
406 | |
407 | /// \brief Sign extend number in the bottom B bits of X to a 32-bit int. |
408 | /// Requires 0 < B <= 32. |
409 | static inline int32_t SignExtend32(uint32_t X, unsigned B) { |
410 | return (int32_t)(X << (32 - B)) >> (32 - B); |
411 | } |
412 | |
413 | /// \brief Sign extend number in the bottom B bits of X to a 64-bit int. |
414 | /// Requires 0 < B <= 64. |
415 | static inline int64_t SignExtend64(uint64_t X, unsigned B) { |
416 | return (int64_t)(X << (64 - B)) >> (64 - B); |
417 | } |
418 | |
419 | /// \brief Count number of 0's from the most significant bit to the least |
420 | /// stopping at the first 1. |
421 | /// |
422 | /// Only unsigned integral types are allowed. |
423 | /// |
424 | /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are |
425 | /// valid arguments. |
426 | static inline unsigned int countLeadingZeros(int x) |
427 | { |
428 | unsigned count = 0; |
429 | int i; |
430 | const unsigned bits = sizeof(x) * 8; |
431 | |
432 | for (i = bits; --i; ) { |
433 | if (x < 0) break; |
434 | count++; |
435 | x <<= 1; |
436 | } |
437 | |
438 | return count; |
439 | } |
440 | |
441 | #endif |
442 | |