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 CS_LLVM_SUPPORT_MATHEXTRAS_H
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.
39static 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.
44static 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.
50static 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.
63static 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).
70static 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.
77static 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.)
83static 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.)
89static 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.
97static 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.
126static 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.
134static 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.
184static 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.
192static 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.
212static 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.
220static 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.
242static 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.
249static 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.)
261static 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
275static 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.)
281static 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
288static 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.)
294static 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.
300static 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.
311static 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.
322static 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.
335static 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.
348static 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.
359static 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.
370static 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
389static 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.
396static 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".
403static 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.
409static 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.
415static 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.
426static 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