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 17 namespace v8 { 18 namespace base { 19 namespace bits { 20 21 TEST(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 31 TEST(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 41 TEST(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 51 TEST(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 65 TEST(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 79 TEST(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 89 TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo32)) { 90 ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo32(0x80000001u); }, 91 "0x80000000"); 92 } 93 94 95 TEST(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 105 TEST(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 115 TEST(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 125 TEST(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 147 TEST(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