https://github.com/electronicarts/EAStdC/blob/master/include/EAStdC/EABitTricks.h Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code + Explore + All features + Documentation + GitHub Skills + Blog * Solutions + For + Enterprise + Teams + Startups + Education + By Solution + CI/CD & Automation + DevOps + DevSecOps + Case Studies + Customer Stories + Resources * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles + Repositories + Topics + Trending + Collections * Pricing [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this organization All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} electronicarts / EAStdC Public * Notifications * Fork 73 * Star 359 * Code * Issues 2 * Pull requests 4 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights Permalink master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create EAStdC/include/EAStdC/EABitTricks.h Go to file * Go to file T * Go to line L * * Copy path * Copy permalink This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. # Roberto Parolin minor whitespace changes Latest commit 8dc9e31 Feb 24, 2020 History 0 contributors Users who have contributed to this file 1566 lines (1364 sloc) 49.6 KB Raw Blame Edit this file E Open in GitHub Desktop * Open with Desktop * View raw * * View blame This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters //////////////////////////////////////////////////////////////////// /////////// // Copyright (c) Electronic Arts Inc. All rights reserved. //////////////////////////////////////////////////////////////////// /////////// //////////////////////////////////////////////////////////////////// ///////// // This is a list of C/C++ bit manipulation tricks. For example, it is // well-known that (x * 2) can be also accomplished with (x << 1). // And while this example may not be useful in practice, there are many // more such tricks which have real use, particularly for speeding up code. // // Notes: // * Twos-complement integer storage is assumed. Nearly all modern // processors use twos-complement storage. // * Some tricks assume that right shifts of signed values preserve // the sign. While nearly all modern processors and C/C++ compilers // support this, some primitive processors don't. By preserving sign, // we mean that signed binary (10000000 >> 1) gives (11000000). // * Only 'tricky' efficient solutions are provided. Obvious brute force loops // to do useful things aren't included. We attempt to use branchless and // loopless logic where possible. // * We don't cover magic number tricks for simplifying multiplication and // division by constants. For example (x * 17) can also be quickly accomplished // with ((x << 4) + x). Optimized integer multiplication and division tricks // such as this is something for a separate library. // * We don't cover floating point tricks. That is something for a separate library. // * Implementations here are written as standalone functions for readability. // However, the user may find that it's better in some cases to copy the implementation // to a macro or to simply copy the implementation directly inline into source // code. EABitTricks is meant to be a reference for copy and paste as much as // it is meant to be used as-is. // * Many of these functions are templated instead of taking a given integer // type such as uint32_t. The reason for this is that we want 64 bit support // and that can be had automatically in most cases by the use of templates. The // generated code will be exactly as fast as the case when templates are not used. // //////////////////////////////////////////////////////////////////// /////////// #ifndef EASTDC_EABITTRICKS_H #define EASTDC_EABITTRICKS_H #include #include #include #if defined(EA_COMPILER_MSVC) && (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64)) // We can use assembly intrinsics for some of these functions. EA_DISABLE_ALL_VC_WARNINGS() #include // VS2008 has an acknowledged bug that requires math.h (and possibly also string.h) to be #included before intrin.h. #include EA_RESTORE_ALL_VC_WARNINGS() #pragma intrinsic(_BitScanForward) #pragma intrinsic(_BitScanReverse) #if defined(EA_PROCESSOR_X86_64) #pragma intrinsic(_BitScanForward64) #pragma intrinsic(_BitScanReverse64) #endif #elif (defined(EA_COMPILER_GNUC) || defined(EA_COMPILER_CLANG)) && (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64)) #include #endif EA_DISABLE_VC_WARNING(6326 4146) // C6326: Potential comparison of a constant with another constant // C4146: unary minus operator applied to unsigned type, result still unsigned namespace EA { namespace StdC { namespace helper { //////////////////////////////////////////////////////////////////// /// // is_signed //////////////////////////////////////////////////////////////////// /// struct false_type { static const bool value = false; }; struct true_type { static const bool value = true; }; template struct is_signed : public false_type{}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type {}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type {}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type {}; template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type{}; #if (CHAR_MAX == SCHAR_MAX) template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type{}; #endif #ifndef EA_WCHAR_T_NON_NATIVE // If wchar_t is a native type instead of simply a define to an existing type... #if defined(__WCHAR_MAX__) && ((__WCHAR_MAX__ == 2147483647) || (__WCHAR_MAX__ == 32767)) // GCC defines __WCHAR_MAX__ for most platforms. template <> struct is_signed : public true_type{}; template <> struct is_signed : public true_type{}; #endif #endif #define bt_is_signed helper::is_signed::value ////////////////////////////////////////////// // add_signed ////////////////////////////////////////////// template struct add_signed { typedef T type; }; template<> struct add_signed { typedef signed char type; }; #if (defined(CHAR_MAX) && defined(UCHAR_MAX) && (CHAR_MAX == UCHAR_MAX)) // If char is unsigned (which is usually not the case)... template<> struct add_signed { typedef signed char type; }; #endif template<> struct add_signed { typedef short type; }; template<> struct add_signed { typedef int type; }; template<> struct add_signed { typedef long type; }; template<> struct add_signed { typedef long long type; }; #ifndef EA_WCHAR_T_NON_NATIVE // If wchar_t is a native type instead of simply a define to an existing type... #if (defined(__WCHAR_MAX__) && (__WCHAR_MAX__ == 4294967295U)) // If wchar_t is a 32 bit unsigned value... template<> struct add_signed { typedef int32_t type; }; #elif (defined(__WCHAR_MAX__) && (__WCHAR_MAX__ == 65535)) // If wchar_t is a 16 bit unsigned value... template<> struct add_signed { typedef int16_t type; }; #endif #endif #define bt_signed typename helper::add_signed::type // Must be used as part of a cast, as in (bt_signed) or static_cast () } //////////////////////////////////////////////////////////////////// //////// // Bit manipulation //////////////////////////////////////////////////////////////////// //////// /// TurnOffLowestBit /// How to turn off the lowest 1 bit in an integer. /// Returns 0 for an input of 0. /// Works with signed and unsigned integers. /// Example: /// 01011000 -> 01010000 template inline T TurnOffLowestBit(T x){ return (T)(x & (x - 1)); } /// IsolateLowestBit /// How to isolate the lowest 1 bit. /// Returns 0 for an input of 0. /// Example: /// 01011000 -> 00001000 template inline T IsolateLowestBit(T x){ return (T)(x & (0 - x)); } /// IsolateLowest0Bit /// How to isolate the lowest 0 bit. /// Returns 0 for an input of all bits set. /// Example: /// 10100111 -> 00001000 template inline T IsolateLowest0Bit(T x){ return (T)(~x & (x + 1)); } /// GetTrailing0Bits /// How to produce a mask of all low zeroes. /// Returns 0 for an input of all bits set. /// Example: /// 01011000 -> 00000111 template inline T GetTrailing0Bits(T x){ return (T)(~x & (x - 1)); } /// GetTrailing1And0Bits /// How to produce a mask of lowest 1 bit and all lower zeroes. /// Returns all bits set for an input of 0. /// Returns 1 for an input of all bits set. /// Example: /// 01011000 -> 00001111 template inline T GetTrailing1And0Bits(T x){ return (T)(x ^ (x - 1)); } /// PropogateLowestBitDownward /// How to propogate the lowest 1 bit downward. /// Returns all bits set for an input of 0. /// Example: /// 01011000 -> 01011111 template inline T PropogateLowestBitDownward(T x){ return (T)(x | (x - 1)); } /// TurnOffLowestContiguousBits /// How to turn off the lowest contiguous string of 1 bits. /// Returns 0 for an input of 0. /// Returns 0 for an input of all bits set. /// Example: /// 01011000 -> 01000000 template inline T TurnOffLowestContiguousBits(T x){ return (T)(((x | (x - 1)) + 1) & x); } /// TurnOnLowest0Bit /// How to turn off the lowest 0 bit in an integer. /// Returns all bits set for an input of all bits set. /// Example: /// 10100111 -> 10101111 template inline T TurnOnLowest0Bit(T x){ return (T)(x | (x + 1)); } /// GetNextWithEqualBitCount /// How to get the next higher integer with the same number of bits set. /// This function is supposed (claim by original author) to be able to /// wrap around and continue properly, but testing indicates otherwise. /// Do not call this with x = 0; as that causes a divide by 0. /// Doesn't work for an input of all bits set. /// Do not assign the result of this to a type of less size than the input argument. /// This function has certain real-world applications. /// This function has been called 'snoob' by some. /// Example: /// 01010110 -> 01011001 template inline T GetNextWithEqualBitCount(T x){ T smallest, ripple, ones; smallest = x & -(bt_signed)x; ripple = x + smallest; ones = x ^ ripple; ones = (ones >> 2) / smallest; return ripple | ones; } /// IsolateSingleBits /// How to isolate single bits in an integer. /// Example: /// 10101011 -> 10101000 template inline T IsolateSingleBits(T x){ return x & ~((x << 1) | (x >> 1)); } template inline T IsolateSingle0Bits(T x){ return IsolateSingleBits(~x); } template inline T IsolateSingle0And1Bits(T x){ return (x ^ (x << 1)) & (x ^ (x >> 1)); } /// ShiftRightSigned /// How to do a signed right shift portably. /// Some platform/compiler combinations don't support sign extension /// with right shifts of signed values. The C language standard doesn't /// guarantee such functionality. Most advanced CPUs and nearly all C /// compilers support this. Weak embedded processors may possibly not. /// Example: /// 10000000 - by 2-> 11100000 /// 00000000 - by 2-> 00000000 inline int32_t ShiftRightSigned(int32_t x, uint32_t n){ return int32_t((((uint32_t)x + UINT32_C(0x80000000)) >> n) - ( UINT32_C(0x80000000) >> n)); } inline int64_t ShiftRightSigned(int64_t x, uint64_t n){ return int64_t((((uint64_t)x + UINT64_C(0x8000000000000000)) >> n) - (UINT64_C(0x8000000000000000) >> n)); } /// CountTrailing0Bits /// How to count the number of trailing zeroes in an unsigned 32 bit integer. /// Example: /// ...10101000 -> 3 /// ...11111111 -> 0 /// ...00000000 -> 32 inline int CountTrailing0Bits(uint32_t x){ #if defined(EA_COMPILER_MSVC) && (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64)) // This has been benchmarked as significantly faster than the generic code below. unsigned char isNonZero; unsigned long index; isNonZero = _BitScanForward(&index, x); return isNonZero ? (int)index : 32; #elif defined(EA_COMPILER_GNUC) && !defined(EA_COMPILER_EDG) if(x) return __builtin_ctz(x); return 32; #else if(x){ int n = 1; if((x & 0x0000FFFF) == 0) {n += 16; x >>= 16;} if((x & 0x000000FF) == 0) {n += 8; x >>= 8;} if((x & 0x0000000F) == 0) {n += 4; x >>= 4;} if((x & 0x00000003) == 0) {n += 2; x >>= 2;} return n - int(x & 1); } return 32; #endif } /// CountTrailing0Bits /// How to count the number of trailing zeroes in an unsigned 64 bit integer. /// Example: /// ...10101000 -> 3 /// ...11111111 -> 0 /// ...00000000 -> 64 inline int CountTrailing0Bits(uint64_t x){ #if defined(EA_COMPILER_MSVC) && defined(EA_PROCESSOR_X86_64) // This has been benchmarked as significantly faster than the generic code below. unsigned char isNonZero; unsigned long index; isNonZero = _BitScanForward64(&index, x); return isNonZero ? (int)index : 64; #elif defined(EA_COMPILER_GNUC) && !defined(EA_COMPILER_EDG) if(x) return __builtin_ctzll(x); return 64; #else if(x){ int n = 1; if((x & 0xFFFFFFFF) == 0) { n += 32; x >>= 32; } if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; } if((x & 0x000000FF) == 0) { n += 8; x >>= 8; } if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } if((x & 0x00000003) == 0) { n += 2; x >>= 2; } return n - (int)(unsigned)(x & 1); } return 64; #endif } /// CountLeading0Bits /// How to count the number of leading zeroes in an unsigned integer. /// Example: /// ..00000000 -> 32 /// 00110111 -> 2 /// 11111111 -> 0 /// inline int CountLeading0Bits(uint32_t x){ #if defined(EA_COMPILER_MSVC) && (defined(EA_PROCESSOR_X86) || defined(EA_PROCESSOR_X86_64)) // This has been benchmarked as significantly faster than the generic code below. unsigned char isNonZero; unsigned long index; isNonZero = _BitScanReverse(&index, x); return isNonZero ? (31 - (int)index) : 32; #elif defined(EA_COMPILER_GNUC) && !defined(EA_COMPILER_EDG) if(x) return __builtin_clz(x); return 32; #else /// This implementation isn't highly compact, but would likely be /// faster than a brute force solution. /// x86 function which is claimed to be faster: /// double ff = (double)(v|1); /// return ((*(1+(unsigned long *)&ff))>>20)-1023; if(x){ int n = 0; if(x <= 0x0000FFFF) { n += 16; x <<= 16; } if(x <= 0x00FFFFFF) { n += 8; x <<= 8; } if(x <= 0x0FFFFFFF) { n += 4; x <<= 4; } if(x <= 0x3FFFFFFF) { n += 2; x <<= 2; } if(x <= 0x7FFFFFFF) { n += 1; } return n; } return 32; #endif } /// CountLeading0Bits /// How to count the number of leading zeroes in an unsigned integer. /// Example: /// ..00000000 -> 64 /// ..00110111 -> 2 /// ..11111111 -> 0 /// inline int CountLeading0Bits(uint64_t x){ #if defined(EA_COMPILER_MSVC) && defined(EA_PROCESSOR_X86_64) // This has been benchmarked as significantly faster than the generic code below. unsigned char isNonZero; unsigned long index; isNonZero = _BitScanReverse64(&index, x); return isNonZero ? (63 - (int)index) : 64; #elif defined(EA_COMPILER_GNUC) && !defined(EA_COMPILER_EDG) if(x) return __builtin_clzll(x); return 64; #else if(x){ // We use a slightly different algorithm than the 32 bit version above because this version avoids slow large 64 bit constants, especially on RISC processors. int n = 0; if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; } if(x & 0xFFFF0000) { n += 16; x >>= 16; } if(x & 0xFFFFFF00) { n += 8; x >>= 8; } if(x & 0xFFFFFFF0) { n += 4; x >>= 4; } if(x & 0xFFFFFFFC) { n += 2; x >>= 2; } if(x & 0xFFFFFFFE) { n += 1; } return 63 - n; } return 64; #endif } /// CountBits /// How to count the number of bits in an unsigned integer. /// There are multiple variations of this function available, /// each tuned to the expected bit counts and locations. /// The version presented here has a large number of logical /// operations but has no looping or branching. /// This implementation is taken from the AMD x86 optimization guide. /// Example: /// 11001010 -> 4 inline int CountBits(uint32_t x) // Branchless version { #if defined(EASTDC_SSE_POPCNT) return _mm_popcnt_u32(x); #else x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; return (int)((x * 0x01010101) >> 24); #endif } inline int CountBits64(uint64_t x) // Branchless version { #if defined(EASTDC_SSE_POPCNT) && defined(EA_PROCESSOR_X86_64) return (int)_mm_popcnt_u64(x); #else #if (EA_PLATFORM_WORD_SIZE < 8) return CountBits((uint32_t)(x >> 32)) + CountBits((uint32_t)x); #else x = x - ((x >> 1) & UINT64_C(0x5555555555555555)); x = (x & UINT64_C(0x3333333333333333)) + ((x >> 2) & UINT64_C( 0x3333333333333333)); x = (x + (x >> 4)) & UINT64_C(0x0F0F0F0F0F0F0F0F); return (int)((x * UINT64_C(0x0101010101010101)) >> 56); #endif #endif } /// RotateLeft /// How to rotate an integer left. /// Bit rotations can often be accomplished with inline assembly /// that uses the processor's native bit rotation capabilities. /// Example: /// 11110000 -> left 2 -> 11000011 inline uint32_t RotateLeft(uint32_t x, uint32_t n){ return (uint32_t)((x << n) | (x >> (32 - n))); } inline uint64_t RotateLeft(uint64_t x, uint64_t n){ return (uint64_t)((x << n) | (x >> (64 - n))); } inline uint32_t RotateRight(uint32_t x, uint32_t n){ return (uint32_t)((x >> n) | (x << (32 - n))); } inline uint64_t RotateRight(uint64_t x, uint64_t n){ return (uint64_t)((x >> n) | (x << (64 - n))); } /// ReverseBits /// How to reverse the bits in an integer. /// There are other mechansims for accomplishing this. /// The version presented here has no branches, looping, nor table lookups. /// Table lookups are the fastest when done on large amounts of data, but slower /// when just done once due to the initial lookup cost. /// Some ARM results: http://corner.squareup.com/2013/07/ reversing-bits-on-arm.html /// http://stackoverflow.com/questions/746171/ best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c /// Example: /// 11100001 -> 10000111 inline uint32_t ReverseBits(uint32_t x){ x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555); x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333); x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F); x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24 ); return x; } // This is surely not the fastest way to do this, and is here for completeness only. // To do: Make a better version of this. inline uint64_t ReverseBits(uint64_t x){ uint32_t x1 = (uint32_t)(x & 0xffffffff); uint32_t x2 = (uint32_t)(x >> 32); return ((uint64_t)ReverseBits(x1) << 32) | ReverseBits(x2); } /// IsolateHighestBit /// How to isolate the highest 1 bit. /// Returns 0 for an input of 0. /// Example: /// 01000100 -> 01000000 /// 00000000 -> 00000000 inline uint32_t IsolateHighestBit(uint32_t x){ x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x ^ (x >> 1); } inline uint64_t IsolateHighestBit(uint64_t x){ x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return x ^ (x >> 1); } inline uint32_t IsolateHighest0Bit(uint32_t x){ return IsolateHighestBit(~x); } inline uint64_t IsolateHighest0Bit(uint64_t x){ return IsolateHighestBit(~x); } /// PropogateHighestBitDownward /// How to set all bits from the highest 1 bit downward. /// Returns 0 for an input of 0. /// Example: /// 01001000 -> 01111111 /// 00000000 -> 00000000 inline uint32_t PropogateHighestBitDownward(uint32_t x){ x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return x; } inline uint64_t PropogateHighestBitDownward(uint64_t x){ x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); x |= (x >> 32); return x; } /// GetHighestContiguous0Bits /// How to set the highest contiguous 0 bits. /// Returns 0 for an input of all bits set. /// Example: /// 00011001 -> 11100000 /// 11111111 -> 00000000 inline uint32_t GetHighestContiguous0Bits(uint32_t x){ x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return ~x; } inline uint64_t GetHighestContiguous0Bits(uint64_t x){ x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); x |= (x >> 32); return ~x; } /// GetBitwiseEquivalence /// How to calculate bitwise equivalence. /// Bitwise equivalence is the opposite of xor. It sets all bits that /// are the same to 1, whereas xor sets all bits that are different to 1. /// Thus, you can simply use ~ to get bitwise equivalence from xor. /// Example: /// 11001100, 11110000 -> 11000011 template inline T GetBitwiseEquivalence(T x, T y){ return (T)(~(x ^ y)); } /// AreLessThan2BitsSet /// How to tell if at least two bits are set in an integer. /// Example: /// 00001000 -> true /// 01001110 -> false template inline bool AreLessThan2BitsSet(T x){ return (x & (x - 1)) == 0; } #if defined(EASTDC_SSE_POPCNT) template <> inline bool AreLessThan2BitsSet(uint32_t x){ uint32_t rv = (uint32_t)_mm_popcnt_u32(x); return (rv < 2); } #if defined(EA_PROCESSOR_X86_64) template <> inline bool AreLessThan2BitsSet(uint64_t x){ uint64_t rv = (uint64_t)_mm_popcnt_u64(x); return (rv < 2); } #endif #endif /// GetHighestBit /// How to refer to the high bit of any integer data type where the /// data type size is not known. /// There are cases where you may want to refer to the higest bit in /// an integer in a portable way. If you can't know the size of the /// destination platform's int type, you can use this to refer to such a bit. /// Example: /// GetHighestBit(uint32_t(0)) -> 0x80000000 /// GetHighestBit(uint16_t(0)) -> 0x8000 template inline T GetHighestBit(T /*t*/){ return (T)((T)1 << (T)((sizeof(T) * 8) - 1)); } //////////////////////////////////////////////////////////////////// //////// // Alignment / Power of 2 //////////////////////////////////////////////////////////////////// //////// /// IsPowerOf2 /// How to tell if an unsigned integer is a power of 2. /// Works with unsigned integers only. /// Returns true for x == 0. /// Example: /// 01000010 (66) -> false /// 00001100 (12) -> false /// 00000100 (4) -> true /// 00000000 (0) -> true template inline bool IsPowerOf2(T x){ return (x & (x - 1)) == 0; } #if defined(EASTDC_SSE_POPCNT) template <> inline bool IsPowerOf2(uint32_t x){ uint32_t rv = (uint32_t)_mm_popcnt_u32(x); return (rv < 2); } #if defined(EA_PROCESSOR_X86_64) template <> inline bool IsPowerOf2(uint64_t x){ uint64_t rv = (uint64_t)_mm_popcnt_u64(x); return (rv < 2); } #endif #endif /// RoundUpToPowerOf2 /// Rounds an integer up to the nearest power of 2. /// Returns 16 for x == 16, 32 for x == 32, etc. /// Returns 0 for x == 0. /// Example: /// 01000010 (66) -> 10000000 (128) /// 00001100 (12) -> 00010000 (16) /// 00000100 (4) -> 00000100 (4) /// 00000000 (0) -> 00000000 (0) inline uint32_t RoundUpToPowerOf2(uint32_t x){ --x; x |= (x >> 16); x |= (x >> 8); x |= (x >> 4); x |= (x >> 2); x |= (x >> 1); return ++x; } inline uint64_t RoundUpToPowerOf2(uint64_t x){ --x; x |= (x >> 32); x |= (x >> 16); x |= (x >> 8); x |= (x >> 4); x |= (x >> 2); x |= (x >> 1); return ++x; } /// IsPowerOf2Multiple /// How to tell if an unsigned integer is a multiple of some specific power of 2. /// Template constant n is required to be a power of 2. /// Works with an input unsigned integers only. 'k' must be an even power of 2, such as 1, 2, 4, 8, etc. /// Returns true for x == 0. /// Example: /// IsPowerOf2Multiple<4>(3) -> false /// IsPowerOf2Multiple<16>(32) -> true /// template inline bool IsPowerOf2Multiple(T x){ return (x & (n - 1)) == 0; } // *** The following is deprecated, as it doesn't use "power of 2" in its name *** template inline bool IsMultipleOf(T x){ return (x & (n - 1)) == 0; } /// IsPowerOf2Minus1 /// How to tell if an unsigned integer is of the form 2n-1 (e.g. 0x0fff, 0x000fffff). /// Returns true for an input of 0. /// Example: /// 00001111 (15) -> true /// 00001011 (11) -> false /// 00000000 (0) -> true template inline bool IsPowerOf2Minus1(T x){ return (x & (x + 1)) == 0; } /// CrossesPowerOf2 /// How to detect any power of two crossing between two integers. /// Useful for telling if an increasing value is about to go over a power of two boundary. /// Example: /// 4, 5, 8 -> false /// 5, 9, 8 -> true template inline bool CrossesPowerOf2(T x, T y, T n){ return (n - (x & (n - 1))) < (y - x); } /// CrossesPowerOf2 /// How to detect a specific power of two crossing between two integers. /// Template parameter n must be an even power of 2, such as 1, 2, 4, 8, 16, etc. /// Example: /// CrossesPowerOf2<8>(3, 5) -> false /// CrossesPowerOf2<8>(7, 30) -> true template inline bool CrossesPowerOf2(T x, T y){ return (n - (x & (n - 1))) < (y - x); } //////////////////////////////////////////////////////////////////// ///////////// // GetHighestBitPowerOf2 template // // There is a templated compile-time constant version of GetHighestBitPowerOf2 // but it is called Log2Uint32 / Log2Int32 / Log2Uint64 / Log2Int64. See below // for that template definition. //////////////////////////////////////////////////////////////////// ///////////// /// GetHighestBitPowerOf2 (a.k.a. GetHighestBitIndex) /// How to detect the power of 2 of the highest bit set in a uint32_t. /// The power of 2 is the same as the bit index, so this could also be /// called GetHighestBitIndex. /// Returns 0 for an input of 0. /// Returns a value in the range of [0, 31] /// Example: /// GetHighestBitPowerOf2(0) -> 0 /// GetHighestBitPowerOf2(1) -> 0 /// GetHighestBitPowerOf2(2) -> 1 /// GetHighestBitPowerOf2(3) -> 1 /// GetHighestBitPowerOf2(4) -> 2 /// GetHighestBitPowerOf2(7) -> 2 /// GetHighestBitPowerOf2(8) -> 3 inline uint32_t GetHighestBitPowerOf2(uint32_t x){ uint32_t r = 0; if(x & 0xffff0000){ r += 16; x >>= 16; } if(x & 0xff00){ r += 8; x >>= 8; } if(x & 0xf0){ r += 4; x >>= 4; } if(x & 0x0c){ r += 2; x >>= 2; } if(x & 0x02){ r += 1; } return r; } /// GetHighestBitPowerOf2 (a.k.a. GetHighestBitIndex) /// How to detect the power of 2 of the highest bit set in a uint64_t. /// The power of 2 is the same as the bit index, so this could also be /// called GetHighestBitIndex. /// Returns a value in the range of [0, 63] /// Returns 0 for an input of 0. /// Example: /// GetHighestBitPowerOf2(0) -> 0 /// GetHighestBitPowerOf2(1) -> 0 /// GetHighestBitPowerOf2(2) -> 1 /// GetHighestBitPowerOf2(3) -> 1 /// GetHighestBitPowerOf2(4) -> 2 /// GetHighestBitPowerOf2(7) -> 2 /// GetHighestBitPowerOf2(8) -> 3 inline uint32_t GetHighestBitPowerOf2(uint64_t x){ uint32_t r = 0; if(x & UINT64_C(0xffffffff00000000)){ r += 32; x >>= 32; } return GetHighestBitPowerOf2((uint32_t)x) + r; } /// GetNextGreaterEven /// Returns the next higher even integer. /// Returns an even number, not necessarily a power of 2. /// Example: /// GetNextGreaterEven(-3) -> -2 /// GetNextGreaterEven(-2) -> 0 /// GetNextGreaterEven(-1) -> 0 /// GetNextGreaterEven( 0) -> 2 /// GetNextGreaterEven( 1) -> 2 /// GetNextGreaterEven( 2) -> 4 /// GetNextGreaterEven( 3) -> 4 template inline T GetNextGreaterEven(T x) { return (x + 2) & -2; } /// GetNextGreaterOdd /// Returns the next higher odd integer. /// Returns an even number, not necessarily a power of 2. /// Example: /// GetNextGreaterOdd(-3) -> -1 /// GetNextGreaterOdd(-2) -> -1 /// GetNextGreaterOdd(-1) -> 1 /// GetNextGreaterOdd( 0) -> 1 /// GetNextGreaterOdd( 1) -> 3 /// GetNextGreaterOdd( 2) -> 3 /// GetNextGreaterOdd( 3) -> 5 template inline T GetNextGreaterOdd(T x) { return ((x + 1) & -2) + 1; } /// RoundUpTo /// Template constant n is required to be a power of 2. /// Rounds values towards positive infinity. /// Returns 0 for an input of 0. /// Example: /// RoundUpTo(3) -> 4 /// RoundUpTo(8) -> 8 /// RoundUpTo(0) -> 0 /// RoundUpTo(-7) -> -4 template inline T RoundUpTo(T x){ return (T)((x + (n - 1)) & (T)-n); } /// RoundUpToEx /// Template constant n is required to be a power of 2. /// Rounds values away from zero. /// Returns 0 for an input of 0. /// Example: /// RoundUpToEx(3) -> 4 /// template struct RoundUpToExStruct { template static T RoundUpToEx(T x){ if(x >= 0) return (T)((x + (n - 1)) & (T)-n); return (T)-(bt_signed)((-(bt_signed)x + (n - 1)) & (T)-n); } }; template <> struct RoundUpToExStruct { template static T RoundUpToEx(T x){ return (T)((x + (n - 1)) & (T)-n); } }; template inline T RoundUpToEx(T x){ return RoundUpToExStruct::template RoundUpToEx (x); } /// RoundDownTo /// Template constant n is required to be a power of 2. /// Returns 0 for an input of 0. /// Rounds values towards negative infinity. /// Example: /// RoundDownTo(5) -> 4 /// RoundDownTo(4) -> 4 /// RoundDownTo(0) -> 0 /// RoundDownTo(-7) -> -8 template inline T RoundDownTo(T x){ return (T)(x & ~(n - 1)); } /// RoundDownToEx /// Template constant n is required to be a power of 2. /// Returns 0 for an input of 0. /// Rounds values towards zero. /// Example: /// RoundDownTo(5) -> 4 /// RoundDownTo(4) -> 4 /// RoundDownTo(0) -> 0 /// RoundDownTo(-7) -> -4 /// template struct RoundDownToExStruct { template static T RoundDownToEx(T x){ if(x >= 0) return (T)(x & ~(n - 1)); return (T)-(bt_signed)(-(bt_signed)x & ~(n - 1)); } }; template <> struct RoundDownToExStruct { template static T RoundDownToEx(T x){ return (T)(x & ~(n - 1)); } }; template inline T RoundDownToEx(T x){ return RoundDownToExStruct::template RoundDownToEx(x); } /// RoundUpToMultiple /// This is a non-power of 2 function; n may be any value > zero. /// Rounds values towards infinity. /// Example: /// RoundUpToMultiple(37) -> 42 /// RoundUpToMultiple(42) -> 42 template inline T RoundUpToMultiple(T x){ return (T)(((x + (n - 1)) / n) * n); } /// RoundDownToMultiple /// This is a non-power of 2 function; n may be any value > zero. /// Rounds values towards zero. /// Example: /// RoundDownToMultiple(37) -> 36 /// RoundDownToMultiple(36) -> 36 template inline T RoundDownToMultiple(T x){ return (T)((x / n) * n); } /// ZeroPresent8 /// Returns true if a 0 byte is present in x. /// Example: /// ZeroPresent8(0xffffffff) -> false /// ZeroPresent8(0xffff00ff) -> true inline bool ZeroPresent8(uint32_t x) { return ((((x - 0x01010101) & ~x) & 0x80808080) != 0); // Works because 0 is the only value for which subtracting 1 results in its high bit going from 0 to 1. } inline bool ZeroPresent8(uint64_t x) { return ((((x - UINT64_C(0x0101010101010101)) & ~x) & UINT64_C( 0x8080808080808080)) != 0); } /// ZeroPresent16 /// Returns true if an aligned uint16_t of 0 is present in x. /// Example: /// ZeroPresent16(0xffffffff) -> false /// ZeroPresent16(0xff0000ff) -> false (There are 16 contiguous 0 bits, but they are not uint16_t aligned) /// ZeroPresent16(0x0000ffff) -> true inline bool ZeroPresent16(uint32_t x) { return ((((x - 0x00010001) & ~x) & 0x80008000) != 0); } inline bool ZeroPresent16(uint64_t x) { return ((((x - UINT64_C(0x0001000100010001)) & ~x) & UINT64_C( 0x8000800080008000)) != 0); } /// ZeroPresent32 /// Returns true if an aligned uint32_t of 0 is present in x. /// Example: /// ZeroPresent16(0xffffffffffffffff) -> false /// ZeroPresent16(0xffffff00000000ff) -> false (There are 32 contiguous 0 bits, but they are not uint32_t aligned) /// ZeroPresent16(0xffffffff00000000) -> true inline bool ZeroPresent32(uint64_t x) { return ((((x - UINT64_C(0x0000000100000001)) & ~x) & UINT64_C( 0x8000000080000000)) != 0); //return (((x & 0xffffffff) == 0) || (x >> 32) == 0); // Alternative implementation which is slower. } /// Log2 /// How to find the integer base 2 log of an integer. /// It is frequently useful to tell what power of 2 a value corresponds to. /// This function rounds the input value down to the nearest power of /// 2 before testing. Thus an input of 17 returns 4. The function can be /// made to round up by doing a standard power of 2 round-up at the /// beginning of the function. /// This function doesn't work for an input of 0. /// This function only works for unsigned integers. /// For example, given "2^y = x" and you want to solve for y, you say: /// y = Log2(x); /// Assumes 32 bit IEEE float. /// Note: This function yields incorrect answers for very large integers. /// Example: /// 4 -> 2 /// 8 -> 3 /// 11 -> 3 /// 16 -> 4 /// 0 -> error /// inline uint32_t Log2(uint32_t x) { const union { float f; uint32_t i; } converter = { (float)x }; return (converter.i >> 23) - 127; } inline uint64_t Log2(uint64_t x) { const union { double f; uint64_t i; } converter = { (double)x }; return ((converter.i >> 52) & 0x7ff) - 1023; } /// CeilLog2 /// Generates the ceiling of Log2. /// This function exists to deal with errors generated by Log2 under /// the case of very large numbers. inline uint32_t CeilLog2(uint32_t x){ const union { float f; uint32_t i; } converter = { (float)x }; return (converter.i - 0x3F000001) >> 23; } //inline uint64_t CeilLog2(uint64_t x){ // const union { double f; uint64_t i; } converter = { (double)x }; // return (converter.i - UINT64_C(0x________________)) >> 52; //} /// Log2Uint32 / Log2Int32 / Log2Uint64 / Log2Int64 /// /// Evaluates to floor(log2(N)) for a compile-time constant value of N, /// with no runtime cost, for any N > 0. This is the equivalent of a /// compile-time version of GetHighestBitPowerOf2, which gets the /// highest bit set in a value. /// /// Example usage of Log2Uint32: /// Log2Uint32<8>::value evaluates to 3 /// Log2Uint32<0x7fffffff>::value evaluates to 30 /// Log2Uint64::value evaluates to 60 /// template struct Log2Uint32 { static const uint32_t value = (1 + Log2Uint32::value); }; template <> struct Log2Uint32<1> { static const uint32_t value = 0; }; template struct Log2Int32 { static const int32_t value = (1 + Log2Int32::value); }; template <> struct Log2Int32<1> { static const int32_t value = 0; }; template struct Log2Uint64 { static const uint64_t value = (1 + Log2Uint64::value); }; template <> struct Log2Uint64<1> { static const uint64_t value = 0; }; template struct Log2Int64 { static const int64_t value = (1 + Log2Int64::value); }; template <> struct Log2Int64<1> { static const int64_t value = 0; }; /// DivideByPowerOf2Rounded /// Divides a number x by 2^n, and rounds the result instead of /// chopping the result. This is useful for certain kinds of /// bit manipulation. /// Example: /// DivideByPowerOf2Rounded( 0) -> 0 /// DivideByPowerOf2Rounded(127) -> 0 /// DivideByPowerOf2Rounded(128) -> 1 /// DivideByPowerOf2Rounded(256) -> 1 /// // This is not yet tested. //template //inline T DivideByPowerOf2Rounded(T x) //{ // return ((x + (1 << (n - 1))) >> n); //} // EAGetAlignment // This functionality and other alignment assistance functions have been // moved to EAAlignment.h. The best way to portably and reliably detect // alignment in both C and C++ is to use a compiler intrinsic or use // some fancy C++ templates. In either case, the solution is outside the // realm of bit tricks. //////////////////////////////////////////////////////////////////// //////// // Overflow //////////////////////////////////////////////////////////////////// //////// EA_DISABLE_VC_WARNING(4310) // cast truncates constant value /// SignedAdditionWouldOverflow /// How to detect that an addition or subtraction of signed values will overflow. /// This is a useful operation to test for when writing robust applications. /// Signed integer overflow of addition or subtraction occurs if and only if /// the operands have the same sign and the result of the operation has the /// opposite of this sign. /// Some platforms generate exceptions upon an overflow, and the functions /// presented here work by possibly causing overflow. Alternative versions of /// these functions exist which are slightly more complex but can work without /// generating overflows themselves. However, no platform that you /// are likely to be using generates such exceptions. /// Example: /// SignedAdditionWouldOverflow(2, 3) -> false /// SignedAdditionWouldOverflow(0x7fffffff, 0x7fffffff) -> true /// /// EA_NO_UBSAN is included because this function is designed to overflow /// and it UBSAN correctly warns here. template EA_NO_UBSAN inline bool SignedAdditionWouldOverflow(T x, T y){ const T temp = (T)(x + y); return (((temp ^ x) & (temp ^ y)) >> ((sizeof(T) * (T)8) - 1)) != 0; } template inline bool SignedSubtractionWouldOverflow(T x, T y){ const T tMin = (T)((T)1 << (T)((sizeof(T) * 8) - 1)); // This is not strictly portable. return (x >= 0) ? (y < (T)(x - (T)-(tMin + 1))) : (y > (T)(x - tMin)); } template inline bool UnsignedAdditionWouldOverflow(T x, T y){ const T temp = (T)(x + y); return (temp < x) && (temp < y); } template inline bool UnsignedSubtractionWouldOverflow(T x, T y){ return y > x; } /// UnsignedMultiplyWouldOverflow /// How to detect that a multiplication will overflow. /// This is a useful operation to test for when writing robust applications. /// Some platforms generate exceptions upon an overflow, and the functions /// presented here work by possibly causing overflow. Alternative versions of /// these functions exist which are slightly more complex but can work without /// generating overflows themselves. However, no platform that you /// are likely to be using generates such exceptions. /// Example: /// 4 * 5 -> false /// 0xffffffff * 0xffffffff -> true template inline bool UnsignedMultiplyWouldOverflow(T x, T y){ if(y) return (((x * y) / y) != x); return false; } inline bool SignedMultiplyWouldOverflow(int32_t x, int32_t y){ if((y < 0) && (x == (int32_t)INT32_C(0x80000000))) return true; if(y) return (((x * y) / y) != x); return false; } inline bool SignedMultiplyWouldOverflow(int64_t x, int64_t y){ if((y < 0) && (x == (int64_t)INT64_C(0x8000000000000000))) return true; if(y) return (((x * y) / y) != x); return false; } /// UnsignedDivisionWouldOverflow /// How to detect that a division will overflow. /// This is a useful operation to test for when writing robust applications. /// Some platforms generate exceptions upon an overflow, and the functions /// presented here work by possibly causing overflow. Alternative versions /// of these functions exist which are slightly more complex but can work /// without generating overflows themselves. However, no platform that you /// are likely to be using generates such exceptions. /// Example: /// 5 / 4 -> false /// 3 / 0 -> true template inline bool UnsignedDivisionWouldOverflow(T /*x*/, T y){ return y == 0; } /// SignedDivisionWouldOverflow /// How to detect that a division will overflow. inline bool SignedDivisionWouldOverflow(int32_t x, int32_t y){ return (y == 0) || ((x == (int32_t)INT32_C(0x80000000)) && (y == -1 )); } inline bool SignedDivisionWouldOverflow(int64_t x, int64_t y){ return (y == 0) || ((x == (int64_t)INT64_C(0x8000000000000000)) && (y == -1)); } /// GetAverage /// How to compute average of two integers without possible overflow errors. /// Returns floor of the average; Rounds to negative infinity. /// This is useful for averaging two integers whereby the standard mechanism /// of returning (x + y) / 2 may overflow and yield an incorrect answer. /// Normally, you want the floor (as opposed to ceiling) of the average, /// at least for positive values. /// Example: /// 3, 4 -> 3 /// 3, 3 -> 3 /// -3, -4 -> -4 /// -4, 5 -> 0 template inline int GetAverage(T x, T y){ return (x & y) + ((x ^ y) >> 1); // Need to use '>> 1' instead of '/ 2' } /// GetAverage_Ceiling /// Returns ceiling of the average; Rounds to positive infinity. /// Example: /// 3, 4 -> 4 /// 3, 3 -> 3 /// -3, -4 -> -3 /// -4, 5 -> 1 template inline int GetAverage_Ceiling(T x, T y){ return (x | y) - ((x ^ y) >> 1); // Need to use '>> 1' instead of '/ 2' } EA_RESTORE_VC_WARNING() // 4310 //////////////////////////////////////////////////////////////////// //////// // Miscellaneous //////////////////////////////////////////////////////////////////// //////// /// GetParity /// How to calculate parity of an integer. /// Parity is defined as the oddness or evenness of the count of 1 bits. /// There are other mechansims for accomplishing this. The version /// presented here has no branches, looping, nor table lookups. /// Example: /// 01100011 -> 0 (even) /// 00101010 -> 1 (odd) inline int GetParity(uint32_t x){ x ^= x >> 1; x ^= x >> 2; x = (x & UINT32_C(0x11111111)) * UINT32_C(0x11111111); return (int)((x >> 28) & 1); } inline int GetParity(uint64_t x){ x ^= x >> 1; x ^= x >> 2; x = (x & UINT64_C(0x1111111111111111)) * UINT64_C(0x1111111111111111 ); return (int)((x >> 60) & 1); } /// GetIsBigEndian /// How to test (or verify) that the current machine is big-endian. /// It is not normally possible with C/C++ to tell at compile-time what /// the machine endian-ness is. However, you might be able to check a /// predefined value, such as EABase's EA_SYSTEM_BIG_ENDIAN. inline bool GetIsBigEndian(){ const int temp = 1; return ((char*)&temp)[0] == 0; } /// ToggleBetween0And1 /// How to toggle an integer between 0 and 1. /// Example: /// 1 -> 0 /// 0 -> 1 inline int ToggleBetween0And1(int x){ return x ^ 1; } /// ToggleBetweenIntegers /// How to toggle between any two integers. /// Toggling between three or more values is possible but requires /// code that is a bit more complicated. /// You can do this in place with: /// x ^= a ^ b; /// Example: /// 5, 4, 5 -> 4 template inline T ToggleBetweenIntegers(T x, T a, T b){ return (T)(x ^ a ^ b); } /// IsBetween0AndValue /// How to quickly see if an int is >= 0 and < some value. /// The purpose of this is to save a comparison to zero and thus /// execute faster because you get two comparisons for the price of one. /// This method can be extended to any integer range by adding a /// value to x before the comparison. /// Normally you wouldn't call a function as with this example, /// but instead you would just say something like: /// if((unsigned)x < 4) ... /// Example: /// 3, 4 -> true /// -3, 4 -> false /// Example function: /// inline bool IsBetween8And12(int x){ /// return ((unsigned)x + 8) < 12; /// } inline bool IsBetween0AndValue(int32_t x, int32_t a){ return (uint32_t)x < (uint32_t)a; } inline bool IsBetween0AndValue(int64_t x, int64_t a){ return (uint64_t)x < (uint64_t)a; } /// ExchangeValues /// How to exchange two values in place. /// It is well-known that xor-ing two values like this exchanges them in place. /// This trick is perhaps of little practical value and is instead more of a curiosity. /// Example: /// 2, 3 -> 3, 2 template inline void ExchangeValues(T& x, T& y){ x = (T)(x ^ y); y = (T)(x ^ y); x = (T)(x ^ y); } /// FloorMod /// The normal C modulo operator (%) operates on the assumption that /// division rounds towards zero, which means that the result of a /// modulus operation on a negative number is also negative. (The /// modulus operator in C is defined as the remainder after a division, /// so in the case where a negative number is rounded up, the remainder /// will be negative.) FloorMod instead returns the remainder of /// a division rounded towards negative infinity; the modulus will always /// be a positive number. template T FloorMod(T n, T mod){ const T v = n % mod; return v + ((v >> ((sizeof(v) * 8) - 1)) & mod); } /// GetSign /// How to get the sign of an integer. /// Negative inputs return -1, positive inputs return +1, a zero input returns 0. /// These functions are significantly faster than brute force if/ else statements. /// Requires signed right shift support. Note that most compilers/ platforms /// support signed numerical right shifts. /// Example: /// -5 -> -1 /// 0 -> 0 /// 250 -> 1 inline int GetSign(int32_t x){ return (int)((x >> 31) | (-(uint32_t)x >> 31)); // negation of signed int is undefined behaviour } inline int GetSign(int64_t x){ return (int)((x >> 63) | (-(uint64_t)x >> 63)); // negation of signed int is undefined behaviour } /// GetSignEx /// How to get the sign of an integer. /// Returns 1 for > 0, 0 for 0, and -1 for < 0. /// This version doesn't work for input of 0x80000000 / 0x8000000000000000. inline int GetSignEx(int32_t x){ return (x >> 31) - (-x >> 31); } inline int GetSignEx(int64_t x){ return (x >> 63) - (-x >> 63); } /// SignExtend12 /// How to do fast sign extension of a 12 bit value to 32 bits. /// Say you have a signed 12 bit value stored in an integer and you want to /// make it be a proper 32 bit int. To do this, you want to take the high bit /// of the 12 bit value and replicate it leftward. /// To do this in a generic way, create a mask of the high bits in the /// larger operand plus the sign bit of the smaller, add, and xor. /// Example: /// 0x00000fff -> 12 -> 0xffffffff /// 0x00000aaa -> 12 -> 0x00000aaa /// /// 0x00ffffff -> 24 -> 0xffffffff /// 0x00aaaaaa -> 24 -> 0x00aaaaaa inline int32_t SignExtend12(int32_t x){ return (int32_t)((x + 0xfffff800) ^ 0xfffff800); } inline int32_t SignExtend24(int32_t x){ return (int32_t)((x + 0xff800000) ^ 0xff800000); } /// IsUnsigned /// This version requires signed right shift support. It should work for most /// modern computers and compilers, as they have a signed right shift. template bool IsUnsigned(T /*x*/){ return (((T)(-1) >> 1) != (T)(-1)); } /// EAIsUnsigned /// How to tell if an integer variable is an unsigned type at runtime. /// /// Note that this isn't a test to see of a given variable is negative; /// this is a test to see if a data type is signed or unsigned. /// With some data types, such as wchar_t and size_t, you can't know /// if the type is signed or unsigned at compile time. /// /// This is a notoriously tricky problem, as commonly published solutions /// don't work for integer types other than int or make assumptions about /// how right shifting of signed values occur. /// /// This could also be solved for C++ with templates. That would be a better /// solution that this and would effectively be a compile-time check as opposed /// to a runtime check. See EASTL type traits for this. /// /// Example usage: /// uint8_t u8 = 0; /// int64_t i64 = 0; /// assert( EAIsUnsigned(u8))); /// assert(!EAIsUnsigned(i64))); #ifndef EAIsUnsigned #define EAIsUnsigned(x) ((((x = ~x) >= 0) || (((x = ~x) != 0) && 0)) && ((x = ~x) >= 0)) #endif // How to tell the integer representation of the computer. // Just about every computer you are likely to work with will be twos-complement. // You can look these terms up on the Internet to get detailed descriptions of them. inline bool IsTwosComplement(){ return ((-2 | -3) == -1); } inline bool IsOnesComplement(){ return ((-1 & -2) == -3); } inline bool IsSignMagnitude(){ return ((-1 | -2) == -3); } inline bool IsOffsetBinary(){ return ((1u << (sizeof(int) * 8 - 1)) == 0); } /// EAOffsetOf /// /// The offsetof macro is guaranteed to only work with POD types. However we wish to use /// it for non-POD types but where we know that offsetof will still work for the cases /// in which we use it. #ifndef EAOffsetOf #define EAOffsetOf EA_OFFSETOF #endif /// EAOffsetOfBase /// /// Returns the offset of the class Base within the subclass Class. /// Fails to compile for cases where Base is multiply inherited by Class. /// Example usage: /// struct A{ int a; }; /// struct B{ int b; }; /// struct C : public A, public B{ int c; }; /// EAOffsetOfBase() => 4 /// /// EAOffsetOfBase is not guaranteed to be a compile-time constant expression, /// due to the use of reinterpret_cast of a pointer. /// #if !defined(EAOffsetOfBaseDefined) #define EAOffsetOfBaseDefined 1 template EA_NO_UBSAN size_t EAOffsetOfBase() // Disable UBSAN because we are using an address which doesn't respect type alignment. { return (size_t)((Base*)reinterpret_cast(1)) - 1; // Use 1 instead of 0 because compilers often treat 0 specially and warn. } #endif } // namespace StdC } // namespace EA EA_RESTORE_VC_WARNING() #endif // Header include guard * Copy lines * Copy permalink * View git blame * Reference in new issue [ ] Go Footer (c) 2022 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.