1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_BASE_BITS_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_BASE_BITS_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include <stdint.h> 9c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch 10c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/base/base-export.h" 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/base/macros.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_CC_MSVC 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <intrin.h> 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_OS_WIN32 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/base/win32-headers.h" 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace base { 21bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 22bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochnamespace internal { 23bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochtemplate <typename T> 24bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochclass CheckedNumeric; 25bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} 26bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace bits { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// CountPopulation32(value) returns the number of bits set in |value|. 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountPopulation32(uint32_t value) { 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_HAS_BUILTIN_POPCOUNT 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return __builtin_popcount(value); 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = ((value >> 1) & 0x55555555) + (value & 0x55555555); 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = ((value >> 2) & 0x33333333) + (value & 0x33333333); 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f); 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff); 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff); 39958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return static_cast<unsigned>(value); 40958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#endif 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 42958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 43958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 44958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// CountPopulation64(value) returns the number of bits set in |value|. 45958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountPopulation64(uint64_t value) { 46958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#if V8_HAS_BUILTIN_POPCOUNT 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return __builtin_popcountll(value); 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#else 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return CountPopulation32(static_cast<uint32_t>(value)) + 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier CountPopulation32(static_cast<uint32_t>(value >> 32)); 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 55014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Overloaded versions of CountPopulation32/64. 56014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline unsigned CountPopulation(uint32_t value) { 57014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return CountPopulation32(value); 58014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 59014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 60014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline unsigned CountPopulation(uint64_t value) { 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return CountPopulation64(value); 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// CountLeadingZeros32(value) returns the number of zero bits following the most 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32. 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountLeadingZeros32(uint32_t value) { 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_HAS_BUILTIN_CLZ 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value ? __builtin_clz(value) : 32; 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#elif V8_CC_MSVC 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unsigned long result; // NOLINT(runtime/int) 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!_BitScanReverse(&result, value)) return 32; 74958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return static_cast<unsigned>(31 - result); 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = value | (value >> 1); 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = value | (value >> 2); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = value | (value >> 4); 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = value | (value >> 8); 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch value = value | (value >> 16); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return CountPopulation32(~value); 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 86958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// CountLeadingZeros64(value) returns the number of zero bits following the most 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// significant 1 bit in |value| if |value| is non-zero, otherwise it returns 64. 88958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountLeadingZeros64(uint64_t value) { 89958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#if V8_HAS_BUILTIN_CLZ 90958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return value ? __builtin_clzll(value) : 64; 91958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#else 92958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 1); 93958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 2); 94958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 4); 95958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 8); 96958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 16); 97958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier value = value | (value >> 32); 98958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return CountPopulation64(~value); 99958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#endif 100958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 101958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 102958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 103109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch// ReverseBits(value) returns |value| in reverse bit order. 104109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdochtemplate <typename T> 105109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben MurdochT ReverseBits(T value) { 106109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch DCHECK((sizeof(value) == 1) || (sizeof(value) == 2) || (sizeof(value) == 4) || 107109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch (sizeof(value) == 8)); 108109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch T result = 0; 109109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch for (unsigned i = 0; i < (sizeof(value) * 8); i++) { 110109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch result = (result << 1) | (value & 1); 111109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch value >>= 1; 112109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch } 113109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch return result; 114109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch} 115109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// CountTrailingZeros32(value) returns the number of zero bits preceding the 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// least significant 1 bit in |value| if |value| is non-zero, otherwise it 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// returns 32. 119958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountTrailingZeros32(uint32_t value) { 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_HAS_BUILTIN_CTZ 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value ? __builtin_ctz(value) : 32; 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#elif V8_CC_MSVC 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unsigned long result; // NOLINT(runtime/int) 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!_BitScanForward(&result, value)) return 32; 125958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return static_cast<unsigned>(result); 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (value == 0) return 32; 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unsigned count = 0; 129014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (value ^= value - 1; value >>= 1; ++count) { 130014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return count; 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 136958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// CountTrailingZeros64(value) returns the number of zero bits preceding the 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// least significant 1 bit in |value| if |value| is non-zero, otherwise it 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// returns 64. 139958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline unsigned CountTrailingZeros64(uint64_t value) { 140958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#if V8_HAS_BUILTIN_CTZ 141958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return value ? __builtin_ctzll(value) : 64; 142958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#else 143958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (value == 0) return 64; 144958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier unsigned count = 0; 145014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (value ^= value - 1; value >>= 1; ++count) { 146014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 147958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return count; 148958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#endif 149958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 15113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// Overloaded versions of CountTrailingZeros32/64. 15213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochinline unsigned CountTrailingZeros(uint32_t value) { 15313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch return CountTrailingZeros32(value); 15413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 15513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 15613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochinline unsigned CountTrailingZeros(uint64_t value) { 15713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch return CountTrailingZeros64(value); 15813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 159958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Returns true iff |value| is a power of 2. 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline bool IsPowerOfTwo32(uint32_t value) { 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value && !(value & (value - 1)); 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Returns true iff |value| is a power of 2. 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline bool IsPowerOfTwo64(uint64_t value) { 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return value && !(value & (value - 1)); 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// RoundUpToPowerOfTwo32(value) returns the smallest power of two which is 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// greater than or equal to |value|. If you pass in a |value| that is already a 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// power of two, it is returned as is. |value| must be less than or equal to 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 0x80000000u. Implementation is from "Hacker's Delight" by Henry S. Warren, 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Jr., figure 3-3, page 48, where the function is called clp2. 177c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT uint32_t RoundUpToPowerOfTwo32(uint32_t value); 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// RoundDownToPowerOfTwo32(value) returns the greatest power of two which is 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// less than or equal to |value|. If you pass in a |value| that is already a 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// power of two, it is returned as is. 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline uint32_t RoundDownToPowerOfTwo32(uint32_t value) { 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (value > 0x80000000u) return 0x80000000u; 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t result = RoundUpToPowerOfTwo32(value); 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (result > value) result >>= 1; 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 190014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Precondition: 0 <= shift < 32 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline uint32_t RotateRight32(uint32_t value, uint32_t shift) { 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (shift == 0) return value; 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return (value >> shift) | (value << (32 - shift)); 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 196014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Precondition: 0 <= shift < 32 197014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline uint32_t RotateLeft32(uint32_t value, uint32_t shift) { 198014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (shift == 0) return value; 199014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return (value << shift) | (value >> (32 - shift)); 200014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 202014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Precondition: 0 <= shift < 64 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline uint64_t RotateRight64(uint64_t value, uint64_t shift) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (shift == 0) return value; 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return (value >> shift) | (value << (64 - shift)); 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 208014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Precondition: 0 <= shift < 64 209014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline uint64_t RotateLeft64(uint64_t value, uint64_t shift) { 210014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (shift == 0) return value; 211014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return (value << shift) | (value >> (64 - shift)); 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// SignedAddOverflow32(lhs,rhs,val) performs a signed summation of |lhs| and 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// |rhs| and stores the result into the variable pointed to by |val| and 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// returns true if the signed summation resulted in an overflow. 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_HAS_BUILTIN_SADD_OVERFLOW 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return __builtin_sadd_overflow(lhs, rhs, val); 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs); 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *val = bit_cast<int32_t>(res); 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return ((res ^ lhs) & (res ^ rhs) & (1U << 31)) != 0; 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// SignedSubOverflow32(lhs,rhs,val) performs a signed subtraction of |lhs| and 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// |rhs| and stores the result into the variable pointed to by |val| and 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// returns true if the signed subtraction resulted in an overflow. 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t* val) { 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if V8_HAS_BUILTIN_SSUB_OVERFLOW 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return __builtin_ssub_overflow(lhs, rhs, val); 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs); 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *val = bit_cast<int32_t>(res); 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return ((res ^ lhs) & (res ^ ~rhs) & (1U << 31)) != 0; 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 242f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// SignedMulOverflow32(lhs,rhs,val) performs a signed multiplication of |lhs| 243f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// and |rhs| and stores the result into the variable pointed to by |val| and 244f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// returns true if the signed multiplication resulted in an overflow. 245c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t* val); 246958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 247014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// SignedAddOverflow64(lhs,rhs,val) performs a signed summation of |lhs| and 248014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// |rhs| and stores the result into the variable pointed to by |val| and 249014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// returns true if the signed summation resulted in an overflow. 250014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline bool SignedAddOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { 251014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint64_t res = static_cast<uint64_t>(lhs) + static_cast<uint64_t>(rhs); 252014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch *val = bit_cast<int64_t>(res); 253014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return ((res ^ lhs) & (res ^ rhs) & (1ULL << 63)) != 0; 254014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 255014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 256014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 257014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// SignedSubOverflow64(lhs,rhs,val) performs a signed subtraction of |lhs| and 258014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// |rhs| and stores the result into the variable pointed to by |val| and 259014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// returns true if the signed subtraction resulted in an overflow. 260014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline bool SignedSubOverflow64(int64_t lhs, int64_t rhs, int64_t* val) { 261014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint64_t res = static_cast<uint64_t>(lhs) - static_cast<uint64_t>(rhs); 262014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch *val = bit_cast<int64_t>(res); 263014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return ((res ^ lhs) & (res ^ ~rhs) & (1ULL << 63)) != 0; 264014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 265014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 266f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// SignedMulOverflow64(lhs,rhs,val) performs a signed multiplication of |lhs| 267f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// and |rhs| and stores the result into the variable pointed to by |val| and 268f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// returns true if the signed multiplication resulted in an overflow. 269c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT bool SignedMulOverflow64(int64_t lhs, int64_t rhs, int64_t* val); 270014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 271958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// SignedMulHigh32(lhs, rhs) multiplies two signed 32-bit values |lhs| and 272958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// |rhs|, extracts the most significant 32 bits of the result, and returns 273958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// those. 274c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int32_t SignedMulHigh32(int32_t lhs, int32_t rhs); 275958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 276958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// SignedMulHighAndAdd32(lhs, rhs, acc) multiplies two signed 32-bit values 277958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// |lhs| and |rhs|, extracts the most significant 32 bits of the result, and 278958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// adds the accumulate value |acc|. 279c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, 280c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch int32_t acc); 281958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 282958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// SignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient 283958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// truncated to int32. If |rhs| is zero, then zero is returned. If |lhs| 284958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// is minint and |rhs| is -1, it returns minint. 285c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int32_t SignedDiv32(int32_t lhs, int32_t rhs); 286958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 287958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// SignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder 288958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// truncated to int32. If either |rhs| is zero or |lhs| is minint and |rhs| 289958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// is -1, it returns zero. 290c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int32_t SignedMod32(int32_t lhs, int32_t rhs); 291958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 292014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// UnsignedAddOverflow32(lhs,rhs,val) performs an unsigned summation of |lhs| 293014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// and |rhs| and stores the result into the variable pointed to by |val| and 294014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// returns true if the unsigned summation resulted in an overflow. 295014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochinline bool UnsignedAddOverflow32(uint32_t lhs, uint32_t rhs, uint32_t* val) { 296014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#if V8_HAS_BUILTIN_SADD_OVERFLOW 297014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return __builtin_uadd_overflow(lhs, rhs, val); 298014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#else 299014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch *val = lhs + rhs; 300014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return *val < (lhs | rhs); 301014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif 302014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 303014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 304014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 305958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// UnsignedDiv32(lhs, rhs) divides |lhs| by |rhs| and returns the quotient 306958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// truncated to uint32. If |rhs| is zero, then zero is returned. 307958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline uint32_t UnsignedDiv32(uint32_t lhs, uint32_t rhs) { 308958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return rhs ? lhs / rhs : 0u; 309958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 310958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 311958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 312958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// UnsignedMod32(lhs, rhs) divides |lhs| by |rhs| and returns the remainder 313958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// truncated to uint32. If |rhs| is zero, then zero is returned. 314958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierinline uint32_t UnsignedMod32(uint32_t lhs, uint32_t rhs) { 315958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return rhs ? lhs % rhs : 0u; 316958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 317958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 318bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 319bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// Clamp |value| on overflow and underflow conditions. 320c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int64_t 321c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochFromCheckedNumeric(const internal::CheckedNumeric<int64_t> value); 322bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 323bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// SignedSaturatedAdd64(lhs, rhs) adds |lhs| and |rhs|, 324bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// checks and returns the result. 325c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs); 326bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 327bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// SignedSaturatedSub64(lhs, rhs) substracts |lhs| by |rhs|, 328bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch// checks and returns the result. 329c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_BASE_EXPORT int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs); 330bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace bits 332b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace base 333b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace v8 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_BASE_BITS_H_ 336