LLVM API Documentation

MathExtras.h

Go to the documentation of this 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/DataTypes.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 
00025 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
00026 inline uint32_t Hi_32(uint64_t Value) {
00027   return static_cast<uint32_t>(Value >> 32);
00028 }
00029 
00030 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
00031 inline uint32_t Lo_32(uint64_t Value) {
00032   return static_cast<uint32_t>(Value);
00033 }
00034 
00035 /// is?Type - these functions produce optimal testing for integer data types.
00036 inline bool isInt8  (int64_t Value) {
00037   return static_cast<int8_t>(Value) == Value;
00038 }
00039 inline bool isUInt8 (int64_t Value) {
00040   return static_cast<uint8_t>(Value) == Value;
00041 }
00042 inline bool isInt16 (int64_t Value) {
00043   return static_cast<int16_t>(Value) == Value;
00044 }
00045 inline bool isUInt16(int64_t Value) {
00046   return static_cast<uint16_t>(Value) == Value;
00047 }
00048 inline bool isInt32 (int64_t Value) {
00049   return static_cast<int32_t>(Value) == Value;
00050 }
00051 inline bool isUInt32(int64_t Value) {
00052   return static_cast<uint32_t>(Value) == Value;
00053 }
00054 
00055 template<unsigned N>
00056 inline bool isInt(int64_t x) {
00057   return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
00058 }
00059 
00060 template<unsigned N>
00061 inline bool isUint(uint64_t x) {
00062   return N >= 64 || x < (UINT64_C(1)<<N);
00063 }
00064 
00065 /// isMask_32 - This function returns true if the argument is a sequence of ones
00066 /// starting at the least significant bit with the remainder zero (32 bit
00067 /// version).   Ex. isMask_32(0x0000FFFFU) == true.
00068 inline bool isMask_32(uint32_t Value) {
00069   return Value && ((Value + 1) & Value) == 0;
00070 }
00071 
00072 /// isMask_64 - This function returns true if the argument is a sequence of ones
00073 /// starting at the least significant bit with the remainder zero (64 bit
00074 /// version).
00075 inline bool isMask_64(uint64_t Value) {
00076   return Value && ((Value + 1) & Value) == 0;
00077 }
00078 
00079 /// isShiftedMask_32 - This function returns true if the argument contains a
00080 /// sequence of ones with the remainder zero (32 bit version.)
00081 /// Ex. isShiftedMask_32(0x0000FF00U) == true.
00082 inline bool isShiftedMask_32(uint32_t Value) {
00083   return isMask_32((Value - 1) | Value);
00084 }
00085 
00086 /// isShiftedMask_64 - This function returns true if the argument contains a
00087 /// sequence of ones with the remainder zero (64 bit version.)
00088 inline bool isShiftedMask_64(uint64_t Value) {
00089   return isMask_64((Value - 1) | Value);
00090 }
00091 
00092 /// isPowerOf2_32 - This function returns true if the argument is a power of
00093 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
00094 inline bool isPowerOf2_32(uint32_t Value) {
00095   return Value && !(Value & (Value - 1));
00096 }
00097 
00098 /// isPowerOf2_64 - This function returns true if the argument is a power of two
00099 /// > 0 (64 bit edition.)
00100 inline bool isPowerOf2_64(uint64_t Value) {
00101   return Value && !(Value & (Value - int64_t(1L)));
00102 }
00103 
00104 /// ByteSwap_16 - This function returns a byte-swapped representation of the
00105 /// 16-bit argument, Value.
00106 inline uint16_t ByteSwap_16(uint16_t Value) {
00107 #if defined(_MSC_VER) && !defined(_DEBUG)
00108   // The DLL version of the runtime lacks these functions (bug!?), but in a
00109   // release build they're replaced with BSWAP instructions anyway.
00110   return _byteswap_ushort(Value);
00111 #else
00112   uint16_t Hi = Value << 8;
00113   uint16_t Lo = Value >> 8;
00114   return Hi | Lo;
00115 #endif
00116 }
00117 
00118 /// ByteSwap_32 - This function returns a byte-swapped representation of the
00119 /// 32-bit argument, Value.
00120 inline uint32_t ByteSwap_32(uint32_t Value) {
00121 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
00122   return __builtin_bswap32(Value);
00123 #elif defined(_MSC_VER) && !defined(_DEBUG)
00124   return _byteswap_ulong(Value);
00125 #else
00126   uint32_t Byte0 = Value & 0x000000FF;
00127   uint32_t Byte1 = Value & 0x0000FF00;
00128   uint32_t Byte2 = Value & 0x00FF0000;
00129   uint32_t Byte3 = Value & 0xFF000000;
00130   return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
00131 #endif
00132 }
00133 
00134 /// ByteSwap_64 - This function returns a byte-swapped representation of the
00135 /// 64-bit argument, Value.
00136 inline uint64_t ByteSwap_64(uint64_t Value) {
00137 #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) && !defined(__ICC)
00138   return __builtin_bswap64(Value);
00139 #elif defined(_MSC_VER) && !defined(_DEBUG)
00140   return _byteswap_uint64(Value);
00141 #else
00142   uint64_t Hi = ByteSwap_32(uint32_t(Value));
00143   uint32_t Lo = ByteSwap_32(uint32_t(Value >> 32));
00144   return (Hi << 32) | Lo;
00145 #endif
00146 }
00147 
00148 /// CountLeadingZeros_32 - this function performs the platform optimal form of
00149 /// counting the number of zeros from the most significant bit to the first one
00150 /// bit.  Ex. CountLeadingZeros_32(0x00F000FF) == 8.
00151 /// Returns 32 if the word is zero.
00152 inline unsigned CountLeadingZeros_32(uint32_t Value) {
00153   unsigned Count; // result
00154 #if __GNUC__ >= 4
00155   // PowerPC is defined for __builtin_clz(0)
00156 #if !defined(__ppc__) && !defined(__ppc64__)
00157   if (!Value) return 32;
00158 #endif
00159   Count = __builtin_clz(Value);
00160 #else
00161   if (!Value) return 32;
00162   Count = 0;
00163   // bisecton method for count leading zeros
00164   for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) {
00165     uint32_t Tmp = Value >> Shift;
00166     if (Tmp) {
00167       Value = Tmp;
00168     } else {
00169       Count |= Shift;
00170     }
00171   }
00172 #endif
00173   return Count;
00174 }
00175 
00176 /// CountLeadingOnes_32 - this function performs the operation of
00177 /// counting the number of ones from the most significant bit to the first zero
00178 /// bit.  Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
00179 /// Returns 32 if the word is all ones.
00180 inline unsigned CountLeadingOnes_32(uint32_t Value) {
00181   return CountLeadingZeros_32(~Value);
00182 }
00183 
00184 /// CountLeadingZeros_64 - This function performs the platform optimal form
00185 /// of counting the number of zeros from the most significant bit to the first
00186 /// one bit (64 bit edition.)
00187 /// Returns 64 if the word is zero.
00188 inline unsigned CountLeadingZeros_64(uint64_t Value) {
00189   unsigned Count; // result
00190 #if __GNUC__ >= 4
00191   // PowerPC is defined for __builtin_clzll(0)
00192 #if !defined(__ppc__) && !defined(__ppc64__)
00193   if (!Value) return 64;
00194 #endif
00195   Count = __builtin_clzll(Value);
00196 #else
00197   if (sizeof(long) == sizeof(int64_t)) {
00198     if (!Value) return 64;
00199     Count = 0;
00200     // bisecton method for count leading zeros
00201     for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) {
00202       uint64_t Tmp = Value >> Shift;
00203       if (Tmp) {
00204         Value = Tmp;
00205       } else {
00206         Count |= Shift;
00207       }
00208     }
00209   } else {
00210     // get hi portion
00211     uint32_t Hi = Hi_32(Value);
00212 
00213     // if some bits in hi portion
00214     if (Hi) {
00215         // leading zeros in hi portion plus all bits in lo portion
00216         Count = CountLeadingZeros_32(Hi);
00217     } else {
00218         // get lo portion
00219         uint32_t Lo = Lo_32(Value);
00220         // same as 32 bit value
00221         Count = CountLeadingZeros_32(Lo)+32;
00222     }
00223   }
00224 #endif
00225   return Count;
00226 }
00227 
00228 /// CountLeadingOnes_64 - This function performs the operation
00229 /// of counting the number of ones from the most significant bit to the first
00230 /// zero bit (64 bit edition.)
00231 /// Returns 64 if the word is all ones.
00232 inline unsigned CountLeadingOnes_64(uint64_t Value) {
00233   return CountLeadingZeros_64(~Value);
00234 }
00235 
00236 /// CountTrailingZeros_32 - this function performs the platform optimal form of
00237 /// counting the number of zeros from the least significant bit to the first one
00238 /// bit.  Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
00239 /// Returns 32 if the word is zero.
00240 inline unsigned CountTrailingZeros_32(uint32_t Value) {
00241 #if __GNUC__ >= 4
00242   return Value ? __builtin_ctz(Value) : 32;
00243 #else
00244   static const unsigned Mod37BitPosition[] = {
00245     32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
00246     4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
00247     5, 20, 8, 19, 18
00248   };
00249   return Mod37BitPosition[(-Value & Value) % 37];
00250 #endif
00251 }
00252 
00253 /// CountTrailingOnes_32 - this function performs the operation of
00254 /// counting the number of ones from the least significant bit to the first zero
00255 /// bit.  Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
00256 /// Returns 32 if the word is all ones.
00257 inline unsigned CountTrailingOnes_32(uint32_t Value) {
00258   return CountTrailingZeros_32(~Value);
00259 }
00260 
00261 /// CountTrailingZeros_64 - This function performs the platform optimal form
00262 /// of counting the number of zeros from the least significant bit to the first
00263 /// one bit (64 bit edition.)
00264 /// Returns 64 if the word is zero.
00265 inline unsigned CountTrailingZeros_64(uint64_t Value) {
00266 #if __GNUC__ >= 4
00267   return Value ? __builtin_ctzll(Value) : 64;
00268 #else
00269   static const unsigned Mod67Position[] = {
00270     64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
00271     4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
00272     47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
00273     29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
00274     7, 48, 35, 6, 34, 33, 0
00275   };
00276   return Mod67Position[(-Value & Value) % 67];
00277 #endif
00278 }
00279 
00280 /// CountTrailingOnes_64 - This function performs the operation
00281 /// of counting the number of ones from the least significant bit to the first
00282 /// zero bit (64 bit edition.)
00283 /// Returns 64 if the word is all ones.
00284 inline unsigned CountTrailingOnes_64(uint64_t Value) {
00285   return CountTrailingZeros_64(~Value);
00286 }
00287 
00288 /// CountPopulation_32 - this function counts the number of set bits in a value.
00289 /// Ex. CountPopulation(0xF000F000) = 8
00290 /// Returns 0 if the word is zero.
00291 inline unsigned CountPopulation_32(uint32_t Value) {
00292 #if __GNUC__ >= 4
00293   return __builtin_popcount(Value);
00294 #else
00295   uint32_t v = Value - ((Value >> 1) & 0x55555555);
00296   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
00297   return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
00298 #endif
00299 }
00300 
00301 /// CountPopulation_64 - this function counts the number of set bits in a value,
00302 /// (64 bit edition.)
00303 inline unsigned CountPopulation_64(uint64_t Value) {
00304 #if __GNUC__ >= 4
00305   return __builtin_popcountll(Value);
00306 #else
00307   uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
00308   v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
00309   v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
00310   return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
00311 #endif
00312 }
00313 
00314 /// Log2_32 - This function returns the floor log base 2 of the specified value,
00315 /// -1 if the value is zero. (32 bit edition.)
00316 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
00317 inline unsigned Log2_32(uint32_t Value) {
00318   return 31 - CountLeadingZeros_32(Value);
00319 }
00320 
00321 /// Log2_64 - This function returns the floor log base 2 of the specified value,
00322 /// -1 if the value is zero. (64 bit edition.)
00323 inline unsigned Log2_64(uint64_t Value) {
00324   return 63 - CountLeadingZeros_64(Value);
00325 }
00326 
00327 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
00328 /// value, 32 if the value is zero. (32 bit edition).
00329 /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
00330 inline unsigned Log2_32_Ceil(uint32_t Value) {
00331   return 32-CountLeadingZeros_32(Value-1);
00332 }
00333 
00334 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
00335 /// value, 64 if the value is zero. (64 bit edition.)
00336 inline unsigned Log2_64_Ceil(uint64_t Value) {
00337   return 64-CountLeadingZeros_64(Value-1);
00338 }
00339 
00340 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
00341 /// values using Euclid's algorithm.
00342 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
00343   while (B) {
00344     uint64_t T = B;
00345     B = A % B;
00346     A = T;
00347   }
00348   return A;
00349 }
00350 
00351 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
00352 /// equivalent double.
00353 inline double BitsToDouble(uint64_t Bits) {
00354   union {
00355     uint64_t L;
00356     double D;
00357   } T;
00358   T.L = Bits;
00359   return T.D;
00360 }
00361 
00362 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
00363 /// equivalent float.
00364 inline float BitsToFloat(uint32_t Bits) {
00365   union {
00366     uint32_t I;
00367     float F;
00368   } T;
00369   T.I = Bits;
00370   return T.F;
00371 }
00372 
00373 /// DoubleToBits - This function takes a double and returns the bit
00374 /// equivalent 64-bit integer.  Note that copying doubles around
00375 /// changes the bits of NaNs on some hosts, notably x86, so this
00376 /// routine cannot be used if these bits are needed.
00377 inline uint64_t DoubleToBits(double Double) {
00378   union {
00379     uint64_t L;
00380     double D;
00381   } T;
00382   T.D = Double;
00383   return T.L;
00384 }
00385 
00386 /// FloatToBits - This function takes a float and returns the bit
00387 /// equivalent 32-bit integer.  Note that copying floats around
00388 /// changes the bits of NaNs on some hosts, notably x86, so this
00389 /// routine cannot be used if these bits are needed.
00390 inline uint32_t FloatToBits(float Float) {
00391   union {
00392     uint32_t I;
00393     float F;
00394   } T;
00395   T.F = Float;
00396   return T.I;
00397 }
00398 
00399 /// Platform-independent wrappers for the C99 isnan() function.
00400 int IsNAN(float f);
00401 int IsNAN(double d);
00402 
00403 /// Platform-independent wrappers for the C99 isinf() function.
00404 int IsInf(float f);
00405 int IsInf(double d);
00406 
00407 /// MinAlign - A and B are either alignments or offsets.  Return the minimum
00408 /// alignment that may be assumed after adding the two together.
00409 static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
00410   // The largest power of 2 that divides both A and B.
00411   return (A | B) & -(A | B);
00412 }
00413 
00414 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
00415 /// that is strictly greater than A.  Returns zero on overflow.
00416 static inline uint64_t NextPowerOf2(uint64_t A) {
00417   A |= (A >> 1);
00418   A |= (A >> 2);
00419   A |= (A >> 4);
00420   A |= (A >> 8);
00421   A |= (A >> 16);
00422   A |= (A >> 32);
00423   return A + 1;
00424 }
00425 
00426 /// RoundUpToAlignment - Returns the next integer (mod 2**64) that is
00427 /// greater than or equal to \arg Value and is a multiple of \arg
00428 /// Align. Align must be non-zero.
00429 ///
00430 /// Examples:
00431 /// RoundUpToAlignment(5, 8) = 8
00432 /// RoundUpToAlignment(17, 8) = 24
00433 /// RoundUpToAlignment(~0LL, 8) = 0
00434 inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
00435   return ((Value + Align - 1) / Align) * Align;
00436 }
00437 
00438 /// abs64 - absolute value of a 64-bit int.  Not all environments support
00439 /// "abs" on whatever their name for the 64-bit int type is.  The absolute
00440 /// value of the largest negative number is undefined, as with "abs".
00441 inline int64_t abs64(int64_t x) {
00442   return (x < 0) ? -x : x;
00443 }
00444 
00445 } // End llvm namespace
00446 
00447 #endif