1/*
2 * Copyright 2012-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#include <cmath>
18
19#include <folly/experimental/Bits.h>
20
21#include <glog/logging.h>
22
23#include <folly/portability/GTest.h>
24
25using namespace folly;
26
27template <class T>
28void runSimpleTest8() {
29 auto load = detail::BitsTraits<T>::load;
30
31 EXPECT_EQ(0, Bits<T>::blockCount(0));
32 EXPECT_EQ(1, Bits<T>::blockCount(1));
33 EXPECT_EQ(1, Bits<T>::blockCount(8));
34 EXPECT_EQ(2, Bits<T>::blockCount(9));
35 EXPECT_EQ(256, Bits<T>::blockCount(2048));
36 EXPECT_EQ(257, Bits<T>::blockCount(2049));
37
38 EXPECT_EQ(4, Bits<T>::blockIndex(39));
39 EXPECT_EQ(7, Bits<T>::bitOffset(39));
40 EXPECT_EQ(5, Bits<T>::blockIndex(40));
41 EXPECT_EQ(0, Bits<T>::bitOffset(40));
42
43 T buf[256];
44 std::fill(buf, buf + 256, T(0));
45
46 Bits<T>::set(buf, 36);
47 Bits<T>::set(buf, 39);
48 EXPECT_EQ((1 << 7) | (1 << 4), load(buf[4]));
49 EXPECT_EQ(0, load(buf[5]));
50 Bits<T>::clear(buf, 39);
51 EXPECT_EQ(1 << 4, load(buf[4]));
52 EXPECT_EQ(0, load(buf[5]));
53 Bits<T>::set(buf, 40);
54 EXPECT_EQ(1 << 4, load(buf[4]));
55 EXPECT_EQ(1, load(buf[5]));
56
57 EXPECT_EQ(2, Bits<T>::count(buf, buf + 256));
58}
59
60TEST(Bits, Simple8) {
61 runSimpleTest8<uint8_t>();
62}
63
64TEST(Bits, SimpleUnaligned8) {
65 runSimpleTest8<Unaligned<uint8_t>>();
66}
67
68template <class T>
69void runSimpleTest64() {
70 auto load = detail::BitsTraits<T>::load;
71
72 EXPECT_EQ(0, Bits<T>::blockCount(0));
73 EXPECT_EQ(1, Bits<T>::blockCount(1));
74 EXPECT_EQ(1, Bits<T>::blockCount(8));
75 EXPECT_EQ(1, Bits<T>::blockCount(9));
76 EXPECT_EQ(1, Bits<T>::blockCount(64));
77 EXPECT_EQ(2, Bits<T>::blockCount(65));
78 EXPECT_EQ(32, Bits<T>::blockCount(2048));
79 EXPECT_EQ(33, Bits<T>::blockCount(2049));
80
81 EXPECT_EQ(0, Bits<T>::blockIndex(39));
82 EXPECT_EQ(39, Bits<T>::bitOffset(39));
83 EXPECT_EQ(4, Bits<T>::blockIndex(319));
84 EXPECT_EQ(63, Bits<T>::bitOffset(319));
85 EXPECT_EQ(5, Bits<T>::blockIndex(320));
86 EXPECT_EQ(0, Bits<T>::bitOffset(320));
87
88 T buf[256];
89 std::fill(buf, buf + 256, T(0));
90
91 Bits<T>::set(buf, 300);
92 Bits<T>::set(buf, 319);
93 EXPECT_EQ((uint64_t(1) << 44) | (uint64_t(1) << 63), load(buf[4]));
94 EXPECT_EQ(0, load(buf[5]));
95 Bits<T>::clear(buf, 319);
96 EXPECT_EQ(uint64_t(1) << 44, load(buf[4]));
97 EXPECT_EQ(0, load(buf[5]));
98 Bits<T>::set(buf, 320);
99 EXPECT_EQ(uint64_t(1) << 44, load(buf[4]));
100 EXPECT_EQ(1, load(buf[5]));
101
102 EXPECT_EQ(2, Bits<T>::count(buf, buf + 256));
103}
104
105TEST(Bits, Simple64) {
106 runSimpleTest64<uint64_t>();
107}
108
109TEST(Bits, SimpleUnaligned64) {
110 runSimpleTest64<Unaligned<uint64_t>>();
111}
112
113template <class T>
114void runMultiBitTest8() {
115 auto load = detail::BitsTraits<T>::load;
116 T buf[] = {0x12, 0x34, 0x56, 0x78};
117
118 EXPECT_EQ(0x02, load(Bits<T>::get(buf, 0, 4)));
119 EXPECT_EQ(0x1a, load(Bits<T>::get(buf, 9, 5)));
120 EXPECT_EQ(0xb1, load(Bits<T>::get(buf, 13, 8)));
121
122 Bits<T>::set(buf, 0, 4, 0x0b);
123 EXPECT_EQ(0x1b, load(buf[0]));
124 EXPECT_EQ(0x34, load(buf[1]));
125 EXPECT_EQ(0x56, load(buf[2]));
126 EXPECT_EQ(0x78, load(buf[3]));
127
128 Bits<T>::set(buf, 9, 5, 0x0e);
129 EXPECT_EQ(0x1b, load(buf[0]));
130 EXPECT_EQ(0x1c, load(buf[1]));
131 EXPECT_EQ(0x56, load(buf[2]));
132 EXPECT_EQ(0x78, load(buf[3]));
133
134 Bits<T>::set(buf, 13, 8, 0xaa);
135 EXPECT_EQ(0x1b, load(buf[0]));
136 EXPECT_EQ(0x5c, load(buf[1]));
137 EXPECT_EQ(0x55, load(buf[2]));
138 EXPECT_EQ(0x78, load(buf[3]));
139}
140
141TEST(Bits, MultiBit8) {
142 runMultiBitTest8<uint8_t>();
143}
144
145TEST(Bits, MultiBitUnaligned8) {
146 runMultiBitTest8<Unaligned<uint8_t>>();
147}
148
149template <class T>
150void runSignedMultiBitTest8() {
151 auto load = detail::BitsTraits<T>::load;
152 T buf[] = {0x12, 0x34, 0x56, 0x78};
153
154 EXPECT_EQ(0x02, load(Bits<T>::get(buf, 0, 4)));
155 EXPECT_EQ(0x1a - 32, load(Bits<T>::get(buf, 9, 5)));
156 EXPECT_EQ(0xb1 - 256, load(Bits<T>::get(buf, 13, 8)));
157
158 Bits<T>::set(buf, 0, 4, 0x0b - 0x10);
159 EXPECT_EQ(0x1b, load(buf[0]));
160 EXPECT_EQ(0x34, load(buf[1]));
161 EXPECT_EQ(0x56, load(buf[2]));
162 EXPECT_EQ(0x78, load(buf[3]));
163
164 Bits<T>::set(buf, 9, 5, 0x0e);
165 EXPECT_EQ(0x1b, load(buf[0]));
166 EXPECT_EQ(0x1c, load(buf[1]));
167 EXPECT_EQ(0x56, load(buf[2]));
168 EXPECT_EQ(0x78, load(buf[3]));
169
170 Bits<T>::set(buf, 13, 8, 0xaa - 0x100);
171 EXPECT_EQ(0x1b, load(buf[0]));
172 EXPECT_EQ(0x5c, load(buf[1]));
173 EXPECT_EQ(0x55, load(buf[2]));
174 EXPECT_EQ(0x78, load(buf[3]));
175}
176
177TEST(Bits, SignedMultiBit8) {
178 runSignedMultiBitTest8<int8_t>();
179}
180
181template <class T, class R = T>
182void runMultiBitTest64() {
183 auto load = detail::BitsTraits<T>::load;
184 T buf[] = {0x123456789abcdef0, 0x13579bdf2468ace0};
185
186 EXPECT_EQ(0x123456789abcdef0, load(Bits<T>::get(buf, 0, 64)));
187 EXPECT_EQ(0xf0, load(Bits<T>::get(buf, 0, 8)));
188 EXPECT_EQ(0x89abcdef, load(Bits<T>::get(buf, 4, 32)));
189 EXPECT_EQ(0x189abcdef, load(Bits<T>::get(buf, 4, 33)));
190
191 Bits<T>::set(buf, 4, 31, 0x55555555);
192 EXPECT_EQ(0xd5555555, load(Bits<T>::get(buf, 4, 32)));
193 EXPECT_EQ(0x1d5555555, load(Bits<T>::get(buf, 4, 33)));
194 EXPECT_EQ(0xd55555550, load(Bits<T>::get(buf, 0, 36)));
195
196 Bits<T>::set(buf, 0, 64, 0x23456789abcdef01);
197 EXPECT_EQ(0x23456789abcdef01, load(Bits<T>::get(buf, 0, 64)));
198}
199
200TEST(Bits, MultiBit64) {
201 runMultiBitTest64<uint64_t>();
202}
203
204TEST(Bits, MultiBitSigned64) {
205 // runMultiBitTest64<int64_t>();
206}
207
208TEST(Bits, MultiBitUnaligned64) {
209 runMultiBitTest64<Unaligned<uint64_t>, uint64_t>();
210}
211
212namespace {
213template <bool aligned, class T>
214typename std::enable_if<!aligned>::type
215testSet(uint8_t* buf, size_t start, size_t bits, T value) {
216 Bits<Unaligned<T>>::set(
217 reinterpret_cast<Unaligned<T>*>(buf), start, bits, value);
218}
219
220template <bool aligned, class T>
221typename std::enable_if<aligned>::type
222testSet(uint8_t* buf, size_t start, size_t bits, T value) {
223 Bits<T>::set(reinterpret_cast<T*>(buf), start, bits, value);
224}
225
226template <bool aligned, class T>
227typename std::enable_if<!aligned, T>::type
228testGet(uint8_t* buf, size_t start, size_t bits) {
229 return Bits<Unaligned<T>>::get(
230 reinterpret_cast<Unaligned<T>*>(buf), start, bits);
231}
232
233template <bool aligned, class T>
234typename std::enable_if<aligned, T>::type
235testGet(uint8_t* buf, size_t start, size_t bits) {
236 return Bits<T>::get(reinterpret_cast<T*>(buf), start, bits);
237}
238
239template <class T, bool negate = false>
240T testValue(int bits) {
241 if (std::is_signed<T>::value) {
242 --bits;
243 }
244 auto value = std::pow(2, bits) * (negate ? -2.0 : 2.0) / 3.0;
245 CHECK_GE(value, std::numeric_limits<T>::min());
246 CHECK_LE(value, std::numeric_limits<T>::max());
247 return static_cast<T>(value);
248}
249} // namespace
250
251TEST(Bits, Boundaries) {
252 uint8_t buf[20];
253 for (size_t offset = 0; offset <= 64; ++offset) {
254 for (size_t size = 0; size <= 32; ++size) {
255 int32_t value = testValue<int32_t>(size);
256 testSet<true>(buf, offset, size, value);
257 EXPECT_EQ(value, (testGet<true, int32_t>(buf, offset, size)));
258 }
259 }
260}
261
262template <size_t N>
263void accSize(size_t& w) {
264 for (size_t s = 0; s <= N; ++s) {
265 w += s;
266 }
267}
268
269template <size_t N, typename T, bool NEG, bool aligned>
270void testSetLoop(size_t& w, size_t bufSize, uint8_t* buf) {
271 for (size_t s = 0; s <= N; ++s) {
272 CHECK_LE(s + w, 8 * bufSize) << s << ' ' << w << ' ' << bufSize;
273 testSet<aligned>(buf, w, s, testValue<T, NEG>(s));
274 EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, w, s))) << s;
275 w += s;
276 }
277}
278
279template <size_t N, typename T, bool NEG, bool aligned>
280void testGetLoop(size_t& r, size_t bufSize, uint8_t* buf) {
281 for (size_t s = 0; s <= N; ++s) {
282 CHECK_LE(s + r, 8 * bufSize);
283 EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, r, s))) << s;
284 r += s;
285 }
286}
287
288template <bool aligned>
289void testConcatenation() {
290 // concatenate fields of length 1, 2, 3, ... 64, all unsigned, storing 2/3s
291 // the maximum value in each.
292
293 // calculate how much buffer size we need
294 size_t bufSize = 0;
295 {
296 size_t w = 0;
297 // Unsigned
298 accSize<8>(w);
299 accSize<16>(w);
300 accSize<32>(w);
301 accSize<64>(w);
302
303 // Signed NEG=false
304 accSize<7>(w);
305 accSize<15>(w);
306 accSize<31>(w);
307 accSize<63>(w);
308
309 // Signed NEG=true
310 accSize<7>(w);
311 accSize<15>(w);
312 accSize<31>(w);
313 accSize<63>(w);
314
315 bufSize = w;
316 }
317 // bits->bytes, rounding up
318 bufSize = (bufSize + 7) / 8;
319 // round up to next multiple of 8
320 bufSize = (bufSize + 7) / 8 * 8;
321 std::vector<uint8_t> buffer(bufSize);
322 uint8_t* buf = buffer.data();
323 {
324 size_t w = 0;
325 // Unsigned
326 testSetLoop<8, uint8_t, false, aligned>(w, bufSize, buf);
327 testSetLoop<16, uint16_t, false, aligned>(w, bufSize, buf);
328 testSetLoop<32, uint32_t, false, aligned>(w, bufSize, buf);
329 testSetLoop<64, uint64_t, false, aligned>(w, bufSize, buf);
330
331 // Signed NEG=false
332 testSetLoop<7, int8_t, false, aligned>(w, bufSize, buf);
333 testSetLoop<15, int16_t, false, aligned>(w, bufSize, buf);
334 testSetLoop<31, int32_t, false, aligned>(w, bufSize, buf);
335 testSetLoop<63, int64_t, false, aligned>(w, bufSize, buf);
336
337 // Signed NEG=true
338 testSetLoop<7, int8_t, true, aligned>(w, bufSize, buf);
339 testSetLoop<15, int16_t, true, aligned>(w, bufSize, buf);
340 testSetLoop<31, int32_t, true, aligned>(w, bufSize, buf);
341 testSetLoop<63, int64_t, true, aligned>(w, bufSize, buf);
342 }
343
344 {
345 size_t r = 0;
346 // Unsigned
347 testGetLoop<8, uint8_t, false, aligned>(r, bufSize, buf);
348 testGetLoop<16, uint16_t, false, aligned>(r, bufSize, buf);
349 testGetLoop<32, uint32_t, false, aligned>(r, bufSize, buf);
350 testGetLoop<64, uint64_t, false, aligned>(r, bufSize, buf);
351
352 // Signed NEG=false
353 testGetLoop<7, int8_t, false, aligned>(r, bufSize, buf);
354 testGetLoop<15, int16_t, false, aligned>(r, bufSize, buf);
355 testGetLoop<31, int32_t, false, aligned>(r, bufSize, buf);
356 testGetLoop<63, int64_t, false, aligned>(r, bufSize, buf);
357
358 // Signed NEG=true
359 testGetLoop<7, int8_t, true, aligned>(r, bufSize, buf);
360 testGetLoop<15, int16_t, true, aligned>(r, bufSize, buf);
361 testGetLoop<31, int32_t, true, aligned>(r, bufSize, buf);
362 testGetLoop<63, int64_t, true, aligned>(r, bufSize, buf);
363 }
364}
365
366TEST(Bits, ConcatenationUnalignedUnsigned) {
367 testConcatenation<false>();
368}
369
370TEST(Bits, ConcatenationAligned) {
371 testConcatenation<true>();
372}
373
374int main(int argc, char* argv[]) {
375 testing::InitGoogleTest(&argc, argv);
376 gflags::ParseCommandLineFlags(&argc, &argv, true);
377 return RUN_ALL_TESTS();
378}
379