Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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, CountPopulation64) { |
| 32 | EXPECT_EQ(0u, CountPopulation64(0)); |
| 33 | EXPECT_EQ(1u, CountPopulation64(1)); |
| 34 | EXPECT_EQ(2u, CountPopulation64(0x8000000000000001)); |
| 35 | EXPECT_EQ(8u, CountPopulation64(0x11111111)); |
| 36 | EXPECT_EQ(16u, CountPopulation64(0xf0f0f0f0)); |
| 37 | EXPECT_EQ(24u, CountPopulation64(0xfff0f0ff)); |
| 38 | EXPECT_EQ(32u, CountPopulation64(0xffffffff)); |
| 39 | EXPECT_EQ(16u, CountPopulation64(0x1111111111111111)); |
| 40 | EXPECT_EQ(32u, CountPopulation64(0xf0f0f0f0f0f0f0f0)); |
| 41 | EXPECT_EQ(48u, CountPopulation64(0xfff0f0fffff0f0ff)); |
| 42 | EXPECT_EQ(64u, CountPopulation64(0xffffffffffffffff)); |
| 43 | } |
| 44 | |
| 45 | |
| 46 | TEST(Bits, CountLeadingZeros32) { |
| 47 | EXPECT_EQ(32u, CountLeadingZeros32(0)); |
| 48 | EXPECT_EQ(31u, CountLeadingZeros32(1)); |
| 49 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 50 | EXPECT_EQ(31u - shift, CountLeadingZeros32(1u << shift)); |
| 51 | } |
| 52 | EXPECT_EQ(4u, CountLeadingZeros32(0x0f0f0f0f)); |
| 53 | } |
| 54 | |
| 55 | |
| 56 | TEST(Bits, CountLeadingZeros64) { |
| 57 | EXPECT_EQ(64u, CountLeadingZeros64(0)); |
| 58 | EXPECT_EQ(63u, CountLeadingZeros64(1)); |
| 59 | TRACED_FORRANGE(uint32_t, shift, 0, 63) { |
| 60 | EXPECT_EQ(63u - shift, CountLeadingZeros64(V8_UINT64_C(1) << shift)); |
| 61 | } |
| 62 | EXPECT_EQ(36u, CountLeadingZeros64(0x0f0f0f0f)); |
| 63 | EXPECT_EQ(4u, CountLeadingZeros64(0x0f0f0f0f00000000)); |
| 64 | } |
| 65 | |
| 66 | |
| 67 | TEST(Bits, CountTrailingZeros32) { |
| 68 | EXPECT_EQ(32u, CountTrailingZeros32(0)); |
| 69 | EXPECT_EQ(31u, CountTrailingZeros32(0x80000000)); |
| 70 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 71 | EXPECT_EQ(shift, CountTrailingZeros32(1u << shift)); |
| 72 | } |
| 73 | EXPECT_EQ(4u, CountTrailingZeros32(0xf0f0f0f0)); |
| 74 | } |
| 75 | |
| 76 | |
| 77 | TEST(Bits, CountTrailingZeros64) { |
| 78 | EXPECT_EQ(64u, CountTrailingZeros64(0)); |
| 79 | EXPECT_EQ(63u, CountTrailingZeros64(0x8000000000000000)); |
| 80 | TRACED_FORRANGE(uint32_t, shift, 0, 63) { |
| 81 | EXPECT_EQ(shift, CountTrailingZeros64(V8_UINT64_C(1) << shift)); |
| 82 | } |
| 83 | EXPECT_EQ(4u, CountTrailingZeros64(0xf0f0f0f0)); |
| 84 | EXPECT_EQ(36u, CountTrailingZeros64(0xf0f0f0f000000000)); |
| 85 | } |
| 86 | |
| 87 | |
| 88 | TEST(Bits, IsPowerOfTwo32) { |
| 89 | EXPECT_FALSE(IsPowerOfTwo32(0U)); |
| 90 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 91 | EXPECT_TRUE(IsPowerOfTwo32(1U << shift)); |
| 92 | EXPECT_FALSE(IsPowerOfTwo32((1U << shift) + 5U)); |
| 93 | EXPECT_FALSE(IsPowerOfTwo32(~(1U << shift))); |
| 94 | } |
| 95 | TRACED_FORRANGE(uint32_t, shift, 2, 31) { |
| 96 | EXPECT_FALSE(IsPowerOfTwo32((1U << shift) - 1U)); |
| 97 | } |
| 98 | EXPECT_FALSE(IsPowerOfTwo32(0xffffffff)); |
| 99 | } |
| 100 | |
| 101 | |
| 102 | TEST(Bits, IsPowerOfTwo64) { |
| 103 | EXPECT_FALSE(IsPowerOfTwo64(0U)); |
| 104 | TRACED_FORRANGE(uint32_t, shift, 0, 63) { |
| 105 | EXPECT_TRUE(IsPowerOfTwo64(V8_UINT64_C(1) << shift)); |
| 106 | EXPECT_FALSE(IsPowerOfTwo64((V8_UINT64_C(1) << shift) + 5U)); |
| 107 | EXPECT_FALSE(IsPowerOfTwo64(~(V8_UINT64_C(1) << shift))); |
| 108 | } |
| 109 | TRACED_FORRANGE(uint32_t, shift, 2, 63) { |
| 110 | EXPECT_FALSE(IsPowerOfTwo64((V8_UINT64_C(1) << shift) - 1U)); |
| 111 | } |
| 112 | EXPECT_FALSE(IsPowerOfTwo64(V8_UINT64_C(0xffffffffffffffff))); |
| 113 | } |
| 114 | |
| 115 | |
| 116 | TEST(Bits, RoundUpToPowerOfTwo32) { |
| 117 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 118 | EXPECT_EQ(1u << shift, RoundUpToPowerOfTwo32(1u << shift)); |
| 119 | } |
| 120 | EXPECT_EQ(0u, RoundUpToPowerOfTwo32(0)); |
| 121 | EXPECT_EQ(4u, RoundUpToPowerOfTwo32(3)); |
| 122 | EXPECT_EQ(0x80000000u, RoundUpToPowerOfTwo32(0x7fffffffu)); |
| 123 | } |
| 124 | |
| 125 | |
| 126 | TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo32)) { |
| 127 | ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo32(0x80000001u); }, |
| 128 | "0x80000000"); |
| 129 | } |
| 130 | |
| 131 | |
| 132 | TEST(Bits, RoundDownToPowerOfTwo32) { |
| 133 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 134 | EXPECT_EQ(1u << shift, RoundDownToPowerOfTwo32(1u << shift)); |
| 135 | } |
| 136 | EXPECT_EQ(0u, RoundDownToPowerOfTwo32(0)); |
| 137 | EXPECT_EQ(4u, RoundDownToPowerOfTwo32(5)); |
| 138 | EXPECT_EQ(0x80000000u, RoundDownToPowerOfTwo32(0x80000001u)); |
| 139 | } |
| 140 | |
| 141 | |
| 142 | TEST(Bits, RotateRight32) { |
| 143 | TRACED_FORRANGE(uint32_t, shift, 0, 31) { |
| 144 | EXPECT_EQ(0u, RotateRight32(0u, shift)); |
| 145 | } |
| 146 | EXPECT_EQ(1u, RotateRight32(1, 0)); |
| 147 | EXPECT_EQ(1u, RotateRight32(2, 1)); |
| 148 | EXPECT_EQ(0x80000000u, RotateRight32(1, 1)); |
| 149 | } |
| 150 | |
| 151 | |
| 152 | TEST(Bits, RotateRight64) { |
| 153 | TRACED_FORRANGE(uint64_t, shift, 0, 63) { |
| 154 | EXPECT_EQ(0u, RotateRight64(0u, shift)); |
| 155 | } |
| 156 | EXPECT_EQ(1u, RotateRight64(1, 0)); |
| 157 | EXPECT_EQ(1u, RotateRight64(2, 1)); |
| 158 | EXPECT_EQ(V8_UINT64_C(0x8000000000000000), RotateRight64(1, 1)); |
| 159 | } |
| 160 | |
| 161 | |
| 162 | TEST(Bits, SignedAddOverflow32) { |
| 163 | int32_t val = 0; |
| 164 | EXPECT_FALSE(SignedAddOverflow32(0, 0, &val)); |
| 165 | EXPECT_EQ(0, val); |
| 166 | EXPECT_TRUE( |
| 167 | SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 1, &val)); |
| 168 | EXPECT_EQ(std::numeric_limits<int32_t>::min(), val); |
| 169 | EXPECT_TRUE( |
| 170 | SignedAddOverflow32(std::numeric_limits<int32_t>::min(), -1, &val)); |
| 171 | EXPECT_EQ(std::numeric_limits<int32_t>::max(), val); |
| 172 | EXPECT_TRUE(SignedAddOverflow32(std::numeric_limits<int32_t>::max(), |
| 173 | std::numeric_limits<int32_t>::max(), &val)); |
| 174 | EXPECT_EQ(-2, val); |
| 175 | TRACED_FORRANGE(int32_t, i, 1, 50) { |
| 176 | TRACED_FORRANGE(int32_t, j, 1, i) { |
| 177 | EXPECT_FALSE(SignedAddOverflow32(i, j, &val)); |
| 178 | EXPECT_EQ(i + j, val); |
| 179 | } |
| 180 | } |
| 181 | } |
| 182 | |
| 183 | |
| 184 | TEST(Bits, SignedSubOverflow32) { |
| 185 | int32_t val = 0; |
| 186 | EXPECT_FALSE(SignedSubOverflow32(0, 0, &val)); |
| 187 | EXPECT_EQ(0, val); |
| 188 | EXPECT_TRUE( |
| 189 | SignedSubOverflow32(std::numeric_limits<int32_t>::min(), 1, &val)); |
| 190 | EXPECT_EQ(std::numeric_limits<int32_t>::max(), val); |
| 191 | EXPECT_TRUE( |
| 192 | SignedSubOverflow32(std::numeric_limits<int32_t>::max(), -1, &val)); |
| 193 | EXPECT_EQ(std::numeric_limits<int32_t>::min(), val); |
| 194 | TRACED_FORRANGE(int32_t, i, 1, 50) { |
| 195 | TRACED_FORRANGE(int32_t, j, 1, i) { |
| 196 | EXPECT_FALSE(SignedSubOverflow32(i, j, &val)); |
| 197 | EXPECT_EQ(i - j, val); |
| 198 | } |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | |
| 203 | TEST(Bits, SignedMulHigh32) { |
| 204 | EXPECT_EQ(0, SignedMulHigh32(0, 0)); |
| 205 | TRACED_FORRANGE(int32_t, i, 1, 50) { |
| 206 | TRACED_FORRANGE(int32_t, j, 1, i) { EXPECT_EQ(0, SignedMulHigh32(i, j)); } |
| 207 | } |
| 208 | EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::max(), |
| 209 | std::numeric_limits<int32_t>::min())); |
| 210 | EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::min(), |
| 211 | std::numeric_limits<int32_t>::max())); |
| 212 | EXPECT_EQ(1, SignedMulHigh32(1024 * 1024 * 1024, 4)); |
| 213 | EXPECT_EQ(2, SignedMulHigh32(8 * 1024, 1024 * 1024)); |
| 214 | } |
| 215 | |
| 216 | |
| 217 | TEST(Bits, SignedMulHighAndAdd32) { |
| 218 | TRACED_FORRANGE(int32_t, i, 1, 50) { |
| 219 | EXPECT_EQ(i, SignedMulHighAndAdd32(0, 0, i)); |
| 220 | TRACED_FORRANGE(int32_t, j, 1, i) { |
| 221 | EXPECT_EQ(i, SignedMulHighAndAdd32(j, j, i)); |
| 222 | } |
| 223 | EXPECT_EQ(i + 1, SignedMulHighAndAdd32(1024 * 1024 * 1024, 4, i)); |
| 224 | } |
| 225 | } |
| 226 | |
| 227 | |
| 228 | TEST(Bits, SignedDiv32) { |
| 229 | EXPECT_EQ(std::numeric_limits<int32_t>::min(), |
| 230 | SignedDiv32(std::numeric_limits<int32_t>::min(), -1)); |
| 231 | EXPECT_EQ(std::numeric_limits<int32_t>::max(), |
| 232 | SignedDiv32(std::numeric_limits<int32_t>::max(), 1)); |
| 233 | TRACED_FORRANGE(int32_t, i, 0, 50) { |
| 234 | EXPECT_EQ(0, SignedDiv32(i, 0)); |
| 235 | TRACED_FORRANGE(int32_t, j, 1, i) { |
| 236 | EXPECT_EQ(1, SignedDiv32(j, j)); |
| 237 | EXPECT_EQ(i / j, SignedDiv32(i, j)); |
| 238 | EXPECT_EQ(-i / j, SignedDiv32(i, -j)); |
| 239 | } |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | |
| 244 | TEST(Bits, SignedMod32) { |
| 245 | EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::min(), -1)); |
| 246 | EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::max(), 1)); |
| 247 | TRACED_FORRANGE(int32_t, i, 0, 50) { |
| 248 | EXPECT_EQ(0, SignedMod32(i, 0)); |
| 249 | TRACED_FORRANGE(int32_t, j, 1, i) { |
| 250 | EXPECT_EQ(0, SignedMod32(j, j)); |
| 251 | EXPECT_EQ(i % j, SignedMod32(i, j)); |
| 252 | EXPECT_EQ(i % j, SignedMod32(i, -j)); |
| 253 | } |
| 254 | } |
| 255 | } |
| 256 | |
| 257 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 258 | TEST(Bits, UnsignedAddOverflow32) { |
| 259 | uint32_t val = 0; |
| 260 | EXPECT_FALSE(UnsignedAddOverflow32(0, 0, &val)); |
| 261 | EXPECT_EQ(0u, val); |
| 262 | EXPECT_TRUE( |
| 263 | UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(), 1u, &val)); |
| 264 | EXPECT_EQ(std::numeric_limits<uint32_t>::min(), val); |
| 265 | EXPECT_TRUE(UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(), |
| 266 | std::numeric_limits<uint32_t>::max(), |
| 267 | &val)); |
| 268 | TRACED_FORRANGE(uint32_t, i, 1, 50) { |
| 269 | TRACED_FORRANGE(uint32_t, j, 1, i) { |
| 270 | EXPECT_FALSE(UnsignedAddOverflow32(i, j, &val)); |
| 271 | EXPECT_EQ(i + j, val); |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 277 | TEST(Bits, UnsignedDiv32) { |
| 278 | TRACED_FORRANGE(uint32_t, i, 0, 50) { |
| 279 | EXPECT_EQ(0u, UnsignedDiv32(i, 0)); |
| 280 | TRACED_FORRANGE(uint32_t, j, i + 1, 100) { |
| 281 | EXPECT_EQ(1u, UnsignedDiv32(j, j)); |
| 282 | EXPECT_EQ(i / j, UnsignedDiv32(i, j)); |
| 283 | } |
| 284 | } |
| 285 | } |
| 286 | |
| 287 | |
| 288 | TEST(Bits, UnsignedMod32) { |
| 289 | TRACED_FORRANGE(uint32_t, i, 0, 50) { |
| 290 | EXPECT_EQ(0u, UnsignedMod32(i, 0)); |
| 291 | TRACED_FORRANGE(uint32_t, j, i + 1, 100) { |
| 292 | EXPECT_EQ(0u, UnsignedMod32(j, j)); |
| 293 | EXPECT_EQ(i % j, UnsignedMod32(i, j)); |
| 294 | } |
| 295 | } |
| 296 | } |
| 297 | |
| 298 | } // namespace bits |
| 299 | } // namespace base |
| 300 | } // namespace v8 |