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