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