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