BitMagicC++Library
bmfunc.h
Go to the documentation of this file.
1 #ifndef BMFUNC__H__INCLUDED__
2 #define BMFUNC__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 #include <memory.h>
22 
23 #include "bmdef.h"
24 #include "bmutil.h"
25 
26 
27 #ifdef _MSC_VER
28 # pragma warning( disable: 4146 )
29 #endif
30 
31 namespace bm
32 {
33 
34 
35 inline
37  bm::word_t left,
38  bm::word_t right);
39 
40 inline
42  bm::word_t left,
43  bm::word_t right);
44 
45 /*!
46  @brief Structure with statistical information about bitset's memory
47  allocation details.
48  @ingroup bvector
49 */
51 {
52  /// Number of bit blocks.
53  unsigned bit_blocks;
54  /// Number of GAP blocks.
55  unsigned gap_blocks;
56  /// Estimated maximum of memory required for serialization.
58  /// Memory used by bitvector including temp and service blocks
59  size_t memory_used;
60  /// Array of all GAP block lengths in the bvector.
62  /// GAP lengths used by bvector
64 
65 
66 
67  /// cound bit block
69  {
70  ++bit_blocks;
71  unsigned mem_used = (unsigned)(sizeof(bm::word_t) * bm::set_block_size);
72  memory_used += mem_used;
73  max_serialize_mem += mem_used;
74  }
75 
76  /// count gap block
77  void add_gap_block(unsigned capacity, unsigned length)
78  {
79  ++gap_blocks;
80  unsigned mem_used = (unsigned)(capacity * sizeof(gap_word_t));
81  memory_used += mem_used;
82  max_serialize_mem += (unsigned)(length * sizeof(gap_word_t));
83  }
84 };
85 
86 /**
87  \brief ad-hoc conditional expressions
88  \internal
89 */
90 template <bool b> struct conditional
91 {
92  static bool test() { return true; }
93 };
94 template <> struct conditional<false>
95 {
96  static bool test() { return false; }
97 };
98 
99 /*!
100  @defgroup gapfunc GAP functions
101  GAP functions implement different opereations on GAP compressed blocks (internals)
102  and serve as a minimal building blocks.
103  \internal
104  @ingroup bvector
105  */
106 
107 /*!
108  @defgroup bitfunc BIT functions
109  Bit functions implement different opereations on bit blocks (internals)
110  and serve as a minimal building blocks.
111  \internal
112  @ingroup bvector
113  */
114 
115 
116 
117 
118 
119 
120 /*!
121  Returns bit count
122  @ingroup bitfunc
123 */
126 {
127 #if defined(BMSSE42OPT) || defined(BMAVX2OPT)
128  return _mm_popcnt_u32(w);
129 #else
130  return
131  bm::bit_count_table<true>::_count[(unsigned char)(w)] +
132  bm::bit_count_table<true>::_count[(unsigned char)((w) >> 8)] +
133  bm::bit_count_table<true>::_count[(unsigned char)((w) >> 16)] +
134  bm::bit_count_table<true>::_count[(unsigned char)((w) >> 24)];
135 #endif
136 }
137 
138 inline
139 int parallel_popcnt_32(unsigned int n)
140 {
141  unsigned int tmp;
142 
143  tmp = n - ((n >> 1) & 033333333333)
144  - ((n >> 2) & 011111111111);
145  return ((tmp + (tmp >> 3)) & 030707070707) % 63;
146 }
147 
148 
149 /*!
150  Function calculates number of 1 bits in 64-bit word.
151  @ingroup bitfunc
152 */
155 {
156 #if defined(BMSSE42OPT) || defined(BMAVX2OPT)
157  return (int)_mm_popcnt_u64(x);
158 #else
159  x = x - ((x >> 1) & 0x5555555555555555);
160  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
161  x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
162  x = x + (x >> 8);
163  x = x + (x >> 16);
164  x = x + (x >> 32);
165  return x & 0xFF;
166 #endif
167 }
168 
169 inline
171  bm::id64_t u, bm::id64_t v)
172 {
173  const bm::id64_t m1 = 0x5555555555555555;
174  const bm::id64_t m2 = 0x3333333333333333;
175  const bm::id64_t m3 = 0x0F0F0F0F0F0F0F0F;
176  const bm::id64_t m4 = 0x000000FF000000FF;
177 
178  x = x - ((x >> 1) & m1);
179  y = y - ((y >> 1) & m1);
180  u = u - ((u >> 1) & m1);
181  v = v - ((v >> 1) & m1);
182  x = (x & m2) + ((x >> 2) & m2);
183  y = (y & m2) + ((y >> 2) & m2);
184  u = (u & m2) + ((u >> 2) & m2);
185  v = (v & m2) + ((v >> 2) & m2);
186  x = x + y;
187  u = u + v;
188  x = (x & m3) + ((x >> 4) & m3);
189  u = (u & m3) + ((u >> 4) & m3);
190  x = x + u;
191  x = x + (x >> 8);
192  x = x + (x >> 16);
193  x = x & m4;
194  x = x + (x >> 32);
195  return x & 0x000001FF;
196 }
197 
198 
199 
200 /*!
201  Returns number of trailing zeros
202  @ingroup bitfunc
203 */
206 {
207  // TODO: find a better variant for MSVC
208 #if defined(BMSSE42OPT) && defined(__GNUC__)
209  return __builtin_ctzl(w);
210 #else
211  // implementation from
212  // https://gist.github.com/andrewrk/1883543
213  static const int mod37_pos[] =
214  {
215  -1, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
216  7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
217  20, 8, 19, 18
218  };
219  return mod37_pos[(-w & w) % 37];
220 #endif
221 }
222 
223 
224 
225 
226 //---------------------------------------------------------------------
227 
228 /**
229  Nomenclature of set operations
230 */
232 {
233  set_AND = 0,
234  set_OR = 1,
235  set_SUB = 2,
236  set_XOR = 3,
246 
248 };
249 
250 /// Returns true if set operation is constant (bitcount)
251 inline
253 {
254  return (int(op) >= int(set_COUNT));
255 }
256 
257 /**
258  Bit operations enumeration.
259 */
261 {
266 };
267 
268 /**
269  Convert set operation to operation
270 */
271 inline
273 {
274  BM_ASSERT(op == set_AND ||
275  op == set_OR ||
276  op == set_SUB ||
277  op == set_XOR);
278  return (bm::operation) op;
279 }
280 
281 //---------------------------------------------------------------------
282 
283 /**
284  Structure carries pointer on bit block with all bits 1
285  @ingroup bitfunc
286 */
287 template<bool T> struct all_set
288 {
290  {
293 
295  {
296  ::memset(_p, 0xFF, sizeof(_p));
297  if (bm::conditional<sizeof(void*) == 8>::test())
298  {
299  const unsigned long long magic_mask = 0xFFFFfffeFFFFfffe;
300  ::memcpy(&_p_fullp, &magic_mask, sizeof(magic_mask));
301  }
302  else
303  {
304  const unsigned magic_mask = 0xFFFFfffe;
305  ::memcpy(&_p_fullp, &magic_mask, sizeof(magic_mask));
306  }
307  }
308  };
309 
311  static bool is_full_block(const bm::word_t* bp)
312  { return (bp == _block._p || bp == _block._p_fullp); }
314  static bool is_valid_block_addr(const bm::word_t* bp)
315  { return (bp && !(bp == _block._p || bp == _block._p_fullp)); }
317 };
318 
319 
320 template<bool T> typename all_set<T>::all_set_block all_set<T>::_block;
321 
322 /// XOR swap two scalar variables
323 template<typename W>
324 void xor_swap(W& x, W& y)
325 {
326  BM_ASSERT(&x != &y);
327  x ^= y;
328  y ^= x;
329  x ^= y;
330 }
331 
332 
333 //---------------------------------------------------------------------
334 
335 /*!
336  \brief Lexicographical comparison of two words as bit strings (reference)
337  Auxiliary implementation for testing and reference purposes.
338  \param w1 - First word.
339  \param w2 - Second word.
340  \return <0 - less, =0 - equal, >0 - greater.
341 
342  @ingroup bitfunc
343 */
344 template<typename T> int wordcmp0(T w1, T w2)
345 {
346  while (w1 != w2)
347  {
348  int res = (w1 & 1) - (w2 & 1);
349  if (res != 0) return res;
350  w1 >>= 1;
351  w2 >>= 1;
352  }
353  return 0;
354 }
355 
356 
357 /*
358 template<typename T> int wordcmp(T w1, T w2)
359 {
360  T diff = w1 ^ w2;
361  return diff ? ((w1 & diff & (diff ^ (diff - 1)))? 1 : -1) : 0;
362 }
363 */
364 /*!
365  \brief Lexicographical comparison of two words as bit strings.
366  Auxiliary implementation for testing and reference purposes.
367  \param a - First word.
368  \param b - Second word.
369  \return <0 - less, =0 - equal, >0 - greater.
370 
371  @ingroup bitfunc
372 */
373 
374 template<typename T> int wordcmp(T a, T b)
375 {
376  T diff = a ^ b;
377  return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
378 }
379 
380 
381 // Low bit extraction
382 // x & (x ^ (x-1))
383 
384 
385 
386 /*!
387  \brief Byte orders recognized by the library.
388 */
390 {
393 };
394 
395 
396 /**
397  Internal structure. Different global settings.
398 */
399 template<bool T> struct globals
400 {
401  struct bo
402  {
404 
405  bo()
406  {
407  unsigned x;
408  unsigned char *s = (unsigned char *)&x;
409  s[0] = 1;
410  s[1] = 2;
411  s[2] = 3;
412  s[3] = 4;
413 
414  if(x == 0x04030201)
415  {
416  _byte_order = LittleEndian;
417  return;
418  }
419 
420  if(x == 0x01020304)
421  {
422  _byte_order = BigEndian;
423  return;
424  }
425 
426  BM_ASSERT(0); // "Invalid Byte Order\n"
427  _byte_order = LittleEndian;
428  }
429  };
430 
431  static bo _bo;
432 
433  static ByteOrder byte_order() { return _bo._byte_order; }
434 
435 };
436 
437 template<bool T> typename globals<T>::bo globals<T>::_bo;
438 
439 
440 
441 
442 
443 
444 /*
445  \brief Binary search for the block where bit = pos located.
446  \param buf - GAP buffer pointer.
447  \param pos - index of the element.
448  \param is_set - output. GAP value (0 or 1).
449  \return GAP index.
450  @ingroup gapfunc
451 */
452 template<typename T>
453 unsigned gap_bfind(const T* buf, unsigned pos, unsigned* is_set)
454 {
456  *is_set = (*buf) & 1;
457 
458  BMREGISTER unsigned start = 1;
459  BMREGISTER unsigned end = 1 + ((*buf) >> 3);
460 
461  while ( start != end )
462  {
463  unsigned curr = (start + end) >> 1;
464  if ( buf[curr] < pos )
465  start = curr + 1;
466  else
467  end = curr;
468  }
469  *is_set ^= ((start-1) & 1);
470  return start;
471 }
472 
473 
474 /*!
475  \brief Tests if bit = pos is true.
476  \param buf - GAP buffer pointer.
477  \param pos - index of the element.
478  \return true if position is in "1" gap
479  @ingroup gapfunc
480 */
481 template<typename T> unsigned gap_test(const T* buf, unsigned pos)
482 {
484 
485  unsigned start = 1;
486  unsigned end = 1 + ((*buf) >> 3);
487 
488  if (end - start < 10)
489  {
490  unsigned sv = *buf & 1;
491  unsigned sv1= sv ^ 1;
492  if (buf[1] >= pos) return sv;
493  if (buf[2] >= pos) return sv1;
494  if (buf[3] >= pos) return sv;
495  if (buf[4] >= pos) return sv1;
496  if (buf[5] >= pos) return sv;
497  if (buf[6] >= pos) return sv1;
498  if (buf[7] >= pos) return sv;
499  if (buf[8] >= pos) return sv1;
500  if (buf[9] >= pos) return sv;
501  BM_ASSERT(0);
502  }
503  else
504  {
505  while (start != end)
506  {
507  unsigned curr = (start + end) >> 1;
508  if (buf[curr] < pos)
509  start = curr + 1;
510  else
511  end = curr;
512  }
513  }
514  return ((*buf) & 1) ^ ((--start) & 1);
515 }
516 
517 /*!
518  \brief Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
519  \param buf - GAP buffer pointer.
520  \param pos - index of the element.
521  \return true if position is in "1" gap
522  @ingroup gapfunc
523 */
524 template<typename T>
525 unsigned gap_test_unr(const T* buf, const unsigned pos)
526 {
528 #if defined(BMSSE2OPT)
529  unsigned start = 1;
530  unsigned end = 1 + ((*buf) >> 3);
531  unsigned dsize = end - start;
532 
533  if (dsize < 17)
534  {
535  start = bm::sse2_gap_find(buf + 1, (bm::gap_word_t)pos, dsize);
536  unsigned res = ((*buf) & 1) ^ ((start) & 1);
537  BM_ASSERT(buf[start + 1] >= pos);
538  BM_ASSERT(buf[start] < pos || (start == 0));
539  BM_ASSERT(res == bm::gap_test(buf, pos));
540  return res;
541  }
542  unsigned arr_end = end;
543  while (start != end)
544  {
545  unsigned curr = (start + end) >> 1;
546  if (buf[curr] < pos)
547  start = curr + 1;
548  else
549  end = curr;
550 
551  unsigned size = end - start;
552  if (size < 16)
553  {
554  size += (end != arr_end);
555  unsigned idx = bm::sse2_gap_find(buf + start, (bm::gap_word_t)pos, size);
556  start += idx;
557 
558  BM_ASSERT(buf[start] >= pos);
559  BM_ASSERT(buf[start - 1] < pos || (start == 1));
560  break;
561  }
562  }
563 
564  unsigned res = ((*buf) & 1) ^ ((--start) & 1);
565 
566  BM_ASSERT(res == bm::gap_test(buf, pos));
567  return res;
568 #endif
569 #if defined(BMSSE42OPT)
570  unsigned start = 1;
571  unsigned end = 1 + ((*buf) >> 3);
572  unsigned dsize = end - start;
573 
574  if (dsize < 17)
575  {
576  start = bm::sse4_gap_find(buf+1, (bm::gap_word_t)pos, dsize);
577  unsigned res = ((*buf) & 1) ^ ((start) & 1);
578  BM_ASSERT(buf[start+1] >= pos);
579  BM_ASSERT(buf[start] < pos || (start==0));
580  BM_ASSERT(res == bm::gap_test(buf, pos));
581  return res;
582  }
583  unsigned arr_end = end;
584  while (start != end)
585  {
586  unsigned curr = (start + end) >> 1;
587  if (buf[curr] < pos)
588  start = curr + 1;
589  else
590  end = curr;
591 
592  unsigned size = end - start;
593  if (size < 16)
594  {
595  size += (end != arr_end);
596  unsigned idx = bm::sse4_gap_find(buf + start, (bm::gap_word_t)pos, size);
597  start += idx;
598 
599  BM_ASSERT(buf[start] >= pos);
600  BM_ASSERT(buf[start - 1] < pos || (start == 1));
601  break;
602  }
603  }
604 
605  unsigned res = ((*buf) & 1) ^ ((--start) & 1);
606 
607  BM_ASSERT(res == bm::gap_test(buf, pos));
608  return res;
609 #else
610  return bm::gap_test(buf, pos);
611 #endif
612 }
613 
614 
615 /*! For each non-zero block executes supplied function.
616  \internal
617 */
618 template<class T, class F>
619 void for_each_nzblock(T*** root, unsigned size1,
620  F& f)
621 {
622  for (unsigned i = 0; i < size1; ++i)
623  {
624  T** blk_blk = root[i];
625  if (!blk_blk)
626  {
627  f.on_empty_top(i);
628  continue;
629  }
630 
631  unsigned non_empty_top = 0;
632  unsigned r = i * bm::set_array_size;
633  for (unsigned j = 0;j < bm::set_array_size; ++j)
634  {
635  if (blk_blk[j])
636  {
637  f(blk_blk[j], r + j);
638  non_empty_top += (blk_blk[j] != 0);// re-check for mutation
639  }
640  else
641  {
642  f.on_empty_block(r + j);
643  }
644  } // for j
645  if (non_empty_top == 0)
646  {
647  f.on_empty_top(i);
648  }
649  } // for i
650 }
651 
652 /*! For each non-zero block executes supplied function.
653 */
654 template<class T, class F>
655 void for_each_nzblock2(T*** root, unsigned size1, F& f)
656 {
657  for (unsigned i = 0; i < size1; ++i)
658  {
659  T** blk_blk;
660  if ((blk_blk = root[i])!=0)
661  {
662  unsigned j = 0;
663  do
664  {
665  if (blk_blk[j])
666  f(blk_blk[j]);
667  if (blk_blk[j+1])
668  f(blk_blk[j+1]);
669  if (blk_blk[j+2])
670  f(blk_blk[j+2]);
671  if (blk_blk[j+3])
672  f(blk_blk[j+3]);
673  j += 4;
674  } while (j < bm::set_array_size);
675  }
676  } // for i
677 }
678 
679 
680 /*! For each non-zero block executes supplied function-predicate.
681  Function returns if function-predicate returns true
682 */
683 template<class T, class F>
684 bool for_each_nzblock_if(T*** root, unsigned size1, F& f)
685 {
686  unsigned block_idx = 0;
687  for (unsigned i = 0; i < size1; ++i)
688  {
689  T** blk_blk = root[i];
690  if (!blk_blk)
691  {
692  block_idx += bm::set_array_size;
693  continue;
694  }
695 
696  for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
697  {
698  if (blk_blk[j])
699  if (f(blk_blk[j], block_idx)) return true;
700  }
701  }
702  return false;
703 }
704 
705 /*! For each block executes supplied function.
706 */
707 template<class T, class F>
708 void for_each_block(T*** root, unsigned size1, F& f)
709 {
710  unsigned block_idx = 0;
711 
712  for (unsigned i = 0; i < size1; ++i)
713  {
714  T** blk_blk = root[i];
715 
716  if (blk_blk)
717  {
718  for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
719  {
720  f(blk_blk[j], block_idx);
721  }
722  }
723  else
724  {
725  for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
726  {
727  f(0, block_idx);
728  }
729  }
730  }
731 }
732 
733 
734 
735 /*! Special BM optimized analog of STL for_each
736 */
737 template<class T, class F> F bmfor_each(T first, T last, F f)
738 {
739  do
740  {
741  f(*first);
742  ++first;
743  } while (first < last);
744  return f;
745 }
746 
747 /*! Computes SUM of all elements of the sequence
748 */
749 template<class T> T sum_arr(T* first, T* last)
750 {
751  T sum = 0;
752  while (first < last)
753  {
754  sum += *first;
755  ++first;
756  }
757  return sum;
758 }
759 
760 
761 
762 
763 /*!
764  \brief Calculates number of bits ON in GAP buffer.
765  \param buf - GAP buffer pointer.
766  \param dsize - buffer size
767  \return Number of non-zero bits.
768  @ingroup gapfunc
769 */
770 template<typename T> unsigned gap_bit_count(const T* buf, unsigned dsize=0)
771 {
772  BMREGISTER const T* pcurr = buf;
773  if (dsize == 0)
774  dsize = (*pcurr >> 3);
775 
776  BMREGISTER const T* pend = pcurr + dsize;
777 
778  BMREGISTER unsigned bits_counter = 0;
779  ++pcurr;
780 
781  if (*buf & 1)
782  {
783  bits_counter += *pcurr + 1;
784  ++pcurr;
785  }
786  ++pcurr; // set GAP to 1
787 
788  while (pcurr <= pend)
789  {
790  bits_counter += *pcurr - *(pcurr-1);
791  pcurr += 2; // jump to the next positive GAP
792  }
793 
794  return bits_counter;
795 }
796 
797 /*!
798  \brief Calculates number of bits ON in GAP buffer. Loop unrolled version.
799  \param buf - GAP buffer pointer.
800  \param dsize - buffer size
801  \return Number of non-zero bits.
802  @ingroup gapfunc
803 */
804 template<typename T> unsigned gap_bit_count_unr(const T* buf)
805 {
806  const T* pcurr = buf;
807  unsigned dsize = (*pcurr >> 3);
808 
809  unsigned cnt = 0;
810  pcurr = buf + 1; // set up start position
811  T first_one = *buf & 1;
812  if (first_one)
813  {
814  cnt += *pcurr + 1;
815  ++pcurr;
816  }
817  ++pcurr; // set GAP to 1
818 
819  #if defined(BMAVX2OPT)
820  if (dsize > 34)
821  {
822  const unsigned unr_factor = 32;
823  unsigned waves = (dsize-2) / unr_factor;
824  pcurr = avx2_gap_sum_arr(pcurr, waves, &cnt);
825  }
826  #elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
827  if (dsize > 18)
828  {
829  const unsigned unr_factor = 16;
830  unsigned waves = (dsize - 2) / unr_factor;
831  pcurr = sse2_gap_sum_arr(pcurr, waves, &cnt);
832  }
833  #else
834  if (dsize > 10)
835  {
836  const unsigned unr_factor = 8;
837  unsigned waves = (dsize - 2) / unr_factor;
838  for (unsigned i = 0; i < waves; i += unr_factor)
839  {
840  cnt += pcurr[0] - pcurr[0 - 1];
841  cnt += pcurr[2] - pcurr[2 - 1];
842  cnt += pcurr[4] - pcurr[4 - 1];
843  cnt += pcurr[6] - pcurr[6 - 1];
844 
845  pcurr += unr_factor;
846  } // for
847  }
848  #endif
849 
850  const T* pend = buf + dsize;
851  for ( ; pcurr <= pend ; pcurr+=2)
852  {
853  cnt += *pcurr - *(pcurr - 1);
854  }
855  BM_ASSERT(cnt == gap_bit_count(buf));
856  return cnt;
857 }
858 
859 
860 
861 /*!
862  \brief Counts 1 bits in GAP buffer in the closed [left, right] range.
863  \param buf - GAP buffer pointer.
864  \param left - leftmost bit index to start from
865  \param right- rightmost bit index
866  \return Number of non-zero bits.
867  @ingroup gapfunc
868 */
869 template<typename T>
870 unsigned gap_bit_count_range(const T* const buf, T left, T right)
871 {
872  BM_ASSERT(left <= right);
873 
874  const T* pcurr = buf;
875  const T* pend = pcurr + (*pcurr >> 3);
876 
877  unsigned bits_counter = 0;
878  unsigned is_set;
879  unsigned start_pos = gap_bfind(buf, left, &is_set);
880  is_set = ~(is_set - 1u); // 0xFFF.. if true (mask for branchless code)
881 
882  pcurr = buf + start_pos;
883  if (right <= *pcurr) // we are in the target gap right now
884  {
885  bits_counter = unsigned(right - left + 1u) & is_set; // & is_set == if(is_set)
886  return bits_counter;
887  }
888  bits_counter += unsigned(*pcurr - left + 1u) & is_set;
889 
890  unsigned prev_gap = *pcurr++;
891  for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u)
892  {
893  bits_counter += (*pcurr - prev_gap) & is_set;
894  if (pcurr == pend)
895  return bits_counter;
896  prev_gap = *pcurr++;
897  }
898  bits_counter += unsigned(right - prev_gap) & is_set;
899  return bits_counter;
900 }
901 
902 
903 /*!
904  \brief Counts 1 bits in GAP buffer in the closed [0, right] range.
905  \param buf - GAP buffer pointer.
906  \param right- rightmost bit index
907  \return Number of non-zero bits.
908  @ingroup gapfunc
909 */
910 template<typename T>
911 unsigned gap_bit_count_to(const T* const buf, T right)
912 {
913  const T* pcurr = buf;
914  const T* pend = pcurr + (*pcurr >> 3);
915 
916  unsigned bits_counter = 0;
917  unsigned is_set = ~((unsigned(*buf) & 1u) - 1u); // 0xFFF.. if true (mask for branchless code)
918  BM_ASSERT(is_set == 0u || is_set == ~0u);
919  pcurr = buf + 1;
920 
921  if (right <= *pcurr) // we are in the target block right now
922  {
923  bits_counter = (right + 1u) & is_set; // & is_set == if (is_set)
924  return bits_counter;
925  }
926  bits_counter += (*pcurr + 1u) & is_set;
927 
928  unsigned prev_gap = *pcurr++;
929  for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u)
930  {
931  bits_counter += (*pcurr - prev_gap) & is_set;
932  if (pcurr == pend)
933  return bits_counter;
934  prev_gap = *pcurr++;
935  }
936  bits_counter += (right - prev_gap) & is_set;
937  return bits_counter;
938 }
939 
940 
941 /*!
942  D-GAP block for_each algorithm
943 
944  D-Gap Functor is called for each element but last one.
945 
946  \param gap_buf - GAP buffer
947  \param func - functor object
948 
949 */
950 template<class T, class Func>
951 void for_each_dgap(const T* gap_buf, Func& func)
952 {
953  const T* pcurr = gap_buf;
954  const T* pend = pcurr + (*pcurr >> 3);
955  ++pcurr;
956 
957  T prev = *pcurr;
958  func((T)(prev + 1)); // first element incremented to avoid 0
959  ++pcurr;
960  do
961  {
962  func((T)(*pcurr - prev)); // all others are [N] - [N-1]
963  prev = *pcurr;
964  } while (++pcurr < pend);
965 }
966 
967 /** d-Gap copy functor
968  @internal
969 */
970 template<typename T> struct d_copy_func
971 {
972  d_copy_func(T* dg_buf) : dgap_buf_(dg_buf) {}
973  void operator()(T dgap) { *dgap_buf_++ = dgap; }
974 
976 };
977 
978 /*!
979  \brief Convert GAP buffer into D-GAP buffer
980 
981  Delta GAP representation is DGAP[N] = GAP[N] - GAP[N-1]
982 
983  \param gap_buf - GAP buffer
984  \param dgap_buf - Delta-GAP buffer
985  \param copy_head - flag to copy GAP header
986 
987  \internal
988 
989  @ingroup gapfunc
990 */
991 template<typename T>
992 T* gap_2_dgap(const T* gap_buf, T* dgap_buf, bool copy_head=true)
993 {
994  if (copy_head) // copy GAP header
995  {
996  *dgap_buf++ = *gap_buf;
997  }
998 
999  d_copy_func<T> copy_func(dgap_buf);
1000  for_each_dgap<T, d_copy_func<T> >(gap_buf, copy_func);
1001  return copy_func.dgap_buf_;
1002 }
1003 
1004 /*!
1005  \brief Convert D-GAP buffer into GAP buffer
1006 
1007  GAP representation is GAP[N] = DGAP[N] + DGAP[N-1]
1008 
1009  \param dgap_buf - Delta-GAP buffer
1010  \param gap_header - GAP header word
1011  \param gap_buf - GAP buffer
1012 
1013  \internal
1014  @ingroup gapfunc
1015 */
1016 template<typename T>
1017 void dgap_2_gap(const T* dgap_buf, T* gap_buf, T gap_header=0)
1018 {
1019  BMREGISTER const T* pcurr = dgap_buf;
1020  unsigned len;
1021  if (!gap_header) // GAP header is already part of the stream
1022  {
1023  len = *pcurr >> 3;
1024  *gap_buf++ = *pcurr++; // copy GAP header
1025  }
1026  else // GAP header passed as a parameter
1027  {
1028  len = gap_header >> 3;
1029  *gap_buf++ = gap_header; // assign GAP header
1030  }
1031  --len; // last element is actually not encoded
1032  BMREGISTER const T* pend = pcurr + len;
1033 
1034  *gap_buf = *pcurr++; // copy first element
1035  if (*gap_buf == 0)
1036  *gap_buf = 65535; // fix +1 overflow
1037  else
1038  *gap_buf = *gap_buf - 1;
1039 
1040  for (++gap_buf; pcurr < pend; ++pcurr)
1041  {
1042  T prev = *(gap_buf-1); // don't remove temp(undef expression!)
1043  *gap_buf++ = *pcurr + prev;
1044  }
1045  *gap_buf = 65535; // add missing last element
1046 }
1047 
1048 
1049 /*!
1050  \brief Lexicographical comparison of GAP buffers.
1051  \param buf1 - First GAP buffer pointer.
1052  \param buf2 - Second GAP buffer pointer.
1053  \return <0 - less, =0 - equal, >0 - greater.
1054 
1055  @ingroup gapfunc
1056 */
1057 template<typename T> int gapcmp(const T* buf1, const T* buf2)
1058 {
1059  const T* pcurr1 = buf1;
1060  const T* pend1 = pcurr1 + (*pcurr1 >> 3);
1061  unsigned bitval1 = *buf1 & 1;
1062  ++pcurr1;
1063 
1064  const T* pcurr2 = buf2;
1065  unsigned bitval2 = *buf2 & 1;
1066  ++pcurr2;
1067 
1068  while (pcurr1 <= pend1)
1069  {
1070  if (*pcurr1 == *pcurr2)
1071  {
1072  if (bitval1 != bitval2)
1073  {
1074  return (bitval1) ? 1 : -1;
1075  }
1076  }
1077  else
1078  {
1079  if (bitval1 == bitval2)
1080  {
1081  if (bitval1)
1082  {
1083  return (*pcurr1 < *pcurr2) ? -1 : 1;
1084  }
1085  else
1086  {
1087  return (*pcurr1 < *pcurr2) ? 1 : -1;
1088  }
1089  }
1090  else
1091  {
1092  return (bitval1) ? 1 : -1;
1093  }
1094  }
1095 
1096  ++pcurr1; ++pcurr2;
1097 
1098  bitval1 ^= 1;
1099  bitval2 ^= 1;
1100  }
1101 
1102  return 0;
1103 }
1104 
1105 
1106 /*!
1107  \brief Abstract operation for GAP buffers.
1108  Receives functor F as a template argument
1109  \param dest - destination memory buffer.
1110  \param vect1 - operand 1 GAP encoded buffer.
1111  \param vect1_mask - XOR mask for starting bitflag for vector1
1112  can be 0 or 1 (1 inverts the vector)
1113  \param vect2 - operand 2 GAP encoded buffer.
1114  \param vect2_mask - same as vect1_mask
1115  \param f - operation functor.
1116  \param dlen - destination length after the operation
1117 
1118  \note Internal function.
1119  @internal
1120 
1121  @ingroup gapfunc
1122 */
1123 template<typename T, class F>
1124 void gap_buff_op(T* BMRESTRICT dest,
1125  const T* BMRESTRICT vect1,
1126  unsigned vect1_mask,
1127  const T* BMRESTRICT vect2,
1128  unsigned vect2_mask,
1129  F& f,
1130  unsigned& dlen)
1131 {
1132  BMREGISTER const T* cur1 = vect1;
1133  BMREGISTER const T* cur2 = vect2;
1134 
1135  T bitval1 = (T)((*cur1++ & 1) ^ vect1_mask);
1136  T bitval2 = (T)((*cur2++ & 1) ^ vect2_mask);
1137 
1138  T bitval = (T) f(bitval1, bitval2);
1139  T bitval_prev = bitval;
1140 
1141  BMREGISTER T* res = dest;
1142  *res = bitval;
1143  ++res;
1144 
1145  while (1)
1146  {
1147  bitval = (T) f(bitval1, bitval2);
1148 
1149  // Check if GAP value changes and we need to
1150  // start the next one.
1151  if (bitval != bitval_prev)
1152  {
1153  ++res;
1154  bitval_prev = bitval;
1155  }
1156 
1157  if (*cur1 < *cur2)
1158  {
1159  *res = *cur1;
1160  ++cur1;
1161  bitval1 ^= 1;
1162  }
1163  else // >=
1164  {
1165  *res = *cur2;
1166  if (*cur2 < *cur1)
1167  {
1168  bitval2 ^= 1;
1169  }
1170  else // equal
1171  {
1172  if (*cur2 == (bm::gap_max_bits - 1))
1173  {
1174  break;
1175  }
1176 
1177  ++cur1;
1178  bitval1 ^= 1;
1179  bitval2 ^= 1;
1180  }
1181  ++cur2;
1182  }
1183 
1184  } // while
1185 
1186  dlen = (unsigned)(res - dest);
1187  *dest = (T)((*dest & 7) + (dlen << 3));
1188 
1189 }
1190 
1191 /*!
1192  \brief Abstract distance test operation for GAP buffers.
1193  Receives functor F as a template argument
1194  \param vect1 - operand 1 GAP encoded buffer.
1195  \param vect1_mask - XOR mask for starting bitflag for vector1
1196  can be 0 or 1 (1 inverts the vector)
1197  \param vect2 - operand 2 GAP encoded buffer.
1198  \param vect2_mask - same as vect1_mask
1199  \param f - operation functor.
1200  \note Internal function.
1201  \return non zero value if operation result returns any 1 bit
1202 
1203  @ingroup gapfunc
1204 */
1205 template<typename T, class F>
1206 unsigned gap_buff_any_op(const T* BMRESTRICT vect1,
1207  unsigned vect1_mask,
1208  const T* BMRESTRICT vect2,
1209  unsigned vect2_mask,
1210  F f)
1211 {
1212  BMREGISTER const T* cur1 = vect1;
1213  BMREGISTER const T* cur2 = vect2;
1214 
1215  unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
1216  unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
1217 
1218  unsigned bitval = f(bitval1, bitval2);
1219  if (bitval)
1220  return bitval;
1221  unsigned bitval_prev = bitval;
1222 
1223  while (1)
1224  {
1225  bitval = f(bitval1, bitval2);
1226  if (bitval)
1227  return bitval;
1228 
1229  if (bitval != bitval_prev)
1230  bitval_prev = bitval;
1231 
1232  if (*cur1 < *cur2)
1233  {
1234  ++cur1;
1235  bitval1 ^= 1;
1236  }
1237  else // >=
1238  {
1239  if (*cur2 < *cur1)
1240  {
1241  bitval2 ^= 1;
1242  }
1243  else // equal
1244  {
1245  if (*cur2 == (bm::gap_max_bits - 1))
1246  {
1247  break;
1248  }
1249 
1250  ++cur1;
1251  bitval1 ^= 1;
1252  bitval2 ^= 1;
1253  }
1254  ++cur2;
1255  }
1256 
1257  } // while
1258 
1259  return 0;
1260 }
1261 
1262 
1263 
1264 /*!
1265  \brief Abstract distance(similarity) operation for GAP buffers.
1266  Receives functor F as a template argument
1267  \param vect1 - operand 1 GAP encoded buffer.
1268  \param vect2 - operand 2 GAP encoded buffer.
1269  \param f - operation functor.
1270  \note Internal function.
1271 
1272  @ingroup gapfunc
1273 */
1274 template<typename T, class F>
1275 unsigned gap_buff_count_op(const T* vect1, const T* vect2, F f)
1276 {
1277  unsigned count;// = 0;
1278  const T* cur1 = vect1;
1279  const T* cur2 = vect2;
1280 
1281  unsigned bitval1 = (*cur1++ & 1);
1282  unsigned bitval2 = (*cur2++ & 1);
1283  unsigned bitval = count = f(bitval1, bitval2);
1284  unsigned bitval_prev = bitval;
1285 
1286  //if (bitval) ++count;
1287 
1288  T res, res_prev;
1289  res = res_prev = 0;
1290 
1291  while (1)
1292  {
1293  bitval = f(bitval1, bitval2);
1294 
1295  // Check if GAP value changes and we need to
1296  // start the next one.
1297  if (bitval != bitval_prev)
1298  {
1299  bitval_prev = bitval;
1300  res_prev = res;
1301  }
1302 
1303  if (*cur1 < *cur2)
1304  {
1305  res = *cur1;
1306  if (bitval)
1307  {
1308  count += res - res_prev;
1309  res_prev = res;
1310  }
1311  ++cur1;
1312  bitval1 ^= 1;
1313  }
1314  else // >=
1315  {
1316  res = *cur2;
1317  if (bitval)
1318  {
1319  count += res - res_prev;
1320  res_prev = res;
1321  }
1322  if (*cur2 < *cur1)
1323  {
1324  bitval2 ^= 1;
1325  }
1326  else // equal
1327  {
1328  if (*cur2 == (bm::gap_max_bits - 1))
1329  {
1330  break;
1331  }
1332 
1333  ++cur1;
1334  bitval1 ^= 1;
1335  bitval2 ^= 1;
1336  }
1337  ++cur2;
1338  }
1339 
1340  } // while
1341 
1342  return count;
1343 }
1344 
1345 
1346 
1347 /*!
1348  \brief Sets or clears bit in the GAP buffer.
1349 
1350  \param val - new bit value
1351  \param buf - GAP buffer.
1352  \param pos - Index of bit to set.
1353  \param is_set - (OUT) flag if bit was actually set.
1354 
1355  \return New GAP buffer length.
1356 
1357  @ingroup gapfunc
1358 */
1359 template<typename T> unsigned gap_set_value(unsigned val,
1360  T* BMRESTRICT buf,
1361  unsigned pos,
1362  unsigned* BMRESTRICT is_set)
1363 {
1364  BM_ASSERT(pos < bm::gap_max_bits);
1365  unsigned curr = gap_bfind(buf, pos, is_set);
1366 
1367  BMREGISTER T end = (T)(*buf >> 3);
1368  if (*is_set == val)
1369  {
1370  *is_set = 0;
1371  return end;
1372  }
1373  *is_set = 1;
1374 
1375  BMREGISTER T* pcurr = buf + curr;
1376  BMREGISTER T* pprev = pcurr - 1;
1377  BMREGISTER T* pend = buf + end;
1378 
1379  // Special case, first bit GAP operation. There is no platform beside it.
1380  // initial flag must be inverted.
1381  if (pos == 0)
1382  {
1383  *buf ^= 1;
1384  if ( buf[1] ) // We need to insert a 1 bit platform here.
1385  {
1386  ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
1387  buf[1] = 0;
1388  ++end;
1389  }
1390  else // Only 1 bit in the GAP. We need to delete the first GAP.
1391  {
1392  pprev = buf + 1;
1393  pcurr = pprev + 1;
1394  do
1395  {
1396  *pprev++ = *pcurr++;
1397  } while (pcurr < pend);
1398  --end;
1399  }
1400  }
1401  else if (curr > 1 && ((unsigned)(*pprev))+1 == pos) // Left border bit
1402  {
1403  ++(*pprev);
1404  if (*pprev == *pcurr) // Curr. GAP to be merged with prev.GAP.
1405  {
1406  --end;
1407  if (pcurr != pend) // GAP merge: 2 GAPS to be deleted
1408  {
1409  --end;
1410  ++pcurr;
1411  do
1412  {
1413  *pprev++ = *pcurr++;
1414  } while (pcurr < pend);
1415  }
1416  }
1417  }
1418  else if (*pcurr == pos) // Rightmost bit in the GAP. Border goes left.
1419  {
1420  --(*pcurr);
1421  if (pcurr == pend)
1422  {
1423  ++end;
1424  }
1425  }
1426  else // Worst case we need to split current block.
1427  {
1428  ::memmove(pcurr+2, pcurr,(end - curr + 1)*sizeof(T));
1429  *pcurr++ = (T)(pos - 1);
1430  *pcurr = (T)pos;
1431  end = (T)(end + 2);
1432  }
1433 
1434  // Set correct length word.
1435  *buf = (T)((*buf & 7) + (end << 3));
1436 
1437  buf[end] = bm::gap_max_bits - 1;
1438  return end;
1439 }
1440 
1441 /*!
1442  \brief Add new value to the end of GAP buffer.
1443 
1444  \param buf - GAP buffer.
1445  \param pos - Index of bit to set.
1446 
1447  \return New GAP buffer length.
1448 
1449  @ingroup gapfunc
1450 */
1451 template<typename T>
1452 unsigned gap_add_value(T* buf, unsigned pos)
1453 {
1454  BM_ASSERT(pos < bm::gap_max_bits);
1455 
1456  BMREGISTER T end = (T)(*buf >> 3);
1457  T curr = end;
1458  BMREGISTER T* pcurr = buf + end;
1459  BMREGISTER T* pend = pcurr;
1460  BMREGISTER T* pprev = pcurr - 1;
1461 
1462  // Special case, first bit GAP operation. There is no platform beside it.
1463  // initial flag must be inverted.
1464  if (pos == 0)
1465  {
1466  *buf ^= 1;
1467  if ( buf[1] ) // We need to insert a 1 bit platform here.
1468  {
1469  ::memmove(&buf[2], &buf[1], (end - 1) * sizeof(gap_word_t));
1470  buf[1] = 0;
1471  ++end;
1472  }
1473  else // Only 1 bit in the GAP. We need to delete the first GAP.
1474  {
1475  pprev = buf + 1;
1476  pcurr = pprev + 1;
1477  do
1478  {
1479  *pprev++ = *pcurr++;
1480  } while (pcurr < pend);
1481  --end;
1482  }
1483  }
1484  else if (((unsigned)(*pprev))+1 == pos && (curr > 1) ) // Left border bit
1485  {
1486  ++(*pprev);
1487  if (*pprev == *pcurr) // Curr. GAP to be merged with prev.GAP.
1488  {
1489  --end;
1490  if (pcurr != pend) // GAP merge: 2 GAPS to be deleted
1491  {
1492  // TODO: should never get here...
1493  --end;
1494  ++pcurr;
1495  do
1496  {
1497  *pprev++ = *pcurr++;
1498  } while (pcurr < pend);
1499  }
1500  }
1501  }
1502  else if (*pcurr == pos) // Rightmost bit in the GAP. Border goes left.
1503  {
1504  --(*pcurr);
1505  if (pcurr == pend)
1506  {
1507  ++end;
1508  }
1509  }
1510  else // Worst case we need to split current block.
1511  {
1512  *pcurr++ = (T)(pos - 1);
1513  *pcurr = (T)pos;
1514  end = (T)(end+2);
1515  }
1516 
1517  // Set correct length word.
1518  *buf = (T)((*buf & 7) + (end << 3));
1519 
1520  buf[end] = bm::gap_max_bits - 1;
1521  return end;
1522 }
1523 
1524 /*!
1525  \brief Convert array to GAP buffer.
1526 
1527  \param buf - GAP buffer.
1528  \param arr - array of values to set
1529  \param len - length of the array
1530 
1531  \return New GAP buffer length.
1532 
1533  @ingroup gapfunc
1534 */
1535 
1536 template<typename T>
1537 unsigned gap_set_array(T* buf, const T* arr, unsigned len)
1538 {
1539  *buf = (T)((*buf & 6u) + (1u << 3)); // gap header setup
1540 
1541  T* pcurr = buf + 1;
1542 
1543  unsigned i = 0;
1544  T curr = arr[i];
1545  if (curr != 0) // need to add the first gap: (0 to arr[0]-1)
1546  {
1547  *pcurr = (T)(curr - 1);
1548  ++pcurr;
1549  }
1550  else
1551  {
1552  ++(*buf); // GAP starts with 1
1553  }
1554  T prev = curr;
1555  T acc = prev;
1556 
1557  for (i = 1; i < len; ++i)
1558  {
1559  curr = arr[i];
1560  if (curr == prev + 1)
1561  {
1562  ++acc;
1563  prev = curr;
1564  }
1565  else
1566  {
1567  *pcurr++ = acc;
1568  acc = curr;
1569  *pcurr++ = (T)(curr-1);
1570  }
1571  prev = curr;
1572  }
1573  *pcurr = acc;
1574  if (acc != bm::gap_max_bits - 1)
1575  {
1576  ++pcurr;
1577  *pcurr = bm::gap_max_bits - 1;
1578  }
1579 
1580  unsigned end = unsigned(pcurr - buf);
1581 
1582  *buf = (T)((*buf & 7) + (end << 3));
1583  return end+1;
1584 }
1585 
1586 
1587 //------------------------------------------------------------------------
1588 
1589 /**
1590  \brief Compute number of GAPs in bit-array
1591  \param arr - array of BITs
1592  \param len - array length
1593 
1594  @ingroup gapfunc
1595 */
1596 template<typename T>
1597 unsigned bit_array_compute_gaps(const T* arr,
1598  unsigned len)
1599 {
1600  unsigned gap_count = 1;
1601  T prev = arr[0];
1602  if (prev > 0)
1603  ++gap_count;
1604  for (unsigned i = 1; i < len; ++i)
1605  {
1606  T curr = arr[i];
1607  if (curr != prev + 1)
1608  {
1609  gap_count += 2;
1610  }
1611  prev = curr;
1612  }
1613  return gap_count;
1614 }
1615 
1616 
1617 //------------------------------------------------------------------------
1618 
1619 /**
1620  \brief Searches for the next 1 bit in the GAP block
1621  \param buf - GAP buffer
1622  \param nbit - bit index to start checking from.
1623  \param prev - returns previously checked value
1624 
1625  @ingroup gapfunc
1626 */
1627 template<typename T> int gap_find_in_block(const T* buf,
1628  unsigned nbit,
1629  bm::id_t* prev)
1630 {
1631  BM_ASSERT(nbit < bm::gap_max_bits);
1632 
1633  unsigned bitval;
1634  unsigned gap_idx = bm::gap_bfind(buf, nbit, &bitval);
1635 
1636  if (bitval) // positive block.
1637  {
1638  return 1;
1639  }
1640 
1641  BMREGISTER unsigned val = buf[gap_idx] + 1;
1642  *prev += val - nbit;
1643 
1644  return (val != bm::gap_max_bits); // no bug here.
1645 }
1646 
1647 /*!
1648  \brief Set 1 bit in a block
1649 
1650  @ingroup bitfunc
1651 */
1652 BMFORCEINLINE void set_bit(unsigned* dest, unsigned bitpos)
1653 {
1654  unsigned nbit = unsigned(bitpos & bm::set_block_mask);
1655  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1656  nbit &= bm::set_word_mask;
1657  dest[nword] |= unsigned(1 << nbit);
1658 }
1659 
1660 /*!
1661  \brief Test 1 bit in a block
1662 
1663  @ingroup bitfunc
1664 */
1665 BMFORCEINLINE unsigned test_bit(const unsigned* block, unsigned bitpos)
1666 {
1667  unsigned nbit = unsigned(bitpos & bm::set_block_mask);
1668  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1669  nbit &= bm::set_word_mask;
1670  return (block[nword] >> nbit) & 1u;
1671 }
1672 
1673 
1674 /*!
1675  \brief Sets bits to 1 in the bitblock.
1676  \param dest - Bitset buffer.
1677  \param bitpos - Offset of the start bit.
1678  \param bitcount - number of bits to set.
1679 
1680  @ingroup bitfunc
1681 */
1682 inline void or_bit_block(unsigned* dest,
1683  unsigned bitpos,
1684  unsigned bitcount)
1685 {
1686  unsigned nbit = unsigned(bitpos & bm::set_block_mask);
1687  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1688  nbit &= bm::set_word_mask;
1689 
1690  bm::word_t* word = dest + nword;
1691 
1692  if (bitcount == 1) // special case (only 1 bit to set)
1693  {
1694  *word |= unsigned(1 << nbit);
1695  return;
1696  }
1697 
1698  if (nbit) // starting position is not aligned
1699  {
1700  unsigned right_margin = nbit + bitcount;
1701 
1702  // here we checking if we setting bits only in the current
1703  // word. Example: 00111000000000000000000000000000 (32 bits word)
1704 
1705  if (right_margin < 32)
1706  {
1707  unsigned mask =
1709  block_set_table<true>::_left[right_margin-1];
1710  *word |= mask;
1711  return; // we are done
1712  }
1713  else
1714  {
1715  *word |= block_set_table<true>::_right[nbit];
1716  bitcount -= 32 - nbit;
1717  }
1718  ++word;
1719  }
1720 
1721  // now we are word aligned, lets find out how many words we
1722  // can now turn ON using loop
1723 
1724  for ( ;bitcount >= 32; bitcount -= 32)
1725  {
1726  *word++ = 0xffffffff;
1727  }
1728 
1729  if (bitcount)
1730  {
1731  *word |= block_set_table<true>::_left[bitcount-1];
1732  }
1733 }
1734 
1735 
1736 /*!
1737  \brief SUB (AND NOT) bit interval to 1 in the bitblock.
1738  \param dest - Bitset buffer.
1739  \param bitpos - Offset of the start bit.
1740  \param bitcount - number of bits to set.
1741 
1742  @ingroup bitfunc
1743 */
1744 inline void sub_bit_block(unsigned* dest,
1745  unsigned bitpos,
1746  unsigned bitcount)
1747 {
1748  unsigned nbit = unsigned(bitpos & bm::set_block_mask);
1749  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1750  nbit &= bm::set_word_mask;
1751 
1752  bm::word_t* word = dest + nword;
1753 
1754  if (bitcount == 1) // special case (only 1 bit to set)
1755  {
1756  *word &= ~unsigned(1 << nbit);
1757  return;
1758  }
1759 
1760  if (nbit) // starting position is not aligned
1761  {
1762  unsigned right_margin = nbit + bitcount;
1763 
1764  // here we checking if we setting bits only in the current
1765  // word. Example: 00111000000000000000000000000000 (32 bits word)
1766 
1767  if (right_margin < 32)
1768  {
1769  unsigned mask =
1771  block_set_table<true>::_left[right_margin-1];
1772  *word &= ~mask;
1773  return; // we are done
1774  }
1775  else
1776  {
1777  *word &= ~block_set_table<true>::_right[nbit];
1778  bitcount -= 32 - nbit;
1779  }
1780  ++word;
1781  }
1782 
1783  // now we are word aligned, lets find out how many words we
1784  // can now turn ON using loop
1785 
1786  for ( ;bitcount >= 32; bitcount -= 32)
1787  {
1788  *word++ = 0;
1789  }
1790 
1791  if (bitcount)
1792  {
1793  *word &= ~block_set_table<true>::_left[bitcount-1];
1794  }
1795 }
1796 
1797 
1798 /*!
1799  \brief XOR bit interval to 1 in the bitblock.
1800  \param dest - Bitset buffer.
1801  \param bitpos - Offset of the start bit.
1802  \param bitcount - number of bits to set.
1803 
1804  @ingroup bitfunc
1805 */
1806 inline void xor_bit_block(unsigned* dest,
1807  unsigned bitpos,
1808  unsigned bitcount)
1809 {
1810  unsigned nbit = unsigned(bitpos & bm::set_block_mask);
1811  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1812  nbit &= bm::set_word_mask;
1813 
1814  bm::word_t* word = dest + nword;
1815 
1816  if (bitcount == 1) // special case (only 1 bit to set)
1817  {
1818  *word ^= unsigned(1 << nbit);
1819  return;
1820  }
1821 
1822  if (nbit) // starting position is not aligned
1823  {
1824  unsigned right_margin = nbit + bitcount;
1825 
1826  // here we checking if we setting bits only in the current
1827  // word. Example: 00111000000000000000000000000000 (32 bits word)
1828 
1829  if (right_margin < 32)
1830  {
1831  unsigned mask =
1833  block_set_table<true>::_left[right_margin-1];
1834  *word ^= mask;
1835  return; // we are done
1836  }
1837  else
1838  {
1839  *word ^= block_set_table<true>::_right[nbit];
1840  bitcount -= 32 - nbit;
1841  }
1842  ++word;
1843  }
1844 
1845  // now we are word aligned, lets find out how many words we
1846  // can now turn ON using loop
1847 
1848  for ( ;bitcount >= 32; bitcount -= 32)
1849  {
1850  *word++ ^= 0xffffffff;
1851  }
1852 
1853  if (bitcount)
1854  {
1855  *word ^= block_set_table<true>::_left[bitcount-1];
1856  }
1857 }
1858 
1859 
1860 /*!
1861  \brief SUB (AND NOT) GAP block to bitblock.
1862  \param dest - bitblock buffer pointer.
1863  \param buf - GAP buffer pointer.
1864 
1865  @ingroup gapfunc
1866 */
1867 template<typename T>
1868 void gap_sub_to_bitset(unsigned* dest, const T* buf)
1869 {
1870  BMREGISTER const T* pcurr = buf;
1871  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
1872  ++pcurr;
1873 
1874  if (*buf & 1) // Starts with 1
1875  {
1876  sub_bit_block(dest, 0, *pcurr + 1);
1877  ++pcurr;
1878  }
1879  ++pcurr; // now we are in GAP "1" again
1880 
1881  while (pcurr <= pend)
1882  {
1883  unsigned bitpos = *(pcurr-1) + 1;
1884  BM_ASSERT(*pcurr > *(pcurr-1));
1885  unsigned gap_len = *pcurr - *(pcurr-1);
1886  sub_bit_block(dest, bitpos, gap_len);
1887  pcurr += 2;
1888  }
1889 }
1890 
1891 
1892 /*!
1893  \brief XOR GAP block to bitblock.
1894  \param dest - bitblock buffer pointer.
1895  \param buf - GAP buffer pointer.
1896 
1897  @ingroup gapfunc
1898 */
1899 template<typename T>
1900 void gap_xor_to_bitset(unsigned* dest, const T* buf)
1901 {
1902  BMREGISTER const T* pcurr = buf;
1903  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
1904  ++pcurr;
1905 
1906  if (*buf & 1) // Starts with 1
1907  {
1908  xor_bit_block(dest, 0, *pcurr + 1);
1909  ++pcurr;
1910  }
1911  ++pcurr; // now we are in GAP "1" again
1912 
1913  while (pcurr <= pend)
1914  {
1915  unsigned bitpos = *(pcurr-1) + 1;
1916  BM_ASSERT(*pcurr > *(pcurr-1));
1917  unsigned gap_len = *pcurr - *(pcurr-1);
1918  xor_bit_block(dest, bitpos, gap_len);
1919  pcurr += 2;
1920  }
1921 }
1922 
1923 
1924 /*!
1925  \brief Adds(OR) GAP block to bitblock.
1926  \param dest - bitblock buffer pointer.
1927  \param buf - GAP buffer pointer.
1928 
1929  @ingroup gapfunc
1930 */
1931 template<typename T>
1932 void gap_add_to_bitset(unsigned* dest, const T* buf)
1933 {
1934  BMREGISTER const T* pcurr = buf;
1935  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
1936  ++pcurr;
1937 
1938  if (*buf & 1) // Starts with 1
1939  {
1940  or_bit_block(dest, 0, *pcurr + 1);
1941  ++pcurr;
1942  }
1943  ++pcurr; // now we are in GAP "1" again
1944 
1945  while (pcurr <= pend)
1946  {
1947  unsigned bitpos = *(pcurr-1) + 1;
1948  BM_ASSERT(*pcurr > *(pcurr-1));
1949  unsigned gap_len = *pcurr - *(pcurr-1);
1950  or_bit_block(dest, bitpos, gap_len);
1951  pcurr += 2;
1952  }
1953 }
1954 
1955 
1956 /*!
1957  \brief ANDs GAP block to bitblock.
1958  \param dest - bitblock buffer pointer.
1959  \param buf - GAP buffer pointer.
1960 
1961  @ingroup gapfunc
1962 */
1963 template<typename T>
1964 void gap_and_to_bitset(unsigned* dest, const T* buf)
1965 {
1966  BMREGISTER const T* pcurr = buf;
1967  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
1968  ++pcurr;
1969 
1970  if (! (*buf & 1) ) // Starts with 0
1971  {
1972  // Instead of AND we can SUB 0 gaps here
1973  sub_bit_block(dest, 0, *pcurr + 1);
1974  ++pcurr;
1975  }
1976  ++pcurr; // now we are in GAP "0" again
1977 
1978  while (pcurr <= pend)
1979  {
1980  unsigned bitpos = *(pcurr-1) + 1;
1981  BM_ASSERT(*pcurr > *(pcurr-1));
1982  unsigned gap_len = *pcurr - *(pcurr-1);
1983  sub_bit_block(dest, bitpos, gap_len);
1984  pcurr += 2;
1985  }
1986 }
1987 
1988 
1989 /*!
1990  \brief Compute bitcount of bit block AND masked by GAP block
1991  \param block - bitblock buffer pointer
1992  \param buf - GAP buffer pointer
1993  \return bitcount - cardinality of the AND product
1994 
1995  @ingroup gapfunc
1996 */
1997 template<typename T>
1998 bm::id_t gap_bitset_and_count(const unsigned* block, const T* buf)
1999 {
2000  BM_ASSERT(block);
2001 
2002  const T* pcurr = buf;
2003  const T* pend = pcurr + (*pcurr >> 3);
2004  ++pcurr;
2005 
2006  bm::id_t count = 0;
2007  if (*buf & 1) // Starts with 1
2008  {
2009  count += bit_block_calc_count_range(block, 0, *pcurr);
2010  ++pcurr;
2011  }
2012  ++pcurr; // now we are in GAP "1" again
2013  for (;pcurr <= pend; pcurr += 2)
2014  {
2015  count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
2016  }
2017  return count;
2018 }
2019 
2020 
2021 /*!
2022  \brief Bitcount test of bit block AND masked by GAP block.
2023  \param block - bitblock buffer pointer
2024  \param buf - GAP buffer pointer
2025  \return non-zero value if AND produces any result
2026 
2027  @ingroup gapfunc
2028 */
2029 template<typename T>
2030 bm::id_t gap_bitset_and_any(const unsigned* block, const T* buf)
2031 {
2032  BM_ASSERT(block);
2033 
2034  BMREGISTER const T* pcurr = buf;
2035  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2036  ++pcurr;
2037 
2038  bm::id_t count = 0;
2039  if (*buf & 1) // Starts with 1
2040  {
2041  count += bit_block_any_range(block, 0, *pcurr);
2042  if (count)
2043  return count;
2044  ++pcurr;
2045  }
2046  ++pcurr; // now we are in GAP "1" again
2047 
2048  while (pcurr <= pend)
2049  {
2050  bm::id_t c = bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
2051  count += c;
2052  if (count)
2053  break;
2054  pcurr += 2;
2055  }
2056  return count;
2057 }
2058 
2059 
2060 
2061 /*!
2062  \brief Compute bitcount of bit block SUB masked by GAP block.
2063  \param block - bitblock buffer pointer.
2064  \param buf - GAP buffer pointer.
2065  \return bit-count result of AND NOT operation
2066 
2067  @ingroup gapfunc
2068 */
2069 template<typename T>
2070 bm::id_t gap_bitset_sub_count(const unsigned* block, const T* buf)
2071 {
2072  BM_ASSERT(block);
2073 
2074  BMREGISTER const T* pcurr = buf;
2075  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2076  ++pcurr;
2077 
2078  bm::id_t count = 0;
2079 
2080  if (!(*buf & 1)) // Starts with 0
2081  {
2082  count += bit_block_calc_count_range(block, 0, *pcurr);
2083  ++pcurr;
2084  }
2085  ++pcurr; // now we are in GAP "0" again
2086 
2087  for (;pcurr <= pend; pcurr+=2)
2088  {
2089  count += bit_block_calc_count_range(block, *(pcurr-1)+1, *pcurr);
2090  }
2091  return count;
2092 }
2093 
2094 
2095 /*!
2096  \brief Compute bitcount test of bit block SUB masked by GAP block
2097  \param block - bitblock buffer pointer
2098  \param buf - GAP buffer pointer
2099  \return non-zero value if AND NOT produces any 1 bits
2100 
2101  @ingroup gapfunc
2102 */
2103 template<typename T>
2104 bm::id_t gap_bitset_sub_any(const unsigned* block, const T* buf)
2105 {
2106  BM_ASSERT(block);
2107 
2108  BMREGISTER const T* pcurr = buf;
2109  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2110  ++pcurr;
2111 
2112  bm::id_t count = 0;
2113 
2114  if (!(*buf & 1)) // Starts with 0
2115  {
2116  count += bit_block_any_range(block, 0, *pcurr);
2117  if (count)
2118  return count;
2119  ++pcurr;
2120  }
2121  ++pcurr; // now we are in GAP "0" again
2122 
2123  for (;pcurr <= pend; pcurr+=2)
2124  {
2125  count += bit_block_any_range(block, *(pcurr-1)+1, *pcurr);
2126  if (count)
2127  return count;
2128  }
2129  return count;
2130 }
2131 
2132 
2133 
2134 /*!
2135  \brief Compute bitcount of bit block XOR masked by GAP block
2136  \param block - bitblock buffer pointer
2137  \param buf - GAP buffer pointer
2138  \return bit count value of XOR operation
2139 
2140  @ingroup gapfunc
2141 */
2142 template<typename T>
2143 bm::id_t gap_bitset_xor_count(const unsigned* block, const T* buf)
2144 {
2145  BM_ASSERT(block);
2146 
2147  BMREGISTER const T* pcurr = buf;
2148  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2149  ++pcurr;
2150 
2151  unsigned bitval = *buf & 1;
2152 
2153  BMREGISTER bm::id_t count = bit_block_calc_count_range(block, 0, *pcurr);
2154  if (bitval)
2155  {
2156  count = *pcurr + 1 - count;
2157  }
2158 
2159  for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
2160  {
2161  T prev = (T)(*(pcurr-1)+1);
2162  bm::id_t c = bit_block_calc_count_range(block, prev, *pcurr);
2163 
2164  if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
2165  {
2166  c = (*pcurr - prev + 1) - c;
2167  }
2168  count += c;
2169  }
2170  return count;
2171 }
2172 
2173 /*!
2174  \brief Compute bitcount test of bit block XOR masked by GAP block.
2175  \param block - bitblock buffer pointer
2176  \param buf - GAP buffer pointer
2177  \return non-zero value if XOR returns anything
2178 
2179  @ingroup gapfunc
2180 */
2181 template<typename T>
2182 bm::id_t gap_bitset_xor_any(const unsigned* block, const T* buf)
2183 {
2184  BM_ASSERT(block);
2185 
2186  BMREGISTER const T* pcurr = buf;
2187  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2188  ++pcurr;
2189 
2190  unsigned bitval = *buf & 1;
2191 
2192  BMREGISTER bm::id_t count = bit_block_any_range(block, 0, *pcurr);
2193  if (bitval)
2194  {
2195  count = *pcurr + 1 - count;
2196  }
2197 
2198  for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
2199  {
2200  T prev = (T)(*(pcurr-1)+1);
2201  bm::id_t c = bit_block_any_range(block, prev, *pcurr);
2202 
2203  if (bitval) // 1 gap; means Result = Total_Bits - BitCount;
2204  {
2205  c = (*pcurr - prev + 1) - c;
2206  }
2207 
2208  count += c;
2209  if (count)
2210  return count;
2211  }
2212  return count;
2213 }
2214 
2215 
2216 
2217 /*!
2218  \brief Compute bitcount of bit block OR masked by GAP block.
2219  \param block - bitblock buffer pointer.
2220  \param buf - GAP buffer pointer.
2221  \return bit count of OR
2222 
2223  @ingroup gapfunc
2224 */
2225 template<typename T>
2226 bm::id_t gap_bitset_or_count(const unsigned* block, const T* buf)
2227 {
2228  BM_ASSERT(block);
2229 
2230  BMREGISTER const T* pcurr = buf;
2231  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2232  ++pcurr;
2233 
2234  unsigned bitval = *buf & 1;
2235 
2236  BMREGISTER bm::id_t count;
2237  if (bitval)
2238  {
2239  count = *pcurr + 1;
2240  }
2241  else
2242  {
2243  count = bit_block_calc_count_range(block, 0, *pcurr);
2244  }
2245 
2246  for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
2247  {
2248  T prev = (T)(*(pcurr-1)+1);
2249  bm::id_t c;
2250 
2251  if (bitval)
2252  {
2253  c = (*pcurr - prev + 1);
2254  }
2255  else
2256  {
2257  c = bit_block_calc_count_range(block, prev, *pcurr);
2258  }
2259 
2260  count += c;
2261  }
2262  return count;
2263 }
2264 
2265 /*!
2266  \brief Compute bitcount test of bit block OR masked by GAP block
2267  \param block - bitblock buffer pointer
2268  \param buf - GAP buffer pointer
2269  \return non zero value if union (OR) returns anything
2270 
2271  @ingroup gapfunc
2272 */
2273 template<typename T>
2274 bm::id_t gap_bitset_or_any(const unsigned* block, const T* buf)
2275 {
2276  BM_ASSERT(block);
2277 
2278  BMREGISTER const T* pcurr = buf;
2279  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2280  ++pcurr;
2281 
2282  unsigned bitval = *buf & 1;
2283 
2284  BMREGISTER bm::id_t count;
2285  if (bitval)
2286  {
2287  count = *pcurr + 1;
2288  }
2289  else
2290  {
2291  count = bit_block_any_range(block, 0, *pcurr);
2292  }
2293 
2294  for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
2295  {
2296  T prev = (T)(*(pcurr-1)+1);
2297  bm::id_t c;
2298 
2299  if (bitval)
2300  {
2301  c = (*pcurr - prev + 1);
2302  }
2303  else
2304  {
2305  c = bit_block_any_range(block, prev, *pcurr);
2306  }
2307  count += c;
2308  if (count)
2309  return count;
2310  }
2311  return count;
2312 }
2313 
2314 
2315 
2316 /*!
2317  \brief Bitblock memset operation.
2318 
2319  \param dst - destination block.
2320  \param value - value to set.
2321 
2322  @ingroup bitfunc
2323 */
2324 inline
2326 {
2327 //#ifdef BMVECTOPT
2328 // VECT_SET_BLOCK(dst, dst + bm::set_block_size, value);
2329 //#else
2330  ::memset(dst, value, bm::set_block_size * sizeof(bm::word_t));
2331 //#endif
2332 }
2333 
2334 
2335 /*!
2336  \brief GAP block to bitblock conversion.
2337  \param dest - bitblock buffer pointer.
2338  \param buf - GAP buffer pointer.
2339 
2340  @ingroup gapfunc
2341 */
2342 template<typename T>
2343 void gap_convert_to_bitset(unsigned* dest, const T* buf)
2344 {
2345  bit_block_set(dest, 0);
2346  gap_add_to_bitset(dest, buf);
2347 }
2348 
2349 
2350 /*!
2351  \brief GAP block to bitblock conversion.
2352  \param dest - bitblock buffer pointer.
2353  \param buf - GAP buffer pointer.
2354  \param dest_len - length/size of the destination buffer.
2355 
2356  @ingroup gapfunc
2357 */
2358 template<typename T>
2359 void gap_convert_to_bitset(unsigned* dest, const T* buf, unsigned dest_len)
2360 {
2361  ::memset(dest, 0, dest_len * sizeof(unsigned));
2362  gap_add_to_bitset(dest, buf);
2363 }
2364 
2365 
2366 
2367 /*!
2368  \brief Smart GAP block to bitblock conversion.
2369 
2370  Checks if GAP block is ALL-ZERO or ALL-ON. In those cases returns
2371  pointer on special static bitblocks.
2372 
2373  \param dest - bitblock buffer pointer.
2374  \param buf - GAP buffer pointer.
2375  \param set_max - max possible bitset length
2376 
2377  @ingroup gapfunc
2378 */
2379 template<typename T>
2380  unsigned* gap_convert_to_bitset_smart(unsigned* dest,
2381  const T* buf,
2382  id_t set_max)
2383 {
2384  if (buf[1] == set_max - 1)
2385  {
2386  return (buf[0] & 1) ? FULL_BLOCK_REAL_ADDR : 0;
2387  }
2388 
2389  gap_convert_to_bitset(dest, buf);
2390  return dest;
2391 }
2392 
2393 
2394 /*!
2395  \brief Calculates sum of all words in GAP block. (For debugging purposes)
2396  \note For debugging and testing ONLY.
2397  \param buf - GAP buffer pointer.
2398  \return Sum of all words.
2399 
2400  @ingroup gapfunc
2401 */
2402 template<typename T> unsigned gap_control_sum(const T* buf)
2403 {
2404  unsigned end = *buf >> 3;
2405 
2406  BMREGISTER const T* pcurr = buf;
2407  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2408  ++pcurr;
2409 
2410  if (*buf & 1) // Starts with 1
2411  {
2412  ++pcurr;
2413  }
2414  ++pcurr; // now we are in GAP "1" again
2415 
2416  while (pcurr <= pend)
2417  {
2418  BM_ASSERT(*pcurr > *(pcurr-1));
2419  pcurr += 2;
2420  }
2421  return buf[end];
2422 
2423 }
2424 
2425 
2426 /*!
2427  \brief Sets all bits to 0 or 1 (GAP)
2428  \param buf - GAP buffer pointer.
2429  \param set_max - max possible bitset length
2430  \param value - value to set
2431 
2432  @ingroup gapfunc
2433 */
2434 template<class T> void gap_set_all(T* buf,
2435  unsigned set_max,
2436  unsigned value)
2437 {
2438  BM_ASSERT(value == 0 || value == 1);
2439  *buf = (T)((*buf & 6u) + (1u << 3) + value);
2440  *(++buf) = (T)(set_max - 1);
2441 }
2442 
2443 
2444 /*!
2445  \brief Init gap block so it has block in it (can be whole block)
2446  \param buf - GAP buffer pointer.
2447  \param from - one block start
2448  \param to - one block end
2449  \param value - (block value)1 or 0
2450  \param set_max - max possible bitset length
2451 
2452  @ingroup gapfunc
2453 */
2454 template<class T>
2456  T from,
2457  T to,
2458  T value,
2459  unsigned set_max)
2460 {
2461  BM_ASSERT(value == 0 || value == 1);
2462 
2463  unsigned gap_len;
2464  if (from == 0)
2465  {
2466  if (to == set_max - 1)
2467  {
2468  gap_set_all(buf, set_max, value);
2469  }
2470  else
2471  {
2472  gap_len = 2;
2473  buf[1] = (T)to;
2474  buf[2] = (T)(set_max - 1);
2475  buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
2476  }
2477  return;
2478  }
2479  // from != 0
2480 
2481  value = !value;
2482  if (to == set_max - 1)
2483  {
2484  gap_len = 2;
2485  buf[1] = (T)(from - 1);
2486  buf[2] = (T)(set_max - 1);
2487  }
2488  else
2489  {
2490  gap_len = 3;
2491  buf[1] = (T) (from - 1);
2492  buf[2] = (T) to;
2493  buf[3] = (T)(set_max - 1);
2494  }
2495  buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
2496 }
2497 
2498 
2499 /*!
2500  \brief Inverts all bits in the GAP buffer.
2501  \param buf - GAP buffer pointer.
2502 
2503  @ingroup gapfunc
2504 */
2505 template<typename T> void gap_invert(T* buf)
2506 {
2507  *buf ^= 1;
2508 }
2509 
2510 /*!
2511  \brief Temporary inverts all bits in the GAP buffer.
2512 
2513  In this function const-ness of the buffer means nothing.
2514  Calling this function again restores the status of the buffer.
2515 
2516  \param buf - GAP buffer pointer. (Buffer IS changed)
2517 
2518  @ingroup gapfunc
2519 */
2520 /*
2521 template<typename T> void gap_temp_invert(const T* buf)
2522 {
2523  T* buftmp = const_cast<T*>(buf);
2524  *buftmp ^= 1;
2525 }
2526 */
2527 
2528 /*!
2529  \brief Checks if GAP block is all-zero.
2530  \param buf - GAP buffer pointer.
2531  \param set_max - max possible bitset length
2532  \returns true if all-zero.
2533 
2534  @ingroup gapfunc
2535 */
2536 template<typename T>
2537  bool gap_is_all_zero(const T* buf, unsigned set_max)
2538 {
2539  return (((*buf & 1)==0) && (*(++buf) == set_max - 1));
2540 }
2541 
2542 /*!
2543  \brief Checks if GAP block is all-one.
2544  \param buf - GAP buffer pointer.
2545  \param set_max - max possible bitset length
2546  \returns true if all-one.
2547 
2548  @ingroup gapfunc
2549 */
2550 template<typename T>
2551  bool gap_is_all_one(const T* buf, unsigned set_max)
2552 {
2553  return ((*buf & 1) && (*(++buf) == set_max - 1));
2554 }
2555 
2556 /*!
2557  \brief Returs GAP block length.
2558  \param buf - GAP buffer pointer.
2559  \returns GAP block length.
2560 
2561  @ingroup gapfunc
2562 */
2563 template<typename T> T gap_length(const T* buf)
2564 {
2565  return (T)((*buf >> 3) + 1);
2566 }
2567 
2568 
2569 /*!
2570  \brief Returs GAP block capacity
2571  \param buf - GAP buffer pointer
2572  \param glevel_len - pointer on GAP header word
2573  \returns GAP block capacity.
2574 
2575  @ingroup gapfunc
2576 */
2577 template<typename T>
2578 unsigned gap_capacity(const T* buf, const T* glevel_len)
2579 {
2580  return glevel_len[(*buf >> 1) & 3];
2581 }
2582 
2583 
2584 /*!
2585  \brief Returs GAP block capacity limit.
2586  \param buf - GAP buffer pointer.
2587  \param glevel_len - GAP lengths table (gap_len_table)
2588  \returns GAP block limit.
2589 
2590  @ingroup gapfunc
2591 */
2592 template<typename T>
2593 unsigned gap_limit(const T* buf, const T* glevel_len)
2594 {
2595  return glevel_len[(*buf >> 1) & 3]-4;
2596 }
2597 
2598 
2599 /*!
2600  \brief Returs GAP blocks capacity level.
2601  \param buf - GAP buffer pointer.
2602  \returns GAP block capacity level.
2603 
2604  @ingroup gapfunc
2605 */
2606 template<typename T> unsigned gap_level(const T* buf)
2607 {
2608  return (*buf >> 1) & 3;
2609 }
2610 
2611 
2612 /*!
2613  \brief Sets GAP block capacity level.
2614  \param buf - GAP buffer pointer.
2615  \param level new GAP block capacity level.
2616 
2617  @ingroup gapfunc
2618 */
2619 template<typename T>
2620 void set_gap_level(T* buf, unsigned level)
2621 {
2622  BM_ASSERT(level < bm::gap_levels);
2623  *buf = (T)(((level & 3) << 1) | (*buf & 1) | (*buf & ~7));
2624 }
2625 
2626 
2627 /*!
2628  \brief Calculates GAP block capacity level.
2629  \param len - GAP buffer length.
2630  \param glevel_len - GAP lengths table
2631  \return GAP block capacity level.
2632  -1 if block does not fit any level.
2633  @ingroup gapfunc
2634 */
2635 template<typename T>
2636 inline int gap_calc_level(int len, const T* glevel_len)
2637 {
2638  if (len <= (glevel_len[0]-4)) return 0;
2639  if (len <= (glevel_len[1]-4)) return 1;
2640  if (len <= (glevel_len[2]-4)) return 2;
2641  if (len <= (glevel_len[3]-4)) return 3;
2642 
2643  BM_ASSERT(bm::gap_levels == 4);
2644  return -1;
2645 }
2646 
2647 /*! @brief Returns number of free elements in GAP block array.
2648  Difference between GAP block capacity on this level and actual GAP length.
2649 
2650  @param buf - GAP buffer pointer
2651  @param glevel_len - GAP lengths table
2652 
2653  @return Number of free GAP elements
2654  @ingroup gapfunc
2655 */
2656 template<typename T>
2657 inline unsigned gap_free_elements(const T* buf, const T* glevel_len)
2658 {
2659  unsigned len = gap_length(buf);
2660  unsigned capacity = gap_capacity(buf, glevel_len);
2661  return capacity - len;
2662 }
2663 
2664 
2665 /*!
2666  \brief Lexicographical comparison of BIT buffers.
2667  \param buf1 - First buffer pointer.
2668  \param buf2 - Second buffer pointer.
2669  \param len - Buffer length in elements (T).
2670  \return <0 - less, =0 - equal, >0 - greater.
2671 
2672  @ingroup bitfunc
2673 */
2674 template<typename T>
2675 int bitcmp(const T* buf1, const T* buf2, unsigned len)
2676 {
2677  BM_ASSERT(len);
2678  const T* pend1 = buf1 + len;
2679  do
2680  {
2681  T w1 = *buf1++;
2682  T w2 = *buf2++;
2683  T diff = w1 ^ w2;
2684 
2685  if (diff)
2686  {
2687  return (w1 & diff & -diff) ? 1 : -1;
2688  }
2689 
2690  } while (buf1 < pend1);
2691 
2692  return 0;
2693 }
2694 
2695 
2696 /*!
2697  \brief Converts bit block to GAP.
2698  \param dest - Destinatio GAP buffer.
2699  \param src - Source bitblock buffer.
2700  \param bits - Number of bits to convert.
2701  \param dest_len - length of the dest. buffer.
2702  \return New length of GAP block or 0 if conversion failed
2703  (insufficicent space).
2704 
2705  @ingroup gapfunc
2706 */
2707 template<typename T>
2708  unsigned bit_convert_to_gap(T* BMRESTRICT dest,
2709  const unsigned* BMRESTRICT src,
2710  bm::id_t bits,
2711  unsigned dest_len)
2712 {
2713  BMREGISTER T* BMRESTRICT pcurr = dest;
2714  T* BMRESTRICT end = dest + dest_len;
2715  BMREGISTER int bitval = (*src) & 1;
2716 // *pcurr |= bitval;
2717  *pcurr = (T)bitval;
2718 
2719  ++pcurr;
2720  *pcurr = 0;
2721  BMREGISTER unsigned bit_idx = 0;
2722  BMREGISTER int bitval_next;
2723 
2724  unsigned val = *src;
2725 
2726  do
2727  {
2728  // We can fast pace if *src == 0 or *src = 0xffffffff
2729 
2730  while (val == 0 || val == 0xffffffff)
2731  {
2732  bitval_next = val ? 1 : 0;
2733  if (bitval != bitval_next)
2734  {
2735  *pcurr++ = (T)(bit_idx-1);
2736  BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
2737  if (pcurr >= end)
2738  {
2739  return 0; // OUT of memory
2740  }
2741  bitval = bitval_next;
2742  }
2743  bit_idx += unsigned(sizeof(*src) * 8);
2744  if (bit_idx >= bits)
2745  {
2746  goto complete;
2747  }
2748  ++src;
2749  val = *src;
2750  }
2751 
2752 
2753  BMREGISTER unsigned mask = 1;
2754  while (mask)
2755  {
2756  // Now plain bitshifting. TODO: Optimization wanted.
2757 
2758  bitval_next = val & mask ? 1 : 0;
2759  if (bitval != bitval_next)
2760  {
2761  *pcurr++ = (T)(bit_idx-1);
2762  BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
2763  bitval = bitval_next;
2764  if (pcurr >= end)
2765  {
2766  return 0; // OUT of memory
2767  }
2768  }
2769 
2770  mask <<= 1;
2771  ++bit_idx;
2772 
2773  } // while mask
2774 
2775  if (bit_idx >= bits)
2776  {
2777  goto complete;
2778  }
2779 
2780  ++src;
2781  val = *src;
2782 
2783  } while(1);
2784 
2785 complete:
2786  *pcurr = (T)(bit_idx-1);
2787  unsigned len = (unsigned)(pcurr - dest);
2788  *dest = (T)((*dest & 7) + (len << 3));
2789  return len;
2790 }
2791 
2792 
2793 /*!
2794  \brief Iterate gap block as delta-bits with a functor
2795  @ingroup gapfunc
2796 */
2797 template<class T, class F>
2798 void for_each_gap_dbit(const T* buf, F& func)
2799 {
2800  const T* pcurr = buf;
2801  const T* pend = pcurr + (*pcurr >> 3);
2802 
2803  ++pcurr;
2804 
2805  unsigned prev = 0;
2806  unsigned first_inc;
2807 
2808  if (*buf & 1)
2809  {
2810  first_inc = 0;
2811  unsigned to = *pcurr;
2812  for (unsigned i = 0; i <= to; ++i)
2813  {
2814  func(1);
2815  }
2816  prev = to;
2817  ++pcurr;
2818  }
2819  else
2820  {
2821  first_inc = 1;
2822  }
2823  ++pcurr; // set GAP to 1
2824 
2825  while (pcurr <= pend)
2826  {
2827  unsigned from = *(pcurr-1)+1;
2828  unsigned to = *pcurr;
2829  if (first_inc)
2830  {
2831  func(from - prev + first_inc);
2832  first_inc = 0;
2833  }
2834  else
2835  {
2836  func(from - prev);
2837  }
2838 
2839  for (unsigned i = from+1; i <= to; ++i)
2840  {
2841  func(1);
2842  }
2843  prev = to;
2844  pcurr += 2; // jump to the next positive GAP
2845  }
2846 }
2847 
2848 /*!
2849  \brief Convert gap block into array of ints corresponding to 1 bits
2850  @ingroup gapfunc
2851 */
2852 template<typename D, typename T>
2854  const T* BMRESTRICT buf,
2855  unsigned dest_len,
2856  bool invert = false)
2857 {
2858  BMREGISTER const T* BMRESTRICT pcurr = buf;
2859  BMREGISTER const T* pend = pcurr + (*pcurr >> 3);
2860 
2861  D* BMRESTRICT dest_curr = dest;
2862  ++pcurr;
2863 
2864  int bitval = (*buf) & 1;
2865  if (invert)
2866  bitval = !bitval; // invert the GAP buffer
2867 
2868  if (bitval)
2869  {
2870  if (unsigned(*pcurr + 1) >= dest_len)
2871  return 0; // insufficient space
2872  dest_len -= *pcurr;
2873  T to = *pcurr;
2874  for (T i = 0; ;++i)
2875  {
2876  *dest_curr++ = i;
2877  if (i == to) break;
2878  }
2879  ++pcurr;
2880  }
2881  ++pcurr; // set GAP to 1
2882 
2883  while (pcurr <= pend)
2884  {
2885  unsigned pending = *pcurr - *(pcurr-1);
2886  if (pending >= dest_len)
2887  return 0;
2888  dest_len -= pending;
2889  T from = (T)(*(pcurr-1)+1);
2890  T to = *pcurr;
2891  for (T i = from; ;++i)
2892  {
2893  *dest_curr++ = i;
2894  if (i == to) break;
2895  }
2896  pcurr += 2; // jump to the next positive GAP
2897  }
2898  return (D) (dest_curr - dest);
2899 }
2900 
2901 
2902 
2903 /*!
2904  @brief Bitcount for bit string
2905 
2906  Function calculates number of 1 bits in the given array of words.
2907  Make sure the addresses are aligned.
2908 
2909  @ingroup bitfunc
2910 */
2911 inline
2913  const bm::word_t* block_end)
2914 {
2915  BM_ASSERT(block < block_end);
2916  bm::id_t count = 0;
2917 
2918 #ifdef BMVECTOPT
2919  count = VECT_BITCOUNT(block, block_end);
2920 #else
2921 #ifdef BM64OPT
2922  // 64-bit optimized algorithm. No sparse vect opt.
2923  // instead it uses 4-way parallel pipelined version
2924 
2925  const bm::id64_t* b1 = (bm::id64_t*) block;
2926  const bm::id64_t* b2 = (bm::id64_t*) block_end;
2927  do
2928  {
2929  count += bitcount64_4way(b1[0], b1[1], b1[2], b1[3]);
2930  b1 += 4;
2931  } while (b1 < b2);
2932 #else
2933  // For 32 bit code the fastest method is
2934  // to use bitcount table for each byte in the block.
2935  // As optimization for sparse bitsets used bits accumulator
2936  // to collect ON bits using bitwise OR.
2937  bm::word_t acc = *block++;
2938  do
2939  {
2940  bm::word_t in = *block++;
2941  bm::word_t acc_prev = acc;
2942  acc |= in;
2943  if (acc_prev &= in) // accumulator miss: counting bits
2944  {
2945  BM_INCWORD_BITCOUNT(count, acc);
2946  acc = acc_prev;
2947  }
2948  } while (block < block_end);
2949 
2950  BM_INCWORD_BITCOUNT(count, acc); // count-in remaining accumulator
2951 
2952 #endif
2953 #endif
2954  return count;
2955 }
2956 
2957 
2958 
2959 /*!
2960  Function calculates number of times when bit value changed
2961  (1-0 or 0-1).
2962 
2963  For 001 result is 2
2964  010 - 3
2965  011 - 2
2966  111 - 1
2967 
2968  @ingroup bitfunc
2969 */
2970 
2971 inline
2973 {
2974  unsigned count = 1;
2975  w ^= (w >> 1);
2976 
2977  count += bm::word_bitcount(w);
2978  //BM_INCWORD_BITCOUNT(count, w);
2979  count -= (w >> ((sizeof(w) * 8) - 1));
2980  return count;
2981 }
2982 
2983 
2984 /*!
2985  Function calculates number of times when bit value changed
2986  @internal
2987 */
2988 inline
2989 void bit_count_change32(const bm::word_t* block,
2990  const bm::word_t* block_end,
2991  unsigned* bit_count,
2992  unsigned* gap_count)
2993 {
2994  BM_ASSERT(block < block_end);
2995  BM_ASSERT(bit_count);
2996  BM_ASSERT(gap_count);
2997 
2998  *gap_count = 1;
2999  *bit_count = 0;
3000 
3001  bm::word_t w, w0, w_prev, w_l;
3002  w = w0 = *block;
3003 
3004  BM_INCWORD_BITCOUNT(*bit_count, w);
3005 
3006  const int w_shift = int(sizeof(w) * 8 - 1);
3007  w ^= (w >> 1);
3008  BM_INCWORD_BITCOUNT(*gap_count, w);
3009  *gap_count -= (w_prev = (w0 >> w_shift)); // negative value correction
3010 
3011  for (++block ;block < block_end; ++block)
3012  {
3013  w = w0 = *block;
3014  ++(*gap_count);
3015 
3016  if (!w)
3017  {
3018  *gap_count -= !w_prev;
3019  w_prev = 0;
3020  }
3021  else
3022  {
3023  BM_INCWORD_BITCOUNT(*bit_count, w);
3024 
3025  w ^= (w >> 1);
3026  BM_INCWORD_BITCOUNT(*gap_count, w);
3027 
3028  w_l = w0 & 1;
3029  *gap_count -= (w0 >> w_shift); // negative value correction
3030  *gap_count -= !(w_prev ^ w_l); // word border correction
3031 
3032  w_prev = (w0 >> w_shift);
3033  }
3034  } // for
3035 
3036 }
3037 
3038 
3039 /*!
3040  Function calculates number of times when bit value changed
3041  (1-0 or 0-1) in the bit block.
3042  Also calulates number of bits ON.
3043 
3044  @param bit_count - OUT total number of bits ON
3045  @param block - bit-block start pointer
3046  @param block_end - bit-block end pointer
3047 
3048  @return number of 1-0, 0-1 transitions
3049 
3050  @ingroup bitfunc
3051 */
3052 inline
3054  const bm::word_t* block_end,
3055  unsigned* bit_count)
3056 {
3057 #if defined(BMSSE2OPT) || defined(BMSSE42OPT) || defined (BMAVX2OPT)
3058 
3059 #ifdef BMAVX2OPT
3060  // TODO: debug true avx2 function (stress test failure)
3061  // temp use SSE4.2 variant
3062  return sse42_bit_block_calc_count_change(
3063  (const __m128i*)block, (const __m128i*)block_end, bit_count);
3064 /*
3065  return avx2_bit_block_calc_count_change(
3066  (const __m256i*)block, (const __m256i*)block_end, bit_count);
3067 */
3068 #else
3069 #ifdef BMSSE42OPT
3071  (const __m128i*)block, (const __m128i*)block_end, bit_count);
3072 #else
3073 # ifdef BMSSE2OPT
3075  (const __m128i*)block, (const __m128i*)block_end, bit_count);
3076 # endif
3077 #endif
3078 #endif
3079 
3080 #else // non-SIMD code
3081 
3082  BM_ASSERT(block < block_end);
3083  BM_ASSERT(bit_count);
3084 
3085 
3086 #ifdef BM64OPT
3087  bm::id64_t count = 1;
3088  *bit_count = 0;
3089 
3090  // 64-bit optimized algorithm.
3091 
3092  const bm::id64_t* b1 = (bm::id64_t*) block;
3093  const bm::id64_t* b2 = (bm::id64_t*) block_end;
3094 
3095  bm::id64_t w, w0, w_prev, w_l;
3096  w = w0 = *b1;
3097 
3098  *bit_count = word_bitcount64(w);
3099 
3100  const int w_shift = sizeof(w) * 8 - 1;
3101  w ^= (w >> 1);
3102  count += word_bitcount64(w);
3103  count -= (w_prev = (w0 >> w_shift)); // negative value correction
3104 
3105 
3106  for (++b1 ;b1 < b2; ++b1)
3107  {
3108  w = w0 = *b1;
3109 
3110  ++count;
3111 
3112  if (!w)
3113  {
3114  count -= !w_prev;
3115  w_prev = 0;
3116  }
3117  else
3118  {
3119  *bit_count += word_bitcount64(w);
3120  w ^= (w >> 1);
3121  count += word_bitcount64(w);
3122 
3123  w_l = w0 & 1;
3124  count -= (w0 >> w_shift); // negative value correction
3125  count -= !(w_prev ^ w_l); // word border correction
3126 
3127  w_prev = (w0 >> w_shift);
3128  }
3129  } // for
3130  return (bm::id_t) count;
3131 
3132 #else
3133  unsigned gap_count;
3134  bit_count_change32(block, block_end, bit_count, &gap_count);
3135  return gap_count;
3136 #endif
3137 
3138 #endif
3139 }
3140 
3141 
3142 /*!
3143  Function calculates number of 1 bits in the given array of words in
3144  the range between left anf right bits (borders included)
3145  Make sure the addr is aligned.
3146 
3147  @ingroup bitfunc
3148 */
3149 inline
3151  bm::word_t left,
3152  bm::word_t right)
3153 {
3154  BM_ASSERT(left <= right);
3155  unsigned nword, nbit;
3156  nbit = left & bm::set_word_mask;
3157  const bm::word_t* word =
3158  block + (nword = unsigned(left >> bm::set_word_shift));
3159  if (left == right) // special case (only 1 bit to check)
3160  {
3161  return (*word >> nbit) & 1;
3162  }
3163  bm::id_t count = 0;
3164 
3165  unsigned acc;
3166  unsigned bitcount = right - left + 1;
3167 
3168  if (nbit) // starting position is not aligned
3169  {
3170  unsigned right_margin = nbit + (right - left);
3171 
3172  if (right_margin < 32)
3173  {
3174  unsigned mask =
3176  block_set_table<true>::_left[right_margin];
3177  acc = *word & mask;
3178 
3179  BM_INCWORD_BITCOUNT(count, acc);
3180  return count;
3181  }
3182  else
3183  {
3184  acc = *word & block_set_table<true>::_right[nbit];
3185  BM_INCWORD_BITCOUNT(count, acc);
3186  bitcount -= 32 - nbit;
3187  }
3188  ++word;
3189  }
3190 
3191  // now when we are word aligned, we can count bits the usual way
3192  for ( ;bitcount >= 32; bitcount -= 32)
3193  {
3194  acc = *word++;
3195  BM_INCWORD_BITCOUNT(count, acc);
3196  }
3197 
3198  if (bitcount) // we have a tail to count
3199  {
3200  acc = (*word) & block_set_table<true>::_left[bitcount-1];
3201  BM_INCWORD_BITCOUNT(count, acc);
3202  }
3203 
3204  return count;
3205 }
3206 
3207 /*!
3208  Function calculates number of 1 bits in the given array of words in
3209  the range between 0 anf right bits (borders included)
3210  Make sure the addr is aligned.
3211 
3212  @ingroup bitfunc
3213 */
3214 inline
3216  bm::word_t right)
3217 {
3218  BM_ASSERT(block);
3219  if (right == 0)
3220  return *block & 1;
3221  bm::id_t count = 0;
3222 
3223  unsigned bitcount = right + 1;
3224 
3225  // AVX2 or 64-bit loop unroll
3226  #if defined(BMAVX2OPT)
3227  BM_AVX2_POPCNT_PROLOG
3228 
3229  __m256i cnt = _mm256_setzero_si256();
3230  uint64_t* cnt64;
3231 
3232  for ( ;bitcount >= 256; bitcount -= 256)
3233  {
3234  const __m256i* src = (__m256i*)block;
3235  __m256i xmm256 = _mm256_load_si256(src);
3236  BM_AVX2_BIT_COUNT(bc, xmm256);
3237  cnt = _mm256_add_epi64(cnt, bc);
3238 
3239  block += 8;
3240  }
3241  cnt64 = (uint64_t*)&cnt;
3242  count += (unsigned)(cnt64[0] + cnt64[1] + cnt64[2] + cnt64[3]);
3243  #else
3244  for ( ;bitcount >= 64; bitcount -= 64)
3245  {
3246  bm::id64_t* p = (bm::id64_t*)block;
3247  bm::id64_t a64 = *p;
3248 
3249  count += bm::word_bitcount64(a64);
3250  block += 2;
3251  }
3252  #endif
3253 
3254  // now word aligned, count bits the usual way
3255  for ( ;bitcount >= 32; bitcount -= 32)
3256  {
3257  unsigned acc = *block++;
3258  count += bm::word_bitcount(acc);
3259  }
3260 
3261  if (bitcount) // tail to count
3262  {
3263  unsigned acc = (*block) & block_set_table<true>::_left[bitcount-1];
3264  count += bm::word_bitcount(acc);
3265  }
3266 
3267  return count;
3268 }
3269 
3270 
3271 
3272 /*!
3273  Cyclic rotation of bit-block left by 1 bit
3274  @ingroup bitfunc
3275 */
3276 inline
3278 {
3279  bm::word_t co_flag = (block[0] >> 31) & 1; // carry over bit
3280  for (unsigned i = 0; i < bm::set_block_size-1; ++i)
3281  {
3282  block[i] = (block[i] << 1) | (block[i + 1] >> 31);
3283  }
3284  block[set_block_size - 1] = (block[set_block_size - 1] << 1) | co_flag;
3285 }
3286 
3287 /*!
3288  Unrolled cyclic rotation of bit-block left by 1 bit
3289  @ingroup bitfunc
3290 */
3291 inline
3293 {
3294  bm::word_t co_flag = (block[0] >> 31) & 1; // carry over bit
3295  const unsigned unroll_factor = 4;
3296  bm::word_t w0, w1, w2, w3;
3297 
3298  unsigned i;
3299  for (i = 0; i < bm::set_block_size - unroll_factor; i += unroll_factor)
3300  {
3301  w0 = block[i + 1] >> 31;
3302  w1 = block[i + 2] >> 31;
3303  w2 = block[i + 3] >> 31;
3304  w3 = block[i + 4] >> 31;
3305 
3306  block[0 + i] = (block[0 + i] << 1) | w0;
3307  block[1 + i] = (block[1 + i] << 1) | w1;
3308  block[2 + i] = (block[2 + i] << 1) | w2;
3309  block[3 + i] = (block[3 + i] << 1) | w3;
3310  }
3311  block[i] = (block[i] << 1) | (block[i + 1] >> 31);
3312  block[i + 1] = (block[i + 1] << 1) | (block[i + 2] >> 31);
3313  block[i + 2] = (block[i + 2] << 1) | (block[i + 3] >> 31);
3314  block[set_block_size - 1] = (block[set_block_size - 1] << 1) | co_flag;
3315 }
3316 
3317 
3318 
3319 /*!
3320  Function calculates if there is any number of 1 bits
3321  in the given array of words in the range between left anf right bits
3322  (borders included). Make sure the addresses are aligned.
3323 
3324  @ingroup bitfunc
3325 */
3326 inline
3328  bm::word_t left,
3329  bm::word_t right)
3330 {
3331  BM_ASSERT(left <= right);
3332 
3333  unsigned nbit = left; // unsigned(left & bm::set_block_mask);
3334  unsigned nword = unsigned(nbit >> bm::set_word_shift);
3335  nbit &= bm::set_word_mask;
3336 
3337  const bm::word_t* word = block + nword;
3338 
3339  if (left == right) // special case (only 1 bit to check)
3340  {
3341  return (*word >> nbit) & 1;
3342  }
3343  unsigned acc;
3344  unsigned bitcount = right - left + 1;
3345 
3346  if (nbit) // starting position is not aligned
3347  {
3348  unsigned right_margin = nbit + (right - left);
3349  if (right_margin < 32)
3350  {
3351  unsigned mask =
3353  block_set_table<true>::_left[right_margin];
3354  acc = *word & mask;
3355  return acc;
3356  }
3357  else
3358  {
3359  acc = *word & block_set_table<true>::_right[nbit];
3360  if (acc)
3361  return acc;
3362  bitcount -= 32 - nbit;
3363  }
3364  ++word;
3365  }
3366 
3367  // now when we are word aligned, we can check bits the usual way
3368  for ( ;bitcount >= 32; bitcount -= 32)
3369  {
3370  acc = *word++;
3371  if (acc)
3372  return acc;
3373  }
3374 
3375  if (bitcount) // we have a tail to count
3376  {
3377  acc = (*word) & block_set_table<true>::_left[bitcount-1];
3378  if (acc)
3379  return acc;
3380  }
3381 
3382  return 0;
3383 }
3384 
3385 
3386 
3387 // ----------------------------------------------------------------------
3388 
3389 /*! Function inverts block of bits
3390  @ingroup bitfunc
3391 */
3392 template<typename T> void bit_invert(T* start, T* end)
3393 {
3394 #ifdef BMVECTOPT
3395  VECT_INVERT_ARR(start, end);
3396 #else
3397  do
3398  {
3399  start[0] = ~start[0];
3400  start[1] = ~start[1];
3401  start[2] = ~start[2];
3402  start[3] = ~start[3];
3403  start+=4;
3404  } while (start < end);
3405 #endif
3406 }
3407 
3408 // ----------------------------------------------------------------------
3409 
3410 /*! @brief Returns "true" if all bits in the block are 1
3411  @ingroup bitfunc
3412 */
3413 inline bool is_bits_one(const bm::wordop_t* start,
3414  const bm::wordop_t* end)
3415 {
3416 #if defined(BMSSE42OPT) || defined(BMAVX2OPT)
3417  return VECT_IS_ONE_BLOCK(start, end);
3418 #else
3419  do
3420  {
3421  bm::wordop_t tmp =
3422  start[0] & start[1] & start[2] & start[3];
3423  if (tmp != bm::all_bits_mask)
3424  return false;
3425  start += 4;
3426  } while (start < end);
3427  return true;
3428 #endif
3429 }
3430 
3431 // ----------------------------------------------------------------------
3432 
3433 
3434 /*! @brief Returns "true" if all bits in the block are 0
3435  @ingroup bitfunc
3436 */
3437 inline
3438 bool bit_is_all_zero(const bm::wordop_t* start,
3439  const bm::wordop_t* end)
3440 {
3441 #if defined(BMSSE42OPT) || defined(BMAVX2OPT)
3442  return VECT_IS_ZERO_BLOCK(start, end);
3443 #else
3444  do
3445  {
3446  bm::wordop_t tmp =
3447  start[0] | start[1] | start[2] | start[3];
3448  if (tmp)
3449  return false;
3450  start += 4;
3451  } while (start < end);
3452  return true;
3453 #endif
3454 }
3455 
3456 // ----------------------------------------------------------------------
3457 
3458 // GAP blocks manipulation functions:
3459 
3460 /*! \brief GAP and functor */
3461 BMFORCEINLINE unsigned and_op(unsigned v1, unsigned v2)
3462 {
3463  return v1 & v2;
3464 }
3465 
3466 
3467 /*! \brief GAP xor functor */
3468 BMFORCEINLINE unsigned xor_op(unsigned v1, unsigned v2)
3469 {
3470  return v1 ^ v2;
3471 }
3472 
3473 
3474 /*! \brief GAP or functor */
3475 BMFORCEINLINE unsigned or_op(unsigned v1, unsigned v2)
3476 {
3477  return v1 | v2;
3478 }
3479 
3480 /*! \brief GAP or functor */
3481 BMFORCEINLINE unsigned sub_op(unsigned v1, unsigned v2)
3482 {
3483  return v1 & ~v2;
3484 }
3485 
3486 
3487 /*!
3488  \brief GAP AND operation.
3489 
3490  Function performs AND logical operation on gap vectors.
3491  If possible function put the result into vect1 and returns this
3492  pointer. Otherwise result is put into tmp_buf, which should be
3493  twice of the vector size.
3494 
3495  \param vect1 - operand 1
3496  \param vect2 - operand 2
3497  \param tmp_buf - pointer on temporary buffer
3498  \param dsize - out size of the destination
3499  \return Result pointer (tmp_buf OR vect1)
3500 
3501  @ingroup gapfunc
3502 */
3505  const gap_word_t* BMRESTRICT vect2,
3506  gap_word_t* BMRESTRICT tmp_buf,
3507  unsigned& dsize)
3508 {
3509  gap_buff_op(tmp_buf, vect1, 0, vect2, 0, and_op, dsize);
3510  return tmp_buf;
3511 }
3512 
3513 /*!
3514  \brief GAP AND operation test.
3515 
3516  Function performs AND logical operation on gap vectors.
3517  If possible function put the result into vect1 and returns this
3518  pointer. Otherwise result is put into tmp_buf, which should be
3519  twice of the vector size.
3520 
3521  \param vect1 - operand 1
3522  \param vect2 - operand 2
3523  \return non zero value if operation returns any 1 bit
3524 
3525  @ingroup gapfunc
3526 */
3529  const gap_word_t* BMRESTRICT vect2)
3530 {
3531  return gap_buff_any_op(vect1, 0, vect2, 0, and_op);
3532 }
3533 
3534 
3535 /*!
3536  \brief GAP bitcount AND operation test.
3537 
3538  \param vect1 - operand 1
3539  \param vect2 - operand 2
3540  \return bitcount of vect1 AND vect2
3541 
3542  @ingroup gapfunc
3543 */
3545 unsigned gap_count_and(const gap_word_t* BMRESTRICT vect1,
3546  const gap_word_t* BMRESTRICT vect2)
3547 {
3548  return gap_buff_count_op(vect1, vect2, and_op);
3549 }
3550 
3551 
3552 
3553 /*!
3554  \brief GAP XOR operation.
3555 
3556  Function performs XOR logical operation on gap vectors.
3557  If possible function put the result into vect1 and returns this
3558  pointer. Otherwise result is put into tmp_buf, which should be
3559  twice of the vector size.
3560 
3561  \param vect1 - operand 1
3562  \param vect2 - operand 2
3563  \param tmp_buf - pointer on temporary buffer
3564  \param dsize - out destination size
3565  \return Result pointer (tmp_buf)
3566 
3567  @ingroup gapfunc
3568 */
3571  const gap_word_t* BMRESTRICT vect2,
3572  gap_word_t* BMRESTRICT tmp_buf,
3573  unsigned& dsize)
3574 {
3575  gap_buff_op(tmp_buf, vect1, 0, vect2, 0, bm::xor_op, dsize);
3576  return tmp_buf;
3577 }
3578 
3579 
3580 /*!
3581  \brief GAP XOR operation test.
3582 
3583  Function performs AND logical operation on gap vectors.
3584  If possible function put the result into vect1 and returns this
3585  pointer. Otherwise result is put into tmp_buf, which should be
3586  twice of the vector size.
3587 
3588  \param vect1 - operand 1
3589  \param vect2 - operand 2
3590  \return non zero value if operation returns any 1 bit
3591 
3592  @ingroup gapfunc
3593 */
3596  const gap_word_t* BMRESTRICT vect2)
3597 {
3598  return gap_buff_any_op(vect1, 0, vect2, 0, bm::xor_op);
3599 }
3600 
3601 /*!
3602  \brief GAP bitcount XOR operation test.
3603 
3604  \param vect1 - operand 1
3605  \param vect2 - operand 2
3606  \return bitcount of vect1 XOR vect2
3607 
3608  @ingroup gapfunc
3609 */
3611 unsigned gap_count_xor(const gap_word_t* BMRESTRICT vect1,
3612  const gap_word_t* BMRESTRICT vect2)
3613 {
3614  return gap_buff_count_op(vect1, vect2, bm::xor_op);
3615 }
3616 
3617 
3618 /*!
3619  \brief GAP OR operation.
3620 
3621  Function performs OR logical oparation on gap vectors.
3622  If possible function put the result into vect1 and returns this
3623  pointer. Otherwise result is put into tmp_buf, which should be
3624  twice of the vector size.
3625 
3626  \param vect1 - operand 1
3627  \param vect2 - operand 2
3628  \param tmp_buf - pointer on temporary buffer
3629  \param dsize - out destination size
3630 
3631  \return Result pointer (tmp_buf)
3632 
3633  @ingroup gapfunc
3634 */
3635 inline
3637  const gap_word_t* BMRESTRICT vect2,
3638  gap_word_t* BMRESTRICT tmp_buf,
3639  unsigned& dsize)
3640 {
3641  gap_buff_op(tmp_buf, vect1, 1, vect2, 1, bm::and_op, dsize);
3642  gap_invert(tmp_buf);
3643  return tmp_buf;
3644 }
3645 
3646 /*!
3647  \brief GAP bitcount OR operation test.
3648 
3649  \param vect1 - operand 1
3650  \param vect2 - operand 2
3651  \return bitcount of vect1 OR vect2
3652 
3653  @ingroup gapfunc
3654 */
3656 unsigned gap_count_or(const gap_word_t* BMRESTRICT vect1,
3657  const gap_word_t* BMRESTRICT vect2)
3658 {
3659  return gap_buff_count_op(vect1, vect2, bm::or_op);
3660 }
3661 
3662 
3663 
3664 /*!
3665  \brief GAP SUB (AND NOT) operation.
3666 
3667  Function performs SUB logical operation on gap vectors.
3668  If possible function put the result into vect1 and returns this
3669  pointer. Otherwise result is put into tmp_buf, which should be
3670  twice of the vector size.
3671 
3672  \param vect1 - operand 1
3673  \param vect2 - operand 2
3674  \param tmp_buf - pointer on temporary buffer
3675  \param dsize - out destination size
3676 
3677  \return Result pointer (tmp_buf)
3678 
3679  @ingroup gapfunc
3680 */
3682  const gap_word_t* BMRESTRICT vect2,
3683  gap_word_t* BMRESTRICT tmp_buf,
3684  unsigned& dsize)
3685 {
3686  gap_buff_op(tmp_buf, vect1, 0, vect2, 1, and_op, dsize);
3687  return tmp_buf;
3688 }
3689 
3690 
3691 /*!
3692  \brief GAP SUB operation test.
3693 
3694  Function performs AND logical operation on gap vectors.
3695  If possible function put the result into vect1 and returns this
3696  pointer. Otherwise result is put into tmp_buf, which should be
3697  twice of the vector size.
3698 
3699  \param vect1 - operand 1
3700  \param vect2 - operand 2
3701  \return non zero value if operation returns any 1 bit
3702 
3703  @ingroup gapfunc
3704 */
3707  const gap_word_t* BMRESTRICT vect2)
3708 {
3709  return gap_buff_any_op(vect1, 0, vect2, 1, bm::and_op);
3710 }
3711 
3712 
3713 /*!
3714 \brief GAP bitcount SUB (AND NOT) operation test.
3715 
3716 \param vect1 - operand 1
3717 \param vect2 - operand 2
3718 \return bitcount of vect1 SUB (AND NOT) vect2
3719 
3720 @ingroup gapfunc
3721 */
3723 unsigned gap_count_sub(const gap_word_t* BMRESTRICT vect1,
3724  const gap_word_t* BMRESTRICT vect2)
3725 {
3726  return gap_buff_count_op(vect1, vect2, bm::sub_op);
3727 }
3728 
3729 
3730 // ----------------------------------------------------------------------
3731 
3732 // BIT blocks manipulation functions:
3733 
3734 
3735 /*!
3736  \brief Bitblock copy operation.
3737 
3738  \param dst - destination block.
3739  \param src - source block.
3740 
3741  @ingroup bitfunc
3742 */
3743 inline
3745 {
3746 #ifdef BMVECTOPT
3747  VECT_COPY_BLOCK(dst, src, src + bm::set_block_size);
3748 #else
3749  ::memcpy(dst, src, bm::set_block_size * sizeof(bm::word_t));
3750 #endif
3751 }
3752 
3753 
3754 /*!
3755  \brief Plain bitblock AND operation.
3756  Function does not analyse availability of source and destination blocks.
3757 
3758  \param dst - destination block.
3759  \param src - source block.
3760 
3761  @ingroup bitfunc
3762 */
3763 inline
3765 {
3766 #ifdef BMVECTOPT
3767  VECT_AND_ARR(dst, src, src + bm::set_block_size);
3768 #else
3769  const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
3770  const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + bm::set_block_size);
3771  bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
3772 
3773  do
3774  {
3775  dst_ptr[0] &= wrd_ptr[0];
3776  dst_ptr[1] &= wrd_ptr[1];
3777  dst_ptr[2] &= wrd_ptr[2];
3778  dst_ptr[3] &= wrd_ptr[3];
3779 
3780  dst_ptr+=4;
3781  wrd_ptr+=4;
3782  } while (wrd_ptr < wrd_end);
3783 #endif
3784 }
3785 
3786 
3787 /*!
3788  \brief Function ANDs two bitblocks and computes the bitcount.
3789  Function does not analyse availability of source blocks.
3790 
3791  \param src1 - first bit block
3792  \param src1_end - first bit block end
3793  \param src2 - second bit block
3794 
3795  @ingroup bitfunc
3796 */
3797 inline
3798 unsigned bit_block_and_count(const bm::word_t* src1,
3799  const bm::word_t* src1_end,
3800  const bm::word_t* src2)
3801 {
3802  unsigned count;
3803 #ifdef BMVECTOPT
3804  count = VECT_BITCOUNT_AND(src1, src1_end, src2);
3805 #else
3806  count = 0;
3807 # ifdef BM64OPT
3808  const bm::id64_t* b1 = (bm::id64_t*) src1;
3809  const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
3810  const bm::id64_t* b2 = (bm::id64_t*) src2;
3811  do
3812  {
3813  count += bitcount64_4way(b1[0] & b2[0],
3814  b1[1] & b2[1],
3815  b1[2] & b2[2],
3816  b1[3] & b2[3]);
3817  b1 += 4;
3818  b2 += 4;
3819  } while (b1 < b1_end);
3820 # else
3821  do
3822  {
3823  BM_INCWORD_BITCOUNT(count, src1[0] & src2[0]);
3824  BM_INCWORD_BITCOUNT(count, src1[1] & src2[1]);
3825  BM_INCWORD_BITCOUNT(count, src1[2] & src2[2]);
3826  BM_INCWORD_BITCOUNT(count, src1[3] & src2[3]);
3827 
3828  src1+=4;
3829  src2+=4;
3830  } while (src1 < src1_end);
3831 # endif
3832 #endif
3833  return count;
3834 }
3835 
3836 
3837 /*!
3838  \brief Function ANDs two bitblocks and tests for any bit.
3839  Function does not analyse availability of source blocks.
3840 
3841  \param src1 - first bit block
3842  \param src1_end - first bit block end
3843  \param src2 - second bit block
3844 
3845  @ingroup bitfunc
3846 */
3847 inline
3848 unsigned bit_block_and_any(const bm::word_t* src1,
3849  const bm::word_t* src1_end,
3850  const bm::word_t* src2)
3851 {
3852  unsigned count = 0;
3853  do
3854  {
3855  count = (src1[0] & src2[0]) |
3856  (src1[1] & src2[1]) |
3857  (src1[2] & src2[2]) |
3858  (src1[3] & src2[3]);
3859 
3860  src1+=4; src2+=4;
3861  } while ((src1 < src1_end) && (count == 0));
3862  return count;
3863 }
3864 
3865 
3866 
3867 
3868 /*!
3869  \brief Function XORs two bitblocks and computes the bitcount.
3870  Function does not analyse availability of source blocks.
3871 
3872  \param src1 - first bit block.
3873  \param src1_end - first bit block end
3874  \param src2 - second bit block.
3875 
3876  @ingroup bitfunc
3877 */
3878 inline
3880  const bm::word_t* BMRESTRICT src1_end,
3881  const bm::word_t* BMRESTRICT src2)
3882 {
3883  unsigned count;
3884 #ifdef BMVECTOPT
3885  count = VECT_BITCOUNT_XOR(src1, src1_end, src2);
3886 #else
3887  count = 0;
3888 # ifdef BM64OPT
3889  const bm::id64_t* b1 = (bm::id64_t*) src1;
3890  const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
3891  const bm::id64_t* b2 = (bm::id64_t*) src2;
3892  do
3893  {
3894  count += bitcount64_4way(b1[0] ^ b2[0],
3895  b1[1] ^ b2[1],
3896  b1[2] ^ b2[2],
3897  b1[3] ^ b2[3]);
3898  b1 += 4;
3899  b2 += 4;
3900  } while (b1 < b1_end);
3901 # else
3902  do
3903  {
3904  BM_INCWORD_BITCOUNT(count, src1[0] ^ src2[0]);
3905  BM_INCWORD_BITCOUNT(count, src1[1] ^ src2[1]);
3906  BM_INCWORD_BITCOUNT(count, src1[2] ^ src2[2]);
3907  BM_INCWORD_BITCOUNT(count, src1[3] ^ src2[3]);
3908 
3909  src1+=4;
3910  src2+=4;
3911  } while (src1 < src1_end);
3912 # endif
3913 #endif
3914  return count;
3915 }
3916 
3917 
3918 /*!
3919  \brief Function XORs two bitblocks and and tests for any bit.
3920  Function does not analyse availability of source blocks.
3921 
3922  \param src1 - first bit block.
3923  \param src1_end - first bit block end
3924  \param src2 - second bit block.
3925 
3926  @ingroup bitfunc
3927 */
3928 inline
3930  const bm::word_t* BMRESTRICT src1_end,
3931  const bm::word_t* BMRESTRICT src2)
3932 {
3933  unsigned count = 0;
3934  do
3935  {
3936  count = (src1[0] ^ src2[0]) |
3937  (src1[1] ^ src2[1]) |
3938  (src1[2] ^ src2[2]) |
3939  (src1[3] ^ src2[3]);
3940 
3941  src1+=4; src2+=4;
3942  } while ((src1 < src1_end) && (count == 0));
3943  return count;
3944 }
3945 
3946 
3947 
3948 
3949 /*!
3950  \brief Function SUBs two bitblocks and computes the bitcount.
3951  Function does not analyse availability of source blocks.
3952 
3953  \param src1 - first bit block.
3954  \param src1_end - first bit block end
3955  \param src2 - second bit block.
3956 
3957  @ingroup bitfunc
3958 */
3959 inline
3961  const bm::word_t* BMRESTRICT src1_end,
3962  const bm::word_t* BMRESTRICT src2)
3963 {
3964  unsigned count;
3965 #ifdef BMVECTOPT
3966  count = VECT_BITCOUNT_SUB(src1, src1_end, src2);
3967 #else
3968  count = 0;
3969 # ifdef BM64OPT
3970  const bm::id64_t* b1 = (bm::id64_t*) src1;
3971  const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
3972  const bm::id64_t* b2 = (bm::id64_t*) src2;
3973  do
3974  {
3975  count += bitcount64_4way(b1[0] & ~b2[0],
3976  b1[1] & ~b2[1],
3977  b1[2] & ~b2[2],
3978  b1[3] & ~b2[3]);
3979  b1 += 4;
3980  b2 += 4;
3981  } while (b1 < b1_end);
3982 # else
3983  do
3984  {
3985  BM_INCWORD_BITCOUNT(count, src1[0] & ~src2[0]);
3986  BM_INCWORD_BITCOUNT(count, src1[1] & ~src2[1]);
3987  BM_INCWORD_BITCOUNT(count, src1[2] & ~src2[2]);
3988  BM_INCWORD_BITCOUNT(count, src1[3] & ~src2[3]);
3989 
3990  src1+=4;
3991  src2+=4;
3992  } while (src1 < src1_end);
3993 # endif
3994 #endif
3995  return count;
3996 }
3997 
3998 /*!
3999  \brief Function SUBs two bitblocks and and tests for any bit.
4000  Function does not analyse availability of source blocks.
4001 
4002  \param src1 - first bit block.
4003  \param src1_end - first bit block end
4004  \param src2 - second bit block.
4005 
4006  @ingroup bitfunc
4007 */
4008 inline
4010  const bm::word_t* BMRESTRICT src1_end,
4011  const bm::word_t* BMRESTRICT src2)
4012 {
4013  unsigned count = 0;
4014  do
4015  {
4016  count = (src1[0] & ~src2[0]) |
4017  (src1[1] & ~src2[1]) |
4018  (src1[2] & ~src2[2]) |
4019  (src1[3] & ~src2[3]);
4020 
4021  src1+=4; src2+=4;
4022  } while ((src1 < src1_end) && (count == 0));
4023  return count;
4024 }
4025 
4026 
4027 
4028 /*!
4029  \brief Function ORs two bitblocks and computes the bitcount.
4030  Function does not analyse availability of source blocks.
4031 
4032  \param src1 - first bit block
4033  \param src1_end - first block end
4034  \param src2 - second bit block.
4035 
4036  @ingroup bitfunc
4037 */
4038 inline
4039 unsigned bit_block_or_count(const bm::word_t* src1,
4040  const bm::word_t* src1_end,
4041  const bm::word_t* src2)
4042 {
4043  unsigned count;
4044 #ifdef BMVECTOPT
4045  count = VECT_BITCOUNT_OR(src1, src1_end, src2);
4046 #else
4047  count = 0;
4048 # ifdef BM64OPT
4049  const bm::id64_t* b1 = (bm::id64_t*) src1;
4050  const bm::id64_t* b1_end = (bm::id64_t*) src1_end;
4051  const bm::id64_t* b2 = (bm::id64_t*) src2;
4052  do
4053  {
4054  count += bitcount64_4way(b1[0] | b2[0],
4055  b1[1] | b2[1],
4056  b1[2] | b2[2],
4057  b1[3] | b2[3]);
4058  b1 += 4;
4059  b2 += 4;
4060  } while (b1 < b1_end);
4061 # else
4062  do
4063  {
4064  BM_INCWORD_BITCOUNT(count, src1[0] | src2[0]);
4065  BM_INCWORD_BITCOUNT(count, src1[1] | src2[1]);
4066  BM_INCWORD_BITCOUNT(count, src1[2] | src2[2]);
4067  BM_INCWORD_BITCOUNT(count, src1[3] | src2[3]);
4068 
4069  src1+=4;
4070  src2+=4;
4071  } while (src1 < src1_end);
4072 # endif
4073 #endif
4074  return count;
4075 }
4076 
4077 /*!
4078  \brief Function ORs two bitblocks and and tests for any bit.
4079  Function does not analyse availability of source blocks.
4080 
4081  \param src1 - first bit block.
4082  \param src1_end - first bit block end
4083  \param src2 - second bit block.
4084 
4085  @ingroup bitfunc
4086 */
4087 inline
4089  const bm::word_t* BMRESTRICT src1_end,
4090  const bm::word_t* BMRESTRICT src2)
4091 {
4092  unsigned count = 0;
4093  do
4094  {
4095  count = (src1[0] | src2[0]) |
4096  (src1[1] | src2[1]) |
4097  (src1[2] | src2[2]) |
4098  (src1[3] | src2[3]);
4099 
4100  src1+=4; src2+=4;
4101  } while ((src1 < src1_end) && (count == 0));
4102  return count;
4103 }
4104 
4105 
4106 
4107 
4108 /*!
4109  \brief bitblock AND operation.
4110 
4111  \param dst - destination block.
4112  \param src - source block.
4113 
4114  \returns pointer on destination block.
4115  If returned value equal to src means that block mutation requested.
4116  NULL is valid return value.
4117 
4118  @ingroup bitfunc
4119 */
4121  const bm::word_t* BMRESTRICT src)
4122 {
4123  BM_ASSERT(dst || src);
4124 
4125  bm::word_t* ret = dst;
4126 
4127  if (IS_VALID_ADDR(dst)) // The destination block already exists
4128  {
4129 
4130  if (!IS_VALID_ADDR(src))
4131  {
4132  if (IS_EMPTY_BLOCK(src))
4133  {
4134  //If the source block is zero
4135  //just clean the destination block
4136  return 0;
4137  }
4138  }
4139  else
4140  {
4141  // Regular operation AND on the whole block.
4142  bit_block_and(dst, src);
4143  }
4144  }
4145  else // The destination block does not exist yet
4146  {
4147  if(!IS_VALID_ADDR(src))
4148  {
4149  if(IS_EMPTY_BLOCK(src))
4150  {
4151  // The source block is empty.
4152  // One argument empty - all result is empty.
4153  return 0;
4154  }
4155  // Here we have nothing to do.
4156  // Src block is all ON, dst block remains as it is
4157  }
4158  else // destination block does not exists, src - valid block
4159  {
4160  if (IS_FULL_BLOCK(dst))
4161  {
4162  return const_cast<bm::word_t*>(src);
4163  }
4164  // Nothng to do.
4165  // Dst block is all ZERO no combination required.
4166  }
4167  }
4168 
4169  return ret;
4170 }
4171 
4172 
4173 /*!
4174  \brief Performs bitblock AND operation and calculates bitcount of the result.
4175 
4176  \param src1 - first bit block.
4177  \param src1_end - first bit block end
4178  \param src2 - second bit block.
4179 
4180  \returns bitcount value
4181 
4182  @ingroup bitfunc
4183 */
4184 inline
4186  const bm::word_t* BMRESTRICT src1_end,
4187  const bm::word_t* BMRESTRICT src2)
4188 {
4189  if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
4190  {
4191  return 0;
4192  }
4193  return bit_block_and_count(src1, src1_end, src2);
4194 }
4195 
4196 /*!
4197  \brief Performs bitblock AND operation test.
4198 
4199  \param src1 - first bit block.
4200  \param src1_end - first bit block end
4201  \param src2 - second bit block.
4202 
4203  \returns non zero if there is any value
4204 
4205  @ingroup bitfunc
4206 */
4207 inline
4209  const bm::word_t* BMRESTRICT src1_end,
4210  const bm::word_t* BMRESTRICT src2)
4211 {
4212  if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
4213  {
4214  return 0;
4215  }
4216  return bit_block_and_any(src1, src1_end, src2);
4217 }
4218 
4219 
4220 
4221 /*!
4222  \brief Performs bitblock SUB operation and calculates bitcount of the result.
4223 
4224  \param src1 - first bit block.
4225  \param src1_end - first bit block end
4226  \param src2 - second bit block
4227 
4228  \returns bitcount value
4229 
4230  @ingroup bitfunc
4231 */
4232 inline
4234  const bm::word_t* BMRESTRICT src1_end,
4235  const bm::word_t* BMRESTRICT src2)
4236 {
4237  if (IS_EMPTY_BLOCK(src1))
4238  {
4239  return 0;
4240  }
4241 
4242  if (IS_EMPTY_BLOCK(src2)) // nothing to diff
4243  {
4244  return bit_block_calc_count(src1, src1_end);
4245  }
4246  return bit_block_sub_count(src1, src1_end, src2);
4247 }
4248 
4249 
4250 /*!
4251  \brief Performs inverted bitblock SUB operation and calculates
4252  bitcount of the result.
4253 
4254  \param src1 - first bit block.
4255  \param src1_end - first bit block end
4256  \param src2 - second bit block
4257 
4258  \returns bitcount value
4259 
4260  @ingroup bitfunc
4261 */
4262 inline
4264  const bm::word_t* BMRESTRICT src1_end,
4265  const bm::word_t* BMRESTRICT src2)
4266 {
4267  unsigned arr_size = unsigned(src1_end - src1);
4268  return bit_operation_sub_count(src2, src2+arr_size, src1);
4269 }
4270 
4271 
4272 /*!
4273  \brief Performs bitblock test of SUB operation.
4274 
4275  \param src1 - first bit block.
4276  \param src1_end - first bit block end
4277  \param src2 - second bit block
4278 
4279  \returns non zero value if there are any bits
4280 
4281  @ingroup bitfunc
4282 */
4283 inline
4285  const bm::word_t* BMRESTRICT src1_end,
4286  const bm::word_t* BMRESTRICT src2)
4287 {
4288  if (IS_EMPTY_BLOCK(src1))
4289  {
4290  return 0;
4291  }
4292 
4293  if (IS_EMPTY_BLOCK(src2)) // nothing to diff
4294  {
4295  return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
4296  }
4297  return bit_block_sub_any(src1, src1_end, src2);
4298 }
4299 
4300 
4301 
4302 /*!
4303  \brief Performs bitblock OR operation and calculates bitcount of the result.
4304 
4305  \param src1 - first bit block.
4306  \param src1_end - first bit block end
4307  \param src2 - second bit block.
4308 
4309  \returns bitcount value
4310 
4311  @ingroup bitfunc
4312 */
4313 inline
4315  const bm::word_t* BMRESTRICT src1_end,
4316  const bm::word_t* BMRESTRICT src2)
4317 {
4318  if (IS_EMPTY_BLOCK(src1))
4319  {
4320  if (!IS_EMPTY_BLOCK(src2))
4321  return bit_block_calc_count(src2, src2 + (src1_end - src1));
4322  else
4323  return 0; // both blocks are empty
4324  }
4325  else
4326  {
4327  if (IS_EMPTY_BLOCK(src2))
4328  return bit_block_calc_count(src1, src1_end);
4329  }
4330 
4331  return bit_block_or_count(src1, src1_end, src2);
4332 }
4333 
4334 /*!
4335  \brief Performs bitblock OR operation test.
4336 
4337  \param src1 - first bit block.
4338  \param src1_end - first bit block end
4339  \param src2 - second bit block.
4340 
4341  \returns non zero value if there are any bits
4342 
4343  @ingroup bitfunc
4344 */
4345 inline
4347  const bm::word_t* BMRESTRICT src1_end,
4348  const bm::word_t* BMRESTRICT src2)
4349 {
4350  if (IS_EMPTY_BLOCK(src1))
4351  {
4352  if (!IS_EMPTY_BLOCK(src2))
4353  return !bit_is_all_zero((bm::wordop_t*)src2,
4354  (bm::wordop_t*)(src2 + (src1_end - src1)));
4355  else
4356  return 0; // both blocks are empty
4357  }
4358  else
4359  {
4360  if (IS_EMPTY_BLOCK(src2))
4361  return !bit_is_all_zero((bm::wordop_t*)src1, (bm::wordop_t*)src1_end);
4362  }
4363 
4364  return bit_block_or_any(src1, src1_end, src2);
4365 }
4366 
4367 
4368 
4369 /*!
4370  \brief Plain bitblock OR operation.
4371  Function does not analyse availability of source and destination blocks.
4372 
4373  \param dst - destination block.
4374  \param src - source block.
4375 
4376  @ingroup bitfunc
4377 */
4379  const bm::word_t* BMRESTRICT src)
4380 {
4381 #ifdef BMVECTOPT
4382  VECT_OR_ARR(dst, src, src + bm::set_block_size);
4383 #else
4384  const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*)src;
4385  const bm::wordop_t* BMRESTRICT wrd_end = (wordop_t*)(src + set_block_size);
4386  bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
4387 
4388  do
4389  {
4390  dst_ptr[0] |= wrd_ptr[0];
4391  dst_ptr[1] |= wrd_ptr[1];
4392  dst_ptr[2] |= wrd_ptr[2];
4393  dst_ptr[3] |= wrd_ptr[3];
4394 
4395  dst_ptr+=4;
4396  wrd_ptr+=4;
4397 
4398  } while (wrd_ptr < wrd_end);
4399 #endif
4400 }
4401 
4402 
4403 /*!
4404  \brief Block OR operation. Makes analysis if block is 0 or FULL.
4405 
4406  \param dst - destination block.
4407  \param src - source block.
4408 
4409  \returns pointer on destination block.
4410  If returned value equal to src means that block mutation requested.
4411  NULL is valid return value.
4412 
4413  @ingroup bitfunc
4414 */
4415 inline
4417  const bm::word_t* BMRESTRICT src)
4418 {
4419  BM_ASSERT(dst || src);
4420 
4421  bm::word_t* ret = dst;
4422 
4423  if (IS_VALID_ADDR(dst)) // The destination block already exists
4424  {
4425  if (!IS_VALID_ADDR(src))
4426  {
4427  if (IS_FULL_BLOCK(src))
4428  {
4429  // if the source block is all set
4430  // just set the destination block
4431  ::memset(dst, 0xFF, bm::set_block_size * sizeof(bm::word_t));
4432  }
4433  }
4434  else
4435  {
4436  // Regular operation OR on the whole block
4437  bit_block_or(dst, src);
4438  }
4439  }
4440  else // The destination block does not exist yet
4441  {
4442  if (!IS_VALID_ADDR(src))
4443  {
4444  if (IS_FULL_BLOCK(src))
4445  {
4446  // The source block is all set, because dst does not exist
4447  // we can simply replace it.
4448  return const_cast<bm::word_t*>(FULL_BLOCK_FAKE_ADDR);
4449  }
4450  }
4451  else
4452  {
4453  if (dst == 0)
4454  {
4455  // The only case when we have to allocate the new block:
4456  // Src is all zero and Dst does not exist
4457  return const_cast<bm::word_t*>(src);
4458  }
4459  }
4460  }
4461  return ret;
4462 }
4463 
4464 /*!
4465  \brief Plain bitblock SUB (AND NOT) operation.
4466  Function does not analyse availability of source and destination blocks.
4467 
4468  \param dst - destination block.
4469  \param src - source block.
4470 
4471  @ingroup bitfunc
4472 */
4473 inline
4475  const bm::word_t* BMRESTRICT src)
4476 {
4477 #ifdef BMVECTOPT
4478  VECT_SUB_ARR(dst, src, src + bm::set_block_size);
4479 #else
4480  const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
4481  const bm::wordop_t* BMRESTRICT wrd_end =
4482  (wordop_t*) (src + bm::set_block_size);
4483  bm::wordop_t* dst_ptr = (wordop_t*)dst;
4484 
4485  // Regular operation AND-NOT on the whole block.
4486  do
4487  {
4488  dst_ptr[0] &= ~wrd_ptr[0];
4489  dst_ptr[1] &= ~wrd_ptr[1];
4490  dst_ptr[2] &= ~wrd_ptr[2];
4491  dst_ptr[3] &= ~wrd_ptr[3];
4492 
4493  dst_ptr+=4;
4494  wrd_ptr+=4;
4495  } while (wrd_ptr < wrd_end);
4496 #endif
4497 
4498 }
4499 
4500 
4501 /*!
4502  \brief bitblock SUB operation.
4503 
4504  \param dst - destination block.
4505  \param src - source block.
4506 
4507  \returns pointer on destination block.
4508  If returned value equal to src means that block mutation requested.
4509  NULL is valid return value.
4510 
4511  @ingroup bitfunc
4512 */
4513 inline
4515  const bm::word_t* BMRESTRICT src)
4516 {
4517  BM_ASSERT(dst || src);
4518 
4519  bm::word_t* ret = dst;
4520  if (IS_VALID_ADDR(dst)) // The destination block already exists
4521  {
4522  if (!IS_VALID_ADDR(src))
4523  {
4524  if (IS_FULL_BLOCK(src))
4525  {
4526  // If the source block is all set
4527  // just clean the destination block
4528  return 0;
4529  }
4530  }
4531  else
4532  {
4533  bit_block_sub(dst, src);
4534  }
4535  }
4536  else // The destination block does not exist yet
4537  {
4538  if (!IS_VALID_ADDR(src))
4539  {
4540  if (IS_FULL_BLOCK(src))
4541  {
4542  // The source block is full
4543  return 0;
4544  }
4545  }
4546  else
4547  {
4548  if (IS_FULL_BLOCK(dst))
4549  {
4550  // The only case when we have to allocate the new block:
4551  // dst is all set and src exists
4552  return const_cast<bm::word_t*>(src);
4553  }
4554  }
4555  }
4556  return ret;
4557 }
4558 
4559 
4560 /*!
4561  \brief Plain bitblock XOR operation.
4562  Function does not analyse availability of source and destination blocks.
4563 
4564  \param dst - destination block.
4565  \param src - source block.
4566 
4567  @ingroup bitfunc
4568 */
4569 inline
4571  const bm::word_t* BMRESTRICT src)
4572 {
4573 #ifdef BMVECTOPT
4574  VECT_XOR_ARR(dst, src, src + bm::set_block_size);
4575 #else
4576  const bm::wordop_t* BMRESTRICT wrd_ptr = (wordop_t*) src;
4577  const bm::wordop_t* BMRESTRICT wrd_end =
4578  (wordop_t*) (src + bm::set_block_size);
4579  bm::wordop_t* BMRESTRICT dst_ptr = (wordop_t*)dst;
4580 
4581  // Regular XOR operation on the whole block.
4582  do
4583  {
4584  dst_ptr[0] ^= wrd_ptr[0];
4585  dst_ptr[1] ^= wrd_ptr[1];
4586  dst_ptr[2] ^= wrd_ptr[2];
4587  dst_ptr[3] ^= wrd_ptr[3];
4588 
4589  dst_ptr+=4;
4590  wrd_ptr+=4;
4591  } while (wrd_ptr < wrd_end);
4592 #endif
4593 
4594 }
4595 
4596 
4597 /*!
4598  \brief bitblock XOR operation.
4599 
4600  \param dst - destination block.
4601  \param src - source block.
4602 
4603  \returns pointer on destination block.
4604  If returned value equal to src means that block mutation requested.
4605  NULL is valid return value.
4606 
4607  @ingroup bitfunc
4608 */
4609 inline
4611  const bm::word_t* BMRESTRICT src)
4612 {
4613  BM_ASSERT(dst || src);
4614  if (src == dst) return 0; // XOR rule
4615 
4616  bm::word_t* ret = dst;
4617 
4618  if (IS_VALID_ADDR(dst)) // The destination block already exists
4619  {
4620  if (!src) return dst;
4621 
4622  bit_block_xor(dst, src);
4623  }
4624  else // The destination block does not exist yet
4625  {
4626  if (!src) return dst; // 1 xor 0 = 1
4627 
4628  // Here we have two cases:
4629  // if dest block is full or zero if zero we need to copy the source
4630  // otherwise XOR loop against 0xFF...
4631  //BM_ASSERT(dst == 0);
4632  return const_cast<bm::word_t*>(src); // src is the final result
4633  }
4634  return ret;
4635 }
4636 
4637 /*!
4638  \brief Performs bitblock XOR operation and calculates bitcount of the result.
4639 
4640  \param src1 - bit block start ptr
4641  \param src1_end - bit block end ptr
4642  \param src2 - second bit block
4643 
4644  \returns bitcount value
4645 
4646  @ingroup bitfunc
4647 */
4648 inline
4650  const bm::word_t* BMRESTRICT src1_end,
4651  const bm::word_t* BMRESTRICT src2)
4652 {
4653  if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
4654  {
4655  if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
4656  return 0;
4657  const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
4658  return bit_block_calc_count(block, block + (src1_end - src1));
4659  }
4660  return bit_block_xor_count(src1, src1_end, src2);
4661 }
4662 
4663 /*!
4664  \brief Performs bitblock XOR operation test.
4665 
4666  \param src1 - bit block start ptr
4667  \param src1_end - bit block end ptr
4668  \param src2 - second bit block ptr
4669 
4670  \returns non zero value if there are bits
4671 
4672  @ingroup bitfunc
4673 */
4674 inline
4676  const bm::word_t* BMRESTRICT src1_end,
4677  const bm::word_t* BMRESTRICT src2)
4678 {
4679  if (IS_EMPTY_BLOCK(src1) || IS_EMPTY_BLOCK(src2))
4680  {
4681  if (IS_EMPTY_BLOCK(src1) && IS_EMPTY_BLOCK(src2))
4682  return 0;
4683  const bm::word_t* block = IS_EMPTY_BLOCK(src1) ? src2 : src1;
4684  return !bit_is_all_zero((bm::wordop_t*)block,
4685  (bm::wordop_t*)(block + (src1_end - src1)));
4686  }
4687  return bit_block_xor_any(src1, src1_end, src2);
4688 }
4689 
4690 
4691 
4692 /**
4693  \brief Inspects block for full zero words
4694 
4695  \param blk - bit block pointer
4696  \param data_size - data size
4697 
4698  \return size of all non-zero words
4699 
4700  @ingroup bitfunc
4701 */
4702 
4703 template<class T>
4704 unsigned bit_count_nonzero_size(const T* blk,
4705  unsigned data_size)
4706 {
4707  BM_ASSERT(blk && data_size);
4708  unsigned count = 0;
4709  const T* blk_end = blk + data_size - 2;
4710 
4711  do
4712  {
4713  if (*blk == 0)
4714  {
4715  // scan fwd to find 0 island length
4716  const T* blk_j = blk + 1;
4717  for (; blk_j < blk_end; ++blk_j)
4718  {
4719  if (*blk_j != 0)
4720  break;
4721  }
4722  blk = blk_j-1;
4723  count += (unsigned)sizeof(gap_word_t);
4724  }
4725  else
4726  {
4727  // scan fwd to find non-0 island length
4728  const T* blk_j = blk + 1;
4729  for ( ; blk_j < blk_end; ++blk_j)
4730  {
4731  if (*blk_j == 0)
4732  {
4733  // look ahead to identify and ignore short 0-run
4734  if (blk_j[1] | blk_j[2])
4735  {
4736  // skip zero word
4737  ++blk_j;
4738  continue;
4739  }
4740  break;
4741  }
4742  }
4743  count += unsigned(sizeof(gap_word_t));
4744  // count all bit-words now
4745  count += (unsigned)((blk_j - blk) * sizeof(T));
4746  blk = blk_j;
4747  }
4748  ++blk;
4749  }
4750  while(blk < blk_end);
4751 
4752  return count + unsigned(2 * sizeof(T));
4753 }
4754 
4755 
4756 /**
4757  \brief Searches for the next 1 bit in the BIT block
4758  \param data - BIT buffer
4759  \param nbit - bit index to start checking from
4760  \param prev - returns previously checked value
4761 
4762  @ingroup bitfunc
4763 */
4764 inline
4766  unsigned nbit,
4767  bm::id_t* prev)
4768 {
4769  BMREGISTER bm::id_t p = *prev;
4770  int found = 0;
4771 
4772  for(;;)
4773  {
4774  unsigned nword = nbit >> bm::set_word_shift;
4775  if (nword >= bm::set_block_size) break;
4776 
4777  BMREGISTER bm::word_t val = data[nword] >> (p & bm::set_word_mask);
4778  if (val)
4779  {
4780  unsigned trail_z = bm::word_trailing_zeros(val);
4781  if (trail_z)
4782  {
4783  val >>= trail_z;
4784  p += trail_z;
4785  BM_ASSERT(val & 1);
4786  }
4787  ++found;
4788  break;
4789  }
4790  else
4791  {
4792  p += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
4793  nbit += (bm::set_word_mask + 1) - (nbit & bm::set_word_mask);
4794  }
4795  }
4796  *prev = p;
4797  return found;
4798 }
4799 
4800 /*!
4801  \brief Templated algorithm to unpacks octet based word into list of ON bit indexes
4802  \param w - value
4803  \param func - bit functor
4804 
4805  @ingroup bitfunc
4806 */
4807 template<typename T, typename F>
4808 void bit_for_each_4(T w, F& func)
4809 {
4810  for (unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
4811  {
4812  switch (w & 15) // 1111
4813  {
4814  case 0: // 0000
4815  break;
4816  case 1: // 0001
4817  func(sub_octet);
4818  break;
4819  case 2: // 0010
4820  func(sub_octet + 1);
4821  break;
4822  case 3: // 0011
4823  func(sub_octet, sub_octet + 1);
4824  break;
4825  case 4: // 0100
4826  func(sub_octet + 2);
4827  break;
4828  case 5: // 0101
4829  func(sub_octet, sub_octet + 2);
4830  break;
4831  case 6: // 0110
4832  func(sub_octet + 1, sub_octet + 2);
4833  break;
4834  case 7: // 0111
4835  func(sub_octet, sub_octet + 1, sub_octet + 2);
4836  break;
4837  case 8: // 1000
4838  func(sub_octet + 3);
4839  break;
4840  case 9: // 1001
4841  func(sub_octet, sub_octet + 3);
4842  break;
4843  case 10: // 1010
4844  func(sub_octet + 1, sub_octet + 3);
4845  break;
4846  case 11: // 1011
4847  func(sub_octet, sub_octet + 1, sub_octet + 3);
4848  break;
4849  case 12: // 1100
4850  func(sub_octet + 2, sub_octet + 3);
4851  break;
4852  case 13: // 1101
4853  func(sub_octet, sub_octet + 2, sub_octet + 3);
4854  break;
4855  case 14: // 1110
4856  func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
4857  break;
4858  case 15: // 1111
4859  func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
4860  break;
4861  default:
4862  BM_ASSERT(0);
4863  break;
4864  }
4865 
4866  } // for
4867 }
4868 
4869 
4870 /*!
4871  \brief Templated algorithm to unpacks word into list of ON bit indexes
4872  \param w - value
4873  \param func - bit functor
4874 
4875  @ingroup bitfunc
4876 */
4877 template<typename T, typename F>
4878 void bit_for_each(T w, F& func)
4879 {
4880  // Note: 4-bit table method works slower than plain check approach
4881  for (unsigned octet = 0; w != 0; w >>= 8, octet += 8)
4882  {
4883  if (w & 1) func(octet + 0);
4884  if (w & 2) func(octet + 1);
4885  if (w & 4) func(octet + 2);
4886  if (w & 8) func(octet + 3);
4887  if (w & 16) func(octet + 4);
4888  if (w & 32) func(octet + 5);
4889  if (w & 64) func(octet + 6);
4890  if (w & 128) func(octet + 7);
4891 
4892  } // for
4893 }
4894 
4895 /*! @brief Adaptor to copy 1 bits to array
4896  @internal
4897 */
4898 template<typename B> class copy_to_array_functor
4899 {
4900 public:
4901  copy_to_array_functor(B* bits): bp_(bits)
4902  {}
4903 
4904  B* ptr() { return bp_; }
4905 
4906  void operator()(unsigned bit_idx) { *bp_++ = (B)bit_idx; }
4907 
4908  void operator()(unsigned bit_idx0,
4909  unsigned bit_idx1)
4910  {
4911  bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
4912  bp_+=2;
4913  }
4914 
4915  void operator()(unsigned bit_idx0,
4916  unsigned bit_idx1,
4917  unsigned bit_idx2)
4918  {
4919  bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
4920  bp_+=3;
4921  }
4922 
4923  void operator()(unsigned bit_idx0,
4924  unsigned bit_idx1,
4925  unsigned bit_idx2,
4926  unsigned bit_idx3)
4927  {
4928  bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
4929  bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
4930  bp_+=4;
4931  }
4932 
4933 private:
4935  copy_to_array_functor& operator=(const copy_to_array_functor&);
4936 private:
4937  B* bp_;
4938 };
4939 
4940 
4941 /*!
4942  \brief Unpacks word into list of ON bit indexes (quad-bit based)
4943  \param w - value
4944  \param bits - pointer on the result array
4945  \return number of bits in the list
4946 
4947  @ingroup bitfunc
4948 */
4949 template<typename T,typename B> unsigned bit_list_4(T w, B* bits)
4950 {
4951  copy_to_array_functor<B> func(bits);
4952  bit_for_each_4(w, func);
4953  return (unsigned)(func.ptr() - bits);
4954 }
4955 
4956 /*!
4957  \brief Unpacks word into list of ON bit indexes using popcnt method
4958  \param w - value
4959  \param bits - pointer on the result array
4960  \return number of bits in the list
4961 
4962  @ingroup bitfunc
4963 */
4964 template<typename B>
4965 unsigned short bitscan_popcnt(bm::id_t w, B* bits, unsigned offs = 0)
4966 {
4967  unsigned pos = 0;
4968  while (w)
4969  {
4970  bm::id_t t = w & -w;
4971  bits[pos++] = (B)(bm::word_bitcount(t - 1) + offs);
4972  w &= w - 1;
4973  }
4974  return (unsigned short)pos;
4975 }
4976 
4977 /*!
4978  \brief Unpacks 64-bit word into list of ON bit indexes using popcnt method
4979  \param w - value
4980  \param bits - pointer on the result array
4981  \param offs - bit address offset to add (0 - default)
4982  \return number of bits in the list
4983 
4984  @ingroup bitfunc
4985 */
4986 template<typename B>
4987 unsigned short bitscan_popcnt64(bm::id64_t w, B* bits)
4988 {
4989  unsigned short pos = 0;
4990  while (w)
4991  {
4992  bm::id64_t t = w & -w;
4993  bits[pos++] = (B) bm::word_bitcount64(t - 1);
4994  w &= w - 1;
4995  }
4996  return pos;
4997 }
4998 
4999 template<typename V, typename B>
5000 unsigned short bitscan(V w, B* bits)
5001 {
5002  if (bm::conditional<sizeof(V) == 8>::test())
5003  {
5004  return bm::bitscan_popcnt64(w, bits);
5005  }
5006  else
5007  {
5008  return bm::bitscan_popcnt((bm::word_t)w, bits);
5009  }
5010 }
5011 
5012 
5013 
5014 
5015 /*!
5016  \brief Unpacks word into list of ON bit indexes
5017  \param w - value
5018  \param bits - pointer on the result array
5019  \return number of bits in the list
5020 
5021  @ingroup bitfunc
5022 */
5023 template<typename T,typename B> unsigned bit_list(T w, B* bits)
5024 {
5025  copy_to_array_functor<B> func(bits);
5026  bit_for_each(w, func);
5027  return (unsigned)(func.ptr() - bits);
5028 }
5029 
5030 
5031 /*!
5032  @brief Choose best representation for a bit-block
5033  @ingroup bitfunc
5034 */
5035 inline
5037  unsigned total_possible_bitcount,
5038  unsigned gap_count,
5039  unsigned block_size)
5040 {
5041  unsigned arr_size = unsigned(sizeof(bm::gap_word_t) * bit_count + sizeof(bm::gap_word_t));
5042  unsigned gap_size = unsigned(sizeof(bm::gap_word_t) * gap_count + sizeof(bm::gap_word_t));
5043  unsigned inv_arr_size = unsigned(sizeof(bm::gap_word_t) * (total_possible_bitcount - bit_count) + sizeof(bm::gap_word_t));
5044 
5045  if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
5046  {
5047  return bm::set_gap;
5048  }
5049 
5050  if (arr_size < inv_arr_size)
5051  {
5052  if ((arr_size < block_size) && (arr_size < gap_size))
5053  {
5054  return bm::set_array1;
5055  }
5056  }
5057  else
5058  {
5059  if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
5060  {
5061  return bm::set_array0;
5062  }
5063  }
5064  return bm::set_bitset;
5065 }
5066 
5067 /*!
5068  @brief Convert bit block into an array of ints corresponding to 1 bits
5069  @ingroup bitfunc
5070 */
5071 template<typename T> T bit_convert_to_arr(T* BMRESTRICT dest,
5072  const unsigned* BMRESTRICT src,
5073  bm::id_t bits,
5074  unsigned dest_len,
5075  unsigned mask = 0)
5076 {
5077  T* BMRESTRICT pcurr = dest;
5078  for (unsigned bit_idx=0; bit_idx < bits; ++src,bit_idx += unsigned(sizeof(*src) * 8))
5079  {
5080  unsigned val = *src ^ mask; // possible to invert value by XOR 0xFF..
5081  if (val == 0)
5082  {
5083  continue;
5084  }
5085  if (pcurr + sizeof(val)*8 >= dest + dest_len) // insufficient space
5086  {
5087  return 0;
5088  }
5089  unsigned char b_list[64];
5090  unsigned word_bit_cnt = bm::bitscan_popcnt(val, b_list);
5091  for (unsigned j = 0; j < word_bit_cnt; ++j)
5092  {
5093  *pcurr++ = (T)(b_list[j] + bit_idx);
5094  }
5095  } // for
5096  return (T)(pcurr - dest);
5097 }
5098 
5099 
5100 
5101 /*! @brief Calculates memory overhead for number of gap blocks sharing
5102  the same memory allocation table (level lengths table).
5103  @ingroup gapfunc
5104 */
5105 template<typename T>
5106 unsigned gap_overhead(const T* length,
5107  const T* length_end,
5108  const T* glevel_len)
5109 {
5110  BM_ASSERT(length && length_end && glevel_len);
5111 
5112  unsigned overhead = 0;
5113  for (;length < length_end; ++length)
5114  {
5115  unsigned len = *length;
5116  int level = gap_calc_level(len, glevel_len);
5117  BM_ASSERT(level >= 0 && level < (int)bm::gap_levels);
5118  unsigned capacity = glevel_len[level];
5119  BM_ASSERT(capacity >= len);
5120  overhead += capacity - len;
5121  }
5122  return overhead;
5123 }
5124 
5125 
5126 /*! @brief Finds optimal gap blocks lengths.
5127  @param length - first element of GAP lengths array
5128  @param length_end - end of the GAP lengths array
5129  @param glevel_len - destination GAP lengths array
5130  @ingroup gapfunc
5131 */
5132 template<typename T>
5133 bool improve_gap_levels(const T* length,
5134  const T* length_end,
5135  T* glevel_len)
5136 {
5137  BM_ASSERT(length && length_end && glevel_len);
5138 
5139  size_t lsize = length_end - length;
5140 
5141  BM_ASSERT(lsize);
5142 
5143  gap_word_t max_len = 0;
5144  unsigned i;
5145  for (i = 0; i < lsize; ++i)
5146  {
5147  if (length[i] > max_len)
5148  max_len = length[i];
5149  }
5150  if (max_len < 5 || lsize <= bm::gap_levels)
5151  {
5152  glevel_len[0] = max_len + 4;
5153  for (i = 1; i < bm::gap_levels; ++i)
5154  {
5155  glevel_len[i] = bm::gap_max_buff_len;
5156  }
5157  return true;
5158  }
5159 
5160  glevel_len[bm::gap_levels-1] = max_len + 5;
5161 
5162  unsigned min_overhead = gap_overhead(length, length_end, glevel_len);
5163  bool is_improved = false;
5164 
5165  // main problem solving loop
5166  //
5167  for (i = bm::gap_levels-2; ; --i)
5168  {
5169  unsigned opt_len = 0;
5170  unsigned j;
5171  bool imp_flag = false;
5172  gap_word_t gap_saved_value = glevel_len[i];
5173  for (j = 0; j < lsize; ++j)
5174  {
5175  glevel_len[i] = length[j]+4;
5176  unsigned ov = gap_overhead(length, length_end, glevel_len);
5177  if (ov <= min_overhead)
5178  {
5179  min_overhead = ov;
5180  opt_len = length[j]+4;
5181  imp_flag = true;
5182  }
5183  }
5184  if (imp_flag)
5185  {
5186  glevel_len[i] = (T)opt_len; // length[opt_idx]+4;
5187  is_improved = true;
5188  }
5189  else
5190  {
5191  glevel_len[i] = gap_saved_value;
5192  }
5193  if (i == 0)
5194  break;
5195  }
5196  //
5197  // Remove duplicates
5198  //
5199 
5200  T val = *glevel_len;
5201  T* gp = glevel_len;
5202  T* res = glevel_len;
5203  for (i = 0; i < bm::gap_levels; ++i)
5204  {
5205  if (val != *gp)
5206  {
5207  val = *gp;
5208  *++res = val;
5209  }
5210  ++gp;
5211  }
5212 
5213  // Filling the "unused" part with max. possible value
5214  while (++res < (glevel_len + bm::gap_levels))
5215  {
5216  *res = bm::gap_max_buff_len;
5217  }
5218 
5219  return is_improved;
5220 
5221 }
5222 
5223 
5224 
5225 /**
5226  Bit-block get adapter, takes bitblock and represents it as a
5227  get_32() accessor function
5228  \internal
5229 */
5231 {
5232 public:
5233  bitblock_get_adapter(const bm::word_t* bit_block) : b_(bit_block) {}
5234 
5236  bm::word_t get_32() { return *b_++; }
5237 private:
5238  const bm::word_t* b_;
5239 };
5240 
5241 
5242 /**
5243  Bit-block store adapter, takes bitblock and saves results into it
5244  \internal
5245 */
5247 {
5248 public:
5249  bitblock_store_adapter(bm::word_t* bit_block) : b_(bit_block) {}
5251  void push_back(bm::word_t w) { *b_++ = w; }
5252 private:
5253  bm::word_t* b_;
5254 };
5255 
5256 /**
5257  Bit-block sum adapter, takes values and sums it
5258  /internal
5259 */
5261 {
5262 public:
5263  bitblock_sum_adapter() : sum_(0) {}
5265  void push_back(bm::word_t w) { this->sum_+= w; }
5266  /// Get accumulated sum
5267  bm::word_t sum() const { return this->sum_; }
5268 private:
5269  bm::word_t sum_;
5270 };
5271 
5272 /**
5273  Adapter to get words from a range stream
5274  (see range serialized bit-block)
5275  \internal
5276 */
5277 template<class DEC> class decoder_range_adapter
5278 {
5279 public:
5280  decoder_range_adapter(DEC& dec, unsigned from_idx, unsigned to_idx)
5281  : decoder_(dec),
5282  from_(from_idx),
5283  to_(to_idx),
5284  cnt_(0)
5285  {}
5286 
5288  {
5289  if (cnt_ < from_ || cnt_ > to_)
5290  {
5291  ++cnt_; return 0;
5292  }
5293  ++cnt_;
5294  return decoder_.get_32();
5295  }
5296 
5297 private:
5298  DEC& decoder_;
5299  unsigned from_;
5300  unsigned to_;
5301  unsigned cnt_;
5302 };
5303 
5304 
5305 /*!
5306  Abstract recombination algorithm for two bit-blocks
5307  Bit blocks can come as dserialization decoders or bit-streams
5308 */
5309 template<class It1, class It2, class BinaryOp, class Encoder>
5310 void bit_recomb(It1& it1, It2& it2,
5311  BinaryOp& op,
5312  Encoder& enc,
5313  unsigned block_size = bm::set_block_size)
5314 {
5315  for (unsigned i = 0; i < block_size; ++i)
5316  {
5317  bm::word_t w1 = it1.get_32();
5318  bm::word_t w2 = it2.get_32();
5319  bm::word_t w = op(w1, w2);
5320  enc.push_back( w );
5321  } // for
5322 }
5323 
5324 /// Bit AND functor
5325 template<typename W> struct bit_AND
5326 {
5327  W operator()(W w1, W w2) { return w1 & w2; }
5328 };
5329 
5330 /// Bit OR functor
5331 template<typename W> struct bit_OR
5332 {
5333  W operator()(W w1, W w2) { return w1 | w2; }
5334 };
5335 
5336 /// Bit SUB functor
5337 template<typename W> struct bit_SUB
5338 {
5339  W operator()(W w1, W w2) { return w1 & ~w2; }
5340 };
5341 
5342 /// Bit XOR functor
5343 template<typename W> struct bit_XOR
5344 {
5345  W operator()(W w1, W w2) { return w1 ^ w2; }
5346 };
5347 
5348 /// Bit ASSIGN functor
5349 template<typename W> struct bit_ASSIGN
5350 {
5351  W operator()(W, W w2) { return w2; }
5352 };
5353 
5354 /// Bit COUNT functor
5355 template<typename W> struct bit_COUNT
5356 {
5357  W operator()(W w1, W w2)
5358  {
5359  w1 = 0;
5360  BM_INCWORD_BITCOUNT(w1, w2);
5361  return w1;
5362  }
5363 };
5364 
5365 /// Bit COUNT AND functor
5366 template<typename W> struct bit_COUNT_AND
5367 {
5368  W operator()(W w1, W w2)
5369  {
5370  W r = 0;
5371  BM_INCWORD_BITCOUNT(r, w1 & w2);
5372  return r;
5373  }
5374 };
5375 
5376 /// Bit COUNT XOR functor
5377 template<typename W> struct bit_COUNT_XOR
5378 {
5379  W operator()(W w1, W w2)
5380  {
5381  W r = 0;
5382  BM_INCWORD_BITCOUNT(r, w1 ^ w2);
5383  return r;
5384  }
5385 };
5386 
5387 /// Bit COUNT OR functor
5388 template<typename W> struct bit_COUNT_OR
5389 {
5390  W operator()(W w1, W w2)
5391  {
5392  W r = 0;
5393  BM_INCWORD_BITCOUNT(r, w1 | w2);
5394  return r;
5395  }
5396 };
5397 
5398 
5399 /// Bit COUNT SUB AB functor
5400 template<typename W> struct bit_COUNT_SUB_AB
5401 {
5402  W operator()(W w1, W w2)
5403  {
5404  W r = 0;
5405  BM_INCWORD_BITCOUNT(r, w1 & (~w2));
5406  return r;
5407  }
5408 };
5409 
5410 /// Bit SUB BA functor
5411 template<typename W> struct bit_COUNT_SUB_BA
5412 {
5413  W operator()(W w1, W w2)
5414  {
5415  W r = 0;
5416  BM_INCWORD_BITCOUNT(r, w2 & (~w1));
5417  return r;
5418  }
5419 };
5420 
5421 /// Bit COUNT A functor
5422 template<typename W> struct bit_COUNT_A
5423 {
5424  W operator()(W w1, W )
5425  {
5426  W r = 0;
5427  BM_INCWORD_BITCOUNT(r, w1);
5428  return r;
5429  }
5430 };
5431 
5432 /// Bit COUNT B functor
5433 template<typename W> struct bit_COUNT_B
5434 {
5435  W operator()(W, W w2)
5436  {
5437  W r = 0;
5438  BM_INCWORD_BITCOUNT(r, w2);
5439  return r;
5440  }
5441 };
5442 
5443 typedef
5445  const gap_word_t*);
5446 
5447 typedef
5448 gap_word_t* (*gap_operation_func_type)(const gap_word_t* BMRESTRICT,
5449  const gap_word_t* BMRESTRICT,
5451  unsigned& );
5452 
5453 typedef
5455  const bm::word_t* BMRESTRICT,
5456  const bm::word_t* BMRESTRICT);
5457 
5458 
5459 template<bool T>
5461 {
5462  static
5464  static
5466  static
5468 
5469  static
5471  {
5472  return gap2bit_table_[i];
5473  }
5474 
5475  static
5477  {
5478  return gapop_table_[i];
5479  }
5480 
5481  static
5483  {
5484  return bit_op_count_table_[i];
5485  }
5486 };
5487 
5488 template<bool T>
5491  &gap_and_to_bitset<bm::gap_word_t>, // set_AND
5492  &gap_add_to_bitset<bm::gap_word_t>, // set_OR
5493  &gap_sub_to_bitset<bm::gap_word_t>, // set_SUB
5494  &gap_xor_to_bitset<bm::gap_word_t>, // set_XOR
5495  0
5496 };
5497 
5498 template<bool T>
5501  &gap_operation_and, // set_AND
5502  &gap_operation_or, // set_OR
5503  &gap_operation_sub, // set_SUB
5504  &gap_operation_xor, // set_XOR
5505  0
5506 };
5507 
5508 
5509 template<bool T>
5512  0, // set_AND
5513  0, // set_OR
5514  0, // set_SUB
5515  0, // set_XOR
5516  0, // set_ASSIGN
5517  0, // set_COUNT
5518  &bit_operation_and_count, // set_COUNT_AND
5519  &bit_operation_xor_count, // set_COUNT_XOR
5520  &bit_operation_or_count, // set_COUNT_OR
5521  &bit_operation_sub_count, // set_COUNT_SUB_AB
5522  &bit_operation_sub_count_inv, // set_COUNT_SUB_BA
5523  0, // set_COUNT_A
5524  0, // set_COUNT_B
5525 };
5526 
5527 
5528 const unsigned short set_bitscan_wave_size = 2;
5529 /*!
5530  \brief Unpacks word wave (2x 32-bit words)
5531  \param w_ptr - pointer on wave start
5532  \param bits - pointer on the result array
5533  \return number of bits in the list
5534 
5535  @ingroup bitfunc
5536  @internal
5537 */
5538 inline
5539 unsigned short bitscan_wave(const bm::word_t* w_ptr, unsigned char* bits)
5540 {
5541  bm::word_t w0, w1;
5542  unsigned short cnt;
5543 
5544  w0 = w_ptr[0];
5545  w1 = w_ptr[1];
5546 
5547 #if defined(BMAVX2OPT) || defined(BMSSE42OPT)
5548  // combine into 64-bit word and scan (when HW popcnt64 is available)
5549  bm::id64_t w = (bm::id64_t(w1) << 32) | w0;
5550  cnt = (unsigned short) bm::bitscan_popcnt64(w, bits);
5551 #else
5552  // decode wave as two 32-bit bitscan decodes
5553  cnt = w0 ? bm::bitscan_popcnt(w0, bits) : 0;
5554  cnt += w1 ? bm::bitscan_popcnt(w1, bits+cnt, 32) : 0; // +32 offset from the first word
5555 #endif
5556  return cnt;
5557 }
5558 
5559 
5560 
5561 } // namespace bm
5562 
5563 #endif
unsigned gap_capacity(const T *buf, const T *glevel_len)
Returs GAP block capacity.
Definition: bmfunc.h:2578
BMFORCEINLINE void push_back(bm::word_t w)
Definition: bmfunc.h:5251
void gap_buff_op(T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F &f, unsigned &dlen)
Abstract operation for GAP buffers. Receives functor F as a template argument.
Definition: bmfunc.h:1124
void bit_block_copy(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Bitblock copy operation.
Definition: bmfunc.h:3744
BMFORCEINLINE unsigned or_op(unsigned v1, unsigned v2)
GAP or functor.
Definition: bmfunc.h:3475
void add_bit_block()
cound bit block
Definition: bmfunc.h:68
unsigned gap_level(const T *buf)
Returs GAP blocks capacity level.
Definition: bmfunc.h:2606
Structure keeps all-left/right ON bits masks.
Definition: bmconst.h:203
bm::word_t * bit_operation_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Block OR operation. Makes analysis if block is 0 or FULL.
Definition: bmfunc.h:4416
BMFORCEINLINE unsigned gap_count_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount AND operation test.
Definition: bmfunc.h:3545
BMFORCEINLINE gap_word_t * gap_operation_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP XOR operation.
Definition: bmfunc.h:3570
void gap_and_to_bitset(unsigned *dest, const T *buf)
ANDs GAP block to bitblock.
Definition: bmfunc.h:1964
bm::id_t bit_operation_xor_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock XOR operation test.
Definition: bmfunc.h:4675
static BMFORCEINLINE bool is_full_block(const bm::word_t *bp)
Definition: bmfunc.h:311
gap_word_t gap_length[bm::set_total_blocks]
Array of all GAP block lengths in the bvector.
Definition: bmfunc.h:61
Bit COUNT AND functor.
Definition: bmfunc.h:5366
#define VECT_BITCOUNT_OR(first, last, mask)
Definition: bmsse4.h:204
#define BM_VECT_ALIGN
Definition: bmdef.h:250
BMFORCEINLINE bm::id_t word_bitcount(bm::id_t w)
Definition: bmfunc.h:125
Bit COUNT SUB AB functor.
Definition: bmfunc.h:5400
bm::id_t sse4_bit_block_calc_count_change(const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT block_end, unsigned *BMRESTRICT bit_count)
Definition: bmsse4.h:247
unsigned gap_control_sum(const T *buf)
Calculates sum of all words in GAP block. (For debugging purposes)
Definition: bmfunc.h:2402
ad-hoc conditional expressions
Definition: bmfunc.h:90
W operator()(W w1, W)
Definition: bmfunc.h:5424
const unsigned set_block_size
Definition: bmconst.h:44
#define VECT_COPY_BLOCK(dst, src, src_end)
Definition: bmsse4.h:228
operation
Bit operations enumeration.
Definition: bmfunc.h:260
set_operation
Nomenclature of set operations.
Definition: bmfunc.h:231
W operator()(W w1, W w2)
Definition: bmfunc.h:5345
const unsigned set_word_shift
Definition: bmconst.h:54
bm::id_t bit_count_change(bm::word_t w)
Definition: bmfunc.h:2972
W operator()(W, W w2)
Definition: bmfunc.h:5351
unsigned short bitscan_popcnt64(bm::id64_t w, B *bits)
Unpacks 64-bit word into list of ON bit indexes using popcnt method.
Definition: bmfunc.h:4987
bm::id_t bit_operation_or_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock OR operation test.
Definition: bmfunc.h:4346
unsigned gap_blocks
Number of GAP blocks.
Definition: bmfunc.h:55
BMFORCEINLINE unsigned sub_op(unsigned v1, unsigned v2)
GAP or functor.
Definition: bmfunc.h:3481
void operator()(unsigned bit_idx0, unsigned bit_idx1)
Definition: bmfunc.h:4908
void for_each_gap_dbit(const T *buf, F &func)
Iterate gap block as delta-bits with a functor.
Definition: bmfunc.h:2798
void bit_block_rotate_left_1_unr(bm::word_t *block)
Definition: bmfunc.h:3292
unsigned gap_add_value(T *buf, unsigned pos)
Add new value to the end of GAP buffer.
Definition: bmfunc.h:1452
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2, unsigned bit_idx3)
Definition: bmfunc.h:4923
Bit-block store adapter, takes bitblock and saves results into it.
Definition: bmfunc.h:5246
unsigned gap_bit_count(const T *buf, unsigned dsize=0)
Calculates number of bits ON in GAP buffer.
Definition: bmfunc.h:770
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:134
BMFORCEINLINE unsigned gap_operation_any_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP AND operation test.
Definition: bmfunc.h:3528
D gap_convert_to_arr(D *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len, bool invert=false)
Convert gap block into array of ints corresponding to 1 bits.
Definition: bmfunc.h:2853
GAP-RLE compression.
Definition: bmconst.h:116
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:1359
void gap_set_all(T *buf, unsigned set_max, unsigned value)
Sets all bits to 0 or 1 (GAP)
Definition: bmfunc.h:2434
Structure carries pointer on bit block with all bits 1.
Definition: bmfunc.h:287
int gap_calc_level(int len, const T *glevel_len)
Calculates GAP block capacity level.
Definition: bmfunc.h:2636
unsigned long long int id64_t
Definition: bmconst.h:30
Simple bitset.
Definition: bmconst.h:115
unsigned gap_overhead(const T *length, const T *length_end, const T *glevel_len)
Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level l...
Definition: bmfunc.h:5106
gap_word_t * gap_operation_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP SUB (AND NOT) operation.
Definition: bmfunc.h:3681
unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y, bm::id64_t u, bm::id64_t v)
Definition: bmfunc.h:170
bm::id_t gap_bitset_and_count(const unsigned *block, const T *buf)
Compute bitcount of bit block AND masked by GAP block.
Definition: bmfunc.h:1998
Adaptor to copy 1 bits to array.
Definition: bmfunc.h:4898
bm::id_t gap_bitset_and_any(const unsigned *block, const T *buf)
Bitcount test of bit block AND masked by GAP block.
Definition: bmfunc.h:2030
ByteOrder _byte_order
Definition: bmfunc.h:403
static bool test()
Definition: bmfunc.h:96
const unsigned short set_bitscan_wave_size
Definition: bmfunc.h:5528
Definition: bm.h:59
bm::id_t gap_bitset_sub_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block SUB masked by GAP block.
Definition: bmfunc.h:2104
bm::id_t sse2_bit_block_calc_count_change(const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT block_end, unsigned *BMRESTRICT bit_count)
Definition: bmsse2.h:230
BMFORCEINLINE bm::word_t get_32()
Definition: bmfunc.h:5236
Adapter to get words from a range stream (see range serialized bit-block)
Definition: bmfunc.h:5277
BMFORCEINLINE unsigned gap_count_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount OR operation test.
Definition: bmfunc.h:3656
unsigned bit_block_or_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of sourc...
Definition: bmfunc.h:4088
W operator()(W w1, W w2)
Definition: bmfunc.h:5402
size_t max_serialize_mem
Estimated maximum of memory required for serialization.
Definition: bmfunc.h:57
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
Definition: bmfunc.h:2343
void operator()(T dgap)
Definition: bmfunc.h:973
Bit COUNT OR functor.
Definition: bmfunc.h:5388
bm::word_t BM_VECT_ALIGN _p [bm::set_block_size] BM_VECT_ALIGN_ATTR
Definition: bmfunc.h:291
array of set 1 values
Definition: bmconst.h:117
void bit_count_change32(const bm::word_t *block, const bm::word_t *block_end, unsigned *bit_count, unsigned *gap_count)
Definition: bmfunc.h:2989
void for_each_dgap(const T *gap_buf, Func &func)
Definition: bmfunc.h:951
Bit-block get adapter, takes bitblock and represents it as a get_32() accessor function.
Definition: bmfunc.h:5230
#define VECT_BITCOUNT(first, last)
Definition: bmsse4.h:198
Bit ASSIGN functor.
Definition: bmfunc.h:5349
W operator()(W, W w2)
Definition: bmfunc.h:5435
bm::word_t * bit_operation_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock SUB operation.
Definition: bmfunc.h:4514
unsigned bit_block_or_count(const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of sourc...
Definition: bmfunc.h:4039
bm::id_t bit_operation_or_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock OR operation and calculates bitcount of the result.
Definition: bmfunc.h:4314
unsigned gap_bit_count_range(const T *const buf, T left, T right)
Counts 1 bits in GAP buffer in the closed [left, right] range.
Definition: bmfunc.h:870
void xor_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount)
XOR bit interval to 1 in the bitblock.
Definition: bmfunc.h:1806
bm::id_t bit_operation_sub_count_inv(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs inverted bitblock SUB operation and calculates bitcount of the result.
Definition: bmfunc.h:4263
unsigned bit_block_xor_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
Definition: bmfunc.h:3879
unsigned bit_list(T w, B *bits)
Unpacks word into list of ON bit indexes.
Definition: bmfunc.h:5023
Bit OR functor.
Definition: bmfunc.h:5331
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
Definition: bmfunc.h:324
void bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:4378
bool for_each_nzblock_if(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:684
bm::id_t bit_operation_xor_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock XOR operation and calculates bitcount of the result.
Definition: bmfunc.h:4649
unsigned gap_buff_count_op(const T *vect1, const T *vect2, F f)
Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument...
Definition: bmfunc.h:1275
bm::word_t sum() const
Get accumulated sum.
Definition: bmfunc.h:5267
W operator()(W w1, W w2)
Definition: bmfunc.h:5357
BMFORCEINLINE void push_back(bm::word_t w)
Definition: bmfunc.h:5265
bool gap_is_all_zero(const T *buf, unsigned set_max)
Temporary inverts all bits in the GAP buffer.
Definition: bmfunc.h:2537
BMFORCEINLINE unsigned test_bit(const unsigned *block, unsigned bitpos)
Test 1 bit in a block.
Definition: bmfunc.h:1665
void bit_for_each(T w, F &func)
Templated algorithm to unpacks word into list of ON bit indexes.
Definition: bmfunc.h:4878
unsigned bit_count_nonzero_size(const T *blk, unsigned data_size)
Inspects block for full zero words.
Definition: bmfunc.h:4704
unsigned bit_block_and_any(const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source b...
Definition: bmfunc.h:3848
unsigned bit_block_xor_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of sour...
Definition: bmfunc.h:3929
unsigned gap_bit_count_to(const T *const buf, T right)
Counts 1 bits in GAP buffer in the closed [0, right] range.
Definition: bmfunc.h:911
#define VECT_BITCOUNT_XOR(first, last, mask)
Definition: bmsse4.h:207
void bit_for_each_4(T w, F &func)
Templated algorithm to unpacks octet based word into list of ON bit indexes.
Definition: bmfunc.h:4808
bm::id_t gap_bitset_xor_count(const unsigned *block, const T *buf)
Compute bitcount of bit block XOR masked by GAP block.
Definition: bmfunc.h:2143
int parallel_popcnt_32(unsigned int n)
Definition: bmfunc.h:139
W operator()(W w1, W w2)
Definition: bmfunc.h:5368
int bit_find_in_block(const bm::word_t *data, unsigned nbit, bm::id_t *prev)
Searches for the next 1 bit in the BIT block.
Definition: bmfunc.h:4765
bm::id_t bit_operation_and_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock AND operation and calculates bitcount of the result.
Definition: bmfunc.h:4185
size_t memory_used
Memory used by bitvector including temp and service blocks.
Definition: bmfunc.h:59
bool gap_is_all_one(const T *buf, unsigned set_max)
Checks if GAP block is all-one.
Definition: bmfunc.h:2551
bool bit_is_all_zero(const bm::wordop_t *start, const bm::wordop_t *end)
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:3438
void gap_invert(T *buf)
Inverts all bits in the GAP buffer.
Definition: bmfunc.h:2505
unsigned gap_test(const T *buf, unsigned pos)
Tests if bit = pos is true.
Definition: bmfunc.h:481
BMFORCEINLINE unsigned gap_count_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount XOR operation test.
Definition: bmfunc.h:3611
int bitcmp(const T *buf1, const T *buf2, unsigned len)
Lexicographical comparison of BIT buffers.
Definition: bmfunc.h:2675
void operator()(unsigned bit_idx)
Definition: bmfunc.h:4906
unsigned int word_t
Definition: bmconst.h:35
bm::id_t bit_block_any_range(const bm::word_t *block, bm::word_t left, bm::word_t right)
Definition: bmfunc.h:3327
BMFORCEINLINE void set_bit(unsigned *dest, unsigned bitpos)
Set 1 bit in a block.
Definition: bmfunc.h:1652
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:135
#define BMREGISTER
Definition: bmdef.h:82
W operator()(W w1, W w2)
Definition: bmfunc.h:5390
void for_each_nzblock2(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:655
Bit XOR functor.
Definition: bmfunc.h:5343
int wordcmp(T a, T b)
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and refe...
Definition: bmfunc.h:374
bm::id_t bit_operation_and_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock AND operation test.
Definition: bmfunc.h:4208
static all_set_block _block
Definition: bmfunc.h:316
BMFORCEINLINE bm::id_t word_trailing_zeros(bm::id_t w)
Definition: bmfunc.h:205
static bo _bo
Definition: bmfunc.h:431
const unsigned gap_max_buff_len
Definition: bmconst.h:62
unsigned gap_bfind(const T *buf, unsigned pos, unsigned *is_set)
Definition: bmfunc.h:453
#define VECT_AND_ARR(dst, src, src_end)
Definition: bmsse4.h:216
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:525
Bit-block sum adapter, takes values and sums it /internal.
Definition: bmfunc.h:5260
Bit COUNT functor.
Definition: bmfunc.h:5355
F bmfor_each(T first, T last, F f)
Definition: bmfunc.h:737
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value)
Bitblock memset operation.
Definition: bmfunc.h:2325
void bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:3764
static ByteOrder byte_order()
Definition: bmfunc.h:433
bm::id_t bit_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right)
Definition: bmfunc.h:3150
#define VECT_SUB_ARR(dst, src, src_end)
Definition: bmsse4.h:222
const unsigned gap_levels
Definition: bmconst.h:66
unsigned bit_convert_to_gap(T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len)
Converts bit block to GAP.
Definition: bmfunc.h:2708
bool is_bits_one(const bm::wordop_t *start, const bm::wordop_t *end)
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:3413
Internal structure.
Definition: bmfunc.h:399
unsigned short gap_word_t
Definition: bmconst.h:60
unsigned gap_set_array(T *buf, const T *arr, unsigned len)
Convert array to GAP buffer.
Definition: bmfunc.h:1537
int gap_find_in_block(const T *buf, unsigned nbit, bm::id_t *prev)
Searches for the next 1 bit in the GAP block.
Definition: bmfunc.h:1627
BMFORCEINLINE unsigned gap_operation_any_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP SUB operation test.
Definition: bmfunc.h:3706
void gap_xor_to_bitset(unsigned *dest, const T *buf)
XOR GAP block to bitblock.
Definition: bmfunc.h:1900
gap_word_t * gap_operation_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP OR operation.
Definition: bmfunc.h:3636
bm::id_t bit_operation_sub_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock SUB operation and calculates bitcount of the result.
Definition: bmfunc.h:4233
void bit_block_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:4570
T sum_arr(T *first, T *last)
Definition: bmfunc.h:749
void gap_sub_to_bitset(unsigned *dest, const T *buf)
SUB (AND NOT) GAP block to bitblock.
Definition: bmfunc.h:1868
#define VECT_IS_ONE_BLOCK(dst, dst_end)
Definition: bmsse4.h:237
BMFORCEINLINE unsigned gap_count_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount SUB (AND NOT) operation test.
Definition: bmfunc.h:3723
bm::id_t bit_block_calc_count_change(const bm::word_t *block, const bm::word_t *block_end, unsigned *bit_count)
Definition: bmfunc.h:3053
void(* gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
Definition: bmfunc.h:5444
bm::set_representation best_representation(unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
Choose best representation for a bit-block.
Definition: bmfunc.h:5036
Bit SUB BA functor.
Definition: bmfunc.h:5411
#define BM_INCWORD_BITCOUNT(cnt, w)
Definition: bmdef.h:273
unsigned bit_block_sub_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
Definition: bmfunc.h:3960
bitblock_get_adapter(const bm::word_t *bit_block)
Definition: bmfunc.h:5233
#define VECT_BITCOUNT_AND(first, last, mask)
Definition: bmsse4.h:201
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
Definition: bmfunc.h:5470
BMFORCEINLINE int word_bitcount64(bm::id64_t x)
Definition: bmfunc.h:154
BMFORCEINLINE unsigned xor_op(unsigned v1, unsigned v2)
GAP xor functor.
Definition: bmfunc.h:3468
void bit_block_rotate_left_1(bm::word_t *block)
Definition: bmfunc.h:3277
BMFORCEINLINE gap_word_t * gap_operation_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP AND operation.
Definition: bmfunc.h:3504
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:131
#define VECT_XOR_ARR(dst, src, src_end)
Definition: bmsse4.h:225
static bit_operation_count_func_type bit_operation_count(unsigned i)
Definition: bmfunc.h:5482
unsigned sse2_gap_find(const bm::gap_word_t *BMRESTRICT pbuf, const bm::gap_word_t pos, const unsigned size)
Definition: bmsse2.h:388
bm::id_t gap_bitset_xor_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block XOR masked by GAP block.
Definition: bmfunc.h:2182
W operator()(W w1, W w2)
Definition: bmfunc.h:5379
unsigned short bitscan_popcnt(bm::id_t w, B *bits, unsigned offs=0)
Unpacks word into list of ON bit indexes using popcnt method.
Definition: bmfunc.h:4965
bm::word_t * bit_operation_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock XOR operation.
Definition: bmfunc.h:4610
d-Gap copy functor
Definition: bmfunc.h:970
bm::id_t(* bit_operation_count_func_type)(const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
Definition: bmfunc.h:5454
void bit_block_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
Definition: bmfunc.h:4474
bm::id_t gap_bitset_or_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block OR masked by GAP block.
Definition: bmfunc.h:2274
const unsigned gap_max_bits
Definition: bmconst.h:63
T * gap_2_dgap(const T *gap_buf, T *dgap_buf, bool copy_head=true)
Convert GAP buffer into D-GAP buffer.
Definition: bmfunc.h:992
BMFORCEINLINE unsigned gap_operation_any_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP XOR operation test.
Definition: bmfunc.h:3595
Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers...
Definition: bmconst.h:181
bitblock_store_adapter(bm::word_t *bit_block)
Definition: bmfunc.h:5249
bm::word_t * _p_fullp
Definition: bmfunc.h:292
bm::operation setop2op(bm::set_operation op)
Convert set operation to operation.
Definition: bmfunc.h:272
int wordcmp0(T w1, T w2)
Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testi...
Definition: bmfunc.h:344
void bit_recomb(It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size)
Definition: bmfunc.h:5310
Bit COUNT B functor.
Definition: bmfunc.h:5433
void or_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount)
Sets bits to 1 in the bitblock.
Definition: bmfunc.h:1682
bool improve_gap_levels(const T *length, const T *length_end, T *glevel_len)
Finds optimal gap blocks lengths.
Definition: bmfunc.h:5133
const unsigned set_block_mask
Definition: bmconst.h:46
unsigned bit_blocks
Number of bit blocks.
Definition: bmfunc.h:53
void gap_init_range_block(T *buf, T from, T to, T value, unsigned set_max)
Init gap block so it has block in it (can be whole block)
Definition: bmfunc.h:2455
bm::id_t bit_block_calc_count(const bm::word_t *block, const bm::word_t *block_end)
Bitcount for bit string.
Definition: bmfunc.h:2912
unsigned gap_buff_any_op(const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F f)
Abstract distance test operation for GAP buffers. Receives functor F as a template argument...
Definition: bmfunc.h:1206
static BMFORCEINLINE bool is_valid_block_addr(const bm::word_t *bp)
Definition: bmfunc.h:314
const unsigned set_array_size
Definition: bmconst.h:72
unsigned gap_bit_count_unr(const T *buf)
Calculates number of bits ON in GAP buffer. Loop unrolled version.
Definition: bmfunc.h:804
void for_each_block(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:708
const unsigned set_word_mask
Definition: bmconst.h:55
bm::word_t * bit_operation_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
bitblock AND operation.
Definition: bmfunc.h:4120
void dgap_2_gap(const T *dgap_buf, T *gap_buf, T gap_header=0)
Convert D-GAP buffer into GAP buffer.
Definition: bmfunc.h:1017
bm::id_t gap_bitset_or_count(const unsigned *block, const T *buf)
Compute bitcount of bit block OR masked by GAP block.
Definition: bmfunc.h:2226
W operator()(W w1, W w2)
Definition: bmfunc.h:5339
unsigned bit_block_and_count(const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
Definition: bmfunc.h:3798
static bool test()
Definition: bmfunc.h:92
void bit_invert(T *start, T *end)
Definition: bmfunc.h:3392
#define BMFORCEINLINE
Definition: bmdef.h:183
unsigned short bitscan_wave(const bm::word_t *w_ptr, unsigned char *bits)
Unpacks word wave (2x 32-bit words)
Definition: bmfunc.h:5539
unsigned int id_t
Definition: bmconst.h:34
Bit SUB functor.
Definition: bmfunc.h:5337
gap_word_t gap_levels[bm::gap_levels]
GAP lengths used by bvector.
Definition: bmfunc.h:63
unsigned gap_limit(const T *buf, const T *glevel_len)
Returs GAP block capacity limit.
Definition: bmfunc.h:2593
unsigned short bitscan(V w, B *bits)
Definition: bmfunc.h:5000
unsigned * gap_convert_to_bitset_smart(unsigned *dest, const T *buf, id_t set_max)
Smart GAP block to bitblock conversion.
Definition: bmfunc.h:2380
unsigned gap_free_elements(const T *buf, const T *glevel_len)
Returns number of free elements in GAP block array. Difference between GAP block capacity on this lev...
Definition: bmfunc.h:2657
T bit_convert_to_arr(T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0)
Convert bit block into an array of ints corresponding to 1 bits.
Definition: bmfunc.h:5071
#define BM_ASSERT
Definition: bmdef.h:112
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2)
Definition: bmfunc.h:4915
static gap_operation_func_type gap_operation(unsigned i)
Definition: bmfunc.h:5476
const unsigned set_total_blocks
Definition: bmconst.h:75
BMFORCEINLINE unsigned and_op(unsigned v1, unsigned v2)
GAP and functor.
Definition: bmfunc.h:3461
id64_t wordop_t
Definition: bmconst.h:83
const bm::gap_word_t * sse2_gap_sum_arr(const bm::gap_word_t *BMRESTRICT pbuf, unsigned sse_vect_waves, unsigned *sum)
Gap block population count (array sum) utility.
Definition: bmsse_util.h:418
#define VECT_BITCOUNT_SUB(first, last, mask)
Definition: bmsse4.h:210
W operator()(W w1, W w2)
Definition: bmfunc.h:5413
#define VECT_OR_ARR(dst, src, src_end)
Definition: bmsse4.h:219
bm::word_t get_32()
Definition: bmfunc.h:5287
unsigned bit_block_sub_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of sour...
Definition: bmfunc.h:4009
#define VECT_IS_ZERO_BLOCK(dst, dst_end)
Definition: bmsse4.h:234
bm::id_t gap_bitset_sub_count(const unsigned *block, const T *buf)
Compute bitcount of bit block SUB masked by GAP block.
Definition: bmfunc.h:2070
unsigned bit_array_compute_gaps(const T *arr, unsigned len)
Compute number of GAPs in bit-array.
Definition: bmfunc.h:1597
Structure with statistical information about bitset&#39;s memory allocation details.
Definition: bmfunc.h:50
bm::id_t bit_block_calc_count_to(const bm::word_t *block, bm::word_t right)
Definition: bmfunc.h:3215
bool is_const_set_operation(set_operation op)
Returns true if set operation is constant (bitcount)
Definition: bmfunc.h:252
copy_to_array_functor(B *bits)
Definition: bmfunc.h:4901
d_copy_func(T *dg_buf)
Definition: bmfunc.h:972
Bit AND functor.
Definition: bmfunc.h:5325
#define IS_EMPTY_BLOCK(addr)
Definition: bmdef.h:136
void for_each_nzblock(T ***root, unsigned size1, F &f)
Definition: bmfunc.h:619
set_representation
set representation variants
Definition: bmconst.h:113
void set_gap_level(T *buf, unsigned level)
Sets GAP block capacity level.
Definition: bmfunc.h:2620
void gap_add_to_bitset(unsigned *dest, const T *buf)
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:1932
int gapcmp(const T *buf1, const T *buf2)
Lexicographical comparison of GAP buffers.
Definition: bmfunc.h:1057
W operator()(W w1, W w2)
Definition: bmfunc.h:5333
void add_gap_block(unsigned capacity, unsigned length)
count gap block
Definition: bmfunc.h:77
ByteOrder
Byte orders recognized by the library.
Definition: bmfunc.h:389
bm::id_t bit_operation_sub_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
Performs bitblock test of SUB operation.
Definition: bmfunc.h:4284
const id64_t all_bits_mask
Definition: bmconst.h:84
Bit COUNT A functor.
Definition: bmfunc.h:5422
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:132
W operator()(W w1, W w2)
Definition: bmfunc.h:5327
void sub_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount)
SUB (AND NOT) bit interval to 1 in the bitblock.
Definition: bmfunc.h:1744
gap_word_t *(* gap_operation_func_type)(const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
Definition: bmfunc.h:5448
array of 0 values
Definition: bmconst.h:118
#define BMRESTRICT
Definition: bmdef.h:173
unsigned sse4_gap_find(const bm::gap_word_t *BMRESTRICT pbuf, const bm::gap_word_t pos, const unsigned size)
Definition: bmsse4.h:353
decoder_range_adapter(DEC &dec, unsigned from_idx, unsigned to_idx)
Definition: bmfunc.h:5280
#define VECT_INVERT_ARR(first, last)
Definition: bmsse4.h:213
unsigned bit_list_4(T w, B *bits)
Unpacks word into list of ON bit indexes (quad-bit based)
Definition: bmfunc.h:4949
Bit COUNT XOR functor.
Definition: bmfunc.h:5377