← Back to branch summary

~ubuntu-branches/ubuntu/saucy/abyss/saucy

« back to all changes in this revision

Viewing changes to FMIndex/bit_array.cc

  • Committer: Package Import Robot
  • Author(s): Shaun Jackman
  • Date: 2011-09-11 10:00:13 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: package-import@ubuntu.com-20110911100013-oa4m5fi036mjuwc8
Tags: 1.3.0-1
* New upstream release.
* Add libboost-graph-dev to Build-Depends.

Show diffs side-by-side

added added

removed removed

Lines of Context:
FMIndex/bit_array.cc
 
1
/*
 
2
 *  Copyright (c) 2010 Daisuke Okanohara
 
3
 *
 
4
 *   Redistribution and use in source and binary forms, with or without
 
5
 *   modification, are permitted provided that the following conditions
 
6
 *   are met:
 
7
 *
 
8
 *   1. Redistributions of source code must retain the above Copyright
 
9
 *      notice, this list of conditions and the following disclaimer.
 
10
 *
 
11
 *   2. Redistributions in binary form must reproduce the above Copyright
 
12
 *      notice, this list of conditions and the following disclaimer in the
 
13
 *      documentation and/or other materials provided with the distribution.
 
14
 *
 
15
 *   3. Neither the name of the authors nor the names of its contributors
 
16
 *      may be used to endorse or promote products derived from this
 
17
 *      software without specific prior written permission.
 
18
 */
 
19
 
 
20
#include "config.h"
 
21
#include "bit_array.h"
 
22
#include <cassert>
 
23
 
 
24
namespace wat_array {
 
25
 
 
26
BitArray::BitArray() : length_(0), one_num_(0){
 
27
}
 
28
 
 
29
BitArray::BitArray(uint64_t length){
 
30
  Init(length);
 
31
}
 
32
 
 
33
BitArray::~BitArray(){
 
34
}
 
35
 
 
36
uint64_t BitArray::length() const {
 
37
  return length_;
 
38
}
 
39
 
 
40
uint64_t BitArray::one_num() const{
 
41
  return one_num_;
 
42
}
 
43
 
 
44
void BitArray::Init(uint64_t length){
 
45
  length_    = length;
 
46
  one_num_ = 0;
 
47
  uint64_t block_num = (length + BLOCK_BITNUM - 1) / BLOCK_BITNUM;
 
48
  bit_blocks_.resize(block_num);
 
49
}
 
50
 
 
51
void BitArray::Clear(){
 
52
  std::vector<uint64_t>().swap(bit_blocks_);
 
53
  std::vector<uint64_t>().swap(rank_tables_);
 
54
  length_ = 0;
 
55
  one_num_ = 0;
 
56
}
 
57
 
 
58
void BitArray::Build() {
 
59
  one_num_ = 0;
 
60
  uint64_t table_num = ((bit_blocks_.size() + TABLE_INTERVAL - 1) / TABLE_INTERVAL) + 1;
 
61
  rank_tables_.resize(table_num);
 
62
  for (size_t i = 0; i < bit_blocks_.size(); ++i){
 
63
    if ((i % TABLE_INTERVAL) == 0){
 
64
      rank_tables_[i/TABLE_INTERVAL] = one_num_;
 
65
    }
 
66
    one_num_ += PopCount(bit_blocks_[i]);
 
67
  }
 
68
  rank_tables_.back() = one_num_;
 
69
}
 
70
 
 
71
void BitArray::SetBit(uint64_t bit, uint64_t pos) {
 
72
  if (!bit) return;
 
73
  bit_blocks_[pos / BLOCK_BITNUM] |= (1LLU << (pos % BLOCK_BITNUM));
 
74
}
 
75
 
 
76
uint64_t BitArray::Rank(uint64_t bit, uint64_t pos) const {
 
77
  if (pos > length_) return NOTFOUND;
 
78
  if (bit) return RankOne(pos);
 
79
  else return pos - RankOne(pos);
 
80
}
 
81
 
 
82
uint64_t BitArray::Select(uint64_t bit, uint64_t rank) const {
 
83
  if (bit){
 
84
    if (rank > one_num_) return NOTFOUND;
 
85
  } else {
 
86
    if (rank > length_ - one_num_) return NOTFOUND;
 
87
  }
 
88
 
 
89
  uint64_t block_pos = SelectOutBlock(bit, rank);
 
90
  uint64_t block = (bit) ? bit_blocks_[block_pos] : ~bit_blocks_[block_pos];
 
91
  return block_pos * BLOCK_BITNUM + SelectInBlock(block, rank);
 
92
}
 
93
 
 
94
uint64_t BitArray::SelectOutBlock(uint64_t bit, uint64_t& rank) const {
 
95
  // binary search over tables
 
96
  uint64_t left = 0;
 
97
  uint64_t right = rank_tables_.size();
 
98
  while (left < right){
 
99
    uint64_t mid = (left + right) / 2;
 
100
    uint64_t length = BLOCK_BITNUM * TABLE_INTERVAL * mid;
 
101
    if (GetBitNum(rank_tables_[mid], length, bit) < rank) {
 
102
      left = mid+1;
 
103
    } else {
 
104
      right = mid;
 
105
    }
 
106
  }
 
107
 
 
108
  uint64_t table_ind   = (left != 0) ? left - 1: 0;
 
109
  uint64_t block_pos   = table_ind * TABLE_INTERVAL;
 
110
  rank -= GetBitNum(rank_tables_[table_ind],
 
111
                    block_pos * BLOCK_BITNUM,
 
112
                    bit);
 
113
 
 
114
  // sequential search over blocks
 
115
  for ( ; block_pos < bit_blocks_.size(); ++block_pos){
 
116
    uint64_t rank_next= GetBitNum(PopCount(bit_blocks_[block_pos]), BLOCK_BITNUM, bit);
 
117
    if (rank <= rank_next){
 
118
      break;
 
119
    }
 
120
    rank -= rank_next;
 
121
  }
 
122
  return block_pos;
 
123
}
 
124
 
 
125
uint64_t BitArray::SelectInBlock(uint64_t x, uint64_t rank) {
 
126
  uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);
 
127
  uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);
 
