tesseract v5.3.3.20231005
Public Member Functions | Static Public Attributes | List of all members
tesseract::BitVector Class Reference

#include <bitvector.h>

Public Member Functions

 BitVector ()=default
 
 BitVector (int length)
 
 BitVector (const BitVector &src)
 
BitVector & operator= (const BitVector &src)
 
 ~BitVector ()=default
 
void Init (int length)
 
int empty () const
 
int size () const
 
bool Serialize (FILE *fp) const
 
bool DeSerialize (bool swap, FILE *fp)
 
void SetAllFalse ()
 
void SetAllTrue ()
 
void SetBit (int index)
 
void ResetBit (int index)
 
void SetValue (int index, bool value)
 
bool At (int index) const
 
bool operator[] (int index) const
 
int NextSetBit (int prev_bit) const
 
int NumSetBits () const
 
void operator|= (const BitVector &other)
 
void operator&= (const BitVector &other)
 
void operator^= (const BitVector &other)
 
void SetSubtract (const BitVector &v1, const BitVector &v2)
 

Static Public Attributes

static const uint8_t lsb_index_ [256]
 
static const uint8_t lsb_eroded_ [256]
 
static const int hamming_table_ [256]
 

Detailed Description

Definition at line 33 of file bitvector.h.

Constructor & Destructor Documentation

◆ BitVector() [1/3]

tesseract::BitVector::BitVector ( )
default

◆ BitVector() [2/3]

tesseract::BitVector::BitVector ( int  length)
inlineexplicit

Definition at line 47 of file bitvector.h.

47 : bit_size_(length), array_(WordLength()) {
48 }

◆ BitVector() [3/3]

tesseract::BitVector::BitVector ( const BitVector &  src)
inline

Definition at line 49 of file bitvector.h.

49 : bit_size_(src.bit_size_), array_(src.array_) {
50 }

◆ ~BitVector()

tesseract::BitVector::~BitVector ( )
default

Member Function Documentation

◆ At()

bool tesseract::BitVector::At ( int  index) const
inline

Definition at line 91 of file bitvector.h.

91 {
92 return (array_[WordIndex(index)] & BitMask(index)) != 0;
93 }

◆ DeSerialize()

bool tesseract::BitVector::DeSerialize ( bool  swap,
FILE *  fp 
)

Definition at line 97 of file bitvector.cpp.

97 {
98 uint32_t new_bit_size;
99 if (!tesseract::DeSerialize(fp, &new_bit_size)) {
100 return false;
101 }
102 if (swap) {
103 ReverseN(&new_bit_size, sizeof(new_bit_size));
104 }
105 Alloc(new_bit_size);
106 int wordlen = WordLength();
107 if (!tesseract::DeSerialize(fp, &array_[0], wordlen)) {
108 return false;
109 }
110 if (swap) {
111 for (int i = 0; i < wordlen; ++i) {
112 ReverseN(&array_[i], sizeof(array_[i]));
113 }
114 }
115 return true;
116}
tesseract::ReverseN
void ReverseN(void *ptr, int num_bytes)
Definition: helpers.h:184
tesseract::DeSerialize
bool DeSerialize(bool swap, FILE *fp, std::vector< T > &data)
Definition: helpers.h:205

◆ empty()

int tesseract::BitVector::empty ( ) const
inline

Definition at line 57 of file bitvector.h.

57 {
58 return bit_size_ == 0;
59 }

◆ Init()

void tesseract::BitVector::Init ( int  length)

Definition at line 81 of file bitvector.cpp.

81 {
82 Alloc(length);
83 SetAllFalse();
84}

◆ NextSetBit()

int tesseract::BitVector::NextSetBit ( int  prev_bit) const

Definition at line 127 of file bitvector.cpp.

127 {
128 // Move on to the next bit.
129 int next_bit = prev_bit + 1;
130 if (next_bit >= bit_size_) {
131 return -1;
132 }
133 // Check the remains of the word containing the next_bit first.
134 int next_word = WordIndex(next_bit);
135 int bit_index = next_word * kBitFactor;
136 int word_end = bit_index + kBitFactor;
137 uint32_t word = array_[next_word];
138 uint8_t byte = word & 0xff;
139 while (bit_index < word_end) {
140 if (bit_index + 8 > next_bit && byte != 0) {
141 while (bit_index + lsb_index_[byte] < next_bit && byte != 0) {
142 byte = lsb_eroded_[byte];
143 }
144 if (byte != 0) {
145 return bit_index + lsb_index_[byte];
146 }
147 }
148 word >>= 8;
149 bit_index += 8;
150 byte = word & 0xff;
151 }
152 // next_word didn't contain a 1, so find the next word with set bit.
153 ++next_word;
154 int wordlen = WordLength();
155 while (next_word < wordlen && (word = array_[next_word]) == 0) {
156 ++next_word;
157 bit_index += kBitFactor;
158 }
159 if (bit_index >= bit_size_) {
160 return -1;
161 }
162 // Find the first non-zero byte within the word.
163 while ((word & 0xff) == 0) {
164 word >>= 8;
165 bit_index += 8;
166 }
167 return bit_index + lsb_index_[word & 0xff];
168}
tesseract::BitVector::lsb_index_
static const uint8_t lsb_index_[256]
Definition: bitvector.h:38
tesseract::BitVector::lsb_eroded_
static const uint8_t lsb_eroded_[256]
Definition: bitvector.h:41

