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 (at) 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. 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