128
  uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;
 
129
 
 
130
  uint64_t pos = 0;
 
131
  for (;;  pos += 8){
 
132
    uint64_t rank_next = (x3 >> pos) & 0xFFLLU;
 
133
    if (rank <= rank_next) break;
 
134
    rank -= rank_next;
 
135
  }
 
136
 
 
137
  uint64_t v2 = (x2 >> pos) & 0xFLLU;
 
138
  if (rank > v2) {
 
139
    rank -= v2;
 
140
    pos += 4;
 
141
  }
 
142
 
 
143
  uint64_t v1 = (x1 >> pos) & 0x3LLU;
 
144
  if (rank > v1){
 
145
    rank -= v1;
 
146
    pos += 2;
 
147
  }
 
148
 
 
149
  uint64_t v0  = (x >> pos) & 0x1LLU;
 
150
  if (v0 < rank){
 
151
    rank -= v0;
 
152
    pos += 1;
 
153
  }
 
154
 
 
155
  return pos;
 
156
}
 
157
 
 
158
uint64_t BitArray::Lookup(uint64_t pos) const {
 
159
  return (bit_blocks_[pos / BLOCK_BITNUM] >> (pos % BLOCK_BITNUM)) & 1LLU;
 
160
}
 
161
 
 
162
 
 
163
uint64_t BitArray::RankOne(uint64_t pos) const {
 
164
  uint64_t block_ind = pos / BLOCK_BITNUM;
 
165
  uint64_t table_ind = block_ind / TABLE_INTERVAL;
 
166
  assert(table_ind < rank_tables_.size());
 
167
 
 
168
  uint64_t rank = rank_tables_[table_ind];
 
169
  for (uint64_t i = table_ind * TABLE_INTERVAL; i < block_ind; ++i){
 
170
    rank += PopCount(bit_blocks_[i]);
 
171
  }
 
172
  rank += PopCountMask(bit_blocks_[block_ind], pos % BLOCK_BITNUM);
 
173
  return rank;
 
174
}
 
175
 
 
176
/** Return the Hamming weight of x. */
 
177
uint64_t BitArray::PopCount(uint64_t x)
 
178
{
 
179
#if ENABLE_POPCNT && __GNUC__ && __x86_64__
 
180
  __asm__("popcnt %1,%0" : "=r" (x) : "r" (x));
 
181
  return x;
 
182
#else
 
183
  x = (x & 0x5555555555555555ULL) +
 
184
    ((x >> 1) & 0x5555555555555555ULL);
 
185
  x = (x & 0x3333333333333333ULL) +
 
186
    ((x >> 2) & 0x3333333333333333ULL);
 
187
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
 
188
  x = x + (x >>  8);
 
189
  x = x + (x >> 16);
 
190
  x = x + (x >> 32);
 
191
  return x & 0x7FLLU;
 
192
#endif
 
193
}
 
194
 
 
195
uint64_t BitArray::PopCountMask(uint64_t x, uint64_t offset) {
 
196
  if (offset == 0) return 0;
 
197
  return PopCount(x & ((1LLU << offset) - 1));
 
198
}
 
199
 
 
200
uint64_t BitArray::GetBitNum(uint64_t one_num, uint64_t num, uint64_t bit) {
 
201
  if (bit) return one_num;
 
202
  else return num - one_num;
 
203
}
 
204
 
 
205
void BitArray::PrintForDebug(std::ostream& os) const {
 
206
  for (uint64_t i = 0; i < length_;  ++i){
 
207
    if (Lookup(i)) os << "1";
 
208
    else           os << "0";
 
209
    if (((i+1) % 8) == 0) {
 
210
      os << " ";
 
211
    }
 
212
  }
 
213
}
 
214
 
 
215
void BitArray::Save(std::ostream& os) const{
 
216
  os.write((const char*)(&length_), sizeof(length_));
 
217
  os.write((const char*)(&bit_blocks_[0]), sizeof(bit_blocks_[0]) * bit_blocks_.size());
 
218
}
 
219
 
 
220
void BitArray::Load(std::istream& is){
 
221
  Clear();
 
222
  is.read((char*)(&length_), sizeof(length_));
 
223
  Init(length_);
 
224
  is.read((char*)(&bit_blocks_[0]), sizeof(bit_blocks_[0]) * bit_blocks_.size());
 
225
  Build();
 
226
}
 
227
 
 
228
 
 
229
}