Home | History | Annotate | Download | only in base 
      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_
    151