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 14 : class BitsTest : public testing::Test {
17 : protected:
18 7 : virtual void SetUp() {}
19 7 : virtual void TearDown() {}
20 :
21 : template<typename Ret, typename In>
22 13 : void TestAllInputsInRange(Ret (*impl)(In), Ret (*test)(In),
23 13 : In start, In end) {
24 52 : EXPECT_LE(start, end);
25 13 : In i = start;
26 13 : do {
27 876823 : Ret impl_result = (*impl)(i);
28 876823 : Ret test_result = (*test)(i);
29 3507292 : EXPECT_EQ(impl_result, test_result);
30 1753646 : } while (i++ != end);
31 13 : }
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 270344 : template<> struct Helper<uint32_t> { static int Bits() { return 32; } };
45 : template<> struct Helper<uint64_t> { static int Bits() { return 64; } };
46 :
47 471307 : template<typename T> INLINE int PopCount(T v) {
48 471307 : int count = 0;
49 14844543 : while (v) {
50 13901929 : count += (v & 1);
51 13901929 : v >>= 1;
52 13901929 : }
53 471307 : return count;
54 : }
55 :
56 135172 : template<typename T> INLINE T BitReverse(T v) {
57 135172 : T result = 0;
58 135172 : const int bits = Helper<T>::Bits();
59 4595848 : for (int i = 0; i < bits / 2; ++i) {
60 : // Rotate LSBs to MSBs.
61 2162752 : T mask = (1 << ((bits - 1) - i));
62 2162752 : int rotation = (bits - 1) - (i << 1);
63 2162752 : result |= (v << rotation) & mask;
64 2162752 : }
65 4595848 : for (int i = bits / 2; i < bits; ++i) {
66 : // Rotate MSBs to LSBs.
67 2162752 : T mask = (1 << ((bits - 1) - i));
68 2162752 : int rotation = ((i - ((bits / 2) - 1)) << 1) - 1;
69 2162752 : result |= (v >> rotation) & mask;
70 2162752 : }
71 135172 : return result;
72 : }
73 :
74 135172 : template<typename T> INLINE int CountTrailingZeroes(T v) {
75 135172 : int i;
76 135173 : if (!v) return -1;
77 540672 : for (i = 0; !(v & 1); v >>= 1, ++i) {
78 135165 : }
79 135171 : return i;
80 135172 : }
81 :
82 135172 : template<typename T> INLINE int CountLeadingZeroes(T v) {
83 135172 : int i;
84 135172 : const int last_bit = Helper<T>::Bits() - 1;
85 135172 : const T last_bit_mask = (T)1 << last_bit;
86 135173 : if (!v) return -1;
87 2560000 : for (i = 0; !(v & last_bit_mask); v <<= 1, ++i) {
88 1144829 : }
89 135171 : return i;
90 135172 : }
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 8 : TEST_F(BitsTest, PopCount8) {
100 1 : TestAllInputs(&nacl::PopCount<uint8_t>,
101 : &bits_test::PopCount<uint8_t>);
102 1 : }
103 8 : TEST_F(BitsTest, PopCount16) {
104 1 : TestAllInputs(&nacl::PopCount<uint16_t>,
105 : &bits_test::PopCount<uint16_t>);
106 1 : }
107 8 : TEST_F(BitsTest, PopCount32) {
108 2 : 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 2 : TestAllInputsInRange(&nacl::PopCount<uint32_t>,
113 : &bits_test::PopCount<uint32_t>,
114 1 : (uint32_t)std::numeric_limits<uint32_t>::max() -
115 1 : std::numeric_limits<uint16_t>::max() - kExtra,
116 1 : std::numeric_limits<uint32_t>::max());
117 1 : }
118 8 : TEST_F(BitsTest, PopCount64) {
119 2 : 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 2 : TestAllInputsInRange(&nacl::PopCount<uint64_t>,
124 : &bits_test::PopCount<uint64_t>,
125 1 : (uint64_t)std::numeric_limits<uint32_t>::max() -
126 1 : std::numeric_limits<uint16_t>::max() - kExtra,
127 1 : (uint64_t)std::numeric_limits<uint32_t>::max() +
128 1 : std::numeric_limits<uint16_t>::max() + kExtra);
129 2 : TestAllInputsInRange(&nacl::PopCount<uint64_t>,
130 : &bits_test::PopCount<uint64_t>,
131 1 : std::numeric_limits<uint64_t>::max() -
132 1 : std::numeric_limits<uint16_t>::max() - kExtra,
133 1 : std::numeric_limits<uint64_t>::max());
134 1 : }
135 :
136 8 : TEST_F(BitsTest, BitReverse32) {
137 2 : 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 2 : TestAllInputsInRange(&nacl::BitReverse<uint32_t>,
142 : &bits_test::BitReverse<uint32_t>,
143 1 : (uint32_t)std::numeric_limits<uint32_t>::max() -
144 1 : std::numeric_limits<uint16_t>::max() - kExtra,
145 1 : std::numeric_limits<uint32_t>::max());
146 1 : }
147 :
148 8 : TEST_F(BitsTest, CountTrailingZeroes32) {
149 2 : 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 2 : TestAllInputsInRange(&nacl::CountTrailingZeroes<uint32_t>,
154 : &bits_test::CountTrailingZeroes<uint32_t>,
155 1 : (uint32_t)std::numeric_limits<uint32_t>::max() -
156 1 : std::numeric_limits<uint16_t>::max() - kExtra,
157 1 : std::numeric_limits<uint32_t>::max());
158 1 : }
159 :
160 8 : TEST_F(BitsTest, CountLeadingZeroes32) {
161 2 : 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 2 : TestAllInputsInRange(&nacl::CountLeadingZeroes<uint32_t>,
166 : &bits_test::CountLeadingZeroes<uint32_t>,
167 1 : (uint32_t)std::numeric_limits<uint32_t>::max() -
168 1 : 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 : }
|
