tesseract  5.0.0-alpha-619-ge9db
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 
21 
22 const int kPrimeLimit = 1000;
23 
24 namespace {
25 
26 class BitVectorTest : public testing::Test {
27  protected:
28  void SetUp() override {
29  std::locale::global(std::locale(""));
30  }
31 
32  public:
33  std::string OutputNameToPath(const std::string& name) {
34  return file::JoinPath(FLAGS_test_tmpdir, name);
35  }
36  // Computes primes up to kPrimeLimit, using the sieve of Eratosthenes.
37  void ComputePrimes(BitVector* map) {
38  map->Init(kPrimeLimit + 1);
39  TestAll(*map, false);
40  map->SetBit(2);
41  // Set all the odds to true.
42  for (int i = 3; i <= kPrimeLimit; i += 2) map->SetValue(i, true);
43  int factor_limit = static_cast<int>(sqrt(1.0 + kPrimeLimit));
44  for (int f = 3; f <= factor_limit; f += 2) {
45  if (map->At(f)) {
46  for (int m = 2; m * f <= kPrimeLimit; ++m) map->ResetBit(f * m);
47  }
48  }
49  }
50 
51  void TestPrimes(const BitVector& map) {
52  // Now all primes in the vector are true, and all others false.
53  // According to Wikipedia, there are 168 primes under 1000, the last
54  // of which is 997.
55  int total_primes = 0;
56  for (int i = 0; i <= kPrimeLimit; ++i) {
57  if (map[i]) ++total_primes;
58  }
59  EXPECT_EQ(168, total_primes);
60  EXPECT_TRUE(map[997]);
61  EXPECT_FALSE(map[998]);
62  EXPECT_FALSE(map[999]);
63  }
64  // Test that all bits in the vector have the given value.
65  void TestAll(const BitVector& map, bool value) {
66  for (int i = 0; i < map.size(); ++i) {
67  EXPECT_EQ(value, map[i]);
68  }
69  }
70 
71  // Sets up a BitVector with bit patterns for byte values in
72  // [start_byte, end_byte) positioned every spacing bytes (for spacing >= 1)
73  // with spacing-1 zero bytes in between the pattern bytes.
74  void SetBitPattern(int start_byte, int end_byte, int spacing, BitVector* bv) {
75  bv->Init((end_byte - start_byte) * 8 * spacing);
76  for (int byte_value = start_byte; byte_value < end_byte; ++byte_value) {
77  for (int bit = 0; bit < 8; ++bit) {
78  if (byte_value & (1 << bit))
79  bv->SetBit((byte_value - start_byte) * 8 * spacing + bit);
80  }
81  }
82  }
83 
84  // Expects that every return from NextSetBit is really set and that all others
85  // are really not set. Checks the return from NumSetBits also.
86  void ExpectCorrectBits(const BitVector& bv) {
87  int bit_index = -1;
88  int prev_bit_index = -1;
89  int num_bits_tested = 0;
90  while ((bit_index = bv.NextSetBit(bit_index)) >= 0) {
91  EXPECT_LT(bit_index, bv.size());
92  // All bits in between must be 0.
93  for (int i = prev_bit_index + 1; i < bit_index; ++i) {
94  EXPECT_EQ(0, bv[i]) << "i = " << i << " prev = " << prev_bit_index;
95  }
96  // This bit must be 1.
97  EXPECT_EQ(1, bv[bit_index]) << "Bit index = " << bit_index;
98  ++num_bits_tested;
99  prev_bit_index = bit_index;
100  }
101  // Check the bits between the last and the end.
102  for (int i = prev_bit_index + 1; i < bv.size(); ++i) {
103  EXPECT_EQ(0, bv[i]);
104  }
105  EXPECT_EQ(num_bits_tested, bv.NumSetBits());
106  }
107 };
108 
109 // Tests the sieve of Eratosthenes as a way of testing set/reset and I/O.
110 TEST_F(BitVectorTest, Primes) {
111  BitVector map;
112  ComputePrimes(&map);
113  TestPrimes(map);
114  // It still works if we use the copy constructor.
115  BitVector map2(map);
116  TestPrimes(map2);
117  // Or if we assign it.
118  BitVector map3;
119  map3 = map;
120  TestPrimes(map3);
121  // Test file i/o too.
122  std::string filename = OutputNameToPath("primesbitvector");
123  FILE* fp = fopen(filename.c_str(), "wb");
124  CHECK(fp != nullptr);
125  EXPECT_TRUE(map.Serialize(fp));
126  fclose(fp);
127  fp = fopen(filename.c_str(), "rb");
128  CHECK(fp != nullptr);
129  BitVector read_map;
130  EXPECT_TRUE(read_map.DeSerialize(false, fp));
131  fclose(fp);
132  TestPrimes(read_map);
133 }
134 
135 // Tests the many-to-one setup feature.
136 TEST_F(BitVectorTest, SetAll) {
137  // Test the default constructor and set/resetall.
138  BitVector map(42);
139  TestAll(map, false);
140  map.SetAllTrue();
141  TestAll(map, true);
142  map.SetAllFalse();
143  TestAll(map, false);
144 }
145 
146 // Tests the values in the tables offset_table_, next_table_, hamming_table_
147 // by setting all possible byte patterns and verifying that the NextSetBit and
148 // NumSetBits functions return the correct values.
149 TEST_F(BitVectorTest, TestNextSetBit) {
150  BitVector bv;
151  for (int spacing = 1; spacing <= 5; ++spacing) {
152  SetBitPattern(0, 256, spacing, &bv);
153  ExpectCorrectBits(bv);
154  }
155 }
156 
157 // Tests the values in hamming_table_ more thoroughly by setting single byte
158 // patterns for each byte individually.
159 TEST_F(BitVectorTest, TestNumSetBits) {
160  BitVector bv;
161  for (int byte = 0; byte < 256; ++byte) {
162  SetBitPattern(byte, byte + 1, 1, &bv);
163  ExpectCorrectBits(bv);
164  }
165 }
166 
167 } // namespace.
file::JoinPath
static std::string JoinPath(const std::string &s1, const std::string &s2)
Definition: include_gunit.h:43
string
std::string string
Definition: equationdetect_test.cc:21
tesseract::BitVector::SetBit
void SetBit(int index)
Definition: bitvector.h:69
tesseract::BitVector::SetAllFalse
void SetAllFalse()
Definition: bitvector.cpp:169
tesseract::BitVector::NumSetBits
int NumSetBits() const
Definition: bitvector.cpp:216
tesseract::BitVector::Init
void Init(int length)
Definition: bitvector.cpp:139
include_gunit.h
tesseract::TEST_F
TEST_F(EquationFinderTest, IdentifySpecialText)
Definition: equationdetect_test.cc:181
tesseract::BitVector::NextSetBit
int NextSetBit(int prev_bit) const
Definition: bitvector.cpp:178
tesseract::BitVector::Serialize
bool Serialize(FILE *fp) const
Definition: bitvector.cpp:145
tesseract::BitVector::ResetBit
void ResetBit(int index)
Definition: bitvector.h:72
CHECK
#define CHECK(test)
Definition: include_gunit.h:57
FLAGS_test_tmpdir
const char * FLAGS_test_tmpdir
Definition: include_gunit.h:20
tesseract::BitVector::SetValue
void SetValue(int index, bool value)
Definition: bitvector.h:75
bitvector.h
tesseract::BitVector
Definition: bitvector.h:30
kPrimeLimit
const int kPrimeLimit
Definition: bitvector_test.cc:22
tesseract::BitVector::At
bool At(int index) const
Definition: bitvector.h:81
tesseract::BitVector::size
int size() const
Definition: bitvector.h:53
tesseract::BitVector::DeSerialize
bool DeSerialize(bool swap, FILE *fp)
Definition: bitvector.cpp:153
tesseract::BitVector::SetAllTrue
void SetAllTrue()
Definition: bitvector.cpp:172