tesseract  5.0.0
bitvector_test.cc
Go to the documentation of this file.
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:
26  void SetUp() override {
27  std::locale::global(std::locale(""));
29  }
30 
31 public:
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.
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 
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.
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.
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.
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.
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.
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.
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.
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
const int kPrimeLimit
TEST_F(EuroText, FastLatinOCR)
void Init(int length)
Definition: bitvector.cpp:81
void SetValue(int index, bool value)
Definition: bitvector.h:84
bool At(int index) const
Definition: bitvector.h:91
void SetBit(int index)
Definition: bitvector.h:78
int NumSetBits() const
Definition: bitvector.cpp:171
bool DeSerialize(bool swap, FILE *fp)
Definition: bitvector.cpp:97
int NextSetBit(int prev_bit) const
Definition: bitvector.cpp:127
int size() const
Definition: bitvector.h:62
void ResetBit(int index)
Definition: bitvector.h:81
bool Serialize(FILE *fp) const
Definition: bitvector.cpp:87
std::string OutputNameToPath(const std::string &name)
void ComputePrimes(BitVector *map)
void TestPrimes(const BitVector &map)
void TestAll(const BitVector &map, bool value)
void ExpectCorrectBits(const BitVector &bv)
void SetBitPattern(int start_byte, int end_byte, int spacing, BitVector *bv)
static void MakeTmpdir()
Definition: include_gunit.h:38
static std::string JoinPath(const std::string &s1, const std::string &s2)
Definition: include_gunit.h:65