00001 #ifndef BMFUNC__H__INCLUDED__
00002 #define BMFUNC__H__INCLUDED__
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
00028
00029 #include <memory.h>
00030
00031 #include "bmdef.h"
00032 #include "bmutil.h"
00033
00034
00035 #ifdef _MSC_VER
00036 # pragma warning( disable: 4146 )
00037 #endif
00038
00039 namespace bm
00040 {
00041
00042
00043
00044
00045
00046
00047
00048 struct bv_statistics
00049 {
00050
00051 unsigned bit_blocks;
00052
00053 unsigned gap_blocks;
00054
00055 unsigned max_serialize_mem;
00056
00057 unsigned memory_used;
00058
00059 gap_word_t gap_length[bm::set_total_blocks];
00060
00061 gap_word_t gap_levels[bm::gap_levels];
00062
00063
00064
00065
00066 void add_bit_block()
00067 {
00068 ++bit_blocks;
00069 unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
00070 memory_used += mem_used;
00071 max_serialize_mem += mem_used;
00072 }
00073
00074
00075 void add_gap_block(unsigned capacity, unsigned length)
00076 {
00077 ++gap_blocks;
00078 unsigned mem_used = capacity * sizeof(gap_word_t);
00079 memory_used += mem_used;
00080 max_serialize_mem += length * sizeof(gap_word_t);
00081 }
00082 };
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102 template<bool T> struct gap_len_table
00103 {
00104 static const gap_word_t _len[bm::gap_levels];
00105 };
00106
00107 template<bool T>
00108 const gap_word_t gap_len_table<T>::_len[bm::gap_levels] =
00109 { 128, 256, 512, bm::gap_max_buff_len };
00110
00111
00112
00113
00114
00115
00116
00117 template<bool T> struct gap_len_table_min
00118 {
00119 static const gap_word_t _len[bm::gap_levels];
00120 };
00121
00122 template<bool T>
00123 const gap_word_t gap_len_table_min<T>::_len[bm::gap_levels] =
00124 { 32, 96, 128, 512 };
00125
00126
00127
00128
00129
00130
00131
00132
00133 template<bool T> struct block_set_table
00134 {
00135 static const unsigned _left[32];
00136 static const unsigned _right[32];
00137 };
00138
00139 template<bool T>
00140 const unsigned block_set_table<T>::_left[32] = {
00141 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff,
00142 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff,
00143 0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff,
00144 0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
00145 };
00146
00147 template<bool T>
00148 const unsigned block_set_table<T>::_right[32] = {
00149 0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8, 0xfffffff0,
00150 0xffffffe0, 0xffffffc0, 0xffffff80, 0xffffff00, 0xfffffe00,
00151 0xfffffc00, 0xfffff800, 0xfffff000, 0xffffe000, 0xffffc000,
00152 0xffff8000, 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
00153 0xfff00000, 0xffe00000, 0xffc00000, 0xff800000, 0xff000000,
00154 0xfe000000, 0xfc000000, 0xf8000000, 0xf0000000, 0xe0000000,
00155 0xc0000000, 0x80000000
00156 };
00157
00158
00159
00160
00161
00162
00163
00164 BMFORCEINLINE
00165 bm::id_t word_bitcount(bm::id_t w)
00166 {
00167 #ifdef BMSSE4OPT
00168 return _mm_popcnt_u32(w);
00169 #else
00170 return
00171 bm::bit_count_table<true>::_count[(unsigned char)(w)] +
00172 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 8)] +
00173 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 16)] +
00174 bm::bit_count_table<true>::_count[(unsigned char)((w) >> 24)];
00175 #endif
00176 }
00177
00178 inline
00179 int parallel_popcnt_32(unsigned int n)
00180 {
00181 unsigned int tmp;
00182
00183 tmp = n - ((n >> 1) & 033333333333)
00184 - ((n >> 2) & 011111111111);
00185 return ((tmp + (tmp >> 3)) & 030707070707) % 63;
00186 }
00187
00188 #ifdef BM64OPT
00189
00190
00191
00192
00193
00194 inline
00195 int word_bitcount64(bm::id64_t x)
00196 {
00197 x = x - ((x >> 1) & 0x5555555555555555);
00198 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
00199 x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
00200 x = x + (x >> 8);
00201 x = x + (x >> 16);
00202 x = x + (x >> 32);
00203 return x & 0xFF;
00204 }
00205
00206 inline
00207 unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y,
00208 bm::id64_t u, bm::id64_t v)
00209 {
00210 const bm::id64_t m1 = 0x5555555555555555;
00211 const bm::id64_t m2 = 0x3333333333333333;
00212 const bm::id64_t m3 = 0x0F0F0F0F0F0F0F0F;
00213 const bm::id64_t m4 = 0x000000FF000000FF;
00214
00215 x = x - ((x >> 1) & m1);
00216 y = y - ((y >> 1) & m1);
00217 u = u - ((u >> 1) & m1);
00218 v = v - ((v >> 1) & m1);
00219 x = (x & m2) + ((x >> 2) & m2);
00220 y = (y & m2) + ((y >> 2) & m2);
00221 u = (u & m2) + ((u >> 2) & m2);
00222 v = (v & m2) + ((v >> 2) & m2);
00223 x = x + y;
00224 u = u + v;
00225 x = (x & m3) + ((x >> 4) & m3);
00226 u = (u & m3) + ((u >> 4) & m3);
00227 x = x + u;
00228 x = x + (x >> 8);
00229 x = x + (x >> 16);
00230 x = x & m4;
00231 x = x + (x >> 32);
00232 return x & 0x000001FF;
00233 }
00234
00235
00236 #endif
00237
00238
00239
00240
00241
00242
00243
00244
00245 enum set_operation
00246 {
00247 set_AND = 0,
00248 set_OR = 1,
00249 set_SUB = 2,
00250 set_XOR = 3,
00251 set_ASSIGN = 4,
00252 set_COUNT = 5,
00253 set_COUNT_AND = 6,
00254 set_COUNT_XOR = 7,
00255 set_COUNT_OR = 8,
00256 set_COUNT_SUB_AB= 9,
00257 set_COUNT_SUB_BA= 10,
00258 set_COUNT_A = 11,
00259 set_COUNT_B = 12,
00260
00261 set_END
00262 };
00263
00264
00265 inline
00266 bool is_const_set_operation(set_operation op)
00267 {
00268 return (int(op) >= int(set_COUNT));
00269 }
00270
00271
00272
00273
00274 enum operation
00275 {
00276 BM_AND = set_AND,
00277 BM_OR = set_OR,
00278 BM_SUB = set_SUB,
00279 BM_XOR = set_XOR
00280 };
00281
00282
00283
00284
00285 inline
00286 bm::operation setop2op(bm::set_operation op)
00287 {
00288 BM_ASSERT(op == set_AND ||
00289 op == set_OR ||
00290 op == set_SUB ||
00291 op == set_XOR);
00292 return (bm::operation) op;
00293 }
00294
00295
00296
00297
00298
00299
00300
00301 template<bool T> struct all_set
00302 {
00303 struct BM_ALIGN16 all_set_block
00304 {
00305 bm::word_t _p[bm::set_block_size] BM_ALIGN16ATTR;
00306
00307 all_set_block()
00308 {
00309 ::memset(_p, 0xFF, sizeof(_p));
00310 }
00311 };
00312
00313 static all_set_block _block;
00314 };
00315
00316
00317 template<bool T> typename all_set<T>::all_set_block all_set<T>::_block;
00318
00319
00320 template<typename W>
00321 void xor_swap(W& x, W& y)
00322 {
00323 BM_ASSERT(&x != &y);
00324 x ^= y;
00325 y ^= x;
00326 x ^= y;
00327 }
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341 template<typename T> int wordcmp0(T w1, T w2)
00342 {
00343 while (w1 != w2)
00344 {
00345 int res = (w1 & 1) - (w2 & 1);
00346 if (res != 0) return res;
00347 w1 >>= 1;
00348 w2 >>= 1;
00349 }
00350 return 0;
00351 }
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371 template<typename T> int wordcmp(T a, T b)
00372 {
00373 T diff = a ^ b;
00374 return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
00375 }
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385 template<bool T> struct _copyright
00386 {
00387 static const char _p[];
00388 };
00389
00390 template<bool T> const char _copyright<T>::_p[] =
00391 "BitMagic C++ Library. v.3.6.3 (c) 2002-2010 Anatoliy Kuznetsov.";
00392
00393
00394
00395
00396
00397 enum ByteOrder
00398 {
00399 BigEndian = 0,
00400 LittleEndian = 1
00401 };
00402
00403
00404
00405
00406
00407 template<bool T> struct globals
00408 {
00409 struct bo
00410 {
00411 ByteOrder _byte_order;
00412
00413 bo()
00414 {
00415 unsigned x;
00416 unsigned char *s = (unsigned char *)&x;
00417 s[0] = 1;
00418 s[1] = 2;
00419 s[2] = 3;
00420 s[3] = 4;
00421
00422 if(x == 0x04030201)
00423 {
00424 _byte_order = LittleEndian;
00425 return;
00426 }
00427
00428 if(x == 0x01020304)
00429 {
00430 _byte_order = BigEndian;
00431 return;
00432 }
00433
00434 BM_ASSERT(0);
00435 _byte_order = LittleEndian;
00436 }
00437 };
00438
00439 static bo _bo;
00440
00441 static ByteOrder byte_order() { return _bo._byte_order; }
00442
00443 };
00444
00445 template<bool T> typename globals<T>::bo globals<T>::_bo;
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460 template<typename T>
00461 unsigned gap_bfind(const T* buf, unsigned pos, unsigned* is_set)
00462 {
00463 BM_ASSERT(pos < bm::gap_max_bits);
00464 *is_set = (*buf) & 1;
00465
00466 register unsigned start = 1;
00467 register unsigned end = 1 + ((*buf) >> 3);
00468
00469 while ( start != end )
00470 {
00471 unsigned curr = (start + end) >> 1;
00472 if ( buf[curr] < pos )
00473 start = curr + 1;
00474 else
00475 end = curr;
00476 }
00477 *is_set ^= ((start-1) & 1);
00478 return start;
00479 }
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489 template<typename T> unsigned gap_test(const T* buf, unsigned pos)
00490 {
00491 BM_ASSERT(pos < bm::gap_max_bits);
00492
00493 unsigned start = 1;
00494 unsigned end = 1 + ((*buf) >> 3);
00495
00496 if (end - start < 10)
00497 {
00498 unsigned sv = *buf & 1;
00499 unsigned sv1= sv ^ 1;
00500 if (buf[1] >= pos) return sv;
00501 if (buf[2] >= pos) return sv1;
00502 if (buf[3] >= pos) return sv;
00503 if (buf[4] >= pos) return sv1;
00504 if (buf[5] >= pos) return sv;
00505 if (buf[6] >= pos) return sv1;
00506 if (buf[7] >= pos) return sv;
00507 if (buf[8] >= pos) return sv1;
00508 if (buf[9] >= pos) return sv;
00509 BM_ASSERT(0);
00510 }
00511 else
00512 while ( start != end )
00513 {
00514 unsigned curr = (start + end) >> 1;
00515 if ( buf[curr] < pos )
00516 start = curr + 1;
00517 else
00518 end = curr;
00519 }
00520 return ((*buf) & 1) ^ ((--start) & 1);
00521 }
00522
00523
00524
00525
00526 template<class T, class F>
00527 void for_each_nzblock(T*** root, unsigned size1, unsigned size2,
00528 F& f)
00529 {
00530 unsigned block_idx = 0;
00531 for (unsigned i = 0; i < size1; ++i)
00532 {
00533 T** blk_blk = root[i];
00534
00535 if (!blk_blk)
00536 {
00537 f.on_empty_top(i);
00538 block_idx += size2;
00539 continue;
00540 }
00541
00542 unsigned non_empty_top = 0;
00543 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00544 {
00545 if (blk_blk[j])
00546 {
00547 f(blk_blk[j], block_idx);
00548
00549 non_empty_top += (blk_blk[j] != 0);
00550 }
00551 else
00552 {
00553 f.on_empty_block(block_idx);
00554 }
00555 }
00556 if (non_empty_top == 0)
00557 {
00558 f.on_empty_top(i);
00559 }
00560 }
00561 }
00562
00563
00564
00565
00566 template<class T, class F>
00567 bool for_each_nzblock_if(T*** root, unsigned size1, unsigned size2, F& f)
00568 {
00569 unsigned block_idx = 0;
00570 for (unsigned i = 0; i < size1; ++i)
00571 {
00572 T** blk_blk = root[i];
00573
00574 if (!blk_blk)
00575 {
00576 block_idx += bm::set_array_size;
00577 continue;
00578 }
00579
00580 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00581 {
00582 if (blk_blk[j])
00583 if (f(blk_blk[j], block_idx)) return true;
00584 }
00585 }
00586 return false;
00587 }
00588
00589
00590
00591 template<class T, class F>
00592 void for_each_block(T*** root, unsigned size1, unsigned size2, F& f)
00593 {
00594 unsigned block_idx = 0;
00595
00596 for (unsigned i = 0; i < size1; ++i)
00597 {
00598 T** blk_blk = root[i];
00599
00600 if (blk_blk)
00601 {
00602 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00603 {
00604 f(blk_blk[j], block_idx);
00605 }
00606 }
00607 else
00608 {
00609 for (unsigned j = 0;j < size2; ++j, ++block_idx)
00610 {
00611 f(0, block_idx);
00612 }
00613 }
00614 }
00615 }
00616
00617
00618
00619
00620
00621 template<class T, class F> F bmfor_each(T first, T last, F f)
00622 {
00623 do
00624 {
00625 f(*first);
00626 ++first;
00627 } while (first < last);
00628 return f;
00629 }
00630
00631
00632
00633 template<class T> T sum_arr(T* first, T* last)
00634 {
00635 T sum = 0;
00636 while (first < last)
00637 {
00638 sum += *first;
00639 ++first;
00640 }
00641 return sum;
00642 }
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653 template<typename T> unsigned gap_bit_count(const T* buf, unsigned dsize=0)
00654 {
00655 register const T* pcurr = buf;
00656 if (dsize == 0)
00657 dsize = (*pcurr >> 3);
00658
00659 register const T* pend = pcurr + dsize;
00660
00661 register unsigned bits_counter = 0;
00662 ++pcurr;
00663
00664 if (*buf & 1)
00665 {
00666 bits_counter += *pcurr + 1;
00667 ++pcurr;
00668 }
00669 ++pcurr;
00670
00671 while (pcurr <= pend)
00672 {
00673 bits_counter += *pcurr - *(pcurr-1);
00674 pcurr += 2;
00675 }
00676
00677 return bits_counter;
00678 }
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688 template<typename T>
00689 unsigned gap_bit_count_range(const T* buf, T left, T right)
00690 {
00691 BM_ASSERT(left <= right);
00692
00693 const T* pcurr = buf;
00694 const T* pend = pcurr + (*pcurr >> 3);
00695
00696 unsigned bits_counter = 0;
00697 unsigned is_set;
00698 unsigned start_pos = gap_bfind(buf, left, &is_set);
00699
00700 pcurr = buf + start_pos;
00701 if (right <= *pcurr)
00702 {
00703 if (is_set)
00704 bits_counter = (right - left + 1);
00705 return bits_counter;
00706 }
00707 if (is_set)
00708 bits_counter += *pcurr - left + 1;
00709
00710 unsigned prev_gap = *pcurr++;
00711 is_set ^= 1;
00712 while (right > *pcurr)
00713 {
00714 if (is_set)
00715 bits_counter += *pcurr - prev_gap;
00716 if (pcurr == pend)
00717 return bits_counter;
00718 prev_gap = *pcurr++;
00719 is_set ^= 1;
00720 }
00721 if (is_set)
00722 bits_counter += right - prev_gap;
00723
00724 return bits_counter;
00725 }
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735 template<class T, class Func>
00736 void for_each_dgap(const T* gap_buf, Func& func)
00737 {
00738 const T* pcurr = gap_buf;
00739 const T* pend = pcurr + (*pcurr >> 3);
00740 ++pcurr;
00741
00742 T prev = *pcurr;
00743 func(prev + 1);
00744 ++pcurr;
00745 do
00746 {
00747 func(*pcurr - prev);
00748 prev = *pcurr;
00749 } while (++pcurr < pend);
00750 }
00751
00752
00753
00754
00755 template<typename T> struct d_copy_func
00756 {
00757 d_copy_func(T* dg_buf) : dgap_buf_(dg_buf) {}
00758 void operator()(T dgap) { *dgap_buf_++ = dgap; }
00759
00760 T* dgap_buf_;
00761 };
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776 template<typename T>
00777 T* gap_2_dgap(const T* gap_buf, T* dgap_buf, bool copy_head=true)
00778 {
00779 if (copy_head)
00780 {
00781 *dgap_buf++ = *gap_buf;
00782 }
00783
00784 d_copy_func<T> copy_func(dgap_buf);
00785 for_each_dgap<T, d_copy_func<T> >(gap_buf, copy_func);
00786 return copy_func.dgap_buf_;
00787 }
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800 template<typename T>
00801 void dgap_2_gap(const T* dgap_buf, T* gap_buf, T gap_header=0)
00802 {
00803 register const T* pcurr = dgap_buf;
00804 unsigned len;
00805 if (!gap_header)
00806 {
00807 len = *pcurr >> 3;
00808 *gap_buf++ = *pcurr++;
00809 }
00810 else
00811 {
00812 len = gap_header >> 3;
00813 *gap_buf++ = gap_header;
00814 }
00815 --len;
00816 register const T* pend = pcurr + len;
00817
00818 *gap_buf = *pcurr++;
00819 if (*gap_buf == 0)
00820 *gap_buf = 65535;
00821 else
00822 *gap_buf = *gap_buf - 1;
00823
00824 for (++gap_buf; pcurr < pend; ++pcurr)
00825 {
00826 T prev = *(gap_buf-1);
00827 *gap_buf++ = *pcurr + prev;
00828 }
00829 *gap_buf = 65535;
00830 }
00831
00832
00833
00834
00835
00836
00837
00838
00839
00840
00841 template<typename T> int gapcmp(const T* buf1, const T* buf2)
00842 {
00843 const T* pcurr1 = buf1;
00844 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
00845 unsigned bitval1 = *buf1 & 1;
00846 ++pcurr1;
00847
00848 const T* pcurr2 = buf2;
00849 unsigned bitval2 = *buf2 & 1;
00850 ++pcurr2;
00851
00852 while (pcurr1 <= pend1)
00853 {
00854 if (*pcurr1 == *pcurr2)
00855 {
00856 if (bitval1 != bitval2)
00857 {
00858 return (bitval1) ? 1 : -1;
00859 }
00860 }
00861 else
00862 {
00863 if (bitval1 == bitval2)
00864 {
00865 if (bitval1)
00866 {
00867 return (*pcurr1 < *pcurr2) ? -1 : 1;
00868 }
00869 else
00870 {
00871 return (*pcurr1 < *pcurr2) ? 1 : -1;
00872 }
00873 }
00874 else
00875 {
00876 return (bitval1) ? 1 : -1;
00877 }
00878 }
00879
00880 ++pcurr1; ++pcurr2;
00881
00882 bitval1 ^= 1;
00883 bitval2 ^= 1;
00884 }
00885
00886 return 0;
00887 }
00888
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907 template<typename T, class F>
00908 void gap_buff_op(T* BMRESTRICT dest,
00909 const T* BMRESTRICT vect1,
00910 unsigned vect1_mask,
00911 const T* BMRESTRICT vect2,
00912 unsigned vect2_mask,
00913 F& f,
00914 unsigned& dlen)
00915 {
00916 register const T* cur1 = vect1;
00917 register const T* cur2 = vect2;
00918
00919 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
00920 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
00921
00922 unsigned bitval = f(bitval1, bitval2);
00923 unsigned bitval_prev = bitval;
00924
00925 register T* res = dest;
00926 *res = bitval;
00927 ++res;
00928
00929 while (1)
00930 {
00931 bitval = f(bitval1, bitval2);
00932
00933
00934
00935 if (bitval != bitval_prev)
00936 {
00937 ++res;
00938 bitval_prev = bitval;
00939 }
00940
00941 if (*cur1 < *cur2)
00942 {
00943 *res = *cur1;
00944 ++cur1;
00945 bitval1 ^= 1;
00946 }
00947 else
00948 {
00949 *res = *cur2;
00950 if (*cur2 < *cur1)
00951 {
00952 bitval2 ^= 1;
00953 }
00954 else
00955 {
00956 if (*cur2 == (bm::gap_max_bits - 1))
00957 {
00958 break;
00959 }
00960
00961 ++cur1;
00962 bitval1 ^= 1;
00963 bitval2 ^= 1;
00964 }
00965 ++cur2;
00966 }
00967
00968 }
00969
00970 dlen = (unsigned)(res - dest);
00971 *dest = (*dest & 7) + (dlen << 3);
00972
00973 }
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986
00987
00988
00989 template<typename T, class F>
00990 unsigned gap_buff_any_op(const T* BMRESTRICT vect1,
00991 unsigned vect1_mask,
00992 const T* BMRESTRICT vect2,
00993 unsigned vect2_mask,
00994 F f)
00995 {
00996 register const T* cur1 = vect1;
00997 register const T* cur2 = vect2;
00998
00999 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
01000 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
01001
01002 unsigned bitval = f(bitval1, bitval2);
01003 if (bitval)
01004 return bitval;
01005 unsigned bitval_prev = bitval;
01006
01007 while (1)
01008 {
01009 bitval = f(bitval1, bitval2);
01010 if (bitval)
01011 return bitval;
01012
01013 if (bitval != bitval_prev)
01014 bitval_prev = bitval;
01015
01016 if (*cur1 < *cur2)
01017 {
01018 ++cur1;
01019 bitval1 ^= 1;
01020 }
01021 else
01022 {
01023 if (*cur2 < *cur1)
01024 {
01025 bitval2 ^= 1;
01026 }
01027 else
01028 {
01029 if (*cur2 == (bm::gap_max_bits - 1))
01030 {
01031 break;
01032 }
01033
01034 ++cur1;
01035 bitval1 ^= 1;
01036 bitval2 ^= 1;
01037 }
01038 ++cur2;
01039 }
01040
01041 }
01042
01043 return 0;
01044 }
01045
01046
01047
01048
01049
01050
01051
01052
01053
01054
01055
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091
01092
01093
01094
01095
01096
01097
01098
01099
01100
01101
01102
01103
01104
01105
01106
01107
01108
01109
01110
01111
01112
01113
01114
01115
01116
01117
01118
01119
01120
01121
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133 template<typename T> unsigned gap_set_value(unsigned val,
01134 T* BMRESTRICT buf,
01135 unsigned pos,
01136 unsigned* BMRESTRICT is_set)
01137 {
01138 BM_ASSERT(pos < bm::gap_max_bits);
01139 unsigned curr = gap_bfind(buf, pos, is_set);
01140
01141 register T end = (*buf >> 3);
01142 if (*is_set == val)
01143 {
01144 *is_set = 0;
01145 return end;
01146 }
01147 *is_set = 1;
01148
01149 register T* pcurr = buf + curr;
01150 register T* pprev = pcurr - 1;
01151 register T* pend = buf + end;
01152
01153
01154
01155 if (pos == 0)
01156 {
01157 *buf ^= 1;
01158 if ( buf[1] )
01159 {
01160 ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
01161 buf[1] = 0;
01162 ++end;
01163 }
01164 else
01165 {
01166 pprev = buf + 1;
01167 pcurr = pprev + 1;
01168 do
01169 {
01170 *pprev++ = *pcurr++;
01171 } while (pcurr < pend);
01172 --end;
01173 }
01174 }
01175 else if (curr > 1 && ((unsigned)(*pprev))+1 == pos)
01176 {
01177 ++(*pprev);
01178 if (*pprev == *pcurr)
01179 {
01180 --end;
01181 if (pcurr != pend)
01182 {
01183 --end;
01184 ++pcurr;
01185 do
01186 {
01187 *pprev++ = *pcurr++;
01188 } while (pcurr < pend);
01189 }
01190 }
01191 }
01192 else if (*pcurr == pos)
01193 {
01194 --(*pcurr);
01195 if (pcurr == pend)
01196 {
01197 ++end;
01198 }
01199 }
01200 else
01201 {
01202 ::memmove(pcurr+2, pcurr,(end - curr + 1)*sizeof(T));
01203 *pcurr++ = pos - 1;
01204 *pcurr = pos;
01205 end+=2;
01206 }
01207
01208
01209 *buf = (*buf & 7) + (end << 3);
01210
01211 buf[end] = bm::gap_max_bits - 1;
01212 return end;
01213 }
01214
01215
01216
01217
01218
01219
01220
01221
01222
01223
01224
01225 template<typename T> int gap_find_in_block(const T* buf,
01226 unsigned nbit,
01227 bm::id_t* prev)
01228 {
01229 BM_ASSERT(nbit < bm::gap_max_bits);
01230
01231 unsigned bitval;
01232 unsigned gap_idx = bm::gap_bfind(buf, nbit, &bitval);
01233
01234 if (bitval)
01235 {
01236 return 1;
01237 }
01238
01239 register unsigned val = buf[gap_idx] + 1;
01240 *prev += val - nbit;
01241
01242 return (val != bm::gap_max_bits);
01243 }
01244
01245
01246
01247
01248
01249
01250 BMFORCEINLINE void set_bit(unsigned* dest, unsigned bitpos)
01251 {
01252 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01253 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01254 nbit &= bm::set_word_mask;
01255 dest[nword] |= unsigned(1 << nbit);
01256 }
01257
01258
01259
01260
01261
01262
01263 BMFORCEINLINE unsigned test_bit(const unsigned* block, unsigned bitpos)
01264 {
01265 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01266 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01267 nbit &= bm::set_word_mask;
01268 return block[nword] & unsigned(1 << nbit);
01269 }
01270
01271
01272
01273
01274
01275
01276
01277
01278
01279
01280 inline void or_bit_block(unsigned* dest,
01281 unsigned bitpos,
01282 unsigned bitcount)
01283 {
01284 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01285 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01286 nbit &= bm::set_word_mask;
01287
01288 bm::word_t* word = dest + nword;
01289
01290 if (bitcount == 1)
01291 {
01292 *word |= unsigned(1 << nbit);
01293 return;
01294 }
01295
01296 if (nbit)
01297 {
01298 unsigned right_margin = nbit + bitcount;
01299
01300
01301
01302
01303 if (right_margin < 32)
01304 {
01305 unsigned mask =
01306 block_set_table<true>::_right[nbit] &
01307 block_set_table<true>::_left[right_margin-1];
01308 *word |= mask;
01309 return;
01310 }
01311 else
01312 {
01313 *word |= block_set_table<true>::_right[nbit];
01314 bitcount -= 32 - nbit;
01315 }
01316 ++word;
01317 }
01318
01319
01320
01321
01322 for ( ;bitcount >= 32; bitcount -= 32)
01323 {
01324 *word++ = 0xffffffff;
01325 }
01326
01327 if (bitcount)
01328 {
01329 *word |= block_set_table<true>::_left[bitcount-1];
01330 }
01331 }
01332
01333
01334
01335
01336
01337
01338
01339
01340
01341
01342 inline void sub_bit_block(unsigned* dest,
01343 unsigned bitpos,
01344 unsigned bitcount)
01345 {
01346 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01347 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01348 nbit &= bm::set_word_mask;
01349
01350 bm::word_t* word = dest + nword;
01351
01352 if (bitcount == 1)
01353 {
01354 *word &= ~unsigned(1 << nbit);
01355 return;
01356 }
01357
01358 if (nbit)
01359 {
01360 unsigned right_margin = nbit + bitcount;
01361
01362
01363
01364
01365 if (right_margin < 32)
01366 {
01367 unsigned mask =
01368 block_set_table<true>::_right[nbit] &
01369 block_set_table<true>::_left[right_margin-1];
01370 *word &= ~mask;
01371 return;
01372 }
01373 else
01374 {
01375 *word &= ~block_set_table<true>::_right[nbit];
01376 bitcount -= 32 - nbit;
01377 }
01378 ++word;
01379 }
01380
01381
01382
01383
01384 for ( ;bitcount >= 32; bitcount -= 32)
01385 {
01386 *word++ = 0;
01387 }
01388
01389 if (bitcount)
01390 {
01391 *word &= ~block_set_table<true>::_left[bitcount-1];
01392 }
01393 }
01394
01395
01396
01397
01398
01399
01400
01401
01402
01403
01404 inline void xor_bit_block(unsigned* dest,
01405 unsigned bitpos,
01406 unsigned bitcount)
01407 {
01408 unsigned nbit = unsigned(bitpos & bm::set_block_mask);
01409 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01410 nbit &= bm::set_word_mask;
01411
01412 bm::word_t* word = dest + nword;
01413
01414 if (bitcount == 1)
01415 {
01416 *word ^= unsigned(1 << nbit);
01417 return;
01418 }
01419
01420 if (nbit)
01421 {
01422 unsigned right_margin = nbit + bitcount;
01423
01424
01425
01426
01427 if (right_margin < 32)
01428 {
01429 unsigned mask =
01430 block_set_table<true>::_right[nbit] &
01431 block_set_table<true>::_left[right_margin-1];
01432 *word ^= mask;
01433 return;
01434 }
01435 else
01436 {
01437 *word ^= block_set_table<true>::_right[nbit];
01438 bitcount -= 32 - nbit;
01439 }
01440 ++word;
01441 }
01442
01443
01444
01445
01446 for ( ;bitcount >= 32; bitcount -= 32)
01447 {
01448 *word++ ^= 0xffffffff;
01449 }
01450
01451 if (bitcount)
01452 {
01453 *word ^= block_set_table<true>::_left[bitcount-1];
01454 }
01455 }
01456
01457
01458
01459
01460
01461
01462
01463
01464
01465 template<typename T>
01466 void gap_sub_to_bitset(unsigned* dest, const T* buf)
01467 {
01468 register const T* pcurr = buf;
01469 register const T* pend = pcurr + (*pcurr >> 3);
01470 ++pcurr;
01471
01472 if (*buf & 1)
01473 {
01474 sub_bit_block(dest, 0, *pcurr + 1);
01475 ++pcurr;
01476 }
01477 ++pcurr;
01478
01479 while (pcurr <= pend)
01480 {
01481 unsigned bitpos = *(pcurr-1) + 1;
01482 BM_ASSERT(*pcurr > *(pcurr-1));
01483 unsigned gap_len = *pcurr - *(pcurr-1);
01484 sub_bit_block(dest, bitpos, gap_len);
01485 pcurr += 2;
01486 }
01487 }
01488
01489
01490
01491
01492
01493
01494
01495
01496
01497 template<typename T>
01498 void gap_xor_to_bitset(unsigned* dest, const T* buf)
01499 {
01500 register const T* pcurr = buf;
01501 register const T* pend = pcurr + (*pcurr >> 3);
01502 ++pcurr;
01503
01504 if (*buf & 1)
01505 {
01506 xor_bit_block(dest, 0, *pcurr + 1);
01507 ++pcurr;
01508 }
01509 ++pcurr;
01510
01511 while (pcurr <= pend)
01512 {
01513 unsigned bitpos = *(pcurr-1) + 1;
01514 BM_ASSERT(*pcurr > *(pcurr-1));
01515 unsigned gap_len = *pcurr - *(pcurr-1);
01516 xor_bit_block(dest, bitpos, gap_len);
01517 pcurr += 2;
01518 }
01519 }
01520
01521
01522
01523
01524
01525
01526
01527
01528
01529 template<typename T>
01530 void gap_add_to_bitset(unsigned* dest, const T* buf)
01531 {
01532 register const T* pcurr = buf;
01533 register const T* pend = pcurr + (*pcurr >> 3);
01534 ++pcurr;
01535
01536 if (*buf & 1)
01537 {
01538 or_bit_block(dest, 0, *pcurr + 1);
01539 ++pcurr;
01540 }
01541 ++pcurr;
01542
01543 while (pcurr <= pend)
01544 {
01545 unsigned bitpos = *(pcurr-1) + 1;
01546 BM_ASSERT(*pcurr > *(pcurr-1));
01547 unsigned gap_len = *pcurr - *(pcurr-1);
01548 or_bit_block(dest, bitpos, gap_len);
01549 pcurr += 2;
01550 }
01551 }
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561 template<typename T>
01562 void gap_and_to_bitset(unsigned* dest, const T* buf)
01563 {
01564 register const T* pcurr = buf;
01565 register const T* pend = pcurr + (*pcurr >> 3);
01566 ++pcurr;
01567
01568 if (! (*buf & 1) )
01569 {
01570
01571 sub_bit_block(dest, 0, *pcurr + 1);
01572 ++pcurr;
01573 }
01574 ++pcurr;
01575
01576 while (pcurr <= pend)
01577 {
01578 unsigned bitpos = *(pcurr-1) + 1;
01579 BM_ASSERT(*pcurr > *(pcurr-1));
01580 unsigned gap_len = *pcurr - *(pcurr-1);
01581 sub_bit_block(dest, bitpos, gap_len);
01582 pcurr += 2;
01583 }
01584 }
01585
01586
01587
01588
01589
01590
01591
01592
01593
01594 template<typename T>
01595 bm::id_t gap_bitset_and_count(const unsigned* block, const T* buf)
01596 {
01597 BM_ASSERT(block);
01598
01599 register const T* pcurr = buf;
01600 register const T* pend = pcurr + (*pcurr >> 3);
01601 ++pcurr;
01602
01603 bm::id_t count = 0;
01604
01605 if (*buf & 1)
01606 {
01607 count += bit_block_calc_count_range(block, 0, *pcurr);
01608 ++pcurr;
01609 }
01610 ++pcurr;
01611
01612 while (pcurr <= pend)
01613 {
01614 bm::id_t c = bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01615
01616 count += c;
01617 pcurr += 2;
01618 }
01619 return count;
01620 }
01621
01622
01623
01624
01625
01626
01627
01628
01629
01630 template<typename T>
01631 bm::id_t gap_bitset_and_any(const unsigned* block, const T* buf)
01632 {
01633 BM_ASSERT(block);
01634
01635 register const T* pcurr = buf;
01636 register const T* pend = pcurr + (*pcurr >> 3);
01637 ++pcurr;
01638
01639 bm::id_t count = 0;
01640 if (*buf & 1)
01641 {
01642 count += bit_block_any_range(block, 0, *pcurr);
01643 if (count)
01644 return count;
01645 ++pcurr;
01646 }
01647 ++pcurr;
01648
01649 while (pcurr <= pend)
01650 {
01651 bm::id_t c = bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
01652 count += c;
01653 if (count)
01654 break;
01655 pcurr += 2;
01656 }
01657 return count;
01658 }
01659
01660
01661
01662
01663
01664
01665
01666
01667
01668
01669 template<typename T>
01670 bm::id_t gap_bitset_sub_count(const unsigned* block, const T* buf)
01671 {
01672 BM_ASSERT(block);
01673
01674 register const T* pcurr = buf;
01675 register const T* pend = pcurr + (*pcurr >> 3);
01676 ++pcurr;
01677
01678 bm::id_t count = 0;
01679
01680 if (!(*buf & 1))
01681 {
01682 count += bit_block_calc_count_range(block, 0, *pcurr);
01683 ++pcurr;
01684 }
01685 ++pcurr;
01686
01687 for (;pcurr <= pend; pcurr+=2)
01688 {
01689 count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
01690 }
01691 return count;
01692 }
01693
01694
01695
01696
01697
01698
01699
01700
01701
01702 template<typename T>
01703 bm::id_t gap_bitset_sub_any(const unsigned* block, const T* buf)
01704 {
01705 BM_ASSERT(block);
01706
01707 register const T* pcurr = buf;
01708 register const T* pend = pcurr + (*pcurr >> 3);
01709 ++pcurr;
01710
01711 bm::id_t count = 0;
01712
01713 if (!(*buf & 1))
01714 {
01715 count += bit_block_any_range(block, 0, *pcurr);
01716 if (count)
01717 return count;
01718 ++pcurr;
01719 }
01720 ++pcurr;
01721
01722 for (;pcurr <= pend; pcurr+=2)
01723 {
01724 count += bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
01725 if (count)
01726 return count;
01727 }
01728 return count;
01729 }
01730
01731
01732
01733
01734
01735
01736
01737
01738
01739
01740 template<typename T>
01741 bm::id_t gap_bitset_xor_count(const unsigned* block, const T* buf)
01742 {
01743 BM_ASSERT(block);
01744
01745 register const T* pcurr = buf;
01746 register const T* pend = pcurr + (*pcurr >> 3);
01747 ++pcurr;
01748
01749 unsigned bitval = *buf & 1;
01750
01751 register bm::id_t count = bit_block_calc_count_range(block, 0, *pcurr);
01752 if (bitval)
01753 {
01754 count = *pcurr + 1 - count;
01755 }
01756
01757 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01758 {
01759 T prev = *(pcurr-1)+1;
01760 bm::id_t c = bit_block_calc_count_range(block, prev, *pcurr);
01761
01762 if (bitval)
01763 {
01764 c = (*pcurr - prev + 1) - c;
01765 }
01766 count += c;
01767 }
01768 return count;
01769 }
01770
01771
01772
01773
01774
01775
01776
01777
01778 template<typename T>
01779 bm::id_t gap_bitset_xor_any(const unsigned* block, const T* buf)
01780 {
01781 BM_ASSERT(block);
01782
01783 register const T* pcurr = buf;
01784 register const T* pend = pcurr + (*pcurr >> 3);
01785 ++pcurr;
01786
01787 unsigned bitval = *buf & 1;
01788
01789 register bm::id_t count = bit_block_any_range(block, 0, *pcurr);
01790 if (bitval)
01791 {
01792 count = *pcurr + 1 - count;
01793 }
01794
01795 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01796 {
01797 T prev = *(pcurr-1)+1;
01798 bm::id_t c = bit_block_any_range(block, prev, *pcurr);
01799
01800 if (bitval)
01801 {
01802 c = (*pcurr - prev + 1) - c;
01803 }
01804
01805 count += c;
01806 if (count)
01807 return count;
01808 }
01809 return count;
01810 }
01811
01812
01813
01814
01815
01816
01817
01818
01819
01820
01821 template<typename T>
01822 bm::id_t gap_bitset_or_count(const unsigned* block, const T* buf)
01823 {
01824 BM_ASSERT(block);
01825
01826 register const T* pcurr = buf;
01827 register const T* pend = pcurr + (*pcurr >> 3);
01828 ++pcurr;
01829
01830 unsigned bitval = *buf & 1;
01831
01832 register bm::id_t count;
01833 if (bitval)
01834 {
01835 count = *pcurr + 1;
01836 }
01837 else
01838 {
01839 count = bit_block_calc_count_range(block, 0, *pcurr);
01840 }
01841
01842 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01843 {
01844 T prev = *(pcurr-1)+1;
01845 bm::id_t c;
01846
01847 if (bitval)
01848 {
01849 c = (*pcurr - prev + 1);
01850 }
01851 else
01852 {
01853 c = bit_block_calc_count_range(block, prev, *pcurr);
01854 }
01855
01856 count += c;
01857 }
01858 return count;
01859 }
01860
01861
01862
01863
01864
01865
01866
01867
01868 template<typename T>
01869 bm::id_t gap_bitset_or_any(const unsigned* block, const T* buf)
01870 {
01871 BM_ASSERT(block);
01872
01873 register const T* pcurr = buf;
01874 register const T* pend = pcurr + (*pcurr >> 3);
01875 ++pcurr;
01876
01877 unsigned bitval = *buf & 1;
01878
01879 register bm::id_t count;
01880 if (bitval)
01881 {
01882 count = *pcurr + 1;
01883 }
01884 else
01885 {
01886 count = bit_block_any_range(block, 0, *pcurr);
01887 }
01888
01889 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
01890 {
01891 T prev = *(pcurr-1)+1;
01892 bm::id_t c;
01893
01894 if (bitval)
01895 {
01896 c = (*pcurr - prev + 1);
01897 }
01898 else
01899 {
01900 c = bit_block_any_range(block, prev, *pcurr);
01901 }
01902 count += c;
01903 if (count)
01904 return count;
01905 }
01906 return count;
01907 }
01908
01909
01910
01911
01912
01913
01914
01915
01916
01917
01918
01919 inline
01920 void bit_block_set(bm::word_t* BMRESTRICT dst, bm::word_t value)
01921 {
01922
01923
01924
01925 ::memset(dst, value, bm::set_block_size * sizeof(bm::word_t));
01926
01927 }
01928
01929
01930
01931
01932
01933
01934
01935
01936
01937 template<typename T>
01938 void gap_convert_to_bitset(unsigned* dest, const T* buf)
01939 {
01940 bit_block_set(dest, 0);
01941 gap_add_to_bitset(dest, buf);
01942 }
01943
01944
01945
01946
01947
01948
01949
01950
01951
01952
01953 template<typename T>
01954 void gap_convert_to_bitset(unsigned* dest, const T* buf, unsigned dest_len)
01955 {
01956 ::memset(dest, 0, dest_len * sizeof(unsigned));
01957 gap_add_to_bitset(dest, buf);
01958 }
01959
01960
01961
01962
01963
01964
01965
01966
01967
01968
01969
01970
01971
01972
01973
01974 template<typename T>
01975 unsigned* gap_convert_to_bitset_smart(unsigned* dest,
01976 const T* buf,
01977 id_t set_max)
01978 {
01979 if (buf[1] == set_max - 1)
01980 {
01981 return (buf[0] & 1) ? FULL_BLOCK_ADDR : 0;
01982 }
01983
01984 gap_convert_to_bitset(dest, buf);
01985 return dest;
01986 }
01987
01988
01989
01990
01991
01992
01993
01994
01995
01996
01997 template<typename T> unsigned gap_control_sum(const T* buf)
01998 {
01999 unsigned end = *buf >> 3;
02000
02001 register const T* pcurr = buf;
02002 register const T* pend = pcurr + (*pcurr >> 3);
02003 ++pcurr;
02004
02005 if (*buf & 1)
02006 {
02007 ++pcurr;
02008 }
02009 ++pcurr;
02010
02011 while (pcurr <= pend)
02012 {
02013 BM_ASSERT(*pcurr > *(pcurr-1));
02014 pcurr += 2;
02015 }
02016 return buf[end];
02017
02018 }
02019
02020
02021
02022
02023
02024
02025
02026
02027
02028 template<class T> void gap_set_all(T* buf,
02029 unsigned set_max,
02030 unsigned value)
02031 {
02032 BM_ASSERT(value == 0 || value == 1);
02033 *buf = (*buf & 6u) + (1u << 3) + value;
02034 *(++buf) = set_max - 1;
02035 }
02036
02037
02038
02039
02040
02041
02042
02043
02044
02045
02046
02047
02048 template<class T>
02049 void gap_init_range_block(T* buf,
02050 unsigned from,
02051 unsigned to,
02052 unsigned value,
02053 unsigned set_max)
02054 {
02055 BM_ASSERT(value == 0 || value == 1);
02056
02057 unsigned gap_len;
02058 if (from == 0)
02059 {
02060 if (to == set_max - 1)
02061 {
02062 gap_set_all(buf, set_max, value);
02063 }
02064 else
02065 {
02066 gap_len = 2;
02067 buf[1] = to;
02068 buf[2] = set_max - 1;
02069 buf[0] = (*buf & 6u) + (gap_len << 3) + value;
02070 }
02071 return;
02072 }
02073
02074
02075 value = !value;
02076 if (to == set_max - 1)
02077 {
02078 gap_len = 2;
02079 buf[1] = from - 1;
02080 buf[2] = set_max - 1;
02081 }
02082 else
02083 {
02084 gap_len = 3;
02085 buf[1] = from - 1;
02086 buf[2] = to;
02087 buf[3] = set_max - 1;
02088 }
02089 buf[0] = (*buf & 6u) + (gap_len << 3) + value;
02090 }
02091
02092
02093
02094
02095
02096
02097
02098
02099 template<typename T> void gap_invert(T* buf)
02100 {
02101 *buf ^= 1;
02102 }
02103
02104
02105
02106
02107
02108
02109
02110
02111
02112
02113
02114
02115
02116
02117
02118
02119
02120
02121
02122
02123
02124
02125
02126
02127
02128
02129
02130 template<typename T>
02131 bool gap_is_all_zero(const T* buf, unsigned set_max)
02132 {
02133 return (((*buf & 1)==0) && (*(++buf) == set_max - 1));
02134 }
02135
02136
02137
02138
02139
02140
02141
02142
02143
02144 template<typename T>
02145 bool gap_is_all_one(const T* buf, unsigned set_max)
02146 {
02147 return ((*buf & 1) && (*(++buf) == set_max - 1));
02148 }
02149
02150
02151
02152
02153
02154
02155
02156
02157 template<typename T> unsigned gap_length(const T* buf)
02158 {
02159 return (*buf >> 3) + 1;
02160 }
02161
02162
02163
02164
02165
02166
02167
02168
02169
02170 template<typename T>
02171 unsigned gap_capacity(const T* buf, const T* glevel_len)
02172 {
02173 return glevel_len[(*buf >> 1) & 3];
02174 }
02175
02176
02177
02178
02179
02180
02181
02182
02183
02184
02185 template<typename T>
02186 unsigned gap_limit(const T* buf, const T* glevel_len)
02187 {
02188 return glevel_len[(*buf >> 1) & 3]-4;
02189 }
02190
02191
02192
02193
02194
02195
02196
02197
02198
02199 template<typename T> unsigned gap_level(const T* buf)
02200 {
02201 return (*buf >> 1) & 3;
02202 }
02203
02204
02205
02206
02207
02208
02209
02210
02211
02212 template<typename T> void set_gap_level(T* buf,
02213 unsigned level)
02214 {
02215 BM_ASSERT(level < bm::gap_levels);
02216 *buf = ((level & 3) << 1) | (*buf & 1) | (*buf & ~7);
02217 }
02218
02219
02220
02221
02222
02223
02224
02225
02226
02227
02228 template<typename T>
02229 inline int gap_calc_level(int len, const T* glevel_len)
02230 {
02231 if (len <= (glevel_len[0]-4)) return 0;
02232 if (len <= (glevel_len[1]-4)) return 1;
02233 if (len <= (glevel_len[2]-4)) return 2;
02234 if (len <= (glevel_len[3]-4)) return 3;
02235
02236 BM_ASSERT(bm::gap_levels == 4);
02237 return -1;
02238 }
02239
02240
02241
02242
02243
02244
02245
02246
02247
02248
02249 template<typename T>
02250 inline unsigned gap_free_elements(const T* buf, const T* glevel_len)
02251 {
02252 unsigned len = gap_length(buf);
02253 unsigned capacity = gap_capacity(buf, glevel_len);
02254 return capacity - len;
02255 }
02256
02257
02258
02259
02260
02261
02262
02263
02264
02265
02266
02267 template<typename T>
02268 int bitcmp(const T* buf1, const T* buf2, unsigned len)
02269 {
02270 BM_ASSERT(len);
02271 const T* pend1 = buf1 + len;
02272 do
02273 {
02274 T w1 = *buf1++;
02275 T w2 = *buf2++;
02276 T diff = w1 ^ w2;
02277
02278 if (diff)
02279 {
02280 return (w1 & diff & -diff) ? 1 : -1;
02281 }
02282
02283 } while (buf1 < pend1);
02284
02285 return 0;
02286 }
02287
02288
02289
02290
02291
02292
02293
02294
02295
02296
02297
02298
02299
02300 template<typename T>
02301 unsigned bit_convert_to_gap(T* BMRESTRICT dest,
02302 const unsigned* BMRESTRICT src,
02303 bm::id_t bits,
02304 unsigned dest_len)
02305 {
02306 register T* BMRESTRICT pcurr = dest;
02307 T* BMRESTRICT end = dest + dest_len;
02308 register int bitval = (*src) & 1;
02309
02310 *pcurr = bitval;
02311
02312 ++pcurr;
02313 *pcurr = 0;
02314 register unsigned bit_idx = 0;
02315 register int bitval_next;
02316
02317 unsigned val = *src;
02318
02319 do
02320 {
02321
02322
02323 while (val == 0 || val == 0xffffffff)
02324 {
02325 bitval_next = val ? 1 : 0;
02326 if (bitval != bitval_next)
02327 {
02328 *pcurr++ = bit_idx-1;
02329 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
02330 if (pcurr >= end)
02331 {
02332 return 0;
02333 }
02334 bitval = bitval_next;
02335 }
02336 bit_idx += sizeof(*src) * 8;
02337 if (bit_idx >= bits)
02338 {
02339 goto complete;
02340 }
02341 ++src;
02342 val = *src;
02343 }
02344
02345
02346 register unsigned mask = 1;
02347 while (mask)
02348 {
02349
02350
02351 bitval_next = val & mask ? 1 : 0;
02352 if (bitval != bitval_next)
02353 {
02354 *pcurr++ = bit_idx-1;
02355 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
02356 bitval = bitval_next;
02357 if (pcurr >= end)
02358 {
02359 return 0;
02360 }
02361 }
02362
02363 mask <<= 1;
02364 ++bit_idx;
02365
02366 }
02367
02368 if (bit_idx >= bits)
02369 {
02370 goto complete;
02371 }
02372
02373 ++src;
02374 val = *src;
02375
02376 } while(1);
02377
02378 complete:
02379 *pcurr = bit_idx-1;
02380 unsigned len = (unsigned)(pcurr - dest);
02381 *dest = (*dest & 7) + (len << 3);
02382 return len;
02383 }
02384
02385
02386
02387
02388
02389
02390 template<class T, class F>
02391 void for_each_gap_dbit(const T* buf, F& func)
02392 {
02393 const T* pcurr = buf;
02394 const T* pend = pcurr + (*pcurr >> 3);
02395
02396 ++pcurr;
02397
02398 unsigned prev = 0;
02399 unsigned first_inc;
02400
02401 if (*buf & 1)
02402 {
02403 first_inc = 0;
02404 unsigned to = *pcurr;
02405 for (unsigned i = 0; i <= to; ++i)
02406 {
02407 func(1);
02408 }
02409 prev = to;
02410 ++pcurr;
02411 }
02412 else
02413 {
02414 first_inc = 1;
02415 }
02416 ++pcurr;
02417
02418 while (pcurr <= pend)
02419 {
02420 unsigned from = *(pcurr-1)+1;
02421 unsigned to = *pcurr;
02422 if (first_inc)
02423 {
02424 func(from - prev + first_inc);
02425 first_inc = 0;
02426 }
02427 else
02428 {
02429 func(from - prev);
02430 }
02431
02432 for (unsigned i = from+1; i <= to; ++i)
02433 {
02434 func(1);
02435 }
02436 prev = to;
02437 pcurr += 2;
02438 }
02439 }
02440
02441
02442
02443
02444
02445 template<typename D, typename T>
02446 D gap_convert_to_arr(D* BMRESTRICT dest,
02447 const T* BMRESTRICT buf,
02448 unsigned dest_len,
02449 bool invert = false)
02450 {
02451 register const T* BMRESTRICT pcurr = buf;
02452 register const T* pend = pcurr + (*pcurr >> 3);
02453
02454 D* BMRESTRICT dest_curr = dest;
02455 ++pcurr;
02456
02457 int bitval = (*buf) & 1;
02458 if (invert)
02459 bitval = !bitval;
02460
02461 if (bitval)
02462 {
02463 if (unsigned(*pcurr + 1) >= dest_len)
02464 return 0;
02465 dest_len -= *pcurr;
02466 T to = *pcurr;
02467 for (T i = 0; ;++i)
02468 {
02469 *dest_curr++ = i;
02470 if (i == to) break;
02471 }
02472 ++pcurr;
02473 }
02474 ++pcurr;
02475
02476 while (pcurr <= pend)
02477 {
02478 unsigned pending = *pcurr - *(pcurr-1);
02479 if (pending >= dest_len)
02480 return 0;
02481 dest_len -= pending;
02482 T from = *(pcurr-1)+1;
02483 T to = *pcurr;
02484 for (T i = from; ;++i)
02485 {
02486 *dest_curr++ = i;
02487 if (i == to) break;
02488 }
02489 pcurr += 2;
02490 }
02491 return (D) (dest_curr - dest);
02492 }
02493
02494
02495
02496
02497
02498
02499
02500
02501
02502
02503
02504 inline
02505 bm::id_t bit_block_calc_count(const bm::word_t* block,
02506 const bm::word_t* block_end)
02507 {
02508 BM_ASSERT(block < block_end);
02509 bm::id_t count = 0;
02510
02511 #ifdef BMVECTOPT
02512 count = VECT_BITCOUNT(block, block_end);
02513 #else
02514 #ifdef BM64OPT
02515
02516
02517
02518 const bm::id64_t* b1 = (bm::id64_t*) block;
02519 const bm::id64_t* b2 = (bm::id64_t*) block_end;
02520 do
02521 {
02522 count += bitcount64_4way(b1[0], b1[1], b1[2], b1[3]);
02523 b1 += 4;
02524 } while (b1 < b2);
02525 #else
02526
02527
02528
02529
02530 bm::word_t acc = *block++;
02531 do
02532 {
02533 bm::word_t in = *block++;
02534 bm::word_t acc_prev = acc;
02535 acc |= in;
02536 if (acc_prev &= in)
02537 {
02538 BM_INCWORD_BITCOUNT(count, acc);
02539 acc = acc_prev;
02540 }
02541 } while (block < block_end);
02542
02543 BM_INCWORD_BITCOUNT(count, acc);
02544
02545 #endif
02546 #endif
02547 return count;
02548 }
02549
02550
02551
02552
02553
02554
02555
02556
02557
02558
02559
02560
02561
02562
02563
02564 inline
02565 bm::id_t bit_count_change(bm::word_t w)
02566 {
02567 unsigned count = 1;
02568 w ^= (w >> 1);
02569
02570 BM_INCWORD_BITCOUNT(count, w);
02571 count -= (w >> ((sizeof(w) * 8) - 1));
02572 return count;
02573 }
02574
02575
02576
02577
02578
02579
02580 inline
02581 void bit_count_change32(const bm::word_t* block,
02582 const bm::word_t* block_end,
02583 unsigned* bit_count,
02584 unsigned* gap_count)
02585 {
02586 BM_ASSERT(block < block_end);
02587 BM_ASSERT(bit_count);
02588 BM_ASSERT(gap_count);
02589
02590 *gap_count = 1;
02591 *bit_count = 0;
02592
02593 bm::word_t w, w0, w_prev, w_l;
02594 w = w0 = *block;
02595
02596 BM_INCWORD_BITCOUNT(*bit_count, w);
02597
02598 const int w_shift = sizeof(w) * 8 - 1;
02599 w ^= (w >> 1);
02600 BM_INCWORD_BITCOUNT(*gap_count, w);
02601 *gap_count -= (w_prev = (w0 >> w_shift));
02602
02603 for (++block ;block < block_end; ++block)
02604 {
02605 w = w0 = *block;
02606 ++(*gap_count);
02607
02608 if (!w)
02609 {
02610 *gap_count -= !w_prev;
02611 w_prev = 0;
02612 }
02613 else
02614 {
02615 BM_INCWORD_BITCOUNT(*bit_count, w);
02616
02617 w ^= (w >> 1);
02618 BM_INCWORD_BITCOUNT(*gap_count, w);
02619
02620 w_l = w0 & 1;
02621 *gap_count -= (w0 >> w_shift);
02622 *gap_count -= !(w_prev ^ w_l);
02623
02624 w_prev = (w0 >> w_shift);
02625 }
02626 }
02627
02628 }
02629
02630
02631
02632
02633
02634
02635
02636
02637
02638
02639
02640
02641
02642 inline
02643 bm::id_t bit_block_calc_count_change(const bm::word_t* block,
02644 const bm::word_t* block_end,
02645 unsigned* bit_count)
02646 {
02647 #if defined(BMSSE2OPT) || defined(BMSSE42OPT)
02648
02649 #ifdef BMSSE42OPT
02650 return sse4_bit_block_calc_count_change(
02651 (const __m128i*)block, (const __m128i*)block_end, bit_count);
02652 #else
02653 # ifdef BMSSE2OPT
02654 return sse2_bit_block_calc_count_change(
02655 (const __m128i*)block, (const __m128i*)block_end, bit_count);
02656 # endif
02657 #endif
02658
02659 #else // non-SSE code
02660
02661 BM_ASSERT(block < block_end);
02662 BM_ASSERT(bit_count);
02663
02664
02665 #ifdef BM64OPT
02666 bm::id_t count = 1;
02667 *bit_count = 0;
02668
02669
02670
02671 const bm::id64_t* b1 = (bm::id64_t*) block;
02672 const bm::id64_t* b2 = (bm::id64_t*) block_end;
02673
02674 bm::id64_t w, w0, w_prev, w_l;
02675 w = w0 = *b1;
02676
02677 *bit_count = word_bitcount64(w);
02678
02679 const int w_shift = sizeof(w) * 8 - 1;
02680 w ^= (w >> 1);
02681 count += word_bitcount64(w);
02682 count -= (w_prev = (w0 >> w_shift));
02683
02684
02685 for (++b1 ;b1 < b2; ++b1)
02686 {
02687 w = w0 = *b1;
02688
02689 ++count;
02690
02691 if (!w)
02692 {
02693 count -= !w_prev;
02694 w_prev = 0;
02695 }
02696 else
02697 {
02698 *bit_count += word_bitcount64(w);
02699 w ^= (w >> 1);
02700 count += word_bitcount64(w);
02701
02702 w_l = w0 & 1;
02703 count -= (w0 >> w_shift);
02704 count -= !(w_prev ^ w_l);
02705
02706 w_prev = (w0 >> w_shift);
02707 }
02708 }
02709 return count;
02710
02711 #else
02712 unsigned gap_count;
02713 bit_count_change32(block, block_end, bit_count, &gap_count);
02714 return gap_count;
02715 #endif
02716
02717 #endif
02718 }
02719
02720
02721
02722
02723
02724
02725
02726
02727
02728 inline
02729 bm::id_t bit_block_calc_count_range(const bm::word_t* block,
02730 bm::word_t left,
02731 bm::word_t right)
02732 {
02733 BM_ASSERT(left <= right);
02734
02735 unsigned nbit = left;
02736 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02737 nbit &= bm::set_word_mask;
02738
02739 const bm::word_t* word = block + nword;
02740
02741 if (left == right)
02742 {
02743 return (*word >> nbit) & 1;
02744 }
02745 bm::id_t count = 0;
02746
02747 unsigned acc;
02748 unsigned bitcount = right - left + 1;
02749
02750 if (nbit)
02751 {
02752 unsigned right_margin = nbit + (right - left);
02753
02754 if (right_margin < 32)
02755 {
02756 unsigned mask =
02757 block_set_table<true>::_right[nbit] &
02758 block_set_table<true>::_left[right_margin];
02759 acc = *word & mask;
02760
02761 BM_INCWORD_BITCOUNT(count, acc);
02762 return count;
02763 }
02764 else
02765 {
02766 acc = *word & block_set_table<true>::_right[nbit];
02767 BM_INCWORD_BITCOUNT(count, acc);
02768 bitcount -= 32 - nbit;
02769 }
02770 ++word;
02771 }
02772
02773
02774 for ( ;bitcount >= 32; bitcount -= 32)
02775 {
02776 acc = *word++;
02777 BM_INCWORD_BITCOUNT(count, acc);
02778 }
02779
02780 if (bitcount)
02781 {
02782 acc = (*word) & block_set_table<true>::_left[bitcount-1];
02783 BM_INCWORD_BITCOUNT(count, acc);
02784 }
02785
02786 return count;
02787 }
02788
02789
02790
02791
02792
02793
02794
02795
02796
02797 inline
02798 bm::id_t bit_block_any_range(const bm::word_t* block,
02799 bm::word_t left,
02800 bm::word_t right)
02801 {
02802 BM_ASSERT(left <= right);
02803
02804 unsigned nbit = left;
02805 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02806 nbit &= bm::set_word_mask;
02807
02808 const bm::word_t* word = block + nword;
02809
02810 if (left == right)
02811 {
02812 return (*word >> nbit) & 1;
02813 }
02814 unsigned acc;
02815 unsigned bitcount = right - left + 1;
02816
02817 if (nbit)
02818 {
02819 unsigned right_margin = nbit + (right - left);
02820 if (right_margin < 32)
02821 {
02822 unsigned mask =
02823 block_set_table<true>::_right[nbit] &
02824 block_set_table<true>::_left[right_margin];
02825 acc = *word & mask;
02826 return acc;
02827 }
02828 else
02829 {
02830 acc = *word & block_set_table<true>::_right[nbit];
02831 if (acc)
02832 return acc;
02833 bitcount -= 32 - nbit;
02834 }
02835 ++word;
02836 }
02837
02838
02839 for ( ;bitcount >= 32; bitcount -= 32)
02840 {
02841 acc = *word++;
02842 if (acc)
02843 return acc;
02844 }
02845
02846 if (bitcount)
02847 {
02848 acc = (*word) & block_set_table<true>::_left[bitcount-1];
02849 if (acc)
02850 return acc;
02851 }
02852
02853 return 0;
02854 }
02855
02856
02857
02858
02859
02860
02861
02862
02863 template<typename T> void bit_invert(T* start, T* end)
02864 {
02865 #ifdef BMVECTOPT
02866 VECT_INVERT_ARR(start, end);
02867 #else
02868 do
02869 {
02870 start[0] = ~start[0];
02871 start[1] = ~start[1];
02872 start[2] = ~start[2];
02873 start[3] = ~start[3];
02874 start+=4;
02875 } while (start < end);
02876 #endif
02877 }
02878
02879
02880
02881
02882
02883
02884 inline bool is_bits_one(const bm::wordop_t* start,
02885 const bm::wordop_t* end)
02886 {
02887 do
02888 {
02889 bm::wordop_t tmp =
02890 start[0] & start[1] & start[2] & start[3];
02891 if (tmp != bm::all_bits_mask)
02892 return false;
02893 start += 4;
02894 } while (start < end);
02895
02896 return true;
02897 }
02898
02899
02900
02901
02902
02903
02904
02905 inline bool bit_is_all_zero(const bm::wordop_t* start,
02906 const bm::wordop_t* end)
02907 {
02908 do
02909 {
02910 bm::wordop_t tmp =
02911 start[0] | start[1] | start[2] | start[3];
02912 if (tmp)
02913 return false;
02914 start += 4;
02915 } while (start < end);
02916
02917 return true;
02918 }
02919
02920
02921
02922
02923
02924
02925 inline unsigned and_op(unsigned v1, unsigned v2)
02926 {
02927 return v1 & v2;
02928 }
02929
02930
02931
02932 inline unsigned xor_op(unsigned v1, unsigned v2)
02933 {
02934 return v1 ^ v2;
02935 }
02936
02937
02938
02939
02940
02941
02942
02943
02944
02945
02946
02947
02948
02949
02950
02951
02952
02953
02954 inline gap_word_t* gap_operation_and(const gap_word_t* BMRESTRICT vect1,
02955 const gap_word_t* BMRESTRICT vect2,
02956 gap_word_t* BMRESTRICT tmp_buf,
02957 unsigned& dsize)
02958 {
02959 gap_buff_op(tmp_buf, vect1, 0, vect2, 0, and_op, dsize);
02960 return tmp_buf;
02961 }
02962
02963
02964
02965
02966
02967
02968
02969
02970
02971
02972
02973
02974
02975
02976
02977 inline unsigned gap_operation_any_and(const gap_word_t* BMRESTRICT vect1,
02978 const gap_word_t* BMRESTRICT vect2)
02979 {
02980 return gap_buff_any_op(vect1, 0, vect2, 0, and_op);
02981 }
02982
02983
02984
02985
02986
02987
02988
02989
02990
02991
02992
02993
02994
02995
02996
02997
02998
02999
03000
03001 inline gap_word_t* gap_operation_xor(const gap_word_t* BMRESTRICT vect1,
03002 const gap_word_t* BMRESTRICT vect2,
03003 gap_word_t* BMRESTRICT tmp_buf,
03004 unsigned& dsize)
03005 {
03006 gap_buff_op(tmp_buf, vect1, 0, vect2, 0, xor_op, dsize);
03007 return tmp_buf;
03008 }
03009
03010
03011
03012
03013
03014
03015
03016
03017
03018
03019
03020
03021
03022
03023
03024
03025 inline unsigned gap_operation_any_xor(const gap_word_t* BMRESTRICT vect1,
03026 const gap_word_t* BMRESTRICT vect2)
03027 {
03028 return gap_buff_any_op(vect1, 0, vect2, 0, xor_op);
03029 }
03030
03031
03032
03033
03034
03035
03036
03037
03038
03039
03040
03041
03042
03043
03044
03045
03046
03047
03048
03049
03050 inline gap_word_t* gap_operation_or(const gap_word_t* BMRESTRICT vect1,
03051 const gap_word_t* BMRESTRICT vect2,
03052 gap_word_t* BMRESTRICT tmp_buf,
03053 unsigned& dsize)
03054 {
03055 gap_buff_op(tmp_buf, vect1, 1, vect2, 1, and_op, dsize);
03056 gap_invert(tmp_buf);
03057 return tmp_buf;
03058 }
03059
03060
03061
03062
03063
03064
03065
03066
03067
03068
03069
03070
03071
03072
03073
03074
03075
03076
03077
03078
03079
03080 inline gap_word_t* gap_operation_sub(const gap_word_t* BMRESTRICT vect1,
03081 const gap_word_t* BMRESTRICT vect2,
03082 gap_word_t* BMRESTRICT tmp_buf,
03083 unsigned& dsize)
03084 {
03085 gap_buff_op(tmp_buf, vect1, 0, vect2, 1, and_op, dsize);
03086 return tmp_buf;
03087 }
03088
03089
03090
03091
03092
03093
03094
03095
03096
03097
03098
03099
03100
03101
03102
03103
03104 inline unsigned gap_operation_any_sub(const gap_word_t* BMRESTRICT vect1,
03105 const gap_word_t* BMRESTRICT vect2)
03106 {
03107 return gap_buff_any_op(vect1, 0, vect2, 1, and_op);
03108 }
03109
03110
03111
03112
03113
03114
03115
03116
03117
03118
03119
03120
03121
03122
03123
03124 inline
03125 void bit_block_copy(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
03126 {
03127 #ifdef BMVECTOPT
03128 VECT_COPY_BLOCK(dst, src, src + bm::set_block_size);
03129 #else
03130 ::memcpy(dst, src, bm::set_block_size * sizeof(bm::word_t));
03131 #endif
03132 }
03133
03134
03135
03136
03137
03138
03139
03140
03141
03142
03143
03144 inline
03145 void bit_block_and(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
03146 {
03147 #ifdef BMVECTOPT
03148 VECT_AND_ARR(dst, src, src + bm::set_block_size);
03149 #else
03150 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
03151 const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + bm::set_block_size);
03152 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03153
03154 do
03155 {
03156 dst_ptr[0] &= wrd_ptr[0];
03157 dst_ptr[1] &= wrd_ptr[1];
03158 dst_ptr[2] &= wrd_ptr[2];
03159 dst_ptr[3] &= wrd_ptr[3];
03160
03161 dst_ptr+=4;
03162 wrd_ptr+=4;
03163 } while (wrd_ptr < wrd_end);
03164 #endif
03165 }
03166
03167
03168
03169
03170
03171
03172
03173
03174
03175
03176
03177
03178 inline
03179 unsigned bit_block_and_count(const bm::word_t* src1,
03180 const bm::word_t* src1_end,
03181 const bm::word_t* src2)
03182 {
03183 unsigned count;
03184 #ifdef BMVECTOPT
03185 count = VECT_BITCOUNT_AND(src1, src1_end, src2);
03186 #else
03187 count = 0;
03188 # ifdef BM64OPT
03189 const bm::id64_t* b1 = (bm::id64_t*) src1;
03190 const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
03191 const bm::id64_t* b2 = (bm::id64_t*) src2;
03192 do
03193 {
03194 count += bitcount64_4way(b1[0] & b2[0],
03195 b1[1] & b2[1],
03196 b1[2] & b2[2],
03197 b1[3] & b2[3]);
03198 b1 += 4;
03199 b2 += 4;
03200 } while (b1 < b1_end);
03201 # else
03202 do
03203 {
03204 BM_INCWORD_BITCOUNT(count, src1[0] & src2[0]);
03205 BM_INCWORD_BITCOUNT(count, src1[1] & src2[1]);
03206 BM_INCWORD_BITCOUNT(count, src1[2] & src2[2]);
03207 BM_INCWORD_BITCOUNT(count, src1[3] & src2[3]);
03208
03209 src1+=4;
03210 src2+=4;
03211 } while (src1 < src1_end);
03212 # endif
03213 #endif
03214 return count;
03215 }
03216
03217
03218
03219
03220
03221
03222
03223
03224
03225
03226
03227
03228 inline
03229 unsigned bit_block_and_any(const bm::word_t* src1,
03230 const bm::word_t* src1_end,
03231 const bm::word_t* src2)
03232 {
03233 unsigned count = 0;
03234 do
03235 {
03236 count = (src1[0] & src2[0]) |
03237 (src1[1] & src2[1]) |
03238 (src1[2] & src2[2]) |
03239 (src1[3] & src2[3]);
03240
03241 src1+=4; src2+=4;
03242 } while ((src1 < src1_end) && (count == 0));
03243 return count;
03244 }
03245
03246
03247
03248
03249
03250
03251
03252
03253
03254
03255
03256
03257
03258
03259 inline
03260 unsigned bit_block_xor_count(const bm::word_t* BMRESTRICT src1,
03261 const bm::word_t* BMRESTRICT src1_end,
03262 const bm::word_t* BMRESTRICT src2)
03263 {
03264 unsigned count;
03265 #ifdef BMVECTOPT
03266 count = VECT_BITCOUNT_XOR(src1, src1_end, src2);
03267 #else
03268 count = 0;
03269 # ifdef BM64OPT
03270 const bm::id64_t* b1 = (bm::id64_t*) src1;
03271 const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
03272 const bm::id64_t* b2 = (bm::id64_t*) src2;
03273 do
03274 {
03275 count += bitcount64_4way(b1[0] ^ b2[0],
03276 b1[1] ^ b2[1],
03277 b1[2] ^ b2[2],
03278 b1[3] ^ b2[3]);
03279 b1 += 4;
03280 b2 += 4;
03281 } while (b1 < b1_end);
03282 # else
03283 do
03284 {
03285 BM_INCWORD_BITCOUNT(count, src1[0] ^ src2[0]);
03286 BM_INCWORD_BITCOUNT(count, src1[1] ^ src2[1]);
03287 BM_INCWORD_BITCOUNT(count, src1[2] ^ src2[2]);
03288 BM_INCWORD_BITCOUNT(count, src1[3] ^ src2[3]);
03289
03290 src1+=4;
03291 src2+=4;
03292 } while (src1 < src1_end);
03293 # endif
03294 #endif
03295 return count;
03296 }
03297
03298
03299
03300
03301
03302
03303
03304
03305
03306
03307
03308
03309 inline
03310 unsigned bit_block_xor_any(const bm::word_t* BMRESTRICT src1,
03311 const bm::word_t* BMRESTRICT src1_end,
03312 const bm::word_t* BMRESTRICT src2)
03313 {
03314 unsigned count = 0;
03315 do
03316 {
03317 count = (src1[0] ^ src2[0]) |
03318 (src1[1] ^ src2[1]) |
03319 (src1[2] ^ src2[2]) |
03320 (src1[3] ^ src2[3]);
03321
03322 src1+=4; src2+=4;
03323 } while ((src1 < src1_end) && (count == 0));
03324 return count;
03325 }
03326
03327
03328
03329
03330
03331
03332
03333
03334
03335
03336
03337
03338
03339
03340 inline
03341 unsigned bit_block_sub_count(const bm::word_t* BMRESTRICT src1,
03342 const bm::word_t* BMRESTRICT src1_end,
03343 const bm::word_t* BMRESTRICT src2)
03344 {
03345 unsigned count;
03346 #ifdef BMVECTOPT
03347 count = VECT_BITCOUNT_SUB(src1, src1_end, src2);
03348 #else
03349 count = 0;
03350 # ifdef BM64OPT
03351 const bm::id64_t* b1 = (bm::id64_t*) src1;
03352 const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
03353 const bm::id64_t* b2 = (bm::id64_t*) src2;
03354 do
03355 {
03356 count += bitcount64_4way(b1[0] & ~b2[0],
03357 b1[1] & ~b2[1],
03358 b1[2] & ~b2[2],
03359 b1[3] & ~b2[3]);
03360 b1 += 4;
03361 b2 += 4;
03362 } while (b1 < b1_end);
03363 # else
03364 do
03365 {
03366 BM_INCWORD_BITCOUNT(count, src1[0] & ~src2[0]);
03367 BM_INCWORD_BITCOUNT(count, src1[1] & ~src2[1]);
03368 BM_INCWORD_BITCOUNT(count, src1[2] & ~src2[2]);
03369 BM_INCWORD_BITCOUNT(count, src1[3] & ~src2[3]);
03370
03371 src1+=4;
03372 src2+=4;
03373 } while (src1 < src1_end);
03374 # endif
03375 #endif
03376 return count;
03377 }
03378
03379
03380
03381
03382
03383
03384
03385
03386
03387
03388
03389 inline
03390 unsigned bit_block_sub_any(const bm::word_t* BMRESTRICT src1,
03391 const bm::word_t* BMRESTRICT src1_end,
03392 const bm::word_t* BMRESTRICT src2)
03393 {
03394 unsigned count = 0;
03395 do
03396 {
03397 count = (src1[0] & ~src2[0]) |
03398 (src1[1] & ~src2[1]) |
03399 (src1[2] & ~src2[2]) |
03400 (src1[3] & ~src2[3]);
03401
03402 src1+=4; src2+=4;
03403 } while ((src1 < src1_end) && (count == 0));
03404 return count;
03405 }
03406
03407
03408
03409
03410
03411
03412
03413
03414
03415
03416
03417
03418
03419 inline
03420 unsigned bit_block_or_count(const bm::word_t* src1,
03421 const bm::word_t* src1_end,
03422 const bm::word_t* src2)
03423 {
03424 unsigned count;
03425 #ifdef BMVECTOPT
03426 count = VECT_BITCOUNT_OR(src1, src1_end, src2);
03427 #else
03428 count = 0;
03429 # ifdef BM64OPT
03430 const bm::id64_t* b1 = (bm::id64_t*) src1;
03431 const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
03432 const bm::id64_t* b2 = (bm::id64_t*) src2;
03433 do
03434 {
03435 count += bitcount64_4way(b1[0] | b2[0],
03436 b1[1] | b2[1],
03437 b1[2] | b2[2],
03438 b1[3] | b2[3]);
03439 b1 += 4;
03440 b2 += 4;
03441 } while (b1 < b1_end);
03442 # else
03443 do
03444 {
03445 BM_INCWORD_BITCOUNT(count, src1[0] | src2[0]);
03446 BM_INCWORD_BITCOUNT(count, src1[1] | src2[1]);
03447 BM_INCWORD_BITCOUNT(count, src1[2] | src2[2]);
03448 BM_INCWORD_BITCOUNT(count, src1[3] | src2[3]);
03449
03450 src1+=4;
03451 src2+=4;
03452 } while (src1 < src1_end);
03453 # endif
03454 #endif
03455 return count;
03456 }
03457
03458
03459
03460
03461
03462
03463
03464
03465
03466
03467
03468 inline
03469 unsigned bit_block_or_any(const bm::word_t* BMRESTRICT src1,
03470 const bm::word_t* BMRESTRICT src1_end,
03471 const bm::word_t* BMRESTRICT src2)
03472 {
03473 unsigned count = 0;
03474 do
03475 {
03476 count = (src1[0] | src2[0]) |
03477 (src1[1] | src2[1]) |
03478 (src1[2] | src2[2]) |
03479 (src1[3] | src2[3]);
03480
03481 src1+=4; src2+=4;
03482 } while ((src1 < src1_end) && (count == 0));
03483 return count;
03484 }
03485
03486
03487
03488
03489
03490
03491
03492
03493
03494
03495
03496
03497
03498
03499
03500
03501 inline bm::word_t* bit_operation_and(bm::word_t* BMRESTRICT dst,
03502 const bm::word_t* BMRESTRICT src)
03503 {
03504 BM_ASSERT(dst || src);
03505
03506 bm::word_t* ret = dst;
03507
03508 if (IS_VALID_ADDR(dst))
03509 {
03510
03511 if (!IS_VALID_ADDR(src))
03512 {
03513 if (IS_EMPTY_BLOCK(src))
03514 {
03515
03516
03517 return 0;
03518 }
03519 }
03520 else
03521 {
03522
03523 bit_block_and(dst, src);
03524 }
03525 }
03526 else
03527 {
03528 if(!IS_VALID_ADDR(src))
03529 {
03530 if(IS_EMPTY_BLOCK(src))
03531 {
03532
03533
03534 return 0;
03535 }
03536
03537
03538 }
03539 else
03540 {
03541 if (IS_FULL_BLOCK(dst))
03542 {
03543 return const_cast<bm::word_t*>(src);
03544 }
03545
03546
03547 }
03548 }
03549
03550 return ret;
03551 }
03552
03553
03554
03555
03556
03557
03558
03559
03560
03561
03562
03563
03564
03565 inline
03566 bm::id_t bit_operation_and_count(const bm::word_t* BMRESTRICT src1,
03567 const bm::word_t* BMRESTRICT src1_end,
03568 const bm::word_t* BMRESTRICT src2)
03569 {
03570 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03571 {
03572 return 0;
03573 }
03574 return bit_block_and_count(src1, src1_end, src2);
03575 }
03576
03577
03578
03579
03580
03581
03582
03583
03584
03585
03586
03587
03588 inline
03589 bm::id_t bit_operation_and_any(const bm::word_t* BMRESTRICT src1,
03590 const bm::word_t* BMRESTRICT src1_end,
03591 const bm::word_t* BMRESTRICT src2)
03592 {
03593 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
03594 {
03595 return 0;
03596 }
03597 return bit_block_and_any(src1, src1_end, src2);
03598 }
03599
03600
03601
03602
03603
03604
03605
03606
03607
03608
03609
03610
03611
03612
03613 inline
03614 bm::id_t bit_operation_sub_count(const bm::word_t* BMRESTRICT src1,
03615 const bm::word_t* BMRESTRICT src1_end,
03616 const bm::word_t* BMRESTRICT src2)
03617 {
03618 if (IS_EMPTY_BLOCK(src1))
03619 {
03620 return 0;
03621 }
03622
03623 if (IS_EMPTY_BLOCK(src2))
03624 {
03625 return bit_block_calc_count(src1, src1_end);
03626 }
03627 return bit_block_sub_count(src1, src1_end, src2);
03628 }
03629
03630
03631
03632
03633
03634
03635
03636
03637
03638
03639
03640
03641
03642
03643 inline
03644 bm::id_t bit_operation_sub_count_inv(const bm::word_t* BMRESTRICT src1,
03645 const bm::word_t* BMRESTRICT src1_end,
03646 const bm::word_t* BMRESTRICT src2)
03647 {
03648 unsigned arr_size = unsigned(src1_end - src1);
03649 return bit_operation_sub_count(src2, src2+arr_size, src1);
03650 }
03651
03652
03653
03654
03655
03656
03657
03658
03659
03660
03661
03662
03663
03664 inline
03665 bm::id_t bit_operation_sub_any(const bm::word_t* BMRESTRICT src1,
03666 const bm::word_t* BMRESTRICT src1_end,
03667 const bm::word_t* BMRESTRICT src2)
03668 {
03669 if (IS_EMPTY_BLOCK(src1))
03670 {
03671 return 0;
03672 }
03673
03674 if (IS_EMPTY_BLOCK(src2))
03675 {
03676 return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
03677 }
03678 return bit_block_sub_any(src1, src1_end, src2);
03679 }
03680
03681
03682
03683
03684
03685
03686
03687
03688
03689
03690
03691
03692
03693
03694 inline
03695 bm::id_t bit_operation_or_count(const bm::word_t* BMRESTRICT src1,
03696 const bm::word_t* BMRESTRICT src1_end,
03697 const bm::word_t* BMRESTRICT src2)
03698 {
03699 if (IS_EMPTY_BLOCK(src1))
03700 {
03701 if (!IS_EMPTY_BLOCK(src2))
03702 return bit_block_calc_count(src2, src2 + (src1_end - src1));
03703 else
03704 return 0;
03705 }
03706 else
03707 {
03708 if (IS_EMPTY_BLOCK(src2))
03709 return bit_block_calc_count(src1, src1_end);
03710 }
03711
03712 return bit_block_or_count(src1, src1_end, src2);
03713 }
03714
03715
03716
03717
03718
03719
03720
03721
03722
03723
03724
03725
03726 inline
03727 bm::id_t bit_operation_or_any(const bm::word_t* BMRESTRICT src1,
03728 const bm::word_t* BMRESTRICT src1_end,
03729 const bm::word_t* BMRESTRICT src2)
03730 {
03731 if (IS_EMPTY_BLOCK(src1))
03732 {
03733 if (!IS_EMPTY_BLOCK(src2))
03734 return !bit_is_all_zero((bm::wordop_t*)src2,
03735 (bm::wordop_t*)(src2 + (src1_end - src1)));
03736 else
03737 return 0;
03738 }
03739 else
03740 {
03741 if (IS_EMPTY_BLOCK(src2))
03742 return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
03743 }
03744
03745 return bit_block_or_any(src1, src1_end, src2);
03746 }
03747
03748
03749
03750
03751
03752
03753
03754
03755
03756
03757
03758
03759 inline void bit_block_or(bm::word_t* BMRESTRICT dst,
03760 const bm::word_t* BMRESTRICT src)
03761 {
03762 #ifdef BMVECTOPT
03763 VECT_OR_ARR(dst, src, src + bm::set_block_size);
03764 #else
03765 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
03766 const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + set_block_size);
03767 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03768
03769 do
03770 {
03771 dst_ptr[0] |= wrd_ptr[0];
03772 dst_ptr[1] |= wrd_ptr[1];
03773 dst_ptr[2] |= wrd_ptr[2];
03774 dst_ptr[3] |= wrd_ptr[3];
03775
03776 dst_ptr+=4;
03777 wrd_ptr+=4;
03778
03779 } while (wrd_ptr < wrd_end);
03780 #endif
03781 }
03782
03783
03784
03785
03786
03787
03788
03789
03790
03791
03792
03793
03794
03795
03796 inline
03797 bm::word_t* bit_operation_or(bm::word_t* BMRESTRICT dst,
03798 const bm::word_t* BMRESTRICT src)
03799 {
03800 BM_ASSERT(dst || src);
03801
03802 bm::word_t* ret = dst;
03803
03804 if (IS_VALID_ADDR(dst))
03805 {
03806 if (!IS_VALID_ADDR(src))
03807 {
03808 if (IS_FULL_BLOCK(src))
03809 {
03810
03811
03812 ::memset(dst, 0xFF, bm::set_block_size * sizeof(bm::word_t));
03813 }
03814 }
03815 else
03816 {
03817
03818 bit_block_or(dst, src);
03819 }
03820 }
03821 else
03822 {
03823 if (!IS_VALID_ADDR(src))
03824 {
03825 if (IS_FULL_BLOCK(src))
03826 {
03827
03828
03829 return const_cast<bm::word_t*>(FULL_BLOCK_ADDR);
03830 }
03831 }
03832 else
03833 {
03834 if (dst == 0)
03835 {
03836
03837
03838 return const_cast<bm::word_t*>(src);
03839 }
03840 }
03841 }
03842 return ret;
03843 }
03844
03845
03846
03847
03848
03849
03850
03851
03852
03853
03854 inline
03855 void bit_block_sub(bm::word_t* BMRESTRICT dst,
03856 const bm::word_t* BMRESTRICT src)
03857 {
03858 #ifdef BMVECTOPT
03859 VECT_SUB_ARR(dst, src, src + bm::set_block_size);
03860 #else
03861 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
03862 const bm::wordop_t* BMRESTRICT wrd_end =
03863 (wordop_t*) (src + bm::set_block_size);
03864 bm::wordop_t* dst_ptr = (wordop_t*)dst;
03865
03866
03867 do
03868 {
03869 dst_ptr[0] &= ~wrd_ptr[0];
03870 dst_ptr[1] &= ~wrd_ptr[1];
03871 dst_ptr[2] &= ~wrd_ptr[2];
03872 dst_ptr[3] &= ~wrd_ptr[3];
03873
03874 dst_ptr+=4;
03875 wrd_ptr+=4;
03876 } while (wrd_ptr < wrd_end);
03877 #endif
03878
03879 }
03880
03881
03882
03883
03884
03885
03886
03887
03888
03889
03890
03891
03892
03893
03894 inline
03895 bm::word_t* bit_operation_sub(bm::word_t* BMRESTRICT dst,
03896 const bm::word_t* BMRESTRICT src)
03897 {
03898 BM_ASSERT(dst || src);
03899
03900 bm::word_t* ret = dst;
03901 if (IS_VALID_ADDR(dst))
03902 {
03903 if (!IS_VALID_ADDR(src))
03904 {
03905 if (IS_FULL_BLOCK(src))
03906 {
03907
03908
03909 return 0;
03910 }
03911 }
03912 else
03913 {
03914 bit_block_sub(dst, src);
03915 }
03916 }
03917 else
03918 {
03919 if (!IS_VALID_ADDR(src))
03920 {
03921 if (IS_FULL_BLOCK(src))
03922 {
03923
03924 return 0;
03925 }
03926 }
03927 else
03928 {
03929 if (IS_FULL_BLOCK(dst))
03930 {
03931
03932
03933 return const_cast<bm::word_t*>(src);
03934 }
03935 }
03936 }
03937 return ret;
03938 }
03939
03940
03941
03942
03943
03944
03945
03946
03947
03948
03949
03950 inline
03951 void bit_block_xor(bm::word_t* BMRESTRICT dst,
03952 const bm::word_t* BMRESTRICT src)
03953 {
03954 #ifdef BMVECTOPT
03955 VECT_XOR_ARR(dst, src, src + bm::set_block_size);
03956 #else
03957 const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
03958 const bm::wordop_t* BMRESTRICT wrd_end =
03959 (wordop_t*) (src + bm::set_block_size);
03960 bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
03961
03962
03963 do
03964 {
03965 dst_ptr[0] ^= wrd_ptr[0];
03966 dst_ptr[1] ^= wrd_ptr[1];
03967 dst_ptr[2] ^= wrd_ptr[2];
03968 dst_ptr[3] ^= wrd_ptr[3];
03969
03970 dst_ptr+=4;
03971 wrd_ptr+=4;
03972 } while (wrd_ptr < wrd_end);
03973 #endif
03974
03975 }
03976
03977
03978
03979
03980
03981
03982
03983
03984
03985
03986
03987
03988
03989
03990 inline
03991 bm::word_t* bit_operation_xor(bm::word_t* BMRESTRICT dst,
03992 const bm::word_t* BMRESTRICT src)
03993 {
03994 BM_ASSERT(dst || src);
03995 if (src == dst) return 0;
03996
03997 bm::word_t* ret = dst;
03998
03999 if (IS_VALID_ADDR(dst))
04000 {
04001 if (!src) return dst;
04002
04003 bit_block_xor(dst, src);
04004 }
04005 else
04006 {
04007 if (!src) return dst;
04008
04009
04010
04011
04012
04013 return const_cast<bm::word_t*>(src);
04014 }
04015 return ret;
04016 }
04017
04018
04019
04020
04021
04022
04023
04024
04025
04026
04027
04028 inline
04029 bm::id_t bit_operation_xor_count(const bm::word_t* BMRESTRICT src1,
04030 const bm::word_t* BMRESTRICT src1_end,
04031 const bm::word_t* BMRESTRICT src2)
04032 {
04033 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
04034 {
04035 if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
04036 return 0;
04037 const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
04038 return bit_block_calc_count(block, block + (src1_end - src1));
04039 }
04040 return bit_block_xor_count(src1, src1_end, src2);
04041 }
04042
04043
04044
04045
04046
04047
04048
04049
04050
04051
04052
04053 inline
04054 bm::id_t bit_operation_xor_any(const bm::word_t* BMRESTRICT src1,
04055 const bm::word_t* BMRESTRICT src1_end,
04056 const bm::word_t* BMRESTRICT src2)
04057 {
04058 if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
04059 {
04060 if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
04061 return 0;
04062 const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
04063 return !bit_is_all_zero((bm::wordop_t*)block,
04064 (bm::wordop_t*)(block + (src1_end - src1)));
04065 }
04066 return bit_block_xor_any(src1, src1_end, src2);
04067 }
04068
04069
04070
04071
04072
04073
04074
04075
04076
04077
04078
04079
04080
04081
04082 template<class T>
04083 unsigned bit_count_nonzero_size(const T* blk,
04084 unsigned data_size)
04085 {
04086 BM_ASSERT(blk && data_size);
04087 unsigned count = 0;
04088
04089 const T* blk_end = blk + data_size - 2;
04090
04091
04092
04093 do
04094 {
04095 if (*blk == 0)
04096 {
04097
04098
04099 const T* blk_j = blk + 1;
04100 for (; blk_j < blk_end; ++blk_j)
04101 {
04102 if (*blk_j != 0)
04103 break;
04104 }
04105
04106 blk = blk_j-1;
04107 count += sizeof(gap_word_t);
04108 }
04109 else
04110 {
04111
04112
04113 const T* blk_j = blk + 1;
04114 for ( ; blk_j < blk_end; ++blk_j)
04115 {
04116
04117 if (*blk_j == 0)
04118 {
04119
04120
04121
04122
04123 if (blk_j[1] | blk_j[2])
04124 {
04125
04126
04127 ++blk_j;
04128 continue;
04129 }
04130 break;
04131 }
04132 }
04133 count += sizeof(gap_word_t);
04134
04135 count += (blk_j - blk) * sizeof(T);
04136 blk = blk_j;
04137
04138
04139
04140
04141
04142
04143 }
04144 ++blk;
04145 }
04146 while(blk < blk_end);
04147
04148 return count + (2 * sizeof(T));
04149 }
04150
04151
04152
04153
04154
04155
04156
04157
04158
04159
04160 inline
04161 int bit_find_in_block(const bm::word_t* data,
04162 unsigned nbit,
04163 bm::id_t* prev)
04164 {
04165 register bm::id_t p = *prev;
04166 int found = 0;
04167
04168 for(;;)
04169 {
04170 unsigned nword = nbit >> bm::set_word_shift;
04171 if (nword >= bm::set_block_size) break;
04172
04173 register bm::word_t val = data[nword] >> (p & bm::set_word_mask);
04174
04175
04176
04177
04178 if (val)
04179 {
04180 while((val & 1) == 0)
04181 {
04182 val >>= 1;
04183 ++nbit;
04184 ++p;
04185 }
04186 ++found;
04187
04188 break;
04189 }
04190 else
04191 {
04192 p += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
04193 nbit += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
04194 }
04195 }
04196 *prev = p;
04197 return found;
04198 }
04199
04200
04201
04202
04203
04204
04205
04206
04207 template<typename T, typename F>
04208 void bit_for_each_4(T w, F& func)
04209 {
04210 for (unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
04211 {
04212 switch (w & 15)
04213 {
04214 case 0:
04215 break;
04216 case 1:
04217 func(sub_octet);
04218 break;
04219 case 2:
04220 func(sub_octet + 1);
04221 break;
04222 case 3:
04223 func(sub_octet, sub_octet + 1);
04224 break;
04225 case 4:
04226 func(sub_octet + 2);
04227 break;
04228 case 5:
04229 func(sub_octet, sub_octet + 2);
04230 break;
04231 case 6:
04232 func(sub_octet + 1, sub_octet + 2);
04233 break;
04234 case 7:
04235 func(sub_octet, sub_octet + 1, sub_octet + 2);
04236 break;
04237 case 8:
04238 func(sub_octet + 3);
04239 break;
04240 case 9:
04241 func(sub_octet, sub_octet + 3);
04242 break;
04243 case 10:
04244 func(sub_octet + 1, sub_octet + 3);
04245 break;
04246 case 11:
04247 func(sub_octet, sub_octet + 1, sub_octet + 3);
04248 break;
04249 case 12:
04250 func(sub_octet + 2, sub_octet + 3);
04251 break;
04252 case 13:
04253 func(sub_octet, sub_octet + 2, sub_octet + 3);
04254 break;
04255 case 14:
04256 func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
04257 break;
04258 case 15:
04259 func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
04260 break;
04261 default:
04262 BM_ASSERT(0);
04263 break;
04264 }
04265
04266 }
04267 }
04268
04269
04270
04271
04272
04273
04274
04275
04276
04277 template<typename T, typename F>
04278 void bit_for_each(T w, F& func)
04279 {
04280
04281 for (unsigned octet = 0; w != 0; w >>= 8, octet += 8)
04282 {
04283 if (w & 1) func(octet + 0);
04284 if (w & 2) func(octet + 1);
04285 if (w & 4) func(octet + 2);
04286 if (w & 8) func(octet + 3);
04287 if (w & 16) func(octet + 4);
04288 if (w & 32) func(octet + 5);
04289 if (w & 64) func(octet + 6);
04290 if (w & 128) func(octet + 7);
04291
04292 }
04293 }
04294
04295
04296
04297
04298 template<typename B> class copy_to_array_functor
04299 {
04300 public:
04301 copy_to_array_functor(B* bits): bp_(bits)
04302 {}
04303
04304 B* ptr() { return bp_; }
04305
04306 void operator()(unsigned bit_idx) { *bp_++ = (B)bit_idx; }
04307
04308 void operator()(unsigned bit_idx0,
04309 unsigned bit_idx1)
04310 {
04311 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
04312 bp_+=2;
04313 }
04314
04315 void operator()(unsigned bit_idx0,
04316 unsigned bit_idx1,
04317 unsigned bit_idx2)
04318 {
04319 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
04320 bp_+=3;
04321 }
04322
04323 void operator()(unsigned bit_idx0,
04324 unsigned bit_idx1,
04325 unsigned bit_idx2,
04326 unsigned bit_idx3)
04327 {
04328 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
04329 bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
04330 bp_+=4;
04331 }
04332
04333 private:
04334 copy_to_array_functor(const copy_to_array_functor&);
04335 copy_to_array_functor& operator=(const copy_to_array_functor&);
04336 private:
04337 B* bp_;
04338 };
04339
04340
04341
04342
04343 template<typename B> class copy_to_array_functor_inc
04344 {
04345 public:
04346 copy_to_array_functor_inc(B* bits, unsigned base_idx)
04347 : bp_(bits), base_idx_(base_idx)
04348 {}
04349
04350 B* ptr() { return bp_; }
04351
04352 void operator()(unsigned bit_idx)
04353 {
04354 *bp_++ = (B)(bit_idx + base_idx_);
04355 }
04356
04357
04358 void operator()(unsigned bit_idx0,
04359 unsigned bit_idx1)
04360 {
04361 bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
04362 bp_+=2;
04363 }
04364
04365 void operator()(unsigned bit_idx0,
04366 unsigned bit_idx1,
04367 unsigned bit_idx2)
04368 {
04369 bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
04370 bp_[2]=(B)(bit_idx2+base_idx_);
04371 bp_+=3;
04372 }
04373
04374 void operator()(unsigned bit_idx0,
04375 unsigned bit_idx1,
04376 unsigned bit_idx2,
04377 unsigned bit_idx3)
04378 {
04379 bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
04380 bp_[2]=(B)(bit_idx2+base_idx_);bp_[3]=(B)(bit_idx3+base_idx_);
04381 bp_+=4;
04382 }
04383
04384 private:
04385 copy_to_array_functor_inc(const copy_to_array_functor_inc&);
04386 copy_to_array_functor_inc& operator=(const copy_to_array_functor_inc&);
04387 private:
04388 B* bp_;
04389 unsigned base_idx_;
04390 };
04391
04392
04393
04394
04395
04396
04397
04398
04399
04400
04401 template<typename T,typename B> unsigned bit_list_4(T w, B* bits)
04402 {
04403 copy_to_array_functor<B> func(bits);
04404 bit_for_each_4(w, func);
04405 return (unsigned)(func.ptr() - bits);
04406 }
04407
04408
04409
04410
04411
04412
04413
04414
04415
04416 template<typename T,typename B> unsigned bit_list(T w, B* bits)
04417 {
04418 copy_to_array_functor<B> func(bits);
04419 bit_for_each(w, func);
04420 return (unsigned)(func.ptr() - bits);
04421 }
04422
04423
04424
04425
04426
04427
04428 inline
04429 bm::set_representation best_representation(unsigned bit_count,
04430 unsigned total_possible_bitcount,
04431 unsigned gap_count,
04432 unsigned block_size)
04433 {
04434 unsigned arr_size = sizeof(bm::gap_word_t) * bit_count + sizeof(bm::gap_word_t);
04435 unsigned gap_size = sizeof(bm::gap_word_t) * gap_count + sizeof(bm::gap_word_t);
04436 unsigned inv_arr_size = sizeof(bm::gap_word_t) * (total_possible_bitcount - bit_count) + sizeof(bm::gap_word_t);
04437
04438 if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
04439 {
04440 return bm::set_gap;
04441 }
04442
04443 if (arr_size < inv_arr_size)
04444 {
04445 if ((arr_size < block_size) && (arr_size < gap_size))
04446 {
04447 return bm::set_array1;
04448 }
04449 }
04450 else
04451 {
04452 if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
04453 {
04454 return bm::set_array0;
04455 }
04456 }
04457 return bm::set_bitset;
04458 }
04459
04460
04461
04462
04463
04464 template<typename T> T bit_convert_to_arr(T* BMRESTRICT dest,
04465 const unsigned* BMRESTRICT src,
04466 bm::id_t bits,
04467 unsigned dest_len,
04468 unsigned mask = 0)
04469 {
04470 T* BMRESTRICT pcurr = dest;
04471 for(unsigned bit_idx=0; bit_idx < bits; ++src,bit_idx += sizeof(*src) * 8)
04472 {
04473 unsigned val = *src ^ mask;
04474 if (val == 0)
04475 {
04476 continue;
04477 }
04478 if (pcurr + sizeof(val)*8 >= dest + dest_len)
04479 {
04480 return 0;
04481 }
04482
04483 copy_to_array_functor_inc<T> func(pcurr, bit_idx);
04484 bit_for_each_4(val, func);
04485 unsigned word_bit_cnt = func.ptr() - pcurr;
04486 pcurr += word_bit_cnt;
04487
04488 }
04489 return (T)(pcurr - dest);
04490 }
04491
04492
04493
04494
04495
04496
04497
04498
04499
04500
04501
04502
04503
04504
04505
04506
04507
04508
04509
04510
04511
04512
04513
04514
04515
04516
04517
04518
04519
04520
04521
04522
04523
04524
04525
04526
04527
04528
04529
04530
04531
04532
04533
04534
04535
04536
04537
04538
04539
04540
04541
04542
04543
04544
04545
04546
04547
04548
04549
04550
04551
04552
04553
04554
04555
04556
04557
04558
04559
04560
04561
04562 template<typename T>
04563 unsigned gap_overhead(const T* length,
04564 const T* length_end,
04565 const T* glevel_len)
04566 {
04567 BM_ASSERT(length && length_end && glevel_len);
04568
04569 unsigned overhead = 0;
04570 for (;length < length_end; ++length)
04571 {
04572 unsigned len = *length;
04573 int level = gap_calc_level(len, glevel_len);
04574 BM_ASSERT(level >= 0 && level < (int)bm::gap_levels);
04575 unsigned capacity = glevel_len[level];
04576 BM_ASSERT(capacity >= len);
04577 overhead += capacity - len;
04578 }
04579 return overhead;
04580 }
04581
04582
04583
04584
04585
04586
04587
04588
04589
04590 template<typename T>
04591 bool improve_gap_levels(const T* length,
04592 const T* length_end,
04593 T* glevel_len)
04594 {
04595 BM_ASSERT(length && length_end && glevel_len);
04596
04597 size_t lsize = length_end - length;
04598
04599 BM_ASSERT(lsize);
04600
04601 gap_word_t max_len = 0;
04602 unsigned i;
04603 for (i = 0; i < lsize; ++i)
04604 {
04605 if (length[i] > max_len)
04606 max_len = length[i];
04607 }
04608 if (max_len < 5 || lsize <= bm::gap_levels)
04609 {
04610 glevel_len[0] = max_len + 4;
04611 for (i = 1; i < bm::gap_levels; ++i)
04612 {
04613 glevel_len[i] = bm::gap_max_buff_len;
04614 }
04615 return true;
04616 }
04617
04618 glevel_len[bm::gap_levels-1] = max_len + 5;
04619
04620 unsigned min_overhead = gap_overhead(length, length_end, glevel_len);
04621 bool is_improved = false;
04622 gap_word_t prev_value = glevel_len[bm::gap_levels-1];
04623
04624
04625
04626 for (i = bm::gap_levels-2; ; --i)
04627 {
04628 unsigned opt_len = 0;
04629 unsigned j;
04630 bool imp_flag = false;
04631 gap_word_t gap_saved_value = glevel_len[i];
04632 for (j = 0; j < lsize; ++j)
04633 {
04634
04635
04636
04637 glevel_len[i] = length[j]+4;
04638 unsigned ov = gap_overhead(length, length_end, glevel_len);
04639 if (ov <= min_overhead)
04640 {
04641 min_overhead = ov;
04642 opt_len = length[j]+4;
04643 imp_flag = true;
04644 }
04645 }
04646 if (imp_flag) {
04647 glevel_len[i] = opt_len;
04648 is_improved = true;
04649 }
04650 else
04651 {
04652 glevel_len[i] = gap_saved_value;
04653 }
04654 if (i == 0)
04655 break;
04656 prev_value = glevel_len[i];
04657 }
04658
04659
04660
04661
04662 T val = *glevel_len;
04663 T* gp = glevel_len;
04664 T* res = glevel_len;
04665 for (i = 0; i < bm::gap_levels; ++i)
04666 {
04667 if (val != *gp)
04668 {
04669 val = *gp;
04670 *++res = val;
04671 }
04672 ++gp;
04673 }
04674
04675
04676 while (++res < (glevel_len + bm::gap_levels))
04677 {
04678 *res = bm::gap_max_buff_len;
04679 }
04680
04681 return is_improved;
04682
04683 }
04684
04685
04686
04687
04688
04689
04690
04691
04692 class bitblock_get_adapter
04693 {
04694 public:
04695 bitblock_get_adapter(const bm::word_t* bit_block) : b_(bit_block) {}
04696
04697 BMFORCEINLINE
04698 bm::word_t get_32() { return *b_++; }
04699 private:
04700 const bm::word_t* b_;
04701 };
04702
04703
04704
04705
04706
04707
04708 class bitblock_store_adapter
04709 {
04710 public:
04711 bitblock_store_adapter(bm::word_t* bit_block) : b_(bit_block) {}
04712 BMFORCEINLINE
04713 void push_back(bm::word_t w) { *b_++ = w; }
04714 private:
04715 bm::word_t* b_;
04716 };
04717
04718
04719
04720
04721
04722 class bitblock_sum_adapter
04723 {
04724 public:
04725 bitblock_sum_adapter() : sum_(0) {}
04726 BMFORCEINLINE
04727 void push_back(bm::word_t w) { this->sum_+= w; }
04728
04729 bm::word_t sum() const { return this->sum_; }
04730 private:
04731 bm::word_t sum_;
04732 };
04733
04734
04735
04736
04737
04738
04739 template<class DEC> class decoder_range_adapter
04740 {
04741 public:
04742 decoder_range_adapter(DEC& dec, unsigned from_idx, unsigned to_idx)
04743 : decoder_(dec),
04744 from_(from_idx),
04745 to_(to_idx),
04746 cnt_(0)
04747 {}
04748
04749 bm::word_t get_32()
04750 {
04751 if (cnt_ < from_ || cnt_ > to_)
04752 {
04753 ++cnt_; return 0;
04754 }
04755 ++cnt_;
04756 return decoder_.get_32();
04757 }
04758
04759 private:
04760 DEC& decoder_;
04761 unsigned from_;
04762 unsigned to_;
04763 unsigned cnt_;
04764 };
04765
04766
04767
04768
04769
04770
04771 template<class It1, class It2, class BinaryOp, class Encoder>
04772 void bit_recomb(It1& it1, It2& it2,
04773 BinaryOp& op,
04774 Encoder& enc,
04775 unsigned block_size = bm::set_block_size)
04776 {
04777 for (unsigned i = 0; i < block_size; ++i)
04778 {
04779 bm::word_t w1 = it1.get_32();
04780 bm::word_t w2 = it2.get_32();
04781 bm::word_t w = op(w1, w2);
04782 enc.push_back( w );
04783 }
04784 }
04785
04786
04787 template<typename W> struct bit_AND
04788 {
04789 W operator()(W w1, W w2) { return w1 & w2; }
04790 };
04791
04792
04793 template<typename W> struct bit_OR
04794 {
04795 W operator()(W w1, W w2) { return w1 | w2; }
04796 };
04797
04798
04799 template<typename W> struct bit_SUB
04800 {
04801 W operator()(W w1, W w2) { return w1 & ~w2; }
04802 };
04803
04804
04805 template<typename W> struct bit_XOR
04806 {
04807 W operator()(W w1, W w2) { return w1 ^ w2; }
04808 };
04809
04810
04811 template<typename W> struct bit_ASSIGN
04812 {
04813 W operator()(W w1, W w2) { return w2; }
04814 };
04815
04816
04817 template<typename W> struct bit_COUNT
04818 {
04819 W operator()(W w1, W w2)
04820 {
04821 w1 = 0;
04822 BM_INCWORD_BITCOUNT(w1, w2);
04823 return w1;
04824 }
04825 };
04826
04827
04828 template<typename W> struct bit_COUNT_AND
04829 {
04830 W operator()(W w1, W w2)
04831 {
04832 W r = 0;
04833 BM_INCWORD_BITCOUNT(r, w1 & w2);
04834 return r;
04835 }
04836 };
04837
04838
04839 template<typename W> struct bit_COUNT_XOR
04840 {
04841 W operator()(W w1, W w2)
04842 {
04843 W r = 0;
04844 BM_INCWORD_BITCOUNT(r, w1 ^ w2);
04845 return r;
04846 }
04847 };
04848
04849
04850 template<typename W> struct bit_COUNT_OR
04851 {
04852 W operator()(W w1, W w2)
04853 {
04854 W r = 0;
04855 BM_INCWORD_BITCOUNT(r, w1 | w2);
04856 return r;
04857 }
04858 };
04859
04860
04861
04862 template<typename W> struct bit_COUNT_SUB_AB
04863 {
04864 W operator()(W w1, W w2)
04865 {
04866 W r = 0;
04867 BM_INCWORD_BITCOUNT(r, w1 & (~w2));
04868 return r;
04869 }
04870 };
04871
04872
04873 template<typename W> struct bit_COUNT_SUB_BA
04874 {
04875 W operator()(W w1, W w2)
04876 {
04877 W r = 0;
04878 BM_INCWORD_BITCOUNT(r, w2 & (~w1));
04879 return r;
04880 }
04881 };
04882
04883
04884 template<typename W> struct bit_COUNT_A
04885 {
04886 W operator()(W w1, W w2)
04887 {
04888 W r = 0;
04889 BM_INCWORD_BITCOUNT(r, w1);
04890 return r;
04891 }
04892 };
04893
04894
04895 template<typename W> struct bit_COUNT_B
04896 {
04897 W operator()(W w1, W w2)
04898 {
04899 W r = 0;
04900 BM_INCWORD_BITCOUNT(r, w2);
04901 return r;
04902 }
04903 };
04904
04905 typedef
04906 void (*gap_operation_to_bitset_func_type)(unsigned*,
04907 const gap_word_t*);
04908
04909 typedef
04910 gap_word_t* (*gap_operation_func_type)(const gap_word_t* BMRESTRICT,
04911 const gap_word_t* BMRESTRICT,
04912 gap_word_t* BMRESTRICT,
04913 unsigned& );
04914
04915 typedef
04916 bm::id_t (*bit_operation_count_func_type)(const bm::word_t* BMRESTRICT,
04917 const bm::word_t* BMRESTRICT,
04918 const bm::word_t* BMRESTRICT);
04919
04920
04921 template<bool T>
04922 struct operation_functions
04923 {
04924 static
04925 gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END];
04926 static
04927 gap_operation_func_type gapop_table_[bm::set_END];
04928 static
04929 bit_operation_count_func_type bit_op_count_table_[bm::set_END];
04930
04931 static
04932 gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
04933 {
04934 return gap2bit_table_[i];
04935 }
04936
04937 static
04938 gap_operation_func_type gap_operation(unsigned i)
04939 {
04940 return gapop_table_[i];
04941 }
04942
04943 static
04944 bit_operation_count_func_type bit_operation_count(unsigned i)
04945 {
04946 return bit_op_count_table_[i];
04947 }
04948 };
04949
04950 template<bool T>
04951 gap_operation_to_bitset_func_type
04952 operation_functions<T>::gap2bit_table_[bm::set_END] = {
04953 &gap_and_to_bitset<bm::gap_word_t>,
04954 &gap_add_to_bitset<bm::gap_word_t>,
04955 &gap_sub_to_bitset<bm::gap_word_t>,
04956 &gap_xor_to_bitset<bm::gap_word_t>,
04957 0
04958 };
04959
04960 template<bool T>
04961 gap_operation_func_type
04962 operation_functions<T>::gapop_table_[bm::set_END] = {
04963 &gap_operation_and,
04964 &gap_operation_or,
04965 &gap_operation_sub,
04966 &gap_operation_xor,
04967 0
04968 };
04969
04970
04971 template<bool T>
04972 bit_operation_count_func_type
04973 operation_functions<T>::bit_op_count_table_[bm::set_END] = {
04974 0,
04975 0,
04976 0,
04977 0,
04978 0,
04979 0,
04980 &bit_operation_and_count,
04981 &bit_operation_xor_count,
04982 &bit_operation_or_count,
04983 &bit_operation_sub_count,
04984 &bit_operation_sub_count_inv,
04985 0,
04986 0,
04987 };
04988
04989 }
04990
04991 #endif