3292f73f7ca10124f8113b017a59030aecc0b1ff
[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         unsigned count = 0;
427         int i;
428         const unsigned bits = sizeof(x) * 8;
429
430         for (i = bits; --i; ) {
431                 if (x < 0) break;
432                 count++;
433                 x <<= 1;
434         }
435
436         return count;
437 }
438
439 #endif