// Copyright 2014 the V8 project authors. All rights reserved.

// Use of this source code is governed by a BSD-style license that can be

// found in the LICENSE file.

#ifndef V8_BASE_BITS_H_

#define V8_BASE_BITS_H_

#include <stdint.h>

#include <type_traits>

#include "src/base/base-export.h"

#include "src/base/macros.h"

#if V8_CC_MSVC

#include <intrin.h>

#endif

#if V8_OS_WIN32

#include "src/base/win32-headers.h"

#endif

namespace v8 {

namespace base {

namespace bits {

// CountPopulation(value) returns the number of bits set in |value|.

template <typename T>

constexpr inline unsigned CountPopulation(T value)

requires(std::is_unsigned<T>::value && sizeof(T) <= 8)

{

static_assert(sizeof(T) <= 8);

#if V8_HAS_BUILTIN_POPCOUNT

return sizeof(T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))

: __builtin_popcount(static_cast<uint32_t>(value));

#else

// Fall back to divide-and-conquer popcount (see "Hacker's Delight" by Henry

// S. Warren, Jr.), chapter 5-1.

constexpr uint64_t mask[] = {0x5555555555555555, 0x3333333333333333,

0x0f0f0f0f0f0f0f0f};

// Start with 64 buckets of 1 bits, holding values from [0,1].

value = ((value >> 1) & mask[0]) + (value & mask[0]);

// Having 32 buckets of 2 bits, holding values from [0,2] now.

value = ((value >> 2) & mask[1]) + (value & mask[1]);

// Having 16 buckets of 4 bits, holding values from [0,4] now.

value = ((value >> 4) & mask[2]) + (value & mask[2]);

// Having 8 buckets of 8 bits, holding values from [0,8] now.

// From this point on, the buckets are bigger than the number of bits

// required to hold the values, and the buckets are bigger the maximum

// result, so there's no need to mask value anymore, since there's no

// more risk of overflow between buckets.

if (sizeof(T) > 1) value = (value >> (sizeof(T) > 1 ? 8 : 0)) + value;

// Having 4 buckets of 16 bits, holding values from [0,16] now.

if (sizeof(T) > 2) value = (value >> (sizeof(T) > 2 ? 16 : 0)) + value;

// Having 2 buckets of 32 bits, holding values from [0,32] now.

if (sizeof(T) > 4) value = (value >> (sizeof(T) > 4 ? 32 : 0)) + value;

// Having 1 buckets of 64 bits, holding values from [0,64] now.

return static_cast<unsigned>(value & 0xff);

#endif

}

// ReverseBits(value) returns |value| in reverse bit order.

template <typename T>

T ReverseBits(T value) {

static_assert((sizeof(value) == 1) || (sizeof(value) == 2) ||

(sizeof(value) == 4) || (sizeof(value) == 8));

T result = 0;

for (unsigned i = 0; i < (sizeof(value) * 8); i++) {

result = (result << 1) | (value & 1);

value >>= 1;

}

return result;

}

// ReverseBytes(value) returns |value| in reverse byte order.

template <typename T>

T ReverseBytes(T value) {

static_assert((sizeof(value) == 1) || (sizeof(value) == 2) ||

(sizeof(value) == 4) || (sizeof(value) == 8));

T result = 0;

for (unsigned i = 0; i < sizeof(value); i++) {

result = (result << 8) | (value & 0xff);

value >>= 8;

}

return result;

}

template <class T>

inline constexpr std::make_unsigned_t<T> Unsigned(T value) {

static_assert(std::is_signed_v<T>);

return static_cast<std::make_unsigned_t<T>>(value);

}

template <class T>

inline constexpr std::make_signed_t<T> Signed(T value) {

static_assert(std::is_unsigned_v<T>);

return static_cast<std::make_signed_t<T>>(value);

}

// CountLeadingZeros(value) returns the number of zero bits following the most

// significant 1 bit in |value| if |value| is non-zero, otherwise it returns

// {sizeof(T) * 8}.

template <typename T, unsigned bits = sizeof(T) * 8>

inline constexpr unsigned CountLeadingZeros(T value)

requires(std::is_unsigned<T>::value && sizeof(T) <= 8)

{

static_assert(bits > 0, "invalid instantiation");

#if V8_HAS_BUILTIN_CLZ

return value == 0

? bits

: bits == 64

? __builtin_clzll(static_cast<uint64_t>(value))

: __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits);

#else

// Binary search algorithm taken from "Hacker's Delight" (by Henry S. Warren,

// Jr.), figures 5-11 and 5-12.

if (bits == 1) return static_cast<unsigned>(value) ^ 1;

T upper_half = value >> (bits / 2);

T next_value = upper_half != 0 ? upper_half : value;

unsigned add = upper_half != 0 ? 0 : bits / 2;

constexpr unsigned next_bits = bits == 1 ? 1 : bits / 2;

return CountLeadingZeros<T, next_bits>(next_value) + add;

#endif

}

inline constexpr unsigned CountLeadingZeros32(uint32_t value) {

return CountLeadingZeros(value);

}

inline constexpr unsigned CountLeadingZeros64(uint64_t value) {

return CountLeadingZeros(value);

}

// The number of leading zeros for a positive number,

// the number of leading ones for a negative number.

template <class T>

constexpr unsigned CountLeadingSignBits(T value) {

static_assert(std::is_signed_v<T>);

return value < 0 ? CountLeadingZeros(~Unsigned(value))

: CountLeadingZeros(Unsigned(value));

}

// CountTrailingZeros(value) returns the number of zero bits preceding the

// least significant 1 bit in |value| if |value| is non-zero, otherwise it

// returns {sizeof(T) * 8}.

// See CountTrailingZerosNonZero for an optimized version for the case that

// |value| is guaranteed to be non-zero.

template <typename T, unsigned bits = sizeof(T) * 8>

inline constexpr unsigned CountTrailingZeros(T value)

requires(std::is_integral<T>::value && sizeof(T) <= 8)

{

#if V8_HAS_BUILTIN_CTZ

return value == 0 ? bits

: bits == 64 ? __builtin_ctzll(static_cast<uint64_t>(value))

: __builtin_ctz(static_cast<uint32_t>(value));

#else

// Fall back to popcount (see "Hacker's Delight" by Henry S. Warren, Jr.),

// chapter 5-4. On x64, since is faster than counting in a loop and faster

// than doing binary search.

using U = typename std::make_unsigned<T>::type;

U u = value;

return CountPopulation(static_cast<U>(~u & (u - 1u)));

#endif

}

inline constexpr unsigned CountTrailingZeros32(uint32_t value) {

return CountTrailingZeros(value);

}

inline constexpr unsigned CountTrailingZeros64(uint64_t value) {

return CountTrailingZeros(value);

}

// CountTrailingZerosNonZero(value) returns the number of zero bits preceding

// the least significant 1 bit in |value| if |value| is non-zero, otherwise the

// behavior is undefined.

// See CountTrailingZeros for an alternative version that allows |value| == 0.

template <typename T, unsigned bits = sizeof(T) * 8>

inline constexpr unsigned CountTrailingZerosNonZero(T value)

requires(std::is_integral<T>::value && sizeof(T) <= 8)

{

DCHECK_NE(0, value);

#if V8_HAS_BUILTIN_CTZ

return bits == 64 ? __builtin_ctzll(static_cast<uint64_t>(value))

: __builtin_ctz(static_cast<uint32_t>(value));

#else

return CountTrailingZeros<T, bits>(value);

#endif

}

// Returns true iff |value| is a power of 2.

template <typename T>

constexpr inline bool IsPowerOfTwo(T value)

requires(std::is_integral<T>::value || std::is_enum<T>::value)

{

return value > 0 && (value & (value - 1)) == 0;

}

// Identical to {CountTrailingZeros}, but only works for powers of 2.

template <typename T>

inline constexpr int WhichPowerOfTwo(T value)

requires std::is_integral<T>::value

{

DCHECK(IsPowerOfTwo(value));

#if V8_HAS_BUILTIN_CTZ

static_assert(sizeof(T) <= 8);

return sizeof(T) == 8 ? __builtin_ctzll(static_cast<uint64_t>(value))

: __builtin_ctz(static_cast<uint32_t>(value));

#else

// Fall back to popcount (see "Hacker's Delight" by Henry S. Warren, Jr.),

// chapter 5-4. On x64, since is faster than counting in a loop and faster

// than doing binary search.

using U = typename std::make_unsigned<T>::type;

U u = value;

return CountPopulation(static_cast<U>(u - 1));

#endif

}

// RoundUpToPowerOfTwo32(value) returns the smallest power of two which is

// greater than or equal to |value|. If you pass in a |value| that is already a

// power of two, it is returned as is. |value| must be less than or equal to

// 0x80000000u. Uses computation based on leading zeros if we have compiler

// support for that. Falls back to the implementation from "Hacker's Delight" by

// Henry S. Warren, Jr., figure 3-3, page 48, where the function is called clp2.

V8_BASE_EXPORT constexpr uint32_t RoundUpToPowerOfTwo32(uint32_t value) {

DCHECK_LE(value, uint32_t{1} << 31);

if (value) --value;

// Use computation based on leading zeros if we have compiler support for that.

#if V8_HAS_BUILTIN_CLZ || V8_CC_MSVC

return 1u << (32 - CountLeadingZeros(value));

#else

value |= value >> 1;

value |= value >> 2;

value |= value >> 4;

value |= value >> 8;

value |= value >> 16;

return value + 1;

#endif

}

// Same for 64 bit integers. |value| must be <= 2^63

V8_BASE_EXPORT constexpr uint64_t RoundUpToPowerOfTwo64(uint64_t value) {

DCHECK_LE(value, uint64_t{1} << 63);

if (value) --value;

// Use computation based on leading zeros if we have compiler support for that.

#if V8_HAS_BUILTIN_CLZ

return uint64_t{1} << (64 - CountLeadingZeros(value));

#else

value |= value >> 1;

value |= value >> 2;

value |= value >> 4;

value |= value >> 8;

value |= value >> 16;

value |= value >> 32;

return value + 1;

#endif

}

// Same for size_t integers.

inline constexpr size_t RoundUpToPowerOfTwo(size_t value) {

if (sizeof(size_t) == sizeof(uint64_t)) {

return RoundUpToPowerOfTwo64(value);

} else {

// Without windows.h included this line triggers a truncation warning on

// 64-bit builds. Presumably windows.h disables the relevant warning.

return RoundUpToPowerOfTwo32(static_cast<uint32_t>(value));

}

}

// RoundDownToPowerOfTwo32(value) returns the greatest power of two which is

// less than or equal to |value|. If you pass in a |value| that is already a

// power of two, it is returned as is.

inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {

if (value > 0x80000000u) return 0x80000000u;

uint32_t result = RoundUpToPowerOfTwo32(value);

if (result > value) result >>= 1;

return result;

}

// Precondition: 0 <= shift < 32

inline constexpr uint32_t RotateRight32(uint32_t value, uint32_t shift) {

return (value >> shift) | (value << ((32 - shift) & 31));

}

// Precondition: 0 <= shift < 32

inline constexpr uint32_t RotateLeft32(uint32_t value, uint32_t shift) {

return (value << shift) | (value >> ((32 - shift) & 31));

}

// Precondition: 0 <= shift < 64

inline constexpr uint64_t RotateRight64(uint64_t value, uint64_t shift) {

return (value >> shift) | (value << ((64 - shift) & 63));

}

// Precondition: 0 <= shift < 64

inline constexpr uint64_t RotateLeft64(uint64_t value, uint64_t shift) {

return (value << shift) | (value >> ((64 - shift) & 63));

}

// SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and

// |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed summation resulted in an overflow.

inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {

#if V8_HAS_BUILTIN_SADD_OVERFLOW

return __builtin_sadd_overflow(lhs, rhs, val);

#else

uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);

*val = base::bit_cast<int32_t>(res);

return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;

#endif

}

// SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and

// |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed subtraction resulted in an overflow.

inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {

#if V8_HAS_BUILTIN_SSUB_OVERFLOW

return __builtin_ssub_overflow(lhs, rhs, val);

#else

uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);

*val = base::bit_cast<int32_t>(res);

return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;

#endif

}

// SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs|

// and |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed multiplication resulted in an overflow.

inline bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {

#if V8_HAS_BUILTIN_SMUL_OVERFLOW

return __builtin_smul_overflow(lhs, rhs, val);

#else

// Compute the result as {int64_t}, then check for overflow.

int64_t result = int64_t{lhs} * int64_t{rhs};

*val = static_cast<int32_t>(result);

using limits = std::numeric_limits<int32_t>;

return result < limits::min() || result > limits::max();

#endif

}

// SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and

// |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed summation resulted in an overflow.

inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {

#if V8_HAS_BUILTIN_ADD_OVERFLOW

return __builtin_add_overflow(lhs, rhs, val);

#else

uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);

*val = base::bit_cast<int64_t>(res);

return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;

#endif

}

// SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and

// |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed subtraction resulted in an overflow.

inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {

#if V8_HAS_BUILTIN_SUB_OVERFLOW

return __builtin_sub_overflow(lhs, rhs, val);

#else

uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);

