Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Namespace Members | Data Fields | Globals | Examples

bmfunc.h

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

Generated on Thu Apr 20 13:28:46 2006 for BitMagic by  doxygen 1.4.1