1 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 // This file contains the unit tests for the bit utilities.
8 #include "build/build_config.h"
14 #include "testing/gtest/include/gtest/gtest.h"
19 TEST(BitsTest, Log2Floor) {
20 EXPECT_EQ(-1, Log2Floor(0));
21 EXPECT_EQ(0, Log2Floor(1));
22 EXPECT_EQ(1, Log2Floor(2));
23 EXPECT_EQ(1, Log2Floor(3));
24 EXPECT_EQ(2, Log2Floor(4));
25 for (int i = 3; i < 31; ++i) {
26 unsigned int value = 1U << i;
27 EXPECT_EQ(i, Log2Floor(value));
28 EXPECT_EQ(i, Log2Floor(value + 1));
29 EXPECT_EQ(i, Log2Floor(value + 2));
30 EXPECT_EQ(i - 1, Log2Floor(value - 1));
31 EXPECT_EQ(i - 1, Log2Floor(value - 2));
33 EXPECT_EQ(31, Log2Floor(0xffffffffU));
36 TEST(BitsTest, Log2Ceiling) {
37 EXPECT_EQ(-1, Log2Ceiling(0));
38 EXPECT_EQ(0, Log2Ceiling(1));
39 EXPECT_EQ(1, Log2Ceiling(2));
40 EXPECT_EQ(2, Log2Ceiling(3));
41 EXPECT_EQ(2, Log2Ceiling(4));
42 for (int i = 3; i < 31; ++i) {
43 unsigned int value = 1U << i;
44 EXPECT_EQ(i, Log2Ceiling(value));
45 EXPECT_EQ(i + 1, Log2Ceiling(value + 1));
46 EXPECT_EQ(i + 1, Log2Ceiling(value + 2));
47 EXPECT_EQ(i, Log2Ceiling(value - 1));
48 EXPECT_EQ(i, Log2Ceiling(value - 2));
50 EXPECT_EQ(32, Log2Ceiling(0xffffffffU));
53 TEST(BitsTest, Align) {
54 static constexpr size_t kSizeTMax = std::numeric_limits<size_t>::max();
55 EXPECT_EQ(0ul, Align(0, 4));
56 EXPECT_EQ(4ul, Align(1, 4));
57 EXPECT_EQ(4096ul, Align(1, 4096));
58 EXPECT_EQ(4096ul, Align(4096, 4096));
59 EXPECT_EQ(4096ul, Align(4095, 4096));
60 EXPECT_EQ(8192ul, Align(4097, 4096));
61 EXPECT_EQ(kSizeTMax - 31, Align(kSizeTMax - 62, 32));
62 EXPECT_EQ(kSizeTMax / 2 + 1, Align(1, kSizeTMax / 2 + 1));
65 TEST(BitsTest, AlignDown) {
66 static constexpr size_t kSizeTMax = std::numeric_limits<size_t>::max();
67 EXPECT_EQ(0ul, AlignDown(0, 4));
68 EXPECT_EQ(0ul, AlignDown(1, 4));
69 EXPECT_EQ(0ul, AlignDown(1, 4096));
70 EXPECT_EQ(4096ul, AlignDown(4096, 4096));
71 EXPECT_EQ(0ul, AlignDown(4095, 4096));
72 EXPECT_EQ(4096ul, AlignDown(4097, 4096));
73 EXPECT_EQ(kSizeTMax - 63, AlignDown(kSizeTMax - 62, 32));
74 EXPECT_EQ(kSizeTMax - 31, AlignDown(kSizeTMax, 32));
75 EXPECT_EQ(0ul, AlignDown(1, kSizeTMax / 2 + 1));
78 TEST(BitsTest, CountLeadingZeroBits8) {
79 EXPECT_EQ(8u, CountLeadingZeroBits(uint8_t{0}));
80 EXPECT_EQ(7u, CountLeadingZeroBits(uint8_t{1}));
81 for (uint8_t shift = 0; shift <= 7; shift++) {
83 CountLeadingZeroBits(static_cast<uint8_t>(1 << shift)));
85 EXPECT_EQ(4u, CountLeadingZeroBits(uint8_t{0x0f}));
88 TEST(BitsTest, CountLeadingZeroBits16) {
89 EXPECT_EQ(16u, CountLeadingZeroBits(uint16_t{0}));
90 EXPECT_EQ(15u, CountLeadingZeroBits(uint16_t{1}));
91 for (uint16_t shift = 0; shift <= 15; shift++) {
92 EXPECT_EQ(15u - shift,
93 CountLeadingZeroBits(static_cast<uint16_t>(1 << shift)));
95 EXPECT_EQ(4u, CountLeadingZeroBits(uint16_t{0x0f0f}));
98 TEST(BitsTest, CountLeadingZeroBits32) {
99 EXPECT_EQ(32u, CountLeadingZeroBits(uint32_t{0}));
100 EXPECT_EQ(31u, CountLeadingZeroBits(uint32_t{1}));
101 for (uint32_t shift = 0; shift <= 31; shift++) {
102 EXPECT_EQ(31u - shift, CountLeadingZeroBits(uint32_t{1} << shift));
104 EXPECT_EQ(4u, CountLeadingZeroBits(uint32_t{0x0f0f0f0f}));
107 TEST(BitsTest, CountTrailingeZeroBits8) {
108 EXPECT_EQ(8u, CountTrailingZeroBits(uint8_t{0}));
109 EXPECT_EQ(7u, CountTrailingZeroBits(uint8_t{128}));
110 for (uint8_t shift = 0; shift <= 7; shift++) {
111 EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint8_t>(1 << shift)));
113 EXPECT_EQ(4u, CountTrailingZeroBits(uint8_t{0xf0}));
116 TEST(BitsTest, CountTrailingeZeroBits16) {
117 EXPECT_EQ(16u, CountTrailingZeroBits(uint16_t{0}));
118 EXPECT_EQ(15u, CountTrailingZeroBits(uint16_t{32768}));
119 for (uint16_t shift = 0; shift <= 15; shift++) {
120 EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint16_t>(1 << shift)));
122 EXPECT_EQ(4u, CountTrailingZeroBits(uint16_t{0xf0f0}));
125 TEST(BitsTest, CountTrailingeZeroBits32) {
126 EXPECT_EQ(32u, CountTrailingZeroBits(uint32_t{0}));
127 EXPECT_EQ(31u, CountTrailingZeroBits(uint32_t{1} << 31));
128 for (uint32_t shift = 0; shift <= 31; shift++) {
129 EXPECT_EQ(shift, CountTrailingZeroBits(uint32_t{1} << shift));
131 EXPECT_EQ(4u, CountTrailingZeroBits(uint32_t{0xf0f0f0f0}));
134 TEST(BitsTest, CountLeadingZeroBits64) {
135 EXPECT_EQ(64u, CountLeadingZeroBits(uint64_t{0}));
136 EXPECT_EQ(63u, CountLeadingZeroBits(uint64_t{1}));
137 for (uint64_t shift = 0; shift <= 63; shift++) {
138 EXPECT_EQ(63u - shift, CountLeadingZeroBits(uint64_t{1} << shift));
140 EXPECT_EQ(4u, CountLeadingZeroBits(uint64_t{0x0f0f0f0f0f0f0f0f}));
143 TEST(BitsTest, CountTrailingeZeroBits64) {
144 EXPECT_EQ(64u, CountTrailingZeroBits(uint64_t{0}));
145 EXPECT_EQ(63u, CountTrailingZeroBits(uint64_t{1} << 63));
146 for (uint64_t shift = 0; shift <= 31; shift++) {
147 EXPECT_EQ(shift, CountTrailingZeroBits(uint64_t{1} << shift));
149 EXPECT_EQ(4u, CountTrailingZeroBits(uint64_t{0xf0f0f0f0f0f0f0f0}));
152 TEST(BitsTest, CountLeadingZeroBitsSizeT) {
153 #if defined(ARCH_CPU_64_BITS)
154 EXPECT_EQ(64u, CountLeadingZeroBitsSizeT(size_t{0}));
155 EXPECT_EQ(63u, CountLeadingZeroBitsSizeT(size_t{1}));
156 EXPECT_EQ(32u, CountLeadingZeroBitsSizeT(size_t{1} << 31));
157 EXPECT_EQ(1u, CountLeadingZeroBitsSizeT(size_t{1} << 62));
158 EXPECT_EQ(0u, CountLeadingZeroBitsSizeT(size_t{1} << 63));
160 EXPECT_EQ(32u, CountLeadingZeroBitsSizeT(size_t{0}));
161 EXPECT_EQ(31u, CountLeadingZeroBitsSizeT(size_t{1}));
162 EXPECT_EQ(1u, CountLeadingZeroBitsSizeT(size_t{1} << 30));
163 EXPECT_EQ(0u, CountLeadingZeroBitsSizeT(size_t{1} << 31));
164 #endif // ARCH_CPU_64_BITS
167 TEST(BitsTest, CountTrailingZeroBitsSizeT) {
168 #if defined(ARCH_CPU_64_BITS)
169 EXPECT_EQ(64u, CountTrailingZeroBitsSizeT(size_t{0}));
170 EXPECT_EQ(63u, CountTrailingZeroBitsSizeT(size_t{1} << 63));
171 EXPECT_EQ(31u, CountTrailingZeroBitsSizeT(size_t{1} << 31));
172 EXPECT_EQ(1u, CountTrailingZeroBitsSizeT(size_t{2}));
173 EXPECT_EQ(0u, CountTrailingZeroBitsSizeT(size_t{1}));
175 EXPECT_EQ(32u, CountTrailingZeroBitsSizeT(size_t{0}));
176 EXPECT_EQ(31u, CountTrailingZeroBitsSizeT(size_t{1} << 31));
177 EXPECT_EQ(1u, CountTrailingZeroBitsSizeT(size_t{2}));
178 EXPECT_EQ(0u, CountTrailingZeroBitsSizeT(size_t{1}));
179 #endif // ARCH_CPU_64_BITS
182 TEST(BitsTest, PowerOfTwo) {
183 EXPECT_FALSE(IsPowerOfTwo(-1));
184 EXPECT_FALSE(IsPowerOfTwo(0));
185 EXPECT_TRUE(IsPowerOfTwo(1));
186 EXPECT_TRUE(IsPowerOfTwo(2));
187 // Unsigned 64 bit cases.
188 for (uint32_t i = 2; i < 64; i++) {
189 const uint64_t val = uint64_t{1} << i;
190 EXPECT_FALSE(IsPowerOfTwo(val - 1));
191 EXPECT_TRUE(IsPowerOfTwo(val));
192 EXPECT_FALSE(IsPowerOfTwo(val + 1));
194 // Signed 64 bit cases.
195 for (uint32_t i = 2; i < 63; i++) {
196 const int64_t val = int64_t{1} << i;
197 EXPECT_FALSE(IsPowerOfTwo(val - 1));
198 EXPECT_TRUE(IsPowerOfTwo(val));
199 EXPECT_FALSE(IsPowerOfTwo(val + 1));
201 // Signed integers with only the last bit set are negative, not powers of two.
202 EXPECT_FALSE(IsPowerOfTwo(int64_t{1} << 63));