1 : /*
2 : * Copyright (c) 2012 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : /*
8 : * Test the portability bits functions work properly for a wide range of
9 : * inputs (limited by test runtime).
10 : */
11 :
12 : #include <limits>
13 : #include "gtest/gtest.h"
14 : #include "native_client/src/include/portability_bits.h"
15 :
16 : class BitsTest : public testing::Test {
17 : protected:
18 1 : virtual void SetUp() {}
19 1 : virtual void TearDown() {}
20 :
21 : template<typename Ret, typename In>
22 : void TestAllInputsInRange(Ret (*impl)(In), Ret (*test)(In),
23 5 : In start, In end) {
24 5 : EXPECT_LE(start, end);
25 5 : In i = start;
26 : do {
27 5 : Ret impl_result = (*impl)(i);
28 5 : Ret test_result = (*test)(i);
29 5 : EXPECT_EQ(impl_result, test_result);
30 5 : } while (i++ != end);
31 5 : }
32 :
33 : template<typename Ret, typename In>
34 2 : void TestAllInputs(Ret (*impl)(In), Ret (*test)(In)) {
35 2 : TestAllInputsInRange(impl, test, (In)0, std::numeric_limits<In>::max());
36 2 : }
37 : };
38 :
39 : namespace bits_test {
40 :
41 : template<typename T> struct Helper { /* Specialized below. */ };
42 : template<> struct Helper<uint8_t> { static int Bits() { return 8; } };
43 : template<> struct Helper<uint16_t> { static int Bits() { return 16; } };
44 1 : template<> struct Helper<uint32_t> { static int Bits() { return 32; } };
45 : template<> struct Helper<uint64_t> { static int Bits() { return 64; } };
46 :
47 4 : template<typename T> INLINE int PopCount(T v) {
48 4 : int count = 0;
49 4 : while (v) {
50 4 : count += (v & 1);
51 4 : v >>= 1;
52 4 : }
53 4 : return count;
54 4 : }
55 :
56 1 : template<typename T> INLINE T BitReverse(T v) {
57 1 : T result = 0;
58 1 : const int bits = Helper<T>::Bits();
59 1 : for (int i = 0; i < bits / 2; ++i) {
60 : // Rotate LSBs to MSBs.
61 1 : T mask = (1 << ((bits - 1) - i));
62 1 : int rotation = (bits - 1) - (i << 1);
63 1 : result |= (v << rotation) & mask;
64 1 : }
65 1 : for (int i = bits / 2; i < bits; ++i) {
66 : // Rotate MSBs to LSBs.
67 1 : T mask = (1 << ((bits - 1) - i));
68 1 : int rotation = ((i - ((bits / 2) - 1)) << 1) - 1;
69 1 : result |= (v >> rotation) & mask;
70 1 : }
71 1 : return result;
72 1 : }
73 :
74 1 : template<typename T> INLINE int CountTrailingZeroes(T v) {
75 : int i;
76 1 : if (!v) return -1;
77 1 : for (i = 0; !(v & 1); v >>= 1, ++i) {
78 1 : }
79 1 : return i;
80 1 : }
81 :
82 1 : template<typename T> INLINE int CountLeadingZeroes(T v) {
83 : int i;
84 1 : const int last_bit = Helper<T>::Bits() - 1;
85 1 : const T last_bit_mask = (T)1 << last_bit;
86 1 : if (!v) return -1;
87 1 : for (i = 0; !(v & last_bit_mask); v <<= 1, ++i) {
88 1 : }
89 1 : return i;
90 1 : }
91 :
92 : } // namespace bits_test
93 :
94 :
95 : // Extra range amount, used to test a bit past interesting values.
96 : static const int kExtra = 2050;
97 :
98 :
99 3 : TEST_F(BitsTest, PopCount8) {
100 : TestAllInputs(&nacl::PopCount<uint8_t>,
101 1 : &bits_test::PopCount<uint8_t>);
102 1 : }
103 3 : TEST_F(BitsTest, PopCount16) {
104 : TestAllInputs(&nacl::PopCount<uint16_t>,
105 1 : &bits_test::PopCount<uint16_t>);
106 1 : }
107 3 : TEST_F(BitsTest, PopCount32) {
108 : TestAllInputsInRange(&nacl::PopCount<uint32_t>,
109 : &bits_test::PopCount<uint32_t>,
110 : (uint32_t)0,
111 1 : (uint32_t)std::numeric_limits<uint16_t>::max() + kExtra);
112 : TestAllInputsInRange(&nacl::PopCount<uint32_t>,
113 : &bits_test::PopCount<uint32_t>,
114 : (uint32_t)std::numeric_limits<uint32_t>::max() -
115 : std::numeric_limits<uint16_t>::max() - kExtra,
116 1 : std::numeric_limits<uint32_t>::max());
117 1 : }
118 3 : TEST_F(BitsTest, PopCount64) {
119 : TestAllInputsInRange(&nacl::PopCount<uint64_t>,
120 : &bits_test::PopCount<uint64_t>,
121 : (uint64_t)0,
122 1 : (uint64_t)std::numeric_limits<uint16_t>::max() + kExtra);
123 : TestAllInputsInRange(&nacl::PopCount<uint64_t>,
124 : &bits_test::PopCount<uint64_t>,
125 : (uint64_t)std::numeric_limits<uint32_t>::max() -
126 : std::numeric_limits<uint16_t>::max() - kExtra,
127 : (uint64_t)std::numeric_limits<uint32_t>::max() +
128 1 : std::numeric_limits<uint16_t>::max() + kExtra);
129 : TestAllInputsInRange(&nacl::PopCount<uint64_t>,
130 : &bits_test::PopCount<uint64_t>,
131 : std::numeric_limits<uint64_t>::max() -
132 : std::numeric_limits<uint16_t>::max() - kExtra,
133 1 : std::numeric_limits<uint64_t>::max());
134 1 : }
135 :
136 3 : TEST_F(BitsTest, BitReverse32) {
137 : TestAllInputsInRange(&nacl::BitReverse<uint32_t>,
138 : &bits_test::BitReverse<uint32_t>,
139 : (uint32_t)0,
140 1 : (uint32_t)std::numeric_limits<uint16_t>::max() + kExtra);
141 : TestAllInputsInRange(&nacl::BitReverse<uint32_t>,
142 : &bits_test::BitReverse<uint32_t>,
143 : (uint32_t)std::numeric_limits<uint32_t>::max() -
144 : std::numeric_limits<uint16_t>::max() - kExtra,
145 1 : std::numeric_limits<uint32_t>::max());
146 1 : }
147 :
148 3 : TEST_F(BitsTest, CountTrailingZeroes32) {
149 : TestAllInputsInRange(&nacl::CountTrailingZeroes<uint32_t>,
150 : &bits_test::CountTrailingZeroes<uint32_t>,
151 : (uint32_t)0,
152 1 : (uint32_t)std::numeric_limits<uint16_t>::max() + kExtra);
153 : TestAllInputsInRange(&nacl::CountTrailingZeroes<uint32_t>,
154 : &bits_test::CountTrailingZeroes<uint32_t>,
155 : (uint32_t)std::numeric_limits<uint32_t>::max() -
156 : std::numeric_limits<uint16_t>::max() - kExtra,
157 1 : std::numeric_limits<uint32_t>::max());
158 1 : }
159 :
160 3 : TEST_F(BitsTest, CountLeadingZeroes32) {
161 : TestAllInputsInRange(&nacl::CountLeadingZeroes<uint32_t>,
162 : &bits_test::CountLeadingZeroes<uint32_t>,
163 : (uint32_t)0,
164 1 : (uint32_t)std::numeric_limits<uint16_t>::max() + kExtra);
165 : TestAllInputsInRange(&nacl::CountLeadingZeroes<uint32_t>,
166 : &bits_test::CountLeadingZeroes<uint32_t>,
167 : (uint32_t)std::numeric_limits<uint32_t>::max() -
168 : std::numeric_limits<uint16_t>::max() - kExtra,
169 1 : std::numeric_limits<uint32_t>::max());
170 1 : }
171 :
172 1 : int main(int argc, char **argv) {
173 1 : testing::InitGoogleTest(&argc, argv);
174 1 : return RUN_ALL_TESTS();
175 1 : }
|
