18 #ifndef FST_EXTENSIONS_NGRAM_BITMAP_INDEX_H_ 19 #define FST_EXTENSIONS_NGRAM_BITMAP_INDEX_H_ 104 bool enable_select_0_index =
false,
105 bool enable_select_1_index =
false) {
106 BuildIndex(bits, num_bits, enable_select_0_index, enable_select_1_index);
109 bool Get(
size_t index)
const {
return Get(bits_, index); }
111 static bool Get(
const uint64_t* bits,
size_t index) {
113 (
kOne << (index & kStorageBlockMask))) != 0;
116 static void Set(uint64_t* bits,
size_t index) {
120 static void Clear(uint64_t* bits,
size_t index) {
124 size_t Bits()
const {
return num_bits_; }
133 return (rank_index_.size() *
sizeof(rank_index_[0]) +
134 select_0_index_.size() *
sizeof(select_0_index_[0]) +
135 select_1_index_.size() *
sizeof(select_1_index_[0]));
141 return rank_index_.back().absolute_ones_count();
146 size_t Rank1(
size_t end)
const;
154 size_t Select1(
size_t bit_index)
const;
158 size_t Select0(
size_t bit_index)
const;
162 std::pair<size_t, size_t>
Select0s(
size_t bit_index)
const;
167 void BuildIndex(
const uint64_t* bits,
size_t num_bits,
168 bool enable_select_0_index =
false,
169 bool enable_select_1_index =
false);
171 static constexpr uint64_t
kOne = 1;
176 static constexpr uint32_t kUnitsPerRankIndexEntry = 8;
177 static constexpr uint32_t kBitsPerRankIndexEntry =
179 static constexpr uint32_t kStorageBlockMask = kStorageBitSize - 1;
184 static constexpr uint32_t kBitsPerSelect0Block = 512;
185 static constexpr uint32_t kBitsPerSelect1Block = 512;
195 static constexpr uint32_t kMaxLinearSearchBlocks = 8;
204 class RankIndexEntry {
206 RankIndexEntry() =
default;
208 uint32_t absolute_ones_count()
const {
return absolute_ones_count_; }
211 uint32_t relative_ones_count(
size_t k)
const {
214 const uint32_t c = k < 4 ? 0 : relative_ones_count_4_;
218 uint32_t relative_ones_counts_8x4 =
219 UnalignedLoad<uint32_t>(&relative_ones_counts_[k >> 2][0] - 1);
220 #if ((defined __ORDER_LITTLE_ENDIAN__) || (defined _WIN32)) 222 relative_ones_counts_8x4 &= ~0xFF;
223 return c + ((relative_ones_counts_8x4 >> (8 * (k & 3))) & 0xFF);
225 #error "Big-endian currently unsupported." 229 uint32_t relative_ones_count_1()
const {
230 return relative_ones_counts_[0][0];
232 uint32_t relative_ones_count_2()
const {
233 return relative_ones_counts_[0][1];
235 uint32_t relative_ones_count_3()
const {
236 return relative_ones_counts_[0][2];
238 uint32_t relative_ones_count_4()
const {
return relative_ones_count_4_; }
239 uint32_t relative_ones_count_5()
const {
240 return relative_ones_count_4() + relative_ones_counts_[1][0];
242 uint32_t relative_ones_count_6()
const {
243 return relative_ones_count_4() + relative_ones_counts_[1][1];
245 uint32_t relative_ones_count_7()
const {
246 return relative_ones_count_4() + relative_ones_counts_[1][2];
249 void set_absolute_ones_count(uint32_t v) { absolute_ones_count_ = v; }
250 void set_relative_ones_count_1(uint32_t v) {
252 relative_ones_counts_[0][0] = v;
254 void set_relative_ones_count_2(uint32_t v) {
256 relative_ones_counts_[0][1] = v;
258 void set_relative_ones_count_3(uint32_t v) {
260 relative_ones_counts_[0][2] = v;
262 void set_relative_ones_count_4(uint32_t v) {
264 DCHECK_EQ(relative_ones_counts_[1][0], 0);
265 DCHECK_EQ(relative_ones_counts_[1][1], 0);
266 DCHECK_EQ(relative_ones_counts_[1][2], 0);
267 relative_ones_count_4_ = v;
269 void set_relative_ones_count_5(uint32_t v) {
271 relative_ones_counts_[1][0] = v - relative_ones_count_4();
273 void set_relative_ones_count_6(uint32_t v) {
275 relative_ones_counts_[1][1] = v - relative_ones_count_4();
277 void set_relative_ones_count_7(uint32_t v) {
279 relative_ones_counts_[1][2] = v - relative_ones_count_4();
285 uint32_t absolute_ones_count_ = 0;
318 uint16_t relative_ones_count_4_ = 0;
319 uint8_t relative_ones_counts_[2][3] = {{0, 0, 0}, {0, 0, 0}};
321 static_assert(
sizeof(RankIndexEntry) == 4 + 8,
322 "RankIndexEntry should be 12 bytes.");
325 uint32_t GetIndexOnesCount(
size_t array_index)
const;
329 const RankIndexEntry& FindRankIndexEntry(
size_t bit_index)
const;
333 const RankIndexEntry& FindInvertedRankIndexEntry(
size_t bit_index)
const;
337 size_t rank_index_size()
const {
338 return (
ArraySize() + kUnitsPerRankIndexEntry - 1) /
339 kUnitsPerRankIndexEntry +
343 const uint64_t* bits_ =
nullptr;
344 size_t num_bits_ = 0;
346 std::vector<RankIndexEntry> rank_index_;
353 std::vector<uint32_t> select_0_index_;
360 std::vector<uint32_t> select_1_index_;
365 #endif // FST_EXTENSIONS_NGRAM_BITMAP_INDEX_H_
BitmapIndex & operator=(BitmapIndex &&)=default
static void Clear(uint64_t *bits, size_t index)
static constexpr uint32_t kStorageBitSize
static void Set(uint64_t *bits, size_t index)
void BuildIndex(const uint64_t *bits, size_t num_bits, bool enable_select_0_index=false, bool enable_select_1_index=false)
size_t Select1(size_t bit_index) const
static constexpr uint64_t kOne
BitmapIndex(const uint64_t *bits, std::size_t num_bits, bool enable_select_0_index=false, bool enable_select_1_index=false)
size_t Rank1(size_t end) const
size_t Select0(size_t bit_index) const
size_t GetOnesCount() const
static size_t StorageSize(size_t num_bits)
size_t ArrayBytes() const
bool Get(size_t index) const
std::pair< size_t, size_t > Select0s(size_t bit_index) const
static bool Get(const uint64_t *bits, size_t index)
size_t IndexBytes() const
size_t Rank0(size_t end) const
static constexpr uint32_t kStorageLogBitSize