1 // (C) Copyright 2017, Google Inc.
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 // http://www.apache.org/licenses/LICENSE-2.0
6 // Unless required by applicable law or agreed to in writing, software
7 // distributed under the License is distributed on an "AS IS" BASIS,
8 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
9 // See the License for the specific language governing permissions and
10 // limitations under the License.
11
12 #include <cmath>
13 #include <cstdio>
14 #include <string>
15
16 #include "bitvector.h"
17
18 #include "include_gunit.h"
19
20 const int kPrimeLimit = 1000;
21
22 namespace tesseract {
23
24 class BitVectorTest : public testing::Test {
25 protected:
SetUp()26 void SetUp() override {
27 std::locale::global(std::locale(""));
28 file::MakeTmpdir();
29 }
30
31 public:
OutputNameToPath(const std::string & name)32 std::string OutputNameToPath(const std::string &name) {
33 return file::JoinPath(FLAGS_test_tmpdir, name);
34 }
35 // Computes primes up to kPrimeLimit, using the sieve of Eratosthenes.
ComputePrimes(BitVector * map)36 void ComputePrimes(BitVector *map) {
37 map->Init(kPrimeLimit + 1);
38 TestAll(*map, false);
39 map->SetBit(2);
40 // Set all the odds to true.
41 for (int i = 3; i <= kPrimeLimit; i += 2) {
42 map->SetValue(i, true);
43 }
44 int factor_limit = static_cast<int>(sqrt(1.0 + kPrimeLimit));
45 for (int f = 3; f <= factor_limit; f += 2) {
46 if (map->At(f)) {
47 for (int m = 2; m * f <= kPrimeLimit; ++m) {
48 map->ResetBit(f * m);
49 }
50 }
51 }
52 }
53
TestPrimes(const BitVector & map)54 void TestPrimes(const BitVector &map) {
55 // Now all primes in the vector are true, and all others false.
56 // According to Wikipedia, there are 168 primes under 1000, the last
57 // of which is 997.
58 int total_primes = 0;
59 for (int i = 0; i <= kPrimeLimit; ++i) {
60 if (map[i]) {
61 ++total_primes;
62 }
63 }
64 EXPECT_EQ(168, total_primes);
65 EXPECT_TRUE(map[997]);
66 EXPECT_FALSE(map[998]);
67 EXPECT_FALSE(map[999]);
68 }
69 // Test that all bits in the vector have the given value.
TestAll(const BitVector & map,bool value)70 void TestAll(const BitVector &map, bool value) {
71 for (int i = 0; i < map.size(); ++i) {
72 EXPECT_EQ(value, map[i]);
73 }
74 }
75
76 // Sets up a BitVector with bit patterns for byte values in
77 // [start_byte, end_byte) positioned every spacing bytes (for spacing >= 1)
78 // with spacing-1 zero bytes in between the pattern bytes.
SetBitPattern(int start_byte,int end_byte,int spacing,BitVector * bv)79 void SetBitPattern(int start_byte, int end_byte, int spacing, BitVector *bv) {
80 bv->Init((end_byte - start_byte) * 8 * spacing);
81 for (int byte_value = start_byte; byte_value < end_byte; ++byte_value) {
82 for (int bit = 0; bit < 8; ++bit) {
83 if (byte_value & (1 << bit)) {
84 bv->SetBit((byte_value - start_byte) * 8 * spacing + bit);
85 }
86 }
87 }
88 }
89
90 // Expects that every return from NextSetBit is really set and that all others
91 // are really not set. Checks the return from NumSetBits also.
ExpectCorrectBits(const BitVector & bv)92 void ExpectCorrectBits(const BitVector &bv) {
93 int bit_index = -1;
94 int prev_bit_index = -1;
95 int num_bits_tested = 0;
96 while ((bit_index = bv.NextSetBit(bit_index)) >= 0) {
97 EXPECT_LT(bit_index, bv.size());
98 // All bits in between must be 0.
99 for (int i = prev_bit_index + 1; i < bit_index; ++i) {
100 EXPECT_EQ(0, bv[i]) << "i = " << i << " prev = " << prev_bit_index;
101 }
102 // This bit must be 1.
103 EXPECT_EQ(1, bv[bit_index]) << "Bit index = " << bit_index;
104 ++num_bits_tested;
105 prev_bit_index = bit_index;
106 }
107 // Check the bits between the last and the end.
108 for (int i = prev_bit_index + 1; i < bv.size(); ++i) {
109 EXPECT_EQ(0, bv[i]);
110 }
111 EXPECT_EQ(num_bits_tested, bv.NumSetBits());
112 }
113 };
114
115 // Tests the sieve of Eratosthenes as a way of testing set/reset and I/O.
TEST_F(BitVectorTest,Primes)116 TEST_F(BitVectorTest, Primes) {
117 BitVector map;
118 ComputePrimes(&map);
119 TestPrimes(map);
120 // It still works if we use the copy constructor.
121 BitVector map2(map);
122 TestPrimes(map2);
123 // Or if we assign it.
124 BitVector map3;
125 map3 = map;
126 TestPrimes(map3);
127 // Test file i/o too.
128 std::string filename = OutputNameToPath("primesbitvector");
129 FILE *fp = fopen(filename.c_str(), "wb");
130 ASSERT_TRUE(fp != nullptr);
131 EXPECT_TRUE(map.Serialize(fp));
132 fclose(fp);
133 fp = fopen(filename.c_str(), "rb");
134 ASSERT_TRUE(fp != nullptr);
135 BitVector read_map;
136 EXPECT_TRUE(read_map.DeSerialize(false, fp));
137 fclose(fp);
138 TestPrimes(read_map);
139 }
140
141 // Tests the many-to-one setup feature.
TEST_F(BitVectorTest,SetAll)142 TEST_F(BitVectorTest, SetAll) {
143 // Test the default constructor and set/resetall.
144 BitVector map(42);
145 TestAll(map, false);
146 map.SetAllTrue();
147 TestAll(map, true);
148 map.SetAllFalse();
149 TestAll(map, false);
150 }
151
152 // Tests the values in the tables offset_table_, next_table_, hamming_table_
153 // by setting all possible byte patterns and verifying that the NextSetBit and
154 // NumSetBits functions return the correct values.
TEST_F(BitVectorTest,TestNextSetBit)155 TEST_F(BitVectorTest, TestNextSetBit) {
156 BitVector bv;
157 for (int spacing = 1; spacing <= 5; ++spacing) {
158 SetBitPattern(0, 256, spacing, &bv);
159 ExpectCorrectBits(bv);
160 }
161 }
162
163 // Tests the values in hamming_table_ more thoroughly by setting single byte
164 // patterns for each byte individually.
TEST_F(BitVectorTest,TestNumSetBits)165 TEST_F(BitVectorTest, TestNumSetBits) {
166 BitVector bv;
167 for (int byte = 0; byte < 256; ++byte) {
168 SetBitPattern(byte, byte + 1, 1, &bv);
169 ExpectCorrectBits(bv);
170 }
171 }
172
173 } // namespace tesseract
174