MathExtras.h

Go to the documentation of this file.

//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains some functions that are useful for math stuff.
//
//===----------------------------------------------------------------------===//
 
/* Capstone Disassembly Engine */
/* By Nguyen Anh Quynh <aquynh@gmail.com>, 2013-2015 */
 
#ifndef CS_LLVM_SUPPORT_MATHEXTRAS_H
#define CS_LLVM_SUPPORT_MATHEXTRAS_H
 
#if defined(_WIN32_WCE) && (_WIN32_WCE < 0x800)
#include "windowsce/intrin.h"
#elif defined(_MSC_VER)
#include <intrin.h>
#endif
 
#ifndef __cplusplus
#if defined (WIN32) || defined (WIN64) || defined (_WIN32) || defined (_WIN64)
#define inline /* inline */
#endif
#endif
 
// NOTE: The following support functions use the _32/_64 extensions instead of
// type overloading so that signed and unsigned integers can be used without
// ambiguity.
 
static inline uint32_t Hi_32(uint64_t Value) {
        return (uint32_t)(Value >> 32);
}
 
static inline uint32_t Lo_32(uint64_t Value) {
        return (uint32_t)(Value);
}
 
static inline bool isUIntN(unsigned N, uint64_t x) {
        return x == (x & (~0ULL >> (64 - N)));
}
 
//static inline bool isIntN(unsigned N, int64_t x) {
//  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
//}
 
static inline bool isMask_32(uint32_t Value) {
        return Value && ((Value + 1) & Value) == 0;
}
 
static inline bool isMask_64(uint64_t Value) {
        return Value && ((Value + 1) & Value) == 0;
}
 
static inline bool isShiftedMask_32(uint32_t Value) {
        return isMask_32((Value - 1) | Value);
}
 
static inline bool isShiftedMask_64(uint64_t Value) {
        return isMask_64((Value - 1) | Value);
}
 
static inline bool isPowerOf2_32(uint32_t Value) {
        return Value && !(Value & (Value - 1));
}
 
static inline unsigned CountLeadingZeros_32(uint32_t Value) {
        unsigned Count; // result
#if __GNUC__ >= 4
        // PowerPC is defined for __builtin_clz(0)
#if !defined(__ppc__) && !defined(__ppc64__)
        if (!Value) return 32;
#endif
        Count = __builtin_clz(Value);
#else
        unsigned Shift;
        if (!Value) return 32;
        Count = 0;
        // bisection method for count leading zeros
        for (Shift = 32 >> 1; Shift; Shift >>= 1) {
                uint32_t Tmp = Value >> Shift;
                if (Tmp) {
                        Value = Tmp;
                } else {
                        Count |= Shift;
                }
        }
#endif
        return Count;
}
 
static inline unsigned CountLeadingOnes_32(uint32_t Value) {
        return CountLeadingZeros_32(~Value);
}
 
static inline unsigned CountLeadingZeros_64(uint64_t Value) {
        unsigned Count; // result
#if __GNUC__ >= 4
        // PowerPC is defined for __builtin_clzll(0)
#if !defined(__ppc__) && !defined(__ppc64__)
        if (!Value) return 64;
#endif
        Count = __builtin_clzll(Value);
#else
#ifndef _MSC_VER
        unsigned Shift;
        if (sizeof(long) == sizeof(int64_t))
        {
                if (!Value) return 64;
                Count = 0;
                // bisection method for count leading zeros
                for (Shift = 64 >> 1; Shift; Shift >>= 1) {
                        uint64_t Tmp = Value >> Shift;
                        if (Tmp) {
                                Value = Tmp;
                        } else {
                                Count |= Shift;
                        }
                }
        }
        else
#endif
        {
                // get hi portion
                uint32_t Hi = Hi_32(Value);
 
                // if some bits in hi portion
                if (Hi) {
                        // leading zeros in hi portion plus all bits in lo portion
                        Count = CountLeadingZeros_32(Hi);
                } else {
                        // get lo portion
                        uint32_t Lo = Lo_32(Value);
                        // same as 32 bit value
                        Count = CountLeadingZeros_32(Lo)+32;
                }
        }
#endif
        return Count;
}
 
static inline unsigned CountLeadingOnes_64(uint64_t Value) {
        return CountLeadingZeros_64(~Value);
}
 
