1 | /* |
2 | * Copyright 2018-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 <folly/experimental/Select64.h> |
18 | |
19 | #include <cstddef> |
20 | #include <cstdint> |
21 | |
22 | #include <folly/experimental/Instructions.h> |
23 | #include <folly/portability/GTest.h> |
24 | |
25 | // for disassembling |
26 | extern "C" uint64_t check_select64_default(uint64_t x, uint64_t k) { |
27 | return folly::select64<folly::compression::instructions::Default>(x, k); |
28 | } |
29 | extern "C" uint64_t check_select64_haswell(uint64_t x, uint64_t k) { |
30 | return folly::select64<folly::compression::instructions::Haswell>(x, k); |
31 | } |
32 | |
33 | class Select64Test : public testing::Test {}; |
34 | |
35 | using TestArch = folly::compression::instructions::Default; |
36 | |
37 | TEST_F(Select64Test, SelectInByteTable) { |
38 | for (size_t i = 0u; i < 256u; ++i) { |
39 | uint8_t decoded = 0; |
40 | for (size_t j = 0u; j < 8u; ++j) { |
41 | auto const entry = folly::detail::kSelectInByte[j][i]; |
42 | decoded |= uint8_t(entry != 8) << entry; |
43 | } |
44 | EXPECT_EQ(i, decoded); |
45 | } |
46 | } |
47 | |
48 | TEST_F(Select64Test, Select64) { |
49 | using instr = TestArch; |
50 | constexpr uint64_t kPrime = uint64_t(-59); |
51 | for (uint64_t x = kPrime, i = 0; i < (1 << 20); x *= kPrime, i += 1) { |
52 | auto const w = instr::popcount(x); |
53 | for (size_t k = 0; k < w; ++k) { |
54 | auto const pos = folly::select64<instr>(x, k); |
55 | CHECK_EQ((x >> pos) & 1, 1); |
56 | CHECK_EQ(instr::popcount(x & ((uint64_t(1) << pos) - 1)), k); |
57 | } |
58 | } |
59 | } |
60 | |