LCOV - code coverage report
Current view: top level - src/base - bits.h (source / functions) Hit Total Coverage
Test: app.info Lines: 19 19 100.0 %
Date: 2017-04-26 Functions: 1 1 100.0 %

          Line data    Source code
       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             : 
      10             : #include "src/base/base-export.h"
      11             : #include "src/base/macros.h"
      12             : #if V8_CC_MSVC
      13             : #include <intrin.h>
      14             : #endif
      15             : #if V8_OS_WIN32
      16             : #include "src/base/win32-headers.h"
      17             : #endif
      18             : 
      19             : namespace v8 {
      20             : namespace base {
      21             : 
      22             : namespace internal {
      23             : template <typename T>
      24             : class CheckedNumeric;
      25             : }
      26             : 
      27             : namespace bits {
      28             : 
      29             : // CountPopulation32(value) returns the number of bits set in |value|.
      30             : inline unsigned CountPopulation32(uint32_t value) {
      31             : #if V8_HAS_BUILTIN_POPCOUNT
      32        8679 :   return __builtin_popcount(value);
      33             : #else
      34             :   value = ((value >> 1) & 0x55555555) + (value & 0x55555555);
      35             :   value = ((value >> 2) & 0x33333333) + (value & 0x33333333);
      36             :   value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f);
      37             :   value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff);
      38             :   value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff);
      39             :   return static_cast<unsigned>(value);
      40             : #endif
      41             : }
      42             : 
      43             : 
      44             : // CountPopulation64(value) returns the number of bits set in |value|.
      45             : inline unsigned CountPopulation64(uint64_t value) {
      46             : #if V8_HAS_BUILTIN_POPCOUNT
      47      247929 :   return __builtin_popcountll(value);
      48             : #else
      49             :   return CountPopulation32(static_cast<uint32_t>(value)) +
      50             :          CountPopulation32(static_cast<uint32_t>(value >> 32));
      51             : #endif
      52             : }
      53             : 
      54             : 
      55             : // Overloaded versions of CountPopulation32/64.
      56             : inline unsigned CountPopulation(uint32_t value) {
      57             :   return CountPopulation32(value);
      58             : }
      59             : 
      60             : 
      61             : inline unsigned CountPopulation(uint64_t value) {
      62             :   return CountPopulation64(value);
      63             : }
      64             : 
      65             : 
      66             : // CountLeadingZeros32(value) returns the number of zero bits following the most
      67             : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32.
      68    69419860 : inline unsigned CountLeadingZeros32(uint32_t value) {
      69             : #if V8_HAS_BUILTIN_CLZ
      70    69420322 :   return value ? __builtin_clz(value) : 32;
      71             : #elif V8_CC_MSVC
      72             :   unsigned long result;  // NOLINT(runtime/int)
      73             :   if (!_BitScanReverse(&result, value)) return 32;
      74             :   return static_cast<unsigned>(31 - result);
      75             : #else
      76             :   value = value | (value >> 1);
      77             :   value = value | (value >> 2);
      78             :   value = value | (value >> 4);
      79             :   value = value | (value >> 8);
      80             :   value = value | (value >> 16);
      81             :   return CountPopulation32(~value);
      82             : #endif
      83             : }
      84             : 
      85             : 
      86             : // CountLeadingZeros64(value) returns the number of zero bits following the most
      87             : // significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64.
      88             : inline unsigned CountLeadingZeros64(uint64_t value) {
      89             : #if V8_HAS_BUILTIN_CLZ
      90     2348621 :   return value ? __builtin_clzll(value) : 64;
      91             : #else
      92             :   value = value | (value >> 1);
      93             :   value = value | (value >> 2);
      94             :   value = value | (value >> 4);
      95             :   value = value | (value >> 8);
      96             :   value = value | (value >> 16);
      97             :   value = value | (value >> 32);
      98             :   return CountPopulation64(~value);
      99             : #endif
     100             : }
     101             : 
     102             : 
     103             : // ReverseBits(value) returns |value| in reverse bit order.
     104             : template <typename T>
     105             : T ReverseBits(T value) {
     106             :   DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) ||
     107             :          (sizeof(value) == 8));
     108             :   T result = 0;
     109             :   for (unsigned i = 0; i < (sizeof(value) * 8); i++) {
     110             :     result = (result << 1) | (value & 1);
     111             :     value >>= 1;
     112             :   }
     113             :   return result;
     114             : }
     115             : 
     116             : // CountTrailingZeros32(value) returns the number of zero bits preceding the
     117             : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
     118             : // returns 32.
     119             : inline unsigned CountTrailingZeros32(uint32_t value) {
     120             : #if V8_HAS_BUILTIN_CTZ
     121   884281361 :   return value ? __builtin_ctz(value) : 32;
     122             : #elif V8_CC_MSVC
     123             :   unsigned long result;  // NOLINT(runtime/int)
     124             :   if (!_BitScanForward(&result, value)) return 32;
     125             :   return static_cast<unsigned>(result);
     126             : #else
     127             :   if (value == 0) return 32;
     128             :   unsigned count = 0;
     129             :   for (value ^= value - 1; value >>= 1; ++count) {
     130             :   }
     131             :   return count;
     132             : #endif
     133             : }
     134             : 
     135             : 
     136             : // CountTrailingZeros64(value) returns the number of zero bits preceding the
     137             : // least significant 1 bit in |value| if |value| is non-zero, otherwise it
     138             : // returns 64.
     139             : inline unsigned CountTrailingZeros64(uint64_t value) {
     140             : #if V8_HAS_BUILTIN_CTZ
     141     2348635 :   return value ? __builtin_ctzll(value) : 64;
     142             : #else
     143             :   if (value == 0) return 64;
     144             :   unsigned count = 0;
     145             :   for (value ^= value - 1; value >>= 1; ++count) {
     146             :   }
     147             :   return count;
     148             : #endif
     149             : }
     150             : 
     151             : // Overloaded versions of CountTrailingZeros32/64.
     152             : inline unsigned CountTrailingZeros(uint32_t value) {
     153             :   return CountTrailingZeros32(value);
     154             : }
     155             : 
     156             : inline unsigned CountTrailingZeros(uint64_t value) {
     157             :   return CountTrailingZeros64(value);
     158             : }
     159             : 
     160             : // Returns true iff |value| is a power of 2.
     161             : inline bool IsPowerOfTwo32(uint32_t value) {
     162      325908 :   return value && !(value & (value - 1));
     163             : }
     164             : 
     165             : 
     166             : // Returns true iff |value| is a power of 2.
     167             : inline bool IsPowerOfTwo64(uint64_t value) {
     168       12659 :   return value && !(value & (value - 1));
     169             : }
     170             : 
     171             : 
     172             : // RoundUpToPowerOfTwo32(value) returns the smallest power of two which is
     173             : // greater than or equal to |value|. If you pass in a |value| that is already a
     174             : // power of two, it is returned as is. |value| must be less than or equal to
     175             : // 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren,
     176             : // Jr., figure 3-3, page 48, where the function is called clp2.
     177             : V8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value);
     178             : 
     179             : // RoundDownToPowerOfTwo32(value) returns the greatest power of two which is
     180             : // less than or equal to |value|. If you pass in a |value| that is already a
     181             : // power of two, it is returned as is.
     182             : inline uint32_t RoundDownToPowerOfTwo32(uint32_t value) {
     183             :   if (value > 0x80000000u) return 0x80000000u;
     184             :   uint32_t result = RoundUpToPowerOfTwo32(value);
     185             :   if (result > value) result >>= 1;
     186             :   return result;
     187             : }
     188             : 
     189             : 
     190             : // Precondition: 0 <= shift < 32
     191             : inline uint32_t RotateRight32(uint32_t value, uint32_t shift) {
     192        1516 :   if (shift == 0) return value;
     193        1516 :   return (value >> shift) | (value << (32 - shift));
     194             : }
     195             : 
     196             : // Precondition: 0 <= shift < 32
     197             : inline uint32_t RotateLeft32(uint32_t value, uint32_t shift) {
     198             :   if (shift == 0) return value;
     199             :   return (value << shift) | (value >> (32 - shift));
     200             : }
     201             : 
     202             : // Precondition: 0 <= shift < 64
     203             : inline uint64_t RotateRight64(uint64_t value, uint64_t shift) {
     204             :   if (shift == 0) return value;
     205             :   return (value >> shift) | (value << (64 - shift));
     206             : }
     207             : 
     208             : // Precondition: 0 <= shift < 64
     209             : inline uint64_t RotateLeft64(uint64_t value, uint64_t shift) {
     210             :   if (shift == 0) return value;
     211             :   return (value << shift) | (value >> (64 - shift));
     212             : }
     213             : 
     214             : 
     215             : // SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and
     216             : // |rhs| and stores the result into the variable pointed to by |val| and
     217             : // returns true if the signed summation resulted in an overflow.
     218             : inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
     219             : #if V8_HAS_BUILTIN_SADD_OVERFLOW
     220             :   return __builtin_sadd_overflow(lhs, rhs, val);
     221             : #else
     222       20038 :   uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
     223             :   *val = bit_cast<int32_t>(res);
     224       20038 :   return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0;
     225             : #endif
     226             : }
     227             : 
     228             : 
     229             : // SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and
     230             : // |rhs| and stores the result into the variable pointed to by |val| and
     231             : // returns true if the signed subtraction resulted in an overflow.
     232             : inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) {
     233             : #if V8_HAS_BUILTIN_SSUB_OVERFLOW
     234             :   return __builtin_ssub_overflow(lhs, rhs, val);
     235             : #else
     236       20024 :   uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
     237             :   *val = bit_cast<int32_t>(res);
     238       20024 :   return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0;
     239             : #endif
     240             : }
     241             : 
     242             : // SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs|
     243             : // and |rhs| and stores the result into the variable pointed to by |val| and
     244             : // returns true if the signed multiplication resulted in an overflow.
     245             : V8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val);
     246             : 
     247             : // SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and
     248             : // |rhs| and stores the result into the variable pointed to by |val| and
     249             : // returns true if the signed summation resulted in an overflow.
     250             : inline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
     251             :   uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs);
     252             :   *val = bit_cast<int64_t>(res);
     253             :   return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0;
     254             : }
     255             : 
     256             : 
     257             : // SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and
     258             : // |rhs| and stores the result into the variable pointed to by |val| and
     259             : // returns true if the signed subtraction resulted in an overflow.
     260             : inline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) {
     261             :   uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs);
     262             :   *val = bit_cast<int64_t>(res);
     263             :   return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0;
     264             : }
     265             : 
     266             : // SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs|
     267             : // and |rhs| and stores the result into the variable pointed to by |val| and
     268             : // returns true if the signed multiplication resulted in an overflow.
     269             : V8_BASE_EXPORT bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val);
     270             : 
     271             : // SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and
     272             : // |rhs|, extracts the most significant 32 bits of the result, and returns
     273             : // those.
     274             : V8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs);
     275             : 
     276             : // SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values
     277             : // |lhs| and |rhs|, extracts the most significant 32 bits of the result, and
     278             : // adds the accumulate value |acc|.
     279             : V8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs,
     280             :                                              int32_t acc);
     281             : 
     282             : // SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
     283             : // truncated to int32. If |rhs| is zero, then zero is returned. If |lhs|
     284             : // is minint and |rhs| is -1, it returns minint.
     285             : V8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs);
     286             : 
     287             : // SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
     288             : // truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs|
     289             : // is -1, it returns zero.
     290             : V8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs);
     291             : 
     292             : // UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs|
     293             : // and |rhs| and stores the result into the variable pointed to by |val| and
     294             : // returns true if the unsigned summation resulted in an overflow.
     295             : inline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) {
     296             : #if V8_HAS_BUILTIN_SADD_OVERFLOW
     297             :   return __builtin_uadd_overflow(lhs, rhs, val);
     298             : #else
     299   112379445 :   *val = lhs + rhs;
     300   112379445 :   return *val < (lhs | rhs);
     301             : #endif
     302             : }
     303             : 
     304             : 
     305             : // UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient
     306             : // truncated to uint32. If |rhs| is zero, then zero is returned.
     307             : inline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) {
     308       21516 :   return rhs ? lhs / rhs : 0u;
     309             : }
     310             : 
     311             : 
     312             : // UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder
     313             : // truncated to uint32. If |rhs| is zero, then zero is returned.
     314             : inline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) {
     315       21526 :   return rhs ? lhs % rhs : 0u;
     316             : }
     317             : 
     318             : 
     319             : // Clamp |value| on overflow and underflow conditions.
     320             : V8_BASE_EXPORT int64_t
     321             : FromCheckedNumeric(const internal::CheckedNumeric<int64_t> value);
     322             : 
     323             : // SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|,
     324             : // checks and returns the result.
     325             : V8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs);
     326             : 
     327             : // SignedSaturatedSub64(lhs, rhs) substracts |lhs| by |rhs|,
     328             : // checks and returns the result.
     329             : V8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs);
     330             : 
     331             : }  // namespace bits
     332             : }  // namespace base
     333             : }  // namespace v8
     334             : 
     335             : #endif  // V8_BASE_BITS_H_

Generated by: LCOV version 1.10