MathExtras.h revision 5005e27f9714f0eaa5b8b7a5a1f6751afa163f07
1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// 263b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman// 3b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// The LLVM Compiler Infrastructure 4b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 763b3afa98460ce38a1c48d3c44ef6edfdaf37b77Misha Brukman// 8b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell//===----------------------------------------------------------------------===// 954ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner// 1054ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner// This file contains some functions that are useful for math stuff. 1154ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner// 1254ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner//===----------------------------------------------------------------------===// 13cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner 14551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_SUPPORT_MATHEXTRAS_H 15551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_SUPPORT_MATHEXTRAS_H 16cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner 178b67f774e9c38b7718b2b300b628388f966df4e0Chandler Carruth#include "llvm/System/DataTypes.h" 184c099b8724abf993262366e2a871004a2777becbMichael J. Spencer#include "llvm/System/SwapByteOrder.h" 19cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner 20d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 21d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 22fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// NOTE: The following support functions use the _32/_64 extensions instead of 2389bfcd34cbd2f4c6bb2cafff0a5c2bff147fae11Chris Lattner// type overloading so that signed and unsigned integers can be used without 2489bfcd34cbd2f4c6bb2cafff0a5c2bff147fae11Chris Lattner// ambiguity. 2588c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 2649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Hi_32 - This function returns the high 32 bits of a 64 bit value. 27c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline uint32_t Hi_32(uint64_t Value) { 28c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen return static_cast<uint32_t>(Value >> 32); 2988c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 3088c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 3149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Lo_32 - This function returns the low 32 bits of a 64 bit value. 32c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline uint32_t Lo_32(uint64_t Value) { 33c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen return static_cast<uint32_t>(Value); 3488c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 3588c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 3634247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer/// isInt - Checks if an integer fits into the given bit width. 37d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesentemplate<unsigned N> 38d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Oleseninline bool isInt(int64_t x) { 39d4c00c0f558193b492aed9ab6aacf84bf1d3fb4eJakob Stoklund Olesen return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); 40d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesen} 4134247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer// Template specializations to get better code for common cases. 4234247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 4334247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isInt<8>(int64_t x) { 4434247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<int8_t>(x) == x; 4534247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 4634247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 4734247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isInt<16>(int64_t x) { 4834247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<int16_t>(x) == x; 4934247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 5034247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 5134247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isInt<32>(int64_t x) { 5234247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<int32_t>(x) == x; 5334247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 54d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesen 5534247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer/// isUInt - Checks if an unsigned integer fits into the given bit width. 56d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesentemplate<unsigned N> 5734247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isUInt(uint64_t x) { 58d4c00c0f558193b492aed9ab6aacf84bf1d3fb4eJakob Stoklund Olesen return N >= 64 || x < (UINT64_C(1)<<N); 59d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesen} 6034247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer// Template specializations to get better code for common cases. 6134247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 6234247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isUInt<8>(uint64_t x) { 6334247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<uint8_t>(x) == x; 6434247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 6534247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 6634247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isUInt<16>(uint64_t x) { 6734247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<uint16_t>(x) == x; 6834247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 6934247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramertemplate<> 7034247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramerinline bool isUInt<32>(uint64_t x) { 7134247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer return static_cast<uint32_t>(x) == x; 7234247a0f356edf45ae3ad9ce04e1f90a77c6dba7Benjamin Kramer} 73d6eb635d1a1317fc3d218056ec77ec242c2413cbJakob Stoklund Olesen 745005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohman/// isUIntN - Checks if an unsigned integer fits into the given (dynamic) 755005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohman/// bit width. 765005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohmaninline bool isUIntN(unsigned N, uint64_t x) { 775005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohman return x == (x & (~0ULL >> (64 - N))); 785005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohman} 795005e27f9714f0eaa5b8b7a5a1f6751afa163f07Dan Gohman 8049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// isMask_32 - This function returns true if the argument is a sequence of ones 8149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// starting at the least significant bit with the remainder zero (32 bit 8249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// version). Ex. isMask_32(0x0000FFFFU) == true. 8318a4c74136a9919dc3235d03c0e060f32d01f3b0Chris Lattnerinline bool isMask_32(uint32_t Value) { 8488c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return Value && ((Value + 1) & Value) == 0; 8588c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 8688c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 8749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// isMask_64 - This function returns true if the argument is a sequence of ones 8849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// starting at the least significant bit with the remainder zero (64 bit 8949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// version). 9018a4c74136a9919dc3235d03c0e060f32d01f3b0Chris Lattnerinline bool isMask_64(uint64_t Value) { 9188c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return Value && ((Value + 1) & Value) == 0; 9288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 9388c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 94fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// isShiftedMask_32 - This function returns true if the argument contains a 9549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// sequence of ones with the remainder zero (32 bit version.) 9649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Ex. isShiftedMask_32(0x0000FF00U) == true. 9718a4c74136a9919dc3235d03c0e060f32d01f3b0Chris Lattnerinline bool isShiftedMask_32(uint32_t Value) { 9888c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return isMask_32((Value - 1) | Value); 9988c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 10088c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 101fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// isShiftedMask_64 - This function returns true if the argument contains a 10249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// sequence of ones with the remainder zero (64 bit version.) 10318a4c74136a9919dc3235d03c0e060f32d01f3b0Chris Lattnerinline bool isShiftedMask_64(uint64_t Value) { 10488c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return isMask_64((Value - 1) | Value); 10588c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 10688c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 107fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// isPowerOf2_32 - This function returns true if the argument is a power of 10849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) 109c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline bool isPowerOf2_32(uint32_t Value) { 11088c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return Value && !(Value & (Value - 1)); 11188c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 11288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 11349e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// isPowerOf2_64 - This function returns true if the argument is a power of two 11449e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// > 0 (64 bit edition.) 11588c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattnerinline bool isPowerOf2_64(uint64_t Value) { 11619b7e0e0cabfa6dfc559c64e3d6ed053832c4047Reid Spencer return Value && !(Value & (Value - int64_t(1L))); 11788c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 11888c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner 11949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// ByteSwap_16 - This function returns a byte-swapped representation of the 12049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// 16-bit argument, Value. 121c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline uint16_t ByteSwap_16(uint16_t Value) { 1224c099b8724abf993262366e2a871004a2777becbMichael J. Spencer return sys::SwapByteOrder(Value); 1236fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman} 1246fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman 12549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// ByteSwap_32 - This function returns a byte-swapped representation of the 12649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// 32-bit argument, Value. 127c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline uint32_t ByteSwap_32(uint32_t Value) { 1284c099b8724abf993262366e2a871004a2777becbMichael J. Spencer return sys::SwapByteOrder(Value); 1296fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman} 1306fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman 13149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// ByteSwap_64 - This function returns a byte-swapped representation of the 13249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// 64-bit argument, Value. 1336fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begemaninline uint64_t ByteSwap_64(uint64_t Value) { 1344c099b8724abf993262366e2a871004a2777becbMichael J. Spencer return sys::SwapByteOrder(Value); 1356fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman} 1366fb3bd6a658940287789198d3207b0da04c0a4e6Nate Begeman 13749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountLeadingZeros_32 - this function performs the platform optimal form of 13849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// counting the number of zeros from the most significant bit to the first one 13949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// bit. Ex. CountLeadingZeros_32(0x00F000FF) == 8. 14049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Returns 32 if the word is zero. 141c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline unsigned CountLeadingZeros_32(uint32_t Value) { 14288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner unsigned Count; // result 143e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#if __GNUC__ >= 4 144e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner // PowerPC is defined for __builtin_clz(0) 145e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#if !defined(__ppc__) && !defined(__ppc64__) 146e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner if (!Value) return 32; 147e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#endif 148e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Count = __builtin_clz(Value); 149e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#else 150e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner if (!Value) return 32; 151e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Count = 0; 152452394d812816b05f626d414ce6dbd3b87d45a73Duncan Sands // bisection method for count leading zeros 153e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner for (unsigned Shift = 32 >> 1; Shift; Shift >>= 1) { 154c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen uint32_t Tmp = Value >> Shift; 155e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner if (Tmp) { 156e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Value = Tmp; 157e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner } else { 158e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Count |= Shift; 15988c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner } 160e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner } 161e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#endif 16288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return Count; 16388c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner} 164bb92f6fbf2c36b3530f33eb2e8d1842764ec9fddBrian Gaeke 165ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// CountLeadingOnes_32 - this function performs the operation of 166ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// counting the number of ones from the most significant bit to the first zero 167ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. 168ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// Returns 32 if the word is all ones. 169ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohmaninline unsigned CountLeadingOnes_32(uint32_t Value) { 170ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman return CountLeadingZeros_32(~Value); 171ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman} 172ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman 17349e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountLeadingZeros_64 - This function performs the platform optimal form 174fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// of counting the number of zeros from the most significant bit to the first 17549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// one bit (64 bit edition.) 17649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Returns 64 if the word is zero. 17788c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattnerinline unsigned CountLeadingZeros_64(uint64_t Value) { 17888c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner unsigned Count; // result 179e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#if __GNUC__ >= 4 180e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner // PowerPC is defined for __builtin_clzll(0) 18189bfcd34cbd2f4c6bb2cafff0a5c2bff147fae11Chris Lattner#if !defined(__ppc__) && !defined(__ppc64__) 182e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner if (!Value) return 64; 183e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#endif 184e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Count = __builtin_clzll(Value); 185e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner#else 1863b65576527b7e0098a401289f9245eb5266fda31Chris Lattner if (sizeof(long) == sizeof(int64_t)) { 18788c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner if (!Value) return 64; 18888c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner Count = 0; 189452394d812816b05f626d414ce6dbd3b87d45a73Duncan Sands // bisection method for count leading zeros 190c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen for (unsigned Shift = 64 >> 1; Shift; Shift >>= 1) { 19188c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner uint64_t Tmp = Value >> Shift; 19288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner if (Tmp) { 19388c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner Value = Tmp; 194e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner } else { 195e6ec587059eb142467cc8a5915946a3b308cb9b7Chris Lattner Count |= Shift; 19688c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner } 1973b65576527b7e0098a401289f9245eb5266fda31Chris Lattner } 1983b65576527b7e0098a401289f9245eb5266fda31Chris Lattner } else { 19988c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner // get hi portion 200c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen uint32_t Hi = Hi_32(Value); 201cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner 20288c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner // if some bits in hi portion 20388c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner if (Hi) { 20488c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner // leading zeros in hi portion plus all bits in lo portion 205865dc8f64f50b72dbc8acb7851e606357f9d81f1Chris Lattner Count = CountLeadingZeros_32(Hi); 20688c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner } else { 20788c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner // get lo portion 208c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Cohen uint32_t Lo = Lo_32(Value); 20988c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner // same as 32 bit value 210865dc8f64f50b72dbc8acb7851e606357f9d81f1Chris Lattner Count = CountLeadingZeros_32(Lo)+32; 21188c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner } 2123b65576527b7e0098a401289f9245eb5266fda31Chris Lattner } 2133b65576527b7e0098a401289f9245eb5266fda31Chris Lattner#endif 21488c606eb0cc5415ed367c24e073f7bb478501d34Chris Lattner return Count; 215e265504e82310266271fa2329b6ef8115bbe8244Chris Lattner} 216e265504e82310266271fa2329b6ef8115bbe8244Chris Lattner 217ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// CountLeadingOnes_64 - This function performs the operation 218fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// of counting the number of ones from the most significant bit to the first 219ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// zero bit (64 bit edition.) 220ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// Returns 64 if the word is all ones. 221ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohmaninline unsigned CountLeadingOnes_64(uint64_t Value) { 222ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman return CountLeadingZeros_64(~Value); 223ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman} 224ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman 22549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountTrailingZeros_32 - this function performs the platform optimal form of 22649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// counting the number of zeros from the least significant bit to the first one 22749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8. 22849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Returns 32 if the word is zero. 229c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline unsigned CountTrailingZeros_32(uint32_t Value) { 230c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#if __GNUC__ >= 4 231c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson return Value ? __builtin_ctz(Value) : 32; 232c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#else 23382a60eca8fb5761817960e75fd469246496f8dceChris Lattner static const unsigned Mod37BitPosition[] = { 23482a60eca8fb5761817960e75fd469246496f8dceChris Lattner 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 23582a60eca8fb5761817960e75fd469246496f8dceChris Lattner 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 23682a60eca8fb5761817960e75fd469246496f8dceChris Lattner 5, 20, 8, 19, 18 23782a60eca8fb5761817960e75fd469246496f8dceChris Lattner }; 238e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov return Mod37BitPosition[(-Value & Value) % 37]; 239c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#endif 24016d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman} 24116d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman 242ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// CountTrailingOnes_32 - this function performs the operation of 243ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// counting the number of ones from the least significant bit to the first zero 244ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. 245ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// Returns 32 if the word is all ones. 246ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohmaninline unsigned CountTrailingOnes_32(uint32_t Value) { 247ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman return CountTrailingZeros_32(~Value); 248ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman} 249ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman 25049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountTrailingZeros_64 - This function performs the platform optimal form 251fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// of counting the number of zeros from the least significant bit to the first 25249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// one bit (64 bit edition.) 25349e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Returns 64 if the word is zero. 25416d6ea526482e733fe3bc63929e94c9e88b6708dNate Begemaninline unsigned CountTrailingZeros_64(uint64_t Value) { 255c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#if __GNUC__ >= 4 256c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson return Value ? __builtin_ctzll(Value) : 64; 257c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#else 25882a60eca8fb5761817960e75fd469246496f8dceChris Lattner static const unsigned Mod67Position[] = { 25982a60eca8fb5761817960e75fd469246496f8dceChris Lattner 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54, 26082a60eca8fb5761817960e75fd469246496f8dceChris Lattner 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 26182a60eca8fb5761817960e75fd469246496f8dceChris Lattner 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 26282a60eca8fb5761817960e75fd469246496f8dceChris Lattner 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 26382a60eca8fb5761817960e75fd469246496f8dceChris Lattner 7, 48, 35, 6, 34, 33, 0 26482a60eca8fb5761817960e75fd469246496f8dceChris Lattner }; 265e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov return Mod67Position[(-Value & Value) % 67]; 266c100b96b1536ef92cadac28bd268da105a67d4a0Owen Anderson#endif 26716d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman} 26816d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman 269ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// CountTrailingOnes_64 - This function performs the operation 270fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// of counting the number of ones from the least significant bit to the first 271ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// zero bit (64 bit edition.) 272ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman/// Returns 64 if the word is all ones. 273ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohmaninline unsigned CountTrailingOnes_64(uint64_t Value) { 274ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman return CountTrailingZeros_64(~Value); 275ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman} 276ca2a0e1062545651efd20dca1f647b864ede4a39Dan Gohman 27749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountPopulation_32 - this function counts the number of set bits in a value. 27849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Ex. CountPopulation(0xF000F000) = 8 27949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Returns 0 if the word is zero. 2802a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Andersoninline unsigned CountPopulation_32(uint32_t Value) { 2812a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#if __GNUC__ >= 4 2822a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson return __builtin_popcount(Value); 2832a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#else 284e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov uint32_t v = Value - ((Value >> 1) & 0x55555555); 285e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 286e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 2872a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#endif 28816d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman} 28916d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman 29049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// CountPopulation_64 - this function counts the number of set bits in a value, 29149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// (64 bit edition.) 29216d6ea526482e733fe3bc63929e94c9e88b6708dNate Begemaninline unsigned CountPopulation_64(uint64_t Value) { 2932a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#if __GNUC__ >= 4 2942a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson return __builtin_popcountll(Value); 2952a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#else 296e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); 297e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 298e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; 299ca5183d445954a9b2a570d6bbba1bc2b00ad6442Jeff Cohen return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); 3002a934cb6072bb0840b39e899e02ad9dea95b18dcOwen Anderson#endif 30116d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman} 30216d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman 303fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// Log2_32 - This function returns the floor log base 2 of the specified value, 30449e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// -1 if the value is zero. (32 bit edition.) 30549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 306c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline unsigned Log2_32(uint32_t Value) { 307e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov return 31 - CountLeadingZeros_32(Value); 30816d6ea526482e733fe3bc63929e94c9e88b6708dNate Begeman} 30954ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner 310fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman/// Log2_64 - This function returns the floor log base 2 of the specified value, 31149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// -1 if the value is zero. (64 bit edition.) 3122be12faabb3ce2d2d3979c73ac65d466fdea5ec5Chris Lattnerinline unsigned Log2_64(uint64_t Value) { 313e6efc859398498c3a08a3f36e82c63a706ae0d7eAnton Korobeynikov return 63 - CountLeadingZeros_64(Value); 314cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner} 315cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner 31649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Log2_32_Ceil - This function returns the ceil log base 2 of the specified 31749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// value, 32 if the value is zero. (32 bit edition). 31849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 319c3c395cf5e401328836e81c18cb70eef1b9ea5acJeff Coheninline unsigned Log2_32_Ceil(uint32_t Value) { 3200683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner return 32-CountLeadingZeros_32(Value-1); 3210683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner} 3220683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner 32355b42513e1548554bfacc72d48ec3483c73fddf9Dan Gohman/// Log2_64_Ceil - This function returns the ceil log base 2 of the specified 32455b42513e1548554bfacc72d48ec3483c73fddf9Dan Gohman/// value, 64 if the value is zero. (64 bit edition.) 3250683c8cad920d241d44b126972d5cdd164dcc213Chris Lattnerinline unsigned Log2_64_Ceil(uint64_t Value) { 3260683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner return 64-CountLeadingZeros_64(Value-1); 3270683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner} 3280683c8cad920d241d44b126972d5cdd164dcc213Chris Lattner 32949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// GreatestCommonDivisor64 - Return the greatest common divisor of the two 33049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// values using Euclid's algorithm. 33149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattnerinline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) { 33249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner while (B) { 33349e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner uint64_t T = B; 33449e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner B = A % B; 33549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner A = T; 33649e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner } 33749e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner return A; 33849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner} 339fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 34049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// BitsToDouble - This function takes a 64-bit integer and returns the bit 34149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// equivalent double. 34259b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskeyinline double BitsToDouble(uint64_t Bits) { 34359b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey union { 34459b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey uint64_t L; 34559b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey double D; 34659b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey } T; 34759b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey T.L = Bits; 34859b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey return T.D; 34959b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey} 35059b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey 35149e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// BitsToFloat - This function takes a 32-bit integer and returns the bit 35249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// equivalent float. 353104338913500d007996056ad092e195009883a84Jim Laskeyinline float BitsToFloat(uint32_t Bits) { 35459b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey union { 355104338913500d007996056ad092e195009883a84Jim Laskey uint32_t I; 35659b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey float F; 35759b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey } T; 35859b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey T.I = Bits; 35959b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey return T.F; 36059b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey} 36159b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey 36249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// DoubleToBits - This function takes a double and returns the bit 363541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// equivalent 64-bit integer. Note that copying doubles around 364541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// changes the bits of NaNs on some hosts, notably x86, so this 365541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// routine cannot be used if these bits are needed. 36659b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskeyinline uint64_t DoubleToBits(double Double) { 36759b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey union { 36859b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey uint64_t L; 36959b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey double D; 37059b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey } T; 37159b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey T.D = Double; 37259b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey return T.L; 37359b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey} 37459b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey 37549e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// FloatToBits - This function takes a float and returns the bit 376541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// equivalent 32-bit integer. Note that copying floats around 377541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// changes the bits of NaNs on some hosts, notably x86, so this 378541ed9fd02ea48d2739f4a9dd681ba2d5da26886Dale Johannesen/// routine cannot be used if these bits are needed. 379104338913500d007996056ad092e195009883a84Jim Laskeyinline uint32_t FloatToBits(float Float) { 38059b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey union { 381104338913500d007996056ad092e195009883a84Jim Laskey uint32_t I; 38259b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey float F; 38359b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey } T; 38459b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey T.F = Float; 38559b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey return T.I; 38659b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey} 38759b8fcfa5f736dff4a08ebcac032935b6fd92f34Jim Laskey 38849e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Platform-independent wrappers for the C99 isnan() function. 38949e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattnerint IsNAN(float f); 39049e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattnerint IsNAN(double d); 3917764f4b2e0e550dc23f3c536f236f9abf86879dcBrian Gaeke 39249e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattner/// Platform-independent wrappers for the C99 isinf() function. 39349e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattnerint IsInf(float f); 39449e6a9bc94a115d674502009b396c1a22fb1b1a1Chris Lattnerint IsInf(double d); 395a7d03b466a41e68e11480ae6ca275140fe4c4507Brian Gaeke 396fd617d0143a158bc1c996445262d409280e7b0ccDuncan Sands/// MinAlign - A and B are either alignments or offsets. Return the minimum 397fd617d0143a158bc1c996445262d409280e7b0ccDuncan Sands/// alignment that may be assumed after adding the two together. 398dc97d4cb2f0eb99a8143272128b76ab45db4ab09Chris Lattnerstatic inline uint64_t MinAlign(uint64_t A, uint64_t B) { 399fd617d0143a158bc1c996445262d409280e7b0ccDuncan Sands // The largest power of 2 that divides both A and B. 400fd617d0143a158bc1c996445262d409280e7b0ccDuncan Sands return (A | B) & -(A | B); 401fd617d0143a158bc1c996445262d409280e7b0ccDuncan Sands} 402d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson 403d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson/// NextPowerOf2 - Returns the next power of two (in 64-bits) 404d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson/// that is strictly greater than A. Returns zero on overflow. 405d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Andersonstatic inline uint64_t NextPowerOf2(uint64_t A) { 406d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 1); 407d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 2); 408d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 4); 409d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 8); 410d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 16); 411d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson A |= (A >> 32); 412d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson return A + 1; 413d98a45d29a6047bd47d3a3cd83c13ac0dac851fbOwen Anderson} 414e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar 415e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// RoundUpToAlignment - Returns the next integer (mod 2**64) that is 416e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// greater than or equal to \arg Value and is a multiple of \arg 417e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// Align. Align must be non-zero. 418e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// 419e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// Examples: 420e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// RoundUpToAlignment(5, 8) = 8 421e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// RoundUpToAlignment(17, 8) = 24 422e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar/// RoundUpToAlignment(~0LL, 8) = 0 423e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbarinline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) { 424e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar return ((Value + Align - 1) / Align) * Align; 425e2a8dfefe5740377dbc323a84337c45d37410ea8Daniel Dunbar} 426fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 427eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar/// OffsetToAlignment - Return the offset to the next integer (mod 2**64) that 428eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar/// is greater than or equal to \arg Value and is a multiple of \arg 429eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar/// Align. Align must be non-zero. 430eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbarinline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) { 431eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar return RoundUpToAlignment(Value, Align) - Value; 432eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar} 433eccf22528f8b4c21cdbd2f620cbe39dbb38ea6e1Daniel Dunbar 4347b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen/// abs64 - absolute value of a 64-bit int. Not all environments support 4357b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen/// "abs" on whatever their name for the 64-bit int type is. The absolute 4367b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen/// value of the largest negative number is undefined, as with "abs". 4377b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johanneseninline int64_t abs64(int64_t x) { 4387b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen return (x < 0) ? -x : x; 4397b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen} 4407b9486ad4355a010d22e0737cee9cd7c7b747eceDale Johannesen 441b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen/// SignExtend32 - Sign extend B-bit number x to 32-bit int. 442b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen/// Usage int32_t r = SignExtend32<5>(x); 443adc6e06ff0c5950abda86574c2da1fc6b863b75cJakob Stoklund Olesentemplate <unsigned B> inline int32_t SignExtend32(uint32_t x) { 444adc6e06ff0c5950abda86574c2da1fc6b863b75cJakob Stoklund Olesen return int32_t(x << (32 - B)) >> (32 - B); 445b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen} 446b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen 447b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen/// SignExtend64 - Sign extend B-bit number x to 64-bit int. 448b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen/// Usage int64_t r = SignExtend64<5>(x); 449adc6e06ff0c5950abda86574c2da1fc6b863b75cJakob Stoklund Olesentemplate <unsigned B> inline int64_t SignExtend64(uint64_t x) { 450adc6e06ff0c5950abda86574c2da1fc6b863b75cJakob Stoklund Olesen return int64_t(x << (64 - B)) >> (64 - B); 451b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen} 452b68a3ee82a8a34f7bae1d68d76f574e76a5535efJohnny Chen 453d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 454d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 45554ea60c69e69b8e5a464a1d7688ceec5c68bacd5Chris Lattner#endif 456