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 
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 
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