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.
4
5 // This file contains the unit tests for the bit utilities.
6
7 #include "base/bits.h"
8 #include "build/build_config.h"
9
10 #include <stddef.h>
11
12 #include <limits>
13
14 #include "testing/gtest/include/gtest/gtest.h"
15
16 namespace base {
17 namespace bits {
18
TEST(BitsTest,Log2Floor)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));
32 }
33 EXPECT_EQ(31, Log2Floor(0xffffffffU));
34 }
35
TEST(BitsTest,Log2Ceiling)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));
49 }
50 EXPECT_EQ(32, Log2Ceiling(0xffffffffU));
51 }
52
TEST(BitsTest,Align)53 TEST(BitsTest, Align) {
54 const 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));
63 }
64
TEST(BitsTest,CountLeadingZeroBits8)65 TEST(BitsTest, CountLeadingZeroBits8) {
66 EXPECT_EQ(8u, CountLeadingZeroBits(uint8_t{0}));
67 EXPECT_EQ(7u, CountLeadingZeroBits(uint8_t{1}));
68 for (uint8_t shift = 0; shift <= 7; shift++) {
69 EXPECT_EQ(7u - shift,
70 CountLeadingZeroBits(static_cast<uint8_t>(1 << shift)));
71 }
72 EXPECT_EQ(4u, CountLeadingZeroBits(uint8_t{0x0f}));
73 }
74
TEST(BitsTest,CountLeadingZeroBits16)75 TEST(BitsTest, CountLeadingZeroBits16) {
76 EXPECT_EQ(16u, CountLeadingZeroBits(uint16_t{0}));
77 EXPECT_EQ(15u, CountLeadingZeroBits(uint16_t{1}));
78 for (uint16_t shift = 0; shift <= 15; shift++) {
79 EXPECT_EQ(15u - shift,
80 CountLeadingZeroBits(static_cast<uint16_t>(1 << shift)));
81 }
82 EXPECT_EQ(4u, CountLeadingZeroBits(uint16_t{0x0f0f}));
83 }
84
TEST(BitsTest,CountLeadingZeroBits32)85 TEST(BitsTest, CountLeadingZeroBits32) {
86 EXPECT_EQ(32u, CountLeadingZeroBits(uint32_t{0}));
87 EXPECT_EQ(31u, CountLeadingZeroBits(uint32_t{1}));
88 for (uint32_t shift = 0; shift <= 31; shift++) {
89 EXPECT_EQ(31u - shift, CountLeadingZeroBits(uint32_t{1} << shift));
90 }
91 EXPECT_EQ(4u, CountLeadingZeroBits(uint32_t{0x0f0f0f0f}));
92 }
93
TEST(BitsTest,CountTrailingeZeroBits8)94 TEST(BitsTest, CountTrailingeZeroBits8) {
95 EXPECT_EQ(8u, CountTrailingZeroBits(uint8_t{0}));
96 EXPECT_EQ(7u, CountTrailingZeroBits(uint8_t{128}));
97 for (uint8_t shift = 0; shift <= 7; shift++) {
98 EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint8_t>(1 << shift)));
99 }
100 EXPECT_EQ(4u, CountTrailingZeroBits(uint8_t{0xf0}));
101 }
102
TEST(BitsTest,CountTrailingeZeroBits16)103 TEST(BitsTest, CountTrailingeZeroBits16) {
104 EXPECT_EQ(16u, CountTrailingZeroBits(uint16_t{0}));
105 EXPECT_EQ(15u, CountTrailingZeroBits(uint16_t{32768}));
106 for (uint16_t shift = 0; shift <= 15; shift++) {
107 EXPECT_EQ(shift, CountTrailingZeroBits(static_cast<uint16_t>(1 << shift)));
108 }
109 EXPECT_EQ(4u, CountTrailingZeroBits(uint16_t{0xf0f0}));
110 }
111
TEST(BitsTest,CountTrailingeZeroBits32)112 TEST(BitsTest, CountTrailingeZeroBits32) {
113 EXPECT_EQ(32u, CountTrailingZeroBits(uint32_t{0}));
114 EXPECT_EQ(31u, CountTrailingZeroBits(uint32_t{1} << 31));
115 for (uint32_t shift = 0; shift <= 31; shift++) {
116 EXPECT_EQ(shift, CountTrailingZeroBits(uint32_t{1} << shift));
117 }
118 EXPECT_EQ(4u, CountTrailingZeroBits(uint32_t{0xf0f0f0f0}));
119 }
120
121 #if defined(ARCH_CPU_64_BITS)
122
TEST(BitsTest,CountLeadingZeroBits64)123 TEST(BitsTest, CountLeadingZeroBits64) {
124 EXPECT_EQ(64u, CountLeadingZeroBits(uint64_t{0}));
125 EXPECT_EQ(63u, CountLeadingZeroBits(uint64_t{1}));
126 for (uint64_t shift = 0; shift <= 63; shift++) {
127 EXPECT_EQ(63u - shift, CountLeadingZeroBits(uint64_t{1} << shift));
128 }
129 EXPECT_EQ(4u, CountLeadingZeroBits(uint64_t{0x0f0f0f0f0f0f0f0f}));
130 }
131
TEST(BitsTest,CountTrailingeZeroBits64)132 TEST(BitsTest, CountTrailingeZeroBits64) {
133 EXPECT_EQ(64u, CountTrailingZeroBits(uint64_t{0}));
134 EXPECT_EQ(63u, CountTrailingZeroBits(uint64_t{1} << 63));
135 for (uint64_t shift = 0; shift <= 31; shift++) {
136 EXPECT_EQ(shift, CountTrailingZeroBits(uint64_t{1} << shift));
137 }
138 EXPECT_EQ(4u, CountTrailingZeroBits(uint64_t{0xf0f0f0f0f0f0f0f0}));
139 }
140
141 #endif // ARCH_CPU_64_BITS
142
TEST(BitsTest,CountLeadingZeroBitsSizeT)143 TEST(BitsTest, CountLeadingZeroBitsSizeT) {
144 #if defined(ARCH_CPU_64_BITS)
145 EXPECT_EQ(64u, CountLeadingZeroBitsSizeT(size_t{0}));
146 EXPECT_EQ(63u, CountLeadingZeroBitsSizeT(size_t{1}));
147 EXPECT_EQ(32u, CountLeadingZeroBitsSizeT(size_t{1} << 31));
148 EXPECT_EQ(1u, CountLeadingZeroBitsSizeT(size_t{1} << 62));
149 EXPECT_EQ(0u, CountLeadingZeroBitsSizeT(size_t{1} << 63));
150 #else
151 EXPECT_EQ(32u, CountLeadingZeroBitsSizeT(size_t{0}));
152 EXPECT_EQ(31u, CountLeadingZeroBitsSizeT(size_t{1}));
153 EXPECT_EQ(1u, CountLeadingZeroBitsSizeT(size_t{1} << 30));
154 EXPECT_EQ(0u, CountLeadingZeroBitsSizeT(size_t{1} << 31));
155 #endif // ARCH_CPU_64_BITS
156 }
157
TEST(BitsTest,CountTrailingZeroBitsSizeT)158 TEST(BitsTest, CountTrailingZeroBitsSizeT) {
159 #if defined(ARCH_CPU_64_BITS)
160 EXPECT_EQ(64u, CountTrailingZeroBitsSizeT(size_t{0}));
161 EXPECT_EQ(63u, CountTrailingZeroBitsSizeT(size_t{1} << 63));
162 EXPECT_EQ(31u, CountTrailingZeroBitsSizeT(size_t{1} << 31));
163 EXPECT_EQ(1u, CountTrailingZeroBitsSizeT(size_t{2}));
164 EXPECT_EQ(0u, CountTrailingZeroBitsSizeT(size_t{1}));
165 #else
166 EXPECT_EQ(32u, CountTrailingZeroBitsSizeT(size_t{0}));
167 EXPECT_EQ(31u, CountTrailingZeroBitsSizeT(size_t{1} << 31));
168 EXPECT_EQ(1u, CountTrailingZeroBitsSizeT(size_t{2}));
169 EXPECT_EQ(0u, CountTrailingZeroBitsSizeT(size_t{1}));
170 #endif // ARCH_CPU_64_BITS
171 }
172
TEST(BitsTest,PowerOfTwo)173 TEST(BitsTest, PowerOfTwo) {
174 EXPECT_FALSE(IsPowerOfTwo(-1));
175 EXPECT_FALSE(IsPowerOfTwo(0));
176 EXPECT_TRUE(IsPowerOfTwo(1));
177 EXPECT_TRUE(IsPowerOfTwo(2));
178 // Unsigned 64 bit cases.
179 for (uint32_t i = 2; i < 64; i++) {
180 const uint64_t val = uint64_t{1} << i;
181 EXPECT_FALSE(IsPowerOfTwo(val - 1));
182 EXPECT_TRUE(IsPowerOfTwo(val));
183 EXPECT_FALSE(IsPowerOfTwo(val + 1));
184 }
185 // Signed 64 bit cases.
186 for (uint32_t i = 2; i < 63; i++) {
187 const int64_t val = int64_t{1} << i;
188 EXPECT_FALSE(IsPowerOfTwo(val - 1));
189 EXPECT_TRUE(IsPowerOfTwo(val));
190 EXPECT_FALSE(IsPowerOfTwo(val + 1));
191 }
192 // Signed integers with only the last bit set are negative, not powers of two.
193 EXPECT_FALSE(IsPowerOfTwo(int64_t{1} << 63));
194 }
195
196 } // namespace bits
197 } // namespace base
198