Galois: MathExtras.h Source File

00001 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains some functions that are useful for math stuff.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
00015 #define LLVM_SUPPORT_MATHEXTRAS_H
00016 
00017 #include "llvm/Support/SwapByteOrder.h"
00018 
00019 namespace llvm {
00020 
00021 // NOTE: The following support functions use the _32/_64 extensions instead of
00022 // type overloading so that signed and unsigned integers can be used without
00023 // ambiguity.
00024 
00026 inline uint32_t Hi_32(uint64_t Value) {
00027   return static_cast<uint32_t>(Value >> 32);
00028 }
00029 
00031 inline uint32_t Lo_32(uint64_t Value) {
00032   return static_cast<uint32_t>(Value);
00033 }
00034 
00036 template<unsigned N>
00037 inline bool isInt(int64_t x) {
00038   return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
00039 }
00040 // Template specializations to get better code for common cases.
00041 template<>
00042 inline bool isInt<8>(int64_t x) {
00043   return static_cast<int8_t>(x) == x;
00044 }
00045 template<>
00046 inline bool isInt<16>(int64_t x) {
00047   return static_cast<int16_t>(x) == x;
00048 }
00049 template<>
00050 inline bool isInt<32>(int64_t x) {
00051   return static_cast<int32_t>(x) == x;
00052 }
00053 
00055 template<unsigned N>
00056 inline bool isUInt(uint64_t x) {
00057   return N >= 64 || x < (UINT64_C(1)<<N);
00058 }
00059 // Template specializations to get better code for common cases.
00060 template<>
00061 inline bool isUInt<8>(uint64_t x) {
00062   return static_cast<uint8_t>(x) == x;
00063 }
00064 template<>
00065 inline bool isUInt<16>(uint64_t x) {
00066   return static_cast<uint16_t>(x) == x;
00067 }
00068 template<>
00069 inline bool isUInt<32>(uint64_t x) {
00070   return static_cast<uint32_t>(x) == x;
00071 }
00072 
00075 inline bool isUIntN(unsigned N, uint64_t x) {
00076   return x == (x & (~0ULL >> (64 - N)));
00077 }
00078 
00081 inline bool isIntN(unsigned N, int64_t x) {
00082   return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
00083 }
00084 
00088 inline bool isMask_32(uint32_t Value) {
00089   return Value && ((Value + 1) & Value) == 0;
00090 }
00091 
00095 inline bool isMask_64(uint64_t Value) {
00096   return Value && ((Value + 1) & Value) == 0;
00097 }
00098 
00102 inline bool isShiftedMask_32(uint32_t Value) {
00103   return isMask_32((Value - 1) | Value);
00104 }
00105 
00108 inline bool isShiftedMask_64(uint64_t Value) {
00109   return isMask_64((Value - 1) | Value);
00110 }
00111 
00114 inline bool isPowerOf2_32(uint32_t Value) {
00115   return Value && !(Value & (Value - 1));
00116 }
00117 
00120 inline bool isPowerOf2_64(uint64_t Value) {
00121   return Value && !(Value & (Value - int64_t(1L)));
00122 }
00123 
00126 inline uint16_t ByteSwap_16(uint16_t Value) {
00127   return sys::SwapByteOrder_16(Value);
00128 }
00129 
00132 inline uint32_t ByteSwap_32(uint32_t Value) {
00133   return sys::SwapByteOrder_32(Value);
00134 }
00135 
00138 inline uint64_t ByteSwap_64(uint64_t Value) {
00139   return sys::SwapByteOrder_64(Value);
00140 }
00141 
00146 inline unsigned CountLeadingZeros_32(uint32_t Value) {
00147   unsigned Count; // result
00148 #if __GNUC__ >= 4
00149   // PowerPC is defined for __builtin_clz(0)
00150 #if !defined(__ppc__) && !defined(__ppc64__)
00151   if (!Value) return 32;
00152 #endif
00153   Count = __builtin_clz(Value);
00154 #else
00155   if (!Value) return 32;
00156   Count = 0;
00157   // bisection method for count leading zeros
00158   for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
00159     uint32_t Tmp = Value >> Shift;
00160     if (Tmp) {
00161       Value = Tmp;
00162     } else {
00163       Count |= Shift;
00164     }
00165   }
00166 #endif
00167   return Count;
00168 }
00169 
00174 inline unsigned CountLeadingOnes_32(uint32_t Value) {
00175   return CountLeadingZeros_32(~Value);
00176 }
00177 
00182 inline unsigned CountLeadingZeros_64(uint64_t Value) {
00183   unsigned Count; // result
00184 #if __GNUC__ >= 4
00185   // PowerPC is defined for __builtin_clzll(0)
00186 #if !defined(__ppc__) && !defined(__ppc64__)
00187   if (!Value) return 64;
00188 #endif
00189   Count = __builtin_clzll(Value);
00190 #else
00191   if (sizeof(long) == sizeof(int64_t)) {
00192     if (!Value) return 64;
00193     Count = 0;
00194     // bisection method for count leading zeros
00195     for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
00196       uint64_t Tmp = Value >> Shift;
00197       if (Tmp) {
00198         Value = Tmp;
00199       } else {
00200         Count |= Shift;
00201       }
00202     }
00203   } else {
00204     // get hi portion
00205     uint32_t Hi = Hi_32(Value);
00206 
00207     // if some bits in hi portion
00208     if (Hi) {
00209         // leading zeros in hi portion plus all bits in lo portion
00210         Count = CountLeadingZeros_32(Hi);
00211     } else {
00212         // get lo portion
00213         uint32_t Lo = Lo_32(Value);
00214         // same as 32 bit value
00215         Count = CountLeadingZeros_32(Lo)+32;
00216     }
00217   }
00218 #endif
00219   return Count;
00220 }
00221 
00226 inline unsigned CountLeadingOnes_64(uint64_t Value) {
00227   return CountLeadingZeros_64(~Value);
00228 }
00229 
00234 inline unsigned CountTrailingZeros_32(uint32_t Value) {
00235 #if __GNUC__ >= 4
00236   return Value ? __builtin_ctz(Value) : 32;
00237 #else
00238   static const unsigned Mod37BitPosition[] = {
00239     32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
00240     4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
00241     5, 20, 8, 19, 18
00242   };
00243   return Mod37BitPosition[(-Value & Value) % 37];
00244 #endif
00245 }
00246 
00251 inline unsigned CountTrailingOnes_32(uint32_t Value) {
00252   return CountTrailingZeros_32(~Value);
00253 }
00254 
00259 inline unsigned CountTrailingZeros_64(uint64_t Value) {
00260 #if __GNUC__ >= 4
00261   return Value ? __builtin_ctzll(Value) : 64;
00262 #else
00263   static const unsigned Mod67Position[] = {
00264     64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
00265     4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
00266     47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
00267     29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
00268     7, 48, 35, 6, 34, 33, 0
00269   };
00270   return Mod67Position[(-Value & Value) % 67];
00271 #endif
00272 }
00273 
00278 inline unsigned CountTrailingOnes_64(uint64_t Value) {
00279   return CountTrailingZeros_64(~Value);
00280 }
00281 
00285 inline unsigned CountPopulation_32(uint32_t Value) {
00286 #if __GNUC__ >= 4
00287   return __builtin_popcount(Value);
00288 #else
00289   uint32_t v = Value - ((Value >> 1) & 0x55555555);
00290   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
00291   return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
00292 #endif
00293 }
00294 
00297 inline unsigned CountPopulation_64(uint64_t Value) {
00298 #if __GNUC__ >= 4
00299   return __builtin_popcountll(Value);
00300 #else
00301   uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
00302   v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
00303   v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
00304   return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
00305 #endif
00306 }
00307 
00311 inline unsigned Log2_32(uint32_t Value) {
00312   return 31 - CountLeadingZeros_32(Value);
00313 }
00314 
00317 inline unsigned Log2_64(uint64_t Value) {
00318   return 63 - CountLeadingZeros_64(Value);
00319 }
00320 
00324 inline unsigned Log2_32_Ceil(uint32_t Value) {
00325   return 32-CountLeadingZeros_32(Value-1);
00326 }
00327 
00330 inline unsigned Log2_64_Ceil(uint64_t Value) {
00331   return 64-CountLeadingZeros_64(Value-1);
00332 }
00333 
00336 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
00337   while (B) {
00338     uint64_t T = B;
00339     B = A % B;
00340     A = T;
00341   }
00342   return A;
00343 }
00344 
00347 inline double BitsToDouble(uint64_t Bits) {
00348   union {
00349     uint64_t L;
00350     double D;
00351   } T;
00352   T.L = Bits;
00353   return T.D;
00354 }
00355 
00358 inline float BitsToFloat(uint32_t Bits) {
00359   union {
00360     uint32_t I;
00361     float F;
00362   } T;
00363   T.I = Bits;
00364   return T.F;
00365 }
00366 
00371 inline uint64_t DoubleToBits(double Double) {
00372   union {
00373     uint64_t L;
00374     double D;
00375   } T;
00376   T.D = Double;
00377   return T.L;
00378 }
00379 
00384 inline uint32_t FloatToBits(float Float) {
00385   union {
00386     uint32_t I;
00387     float F;
00388   } T;
00389   T.F = Float;
00390   return T.I;
00391 }
00392 
00394 int IsNAN(float f);
00395 int IsNAN(double d);
00396 
00398 int IsInf(float f);
00399 int IsInf(double d);
00400 
00403 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
00404   // The largest power of 2 that divides both A and B.
00405   return (A | B) & -(A | B);
00406 }
00407 
00410 static inline uint64_t NextPowerOf2(uint64_t A) {
00411   A |= (A >> 1);
00412   A |= (A >> 2);
00413   A |= (A >> 4);
00414   A |= (A >> 8);
00415   A |= (A >> 16);
00416   A |= (A >> 32);
00417   return A + 1;
00418 }
00419 
00428 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
00429   return ((Value + Align - 1) / Align) * Align;
00430 }
00431 
00435 inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
00436   return RoundUpToAlignment(Value, Align) - Value;
00437 }
00438 
00442 inline int64_t abs64(int64_t x) {
00443   return (x < 0) ? -x : x;
00444 }
00445 
00448 template <unsigned B> inline int32_t SignExtend32(uint32_t x) {
00449   return int32_t(x << (32 - B)) >> (32 - B);
00450 }
00451 
00454 template <unsigned B> inline int64_t SignExtend64(uint64_t x) {
00455   return int64_t(x << (64 - B)) >> (64 - B);
00456 }
00457 
00458 } // End llvm namespace
00459 
00460 #endif