◆ NumSetBits()

int tesseract::BitVector::NumSetBits ( ) const

Definition at line 171 of file bitvector.cpp.

171 {
172 int wordlen = WordLength();
173 int total_bits = 0;
174 for (int w = 0; w < wordlen; ++w) {
175 uint32_t word = array_[w];
176 for (int i = 0; i < 4; ++i) {
177 total_bits += hamming_table_[word & 0xff];
178 word >>= 8;
179 }
180 }
181 return total_bits;
182}
tesseract::BitVector::hamming_table_
static const int hamming_table_[256]
Definition: bitvector.h:43

◆ operator&=()

void tesseract::BitVector::operator&= ( const BitVector &  other)

Definition at line 192 of file bitvector.cpp.

192 {
193 int length = std::min(WordLength(), other.WordLength());
194 for (int w = 0; w < length; ++w) {
195 array_[w] &= other.array_[w];
196 }
197 for (int w = WordLength() - 1; w >= length; --w) {
198 array_[w] = 0;
199 }
200}

◆ operator=()

BitVector & tesseract::BitVector::operator= ( const BitVector &  src)

Definition at line 74 of file bitvector.cpp.

74 {
75 array_ = src.array_;
76 bit_size_ = src.bit_size_;
77 return *this;
78}

◆ operator[]()

bool tesseract::BitVector::operator[] ( int  index) const
inline

Definition at line 94 of file bitvector.h.

94 {
95 return (array_[WordIndex(index)] & BitMask(index)) != 0;
96 }

◆ operator^=()

void tesseract::BitVector::operator^= ( const BitVector &  other)

Definition at line 201 of file bitvector.cpp.

201 {
202 int length = std::min(WordLength(), other.WordLength());
203 for (int w = 0; w < length; ++w) {
204 array_[w] ^= other.array_[w];
205 }
206}

◆ operator|=()

void tesseract::BitVector::operator|= ( const BitVector &  other)

Definition at line 186 of file bitvector.cpp.

186 {
187 int length = std::min(WordLength(), other.WordLength());
188 for (int w = 0; w < length; ++w) {
189 array_[w] |= other.array_[w];
190 }
191}

◆ ResetBit()

void tesseract::BitVector::ResetBit ( int  index)
inline

Definition at line 81 of file bitvector.h.

81 {
82 array_[WordIndex(index)] &= ~BitMask(index);
83 }

◆ Serialize()

bool tesseract::BitVector::Serialize ( FILE *  fp) const

Definition at line 87 of file bitvector.cpp.

87 {
88 if (!tesseract::Serialize(fp, &bit_size_)) {
89 return false;
90 }
91 int wordlen = WordLength();
92 return tesseract::Serialize(fp, &array_[0], wordlen);
93}
tesseract::Serialize
bool Serialize(FILE *fp, const std::vector< T > &data)
Definition: helpers.h:236

◆ SetAllFalse()

void tesseract::BitVector::SetAllFalse ( )

Definition at line 118 of file bitvector.cpp.

118 {
119 memset(&array_[0], 0, ByteLength());
120}

◆ SetAllTrue()

void tesseract::BitVector::SetAllTrue ( )

Definition at line 121 of file bitvector.cpp.

121 {
122 memset(&array_[0], ~0, ByteLength());
123}

◆ SetBit()

void tesseract::BitVector::SetBit ( int  index)
inline

Definition at line 78 of file bitvector.h.

78 {
79 array_[WordIndex(index)] |= BitMask(index);
80 }

◆ SetSubtract()

void tesseract::BitVector::SetSubtract ( const BitVector &  v1,
const BitVector &  v2 
)

Definition at line 208 of file bitvector.cpp.

208 {
209 Alloc(v1.size());
210 int length = std::min(v1.WordLength(), v2.WordLength());
211 for (int w = 0; w < length; ++w) {
212 array_[w] = v1.array_[w] ^ (v1.array_[w] & v2.array_[w]);
213 }
214 for (int w = WordLength() - 1; w >= length; --w) {
215 array_[w] = v1.array_[w];
216 }
217}

