00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef BMFUNC__H__INCLUDED__
00028 #define BMFUNC__H__INCLUDED__
00029
00030 #include <memory.h>
00031
00032
00033 #ifdef _MSC_VER
00034 # pragma warning( disable: 4146 )
00035 #endif
00036
00037 namespace bm
00038 {
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058 template<bool T> struct gap_len_table
00059 {
00060 static const gap_word_t _len[bm::gap_levels];
00061 };
00062
00063 template<bool T>
00064 const gap_word_t gap_len_table<T>::_len[bm::gap_levels] =
00065 { 128, 256, 512, bm::gap_max_buff_len };
00066
00067
00068
00069
00070
00071
00072
00073 template<bool T> struct gap_len_table_min
00074 {
00075 static const gap_word_t _len[bm::gap_levels];
00076 };
00077
00078 template<bool T>
00079 const gap_word_t gap_len_table_min<T>::_len[bm::gap_levels] =
00080 { 32, 96, 128, 512 };
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090 template<bool T> struct bit_count_table
00091 {
00092 static const unsigned char _count[256];
00093 };
00094
00095 template<bool T>
00096 const unsigned char bit_count_table<T>::_count[256] = {
00097 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,
00098 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,
00099 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,
00100 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,
00101 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,
00102 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,
00103 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,
00104 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
00105 };
00106
00107
00108
00109
00110
00111
00112 template<bool T> struct block_set_table
00113 {
00114 static const unsigned _left[32];
00115 static const unsigned _right[32];
00116 };
00117
00118 template<bool T>
00119 const unsigned block_set_table<T>::_left[32] = {
00120 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff,
00121 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff,
00122 0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff,
00123 0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
00124 };
00125
00126 template<bool T>
00127 const unsigned block_set_table<T>::_right[32] = {
00128 0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8, 0xfffffff0,
00129 0xffffffe0, 0xffffffc0, 0xffffff80, 0xffffff00, 0xfffffe00,
00130 0xfffffc00, 0xfffff800, 0xfffff000, 0xffffe000, 0xffffc000,
00131 0xffff8000, 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
00132 0xfff00000, 0xffe00000, 0xffc00000, 0xff800000, 0xff000000,
00133 0xfe000000, 0xfc000000, 0xf8000000, 0xf0000000, 0xe0000000,
00134 0xc0000000, 0x80000000
00135 };
00136
00137
00138
00139
00140
00141
00142 template<bool T> struct first_bit_table
00143 {
00144 static const char _idx[256];
00145 };
00146
00147 template<bool T>
00148 const char first_bit_table<T>::_idx[256] = {
00149 -1,
00150 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,
00151 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,
00152 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,
00153 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,
00154 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,
00155 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,
00156 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,
00157 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,
00158 3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
00159 };
00160
00161
00162
00163
00164
00165
00166
00167 #define BM_INCWORD_BITCOUNT(cnt, w) cnt += \
00168 bm::bit_count_table<true>::_count[(unsigned char)(w)] + \
00169 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 8)] + \
00170 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 16)] + \
00171 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 24)];
00172
00173 #ifdef BM64OPT
00174
00175
00176
00177
00178 inline bm::id_t word_bitcount64(bm::id64_t w)
00179 {
00180 w = (w & 0x5555555555555555LU) + (w >> 1 & 0x5555555555555555LU);
00181 w = (w & 0x3333333333333333LU) + (w >> 2 & 0x3333333333333333LU);
00182 w = w + (w >> 4) & 0x0F0F0F0F0F0F0F0FLU;
00183 w = w + (w >> 8);
00184 w = w + (w >> 16);
00185 w = w + (w >> 32) & 0x0000007F;
00186 return (bm::id_t)w;
00187 }
00188 #endif
00189
00190
00191
00192
00193
00194
00195
00196
00197 enum operation
00198 {
00199 BM_AND = 0,
00200 BM_OR,
00201 BM_SUB,
00202 BM_XOR
00203 };
00204
00205
00206
00207
00208
00209
00210
00211 template<bool T> struct all_set
00212 {
00213 struct all_set_block
00214 {
00215 bm::word_t _p[bm::set_block_size];
00216
00217 all_set_block()
00218 {
00219 ::memset(_p, 0xFF, sizeof(_p));
00220 }
00221 };
00222
00223 static all_set_block _block;
00224 };
00225
00226
00227 template<bool T> typename all_set<T>::all_set_block all_set<T>::_block;
00228
00229
00230 template<typename W>
00231 void xor_swap(W& x, W& y)
00232 {
00233 BM_ASSERT(&x != &y);
00234 x ^= y;
00235 y ^= x;
00236 x ^= y;
00237 }
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251 template<typename T> int wordcmp0(T w1, T w2)
00252 {
00253 while (w1 != w2)
00254 {
00255 int res = (w1 & 1) - (w2 & 1);
00256 if (res != 0) return res;
00257 w1 >>= 1;
00258 w2 >>= 1;
00259 }
00260 return 0;
00261 }
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280
00281 template<typename T> int wordcmp(T a, T b)
00282 {
00283 T diff = a ^ b;
00284 return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
00285 }
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295 template<bool T> struct _copyright
00296 {
00297 static const char _p[];
00298 };
00299
00300 template<bool T> const char _copyright<T>::_p[] =
00301 "BitMagic Library. v.3.4.0 (c) 2002-2006 Anatoliy Kuznetsov.";
00302
00303
00304
00305
00306
00307 enum ByteOrder
00308 {
00309 BigEndian = 0,
00310 LittleEndian = 1
00311 };
00312
00313
00314
00315
00316
00317 template<bool T> struct globals
00318 {
00319 struct bo
00320 {
00321 ByteOrder _byte_order;
00322
00323 bo()
00324 {
00325 unsigned x;
00326 unsigned char *s = (unsigned char *)&x;
00327 s[0] = 1;
00328 s[1] = 2;
00329 s[2] = 3;
00330 s[3] = 4;
00331
00332 if(x == 0x04030201)
00333 {
00334 _byte_order = LittleEndian;
00335 return;
00336 }
00337
00338 if(x == 0x01020304)
00339 {
00340 _byte_order = BigEndian;
00341 return;
00342 }
00343
00344 BM_ASSERT(0);
00345 _byte_order = LittleEndian;
00346 }
00347 };
00348
00349 static bo _bo;
00350
00351 static ByteOrder byte_order() { return _bo._byte_order; }
00352
00353 };
00354
00355 template<bool T> typename globals<T>::bo globals<T>::_bo;
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 template<typename T>
00371 unsigned gap_bfind(const T* buf, unsigned pos, unsigned* is_set)
00372 {
00373 BM_ASSERT(pos < bm::gap_max_bits);
00374 *is_set = (*buf) & 1;
00375
00376 register unsigned start = 1;
00377 register unsigned end = 1 + ((*buf) >> 3);
00378
00379 while ( start != end )
00380 {
00381 unsigned curr = (start + end) >> 1;
00382 if ( buf[curr] < pos )
00383 start = curr + 1;
00384 else
00385 end = curr;
00386 }
00387 *is_set ^= ((start-1) & 1);
00388 return start;
00389 }
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399 template<typename T> unsigned gap_test(const T* buf, unsigned pos)
00400 {
00401 BM_ASSERT(pos < bm::gap_max_bits);
00402
00403 unsigned start = 1;
00404 unsigned end = 1 + ((*buf) >> 3);
00405
00406 if (end - start < 10)
00407 {
00408 unsigned sv = *buf & 1;
00409 unsigned sv1= sv ^ 1;
00410 if (buf[1] >= pos) return sv;
00411 if (buf[2] >= pos) return sv1;
00412 if (buf[3] >= pos) return sv;
00413 if (buf[4] >= pos) return sv1;
00414 if (buf[5] >= pos) return sv;
00415 if (buf[6] >= pos) return sv1;
00416 if (buf[7] >= pos) return sv;
00417 if (buf[8] >= pos) return sv1;
00418 if (buf[9] >= pos) return sv;
00419 BM_ASSERT(0);
00420 }
00421 else
00422 while ( start != end )
00423 {
00424 unsigned curr = (start + end) >> 1;
00425 if ( buf[curr] < pos )
00426 start = curr + 1;
00427 else
00428 end = curr;
00429 }
00430 return ((*buf) & 1) ^ ((--start) & 1);
00431 }
00432
00433
00434
00435
00436 template<class T, class F>
00437 void for_each_nzblock(T*** root, unsigned size1, unsigned size2, F& f)
00438 {
00439 unsigned block_idx = 0;
00440
00441 for (unsigned i = 0; i < size1; ++i)
00442 {
00443 T** blk_blk = root[i];
00444
00445 if (!blk_blk)
00446 {
00447 block_idx += bm::set_array_size;
00448 continue;
00449 }
00450
00451 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00452 {
00453 if (blk_blk[j]) f(blk_blk[j], block_idx);
00454 }
00455 }
00456 }
00457
00458
00459
00460
00461 template<class T, class F>
00462 bool for_each_nzblock_if(T*** root, unsigned size1, unsigned size2, F& f)
00463 {
00464 unsigned block_idx = 0;
00465
00466 for (unsigned i = 0; i < size1; ++i)
00467 {
00468 T** blk_blk = root[i];
00469
00470 if (!blk_blk)
00471 {
00472 block_idx += bm::set_array_size;
00473 continue;
00474 }
00475
00476 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00477 {
00478 if (blk_blk[j])
00479 if (f(blk_blk[j], block_idx)) return true;
00480 }
00481 }
00482 return false;
00483 }
00484
00485
00486
00487 template<class T, class F>
00488 void for_each_block(T*** root, unsigned size1, unsigned size2, F& f)
00489 {
00490 unsigned block_idx = 0;
00491
00492 for (unsigned i = 0; i < size1; ++i)
00493 {
00494 T** blk_blk = root[i];
00495
00496 if (blk_blk)
00497 {
00498 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00499 {
00500 f(blk_blk[j], block_idx);
00501 }
00502 }
00503 else
00504 {
00505 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00506 {
00507 f(0, block_idx);
00508 }
00509 }
00510 }
00511 }
00512
00513
00514
00515
00516
00517 template<class T, class F> F bmfor_each(T first, T last, F f)
00518 {
00519 do
00520 {
00521 f(*first);
00522 ++first;
00523 } while (first < last);
00524 return f;
00525 }
00526
00527
00528
00529 template<class T> T sum_arr(T* first, T* last)
00530 {
00531 T sum = 0;
00532 while (first < last)
00533 {
00534 sum += *first;
00535 ++first;
00536 }
00537 return sum;
00538 }
00539
00540
00541
00542
00543
00544
00545
00546
00547 template<typename T> unsigned gap_bit_count(const T* buf)
00548 {
00549 register const T* pcurr = buf;
00550 register const T* pend = pcurr + (*pcurr >> 3);
00551
00552 register unsigned bits_counter = 0;
00553 ++pcurr;
00554
00555 if (*buf & 1)
00556 {
00557 bits_counter += *pcurr + 1;
00558 ++pcurr;
00559 }
00560 ++pcurr;
00561
00562 while (pcurr <= pend)
00563 {
00564 bits_counter += *pcurr - *(pcurr-1);
00565 pcurr += 2;
00566 }
00567
00568 return bits_counter;
00569 }
00570
00571
00572
00573
00574
00575
00576
00577
00578 template<typename T>
00579 unsigned gap_bit_count_range(const T* buf, T left, T right)
00580 {
00581 BM_ASSERT(left <= right);
00582
00583 const T* pcurr = buf;
00584 const T* pend = pcurr + (*pcurr >> 3);
00585
00586 unsigned bits_counter = 0;
00587 unsigned is_set;
00588 unsigned start_pos = gap_bfind(buf, left, &is_set);
00589
00590 pcurr = buf + start_pos;
00591 if (right <= *pcurr)
00592 {
00593 if (is_set)
00594 bits_counter = (right - left + 1);
00595 return bits_counter;
00596 }
00597 if (is_set)
00598 bits_counter += *pcurr - left + 1;
00599
00600 unsigned prev_gap = *pcurr++;
00601 is_set ^= 1;
00602 while (right > *pcurr)
00603 {
00604 if (is_set)
00605 bits_counter += *pcurr - prev_gap;
00606 if (pcurr == pend)
00607 return bits_counter;
00608 prev_gap = *pcurr++;
00609 is_set ^= 1;
00610 }
00611 if (is_set)
00612 bits_counter += right - prev_gap;
00613
00614 return bits_counter;
00615 }
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627 template<typename T> int gapcmp(const T* buf1, const T* buf2)
00628 {
00629 const T* pcurr1 = buf1;
00630 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
00631 unsigned bitval1 = *buf1 & 1;
00632 ++pcurr1;
00633
00634 const T* pcurr2 = buf2;
00635 unsigned bitval2 = *buf2 & 1;
00636 ++pcurr2;
00637
00638 while (pcurr1 <= pend1)
00639 {
00640 if (*pcurr1 == *pcurr2)
00641 {
00642 if (bitval1 != bitval2)
00643 {
00644 return (bitval1) ? 1 : -1;
00645 }
00646 }
00647 else
00648 {
00649 if (bitval1 == bitval2)
00650 {
00651 if (bitval1)
00652 {
00653 return (*pcurr1 < *pcurr2) ? -1 : 1;
00654 }
00655 else
00656 {
00657 return (*pcurr1 < *pcurr2) ? 1 : -1;
00658 }
00659 }
00660 else
00661 {
00662 return (bitval1) ? 1 : -1;
00663 }
00664 }
00665
00666 ++pcurr1; ++pcurr2;
00667
00668 bitval1 ^= 1;
00669 bitval2 ^= 1;
00670 }
00671
00672 return 0;
00673 }
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690 template<typename T, class F>
00691 void gap_buff_op(T* BMRESTRICT dest,
00692 const T* BMRESTRICT vect1,
00693 unsigned vect1_mask,
00694 const T* BMRESTRICT vect2,
00695 unsigned vect2_mask,
00696 F f)
00697 {
00698 register const T* cur1 = vect1;
00699 register const T* cur2 = vect2;
00700
00701 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
00702 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
00703
00704 unsigned bitval = f(bitval1, bitval2);
00705 unsigned bitval_prev = bitval;
00706
00707 register T* res = dest;
00708 *res = bitval;
00709 ++res;
00710
00711 while (1)
00712 {
00713 bitval = f(bitval1, bitval2);
00714
00715
00716
00717 if (bitval != bitval_prev)
00718 {
00719 ++res;
00720 bitval_prev = bitval;
00721 }
00722
00723 if (*cur1 < *cur2)
00724 {
00725 *res = *cur1;
00726 ++cur1;
00727 bitval1 ^= 1;
00728 }
00729 else
00730 {
00731 *res = *cur2;
00732 if (*cur2 < *cur1)
00733 {
00734 bitval2 ^= 1;
00735 }
00736 else
00737 {
00738 if (*cur2 == (bm::gap_max_bits - 1))
00739 {
00740 break;
00741 }
00742
00743 ++cur1;
00744 bitval1 ^= 1;
00745 bitval2 ^= 1;
00746 }
00747 ++cur2;
00748 }
00749
00750 }
00751
00752 unsigned dlen = (unsigned)(res - dest);
00753 *dest = (*dest & 7) + (dlen << 3);
00754
00755 }
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805
00806
00807
00808
00809
00810
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830
00831
00832
00833
00834
00835
00836
00837
00838
00839
00840
00841
00842
00843 template<typename T> unsigned gap_set_value(unsigned val,
00844 T* BMRESTRICT buf,
00845 unsigned pos,
00846 unsigned* BMRESTRICT is_set)
00847 {
00848 BM_ASSERT(pos < bm::gap_max_bits);
00849 unsigned curr = gap_bfind(buf, pos, is_set);
00850
00851 register T end = (*buf >> 3);
00852 if (*is_set == val)
00853 {
00854 *is_set = 0;
00855 return end;
00856 }
00857 *is_set = 1;
00858
00859 register T* pcurr = buf + curr;
00860 register T* pprev = pcurr - 1;
00861 register T* pend = buf + end;
00862
00863
00864
00865 if (pos == 0)
00866 {
00867 *buf ^= 1;
00868 if ( buf[1] )
00869 {
00870 ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
00871 buf[1] = 0;
00872 ++end;
00873 }
00874 else
00875 {
00876 pprev = buf + 1;
00877 pcurr = pprev + 1;
00878 do
00879 {
00880 *pprev++ = *pcurr++;
00881 } while (pcurr < pend);
00882 --end;
00883 }
00884 }
00885 else if (curr > 1 && ((unsigned)(*pprev))+1 == pos)
00886 {
00887 ++(*pprev);
00888 if (*pprev == *pcurr)
00889 {
00890 --end;
00891 if (pcurr != pend)
00892 {
00893 --end;
00894 ++pcurr;
00895 do
00896 {
00897 *pprev++ = *pcurr++;
00898 } while (pcurr < pend);
00899 }
00900 }
00901 }
00902 else if (*pcurr == pos)
00903 {
00904 --(*pcurr);
00905 if (pcurr == pend)
00906 {
00907 ++end;
00908 }
00909 }
00910 else
00911 {
00912 ::memmove(pcurr+2, pcurr,(end - curr + 1)*sizeof(T));
00913 *pcurr++ = pos - 1;
00914 *pcurr = pos;
00915 end+=2;
00916 }
00917
00918
00919 *buf = (*buf & 7) + (end << 3);
00920
00921 buf[end] = bm::gap_max_bits - 1;
00922 return end;
00923 }
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935 template<typename T> int gap_find_in_block(const T* buf,
00936 unsigned nbit,
00937 bm::id_t* prev)
00938 {
00939 BM_ASSERT(nbit < bm::gap_max_bits);
00940
00941 unsigned bitval;
00942 unsigned gap_idx = bm::gap_bfind(buf, nbit, &bitval);
00943
00944 if (bitval)
00945 {
00946 return 1;
00947 }
00948
00949 register unsigned val = buf[gap_idx] + 1;
00950 *prev += val - nbit;
00951
00952 return (val != bm::gap_max_bits);
00953 }
00954
00955
00956
00957
00958
00959
00960
00961
00962
00963
00964
00965 inline void or_bit_block(unsigned* dest,
00966 unsigned bitpos,
00967 unsigned bitcount)
00968 {
00969 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
00970 unsigned nword = unsigned(nbit >> bm::set_word_shift);
00971 nbit &= bm::set_word_mask;
00972
00973 bm::word_t* word = dest + nword;
00974
00975 if (bitcount == 1)
00976 {
00977 *word |= unsigned(1 << nbit);
00978 return;
00979 }
00980
00981 if (nbit)
00982 {
00983 unsigned right_margin = nbit + bitcount;
00984
00985
00986
00987
00988 if (right_margin < 32)
00989 {
00990 unsigned mask =
00991 block_set_table<true>::_right[nbit] &
00992 block_set_table<true>::_left[right_margin-1];
00993 *word |= mask;
00994 return;
00995 }
00996 else
00997 {
00998 *word |= block_set_table<true>::_right[nbit];
00999 bitcount -= 32 - nbit;
01000 }
01001 ++word;
01002 }
01003
01004
01005
01006
01007 for ( ;bitcount >= 32; bitcount -= 32)
01008 {
01009 *word++ = 0xffffffff;
01010 }
01011
01012 if (bitcount)
01013 {
01014 *word |= block_set_table<true>::_left[bitcount-1];
01015 }
01016 }
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027 inline void sub_bit_block(unsigned* dest,
01028 unsigned bitpos,
01029 unsigned bitcount)
01030 {
01031 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01032 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01033 nbit &= bm::set_word_mask;
01034
01035 bm::word_t* word = dest + nword;
01036
01037 if (bitcount == 1)
01038 {
01039 *word &= ~unsigned(1 << nbit);
01040 return;
01041 }
01042
01043 if (nbit)
01044 {
01045 unsigned right_margin = nbit + bitcount;
01046
01047
01048
01049
01050 if (right_margin < 32)
01051 {
01052 unsigned mask =
01053 block_set_table<true>::_right[nbit] &
01054 block_set_table<true>::_left[right_margin-1];
01055 *word &= ~mask;
01056 return;
01057 }
01058 else
01059 {
01060 *word &= ~block_set_table<true>::_right[nbit];
01061 bitcount -= 32 - nbit;
01062 }
01063 ++word;
01064 }
01065
01066
01067
01068
01069 for ( ;bitcount >= 32; bitcount -= 32)
01070 {
01071 *word++ = 0;
01072 }
01073
01074 if (bitcount)
01075 {
01076 *word &= ~block_set_table<true>::_left[bitcount-1];
01077 }
01078 }
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089 inline void xor_bit_block(unsigned* dest,
01090 unsigned bitpos,
01091 unsigned bitcount)
01092 {
01093 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01094 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01095 nbit &= bm::set_word_mask;
01096
01097 bm::word_t* word = dest + nword;
01098
01099 if (bitcount == 1)
01100 {
01101 *word ^= unsigned(1 << nbit);
01102 return;
01103 }
01104
01105 if (nbit)
01106 {
01107 unsigned right_margin = nbit + bitcount;
01108
01109
01110
01111
01112 if (right_margin < 32)
01113 {
01114 unsigned mask =
01115 block_set_table<true>::_right[nbit] &
01116 block_set_table<true>::_left[right_margin-1];
01117 *word ^= mask;
01118 return;
01119 }
01120 else
01121 {
01122 *word ^= block_set_table<true>::_right[nbit];
01123 bitcount -= 32 - nbit;
01124 }
01125 ++word;
01126 }
01127
01128
01129
01130
01131 for ( ;bitcount >= 32; bitcount -= 32)
01132 {
01133 *word++ ^= 0xffffffff;
01134 }
01135
01136 if (bitcount)
01137 {
01138 *word ^= block_set_table<true>::_left[bitcount-1];
01139 }
01140 }
01141
01142
01143
01144
01145
01146
01147
01148
01149
01150 template<typename T>
01151 void gap_sub_to_bitset(unsigned* dest, const T* buf)
01152 {
01153 register const T* pcurr = buf;
01154 register const T* pend = pcurr + (*pcurr >> 3);
01155 ++pcurr;
01156
01157 if (*buf & 1)
01158 {
01159 sub_bit_block(dest, 0, *pcurr + 1);
01160 ++pcurr;
01161 }
01162 ++pcurr;
01163
01164 while (pcurr <= pend)
01165 {
01166 unsigned bitpos = *(pcurr-1) + 1;
01167 BM_ASSERT(*pcurr > *(pcurr-1));
01168 unsigned gap_len = *pcurr - *(pcurr-1);
01169 sub_bit_block(dest, bitpos, gap_len);
01170 pcurr += 2;
01171 }
01172 }
01173
01174
01175
01176
01177
01178
01179
01180
01181
01182 template<typename T>
01183 void gap_xor_to_bitset(unsigned* dest, const T* buf)
01184 {
01185 register const T* pcurr = buf;
01186 register const T* pend = pcurr + (*pcurr >> 3);
01187 ++pcurr;
01188
01189 if (*buf & 1)
01190 {
01191 xor_bit_block(dest, 0, *pcurr + 1);
01192 ++pcurr;
01193 }
01194 ++pcurr;
01195
01196 while (pcurr <= pend)
01197 {
01198 unsigned bitpos = *(pcurr-1) + 1;
01199 BM_ASSERT(*pcurr > *(pcurr-1));
01200 unsigned gap_len = *pcurr - *(pcurr-1);
01201 xor_bit_block(dest, bitpos, gap_len);
01202 pcurr += 2;
01203 }
01204 }
01205
01206
01207
01208
01209
01210
01211
01212
01213
01214 template<typename T>
01215 void gap_add_to_bitset(unsigned* dest, const T* buf)
01216 {
01217 register const T* pcurr = buf;
01218 register const T* pend = pcurr + (*pcurr >> 3);
01219 ++pcurr;
01220
01221 if (*buf & 1)
01222 {
01223 or_bit_block(dest, 0, *pcurr + 1);
01224 ++pcurr;
01225 }
01226 ++pcurr;
01227
01228 while (pcurr <= pend)
01229 {
01230 unsigned bitpos = *(pcurr-1) + 1;
01231 BM_ASSERT(*pcurr > *(pcurr-1));
01232 unsigned gap_len = *pcurr - *(pcurr-1);
01233 or_bit_block(dest, bitpos, gap_len);
01234 pcurr += 2;
01235 }
01236 }
01237
01238
01239
01240
01241
01242
01243
01244
01245
01246 template<typename T>
01247 void gap_and_to_bitset(unsigned* dest, const T* buf)
01248 {
01249 register const T* pcurr = buf;
01250 register const T* pend = pcurr + (*pcurr >> 3);
01251 ++pcurr;
01252
01253 if (! (*buf & 1) )
01254 {
01255
01256 sub_bit_block(dest, 0, *pcurr + 1);
01257 ++pcurr;
01258 }
01259 ++pcurr;
01260
01261 while (pcurr <= pend)
01262 {
01263 unsigned bitpos = *(pcurr-1) + 1;
01264 BM_ASSERT(*pcurr > *(pcurr-1));
01265 unsigned gap_len = *pcurr - *(pcurr-1);
01266 sub_bit_block(dest, bitpos, gap_len);
01267 pcurr += 2;
01268 }
01269 }
01270
01271
01272
01273
01274
01275
01276
01277
01278
01279 template<typename T>
01280 bm::id_t gap_bitset_and_count(const unsigned* block, const T* buf)
01281 {
01282 BM_ASSERT(block);
01283
01284 register const T* pcurr = buf;
01285 register const T* pend = pcurr + (*pcurr >> 3);
01286 ++pcurr;
01287
01288 bm::id_t count = 0;
01289
01290 if (*buf & 1)
01291 {
01292 count += bit_block_calc_count_range(block, 0, *pcurr);
01293 ++pcurr;
01294 }
01295 ++pcurr;
01296
01297 while (pcurr <= pend)
01298 {
01299 bm::id_t c = bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01300
01301 count += c;
01302 pcurr += 2;
01303 }
01304 return count;
01305 }
01306
01307
01308
01309
01310
01311
01312
01313
01314
01315 template<typename T>
01316 bm::id_t gap_bitset_sub_count(const unsigned* block, const T* buf)
01317 {
01318 BM_ASSERT(block);
01319
01320 register const T* pcurr = buf;
01321 register const T* pend = pcurr + (*pcurr >> 3);
01322 ++pcurr;
01323
01324 bm::id_t count = 0;
01325
01326 if (!(*buf & 1))
01327 {
01328 count += bit_block_calc_count_range(block, 0, *pcurr);
01329 ++pcurr;
01330 }
01331 ++pcurr;
01332
01333 for (;pcurr <= pend; pcurr+=2)
01334 {
01335 count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01336 }
01337 return count;
01338 }
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349 template<typename T>
01350 bm::id_t gap_bitset_xor_count(const unsigned* block, const T* buf)
01351 {
01352 BM_ASSERT(block);
01353
01354 register const T* pcurr = buf;
01355 register const T* pend = pcurr + (*pcurr >> 3);
01356 ++pcurr;
01357
01358 unsigned bitval = *buf & 1;
01359
01360 register bm::id_t count = bit_block_calc_count_range(block, 0, *pcurr);
01361 if (bitval)
01362 {
01363 count = *pcurr + 1 - count;
01364 }
01365
01366 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01367 {
01368 T prev = *(pcurr-1)+1;
01369 bm::id_t c = bit_block_calc_count_range(block, prev, *pcurr);
01370
01371 if (bitval)
01372 {
01373 c = (*pcurr - prev + 1) - c;
01374 }
01375
01376 count += c;
01377 }
01378 return count;
01379 }
01380
01381
01382
01383
01384
01385
01386
01387
01388
01389 template<typename T>
01390 bm::id_t gap_bitset_or_count(const unsigned* block, const T* buf)
01391 {
01392 BM_ASSERT(block);
01393
01394 register const T* pcurr = buf;
01395 register const T* pend = pcurr + (*pcurr >> 3);
01396 ++pcurr;
01397
01398 unsigned bitval = *buf & 1;
01399
01400 register bm::id_t count;
01401 if (bitval)
01402 {
01403 count = *pcurr + 1;
01404 }
01405 else
01406 {
01407 count = bit_block_calc_count_range(block, 0, *pcurr);
01408 }
01409
01410 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01411 {
01412 T prev = *(pcurr-1)+1;
01413 bm::id_t c;
01414
01415 if (bitval)
01416 {
01417 c = (*pcurr - prev + 1);
01418 }
01419 else
01420 {
01421 c = bit_block_calc_count_range(block, prev, *pcurr);
01422 }
01423
01424 count += c;
01425 }
01426 return count;
01427 }
01428
01429
01430
01431
01432
01433
01434
01435
01436
01437 inline
01438 void bit_block_set(bm::word_t* BMRESTRICT dst, bm::word_t value)
01439 {
01440
01441
01442
01443 ::memset(dst, value, bm::set_block_size * sizeof(bm::word_t));
01444
01445 }
01446
01447
01448
01449
01450
01451
01452
01453
01454
01455 template<typename T>
01456 void gap_convert_to_bitset(unsigned* dest, const T* buf)
01457 {
01458 bit_block_set(dest, 0);
01459 gap_add_to_bitset(dest, buf);
01460 }
01461
01462
01463
01464
01465
01466
01467
01468
01469
01470
01471 template<typename T>
01472 void gap_convert_to_bitset(unsigned* dest, const T* buf, unsigned dest_len)
01473 {
01474 ::memset(dest, 0, dest_len * sizeof(unsigned));
01475 gap_add_to_bitset(dest, buf);
01476 }
01477
01478
01479
01480
01481
01482
01483
01484
01485
01486
01487
01488
01489
01490
01491
01492 template<typename T>
01493 unsigned* gap_convert_to_bitset_smart(unsigned* dest,
01494 const T* buf,
01495 id_t set_max)
01496 {
01497 if (buf[1] == set_max - 1)
01498 {
01499 return (buf[0] & 1) ? FULL_BLOCK_ADDR : 0;
01500 }
01501
01502 gap_convert_to_bitset(dest, buf);
01503 return dest;
01504 }
01505
01506
01507
01508
01509
01510
01511
01512
01513
01514
01515 template<typename T> unsigned gap_control_sum(const T* buf)
01516 {
01517 unsigned end = *buf >> 3;
01518
01519 register const T* pcurr = buf;
01520 register const T* pend = pcurr + (*pcurr >> 3);
01521 ++pcurr;
01522
01523 if (*buf & 1)
01524 {
01525 ++pcurr;
01526 }
01527 ++pcurr;
01528
01529 while (pcurr <= pend)
01530 {
01531 BM_ASSERT(*pcurr > *(pcurr-1));
01532 pcurr += 2;
01533 }
01534 return buf[end];
01535
01536 }
01537
01538
01539
01540
01541
01542
01543
01544
01545
01546 template<class T> void gap_set_all(T* buf,
01547 unsigned set_max,
01548 unsigned value)
01549 {
01550 BM_ASSERT(value == 0 || value == 1);
01551 *buf = (*buf & 6u) + (1u << 3) + value;
01552 *(++buf) = set_max - 1;
01553 }
01554
01555
01556
01557
01558
01559
01560
01561
01562
01563
01564
01565
01566 template<class T>
01567 void gap_init_range_block(T* buf,
01568 unsigned from,
01569 unsigned to,
01570 unsigned value,
01571 unsigned set_max)
01572 {
01573 BM_ASSERT(value == 0 || value == 1);
01574
01575 unsigned gap_len;
01576 if (from == 0)
01577 {
01578 if (to == set_max - 1)
01579 {
01580 gap_set_all(buf, set_max, value);
01581 }
01582 else
01583 {
01584 gap_len = 2;
01585 buf[1] = to;
01586 buf[2] = set_max - 1;
01587 buf[0] = (*buf & 6u) + (gap_len << 3) + value;
01588 }
01589 return;
01590 }
01591
01592
01593 value = !value;
01594 if (to == set_max - 1)
01595 {
01596 gap_len = 2;
01597 buf[1] = from - 1;
01598 buf[2] = set_max - 1;
01599 }
01600 else
01601 {
01602 gap_len = 3;
01603 buf[1] = from - 1;
01604 buf[2] = to;
01605 buf[3] = set_max - 1;
01606 }
01607 buf[0] = (*buf & 6u) + (gap_len << 3) + value;
01608 }
01609
01610
01611
01612
01613
01614
01615
01616
01617 template<typename T> void gap_invert(T* buf)
01618 {
01619 *buf ^= 1;
01620 }
01621
01622
01623
01624
01625
01626
01627
01628
01629
01630
01631
01632
01633
01634
01635
01636
01637
01638
01639
01640
01641
01642
01643
01644
01645
01646
01647
01648 template<typename T>
01649 bool gap_is_all_zero(const T* buf, unsigned set_max)
01650 {
01651 return (((*buf & 1)==0) && (*(++buf) == set_max - 1));
01652 }
01653
01654
01655
01656
01657
01658
01659
01660
01661
01662 template<typename T>
01663 bool gap_is_all_one(const T* buf, unsigned set_max)
01664 {
01665 return ((*buf & 1) && (*(++buf) == set_max - 1));
01666 }
01667
01668
01669
01670
01671
01672
01673
01674
01675 template<typename T> unsigned gap_length(const T* buf)
01676 {
01677 return (*buf >> 3) + 1;
01678 }
01679
01680
01681
01682
01683
01684
01685
01686
01687
01688 template<typename T>
01689 unsigned gap_capacity(const T* buf, const T* glevel_len)
01690 {
01691 return glevel_len[(*buf >> 1) & 3];
01692 }
01693
01694
01695
01696
01697
01698
01699
01700
01701
01702
01703 template<typename T>
01704 unsigned gap_limit(const T* buf, const T* glevel_len)
01705 {
01706 return glevel_len[(*buf >> 1) & 3]-4;
01707 }
01708
01709
01710
01711
01712
01713
01714
01715
01716
01717 template<typename T> unsigned gap_level(const T* buf)
01718 {
01719 return (*buf >> 1) & 3;
01720 }
01721
01722
01723
01724
01725
01726
01727
01728
01729
01730 template<typename T> void set_gap_level(T* buf,
01731 unsigned level)
01732 {
01733 BM_ASSERT(level < bm::gap_levels);
01734 *buf = ((level & 3) << 1) | (*buf & 1) | (*buf & ~7);
01735 }
01736
01737
01738
01739
01740
01741
01742
01743
01744
01745
01746 template<typename T>
01747 inline int gap_calc_level(int len, const T* glevel_len)
01748 {
01749 if (len <= (glevel_len[0]-4)) return 0;
01750 if (len <= (glevel_len[1]-4)) return 1;
01751 if (len <= (glevel_len[2]-4)) return 2;
01752 if (len <= (glevel_len[3]-4)) return 3;
01753
01754 BM_ASSERT(bm::gap_levels == 4);
01755 return -1;
01756 }
01757
01758
01759
01760
01761
01762
01763
01764
01765
01766
01767 template<typename T>
01768 inline unsigned gap_free_elements(const T* buf, const T* glevel_len)
01769 {
01770 unsigned len = gap_length(buf);
01771 unsigned capacity = gap_capacity(buf, glevel_len);
01772 return capacity - len;
01773 }
01774
01775
01776
01777
01778
01779
01780
01781
01782
01783
01784
01785 template<typename T>
01786 int bitcmp(const T* buf1, const T* buf2, unsigned len)
01787 {
01788 BM_ASSERT(len);
01789
01790 const T* pend1 = buf1 + len;
01791 do
01792 {
01793 T w1 = *buf1++;
01794 T w2 = *buf2++;
01795 T diff = w1 ^ w2;
01796
01797 if (diff)
01798 {
01799 return (w1 & diff & -diff) ? 1 : -1;
01800 }
01801
01802 } while (buf1 < pend1);
01803
01804 return 0;
01805 }
01806
01807
01808
01809
01810
01811
01812
01813
01814
01815
01816
01817
01818
01819 template<typename T>
01820 unsigned bit_convert_to_gap(T* BMRESTRICT dest,
01821 const unsigned* BMRESTRICT src,
01822 bm::id_t bits,
01823 unsigned dest_len)
01824 {
01825 register T* BMRESTRICT pcurr = dest;
01826 T* BMRESTRICT end = dest + dest_len;
01827 register int bitval = (*src) & 1;
01828 *pcurr |= bitval;
01829
01830 ++pcurr;
01831 *pcurr = 0;
01832 register unsigned bit_idx = 0;
01833 register int bitval_next;
01834
01835 unsigned val = *src;
01836
01837 do
01838 {
01839
01840
01841 while (val == 0 || val == 0xffffffff)
01842 {
01843 bitval_next = val ? 1 : 0;
01844 if (bitval != bitval_next)
01845 {
01846 *pcurr++ = bit_idx-1;
01847 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
01848 if (pcurr >= end)
01849 {
01850 return 0;
01851 }
01852 bitval = bitval_next;
01853 }
01854 bit_idx += sizeof(*src) * 8;
01855 if (bit_idx >= bits)
01856 {
01857 goto complete;
01858 }
01859 ++src;
01860 val = *src;
01861 }
01862
01863
01864 register unsigned mask = 1;
01865 while (mask)
01866 {
01867
01868
01869 bitval_next = val & mask ? 1 : 0;
01870 if (bitval != bitval_next)
01871 {
01872 *pcurr++ = bit_idx-1;
01873 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
01874 bitval = bitval_next;
01875 if (pcurr >= end)
01876 {
01877 return 0;
01878 }
01879 }
01880
01881 mask <<= 1;
01882 ++bit_idx;
01883
01884 }
01885
01886 if (bit_idx >= bits)
01887 {
01888 goto complete;
01889 }
01890
01891 ++src;
01892 val = *src;
01893
01894 } while(1);
01895
01896 complete:
01897 *pcurr = bit_idx-1;
01898 unsigned len = (unsigned)(pcurr - dest);
01899 *dest = (*dest & 7) + (len << 3);
01900 return len;
01901 }
01902
01903
01904
01905
01906
01907
01908 template<typename D, typename T>
01909 D gap_convert_to_arr(D* BMRESTRICT dest,
01910 const T* BMRESTRICT buf,
01911 unsigned dest_len)
01912 {
01913 register const T* BMRESTRICT pcurr = buf;
01914 register const T* pend = pcurr + (*pcurr >> 3);
01915
01916 D* BMRESTRICT dest_curr = dest;
01917 ++pcurr;
01918
01919 if (*buf & 1)
01920 {
01921 if (unsigned(*pcurr + 1) >= dest_len)
01922 return 0;
01923 dest_len -= *pcurr;
01924 T to = *pcurr;
01925 for (T i = 0; ;++i)
01926 {
01927 *dest_curr++ = i;
01928 if (i == to) break;
01929 }
01930 ++pcurr;
01931 }
01932 ++pcurr;
01933
01934 while (pcurr <= pend)
01935 {
01936 unsigned pending = *pcurr - *(pcurr-1);
01937 if (pending >= dest_len)
01938 return 0;
01939 dest_len -= pending;
01940 T from = *(pcurr-1)+1;
01941 T to = *pcurr;
01942 for (T i = from; ;++i)
01943 {
01944 *dest_curr++ = i;
01945 if (i == to) break;
01946 }
01947 pcurr += 2;
01948 }
01949 return (D) (dest_curr - dest);
01950 }
01951
01952
01953
01954
01955
01956 template<typename T> T bit_convert_to_arr(T* BMRESTRICT dest,
01957 const unsigned* BMRESTRICT src,
01958 bm::id_t bits,
01959 unsigned dest_len)
01960 {
01961 register T* BMRESTRICT pcurr = dest;
01962 T* BMRESTRICT end = dest + dest_len;
01963 register unsigned bit_idx = 0;
01964
01965 do
01966 {
01967 register unsigned val = *src;
01968
01969
01970 while (val == 0)
01971 {
01972 bit_idx += sizeof(*src) * 8;
01973 if (bit_idx >= bits)
01974 {
01975 return (T)(pcurr - dest);
01976 }
01977 val = *(++src);
01978 }
01979
01980 if (pcurr + sizeof(val)*8 > end)
01981 {
01982 return 0;
01983 }
01984
01985 for (int i = 0; i < 32; i+=4)
01986 {
01987 if (val & 1)
01988 *pcurr++ = bit_idx;
01989 val >>= 1; ++bit_idx;
01990 if (val & 1)
01991 *pcurr++ = bit_idx;
01992 val >>= 1; ++bit_idx;
01993 if (val & 1)
01994 *pcurr++ = bit_idx;
01995 val >>= 1; ++bit_idx;
01996 if (val & 1)
01997 *pcurr++ = bit_idx;
01998 val >>= 1; ++bit_idx;
01999 }
02000 if (bits <= bit_idx)
02001 break;
02002
02003 val = *(++src);
02004
02005 } while (1);
02006
02007 return (T)(pcurr - dest);
02008 }
02009
02010
02011
02012
02013
02014
02015
02016
02017
02018
02019
02020 inline
02021 bm::id_t bit_block_calc_count(const bm::word_t* block,
02022 const bm::word_t* block_end)
02023 {
02024 BM_ASSERT(block < block_end);
02025 bm::id_t count = 0;
02026
02027 #ifdef BM64OPT
02028
02029
02030
02031 const bm::id64_t* b1 = (bm::id64_t*) block;
02032 const bm::id64_t* b2 = (bm::id64_t*) block_end;
02033
02034 bm::id64_t acc = *b1++;
02035
02036 do
02037 {
02038 bm::id64_t in = *b1++;
02039 bm::id64_t acc_prev = acc;
02040 acc |= in;
02041
02042 if (acc_prev &= in)
02043 {
02044 acc = (acc & 0x5555555555555555LU) + (acc >> 1 & 0x5555555555555555LU);
02045 acc = (acc & 0x3333333333333333LU) + (acc >> 2 & 0x3333333333333333LU);
02046 acc = acc + (acc >> 4) & 0x0F0F0F0F0F0F0F0FLU;
02047 acc = acc + (acc >> 8);
02048 acc = acc + (acc >> 16);
02049 acc = acc + (acc >> 32) & 0x0000007F;
02050 count += (unsigned)acc;
02051
02052 acc = acc_prev;
02053 }
02054 } while (b1 < b2);
02055 count += word_bitcount64(acc);
02056
02057 #else
02058
02059
02060
02061
02062 bm::word_t acc = *block++;
02063 do
02064 {
02065 bm::word_t in = *block++;
02066 bm::word_t acc_prev = acc;
02067 acc |= in;
02068 if (acc_prev &= in)
02069 {
02070 BM_INCWORD_BITCOUNT(count, acc);
02071 acc = acc_prev;
02072 }
02073 } while (block < block_end);
02074
02075 BM_INCWORD_BITCOUNT(count, acc);
02076
02077 #endif
02078
02079 return count;
02080 }
02081
02082
02083
02084
02085
02086
02087
02088
02089
02090
02091
02092
02093
02094 inline
02095 bm::id_t bit_count_change(bm::word_t w)
02096 {
02097 unsigned count = 1;
02098 w ^= (w >> 1);
02099
02100 BM_INCWORD_BITCOUNT(count, w);
02101 count -= (w >> ((sizeof(w) * 8) - 1));
02102 return count;
02103 }
02104
02105
02106
02107
02108
02109
02110
02111
02112 inline
02113 bm::id_t bit_block_calc_count_change(const bm::word_t* block,
02114 const bm::word_t* block_end)
02115 {
02116 BM_ASSERT(block < block_end);
02117 bm::id_t count = 1;
02118
02119 #ifdef BM64OPT
02120
02121
02122
02123 const bm::id64_t* b1 = (bm::id64_t*) block;
02124 const bm::id64_t* b2 = (bm::id64_t*) block_end;
02125
02126 bm::id64_t w, w0, w_prev, w_l;
02127 w = w0 = *b1;
02128 const int w_shift = sizeof(w) * 8 - 1;
02129 w ^= (w >> 1);
02130 count += word_bitcount64(w);
02131 count -= (w_prev = (w0 >> w_shift));
02132
02133 for (++b1 ;b1 < b2; ++b1)
02134 {
02135 w = w0 = *b1;
02136 ++count;
02137
02138 if (!w)
02139 {
02140 count -= !w_prev;
02141 w_prev = 0;
02142 }
02143 else
02144 {
02145 w ^= (w >> 1);
02146 count += word_bitcount64(w);
02147
02148 w_l = w0 & 1;
02149 count -= (w0 >> w_shift);
02150 count -= !(w_prev ^ w_l);
02151
02152 w_prev = (w0 >> w_shift);
02153 }
02154 }
02155
02156 #else
02157
02158 bm::word_t w, w0, w_prev, w_l;
02159
02160 w = w0 = *block;
02161 const int w_shift = sizeof(w) * 8 - 1;
02162 w ^= (w >> 1);
02163 BM_INCWORD_BITCOUNT(count, w);
02164 count -= (w_prev = (w0 >> w_shift));
02165
02166 for (++block ;block < block_end; ++block)
02167 {
02168 w = w0 = *block;
02169 ++count;
02170
02171 if (!w)
02172 {
02173 count -= !w_prev;
02174 w_prev = 0;
02175 }
02176 else
02177 {
02178 w ^= (w >> 1);
02179 BM_INCWORD_BITCOUNT(count, w);
02180
02181 w_l = w0 & 1;
02182 count -= (w0 >> w_shift);
02183 count -= !(w_prev ^ w_l);
02184
02185 w_prev = (w0 >> w_shift);
02186 }
02187 }
02188 #endif
02189 return count;
02190 }
02191
02192
02193
02194
02195
02196
02197
02198
02199
02200 inline
02201 bm::id_t bit_block_calc_count_range(const bm::word_t* block,
02202 bm::word_t left,
02203 bm::word_t right)
02204 {
02205 BM_ASSERT(left <= right);
02206
02207 bm::id_t count = 0;
02208
02209 unsigned nbit = left;
02210 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02211 nbit &= bm::set_word_mask;
02212
02213 const bm::word_t* word = block + nword;
02214
02215 if (left == right)
02216 {
02217 return (*word >> nbit) & 1;
02218 }
02219 unsigned acc;
02220 unsigned bitcount = right - left + 1;
02221
02222 if (nbit)
02223 {
02224 unsigned right_margin = nbit + (right - left);
02225
02226 if (right_margin < 32)
02227 {
02228 unsigned mask =
02229 block_set_table<true>::_right[nbit] &
02230 block_set_table<true>::_left[right_margin];
02231 acc = *word & mask;
02232
02233 BM_INCWORD_BITCOUNT(count, acc);
02234 return count;
02235 }
02236 else
02237 {
02238 acc = *word & block_set_table<true>::_right[nbit];
02239 BM_INCWORD_BITCOUNT(count, acc);
02240 bitcount -= 32 - nbit;
02241 }
02242 ++word;
02243 }
02244
02245
02246 for ( ;bitcount >= 32; bitcount -= 32)
02247 {
02248 acc = *word++;
02249 BM_INCWORD_BITCOUNT(count, acc);
02250 }
02251
02252 if (bitcount)
02253 {
02254 acc = (*word) & block_set_table<true>::_left[bitcount-1];
02255 BM_INCWORD_BITCOUNT(count, acc);
02256 }
02257
02258 return count;
02259 }
02260
02261
02262
02263
02264
02265
02266
02267 template<typename T> void bit_invert(T* start, T* end)
02268 {
02269 #ifdef BMVECTOPT
02270 VECT_INVERT_ARR(start, end);
02271 #else
02272 do
02273 {
02274 start[0] = ~start[0];
02275 start[1] = ~start[1];
02276 start[2] = ~start[2];
02277 start[3] = ~start[3];
02278 start+=4;
02279 } while (start < end);
02280 #endif
02281 }
02282
02283
02284
02285
02286
02287
02288 inline bool is_bits_one(const bm::wordop_t* start,
02289 const bm::wordop_t* end)
02290 {
02291 do
02292 {
02293 bm::wordop_t tmp =
02294 start[0] & start[1] & start[2] & start[3];
02295 if (tmp != bm::all_bits_mask)
02296 return false;
02297 start += 4;
02298 } while (start < end);
02299
02300 return true;
02301 }
02302
02303
02304
02305
02306
02307
02308
02309 inline bool bit_is_all_zero(const bm::wordop_t* start,
02310 const bm::wordop_t* end)
02311 {
02312 do
02313 {
02314 bm::wordop_t tmp =
02315 start[0] | start[1] | start[2] | start[3];
02316 if (tmp)
02317 return false;
02318 start += 4;
02319 } while (start < end);
02320
02321 return true;
02322 }
02323
02324
02325
02326
02327
02328
02329 inline unsigned and_op(unsigned v1, unsigned v2)
02330 {
02331 return v1 & v2;
02332 }
02333
02334
02335
02336 inline unsigned xor_op(unsigned v1, unsigned v2)
02337 {
02338 return v1 ^ v2;
02339 }
02340
02341
02342
02343
02344
02345
02346
02347
02348
02349
02350
02351
02352
02353
02354
02355
02356
02357 inline gap_word_t* gap_operation_and(const gap_word_t* BMRESTRICT vect1,
02358 const gap_word_t* BMRESTRICT vect2,
02359 gap_word_t* BMRESTRICT tmp_buf)
02360 {
02361 gap_buff_op(tmp_buf, vect1, 0, vect2, 0, and_op);
02362
02363 return tmp_buf;
02364 }
02365
02366
02367
02368
02369
02370
02371
02372
02373
02374
02375
02376
02377
02378
02379
02380
02381
02382 inline gap_word_t* gap_operation_xor(const gap_word_t* BMRESTRICT vect1,
02383 const gap_word_t* BMRESTRICT vect2,
02384 gap_word_t* BMRESTRICT tmp_buf)
02385 {
02386 gap_buff_op(tmp_buf, vect1, 0, vect2, 0, xor_op);
02387
02388 return tmp_buf;
02389 }
02390
02391
02392
02393
02394
02395
02396
02397
02398
02399
02400
02401
02402
02403
02404
02405
02406
02407
02408 inline gap_word_t* gap_operation_or(const gap_word_t* BMRESTRICT vect1,
02409 const gap_word_t* BMRESTRICT vect2,
02410 gap_word_t* BMRESTRICT tmp_buf)
02411 {
02412
02413
02414 gap_buff_op(tmp_buf, vect1, 1, vect2, 1, and_op);
02415
02416
02417
02418 gap_invert(tmp_buf);
02419
02420
02421 return tmp_buf;
02422 }
02423
02424
02425
02426
02427
02428
02429
02430
02431
02432
02433
02434
02435
02436
02437
02438
02439
02440 inline gap_word_t* gap_operation_sub(const gap_word_t* BMRESTRICT vect1,
02441 const gap_word_t* BMRESTRICT vect2,
02442 gap_word_t* BMRESTRICT tmp_buf)
02443 {
02444
02445
02446 gap_buff_op(tmp_buf, vect1, 0, vect2, 1, and_op);
02447
02448
02449
02450 return tmp_buf;
02451 }
02452
02453
02454
02455
02456
02457
02458
02459
02460
02461
02462
02463
02464
02465
02466
02467 inline
02468 void bit_block_copy(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
02469 {
02470 #ifdef BMVECTOPT
02471 VECT_COPY_BLOCK(dst, src, src + bm::set_block_size);
02472 #else
02473 ::memcpy(dst, src, bm::set_block_size * sizeof(bm::word_t));
02474 #endif
02475 }
02476
02477
02478
02479
02480
02481
02482
02483
02484
02485
02486
02487 inline
02488 void bit_block_and(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
02489 {
02490 #ifdef BMVECTOPT
02491 VECT_AND_ARR(dst, src, src + bm::set_block_size);
02492 #else
02493 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
02494 const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + bm::set_block_size);
02495 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
02496
02497 do
02498 {
02499 dst_ptr[0] &= wrd_ptr[0];
02500 dst_ptr[1] &= wrd_ptr[1];
02501 dst_ptr[2] &= wrd_ptr[2];
02502 dst_ptr[3] &= wrd_ptr[3];
02503
02504 dst_ptr+=4;
02505 wrd_ptr+=4;
02506 } while (wrd_ptr < wrd_end);
02507 #endif
02508 }
02509
02510
02511
02512
02513
02514
02515
02516
02517
02518
02519
02520
02521 inline
02522 unsigned bit_block_and_count(const bm::word_t* src1,
02523 const bm::word_t* src1_end,
02524 const bm::word_t* src2)
02525 {
02526 unsigned count;
02527 #ifdef BMVECTOPT
02528 count = VECT_BITCOUNT_AND(src1, src1_end, src2);
02529 #else
02530 count = 0;
02531 do
02532 {
02533 BM_INCWORD_BITCOUNT(count, src1[0] & src2[0]);
02534 BM_INCWORD_BITCOUNT(count, src1[1] & src2[1]);
02535 BM_INCWORD_BITCOUNT(count, src1[2] & src2[2]);
02536 BM_INCWORD_BITCOUNT(count, src1[3] & src2[3]);
02537
02538 src1+=4;
02539 src2+=4;
02540 } while (src1 < src1_end);
02541 #endif
02542 return count;
02543 }
02544
02545
02546
02547
02548
02549
02550
02551
02552
02553
02554
02555
02556 inline
02557 unsigned bit_block_xor_count(const bm::word_t* BMRESTRICT src1,
02558 const bm::word_t* BMRESTRICT src1_end,
02559 const bm::word_t* BMRESTRICT src2)
02560 {
02561 unsigned count;
02562 #ifdef BMVECTOPT
02563 count = VECT_BITCOUNT_XOR(src1, src1_end, src2);
02564 #else
02565 count = 0;
02566 do
02567 {
02568 BM_INCWORD_BITCOUNT(count, src1[0] ^ src2[0]);
02569 BM_INCWORD_BITCOUNT(count, src1[1] ^ src2[1]);
02570 BM_INCWORD_BITCOUNT(count, src1[2] ^ src2[2]);
02571 BM_INCWORD_BITCOUNT(count, src1[3] ^ src2[3]);
02572
02573 src1+=4;
02574 src2+=4;
02575 } while (src1 < src1_end);
02576 #endif
02577 return count;
02578 }
02579
02580
02581
02582
02583
02584
02585
02586
02587
02588
02589
02590
02591 inline
02592 unsigned bit_block_sub_count(const bm::word_t* BMRESTRICT src1,
02593 const bm::word_t* BMRESTRICT src1_end,
02594 const bm::word_t* BMRESTRICT src2)
02595 {
02596 unsigned count;
02597 #ifdef BMVECTOPT
02598 count = VECT_BITCOUNT_SUB(src1, src1_end, src2);
02599 #else
02600 count = 0;
02601 do
02602 {
02603 BM_INCWORD_BITCOUNT(count, src1[0] & ~src2[0]);
02604 BM_INCWORD_BITCOUNT(count, src1[1] & ~src2[1]);
02605 BM_INCWORD_BITCOUNT(count, src1[2] & ~src2[2]);
02606 BM_INCWORD_BITCOUNT(count, src1[3] & ~src2[3]);
02607
02608 src1+=4;
02609 src2+=4;
02610 } while (src1 < src1_end);
02611 #endif
02612 return count;
02613 }
02614
02615
02616
02617
02618
02619
02620
02621
02622
02623
02624
02625
02626 inline
02627 unsigned bit_block_or_count(const bm::word_t* src1,
02628 const bm::word_t* src1_end,
02629 const bm::word_t* src2)
02630 {
02631 unsigned count;
02632 #ifdef BMVECTOPT
02633 count = VECT_BITCOUNT_OR(src1, src1_end, src2);
02634 #else
02635 count = 0;
02636 do
02637 {
02638 BM_INCWORD_BITCOUNT(count, src1[0] | src2[0]);
02639 BM_INCWORD_BITCOUNT(count, src1[1] | src2[1]);
02640 BM_INCWORD_BITCOUNT(count, src1[2] | src2[2]);
02641 BM_INCWORD_BITCOUNT(count, src1[3] | src2[3]);
02642
02643 src1+=4;
02644 src2+=4;
02645 } while (src1 < src1_end);
02646 #endif
02647 return count;
02648 }
02649
02650
02651
02652
02653
02654
02655
02656
02657
02658
02659
02660
02661
02662
02663 inline bm::word_t* bit_operation_and(bm::word_t* BMRESTRICT dst,
02664 const bm::word_t* BMRESTRICT src)
02665 {
02666 BM_ASSERT(dst || src);
02667
02668 bm::word_t* ret = dst;
02669
02670 if (IS_VALID_ADDR(dst))
02671 {
02672
02673 if (!IS_VALID_ADDR(src))
02674 {
02675 if (IS_EMPTY_BLOCK(src))
02676 {
02677
02678
02679 return 0;
02680 }
02681 }
02682 else
02683 {
02684
02685 bit_block_and(dst, src);
02686 }
02687 }
02688 else
02689 {
02690 if(!IS_VALID_ADDR(src))
02691 {
02692 if(IS_EMPTY_BLOCK(src))
02693 {
02694
02695
02696 return 0;
02697 }
02698
02699
02700 }
02701 else
02702 {
02703 if (IS_FULL_BLOCK(dst))
02704 {
02705 return const_cast<bm::word_t*>(src);
02706 }
02707
02708
02709 }
02710 }
02711
02712 return ret;
02713 }
02714
02715
02716
02717
02718
02719
02720
02721
02722
02723
02724
02725
02726
02727 inline
02728 bm::id_t bit_operation_and_count(const bm::word_t* BMRESTRICT src1,
02729 const bm::word_t* BMRESTRICT src1_end,
02730 const bm::word_t* BMRESTRICT src2)
02731 {
02732 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
02733 {
02734 return 0;
02735 }
02736 return bit_block_and_count(src1, src1_end, src2);
02737 }
02738
02739
02740
02741
02742
02743
02744
02745
02746
02747
02748
02749
02750
02751 inline
02752 bm::id_t bit_operation_sub_count(const bm::word_t* BMRESTRICT src1,
02753 const bm::word_t* BMRESTRICT src1_end,
02754 const bm::word_t* BMRESTRICT src2)
02755 {
02756 if (IS_EMPTY_BLOCK(src1))
02757 {
02758 return 0;
02759 }
02760
02761 if (IS_EMPTY_BLOCK(src2))
02762 {
02763 return bit_block_calc_count(src1, src1_end);
02764 }
02765 return bit_block_sub_count(src1, src1_end, src2);
02766 }
02767
02768
02769
02770
02771
02772
02773
02774
02775
02776
02777
02778
02779
02780 inline
02781 bm::id_t bit_operation_or_count(const bm::word_t* BMRESTRICT src1,
02782 const bm::word_t* BMRESTRICT src1_end,
02783 const bm::word_t* BMRESTRICT src2)
02784 {
02785 if (IS_EMPTY_BLOCK(src1))
02786 {
02787 if (!IS_EMPTY_BLOCK(src2))
02788 return bit_block_calc_count(src2, src2 + (src1_end - src1));
02789 else
02790 return 0;
02791 }
02792 else
02793 {
02794 if (IS_EMPTY_BLOCK(src2))
02795 return bit_block_calc_count(src1, src1_end);
02796 }
02797
02798 return bit_block_or_count(src1, src1_end, src2);
02799 }
02800
02801
02802
02803
02804
02805
02806
02807
02808
02809
02810
02811 inline void bit_block_or(bm::word_t* BMRESTRICT dst,
02812 const bm::word_t* BMRESTRICT src)
02813 {
02814 #ifdef BMVECTOPT
02815 VECT_OR_ARR(dst, src, src + bm::set_block_size);
02816 #else
02817 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
02818 const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + set_block_size);
02819 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
02820
02821 do
02822 {
02823 dst_ptr[0] |= wrd_ptr[0];
02824 dst_ptr[1] |= wrd_ptr[1];
02825 dst_ptr[2] |= wrd_ptr[2];
02826 dst_ptr[3] |= wrd_ptr[3];
02827
02828 dst_ptr+=4;
02829 wrd_ptr+=4;
02830
02831 } while (wrd_ptr < wrd_end);
02832 #endif
02833 }
02834
02835
02836
02837
02838
02839
02840
02841
02842
02843
02844
02845
02846
02847
02848 inline
02849 bm::word_t* bit_operation_or(bm::word_t* BMRESTRICT dst,
02850 const bm::word_t* BMRESTRICT src)
02851 {
02852 BM_ASSERT(dst || src);
02853
02854 bm::word_t* ret = dst;
02855
02856 if (IS_VALID_ADDR(dst))
02857 {
02858 if (!IS_VALID_ADDR(src))
02859 {
02860 if (IS_FULL_BLOCK(src))
02861 {
02862
02863
02864 ::memset(dst, 0xFF, bm::set_block_size * sizeof(bm::word_t));
02865 }
02866 }
02867 else
02868 {
02869
02870 bit_block_or(dst, src);
02871 }
02872 }
02873 else
02874 {
02875 if (!IS_VALID_ADDR(src))
02876 {
02877 if (IS_FULL_BLOCK(src))
02878 {
02879
02880
02881 return const_cast<bm::word_t*>(FULL_BLOCK_ADDR);
02882 }
02883 }
02884 else
02885 {
02886 if (dst == 0)
02887 {
02888
02889
02890 return const_cast<bm::word_t*>(src);
02891 }
02892 }
02893 }
02894 return ret;
02895 }
02896
02897
02898
02899
02900
02901
02902
02903
02904
02905
02906 inline
02907 void bit_block_sub(bm::word_t* BMRESTRICT dst,
02908 const bm::word_t* BMRESTRICT src)
02909 {
02910 #ifdef BMVECTOPT
02911 VECT_SUB_ARR(dst, src, src + bm::set_block_size);
02912 #else
02913 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
02914 const bm::wordop_t* BMRESTRICT wrd_end =
02915 (wordop_t*) (src + bm::set_block_size);
02916 bm::wordop_t* dst_ptr = (wordop_t*)dst;
02917
02918
02919 do
02920 {
02921 dst_ptr[0] &= ~wrd_ptr[0];
02922 dst_ptr[1] &= ~wrd_ptr[1];
02923 dst_ptr[2] &= ~wrd_ptr[2];
02924 dst_ptr[3] &= ~wrd_ptr[3];
02925
02926 dst_ptr+=4;
02927 wrd_ptr+=4;
02928 } while (wrd_ptr < wrd_end);
02929 #endif
02930
02931 }
02932
02933
02934
02935
02936
02937
02938
02939
02940
02941
02942
02943
02944
02945
02946 inline
02947 bm::word_t* bit_operation_sub(bm::word_t* BMRESTRICT dst,
02948 const bm::word_t* BMRESTRICT src)
02949 {
02950 BM_ASSERT(dst || src);
02951
02952 bm::word_t* ret = dst;
02953 if (IS_VALID_ADDR(dst))
02954 {
02955 if (!IS_VALID_ADDR(src))
02956 {
02957 if (IS_FULL_BLOCK(src))
02958 {
02959
02960
02961 return 0;
02962 }
02963 }
02964 else
02965 {
02966 bit_block_sub(dst, src);
02967 }
02968 }
02969 else
02970 {
02971 if (!IS_VALID_ADDR(src))
02972 {
02973 if (IS_FULL_BLOCK(src))
02974 {
02975
02976 return 0;
02977 }
02978 }
02979 else
02980 {
02981 if (IS_FULL_BLOCK(dst))
02982 {
02983
02984
02985 return const_cast<bm::word_t*>(src);
02986 }
02987 }
02988 }
02989 return ret;
02990 }
02991
02992
02993
02994
02995
02996
02997
02998
02999
03000
03001
03002 inline
03003 void bit_block_xor(bm::word_t* BMRESTRICT dst,
03004 const bm::word_t* BMRESTRICT src)
03005 {
03006 #ifdef BMVECTOPT
03007 VECT_XOR_ARR(dst, src, src + bm::set_block_size);
03008 #else
03009 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
03010 const bm::wordop_t* BMRESTRICT wrd_end =
03011 (wordop_t*) (src + bm::set_block_size);
03012 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03013
03014
03015 do
03016 {
03017 dst_ptr[0] ^= wrd_ptr[0];
03018 dst_ptr[1] ^= wrd_ptr[1];
03019 dst_ptr[2] ^= wrd_ptr[2];
03020 dst_ptr[3] ^= wrd_ptr[3];
03021
03022 dst_ptr+=4;
03023 wrd_ptr+=4;
03024 } while (wrd_ptr < wrd_end);
03025 #endif
03026
03027 }
03028
03029
03030
03031
03032
03033
03034
03035
03036
03037
03038
03039
03040
03041
03042 inline
03043 bm::word_t* bit_operation_xor(bm::word_t* BMRESTRICT dst,
03044 const bm::word_t* BMRESTRICT src)
03045 {
03046 BM_ASSERT(dst || src);
03047 if (src == dst) return 0;
03048
03049 bm::word_t* ret = dst;
03050
03051 if (IS_VALID_ADDR(dst))
03052 {
03053 if (!src) return dst;
03054
03055 bit_block_xor(dst, src);
03056 }
03057 else
03058 {
03059 if (!src) return dst;
03060
03061
03062
03063
03064
03065 return const_cast<bm::word_t*>(src);
03066 }
03067 return ret;
03068 }
03069
03070
03071
03072
03073
03074
03075
03076
03077
03078
03079
03080 inline
03081 bm::id_t bit_operation_xor_count(const bm::word_t* BMRESTRICT src1,
03082 const bm::word_t* BMRESTRICT src1_end,
03083 const bm::word_t* BMRESTRICT src2)
03084 {
03085 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03086 {
03087 if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
03088 return 0;
03089 const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
03090 return bit_block_calc_count(block, block + (src1_end - src1));
03091 }
03092 return bit_block_xor_count(src1, src1_end, src2);
03093 }
03094
03095
03096
03097
03098
03099
03100
03101
03102
03103
03104
03105
03106
03107
03108 inline
03109 void bit_find_head_tail(const bm::word_t* data,
03110 unsigned* head_idx,
03111 unsigned* tail_idx)
03112 {
03113 BM_ASSERT(head_idx && tail_idx);
03114 *head_idx = (unsigned)-1;
03115 for (unsigned i = 0; i < bm::set_block_size; ++i)
03116 {
03117 if (data[i])
03118 {
03119 *head_idx = i;
03120 break;
03121 }
03122 }
03123 if (*head_idx == (unsigned)-1)
03124 {
03125 return;
03126 }
03127
03128 for (unsigned j = bm::set_block_size-1; j >= *head_idx; --j)
03129 {
03130 if (data[j])
03131 {
03132 *tail_idx = j;
03133 break;
03134 }
03135 }
03136
03137 }
03138
03139
03140
03141
03142
03143
03144
03145
03146
03147
03148
03149 inline
03150 int bit_find_in_block(const bm::word_t* data,
03151 unsigned nbit,
03152 bm::id_t* prev)
03153 {
03154 register bm::id_t p = *prev;
03155 int found = 0;
03156
03157 for(;;)
03158 {
03159 unsigned nword = nbit >> bm::set_word_shift;
03160 if (nword >= bm::set_block_size) break;
03161
03162 register bm::word_t val = data[nword] >> (p & bm::set_word_mask);
03163
03164 if (val)
03165 {
03166 while((val & 1) == 0)
03167 {
03168 val >>= 1;
03169 ++nbit;
03170 ++p;
03171 }
03172 ++found;
03173 break;
03174 }
03175 else
03176 {
03177 p += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
03178 nbit += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
03179 }
03180 }
03181 *prev = p;
03182 return found;
03183 }
03184
03185
03186
03187
03188
03189
03190
03191
03192
03193 template<typename T,typename B> unsigned bit_list(T w, B* bits)
03194 {
03195
03196 unsigned octet = 0;
03197 B* bp = bits;
03198 do
03199 {
03200 if (w & 1) *bp++ = octet + 0;
03201 if (w & 2) *bp++ = octet + 1;
03202 if (w & 4) *bp++ = octet + 2;
03203 if (w & 8) *bp++ = octet + 3;
03204 if (w & 16) *bp++ = octet + 4;
03205 if (w & 32) *bp++ = octet + 5;
03206 if (w & 64) *bp++ = octet + 6;
03207 if (w & 128) *bp++ = octet + 7;
03208
03209 w >>= 8;
03210 octet += 8;
03211 } while (w);
03212 return (unsigned)(bp - bits);
03213 }
03214
03215
03216
03217
03218
03219
03220 template<typename T>
03221 unsigned gap_overhead(const T* length,
03222 const T* length_end,
03223 const T* glevel_len)
03224 {
03225 BM_ASSERT(length && length_end && glevel_len);
03226
03227 unsigned overhead = 0;
03228 for (;length < length_end; ++length)
03229 {
03230 unsigned len = *length;
03231 int level = gap_calc_level(len, glevel_len);
03232 BM_ASSERT(level >= 0 && level < (int)bm::gap_levels);
03233 unsigned capacity = glevel_len[level];
03234 BM_ASSERT(capacity >= len);
03235 overhead += capacity - len;
03236 }
03237 return overhead;
03238 }
03239
03240
03241
03242
03243
03244
03245
03246
03247
03248 template<typename T>
03249 bool improve_gap_levels(const T* length,
03250 const T* length_end,
03251 T* glevel_len)
03252 {
03253 BM_ASSERT(length && length_end && glevel_len);
03254
03255 size_t lsize = length_end - length;
03256
03257 BM_ASSERT(lsize);
03258
03259 gap_word_t max_len = 0;
03260 unsigned i;
03261 for (i = 0; i < lsize; ++i)
03262 {
03263 if (length[i] > max_len)
03264 max_len = length[i];
03265 }
03266 if (max_len < 5 || lsize <= bm::gap_levels)
03267 {
03268 glevel_len[0] = max_len + 4;
03269 for (i = 1; i < bm::gap_levels; ++i)
03270 {
03271 glevel_len[i] = bm::gap_max_buff_len;
03272 }
03273 return true;
03274 }
03275
03276 glevel_len[bm::gap_levels-1] = max_len + 5;
03277
03278 unsigned min_overhead = gap_overhead(length, length_end, glevel_len);
03279 bool is_improved = false;
03280 gap_word_t prev_value = glevel_len[bm::gap_levels-1];
03281
03282
03283
03284 for (i = bm::gap_levels-2; ; --i)
03285 {
03286 unsigned opt_len = 0;
03287 unsigned j;
03288 bool imp_flag = false;
03289 gap_word_t gap_saved_value = glevel_len[i];
03290 for (j = 0; j < lsize; ++j)
03291 {
03292
03293
03294
03295 glevel_len[i] = length[j]+4;
03296 unsigned ov = gap_overhead(length, length_end, glevel_len);
03297 if (ov <= min_overhead)
03298 {
03299 min_overhead = ov;
03300 opt_len = length[j]+4;
03301 imp_flag = true;
03302 }
03303 }
03304 if (imp_flag) {
03305 glevel_len[i] = opt_len;
03306 is_improved = true;
03307 }
03308 else
03309 {
03310 glevel_len[i] = gap_saved_value;
03311 }
03312 if (i == 0)
03313 break;
03314 prev_value = glevel_len[i];
03315 }
03316
03317
03318
03319
03320 T val = *glevel_len;
03321 T* gp = glevel_len;
03322 T* res = glevel_len;
03323 for (i = 0; i < bm::gap_levels; ++i)
03324 {
03325 if (val != *gp)
03326 {
03327 val = *gp;
03328 *++res = val;
03329 }
03330 ++gp;
03331 }
03332
03333
03334 while (++res < (glevel_len + bm::gap_levels))
03335 {
03336 *res = bm::gap_max_buff_len;
03337 }
03338
03339 return is_improved;
03340
03341 }
03342
03343
03344
03345 }
03346
03347 #endif
03348