NCBI C++ ToolKit
stress32.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1  /*
2 Copyright(c) 2002-2018 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For more information please visit: http://bitmagic.io
17 */
18 
19 
20 //#define BMSSE2OPT
21 //#define BMSSE42OPT
22 //#define BMAVX2OPT
23 //#define BM_USE_EXPLICIT_TEMP
24 //#define BM_USE_GCC_BUILD
25 
26 #define BMXORCOMP
27 #define BM_NONSTANDARD_EXTENTIONS
28 
29 #include <ncbi_pch.hpp>
30 
31 #include <stdio.h>
32 #include <stdlib.h>
33 #undef NDEBUG
34 #include <time.h>
35 #include <math.h>
36 #include <string.h>
37 
38 #include <iostream>
39 #include <iomanip>
40 #include <utility>
41 #include <memory>
42 #include <random>
43 #include <algorithm>
44 #include <stdarg.h>
45 #include <mutex>
46 
49 #include <util/bitset/bmxor.h>
51 #include <util/bitset/bmutil.h>
52 #include <util/bitset/bmserial.h>
53 #include <util/bitset/bmbvimport.h>
54 #include <util/bitset/bmrandom.h>
55 #include <util/bitset/bmvmin.h>
56 #include <util/bitset/bmbmatrix.h>
65 #include <util/bitset/bm3vl.h>
66 #include <util/bitset/bmtimer.h>
67 #include <util/bitset/bmtask.h>
70 
71 #include <common/test_assert.h>
72 
73 using namespace bm;
74 using namespace std;
75 
76 #include "rlebtv.h"
77 #include <util/bitset/encoding.h>
78 #include <limits.h>
79 
80 #include <util/bitset/bmdbg.h>
81 #include <vector>
82 
83 bool is_silent = false;
84 
85 #if defined(BMSSE2OPT) || defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || defined(__ARM_NEON__)
86 #else
87 # define MEM_DEBUG
88 #endif
89 
90 #ifdef MEM_DEBUG
91 
92 #include "stacktrace_dbg.h"
93 #include <unordered_map>
94 
95 
96 
97 // -------------------------------
98 // memory profiler: very slow if defined
99 //
100 //#define BM_STACK_COLL
101 
102 // NOTE: ARM NEON compilation causes SIGBUS failure (Pi 32-bit)
103 // (disabled as non-essential)
104 
105 #ifdef BM_STACK_COLL
106 std::unordered_map<void*, std::string> g_alloc_trace_map;
107 #endif
108 std::mutex g_trace_lock;
109 
111 {
112 public:
113  static inline size_t na_ = 0;
114  static inline size_t nf_ = 0;
115 
116  static bm::word_t* allocate(size_t n, const void *)
117  {
118  #ifdef BM_STACK_COLL
119  std::string stack_str;
120  stack_str.reserve(2048);
121  get_stacktrace(stack_str);
122  #endif
123  g_trace_lock.lock();
124  ++na_;
125  assert(n);
126  bm::word_t* p =
127  (bm::word_t*) ::malloc((n+1) * sizeof(bm::word_t));
128  if (!p)
129  {
130  std::cerr << "ERROR Failed allocation!" << endl;
131  assert(0);exit(1);
132  }
133  *p = (bm::word_t)n;
134 
135  #ifdef BM_STACK_COLL
136  g_alloc_trace_map.emplace(p, std::move(stack_str));
137  #endif
138  g_trace_lock.unlock();
139  return ++p;
140  }
141 
142  static void deallocate(bm::word_t* p, size_t n)
143  {
144  g_trace_lock.lock();
145  ++nf_;
146  --p;
147  if (*p != n)
148  {
149  printf("Block memory deallocation ERROR! n = %i (expected %i)\n", (int)n, (int)*p);
150  assert(0);exit(1);
151  }
152  ::free(p);
153  #ifdef BM_STACK_COLL
154  g_alloc_trace_map.erase(p);
155  #endif
156  g_trace_lock.unlock();
157  }
158 
159  static size_t balance() BMNOEXCEPT { return na_ - nf_; }
160 };
161 
163 {
164 public:
165  static inline size_t na_ = 0;
166  static inline size_t nf_ = 0;
167 
168  static void* allocate(size_t n, const void *)
169  {
170  #ifdef BM_STACK_COLL
171  std::string stack_str;
172  stack_str.reserve(2048);
173  get_stacktrace(stack_str);
174  #endif
175 
176  g_trace_lock.lock();
177  ++na_;
178  assert(sizeof(size_t) == sizeof(void*));
179  void* p = ::malloc((n+1) * sizeof(void*));
180  if (!p)
181  {
182  std::cerr << "ERROR! Failed allocation!" << endl;
183  exit(1);
184  }
185  size_t* s = (size_t*) p;
186  *s = n;
187 
188  #ifdef BM_STACK_COLL
189  g_alloc_trace_map.emplace(p, std::move(stack_str));
190  #endif
191  g_trace_lock.unlock();
192 
193  return (void*)++s;
194  }
195 
196  static void deallocate(void* p, size_t n)
197  {
198  g_trace_lock.lock();
199  ++nf_;
200  size_t* s = (size_t*) p;
201  --s;
202  if(*s != n)
203  {
204  printf("Ptr memory deallocation ERROR!\n");
205  assert(0);
206  exit(1);
207  }
208  ::free(s);
209 
210  #ifdef BM_STACK_COLL
211  g_alloc_trace_map.erase(s);
212  #endif
213  g_trace_lock.unlock();
214  }
215 
216  static size_t balance() BMNOEXCEPT { return nf_ - na_; }
217 
218 };
219 
220 
221 
223 
227 
228 #else
229 
230 typedef bm::bvector<> bvect;
232 typedef bm::rs_index<> rs_ind;
233 
234 
235 #endif
236 
237 typedef std::vector<unsigned> ref_vect_type;
238 
247 
248 //const unsigned BITVECT_SIZE = 100000000 * 8;
249 
250 // This this setting program will consume around 150M of RAM
251 const unsigned BITVECT_SIZE = 100000000 * 2;
252 
253 const unsigned ITERATIONS = 180000;
254 //const unsigned PROGRESS_PRINT = 2000000;
255 
256 /// Reference (naive) inetrval detector based on population counting
257 /// and boundaries tests
258 ///
259 template<typename BV>
260 bool test_interval(const BV& bv,
261  typename BV::size_type left, typename BV::size_type right)
262 {
263  if (left > right)
264  bm::xor_swap(left, right); // make sure left <= right
265  bool is_left(0), is_right(0);
266  if (left) // check left-1 bit (if exists)
267  is_left = bv.test(left - 1);
268  if ((is_left == false) && (right < bm::id_max - 1))
269  is_right = bv.test(right + 1); // check [...right] range condition
270  if (is_left == false && is_right == false)
271  {
272  typename BV::size_type cnt = bv.count_range(left, right);
273  if (cnt == (1 + right - left))
274  return true;
275  }
276  return false;
277 }
278 
279 
280 template<class BV>
281 void DetailedCompareBVectors(const BV& bv1, const BV& bv2)
282 {
283  bvect::counted_enumerator en1 = bv1.first();
284  bvect::counted_enumerator en2 = bv2.first();
285 
286  for (; en1.valid(); ++en1)
287  {
288  assert(en2.valid());
289 
290  bm::id_t i1 = *en1;
291  bm::id_t i2 = *en2;
292 
293  if (i1 != i2)
294  {
295  unsigned nb1 = unsigned(i1 >> bm::set_block_shift);
296  unsigned nb2 = unsigned(i2 >> bm::set_block_shift);
297  unsigned ii1 = nb1 >> bm::set_array_shift;
298  unsigned jj1 = nb1 & bm::set_array_mask;
299  unsigned ii2 = nb2 >> bm::set_array_shift;
300  unsigned jj2 = nb2 & bm::set_array_mask;
301 
302  std::cerr << "Difference detected at: position="
303  << i1 << " nb=" << nb1
304  << "[" << ii1 << ", " << jj1 << "]"
305  " other position = " << i2 <<
306  " nb=" << nb2
307  << "[" << ii2 << ", " << jj2 << "]"
308  << std::endl;
309  std::cerr << " en1.count()=" << en1.count() << " en2.count()=" << en2.count()
310  << std::endl;
311 
312  exit(1);
313  return;
314  }
315  ++en2;
316  } // for
317 
318  bool eq = bv1.equal(bv2);
319  if (!eq)
320  {
321  cerr << "EQ (1-2) discrepancy! " << endl;
322  exit(1);
323  }
324  int cmp = bv1.compare(bv2);
325  if (cmp != 0)
326  {
327  cerr << "Compare (1-2) discrepancy! " << cmp << endl;
328  exit(1);
329  }
330  cmp = bv2.compare(bv1);
331  if (cmp != 0)
332  {
333  cerr << "Compare (2-1) discrepancy! " << cmp << endl;
334  exit(1);
335  }
336 
337  cout << "Detailed compare OK (no difference)." << endl;
338 }
339 
340 void CheckVectors(bvect_mini &bvect_min,
341  bvect &bvect_full,
342  unsigned size,
343  bool detailed = true);
344 
345 
346 extern "C" {
347  static
348  int bit_decode_func(void* handle_ptr, bm::id_t bit_idx)
349  {
350  std::vector<bm::id_t>* vp = (std::vector<bm::id_t>*)handle_ptr;
351  vp->push_back(bit_idx);
352  return 0;
353  }
354  /*
355  static
356  int bit_decode_func2(void* handle_ptr, bm::id_t bit_idx)
357  {
358  if (bit_idx > (65536 * 256))
359  {
360  throw 1;
361  }
362  std::vector<bm::id_t>* vp = (std::vector<bm::id_t>*)handle_ptr;
363  vp->push_back(bit_idx);
364  return 0;
365  }
366  */
367 } // extern C
368 
369 
370 template<class BV>
371 void VisitorAllRangeTest(const BV& bv, typename BV::size_type step = 1)
372 {
373  typename BV::size_type left, right, next, i_end;
374  bool non_empty = bv.find_range(left, right);
375  if (!non_empty)
376  return;
377  if (left < 65536)
378  left = 0;
379  if (right < 65536)
380  right = 65535;
381 
382  auto drange = right - left;
383  if (!drange)
384  drange = 256;
385  if (!step)
386  step = drange / 100;
387  if (!step)
388  step = 1;
389 
390  cout << "... VisitorAllRangeTest() step=" << step << endl;
391 
392  auto pcnt = 256;
393  for (auto i = left; i <= right; i+=step)
394  {
395  {
396  bvect bv_control;
397  bm::bit_vistor_copy_functor<bvect> func(bv_control);
398  bm::for_each_bit_range(bv, i, right, func);
399 
400  bvect bv2;
401  bv2.copy_range(bv, i, right);
402 
403  bool eq = bv2.equal(bv_control);
404  assert(eq);
405  }
406  next = bv.get_next(i);
407  if (next)
408  {
409  auto delta = next - i;
410  if (delta > 32)
411  {
412  i += delta / 2;
413  }
414  else
415  if (delta == 1)
416  {
417  bool f = bm::find_interval_end(bv, next, i_end);
418  if (f)
419  {
420  delta = i_end - i;
421  if (delta > 4)
422  i += delta / 2;
423  }
424  else
425  {
426  assert(!bv.test(i));
427  }
428  }
429  }
430  if (!pcnt)
431  {
432  if (!is_silent)
433  cout << "\r" << i << " / " << right << flush;
434  pcnt = 128;
435  }
436  --pcnt;
437 
438  } // for i
439  cout << endl;
440 
441  pcnt = 256;
442  for (; left <= right; left+=step, --right)
443  {
444  {
445  bvect bv_control;
446  bm::bit_vistor_copy_functor<bvect> func(bv_control);
447  bm::for_each_bit_range(bv, left, right, func);
448 
449  bvect bv2;
450  bv2.copy_range(bv, left, right);
451 
452  bool eq = bv2.equal(bv_control);
453  assert(eq);
454  }
455  next = bv.get_next(left);
456  if (next)
457  {
458  auto delta = next - left;
459  if (delta > 128)
460  {
461  left += delta / 2;
462  }
463  else
464  if (delta == 1)
465  {
466  bool f = bm::find_interval_end(bv, left, i_end);
467  if (f)
468  {
469  delta = i_end - left;
470  if (delta > 4)
471  left += delta / 2;
472  }
473  }
474  }
475  if (!pcnt)
476  {
477  if (!is_silent)
478  cout << "\r" << left << " / " << right << flush;
479  pcnt = 128;
480  }
481  --pcnt;
482 
483  } // for i
484  cout << endl;
485 }
486 
487 
488 void generate_bvector(bvect& bv, unsigned vector_max = 40000000, bool optimize=true);
489 
490 static
491 unsigned random_minmax(unsigned min, unsigned max)
492 {
493  unsigned r = (unsigned(rand()) << 16u) | unsigned(rand());
494  return r % (max-min) + min;
495 }
496 
497 template<typename BV>
498 void TestFindDiff(const BV& bv1, BV& bv2)
499 {
500  bool f;
501  typename BV::size_type pos, pos_c, pos_l;
502  f = bv1.find_first_mismatch(bv2, pos);
503  bvect bv_x;
504  bv_x.bit_xor(bv1, bv2, bvect::opt_compress);
505  if (!f)
506  {
507  auto a = bv_x.any();
508  assert(!a);
509  return;
510  }
511  else // found
512  {
513  bool f2 = bv1.find_first_mismatch(bv2, pos_l, pos);
514  assert(f2 == f);
515  assert(pos_l == pos);
516  if (pos)
517  {
518  f2 = bv1.find_first_mismatch(bv2, pos_l, pos-1);
519  assert(!f2);
520  }
521  }
522  bool cf = bv_x.find(pos_c);
523  assert(f == cf);
524  assert(pos == pos_c);
525 
526  f = bv2.find_first_mismatch(bv1, pos);
527  assert(f == cf);
528  assert(pos == pos_c);
529 }
530 
531 
532 static
533 void FillSets(bvect_mini* bvect_min,
534  bvect* bvect_full,
535  unsigned min,
536  unsigned max,
537  unsigned fill_factor)
538 {
539  unsigned i;
540  unsigned id;
541 
542  //Random filling
543  if(fill_factor == 0)
544  {
545  unsigned n_id = (max - min) / 100;
546  printf("random filling : %i\n", n_id);
547  for (i = 0; i < n_id; i++)
548  {
549  id = random_minmax(min, max);
550  bvect_min->set_bit(id);
551  bvect_full->set_bit(id);
552  }
553  std::cout << endl;
554  }
555  else
556  {
557  printf("fill_factor random filling : factor = %i\n", fill_factor);
558 
559  for(i = 0; i < fill_factor; i++)
560  {
561  unsigned k = unsigned(rand()) % 10;
562  if (k == 0)
563  k+=2;
564 
565  //Calculate start
566  unsigned start = min + (max - min) / (fill_factor * k);
567 
568  //Randomize start
569  start += random_minmax(1, (max - min) / (fill_factor * 10));
570 
571  if (start > max)
572  {
573  start = min;
574  }
575 
576  //Calculate end
577  unsigned end = start + (max - start) / (fill_factor *2);
578 
579  //Randomize end
580  end -= random_minmax(1, (max - start) / (fill_factor * 10));
581 
582  if (end > max )
583  {
584  end = max;
585  }
586 
587  bvect::bulk_insert_iterator iit = bvect_full->inserter();
588 
589  if (fill_factor > 1)
590  {
591  for(; start < end;)
592  {
593  unsigned r = unsigned(rand()) % 8;
594 
595  if (r > 7)
596  {
597  unsigned inc = unsigned(rand()) % 3;
598  ++inc;
599  unsigned end2 = start + (unsigned)rand() % 1000;
600  if (end2 > end)
601  end2 = end;
602  while (start < end2)
603  {
604  bvect_min->set_bit(start);
605  iit = start;
606  start += inc;
607  }
608  continue;
609  }
610 
611  if (r)
612  {
613  bvect_min->set_bit(start);
614  iit = start;
615  ++start;
616  }
617  else
618  {
619  start+=r;
620  bvect_min->set_bit(start);
621  iit = start;
622  }
623  }
624  }
625  else
626  {
627  unsigned c = unsigned(rand()) % 15;
628  if (c == 0)
629  ++c;
630  for(; start < end; ++start)
631  {
632  bvect_min->set_bit(start);
633  iit = start;
634  if (start % c)
635  {
636  start += c;
637  }
638  }
639  }
640  cout << endl;
641 
642  }
643  }
644 }
645 
646 //
647 // Interval filling.
648 // 111........111111........111111..........11111111.......1111111...
649 //
650 
651 static
652 void FillSetsIntervals(bvect_mini* bvect_min,
653  bvect& bvect_full,
654  unsigned min,
655  unsigned max,
656  unsigned fill_factor,
657  bool set_flag=true)
658 {
659 
660  while(fill_factor==0)
661  {
662  fill_factor=(unsigned)rand()%10;
663  }
664  bvect_full.init();
665 
666  cout << "Intervals filling. Factor="
667  << fill_factor << endl << endl;
668 
669  unsigned i, j;
670  unsigned factor = 70 * fill_factor;
671  for (i = min; i < max; ++i)
672  {
673  unsigned len, end;
674 
675  do
676  {
677  len = unsigned(rand()) % factor;
678  end = i+len;
679 
680  } while (end >= max);
681  if (i < end)
682  {
683  bvect_full.set_range(i, end-1, set_flag);
684  bool all_one_range = bvect_full.is_all_one_range(i, end - 1);
685  assert(all_one_range == set_flag);
686  bool any_one = bvect_full.any_range(i, end - 1);
687  assert(any_one == set_flag);
688  bool is_int = bm::is_interval(bvect_full, i, end-1);
689  bool is_int_c = test_interval(bvect_full, i, end-1);
690  assert(is_int == is_int_c);
691  if (is_int)
692  {
693  bvect::size_type pos;
694  bool b = bm::find_interval_end(bvect_full, i, pos);
695  assert(b && pos == end-1);
696  }
697  }
698 
699  for (j = i; j < end; ++j)
700  {
701  if (set_flag)
702  {
703  if (bvect_min)
704  bvect_min->set_bit(j);
705  //bvect_full.set_bit(j);
706  }
707  else
708  {
709  if (bvect_min)
710  bvect_min->clear_bit(j);
711  //bvect_full.clear_bit(j);
712  }
713 
714 
715  } // j
716 
717  i = end;
718  len = unsigned(rand()) % (factor* 10 * bm::gap_max_bits);
719  if (len % 2)
720  {
721  len *= unsigned(rand()) % (factor * 10);
722  }
723 
724  i+=len;
725 
726  if ( (len % 6) == 0)
727  {
728  for(unsigned k=0; k < 1000 && i < max; k+=3,i+=3)
729  {
730  if (set_flag)
731  {
732  if (bvect_min)
733  bvect_min->set_bit(i);
734  bvect_full.set_bit_no_check(i);
735  }
736  else
737  {
738  if (bvect_min)
739  bvect_min->clear_bit(j);
740  bvect_full.clear_bit(j);
741  }
742  }
743  }
744  } // for i
745 
746 }
747 
748 static
750  bvect* bvect_full,
751  unsigned min,
752  unsigned max,
753  unsigned fill_factor)
754 {
755  FillSetsIntervals(bvect_min, *bvect_full, min, max, fill_factor, true);
756  FillSetsIntervals(bvect_min, *bvect_full, min, max, fill_factor, false);
757 }
758 
759 static
760 void FillSetsRandomOne(bvect_mini* bvect_min,
761  bvect* bvect_full,
762  unsigned min,
763  unsigned max)
764 {
765  unsigned range = max - min;
766  unsigned bit_idx = unsigned(rand()) % range;
767  bvect_min->set_bit(bit_idx);
768  bvect_full->set_bit(bit_idx);
769  std::cout << "Bit_idx=" << bit_idx << endl;
770 }
771 
772 static
773 void FillSetsRandom(bvect_mini* bvect_min,
774  bvect* bvect_full,
775  unsigned min,
776  unsigned max,
777  unsigned fill_factor)
778 {
779  bvect_full->init();
780  unsigned diap = max - min;
781  unsigned count;
782 
783  switch (fill_factor)
784  {
785  case 0:
786  count = diap / 1000;
787  break;
788  case 1:
789  count = diap / 255;
790  break;
791  default:
792  count = diap / 10;
793  break;
794  }
795 
796  for (unsigned i = 0; i < count; ++i)
797  {
798  unsigned bn = unsigned(rand()) % count;
799  bn += min;
800 
801  if (bn > max)
802  {
803  bn = max;
804  }
805  bvect_min->set_bit(bn);
806  bvect_full->set_bit_no_check(bn);
807  }
808  cout << "Ok" << endl;
809 
810 }
811 
812 static
813 void FillSetsRegular(bvect_mini* bvect_min,
814  bvect* bvect_full,
815  unsigned /*min*/,
816  unsigned max,
817  unsigned /*fill_factor*/)
818 {
819  bvect::bulk_insert_iterator iit = bvect_full->inserter();
820 
821  unsigned step = (unsigned)rand() % 4;
822  if (step < 2) ++step;
823  for (unsigned i = 0; i < max; i+=step)
824  {
825  bvect_min->set_bit(i);
826  iit = i;
827  //bvect_full->set_bit_no_check(i);
828  }
829  cout << "Ok" << endl;
830 }
831 
832 
833 
834 
835 //
836 // Quasi random filling with choosing randomizing method.
837 //
838 //
839 static
841  bvect* bvect_full,
842  unsigned min,
843  unsigned max,
844  int optimize = 0,
845  int method = -1)
846 {
847  if (method == -1)
848  {
849  method = rand() % 7;
850  }
851 //method = 2;
852  unsigned factor;
853  switch (method)
854  {
855 
856  case 0:
857  cout << "Random filling: method - FillSets - factor(0)" << endl;
858  FillSets(bvect_min, bvect_full, min, max, 0);
859  break;
860 
861  case 1:
862  cout << "Random filling: method - FillSets - factor(random)" << endl;
863  factor = (unsigned)rand()%3;
864  FillSets(bvect_min, bvect_full, min, max, factor?factor:1);
865  break;
866 
867  case 2:
868  cout << "Random filling: method - Set-Clear Intervals - factor(random)" << endl;
869  factor = (unsigned)rand()%10;
870  FillSetClearIntervals(bvect_min, bvect_full, min, max, factor);
871  break;
872  case 3:
873  cout << "Random filling: method - FillRandom - factor(random)" << endl;
874  factor = (unsigned)rand()%3;
875  FillSetsRandom(bvect_min, bvect_full, min, max, factor?factor:1);
876  break;
877  case 4:
878  cout << "Random set one bit" << endl;
879  FillSetsRandomOne(bvect_min, bvect_full, min, max);
880  break;
881  case 5:
882  cout << "Regular pattern filling" << endl;
883  FillSetsRegular(bvect_min, bvect_full, min, max, 2);
884  break;
885  default:
886  cout << "Random filling: method - Set Intervals - factor(random)" << endl;
887  factor = (unsigned)rand()%10;
888  FillSetsIntervals(bvect_min, *bvect_full, min, max, factor);
889  break;
890 
891  } // switch
892 
893  if (optimize && (method <= 1))
894  {
896  bvect_full->optimize(tb);
897  }
898 }
899 
900 static
901 void print_bv(const bvect& bv)
902 {
903  std::cout << bv.count() << ": ";
904  bvect::enumerator en = bv.first();
905  for (; en.valid(); ++en)
906  std::cout << *en << ", ";
907  std::cout << std::endl;
908 }
909 
910 // reference SHIFT right
911 static
912 void ShiftRight(bvect* bv, unsigned shift)
913 {
914  bvect bv_tmp;
915  {
917  bvect::enumerator en = bv->first();
918  for (; en.valid(); ++en)
919  {
920  unsigned v = *en;
921  unsigned new_v = v + shift;
922  if (new_v < v || new_v == bm::id_max) // check overflow
923  {}
924  else
925  {
926  bi = new_v;
927  }
928  }
929  }
930  bv->swap(bv_tmp);
931 }
932 
933 // Reference bit insert
934 static
935 void BVectorInsert(bvect* bv, unsigned pos, bool value)
936 {
937  bvect bv_tmp;
938  if (pos)
939  bv_tmp.copy_range(*bv, 0, pos-1);
940 
941  {
943  bvect::enumerator en = bv->first();
944  for (; en.valid(); ++en)
945  {
946  unsigned v = *en;
947  if (v < pos)
948  continue;
949  unsigned new_v = v + 1;
950  if (new_v < v || new_v == bm::id_max) // check overflow
951  {}
952  else
953  {
954  bi = new_v;
955  }
956  }
957  }
958  bv->swap(bv_tmp);
959  bv->set(pos, value);
960 }
961 
962 // Reference bit erase
963 static
964 void BVectorErase(bvect* bv, unsigned pos)
965 {
966  bvect bv_tmp;
967  if (pos)
968  bv_tmp.copy_range(*bv, 0, pos-1);
969 
970  {
972  bvect::enumerator en = bv->first();
973  en.go_to(pos+1);
974  for (; en.valid(); ++en)
975  {
976  unsigned v = *en;
977  assert(v > pos);
978  bi = v -1;
979  }
980  }
981  bv->swap(bv_tmp);
982 }
983 
984 
985 
986 // do logical operation through serialization
987 static
988 unsigned SerializationOperation(bvect* bv_target,
989  /*const*/ bvect& bv1,
990  /*const*/ bvect& bv2,
991  set_operation op,
992  bool check_reverse=false)
993 {
994  bvect bv_tmp;
995  if (!bv_target)
996  {
997  bv_target = &bv_tmp;
998  }
999 
1000  if (op == set_COUNT_SUB_AB ||
1001  op == set_COUNT_SUB_BA)
1002  {
1003  check_reverse = false;
1004  }
1005 
1006  // serialize input vectors
1007  bvect::statistics st1_op, st2_op;
1008 
1010  if (!bv1.is_ro())
1011  bv1.optimize(tb, bvect::opt_compress, &st1_op);
1012  else
1013  bv1.calc_stat(&st1_op);
1014  if (!bv2.is_ro())
1015  bv2.optimize(tb, bvect::opt_compress, &st2_op);
1016  else
1017  bv2.calc_stat(&st2_op);
1018 
1019 
1020  struct bvect::statistics st1, st2;
1021  bv1.calc_stat(&st1);
1022  bv2.calc_stat(&st2);
1023 
1024 
1025  if (st1.max_serialize_mem > st1_op.max_serialize_mem)
1026  {
1027  cout << "Error: Optimize failed to compute max_serialize_mem" << endl;
1028  cout << "calc_stat=" << st1.max_serialize_mem << endl;
1029  cout << "optimize=" << st1_op.max_serialize_mem << endl;
1030  assert(0);
1031  exit(1);
1032  }
1033  if (st2.max_serialize_mem > st2_op.max_serialize_mem)
1034  {
1035  cout << "Error:Optimize failed to compute max_serialize_mem" << endl;
1036  cout << "calc_stat=" << st2.max_serialize_mem << endl;
1037  cout << "optimize=" << st2_op.max_serialize_mem << endl;
1038  assert(0); exit(1);
1039  }
1040 
1041  unsigned char* smem1 = new unsigned char[st1.max_serialize_mem];
1042  unsigned char* smem2 = new unsigned char[st2.max_serialize_mem];
1043 
1044  size_t slen1 = bm::serialize(bv1, smem1, tb);
1045  size_t slen2 = bm::serialize(bv2, smem2, tb);
1046 
1047  if (slen1 > st1.max_serialize_mem || slen2 > st2.max_serialize_mem)
1048  {
1049  cout << "Serialization override detected!" << endl;
1050  exit(1);
1051  }
1052 
1054 
1055  auto count = od.deserialize(*bv_target, smem1, nullptr, set_ASSIGN);
1056  cout << slen1 << " " << slen2 << endl;
1057  int res = bv1.compare(*bv_target);
1058  if (res != 0)
1059  {
1060  cout << "---------------------------------- " << endl;
1061  cout << "bv1.count()=" << bv1.count() << endl;
1062  print_stat(cout, bv1);
1063  cout << "---------------------------------- " << endl;
1064  cout << "bv_target.count()=" << bv_target->count() << endl;
1065  print_stat(cout, *bv_target);
1066 
1067  bv_target->bit_xor(bv1);
1068  cout << "First diff=" << bv_target->get_first() << endl;
1069  cout << "set_ASSIGN 1 failed!" << endl;
1070  exit (1);
1071  }
1072  cout << "Deserialization ASSIGN into bv1 OK" << endl;
1073 
1074  {
1075  bvect* bv_tmp2 = new bvect();
1076  bm::deserialize(*bv_tmp2, smem1);
1077  if (*bv_tmp2 != bv1)
1078  {
1079  cout << "Deserialize NOT equal to Operation deserialize!" << endl;
1080  assert(0); exit(1);
1081  }
1082  delete bv_tmp2;
1083  }
1084 
1085 
1086  cout << "Operation deserialization... " << op << endl;
1087 
1088  count = od.deserialize(*bv_target, smem2, 0, op);
1089  cout << "OK" << endl;
1090 
1091  // check if operation was ok
1092  {
1093  bvect bv_agg, bv_agg2;
1094 
1096  agg.set_optimization();
1097 
1098  const bvect* agg_list[10];
1099  const bvect* agg_list2[10];
1100  agg_list[0] = &bv1;
1101  agg_list[1] = &bv2;
1102  agg_list2[0] = &bv2;
1103 
1104 
1105  bool agg_check = false;
1106 
1108  switch(op)
1109  {
1110  case bm::set_OR:
1111  {
1113  bvc |= bv2;
1114  bvect bv_merge1(bv1, bm::finalization::READWRITE);
1115  bvect bv_merge2(bv2, bm::finalization::READWRITE);
1116  bv_merge1.merge(bv_merge2);
1117 
1118  if (bv_merge1 != bvc)
1119  {
1120  cerr << "Merge(OR) check error!" << endl;
1121  exit(1);
1122  }
1123  // 2-way
1124  {
1125  bvect bvt1;
1126  bvt1.bit_or(bv1, bv2, bvect::opt_none);
1127  if (bvt1 != bvc)
1128  {
1129  cerr << "1. OR 2-way check error!" << endl;
1130  exit(1);
1131  }
1132  bvect bvt2;
1133  bvt2.bit_or(bv2, bv1, bvect::opt_compress);
1134  if (bvt2 != bvc)
1135  {
1136  cerr << "2. OR 2-way check error!" << endl;
1137  exit(1);
1138  }
1139  }
1140  }
1141  bvt |= bv2;
1142  agg.combine_or(bv_agg, agg_list, 2);
1143  agg_check = true;
1144  break;
1145  case bm::set_XOR:
1146  bvt ^= bv2;
1147  // 2-way
1148  {
1150  bvc ^= bv2;
1151 
1152  bvect bvt1;
1153  bvt1.bit_xor(bv1, bv2, bvect::opt_none);
1154  if (bvt1 != bvc)
1155  {
1156  cerr << "1. XOR 2-way check error!" << endl;
1157  cerr << "Run detailed check (1)..." << endl;
1158  DetailedCompareBVectors(bvt1, bvc);
1159 
1160  bvect bvt2;
1161  bvt2.bit_xor(bv2, bv1, bvect::opt_compress);
1162  if (bvt2 != bvc)
1163  {
1164  cerr << "Reverse XOR 2-way check failed too!" << endl;
1165  }
1166 
1167  cerr << "Run detailed check (2)..." << endl;
1168  DetailedCompareBVectors(bvt2, bvc);
1169 
1170  exit(1);
1171  }
1172  bvect bvt2;
1173  bvt2.bit_xor(bv2, bv1, bvect::opt_compress);
1174  if (bvt2 != bvc)
1175  {
1176  cerr << "2. XOR 2-way check error!" << endl;
1177  exit(1);
1178  }
1179  }
1180  break;
1181  case bm::set_AND:
1182  bvt &= bv2;
1183  agg.combine_and(bv_agg, agg_list, 2);
1184  agg.combine_and_sub(bv_agg2, agg_list, 2, 0, 0, false);
1185  {
1186  if (bv_agg != bv_agg2)
1187  {
1188  cerr << "Error: Aggregator AND - AND-SUB(0) comparison failed!" << endl;
1189  exit(1);
1190  }
1191  }
1192  agg_check = true;
1193 
1194  // 2-way
1195  {
1197  bvc &= bv2;
1198 
1199  bvect bv_ro1(bv1, bm::finalization::READONLY);
1200  bvect bv_ro2(bv2, bm::finalization::READONLY);
1201 
1202  bvect bvt1;
1203  bvt1.bit_and(bv1, bv2, bvect::opt_none);
1204  if (bvt1 != bvc)
1205  {
1206  cerr << "1. AND 2-way check error!" << endl;
1207  //print_bv(bvt1);
1208  //cout << "control:" << endl;
1209  //print_bv(bvc);
1210  assert(0); exit(1);
1211  }
1212  bvect bvt11;
1213  bvt11.bit_and(bv_ro1, bv_ro2, bvect::opt_none);
1214  if (bvt11 != bvc)
1215  {
1216  cerr << "1.1 AND 2-way check error!" << endl;
1217  assert(0); exit(1);
1218  }
1219 
1220  bvect bvt2;
1221  bvt2.bit_and(bv2, bv1, bvect::opt_compress);
1222  if (bvt2 != bvc)
1223  {
1224  cerr << "2. AND 2-way check error!" << endl;
1225  assert(0);exit(1);
1226  }
1227  bvect bvt12;
1228  bvt12.bit_and(bv_ro1, bv_ro2, bvect::opt_none);
1229  if (bvt12 != bvc)
1230  {
1231  cerr << "2.1 AND 2-way check error!" << endl;
1232  assert(0); exit(1);
1233  }
1234  }
1235  break;
1236  case bm::set_SUB:
1237  bvt -= bv2;
1238  agg.combine_and_sub(bv_agg, agg_list, 1, agg_list2, 1, false);
1239  {
1240  bvect bv_h;
1241  agg.combine_and_sub_horizontal(bv_h, agg_list, 1, agg_list2, 1);
1242  if (bv_agg != bv_h)
1243  {
1244  cerr << "Error: Aggregator Horz-AND-SUB comparison failed!" << endl;
1245  exit(1);
1246  }
1247  }
1248  agg_check = true;
1249  // 2-way
1250  {
1253  bvc1 -= bv2;
1254  bvc2 -= bv1;
1255 
1256  bvect bvt1;
1257  bvt1.bit_sub(bv1, bv2, bvect::opt_compress);
1258  if (bvt1 != bvc1)
1259  {
1260  DetailedCompareBVectors(bvt1, bvc1);
1261  cerr << "1. SUB 2-way check error!" << endl;
1262  exit(1);
1263  }
1264  bvect bvt2;
1265  bvt2.bit_sub(bv2, bv1, bvect::opt_compress);
1266  if (bvt2 != bvc2)
1267  {
1268  cerr << "2. SUB 2-way check error!" << endl;
1269  exit(1);
1270  }
1271  }
1272 
1273  break;
1274  default:
1275  goto no_compare;
1276  }
1277  if (bvt.compare(*bv_target) != 0)
1278  {
1279  cout << "Direct Serial operation comparison failed!" << endl;
1280  exit(1);
1281  }
1282  if (agg_check && bvt.compare(bv_agg) != 0)
1283  {
1284  cerr << "Error: Aggregator operation comparison failed!" << endl;
1285  exit(1);
1286  }
1287 
1288  no_compare:
1289  ;
1290 
1291  }
1292 /*
1293  if (op == bm::set_AND || op == bm::set_OR || op == bm::set_XOR || op == bm::set_SUB)
1294  {
1295  cout << "3 way operation check... " << op << endl;
1296  operation_deserializer<bvect>::deserialize(*bv_target,
1297  bv1,
1298  smem2,
1299  0,
1300  op);
1301  cout << "OK" << endl;
1302 
1303  bvect bvt(bv1);
1304  switch(op)
1305  {
1306  case bm::set_OR:
1307  bvt |= bv2;
1308  break;
1309  case bm::set_XOR:
1310  bvt ^= bv2;
1311  break;
1312  case bm::set_AND:
1313  bvt &= bv2;
1314  break;
1315  case bm::set_SUB:
1316  bvt -= bv2;
1317  break;
1318  default:
1319  goto no_compare2;
1320  }
1321  if (bvt.compare(*bv_target) != 0)
1322  {
1323  cout << "3-way Serial operation comparison failed!" << endl;
1324  exit(1);
1325  }
1326  no_compare2:
1327  ;
1328  }
1329 */
1330 
1331  if (check_reverse)
1332  {
1333  cout << "Reverse check... " << endl;
1334  bvect bv_tmp2(BM_GAP);
1335  od.deserialize(bv_tmp2, smem2, 0, set_ASSIGN);
1336  res = bv_tmp2.compare(bv2);
1337  if (res != 0)
1338  {
1339  cout << "set_ASSIGN failed 2! " << endl;
1340  exit(1);
1341  }
1342  if (bv_tmp2 != bv2)
1343  {
1344  cout << "set_ASSIGN failed 2-1! " << endl;
1345  exit(1);
1346  }
1347  cout << "Deserialization assign to bv_tmp2 OK" << endl;
1348  unsigned count_rev =
1349  od.deserialize(bv_tmp2, smem1, 0, op);
1350  if (count != count_rev)
1351  {
1352 // print_stat(bv1);
1353 /*
1354  unsigned c = count_or(bv1, bv2);
1355  cout << "Correct count=" << c << endl;
1356 
1357  c = count_or(bv2, bv1);
1358  cout << "Correct count=" << c << endl;
1359 
1360  bv1 |= bv2;
1361  cout << "Count3 = " << bv1.count() << endl;;
1362 */
1363  //SaveBVector("err1.bv", bv1);
1364  //SaveBVector("err2.bv", bv2);
1365 
1366 
1367 
1368  cout << "Operation=" << op << endl;
1369 
1370  cout << "Serialization operation reverse check failed"
1371  << " count = " << count
1372  << " count rev= " << count_rev
1373  << endl;
1374  cout << "See bvector dumps: err1.bv, err2.bv" << endl;
1375 
1376  exit(1);
1377  }
1378 
1379  }
1380 
1381  delete [] smem1;
1382  delete [] smem2;
1383 
1384  return count;
1385 }
1386 
1387 static
1389  bvect& bv1,
1390  bvect& bv2,
1391  unsigned predicted_count,
1392  set_operation op_count,
1393  set_operation op_combine)
1394 {
1395  bv_target->clear(true);
1396 
1397  bvect bv_ro1(bv1, bm::finalization::READONLY);
1398  bvect bv_ro2(bv2, bm::finalization::READONLY);
1399 
1400  cout << "Serialization operation count..." << endl;
1401 
1402  unsigned scount1 = SerializationOperation(0,
1403  bv1,
1404  bv2,
1405  op_count,
1406  true //reverse check
1407  );
1408  cout << "Serialization operation count OK." << endl;
1409 
1410 
1411 
1412  cout << "Serialization operation. " << endl;
1413  unsigned scount2 = SerializationOperation(bv_target,
1414  bv1,
1415  bv2,
1416  op_combine);
1417  scount2 = bv_target->count();
1418  if (predicted_count != scount2 || scount1 != scount2)
1419  {
1420  cout << "Serialization count != predicted" << endl
1421  << " predicted=" << predicted_count
1422  << " scount1=" << scount1
1423  << " scount2=" << scount2
1424  << endl;
1425 
1426  cout << endl << "target:" << endl;
1427  print_stat(cout, *bv_target);
1428  cout << endl << endl << "Reference" << endl;
1429  if (op_combine == set_OR)
1430  {
1431  bv1 |= bv2;
1432  if (bv1 != *bv_target)
1433  {
1434  cout << "Comparison OR error!" << endl;
1435  }
1436  cout << "OR operation count=" << bv1.count() << endl;
1437  print_stat(cout, bv1);
1438  }
1439  else
1440  if (op_combine == set_AND)
1441  {
1442  bv1 &= bv2;
1443  print_stat(cout,bv1);
1444  }
1445 
1446  exit(1);
1447  }
1448 
1449  bvect bv_target2;
1450  unsigned scount3 = SerializationOperation(&bv_target2,
1451  bv_ro1,
1452  bv_ro2,
1453  op_combine);
1454  scount3 = bv_target2.count();
1455  assert(scount3 == scount2);
1456 
1457  bool eq = bv_target->equal(bv_target2);
1458  assert(eq);
1459 
1460  cout << "OK" << endl;
1461 }
1462 
1463 static
1464 void print_mv(const bvect_mini &bvect_min, unsigned size)
1465 {
1466  unsigned i;
1467  for (i = 0; i < size; ++i)
1468  {
1469  bool bflag = bvect_min.is_bit_true(i) != 0;
1470 
1471  if (bflag)
1472  printf("1");
1473  else
1474  printf("0");
1475  if ((i % 31) == 0 && (i != 0))
1476  printf(".");
1477  }
1478 
1479  printf("\n");
1480 }
1481 
1482 static
1483 void print_gap(const gap_vector& gap_vect, unsigned /*size*/)
1484 {
1485  const gap_word_t *buf = gap_vect.get_buf();
1486  unsigned len = gap_length(buf);
1487  printf("[%i:]", *buf++ & 1);
1488 
1489  for (unsigned i = 1; i < len; ++i)
1490  {
1491  printf("%i,", *buf++);
1492  }
1493 
1494  printf("\n");
1495 }
1496 
1497 
1498 static
1499 void CheckGAPMin(const gap_vector& gapv, const bvect_mini& bvect_min, unsigned len)
1500 {
1501  int last_bit = -1;
1502  for (unsigned i = 0; i < len; ++i)
1503  {
1504  int bit1 = (gapv.is_bit_true(i) == 1);
1505  int bit2 = (bvect_min.is_bit_true(i) != 0);
1506  if (bit1 != bit2)
1507  {
1508  cout << "Bit comparison failed. " << "Bit N=" << i << endl;
1509  assert(0);
1510  exit(1);
1511  }
1512  if (bvect_min.is_bit_true(i))
1513  {
1514  last_bit = (int)i;
1515  }
1516  }
1517  unsigned glast;
1518  bool found = gapv.get_last(&glast);
1519  if (!found && last_bit != -1)
1520  {
1521  cout << "Gap last search failed. " << "Bit=" << last_bit << endl;
1522  assert(0);
1523  exit(1);
1524  }
1525 
1526  if (found && last_bit == -1)
1527  {
1528  cout << "Gap last search ok but should failed. " << "Bit=" <<
1529  glast << endl;
1530  assert(0);
1531  exit(1);
1532  }
1533 
1534  if (last_bit != (int)glast)
1535  {
1536  if (!found && last_bit == -1)
1537  {}
1538  else
1539  {
1540  cout << "Gap last search discrepancy:" << " found Bit=" <<
1541  glast << " last=" << last_bit << endl;
1542  assert(0);
1543  exit(1);
1544  }
1545  }
1546 }
1547 
1548 static
1549 void CheckIntervals(const bvect& bv, unsigned /*max_bit*/)
1550 {
1551  unsigned cnt0 = count_intervals(bv);
1552  unsigned cnt1 = 1;
1553  //bool bit_prev = bv.test(0);
1554 
1555  unsigned cnt2 = 0;
1556  bvect::enumerator en = bv.first();
1557  if (!en.valid())
1558  {
1559  cnt2 = 1;
1560  }
1561  else
1562  {
1563  if (*en > 0)
1564  ++cnt2;
1565  unsigned prev = *en;
1566  for (++en; en.valid(); ++en)
1567  {
1568  if (++prev == *en)
1569  {
1570  }
1571  else
1572  {
1573  cnt2 += 2;
1574  prev = *en;
1575  }
1576  }
1577  cnt2 += 2;
1578  }
1579 /*
1580  for (unsigned i = 1; i < max_bit; ++i)
1581  {
1582  bool bit = bv.test(i);
1583  cnt1 += bit_prev ^ bit;
1584  bit_prev = bit;
1585  }
1586 */
1587  if (cnt0 != cnt2)
1588  {
1589  cout << "CheckIntervals error. " << "bm count=" << cnt0
1590  << " Control = " << cnt1 << endl;
1591  exit(1);
1592  }
1593 }
1594 
1595 template<class T> void CheckCountGapRange(const T& vect,
1596  unsigned left,
1597  unsigned right,
1598  unsigned* block_count_arr=0)
1599 {
1600  unsigned cnt1 = vect.count_range(left, right, block_count_arr);
1601  unsigned cnt2 = 0;
1602  for (unsigned i = left; i <= right; ++i)
1603  {
1604  if (vect.test(i))
1605  {
1606  ++cnt2;
1607  }
1608  }
1609  if (cnt1 != cnt2)
1610  {
1611  cout << "Bitcount range failed!" << "left=" << left
1612  << " right=" << right << endl
1613  << "count_range()=" << cnt1
1614  << " check=" << cnt2;
1615  exit(1);
1616  }
1617 }
1618 
1619 template<typename T>
1620 bool FindRank(const T& bv, bm::id_t rank, bm::id_t from, bm::id_t& pos)
1621 {
1622  assert(rank);
1623  bool res = false;
1624 
1625  typename T::enumerator en = bv.get_enumerator(from);
1626 
1627  typename T::enumerator en2 = bv.get_enumerator(from);
1628  if (rank > 1)
1629  en2.skip_to_rank(rank);
1630  if (!en.valid())
1631  return false;
1632  for (; en.valid(); ++en)
1633  {
1634  rank -= en.valid();
1635  if (rank == 0)
1636  {
1637  pos = *en;
1638  res = true;
1639  break;
1640  }
1641  } // for en
1642 
1643  bm::id_t pos2 = *en2;
1644  if (pos != pos2)
1645  {
1646  cerr << "FindRank enumerator::skip() failed: "
1647  << "pos=" << pos << " skip()pos=" << pos2
1648  << " from=" << from
1649  << endl;
1650  assert(0);
1651  exit(1);
1652  }
1653 
1654  return res;
1655 }
1656 
1657 inline
1658 void CheckRangeCopy(const bvect& bv, unsigned from, unsigned to)
1659 {
1660  bm::id_t f1, l1, f2, l2;
1661 
1662  bvect bv_cp(bv, from, to);
1663  bvect bv_cp2(bv, to, from); // swapped interval copy is legal
1664 
1665  bvect bv_control;
1666  bv_control.set_range(from, to);
1667 
1668  bv_control &= bv;
1669 
1670  int res = bv_control.compare(bv_cp);
1671  if (res != 0)
1672  {
1673  bool found1 = bv_cp.find_range(f1, l1);
1674  bool found2 = bv_control.find_range(f2, l2);
1675 
1676  bvect bv_cp3(bv, from, to);
1677 
1678  cerr << "Error: bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
1679  if (found1)
1680  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
1681  if (found2)
1682  cerr << " control from=" << f2 << " to=" << l2 << endl;
1683  exit(1);
1684  }
1685 
1686  int res2 = bv_control.compare(bv_cp2);
1687  if (res2 != 0)
1688  {
1689  bool found1 = bv_cp2.find_range(f1, l1);
1690  bool found2 = bv_control.find_range(f2, l2);
1691 
1692  cerr << "Error: reversed bvector<>::range_copy() failed. from=" << from << " to=" << to << endl;
1693  if (found1)
1694  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
1695  if (found2)
1696  cerr << " control from=" << f2 << " to=" << l2 << endl;
1697  exit(1);
1698  }
1699 
1700  bool found1 = bv_cp.find_range(f1, l1);
1701  bool found2 = bv_control.find_range(f2, l2);
1702  if (found1 != found2)
1703  {
1704  cerr << "Error: Dynamic range integrity check." << endl;
1705  exit(1);
1706  }
1707  if (found1)
1708  {
1709  if (f1 != f2 || l1 != l2)
1710  {
1711  cerr << "Error: bvector<>::range_copy() failed (dynamic range check). from=" << from << " to=" << to << endl;
1712  cerr << " range copy from=" << f1 << " to=" << l1 << endl;
1713  cerr << " control from=" << f2 << " to=" << l2 << endl;
1714  exit(1);
1715  }
1716  }
1717 
1718 }
1719 
1720 
1721 template<class T>
1722 void CheckCountRange(const T& vect, const bvect::rs_index_type& bc_arr,
1723  unsigned left,
1724  unsigned right)
1725 {
1726  unsigned cnt1 = vect.count_range(left, right);
1727  unsigned cnt2 = 0;
1728 
1729  typename T::enumerator en = vect.get_enumerator(left);
1730  for (; en.valid(); ++en)
1731  {
1732  if (*en > right)
1733  break;
1734  cnt2 += en.valid();
1735  }
1736  if (cnt1 != cnt2)
1737  {
1738  cout << "2. Bitcount range failed!" << "left=" << left
1739  << " right=" << right << endl
1740  << "count_range()=" << cnt1
1741  << " check=" << cnt2;
1742  exit(1);
1743  }
1744 
1745  CheckRangeCopy(vect, left, right);
1746 
1747 // bvect::rs_index_type bc_arr;
1748 // vect.build_rs_index(&bc_arr);
1749 
1750  // run a cycle to check count_to()
1751  //
1752  //for (unsigned i = 0; i <= right; ++i)
1753  {
1754  if (left > right)
1755  swap(left, right);
1756 
1757  unsigned cnt_to_r = vect.count_to(right, bc_arr);
1758  cnt1 = vect.count_range(left, right, bc_arr);
1759  unsigned cnt_to_l = left ? vect.count_to(left - 1, bc_arr) : 0;
1760  cnt2 = cnt_to_r - cnt_to_l;
1761  if (cnt1 != cnt2)
1762  {
1763  cout << "Bitcount range TO failed!" << " left=" << left
1764  << " right=" << right << endl
1765  << " count_range()=" << cnt1
1766  << " check=" << cnt2;
1767  assert(0); exit(1);
1768  }
1769 
1770  bm::id_t range = 1 + right - left;
1771  if (cnt1 > range)
1772  {
1773  cerr << "Impossible count_range detected!" << endl;
1774  cerr << " range = " << range << endl;
1775  cerr << " cnt1 = " << cnt1 << endl;
1776  cerr << " left = " << left << endl;
1777  cerr << " right = " << right << endl;
1778  cnt1 = vect.count_range(left, right, bc_arr);
1779  cerr << " cnt1 = " << cnt1 << endl;
1780  assert(0); exit(1);
1781  }
1782 
1783 
1784  if (cnt1) // check if we can reverse the search (rank)
1785  {
1786  unsigned pos, pos1;
1787  pos = pos1 = 0;
1788  bool rf = vect.find_rank(cnt1, left, pos);
1789  bool rf1 = vect.find_rank(cnt1, left, pos1, bc_arr);
1790  if (!rf || !rf1)
1791  {
1792  cerr << "1. find_rank() failed!" << " left=" << left
1793  << " right=" << right
1794  << " count_range()=" << cnt1
1795  << " pos=" << pos
1796  << " pos1=" << pos1
1797  << " range=" << range
1798  << endl;
1799 
1800  unsigned pos2;
1801  bool rf2 = FindRank(vect, cnt1, left, pos2);
1802  if (!rf2)
1803  {
1804  cerr << "Debug FindRank failed!" << endl;
1805  }
1806  else
1807  {
1808  cerr << " rank=" << pos2 << endl;
1809  }
1810 
1811  cerr << "detailed bug search..." << endl;
1812  for (unsigned k = 1; k <= cnt1; ++k)
1813  {
1814  rf = vect.find_rank(k, left, pos);
1815  rf2 = FindRank(vect, k, left, pos2);
1816  if (rf != rf2 || pos != pos2)
1817  {
1818  rf = vect.find_rank(k, left, pos);
1819 
1820  cerr << "Failed for rank=" << k << endl;
1821  cerr << rf << " " << rf2 << endl;
1822  cerr << "pos = " << pos << " pos2 = " << pos2 << endl;
1823  assert(0); exit(1);
1824  }
1825  }
1826  assert(0); exit(1);
1827  }
1828  assert(pos == pos1);
1829 
1830  if (left > 0)
1831  {
1832  unsigned pos3;
1833  T bv1(vect, left, bm::id_max-1);
1834  std::unique_ptr<bvect::rs_index_type> bc_arr2(new bvect::rs_index_type);
1835  bv1.build_rs_index(bc_arr2.get());
1836 
1837  bool rf3 = bv1.select(cnt1, pos3, *bc_arr2);
1838  assert(rf3 == rf);
1839  assert(pos == pos3);
1840  }
1841 
1842  if (right != pos)
1843  {
1844  unsigned pos2;
1845  bool rf2 = FindRank(vect, cnt1, left, pos2);
1846  assert(rf2);
1847  // check if we found zero-tail
1848  //auto cnt3 = vect.count_range(pos+1, right, block_count_arr);
1849  if (pos2 != pos)
1850  {
1851  rf = vect.find_rank(cnt1, left, pos);
1852  cout << "2. find_rank() check failed! \n" << "left=" << left
1853  << " right=" << right
1854  << " count_range()=" << cnt1
1855  << " pos=" << pos
1856  << " rank = " << pos2
1857  << endl;
1858  assert(0); exit(1);
1859  }
1860  }
1861  }
1862  }
1863 }
1864 
1865 static
1866 unsigned BitCountChange(unsigned word)
1867 {
1868  unsigned count = 1;
1869  unsigned bit_prev = word & 1;
1870  word >>= 1;
1871  for (unsigned i = 1; i < 32; ++i)
1872  {
1873  unsigned bit = word & 1;
1874  count += bit ^ bit_prev;
1875  bit_prev = bit;
1876  word >>= 1;
1877  }
1878  return count;
1879 }
1880 
1881 static
1882 void DetailedCheckVectors(const bvect &bv1,
1883  const bvect &bv2)
1884 {
1885  bvect::enumerator en1 = bv1.first();
1886  bvect::enumerator en2 = bv2.first();
1887 
1888  while (en1.valid())
1889  {
1890  if (!en2.valid())
1891  {
1892  cout << "Second vector - invalid enumerator at:" << *en1;
1893  return;
1894  }
1895  if (*en1 != *en2)
1896  {
1897  cout << "Discrepancy at bit position: " << *en1;
1898  cout << " second vector is at:" << *en2;
1899  return;
1900  }
1901  ++en1;
1902  ++en2;
1903  }
1904  cout << "Detailed check OK" << endl; // Hmmm... Why?
1905 }
1906 
1907 static
1908 void DetailedCheckVectors(const bvect_mini &bvect_min,
1909  const bvect &bvect_full,
1910  unsigned size)
1911 {
1912  cout << "Detailed check" << endl;
1913 
1914  //bvect_full.stat();
1915 
1916  // detailed bit by bit comparison. Paranoia check.
1917 
1918  unsigned i;
1919  for (i = 0; i < size; ++i)
1920  {
1921  bool bv_m_flag = bvect_min.is_bit_true(i) != 0;
1922  bool bv_f_flag = bvect_full.get_bit(i) != 0;
1923 
1924  if (bv_m_flag != bv_f_flag)
1925  {
1926  printf("Bit %u is non conformant. vect_min=%i vect_full=%i\n",
1927  i, (int)bv_m_flag, (int)bv_f_flag);
1928 
1929  cout << "Non-conformant block number is: " << unsigned(i >> bm::set_block_shift) << endl;
1930  assert(0); exit(1);
1931  }
1932  }
1933 
1934  printf("\n detailed check ok.\n");
1935 
1936 }
1937 
1938 static
1940 {
1941  if (!en1.valid() && !en2.valid())
1942  return;
1943  bool fsm_equal = en1.compare_state(en2);
1944  if (!fsm_equal)
1945  {
1946  cerr << "Enumerators FSM comparison failed" << endl;
1947  exit(1);
1948  }
1949 }
1950 
1951 // find last set bit by scan (not optimal)
1952 //
1953 static
1954 bool FindLastBit(const bvect& bv, bm::id_t& last_pos)
1955 {
1956  bvect::enumerator en = bv.first();
1957  if (!en.valid())
1958  return false;
1959  for (; en.valid(); ++en)
1960  {
1961  last_pos = *en;
1962  }
1963  return true;
1964 }
1965 
1966 
1967 
1968 template<class BV>
1969 void IntervalsCheck(const BV& bv)
1970 {
1971  cout << " ... IntervalsCheck" << endl;
1972  BV bv_inv(bv);
1973  bv_inv.invert();
1974 
1975  typename BV::size_type intervals = bm::count_intervals(bv);
1976  typename BV::size_type intervals_c = 1;
1977 
1978  typename BV::enumerator en1 = bv.get_enumerator(0);
1979  typename BV::enumerator en2 = bv_inv.get_enumerator(0);
1980 
1981  while (en1.valid())
1982  {
1983  typename BV::size_type from = *en1;
1984  typename BV::size_type to = *en2;
1985  assert(from != to);
1986 
1987  bool all_one, any_one;
1988  bool is_int, is_int_c;
1989  if (to == bm::id_max)
1990  {
1991  all_one = bv.is_all_one_range(from, to-1);
1992  assert(all_one);
1993  any_one = bv.any_range(from, to-1);
1994  assert(any_one);
1995  is_int = bm::is_interval(bv, from, to-1);
1996  is_int_c = test_interval(bv, from, to-1);
1997  assert(is_int == is_int_c);
1998  {
1999  bvect::size_type pos;
2000  bool b = bm::find_interval_end(bv, from, pos);
2001  assert(b == is_int);
2002  if (b)
2003  {
2004  assert(pos == to-1);
2005  }
2006  }
2007  if (is_int)
2008  {
2009  bvect::size_type pos;
2010  bool b = bm::find_interval_start(bv, from, pos);
2011  assert(b && pos == from);
2012  b = bm::find_interval_start(bv, to-1, pos);
2013  assert(b && pos == from);
2014  }
2015 
2016  break;
2017  }
2018  else
2019  {
2020  all_one = bv.is_all_one_range(from, to);
2021  assert(!all_one);
2022  any_one = bv.any_range(from, to);
2023  auto cnt = bv.count_range(from, to);
2024  if (any_one)
2025  {
2026  assert(cnt);
2027  }
2028  else
2029  {
2030  assert(!cnt);
2031  }
2032  is_int = bm::is_interval(bv, from, to);
2033  is_int_c = test_interval(bv, from, to);
2034  assert(is_int == is_int_c);
2035  if (is_int)
2036  {
2037  bvect::size_type pos;
2038  bool b = bm::find_interval_end(bv, from, pos);
2039  assert(b == is_int);
2040  if (b)
2041  {
2042  assert(pos == to);
2043  }
2044  b = bm::find_interval_start(bv, from, pos);
2045  assert(b && pos == from);
2046  pos = 0xDEADBEEF;
2047  b = bm::find_interval_start(bv, to, pos);
2048  assert(b && pos == from);
2049  }
2050 
2051  }
2052 
2053 
2054  if (to == bm::id_max)
2055  {}
2056  else
2057  {
2058  ++intervals_c;
2059  }
2060  if (to < from)
2061  {
2062  --from;
2063  assert(!bv.test(to));
2064  all_one = bv.is_all_one_range(from, to);
2065  assert(!all_one);
2066  any_one = bv.any_range(from, to);
2067  assert(!any_one);
2068  typename BV::size_type cnt = bv.count_range(to, from);
2069  assert(!cnt);
2070  is_int = bm::is_interval(bv, from, to);
2071  is_int_c = test_interval(bv, from, to);
2072  assert(is_int == is_int_c);
2073  if (is_int)
2074  {
2075  bvect::size_type pos;
2076  bool b = bm::find_interval_end(bv, from, pos);
2077  assert(b == is_int);
2078  if (b)
2079  {
2080  assert(pos == to);
2081  }
2082  b = bm::find_interval_start(bv, from, pos);
2083  assert(b && pos == from);
2084  pos = 0xDEADBEEF;
2085  b = bm::find_interval_start(bv, to, pos);
2086  assert(b && pos == from);
2087  }
2088 
2089  en2.go_to(from+1);
2090  if (!en2.valid())
2091  break;
2092  }
2093  else
2094  {
2095  --to;
2096  assert(bv.test(to));
2097  all_one = bv.is_all_one_range(from, to);
2098  assert(all_one);
2099  any_one = bv.any_range(from, to);
2100  assert(any_one);
2101  typename BV::size_type cnt = bv.count_range(from, to);
2102  assert(cnt == (to - from + 1));
2103  is_int = bm::is_interval(bv, from, to);
2104  is_int_c = test_interval(bv, from, to);
2105  assert(is_int == is_int_c);
2106  if (is_int)
2107  {
2108  bvect::size_type pos;
2109  bool b = bm::find_interval_end(bv, from, pos);
2110  assert(b == is_int);
2111  if (b)
2112  {
2113  assert(pos == to);
2114  }
2115  b = bm::find_interval_start(bv, from, pos);
2116  assert(b && pos == from);
2117  pos = 0xDEADBEEF;
2118  b = bm::find_interval_start(bv, to, pos);
2119  assert(b && pos == from);
2120  }
2121 
2122  en1.go_to(to+1);
2123  }
2124 
2125  } // while
2126  if (intervals != intervals_c)
2127  {
2128  typename BV::size_type diff;
2129  diff = std::max(intervals, intervals_c) - std::min(intervals, intervals_c);
2130  if (diff > 1)
2131  {
2132  cerr << "Intervals difference:" << diff << endl;
2133  assert(0);
2134  exit(1);
2135  }
2136  }
2137 }
2138 
2139 template<class BV>
2140 void interval_copy_range(BV& bv, const BV& bv_src,
2141  typename BV::size_type from, typename BV::size_type to)
2142 {
2143  bv.clear();
2144 
2145  if (from > to)
2146  bm::xor_swap(from, to);
2147 
2148  bm::interval_enumerator<bvect> ien(bv_src, from, false);
2149  while (ien.valid())
2150  {
2151  auto st = ien.start();
2152  assert(st >= from);
2153  if (st > to)
2154  break;
2155  auto end = ien.end();
2156  if (end > to)
2157  end = to;
2158 
2159  assert(st <= end);
2160  bv.set_range(st, end);
2161  if (!ien.advance())
2162  break;
2163  } // while
2164 }
2165 
2166 template<typename BV>
2167 void IntervalsEnumeratorCheck(const BV& bv, bool report)
2168 {
2169  if (report)
2170  cout << "..IntervalsEnumeratorCheck()" << flush;
2172 
2173  typename BV::size_type f, l, m;
2174  auto b = bv.find_range(f, l);
2175  if (!b)
2176  {
2177  assert(bv.count() == 0);
2178  return;
2179  }
2180  m = l - f;
2181  if (!m)
2182  m = l;
2183 
2184  bool eq;
2185  if (report)
2186  cout << "1 " << flush;
2187  // Full vector
2188  {
2189  bvect bv2; bvect bv2_c;
2190  bvect::mem_pool_guard g1(pool, bv2);
2191  bvect::mem_pool_guard g2(pool, bv2_c);
2192 
2193  bv2_c.copy_range(bv, 0, bm::id_max-1);
2194 
2195  interval_copy_range(bv2, bv, 0, bm::id_max - 1);
2196  eq = bv2.equal(bv2_c);
2197  assert(eq);
2198  }
2199  if (report)
2200  cout << "2 " << flush;
2201  // 0 -> frist
2202  {
2203  bvect bv2; bvect bv2_c;
2204  bvect::mem_pool_guard g1(pool, bv2);
2205  bvect::mem_pool_guard g2(pool, bv2_c);
2206 
2207  bv2_c.copy_range(bv, 0, l);
2208 
2209  interval_copy_range(bv2, bv, 0, l);
2210  eq = bv2.equal(bv2_c);
2211  assert(eq);
2212  }
2213 
2214  if (report)
2215  cout << "3 " << flush;
2216  // [first..last]
2217  {
2218  bvect bv2; bvect bv2_c;
2219  bvect::mem_pool_guard g1(pool, bv2);
2220  bvect::mem_pool_guard g2(pool, bv2_c);
2221 
2222  bv2_c.copy_range(bv, f, l);
2223 
2224  interval_copy_range(bv2, bv, f, l);
2225  eq = bv2.equal(bv2_c);
2226  assert(eq);
2227  }
2228  if (report)
2229  cout << "4 " << flush;
2230  // [last..]
2231  {
2232  bvect bv2; bvect bv2_c;
2233  bvect::mem_pool_guard g1(pool, bv2);
2234  bvect::mem_pool_guard g2(pool, bv2_c);
2235 
2236  bv2_c.copy_range(bv, l, bm::id_max-1);
2237 
2238  interval_copy_range(bv2, bv, l, bm::id_max - 1);
2239  eq = bv2.equal(bv2_c);
2240  assert(eq);
2241  }
2242  if (report)
2243  cout << "5 " << flush;
2244  // [mid..last]
2245  {
2246  bvect bv2; bvect bv2_c;
2247  bvect::mem_pool_guard g1(pool, bv2);
2248  bvect::mem_pool_guard g2(pool, bv2_c);
2249 
2250  bv2_c.copy_range(bv, m, l);
2251 
2252  interval_copy_range(bv2, bv, m, l);
2253  eq = bv2.equal(bv2_c);
2254  assert(eq);
2255  }
2256  if (report)
2257  cout << "6 " << flush;
2258  // [first..mid]
2259  {
2260  bvect bv2; bvect bv2_c;
2261  bvect::mem_pool_guard g1(pool, bv2);
2262  bvect::mem_pool_guard g2(pool, bv2_c);
2263 
2264  bv2_c.copy_range(bv, f, m);
2265 
2266  interval_copy_range(bv2, bv, f, m);
2267  eq = bv2.equal(bv2_c);
2268  assert(eq);
2269  }
2270  if (report)
2271  cout << endl;
2272 }
2273 
2274 
2275 
2276 
2277 // vectors comparison check
2278 
2279 void CheckVectors(bvect_mini &bvect_min,
2280  bvect &bvect_full,
2281  unsigned size,
2282  bool detailed)
2283 {
2284  cout << "\nVectors checking...bits to compare = " << size << endl;
2285 
2286  cout << "Bitcount summary : ";
2287  unsigned min_count = bvect_min.bit_count();
2288  cout << " minvector count = " << min_count;
2289  unsigned count = bvect_full.count();
2290  unsigned full_count = bvect_full.recalc_count();
2291  cout << " fullvector re-count = " << full_count << endl;
2292 
2293  if (min_count != full_count)
2294  {
2295  cout << "fullvector count = " << count << endl;
2296  cout << "Count comparison failed !!!!" << endl;
2297  print_stat(cout, bvect_full);
2298  DetailedCheckVectors(bvect_min, bvect_full, size);
2299  assert(0);
2300  exit(1);
2301  }
2302 
2303  if (full_count)
2304  {
2305  bool any = bvect_full.any();
2306  if (!any)
2307  {
2308  cout << "Anycheck failed!" << endl;
2309  exit(1);
2310  }
2311  }
2312 
2313  // find_last check
2314  {
2315  bm::id_t pos1 = 0;
2316  bm::id_t pos2 = 0;
2317  bool last_found1 = FindLastBit(bvect_full, pos1);
2318  bool last_found2 = bvect_full.find_reverse(pos2);
2319 
2320  assert(last_found1 == last_found2);
2321  if (last_found1)
2322  {
2323  assert(pos1 == pos2);
2324  }
2325  }
2326 
2327  IntervalsCheck(bvect_full);
2328  IntervalsEnumeratorCheck(bvect_full, true);
2329 
2330  if (!detailed)
2331  return;
2332 
2333  // get_next comparison
2334  cout << "Positive bits comparison..." << flush;
2335  unsigned nb_min = bvect_min.get_first();
2336  unsigned nb_ful = bvect_full.get_first();
2337 
2338  bvect::counted_enumerator en = bvect_full.first();
2339  unsigned nb_en = *en;
2340  bvect::enumerator en1 = bvect_full.get_enumerator(*en);
2341  if (nb_min != nb_ful)
2342  {
2343  cout << "!!!! First bit comparison failed. Full id = "
2344  << nb_ful << " Min id = " << nb_min
2345  << endl;
2346 
2347  bool bit_f = bvect_full.get_bit(nb_ful);
2348  cout << "Full vector'd bit #" << nb_ful << "is:"
2349  << bit_f << endl;
2350 
2351  bool bit_m = (bvect_min.is_bit_true(nb_min) == 1);
2352  cout << "Min vector'd bit #" << nb_min << "is:"
2353  << bit_m << endl;
2354 
2355 
2356  print_stat(cout,bvect_full);
2357 
2358  DetailedCheckVectors(bvect_min, bvect_full, size);
2359 
2360  exit(1);
2361  }
2362  CompareEnumerators(en, en1);
2363 
2364  if (full_count)
2365  {
2366  unsigned bit_count = 1;
2367  unsigned en_prev = nb_en;
2368 
2369  do
2370  {
2371  nb_min = bvect_min.get_next(nb_min);
2372  if (nb_min == 0)
2373  {
2374  break;
2375  }
2376 
2377  en_prev = nb_en;
2378  ++en;
2379  ++en1;
2380  CompareEnumerators(en, en1);
2381 
2382  if ((bit_count % 10 == 0) || (bit_count % 128 == 0))
2383  {
2384  bvect::enumerator en2 = bvect_full.get_enumerator(*en);
2385  CompareEnumerators(en, en2);
2386  }
2387 
2388  nb_en = *en;
2389  ++bit_count;
2390 
2391  if (nb_en != nb_min)
2392  {
2393  nb_ful = bvect_full.get_next(en_prev);
2394  cout << "!!!!! next bit comparison failed. Full id = "
2395  << nb_ful << " Min id = " << nb_min
2396  << " Enumerator = " << nb_en
2397  << endl;
2398 
2399  // bvect_full.stat();
2400 
2401  // DetailedCheckVectors(bvect_min, bvect_full, size);
2402 
2403  exit(1);
2404  }
2405  } while (en.valid());
2406  if (bit_count != min_count)
2407  {
2408  cout << " Bit count failed."
2409  << " min = " << min_count
2410  << " bit = " << bit_count
2411  << endl;
2412  exit(1);
2413  }
2414  }
2415 
2416  cout << "OK" << endl;
2417 
2418  return;
2419 }
2420 
2421 static
2423 {
2424  cout << "---------------------------- DynamicMatrixTest() test" << endl;
2425 
2426  {
2428  matr.resize(3, bm::set_sub_array_size);
2429  matr.set_zero();
2430 
2431  {
2432  unsigned* r = matr.row(1);
2433  for (unsigned i = 0; i < matr.cols(); ++i)
2434  {
2435  r[i] = i;
2436  }
2437  }
2438 
2439  matr.resize(matr.rows()+1, matr.cols());
2440  {
2441  unsigned* r = matr.row(3);
2442  for (unsigned i = 0; i < matr.cols(); ++i)
2443  {
2444  r[i] = i;
2445  }
2446  }
2447 
2448  {
2449  const unsigned* r = matr.row(1);
2450  for (unsigned i = 0; i < matr.cols(); ++i)
2451  {
2452  assert(r[i] == i);
2453  }
2454  }
2455  }
2456  {
2458  matr.init();
2459  matr.set_zero();
2460 
2461  matr.set(0, 0, 10);
2462  matr.set(1, 1, 100);
2463  matr.set(2, 2, 200);
2464 
2465  matr.set(1, 0, 1);
2466  matr.set(2, 0, 2);
2467  matr.set(2, 1, 21);
2468 
2469  assert(matr.get(0, 0) == 10);
2470  assert(matr.get(1, 1) == 100);
2471  assert(matr.get(2, 2) == 200);
2472 
2473 
2474  matr.replicate_triange();
2475 
2476  assert(matr.get(0, 1) == 1);
2477  assert(matr.get(0, 2) == 2);
2478  assert(matr.get(1, 2) == 21);
2479 
2480 
2481 
2482  bm::id64_t s;
2483  matr.sum(s, 0);
2484  assert(s == 13);
2485 
2486  }
2487 
2488 
2489  cout << "---------------------------- DynamicMatrixTest() test OK" << endl;
2490 }
2491 
2492 static
2494 {
2495  cout << "---------------------------- RSIndexTest() test" << endl;
2496 
2497  {
2498  rs_ind rsi;
2499 
2502 
2503  rsi.set_super_block(0, 1);
2504  rsi.set_super_block(1, 2);
2505  rsi.set_super_block(2, 3);
2506  rsi.set_null_super_block(3);
2507  rsi.set_full_super_block(4);
2508 
2509  auto sb_size = rsi.super_block_size();
2510  assert(sb_size == 5);
2511 
2512  auto rc = rsi.get_super_block_count(0);
2513  assert(rc == 1);
2514  rc = rsi.get_super_block_count(1);
2515  assert(rc == 2);
2516  rc = rsi.get_super_block_count(2);
2517  assert(rc == 3);
2518  rc = rsi.get_super_block_count(256);
2519  assert(rc == 0);
2520 
2521 
2522  auto bc = rsi.get_super_block_rcount(0);
2523  assert(bc == 1);
2524  bc = rsi.get_super_block_rcount(1);
2525  assert(bc == 3);
2526  bc = rsi.get_super_block_rcount(2);
2527  assert(bc == 6);
2528 
2529  unsigned i = rsi.find_super_block(1);
2530  assert(i == 0);
2531  i = rsi.find_super_block(2);
2532  assert(i == 1);
2533  i = rsi.find_super_block(3);
2534  assert(i == 1);
2535  i = rsi.find_super_block(4);
2536  assert(i == 2);
2537  i = rsi.find_super_block(200);
2538  assert(i == 4);
2539 /*
2540  i = rsi.find_super_block(bm::id_max);
2541  assert(i == 5);
2542 */
2543  }
2544 
2545  {
2546  unsigned bcount[bm::set_sub_array_size];
2547  bm::id64_t sub_count1[bm::set_sub_array_size];
2548  bm::id64_t sub_count2[bm::set_sub_array_size];
2549  for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
2550  {
2551  bcount[i] = 0; sub_count1[i] = sub_count2[i] = 0;
2552  } // for
2553  bcount[0] = 1;
2554  bcount[255] = 2;
2555 
2556  sub_count1[0] = 1; // sub-range 0
2557  sub_count1[255] = 0; // sub-3
2558  sub_count2[0] = 1 << 16; // sub-2
2559  sub_count2[255] = 1 << 16; // sub 2,3
2560 
2561 
2562  rs_ind rsi;
2563  // -----------------------------------------
2567 
2568 
2569  rsi.set_null_super_block(0);
2570  auto tcnt = rsi.count();
2571  assert(tcnt == 0);
2572  rsi.register_super_block(1, &bcount[0], &sub_count1[0]);
2573  tcnt = rsi.count();
2574  assert(tcnt == 3);
2575  rsi.register_super_block(2, &bcount[0], &sub_count2[0]);
2576  tcnt = rsi.count();
2577  assert(tcnt == 6);
2578  rsi.set_full_super_block(3);
2579  tcnt = rsi.count();
2580  assert(tcnt == 6 + bm::set_sub_array_size * 65536);
2581 
2582  unsigned i = rsi.find_super_block(1);
2583  assert(i == 1);
2584  i = rsi.find_super_block(3);
2585  assert(i == 1);
2586  i = rsi.find_super_block(4);
2587  assert(i == 2);
2588  i = rsi.find_super_block(400);
2589  assert(i == 3);
2590 // i = rsi.find_super_block(bm::id_max);
2591 // assert(i == rsi.super_block_size());
2592 
2593  unsigned bc;
2594  rs_ind::size_type rbc;
2595  for (unsigned nb = 0; nb < bm::set_sub_array_size; ++nb)
2596  {
2597  bc = rsi.count(nb);
2598  assert(bc == 0);
2599  rbc = rsi.rcount(nb);
2600  assert(!rbc);
2601  }
2602  bc = rsi.count(bm::set_sub_array_size);
2603  assert(bc == 1);
2604  rbc = rsi.rcount(bm::set_sub_array_size);
2605  assert(rbc == 1);
2606 
2607  bc = rsi.count(bm::set_sub_array_size+1);
2608  assert(bc == 0);
2609  rbc = rsi.rcount(bm::set_sub_array_size+1);
2610  assert(rbc == 1);
2611 
2612  bc = rsi.count(bm::set_sub_array_size + 255);
2613  assert(bc == 2);
2614  rbc = rsi.rcount(bm::set_sub_array_size + 255);
2615  assert(rbc == 3);
2616 
2617  bc = rsi.count(bm::set_sub_array_size*3);
2618  assert(bc == 65536);
2619  rbc = rsi.rcount(bm::set_sub_array_size*3);
2620  assert(rbc == 65536+6);
2621  rbc = rsi.rcount(bm::set_sub_array_size*3 + 1);
2622  assert(rbc == 65536+6 + 65536);
2623 
2624 
2625  // ==========================
2626  {
2627  auto nb = rsi.find(1);
2628  assert(nb == 256);
2629 
2630  nb = rsi.find(2);
2631  assert(nb == bm::set_sub_array_size+255);
2632  nb = rsi.find(3);
2633  assert(nb == bm::set_sub_array_size+255);
2634 
2635  nb = rsi.find(4);
2636  assert(nb == bm::set_sub_array_size+255+1);
2637 
2638  nb = rsi.find(65536);
2639  assert(nb == 3*bm::set_sub_array_size+0);
2640  nb = rsi.find(65536*2);
2641  assert(nb == 3*bm::set_sub_array_size+1);
2642  nb = rsi.find(65536*3);
2643  assert(nb == 3*bm::set_sub_array_size+2);
2644  }
2645  // ==========================
2646 
2647  {
2648  bool b;
2651  bm::gap_word_t sub_range;
2652 
2653  rank = 1;
2654  b = rsi.find(&rank, &nb, &sub_range);
2655  assert(b);
2656  assert(nb == 256);
2657  assert(sub_range == 0);
2658  assert(rank == 1);
2659 
2660  rank = 2;
2661  b = rsi.find(&rank, &nb, &sub_range);
2662  assert(b);
2663  assert(nb == bm::set_sub_array_size+255);
2664  assert(sub_range == bm::rs3_border1 + 1);
2665  assert(rank == 1);
2666 
2667  rank = 3;
2668  b = rsi.find(&rank, &nb, &sub_range);
2669  assert(b);
2670  assert(nb == bm::set_sub_array_size+255);
2671  assert(sub_range == bm::rs3_border1 + 1);
2672  assert(rank == 2);
2673 
2674  rank = 4;
2675  b = rsi.find(&rank, &nb, &sub_range);
2676  assert(b);
2677  assert(nb == bm::set_sub_array_size+255+1);
2678  assert(sub_range == bm::rs3_border0 + 1);
2679  assert(rank == 1);
2680 
2681  rank = 5;
2682  b = rsi.find(&rank, &nb, &sub_range);
2683  assert(b);
2684  assert(nb == bm::set_sub_array_size+256+255);
2685  assert(sub_range == bm::rs3_border0 + 1);
2686  assert(rank == 1);
2687 
2688  rank = 6;
2689  b = rsi.find(&rank, &nb, &sub_range);
2690  assert(b);
2691  assert(nb == bm::set_sub_array_size+256+255);
2692  assert(sub_range == bm::rs3_border1 + 1);
2693  assert(rank == 1);
2694 
2695  rank = 65536;
2696  b = rsi.find(&rank, &nb, &sub_range);
2697  assert(b);
2698  assert(nb == 3*bm::set_sub_array_size+0);
2699  assert(sub_range == bm::rs3_border1 + 1);
2700  assert(rank == 65536 - 6 - bm::rs3_border1 - 1);
2701 
2702  rank = 65536 + 7;
2703  b = rsi.find(&rank, &nb, &sub_range);
2704  assert(b);
2705  assert(nb == 3*bm::set_sub_array_size+1);
2706  assert(sub_range == 0);
2707  assert(rank == 1);
2708 
2709  rank = bm::id_max;
2710  b = rsi.find(&rank, &nb, &sub_range);
2711  assert(!b);
2712 
2713 
2714  }
2715 
2716  }
2717 
2718 
2719  cout << "---------------------------- RSIndexTest() test OK" << endl;
2720 }
2721 
2722 
2723 static
2725 {
2726  bvect bvect_full;
2727 
2728  for (unsigned i = 0; i < 100000; ++i)
2729  {
2730  bvect_full.set_bit(i);
2731  }
2733  bvect_full.optimize(tb);
2734  bvect_full.clear();
2735 
2736  print_stat(cout, bvect_full);
2737 
2738  unsigned count = bvect_full.count();
2739  assert(count == 0);
2740  print_stat(cout, bvect_full);
2741 }
2742 
2743 static
2745 {
2746  cout << "---------------------------- WordCmp test" << endl;
2747 
2748  for (int i = 0; i < 10000000; ++i)
2749  {
2750  unsigned w1 = unsigned(rand());
2751  unsigned w2 = unsigned(rand());
2752  int res = wordcmp0(w1, w2);
2753  int res2 = wordcmp(w1, w2);
2754  if (res != res2)
2755  {
2756  printf("WordCmp failed !\n");
2757  exit(1);
2758  }
2759 
2760  res = wordcmp0((unsigned)0U, (unsigned)w2);
2761  res2 = wordcmp((unsigned)0U, (unsigned)w2);
2762 
2763  if (res != res2)
2764  {
2765  printf("WordCmp 0 test failed !\n");
2766  exit(1);
2767  }
2768 
2769  res = wordcmp0((unsigned)~0U, (unsigned)w2);
2770  res2 = wordcmp((unsigned)~0U, (unsigned)w2);
2771 
2772  if (res != res2)
2773  {
2774  printf("WordCmp ~0 test failed !\n");
2775  exit(1);
2776  }
2777 
2778  res = wordcmp0((unsigned)w2, (unsigned)0);
2779  res2 = wordcmp((unsigned)w2, (unsigned)0);
2780 
2781  if (res != res2)
2782  {
2783  printf("WordCmp 0-2 test failed !\n");
2784  exit(1);
2785  }
2786 
2787  }
2788 
2789  cout << "Ok." << endl;
2790 }
2791 
2792 
2793 static
2795 {
2796  cout << "---------------------------- CountChange test" << endl;
2797 
2798 #ifdef VECT_BLOCK_CHANGE
2799 
2800  unsigned i, c, cc;
2802 
2803  for (i = 0; i < bm::set_block_size; ++i)
2804  blk[i] = 0;
2805 
2806  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2807  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2808  assert(c == 1);
2809  assert(c == cc);
2810 
2811  blk[0] = 1;
2812  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2813  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2814  assert(c == 2);
2815  assert(c == cc);
2816 
2817  blk[0] = 0xFF;
2818  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2819  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2820  assert(c == 2);
2821  assert(c == cc);
2822 
2823  blk[0] = ~0u;
2824  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2825  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2826  assert(c == 2);
2827  assert(c == cc);
2828 
2829  blk[0] = blk[1] = blk[2] = blk[3] = 2;
2830  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2831  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2832  assert(c == cc);
2833 
2834  blk[4] = blk[5] = blk[6] = blk[7] = 2;
2835  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2836  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2837  assert(c == cc);
2838 
2839  {
2840  for (i = 0; i < bm::set_block_size; ++i)
2841  blk[i] = 2;
2842 
2843  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2844  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2845  assert(c == cc);
2846  }
2847 
2848  {
2849  for (i = 0; i < bm::set_block_size; ++i)
2850  blk[i] = 1u << 31;
2851 
2852  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2853  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2854  assert(c == cc);
2855  }
2856 
2857  {
2858  for (i = 0; i < bm::set_block_size; ++i)
2859  blk[i] = ~0u << 30;
2860 
2861  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2862  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2863  assert(c == cc);
2864  }
2865 
2866  cout << "Block change stress..." << endl;
2867  {
2868  std::chrono::time_point<std::chrono::steady_clock> s;
2869  std::chrono::time_point<std::chrono::steady_clock> f;
2870  s = std::chrono::steady_clock::now();
2871 
2872 
2873  unsigned k_max = (1u << 31) / 4;
2874  for (unsigned k = 0; k <= k_max; ++k)
2875  {
2876  for (i = 0; i < bm::set_block_size; ++i)
2877  blk[i] = k;
2878  c = VECT_BLOCK_CHANGE(blk, sizeof(blk)/sizeof(blk[0]));
2879  cc = bm::bit_block_change32(blk, sizeof(blk)/sizeof(blk[0]));
2880  assert(c == cc);
2881 
2882  if (k % 100000 == 0)
2883  {
2884  f = std::chrono::steady_clock::now();
2885  auto diff = f - s;
2886  auto d = std::chrono::duration <double, std::milli> (diff).count();
2887 
2888  if (!is_silent)
2889  cout << "\r" << k << " / " << k_max << " (" << d << "ms)" << flush;
2890 
2891  s = std::chrono::steady_clock::now();
2892  }
2893  } // for k
2894  }
2895  cout << endl;
2896 
2897 #endif
2898 
2899 
2900  cout << "---------------------------- CountChange test OK" << endl;
2901 }
2902 
2903 
2904 inline
2906  const bm::word_t* block,
2907  const bm::word_t* xor_block,
2908  block_waves_xor_descr& x_descr,
2909  bm::xor_complement_match& match_type)
2910 {
2911  unsigned gc, bc;
2912  unsigned c_gc, c_bc;
2913  bm::compute_s_block_descr(block, x_descr, &gc, &bc);
2914  bm::bit_block_change_bc(block, &c_gc, &c_bc);
2915  assert(gc == c_gc);
2916  assert(bc == c_bc);
2917 
2919  bm::id64_t d64 = bm::calc_block_digest0(block);
2920 
2921  xor_scanner<bvect> xs;
2922  xs.compute_s_block_stats(block);
2923  xs.compute_xor_complexity_descr(block, d64, xor_block, x_descr, xmd);
2924  match_type = xmd.match_type;
2925  return xmd.xor_d64;
2926 }
2927 
2928 static
2929 void Check_XOR_Product(const bm::word_t* block,
2930  const bm::word_t* xor_block,
2931  bm::id64_t digest)
2932 {
2933  assert(digest);
2934 
2937 
2938  bm::bit_block_xor(t_blk1, block, xor_block, digest);
2939  bm::bit_block_xor(t_blk2, t_blk1, xor_block, digest);
2940 
2941  unsigned cnt = bm::bit_block_xor_count(block, t_blk2);
2942  assert(cnt == 0); // identically restored
2943 }
2944 
2945 
2946 static
2948 {
2949  cout << "---------------------------- TestBlockCountXORChange() test" << endl;
2950  unsigned i;
2951  bm::id64_t d64;
2952  bm::block_waves_xor_descr x_descr;
2953  unsigned gc, bc;
2954 
2955  {
2957  bmc.nb=100;
2958  bmc.chain_size = 56;
2959  bmc.ref_idx[0]=1024;
2960  bmc.xor_d64[0]=~0ULL;
2961 
2963  bmc2 = bmc;
2964  assert(bmc2.nb==100);
2965  assert(bmc2.chain_size == 56);
2966  assert(bmc2.ref_idx[0]==1024);
2967  }
2968 
2969  {
2971  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
2972  for (unsigned k = 0; k < bm::block_waves; ++k)
2973  {
2974  assert(x_descr.sb_bc[k] == 0);
2975  } // for
2976  assert(bc == 0);
2977  assert(gc == 1);
2978 
2980  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
2981  assert(x_descr.sb_bc[0] == 0);
2982  assert(x_descr.sb_bc[1] == 1);
2983  assert(x_descr.sb_gc[0] == 1);
2984  assert(x_descr.sb_gc[1] == 2);
2985  assert(bc == 1);
2986  assert(gc == 3);
2987 
2988  blk[bm::set_block_digest_wave_size-1] = 1u << 31;
2989  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
2990  assert(x_descr.sb_bc[0] == 1);
2991  assert(x_descr.sb_bc[1] == 1);
2992  assert(x_descr.sb_gc[0] == 2);
2993  assert(x_descr.sb_gc[1] == 2 || x_descr.sb_gc[1] == 1);
2994  assert(bc == 2);
2995  assert(gc == 3);
2996 
2997 
2998  blk[bm::set_block_digest_wave_size-1] = 0;
3000 
3001 
3002 
3003  blk[0] = 1;
3004  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
3005  assert(x_descr.sb_bc[0] == 1);
3006  assert(x_descr.sb_gc[0] == 2);
3007  for (unsigned k = 1; k < bm::block_waves; ++k)
3008  {
3009  assert(x_descr.sb_bc[k] == 0);
3010  } // for
3011  assert(bc == 1);
3012  assert(gc == 2);
3013 
3014 
3015 
3016  blk[0] = 1 | (1 << 1);
3017  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
3018  assert(x_descr.sb_bc[0] == 2);
3019  assert(x_descr.sb_gc[0] == 2);
3020  for (unsigned k = 1; k < bm::block_waves; ++k)
3021  {
3022  assert(x_descr.sb_bc[k] == 0);
3023  assert(x_descr.sb_gc[k] == 0);
3024  } // for
3025  assert(bc == 2);
3026  assert(gc == 2);
3027 
3028  blk[bm::set_block_size-1] = 1 | (1 << 1);
3029  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
3030  assert(x_descr.sb_bc[0] == 2);
3031  assert(x_descr.sb_gc[0] == 2);
3032  assert(x_descr.sb_bc[bm::block_waves-1] == 2);
3033  assert(x_descr.sb_gc[bm::block_waves-1] == 3 || x_descr.sb_gc[bm::block_waves-1] == 2);
3034  for (unsigned k = 1; k < bm::block_waves-1; ++k)
3035  {
3036  assert(x_descr.sb_bc[k] == 0);
3037  assert(x_descr.sb_gc[k] == 0);
3038  } // for
3039 
3040  blk[0] = 0;
3041  bm::compute_s_block_descr(blk, x_descr, &gc, &bc);
3042  assert(x_descr.sb_bc[bm::block_waves-1] == 2);
3043  assert(x_descr.sb_gc[bm::block_waves-1] == 3 || x_descr.sb_gc[bm::block_waves-1] == 2);
3044  for (unsigned k = 0; k < bm::block_waves-1; ++k)
3045  {
3046  assert(x_descr.sb_bc[k] == 0);
3047  if (k == 0)
3048  {
3049  assert(x_descr.sb_gc[k] == 1);
3050  }
3051  } // for
3052 
3053  }
3054 
3055  // test match vector search/refine
3056  //
3057  {
3058  typedef
3060  xor_matches_vector_type;
3061  typedef
3063  m_pairs_vector_type;
3064  xor_matches_vector_type xm_vect;
3065  m_pairs_vector_type pm_vect;
3066  {
3068  xmd.match_type = e_xor_match_BC; xmd.ref_idx = 10; xmd.xor_d64 = 1ull;
3069  xm_vect.push_back(xmd);
3070  }
3071  auto cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 10, (1ull << 1), e_xor_match_BC);
3072  assert(!cnt);
3073  assert(pm_vect.size()==0);
3074  cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
3075  assert(cnt == 1);
3076  assert(pm_vect.size()==1);
3077  bm::match_pair mp = pm_vect[0];
3078  assert(mp.ref_idx == 10);
3079  assert(pm_vect[0].xor_d64 == 1ull);
3080  cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_iBC);
3081  assert(cnt == 0);
3082 /*
3083  int brate = bm::check_pair_vect_vbr(pm_vect, 255);
3084  assert(brate == 1);
3085  brate = bm::check_pair_vect_vbr(pm_vect, 65535);
3086  assert(brate == 2);
3087  brate = bm::check_pair_vect_vbr(pm_vect, 65536);
3088  assert(brate == 0);
3089 */
3090 
3091  {
3093  xmd.match_type = e_xor_match_BC; xmd.ref_idx = 20; xmd.xor_d64 = 3ull;
3094  xm_vect.push_back(xmd);
3095  }
3096  cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
3097  assert(cnt == 1);
3098  mp = pm_vect[0];
3099  assert(pm_vect[0].ref_idx == 20);
3100  assert(mp.xor_d64 == 1ull);
3101 
3102  {
3103  xm_vect.resize(0);
3105  xmd.match_type = e_xor_match_BC; xmd.ref_idx = 20; xmd.xor_d64 = 3ull;
3106  xm_vect.push_back(xmd);
3107  xmd.match_type = e_xor_match_BC; xmd.ref_idx = 25; xmd.xor_d64 = 3ull << 60;
3108  xm_vect.push_back(xmd);
3109  }
3110  cnt = bm::greedy_refine_match_vector(pm_vect, xm_vect, 11, (1ull << 1), e_xor_match_BC);
3111  assert(cnt == 2);
3112  mp = pm_vect[0];
3113  assert(pm_vect[0].ref_idx == 20);
3114  assert(mp.xor_d64 == 1ull);
3115  mp = pm_vect[1];
3116  assert(mp.ref_idx == 25);
3117  assert(mp.xor_d64 == 3ull << 60);
3118 
3119  }
3120 
3121  {
3122  bm::xor_complement_match match_type;
3125 
3126  for (i = 0; i < bm::set_block_size; ++i)
3127  blk[i] = blk_xor[i] = 0;
3128 
3129  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3130  assert(d64 == ~0ull);
3131  assert(match_type == bm::e_xor_match_GC);
3132  for (unsigned k = 0; k < bm::block_waves; ++k)
3133  {
3134  assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
3135  assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
3136  } // for k
3137 
3138  blk[0] = 1;
3139  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3140  assert(!d64);
3141  assert(match_type == bm::e_no_xor_match);
3142 
3143  assert(x_descr.sb_gc[0] == 2);
3144  assert(x_descr.sb_xor_gc[0] == 2);
3145  for (unsigned k = 1; k < bm::block_waves; ++k)
3146  {
3147  assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
3148  assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
3149  } // for k
3150 
3151  // ----------------------------
3152  blk[0] = 1 | (1<<1) | (1<<2); blk_xor[0] = (1 << 1);
3153  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3154  assert(d64);
3155  assert(x_descr.sb_bc[0] == 3);
3156  assert(x_descr.sb_xor_bc[0] == 2);
3157  assert(match_type == bm::e_xor_match_BC);
3158 
3159 
3160  // ----------------------------
3161  blk[0] = 1; blk_xor[0] = 1;
3162  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3163  cout << x_descr.sb_xor_gc[0] << endl;
3164  assert(x_descr.sb_gc[0] == 2);
3165  assert(match_type == bm::e_xor_match_BC);
3166  // next assert hides non-critical discrepancy between SIMD versions
3167  assert(x_descr.sb_xor_gc[0] == 1 || x_descr.sb_xor_gc[0] == 0);
3168  assert(d64 == 1ull);
3169  for (unsigned k = 1; k < bm::block_waves; ++k)
3170  {
3171  assert(x_descr.sb_gc[k] == 1 || (k && x_descr.sb_gc[k] == 0));
3172  assert(x_descr.sb_xor_gc[k] == 1 || (k && x_descr.sb_xor_gc[k] == 0));
3173  } // for k
3174 
3175  Check_XOR_Product(blk, blk_xor, d64);
3176 
3177  blk[0] = (1 << 10) | (1 << 12) | (1 << 14) | ( 1 << 16) | (1 << 18) | (1<<19);
3178  blk_xor[0] = (1 << 11) | (1 << 13) | (1 << 15) | (1 << 17);
3179  unsigned off = (60 * bm::set_block_digest_wave_size);
3180  blk[off] = (1 << 10) | (1 << 12);
3181 
3182  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3183  assert(x_descr.sb_gc[0] == 11);
3184  assert(x_descr.sb_xor_gc[0] == 3);
3185  assert((d64 & 1));
3186  assert(match_type == bm::e_xor_match_GC);
3187 
3188  Check_XOR_Product(blk, blk_xor, d64);
3189 
3190  for (unsigned k = 1; k < bm::block_waves; ++k)
3191  {
3192  if (k!= 60)
3193  {
3194  assert(x_descr.sb_gc[k] == 0);
3195  assert(x_descr.sb_xor_gc[k] == 0);
3196  }
3197  else
3198  {
3199  assert(x_descr.sb_gc[60] == 4);
3200  assert(x_descr.sb_xor_gc[60] == 4);
3201  }
3202  } // for k
3203 
3204  blk_xor[off] = (1 << 10) | (1 << 11) | (1 << 12);
3205  d64 = bit_block_calc_xor_change_digest(blk, blk_xor, x_descr, match_type);
3206  assert(x_descr.sb_gc[0] == 11);
3207  assert(x_descr.sb_xor_gc[0] == 3);
3208  assert((d64 & 1) && (d64 & (1ull << 60)));
3209  assert(match_type == bm::e_xor_match_GC);
3210 
3211  for (unsigned k = 1; k < bm::block_waves; ++k)
3212  {
3213  if (k!= 60)
3214  {
3215  assert(x_descr.sb_gc[k] == 0);
3216  assert(x_descr.sb_xor_gc[k] == 0);
3217  }
3218  else
3219  {
3220  assert(x_descr.sb_gc[60] == 4);
3221  assert(x_descr.sb_xor_gc[60] == 2);
3222  }
3223  } // for k
3224 
3225  Check_XOR_Product(blk, blk_xor, d64);
3226 
3227  }
3228 
3229  cout << "---------------------------- TestBlockCountXORChange() test OK" << endl;
3230 }
3231 
3232 
3233 /*!
3234  \brief Converts bit block to GAP.
3235  \param dest - Destinatio GAP buffer.
3236  \param src - Source bitblock buffer.
3237  \param bits - Number of bits to convert.
3238  \param dest_len - length of the dest. buffer.
3239  \return New length of GAP block or 0 if conversion failed
3240  (insufficicent space).
3241 
3242  @ingroup gapfunc
3243 */
3244 template<typename T>
3245 unsigned bit_convert_to_gap(T* dest,
3246  const unsigned* src,
3247  bm::id_t bits,
3248  unsigned dest_len)
3249 {
3250  T* pcurr = dest;
3251  T* end = dest + dest_len;
3252  unsigned bitval = (*src) & 1u;
3253  *pcurr = (T)bitval;
3254 
3255  ++pcurr;
3256  *pcurr = 0;
3257  unsigned bit_idx = 0;
3258  unsigned bitval_next;
3259 
3260  unsigned val = *src;
3261 
3262  do
3263  {
3264  // We can fast pace if *src == 0 or *src = 0xffffffff
3265 
3266  while (val == 0 || val == 0xffffffff)
3267  {
3268  bitval_next = val ? 1 : 0;
3269  if (bitval != bitval_next)
3270  {
3271  *pcurr++ = (T)(bit_idx-1);
3272  assert((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
3273  if (pcurr >= end)
3274  {
3275  return 0; // OUT of memory
3276  }
3277  bitval = bitval_next;
3278  }
3279  bit_idx += unsigned(sizeof(*src) * 8);
3280  if (bit_idx >= bits)
3281  {
3282  goto complete;
3283  }
3284  ++src;
3285  val = *src;
3286  }
3287 
3288  unsigned mask = 1;
3289  while (mask)
3290  {
3291  // Now plane bitshifting. TODO: Optimization wanted.
3292 
3293  bitval_next = val & mask ? 1 : 0;
3294  if (bitval != bitval_next)
3295  {
3296  *pcurr++ = (T)(bit_idx-1);
3297  assert((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
3298  bitval = bitval_next;
3299  if (pcurr >= end)
3300  return 0; // OUT of memory
3301  }
3302  mask <<= 1;
3303  ++bit_idx;
3304  } // while mask
3305 
3306  if (bit_idx >= bits)
3307  goto complete;
3308 
3309  ++src;
3310  val = *src;
3311 
3312  } while(1);
3313 
3314 complete:
3315  *pcurr = (T)(bit_idx-1);
3316  unsigned len = (unsigned)(pcurr - dest);
3317  *dest = (T)((*dest & 7) + (len << 3));
3318  return len;
3319 }
3320 
3321 /*
3322 static
3323 void TestGAP_XOR()
3324 {
3325  cout << "---------------------------- TestGAP_XOR()" << endl;
3326 
3327  unsigned gc, bc;
3328  {
3329  gap_vector gapv1(0);
3330  gap_vector gapv2(0);
3331  gap_word_t* gap_buf1 = gapv1.get_buf();
3332  gap_word_t* gap_buf2 = gapv2.get_buf();
3333 
3334 
3335  gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
3336  assert(bc == 0);
3337  assert(gc == 1);
3338 
3339  gapv1.set_bit(256);
3340  gapv2.set_bit(256);
3341 
3342  gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
3343  assert(bc == 0);
3344  assert(gc == 1);
3345 
3346  gapv1.set_bit(258);
3347  gapv2.set_bit(257);
3348  gapv1.set_bit(259);
3349  gapv1.set_bit(260);
3350 
3351  gap_operation_dry_xor(gap_buf1, gap_buf2, gc, bc);
3352  assert(bc == 4);
3353  assert(gc == 3);
3354 
3355  }
3356 
3357  cout << "---------------------------- TestGAP_XOR() - end" << endl;
3358 }*/
3359 
3360 static
3362 {
3363  cout << "---------------------------- TestBlockToGAP" << endl;
3364 
3365  unsigned i;
3367 
3368  for (i = 0; i < bm::set_block_size; ++i)
3369  blk[i] = 0;
3370 
3371  {
3372  gap_vector gapv1(0);
3373  gap_vector gapv2(0);
3374  gap_word_t* gap_buf1 = gapv1.get_buf();
3375  *gap_buf1 = 0;
3376  unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
3377  gap_word_t* gap_buf2 = gapv2.get_buf();
3378  unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
3379  print_gap(gapv2, 100);
3380  assert(len1 == len2);
3381  int cmp = bm::gapcmp(gap_buf1, gap_buf2);
3382  assert(cmp == 0);
3383 
3384  unsigned pos;
3385  bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
3386  assert(!f);
3387  }
3388 
3389  unsigned test_arr[] = { 1, 2, 3, (~0u << 4), ~0u, (~0u >> 1), (~0u >> 2) };
3390  unsigned arr_size = sizeof(test_arr)/sizeof(test_arr[0]);
3391  for (unsigned k = 0; k < bm::set_block_size; ++k)
3392  {
3393  for (i = 0; i < bm::set_block_size; ++i)
3394  blk[i] = 0;
3395  for (i = 0; i < arr_size; ++i)
3396  {
3397  blk[k] = test_arr[i];
3398 
3399  gap_vector gapv1(0);
3400  gap_vector gapv2(0);
3401  gap_word_t* gap_buf1 = gapv1.get_buf();
3402  *gap_buf1 = 0;
3403  unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
3404  print_gap(gapv1, 100);
3405  gap_word_t* gap_buf2 = gapv2.get_buf();
3406  unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
3407  assert(len1 == len2);
3408  assert(len1);
3409  print_gap(gapv2, 100);
3410  int cmp = bm::gapcmp(gap_buf1, gap_buf2);
3411  assert(cmp == 0);
3412 
3413  unsigned pos;
3414  bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
3415  assert(!f);
3416  }
3417  } // for k
3418 
3419  cout << "Test arr - ok" << endl;
3420 
3421  {
3422  gap_vector gapv1(0);
3423  gap_vector gapv2(0);
3424  gap_word_t* gap_buf1 = gapv1.get_buf();
3425  *gap_buf1 = 0;
3426  gap_word_t* gap_buf2 = gapv2.get_buf();
3427  *gap_buf2 = 0;
3428 
3429  unsigned mask = 1u;
3430  for (unsigned k = 0; k < bm::set_block_size; ++k)
3431  {
3432  for (i = 0; i < bm::set_block_size; ++i)
3433  blk[i] = 0;
3434 
3435  blk[k] = mask;
3436  mask <<= 1;
3437  if (!mask)
3438  mask = 1u;
3439 
3440  *gap_buf1 = 0;
3441  *gap_buf2 = 0;
3442  unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
3443  unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
3444  assert(len1);
3445  assert(len1 == len2);
3446  if (len1)
3447  {
3448  int cmp = bm::gapcmp(gap_buf1, gap_buf2);
3449  assert(cmp == 0);
3450 
3451  unsigned pos;
3452  bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
3453  assert(!f);
3454  }
3455  }
3456  }
3457 
3458  cout << "mask shift - ok" << endl;
3459 
3460  {
3461  gap_vector gapv1(0);
3462  gap_vector gapv2(0);
3463  gap_word_t* gap_buf1 = gapv1.get_buf();
3464  *gap_buf1 = 0;
3465  gap_word_t* gap_buf2 = gapv2.get_buf();
3466  *gap_buf2 = 0;
3467 
3468  unsigned max_try = 1000000;
3469  for (unsigned k = 0; k < max_try; ++k)
3470  {
3471  for (i = 0; i < bm::set_block_size; ++i)
3472  blk[i] = 0;
3473 
3474  unsigned idx = (unsigned)rand() % bm::set_block_size;
3475  blk[idx] |= (unsigned)rand();
3476  idx = (unsigned)rand() % bm::set_block_size;
3477  blk[idx] |= (unsigned)rand();
3478  idx = (unsigned)rand() % bm::set_block_size;
3479  blk[idx] |= (unsigned)rand();
3480  idx = (unsigned)rand() % bm::set_block_size;
3481  blk[idx] |= (unsigned)rand();
3482 
3483  idx = (unsigned)rand() % bm::set_block_size;
3484  blk[idx] |= ~0u;
3485  idx = (unsigned)rand() % bm::set_block_size;
3486  blk[idx] |= (~0u << (rand()%31));
3487 
3488  *gap_buf1 = 0;
3489  *gap_buf2 = 0;
3490  unsigned len1 = bit_convert_to_gap(gap_buf1, blk, bm::gap_max_bits, bm::gap_max_buff_len);
3491  unsigned len2 = bm::bit_to_gap(gap_buf2, blk, bm::gap_max_buff_len);
3492  assert(len1);
3493  assert(len1 == len2);
3494  if (len1)
3495  {
3496  int cmp = bm::gapcmp(gap_buf1, gap_buf2);
3497  assert(cmp == 0);
3498  unsigned pos;
3499  bool f = bm::gap_find_first_diff(gap_buf1, gap_buf2, &pos);
3500  assert(!f);
3501  }
3502  }
3503  }
3504 
3505 
3506  cout << "---------------------------- TestBlockToGAP OK" << endl;
3507 
3508 }
3509 
3510 
3511 static
3513 {
3514  cout << "---------------------------- ShiftRotate test" << endl;
3515 
3518  unsigned i;
3519 
3520  for (i = 0; i < bm::set_block_size; ++i)
3521  {
3522  blk0[i] = blk1[i] = 1;
3523  }
3524 
3527 
3528  for (i = 0; i < bm::set_block_size; ++i)
3529  {
3530  if (blk0[i] != 2 || blk0[i] != blk1[i])
3531  {
3532  cerr << "Cyclic rotate check failed" << endl;
3533  exit(1);
3534  }
3535  }
3536 
3539 
3540  for (i = 0; i < bm::set_block_size; ++i)
3541  {
3542  if (blk0[i] != 4 || blk0[i] != blk1[i])
3543  {
3544  cerr << "Cyclic rotate check failed" << endl;
3545  exit(1);
3546  }
3547  }
3548 
3549  for (i = 0; i < bm::set_block_size; ++i)
3550  {
3551  blk0[i] = blk1[i] = 1u << 31;
3552  }
3555 
3556  for (i = 0; i < bm::set_block_size; ++i)
3557  {
3558  if (blk0[i] != 1 || blk0[i] != blk1[i])
3559  {
3560  cerr << "Cyclic rotate check failed" << endl;
3561  exit(1);
3562  }
3563  }
3564 
3565  for (i = 0; i < bm::set_block_size; ++i)
3566  {
3567  blk0[i] = blk1[i] = unsigned(rand());
3568  }
3569 
3570  for (unsigned j = 0; j < bm::set_block_size * 32; ++j)
3571  {
3574 
3575  for (i = 0; i < bm::set_block_size; ++i)
3576  {
3577  if (blk0[i] != blk1[i])
3578  {
3579  cerr << "Stress Cyclic rotate check failed" << endl;
3580  exit(1);
3581  }
3582  }
3583  }
3584 
3585  // SHIFT-R tests
3586  //
3587 
3588  unsigned acc0, acc1;
3589 
3590  for (i = 0; i < bm::set_block_size; ++i)
3591  {
3592  blk0[i] = blk1[i] = 1;
3593  }
3594 
3595  bm::bit_block_shift_r1(blk0, &acc0, 0);
3596  bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
3597 
3598  for (i = 0; i < bm::set_block_size; ++i)
3599  {
3600  if (blk0[i] != blk1[i])
3601  {
3602  cerr << "1. SHIFT-r check failed" << endl;
3603  assert(0); exit(1);
3604  }
3605  assert(blk0[i] == 2);
3606  }
3607 
3608 
3609  for (i = 0; i < bm::set_block_size; ++i)
3610  {
3611  blk0[i] = blk1[i] = (1u << 31);
3612  }
3613 
3614  bm::bit_block_shift_r1(blk0, &acc0, 0);
3615  bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
3616 
3617  for (i = 0; i < bm::set_block_size; ++i)
3618  {
3619  if (blk0[i] != blk1[i])
3620  {
3621  cerr << "2. SHIFT-r check failed" << endl;
3622  exit(1);
3623  }
3624  }
3625 
3626  for (i = 0; i < bm::set_block_size; ++i)
3627  {
3628  blk0[i] = blk1[i] = unsigned(rand());
3629  }
3630 
3631  for (unsigned j = 0; j < bm::set_block_size * 32; ++j)
3632  {
3633  bm::bit_block_shift_r1(blk0, &acc0, 0);
3634  bm::bit_block_shift_r1_unr(blk1, &acc1, 0);
3635 
3636  assert(bool(acc0) == bool(acc1));
3637 
3638  for (i = 0; i < bm::set_block_size; ++i)
3639  {
3640  if (blk0[i] != blk1[i])
3641  {
3642  cerr << "Stress SHIFT-r check failed" << endl;
3643  exit(1);
3644  }
3645  }
3646  }
3647 
3648  cout << "---------------------------- ShiftRotate test OK" << endl;
3649 }
3650 
3651 static
3653 {
3654  cout << "---------------------------- BlockBitInsertTest test" << endl;
3655 
3658 
3659  unsigned i;
3660  for (i = 0; i < bm::set_block_size; ++i)
3661  blk0[i] = blk1[i] = 0;
3662 
3663  {
3664  bm::word_t co = bm::bit_block_insert(blk0, 0, 1);
3665  assert(co == 0);
3666  assert(blk0[0]==1u);
3667  co = bm::bit_block_insert(blk0, 0, 1);
3668  assert(co == 0);
3669  assert(blk0[0]==3u);
3670 
3671  blk0[bm::set_block_size-1] = ~0u;
3672  co = bm::bit_block_insert(blk0, 0, 0);
3673  assert(co == 1);
3674  assert(blk0[0]==(3u << 1));
3675  assert(blk0[bm::set_block_size-1] == (~0u << 1));
3676 
3677  blk0[0] = ~0u;
3678  co = bm::bit_block_insert(blk0, 1, 0);
3679  assert(co == 1);
3680  assert(blk0[0]==(~0u & ~(1u << 1)));
3681  assert(blk0[bm::set_block_size-1] == (~0u << 2));
3682 
3683  blk0[0] = ~0u;
3684  co = bm::bit_block_insert(blk0, 31, 0);
3685  assert(co == 1);
3686  assert(blk0[0]==(~0u >> 1));
3687  assert(blk0[1]==3);
3688  assert(blk0[bm::set_block_size-1] == (~0u << 3));
3689 
3690  blk0[0] = 0u;
3691  co = bm::bit_block_insert(blk0, 31, 1);
3692  assert(co == 1);
3693  assert(blk0[0]==(1u << 31));
3694  assert(blk0[1]==(3u << 1));
3695  assert(blk0[bm::set_block_size-1] == (~0u << 4));
3696  }
3697 
3698  cout << "bit-insert stress 0..." << endl;
3699  {
3700  for (i = 0; i < bm::set_block_size; ++i)
3701  blk0[i] = blk1[i] = 0;
3702 
3703  blk0[0] = 1;
3704  for (i = 0; i < 65536; ++i)
3705  {
3706  bm::word_t co = bm::bit_block_insert(blk0, i, 0);
3707  assert(co == 0 || i == 65535);
3708  if (i < 65535)
3709  {
3710  unsigned t = bm::test_bit(blk0, i+1);
3711  assert(t);
3712  }
3713  for (unsigned k = 0; k < 65536; ++k)
3714  {
3715  if (k != i+1)
3716  {
3717  unsigned t = bm::test_bit(blk0, k);
3718  assert(!t);
3719  }
3720  } // for k
3721  } // for i
3722  for (i = 0; i < bm::set_block_size; ++i)
3723  {
3724  if (blk0[i] != blk1[i])
3725  {
3726  cerr << "Stress insert(0) failed" << endl;
3727  exit(1);
3728  }
3729  }
3730  }
3731  cout << "OK" << endl;
3732 
3733  cout << "bit-insert stress 1..." << endl;
3734  {
3735  for (i = 0; i < bm::set_block_size; ++i)
3736  blk0[i] = ~0u;
3737 
3738  for (i = 0; i < 65536; ++i)
3739  {
3740  bm::word_t co = bm::bit_block_insert(blk0, i, 0);
3741  assert(co == 1 || i == 65535);
3742  for (unsigned k = 0; k < 65536; ++k)
3743  {
3744  unsigned t = bm::test_bit(blk0, k);
3745  if (k <= i)
3746  {
3747  assert(!t);
3748  }
3749  else
3750  {
3751  assert(t);
3752  }
3753  } // for k
3754  } // for i
3755  for (i = 0; i < bm::set_block_size; ++i)
3756  {
3757  if (blk0[i] != blk1[i])
3758  {
3759  cerr << "Stress insert(1) failed" << endl;
3760  exit(1);
3761  }
3762  }
3763  }
3764  cout << "OK" << endl;
3765 
3766 
3767  cout << "---------------------------- BlockBitInsertTest test OK" << endl;
3768 }
3769 
3770 
3771 static
3773 {
3774  cout << "---------------------------- BlockBitEraseTest test" << endl;
3777 
3778  bm::bit_block_set(blk0, 0);
3779  bm::bit_block_set(blk1, 0);
3780 
3781  {
3782  blk0[0] = 1;
3783  bm::bit_block_erase(blk0, 0, true);
3784  assert(blk0[0] == 0);
3785  assert(blk0[bm::set_block_size-1] == (1u << 31u));
3786 
3787  blk0[0] = ~0u;
3788  blk0[1] = 1u;
3789  blk0[bm::set_block_size-1] = (1u << 31u);
3790  bm::bit_block_erase(blk0, 0, false);
3791  assert(blk0[0] == ~0u);
3792  assert(blk0[1] == 0);
3793  assert(blk0[bm::set_block_size-1] == (1u << 30u));
3794 
3795  bm::bit_block_set(blk0, 0);
3796  blk0[1] = 15u; // ..01111
3797  bm::bit_block_erase(blk0, 31, false);
3798  assert(blk0[1] == 7u); // ..0111
3799  assert(blk0[0] == 1u << 31u);
3800 
3801  bm::bit_block_erase(blk0, 32, false);
3802  assert(blk0[1] == 3u); // ..011
3803 
3804  blk0[1] = 15u; // ..01111
3805  bm::bit_block_erase(blk0, 33, false);
3806  assert(blk0[1] == 7); //0b111
3807  }
3808 
3809  {
3810  bm::bit_block_set(blk0, ~0u);
3811  bm::word_t acc;
3812  bm::bit_block_shift_l1_unr(blk0, &acc, true);
3813  for (unsigned i = 0; i < bm::set_block_size; ++i)
3814  {
3815  assert(blk0[i] == ~0u);
3816  }
3817  bm::bit_block_erase(blk0, 0, false);
3818  for (unsigned i = 0; i < bm::set_block_size-1; ++i)
3819  {
3820  assert(blk0[i] == ~0u);
3821  }
3822  assert(blk0[bm::set_block_size-1] == ((~0u) >> 1) );
3823 
3824  bm::bit_block_shift_l1_unr(blk0, &acc, false);
3825  for (unsigned i = 0; i < bm::set_block_size-1; ++i)
3826  {
3827  assert(blk0[i] == ~0u);
3828  }
3829  assert(blk0[bm::set_block_size-1] == ((~0u) >> 2) );
3830 
3831  bm::bit_block_erase(blk0, 0, true);
3832  for (unsigned i = 0; i < bm::set_block_size-1; ++i)
3833  {
3834  assert(blk0[i] == ~0u);
3835  }
3836  assert(blk0[bm::set_block_size-1] == ((~0u >> 3) | (1u << 31)));
3837  }
3838 
3839  cout << "bit-insert-erase stress 0..." << endl;
3840  unsigned c = 0;
3841  {
3842  bm::bit_block_set(blk0, 0);
3843  bm::bit_block_set(blk1, 0);
3844 
3845  blk0[bm::set_block_size-1] = (1u << 31);
3846  for (unsigned i = 65535; i != 0; --i)
3847  {
3848  unsigned t = bm::test_bit(blk0, i);
3849  assert(t);
3850  bm::bit_block_erase(blk0, 0, false);
3851  unsigned cnt = bm::bit_block_count(blk0);
3852  {
3853  auto cnt2 = bm::bit_block_count(blk0, ~0ull);
3854  assert(cnt2 == cnt);
3855  auto d = calc_block_digest0(blk0);
3856  cnt2 = bm::bit_block_count(blk0, d);
3857  assert(cnt2 == cnt);
3858  }
3859 
3860  c += cnt;
3861  if (cnt != 1)
3862  {
3863  unsigned control = 0;
3864  for (unsigned k = 0; k < 65536; ++k)
3865  {
3866  t = bm::test_bit(blk0, k);
3867  control += t;
3868  }
3869 
3870  t = bm::test_bit(blk0, i-1);
3871  assert(t);
3872  cerr << t << " " << control << endl;
3873  cerr << "i=" << i << " cnt=" << cnt;
3874  cerr << " CNT==1 failed!" << endl;
3875  assert(cnt == 1);
3876  exit(1);
3877  }
3878  } // for i
3879 
3880  std::cout << c << endl;
3881 
3882  bm::bit_block_set(blk0, 0);
3883 
3884  {
3885  blk0[bm::set_block_size-1] = (1u << 31);
3886  unsigned j = 0;
3887  for (unsigned i = 65535; i != 0; --i, ++j)
3888  {
3889  unsigned t = bm::test_bit(blk0, i);
3890  assert(t);
3891  bm::bit_block_erase(blk0, j, false);
3892  if (i <= j)
3893  {
3894  t = bm::test_bit(blk0, j);
3895  assert(!t);
3896  t = bm::test_bit(blk0, i);
3897  assert(t);
3898 
3899  auto cnt = bm::bit_block_count(blk0);
3900  assert(cnt);
3901 
3902  bm::bit_block_erase(blk0, i, false);
3903  t = bm::test_bit(blk0, i);
3904  assert(!t);
3905  cnt = bm::bit_block_count(blk0);
3906  assert(!cnt);
3907  {
3908  auto cnt2 = bm::bit_block_count(blk0, ~0ull);
3909  assert(cnt == cnt2);
3910  auto d = calc_block_digest0(blk0);
3911  cnt2 = bm::bit_block_count(blk0, d);
3912  assert(cnt2 == cnt);
3913  }
3914  break;
3915  }
3916  auto cnt = bm::bit_block_count(blk0);
3917  assert(cnt == 1);
3918  } // for i
3919  }
3920 
3921  {
3922  bm::bit_block_set(blk0, 0);
3923  for (unsigned i = 0; i < 65535; ++i)
3924  {
3925  for(unsigned j = i; j < 65535; ++j)
3926  {
3927  bm::bit_block_set(blk0, 0);
3928  unsigned bitcount = j - i + 1;
3929  assert(i + bitcount < 65536);
3930  bm::or_bit_block(blk0, i, bitcount);
3931  if (bitcount == 1)
3932  {
3933  break;
3934  }
3935  unsigned bc = bm::bit_block_count(blk0);
3936  for (unsigned k = i + bitcount/2; k < i+bitcount; ++k)
3937  {
3938  auto t = bm::test_bit(blk0, k);
3939  assert(t);
3940 
3941  bm::bit_block_erase(blk0, k, false);
3942 
3943  unsigned bc2 = bm::bit_block_count(blk0);
3944  assert(bc2 == bc-1);
3945  {
3946  auto cnt2 = bm::bit_block_count(blk0, ~0ull);
3947  assert(cnt2 == bc2);
3948  auto d = calc_block_digest0(blk0);
3949  cnt2 = bm::bit_block_count(blk0, d);
3950  assert(cnt2 == bc2);
3951  }
3952  --bc;
3953  } // for k
3954 
3955  } // for j
3956  } // for i
3957  }
3958 
3959 
3960  }
3961  cout << "ok" << endl;
3962 
3963  cout << "---------------------------- BlockBitEraseTest test OK" << endl;
3964 }
3965 
3966 static
3968 {
3969  cout << "---------------------------- Empty bvector test" << endl;
3970 
3971  {
3972  bvect bv1;
3973  bvect bv2;
3974 
3975  bvect bv3(bv1 & bv2);
3976  bvect bv4 = (bv1 & bv2);
3977 
3978  std::vector< bvect > v;
3979  v.push_back(bvect());
3980  }
3981 
3982  {
3983  bvect bv1;
3984  bm::id_t cnt = bv1.count_range(0, 10);
3985  if (cnt)
3986  {
3987  cerr << "Failed count_range()" << endl;
3988  exit(1);
3989  }
3990  bool b = bv1.test(0);
3991  if (b)
3992  {
3993  cerr << "Failed test" << endl;
3994  exit(1);
3995  }
3996 
3997  b = bv1.any();
3998  if (b)
3999  {
4000  cerr << "Failed any" << endl;
4001  exit(1);
4002  }
4003 
4004  bv1.set_bit(0);
4005  if (!bv1.any())
4006  {
4007  cerr << "Failed set_bit" << endl;
4008  exit(1);
4009  }
4010  }
4011  {
4012  bvect bv1;
4013  bool b = bv1.set_bit_and(0, false);
4014  if (bv1.any() || b)
4015  {
4016  cerr << "Failed set_bit" << endl;
4017  exit(1);
4018  }
4019  }
4020  {
4021  bvect bv1;
4022  bv1.set_range(0, 1, false);
4023  if (bv1.any())
4024  {
4025  cerr << "Failed set_range" << endl;
4026  exit(1);
4027  }
4028  bv1.set_range(0, 1, true);
4029  if (bv1.count()!=2)
4030  {
4031  cerr << "Failed set_range(0,1)" << endl;
4032  exit(1);
4033  }
4034  }
4035  {
4036  bvect bv1;
4037  bv1.clear_bit(0);
4038  if (bv1.any())
4039  {
4040  cerr << "Failed clear_bit" << endl;
4041  exit(1);
4042  }
4043  }
4044  {
4045  bvect bv1;
4046  bv1.clear();
4047  if (bv1.any())
4048  {
4049  cerr << "Failed clear()" << endl;
4050  exit(1);
4051  }
4052  }
4053  {
4054  bvect bv1;
4055  bv1.invert();
4056  if (!bv1.any())
4057  {
4058  cerr << "Failed invert()" << endl;
4059  exit(1);
4060  }
4061  }
4062  {
4063  bvect bv1;
4064  bvect bv2;
4065  bv1.swap(bv2);
4066  if (bv1.any() || bv2.any())
4067  {
4068  cerr << "Failed swap()" << endl;
4069  exit(1);
4070  }
4071  }
4072  {
4073  bvect bv1;
4074  if (bv1.get_first() != 0)
4075  {
4076  cerr << "Failed get_first()" << endl;
4077  exit(1);
4078  }
4079  }
4080  {
4081  bvect bv1;
4082  if (bv1.extract_next(0) != 0)
4083  {
4084  cerr << "Failed extract_next()" << endl;
4085  exit(1);
4086  }
4087  }
4088  {
4089  bvect bv1;
4090  bvect::statistics st;
4091  bv1.calc_stat(&st);
4092  if (st.memory_used == 0)
4093  {
4094  cerr << "Failed calc_stat()" << endl;
4095  exit(1);
4096  }
4097  }
4098  {
4099  bvect bv1;
4100  bvect bv2;
4101  bvect bv3;
4102  bv1.bit_or(bv2);
4103  if (bv1.any())
4104  {
4105  cerr << "Failed bit_or()" << endl;
4106  exit(1);
4107  }
4108  bv2.set_bit(100000000);
4109  bv1.bit_or(bv2);
4110  if (!bv1.any())
4111  {
4112  cerr << "Failed bit_or()" << endl;
4113  exit(1);
4114  }
4115  bv1.bit_or(bv3);
4116  if (bv1.count()!=1)
4117  {
4118  cerr << "Failed bit_or()" << endl;
4119  exit(1);
4120  }
4121  }
4122 
4123  {
4124  bvect bv1;
4125  bvect bv2;
4126  bv1.bit_and(bv2);
4127  if (bv1.any())
4128  {
4129  cerr << "Failed bit_and()" << endl;
4130  exit(1);
4131  }
4132  bv2.set_bit(100000000);
4133  bv1.bit_and(bv2);
4134  if (bv1.any())
4135  {
4136  cerr << "Failed bit_and()" << endl;
4137  exit(1);
4138  }
4139  bv2.bit_and(bv1);
4140  if (bv2.count()!=0)
4141  {
4142  cerr << "Failed bit_and()" << endl;
4143  exit(1);
4144  }
4145  }
4146 
4147  {
4148  bvect bv1;
4149  bvect::statistics st1;
4150  bv1.optimize(0, bvect::opt_compress, &st1);
4151  if (st1.memory_used == 0)
4152  {
4153  cerr << "Failed calc_stat()" << endl;
4154  exit(1);
4155  }
4156  bv1.optimize_gap_size();
4157  }
4158 
4159  {
4160  bvect bv1;
4161  bvect bv2;
4162 
4163  int r = bv1.compare(bv2);
4164  if (r != 0)
4165  {
4166  cerr << "Failed compare()" << endl;
4167  exit(1);
4168 
4169  }
4170  bv2.set_bit(1000);
4171  r = bv1.compare(bv2);
4172  if (r == 0)
4173  {
4174  cerr << "Failed compare()" << endl;
4175  exit(1);
4176 
4177  }
4178  r = bv2.compare(bv1);
4179  if (r == 0)
4180  {
4181  cerr << "Failed compare()" << endl;
4182  exit(1);
4183  }
4184  }
4185 
4186  {
4187  bvect bv1;
4188  bvect::enumerator en1 = bv1.first();
4189  bvect::enumerator en2 = bv1.get_enumerator(65535);
4190  CompareEnumerators(en1, en2);
4191  if (en1.valid() || en2.valid())
4192  {
4193  cerr << "failed first enumerator" << endl;
4194  exit(1);
4195  }
4196  }
4197 
4198  {
4199  bvect bv1;
4200  bv1.resize(0);
4201 
4202  bv1.invert();
4203  assert(!bv1.any());
4204  assert(bv1.size()==0);
4205  }
4206 
4207  cout << "---------------------------- Empty bvector test OK" << endl;
4208 
4209 }
4210 
4211 
4212 
4213 
4214 static
4216 {
4217  cout << "---------------------------- Basic functinality test" << endl;
4218 
4220 
4221  bvect_mini bvect_min(BITVECT_SIZE);
4222  bvect bvect_full;
4223  bvect bvect_full1;
4224  bvect::rs_index_type bc_arr;
4225  bvect::rs_index_type bc_arr1;
4226 
4227  printf("\nBasic functionality test.\n");
4228 
4229  {
4230  bvect::rs_index_type rs_idx;
4231  for (unsigned i = 0; i < ITERATIONS; ++i)
4232  {
4233  rs_idx.resize(i);
4234  }
4235  }
4236 
4237 
4238  // clear_range with memory de-allocation
4239  {
4240  bvect::statistics st;
4241  bvect bv { 65536, 65538};
4242  bv.calc_stat(&st);
4243  assert(st.bit_blocks == 1);
4244 
4245  bv.clear_range(65536, 65536+65535);
4246  bv.calc_stat(&st);
4247  assert(st.bit_blocks == 0);
4248 
4249  }
4250 
4251 
4252  {
4253  bvect::statistics st;
4254  bvect bv;
4255  bv.init(256, false/* NOT allocate secondary structures*/);
4256  bv.calc_stat(&st);
4257  assert(st.ptr_sub_blocks == 0);
4258  }
4259  {
4260  bvect::statistics st;
4261  bvect bv;
4262  bv.init(256, true/*allocate secondary structures*/);
4263  bv.calc_stat(&st);
4264  assert(st.ptr_sub_blocks == 256);
4265  }
4266 
4267  // filling vectors with regular values
4268 
4269  cout << "test data generation... " << endl;
4270  unsigned i;
4271  for (i = 0; i < ITERATIONS; ++i)
4272  {
4273  bvect_min.set_bit(i);
4274  bvect_full.set_bit(i);
4275 
4276  bvect_full.build_rs_index(&bc_arr);
4277 
4278  bm::id_t pos1, pos2, pos3, pos4, pos5;
4279  auto rf1 = FindRank(bvect_full, i+1, 0, pos1);
4280  auto rf2 = bvect_full.find_rank(i+1, 0, pos2);
4281  auto rf3 = bvect_full.find_rank(i+1, 0, pos3);
4282  auto rf4 = bvect_full.select(i+1, pos4, bc_arr);
4283 
4284  assert(rf1);
4285  assert(rf2);
4286  assert(rf3);
4287  assert(rf4);
4288  if (pos1 != pos2 || pos1 != pos3 || pos1 != pos4)
4289  {
4290  rf2 = bvect_full.find_rank(i+1, 0, pos2);
4291  cerr << "1.Rank check error!\n"
4292  << " pos1 = " << pos1
4293  << " pos2 = " << pos2
4294  << " pos3 = " << pos3
4295  << " pos4 = " << pos4
4296  << endl;
4297  ;
4298  exit(1);
4299  }
4300 
4301  {
4302  bvect bv_opt(bvect_full);
4303  bv_opt.optimize();
4304  bv_opt.build_rs_index(&bc_arr);
4305  auto rf5 = bv_opt.select(i+1, pos5, bc_arr);
4306  assert(rf5);
4307  assert(pos1 == pos5);
4308  }
4309 
4310  }
4311 
4312  bvect_full1.set_range(0, ITERATIONS-1);
4313 
4314  bvect_full1.build_rs_index(&bc_arr1);
4315 
4316  cout << "Rank check 2" << endl;
4317 
4318  for (i = 0; i < ITERATIONS; ++i)
4319  {
4320  bm::id_t pos1, pos2, pos3, pos4;
4321  auto rf1 = FindRank(bvect_full1, i+1, 0, pos1);
4322  auto rf2 = bvect_full1.find_rank(i+1, 0, pos2);
4323  auto rf3 = bvect_full1.find_rank(i+1, 0, pos3);
4324  auto rf4 = bvect_full1.select(i+1, pos4, bc_arr1);
4325  assert(rf1);
4326  assert(rf2);
4327  assert(rf3);
4328  assert(rf4);
4329  if (pos1 != pos2 || pos1 != pos3 || pos1 != pos4)
4330  {
4331  rf2 = bvect_full1.find_rank(i+1, 0, pos2);
4332  cerr << "2.Rank check error!\n"
4333  << " pos1 = " << pos1
4334  << " pos2 = " << pos2
4335  << " pos3 = " << pos3
4336  << " pos4 = " << pos4
4337  << endl;
4338  ;
4339  exit(1);
4340  }
4341  if (i % 1000 == 0)
4342  {
4343  if (!is_silent)
4344  cout << "\r" << i << " / " << ITERATIONS << flush;
4345  }
4346  }
4347  cout << endl;
4348 
4349  bvect::rs_index_type rs_idx_full;
4350  bvect_full.build_rs_index(&rs_idx_full);
4351 
4352  bvect::rs_index_type rs_idx_full1;
4353  bvect_full1.build_rs_index(&rs_idx_full1);
4354 
4355  CheckCountRange(bvect_full, rs_idx_full, 0, ITERATIONS);
4356  CheckCountRange(bvect_full, rs_idx_full, 10, ITERATIONS+10);
4357  CheckCountRange(bvect_full1, rs_idx_full1, 0, ITERATIONS);
4358  CheckCountRange(bvect_full1, rs_idx_full1, ITERATIONS-10, ITERATIONS+10);
4359  CheckCountRange(bvect_full1, rs_idx_full1, 10, ITERATIONS+10);
4360 
4361  if (bvect_full1 != bvect_full)
4362  {
4363  cout << "set_range failed!" << endl;
4364  print_stat(cout,bvect_full1);
4365  exit(1);
4366  }
4367 
4368  print_stat(cout,bvect_full);
4369  print_stat(cout,bvect_full1);
4370 
4371  // checking the results
4372  unsigned count_min = 0;
4373 
4374  for (i = 0; i < ITERATIONS; ++i)
4375  {
4376  if (bvect_min.is_bit_true(i))
4377  ++count_min;
4378  }
4379 
4380  cout << "Rank check 3" << endl;
4381  for (i = 0; i < ITERATIONS; ++i)
4382  {
4383  CheckCountRange(bvect_full, rs_idx_full, i, ITERATIONS);
4384  CheckCountRange(bvect_full1, rs_idx_full1, i, ITERATIONS);
4385  }
4386 
4387  cout << "Rank check 4" << endl;
4388  for (i = ITERATIONS; i > 0; --i)
4389  {
4390  CheckCountRange(bvect_full, rs_idx_full, 0, i);
4391  CheckCountRange(bvect_full1, rs_idx_full1, 0, i);
4392  }
4393 
4394  unsigned count_full = bvect_full.count();
4395 
4396  if (count_min == count_full)
4397  {
4398  printf("simple count test ok.\n");
4399  }
4400  else
4401  {
4402  printf("simple count test failed count_min = %i count_full = %i\n",
4403  count_min, count_full);
4404  exit(1);
4405  }
4406 
4407 
4408  // detailed vectors verification
4409 
4410  CheckVectors(bvect_min, bvect_full, ITERATIONS);
4411 
4412  // now clearning
4413 
4414  for (i = 0; i < ITERATIONS; i+=2)
4415  {
4416  bvect_min.clear_bit(i);
4417  bvect_full.clear_bit(i);
4418  bvect_full1.set_range(i, i, false);
4419  }
4420 
4421  CheckVectors(bvect_min, bvect_full, ITERATIONS);
4422  CheckVectors(bvect_min, bvect_full1, ITERATIONS);
4423 
4424  for (i = 0; i < ITERATIONS; ++i)
4425  {
4426  bvect_min.clear_bit(i);
4427  }
4428  bvect_full.clear();
4429 
4430  CheckVectors(bvect_min, bvect_full, ITERATIONS);
4431 
4432  cout << "Random step filling" << endl;
4433 
4434  for (i = (unsigned)rand()%10; i < ITERATIONS; i+=(unsigned)rand()%10)
4435  {
4436  bvect_min.clear_bit(i);
4437  bvect_full.clear_bit(i);
4438  }
4439 
4440  CheckVectors(bvect_min, bvect_full, ITERATIONS);
4441 
4442  bvect bv1;
4443  bvect bv2;
4444 
4445  bv1[10] = true;
4446  bv1[1000] = true;
4447 
4448  bv2[200] = bv2[700] = bv2[500] = true;
4449 
4450  bv1.swap(bv2);
4451 
4452  if (bv1.count() != 3)
4453  {
4454  cout << "Swap test failed!" << endl;
4455  exit(1);
4456  }
4457 
4458  if (bv2.count() != 2)
4459  {
4460  cout << "Swap test failed!" << endl;
4461  exit(1);
4462  }
4463 
4464  {
4465  //bm::standard_alloc_pool pool;
4467  bvect bv3, bv4;
4468  bv3.set_allocator_pool(&pool);
4469  bv3.set(10, true);
4470  bv4.set(10, true);
4471  bv4.set(10, false);
4472  bv3 &= bv4;
4473  }
4474  {
4475  bvect bv(100);
4476  bv.set_range(150, 151);
4477  assert(bv.size() == 152);
4478  bv.set_bit(160);
4479  assert(bv.size() == 161);
4480  }
4481 }
4482 
4483 
4484 static
4485 void generate_test_vectors(std::vector<bm::id_t> &v1,
4486  std::vector<bm::id_t> &v2,
4487  std::vector<bm::id_t> &v3,
4488  unsigned vector_max)
4489 {
4490  bm::id_t j;
4491  for (j = 0; j < vector_max; j += 2)
4492  v1.push_back(j);
4493  for (j = 0; j < vector_max; j += 5)
4494  v2.push_back(j);
4495  for (j = 0; j < vector_max; j += 120)
4496  v3.push_back(j);
4497 }
4498 
4499 
4500 static
4502 {
4503  cout << "---------------------------- Bvector BULK set test" << endl;
4504 
4505 
4506  {
4507  unsigned ids[] = { 0 };
4508 
4509  bvect bv1, bv2, bv3;
4510  {
4512  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4513  {
4514  bv1.set(ids[i]);
4515  iit = ids[i];
4516  }
4517  }
4518  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4519 
4520  int cmp = bv1.compare(bv2);
4521  assert(cmp==0);
4522  cmp = bv1.compare(bv3);
4523  assert(cmp==0);
4524 
4525  bv2.set(0);
4526  bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
4527  assert(bv2.count()==1);
4528  assert(bv2.test(0));
4529  }
4530 
4531  {
4532  unsigned ids[] = {65535, bm::id_max };
4533  unsigned cnt;
4534  bvect bv2;
4535  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4536 
4537  cnt = bv2.count();
4538  cout << cnt << endl;
4539 
4540  assert(cnt == 1);
4541  assert(bv2.test(ids[0]));
4542  }
4543 
4544  // set bits in FULL vector
4545  {
4546  unsigned ids[] = {0, 10, 65535, bm::id_max-1, bm::id_max };
4547  unsigned cnt;
4548  bvect bv2;
4549  bv2.invert();
4550  struct bvect::statistics st1, st2;
4551  bv2.calc_stat(&st1);
4552 
4553  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4554 
4555  bv2.calc_stat(&st2);
4556  assert(st1.bit_blocks == st2.bit_blocks);
4557  assert(st1.gap_blocks == st2.gap_blocks);
4558 
4559  cnt = bv2.count();
4560  cout << cnt << endl;
4561 
4562  assert(cnt == bm::id_max);
4563  }
4564 
4565  // test correct sizing
4566  {
4567  unsigned ids[] = {65536 };
4568  bvect bv1;
4569  bv1.resize(10);
4570 
4571  bv1.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4572  assert(bv1.size()==65536+1);
4573  bv1.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
4574  cout << bv1.size() << endl;
4575  assert(bv1.size()==65536+1);
4576  }
4577 
4578  {
4579  unsigned ids[] = {65536, 1280000, 65535 };
4580  bvect bv1, bv2;
4581 
4582  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4583  bv1.set(ids[i]);
4584 
4585  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4586  int cmp = bv1.compare(bv2);
4587  assert(cmp==0);
4588 
4589  bv2.keep(&ids[0], sizeof(ids)/sizeof(ids[0]));
4590  cmp = bv1.compare(bv2);
4591  assert(cmp==0);
4592  }
4593 
4594 
4595  {
4596  unsigned ids[] = { 0, 1, 2, 3, 4, 5, 256, 1024, 1028, 256000 };
4597 
4598  bvect bv1, bv2;
4599  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4600  bv1.set(ids[i]);
4601  bv2.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4602 
4603  DetailedCompareBVectors(bv1, bv2);
4604 
4605  int cmp = bv1.compare(bv2);
4606  assert(cmp==0);
4607 
4608  {
4609  bvect bv_inv;
4610  bv_inv.flip();
4611  unsigned keep_cnt = sizeof(ids)/sizeof(ids[0]);
4612  bv_inv.keep(&ids[0], keep_cnt, bm::BM_SORTED);
4613  unsigned cnt_inv2 = bv_inv.count();
4614  assert(cnt_inv2 == keep_cnt);
4615  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4616  {
4617  assert(bv_inv.test(ids[i]));
4618  }
4619  }
4620 
4621  bvect bv3, bv4, bv5;
4622  bv3.invert();
4623  bv4.invert();
4624  bv5.invert();
4625 
4626  {
4628  for (unsigned i = 0; i < sizeof(ids)/sizeof(ids[0]); ++i)
4629  {
4630  bv3.set(ids[i]);
4631  iit = ids[i];
4632  }
4633  }
4634  bv4.set(&ids[0], sizeof(ids)/sizeof(ids[0]));
4635  cmp = bv3.compare(bv4);
4636  assert(cmp==0);
4637  cmp = bv4.compare(bv3);
4638  assert(cmp==0);
4639 
4640  cmp = bv3.compare(bv5);
4641  assert(cmp==0);
4642  }
4643 
4644  {
4645  unsigned vector_max = 4000000;
4646  std::vector<bm::id_t> v1, v2, v3;
4647  generate_test_vectors(v1, v2, v3, vector_max);
4648 
4649  for (unsigned k = 0; k < 2; ++ k)
4650  {
4651  bvect bvu, bvuc;
4652  bvect bv1, bv2, bv3, bv11;
4653  bvect bv1c, bv2c, bv3c;
4654 
4655  {
4656  bvect::bulk_insert_iterator iit(bv11);
4657  for (unsigned i = 0; i < v1.size(); ++i)
4658  {
4659  bv1c.set(v1[i]);
4660  iit = v1[i];
4661  }
4662  iit.flush();
4663  }
4664 
4665  for (unsigned i = 0; i < v2.size(); ++i)
4666  bv2c.set(v2[i]);
4667  for (unsigned i = 0; i < v3.size(); ++i)
4668  bv3c.set(v3[i]);
4669 
4670  // union of 3 vectors
4671  bvuc = bv1c;
4672  bvuc |= bv2c;
4673  bvuc |= bv3c;
4674 
4675  bv1.set(&v1[0], unsigned(v1.size()));
4676  bv2.set(&v2[0], unsigned(v2.size()));
4677  bv3.set(&v3[0], unsigned(v3.size()));
4678 
4679  // imported union of 3 vectors
4680  bvu.set(&v1[0], unsigned(v1.size()));
4681  bvu.set(&v2[0], unsigned(v2.size()));
4682  bvu.set(&v3[0], unsigned(v3.size()));
4683 
4684  cout << bv1.count() << " " << bv1c.count() << endl;
4685 
4686  int cmp;
4687  cmp = bv1c.compare(bv1);
4688  if (cmp != 0)
4689  {
4690  DetailedCompareBVectors(bv1, bv1c);
4691  }
4692  assert(cmp==0);
4693  cmp = bv2c.compare(bv2);
4694  assert(cmp==0);
4695  cmp = bv3c.compare(bv3);
4696  assert(cmp==0);
4697  cmp = bv1.compare(bv11);
4698  assert(cmp==0);
4699 
4700  cmp = bvuc.compare(bvu);
4701  assert(cmp == 0);
4702 
4703  {
4704  std::random_device rd;
4705  std::mt19937 g(rd());
4706 
4707  std::shuffle(v1.begin(), v1.end(), g);
4708  std::shuffle(v2.begin(), v2.end(), g);
4709  std::shuffle(v3.begin(), v3.end(), g);
4710  }
4711  }
4712 
4713 
4714  }
4715 
4716  cout << "Bulk bvector<>::set() stress.." << endl;
4717  {
4718  unsigned vector_max =40000000;
4719  unsigned delta_max = 65537;
4720 
4721  bvect bv1, bv2;
4722  bvect bv1c;
4723  std::vector<bm::id_t> v1;
4724 
4725  for (unsigned delta = 1; delta < delta_max; ++delta)
4726  {
4727  v1.resize(0);
4728  bvect::bulk_insert_iterator iit(bv2);
4729  for (unsigned i = 0; i < vector_max; i+=delta)
4730  {
4731  v1.push_back(i);
4732  iit = i;
4733  }
4734  iit.flush();
4735 
4736  bv1.set(&v1[0], unsigned(v1.size()));
4737  bm::combine_or(bv1c, v1.begin(), v1.end());
4738 
4739  int cmp = bv1.compare(bv1c);
4740  if (cmp!=0)
4741  {
4742  cerr << "1.Failed bulk set test at delta=" << delta << endl;
4743  exit(1);
4744  }
4745  cmp = bv1.compare(bv2);
4746  if (cmp!=0)
4747  {
4748  cerr << "2.Failed bulk set test at delta=" << delta << endl;
4749  exit(1);
4750  }
4751 
4752  // test AND/keep
4753  {
4754  bvect bv3(bv1);
4755  bvect bv4;
4756  bv3.keep(&v1[0], unsigned(v1.size()));
4757  bv4.set(&v1[0], unsigned(v1.size()));
4758  cmp = bv3.compare(bv4);
4759  if (cmp!=0)
4760  {
4761  cerr << "3.Failed keep() test at delta=" << delta << endl;
4762  exit(1);
4763  }
4764  if (v1.size())
4765  {
4766  bv3.keep(&v1[0], 1);
4767  assert(bv3.count()==1);
4768  assert(bv3.test(v1[0]));
4769  }
4770  }
4771 
4772  bv1.clear();
4773  bv1c.clear();
4774  bv2.clear();
4775 
4776  if (delta % 256 == 0)
4777  {
4778  if (!is_silent)
4779  cout << "\r" << delta << "/" << delta_max << flush;
4780  }
4781 
4782  } // for delta
4783  cout << endl;
4784  }
4785 
4786 
4787  cout << "---------------------------- Bvector BULK set test OK\n" << endl;
4788 }
4789 
4790 
4791 
4792 static
4794 {
4795  cout << "---------------------------- Find Rank test" << endl;
4796 
4797  {
4798  bvect bv1;
4799  bv1[30] = true;
4800  bv1[65534] = true;
4801 
4802  bvect::rs_index_type bc_arr1;
4803  bv1.build_rs_index(&bc_arr1);
4804 
4805  bool rf1, rf2, rf3;
4806  bm::id_t pos, pos1;
4807  rf1 = bv1.find_rank(1, 20, pos);
4808  rf3 = bv1.find_rank(1, 20, pos1, bc_arr1);
4809  assert(rf1);
4810  assert(rf3);
4811  assert(pos == 30);
4812  assert(pos1 == 30);
4813 
4814  rf2 = bv1.find_rank(2, 30, pos);
4815  rf3 = bv1.find_rank(2, 30, pos1, bc_arr1);
4816  assert(rf2);
4817  assert(rf3);
4818  assert(pos == 65534);
4819  assert(pos1 == 65534);
4820  }
4821 
4822 
4823  cout << "Test bvector<>::select()" << endl;
4824  {
4825  bvect::size_type r(65536*256-1), pos;
4826 
4827  bvect bv;
4828  bv.set_range(0, r);
4829  bv.optimize();
4830 
4831  bvect::rs_index_type rs_idx;
4832  bv.build_rs_index(&rs_idx);
4833 
4834  struct bvect::statistics st;
4835  bv.calc_stat(&st);
4836  assert(st.bit_blocks == 0);
4837  assert(st.gap_blocks == 0);
4838 
4840  for (i = 0; i <=r; ++i)
4841  {
4842  bvect::size_type ri = bv.rank(i, rs_idx);
4843  assert(ri == (i+1));
4844  bool f = bv.select(ri, pos, rs_idx);
4845  assert(f);
4846  assert(pos == i);
4847  }
4848  bool f = bv.select(i+1, pos, rs_idx);
4849  assert(!f);
4850  }
4851 
4852  cout << "Find Rank test stress 1\n" << endl;
4853 
4854  {
4855  const unsigned max_size = 2000000;
4856  bvect bv1;
4857  for (unsigned i = 0; i < max_size;)
4858  {
4859  bv1.set(i);
4860  i += (unsigned)rand()%5;
4861  }
4862  bvect::rs_index_type bc_arr1;
4863  bv1.build_rs_index(&bc_arr1);
4864 
4865 
4866  for (unsigned i = 0; i < max_size; ++i)
4867  {
4868  bool rf1, rf3;
4869  bm::id_t pos, pos1;
4870 
4871  rf1 = bv1.find_rank(0, i, pos);
4872  rf3 = bv1.find_rank(0, i, pos1, bc_arr1);
4873  assert (rf1 == rf3);
4874  if (rf1)
4875  {
4876  if (pos != pos1)
4877  {
4878  cerr << "Rank cmp test failed! i=" << i
4879  << " pos=" << pos
4880  << " pos1=" << pos1
4881  << endl;
4882  exit(1);
4883  }
4884  }
4885 
4886  rf1 = bv1.find_rank(i, max_size-i, pos);
4887  rf3 = bv1.find_rank(i, max_size-i, pos1, bc_arr1);
4888  assert (rf1 == rf3);
4889  if (rf1)
4890  {
4891  if (pos != pos1)
4892  {
4893  cerr << "Rank cmp test failed! i=" << i
4894  << " pos=" << pos
4895  << " pos1=" << pos1
4896  << endl;
4897  exit(1);
4898  }
4899  }
4900  if (i % 100 == 0)
4901  if (!is_silent)
4902  cout << "\r" << i << "/" << max_size << flush;
4903  } // for
4904  cout << endl;
4905  }
4906 
4907  cout << "---------------------------- Find Rank test OK" << endl;
4908 }
4909 
4910 static
4912 {
4913  cout << "---------------------------- Bvector inc test" << endl;
4914 
4915  {
4916  bvect bv1;
4917  bool b;
4918 
4919  b = bv1.inc(0);
4920  assert(!b);
4921  b = bv1.inc(0);
4922  assert(b);
4923 
4924  b = bv1.inc(10);
4925  assert(!b);
4926  b = bv1.inc(10);
4927  assert(b);
4928  }
4929 
4930  {
4931  bvect bv1(BM_GAP);
4932  bool b;
4933 
4934  assert(bv1.count()==0);
4935 
4936  b = bv1.inc(0);
4937  assert(!b);
4938  cout << bv1.count() << endl;
4939  assert(bv1.count()==1);
4940  b = bv1.inc(0);
4941  assert(b);
4942  assert(bv1.count()==0);
4943 
4944  b = bv1.inc(10);
4945  assert(!b);
4946  b = bv1.inc(10);
4947  assert(b);
4948  }
4949 
4950  {
4951  bvect bv1(BM_GAP);
4952  bool b;
4953 
4954  bv1.flip();
4955 
4956  b = bv1.inc(0);
4957  assert(b);
4958  b = bv1.inc(0);
4959  assert(!b);
4960 
4961  b = bv1.inc(10);
4962  assert(b);
4963  b = bv1.inc(10);
4964  assert(!b);
4965  }
4966 
4967  cout << "---------------------------- Bvector inc test OK" << endl;
4968 }
4969 
4970 // -----------------------------------------------------------------------
4971 
4972 static
4973 void optimize_fill(bvect& bv, bvect::size_type base, unsigned inc,
4975  bool value = true)
4976 {
4977  for (bvect::size_type i = 0; i < bm::set_sub_array_size; ++i)
4978  {
4979  bvect::size_type base_idx = i * bm::gap_max_bits;
4980  for (bvect::size_type j = base; j < max_bits; j += inc)
4981  {
4982  bv.set(base_idx + j, value);
4983  } // for j
4984  } // for i
4985 }
4986 
4987 static
4989 {
4990  cout << "---------------------------- Bvector Optimize test" << endl;
4992 
4993  {
4994  bvect bv;
4995  optimize_fill(bv, 0, 1, bm::gap_max_bits, true);
4996 
4997  bvect::statistics st1;
4998  bv.calc_stat(&st1);
4999 
5001  assert(st1.gap_blocks == 0);
5002  assert(st1.ptr_sub_blocks == 1);
5003 
5004  bv.optimize(tb, bvect::opt_compress, &st1);
5005 
5006  assert(st1.bit_blocks == 0);
5007  assert(st1.gap_blocks == 0);
5008  assert(st1.ptr_sub_blocks == 0);
5009 
5010  bv.calc_stat(&st1);
5011 
5012  assert(st1.bit_blocks == 0);
5013  assert(st1.gap_blocks == 0);
5014  assert(st1.ptr_sub_blocks == 0);
5015  }
5016 
5017  {
5018  bvect::statistics st;
5019  bvect bv;
5020  bv.set(10);
5021  bv.set(65536);
5022  bv.optimize_range(0, 0, tb, bvect::opt_compress);
5023  bv.calc_stat(&st);
5024  assert(st.bit_blocks == 1);
5025  assert(st.gap_blocks == 1);
5027  bv.calc_stat(&st);
5028  assert(st.bit_blocks == 0);
5029  assert(st.gap_blocks == 2);
5030  }
5031 
5032 
5033  {
5034  bvect::statistics st;
5035 
5036  bvect bv;
5037  bv.optimize_range(0, 0, tb, bvect::opt_compress);
5038  bv.invert();
5039 
5040  bv.optimize_range(0, 65536, tb, bvect::opt_compress);
5041  bv.calc_stat(&st);
5042  assert(st.bit_blocks == 1);
5043  assert(st.gap_blocks == 0);
5044 
5045  bv.optimize_range(65536, bm::id_max-1, tb, bvect::opt_compress);
5046  bv.calc_stat(&st);
5047  assert(st.bit_blocks == 0);
5048  assert(st.gap_blocks == 1);
5049 
5050  }
5051 
5052 
5053  {
5054  bvect bv;
5055  optimize_fill(bv, 0, 100, bm::gap_max_bits, true);
5056  optimize_fill(bv, 0, 100, bm::gap_max_bits, false);
5057 
5058  bvect::statistics st1;
5059  bv.calc_stat(&st1);
5060 
5062  assert(st1.gap_blocks == 0);
5063  assert(st1.ptr_sub_blocks == 1);
5064 
5065  bv.optimize(tb, bvect::opt_compress, &st1);
5066 
5067  assert(st1.bit_blocks == 0);
5068  assert(st1.gap_blocks == 0);
5069  assert(st1.ptr_sub_blocks == 0);
5070  }
5071 
5072 
5073  {
5074  bvect bv(BM_GAP);
5075  optimize_fill(bv, 0, 1, bm::gap_max_bits, true);
5076 
5077  bvect::statistics st1;
5078  bv.calc_stat(&st1);
5079 
5080  assert(st1.bit_blocks == 0);
5082  assert(st1.ptr_sub_blocks == 1);
5083 
5084  bv.optimize(tb, bvect::opt_compress, &st1);
5085 
5086  assert(st1.bit_blocks == 0);
5087  assert(st1.gap_blocks == 0);
5088  assert(st1.ptr_sub_blocks == 0);
5089 
5090  bv.calc_stat(&st1);
5091 
5092  assert(st1.bit_blocks == 0);
5093  assert(st1.gap_blocks == 0);
5094  assert(st1.ptr_sub_blocks == 0);
5095  }
5096 
5097  {
5098  bvect bv(BM_GAP);
5099  optimize_fill(bv, 0, 1000, bm::gap_max_bits, true);
5100  optimize_fill(bv, 0, 1000, bm::gap_max_bits, false);
5101 
5102  bvect::statistics st1;
5103  bv.calc_stat(&st1);
5104 
5105  assert(st1.bit_blocks == 0);
5107  assert(st1.gaps_by_level[0] == 0);
5109  assert(st1.ptr_sub_blocks == 1);
5110 
5111  bv.optimize(tb, bvect::opt_compress, &st1);
5112 
5113  assert(st1.bit_blocks == 0);
5114  assert(st1.gap_blocks == 0);
5115  assert(st1.ptr_sub_blocks == 0);
5116  }
5117 
5118  {
5119  bvect bv(BM_GAP);
5120  optimize_fill(bv, 0, 1000, bm::gap_max_bits, true);
5121  optimize_fill(bv, 1, 1, bm::gap_max_bits, false);
5122 
5123  bvect::statistics st1;
5124  bv.calc_stat(&st1);
5125 
5126  assert(st1.bit_blocks == 0);
5128  assert(st1.gaps_by_level[0] == 0);
5130  assert(st1.ptr_sub_blocks == 1);
5131 
5132  bv.optimize(tb, bvect::opt_compress, &st1);
5133 
5134  assert(st1.bit_blocks == 0);
5136  assert(st1.ptr_sub_blocks == 1);
5138  assert(st1.gaps_by_level[1] == 0);
5139  }
5140 
5141 
5142  cout << "---------------------------- Bvector Optimize test OK" << endl;
5143 }
5144 
5145 
5146 // -----------------------------------------------------------------------
5147 
5148 static
5150  unsigned min = 0,
5151  unsigned max = 40000000,
5152  unsigned fill_factor = 65536)
5153 {
5155  unsigned ff = fill_factor / 10;
5156  for (unsigned i = min; i < max; i+= ff)
5157  {
5158  //bv.set(i);
5159  iit = i;
5160  ff += ff / 2;
5161  if (ff > fill_factor)
5162  ff = fill_factor / 10;
5163  }
5164  iit.flush();
5165 }
5166 
5167 
5168 static
5169 void GenerateShiftTestCollection(std::vector<bvect>* target,
5170  unsigned count = 30,
5171  unsigned vector_max = 40000000,
5172  bool optimize = true)
5173 {
5174  assert(target);
5175  bvect bv_common; // sub-vector common for all collection
5176  generate_sparse_bvector(bv_common, vector_max/10, vector_max, 250000);
5177 
5178  unsigned cnt1 = (count / 2);
5179 
5180  unsigned i = 0;
5181 
5182  for (i = 0; i < cnt1; ++i)
5183  {
5184  std::unique_ptr<bvect> bv (new bvect);
5185  generate_bvector(*bv, vector_max, optimize);
5186  *bv |= bv_common;
5187  if (optimize)
5188  bv->optimize();
5189  target->push_back(std::move(*bv));
5190  } // for
5191 
5192  unsigned fill_factor = 10;
5193  for (; i < count; ++i)
5194  {
5195  std::unique_ptr<bvect> bv (new bvect);
5196 
5197  FillSetsIntervals(0, *bv, vector_max/ 10, vector_max, fill_factor);
5198  *bv |= bv_common;
5199 
5200  target->push_back(std::move(*bv));
5201  } // for
5202 }
5203 
5204 
5205 
5206 static
5208 {
5209  cout << "---------------------------- Bvector SHIFT test" << endl;
5210 
5211 
5212  {
5213  bvect bv;
5214 
5215  bv.set(bm::id_max-1);
5216  bv.shift_right();
5217  print_bv(bv);
5218  assert(bv.count()==0);
5219  }
5220 
5221  {
5222  bvect bv(BM_GAP);
5223 
5224  bv.set(bm::id_max-1);
5225  bv.optimize();
5226  bv.shift_right();
5227  assert(bv.count()==0);
5228  }
5229 
5230  {
5231  bvect bv;
5232 
5233  bv.set();
5234  auto cnt1 = bv.count();
5235  bv.shift_right();
5236  auto cnt2 = bv.count();
5237  assert(cnt1-1 == cnt2);
5238  bool b = bv.test(0);
5239  assert(!b);
5240  }
5241  {
5242  bvect bv;
5243  bv.set();
5245 
5246  auto cnt1 = bv.count();
5247  bv.shift_left();
5248  auto cnt2 = bv.count();
5249  assert(cnt1-1 == cnt2);
5250  bool b = bv.test(bm::id_max-1);
5251  assert(!b);
5252  b = bv.test(bm::id_max-2);
5253  assert(b);
5255  assert(b);
5257  assert(!b);
5258  }
5259 
5260  {
5261  bvect bv;
5262 
5263  bv.set();
5264  auto cnt1 = bv.count();
5265  bv.shift_left();
5266  auto cnt2 = bv.count();
5267  assert(cnt1-1 == cnt2);
5268  bool b = bv.test(bm::id_max-1);
5269  assert(!b);
5270  }
5271 
5272 
5273 
5274  {
5275  bvect bv;
5276 
5277  bv.set(0);
5278  bv.set(65535);
5279  bv.set(bm::id_max-1);
5280  bvect bv1(bv);
5281 
5282  bvect bv2(bm::BM_GAP);
5283  bv2 = bv;
5284  bv2.optimize();
5285 
5286  ShiftRight(&bv, 1);
5287  assert(bv.count() == 2);
5288  assert(bv.test(1));
5289  assert(bv.test(65536));
5290 
5291  bv1.shift_right();
5292  print_bv(bv1);
5293  int cmp = bv.compare(bv1);
5294  assert(cmp == 0);
5295 
5296  bv2.shift_right();
5297  print_bv(bv2);
5298  cmp = bv.compare(bv2);
5299  assert(cmp == 0);
5300  struct bvect::statistics st;
5301  bv2.calc_stat(&st);
5302  assert(st.gap_blocks >= 2);
5303 
5304  }
5305 
5306  {
5307  bvect bv(BM_GAP);
5308  struct bvect::statistics st;
5309 
5310  for (unsigned i = 0; i < 65536; ++i)
5311  {
5312  bv.set(i);
5313  }
5314  bv.calc_stat(&st);
5315  assert(st.gap_blocks == 1);
5316 
5317  auto cnt = bv.count();
5318  bv.shift_right();
5319  assert(bv.test(0)==0);
5320  assert(bv.count() == cnt);
5321 
5322  bv.calc_stat(&st);
5323  auto bcnt = st.bit_blocks + st.gap_blocks;
5324  assert(bcnt == 2);
5325  assert(st.gap_blocks);
5326  for (unsigned i = 0+1; i < 65536+1; ++i)
5327  {
5328  assert(bv.test(i));
5329  }
5330  }
5331 
5332 
5333  {
5334  cout << " inverted test" << endl;
5335  bvect bv;
5336  bv.invert();
5337  unsigned cnt = bv.count();
5338  bool carry_over = bv.shift_right();
5339  assert(carry_over);
5340  unsigned cnt1 = bv.count();
5341  assert(cnt1 == cnt - 1);
5342  assert(bv.test(0)==0);
5343  assert(bv.test(1)==1);
5344 
5345  struct bvect::statistics st;
5346  bv.calc_stat(&st);
5347  auto bcnt = st.bit_blocks + st.gap_blocks;
5348  assert(bcnt == 2);
5349 
5350  }
5351 
5352  {
5353  cout << " 3-bit optimized test" << endl;
5354  bvect bv;
5355 
5356  bv.set(0);
5357  bv.set(65535);
5358  bv.set(66000);
5359  bv.optimize();
5360  bvect bv1(bv);
5361  ShiftRight(&bv, 1);
5362  bv1.shift_right();
5363  int cmp = bv.compare(bv1);
5364 
5365  assert(cmp == 0);
5366  }
5367 
5368 
5369  {
5370  cout << " carry-over test" << endl;
5371  bvect bv { 1 };
5372  bool carry_over = bv.shift_left();
5373  assert(!carry_over);
5374  unsigned idx = bv.get_first();
5375  assert(idx == 0);
5376  carry_over = bv.shift_left();
5377  assert(carry_over);
5378  idx = bv.get_first();
5379  std::cout << idx << endl;
5380  assert(idx == 0);
5381  assert(bv.count()==0);
5382  }
5383 
5384  {
5385  cout << " 4278190080 test" << endl;
5386 
5387  bvect bv { 4278190080 };
5388  bv.shift_left();
5389  unsigned idx = bv.get_first();
5390  assert(idx == 4278190080-1);
5391  bv.shift_left();
5392  idx = bv.get_first();
5393  assert(idx == 4278190080-2);
5394  }
5395 
5396  {
5397  cout << " 4278190080 (optimized) test" << endl;
5398  bvect bv { 4278190080 };
5399  bv.optimize();
5400  bv.shift_left();
5401  unsigned idx = bv.get_first();
5402  assert(idx == 4278190080-1);
5403  bv.shift_left();
5404  idx = bv.get_first();
5405  assert(idx == 4278190080-2);
5406  }
5407 
5408  {
5409  std::cout << "\nShift-L stress (1 bit shift)..\n" << endl;;
5410  unsigned start = bm::id_max-1;
5411  bvect bv;
5412  bv.set(start);
5413 
5414  struct bvect::statistics st;
5415  bv.calc_stat(&st);
5416  auto bcnt = st.bit_blocks + st.gap_blocks;
5417  assert(bcnt == 1);
5418 
5419  std::chrono::time_point<std::chrono::steady_clock> s;
5420  std::chrono::time_point<std::chrono::steady_clock> f;
5421 
5422  s = std::chrono::steady_clock::now();
5423 
5424  for( ; start; --start)
5425  {
5426  bool carry_over = bv.shift_left();
5427  if (carry_over)
5428  {
5429  cout << "CO at " << start << endl;
5430  assert(bv.count()==0);
5431  assert(start == bm::id_max-1);
5432  break;
5433  }
5434  /*
5435  unsigned idx = bv.get_first();
5436  if(idx != start-1)
5437  {
5438  cerr << bv.count() << endl;
5439  cerr << "Shift-L Failed at idx=" << idx << " != " << start << endl;
5440  exit(1);
5441  }
5442  */
5443 
5444  if ((start % (1024 * 1024)) == 0)
5445  {
5446  f = std::chrono::steady_clock::now();
5447  auto diff = f - s;
5448  auto d = std::chrono::duration <double, std::milli> (diff).count();
5449  cout << "\r" << start << " (" << d << ") " << flush;
5450 
5451  unsigned idx = bv.get_first();
5452  assert(idx == start-1);
5453 
5454  bv.optimize();
5455 
5456  bv.calc_stat(&st);
5457  bcnt = st.bit_blocks + st.gap_blocks;
5458  assert(bcnt == 1);
5459 
5460  s = std::chrono::steady_clock::now();
5461  }
5462  }
5463  cout << "ok.\n";
5464  }
5465 
5466  {
5467  std::cout << "\nShift-R stress (1 bit shift)..\n" << endl;
5468  unsigned start = 0;
5469  bvect bv, bv1(BM_GAP);
5470  bv.set(start);
5471  bv1.set(start);
5472 
5473  struct bvect::statistics st;
5474  bv.calc_stat(&st);
5475  auto bcnt = st.bit_blocks + st.gap_blocks;
5476  assert(bcnt == 1);
5477 
5478  std::chrono::time_point<std::chrono::steady_clock> s;
5479  std::chrono::time_point<std::chrono::steady_clock> f;
5480 
5481  s = std::chrono::steady_clock::now();
5482 
5483  while(1)
5484  {
5485  bool carry_over = bv.shift_right();
5486  if (carry_over)
5487  {
5488  cout << "CO at " << start << endl;
5489  assert(bv.count()==0);
5490  assert(start == bm::id_max-1);
5491  break;
5492  }
5493 
5494  {
5495  bv.calc_stat(&st);
5496  bcnt = st.bit_blocks + st.gap_blocks;
5497  assert(bcnt == 1);
5498  }
5499  carry_over = bv1.shift_right();
5500  if (carry_over)
5501  {
5502  cout << "CO at " << start << endl;
5503  assert(bv1.count()==0);
5504  assert(start == bm::id_max-1);
5505  break;
5506  }
5507  // optmization of GAP blocks is not implemented yet
5508  #if 0
5509  {
5510  bv1.calc_stat(&st);
5511  bcnt = st.bit_blocks + st.gap_blocks;
5512  assert(bcnt == 1);
5513  }
5514  #endif
5515 
5516 
5517  if ((start % (1024 * 1024)) == 0)
5518  {
5519  bool eq = bv.equal(bv1);
5520  assert(eq);
5521 
5522  bv1.optimize();
5523 
5524  f = std::chrono::steady_clock::now();
5525  auto diff = f - s;
5526  auto d = std::chrono::duration <double, std::milli> (diff).count();
5527 
5528  cout << "\r" << start << " (" << d << ") " << flush;
5529 
5530  unsigned idx = bv.get_first();
5531  assert(idx-1 == start);
5532 
5533  bv.calc_stat(&st);
5534  bcnt = st.bit_blocks + st.gap_blocks;
5535  assert(bcnt == 1);
5536 
5537  s = std::chrono::steady_clock::now();
5538  }
5539  ++start;
5540  }
5541  cout << "ok.\n";
5542  }
5543 
5544  {
5545  std::cout << "\nShift-R stress (large vector shift)..\n" << endl;
5546  bvect bv;
5547  generate_bvector(bv);
5548  bvect bv_control(bv);
5549 
5550  unsigned max_shifts = 10000;
5551  for (unsigned i = 0; i < max_shifts; ++i)
5552  {
5553  ShiftRight(&bv_control, 1);
5554  bv.shift_right();
5555  int cmp = bv.compare(bv_control);
5556  assert(cmp==0);
5557  if ((i % 16) == 0)
5558  {
5559  if (!is_silent)
5560  cout << "\r" << i << "/" << max_shifts << flush;
5561  }
5562  }
5563  }
5564  cout << "ok.\n";
5565 
5566 
5567  // stress test for shifting aggregator
5568  //
5569  cout << "\nAggregator based SHIT-R tests..." << endl;
5570  {
5571  const unsigned int REPEATS = 300;
5572 
5573  bvect mask_bv; // mask vector
5574  mask_bv.init();
5575  generate_bvector(mask_bv, 75000000, false); // mask is shorter on both ends
5576 
5577  std::vector<bvect> bv_coll1;
5578  GenerateShiftTestCollection(&bv_coll1, 25, 80000000);
5579 
5580  {
5582  agg.add(&mask_bv);
5583  for (unsigned k = 0; k < bv_coll1.size(); ++k)
5584  {
5585  agg.add(&bv_coll1[k]);
5586  }
5587 
5588  for (unsigned i = 0; i < REPEATS; ++i)
5589  {
5590  bvect bv1(mask_bv);
5591  for (unsigned k = 0; k < bv_coll1.size(); ++k)
5592  {
5593  bv1.shift_right();
5594  bv1 &= bv_coll1[k];
5595  } // for
5596 
5597  bvect bv2;
5598  agg.set_compute_count(false);
5599  agg.combine_shift_right_and(bv2);
5600  int cmp = bv1.compare(bv2);
5601  if (cmp != 0)
5602  {
5603  cerr << "Shift-R compare failure!" << endl;
5604  exit(1);
5605  }
5606  bvect bv3;
5607  agg.set_compute_count(true);
5608  agg.combine_shift_right_and(bv3);
5609  assert(!bv3.any());
5610  auto cnt = agg.count();
5611  auto cnt_c = bv1.count();
5612  assert(cnt == cnt_c);
5613 
5614  } // for
5615  }
5616  }
5617 
5618 
5619  cout << "\n---------------------------- Bvector SHIFT test OK" << endl;
5620 }
5621 
5622 static
5624 {
5625  cout << "\n---------------------------- Bvector INSERT test" << endl;
5626 
5627  {
5628  bvect bv { 1, 2, 3 };
5629  bvect bv_c { 2, 3, 4 };
5630  bvect bv1(bv);
5631  bvect bv2(bv); bv2.optimize();
5632 
5633  BVectorInsert(&bv, 0, false);
5634  int cmp = bv.compare(bv_c);
5635  assert(cmp == 0);
5636 
5637  bv1.insert(0, false);
5638  cmp = bv1.compare(bv_c);
5639  assert(cmp == 0);
5640 
5641  bv2.insert(0, false);
5642  cmp = bv2.compare(bv_c);
5643  assert(cmp == 0);
5644 
5645  struct bvect::statistics st2;
5646  bv2.calc_stat(&st2);
5647  assert(st2.gap_blocks==1);
5648  assert(st2.bit_blocks==0);
5649  }
5650 
5651  {
5652  bvect bv { 1, 2, 3 };
5653  bvect bv_c { 0, 2, 3, 4 };
5654  bvect bv1(bv);
5655  bvect bv2(bv); bv2.optimize();
5656 
5657  BVectorInsert(&bv, 0, true);
5658  int cmp = bv.compare(bv_c);
5659  assert(cmp == 0);
5660 
5661  bv1.insert(0, true);
5662  cmp = bv1.compare(bv_c);
5663  assert(cmp == 0);
5664 
5665  bv2.insert(0, true);
5666 // print_bv(bv2);
5667 // print_bv(bv_c);
5668  cmp = bv2.compare(bv_c);
5669  assert(cmp == 0);
5670 
5671  struct bvect::statistics st2;
5672  bv2.calc_stat(&st2);
5673  assert(st2.gap_blocks==1);
5674  assert(st2.bit_blocks==0);
5675  }
5676 
5677  {
5678  bvect bv;
5679  bv.set_range(0, 65535);
5680  bv.optimize();
5681  bvect bv_c;
5682  bv_c.set_range(0, 65536);
5683 
5684  bv.insert(1, true);
5685  int cmp = bv.compare(bv_c);
5686  assert(cmp == 0);
5687 
5688  struct bvect::statistics st;
5689  bv.calc_stat(&st);
5690  assert(st.gap_blocks==0);
5691  assert(st.bit_blocks==1);
5692 
5693  }
5694 
5695  {
5696  bvect bv { 1, 20, 65535 };
5697  bvect bv_c { 1, 20, 65535, 65536 };
5698  bvect bv1(bv);
5699  bvect bv2(bv); bv2.optimize();
5700 
5701  BVectorInsert(&bv, 65535, true);
5702  int cmp = bv.compare(bv_c);
5703  assert(cmp == 0);
5704 
5705  bv1.insert(65535, true);
5706  print_bv(bv1);
5707  cmp = bv1.compare(bv_c);
5708  assert(cmp == 0);
5709 
5710  bv2.insert(65535, true);
5711  cmp = bv2.compare(bv_c);
5712  assert(cmp == 0);
5713 
5714  struct bvect::statistics st2;
5715  bv2.calc_stat(&st2);
5716  assert(st2.gap_blocks==1);
5717  assert(st2.bit_blocks==1);
5718 
5719  }
5720 
5721  // bit-vector insert checks
5722  {
5723  bvect bv;
5724  bv.resize(10);
5725  bv.insert(120303030, true);
5726  assert(bv.test(120303030));
5727  assert(bv.count()==1);
5728  assert(bv.size() == 120303030+1);
5729  }
5730 
5731  {
5732  bvect bv { 120303030u, 120303031u };
5733  bvect bv1(bv);
5734  BVectorInsert(&bv, 120303031u, true);
5735  bv1.insert(120303031u, true);
5736  int cmp = bv1.compare(bv);
5737  assert(cmp==0);
5738  bv.optimize();
5739  bv1.optimize();
5740  BVectorInsert(&bv, 120303031u, true);
5741  bv1.insert(120303031u, true);
5742  cmp = bv1.compare(bv);
5743  assert(cmp==0);
5744  }
5745 
5746  {
5747  bvect bv, bv1;
5748  bv.set(10);
5749  bv.set_range(1203030u, 1203030u+65535u*10u);
5750  bv1 = bv;
5751  BVectorInsert(&bv, 1203030u+10, false);
5752  bv1.insert(1203030u+10, false);
5753  int cmp = bv1.compare(bv);
5754  assert(cmp==0);
5755  }
5756 
5757  {
5758  std::cout << "INSERT GAP (random)..\n";
5759 
5760  bvect bv(BM_GAP), bv1;
5761  bv.set(10);
5762  bv1 = bv;
5763  bv.optimize();
5764 
5765  for (unsigned i = 0; i < 1000; ++i)
5766  {
5767  unsigned idx = (unsigned)rand() % 65535;
5768  unsigned val = (unsigned)rand() & 1;
5769  bv.insert(idx, val);
5770  bv1.insert(idx, val);
5771  int cmp = bv1.compare(bv);
5772  assert(cmp==0);
5773 
5774  struct bvect::statistics st;
5775  bv.calc_stat(&st);
5776  assert(st.gap_blocks >= 1);
5777  assert(st.bit_blocks == 0);
5778 
5779  bv.insert(idx, val);
5780  bv1.insert(idx, val);
5781  cmp = bv1.compare(bv);
5782  assert(cmp==0);
5783 
5784  bv.calc_stat(&st);
5785  assert(st.gap_blocks >= 1);
5786  assert(st.bit_blocks == 0);
5787  }
5788  }
5789 
5790 
5791  {
5792  std::cout << "INSERT stress (large vector insert)..\n";
5793  bvect bv;
5794  generate_bvector(bv, 40000000);
5795  bvect bv_control(bv);
5796 
5797  unsigned max_shifts = 10000;
5798  for (unsigned i = 0; i < max_shifts; ++i)
5799  {
5800  bvect bv2(bm::BM_GAP);
5801  bv2 = bv_control;
5802  bv2.optimize();
5803 
5804  unsigned i_pos = (unsigned)rand()%40000000;
5805 
5806  BVectorInsert(&bv_control, i_pos, i & 1u);
5807  bv.insert(i_pos, i & 1u);
5808  int cmp = bv.compare(bv_control);
5809  if (cmp != 0)
5810  {
5811  DetailedCompareBVectors(bv, bv_control);
5812  }
5813  assert(cmp==0);
5814 
5815  bv2.insert(i_pos, i & 1u);
5816  cmp = bv2.compare(bv_control);
5817  assert(cmp==0);
5818 
5819  if ((i % 16) == 0)
5820  {
5821  if (!is_silent)
5822  cout << "\r" << i << "/" << max_shifts << flush;
5823  }
5824  } // for i
5825  }
5826  cout << "ok.\n";
5827 
5828 
5829  cout << "---------------------------- Bvector INSERT test OK" << endl;
5830 }
5831 
5832 static