static inline unsigned CountTrailingZeros_32(uint32_t Value) {
#if __GNUC__ >= 4
        return Value ? __builtin_ctz(Value) : 32;
#else
        static const unsigned Mod37BitPosition[] = {
                32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
                4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
                5, 20, 8, 19, 18
        };
        // Replace "-Value" by "1+~Value" in the following commented code to avoid 
        // MSVC warning C4146
        //    return Mod37BitPosition[(-Value & Value) % 37];
        return Mod37BitPosition[((1 + ~Value) & Value) % 37];
#endif
}
 
static inline unsigned CountTrailingOnes_32(uint32_t Value) {
        return CountTrailingZeros_32(~Value);
}
 
static inline unsigned CountTrailingZeros_64(uint64_t Value) {
#if __GNUC__ >= 4
        return Value ? __builtin_ctzll(Value) : 64;
#else
        static const unsigned Mod67Position[] = {
                64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
                4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
                47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
                29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
                7, 48, 35, 6, 34, 33, 0
        };
        // Replace "-Value" by "1+~Value" in the following commented code to avoid 
        // MSVC warning C4146
        //    return Mod67Position[(-Value & Value) % 67];
        return Mod67Position[((1 + ~Value) & Value) % 67];
#endif
}
 
static inline unsigned CountTrailingOnes_64(uint64_t Value) {
        return CountTrailingZeros_64(~Value);
}
 
static inline unsigned CountPopulation_32(uint32_t Value) {
#if __GNUC__ >= 4
        return __builtin_popcount(Value);
#else
        uint32_t v = Value - ((Value >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
#endif
}
 
static inline unsigned CountPopulation_64(uint64_t Value) {
#if __GNUC__ >= 4
        return __builtin_popcountll(Value);
#else
        uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
        v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
        v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
        return (uint64_t)((v * 0x0101010101010101ULL) >> 56);
#endif
}
 
static inline unsigned Log2_32(uint32_t Value) {
        return 31 - CountLeadingZeros_32(Value);
}
 
static inline unsigned Log2_64(uint64_t Value) {
        return 63 - CountLeadingZeros_64(Value);
}
 
static inline unsigned Log2_32_Ceil(uint32_t Value) {
        return 32-CountLeadingZeros_32(Value-1);
}
 
static inline unsigned Log2_64_Ceil(uint64_t Value) {
        return 64-CountLeadingZeros_64(Value-1);
}
 
static inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
        while (B) {
                uint64_t T = B;
                B = A % B;
                A = T;
        }
        return A;
}
 
static inline double BitsToDouble(uint64_t Bits) {
        union {
                uint64_t L;
                double D;
        } T;
        T.L = Bits;
        return T.D;
}
 
static inline float BitsToFloat(uint32_t Bits) {
        union {
                uint32_t I;
                float F;
        } T;
        T.I = Bits;
        return T.F;
}
 
static inline uint64_t DoubleToBits(double Double) {
        union {
                uint64_t L;
                double D;
        } T;
        T.D = Double;
        return T.L;
}
 
static inline uint32_t FloatToBits(float Float) {
        union {
                uint32_t I;
                float F;
        } T;
        T.F = Float;
        return T.I;
}
 
static inline uint64_t MinAlign(uint64_t A, uint64_t B) {
        // The largest power of 2 that divides both A and B.
        //
        // Replace "-Value" by "1+~Value" in the following commented code to avoid 
        // MSVC warning C4146
        //    return (A | B) & -(A | B);
        return (A | B) & (1 + ~(A | B));
}
 
static inline uint64_t NextPowerOf2(uint64_t A) {
        A |= (A >> 1);
        A |= (A >> 2);
        A |= (A >> 4);
        A |= (A >> 8);
        A |= (A >> 16);
        A |= (A >> 32);
        return A + 1;
}
 
static inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
        return ((Value + Align - 1) / Align) * Align;
}
 
static inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
        return RoundUpToAlignment(Value, Align) - Value;
}
 
static inline int64_t abs64(int64_t x) {
        return (x < 0) ? -x : x;
}
 
static inline int32_t SignExtend32(uint32_t X, unsigned B) {
        return (int32_t)(X << (32 - B)) >> (32 - B);
}
 
static inline int64_t SignExtend64(uint64_t X, unsigned B) {
        return (int64_t)(X << (64 - B)) >> (64 - B);
}
 
static inline unsigned int countLeadingZeros(int x)
{
        int i;
        const unsigned bits = sizeof(x) * 8;
        unsigned count = bits;
 
        if (x < 0) {
                return 0;
        }
        for (i = bits; --i; ) {
                if (x == 0) break;
                count--;
                x >>= 1;
        }
 
        return count;
}
 
#endif