1 | /* |
2 | * Copyright 2011-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | // @author Tudor Bosman (tudorb@fb.com) |
18 | |
19 | #include <algorithm> |
20 | #include <random> |
21 | #include <vector> |
22 | |
23 | #include <folly/Random.h> |
24 | #include <folly/lang/Bits.h> |
25 | |
26 | #include <folly/portability/GTest.h> |
27 | |
28 | using namespace folly; |
29 | |
30 | // Test constexpr-ness. |
31 | #if !defined(__clang__) && !defined(_MSC_VER) |
32 | static_assert(findFirstSet(2u) == 2, "findFirstSet" ); |
33 | static_assert(findLastSet(2u) == 2, "findLastSet" ); |
34 | static_assert(nextPowTwo(2u) == 2, "nextPowTwo" ); |
35 | #endif |
36 | |
37 | #ifndef __clang__ |
38 | static_assert(isPowTwo(2u), "isPowTwo" ); |
39 | #endif |
40 | |
41 | namespace { |
42 | |
43 | template <class INT> |
44 | void testFFS() { |
45 | EXPECT_EQ(0, findFirstSet(static_cast<INT>(0))); |
46 | size_t bits = |
47 | std::numeric_limits<typename std::make_unsigned<INT>::type>::digits; |
48 | for (size_t i = 0; i < bits; i++) { |
49 | INT v = (static_cast<INT>(1) << (bits - 1)) | (static_cast<INT>(1) << i); |
50 | EXPECT_EQ(i + 1, findFirstSet(v)); |
51 | } |
52 | } |
53 | |
54 | template <class INT> |
55 | void testFLS() { |
56 | typedef typename std::make_unsigned<INT>::type UINT_T; |
57 | EXPECT_EQ(0, findLastSet(static_cast<INT>(0))); |
58 | size_t bits = std::numeric_limits<UINT_T>::digits; |
59 | for (size_t i = 0; i < bits; i++) { |
60 | INT v1 = static_cast<UINT_T>(1) << i; |
61 | EXPECT_EQ(i + 1, findLastSet(v1)); |
62 | |
63 | INT v2 = (static_cast<UINT_T>(1) << i) - 1; |
64 | EXPECT_EQ(i, findLastSet(v2)); |
65 | } |
66 | } |
67 | |
68 | } // namespace |
69 | |
70 | TEST(Bits, FindFirstSet) { |
71 | testFFS<char>(); |
72 | testFFS<signed char>(); |
73 | testFFS<unsigned char>(); |
74 | testFFS<short>(); |
75 | testFFS<unsigned short>(); |
76 | testFFS<int>(); |
77 | testFFS<unsigned int>(); |
78 | testFFS<long>(); |
79 | testFFS<unsigned long>(); |
80 | testFFS<long long>(); |
81 | testFFS<unsigned long long>(); |
82 | } |
83 | |
84 | TEST(Bits, FindLastSet) { |
85 | testFLS<char>(); |
86 | testFLS<signed char>(); |
87 | testFLS<unsigned char>(); |
88 | testFLS<short>(); |
89 | testFLS<unsigned short>(); |
90 | testFLS<int>(); |
91 | testFLS<unsigned int>(); |
92 | testFLS<long>(); |
93 | testFLS<unsigned long>(); |
94 | testFLS<long long>(); |
95 | testFLS<unsigned long long>(); |
96 | } |
97 | |
98 | TEST(Bits, nextPowTwoClz) { |
99 | EXPECT_EQ(1, nextPowTwo(0u)); |
100 | EXPECT_EQ(1, nextPowTwo(1u)); |
101 | EXPECT_EQ(2, nextPowTwo(2u)); |
102 | EXPECT_EQ(4, nextPowTwo(3u)); |
103 | EXPECT_EQ(4, nextPowTwo(4u)); |
104 | EXPECT_EQ(8, nextPowTwo(5u)); |
105 | EXPECT_EQ(8, nextPowTwo(6u)); |
106 | EXPECT_EQ(8, nextPowTwo(7u)); |
107 | EXPECT_EQ(8, nextPowTwo(8u)); |
108 | EXPECT_EQ(16, nextPowTwo(9u)); |
109 | EXPECT_EQ(16, nextPowTwo(13u)); |
110 | EXPECT_EQ(16, nextPowTwo(16u)); |
111 | EXPECT_EQ(512, nextPowTwo(510u)); |
112 | EXPECT_EQ(512, nextPowTwo(511u)); |
113 | EXPECT_EQ(512, nextPowTwo(512u)); |
114 | EXPECT_EQ(1024, nextPowTwo(513u)); |
115 | EXPECT_EQ(1024, nextPowTwo(777u)); |
116 | EXPECT_EQ(1ul << 31, nextPowTwo((1ul << 31) - 1)); |
117 | EXPECT_EQ(1ull << 32, nextPowTwo((1ull << 32) - 1)); |
118 | EXPECT_EQ(1ull << 63, nextPowTwo((1ull << 62) + 1)); |
119 | } |
120 | |
121 | TEST(Bits, prevPowTwoClz) { |
122 | EXPECT_EQ(0, prevPowTwo(0u)); |
123 | EXPECT_EQ(1, prevPowTwo(1u)); |
124 | EXPECT_EQ(2, prevPowTwo(2u)); |
125 | EXPECT_EQ(2, prevPowTwo(3u)); |
126 | EXPECT_EQ(4, prevPowTwo(4u)); |
127 | EXPECT_EQ(4, prevPowTwo(5u)); |
128 | EXPECT_EQ(4, prevPowTwo(6u)); |
129 | EXPECT_EQ(4, prevPowTwo(7u)); |
130 | EXPECT_EQ(8, prevPowTwo(8u)); |
131 | EXPECT_EQ(8, prevPowTwo(9u)); |
132 | EXPECT_EQ(8, prevPowTwo(13u)); |
133 | EXPECT_EQ(16, prevPowTwo(16u)); |
134 | EXPECT_EQ(256, prevPowTwo(510u)); |
135 | EXPECT_EQ(256, prevPowTwo(511u)); |
136 | EXPECT_EQ(512, prevPowTwo(512u)); |
137 | EXPECT_EQ(512, prevPowTwo(513u)); |
138 | EXPECT_EQ(512, prevPowTwo(777u)); |
139 | EXPECT_EQ(1ul << 30, prevPowTwo((1ul << 31) - 1)); |
140 | EXPECT_EQ(1ull << 31, prevPowTwo((1ull << 32) - 1)); |
141 | EXPECT_EQ(1ull << 62, prevPowTwo((1ull << 62) + 1)); |
142 | } |
143 | |
144 | TEST(Bits, isPowTwo) { |
145 | EXPECT_FALSE(isPowTwo(0u)); |
146 | EXPECT_TRUE(isPowTwo(1ul)); |
147 | EXPECT_TRUE(isPowTwo(2ull)); |
148 | EXPECT_FALSE(isPowTwo(3ul)); |
149 | EXPECT_TRUE(isPowTwo(4ul)); |
150 | EXPECT_FALSE(isPowTwo(5ul)); |
151 | EXPECT_TRUE(isPowTwo(8ul)); |
152 | EXPECT_FALSE(isPowTwo(15u)); |
153 | EXPECT_TRUE(isPowTwo(16u)); |
154 | EXPECT_FALSE(isPowTwo(17u)); |
155 | EXPECT_FALSE(isPowTwo(511ul)); |
156 | EXPECT_TRUE(isPowTwo(512ul)); |
157 | EXPECT_FALSE(isPowTwo(513ul)); |
158 | EXPECT_FALSE(isPowTwo((1ul << 31) - 1)); |
159 | EXPECT_TRUE(isPowTwo(1ul << 31)); |
160 | EXPECT_FALSE(isPowTwo((1ul << 31) + 1)); |
161 | EXPECT_FALSE(isPowTwo((1ull << 63) - 1)); |
162 | EXPECT_TRUE(isPowTwo(1ull << 63)); |
163 | EXPECT_FALSE(isPowTwo((1ull << 63) + 1)); |
164 | } |
165 | |
166 | TEST(Bits, popcount) { |
167 | EXPECT_EQ(0, popcount(0U)); |
168 | EXPECT_EQ(1, popcount(1U)); |
169 | EXPECT_EQ(32, popcount(uint32_t(-1))); |
170 | EXPECT_EQ(64, popcount(uint64_t(-1))); |
171 | } |
172 | |
173 | TEST(Bits, Endian_swap_uint) { |
174 | EXPECT_EQ(uint8_t(0xda), Endian::swap(uint8_t(0xda))); |
175 | EXPECT_EQ(uint16_t(0x4175), Endian::swap(uint16_t(0x7541))); |
176 | EXPECT_EQ(uint32_t(0x42efb918), Endian::swap(uint32_t(0x18b9ef42))); |
177 | EXPECT_EQ( |
178 | uint64_t(0xa244f5e862c71d8a), Endian::swap(uint64_t(0x8a1dc762e8f544a2))); |
179 | } |
180 | |
181 | TEST(Bits, Endian_swap_real) { |
182 | std::mt19937_64 rng; |
183 | auto f = std::uniform_real_distribution<float>()(rng); |
184 | EXPECT_NE(f, Endian::swap(f)); |
185 | EXPECT_EQ(f, Endian::swap(Endian::swap(f))); |
186 | auto d = std::uniform_real_distribution<double>()(rng); |
187 | EXPECT_NE(d, Endian::swap(d)); |
188 | EXPECT_EQ(d, Endian::swap(Endian::swap(d))); |
189 | } |
190 | |
191 | uint64_t reverse_simple(uint64_t v) { |
192 | uint64_t r = 0; |
193 | |
194 | for (int i = 0; i < 64; i++) { |
195 | r <<= 1; |
196 | r |= v & 1; |
197 | v >>= 1; |
198 | } |
199 | return r; |
200 | } |
201 | |
202 | TEST(Bits, BitReverse) { |
203 | EXPECT_EQ(folly::bitReverse<uint8_t>(0), 0); |
204 | EXPECT_EQ(folly::bitReverse<uint8_t>(1), 128); |
205 | for (int i = 0; i < 100; i++) { |
206 | uint64_t v = folly::Random::rand64(); |
207 | EXPECT_EQ(folly::bitReverse(v), reverse_simple(v)); |
208 | uint32_t b = folly::Random::rand32(); |
209 | EXPECT_EQ(folly::bitReverse(b), reverse_simple(b) >> 32); |
210 | } |
211 | } |
212 | |
213 | TEST(Bits, PartialLoadUnaligned) { |
214 | std::vector<char> buf(128); |
215 | std::generate( |
216 | buf.begin(), buf.end(), [] { return folly::Random::rand32(255); }); |
217 | for (size_t l = 0; l < 8; ++l) { |
218 | for (size_t pos = 0; pos <= buf.size() - l; ++pos) { |
219 | auto p = buf.data() + pos; |
220 | auto x = folly::partialLoadUnaligned<uint64_t>(p, l); |
221 | |
222 | uint64_t expected = 0; |
223 | memcpy(&expected, p, l); |
224 | |
225 | EXPECT_EQ(x, expected); |
226 | |
227 | if (l < 4) { |
228 | auto x32 = folly::partialLoadUnaligned<uint32_t>(p, l); |
229 | EXPECT_EQ(x32, static_cast<uint32_t>(expected)); |
230 | } |
231 | } |
232 | } |
233 | } |
234 | |