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