◆ SetValue()

void tesseract::BitVector::SetValue ( int  index,
bool  value 
)
inline

Definition at line 84 of file bitvector.h.

84 {
85 if (value) {
86 SetBit(index);
87 } else {
88 ResetBit(index);
89 }
90 }
value
int value
Definition: gmock-matchers_test.cc:664
tesseract::BitVector::SetBit
void SetBit(int index)
Definition: bitvector.h:78
tesseract::BitVector::ResetBit
void ResetBit(int index)
Definition: bitvector.h:81

◆ size()

int tesseract::BitVector::size ( ) const
inline

Definition at line 62 of file bitvector.h.

62 {
63 return bit_size_;
64 }

Member Data Documentation

◆ hamming_table_

const int tesseract::BitVector::hamming_table_
static
Initial value:
= {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}

Definition at line 43 of file bitvector.h.

◆ lsb_eroded_

const uint8_t tesseract::BitVector::lsb_eroded_
static
Initial value:
= {
0, 0, 0, 0x2, 0, 0x4, 0x4, 0x6, 0, 0x8, 0x8, 0x0a, 0x08, 0x0c, 0x0c, 0x0e,
0, 0x10, 0x10, 0x12, 0x10, 0x14, 0x14, 0x16, 0x10, 0x18, 0x18, 0x1a, 0x18, 0x1c, 0x1c, 0x1e,
0, 0x20, 0x20, 0x22, 0x20, 0x24, 0x24, 0x26, 0x20, 0x28, 0x28, 0x2a, 0x28, 0x2c, 0x2c, 0x2e,
0x20, 0x30, 0x30, 0x32, 0x30, 0x34, 0x34, 0x36, 0x30, 0x38, 0x38, 0x3a, 0x38, 0x3c, 0x3c, 0x3e,
0, 0x40, 0x40, 0x42, 0x40, 0x44, 0x44, 0x46, 0x40, 0x48, 0x48, 0x4a, 0x48, 0x4c, 0x4c, 0x4e,
0x40, 0x50, 0x50, 0x52, 0x50, 0x54, 0x54, 0x56, 0x50, 0x58, 0x58, 0x5a, 0x58, 0x5c, 0x5c, 0x5e,
0x40, 0x60, 0x60, 0x62, 0x60, 0x64, 0x64, 0x66, 0x60, 0x68, 0x68, 0x6a, 0x68, 0x6c, 0x6c, 0x6e,
0x60, 0x70, 0x70, 0x72, 0x70, 0x74, 0x74, 0x76, 0x70, 0x78, 0x78, 0x7a, 0x78, 0x7c, 0x7c, 0x7e,
0, 0x80, 0x80, 0x82, 0x80, 0x84, 0x84, 0x86, 0x80, 0x88, 0x88, 0x8a, 0x88, 0x8c, 0x8c, 0x8e,
0x80, 0x90, 0x90, 0x92, 0x90, 0x94, 0x94, 0x96, 0x90, 0x98, 0x98, 0x9a, 0x98, 0x9c, 0x9c, 0x9e,
0x80, 0xa0, 0xa0, 0xa2, 0xa0, 0xa4, 0xa4, 0xa6, 0xa0, 0xa8, 0xa8, 0xaa, 0xa8, 0xac, 0xac, 0xae,
0xa0, 0xb0, 0xb0, 0xb2, 0xb0, 0xb4, 0xb4, 0xb6, 0xb0, 0xb8, 0xb8, 0xba, 0xb8, 0xbc, 0xbc, 0xbe,
0x80, 0xc0, 0xc0, 0xc2, 0xc0, 0xc4, 0xc4, 0xc6, 0xc0, 0xc8, 0xc8, 0xca, 0xc8, 0xcc, 0xcc, 0xce,
0xc0, 0xd0, 0xd0, 0xd2, 0xd0, 0xd4, 0xd4, 0xd6, 0xd0, 0xd8, 0xd8, 0xda, 0xd8, 0xdc, 0xdc, 0xde,
0xc0, 0xe0, 0xe0, 0xe2, 0xe0, 0xe4, 0xe4, 0xe6, 0xe0, 0xe8, 0xe8, 0xea, 0xe8, 0xec, 0xec, 0xee,
0xe0, 0xf0, 0xf0, 0xf2, 0xf0, 0xf4, 0xf4, 0xf6, 0xf0, 0xf8, 0xf8, 0xfa, 0xf8, 0xfc, 0xfc, 0xfe}

Definition at line 41 of file bitvector.h.

◆ lsb_index_

const uint8_t tesseract::BitVector::lsb_index_
static
Initial value:
= {
255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1,
0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1,
0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}

Definition at line 38 of file bitvector.h.

The documentation for this class was generated from the following files: