src/v8/src/base/bits.h

   1 // Copyright 2014 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 #ifndef V8_BASE_BITS_H_
   6 #define V8_BASE_BITS_H_
   7
   8 #include <stdint.h>
   9 #include "src/base/macros.h"
  10 #if V8_CC_MSVC
  11 #include <intrin.h>
  12 #endif
  13 #if V8_OS_WIN32
  14 #include "src/base/win32-headers.h"
  15 #endif
  16
  17 namespace v8 {
  18 namespace base {
  19 namespace bits {
  20
  21 // CountPopulation32(value) returns the number of bits set in |value|.
  22 inline unsigned CountPopulation32(uint32_t value) {
  23 #if V8_HAS_BUILTIN_POPCOUNT
  24   return __builtin_popcount(value);
  25 #else
  26   value = ((value >> 1) & 0x55555555) + (value & 0x55555555);
  27   value = ((value >> 2) & 0x33333333) + (value & 0x33333333);
  28   value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f);
  29   value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff);
  30   value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff);
  31   return static_cast<unsigned>(value);
  32 #endif
  33 }
  34
  35
  36 // CountPopulation64(value) returns the number of bits set in |value|.
  37 inline unsigned CountPopulation64(uint64_t value) {
  38 #if V8_HAS_BUILTIN_POPCOUNT
  39   return __builtin_popcountll(value);
  40 #else
  41   return CountPopulation32(static_cast<uint32_t>(value)) +
  42          CountPopulation32(static_cast<uint32_t>(value >> 32));
  43 #endif
  44 }
  45
  46
  47 // CountLeadingZeros32(value) returns the number of zero bits following the most
  48 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
  49 inline unsigned CountLeadingZeros32(uint32_t value) {
  50 #if V8_HAS_BUILTIN_CLZ
  51   return value ? __builtin_clz(value) : 32;
  52 #elif V8_CC_MSVC
  53   unsigned long result;  // NOLINT(runtime/int)
  54   if (!_BitScanReverse(&result, value)) return 32;
  55   return static_cast<unsigned>(31 - result);
  56 #else
  57   value = value | (value >> 1);
  58   value = value | (value >> 2);
  59   value = value | (value >> 4);
  60   value = value | (value >> 8);
  61   value = value | (value >> 16);
  62   return CountPopulation32(~value);
  63 #endif
  64 }
  65
  66
  67 // CountLeadingZeros64(value) returns the number of zero bits following the most
  68 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64.
  69 inline unsigned CountLeadingZeros64(uint64_t value) {
  70 #if V8_HAS_BUILTIN_CLZ
  71   return value ? __builtin_clzll(value) : 64;
  72 #else
  73   value = value | (value >> 1);
  74   value = value | (value >> 2);
  75   value = value | (value >> 4);
  76   value = value | (value >> 8);
  77   value = value | (value >> 16);
  78   value = value | (value >> 32);
  79   return CountPopulation64(~value);
  80 #endif
  81 }
  82
  83
  84 // CountTrailingZeros32(value) returns the number of zero bits preceding the
  85 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
  86 // returns 32.
  87 inline unsigned CountTrailingZeros32(uint32_t value) {
  88 #if V8_HAS_BUILTIN_CTZ
  89   return value ? __builtin_ctz(value) : 32;
  90 #elif V8_CC_MSVC
  91   unsigned long result;  // NOLINT(runtime/int)
  92   if (!_BitScanForward(&result, value)) return 32;
  93   return static_cast<unsigned>(result);
  94 #else
  95   if (value == 0) return 32;
  96   unsigned count = 0;
  97   for (value ^= value - 1; value >>= 1; ++count)
  98     ;
  99   return count;
 100 #endif
 101 }
 102
 103
 104 // CountTrailingZeros64(value) returns the number of zero bits preceding the
 105 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
 106 // returns 64.
 107 inline unsigned CountTrailingZeros64(uint64_t value) {
 108 #if V8_HAS_BUILTIN_CTZ
 109   return value ? __builtin_ctzll(value) : 64;
 110 #else
 111   if (value == 0) return 64;
 112   unsigned count = 0;
 113   for (value ^= value - 1; value >>= 1; ++count)
 114     ;
 115   return count;
 116 #endif
 117 }
 118
 119
 120 // Returns true iff |value| is a power of 2.
 121 inline bool IsPowerOfTwo32(uint32_t value) {
 122   return value && !(value & (value - 1));
 123 }
 124
 125
 126 // Returns true iff |value| is a power of 2.
 127 inline bool IsPowerOfTwo64(uint64_t value) {
 128   return value && !(value & (value - 1));
 129 }
 130
 131
 132 // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
 133 // greater than or equal to |value|. If you pass in a |value| that is already a
 134 // power of two, it is returned as is. |value| must be less than or equal to
 135 // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
 136 // Jr., figure 3-3, page 48, where the function is called clp2.
 137 uint32_t RoundUpToPowerOfTwo32(uint32_t value);
 138
 139
 140 // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
 141 // less than or equal to |value|. If you pass in a |value| that is already a
 142 // power of two, it is returned as is.
 143 inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
 144   if (value > 0x80000000u) return 0x80000000u;
 145   uint32_t result = RoundUpToPowerOfTwo32(value);
 146   if (result > value) result >>= 1;
 147   return result;
 148 }
 149
 150
 151 inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
 152   if (shift == 0) return value;
 153   return (value >> shift) | (value << (32 - shift));
 154 }
 155
 156
 157 inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
 158   if (shift == 0) return value;
 159   return (value >> shift) | (value << (64 - shift));
 160 }
 161
 162
 163 // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
 164 // |rhs| and stores the result into the variable pointed to by |val| and
 165 // returns true if the signed summation resulted in an overflow.
 166 inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
 167 #if V8_HAS_BUILTIN_SADD_OVERFLOW
 168   return __builtin_sadd_overflow(lhs, rhs, val);
 169 #else
 170   uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
 171   *val = bit_cast<int32_t>(res);
 172   return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
 173 #endif
 174 }
 175
 176
 177 // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
 178 // |rhs| and stores the result into the variable pointed to by |val| and
 179 // returns true if the signed subtraction resulted in an overflow.
 180 inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
 181 #if V8_HAS_BUILTIN_SSUB_OVERFLOW
 182   return __builtin_ssub_overflow(lhs, rhs, val);
 183 #else
 184   uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
 185   *val = bit_cast<int32_t>(res);
 186   return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
 187 #endif
 188 }
 189
 190
 191 // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
 192 // |rhs|, extracts the most significant 32 bits of the result, and returns
 193 // those.
 194 int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
 195
 196
 197 // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
 198 // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
 199 // adds the accumulate value |acc|.
 200 int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, int32_t acc);
 201
 202
 203 // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
 204 // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
 205 // is minint and |rhs| is -1, it returns minint.
 206 int32_t SignedDiv32(int32_t lhs, int32_t rhs);
 207
 208
 209 // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
 210 // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
 211 // is -1, it returns zero.
 212 int32_t SignedMod32(int32_t lhs, int32_t rhs);
 213
 214
 215 // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
 216 // truncated to uint32. If |rhs| is zero, then zero is returned.
 217 inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
 218   return rhs ? lhs / rhs : 0u;
 219 }
 220
 221
 222 // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
 223 // truncated to uint32. If |rhs| is zero, then zero is returned.
 224 inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
 225   return rhs ? lhs % rhs : 0u;
 226 }
 227
 228 }  // namespace bits
 229 }  // namespace base
 230 }  // namespace v8
 231
 232 #endif  // V8_BASE_BITS_H_