bits.h | Explore in Territory

// 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
    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
                            unsigned>::type
    CountPopulation(T value) { … }

// ReverseBits(value) returns |value| in reverse bit order.
template <typename T>
T ReverseBits(T value) { … }

// ReverseBytes(value) returns |value| in reverse byte order.
template <typename T>
T ReverseBytes(T value) { … }

template <class T>
inline constexpr std::make_unsigned_t<T> Unsigned(T value) { … }
template <class T>
inline constexpr std::make_signed_t<T> Signed(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
    typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8,
                            unsigned>::type
    CountLeadingZeros(T value) { … }

inline constexpr unsigned CountLeadingZeros32(uint32_t value) { … }
inline constexpr unsigned CountLeadingZeros64(uint64_t 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) { … }

// 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
    typename std::enable_if<std::is_integral<T>::value && sizeof(T) <= 8,
                            unsigned>::type
    CountTrailingZeros(T value) { … }

inline constexpr unsigned CountTrailingZeros32(uint32_t value) { … }
inline constexpr unsigned CountTrailingZeros64(uint64_t 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
    typename std::enable_if<std::is_integral<T>::value && sizeof(T) <= 8,
                            unsigned>::type
    CountTrailingZerosNonZero(T value) { … }

// Returns true iff |value| is a power of 2.
template <typename T,
          typename = typename std::enable_if<std::is_integral<T>::value ||
                                             std::is_enum<T>::value>::type>
constexpr inline bool IsPowerOfTwo(T value) { … }

// Identical to {CountTrailingZeros}, but only works for powers of 2.
template <typename T,
          typename = typename std::enable_if<std::is_integral<T>::value>::type>
inline constexpr int WhichPowerOfTwo(T value) { … }

// 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) { … }
// Same for 64 bit integers. |value| must be <= 2^63
V8_BASE_EXPORT constexpr uint64_t RoundUpToPowerOfTwo64(uint64_t value) { … }
// Same for size_t integers.
inline constexpr size_t RoundUpToPowerOfTwo(size_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) { … }


// Precondition: 0 <= shift < 32
inline constexpr uint32_t RotateRight32(uint32_t value, uint32_t shift) { … }

// Precondition: 0 <= shift < 32
inline constexpr uint32_t RotateLeft32(uint32_t value, uint32_t shift) { … }

// Precondition: 0 <= shift < 64
inline constexpr uint64_t RotateRight64(uint64_t value, uint64_t shift) { … }

// Precondition: 0 <= shift < 64
inline constexpr uint64_t RotateLeft64(uint64_t value, uint64_t shift) { … }

// 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) { … }


// 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) { … }

// 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) { … }

// 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) { … }


// 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) { … }

// 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) { … }

// 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) { … }


// 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) { … }

// 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) { … }

// 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) { … }

// 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) { … }

// Wraparound integer arithmetic without undefined behavior.

inline int32_t WraparoundAdd32(int32_t lhs, int32_t rhs) { … }

inline int32_t WraparoundNeg32(int32_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) { … }

}  // namespace bits
}  // namespace base
}  // namespace v8

#endif  // V8_BASE_BITS_H_
chromium/v8/src/base/bits.h
