1 /*
2 * Copyright 2021 Google LLC
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 #include "bits_util.h"
17
18 #include <gtest/gtest.h>
19
20 #include <limits>
21
22 namespace dist_proc {
23 namespace aggregation {
24 namespace internal {
25
26 namespace {
27
28 class BitsUtilTest : public ::testing::Test {};
29
TEST_F(BitsUtilTest,Log2EdgeCases)30 TEST_F(BitsUtilTest, Log2EdgeCases) {
31 for (uint8_t i = 0; i < 64; i++) {
32 uint64_t n = 1ULL << i;
33 EXPECT_EQ(i, BitsUtil::Log2FloorNonZero64(n));
34 if (n > 2) {
35 EXPECT_EQ(i - 1, BitsUtil::Log2FloorNonZero64(n - 1));
36 EXPECT_EQ(i, BitsUtil::Log2FloorNonZero64(n + 1));
37 }
38 }
39 }
40
41 struct BitsUtilTupleParam {
42 uint64_t input;
43 uint8_t result;
44 };
45
46 class BitsUtilTupleTest : public ::testing::TestWithParam<BitsUtilTupleParam> {};
47
TEST_P(BitsUtilTupleTest,CorrectResult)48 TEST_P(BitsUtilTupleTest, CorrectResult) {
49 BitsUtilTupleParam params = GetParam();
50 EXPECT_EQ(BitsUtil::Log2FloorNonZero64(params.input), params.result);
51 }
52
53 const BitsUtilTupleParam cases[]{{0x1LL, 0},
54 {0x2LL, 1},
55 {0x4LL, 2},
56 {0x5LL, 2},
57 {0x7LL, 2},
58 {0x9LL, 3},
59 {0x10LL, 4},
60 {0x20LL, 5},
61 {0x40LL, 6},
62 {0x80LL, 7},
63 {0x100LL, 8},
64 {0x200LL, 9},
65 {0x402LL, 10},
66 {0x800LL, 11},
67 {0x10b0LL, 12},
68 {0x200aLL, 13},
69 {0x4000LL, 14},
70 {0x8000LL, 15},
71 {0x10002LL, 16},
72 {0x8004000LL, 27},
73 {0x10002000LL, 28},
74 {0x40000020LL, 30},
75 {0x100000002LL, 32},
76 {0x100000002LL, 32},
77 {0x800020800LL, 35},
78 {0x1040000020LL, 36},
79 {0x2000000000LL, 37},
80 {0x4000000000LL, 38},
81 {0x8000000000LL, 39},
82 {0xb000000404LL, 39},
83 {0x8000000000LL, 39},
84 {0x10000000000LL, 40},
85 {0x20008004000LL, 41},
86 {0x80000010000LL, 43},
87 {0x200000000004LL, 45},
88 {0x400000000000LL, 46},
89 {0x408000000000LL, 46},
90 {0x2000000000422LL, 49},
91 {0x108840000801c4LL, 52},
92 {0x4000b800200604LL, 54},
93 {0x44020118004900LL, 54},
94 {0xc4020118004900LL, 55},
95 {0x101964002152400LL, 56},
96 {0x100004000000000LL, 56},
97 {0x298281040000020LL, 57},
98 {0x404014310000044LL, 58},
99 {0x586000401200423LL, 58},
100 {0x800002000000000LL, 59},
101 {0x800620001000000LL, 59},
102 {0x1000408000000000LL, 60},
103 {0x27908a643028d1e5LL, 61},
104 {0x2404014310000044LL, 61},
105 {0x2008000000200021LL, 61},
106 {0x6008000000200021LL, 62},
107 {0x40c4020118004900LL, 62},
108 {0x67908a643028d1e5LL, 62},
109 {0xc52df86bf16be929LL, 63},
110 {0xefffefefffffffffLL, 63},
111 {0x80fa6201c594b6a9LL, 63},
112 {0xefebdfff7fafffdfLL, 63}};
113
114 INSTANTIATE_TEST_SUITE_P(BitsUtilTestCases, BitsUtilTupleTest, ::testing::ValuesIn(cases));
115
116 } // namespace
117
118 } // namespace internal
119 } // namespace aggregation
120 } // namespace dist_proc
121