1 // Copyright 2021 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // "Generic" helper functions (not specific to BigInts). 6 7 #include <stdint.h> 8 9 #include <type_traits> 10 11 #ifdef _MSC_VER 12 #include <intrin.h> // For _BitScanReverse. 13 #endif 14 15 #ifndef V8_BIGINT_UTIL_H_ 16 #define V8_BIGINT_UTIL_H_ 17 18 // Integer division, rounding up. 19 #define DIV_CEIL(x, y) (((x)-1) / (y) + 1) 20 21 namespace v8 { 22 namespace bigint { 23 24 // Rounds up x to a multiple of y. RoundUp(int x,int y)25inline constexpr int RoundUp(int x, int y) { return (x + y - 1) & -y; } 26 27 // Different environments disagree on how 64-bit uintptr_t and uint64_t are 28 // defined, so we have to use templates to be generic. 29 template <typename T, typename = typename std::enable_if< 30 std::is_unsigned<T>::value && sizeof(T) == 8>::type> CountLeadingZeros(T value)31constexpr int CountLeadingZeros(T value) { 32 #if __GNUC__ || __clang__ 33 return value == 0 ? 64 : __builtin_clzll(value); 34 #elif _MSC_VER 35 unsigned long index = 0; // NOLINT(runtime/int). MSVC insists. 36 return _BitScanReverse64(&index, value) ? 63 - index : 64; 37 #else 38 #error Unsupported compiler. 39 #endif 40 } 41 CountLeadingZeros(uint32_t value)42constexpr int CountLeadingZeros(uint32_t value) { 43 #if __GNUC__ || __clang__ 44 return value == 0 ? 32 : __builtin_clz(value); 45 #elif _MSC_VER 46 unsigned long index = 0; // NOLINT(runtime/int). MSVC insists. 47 return _BitScanReverse(&index, value) ? 31 - index : 32; 48 #else 49 #error Unsupported compiler. 50 #endif 51 } 52 CountTrailingZeros(uint32_t value)53inline constexpr int CountTrailingZeros(uint32_t value) { 54 #if __GNUC__ || __clang__ 55 return value == 0 ? 32 : __builtin_ctz(value); 56 #elif _MSC_VER 57 unsigned long index = 0; // NOLINT(runtime/int). 58 return _BitScanForward(&index, value) ? index : 32; 59 #else 60 #error Unsupported compiler. 61 #endif 62 } 63 BitLength(int n)64inline constexpr int BitLength(int n) { 65 return 32 - CountLeadingZeros(static_cast<uint32_t>(n)); 66 } 67 IsPowerOfTwo(int value)68inline constexpr bool IsPowerOfTwo(int value) { 69 return value > 0 && (value & (value - 1)) == 0; 70 } 71 72 } // namespace bigint 73 } // namespace v8 74 75 #endif // V8_BIGINT_UTIL_H_ 76