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 "include/v8stdint.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 uint32_t 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 value;
  32 #endif
  33 }
  34
  35
  36 // CountLeadingZeros32(value) returns the number of zero bits following the most
  37 // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
  38 inline uint32_t CountLeadingZeros32(uint32_t value) {
  39 #if V8_HAS_BUILTIN_CLZ
  40   return value ? __builtin_clz(value) : 32;
  41 #elif V8_CC_MSVC
  42   unsigned long result;  // NOLINT(runtime/int)
  43   if (!_BitScanReverse(&result, value)) return 32;
  44   return static_cast<uint32_t>(31 - result);
  45 #else
  46   value = value | (value >> 1);
  47   value = value | (value >> 2);
  48   value = value | (value >> 4);
  49   value = value | (value >> 8);
  50   value = value | (value >> 16);
  51   return CountPopulation32(~value);
  52 #endif
  53 }
  54
  55
  56 // CountTrailingZeros32(value) returns the number of zero bits preceding the
  57 // least significant 1 bit in |value| if |value| is non-zero, otherwise it
  58 // returns 32.
  59 inline uint32_t CountTrailingZeros32(uint32_t value) {
  60 #if V8_HAS_BUILTIN_CTZ
  61   return value ? __builtin_ctz(value) : 32;
  62 #elif V8_CC_MSVC
  63   unsigned long result;  // NOLINT(runtime/int)
  64   if (!_BitScanForward(&result, value)) return 32;
  65   return static_cast<uint32_t>(result);
  66 #else
  67   if (value == 0) return 32;
  68   unsigned count = 0;
  69   for (value ^= value - 1; value >>= 1; ++count)
  70     ;
  71   return count;
  72 #endif
  73 }
  74
  75
  76 // Returns true iff |value| is a power of 2.
  77 inline bool IsPowerOfTwo32(uint32_t value) {
  78   return value && !(value & (value - 1));
  79 }
  80
  81
  82 // Returns true iff |value| is a power of 2.
  83 inline bool IsPowerOfTwo64(uint64_t value) {
  84   return value && !(value & (value - 1));
  85 }
  86
  87
  88 // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
  89 // greater than or equal to |value|. If you pass in a |value| that is already a
  90 // power of two, it is returned as is. |value| must be less than or equal to
  91 // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
  92 // Jr., figure 3-3, page 48, where the function is called clp2.
  93 uint32_t RoundUpToPowerOfTwo32(uint32_t value);
  94
  95
  96 // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
  97 // less than or equal to |value|. If you pass in a |value| that is already a
  98 // power of two, it is returned as is.
  99 inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
 100   if (value > 0x80000000u) return 0x80000000u;
 101   uint32_t result = RoundUpToPowerOfTwo32(value);
 102   if (result > value) result >>= 1;
 103   return result;
 104 }
 105
 106
 107 inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
 108   if (shift == 0) return value;
 109   return (value >> shift) | (value << (32 - shift));
 110 }
 111
 112
 113 inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
 114   if (shift == 0) return value;
 115   return (value >> shift) | (value << (64 - shift));
 116 }
 117
 118
 119 // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
 120 // |rhs| and stores the result into the variable pointed to by |val| and
 121 // returns true if the signed summation resulted in an overflow.
 122 inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
 123 #if V8_HAS_BUILTIN_SADD_OVERFLOW
 124   return __builtin_sadd_overflow(lhs, rhs, val);
 125 #else
 126   uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
 127   *val = bit_cast<int32_t>(res);
 128   return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
 129 #endif
 130 }
 131
 132
 133 // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
 134 // |rhs| and stores the result into the variable pointed to by |val| and
 135 // returns true if the signed subtraction resulted in an overflow.
 136 inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
 137 #if V8_HAS_BUILTIN_SSUB_OVERFLOW
 138   return __builtin_ssub_overflow(lhs, rhs, val);
 139 #else
 140   uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
 141   *val = bit_cast<int32_t>(res);
 142   return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
 143 #endif
 144 }
 145
 146 }  // namespace bits
 147 }  // namespace base
 148 }  // namespace v8
 149
 150 #endif  // V8_BASE_BITS_H_