1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/base/internal/bits.h"
16
17 #include "gtest/gtest.h"
18
19 namespace {
20
CLZ64(uint64_t n)21 int CLZ64(uint64_t n) {
22 int fast = absl::base_internal::CountLeadingZeros64(n);
23 int slow = absl::base_internal::CountLeadingZeros64Slow(n);
24 EXPECT_EQ(fast, slow) << n;
25 return fast;
26 }
27
TEST(BitsTest,CountLeadingZeros64)28 TEST(BitsTest, CountLeadingZeros64) {
29 EXPECT_EQ(64, CLZ64(uint64_t{}));
30 EXPECT_EQ(0, CLZ64(~uint64_t{}));
31
32 for (int index = 0; index < 64; index++) {
33 uint64_t x = static_cast<uint64_t>(1) << index;
34 const auto cnt = 63 - index;
35 ASSERT_EQ(cnt, CLZ64(x)) << index;
36 ASSERT_EQ(cnt, CLZ64(x + x - 1)) << index;
37 }
38 }
39
CLZ32(uint32_t n)40 int CLZ32(uint32_t n) {
41 int fast = absl::base_internal::CountLeadingZeros32(n);
42 int slow = absl::base_internal::CountLeadingZeros32Slow(n);
43 EXPECT_EQ(fast, slow) << n;
44 return fast;
45 }
46
TEST(BitsTest,CountLeadingZeros32)47 TEST(BitsTest, CountLeadingZeros32) {
48 EXPECT_EQ(32, CLZ32(uint32_t{}));
49 EXPECT_EQ(0, CLZ32(~uint32_t{}));
50
51 for (int index = 0; index < 32; index++) {
52 uint32_t x = static_cast<uint32_t>(1) << index;
53 const auto cnt = 31 - index;
54 ASSERT_EQ(cnt, CLZ32(x)) << index;
55 ASSERT_EQ(cnt, CLZ32(x + x - 1)) << index;
56 ASSERT_EQ(CLZ64(x), CLZ32(x) + 32);
57 }
58 }
59
CTZ64(uint64_t n)60 int CTZ64(uint64_t n) {
61 int fast = absl::base_internal::CountTrailingZerosNonZero64(n);
62 int slow = absl::base_internal::CountTrailingZerosNonZero64Slow(n);
63 EXPECT_EQ(fast, slow) << n;
64 return fast;
65 }
66
TEST(BitsTest,CountTrailingZerosNonZero64)67 TEST(BitsTest, CountTrailingZerosNonZero64) {
68 EXPECT_EQ(0, CTZ64(~uint64_t{}));
69
70 for (int index = 0; index < 64; index++) {
71 uint64_t x = static_cast<uint64_t>(1) << index;
72 const auto cnt = index;
73 ASSERT_EQ(cnt, CTZ64(x)) << index;
74 ASSERT_EQ(cnt, CTZ64(~(x - 1))) << index;
75 }
76 }
77
CTZ32(uint32_t n)78 int CTZ32(uint32_t n) {
79 int fast = absl::base_internal::CountTrailingZerosNonZero32(n);
80 int slow = absl::base_internal::CountTrailingZerosNonZero32Slow(n);
81 EXPECT_EQ(fast, slow) << n;
82 return fast;
83 }
84
TEST(BitsTest,CountTrailingZerosNonZero32)85 TEST(BitsTest, CountTrailingZerosNonZero32) {
86 EXPECT_EQ(0, CTZ32(~uint32_t{}));
87
88 for (int index = 0; index < 32; index++) {
89 uint32_t x = static_cast<uint32_t>(1) << index;
90 const auto cnt = index;
91 ASSERT_EQ(cnt, CTZ32(x)) << index;
92 ASSERT_EQ(cnt, CTZ32(~(x - 1))) << index;
93 }
94 }
95
96
97 } // namespace
98