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