include/llvm/Support/MathExtras.h

   1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 unsigned Hi_32(uint64_t Value) {
  27   return static_cast<unsigned>(Value >> 32);
  28 }
  29
  30 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
  31 inline unsigned Lo_32(uint64_t Value) {
  32   return static_cast<unsigned>(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<signed char>(Value) == Value;
  38 }
  39 inline bool isUInt8 (int64_t Value) {
  40   return static_cast<unsigned char>(Value) == Value;
  41 }
  42 inline bool isInt16 (int64_t Value) {
  43   return static_cast<signed short>(Value) == Value;
  44 }
  45 inline bool isUInt16(int64_t Value) {
  46   return static_cast<unsigned short>(Value) == Value;
  47 }
  48 inline bool isInt32 (int64_t Value) {
  49   return static_cast<signed int>(Value) == Value;
  50 }
  51 inline bool isUInt32(int64_t Value) {
  52   return static_cast<unsigned int>(Value) == Value;
  53 }
  54
  55 /// isMask_32 - This function returns true if the argument is a sequence of ones
  56 /// starting at the least significant bit with the remainder zero (32 bit
  57 /// version).   Ex. isMask_32(0x0000FFFFU) == true.
  58 inline const bool isMask_32(unsigned Value) {
  59   return Value && ((Value + 1) & Value) == 0;
  60 }
  61
  62 /// isMask_64 - This function returns true if the argument is a sequence of ones
  63 /// starting at the least significant bit with the remainder zero (64 bit
  64 /// version).
  65 inline const bool isMask_64(uint64_t Value) {
  66   return Value && ((Value + 1) & Value) == 0;
  67 }
  68
  69 /// isShiftedMask_32 - This function returns true if the argument contains a
  70 /// sequence of ones with the remainder zero (32 bit version.)
  71 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
  72 inline const bool isShiftedMask_32(unsigned Value) {
  73   return isMask_32((Value - 1) | Value);
  74 }
  75
  76 /// isShiftedMask_64 - This function returns true if the argument contains a
  77 /// sequence of ones with the remainder zero (64 bit version.)
  78 inline const bool isShiftedMask_64(uint64_t Value) {
  79   return isMask_64((Value - 1) | Value);
  80 }
  81
  82 /// isPowerOf2_32 - This function returns true if the argument is a power of
  83 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
  84 inline bool isPowerOf2_32(unsigned Value) {
  85   return Value && !(Value & (Value - 1));
  86 }
  87
  88 /// isPowerOf2_64 - This function returns true if the argument is a power of two
  89 /// > 0 (64 bit edition.)
  90 inline bool isPowerOf2_64(uint64_t Value) {
  91   return Value && !(Value & (Value - int64_t(1L)));
  92 }
  93
  94 /// ByteSwap_16 - This function returns a byte-swapped representation of the
  95 /// 16-bit argument, Value.
  96 inline unsigned short ByteSwap_16(unsigned short Value) {
  97   unsigned short Hi = Value << 8;
  98   unsigned short Lo = Value >> 8;
  99   return Hi | Lo;
 100 }
 101
 102 /// ByteSwap_32 - This function returns a byte-swapped representation of the
 103 /// 32-bit argument, Value.
 104 inline unsigned ByteSwap_32(unsigned Value) {
 105 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
 106         return __builtin_bswap32(Value);
 107 #else
 108   unsigned Byte0 = Value & 0x000000FF;
 109   unsigned Byte1 = Value & 0x0000FF00;
 110   unsigned Byte2 = Value & 0x00FF0000;
 111   unsigned Byte3 = Value & 0xFF000000;
 112   return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
 113 #endif
 114 }
 115
 116 /// ByteSwap_64 - This function returns a byte-swapped representation of the
 117 /// 64-bit argument, Value.
 118 inline uint64_t ByteSwap_64(uint64_t Value) {
 119 #if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)
 120         return __builtin_bswap64(Value);
 121 #else
 122   uint64_t Hi = ByteSwap_32(unsigned(Value));
 123   uint64_t Lo = ByteSwap_32(unsigned(Value >> 32));
 124   return (Hi << 32) | Lo;
 125 #endif
 126 }
 127
 128 /// CountLeadingZeros_32 - this function performs the platform optimal form of
 129 /// counting the number of zeros from the most significant bit to the first one
 130 /// bit.  Ex. CountLeadingZeros_32(0x00F000FF) == 8.
 131 /// Returns 32 if the word is zero.
 132 inline unsigned CountLeadingZeros_32(unsigned Value) {
 133   unsigned Count; // result
 134 #if __GNUC__ >= 4
 135   // PowerPC is defined for __builtin_clz(0)
 136 #if !defined(__ppc__) && !defined(__ppc64__)
 137   if (!Value) return 32;
 138 #endif
 139   Count = __builtin_clz(Value);
 140 #else
 141   if (!Value) return 32;
 142   Count = 0;
 143   // bisecton method for count leading zeros
 144   for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
 145     unsigned Tmp = Value >> Shift;
 146     if (Tmp) {
 147       Value = Tmp;
 148     } else {
 149       Count |= Shift;
 150     }
 151   }
 152 #endif
 153   return Count;
 154 }
 155
 156 /// CountLeadingZeros_64 - This function performs the platform optimal form
 157 /// of counting the number of zeros from the most significant bit to the first
 158 /// one bit (64 bit edition.)
 159 /// Returns 64 if the word is zero.
 160 inline unsigned CountLeadingZeros_64(uint64_t Value) {
 161   unsigned Count; // result
 162 #if __GNUC__ >= 4
 163   // PowerPC is defined for __builtin_clzll(0)
 164 #if !defined(__ppc__) && !defined(__ppc64__)
 165   if (!Value) return 64;
 166 #endif
 167   Count = __builtin_clzll(Value);
 168 #else
 169   if (sizeof(long) == sizeof(int64_t)) {
 170     if (!Value) return 64;
 171     Count = 0;
 172     // bisecton method for count leading zeros
 173     for (uint64_t Shift = 64 >> 1; Shift; Shift >>= 1) {
 174       uint64_t Tmp = Value >> Shift;
 175       if (Tmp) {
 176         Value = Tmp;
 177       } else {
 178         Count |= Shift;
 179       }
 180     }
 181   } else {
 182     // get hi portion
 183     unsigned Hi = Hi_32(Value);
 184
 185     // if some bits in hi portion
 186     if (Hi) {
 187         // leading zeros in hi portion plus all bits in lo portion
 188         Count = CountLeadingZeros_32(Hi);
 189     } else {
 190         // get lo portion
 191         unsigned Lo = Lo_32(Value);
 192         // same as 32 bit value
 193         Count = CountLeadingZeros_32(Lo)+32;
 194     }
 195   }
 196 #endif
 197   return Count;
 198 }
 199
 200 /// CountTrailingZeros_32 - this function performs the platform optimal form of
 201 /// counting the number of zeros from the least significant bit to the first one
 202 /// bit.  Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
 203 /// Returns 32 if the word is zero.
 204 inline unsigned CountTrailingZeros_32(unsigned Value) {
 205 #if __GNUC__ >= 4
 206   return Value ? __builtin_ctz(Value) : 32;
 207 #else
 208         const unsigned Mod37BitPosition[] = {32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
 209                                                    4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
 210                                                    5, 20, 8, 19, 18 };
 211         return Mod37BitPosition[(-Value & Value) % 37];
 212 #endif
 213 }
 214
 215 /// CountTrailingZeros_64 - This function performs the platform optimal form
 216 /// of counting the number of zeros from the least significant bit to the first
 217 /// one bit (64 bit edition.)
 218 /// Returns 64 if the word is zero.
 219 inline unsigned CountTrailingZeros_64(uint64_t Value) {
 220 #if __GNUC__ >= 4
 221   return Value ? __builtin_ctzll(Value) : 64;
 222 #else
 223   const unsigned Mod67Position[] = { 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         return Mod67Position[(-Value & Value) % 67];
 229 #endif
 230 }
 231
 232 /// CountPopulation_32 - this function counts the number of set bits in a value.
 233 /// Ex. CountPopulation(0xF000F000) = 8
 234 /// Returns 0 if the word is zero.
 235 inline unsigned CountPopulation_32(uint32_t Value) {
 236 #if __GNUC__ >= 4
 237   return __builtin_popcount(Value);
 238 #else
 239         uint32_t v = v - ((v >> 1) & 0x55555555);
 240         v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
 241         return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
 242 #endif
 243 }
 244
 245 /// CountPopulation_64 - this function counts the number of set bits in a value,
 246 /// (64 bit edition.)
 247 inline unsigned CountPopulation_64(uint64_t Value) {
 248 #if __GNUC__ >= 4
 249   return __builtin_popcountll(Value);
 250 #else
 251         uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
 252         v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
 253         v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
 254         return (uint64_t)(v * 0x0101010101010101ULL) >> 56;
 255 #endif
 256 }
 257
 258 /// Log2_32 - This function returns the floor log base 2 of the specified value,
 259 /// -1 if the value is zero. (32 bit edition.)
 260 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
 261 inline unsigned Log2_32(unsigned Value) {
 262     return 31 - CountLeadingZeros_32(Value);
 263 }
 264
 265 /// Log2_64 - This function returns the floor log base 2 of the specified value,
 266 /// -1 if the value is zero. (64 bit edition.)
 267 inline unsigned Log2_64(uint64_t Value) {
 268     return 63 - CountLeadingZeros_64(Value);
 269 }
 270
 271 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
 272 /// value, 32 if the value is zero. (32 bit edition).
 273 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
 274 inline unsigned Log2_32_Ceil(unsigned Value) {
 275   return 32-CountLeadingZeros_32(Value-1);
 276 }
 277
 278 /// Log2_64 - This function returns the ceil log base 2 of the specified value,
 279 /// 64 if the value is zero. (64 bit edition.)
 280 inline unsigned Log2_64_Ceil(uint64_t Value) {
 281   return 64-CountLeadingZeros_64(Value-1);
 282 }
 283
 284 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
 285 /// values using Euclid's algorithm.
 286 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
 287   while (B) {
 288     uint64_t T = B;
 289     B = A % B;
 290     A = T;
 291   }
 292   return A;
 293 }
 294
 295 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
 296 /// equivalent double.
 297 inline double BitsToDouble(uint64_t Bits) {
 298   union {
 299     uint64_t L;
 300     double D;
 301   } T;
 302   T.L = Bits;
 303   return T.D;
 304 }
 305
 306 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
 307 /// equivalent float.
 308 inline float BitsToFloat(uint32_t Bits) {
 309   union {
 310     uint32_t I;
 311     float F;
 312   } T;
 313   T.I = Bits;
 314   return T.F;
 315 }
 316
 317 /// DoubleToBits - This function takes a double and returns the bit
 318 /// equivalent 64-bit integer.
 319 inline uint64_t DoubleToBits(double Double) {
 320   union {
 321     uint64_t L;
 322     double D;
 323   } T;
 324   T.D = Double;
 325   return T.L;
 326 }
 327
 328 /// FloatToBits - This function takes a float and returns the bit
 329 /// equivalent 32-bit integer.
 330 inline uint32_t FloatToBits(float Float) {
 331   union {
 332     uint32_t I;
 333     float F;
 334   } T;
 335   T.F = Float;
 336   return T.I;
 337 }
 338
 339 /// Platform-independent wrappers for the C99 isnan() function.
 340 int IsNAN(float f);
 341 int IsNAN(double d);
 342
 343 /// Platform-independent wrappers for the C99 isinf() function.
 344 int IsInf(float f);
 345 int IsInf(double d);
 346
 347 } // End llvm namespace
 348
 349 #endif