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#include <limits> 6 7#include "src/base/bits.h" 8#include "src/base/macros.h" 9#include "testing/gtest-support.h" 10 11#ifdef DEBUG 12#define DISABLE_IN_RELEASE(Name) Name 13#else 14#define DISABLE_IN_RELEASE(Name) DISABLED_##Name 15#endif 16 17namespace v8 { 18namespace base { 19namespace bits { 20 21TEST(Bits, CountPopulation32) { 22 EXPECT_EQ(0u, CountPopulation32(0)); 23 EXPECT_EQ(1u, CountPopulation32(1)); 24 EXPECT_EQ(8u, CountPopulation32(0x11111111)); 25 EXPECT_EQ(16u, CountPopulation32(0xf0f0f0f0)); 26 EXPECT_EQ(24u, CountPopulation32(0xfff0f0ff)); 27 EXPECT_EQ(32u, CountPopulation32(0xffffffff)); 28} 29 30 31TEST(Bits, CountLeadingZeros32) { 32 EXPECT_EQ(32u, CountLeadingZeros32(0)); 33 EXPECT_EQ(31u, CountLeadingZeros32(1)); 34 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 35 EXPECT_EQ(31u - shift, CountLeadingZeros32(1u << shift)); 36 } 37 EXPECT_EQ(4u, CountLeadingZeros32(0x0f0f0f0f)); 38} 39 40 41TEST(Bits, CountTrailingZeros32) { 42 EXPECT_EQ(32u, CountTrailingZeros32(0)); 43 EXPECT_EQ(31u, CountTrailingZeros32(0x80000000)); 44 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 45 EXPECT_EQ(shift, CountTrailingZeros32(1u << shift)); 46 } 47 EXPECT_EQ(4u, CountTrailingZeros32(0xf0f0f0f0)); 48} 49 50 51TEST(Bits, IsPowerOfTwo32) { 52 EXPECT_FALSE(IsPowerOfTwo32(0U)); 53 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 54 EXPECT_TRUE(IsPowerOfTwo32(1U << shift)); 55 EXPECT_FALSE(IsPowerOfTwo32((1U << shift) + 5U)); 56 EXPECT_FALSE(IsPowerOfTwo32(~(1U << shift))); 57 } 58 TRACED_FORRANGE(uint32_t, shift, 2, 31) { 59 EXPECT_FALSE(IsPowerOfTwo32((1U << shift) - 1U)); 60 } 61 EXPECT_FALSE(IsPowerOfTwo32(0xffffffff)); 62} 63 64 65TEST(Bits, IsPowerOfTwo64) { 66 EXPECT_FALSE(IsPowerOfTwo64(0U)); 67 TRACED_FORRANGE(uint32_t, shift, 0, 63) { 68 EXPECT_TRUE(IsPowerOfTwo64(V8_UINT64_C(1) << shift)); 69 EXPECT_FALSE(IsPowerOfTwo64((V8_UINT64_C(1) << shift) + 5U)); 70 EXPECT_FALSE(IsPowerOfTwo64(~(V8_UINT64_C(1) << shift))); 71 } 72 TRACED_FORRANGE(uint32_t, shift, 2, 63) { 73 EXPECT_FALSE(IsPowerOfTwo64((V8_UINT64_C(1) << shift) - 1U)); 74 } 75 EXPECT_FALSE(IsPowerOfTwo64(V8_UINT64_C(0xffffffffffffffff))); 76} 77 78 79TEST(Bits, RoundUpToPowerOfTwo32) { 80 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 81 EXPECT_EQ(1u << shift, RoundUpToPowerOfTwo32(1u << shift)); 82 } 83 EXPECT_EQ(0u, RoundUpToPowerOfTwo32(0)); 84 EXPECT_EQ(4u, RoundUpToPowerOfTwo32(3)); 85 EXPECT_EQ(0x80000000u, RoundUpToPowerOfTwo32(0x7fffffffu)); 86} 87 88 89TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo32)) { 90 ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo32(0x80000001u); }, 91 "0x80000000"); 92} 93 94 95TEST(Bits, RoundDownToPowerOfTwo32) { 96 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 97 EXPECT_EQ(1u << shift, RoundDownToPowerOfTwo32(1u << shift)); 98 } 99 EXPECT_EQ(0u, RoundDownToPowerOfTwo32(0)); 100 EXPECT_EQ(4u, RoundDownToPowerOfTwo32(5)); 101 EXPECT_EQ(0x80000000u, RoundDownToPowerOfTwo32(0x80000001u)); 102} 103 104 105TEST(Bits, RotateRight32) { 106 TRACED_FORRANGE(uint32_t, shift, 0, 31) { 107 EXPECT_EQ(0u, RotateRight32(0u, shift)); 108 } 109 EXPECT_EQ(1u, RotateRight32(1, 0)); 110 EXPECT_EQ(1u, RotateRight32(2, 1)); 111 EXPECT_EQ(0x80000000u, RotateRight32(1, 1)); 112} 113 114 115TEST(Bits, RotateRight64) { 116 TRACED_FORRANGE(uint64_t, shift, 0, 63) { 117 EXPECT_EQ(0u, RotateRight64(0u, shift)); 118 } 119 EXPECT_EQ(1u, RotateRight64(1, 0)); 120 EXPECT_EQ(1u, RotateRight64(2, 1)); 121 EXPECT_EQ(V8_UINT64_C(0x8000000000000000), RotateRight64(1, 1)); 122} 123 124 125TEST(Bits, SignedAddOverflow32) { 126 int32_t val = 0; 127 EXPECT_FALSE(SignedAddOverflow32(0, 0, &val)); 128 EXPECT_EQ(0, val); 129 EXPECT_TRUE( 130 SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 1, &val)); 131 EXPECT_EQ(std::numeric_limits<int32_t>::min(), val); 132 EXPECT_TRUE( 133 SignedAddOverflow32(std::numeric_limits<int32_t>::min(), -1, &val)); 134 EXPECT_EQ(std::numeric_limits<int32_t>::max(), val); 135 EXPECT_TRUE(SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 136 std::numeric_limits<int32_t>::max(), &val)); 137 EXPECT_EQ(-2, val); 138 TRACED_FORRANGE(int32_t, i, 1, 50) { 139 TRACED_FORRANGE(int32_t, j, 1, i) { 140 EXPECT_FALSE(SignedAddOverflow32(i, j, &val)); 141 EXPECT_EQ(i + j, val); 142 } 143 } 144} 145 146 147TEST(Bits, SignedSubOverflow32) { 148 int32_t val = 0; 149 EXPECT_FALSE(SignedSubOverflow32(0, 0, &val)); 150 EXPECT_EQ(0, val); 151 EXPECT_TRUE( 152 SignedSubOverflow32(std::numeric_limits<int32_t>::min(), 1, &val)); 153 EXPECT_EQ(std::numeric_limits<int32_t>::max(), val); 154 EXPECT_TRUE( 155 SignedSubOverflow32(std::numeric_limits<int32_t>::max(), -1, &val)); 156 EXPECT_EQ(std::numeric_limits<int32_t>::min(), val); 157 TRACED_FORRANGE(int32_t, i, 1, 50) { 158 TRACED_FORRANGE(int32_t, j, 1, i) { 159 EXPECT_FALSE(SignedSubOverflow32(i, j, &val)); 160 EXPECT_EQ(i - j, val); 161 } 162 } 163} 164 165} // namespace bits 166} // namespace base 167} // namespace v8 168