1#include "bitvector.h" 2#include "popcount.h" 3 4namespace marisa_alpha { 5namespace { 6 7const UInt8 SelectTable[8][256] = { 8 { 9 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 10 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 11 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 12 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 13 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 14 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 15 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 16 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 17 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 18 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 19 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 20 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 21 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 22 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 23 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 24 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 25 }, 26 { 27 7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, 28 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 29 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 30 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 31 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 32 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 33 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 34 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 35 7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, 36 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 37 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 38 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 39 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 40 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 41 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 42 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1 43 }, 44 { 45 7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2, 46 7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2, 47 7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2, 48 7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 49 7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2, 50 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2, 51 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2, 52 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 53 7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2, 54 7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2, 55 7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2, 56 7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2, 57 7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2, 58 7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2, 59 7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2, 60 6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2 61 }, 62 { 63 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 64 7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3, 65 7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3, 66 7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3, 67 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3, 68 7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3, 69 7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3, 70 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3, 71 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 72 7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3, 73 7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3, 74 7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3, 75 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3, 76 7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3, 77 7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3, 78 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3 79 }, 80 { 81 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 82 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 83 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 84 7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4, 85 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 86 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4, 87 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5, 88 7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4, 89 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 90 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 91 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 92 7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4, 93 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 94 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4, 95 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5, 96 7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4 97 }, 98 { 99 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 100 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 101 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 102 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 103 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 104 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 105 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 106 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5, 107 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 108 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 109 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 110 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 111 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 112 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 113 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 114 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5 115 }, 116 { 117 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 118 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 119 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 120 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 121 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 122 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 123 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 124 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 125 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 126 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 127 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 128 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 129 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 130 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 131 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 132 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6 133 }, 134 { 135 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 136 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 137 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 138 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 139 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 140 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 141 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 142 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 143 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 144 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 145 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 146 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 147 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 148 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 149 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 150 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 151 } 152}; 153 154} // namespace 155 156BitVector::BitVector() 157 : blocks_(), size_(0), ranks_(), select0s_(), select1s_() {} 158 159void BitVector::build() { 160 Vector<Rank> ranks; 161 const UInt32 num_blocks = (size_ / 512) + (((size_ % 512) != 0) ? 1 : 0); 162 ranks.resize(num_blocks + 1); 163 Vector<UInt32> select0s; 164 Vector<UInt32> select1s; 165 UInt32 num_0s = 0; 166 UInt32 num_1s = 0; 167 for (UInt32 i = 0; i < size_; ++i) { 168 if ((i % 64) == 0) { 169 UInt32 rank_id = i / 512; 170 switch ((i / 64) % 8) { 171 case 0: { 172 ranks[rank_id].set_abs(num_1s); 173 break; 174 } 175 case 1: { 176 ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs()); 177 break; 178 } 179 case 2: { 180 ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs()); 181 break; 182 } 183 case 3: { 184 ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs()); 185 break; 186 } 187 case 4: { 188 ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs()); 189 break; 190 } 191 case 5: { 192 ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs()); 193 break; 194 } 195 case 6: { 196 ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs()); 197 break; 198 } 199 case 7: { 200 ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs()); 201 break; 202 } 203 } 204 } 205 if ((*this)[i]) { 206 if ((num_1s % 512) == 0) { 207 select1s.push_back(i); 208 } 209 ++num_1s; 210 } else { 211 if ((num_0s % 512) == 0) { 212 select0s.push_back(i); 213 } 214 ++num_0s; 215 } 216 } 217 if ((size_ % 512) != 0) { 218 UInt32 rank_id = (size_ - 1) / 512; 219 switch (((size_ - 1) / 64) % 8) { 220 case 0: { 221 ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs()); 222 } 223 case 1: { 224 ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs()); 225 } 226 case 2: { 227 ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs()); 228 } 229 case 3: { 230 ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs()); 231 } 232 case 4: { 233 ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs()); 234 } 235 case 5: { 236 ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs()); 237 } 238 case 6: { 239 ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs()); 240 break; 241 } 242 } 243 } 244 ranks.back().set_abs(num_1s); 245 select0s.push_back(size_); 246 select1s.push_back(size_); 247 select0s.shrink(); 248 select1s.shrink(); 249 250 blocks_.shrink(); 251 ranks_.swap(&ranks); 252 select0s_.swap(&select0s); 253 select1s_.swap(&select1s); 254} 255 256void BitVector::mmap(Mapper *mapper, const char *filename, 257 long offset, int whence) { 258 MARISA_ALPHA_THROW_IF(mapper == NULL, MARISA_ALPHA_PARAM_ERROR); 259 Mapper temp_mapper; 260 temp_mapper.open(filename, offset, whence); 261 map(temp_mapper); 262 temp_mapper.swap(mapper); 263} 264 265void BitVector::map(const void *ptr, std::size_t size) { 266 Mapper mapper(ptr, size); 267 map(mapper); 268} 269 270void BitVector::map(Mapper &mapper) { 271 BitVector temp; 272 temp.blocks_.map(mapper); 273 mapper.map(&temp.size_); 274 temp.ranks_.map(mapper); 275 temp.select0s_.map(mapper); 276 temp.select1s_.map(mapper); 277 temp.swap(this); 278} 279 280void BitVector::load(const char *filename, 281 long offset, int whence) { 282 Reader reader; 283 reader.open(filename, offset, whence); 284 read(reader); 285} 286 287void BitVector::fread(std::FILE *file) { 288 Reader reader(file); 289 read(reader); 290} 291 292void BitVector::read(int fd) { 293 Reader reader(fd); 294 read(reader); 295} 296 297void BitVector::read(std::istream &stream) { 298 Reader reader(&stream); 299 read(reader); 300} 301 302void BitVector::read(Reader &reader) { 303 BitVector temp; 304 temp.blocks_.read(reader); 305 reader.read(&temp.size_); 306 temp.ranks_.read(reader); 307 temp.select0s_.read(reader); 308 temp.select1s_.read(reader); 309 temp.swap(this); 310} 311 312void BitVector::save(const char *filename, bool trunc_flag, 313 long offset, int whence) const { 314 Writer writer; 315 writer.open(filename, trunc_flag, offset, whence); 316 write(writer); 317} 318 319void BitVector::fwrite(std::FILE *file) const { 320 Writer writer(file); 321 write(writer); 322} 323 324void BitVector::write(int fd) const { 325 Writer writer(fd); 326 write(writer); 327} 328 329void BitVector::write(std::ostream &stream) const { 330 Writer writer(&stream); 331 write(writer); 332} 333 334void BitVector::write(Writer &writer) const { 335 blocks_.write(writer); 336 writer.write(size_); 337 ranks_.write(writer); 338 select0s_.write(writer); 339 select1s_.write(writer); 340} 341 342UInt32 BitVector::rank1(UInt32 i) const { 343 MARISA_ALPHA_DEBUG_IF(i > size_, MARISA_ALPHA_PARAM_ERROR); 344 const Rank &rank = ranks_[i / 512]; 345 UInt32 offset = rank.abs(); 346 switch ((i / 64) % 8) { 347 case 1: { 348 offset += rank.rel1(); 349 break; 350 } 351 case 2: { 352 offset += rank.rel2(); 353 break; 354 } 355 case 3: { 356 offset += rank.rel3(); 357 break; 358 } 359 case 4: { 360 offset += rank.rel4(); 361 break; 362 } 363 case 5: { 364 offset += rank.rel5(); 365 break; 366 } 367 case 6: { 368 offset += rank.rel6(); 369 break; 370 } 371 case 7: { 372 offset += rank.rel7(); 373 break; 374 } 375 } 376 switch ((i / 32) % 2) { 377 case 1: { 378 offset += PopCount(blocks_[(i / 32) - 1]).lo32(); 379 } 380 case 0: { 381 offset += PopCount(blocks_[i / 32] & ((1U << (i % 32)) - 1)).lo32(); 382 break; 383 } 384 } 385 return offset; 386} 387 388UInt32 BitVector::select0(UInt32 i) const { 389 UInt32 select_id = i / 512; 390 MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select0s_.size(), 391 MARISA_ALPHA_PARAM_ERROR); 392 if ((i % 512) == 0) { 393 return select0s_[select_id]; 394 } 395 UInt32 begin = select0s_[select_id] / 512; 396 UInt32 end = (select0s_[select_id + 1] + 511) / 512; 397 if (begin + 10 >= end) { 398 while (i >= ((begin + 1) * 512) - ranks_[begin + 1].abs()) { 399 ++begin; 400 } 401 } else { 402 while (begin + 1 < end) { 403 UInt32 middle = (begin + end) / 2; 404 if (i < (middle * 512) - ranks_[middle].abs()) { 405 end = middle; 406 } else { 407 begin = middle; 408 } 409 } 410 } 411 const UInt32 rank_id = begin; 412 i -= (rank_id * 512) - ranks_[rank_id].abs(); 413 414 const Rank &rank = ranks_[rank_id]; 415 UInt32 block_id = rank_id * 16; 416 if (i < (256U - rank.rel4())) { 417 if (i < (128U - rank.rel2())) { 418 if (i >= (64U - rank.rel1())) { 419 block_id += 2; 420 i -= 64 - rank.rel1(); 421 } 422 } else if (i < (192U - rank.rel3())) { 423 block_id += 4; 424 i -= 128 - rank.rel2(); 425 } else { 426 block_id += 6; 427 i -= 192 - rank.rel3(); 428 } 429 } else if (i < (384U - rank.rel6())) { 430 if (i < (320U - rank.rel5())) { 431 block_id += 8; 432 i -= 256 - rank.rel4(); 433 } else { 434 block_id += 10; 435 i -= 320 - rank.rel5(); 436 } 437 } else if (i < (448U - rank.rel7())) { 438 block_id += 12; 439 i -= 384 - rank.rel6(); 440 } else { 441 block_id += 14; 442 i -= 448 - rank.rel7(); 443 } 444 445 UInt32 block = ~blocks_[block_id]; 446 PopCount count(block); 447 if (i >= count.lo32()) { 448 ++block_id; 449 i -= count.lo32(); 450 block = ~blocks_[block_id]; 451 count = PopCount(block); 452 } 453 454 UInt32 bit_id = block_id * 32; 455 if (i < count.lo16()) { 456 if (i >= count.lo8()) { 457 bit_id += 8; 458 block >>= 8; 459 i -= count.lo8(); 460 } 461 } else if (i < count.lo24()) { 462 bit_id += 16; 463 block >>= 16; 464 i -= count.lo16(); 465 } else { 466 bit_id += 24; 467 block >>= 24; 468 i -= count.lo24(); 469 } 470 return bit_id + SelectTable[i][block & 0xFF]; 471} 472 473UInt32 BitVector::select1(UInt32 i) const { 474 UInt32 select_id = i / 512; 475 MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select1s_.size(), 476 MARISA_ALPHA_PARAM_ERROR); 477 if ((i % 512) == 0) { 478 return select1s_[select_id]; 479 } 480 UInt32 begin = select1s_[select_id] / 512; 481 UInt32 end = (select1s_[select_id + 1] + 511) / 512; 482 if (begin + 10 >= end) { 483 while (i >= ranks_[begin + 1].abs()) { 484 ++begin; 485 } 486 } else { 487 while (begin + 1 < end) { 488 UInt32 middle = (begin + end) / 2; 489 if (i < ranks_[middle].abs()) { 490 end = middle; 491 } else { 492 begin = middle; 493 } 494 } 495 } 496 const UInt32 rank_id = begin; 497 i -= ranks_[rank_id].abs(); 498 499 const Rank &rank = ranks_[rank_id]; 500 UInt32 block_id = rank_id * 16; 501 if (i < rank.rel4()) { 502 if (i < rank.rel2()) { 503 if (i >= rank.rel1()) { 504 block_id += 2; 505 i -= rank.rel1(); 506 } 507 } else if (i < rank.rel3()) { 508 block_id += 4; 509 i -= rank.rel2(); 510 } else { 511 block_id += 6; 512 i -= rank.rel3(); 513 } 514 } else if (i < rank.rel6()) { 515 if (i < rank.rel5()) { 516 block_id += 8; 517 i -= rank.rel4(); 518 } else { 519 block_id += 10; 520 i -= rank.rel5(); 521 } 522 } else if (i < rank.rel7()) { 523 block_id += 12; 524 i -= rank.rel6(); 525 } else { 526 block_id += 14; 527 i -= rank.rel7(); 528 } 529 530 UInt32 block = blocks_[block_id]; 531 PopCount count(block); 532 if (i >= count.lo32()) { 533 ++block_id; 534 i -= count.lo32(); 535 block = blocks_[block_id]; 536 count = PopCount(block); 537 } 538 539 UInt32 bit_id = block_id * 32; 540 if (i < count.lo16()) { 541 if (i >= count.lo8()) { 542 bit_id += 8; 543 block >>= 8; 544 i -= count.lo8(); 545 } 546 } else if (i < count.lo24()) { 547 bit_id += 16; 548 block >>= 16; 549 i -= count.lo16(); 550 } else { 551 bit_id += 24; 552 block >>= 24; 553 i -= count.lo24(); 554 } 555 return bit_id + SelectTable[i][block & 0xFF]; 556} 557 558void BitVector::clear() { 559 BitVector().swap(this); 560} 561 562void BitVector::swap(BitVector *rhs) { 563 MARISA_ALPHA_THROW_IF(rhs == NULL, MARISA_ALPHA_PARAM_ERROR); 564 blocks_.swap(&rhs->blocks_); 565 Swap(&size_, &rhs->size_); 566 ranks_.swap(&rhs->ranks_); 567 select0s_.swap(&rhs->select0s_); 568 select1s_.swap(&rhs->select1s_); 569} 570 571} // namespace marisa_alpha 572