*val = base::bit_cast<int64_t>(res);

return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;

#endif

}

// SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs|

// and |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the signed multiplication resulted in an overflow.

inline bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {

#if V8_HAS_BUILTIN_MUL_OVERFLOW

return __builtin_mul_overflow(lhs, rhs, val);

#else

int64_t res = base::bit_cast<int64_t>(static_cast<uint64_t>(lhs) *

static_cast<uint64_t>(rhs));

*val = res;

// Check for INT64_MIN / -1 as it's undefined behaviour and could cause

// hardware exceptions.

if ((res == INT64_MIN && lhs == -1)) {

return true;

}

return lhs != 0 && (res / lhs) != rhs;

#endif

}

// SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and

// |rhs|, extracts the most significant 32 bits of the result, and returns

// those.

V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);

// UnsignedMulHigh32(lhs, rhs) multiplies two unsigned 32-bit values |lhs| and

// |rhs|, extracts the most significant 32 bits of the result, and returns

// those.

V8_BASE_EXPORT uint32_t UnsignedMulHigh32(uint32_t lhs, uint32_t rhs);

// SignedMulHigh64(lhs, rhs) multiplies two signed 64-bit values |lhs| and

// |rhs|, extracts the most significant 64 bits of the result, and returns

// those.

V8_BASE_EXPORT int64_t SignedMulHigh64(int64_t lhs, int64_t rhs);

