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
26extern "C" uint64_t check_select64_default(uint64_t x, uint64_t k) {
27 return folly::select64<folly::compression::instructions::Default>(x, k);
28}
29extern "C" uint64_t check_select64_haswell(uint64_t x, uint64_t k) {
30 return folly::select64<folly::compression::instructions::Haswell>(x, k);
31}
32
33class Select64Test : public testing::Test {};
34
35using TestArch = folly::compression::instructions::Default;
36
37TEST_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
48TEST_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