bits.h 12.2 KB
Newer Older
1 2 3 4 5 6 7
// 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_

8
#include <stdint.h>
9
#include <type_traits>
10 11

#include "src/base/base-export.h"
12
#include "src/base/macros.h"
13 14 15
#if V8_CC_MSVC
#include <intrin.h>
#endif
bmeurer@chromium.org's avatar
bmeurer@chromium.org committed
16 17 18
#if V8_OS_WIN32
#include "src/base/win32-headers.h"
#endif
19 20 21 22 23

namespace v8 {
namespace base {
namespace bits {

24 25 26 27 28 29
// 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) {
30
  STATIC_ASSERT(sizeof(T) <= 8);
31
#if V8_HAS_BUILTIN_POPCOUNT
32 33
  return sizeof(T) == 8 ? __builtin_popcountll(static_cast<uint64_t>(value))
                        : __builtin_popcount(static_cast<uint32_t>(value));
34
#else
35
  constexpr uint64_t mask[] = {0x5555555555555555, 0x3333333333333333,
36 37
                               0x0f0f0f0f0f0f0f0f};
  // Start with 1 bit wide buckets of [0,1].
38
  value = ((value >> 1) & mask[0]) + (value & mask[0]);
39
  // Having 2 bit wide buckets of [0,2] now.
40
  value = ((value >> 2) & mask[1]) + (value & mask[1]);
41 42 43
  // Having 4 bit wide buckets of [0,4] now.
  value = (value >> 4) + value;
  // Having 4 bit wide buckets of [0,8] now.
44
  if (sizeof(T) > 1)
45 46 47 48 49 50 51
    value = ((value >> (sizeof(T) > 1 ? 8 : 0)) & mask[2]) + (value & mask[2]);
  // Having 8 bit wide buckets of [0,16] now.
  if (sizeof(T) > 2) value = (value >> (sizeof(T) > 2 ? 16 : 0)) + value;
  // Having 8 bit wide buckets of [0,32] now.
  if (sizeof(T) > 4) value = (value >> (sizeof(T) > 4 ? 32 : 0)) + value;
  // Having 8 bit wide buckets of [0,64] now.
  return static_cast<unsigned>(value & 0xff);
52 53 54
#endif
}

55 56 57
// ReverseBits(value) returns |value| in reverse bit order.
template <typename T>
T ReverseBits(T value) {
58 59
  STATIC_ASSERT((sizeof(value) == 1) || (sizeof(value) == 2) ||
                (sizeof(value) == 4) || (sizeof(value) == 8));
60 61 62 63 64 65 66 67
  T result = 0;
  for (unsigned i = 0; i < (sizeof(value) * 8); i++) {
    result = (result << 1) | (value & 1);
    value >>= 1;
  }
  return result;
}

68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
// 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) {
  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);
83
#else
84 85 86 87 88 89 90 91
  // 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;
92 93 94
#endif
}

95 96 97 98 99 100
inline constexpr unsigned CountLeadingZeros32(uint32_t value) {
  return CountLeadingZeros(value);
}
inline constexpr unsigned CountLeadingZeros64(uint64_t value) {
  return CountLeadingZeros(value);
}
101

102
// CountTrailingZeros(value) returns the number of zero bits preceding the
103
// least significant 1 bit in |value| if |value| is non-zero, otherwise it
104 105 106 107 108 109
// returns {sizeof(T) * 8}.
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) {
110
#if V8_HAS_BUILTIN_CTZ
111 112 113
  return value == 0 ? bits
                    : bits == 64 ? __builtin_ctzll(static_cast<uint64_t>(value))
                                 : __builtin_ctz(static_cast<uint32_t>(value));
114
#else
115 116 117 118 119 120
  // 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)));
121 122 123
#endif
}

124 125 126 127 128 129
inline constexpr unsigned CountTrailingZeros32(uint32_t value) {
  return CountTrailingZeros(value);
}
inline constexpr unsigned CountTrailingZeros64(uint64_t value) {
  return CountTrailingZeros(value);
}
130

131
// Returns true iff |value| is a power of 2.
132
template <typename T,
133 134
          typename = typename std::enable_if<std::is_integral<T>::value ||
                                             std::is_enum<T>::value>::type>
135 136
constexpr inline bool IsPowerOfTwo(T value) {
  return value > 0 && (value & (value - 1)) == 0;
137 138
}

139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
// 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) {
#if V8_HAS_CXX14_CONSTEXPR
  DCHECK(IsPowerOfTwo(value));
#endif
#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
}

160 161 162
// 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
163 164 165
// 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.
166
V8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value);
167 168
// Same for 64 bit integers. |value| must be <= 2^63
V8_BASE_EXPORT uint64_t RoundUpToPowerOfTwo64(uint64_t value);
169 170 171 172 173 174 175 176
// Same for size_t integers.
inline size_t RoundUpToPowerOfTwo(size_t value) {
  if (sizeof(size_t) == sizeof(uint64_t)) {
    return RoundUpToPowerOfTwo64(value);
  } else {
    return RoundUpToPowerOfTwo32(value);
  }
}
177 178 179 180 181 182 183 184 185 186 187 188

// 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;
}


189
// Precondition: 0 <= shift < 32
190 191
inline constexpr uint32_t RotateRight32(uint32_t value, uint32_t shift) {
  return (value >> shift) | (value << ((32 - shift) & 31));
192 193
}

194
// Precondition: 0 <= shift < 32
195 196
inline constexpr uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
  return (value << shift) | (value >> ((32 - shift) & 31));
197
}
198

199
// Precondition: 0 <= shift < 64
200 201
inline constexpr uint64_t RotateRight64(uint64_t value, uint64_t shift) {
  return (value >> shift) | (value << ((64 - shift) & 63));
202 203
}

204
// Precondition: 0 <= shift < 64
205 206
inline constexpr uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
  return (value << shift) | (value >> ((64 - shift) & 63));
207 208
}

209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235
// 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 = 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 = bit_cast<int32_t>(res);
  return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
#endif
}

236 237 238
// 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.
239
V8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
240

241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
// 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) {
  uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
  *val = bit_cast<int64_t>(res);
  return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
}


// 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) {
  uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
  *val = bit_cast<int64_t>(res);
  return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
}

260 261 262
// SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
// |rhs|, extracts the most significant 32 bits of the result, and returns
// those.
263
V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
264 265 266 267

// 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|.
268 269
V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
                                             int32_t acc);
270 271 272 273

// 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.
274
V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
275 276 277 278

// 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.
279
V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
280

281 282 283 284 285 286 287 288 289 290 291 292 293
// 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
}


294 295 296 297 298 299 300 301 302 303 304 305 306
// 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;
}


// 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;
}

307 308 309

// SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
// checks and returns the result.
310
V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);
311

312
// SignedSaturatedSub64(lhs, rhs) subtracts |lhs| by |rhs|,
313
// checks and returns the result.
314
V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);
315

316 317 318 319 320
}  // namespace bits
}  // namespace base
}  // namespace v8

#endif  // V8_BASE_BITS_H_