// UnsignedMulHigh64(lhs, rhs) multiplies two unsigned 64-bit values |lhs| and

// |rhs|, extracts the most significant 64 bits of the result, and returns

// those.

V8_BASE_EXPORT uint64_t UnsignedMulHigh64(uint64_t lhs, uint64_t rhs);

// SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values

// |lhs| and |rhs|, extracts the most significant 32 bits of the result, and

// adds the accumulate value |acc|.

V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,

int32_t acc);

// SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient

// truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|

// is minint and |rhs| is -1, it returns minint.

V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);

// SignedDiv64(lhs, rhs) divides |lhs| by |rhs| and returns the quotient

// truncated to int64. If |rhs| is zero, then zero is returned. If |lhs|

// is minint and |rhs| is -1, it returns minint.

V8_BASE_EXPORT int64_t SignedDiv64(int64_t lhs, int64_t rhs);

// SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder

// truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|

// is -1, it returns zero.

V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);

// SignedMod64(lhs, rhs) divides |lhs| by |rhs| and returns the remainder

// truncated to int64. If either |rhs| is zero or |lhs| is minint and |rhs|

// is -1, it returns zero.

V8_BASE_EXPORT int64_t SignedMod64(int64_t lhs, int64_t rhs);

// UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs|

// and |rhs| and stores the result into the variable pointed to by |val| and

// returns true if the unsigned summation resulted in an overflow.

inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) {

#if V8_HAS_BUILTIN_SADD_OVERFLOW

return __builtin_uadd_overflow(lhs, rhs, val);

#else

*val = lhs + rhs;

return *val < (lhs | rhs);

#endif

}

// UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient

// truncated to uint32. If |rhs| is zero, then zero is returned.

inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {

return rhs ? lhs / rhs : 0u;

}

// UnsignedDiv64(lhs, rhs) divides |lhs| by |rhs| and returns the quotient

// truncated to uint64. If |rhs| is zero, then zero is returned.

inline uint64_t UnsignedDiv64(uint64_t lhs, uint64_t rhs) {

return rhs ? lhs / rhs : 0u;

}

// UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder

// truncated to uint32. If |rhs| is zero, then zero is returned.

inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {

return rhs ? lhs % rhs : 0u;

}

// UnsignedMod64(lhs, rhs) divides |lhs| by |rhs| and returns the remainder

// truncated to uint64. If |rhs| is zero, then zero is returned.

inline uint64_t UnsignedMod64(uint64_t lhs, uint64_t rhs) {

return rhs ? lhs % rhs : 0u;

}

// Wraparound integer arithmetic without undefined behavior.

inline int32_t WraparoundAdd32(int32_t lhs, int32_t rhs) {

return static_cast<int32_t>(static_cast<uint32_t>(lhs) +

static_cast<uint32_t>(rhs));

}

inline int32_t WraparoundNeg32(int32_t x) {

return static_cast<int32_t>(-static_cast<uint32_t>(x));

}

// SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,

// checks and returns the result.

V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);

// SignedSaturatedSub64(lhs, rhs) subtracts |lhs| by |rhs|,

// checks and returns the result.

V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);

template <class T>

V8_BASE_EXPORT constexpr int BitWidth(T x) {

return std::numeric_limits<T>::digits - CountLeadingZeros(x);

}

} // namespace bits

} // namespace base

} // namespace v8

#endif // V8_BASE_BITS_H_