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 21namespace v8 { 22namespace bigint { 23 24// Rounds up x to a multiple of 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. 29template <typename T, typename = typename std::enable_if< 30 std::is_unsigned<T>::value && sizeof(T) == 8>::type> 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 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 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 64inline constexpr int BitLength(int n) { 65 return 32 - CountLeadingZeros(static_cast<uint32_t>(n)); 66} 67 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