- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# bmfunc.h

Go to the documentation of this file.

    00001 #ifndef BMFUNC__H__INCLUDED__
    00002 #define BMFUNC__H__INCLUDED__
    00003 /*
    00004 Copyright(c) 2002-2010 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
    00005
    00006 Permission is hereby granted, free of charge, to any person
    00007 obtaining a copy of this software and associated documentation
    00008 files (the "Software"), to deal in the Software without restriction,
    00009 including without limitation the rights to use, copy, modify, merge,
    00010 publish, distribute, sublicense, and/or sell copies of the Software,
    00011 and to permit persons to whom the Software is furnished to do so,
    00012 subject to the following conditions:
    00013
    00014 The above copyright notice and this permission notice shall be included
    00015 in all copies or substantial portions of the Software.
    00016
    00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    00018 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    00019 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    00020 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
    00021 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    00022 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    00023 OTHER DEALINGS IN THE SOFTWARE.
    00024
    00025 For more information please visit:  http://bmagic.sourceforge.net
    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     @brief Structure with statistical information about bitset's memory
    00045             allocation details.
    00046     @ingroup bvector
    00047 */
    00048 struct bv_statistics
    00049 {
    00050     /// Number of bit blocks.
    00051     unsigned bit_blocks;
    00052     /// Number of GAP blocks.
    00053     unsigned gap_blocks;
    00054     /// Estimated maximum of memory required for serialization.
    00055     unsigned max_serialize_mem;
    00056     /// Memory used by bitvector including temp and service blocks
    00057     unsigned  memory_used;
    00058     /// Array of all GAP block lengths in the bvector.
    00059     gap_word_t   gap_length[bm::set_total_blocks];
    00060     /// GAP lengths used by bvector
    00061     gap_word_t  gap_levels[bm::gap_levels];
    00062
    00063
    00064
    00065     /// cound bit block
    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     /// count gap block
    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 /*! @defgroup gapfunc GAP functions
    00086  *  GAP functions implement different opereations on GAP compressed blocks
    00087  *  and serve as a minimal building blocks.
    00088  *  @ingroup bmagic
    00089  *
    00090  */
    00091
    00092 /*! @defgroup bitfunc BIT functions
    00093  *  Bit functions implement different opereations on bit blocks
    00094  *  and serve as a minimal building blocks.
    00095  *  @ingroup bmagic
    00096  */
    00097
    00098
    00099 /*! @brief Default GAP lengths table.
    00100     @ingroup gapfunc
    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 /*! @brief Alternative GAP lengths table.
    00113     Good for for memory saver mode and very sparse bitsets.
    00114
    00115     @ingroup gapfunc
    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 /** Structure keeps all-left/right ON bits masks.
    00131     @ingroup bitfunc
    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     Returns bit count
    00162     @ingroup bitfunc
    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     Function calculates number of 1 bits in 64-bit word.
    00191     @ingroup bitfunc
    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     Nomenclature of set operations
    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 /// Returns true if set operation is constant (bitcount)
    00265 inline
    00266 bool is_const_set_operation(set_operation op)
    00267 {
    00268     return (int(op) >= int(set_COUNT));
    00269 }
    00270
    00271 /**
    00272     Bit operations enumeration.
    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     Convert set operation to operation
    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     Structure carries pointer on bit block with all bits 1
    00299     @ingroup bitfunc
    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 /// XOR swap two scalar variables
    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    \brief Lexicographical comparison of two words as bit strings.
    00334    Auxiliary implementation for testing and reference purposes.
    00335    \param buf1 - First word.
    00336    \param buf2 - Second word.
    00337    \return  <0 - less, =0 - equal,  >0 - greater.
    00338
    00339    @ingroup bitfunc
    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    \brief Lexicographical comparison of two words as bit strings.
    00356    Auxiliary implementation for testing and reference purposes.
    00357    \param buf1 - First word.
    00358    \param buf2 - Second word.
    00359    \return  <0 - less, =0 - equal,  >0 - greater.
    00360
    00361    @ingroup bitfunc
    00362 */
    00363 /*
    00364 template<typename T> int wordcmp(T w1, T w2)
    00365 {
    00366     T diff = w1 ^ w2;
    00367     return diff ? ((w1 & diff & (diff ^ (diff - 1)))? 1 : -1) : 0;
    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 // Low bit extraction
    00379 // x & (x ^ (x-1))
    00380
    00381
    00382 /**
    00383     Internal structure. Copyright information.
    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.7.0 (c) 2002-2010 Anatoliy Kuznetsov.";
    00392
    00393
    00394 /*!
    00395    \brief Byte orders recognized by the library.
    00396 */
    00397 enum ByteOrder
    00398 {
    00399     BigEndian    = 0,
    00400     LittleEndian = 1
    00401 };
    00402
    00403
    00404 /**
    00405     Internal structure. Different global settings.
    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); // "Invalid Byte Order\n"
    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    \brief Binary search for the block where bit = pos located.
    00454    \param buf - GAP buffer pointer.
    00455    \param pos - index of the element.
    00456    \param is_set - output. GAP value (0 or 1).
    00457    \return GAP index.
    00458    @ingroup gapfunc
    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    \brief Tests if bit = pos is true.
    00484    \param buf - GAP buffer pointer.
    00485    \param pos - index of the element.
    00486    \return true if position is in "1" gap
    00487    @ingroup gapfunc
    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 /*! For each non-zero block executes supplied function.
    00526 */
    00527 template<class T, class F>
    00528 void for_each_nzblock(T*** root, unsigned size1, //unsigned size2,
    00529                       F& f)
    00530 {
    00531     for (unsigned i = 0; i < size1; ++i)
    00532     {
    00533         T** blk_blk = root[i];
    00534         if (!blk_blk)
    00535         {
    00536             f.on_empty_top(i);
    00537             continue;
    00538         }
    00539
    00540         unsigned non_empty_top = 0;
    00541         unsigned r = i * bm::set_array_size;
    00542         for (unsigned j = 0;j < bm::set_array_size; ++j)
    00543         {
    00544             if (blk_blk[j])
    00545             {
    00546                 f(blk_blk[j], r + j);
    00547                 non_empty_top += (blk_blk[j] != 0);// re-check for mutation
    00548             }
    00549             else
    00550             {
    00551                 f.on_empty_block(r + j);
    00552             }
    00553         } // for j
    00554         if (non_empty_top == 0)
    00555         {
    00556             f.on_empty_top(i);
    00557         }
    00558     }  // for i
    00559 }
    00560
    00561 /*! For each non-zero block executes supplied function.
    00562 */
    00563 template<class T, class F>
    00564 void for_each_nzblock2(T*** root, unsigned size1, F& f)
    00565 {
    00566     for (unsigned i = 0; i < size1; ++i)
    00567     {
    00568         T** blk_blk;
    00569         if ((blk_blk = root[i])!=0)
    00570         {
    00571             unsigned j = 0;
    00572             do
    00573             {
    00574                 if (blk_blk[j])
    00575                     f(blk_blk[j]);
    00576                 if (blk_blk[j+1])
    00577                     f(blk_blk[j+1]);
    00578                 if (blk_blk[j+2])
    00579                     f(blk_blk[j+2]);
    00580                 if (blk_blk[j+3])
    00581                     f(blk_blk[j+3]);
    00582                 j += 4;
    00583             } while (j < bm::set_array_size);
    00584         }
    00585     }  // for i
    00586 }
    00587
    00588
    00589 /*! For each non-zero block executes supplied function-predicate.
    00590     Function returns if function-predicate returns true
    00591 */
    00592 template<class T, class F>
    00593 bool for_each_nzblock_if(T*** root, unsigned size1, F& f)
    00594 {
    00595     unsigned block_idx = 0;
    00596     for (unsigned i = 0; i < size1; ++i)
    00597     {
    00598         T** blk_blk = root[i];
    00599         if (!blk_blk)
    00600         {
    00601             block_idx += bm::set_array_size;
    00602             continue;
    00603         }
    00604
    00605         for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
    00606         {
    00607             if (blk_blk[j])
    00608                 if (f(blk_blk[j], block_idx)) return true;
    00609         }
    00610     }
    00611     return false;
    00612 }
    00613
    00614 /*! For each block executes supplied function.
    00615 */
    00616 template<class T, class F>
    00617 void for_each_block(T*** root, unsigned size1, F& f)
    00618 {
    00619     unsigned block_idx = 0;
    00620
    00621     for (unsigned i = 0; i < size1; ++i)
    00622     {
    00623         T** blk_blk = root[i];
    00624
    00625         if (blk_blk)
    00626         {
    00627             for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
    00628             {
    00629                 f(blk_blk[j], block_idx);
    00630             }
    00631         }
    00632         else
    00633         {
    00634             for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
    00635             {
    00636                 f(0, block_idx);
    00637             }
    00638         }
    00639     }
    00640 }
    00641
    00642
    00643
    00644 /*! Special BM optimized analog of STL for_each
    00645 */
    00646 template<class T, class F> F bmfor_each(T first, T last, F f)
    00647 {
    00648     do
    00649     {
    00650         f(*first);
    00651         ++first;
    00652     } while (first < last);
    00653     return f;
    00654 }
    00655
    00656 /*! Computes SUM of all elements of the sequence
    00657 */
    00658 template<class T> T sum_arr(T* first, T* last)
    00659 {
    00660     T sum = 0;
    00661     while (first < last)
    00662     {
    00663         sum += *first;
    00664         ++first;
    00665     }
    00666     return sum;
    00667 }
    00668
    00669
    00670
    00671 /*!
    00672    \brief Calculates number of bits ON in GAP buffer.
    00673    \param buf - GAP buffer pointer.
    00674    \param dsize - buffer size
    00675    \return Number of non-zero bits.
    00676    @ingroup gapfunc
    00677 */
    00678 template<typename T> unsigned gap_bit_count(const T* buf, unsigned dsize=0)
    00679 {
    00680     register const T* pcurr = buf;
    00681     if (dsize == 0)
    00682         dsize = (*pcurr >> 3);
    00683
    00684     register const T* pend = pcurr + dsize;
    00685
    00686     register unsigned bits_counter = 0;
    00687     ++pcurr;
    00688
    00689     if (*buf & 1)
    00690     {
    00691         bits_counter += *pcurr + 1;
    00692         ++pcurr;
    00693     }
    00694     ++pcurr;  // set GAP to 1
    00695
    00696     while (pcurr <= pend)
    00697     {
    00698         bits_counter += *pcurr - *(pcurr-1);
    00699         pcurr += 2; // jump to the next positive GAP
    00700     }
    00701
    00702     return bits_counter;
    00703 }
    00704
    00705
    00706 /*!
    00707    \brief Counts 1 bits in GAP buffer in the closed [left, right] diapason.
    00708    \param buf - GAP buffer pointer.
    00709    \param left - leftmost bit index to start from
    00710    \param right- rightmost bit index
    00711    \return Number of non-zero bits.
    00712 */
    00713 template<typename T>
    00714 unsigned gap_bit_count_range(const T* buf, T left, T right)
    00715 {
    00716     BM_ASSERT(left <= right);
    00717
    00718     const T* pcurr = buf;
    00719     const T* pend = pcurr + (*pcurr >> 3);
    00720
    00721     unsigned bits_counter = 0;
    00722     unsigned is_set;
    00723     unsigned start_pos = gap_bfind(buf, left, &is_set);
    00724
    00725     pcurr = buf + start_pos;
    00726     if (right <= *pcurr) // we are in the target block right now
    00727     {
    00728         if (is_set)
    00729             bits_counter = (right - left + 1);
    00730         return bits_counter;
    00731     }
    00732     if (is_set)
    00733         bits_counter += *pcurr - left + 1;
    00734
    00735     unsigned prev_gap = *pcurr++;
    00736     is_set ^= 1;
    00737     while (right > *pcurr)
    00738     {
    00739         if (is_set)
    00740             bits_counter += *pcurr - prev_gap;
    00741         if (pcurr == pend)
    00742             return bits_counter;
    00743         prev_gap = *pcurr++;
    00744         is_set ^= 1;
    00745     }
    00746     if (is_set)
    00747         bits_counter += right - prev_gap;
    00748
    00749     return bits_counter;
    00750 }
    00751
    00752 /*!
    00753     D-GAP block for_each algorithm
    00754
    00755     D-Gap Functor is called for each element but last one.
    00756
    00757    \param gap_buf - GAP buffer
    00758
    00759 */
    00760 template<class T, class Func>
    00761 void for_each_dgap(const T* gap_buf, Func& func)
    00762 {
    00763     const T* pcurr = gap_buf;
    00764     const T* pend = pcurr + (*pcurr >> 3);
    00765     ++pcurr;
    00766
    00767     T prev = *pcurr;
    00768     func(prev + 1); // first element incremented to avoid 0
    00769     ++pcurr;
    00770     do
    00771     {
    00772         func(*pcurr - prev); // all others are [N] - [N-1]
    00773         prev = *pcurr;
    00774     } while (++pcurr < pend);
    00775 }
    00776
    00777 /** d-Gap copy functor
    00778     @internal
    00779 */
    00780 template<typename T> struct d_copy_func
    00781 {
    00782     d_copy_func(T* dg_buf) : dgap_buf_(dg_buf) {}
    00783     void operator()(T dgap) { *dgap_buf_++ = dgap; }
    00784
    00785     T* dgap_buf_;
    00786 };
    00787
    00788 /*!
    00789    \brief Convert GAP buffer into D-GAP buffer
    00790
    00791    Delta GAP representation is DGAP[N] = GAP[N] - GAP[N-1]
    00792
    00793    \param gap_buf - GAP buffer
    00794    \param dgap_buf - Delta-GAP buffer
    00795    \param copy_head - flag to copy GAP header
    00796
    00797    \internal
    00798
    00799    @ingroup gapfunc
    00800 */
    00801 template<typename T>
    00802 T* gap_2_dgap(const T* gap_buf, T* dgap_buf, bool copy_head=true)
    00803 {
    00804     if (copy_head) // copy GAP header
    00805     {
    00806         *dgap_buf++ = *gap_buf;
    00807     }
    00808
    00809     d_copy_func<T> copy_func(dgap_buf);
    00810     for_each_dgap<T, d_copy_func<T> >(gap_buf, copy_func);
    00811     return copy_func.dgap_buf_;
    00812 }
    00813
    00814 /*!
    00815    \brief Convert D-GAP buffer into GAP buffer
    00816
    00817    GAP representation is GAP[N] = DGAP[N] + DGAP[N-1]
    00818
    00819    \param dgap_buf - Delta-GAP buffer
    00820    \param gap_buf  - GAP buffer
    00821
    00822    \internal
    00823    @ingroup gapfunc
    00824 */
    00825 template<typename T>
    00826 void dgap_2_gap(const T* dgap_buf, T* gap_buf, T gap_header=0)
    00827 {
    00828     const T* pcurr = dgap_buf;
    00829     unsigned len;
    00830     if (!gap_header) // GAP header is already part of the stream
    00831     {
    00832         len = *pcurr >> 3;
    00833         *gap_buf++ = *pcurr++; // copy GAP header
    00834     }
    00835     else // GAP header passed as a parameter
    00836     {
    00837         len = gap_header >> 3;
    00838         *gap_buf++ = gap_header; // assign GAP header
    00839     }
    00840     --len; // last element is actually not encoded
    00841     register const T* pend = pcurr + len;
    00842
    00843     *gap_buf = *pcurr++; // copy first element
    00844     if (*gap_buf == 0)
    00845         *gap_buf = 65535; // fix +1 overflow
    00846     else
    00847         *gap_buf = *gap_buf - 1;
    00848
    00849     for (++gap_buf; pcurr < pend; ++pcurr)
    00850     {
    00851         T prev = *(gap_buf-1); // don't remove temp(undef expression!)
    00852         *gap_buf++ = *pcurr + prev;
    00853     }
    00854     *gap_buf = 65535; // add missing last element
    00855 }
    00856
    00857
    00858 /*!
    00859    \brief Lexicographical comparison of GAP buffers.
    00860    \param buf1 - First GAP buffer pointer.
    00861    \param buf2 - Second GAP buffer pointer.
    00862    \return  <0 - less, =0 - equal,  >0 - greater.
    00863
    00864    @ingroup gapfunc
    00865 */
    00866 template<typename T> int gapcmp(const T* buf1, const T* buf2)
    00867 {
    00868     const T* pcurr1 = buf1;
    00869     const T* pend1 = pcurr1 + (*pcurr1 >> 3);
    00870     unsigned bitval1 = *buf1 & 1;
    00871     ++pcurr1;
    00872
    00873     const T* pcurr2 = buf2;
    00874     unsigned bitval2 = *buf2 & 1;
    00875     ++pcurr2;
    00876
    00877     while (pcurr1 <= pend1)
    00878     {
    00879         if (*pcurr1 == *pcurr2)
    00880         {
    00881             if (bitval1 != bitval2)
    00882             {
    00883                 return (bitval1) ? 1 : -1;
    00884             }
    00885         }
    00886         else
    00887         {
    00888             if (bitval1 == bitval2)
    00889             {
    00890                 if (bitval1)
    00891                 {
    00892                     return (*pcurr1 < *pcurr2) ? -1 : 1;
    00893                 }
    00894                 else
    00895                 {
    00896                     return (*pcurr1 < *pcurr2) ? 1 : -1;
    00897                 }
    00898             }
    00899             else
    00900             {
    00901                 return (bitval1) ? 1 : -1;
    00902             }
    00903         }
    00904
    00905         ++pcurr1; ++pcurr2;
    00906
    00907         bitval1 ^= 1;
    00908         bitval2 ^= 1;
    00909     }
    00910
    00911     return 0;
    00912 }
    00913
    00914
    00915 /*!
    00916    \brief Abstract operation for GAP buffers.
    00917           Receives functor F as a template argument
    00918    \param dest - destination memory buffer.
    00919    \param vect1 - operand 1 GAP encoded buffer.
    00920    \param vect1_mask - XOR mask for starting bitflag for vector1
    00921    can be 0 or 1 (1 inverts the vector)
    00922    \param vect2 - operand 2 GAP encoded buffer.
    00923    \param vect2_mask - same as vect1_mask
    00924    \param f - operation functor.
    00925    \param dlen - destination length after the operation
    00926
    00927    \note Internal function.
    00928    @internal
    00929
    00930    @ingroup gapfunc
    00931 */
    00932 template<typename T, class F>
    00933 void gap_buff_op(T*         BMRESTRICT dest,
    00934                  const T*   BMRESTRICT vect1,
    00935                  unsigned   vect1_mask,
    00936                  const T*   BMRESTRICT vect2,
    00937                  unsigned   vect2_mask,
    00938                  F&         f,
    00939                  unsigned&  dlen)
    00940 {
    00941     register const T*  cur1 = vect1;
    00942     register const T*  cur2 = vect2;
    00943
    00944     T bitval1 = (T)((*cur1++ & 1) ^ vect1_mask);
    00945     T bitval2 = (T)((*cur2++ & 1) ^ vect2_mask);
    00946
    00947     T bitval = (T) f(bitval1, bitval2);
    00948     T bitval_prev = bitval;
    00949
    00950     register T* res = dest;
    00951     *res = bitval;
    00952     ++res;
    00953
    00954     while (1)
    00955     {
    00956         bitval = (T) f(bitval1, bitval2);
    00957
    00958         // Check if GAP value changes and we need to
    00959         // start the next one.
    00960         if (bitval != bitval_prev)
    00961         {
    00962             ++res;
    00963             bitval_prev = bitval;
    00964         }
    00965
    00966         if (*cur1 < *cur2)
    00967         {
    00968             *res = *cur1;
    00969             ++cur1;
    00970             bitval1 ^= 1;
    00971         }
    00972         else // >=
    00973         {
    00974             *res = *cur2;
    00975             if (*cur2 < *cur1)
    00976             {
    00977                 bitval2 ^= 1;
    00978             }
    00979             else  // equal
    00980             {
    00981                 if (*cur2 == (bm::gap_max_bits - 1))
    00982                 {
    00983                     break;
    00984                 }
    00985
    00986                 ++cur1;
    00987                 bitval1 ^= 1;
    00988                 bitval2 ^= 1;
    00989             }
    00990             ++cur2;
    00991         }
    00992
    00993     } // while
    00994
    00995     dlen = (unsigned)(res - dest);
    00996     *dest = (T)((*dest & 7) + (dlen << 3));
    00997
    00998 }
    00999
    01000 /*!
    01001    \brief Abstract distance test operation for GAP buffers.
    01002           Receives functor F as a template argument
    01003    \param vect1 - operand 1 GAP encoded buffer.
    01004    \param vect1_mask - XOR mask for starting bitflag for vector1
    01005                        can be 0 or 1 (1 inverts the vector)
    01006    \param vect2 - operand 2 GAP encoded buffer.
    01007    \param vect2_mask - same as vect1_mask
    01008    \param f - operation functor.
    01009    \note Internal function.
    01010    \return non zero value if operation result returns any 1 bit
    01011
    01012    @ingroup gapfunc
    01013 */
    01014 template<typename T, class F>
    01015 unsigned gap_buff_any_op(const T*   BMRESTRICT vect1,
    01016                          unsigned              vect1_mask,
    01017                          const T*   BMRESTRICT vect2,
    01018                          unsigned              vect2_mask,
    01019                          F                     f)
    01020 {
    01021     register const T*  cur1 = vect1;
    01022     register const T*  cur2 = vect2;
    01023
    01024     unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
    01025     unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
    01026
    01027     unsigned bitval = f(bitval1, bitval2);
    01028     if (bitval)
    01029         return bitval;
    01030     unsigned bitval_prev = bitval;
    01031
    01032     while (1)
    01033     {
    01034         bitval = f(bitval1, bitval2);
    01035         if (bitval)
    01036             return bitval;
    01037
    01038         if (bitval != bitval_prev)
    01039             bitval_prev = bitval;
    01040
    01041         if (*cur1 < *cur2)
    01042         {
    01043             ++cur1;
    01044             bitval1 ^= 1;
    01045         }
    01046         else // >=
    01047         {
    01048             if (*cur2 < *cur1)
    01049             {
    01050                 bitval2 ^= 1;
    01051             }
    01052             else  // equal
    01053             {
    01054                 if (*cur2 == (bm::gap_max_bits - 1))
    01055                 {
    01056                     break;
    01057                 }
    01058
    01059                 ++cur1;
    01060                 bitval1 ^= 1;
    01061                 bitval2 ^= 1;
    01062             }
    01063             ++cur2;
    01064         }
    01065
    01066     } // while
    01067
    01068     return 0;
    01069 }
    01070
    01071
    01072
    01073 /*!
    01074    \brief Abstract distance(similarity) operation for GAP buffers.
    01075           Receives functor F as a template argument
    01076    \param vect1 - operand 1 GAP encoded buffer.
    01077    \param vect2 - operand 2 GAP encoded buffer.
    01078    \param f - operation functor.
    01079    \note Internal function.
    01080
    01081    @ingroup gapfunc
    01082 */
    01083 template<typename T, class F>
    01084 unsigned gap_buff_count_op(const T*  vect1, const T*  vect2, F f)
    01085 {
    01086     unsigned count;// = 0;
    01087     const T* cur1 = vect1;
    01088     const T* cur2 = vect2;
    01089
    01090     unsigned bitval1 = (*cur1++ & 1);
    01091     unsigned bitval2 = (*cur2++ & 1);
    01092     unsigned bitval = count = f(bitval1, bitval2);
    01093     unsigned bitval_prev = bitval;
    01094
    01095     //if (bitval) ++count;
    01096
    01097     T res, res_prev;
    01098     res = res_prev = 0;
    01099
    01100     while (1)
    01101     {
    01102         bitval = f(bitval1, bitval2);
    01103
    01104         // Check if GAP value changes and we need to
    01105         // start the next one.
    01106         if (bitval != bitval_prev)
    01107         {
    01108             bitval_prev = bitval;
    01109             res_prev = res;
    01110         }
    01111
    01112         if (*cur1 < *cur2)
    01113         {
    01114             res = *cur1;
    01115             if (bitval)
    01116             {
    01117                 count += res - res_prev;
    01118                 res_prev = res;
    01119             }
    01120             ++cur1;
    01121             bitval1 ^= 1;
    01122         }
    01123         else // >=
    01124         {
    01125             res = *cur2;
    01126             if (bitval)
    01127             {
    01128                 count += res - res_prev;
    01129                 res_prev = res;
    01130             }
    01131             if (*cur2 < *cur1)
    01132             {
    01133                 bitval2 ^= 1;
    01134             }
    01135             else  // equal
    01136             {
    01137                 if (*cur2 == (bm::gap_max_bits - 1))
    01138                 {
    01139                     break;
    01140                 }
    01141
    01142                 ++cur1;
    01143                 bitval1 ^= 1;
    01144                 bitval2 ^= 1;
    01145             }
    01146             ++cur2;
    01147         }
    01148
    01149     } // while
    01150
    01151     return count;
    01152 }
    01153
    01154
    01155
    01156 /*!
    01157    \brief Sets or clears bit in the GAP buffer.
    01158
    01159    \param val - new bit value
    01160    \param buf - GAP buffer.
    01161    \param pos - Index of bit to set.
    01162    \param is_set - (OUT) flag if bit was actually set.
    01163
    01164    \return New GAP buffer length.
    01165
    01166    @ingroup gapfunc
    01167 */
    01168 template<typename T> unsigned gap_set_value(unsigned val,
    01169                                             T* BMRESTRICT buf,
    01170                                             unsigned pos,
    01171                                             unsigned* BMRESTRICT is_set)
    01172 {
    01173     BM_ASSERT(pos < bm::gap_max_bits);
    01174     unsigned curr = gap_bfind(buf, pos, is_set);
    01175
    01176     register T end = (*buf >> 3);
    01177     if (*is_set == val)
    01178     {
    01179         *is_set = 0;
    01180         return end;
    01181     }
    01182     *is_set = 1;
    01183
    01184     register T* pcurr = buf + curr;
    01185     register T* pprev = pcurr - 1;
    01186     register T* pend = buf + end;
    01187
    01188     // Special case, first bit GAP operation. There is no platform beside it.
    01189     // initial flag must be inverted.
    01190     if (pos == 0)
    01191     {
    01192         *buf ^= 1;
    01193         if ( buf[1] ) // We need to insert a 1 bit platform here.
    01194         {
    01195             ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
    01196             buf[1] = 0;
    01197             ++end;
    01198         }
    01199         else // Only 1 bit in the GAP. We need to delete the first GAP.
    01200         {
    01201             pprev = buf + 1;
    01202             pcurr = pprev + 1;
    01203             do
    01204             {
    01205                 *pprev++ = *pcurr++;
    01206             } while (pcurr < pend);
    01207             --end;
    01208         }
    01209     }
    01210     else if (curr > 1 && ((unsigned)(*pprev))+1 == pos) // Left border bit
    01211     {
    01212        ++(*pprev);
    01213        if (*pprev == *pcurr)  // Curr. GAP to be merged with prev.GAP.
    01214        {
    01215             --end;
    01216             if (pcurr != pend) // GAP merge: 2 GAPS to be deleted
    01217             {
    01218                 --end;
    01219                 ++pcurr;
    01220                 do
    01221                 {
    01222                     *pprev++ = *pcurr++;
    01223                 } while (pcurr < pend);
    01224             }
    01225        }
    01226     }
    01227     else if (*pcurr == pos) // Rightmost bit in the GAP. Border goes left.
    01228     {
    01229         --(*pcurr);
    01230         if (pcurr == pend)
    01231         {
    01232            ++end;
    01233         }
    01234     }
    01235     else  // Worst case we need to split current block.
    01236     {
    01237         ::memmove(pcurr+2, pcurr,(end - curr + 1)*sizeof(T));
    01238         *pcurr++ = (T)(pos - 1);
    01239         *pcurr = (T)pos;
    01240         end+=2;
    01241     }
    01242
    01243     // Set correct length word.
    01244     *buf = (*buf & 7) + (end << 3);
    01245
    01246     buf[end] = bm::gap_max_bits - 1;
    01247     return end;
    01248 }
    01249
    01250 /*!
    01251    \brief Add new value to the end of GAP buffer.
    01252
    01253    \param buf - GAP buffer.
    01254    \param pos - Index of bit to set.
    01255
    01256    \return New GAP buffer length.
    01257
    01258    @ingroup gapfunc
    01259 */
    01260 template<typename T>
    01261 unsigned gap_add_value(T* buf, T pos)
    01262 {
    01263     BM_ASSERT(pos < bm::gap_max_bits);
    01264
    01265     register T end = (*buf >> 3);
    01266     T curr = end;
    01267     register T* pcurr = buf + end;
    01268     register T* pend  = pcurr;
    01269     register T* pprev = pcurr - 1;
    01270
    01271     // Special case, first bit GAP operation. There is no platform beside it.
    01272     // initial flag must be inverted.
    01273     if (pos == 0)
    01274     {
    01275         *buf ^= 1;
    01276         if ( buf[1] ) // We need to insert a 1 bit platform here.
    01277         {
    01278             ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
    01279             buf[1] = 0;
    01280             ++end;
    01281         }
    01282         else // Only 1 bit in the GAP. We need to delete the first GAP.
    01283         {
    01284             pprev = buf + 1;
    01285             pcurr = pprev + 1;
    01286             do
    01287             {
    01288                 *pprev++ = *pcurr++;
    01289             } while (pcurr < pend);
    01290             --end;
    01291         }
    01292     }
    01293     else if (((unsigned)(*pprev))+1 == pos && (curr > 1) ) // Left border bit
    01294     {
    01295        ++(*pprev);
    01296        if (*pprev == *pcurr)  // Curr. GAP to be merged with prev.GAP.
    01297        {
    01298             --end;
    01299             if (pcurr != pend) // GAP merge: 2 GAPS to be deleted
    01300             {
    01301                 // TODO: should never get here...
    01302                 --end;
    01303                 ++pcurr;
    01304                 do
    01305                 {
    01306                     *pprev++ = *pcurr++;
    01307                 } while (pcurr < pend);
    01308             }
    01309        }
    01310     }
    01311     else if (*pcurr == pos) // Rightmost bit in the GAP. Border goes left.
    01312     {
    01313         --(*pcurr);
    01314         if (pcurr == pend)
    01315         {
    01316            ++end;
    01317         }
    01318     }
    01319     else  // Worst case we need to split current block.
    01320     {
    01321         *pcurr++ = pos - 1;
    01322         *pcurr = pos;
    01323         end+=2;
    01324     }
    01325
    01326     // Set correct length word.
    01327     *buf = (*buf & 7) + (end << 3);
    01328
    01329     buf[end] = bm::gap_max_bits - 1;
    01330     return end;
    01331 }
    01332
    01333 /*!
    01334    \brief Convert array to GAP buffer.
    01335
    01336    \param buf - GAP buffer.
    01337    \param arr - array of values to set
    01338    \param len - length of the array
    01339
    01340    \return New GAP buffer length.
    01341
    01342    @ingroup gapfunc
    01343 */
    01344
    01345 template<typename T>
    01346 unsigned gap_set_array(T* buf, const T* arr, unsigned len)
    01347 {
    01348     *buf = (*buf & 6u) + (1u << 3); // gap header setup
    01349
    01350     T* pcurr = buf + 1;
    01351
    01352     unsigned i = 0;
    01353     T curr = arr[i];
    01354     if (curr != 0) // need to add the first gap: (0 to arr[0]-1)
    01355     {
    01356         *pcurr = curr - 1;
    01357         ++pcurr;
    01358     }
    01359     else
    01360     {
    01361         *buf += 1; // GAP starts with 1
    01362     }
    01363     T prev = curr;
    01364     T acc = prev;
    01365
    01366     for (i = 1; i < len; ++i)
    01367     {
    01368         T curr = arr[i];
    01369         if (curr == prev + 1)
    01370         {
    01371             ++acc;
    01372             prev = curr;
    01373         }
    01374         else
    01375         {
    01376             *pcurr++ = acc;
    01377             acc = curr;
    01378             *pcurr++ = curr-1;
    01379         }
    01380         prev = curr;
    01381     }
    01382     *pcurr = acc;
    01383     if (acc != bm::gap_max_bits - 1)
    01384     {
    01385         ++pcurr;
    01386         *pcurr = bm::gap_max_bits - 1;
    01387     }
    01388
    01389     unsigned end = pcurr - buf;
    01390
    01391     *buf = (T)((*buf & 7) + (end << 3));
    01392     return end+1;
    01393 }
    01394
    01395
    01396 //------------------------------------------------------------------------
    01397
    01398 /**
    01399     \brief Compute number of GAPs in bit-array
    01400     \param arr - array of BITs
    01401     \param len - array length
    01402
    01403     @ingroup gapfunc
    01404 */
    01405 template<typename T>
    01406 unsigned bit_array_compute_gaps(const T* arr,
    01407                                 unsigned len)
    01408 {
    01409     unsigned gap_count = 1;
    01410     T prev = arr[0];
    01411     if (prev > 0)
    01412         ++gap_count;
    01413     for (unsigned i = 1; i < len; ++i)
    01414     {
    01415         T curr = arr[i];
    01416         if (curr != prev + 1)
    01417         {
    01418             gap_count += 2;
    01419         }
    01420         prev = curr;
    01421     }
    01422     return gap_count;
    01423 }
    01424
    01425
    01426 //------------------------------------------------------------------------
    01427
    01428 /**
    01429     \brief Searches for the next 1 bit in the GAP block
    01430     \param buf - GAP buffer
    01431     \param nbit - bit index to start checking from.
    01432     \param prev - returns previously checked value
    01433
    01434     @ingroup gapfunc
    01435 */
    01436 template<typename T> int gap_find_in_block(const T* buf,
    01437                                            unsigned nbit,
    01438                                            bm::id_t* prev)
    01439 {
    01440     BM_ASSERT(nbit < bm::gap_max_bits);
    01441
    01442     unsigned bitval;
    01443     unsigned gap_idx = bm::gap_bfind(buf, nbit, &bitval);
    01444
    01445     if (bitval) // positive block.
    01446     {
    01447        return 1;
    01448     }
    01449
    01450     register unsigned val = buf[gap_idx] + 1;
    01451     *prev += val - nbit;
    01452
    01453     return (val != bm::gap_max_bits);  // no bug here.
    01454 }
    01455
    01456 /*!
    01457     \brief Set 1 bit in a block
    01458
    01459     @ingroup bitfunc
    01460 */
    01461 BMFORCEINLINE void set_bit(unsigned* dest, unsigned  bitpos)
    01462 {
    01463     unsigned nbit  = unsigned(bitpos & bm::set_block_mask);
    01464     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    01465     nbit &= bm::set_word_mask;
    01466     dest[nword] |= unsigned(1 << nbit);
    01467 }
    01468
    01469 /*!
    01470     \brief Test 1 bit in a block
    01471
    01472     @ingroup bitfunc
    01473 */
    01474 BMFORCEINLINE unsigned test_bit(const unsigned* block, unsigned  bitpos)
    01475 {
    01476     unsigned nbit  = unsigned(bitpos & bm::set_block_mask);
    01477     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    01478     nbit &= bm::set_word_mask;
    01479     return (block[nword] >> nbit) & 1u;
    01480 }
    01481
    01482
    01483 /*!
    01484    \brief Sets bits to 1 in the bitblock.
    01485    \param dest - Bitset buffer.
    01486    \param bitpos - Offset of the start bit.
    01487    \param bitcount - number of bits to set.
    01488
    01489    @ingroup bitfunc
    01490 */
    01491 inline void or_bit_block(unsigned* dest,
    01492                          unsigned bitpos,
    01493                          unsigned bitcount)
    01494 {
    01495     unsigned nbit  = unsigned(bitpos & bm::set_block_mask);
    01496     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    01497     nbit &= bm::set_word_mask;
    01498
    01499     bm::word_t* word = dest + nword;
    01500
    01501     if (bitcount == 1)  // special case (only 1 bit to set)
    01502     {
    01503         *word |= unsigned(1 << nbit);
    01504         return;
    01505     }
    01506
    01507     if (nbit) // starting position is not aligned
    01508     {
    01509         unsigned right_margin = nbit + bitcount;
    01510
    01511         // here we checking if we setting bits only in the current
    01512         // word. Example: 00111000000000000000000000000000 (32 bits word)
    01513
    01514         if (right_margin < 32)
    01515         {
    01516             unsigned mask =
    01517                 block_set_table<true>::_right[nbit] &
    01518                 block_set_table<true>::_left[right_margin-1];
    01519             *word |= mask;
    01520             return; // we are done
    01521         }
    01522         else
    01523         {
    01524             *word |= block_set_table<true>::_right[nbit];
    01525             bitcount -= 32 - nbit;
    01526         }
    01527         ++word;
    01528     }
    01529
    01530     // now we are word aligned, lets find out how many words we
    01531     // can now turn ON using loop
    01532
    01533     for ( ;bitcount >= 32; bitcount -= 32)
    01534     {
    01535         *word++ = 0xffffffff;
    01536     }
    01537
    01538     if (bitcount)
    01539     {
    01540         *word |= block_set_table<true>::_left[bitcount-1];
    01541     }
    01542 }
    01543
    01544
    01545 /*!
    01546    \brief SUB (AND NOT) bit interval to 1 in the bitblock.
    01547    \param dest - Bitset buffer.
    01548    \param bitpos - Offset of the start bit.
    01549    \param bitcount - number of bits to set.
    01550
    01551    @ingroup bitfunc
    01552 */
    01553 inline void sub_bit_block(unsigned* dest,
    01554                           unsigned bitpos,
    01555                           unsigned bitcount)
    01556 {
    01557     unsigned nbit  = unsigned(bitpos & bm::set_block_mask);
    01558     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    01559     nbit &= bm::set_word_mask;
    01560
    01561     bm::word_t* word = dest + nword;
    01562
    01563     if (bitcount == 1)  // special case (only 1 bit to set)
    01564     {
    01565         *word &= ~unsigned(1 << nbit);
    01566         return;
    01567     }
    01568
    01569     if (nbit) // starting position is not aligned
    01570     {
    01571         unsigned right_margin = nbit + bitcount;
    01572
    01573         // here we checking if we setting bits only in the current
    01574         // word. Example: 00111000000000000000000000000000 (32 bits word)
    01575
    01576         if (right_margin < 32)
    01577         {
    01578             unsigned mask =
    01579                 block_set_table<true>::_right[nbit] &
    01580                 block_set_table<true>::_left[right_margin-1];
    01581             *word &= ~mask;
    01582             return; // we are done
    01583         }
    01584         else
    01585         {
    01586             *word &= ~block_set_table<true>::_right[nbit];
    01587             bitcount -= 32 - nbit;
    01588         }
    01589         ++word;
    01590     }
    01591
    01592     // now we are word aligned, lets find out how many words we
    01593     // can now turn ON using loop
    01594
    01595     for ( ;bitcount >= 32; bitcount -= 32)
    01596     {
    01597         *word++ = 0;
    01598     }
    01599
    01600     if (bitcount)
    01601     {
    01602         *word &= ~block_set_table<true>::_left[bitcount-1];
    01603     }
    01604 }
    01605
    01606
    01607 /*!
    01608    \brief XOR bit interval to 1 in the bitblock.
    01609    \param dest - Bitset buffer.
    01610    \param bitpos - Offset of the start bit.
    01611    \param bitcount - number of bits to set.
    01612
    01613    @ingroup bitfunc
    01614 */
    01615 inline void xor_bit_block(unsigned* dest,
    01616                           unsigned bitpos,
    01617                           unsigned bitcount)
    01618 {
    01619     unsigned nbit  = unsigned(bitpos & bm::set_block_mask);
    01620     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    01621     nbit &= bm::set_word_mask;
    01622
    01623     bm::word_t* word = dest + nword;
    01624
    01625     if (bitcount == 1)  // special case (only 1 bit to set)
    01626     {
    01627         *word ^= unsigned(1 << nbit);
    01628         return;
    01629     }
    01630
    01631     if (nbit) // starting position is not aligned
    01632     {
    01633         unsigned right_margin = nbit + bitcount;
    01634
    01635         // here we checking if we setting bits only in the current
    01636         // word. Example: 00111000000000000000000000000000 (32 bits word)
    01637
    01638         if (right_margin < 32)
    01639         {
    01640             unsigned mask =
    01641                 block_set_table<true>::_right[nbit] &
    01642                 block_set_table<true>::_left[right_margin-1];
    01643             *word ^= mask;
    01644             return; // we are done
    01645         }
    01646         else
    01647         {
    01648             *word ^= block_set_table<true>::_right[nbit];
    01649             bitcount -= 32 - nbit;
    01650         }
    01651         ++word;
    01652     }
    01653
    01654     // now we are word aligned, lets find out how many words we
    01655     // can now turn ON using loop
    01656
    01657     for ( ;bitcount >= 32; bitcount -= 32)
    01658     {
    01659         *word++ ^= 0xffffffff;
    01660     }
    01661
    01662     if (bitcount)
    01663     {
    01664         *word ^= block_set_table<true>::_left[bitcount-1];
    01665     }
    01666 }
    01667
    01668
    01669 /*!
    01670    \brief SUB (AND NOT) GAP block to bitblock.
    01671    \param dest - bitblock buffer pointer.
    01672    \param buf  - GAP buffer pointer.
    01673
    01674    @ingroup gapfunc
    01675 */
    01676 template<typename T>
    01677 void gap_sub_to_bitset(unsigned* BMRESTRICT dest, const T* BMRESTRICT buf)
    01678 {
    01679     const T* pend = buf + (*buf >> 3);
    01680     T b = *buf & 1;
    01681     ++buf;
    01682
    01683     if (b)  // Starts with 1
    01684     {
    01685         sub_bit_block(dest, 0, *buf + 1);
    01686         ++buf;
    01687     }
    01688     for (++buf; buf <= pend; buf += 2)
    01689     {
    01690         T prev = *(buf-1);
    01691         BM_ASSERT(*buf > prev);
    01692         sub_bit_block(dest, prev + 1, *buf - prev);
    01693     }
    01694 }
    01695
    01696
    01697 /*!
    01698    \brief XOR GAP block to bitblock.
    01699    \param dest - bitblock buffer pointer.
    01700    \param buf  - GAP buffer pointer.
    01701
    01702    @ingroup gapfunc
    01703 */
    01704 template<typename T>
    01705 void gap_xor_to_bitset(unsigned* BMRESTRICT dest, const T* BMRESTRICT buf)
    01706 {
    01707     const T* pend = buf + (*buf >> 3);
    01708     T b = *buf & 1;
    01709     ++buf;
    01710
    01711     if (b)  // Starts with 1
    01712     {
    01713         xor_bit_block(dest, 0, *buf + 1);
    01714         ++buf;
    01715     }
    01716     for (++buf; buf <= pend; buf += 2)
    01717     {
    01718         T prev = *(buf-1);
    01719         BM_ASSERT(*buf > prev);
    01720         xor_bit_block(dest, prev + 1, *buf - prev);
    01721     }
    01722 }
    01723
    01724 /*!
    01725 \brief Adds(OR) GAP block to bitblock.
    01726 \param dest - bitblock buffer pointer.
    01727 \param buf  - GAP buffer pointer.
    01728 \param buf_len - GAP buffer length
    01729
    01730 @ingroup gapfunc
    01731 */
    01732 template<typename T>
    01733 void gap_add_to_bitset_l(unsigned* dest, const T*  buf, unsigned buf_len)
    01734 {
    01735     BM_ASSERT(buf_len);
    01736     register const T* pend = buf + buf_len;
    01737     T b = *buf & 1;
    01738     ++buf;
    01739
    01740     if (b)  // Starts with 1
    01741     {
    01742         or_bit_block(dest, 0, *buf + 1);
    01743         ++buf;
    01744     }
    01745     for (++buf; buf <= pend; buf += 2)
    01746     {
    01747         T prev = *(buf-1);
    01748         BM_ASSERT(*buf > prev);
    01749         or_bit_block(dest, prev + 1, *buf - prev);
    01750     }
    01751 }
    01752
    01753
    01754
    01755 /*!
    01756    \brief Adds(OR) GAP block to bitblock.
    01757    \param dest - bitblock buffer pointer.
    01758    \param buf  - GAP buffer pointer.
    01759
    01760    @ingroup gapfunc
    01761 */
    01762 template<typename T>
    01763 void gap_add_to_bitset(unsigned* dest, const T*  buf)
    01764 {
    01765     gap_add_to_bitset_l(dest, buf, *buf >> 3);
    01766 }
    01767
    01768
    01769 /*!
    01770    \brief ANDs GAP block to bitblock.
    01771    \param dest - bitblock buffer pointer.
    01772    \param buf  - GAP buffer pointer.
    01773
    01774    @ingroup gapfunc
    01775 */
    01776 template<typename T>
    01777 void gap_and_to_bitset(unsigned* dest, const T*  buf)
    01778 {
    01779     register const T* pend = buf + (*buf >> 3);
    01780     T b = *buf & 1;
    01781     ++buf;
    01782
    01783     if (!b )  // Starts with 0
    01784     {
    01785         // Instead of AND we can SUB 0 gaps here
    01786         sub_bit_block(dest, 0, *buf + 1);
    01787         ++buf;
    01788     }
    01789     for (++buf; buf <= pend; buf += 2)
    01790     {
    01791         T prev = *(buf-1);
    01792         BM_ASSERT(*buf > prev);
    01793         sub_bit_block(dest, prev + 1, *buf - prev);
    01794     }
    01795 }
    01796
    01797
    01798 /*!
    01799    \brief Compute bitcount of bit block AND masked by GAP block.
    01800    \param dest - bitblock buffer pointer.
    01801    \param buf  - GAP buffer pointer.
    01802
    01803    @ingroup gapfunc bitfunc
    01804 */
    01805 template<typename T>
    01806 bm::id_t gap_bitset_and_count(const unsigned* block, const T*  buf)
    01807 {
    01808     BM_ASSERT(block);
    01809
    01810     const T* pcurr = buf;
    01811     const T* pend = pcurr + (*pcurr >> 3);
    01812     ++pcurr;
    01813
    01814     bm::id_t count = 0;
    01815     if (*buf & 1)  // Starts with 1
    01816     {
    01817         count += bit_block_calc_count_range(block, 0, *pcurr);
    01818         ++pcurr;
    01819     }
    01820     ++pcurr; // now we are in GAP "1" again
    01821     for (;pcurr <= pend; pcurr += 2)
    01822     {
    01823         count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
    01824     }
    01825     return count;
    01826 }
    01827
    01828
    01829 /*!
    01830    \brief Bitcount test of bit block AND masked by GAP block.
    01831    \param dest - bitblock buffer pointer.
    01832    \param buf  - GAP buffer pointer.
    01833
    01834    @ingroup gapfunc bitfunc
    01835 */
    01836 template<typename T>
    01837 bm::id_t gap_bitset_and_any(const unsigned* block, const T*  buf)
    01838 {
    01839     BM_ASSERT(block);
    01840
    01841     register const T* pcurr = buf;
    01842     register const T* pend = pcurr + (*pcurr >> 3);
    01843     ++pcurr;
    01844
    01845     bm::id_t count = 0;
    01846     if (*buf & 1)  // Starts with 1
    01847     {
    01848         count += bit_block_any_range(block, 0, *pcurr);
    01849         if (count)
    01850             return count;
    01851         ++pcurr;
    01852     }
    01853     ++pcurr; // now we are in GAP "1" again
    01854
    01855     while (pcurr <= pend)
    01856     {
    01857         bm::id_t c = bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
    01858         count += c;
    01859         if (count)
    01860             break;
    01861         pcurr += 2;
    01862     }
    01863     return count;
    01864 }
    01865
    01866
    01867
    01868 /*!
    01869    \brief Compute bitcount of bit block SUB masked by GAP block.
    01870    \param dest - bitblock buffer pointer.
    01871    \param buf  - GAP buffer pointer.
    01872
    01873    @ingroup gapfunc bitfunc
    01874 */
    01875 template<typename T>
    01876 bm::id_t gap_bitset_sub_count(const unsigned* block, const T*  buf)
    01877 {
    01878     BM_ASSERT(block);
    01879
    01880     register const T* pcurr = buf;
    01881     register const T* pend = pcurr + (*pcurr >> 3);
    01882     ++pcurr;
    01883
    01884     bm::id_t count = 0;
    01885
    01886     if (!(*buf & 1))  // Starts with 0
    01887     {
    01888         count += bit_block_calc_count_range(block, 0, *pcurr);
    01889         ++pcurr;
    01890     }
    01891     ++pcurr; // now we are in GAP "0" again
    01892
    01893     for (;pcurr <= pend; pcurr+=2)
    01894     {
    01895         count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
    01896     }
    01897     return count;
    01898 }
    01899
    01900
    01901 /*!
    01902    \brief Compute bitcount test of bit block SUB masked by GAP block.
    01903    \param dest - bitblock buffer pointer.
    01904    \param buf  - GAP buffer pointer.
    01905
    01906    @ingroup gapfunc bitfunc
    01907 */
    01908 template<typename T>
    01909 bm::id_t gap_bitset_sub_any(const unsigned* block, const T*  buf)
    01910 {
    01911     BM_ASSERT(block);
    01912
    01913     register const T* pcurr = buf;
    01914     register const T* pend = pcurr + (*pcurr >> 3);
    01915     ++pcurr;
    01916
    01917     bm::id_t count = 0;
    01918
    01919     if (!(*buf & 1))  // Starts with 0
    01920     {
    01921         count += bit_block_any_range(block, 0, *pcurr);
    01922         if (count)
    01923             return count;
    01924         ++pcurr;
    01925     }
    01926     ++pcurr; // now we are in GAP "0" again
    01927
    01928     for (;pcurr <= pend; pcurr+=2)
    01929     {
    01930         count += bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
    01931         if (count)
    01932             return count;
    01933     }
    01934     return count;
    01935 }
    01936
    01937
    01938
    01939 /*!
    01940    \brief Compute bitcount of bit block XOR masked by GAP block.
    01941    \param dest - bitblock buffer pointer.
    01942    \param buf  - GAP buffer pointer.
    01943
    01944    @ingroup gapfunc bitfunc
    01945 */
    01946 template<typename T>
    01947 bm::id_t gap_bitset_xor_count(const unsigned* block, const T*  buf)
    01948 {
    01949     BM_ASSERT(block);
    01950
    01951     register const T* pcurr = buf;
    01952     register const T* pend = pcurr + (*pcurr >> 3);
    01953     ++pcurr;
    01954
    01955     unsigned bitval = *buf & 1;
    01956
    01957     register bm::id_t count = bit_block_calc_count_range(block, 0, *pcurr);
    01958     if (bitval)
    01959     {
    01960         count = *pcurr + 1 - count;
    01961     }
    01962
    01963     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
    01964     {
    01965         T prev = *(pcurr-1)+1;
    01966         bm::id_t c = bit_block_calc_count_range(block, prev, *pcurr);
    01967
    01968         if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
    01969         {
    01970             c = (*pcurr - prev + 1) - c;
    01971         }
    01972         count += c;
    01973     }
    01974     return count;
    01975 }
    01976
    01977 /*!
    01978    \brief Compute bitcount test of bit block XOR masked by GAP block.
    01979    \param dest - bitblock buffer pointer.
    01980    \param buf  - GAP buffer pointer.
    01981
    01982    @ingroup gapfunc bitfunc
    01983 */
    01984 template<typename T>
    01985 bm::id_t gap_bitset_xor_any(const unsigned* block, const T*  buf)
    01986 {
    01987     BM_ASSERT(block);
    01988
    01989     register const T* pcurr = buf;
    01990     register const T* pend = pcurr + (*pcurr >> 3);
    01991     ++pcurr;
    01992
    01993     unsigned bitval = *buf & 1;
    01994
    01995     register bm::id_t count = bit_block_any_range(block, 0, *pcurr);
    01996     if (bitval)
    01997     {
    01998         count = *pcurr + 1 - count;
    01999     }
    02000
    02001     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
    02002     {
    02003         T prev = *(pcurr-1)+1;
    02004         bm::id_t c = bit_block_any_range(block, prev, *pcurr);
    02005
    02006         if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
    02007         {
    02008             c = (*pcurr - prev + 1) - c;
    02009         }
    02010
    02011         count += c;
    02012         if (count)
    02013             return count;
    02014     }
    02015     return count;
    02016 }
    02017
    02018
    02019
    02020 /*!
    02021    \brief Compute bitcount of bit block OR masked by GAP block.
    02022    \param dest - bitblock buffer pointer.
    02023    \param buf  - GAP buffer pointer.
    02024
    02025    @ingroup gapfunc bitfunc
    02026 */
    02027 template<typename T>
    02028 bm::id_t gap_bitset_or_count(const unsigned* block, const T*  buf)
    02029 {
    02030     BM_ASSERT(block);
    02031
    02032     register const T* pcurr = buf;
    02033     register const T* pend = pcurr + (*pcurr >> 3);
    02034     ++pcurr;
    02035
    02036     unsigned bitval = *buf & 1;
    02037
    02038     register bm::id_t count;
    02039     if (bitval)
    02040     {
    02041         count = *pcurr + 1;
    02042     }
    02043     else
    02044     {
    02045         count = bit_block_calc_count_range(block, 0, *pcurr);
    02046     }
    02047
    02048     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
    02049     {
    02050         T prev = *(pcurr-1)+1;
    02051         bm::id_t c;
    02052
    02053         if (bitval)
    02054         {
    02055             c = (*pcurr - prev + 1);
    02056         }
    02057         else
    02058         {
    02059             c = bit_block_calc_count_range(block, prev, *pcurr);
    02060         }
    02061
    02062         count += c;
    02063     }
    02064     return count;
    02065 }
    02066
    02067 /*!
    02068    \brief Compute bitcount test of bit block OR masked by GAP block.
    02069    \param dest - bitblock buffer pointer.
    02070    \param buf  - GAP buffer pointer.
    02071
    02072    @ingroup gapfunc bitfunc
    02073 */
    02074 template<typename T>
    02075 bm::id_t gap_bitset_or_any(const unsigned* block, const T*  buf)
    02076 {
    02077     BM_ASSERT(block);
    02078
    02079     register const T* pcurr = buf;
    02080     register const T* pend = pcurr + (*pcurr >> 3);
    02081     ++pcurr;
    02082
    02083     unsigned bitval = *buf & 1;
    02084
    02085     register bm::id_t count;
    02086     if (bitval)
    02087     {
    02088         count = *pcurr + 1;
    02089     }
    02090     else
    02091     {
    02092         count = bit_block_any_range(block, 0, *pcurr);
    02093     }
    02094
    02095     for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
    02096     {
    02097         T prev = *(pcurr-1)+1;
    02098         bm::id_t c;
    02099
    02100         if (bitval)
    02101         {
    02102             c = (*pcurr - prev + 1);
    02103         }
    02104         else
    02105         {
    02106             c = bit_block_any_range(block, prev, *pcurr);
    02107         }
    02108         count += c;
    02109         if (count)
    02110             return count;
    02111     }
    02112     return count;
    02113 }
    02114
    02115
    02116
    02117 /*!
    02118    \brief Bitblock memset operation.
    02119
    02120    \param dst - destination block.
    02121    \param value - value to set.
    02122
    02123    @ingroup bitfunc
    02124 */
    02125 inline
    02126 void bit_block_set(bm::word_t* BMRESTRICT dst, bm::word_t value)
    02127 {
    02128 //#ifdef BMVECTOPT
    02129 //    VECT_SET_BLOCK(dst, dst + bm::set_block_size, value);
    02130 //#else
    02131     ::memset(dst, value, bm::set_block_size * sizeof(bm::word_t));
    02132 //#endif
    02133 }
    02134
    02135
    02136 /*!
    02137    \brief GAP block to bitblock conversion.
    02138    \param dest - bitblock buffer pointer.
    02139    \param buf  - GAP buffer pointer.
    02140
    02141    @ingroup gapfunc
    02142 */
    02143 template<typename T>
    02144 void gap_convert_to_bitset(unsigned* dest, const T*  buf)
    02145 {
    02146     bit_block_set(dest, 0);
    02147     gap_add_to_bitset(dest, buf);
    02148 }
    02149
    02150 /*!
    02151 \brief GAP block to bitblock conversion.
    02152 \param dest - bitblock buffer pointer.
    02153 \param buf  - GAP buffer pointer.
    02154
    02155 @ingroup gapfunc
    02156 */
    02157 template<typename T>
    02158 void gap_convert_to_bitset_l(unsigned* dest, const T*  buf, unsigned buf_len)
    02159 {
    02160     bit_block_set(dest, 0);
    02161     gap_add_to_bitset_l(dest, buf, buf_len ? buf_len : *buf >> 3);
    02162 }
    02163
    02164
    02165
    02166 /*!
    02167    \brief GAP block to bitblock conversion.
    02168    \param dest - bitblock buffer pointer.
    02169    \param buf  - GAP buffer pointer.
    02170    \param dest_size - length of the destination buffer.
    02171
    02172    @ingroup gapfunc
    02173 */
    02174 template<typename T>
    02175 void gap_convert_to_bitset(unsigned* dest, const T*  buf,  unsigned  dest_len)
    02176 {
    02177    ::memset(dest, 0, dest_len * sizeof(unsigned));
    02178     gap_add_to_bitset(dest, buf);
    02179 }
    02180
    02181
    02182
    02183 /*!
    02184    \brief Smart GAP block to bitblock conversion.
    02185
    02186     Checks if GAP block is ALL-ZERO or ALL-ON. In those cases returns
    02187     pointer on special static bitblocks.
    02188
    02189    \param dest - bitblock buffer pointer.
    02190    \param buf  - GAP buffer pointer.
    02191    \param set_max - max possible bitset length
    02192
    02193    @ingroup gapfunc
    02194 */
    02195 template<typename T>
    02196         unsigned* gap_convert_to_bitset_smart(unsigned* dest,
    02197                                               const T* buf,
    02198                                               id_t set_max)
    02199 {
    02200     if (buf[1] == set_max - 1)
    02201     {
    02202         return (buf[0] & 1) ? FULL_BLOCK_ADDR : 0;
    02203     }
    02204
    02205     gap_convert_to_bitset(dest, buf);
    02206     return dest;
    02207 }
    02208
    02209
    02210 /*!
    02211    \brief Calculates sum of all words in GAP block. (For debugging purposes)
    02212    \note For debugging and testing ONLY.
    02213    \param buf - GAP buffer pointer.
    02214    \return Sum of all words.
    02215
    02216    @ingroup gapfunc
    02217 */
    02218 template<typename T> unsigned gap_control_sum(const T* buf)
    02219 {
    02220     unsigned end = *buf >> 3;
    02221
    02222     register const T* pcurr = buf;
    02223     register const T* pend = pcurr + (*pcurr >> 3);
    02224     ++pcurr;
    02225
    02226     if (*buf & 1)  // Starts with 1
    02227     {
    02228         ++pcurr;
    02229     }
    02230     ++pcurr; // now we are in GAP "1" again
    02231
    02232     while (pcurr <= pend)
    02233     {
    02234         BM_ASSERT(*pcurr > *(pcurr-1));
    02235         pcurr += 2;
    02236     }
    02237     return buf[end];
    02238
    02239 }
    02240
    02241
    02242 /*!
    02243    \brief Sets all bits to 0 or 1 (GAP)
    02244    \param buf - GAP buffer pointer.
    02245    \param set_max - max possible bitset length
    02246
    02247    @ingroup gapfunc
    02248 */
    02249 template<class T> void gap_set_all(T* buf,
    02250                                    unsigned set_max,
    02251                                    unsigned value)
    02252 {
    02253     BM_ASSERT(value == 0 || value == 1);
    02254     *buf = (T)((*buf & 6u) + (1u << 3) + value);
    02255     *(++buf) = (T)(set_max - 1);
    02256 }
    02257
    02258
    02259 /*!
    02260     \brief Init gap block so it has block in it (can be whole block)
    02261     \param buf  - GAP buffer pointer.
    02262     \param from - one block start
    02263     \param to   - one block end
    02264     \param value - (block value)1 or 0
    02265     \param set_max - max possible bitset length
    02266
    02267    @ingroup gapfunc
    02268 */
    02269 template<class T>
    02270 void gap_init_range_block(T* buf,
    02271                           T  from,
    02272                           T  to,
    02273                           T  value,
    02274                           unsigned set_max)
    02275 {
    02276     BM_ASSERT(value == 0 || value == 1);
    02277
    02278     unsigned gap_len;
    02279     if (from == 0)
    02280     {
    02281         if (to == set_max - 1)
    02282         {
    02283             gap_set_all(buf, set_max, value);
    02284         }
    02285         else
    02286         {
    02287             gap_len = 2;
    02288             buf[1] = to;
    02289             buf[2] = (T)(set_max - 1);
    02290             buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
    02291         }
    02292         return;
    02293     }
    02294     // from != 0
    02295
    02296     value = !value;
    02297     if (to == set_max - 1)
    02298     {
    02299         gap_len = 2;
    02300         buf[1] = (T)(from - 1);
    02301         buf[2] = (T)(set_max - 1);
    02302     }
    02303     else
    02304     {
    02305         gap_len = 3;
    02306         buf[1] = from - 1;
    02307         buf[2] = (T) to;
    02308         buf[3] = (T)(set_max - 1);
    02309     }
    02310     buf[0] =  (T)((*buf & 6u) + (gap_len << 3) + value);
    02311 }
    02312
    02313
    02314 /*!
    02315    \brief Inverts all bits in the GAP buffer.
    02316    \param buf - GAP buffer pointer.
    02317
    02318    @ingroup gapfunc
    02319 */
    02320 template<typename T> void gap_invert(T* buf)
    02321 {
    02322     *buf ^= 1;
    02323 }
    02324
    02325 /*!
    02326    \brief Temporary inverts all bits in the GAP buffer.
    02327
    02328    In this function const-ness of the buffer means nothing.
    02329    Calling this function again restores the status of the buffer.
    02330
    02331    \param buf - GAP buffer pointer. (Buffer IS changed)
    02332
    02333    @ingroup gapfunc
    02334 */
    02335 /*
    02336 template<typename T> void gap_temp_invert(const T* buf)
    02337 {
    02338     T* buftmp = const_cast<T*>(buf);
    02339     *buftmp ^= 1;
    02340 }
    02341 */
    02342
    02343 /*!
    02344    \brief Checks if GAP block is all-zero.
    02345    \param buf - GAP buffer pointer.
    02346    \param set_max - max possible bitset length
    02347    \returns true if all-zero.
    02348
    02349    @ingroup gapfunc
    02350 */
    02351 template<typename T>
    02352              bool gap_is_all_zero(const T* buf, unsigned set_max)
    02353 {
    02354     return (((*buf & 1)==0)  && (*(++buf) == set_max - 1));
    02355 }
    02356
    02357 /*!
    02358    \brief Checks if GAP block is all-one.
    02359    \param buf - GAP buffer pointer.
    02360    \param set_max - max possible bitset length
    02361    \returns true if all-one.
    02362
    02363    @ingroup gapfunc
    02364 */
    02365 template<typename T>
    02366          bool gap_is_all_one(const T* buf, unsigned set_max)
    02367 {
    02368     return ((*buf & 1)  && (*(++buf) == set_max - 1));
    02369 }
    02370
    02371 /*!
    02372    \brief Returs GAP block length.
    02373    \param buf - GAP buffer pointer.
    02374    \returns GAP block length.
    02375
    02376    @ingroup gapfunc
    02377 */
    02378 template<typename T> T gap_length(const T* buf)
    02379 {
    02380     return (*buf >> 3) + 1;
    02381 }
    02382
    02383
    02384 /*!
    02385    \brief Returs GAP block capacity.
    02386    \param buf - GAP buffer pointer.
    02387    \returns GAP block capacity.
    02388
    02389    @ingroup gapfunc
    02390 */
    02391 template<typename T>
    02392 unsigned gap_capacity(const T* buf, const T* glevel_len)
    02393 {
    02394     return glevel_len[(*buf >> 1) & 3];
    02395 }
    02396
    02397
    02398 /*!
    02399    \brief Returs GAP block capacity limit.
    02400    \param buf - GAP buffer pointer.
    02401    \param glevel_len - GAP lengths table (gap_len_table)
    02402    \returns GAP block limit.
    02403
    02404    @ingroup gapfunc
    02405 */
    02406 template<typename T>
    02407 unsigned gap_limit(const T* buf, const T* glevel_len)
    02408 {
    02409     return glevel_len[(*buf >> 1) & 3]-4;
    02410 }
    02411
    02412
    02413 /*!
    02414    \brief Returs GAP blocks capacity level.
    02415    \param buf - GAP buffer pointer.
    02416    \returns GAP block capacity level.
    02417
    02418    @ingroup gapfunc
    02419 */
    02420 template<typename T> unsigned gap_level(const T* buf)
    02421 {
    02422     return (*buf >> 1) & 3;
    02423 }
    02424
    02425
    02426 /*!
    02427    \brief Sets GAP block capacity level.
    02428    \param buf - GAP buffer pointer.
    02429    \param level new GAP block capacity level.
    02430
    02431    @ingroup gapfunc
    02432 */
    02433 template<typename T>
    02434 void set_gap_level(T* buf, unsigned level)
    02435 {
    02436     BM_ASSERT(level < bm::gap_levels);
    02437     *buf = ((level & 3) << 1) | (*buf & 1) | (*buf & ~7);
    02438 }
    02439
    02440
    02441 /*!
    02442    \brief Calculates GAP block capacity level.
    02443    \param len - GAP buffer length.
    02444    \param glevel_len - GAP lengths table
    02445    \return GAP block capacity level.
    02446             -1 if block does not fit any level.
    02447    @ingroup gapfunc
    02448 */
    02449 template<typename T>
    02450 inline int gap_calc_level(int len, const T* glevel_len)
    02451 {
    02452     if (len <= (glevel_len[0]-4)) return 0;
    02453     if (len <= (glevel_len[1]-4)) return 1;
    02454     if (len <= (glevel_len[2]-4)) return 2;
    02455     if (len <= (glevel_len[3]-4)) return 3;
    02456
    02457     BM_ASSERT(bm::gap_levels == 4);
    02458     return -1;
    02459 }
    02460
    02461 /*! @brief Returns number of free elements in GAP block array.
    02462     Difference between GAP block capacity on this level and actual GAP length.
    02463
    02464     @param buf - GAP buffer pointer
    02465     @parma glevel_len - GAP lengths table
    02466
    02467     @return Number of free GAP elements
    02468     @ingroup gapfunc
    02469 */
    02470 template<typename T>
    02471 inline unsigned gap_free_elements(const T* buf, const T* glevel_len)
    02472 {
    02473     unsigned len = gap_length(buf);
    02474     unsigned capacity = gap_capacity(buf, glevel_len);
    02475     return capacity - len;
    02476 }
    02477
    02478
    02479 /*!
    02480    \brief Lexicographical comparison of BIT buffers.
    02481    \param buf1 - First buffer pointer.
    02482    \param buf2 - Second buffer pointer.
    02483    \param len - Buffer length in elements (T).
    02484    \return  <0 - less, =0 - equal,  >0 - greater.
    02485
    02486    @ingroup bitfunc
    02487 */
    02488 template<typename T>
    02489 int bitcmp(const T* buf1, const T* buf2, unsigned len)
    02490 {
    02491     BM_ASSERT(len);
    02492     const T* pend1 = buf1 + len;
    02493     do
    02494     {
    02495         T w1 = *buf1++;
    02496         T w2 = *buf2++;
    02497         T diff = w1 ^ w2;
    02498
    02499         if (diff)
    02500         {
    02501             return (w1 & diff & -diff) ? 1 : -1;
    02502         }
    02503
    02504     } while (buf1 < pend1);
    02505
    02506     return 0;
    02507 }
    02508
    02509
    02510 /*!
    02511    \brief Converts bit block to GAP.
    02512    \param dest - Destinatio GAP buffer.
    02513    \param src - Source bitblock buffer.
    02514    \param bits - Number of bits to convert.
    02515    \param dest_len - length of the dest. buffer.
    02516    \return  New length of GAP block or 0 if conversion failed
    02517    (insufficicent space).
    02518
    02519    @ingroup gapfunc
    02520 */
    02521 template<typename T>
    02522     unsigned bit_convert_to_gap(T* BMRESTRICT dest,
    02523                                 const unsigned* BMRESTRICT src,
    02524                                 bm::id_t bits,
    02525                                 unsigned dest_len)
    02526 {
    02527     register T* BMRESTRICT pcurr = dest;
    02528     T* BMRESTRICT end = dest + dest_len;
    02529     register int bitval = (*src) & 1;
    02530 //    *pcurr |= bitval;
    02531     *pcurr = (T)bitval;
    02532
    02533     ++pcurr;
    02534     *pcurr = 0;
    02535     register unsigned bit_idx = 0;
    02536     register int bitval_next;
    02537
    02538     unsigned val = *src;
    02539
    02540     do
    02541     {
    02542         // We can fast pace if *src == 0 or *src = 0xffffffff
    02543
    02544         while (val == 0 || val == 0xffffffff)
    02545         {
    02546            bitval_next = val ? 1 : 0;
    02547            if (bitval != bitval_next)
    02548            {
    02549                *pcurr++ = (T)(bit_idx-1);
    02550                BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
    02551                if (pcurr >= end)
    02552                {
    02553                    return 0; // OUT of memory
    02554                }
    02555                bitval = bitval_next;
    02556            }
    02557            bit_idx += sizeof(*src) * 8;
    02558            if (bit_idx >= bits)
    02559            {
    02560                goto complete;
    02561            }
    02562            ++src;
    02563            val = *src;
    02564         }
    02565
    02566
    02567         register unsigned mask = 1;
    02568         while (mask)
    02569         {
    02570             // Now plain bitshifting. TODO: Optimization wanted.
    02571
    02572             bitval_next = val & mask ? 1 : 0;
    02573             if (bitval != bitval_next)
    02574             {
    02575                 *pcurr++ = (T)(bit_idx-1);
    02576                 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
    02577                 bitval = bitval_next;
    02578                 if (pcurr >= end)
    02579                 {
    02580                     return 0; // OUT of memory
    02581                 }
    02582             }
    02583
    02584             mask <<= 1;
    02585             ++bit_idx;
    02586
    02587         } // while mask
    02588
    02589         if (bit_idx >= bits)
    02590         {
    02591             goto complete;
    02592         }
    02593
    02594         ++src;
    02595         val = *src;
    02596
    02597     } while(1);
    02598
    02599 complete:
    02600     *pcurr = (T)(bit_idx-1);
    02601     unsigned len = (unsigned)(pcurr - dest);
    02602     *dest = (T)((*dest & 7) + (len << 3));
    02603     return len;
    02604 }
    02605
    02606
    02607 /*!
    02608    \brief Iterate gap block as delta-bits with a functor
    02609    @ingroup gapfunc
    02610 */
    02611 template<class T, class F>
    02612 void for_each_gap_dbit(const T* buf, F& func)
    02613 {
    02614     const T* pcurr = buf;
    02615     const T* pend = pcurr + (*pcurr >> 3);
    02616
    02617     ++pcurr;
    02618
    02619     unsigned prev = 0;
    02620     unsigned first_inc;
    02621
    02622     if (*buf & 1)
    02623     {
    02624         first_inc = 0;
    02625         unsigned to = *pcurr;
    02626         for (unsigned i = 0; i <= to; ++i)
    02627         {
    02628             func(1);
    02629         }
    02630         prev = to;
    02631         ++pcurr;
    02632     }
    02633     else
    02634     {
    02635         first_inc = 1;
    02636     }
    02637     ++pcurr;  // set GAP to 1
    02638
    02639     while (pcurr <= pend)
    02640     {
    02641         unsigned from = *(pcurr-1)+1;
    02642         unsigned to = *pcurr;
    02643         if (first_inc)
    02644         {
    02645             func(from - prev + first_inc);
    02646             first_inc = 0;
    02647         }
    02648         else
    02649         {
    02650             func(from - prev);
    02651         }
    02652
    02653         for (unsigned i = from+1; i <= to; ++i)
    02654         {
    02655             func(1);
    02656         }
    02657         prev = to;
    02658         pcurr += 2; // jump to the next positive GAP
    02659     }
    02660 }
    02661
    02662 /*!
    02663    \brief Convert gap block into array of ints corresponding to 1 bits
    02664    @ingroup gapfunc
    02665 */
    02666 template<typename D, typename T>
    02667 D gap_convert_to_arr(D* BMRESTRICT       dest,
    02668                      const T* BMRESTRICT buf,
    02669                      unsigned            dest_len,
    02670                      bool                invert = false)
    02671 {
    02672     register const T* BMRESTRICT pcurr = buf;
    02673     register const T* pend = pcurr + (*pcurr >> 3);
    02674
    02675     D* BMRESTRICT dest_curr = dest;
    02676     ++pcurr;
    02677
    02678     int bitval = (*buf) & 1;
    02679     if (invert)
    02680         bitval = !bitval; // invert the GAP buffer
    02681
    02682     if (bitval)
    02683     {
    02684         if (unsigned(*pcurr + 1) >= dest_len)
    02685             return 0; // insufficient space
    02686         dest_len -= *pcurr;
    02687         T to = *pcurr;
    02688         for (T i = 0; ;++i)
    02689         {
    02690             *dest_curr++ = i;
    02691             if (i == to) break;
    02692         }
    02693         ++pcurr;
    02694     }
    02695     ++pcurr;  // set GAP to 1
    02696
    02697     while (pcurr <= pend)
    02698     {
    02699         unsigned pending = *pcurr - *(pcurr-1);
    02700         if (pending >= dest_len)
    02701             return 0;
    02702         dest_len -= pending;
    02703         T from = *(pcurr-1)+1;
    02704         T to = *pcurr;
    02705         for (T i = from; ;++i)
    02706         {
    02707             *dest_curr++ = i;
    02708             if (i == to) break;
    02709         }
    02710         pcurr += 2; // jump to the next positive GAP
    02711     }
    02712     return (D) (dest_curr - dest);
    02713 }
    02714
    02715
    02716
    02717 /*!
    02718     @brief Bitcount for bit string
    02719
    02720     Function calculates number of 1 bits in the given array of words.
    02721     Make sure the addresses are aligned.
    02722
    02723     @ingroup bitfunc
    02724 */
    02725 inline
    02726 bm::id_t bit_block_calc_count(const bm::word_t* block,
    02727                               const bm::word_t* block_end)
    02728 {
    02729     BM_ASSERT(block < block_end);
    02730     bm::id_t count = 0;
    02731
    02732 #ifdef BMVECTOPT
    02733     count = VECT_BITCOUNT(block, block_end);
    02734 #else
    02735 #ifdef BM64OPT
    02736     // 64-bit optimized algorithm. No sparse vect opt.
    02737     // instead it uses 4-way parallel pipelined version
    02738
    02739     const bm::id64_t* b1 = (bm::id64_t*) block;
    02740     const bm::id64_t* b2 = (bm::id64_t*) block_end;
    02741     do
    02742     {
    02743         count += bitcount64_4way(b1[0], b1[1], b1[2], b1[3]);
    02744         b1 += 4;
    02745     } while (b1 < b2);
    02746 #else
    02747     // For 32 bit code the fastest method is
    02748     // to use bitcount table for each byte in the block.
    02749     // As optimization for sparse bitsets used bits accumulator
    02750     // to collect ON bits using bitwise OR.
    02751     bm::word_t  acc = *block++;
    02752     do
    02753     {
    02754         bm::word_t in = *block++;
    02755         bm::word_t acc_prev = acc;
    02756         acc |= in;
    02757         if (acc_prev &= in)  // accumulator miss: counting bits
    02758         {
    02759             BM_INCWORD_BITCOUNT(count, acc);
    02760             acc = acc_prev;
    02761         }
    02762     } while (block < block_end);
    02763
    02764     BM_INCWORD_BITCOUNT(count, acc); // count-in remaining accumulator
    02765
    02766 #endif
    02767 #endif
    02768     return count;
    02769 }
    02770
    02771
    02772
    02773 /*!
    02774     Function calculates number of times when bit value changed
    02775     (1-0 or 0-1).
    02776
    02777     For 001 result is 2
    02778         010 - 3
    02779         011 - 2
    02780         111 - 1
    02781
    02782     @ingroup bitfunc
    02783 */
    02784
    02785 inline
    02786 bm::id_t bit_count_change(bm::word_t w)
    02787 {
    02788     unsigned count = 1;
    02789     w ^= (w >> 1);
    02790
    02791     BM_INCWORD_BITCOUNT(count, w);
    02792     count -= (w >> ((sizeof(w) * 8) - 1));
    02793     return count;
    02794 }
    02795
    02796
    02797 /*!
    02798     Function calculates number of times when bit value changed
    02799     @internal
    02800 */
    02801 inline
    02802 void bit_count_change32(const bm::word_t* block,
    02803                         const bm::word_t* block_end,
    02804                         unsigned*         bit_count,
    02805                         unsigned*         gap_count)
    02806 {
    02807     BM_ASSERT(block < block_end);
    02808     BM_ASSERT(bit_count);
    02809     BM_ASSERT(gap_count);
    02810
    02811     *gap_count = 1;
    02812     *bit_count = 0;
    02813
    02814     bm::word_t  w, w0, w_prev, w_l;
    02815     w = w0 = *block;
    02816
    02817     BM_INCWORD_BITCOUNT(*bit_count, w);
    02818
    02819     const int w_shift = sizeof(w) * 8 - 1;
    02820     w ^= (w >> 1);
    02821     BM_INCWORD_BITCOUNT(*gap_count, w);
    02822     *gap_count -= (w_prev = (w0 >> w_shift)); // negative value correction
    02823
    02824     for (++block ;block < block_end; ++block)
    02825     {
    02826         w = w0 = *block;
    02827         ++(*gap_count);
    02828
    02829         if (!w)
    02830         {
    02831             *gap_count -= !w_prev;
    02832             w_prev = 0;
    02833         }
    02834         else
    02835         {
    02836             BM_INCWORD_BITCOUNT(*bit_count, w);
    02837
    02838             w ^= (w >> 1);
    02839             BM_INCWORD_BITCOUNT(*gap_count, w);
    02840
    02841             w_l = w0 & 1;
    02842             *gap_count -= (w0 >> w_shift);  // negative value correction
    02843             *gap_count -= !(w_prev ^ w_l);  // word border correction
    02844
    02845             w_prev = (w0 >> w_shift);
    02846         }
    02847     } // for
    02848
    02849 }
    02850
    02851
    02852 /*!
    02853     Function calculates number of times when bit value changed
    02854     (1-0 or 0-1) in the bit block.
    02855     Also calulates number of bits ON.
    02856
    02857     @param bit_count - OUT total number of bits ON
    02858
    02859     @return number of 1-0, 0-1 transitions
    02860
    02861     @ingroup bitfunc
    02862 */
    02863 inline
    02864 bm::id_t bit_block_calc_count_change(const bm::word_t* block,
    02865                                      const bm::word_t* block_end,
    02866                                      unsigned*         bit_count)
    02867 {
    02868 #if defined(BMSSE2OPT) || defined(BMSSE42OPT)
    02869
    02870 #ifdef BMSSE42OPT
    02871     return sse4_bit_block_calc_count_change(
    02872         (const __m128i*)block, (const __m128i*)block_end, bit_count);
    02873 #else
    02874 # ifdef BMSSE2OPT
    02875     return sse2_bit_block_calc_count_change(
    02876         (const __m128i*)block, (const __m128i*)block_end, bit_count);
    02877 # endif
    02878 #endif
    02879
    02880 #else // non-SSE code
    02881
    02882     BM_ASSERT(block < block_end);
    02883     BM_ASSERT(bit_count);
    02884
    02885
    02886 #ifdef BM64OPT
    02887     bm::id_t count = 1;
    02888     *bit_count = 0;
    02889
    02890     // 64-bit optimized algorithm.
    02891
    02892     const bm::id64_t* b1 = (bm::id64_t*) block;
    02893     const bm::id64_t* b2 = (bm::id64_t*) block_end;
    02894
    02895     bm::id64_t w, w0, w_prev, w_l;
    02896     w = w0 = *b1;
    02897
    02898     *bit_count = word_bitcount64(w);
    02899
    02900     const int w_shift = sizeof(w) * 8 - 1;
    02901     w ^= (w >> 1);
    02902     count += word_bitcount64(w);
    02903     count -= (w_prev = (w0 >> w_shift)); // negative value correction
    02904
    02905
    02906     for (++b1 ;b1 < b2; ++b1)
    02907     {
    02908         w = w0 = *b1;
    02909
    02910         ++count;
    02911
    02912         if (!w)
    02913         {
    02914             count -= !w_prev;
    02915             w_prev = 0;
    02916         }
    02917         else
    02918         {
    02919             *bit_count += word_bitcount64(w);
    02920             w ^= (w >> 1);
    02921             count += word_bitcount64(w);
    02922
    02923             w_l = w0 & 1;
    02924             count -= (w0 >> w_shift);  // negative value correction
    02925             count -= !(w_prev ^ w_l);  // word border correction
    02926
    02927             w_prev = (w0 >> w_shift);
    02928         }
    02929     } // for
    02930     return count;
    02931
    02932 #else
    02933     unsigned gap_count;
    02934     bit_count_change32(block, block_end, bit_count, &gap_count);
    02935     return gap_count;
    02936 #endif
    02937
    02938 #endif
    02939 }
    02940
    02941
    02942 /*!
    02943     Function calculates number of 1 bits in the given array of words in
    02944     the range between left anf right bits (borders included)
    02945     Make sure the addresses are aligned.
    02946
    02947     @ingroup bitfunc
    02948 */
    02949 inline
    02950 bm::id_t bit_block_calc_count_range(const bm::word_t* block,
    02951                                     bm::word_t left,
    02952                                     bm::word_t right)
    02953 {
    02954     BM_ASSERT(left <= right);
    02955     unsigned nword, nbit;
    02956     nbit = left & bm::set_word_mask;
    02957     const bm::word_t* word =
    02958         block + (nword = unsigned(left >> bm::set_word_shift));
    02959     if (left == right)  // special case (only 1 bit to check)
    02960     {
    02961         return (*word >> nbit) & 1;
    02962     }
    02963     bm::id_t count = 0;
    02964
    02965     unsigned acc;
    02966     unsigned bitcount = right - left + 1;
    02967
    02968     if (nbit) // starting position is not aligned
    02969     {
    02970         unsigned right_margin = nbit + (right - left);
    02971
    02972         if (right_margin < 32)
    02973         {
    02974             unsigned mask =
    02975                 block_set_table<true>::_right[nbit] &
    02976                 block_set_table<true>::_left[right_margin];
    02977             acc = *word & mask;
    02978
    02979             BM_INCWORD_BITCOUNT(count, acc);
    02980             return count;
    02981         }
    02982         else
    02983         {
    02984             acc = *word & block_set_table<true>::_right[nbit];
    02985             BM_INCWORD_BITCOUNT(count, acc);
    02986             bitcount -= 32 - nbit;
    02987         }
    02988         ++word;
    02989     }
    02990
    02991     // now when we are word aligned, we can count bits the usual way
    02992     for ( ;bitcount >= 32; bitcount -= 32)
    02993     {
    02994         acc = *word++;
    02995         BM_INCWORD_BITCOUNT(count, acc);
    02996     }
    02997
    02998     if (bitcount)  // we have a tail to count
    02999     {
    03000         acc = (*word) & block_set_table<true>::_left[bitcount-1];
    03001         BM_INCWORD_BITCOUNT(count, acc);
    03002     }
    03003
    03004     return count;
    03005 }
    03006
    03007
    03008 /*!
    03009     Function calculates if there is any number of 1 bits
    03010     in the given array of words in the range between left anf right bits
    03011     (borders included). Make sure the addresses are aligned.
    03012
    03013     @ingroup bitfunc
    03014 */
    03015 inline
    03016 bm::id_t bit_block_any_range(const bm::word_t* block,
    03017                              bm::word_t left,
    03018                              bm::word_t right)
    03019 {
    03020     BM_ASSERT(left <= right);
    03021
    03022     unsigned nbit  = left; // unsigned(left & bm::set_block_mask);
    03023     unsigned nword = unsigned(nbit >> bm::set_word_shift);
    03024     nbit &= bm::set_word_mask;
    03025
    03026     const bm::word_t* word = block + nword;
    03027
    03028     if (left == right)  // special case (only 1 bit to check)
    03029     {
    03030         return (*word >> nbit) & 1;
    03031     }
    03032     unsigned acc;
    03033     unsigned bitcount = right - left + 1;
    03034
    03035     if (nbit) // starting position is not aligned
    03036     {
    03037         unsigned right_margin = nbit + (right - left);
    03038         if (right_margin < 32)
    03039         {
    03040             unsigned mask =
    03041                 block_set_table<true>::_right[nbit] &
    03042                 block_set_table<true>::_left[right_margin];
    03043             acc = *word & mask;
    03044             return acc;
    03045         }
    03046         else
    03047         {
    03048             acc = *word & block_set_table<true>::_right[nbit];
    03049             if (acc)
    03050                 return acc;
    03051             bitcount -= 32 - nbit;
    03052         }
    03053         ++word;
    03054     }
    03055
    03056     // now when we are word aligned, we can check bits the usual way
    03057     for ( ;bitcount >= 32; bitcount -= 32)
    03058     {
    03059         acc = *word++;
    03060         if (acc)
    03061             return acc;
    03062     }
    03063
    03064     if (bitcount)  // we have a tail to count
    03065     {
    03066         acc = (*word) & block_set_table<true>::_left[bitcount-1];
    03067         if (acc)
    03068             return acc;
    03069     }
    03070
    03071     return 0;
    03072 }
    03073
    03074
    03075
    03076 // ----------------------------------------------------------------------
    03077
    03078 /*! Function inverts block of bits
    03079     @ingroup bitfunc
    03080 */
    03081 template<typename T> void bit_invert(T* start, T* end)
    03082 {
    03083 #ifdef BMVECTOPT
    03084     VECT_INVERT_ARR(start, end);
    03085 #else
    03086     do
    03087     {
    03088         start[0] = ~start[0];
    03089         start[1] = ~start[1];
    03090         start[2] = ~start[2];
    03091         start[3] = ~start[3];
    03092         start+=4;
    03093     } while (start < end);
    03094 #endif
    03095 }
    03096
    03097 // ----------------------------------------------------------------------
    03098
    03099 /*! @brief Returns "true" if all bits in the block are 1
    03100     @ingroup bitfunc
    03101 */
    03102 inline bool is_bits_one(const bm::wordop_t* start,
    03103                         const bm::wordop_t* end)
    03104 {
    03105    do
    03106    {
    03107         bm::wordop_t tmp =
    03108             start[0] & start[1] & start[2] & start[3];
    03109         if (tmp != bm::all_bits_mask)
    03110             return false;
    03111         start += 4;
    03112    } while (start < end);
    03113
    03114    return true;
    03115 }
    03116
    03117 // ----------------------------------------------------------------------
    03118
    03119
    03120 /*! @brief Returns "true" if all bits in the block are 0
    03121     @ingroup bitfunc
    03122 */
    03123 inline bool bit_is_all_zero(const bm::wordop_t* start,
    03124                             const bm::wordop_t* end)
    03125 {
    03126    do
    03127    {
    03128         bm::wordop_t tmp =
    03129             start[0] | start[1] | start[2] | start[3];
    03130        if (tmp)
    03131            return false;
    03132        start += 4;
    03133    } while (start < end);
    03134
    03135    return true;
    03136 }
    03137
    03138 // ----------------------------------------------------------------------
    03139
    03140 // GAP blocks manipulation functions:
    03141
    03142 /*! \brief GAP and functor */
    03143 BMFORCEINLINE unsigned and_op(unsigned v1, unsigned v2)
    03144 {
    03145     return v1 & v2;
    03146 }
    03147
    03148
    03149 /*! \brief GAP xor functor */
    03150 BMFORCEINLINE unsigned xor_op(unsigned v1, unsigned v2)
    03151 {
    03152     return v1 ^ v2;
    03153 }
    03154
    03155
    03156 /*! \brief GAP or functor */
    03157 BMFORCEINLINE unsigned or_op(unsigned v1, unsigned v2)
    03158 {
    03159     return v1 | v2;
    03160 }
    03161
    03162 /*! \brief GAP or functor */
    03163 BMFORCEINLINE unsigned sub_op(unsigned v1, unsigned v2)
    03164 {
    03165     return v1 & ~v2;
    03166 }
    03167
    03168
    03169 /*!
    03170    \brief GAP AND operation.
    03171
    03172    Function performs AND logical operation on gap vectors.
    03173    If possible function put the result into vect1 and returns this
    03174    pointer.  Otherwise result is put into tmp_buf, which should be
    03175    twice of the vector size.
    03176
    03177    \param vect1   - operand 1
    03178    \param vect2   - operand 2
    03179    \param tmp_buf - pointer on temporary buffer
    03180    \param dsize   - out size of the destination
    03181    \return Result pointer (tmp_buf OR vect1)
    03182
    03183    @ingroup gapfunc
    03184 */
    03185 BMFORCEINLINE
    03186 gap_word_t* gap_operation_and(const gap_word_t* BMRESTRICT vect1,
    03187                               const gap_word_t* BMRESTRICT vect2,
    03188                               gap_word_t*       BMRESTRICT tmp_buf,
    03189                               unsigned&         dsize)
    03190 {
    03191     gap_buff_op(tmp_buf, vect1, 0, vect2, 0, and_op, dsize);
    03192     return tmp_buf;
    03193 }
    03194
    03195 /*!
    03196    \brief GAP AND operation test.
    03197
    03198    Function performs AND logical operation on gap vectors.
    03199    If possible function put the result into vect1 and returns this
    03200    pointer.  Otherwise result is put into tmp_buf, which should be
    03201    twice of the vector size.
    03202
    03203    \param vect1   - operand 1
    03204    \param vect2   - operand 2
    03205    \return non zero value if operation returns any 1 bit
    03206
    03207    @ingroup gapfunc
    03208 */
    03209 BMFORCEINLINE
    03210 unsigned gap_operation_any_and(const gap_word_t* BMRESTRICT vect1,
    03211                                       const gap_word_t* BMRESTRICT vect2)
    03212 {
    03213     return gap_buff_any_op(vect1, 0, vect2, 0, and_op);
    03214 }
    03215
    03216
    03217 /*!
    03218    \brief GAP bitcount AND operation test.
    03219
    03220    \param vect1   - operand 1
    03221    \param vect2   - operand 2
    03222    \return bitcount of vect1 AND vect2
    03223
    03224    @ingroup gapfunc
    03225 */
    03226 BMFORCEINLINE
    03227 unsigned gap_count_and(const gap_word_t* BMRESTRICT vect1,
    03228                        const gap_word_t* BMRESTRICT vect2)
    03229 {
    03230     return gap_buff_count_op(vect1, vect2, and_op);
    03231 }
    03232
    03233
    03234
    03235 /*!
    03236    \brief GAP XOR operation.
    03237
    03238    Function performs XOR logical operation on gap vectors.
    03239    If possible function put the result into vect1 and returns this
    03240    pointer.  Otherwise result is put into tmp_buf, which should be
    03241    twice of the vector size.
    03242
    03243    \param vect1   - operand 1
    03244    \param vect2   - operand 2
    03245    \param tmp_buf - pointer on temporary buffer
    03246    \param dsize   - out destination size
    03247    \return Result pointer (tmp_buf)
    03248
    03249    @ingroup gapfunc
    03250 */
    03251 BMFORCEINLINE
    03252 gap_word_t* gap_operation_xor(const gap_word_t*  BMRESTRICT vect1,
    03253                               const gap_word_t*  BMRESTRICT vect2,
    03254                               gap_word_t*        BMRESTRICT tmp_buf,
    03255                               unsigned&                     dsize)
    03256 {
    03257     gap_buff_op(tmp_buf, vect1, 0, vect2, 0, bm::xor_op, dsize);
    03258     return tmp_buf;
    03259 }
    03260
    03261
    03262 /*!
    03263    \brief GAP XOR operation test.
    03264
    03265    Function performs AND logical operation on gap vectors.
    03266    If possible function put the result into vect1 and returns this
    03267    pointer.  Otherwise result is put into tmp_buf, which should be
    03268    twice of the vector size.
    03269
    03270    \param vect1   - operand 1
    03271    \param vect2   - operand 2
    03272    \return non zero value if operation returns any 1 bit
    03273
    03274    @ingroup gapfunc
    03275 */
    03276 BMFORCEINLINE
    03277 unsigned gap_operation_any_xor(const gap_word_t* BMRESTRICT vect1,
    03278                                const gap_word_t* BMRESTRICT vect2)
    03279 {
    03280     return gap_buff_any_op(vect1, 0, vect2, 0, bm::xor_op);
    03281 }
    03282
    03283 /*!
    03284    \brief GAP bitcount XOR operation test.
    03285
    03286    \param vect1   - operand 1
    03287    \param vect2   - operand 2
    03288    \return bitcount of vect1 XOR vect2
    03289
    03290    @ingroup gapfunc
    03291 */
    03292 BMFORCEINLINE
    03293 unsigned gap_count_xor(const gap_word_t* BMRESTRICT vect1,
    03294                        const gap_word_t* BMRESTRICT vect2)
    03295 {
    03296     return gap_buff_count_op(vect1, vect2, bm::xor_op);
    03297 }
    03298
    03299
    03300 /*!
    03301    \brief GAP OR operation.
    03302
    03303    Function performs OR logical oparation on gap vectors.
    03304    If possible function put the result into vect1 and returns this
    03305    pointer.  Otherwise result is put into tmp_buf, which should be
    03306    twice of the vector size.
    03307
    03308    \param vect1   - operand 1
    03309    \param vect2   - operand 2
    03310    \param tmp_buf - pointer on temporary buffer
    03311    \param dsize   - out destination size
    03312
    03313    \return Result pointer (tmp_buf)
    03314
    03315    @ingroup gapfunc
    03316 */
    03317 inline
    03318 gap_word_t* gap_operation_or(const gap_word_t*  BMRESTRICT vect1,
    03319                              const gap_word_t*  BMRESTRICT vect2,
    03320                              gap_word_t*        BMRESTRICT tmp_buf,
    03321                              unsigned&                     dsize)
    03322 {
    03323     gap_buff_op(tmp_buf, vect1, 1, vect2, 1, bm::and_op, dsize);
    03324     gap_invert(tmp_buf);
    03325     return tmp_buf;
    03326 }
    03327
    03328 /*!
    03329    \brief GAP bitcount OR operation test.
    03330
    03331    \param vect1   - operand 1
    03332    \param vect2   - operand 2
    03333    \return bitcount of vect1 OR vect2
    03334
    03335    @ingroup gapfunc
    03336 */
    03337 BMFORCEINLINE
    03338 unsigned gap_count_or(const gap_word_t* BMRESTRICT vect1,
    03339                       const gap_word_t* BMRESTRICT vect2)
    03340 {
    03341     return gap_buff_count_op(vect1, vect2, bm::or_op);
    03342 }
    03343
    03344
    03345
    03346 /*!
    03347    \brief GAP SUB (AND NOT) operation.
    03348
    03349    Function performs SUB logical operation on gap vectors.
    03350    If possible function put the result into vect1 and returns this
    03351    pointer.  Otherwise result is put into tmp_buf, which should be
    03352    twice of the vector size.
    03353
    03354    \param vect1   - operand 1
    03355    \param vect2   - operand 2
    03356    \param tmp_buf - pointer on temporary buffer
    03357    \param dsize   - out destination size
    03358
    03359    \return Result pointer (tmp_buf)
    03360
    03361    @ingroup gapfunc
    03362 */
    03363 inline gap_word_t* gap_operation_sub(const gap_word_t*  BMRESTRICT vect1,
    03364                                      const gap_word_t*  BMRESTRICT vect2,
    03365                                      gap_word_t*        BMRESTRICT tmp_buf,
    03366                                      unsigned&                     dsize)
    03367 {
    03368     gap_buff_op(tmp_buf, vect1, 0, vect2, 1, and_op, dsize);
    03369     return tmp_buf;
    03370 }
    03371
    03372
    03373 /*!
    03374    \brief GAP SUB operation test.
    03375
    03376    Function performs AND logical operation on gap vectors.
    03377    If possible function put the result into vect1 and returns this
    03378    pointer.  Otherwise result is put into tmp_buf, which should be
    03379    twice of the vector size.
    03380
    03381    \param vect1   - operand 1
    03382    \param vect2   - operand 2
    03383    \return non zero value if operation returns any 1 bit
    03384
    03385    @ingroup gapfunc
    03386 */
    03387 BMFORCEINLINE
    03388 unsigned gap_operation_any_sub(const gap_word_t* BMRESTRICT vect1,
    03389                                const gap_word_t* BMRESTRICT vect2)
    03390 {
    03391     return gap_buff_any_op(vect1, 0, vect2, 1, bm::and_op);
    03392 }
    03393
    03394
    03395 /*!
    03396 \brief GAP bitcount SUB (AND NOT) operation test.
    03397
    03398 \param vect1   - operand 1
    03399 \param vect2   - operand 2
    03400 \return bitcount of vect1 SUB (AND NOT) vect2
    03401
    03402 @ingroup gapfunc
    03403 */
    03404 BMFORCEINLINE
    03405 unsigned gap_count_sub(const gap_word_t* BMRESTRICT vect1,
    03406                        const gap_word_t* BMRESTRICT vect2)
    03407 {
    03408     return gap_buff_count_op(vect1, vect2, bm::sub_op);
    03409 }
    03410
    03411
    03412 // ----------------------------------------------------------------------
    03413
    03414 // BIT blocks manipulation functions:
    03415
    03416
    03417 /*!
    03418    \brief Bitblock copy operation.
    03419
    03420    \param dst - destination block.
    03421    \param src - source block.
    03422
    03423    @ingroup bitfunc
    03424 */
    03425 inline
    03426 void bit_block_copy(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
    03427 {
    03428 #ifdef BMVECTOPT
    03429     VECT_COPY_BLOCK(dst, src, src + bm::set_block_size);
    03430 #else
    03431     ::memcpy(dst, src, bm::set_block_size * sizeof(bm::word_t));
    03432 #endif
    03433 }
    03434
    03435
    03436 /*!
    03437    \brief Plain bitblock AND operation.
    03438    Function does not analyse availability of source and destination blocks.
    03439
    03440    \param dst - destination block.
    03441    \param src - source block.
    03442
    03443    @ingroup bitfunc
    03444 */
    03445 inline
    03446 void bit_block_and(bm::word_t* BMRESTRICT dst, const bm::word_t* BMRESTRICT src)
    03447 {
    03448 #ifdef BMVECTOPT
    03449     VECT_AND_ARR(dst, src, src + bm::set_block_size);
    03450 #else
    03451     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
    03452     const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + bm::set_block_size);
    03453     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
    03454
    03455     do
    03456     {
    03457         dst_ptr[0] &= wrd_ptr[0];
    03458         dst_ptr[1] &= wrd_ptr[1];
    03459         dst_ptr[2] &= wrd_ptr[2];
    03460         dst_ptr[3] &= wrd_ptr[3];
    03461
    03462         dst_ptr+=4;
    03463         wrd_ptr+=4;
    03464     } while (wrd_ptr < wrd_end);
    03465 #endif
    03466 }
    03467
    03468
    03469 /*!
    03470    \brief Function ANDs two bitblocks and computes the bitcount.
    03471    Function does not analyse availability of source blocks.
    03472
    03473    \param src1     - first bit block
    03474    \param src1_end - first bit block end
    03475    \param src2     - second bit block
    03476
    03477    @ingroup bitfunc
    03478 */
    03479 inline
    03480 unsigned bit_block_and_count(const bm::word_t* src1,
    03481                              const bm::word_t* src1_end,
    03482                              const bm::word_t* src2)
    03483 {
    03484     unsigned count;
    03485 #ifdef BMVECTOPT
    03486     count = VECT_BITCOUNT_AND(src1, src1_end, src2);
    03487 #else
    03488     count = 0;
    03489 # ifdef BM64OPT
    03490     const bm::id64_t* b1 = (bm::id64_t*) src1;
    03491     const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
    03492     const bm::id64_t* b2 = (bm::id64_t*) src2;
    03493     do
    03494     {
    03495         count += bitcount64_4way(b1[0] & b2[0],
    03496                                  b1[1] & b2[1],
    03497                                  b1[2] & b2[2],
    03498                                  b1[3] & b2[3]);
    03499         b1 += 4;
    03500         b2 += 4;
    03501     } while (b1 < b1_end);
    03502 # else
    03503     do
    03504     {
    03505         BM_INCWORD_BITCOUNT(count, src1[0] & src2[0]);
    03506         BM_INCWORD_BITCOUNT(count, src1[1] & src2[1]);
    03507         BM_INCWORD_BITCOUNT(count, src1[2] & src2[2]);
    03508         BM_INCWORD_BITCOUNT(count, src1[3] & src2[3]);
    03509
    03510         src1+=4;
    03511         src2+=4;
    03512     } while (src1 < src1_end);
    03513 # endif
    03514 #endif
    03515     return count;
    03516 }
    03517
    03518
    03519 /*!
    03520    \brief Function ANDs two bitblocks and tests for any bit.
    03521    Function does not analyse availability of source blocks.
    03522
    03523    \param src1     - first bit block
    03524    \param src1_end - first bit block end
    03525    \param src2     - second bit block
    03526
    03527    @ingroup bitfunc
    03528 */
    03529 inline
    03530 unsigned bit_block_and_any(const bm::word_t* src1,
    03531                            const bm::word_t* src1_end,
    03532                            const bm::word_t* src2)
    03533 {
    03534     unsigned count = 0;
    03535     do
    03536     {
    03537         count = (src1[0] & src2[0]) |
    03538                 (src1[1] & src2[1]) |
    03539                 (src1[2] & src2[2]) |
    03540                 (src1[3] & src2[3]);
    03541
    03542         src1+=4; src2+=4;
    03543     } while ((src1 < src1_end) && (count == 0));
    03544     return count;
    03545 }
    03546
    03547
    03548
    03549
    03550 /*!
    03551    \brief Function XORs two bitblocks and computes the bitcount.
    03552    Function does not analyse availability of source blocks.
    03553
    03554    \param src1     - first bit block.
    03555    \param src1_end - first bit block end
    03556    \param src2     - second bit block.
    03557
    03558    @ingroup bitfunc
    03559 */
    03560 inline
    03561 unsigned bit_block_xor_count(const bm::word_t* BMRESTRICT src1,
    03562                              const bm::word_t* BMRESTRICT src1_end,
    03563                              const bm::word_t* BMRESTRICT src2)
    03564 {
    03565     unsigned count;
    03566 #ifdef BMVECTOPT
    03567     count = VECT_BITCOUNT_XOR(src1, src1_end, src2);
    03568 #else
    03569     count = 0;
    03570 # ifdef BM64OPT
    03571     const bm::id64_t* b1 = (bm::id64_t*) src1;
    03572     const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
    03573     const bm::id64_t* b2 = (bm::id64_t*) src2;
    03574     do
    03575     {
    03576         count += bitcount64_4way(b1[0] ^ b2[0],
    03577                                  b1[1] ^ b2[1],
    03578                                  b1[2] ^ b2[2],
    03579                                  b1[3] ^ b2[3]);
    03580         b1 += 4;
    03581         b2 += 4;
    03582     } while (b1 < b1_end);
    03583 # else
    03584     do
    03585     {
    03586         BM_INCWORD_BITCOUNT(count, src1[0] ^ src2[0]);
    03587         BM_INCWORD_BITCOUNT(count, src1[1] ^ src2[1]);
    03588         BM_INCWORD_BITCOUNT(count, src1[2] ^ src2[2]);
    03589         BM_INCWORD_BITCOUNT(count, src1[3] ^ src2[3]);
    03590
    03591         src1+=4;
    03592         src2+=4;
    03593     } while (src1 < src1_end);
    03594 # endif
    03595 #endif
    03596     return count;
    03597 }
    03598
    03599
    03600 /*!
    03601    \brief Function XORs two bitblocks and and tests for any bit.
    03602    Function does not analyse availability of source blocks.
    03603
    03604    \param src1     - first bit block.
    03605    \param src1_end - first bit block end
    03606    \param src2     - second bit block.
    03607
    03608    @ingroup bitfunc
    03609 */
    03610 inline
    03611 unsigned bit_block_xor_any(const bm::word_t* BMRESTRICT src1,
    03612                              const bm::word_t* BMRESTRICT src1_end,
    03613                              const bm::word_t* BMRESTRICT src2)
    03614 {
    03615     unsigned count = 0;
    03616     do
    03617     {
    03618         count = (src1[0] ^ src2[0]) |
    03619                 (src1[1] ^ src2[1]) |
    03620                 (src1[2] ^ src2[2]) |
    03621                 (src1[3] ^ src2[3]);
    03622
    03623         src1+=4; src2+=4;
    03624     } while ((src1 < src1_end) && (count == 0));
    03625     return count;
    03626 }
    03627
    03628
    03629
    03630
    03631 /*!
    03632    \brief Function SUBs two bitblocks and computes the bitcount.
    03633    Function does not analyse availability of source blocks.
    03634
    03635    \param src1     - first bit block.
    03636    \param src1_end - first bit block end
    03637    \param src2     - second bit block.
    03638
    03639    @ingroup bitfunc
    03640 */
    03641 inline
    03642 unsigned bit_block_sub_count(const bm::word_t* BMRESTRICT src1,
    03643                              const bm::word_t* BMRESTRICT src1_end,
    03644                              const bm::word_t* BMRESTRICT src2)
    03645 {
    03646     unsigned count;
    03647 #ifdef BMVECTOPT
    03648     count = VECT_BITCOUNT_SUB(src1, src1_end, src2);
    03649 #else
    03650     count = 0;
    03651 # ifdef BM64OPT
    03652     const bm::id64_t* b1 = (bm::id64_t*) src1;
    03653     const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
    03654     const bm::id64_t* b2 = (bm::id64_t*) src2;
    03655     do
    03656     {
    03657         count += bitcount64_4way(b1[0] & ~b2[0],
    03658                                  b1[1] & ~b2[1],
    03659                                  b1[2] & ~b2[2],
    03660                                  b1[3] & ~b2[3]);
    03661         b1 += 4;
    03662         b2 += 4;
    03663     } while (b1 < b1_end);
    03664 # else
    03665     do
    03666     {
    03667         BM_INCWORD_BITCOUNT(count, src1[0] & ~src2[0]);
    03668         BM_INCWORD_BITCOUNT(count, src1[1] & ~src2[1]);
    03669         BM_INCWORD_BITCOUNT(count, src1[2] & ~src2[2]);
    03670         BM_INCWORD_BITCOUNT(count, src1[3] & ~src2[3]);
    03671
    03672         src1+=4;
    03673         src2+=4;
    03674     } while (src1 < src1_end);
    03675 # endif
    03676 #endif
    03677     return count;
    03678 }
    03679
    03680 /*!
    03681    \brief Function SUBs two bitblocks and and tests for any bit.
    03682    Function does not analyse availability of source blocks.
    03683
    03684    \param src1     - first bit block.
    03685    \param src1_end - first bit block end
    03686    \param src2     - second bit block.
    03687
    03688    @ingroup bitfunc
    03689 */
    03690 inline
    03691 unsigned bit_block_sub_any(const bm::word_t* BMRESTRICT src1,
    03692                              const bm::word_t* BMRESTRICT src1_end,
    03693                              const bm::word_t* BMRESTRICT src2)
    03694 {
    03695     unsigned count = 0;
    03696     do
    03697     {
    03698         count = (src1[0] & ~src2[0]) |
    03699                 (src1[1] & ~src2[1]) |
    03700                 (src1[2] & ~src2[2]) |
    03701                 (src1[3] & ~src2[3]);
    03702
    03703         src1+=4; src2+=4;
    03704     } while ((src1 < src1_end) && (count == 0));
    03705     return count;
    03706 }
    03707
    03708
    03709
    03710 /*!
    03711    \brief Function ORs two bitblocks and computes the bitcount.
    03712    Function does not analyse availability of source blocks.
    03713
    03714    \param src1     - first bit block
    03715    \param src1_end - first block end
    03716    \param src2     - second bit block.
    03717
    03718    @ingroup bitfunc
    03719 */
    03720 inline
    03721 unsigned bit_block_or_count(const bm::word_t* src1,
    03722                             const bm::word_t* src1_end,
    03723                             const bm::word_t* src2)
    03724 {
    03725     unsigned count;
    03726 #ifdef BMVECTOPT
    03727     count = VECT_BITCOUNT_OR(src1, src1_end, src2);
    03728 #else
    03729     count = 0;
    03730 # ifdef BM64OPT
    03731     const bm::id64_t* b1 = (bm::id64_t*) src1;
    03732     const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
    03733     const bm::id64_t* b2 = (bm::id64_t*) src2;
    03734     do
    03735     {
    03736         count += bitcount64_4way(b1[0] | b2[0],
    03737                                  b1[1] | b2[1],
    03738                                  b1[2] | b2[2],
    03739                                  b1[3] | b2[3]);
    03740         b1 += 4;
    03741         b2 += 4;
    03742     } while (b1 < b1_end);
    03743 # else
    03744     do
    03745     {
    03746         BM_INCWORD_BITCOUNT(count, src1[0] | src2[0]);
    03747         BM_INCWORD_BITCOUNT(count, src1[1] | src2[1]);
    03748         BM_INCWORD_BITCOUNT(count, src1[2] | src2[2]);
    03749         BM_INCWORD_BITCOUNT(count, src1[3] | src2[3]);
    03750
    03751         src1+=4;
    03752         src2+=4;
    03753     } while (src1 < src1_end);
    03754 # endif
    03755 #endif
    03756     return count;
    03757 }
    03758
    03759 /*!
    03760    \brief Function ORs two bitblocks and and tests for any bit.
    03761    Function does not analyse availability of source blocks.
    03762
    03763    \param src1     - first bit block.
    03764    \param src1_end - first bit block end
    03765    \param src2     - second bit block.
    03766
    03767    @ingroup bitfunc
    03768 */
    03769 inline
    03770 unsigned bit_block_or_any(const bm::word_t* BMRESTRICT src1,
    03771                           const bm::word_t* BMRESTRICT src1_end,
    03772                           const bm::word_t* BMRESTRICT src2)
    03773 {
    03774     unsigned count = 0;
    03775     do
    03776     {
    03777         count = (src1[0] | src2[0]) |
    03778                 (src1[1] | src2[1]) |
    03779                 (src1[2] | src2[2]) |
    03780                 (src1[3] | src2[3]);
    03781
    03782         src1+=4; src2+=4;
    03783     } while ((src1 < src1_end) && (count == 0));
    03784     return count;
    03785 }
    03786
    03787
    03788
    03789
    03790 /*!
    03791    \brief bitblock AND operation.
    03792
    03793    \param dst - destination block.
    03794    \param src - source block.
    03795
    03796    \returns pointer on destination block.
    03797     If returned value  equal to src means that block mutation requested.
    03798     NULL is valid return value.
    03799
    03800    @ingroup bitfunc
    03801 */
    03802 inline bm::word_t* bit_operation_and(bm::word_t* BMRESTRICT dst,
    03803                                      const bm::word_t* BMRESTRICT src)
    03804 {
    03805     BM_ASSERT(dst || src);
    03806
    03807     bm::word_t* ret = dst;
    03808
    03809     if (IS_VALID_ADDR(dst))  // The destination block already exists
    03810     {
    03811
    03812         if (!IS_VALID_ADDR(src))
    03813         {
    03814             if (IS_EMPTY_BLOCK(src))
    03815             {
    03816                 //If the source block is zero
    03817                 //just clean the destination block
    03818                 return 0;
    03819             }
    03820         }
    03821         else
    03822         {
    03823             // Regular operation AND on the whole block.
    03824             bit_block_and(dst, src);
    03825         }
    03826     }
    03827     else // The destination block does not exist yet
    03828     {
    03829         if(!IS_VALID_ADDR(src))
    03830         {
    03831             if(IS_EMPTY_BLOCK(src))
    03832             {
    03833                 // The source block is empty.
    03834                 // One argument empty - all result is empty.
    03835                 return 0;
    03836             }
    03837             // Here we have nothing to do.
    03838             // Src block is all ON, dst block remains as it is
    03839         }
    03840         else // destination block does not exists, src - valid block
    03841         {
    03842             if (IS_FULL_BLOCK(dst))
    03843             {
    03844                 return const_cast<bm::word_t*>(src);
    03845             }
    03846             // Nothng to do.
    03847             // Dst block is all ZERO no combination required.
    03848         }
    03849     }
    03850
    03851     return ret;
    03852 }
    03853
    03854
    03855 /*!
    03856    \brief Performs bitblock AND operation and calculates bitcount of the result.
    03857
    03858    \param src1     - first bit block.
    03859    \param src1_end - first bit block end
    03860    \param src2     - second bit block.
    03861
    03862    \returns bitcount value
    03863
    03864    @ingroup bitfunc
    03865 */
    03866 inline
    03867 bm::id_t bit_operation_and_count(const bm::word_t* BMRESTRICT src1,
    03868                                  const bm::word_t* BMRESTRICT src1_end,
    03869                                  const bm::word_t* BMRESTRICT src2)
    03870 {
    03871     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
    03872     {
    03873         return 0;
    03874     }
    03875     return bit_block_and_count(src1, src1_end, src2);
    03876 }
    03877
    03878 /*!
    03879    \brief Performs bitblock AND operation test.
    03880
    03881    \param src1     - first bit block.
    03882    \param src1_end - first bit block end
    03883    \param src2     - second bit block.
    03884
    03885    \returns non zero if there is any value
    03886
    03887    @ingroup bitfunc
    03888 */
    03889 inline
    03890 bm::id_t bit_operation_and_any(const bm::word_t* BMRESTRICT src1,
    03891                                const bm::word_t* BMRESTRICT src1_end,
    03892                                const bm::word_t* BMRESTRICT src2)
    03893 {
    03894     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
    03895     {
    03896         return 0;
    03897     }
    03898     return bit_block_and_any(src1, src1_end, src2);
    03899 }
    03900
    03901
    03902
    03903 /*!
    03904    \brief Performs bitblock SUB operation and calculates bitcount of the result.
    03905
    03906    \param src1      - first bit block.
    03907    \param src1_end  - first bit block end
    03908    \param src2      - second bit block
    03909
    03910    \returns bitcount value
    03911
    03912    @ingroup bitfunc
    03913 */
    03914 inline
    03915 bm::id_t bit_operation_sub_count(const bm::word_t* BMRESTRICT src1,
    03916                                  const bm::word_t* BMRESTRICT src1_end,
    03917                                  const bm::word_t* BMRESTRICT src2)
    03918 {
    03919     if (IS_EMPTY_BLOCK(src1))
    03920     {
    03921         return 0;
    03922     }
    03923
    03924     if (IS_EMPTY_BLOCK(src2)) // nothing to diff
    03925     {
    03926         return bit_block_calc_count(src1, src1_end);
    03927     }
    03928     return bit_block_sub_count(src1, src1_end, src2);
    03929 }
    03930
    03931
    03932 /*!
    03933    \brief Performs inverted bitblock SUB operation and calculates
    03934           bitcount of the result.
    03935
    03936    \param src1      - first bit block.
    03937    \param src1_end  - first bit block end
    03938    \param src2      - second bit block
    03939
    03940    \returns bitcount value
    03941
    03942    @ingroup bitfunc
    03943 */
    03944 inline
    03945 bm::id_t bit_operation_sub_count_inv(const bm::word_t* BMRESTRICT src1,
    03946                                      const bm::word_t* BMRESTRICT src1_end,
    03947                                      const bm::word_t* BMRESTRICT src2)
    03948 {
    03949     unsigned arr_size = unsigned(src1_end - src1);
    03950     return bit_operation_sub_count(src2, src2+arr_size, src1);
    03951 }
    03952
    03953
    03954 /*!
    03955    \brief Performs bitblock test of SUB operation.
    03956
    03957    \param src1      - first bit block.
    03958    \param src1_end  - first bit block end
    03959    \param src2      - second bit block
    03960
    03961    \returns non zero value if there are any bits
    03962
    03963    @ingroup bitfunc
    03964 */
    03965 inline
    03966 bm::id_t bit_operation_sub_any(const bm::word_t* BMRESTRICT src1,
    03967                                const bm::word_t* BMRESTRICT src1_end,
    03968                                const bm::word_t* BMRESTRICT src2)
    03969 {
    03970     if (IS_EMPTY_BLOCK(src1))
    03971     {
    03972         return 0;
    03973     }
    03974
    03975     if (IS_EMPTY_BLOCK(src2)) // nothing to diff
    03976     {
    03977         return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
    03978     }
    03979     return bit_block_sub_any(src1, src1_end, src2);
    03980 }
    03981
    03982
    03983
    03984 /*!
    03985    \brief Performs bitblock OR operation and calculates bitcount of the result.
    03986
    03987    \param src1     - first bit block.
    03988    \param src1_end - first bit block end
    03989    \param src2     - second bit block.
    03990
    03991    \returns bitcount value
    03992
    03993    @ingroup bitfunc
    03994 */
    03995 inline
    03996 bm::id_t bit_operation_or_count(const bm::word_t* BMRESTRICT src1,
    03997                                 const bm::word_t* BMRESTRICT src1_end,
    03998                                 const bm::word_t* BMRESTRICT src2)
    03999 {
    04000     if (IS_EMPTY_BLOCK(src1))
    04001     {
    04002         if (!IS_EMPTY_BLOCK(src2))
    04003             return bit_block_calc_count(src2, src2 + (src1_end - src1));
    04004         else
    04005             return 0; // both blocks are empty
    04006     }
    04007     else
    04008     {
    04009         if (IS_EMPTY_BLOCK(src2))
    04010             return bit_block_calc_count(src1, src1_end);
    04011     }
    04012
    04013     return bit_block_or_count(src1, src1_end, src2);
    04014 }
    04015
    04016 /*!
    04017    \brief Performs bitblock OR operation test.
    04018
    04019    \param src1     - first bit block.
    04020    \param src1_end - first bit block end
    04021    \param src2     - second bit block.
    04022
    04023    \returns non zero value if there are any bits
    04024
    04025    @ingroup bitfunc
    04026 */
    04027 inline
    04028 bm::id_t bit_operation_or_any(const bm::word_t* BMRESTRICT src1,
    04029                               const bm::word_t* BMRESTRICT src1_end,
    04030                               const bm::word_t* BMRESTRICT src2)
    04031 {
    04032     if (IS_EMPTY_BLOCK(src1))
    04033     {
    04034         if (!IS_EMPTY_BLOCK(src2))
    04035             return !bit_is_all_zero((bm::wordop_t*)src2,
    04036                                      (bm::wordop_t*)(src2 + (src1_end - src1)));
    04037         else
    04038             return 0; // both blocks are empty
    04039     }
    04040     else
    04041     {
    04042         if (IS_EMPTY_BLOCK(src2))
    04043             return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
    04044     }
    04045
    04046     return bit_block_or_any(src1, src1_end, src2);
    04047 }
    04048
    04049
    04050
    04051 /*!
    04052    \brief Plain bitblock OR operation.
    04053    Function does not analyse availability of source and destination blocks.
    04054
    04055    \param dst - destination block.
    04056    \param src - source block.
    04057
    04058    @ingroup bitfunc
    04059 */
    04060 inline void bit_block_or(bm::word_t* BMRESTRICT dst,
    04061                          const bm::word_t* BMRESTRICT src)
    04062 {
    04063 #ifdef BMVECTOPT
    04064     VECT_OR_ARR(dst, src, src + bm::set_block_size);
    04065 #else
    04066     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
    04067     const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + set_block_size);
    04068     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
    04069
    04070     do
    04071     {
    04072         dst_ptr[0] |= wrd_ptr[0];
    04073         dst_ptr[1] |= wrd_ptr[1];
    04074         dst_ptr[2] |= wrd_ptr[2];
    04075         dst_ptr[3] |= wrd_ptr[3];
    04076
    04077         dst_ptr+=4;
    04078         wrd_ptr+=4;
    04079
    04080     } while (wrd_ptr < wrd_end);
    04081 #endif
    04082 }
    04083
    04084
    04085 /*!
    04086    \brief Block OR operation. Makes analysis if block is 0 or FULL.
    04087
    04088    \param dst - destination block.
    04089    \param src - source block.
    04090
    04091    \returns pointer on destination block.
    04092     If returned value  equal to src means that block mutation requested.
    04093     NULL is valid return value.
    04094
    04095    @ingroup bitfunc
    04096 */
    04097 inline
    04098 bm::word_t* bit_operation_or(bm::word_t* BMRESTRICT dst,
    04099                              const bm::word_t* BMRESTRICT src)
    04100 {
    04101     BM_ASSERT(dst || src);
    04102
    04103     bm::word_t* ret = dst;
    04104
    04105     if (IS_VALID_ADDR(dst)) // The destination block already exists
    04106     {
    04107         if (!IS_VALID_ADDR(src))
    04108         {
    04109             if (IS_FULL_BLOCK(src))
    04110             {
    04111                 // if the source block is all set
    04112                 // just set the destination block
    04113                 ::memset(dst, 0xFF, bm::set_block_size * sizeof(bm::word_t));
    04114             }
    04115         }
    04116         else
    04117         {
    04118             // Regular operation OR on the whole block
    04119             bit_block_or(dst, src);
    04120         }
    04121     }
    04122     else // The destination block does not exist yet
    04123     {
    04124         if (!IS_VALID_ADDR(src))
    04125         {
    04126             if (IS_FULL_BLOCK(src))
    04127             {
    04128                 // The source block is all set, because dst does not exist
    04129                 // we can simply replace it.
    04130                 return const_cast<bm::word_t*>(FULL_BLOCK_ADDR);
    04131             }
    04132         }
    04133         else
    04134         {
    04135             if (dst == 0)
    04136             {
    04137                 // The only case when we have to allocate the new block:
    04138                 // Src is all zero and Dst does not exist
    04139                 return const_cast<bm::word_t*>(src);
    04140             }
    04141         }
    04142     }
    04143     return ret;
    04144 }
    04145
    04146 /*!
    04147    \brief Plain bitblock SUB (AND NOT) operation.
    04148    Function does not analyse availability of source and destination blocks.
    04149
    04150    \param dst - destination block.
    04151    \param src - source block.
    04152
    04153    @ingroup bitfunc
    04154 */
    04155 inline
    04156 void bit_block_sub(bm::word_t* BMRESTRICT dst,
    04157                    const bm::word_t* BMRESTRICT src)
    04158 {
    04159 #ifdef BMVECTOPT
    04160     VECT_SUB_ARR(dst, src, src + bm::set_block_size);
    04161 #else
    04162     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
    04163     const bm::wordop_t* BMRESTRICT wrd_end =
    04164                      (wordop_t*) (src + bm::set_block_size);
    04165     bm::wordop_t* dst_ptr = (wordop_t*)dst;
    04166
    04167     // Regular operation AND-NOT on the whole block.
    04168     do
    04169     {
    04170         dst_ptr[0] &= ~wrd_ptr[0];
    04171         dst_ptr[1] &= ~wrd_ptr[1];
    04172         dst_ptr[2] &= ~wrd_ptr[2];
    04173         dst_ptr[3] &= ~wrd_ptr[3];
    04174
    04175         dst_ptr+=4;
    04176         wrd_ptr+=4;
    04177     } while (wrd_ptr < wrd_end);
    04178 #endif
    04179
    04180 }
    04181
    04182
    04183 /*!
    04184    \brief bitblock SUB operation.
    04185
    04186    \param dst - destination block.
    04187    \param src - source block.
    04188
    04189    \returns pointer on destination block.
    04190     If returned value  equal to src means that block mutation requested.
    04191     NULL is valid return value.
    04192
    04193    @ingroup bitfunc
    04194 */
    04195 inline
    04196 bm::word_t* bit_operation_sub(bm::word_t* BMRESTRICT dst,
    04197                               const bm::word_t* BMRESTRICT src)
    04198 {
    04199     BM_ASSERT(dst || src);
    04200
    04201     bm::word_t* ret = dst;
    04202     if (IS_VALID_ADDR(dst))  //  The destination block already exists
    04203     {
    04204         if (!IS_VALID_ADDR(src))
    04205         {
    04206             if (IS_FULL_BLOCK(src))
    04207             {
    04208                 // If the source block is all set
    04209                 // just clean the destination block
    04210                 return 0;
    04211             }
    04212         }
    04213         else
    04214         {
    04215             bit_block_sub(dst, src);
    04216         }
    04217     }
    04218     else // The destination block does not exist yet
    04219     {
    04220         if (!IS_VALID_ADDR(src))
    04221         {
    04222             if (IS_FULL_BLOCK(src))
    04223             {
    04224                 // The source block is full
    04225                 return 0;
    04226             }
    04227         }
    04228         else
    04229         {
    04230             if (IS_FULL_BLOCK(dst))
    04231             {
    04232                 // The only case when we have to allocate the new block:
    04233                 // dst is all set and src exists
    04234                 return const_cast<bm::word_t*>(src);
    04235             }
    04236         }
    04237     }
    04238     return ret;
    04239 }
    04240
    04241
    04242 /*!
    04243    \brief Plain bitblock XOR operation.
    04244    Function does not analyse availability of source and destination blocks.
    04245
    04246    \param dst - destination block.
    04247    \param src - source block.
    04248
    04249    @ingroup bitfunc
    04250 */
    04251 inline
    04252 void bit_block_xor(bm::word_t* BMRESTRICT dst,
    04253                    const bm::word_t* BMRESTRICT src)
    04254 {
    04255 #ifdef BMVECTOPT
    04256     VECT_XOR_ARR(dst, src, src + bm::set_block_size);
    04257 #else
    04258     const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
    04259     const bm::wordop_t* BMRESTRICT wrd_end =
    04260                             (wordop_t*) (src + bm::set_block_size);
    04261     bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
    04262
    04263     // Regular XOR operation on the whole block.
    04264     do
    04265     {
    04266         dst_ptr[0] ^= wrd_ptr[0];
    04267         dst_ptr[1] ^= wrd_ptr[1];
    04268         dst_ptr[2] ^= wrd_ptr[2];
    04269         dst_ptr[3] ^= wrd_ptr[3];
    04270
    04271         dst_ptr+=4;
    04272         wrd_ptr+=4;
    04273     } while (wrd_ptr < wrd_end);
    04274 #endif
    04275
    04276 }
    04277
    04278
    04279 /*!
    04280    \brief bitblock XOR operation.
    04281
    04282    \param dst - destination block.
    04283    \param src - source block.
    04284
    04285    \returns pointer on destination block.
    04286     If returned value  equal to src means that block mutation requested.
    04287     NULL is valid return value.
    04288
    04289    @ingroup bitfunc
    04290 */
    04291 inline
    04292 bm::word_t* bit_operation_xor(bm::word_t* BMRESTRICT dst,
    04293                               const bm::word_t* BMRESTRICT src)
    04294 {
    04295     BM_ASSERT(dst || src);
    04296     if (src == dst) return 0;  // XOR rule
    04297
    04298     bm::word_t* ret = dst;
    04299
    04300     if (IS_VALID_ADDR(dst))  //  The destination block already exists
    04301     {
    04302         if (!src) return dst;
    04303
    04304         bit_block_xor(dst, src);
    04305     }
    04306     else // The destination block does not exist yet
    04307     {
    04308         if (!src) return dst;      // 1 xor 0 = 1
    04309
    04310         // Here we have two cases:
    04311         // if dest block is full or zero if zero we need to copy the source
    04312         // otherwise XOR loop against 0xFF...
    04313         //BM_ASSERT(dst == 0);
    04314         return const_cast<bm::word_t*>(src);  // src is the final result
    04315     }
    04316     return ret;
    04317 }
    04318
    04319 /*!
    04320    \brief Performs bitblock XOR operation and calculates bitcount of the result.
    04321
    04322    \param src1 - first bit block.
    04323    \param src2 - second bit block.
    04324
    04325    \returns bitcount value
    04326
    04327    @ingroup bitfunc
    04328 */
    04329 inline
    04330 bm::id_t bit_operation_xor_count(const bm::word_t* BMRESTRICT src1,
    04331                                  const bm::word_t* BMRESTRICT src1_end,
    04332                                  const bm::word_t* BMRESTRICT src2)
    04333 {
    04334     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
    04335     {
    04336         if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
    04337             return 0;
    04338         const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
    04339         return bit_block_calc_count(block, block + (src1_end - src1));
    04340     }
    04341     return bit_block_xor_count(src1, src1_end, src2);
    04342 }
    04343
    04344 /*!
    04345    \brief Performs bitblock XOR operation test.
    04346
    04347    \param src1 - first bit block.
    04348    \param src2 - second bit block.
    04349
    04350    \returns non zero value if there are bits
    04351
    04352    @ingroup bitfunc
    04353 */
    04354 inline
    04355 bm::id_t bit_operation_xor_any(const bm::word_t* BMRESTRICT src1,
    04356                                const bm::word_t* BMRESTRICT src1_end,
    04357                                const bm::word_t* BMRESTRICT src2)
    04358 {
    04359     if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
    04360     {
    04361         if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
    04362             return 0;
    04363         const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
    04364         return !bit_is_all_zero((bm::wordop_t*)block,
    04365                                 (bm::wordop_t*)(block + (src1_end - src1)));
    04366     }
    04367     return bit_block_xor_any(src1, src1_end, src2);
    04368 }
    04369
    04370
    04371
    04372 /**
    04373     \brief Inspects block for full zero words
    04374
    04375     \param data - bit block pointer
    04376     \param data_size - data size
    04377
    04378     \return size of all non-zero words
    04379
    04380     @ingroup bitfunc
    04381 */
    04382
    04383 template<class T>
    04384 unsigned bit_count_nonzero_size(const T*     blk,
    04385                                 unsigned     data_size)
    04386 {
    04387     BM_ASSERT(blk && data_size);
    04388     unsigned count = 0;
    04389     const T* blk_end = blk + data_size - 2;
    04390
    04391     do
    04392     {
    04393         if (*blk == 0)
    04394         {
    04395             // scan fwd to find 0 island length
    04396             const T* blk_j = blk + 1;
    04397             for (; blk_j < blk_end; ++blk_j)
    04398             {
    04399                 if (*blk_j != 0)
    04400                     break;
    04401             }
    04402             blk = blk_j-1;
    04403             count += sizeof(gap_word_t);
    04404         }
    04405         else
    04406         {
    04407             // scan fwd to find non-0 island length
    04408             const T* blk_j = blk + 1;
    04409             for ( ; blk_j < blk_end; ++blk_j)
    04410             {
    04411                 if (*blk_j == 0)
    04412                 {
    04413                     // look ahead to identify and ignore short 0-run
    04414                     if (blk_j[1] | blk_j[2])
    04415                     {
    04416                         // skip zero word
    04417                         ++blk_j;
    04418                         continue;
    04419                     }
    04420                     break;
    04421                 }
    04422             }
    04423             count += sizeof(gap_word_t);
    04424             // count all bit-words now
    04425             count += (blk_j - blk) * sizeof(T);
    04426             blk = blk_j;
    04427         }
    04428         ++blk;
    04429     }
    04430     while(blk < blk_end);
    04431
    04432     return count + (2 * sizeof(T));
    04433 }
    04434
    04435
    04436 /**
    04437     \brief Searches for the next 1 bit in the BIT block
    04438     \param data - BIT buffer
    04439     \param nbit - bit index to start checking from
    04440     \param prev - returns previously checked value
    04441
    04442     @ingroup bitfunc
    04443 */
    04444 inline
    04445 int bit_find_in_block(const bm::word_t* data,
    04446                       unsigned          nbit,
    04447                       bm::id_t*         prev)
    04448 {
    04449     register bm::id_t p = *prev;
    04450     int found = 0;
    04451
    04452     for(;;)
    04453     {
    04454         unsigned nword  = nbit >> bm::set_word_shift;
    04455         if (nword >= bm::set_block_size) break;
    04456
    04457         register bm::word_t val = data[nword] >> (p & bm::set_word_mask);
    04458
    04459         // TODO: consider BSF and de bruijn sequences here:
    04460         // http://www.0xe3.com/text/ntz/ComputingTrailingZerosHOWTO.html#debruijn
    04461
    04462         if (val)
    04463         {
    04464             while((val & 1) == 0)
    04465             {
    04466                 val >>= 1;
    04467                 ++nbit;
    04468                 ++p;
    04469             }
    04470             ++found;
    04471
    04472             break;
    04473         }
    04474         else
    04475         {
    04476            p    += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
    04477            nbit += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
    04478         }
    04479     }
    04480     *prev = p;
    04481     return found;
    04482 }
    04483
    04484 /*!
    04485    \brief Templated algorithm to unpacks octet based word into list of ON bit indexes
    04486    \param w - value
    04487    \param func - bit functor
    04488
    04489    @ingroup bitfunc
    04490 */
    04491 template<typename T, typename F>
    04492 void bit_for_each_4(T w, F& func)
    04493 {
    04494     for (unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
    04495     {
    04496         switch (w & 15)
    04497         {
    04498         case 0: // 0000
    04499             break;
    04500         case 1: // 0001
    04501             func(sub_octet);
    04502             break;
    04503         case 2: // 0010
    04504             func(sub_octet + 1);
    04505             break;
    04506         case 3: // 0011
    04507             func(sub_octet, sub_octet + 1);
    04508             break;
    04509         case 4: // 0100
    04510             func(sub_octet + 2);
    04511             break;
    04512         case 5: // 0101
    04513             func(sub_octet, sub_octet + 2);
    04514             break;
    04515         case 6: // 0110
    04516             func(sub_octet + 1, sub_octet + 2);
    04517             break;
    04518         case 7: // 0111
    04519             func(sub_octet, sub_octet + 1, sub_octet + 2);
    04520             break;
    04521         case 8: // 1000
    04522             func(sub_octet + 3);
    04523             break;
    04524         case 9: // 1001
    04525             func(sub_octet, sub_octet + 3);
    04526             break;
    04527         case 10: // 1010
    04528             func(sub_octet + 1, sub_octet + 3);
    04529             break;
    04530         case 11: // 1011
    04531             func(sub_octet, sub_octet + 1, sub_octet + 3);
    04532             break;
    04533         case 12: // 1100
    04534             func(sub_octet + 2, sub_octet + 3);
    04535             break;
    04536         case 13: // 1101
    04537             func(sub_octet, sub_octet + 2, sub_octet + 3);
    04538             break;
    04539         case 14: // 1110
    04540             func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
    04541             break;
    04542         case 15: // 1111
    04543             func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
    04544             break;
    04545         default:
    04546             BM_ASSERT(0);
    04547             break;
    04548         }
    04549
    04550     } // for
    04551 }
    04552
    04553
    04554 /*!
    04555    \brief Templated algorithm to unpacks word into list of ON bit indexes
    04556    \param w - value
    04557    \param func - bit functor
    04558
    04559    @ingroup bitfunc
    04560 */
    04561 template<typename T, typename F>
    04562 void bit_for_each(T w, F& func)
    04563 {
    04564     // Note: 4-bit table method works slower than plain check approach
    04565     for (unsigned octet = 0; w != 0; w >>= 8, octet += 8)
    04566     {
    04567         if (w & 1)   func(octet + 0);
    04568         if (w & 2)   func(octet + 1);
    04569         if (w & 4)   func(octet + 2);
    04570         if (w & 8)   func(octet + 3);
    04571         if (w & 16)  func(octet + 4);
    04572         if (w & 32)  func(octet + 5);
    04573         if (w & 64)  func(octet + 6);
    04574         if (w & 128) func(octet + 7);
    04575
    04576     } // for
    04577 }
    04578
    04579 /*! @brief Adaptor to copy 1 bits to array
    04580     @internal
    04581 */
    04582 template<typename B> class copy_to_array_functor
    04583 {
    04584 public:
    04585     copy_to_array_functor(B* bits): bp_(bits)
    04586     {}
    04587
    04588     B* ptr() { return bp_; }
    04589
    04590     void operator()(unsigned bit_idx) { *bp_++ = (B)bit_idx; }
    04591
    04592     void operator()(unsigned bit_idx0,
    04593                     unsigned bit_idx1)
    04594     {
    04595         bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
    04596         bp_+=2;
    04597     }
    04598
    04599     void operator()(unsigned bit_idx0,
    04600                     unsigned bit_idx1,
    04601                     unsigned bit_idx2)
    04602     {
    04603         bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
    04604         bp_+=3;
    04605     }
    04606
    04607     void operator()(unsigned bit_idx0,
    04608                     unsigned bit_idx1,
    04609                     unsigned bit_idx2,
    04610                     unsigned bit_idx3)
    04611     {
    04612         bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
    04613         bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
    04614         bp_+=4;
    04615     }
    04616
    04617 private:
    04618     copy_to_array_functor(const copy_to_array_functor&);
    04619     copy_to_array_functor& operator=(const copy_to_array_functor&);
    04620 private:
    04621     B* bp_;
    04622 };
    04623
    04624 /*! @brief Adaptor to copy 1 bits to array with base increment
    04625     @internal
    04626 */
    04627 template<typename B> class copy_to_array_functor_inc
    04628 {
    04629 public:
    04630     copy_to_array_functor_inc(B* bits, unsigned base_idx)
    04631     : bp_(bits), base_idx_(base_idx)
    04632     {}
    04633
    04634     B* ptr() { return bp_; }
    04635
    04636     void operator()(unsigned bit_idx)
    04637     {
    04638         *bp_++ = (B)(bit_idx + base_idx_);
    04639     }
    04640
    04641
    04642     void operator()(unsigned bit_idx0,
    04643                     unsigned bit_idx1)
    04644     {
    04645         bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
    04646         bp_+=2;
    04647     }
    04648
    04649     void operator()(unsigned bit_idx0,
    04650                     unsigned bit_idx1,
    04651                     unsigned bit_idx2)
    04652     {
    04653         bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
    04654         bp_[2]=(B)(bit_idx2+base_idx_);
    04655         bp_+=3;
    04656     }
    04657
    04658     void operator()(unsigned bit_idx0,
    04659                     unsigned bit_idx1,
    04660                     unsigned bit_idx2,
    04661                     unsigned bit_idx3)
    04662     {
    04663         bp_[0]=(B)(bit_idx0+base_idx_);bp_[1]=(B)(bit_idx1+base_idx_);
    04664         bp_[2]=(B)(bit_idx2+base_idx_);bp_[3]=(B)(bit_idx3+base_idx_);
    04665         bp_+=4;
    04666     }
    04667
    04668 private:
    04669     copy_to_array_functor_inc(const copy_to_array_functor_inc&);
    04670     copy_to_array_functor_inc& operator=(const copy_to_array_functor_inc&);
    04671 private:
    04672     B*        bp_;
    04673     unsigned  base_idx_; ///< Base increment factor
    04674 };
    04675
    04676
    04677 /*!
    04678    \brief Unpacks word into list of ON bit indexes (quad-bit based)
    04679    \param w - value
    04680    \param bits - pointer on the result array
    04681    \return number of bits in the list
    04682
    04683    @ingroup bitfunc
    04684 */
    04685 template<typename T,typename B> unsigned bit_list_4(T w, B* bits)
    04686 {
    04687     copy_to_array_functor<B> func(bits);
    04688     bit_for_each_4(w, func);
    04689     return (unsigned)(func.ptr() - bits);
    04690 }
    04691
    04692 /*!
    04693    \brief Unpacks word into list of ON bit indexes
    04694    \param w - value
    04695    \param bits - pointer on the result array
    04696    \return number of bits in the list
    04697
    04698    @ingroup bitfunc
    04699 */
    04700 template<typename T,typename B> unsigned bit_list(T w, B* bits)
    04701 {
    04702     copy_to_array_functor<B> func(bits);
    04703     bit_for_each(w, func);
    04704     return (unsigned)(func.ptr() - bits);
    04705 }
    04706
    04707
    04708 /*!
    04709     @brief Choose best representation for a bit-block
    04710     @ingroup bitfunc
    04711 */
    04712 inline
    04713 bm::set_representation best_representation(unsigned bit_count,
    04714                                            unsigned total_possible_bitcount,
    04715                                            unsigned gap_count,
    04716                                            unsigned block_size)
    04717 {
    04718     unsigned arr_size = sizeof(bm::gap_word_t) * bit_count + sizeof(bm::gap_word_t);
    04719     unsigned gap_size = sizeof(bm::gap_word_t) * gap_count + sizeof(bm::gap_word_t);
    04720     unsigned inv_arr_size = sizeof(bm::gap_word_t) * (total_possible_bitcount - bit_count) + sizeof(bm::gap_word_t);
    04721
    04722     if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
    04723     {
    04724         return bm::set_gap;
    04725     }
    04726
    04727     if (arr_size < inv_arr_size)
    04728     {
    04729         if ((arr_size < block_size) && (arr_size < gap_size))
    04730         {
    04731             return bm::set_array1;
    04732         }
    04733     }
    04734     else
    04735     {
    04736         if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
    04737         {
    04738             return bm::set_array0;
    04739         }
    04740     }
    04741     return bm::set_bitset;
    04742 }
    04743
    04744 /*!
    04745     @brief Convert bit block into an array of ints corresponding to 1 bits
    04746     @ingroup bitfunc
    04747 */
    04748 template<typename T> T bit_convert_to_arr(T* BMRESTRICT dest,
    04749                                           const unsigned* BMRESTRICT src,
    04750                                           bm::id_t bits,
    04751                                           unsigned dest_len,
    04752                                           unsigned mask = 0)
    04753 {
    04754     T* BMRESTRICT pcurr = dest;
    04755     for(unsigned bit_idx=0; bit_idx < bits; ++src,bit_idx += sizeof(*src) * 8)
    04756     {
    04757         unsigned val = *src ^ mask; // possible to invert value by XOR 0xFF..
    04758         if (val == 0)
    04759         {
    04760             continue;
    04761         }
    04762         if (pcurr + sizeof(val)*8 >= dest + dest_len) // insufficient space
    04763         {
    04764             return 0;
    04765         }
    04766
    04767         copy_to_array_functor_inc<T> func(pcurr, bit_idx);
    04768         bit_for_each_4(val, func);
    04769         unsigned word_bit_cnt = func.ptr() - pcurr;
    04770         pcurr += word_bit_cnt;
    04771
    04772     } // for
    04773     return (T)(pcurr - dest);
    04774 }
    04775
    04776
    04777
    04778
    04779 /*!
    04780     OBSOLETE function
    04781     \brief Convert bit block into an array of ints corresponding to 1 bits
    04782     \internal
    04783     @ingroup bitfunc
    04784 */
    04785 /*
    04786 template<typename T> T bit_convert_to_arr2(T* BMRESTRICT dest,
    04787                                           const unsigned* BMRESTRICT src,
    04788                                           bm::id_t bits,
    04789                                           unsigned dest_len)
    04790 {
    04791     register T* BMRESTRICT pcurr = dest;
    04792     T* BMRESTRICT end = dest + dest_len;
    04793     unsigned  bit_idx = 0;
    04794
    04795     do
    04796     {
    04797         register unsigned val = *src;
    04798         // We can skip if *src == 0
    04799
    04800         while (val == 0)
    04801         {
    04802             bit_idx += sizeof(*src) * 8;
    04803             if (bit_idx >= bits)
    04804             {
    04805                return (T)(pcurr - dest);
    04806             }
    04807             val = *(++src);
    04808         }
    04809
    04810         if (pcurr + sizeof(val)*8 > end) // insufficient space
    04811         {
    04812             return 0;
    04813         }
    04814
    04815         for (int i = 0; i < 32; i+=4)
    04816         {
    04817             if (val & 1)
    04818                 *pcurr++ = bit_idx;
    04819             val >>= 1; ++bit_idx;
    04820             if (val & 1)
    04821                 *pcurr++ = bit_idx;
    04822             val >>= 1; ++bit_idx;
    04823             if (val & 1)
    04824                 *pcurr++ = bit_idx;
    04825             val >>= 1; ++bit_idx;
    04826             if (val & 1)
    04827                 *pcurr++ = bit_idx;
    04828             val >>= 1; ++bit_idx;
    04829         }
    04830
    04831         if (bits <= bit_idx)
    04832             break;
    04833
    04834         val = *(++src);
    04835     } while (1);
    04836
    04837     return (T)(pcurr - dest);
    04838 }
    04839 */
    04840
    04841
    04842 /*! @brief Calculates memory overhead for number of gap blocks sharing
    04843            the same memory allocation table (level lengths table).
    04844     @ingroup gapfunc
    04845 */
    04846 template<typename T>
    04847 unsigned gap_overhead(const T* length,
    04848                       const T* length_end,
    04849                       const T* glevel_len)
    04850 {
    04851     BM_ASSERT(length && length_end && glevel_len);
    04852
    04853     unsigned overhead = 0;
    04854     for (;length < length_end; ++length)
    04855     {
    04856         unsigned len = *length;
    04857         int level = gap_calc_level(len, glevel_len);
    04858         BM_ASSERT(level >= 0 && level < (int)bm::gap_levels);
    04859         unsigned capacity = glevel_len[level];
    04860         BM_ASSERT(capacity >= len);
    04861         overhead += capacity - len;
    04862     }
    04863     return overhead;
    04864 }
    04865
    04866
    04867 /*! @brief Finds optimal gap blocks lengths.
    04868     @param length - first element of GAP lengths array
    04869     @param length_end - end of the GAP lengths array
    04870     @param glevel_len - destination GAP lengths array
    04871     @ingroup gapfunc
    04872 */
    04873 template<typename T>
    04874 bool improve_gap_levels(const T* length,
    04875                         const T* length_end,
    04876                         T*       glevel_len)
    04877 {
    04878     BM_ASSERT(length && length_end && glevel_len);
    04879
    04880     size_t lsize = length_end - length;
    04881
    04882     BM_ASSERT(lsize);
    04883
    04884     gap_word_t max_len = 0;
    04885     unsigned i;
    04886     for (i = 0; i < lsize; ++i)
    04887     {
    04888         if (length[i] > max_len)
    04889             max_len = length[i];
    04890     }
    04891     if (max_len < 5 || lsize <= bm::gap_levels)
    04892     {
    04893         glevel_len[0] = max_len + 4;
    04894         for (i = 1; i < bm::gap_levels; ++i)
    04895         {
    04896             glevel_len[i] = bm::gap_max_buff_len;
    04897         }
    04898         return true;
    04899     }
    04900
    04901     glevel_len[bm::gap_levels-1] = max_len + 5;
    04902
    04903     unsigned min_overhead = gap_overhead(length, length_end, glevel_len);
    04904     bool is_improved = false;
    04905     gap_word_t prev_value = glevel_len[bm::gap_levels-1];
    04906
    04907     // main problem solving loop
    04908     //
    04909     for (i = bm::gap_levels-2; ; --i)
    04910     {
    04911         unsigned opt_len = 0;
    04912         unsigned j;
    04913         bool imp_flag = false;
    04914         gap_word_t gap_saved_value = glevel_len[i];
    04915         for (j = 0; j < lsize; ++j)
    04916         {
    04917             glevel_len[i] = length[j]+4;
    04918             unsigned ov = gap_overhead(length, length_end, glevel_len);
    04919             if (ov <= min_overhead)
    04920             {
    04921                 min_overhead = ov;
    04922                 opt_len = length[j]+4;
    04923                 imp_flag = true;
    04924             }
    04925         }
    04926         if (imp_flag)
    04927         {
    04928             glevel_len[i] = (T)opt_len; // length[opt_idx]+4;
    04929             is_improved = true;
    04930         }
    04931         else
    04932         {
    04933             glevel_len[i] = gap_saved_value;
    04934         }
    04935         if (i == 0)
    04936             break;
    04937         prev_value = glevel_len[i];
    04938     }
    04939     //
    04940     // Remove duplicates
    04941     //
    04942
    04943     T val = *glevel_len;
    04944     T* gp = glevel_len;
    04945     T* res = glevel_len;
    04946     for (i = 0; i < bm::gap_levels; ++i)
    04947     {
    04948         if (val != *gp)
    04949         {
    04950             val = *gp;
    04951             *++res = val;
    04952         }
    04953         ++gp;
    04954     }
    04955
    04956     // Filling the "unused" part with max. possible value
    04957     while (++res < (glevel_len + bm::gap_levels))
    04958     {
    04959         *res = bm::gap_max_buff_len;
    04960     }
    04961
    04962     return is_improved;
    04963
    04964 }
    04965
    04966
    04967
    04968 /**
    04969     Bit-block get adapter, takes bitblock and represents it as a
    04970     get_32() accessor function
    04971     /internal
    04972 */
    04973 class bitblock_get_adapter
    04974 {
    04975 public:
    04976     bitblock_get_adapter(const bm::word_t* bit_block) : b_(bit_block) {}
    04977
    04978     BMFORCEINLINE
    04979     bm::word_t get_32() { return *b_++; }
    04980 private:
    04981     const bm::word_t*  b_;
    04982 };
    04983
    04984
    04985 /**
    04986     Bit-block store adapter, takes bitblock and saves results into it
    04987     /internal
    04988 */
    04989 class bitblock_store_adapter
    04990 {
    04991 public:
    04992     bitblock_store_adapter(bm::word_t* bit_block) : b_(bit_block) {}
    04993     BMFORCEINLINE
    04994     void push_back(bm::word_t w) { *b_++ = w; }
    04995 private:
    04996     bm::word_t* b_;
    04997 };
    04998
    04999 /**
    05000     Bit-block sum adapter, takes values and sums it
    05001     /internal
    05002 */
    05003 class bitblock_sum_adapter
    05004 {
    05005 public:
    05006     bitblock_sum_adapter() : sum_(0) {}
    05007     BMFORCEINLINE
    05008     void push_back(bm::word_t w) { this->sum_+= w; }
    05009     /// Get accumulated sum
    05010     bm::word_t sum() const { return this->sum_; }
    05011 private:
    05012     bm::word_t sum_;
    05013 };
    05014
    05015 /**
    05016     Adapter to get words from a range stream
    05017     (see range serialized bit-block)
    05018     \internal
    05019 */
    05020 template<class DEC> class decoder_range_adapter
    05021 {
    05022 public:
    05023     decoder_range_adapter(DEC& dec, unsigned from_idx, unsigned to_idx)
    05024     : decoder_(dec),
    05025       from_(from_idx),
    05026       to_(to_idx),
    05027       cnt_(0)
    05028     {}
    05029
    05030     bm::word_t get_32()
    05031     {
    05032         if (cnt_ < from_ || cnt_ > to_)
    05033         {
    05034             ++cnt_; return 0;
    05035         }
    05036         ++cnt_;
    05037         return decoder_.get_32();
    05038     }
    05039
    05040 private:
    05041     DEC&     decoder_;
    05042     unsigned from_;
    05043     unsigned to_;
    05044     unsigned cnt_;
    05045 };
    05046
    05047
    05048 /*!
    05049     Abstract recombination algorithm for two bit-blocks
    05050     Bit blocks can come as dserialization decoders or bit-streams
    05051 */
    05052 template<class It1, class It2, class BinaryOp, class Encoder>
    05053 void bit_recomb(It1& it1, It2& it2,
    05054                 BinaryOp& op,
    05055                 Encoder& enc,
    05056                 unsigned block_size = bm::set_block_size)
    05057 {
    05058     for (unsigned i = 0; i < block_size; ++i)
    05059     {
    05060         bm::word_t w1 = it1.get_32();
    05061         bm::word_t w2 = it2.get_32();
    05062         bm::word_t w = op(w1, w2);
    05063         enc.push_back( w );
    05064     } // for
    05065 }
    05066
    05067 /// Bit AND functor
    05068 template<typename W> struct bit_AND
    05069 {
    05070     W operator()(W w1, W w2) { return w1 & w2; }
    05071 };
    05072
    05073 /// Bit OR functor
    05074 template<typename W> struct bit_OR
    05075 {
    05076     W operator()(W w1, W w2) { return w1 | w2; }
    05077 };
    05078
    05079 /// Bit SUB functor
    05080 template<typename W> struct bit_SUB
    05081 {
    05082     W operator()(W w1, W w2) { return w1 & ~w2; }
    05083 };
    05084
    05085 /// Bit XOR functor
    05086 template<typename W> struct bit_XOR
    05087 {
    05088     W operator()(W w1, W w2) { return w1 ^ w2; }
    05089 };
    05090
    05091 /// Bit ASSIGN functor
    05092 template<typename W> struct bit_ASSIGN
    05093 {
    05094     W operator()(W w1, W w2) { return w2; }
    05095 };
    05096
    05097 /// Bit COUNT functor
    05098 template<typename W> struct bit_COUNT
    05099 {
    05100     W operator()(W w1, W w2)
    05101     {
    05102         w1 = 0;
    05103         BM_INCWORD_BITCOUNT(w1, w2);
    05104         return w1;
    05105     }
    05106 };
    05107
    05108 /// Bit COUNT AND functor
    05109 template<typename W> struct bit_COUNT_AND
    05110 {
    05111     W operator()(W w1, W w2)
    05112     {
    05113         W r = 0;
    05114         BM_INCWORD_BITCOUNT(r, w1 & w2);
    05115         return r;
    05116     }
    05117 };
    05118
    05119 /// Bit COUNT XOR functor
    05120 template<typename W> struct bit_COUNT_XOR
    05121 {
    05122     W operator()(W w1, W w2)
    05123     {
    05124         W r = 0;
    05125         BM_INCWORD_BITCOUNT(r, w1 ^ w2);
    05126         return r;
    05127     }
    05128 };
    05129
    05130 /// Bit COUNT OR functor
    05131 template<typename W> struct bit_COUNT_OR
    05132 {
    05133     W operator()(W w1, W w2)
    05134     {
    05135         W r = 0;
    05136         BM_INCWORD_BITCOUNT(r, w1 | w2);
    05137         return r;
    05138     }
    05139 };
    05140
    05141
    05142 /// Bit COUNT SUB AB functor
    05143 template<typename W> struct bit_COUNT_SUB_AB
    05144 {
    05145     W operator()(W w1, W w2)
    05146     {
    05147         W r = 0;
    05148         BM_INCWORD_BITCOUNT(r, w1 & (~w2));
    05149         return r;
    05150     }
    05151 };
    05152
    05153 /// Bit SUB BA functor
    05154 template<typename W> struct bit_COUNT_SUB_BA
    05155 {
    05156     W operator()(W w1, W w2)
    05157     {
    05158         W r = 0;
    05159         BM_INCWORD_BITCOUNT(r, w2 & (~w1));
    05160         return r;
    05161     }
    05162 };
    05163
    05164 /// Bit COUNT A functor
    05165 template<typename W> struct bit_COUNT_A
    05166 {
    05167     W operator()(W w1, W w2)
    05168     {
    05169         W r = 0;
    05170         BM_INCWORD_BITCOUNT(r, w1);
    05171         return r;
    05172     }
    05173 };
    05174
    05175 /// Bit COUNT B functor
    05176 template<typename W> struct bit_COUNT_B
    05177 {
    05178     W operator()(W w1, W w2)
    05179     {
    05180         W r = 0;
    05181         BM_INCWORD_BITCOUNT(r, w2);
    05182         return r;
    05183     }
    05184 };
    05185
    05186 typedef
    05187 void (*gap_operation_to_bitset_func_type)(unsigned*,
    05188                                           const gap_word_t*);
    05189
    05190 typedef
    05191 gap_word_t* (*gap_operation_func_type)(const gap_word_t* BMRESTRICT,
    05192                                        const gap_word_t* BMRESTRICT,
    05193                                        gap_word_t*       BMRESTRICT,
    05194                                        unsigned& );
    05195
    05196 typedef
    05197 bm::id_t (*bit_operation_count_func_type)(const bm::word_t* BMRESTRICT,
    05198                                           const bm::word_t* BMRESTRICT,
    05199                                           const bm::word_t* BMRESTRICT);
    05200
    05201
    05202 template<bool T>
    05203 struct operation_functions
    05204 {
    05205     static
    05206         gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END];
    05207     static
    05208         gap_operation_func_type gapop_table_[bm::set_END];
    05209     static
    05210         bit_operation_count_func_type bit_op_count_table_[bm::set_END];
    05211
    05212     static
    05213     gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
    05214     {
    05215         return gap2bit_table_[i];
    05216     }
    05217
    05218     static
    05219     gap_operation_func_type gap_operation(unsigned i)
    05220     {
    05221         return gapop_table_[i];
    05222     }
    05223
    05224     static
    05225     bit_operation_count_func_type bit_operation_count(unsigned i)
    05226     {
    05227         return bit_op_count_table_[i];
    05228     }
    05229 };
    05230
    05231 template<bool T>
    05232 gap_operation_to_bitset_func_type
    05233 operation_functions<T>::gap2bit_table_[bm::set_END] = {
    05234     &gap_and_to_bitset<bm::gap_word_t>,    // set_AND
    05235     &gap_add_to_bitset<bm::gap_word_t>,    // set_OR
    05236     &gap_sub_to_bitset<bm::gap_word_t>,    // set_SUB
    05237     &gap_xor_to_bitset<bm::gap_word_t>,    // set_XOR
    05238     0
    05239 };
    05240
    05241 template<bool T>
    05242 gap_operation_func_type
    05243 operation_functions<T>::gapop_table_[bm::set_END] = {
    05244     &gap_operation_and,    // set_AND
    05245     &gap_operation_or,     // set_OR
    05246     &gap_operation_sub,    // set_SUB
    05247     &gap_operation_xor,    // set_XOR
    05248     0
    05249 };
    05250
    05251
    05252 template<bool T>
    05253 bit_operation_count_func_type
    05254 operation_functions<T>::bit_op_count_table_[bm::set_END] = {
    05255     0,                            // set_AND
    05256     0,                            // set_OR
    05257     0,                            // set_SUB
    05258     0,                            // set_XOR
    05259     0,                            // set_ASSIGN
    05260     0,                            // set_COUNT
    05261     &bit_operation_and_count,     // set_COUNT_AND
    05262     &bit_operation_xor_count,     // set_COUNT_XOR
    05263     &bit_operation_or_count,      // set_COUNT_OR
    05264     &bit_operation_sub_count,     // set_COUNT_SUB_AB
    05265     &bit_operation_sub_count_inv, // set_COUNT_SUB_BA
    05266     0,                            // set_COUNT_A
    05267     0,                            // set_COUNT_B
    05268 };
    05269
    05270 } // namespace bm
    05271
    05272 #endif