BitMagic-C++
bmaggregator.h
Go to the documentation of this file.
1 #ifndef BMAGGREGATOR__H__INCLUDED__
2 #define BMAGGREGATOR__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmaggregator.h
22  \brief Algorithms for fast aggregation of N bvectors
23 */
24 
25 
26 #ifndef BM__H__INCLUDED__
27 // BitMagic utility headers do not include main "bm.h" declaration
28 // #include "bm.h" or "bm64.h" explicitly
29 # error missing include (bm.h or bm64.h)
30 #endif
31 
32 
33 #include "bmfunc.h"
34 #include "bmdef.h"
35 
36 #include "bmalgo_impl.h"
37 
38 
39 namespace bm
40 {
41 
42 
43 /**
44  Algorithms for fast aggregation of a group of bit-vectors
45 
46  Current implementation can aggregate up to max_aggregator_cap vectors
47  (TODO: remove this limitation)
48 
49  Algorithms of this class use cache locality optimizations and efficient
50  on cases, wehen we need to apply the same logical operation (aggregate)
51  more than 2x vectors.
52 
53  TARGET = BV1 or BV2 or BV3 or BV4 ...
54 
55  @ingroup setalgo
56 */
57 template<typename BV>
59 {
60 public:
61  typedef BV bvector_type;
62  typedef typename BV::size_type size_type;
63  typedef const bvector_type* bvector_type_const_ptr;
65 
67 
68  /// Maximum aggregation capacity in one pass
69  enum max_size
70  {
72  };
73 
74  /// Codes for aggregation operations which can be pipelined for efficient execution
75  ///
76  enum operation
77  {
80  };
81 
83  {
88  };
89 
90 public:
91 
92  /*! @name Construction and setup */
93  //@{
94  aggregator();
95  ~aggregator();
96 
97  /**
98  \brief set on-the-fly bit-block compression
99  By default aggregator does not try to optimize result, but in some cases
100  it can be quite a lot faster than calling bvector<>::optimize() later
101  (because block data sits in CPU cache).
102 
103  \param opt - optimization mode (full compression by default)
104  */
107  { opt_mode_ = opt; }
108  //@}
109 
110 
111  // -----------------------------------------------------------------------
112 
113  /*! @name Methods to setup argument groups and run operations on groups */
114  //@{
115 
116  /**
117  Attach source bit-vector to a argument group (0 or 1).
118  Arg group 1 used for fused operations like (AND-SUB)
119  \param bv - input bit-vector pointer to attach
120  \param agr_group - input argument group (0 - default, 1 - fused op)
121 
122  @return current arg group size (0 if vector was not added (empty))
123  @sa reset
124  */
125  unsigned add(const bvector_type* bv, unsigned agr_group = 0);
126 
127  /**
128  Reset aggregate groups, forget all attached vectors
129  */
130  void reset();
131 
132  /**
133  Aggregate added group of vectors using logical OR
134  Operation does NOT perform an explicit reset of arg group(s)
135 
136  \param bv_target - target vector (input is arg group 0)
137 
138  @sa add, reset
139  */
140  void combine_or(bvector_type& bv_target);
141 
142  /**
143  Aggregate added group of vectors using logical AND
144  Operation does NOT perform an explicit reset of arg group(s)
145 
146  \param bv_target - target vector (input is arg group 0)
147 
148  @sa add, reset
149  */
150  void combine_and(bvector_type& bv_target);
151 
152  /**
153  Aggregate added group of vectors using fused logical AND-SUB
154  Operation does NOT perform an explicit reset of arg group(s)
155 
156  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
157 
158  \return true if anything was found
159 
160  @sa add, reset
161  */
162  bool combine_and_sub(bvector_type& bv_target);
163 
164 
165  /**
166  Aggregate added group of vectors using fused logical AND-SUB
167  Operation does NOT perform an explicit reset of arg group(s)
168  Operation can terminate early if anything was found.
169 
170  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
171  \param any - if true, search result will terminate of first found result
172 
173  \return true if anything was found
174 
175  @sa add, reset
176  */
177  bool combine_and_sub(bvector_type& bv_target, bool any);
178 
179  bool find_first_and_sub(size_type& idx);
180 
181 
182  /**
183  Aggregate added group of vectors using SHIFT-RIGHT and logical AND
184  Operation does NOT perform an explicit reset of arg group(s)
185 
186  \param bv_target - target vector (input is arg group 0)
187 
188  @return bool if anything was found
189 
190  @sa add, reset
191  */
192  void combine_shift_right_and(bvector_type& bv_target);
193 
194  /**
195  Set search hint for the range, where results needs to be searched
196  (experimental for internal use).
197  */
198  void set_range_hint(size_type from, size_type to);
199 
200  //@}
201 
202  // -----------------------------------------------------------------------
203 
204  /*! @name Logical operations (C-style interface) */
205  //@{
206 
207  /**
208  Aggregate group of vectors using logical OR
209  \param bv_target - target vector
210  \param bv_src - array of pointers on bit-vector aggregate arguments
211  \param src_size - size of bv_src (how many vectors to aggregate)
212  */
213  void combine_or(bvector_type& bv_target,
214  const bvector_type_const_ptr* bv_src, unsigned src_size);
215 
216  /**
217  Aggregate group of vectors using logical AND
218  \param bv_target - target vector
219  \param bv_src - array of pointers on bit-vector aggregate arguments
220  \param src_size - size of bv_src (how many vectors to aggregate)
221  */
222  void combine_and(bvector_type& bv_target,
223  const bvector_type_const_ptr* bv_src, unsigned src_size);
224 
225  /**
226  Fusion aggregate group of vectors using logical AND MINUS another set
227 
228  \param bv_target - target vector
229  \param bv_src_and - array of pointers on bit-vectors for AND
230  \param src_and_size - size of AND group
231  \param bv_src_sub - array of pointers on bit-vectors for SUBstract
232  \param src_sub_size - size of SUB group
233  \param any - flag if caller needs any results asap (incomplete results)
234 
235  \return true when found
236  */
237  bool combine_and_sub(bvector_type& bv_target,
238  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
239  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
240  bool any);
241 
242  bool find_first_and_sub(size_type& idx,
243  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
244  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size);
245 
246  /**
247  Fusion aggregate group of vectors using SHIFT right with AND
248 
249  \param bv_target - target vector
250  \param bv_src_and - array of pointers on bit-vectors for AND masking
251  \param src_and_size - size of AND group
252  \param any - flag if caller needs any results asap (incomplete results)
253 
254  \return true when found
255  */
256  bool combine_shift_right_and(bvector_type& bv_target,
257  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
258  bool any);
259 
260 
261  //@}
262 
263  // -----------------------------------------------------------------------
264 
265  /*! @name Horizontal Logical operations used for tests (C-style interface) */
266  //@{
267 
268  /**
269  Horizontal OR aggregation (potentially slower) method.
270  \param bv_target - target vector
271  \param bv_src - array of pointers on bit-vector aggregate arguments
272  \param src_size - size of bv_src (how many vectors to aggregate)
273  */
274  void combine_or_horizontal(bvector_type& bv_target,
275  const bvector_type_const_ptr* bv_src, unsigned src_size);
276  /**
277  Horizontal AND aggregation (potentially slower) method.
278  \param bv_target - target vector
279  \param bv_src - array of pointers on bit-vector aggregate arguments
280  \param src_size - size of bv_src (how many vectors to aggregate)
281  */
282  void combine_and_horizontal(bvector_type& bv_target,
283  const bvector_type_const_ptr* bv_src, unsigned src_size);
284 
285  /**
286  Horizontal AND-SUB aggregation (potentially slower) method.
287  \param bv_target - target vector
288  \param bv_src_and - array of pointers on bit-vector to AND aggregate
289  \param src_and_size - size of bv_src_and
290  \param bv_src_sub - array of pointers on bit-vector to SUB aggregate
291  \param src_sub_size - size of bv_src_sub
292  */
293  void combine_and_sub_horizontal(bvector_type& bv_target,
294  const bvector_type_const_ptr* bv_src_and,
295  unsigned src_and_size,
296  const bvector_type_const_ptr* bv_src_sub,
297  unsigned src_sub_size);
298 
299  //@}
300 
301 
302  // -----------------------------------------------------------------------
303 
304  /*! @name Pipeline operations */
305  //@{
306 
307  /** Get current operation code */
308  int get_operation() const { return operation_; }
309 
310  /** Set operation code for the aggregator */
311  void set_operation(int op_code) { operation_ = op_code; }
312 
313  /**
314  Prepare operation, create internal resources, analyse dependencies.
315  Prerequisites are: that operation is set and all argument vectors are added
316  */
317  void stage(bm::word_t* temp_block);
318 
319  /**
320  Run a step of current arrgegation operation
321  */
322  operation_status run_step(unsigned i, unsigned j);
323 
324  operation_status get_operation_status() const { return operation_status_; }
325 
326  const bvector_type* get_target() const { return bv_target_; }
327 
328  bm::word_t* get_temp_block() { return ar_->tb1; }
329 
330  //@}
331 
332 protected:
334  typedef typename BV::block_idx_type block_idx_type;
335 
336 
337  void combine_or(unsigned i, unsigned j,
338  bvector_type& bv_target,
339  const bvector_type_const_ptr* bv_src, unsigned src_size);
340 
341  void combine_and(unsigned i, unsigned j,
342  bvector_type& bv_target,
343  const bvector_type_const_ptr* bv_src, unsigned src_size);
344 
345  digest_type combine_and_sub(unsigned i, unsigned j,
346  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
347  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
348  int* is_result_full);
349 
350  void prepare_shift_right_and(bvector_type& bv_target,
351  const bvector_type_const_ptr* bv_src, unsigned src_size);
352 
353  bool combine_shift_right_and(unsigned i, unsigned j,
354  bvector_type& bv_target,
355  const bvector_type_const_ptr* bv_src, unsigned src_size);
356 
357  static
358  unsigned resize_target(bvector_type& bv_target,
359  const bvector_type_const_ptr* bv_src,
360  unsigned src_size,
361  bool init_clear = true);
362 
363  static
364  unsigned max_top_blocks(const bvector_type_const_ptr* bv_src, unsigned src_size);
365 
366  bm::word_t* sort_input_blocks_or(const bvector_type_const_ptr* bv_src,
367  unsigned src_size,
368  unsigned i, unsigned j,
369  unsigned* arg_blk_count,
370  unsigned* arg_blk_gap_count);
371 
372  bm::word_t* sort_input_blocks_and(const bvector_type_const_ptr* bv_src,
373  unsigned src_size,
374  unsigned i, unsigned j,
375  unsigned* arg_blk_count,
376  unsigned* arg_blk_gap_count);
377 
378 
379  bool process_bit_blocks_or(blocks_manager_type& bman_target,
380  unsigned i, unsigned j, unsigned block_count);
381 
382  void process_gap_blocks_or(unsigned block_count);
383 
384  digest_type process_bit_blocks_and(unsigned block_count, digest_type digest);
385 
386  digest_type process_gap_blocks_and(unsigned block_count, digest_type digest);
387 
388  bool test_gap_blocks_and(unsigned block_count, unsigned bit_idx);
389  bool test_gap_blocks_sub(unsigned block_count, unsigned bit_idx);
390 
391  digest_type process_bit_blocks_sub(unsigned block_count, digest_type digest);
392 
393  digest_type process_gap_blocks_sub(unsigned block_count, digest_type digest);
394 
395  static
396  unsigned find_effective_sub_block_size(unsigned i,
397  const bvector_type_const_ptr* bv_src,
398  unsigned src_size,
399  bool top_null_as_zero);
400 
401  bool any_carry_overs(unsigned co_size) const;
402 
403  /**
404  @return carry over
405  */
406  bool process_shift_right_and(const bm::word_t* arg_blk,
407  digest_type& digest,
408  unsigned carry_over);
409 
410  const bm::word_t* get_arg_block(const bvector_type_const_ptr* bv_src,
411  unsigned k, unsigned i, unsigned j);
412 
413  bvector_type* check_create_target();
414 
415 private:
416  /// Memory arena for logical operations
417  ///
418  /// @internal
419  struct arena
420  {
422  BM_DECLARE_TEMP_BLOCK(tb_opt); ///< temp block for results optimization
423  const bm::word_t* v_arg_or_blk[max_aggregator_cap]; ///< source blocks list (OR)
424  const bm::gap_word_t* v_arg_or_blk_gap[max_aggregator_cap]; ///< source GAP blocks list (OR)
425  const bm::word_t* v_arg_and_blk[max_aggregator_cap]; ///< source blocks list (AND)
426  const bm::gap_word_t* v_arg_and_blk_gap[max_aggregator_cap]; ///< source GAP blocks list (AND)
427 
428  bvector_type_const_ptr arg_bv0[max_aggregator_cap]; ///< arg group 0
429  bvector_type_const_ptr arg_bv1[max_aggregator_cap]; ///< arg group 1
430  unsigned char carry_overs_[max_aggregator_cap]; /// carry over flags
431  };
432 
433  aggregator(const aggregator&) = delete;
434  aggregator& operator=(const aggregator&) = delete;
435 
436 private:
437  arena* ar_; ///< data arena ptr (heap allocated)
438  unsigned arg_group0_size = 0;
439  unsigned arg_group1_size = 0;
440  allocator_pool_type pool_; ///< pool for operations with cyclic mem.use
441 
442  bm::word_t* temp_blk_= 0; ///< external temp block ptr
443  int operation_ = 0; ///< operation code (default: not defined)
444  operation_status operation_status_ = op_undefined;
445  bvector_type* bv_target_ = 0; ///< target bit-vector
446  unsigned top_block_size_ = 0; ///< operation top block (i) size
447 
448  // search range setting (hint) [from, to]
449  bool range_set_ = false; ///< range flag
450  size_type range_from_ = bm::id_max; ///< search from
451  size_type range_to_ = bm::id_max; ///< search to
452 
453  typename bvector_type::optmode opt_mode_;
454 
455 };
456 
457 
458 
459 
460 // ------------------------------------------------------------------------
461 //
462 // ------------------------------------------------------------------------
463 
464 /**
465  Experimental method ro run multiple aggregators in sync
466 
467  Pipeleine algorithm walts the sequence of iterators (pointers on aggregators)
468  and run them all via aggregator<>::run_step() method
469 
470  @param first - iterator (pointer on aggregator)
471  @param last - iterator (pointer on aggregator)
472  @ingroup setalgo
473 */
474 template<typename Agg, typename It>
475 void aggregator_pipeline_execute(It first, It last)
476 {
477  bm::word_t* tb = (*first)->get_temp_block();
478 
479  int pipeline_size = 0;
480  for (It it = first; it != last; ++it, ++pipeline_size)
481  {
482  Agg& agg = *(*it);
483  agg.stage(tb);
484  }
485  for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
486  {
487  unsigned j = 0;
488  do
489  {
490  // run all aggregators for the [i,j] coordinate
491  unsigned w = 0;
492  for (It it = first; it != last; ++it, ++w)
493  {
494  Agg& agg = *(*it);
495  auto op_st = agg.get_operation_status();
496  if (op_st != Agg::op_done)
497  {
498  op_st = agg.run_step(i, j);
499  pipeline_size -= (op_st == Agg::op_done);
500  }
501  } // for it
502  if (pipeline_size <= 0)
503  return;
504 
505  } while (++j < bm::set_sub_array_size);
506 
507  } // for i
508 }
509 
510 
511 // ------------------------------------------------------------------------
512 //
513 // ------------------------------------------------------------------------
514 
515 
516 template<typename BV>
518 : opt_mode_(bvector_type::opt_none)
519 {
520  ar_ = (arena*) bm::aligned_new_malloc(sizeof(arena));
521 }
522 
523 // ------------------------------------------------------------------------
524 
525 template<typename BV>
527 {
528  BM_ASSERT(ar_);
529  bm::aligned_free(ar_);
530  delete bv_target_;
531 }
532 
533 // ------------------------------------------------------------------------
534 
535 template<typename BV>
537 {
538  arg_group0_size = arg_group1_size = operation_ = top_block_size_ = 0;
539  operation_status_ = op_undefined;
540  range_set_ = false;
541  range_from_ = range_to_ = bm::id_max;
542 }
543 
544 // ------------------------------------------------------------------------
545 
546 template<typename BV>
548 {
549  range_from_ = from; range_to_ = to;
550  range_set_ = true;
551 }
552 
553 // ------------------------------------------------------------------------
554 
555 template<typename BV>
557 {
558  if (!bv_target_)
559  {
560  bv_target_ = new bvector_type();
561  bv_target_->init();
562  }
563  return bv_target_;
564 }
565 
566 // ------------------------------------------------------------------------
567 
568 template<typename BV>
569 unsigned aggregator<BV>::add(const bvector_type* bv, unsigned agr_group)
570 {
571  BM_ASSERT_THROW(agr_group <= 1, BM_ERR_RANGE);
572  BM_ASSERT(agr_group <= 1);
573 
574  if (agr_group) // arg group 1
575  {
576  BM_ASSERT(arg_group1_size < max_aggregator_cap);
577  BM_ASSERT_THROW(arg_group1_size < max_aggregator_cap, BM_ERR_RANGE);
578 
579  if (!bv)
580  return arg_group1_size;
581 
582  ar_->arg_bv1[arg_group1_size++] = bv;
583  return arg_group1_size;
584  }
585  else // arg group 0
586  {
587  BM_ASSERT(arg_group0_size < max_aggregator_cap);
588  BM_ASSERT_THROW(arg_group0_size < max_aggregator_cap, BM_ERR_RANGE);
589 
590  if (!bv)
591  return arg_group0_size;
592 
593  ar_->arg_bv0[arg_group0_size++] = bv;
594  return arg_group0_size;
595  }
596 }
597 
598 // ------------------------------------------------------------------------
599 
600 template<typename BV>
602 {
603  combine_or(bv_target, ar_->arg_bv0, arg_group0_size);
604 }
605 
606 // ------------------------------------------------------------------------
607 
608 template<typename BV>
610 {
611  combine_and(bv_target, ar_->arg_bv0, arg_group0_size);
612 }
613 
614 // ------------------------------------------------------------------------
615 
616 template<typename BV>
618 {
619  return combine_and_sub(bv_target,
620  ar_->arg_bv0, arg_group0_size,
621  ar_->arg_bv1, arg_group1_size, false);
622 }
623 
624 // ------------------------------------------------------------------------
625 
626 template<typename BV>
628 {
629  return combine_and_sub(bv_target,
630  ar_->arg_bv0, arg_group0_size,
631  ar_->arg_bv1, arg_group1_size, any);
632 }
633 
634 // ------------------------------------------------------------------------
635 
636 template<typename BV>
638 {
639  return find_first_and_sub(idx,
640  ar_->arg_bv0, arg_group0_size,
641  ar_->arg_bv1, arg_group1_size);
642 }
643 
644 // ------------------------------------------------------------------------
645 
646 template<typename BV>
648 {
649  combine_shift_right_and(bv_target, ar_->arg_bv0, arg_group0_size, false);
650 }
651 
652 // ------------------------------------------------------------------------
653 
654 template<typename BV>
656  const bvector_type_const_ptr* bv_src, unsigned src_size)
657 {
658  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
659  if (!src_size)
660  {
661  bv_target.clear();
662  return;
663  }
664  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
665  for (unsigned i = 0; i < top_blocks; ++i)
666  {
667  unsigned set_array_max =
668  find_effective_sub_block_size(i, bv_src, src_size, false);
669  for (unsigned j = 0; j < set_array_max; ++j)
670  {
671  combine_or(i, j, bv_target, bv_src, src_size);
672  } // for j
673  } // for i
674 }
675 
676 // ------------------------------------------------------------------------
677 
678 template<typename BV>
680  const bvector_type_const_ptr* bv_src,
681  unsigned src_size)
682 {
683  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
684  if (src_size == 1)
685  {
686  const bvector_type* bv = bv_src[0];
687  bv_target = *bv;
688  return;
689  }
690  if (!src_size)
691  {
692  bv_target.clear();
693  return;
694  }
695  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
696  for (unsigned i = 0; i < top_blocks; ++i)
697  {
698  // TODO: find range, not just size
699  unsigned set_array_max =
700  find_effective_sub_block_size(i, bv_src, src_size, true);
701  for (unsigned j = 0; j < set_array_max; ++j)
702  {
703  // TODO: use block_managers not bvectors to avoid extra indirect
704  combine_and(i, j, bv_target, bv_src, src_size);
705  } // for j
706  } // for i
707 }
708 
709 // ------------------------------------------------------------------------
710 
711 template<typename BV>
713  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
714  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
715  bool any)
716 {
717  BM_ASSERT_THROW(src_and_size < max_aggregator_cap, BM_ERR_RANGE);
718  BM_ASSERT_THROW(src_sub_size < max_aggregator_cap, BM_ERR_RANGE);
719 
720  bool global_found = false;
721 
722  if (!bv_src_and || !src_and_size)
723  {
724  bv_target.clear();
725  return false;
726  }
727 
728  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
729 
730  unsigned top_blocks = resize_target(bv_target, bv_src_and, src_and_size);
731  unsigned top_blocks2 = resize_target(bv_target, bv_src_sub, src_sub_size, false);
732 
733  if (top_blocks2 > top_blocks)
734  top_blocks = top_blocks2;
735 
736  for (unsigned i = 0; i < top_blocks; ++i)
737  {
738  unsigned set_array_max = find_effective_sub_block_size(i, bv_src_and, src_and_size, true);
739  if (!set_array_max)
740  continue;
741  if (src_sub_size)
742  {
743  unsigned set_array_max2 =
744  find_effective_sub_block_size(i, bv_src_sub, src_sub_size, false);
745  if (set_array_max2 > set_array_max) // TODO: use range intersect
746  set_array_max = set_array_max2;
747  }
748  for (unsigned j = 0; j < set_array_max; ++j)
749  {
750  int is_res_full;
751  digest_type digest = combine_and_sub(i, j,
752  bv_src_and, src_and_size,
753  bv_src_sub, src_sub_size,
754  &is_res_full);
755  if (is_res_full)
756  {
757  bman_target.check_alloc_top_subblock(i);
758  bman_target.set_block_ptr(i, j, (bm::word_t*)FULL_BLOCK_FAKE_ADDR);
759  if (j == bm::set_sub_array_size-1)
760  {
761  bman_target.validate_top_full(i);
762  }
763  if (any)
764  return any;
765  }
766  else
767  {
768  bool found = digest;
769  if (found)
770  {
771  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
772  opt_mode_, ar_->tb_opt);
773  if (any)
774  return found;
775  }
776  global_found |= found;
777  }
778  } // for j
779  } // for i
780  return global_found;
781 }
782 
783 // ------------------------------------------------------------------------
784 
785 template<typename BV>
787  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
788  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size)
789 {
790  BM_ASSERT_THROW(src_and_size < max_aggregator_cap, BM_ERR_RANGE);
791  BM_ASSERT_THROW(src_sub_size < max_aggregator_cap, BM_ERR_RANGE);
792 
793  if (!bv_src_and || !src_and_size)
794  return false;
795 
796  unsigned top_blocks = max_top_blocks(bv_src_and, src_and_size);
797  unsigned top_blocks2 = max_top_blocks(bv_src_sub, src_sub_size);
798 
799  if (top_blocks2 > top_blocks)
800  top_blocks = top_blocks2;
801 
802  // compute range blocks coordinates
803  //
804  block_idx_type nblock_from = (range_from_ >> bm::set_block_shift);
805  block_idx_type nblock_to = (range_to_ >> bm::set_block_shift);
806  unsigned top_from = unsigned(nblock_from >> bm::set_array_shift);
807  unsigned top_to = unsigned(nblock_to >> bm::set_array_shift);
808 
809  if (range_set_)
810  {
811  if (nblock_from == nblock_to) // one block search
812  {
813  int is_res_full;
814  unsigned i = top_from;
815  unsigned j = unsigned(nblock_from & bm::set_array_mask);
816  digest_type digest = combine_and_sub(i, j,
817  bv_src_and, src_and_size,
818  bv_src_sub, src_sub_size,
819  &is_res_full);
820  // is_res_full is not needed here, since it is just 1 block
821  if (digest)
822  {
823  unsigned block_bit_idx = 0;
824  bool found = bm::bit_find_first(ar_->tb1, &block_bit_idx, digest);
825  BM_ASSERT(found);
826  idx = bm::block_to_global_index(i, j, block_bit_idx);
827  return found;
828  }
829  return false;
830  }
831 
832  if (top_to < top_blocks)
833  top_blocks = top_to+1;
834  }
835  else
836  {
837  top_from = 0;
838  }
839 
840  for (unsigned i = top_from; i < top_blocks; ++i)
841  {
842  unsigned set_array_max = bm::set_sub_array_size;
843  unsigned j = 0;
844  if (range_set_)
845  {
846  if (i == top_from)
847  {
848  j = nblock_from & bm::set_array_mask;
849  }
850  if (i == top_to)
851  {
852  set_array_max = 1 + unsigned(nblock_to & bm::set_array_mask);
853  }
854  }
855  else
856  {
857  set_array_max = find_effective_sub_block_size(i, bv_src_and, src_and_size, true);
858  if (!set_array_max)
859  continue;
860  if (src_sub_size)
861  {
862  unsigned set_array_max2 =
863  find_effective_sub_block_size(i, bv_src_sub, src_sub_size, false);
864  if (set_array_max2 > set_array_max)
865  set_array_max = set_array_max2;
866  }
867  }
868  for (; j < set_array_max; ++j)
869  {
870  int is_res_full;
871  digest_type digest = combine_and_sub(i, j,
872  bv_src_and, src_and_size,
873  bv_src_sub, src_sub_size,
874  &is_res_full);
875  if (digest)
876  {
877  unsigned block_bit_idx = 0;
878  bool found = bm::bit_find_first(ar_->tb1, &block_bit_idx, digest);
879  BM_ASSERT(found);
880  idx = bm::block_to_global_index(i, j, block_bit_idx);
881  return found;
882  }
883  } // for j
884  //while (++j < set_array_max);
885  } // for i
886  return false;
887 }
888 
889 // ------------------------------------------------------------------------
890 
891 template<typename BV>
892 unsigned
894  const bvector_type_const_ptr* bv_src,
895  unsigned src_size,
896  bool top_null_as_zero)
897 {
898  // quick hack to avoid scanning large, arrays, where such scan can be quite
899  // expensive by itself (this makes this function approximate)
900  if (src_size > 32)
901  return bm::set_sub_array_size;
902 
903  unsigned max_size = 1;
904  for (unsigned k = 0; k < src_size; ++k)
905  {
906  const bvector_type* bv = bv_src[k];
907  BM_ASSERT(bv);
908  const typename bvector_type::blocks_manager_type& bman_arg =
909  bv->get_blocks_manager();
910  const bm::word_t* const* blk_blk_arg = bman_arg.get_topblock(i);
911  if (!blk_blk_arg)
912  {
913  if (top_null_as_zero)
914  return 0;
915  continue;
916  }
917  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
918  return bm::set_sub_array_size;
919 
920  for (unsigned j = bm::set_sub_array_size - 1; j > max_size; --j)
921  {
922  if (blk_blk_arg[j])
923  {
924  max_size = j;
925  break;
926  }
927  }
928  if (max_size == bm::set_sub_array_size - 1)
929  break;
930  } // for k
931  ++max_size;
932  BM_ASSERT(max_size <= bm::set_sub_array_size);
933 
934  return max_size;
935 }
936 
937 // ------------------------------------------------------------------------
938 
939 template<typename BV>
940 void aggregator<BV>::combine_or(unsigned i, unsigned j,
941  bvector_type& bv_target,
942  const bvector_type_const_ptr* bv_src,
943  unsigned src_size)
944 {
945  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
946 
947  unsigned arg_blk_count = 0;
948  unsigned arg_blk_gap_count = 0;
949  bm::word_t* blk =
950  sort_input_blocks_or(bv_src, src_size, i, j,
951  &arg_blk_count, &arg_blk_gap_count);
952 
953  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
954 
955  if (blk == FULL_BLOCK_FAKE_ADDR) // nothing to do - golden block(!)
956  {
957  bman_target.check_alloc_top_subblock(i);
958  bman_target.set_block_ptr(i, j, blk);
959  if (++j == bm::set_sub_array_size)
960  {
961  bman_target.validate_top_full(i);
962  }
963  }
964  else
965  {
966  blk = ar_->tb1;
967  if (arg_blk_count || arg_blk_gap_count)
968  {
969  bool all_one =
970  process_bit_blocks_or(bman_target, i, j, arg_blk_count);
971  if (!all_one)
972  {
973  if (arg_blk_gap_count)
974  {
975  process_gap_blocks_or(arg_blk_gap_count);
976  }
977  // we have some results, allocate block and copy from temp
978  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
979  opt_mode_, ar_->tb_opt);
980  }
981  }
982  }
983 }
984 
985 // ------------------------------------------------------------------------
986 
987 template<typename BV>
988 void aggregator<BV>::combine_and(unsigned i, unsigned j,
989  bvector_type& bv_target,
990  const bvector_type_const_ptr* bv_src,
991  unsigned src_size)
992 {
993  BM_ASSERT(src_size);
994 
995  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
996 
997  unsigned arg_blk_count = 0;
998  unsigned arg_blk_gap_count = 0;
999  bm::word_t* blk =
1000  sort_input_blocks_and(bv_src, src_size,
1001  i, j,
1002  &arg_blk_count, &arg_blk_gap_count);
1003 
1004  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1005 
1006  if (!blk) // nothing to do - golden block(!)
1007  return;
1008  if (arg_blk_count || arg_blk_gap_count)
1009  {
1010  if (!arg_blk_gap_count && (arg_blk_count == 1))
1011  {
1012  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1013  {
1014  // another nothing to do: one FULL block
1015  bman_target.check_alloc_top_subblock(i);
1016  bman_target.set_block_ptr(i, j, blk);
1017  if (++j == bm::set_sub_array_size)
1018  {
1019  bman_target.validate_top_full(i);
1020  }
1021  return;
1022  }
1023  }
1024  // AND bit-blocks
1025  //
1026  bm::id64_t digest = ~0ull;
1027  digest = process_bit_blocks_and(arg_blk_count, digest);
1028  if (!digest)
1029  return;
1030 
1031  // AND all GAP blocks (if any)
1032  //
1033  if (arg_blk_gap_count)
1034  {
1035  digest =
1036  process_gap_blocks_and(arg_blk_gap_count, digest);
1037  }
1038  if (digest) // some results
1039  {
1040  // we have some results, allocate block and copy from temp
1041  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
1042  opt_mode_, ar_->tb_opt);
1043  }
1044  }
1045 }
1046 
1047 // ------------------------------------------------------------------------
1048 
1049 template<typename BV>
1051 aggregator<BV>::combine_and_sub(unsigned i, unsigned j,
1052  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
1053  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
1054  int* is_result_full)
1055 {
1056  BM_ASSERT(src_and_size);
1057  BM_ASSERT(is_result_full);
1058 
1059  unsigned arg_blk_and_count = 0;
1060  unsigned arg_blk_and_gap_count = 0;
1061  unsigned arg_blk_sub_count = 0;
1062  unsigned arg_blk_sub_gap_count = 0;
1063 
1064  *is_result_full = 0;
1065  bm::word_t* blk = sort_input_blocks_and(bv_src_and, src_and_size,
1066  i, j,
1067  &arg_blk_and_count, &arg_blk_and_gap_count);
1068  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1069  if (!blk || !(arg_blk_and_count | arg_blk_and_gap_count))
1070  return 0; // nothing to do - golden block(!)
1071 
1072  if (src_sub_size)
1073  {
1074  blk = sort_input_blocks_or(bv_src_sub, src_sub_size,
1075  i, j,
1076  &arg_blk_sub_count, &arg_blk_sub_gap_count);
1077  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1078  if (blk == FULL_BLOCK_FAKE_ADDR)
1079  return 0; // nothing to do - golden block(!)
1080  }
1081  else
1082  {
1083  if (!arg_blk_and_gap_count && (arg_blk_and_count == 1))
1084  {
1085  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1086  {
1087  *is_result_full = 1;
1088  return ~0ull;
1089  }
1090  }
1091  }
1092 
1093  digest_type digest = ~0ull;
1094 
1095  // AND-SUB bit-blocks
1096  //
1097  digest = process_bit_blocks_and(arg_blk_and_count, digest);
1098  if (!digest)
1099  return digest;
1100  digest = process_bit_blocks_sub(arg_blk_sub_count, digest);
1101  if (!digest)
1102  return digest;
1103 
1104  // AND all GAP block
1105  //
1106  digest =
1107  process_gap_blocks_and(arg_blk_and_gap_count, digest);
1108  if (!digest)
1109  return digest;
1110 
1111  if (arg_blk_sub_gap_count)
1112  {
1113  digest =
1114  process_gap_blocks_sub(arg_blk_sub_gap_count, digest);
1115  }
1116 
1117  return digest;
1118 }
1119 
1120 // ------------------------------------------------------------------------
1121 
1122 template<typename BV>
1123 void aggregator<BV>::process_gap_blocks_or(unsigned arg_blk_gap_count)
1124 {
1125  bm::word_t* blk = ar_->tb1;
1126  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1127  bm::gap_add_to_bitset(blk, ar_->v_arg_or_blk_gap[k]);
1128 }
1129 
1130 // ------------------------------------------------------------------------
1131 
1132 template<typename BV>
1134 aggregator<BV>::process_gap_blocks_and(unsigned arg_blk_gap_count,
1135  digest_type digest)
1136 {
1137  bm::word_t* blk = ar_->tb1;
1138  bool single_bit_found;
1139  unsigned single_bit_idx;
1140  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1141  {
1142  bm::gap_and_to_bitset(blk, ar_->v_arg_and_blk_gap[k], digest);
1143  digest = bm::update_block_digest0(blk, digest);
1144  if (!digest)
1145  {
1147  break;
1148  }
1149  single_bit_found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1150  if (single_bit_found)
1151  {
1152  for (++k; k < arg_blk_gap_count; ++k)
1153  {
1154  bool b = bm::gap_test_unr(ar_->v_arg_and_blk_gap[k], single_bit_idx);
1155  if (!b)
1156  return 0; // AND 0 causes result to turn 0
1157  }
1158  break;
1159  }
1160  }
1161  return digest;
1162 }
1163 
1164 // ------------------------------------------------------------------------
1165 
1166 template<typename BV>
1168 aggregator<BV>::process_gap_blocks_sub(unsigned arg_blk_gap_count,
1169  digest_type digest)
1170 {
1171  bm::word_t* blk = ar_->tb1;
1172  bool single_bit_found;
1173  unsigned single_bit_idx;
1174  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1175  {
1176  bm::gap_sub_to_bitset(blk, ar_->v_arg_or_blk_gap[k], digest);
1177  digest = bm::update_block_digest0(blk, digest);
1178  if (!digest)
1179  {
1181  break;
1182  }
1183  // check if logical operation reduced to a corner case of one single bit
1184  single_bit_found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1185  if (single_bit_found)
1186  {
1187  for (++k; k < arg_blk_gap_count; ++k)
1188  {
1189  bool b = bm::gap_test_unr(ar_->v_arg_or_blk_gap[k], single_bit_idx);
1190  if (b)
1191  return 0; // AND-NOT causes search result to turn 0
1192  } // for k
1193  break;
1194  }
1195  } // for k
1196  return digest;
1197 }
1198 
1199 // ------------------------------------------------------------------------
1200 
1201 template<typename BV>
1202 bool aggregator<BV>::test_gap_blocks_and(unsigned arg_blk_gap_count,
1203  unsigned bit_idx)
1204 {
1205  unsigned b = 1;
1206  for (unsigned i = 0; i < arg_blk_gap_count && b; ++i)
1207  {
1208  b = bm::gap_test_unr(ar_->v_arg_and_blk_gap[i], bit_idx);
1209  }
1210  return b;
1211 }
1212 
1213 // ------------------------------------------------------------------------
1214 
1215 template<typename BV>
1216 bool aggregator<BV>::test_gap_blocks_sub(unsigned arg_blk_gap_count,
1217  unsigned bit_idx)
1218 {
1219  unsigned b = 1;
1220  for (unsigned i = 0; i < arg_blk_gap_count; ++i)
1221  {
1222  b = bm::gap_test_unr(ar_->v_arg_or_blk_gap[i], bit_idx);
1223  if (b)
1224  return false;
1225  }
1226  return true;
1227 }
1228 
1229 // ------------------------------------------------------------------------
1230 
1231 
1232 template<typename BV>
1234  unsigned i, unsigned j,
1235  unsigned arg_blk_count)
1236 {
1237  bm::word_t* blk = ar_->tb1;
1238  bool all_one;
1239 
1240  unsigned k = 0;
1241 
1242  if (arg_blk_count) // copy the first block
1243  bm::bit_block_copy(blk, ar_->v_arg_or_blk[k++]);
1244  else
1245  bm::bit_block_set(blk, 0);
1246 
1247  // process all BIT blocks
1248  //
1249  unsigned unroll_factor, len, len_unr;
1250 
1251  unroll_factor = 4;
1252  len = arg_blk_count - k;
1253  len_unr = len - (len % unroll_factor);
1254  for( ;k < len_unr; k+=unroll_factor)
1255  {
1256  all_one = bm::bit_block_or_5way(blk,
1257  ar_->v_arg_or_blk[k], ar_->v_arg_or_blk[k+1],
1258  ar_->v_arg_or_blk[k+2], ar_->v_arg_or_blk[k+3]);
1259  if (all_one)
1260  {
1261  BM_ASSERT(blk == ar_->tb1);
1263  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1264  return true;
1265  }
1266  } // for k
1267 
1268  unroll_factor = 2;
1269  len = arg_blk_count - k;
1270  len_unr = len - (len % unroll_factor);
1271  for( ;k < len_unr; k+=unroll_factor)
1272  {
1273  all_one = bm::bit_block_or_3way(blk, ar_->v_arg_or_blk[k], ar_->v_arg_or_blk[k+1]);
1274  if (all_one)
1275  {
1276  BM_ASSERT(blk == ar_->tb1);
1278  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1279  return true;
1280  }
1281  } // for k
1282 
1283  for (; k < arg_blk_count; ++k)
1284  {
1285  all_one = bm::bit_block_or(blk, ar_->v_arg_or_blk[k]);
1286  if (all_one)
1287  {
1288  BM_ASSERT(blk == ar_->tb1);
1290  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1291  return true;
1292  }
1293  } // for k
1294 
1295  return false;
1296 }
1297 
1298 // ------------------------------------------------------------------------
1299 
1300 template<typename BV>
1303  digest_type digest)
1304 {
1305  bm::word_t* blk = ar_->tb1;
1306  unsigned k = 0;
1307 
1308  block_idx_type nb_from = (range_from_ >> bm::set_block_shift);
1309  block_idx_type nb_to = (range_to_ >> bm::set_block_shift);
1310  if (range_set_ && (nb_from == nb_to))
1311  {
1312  unsigned nbit_from = unsigned(range_from_ & bm::set_block_mask);
1313  unsigned nbit_to = unsigned(range_to_ & bm::set_block_mask);
1314  digest_type digest0 = bm::digest_mask(nbit_from, nbit_to);
1315  digest &= digest0;
1316  bm::block_init_digest0(blk, digest);
1317  }
1318  else
1319  {
1320  switch (arg_blk_count)
1321  {
1322  case 0:
1323  bm::block_init_digest0(blk, digest); // 0xFF... by default
1324  return digest;
1325  case 1:
1326  bm::bit_block_copy(blk, ar_->v_arg_and_blk[k]);
1327  return bm::calc_block_digest0(blk);
1328  default:
1329  digest = bm::bit_block_and_2way(blk,
1330  ar_->v_arg_and_blk[k],
1331  ar_->v_arg_and_blk[k+1],
1332  ~0ull);
1333  k += 2;
1334  break;
1335  } // switch
1336  }
1337 
1338  unsigned unroll_factor, len, len_unr;
1339  unsigned single_bit_idx;
1340 
1341  unroll_factor = 4;
1342  len = arg_blk_count - k;
1343  len_unr = len - (len % unroll_factor);
1344  for (; k < len_unr; k += unroll_factor)
1345  {
1346  digest =
1348  ar_->v_arg_and_blk[k], ar_->v_arg_and_blk[k + 1],
1349  ar_->v_arg_and_blk[k + 2], ar_->v_arg_and_blk[k + 3],
1350  digest);
1351  if (!digest) // all zero
1352  return digest;
1353  bool found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1354  if (found)
1355  {
1356  unsigned nword = unsigned(single_bit_idx >> bm::set_word_shift);
1357  unsigned mask = 1u << (single_bit_idx & bm::set_word_mask);
1358  for (++k; k < arg_blk_count; ++k)
1359  {
1360  const bm::word_t* arg_blk = ar_->v_arg_and_blk[k];
1361  if (!(mask & arg_blk[nword]))
1362  {
1363  blk[nword] = 0;
1364  return 0;
1365  }
1366  } // for k
1367  break;
1368  }
1369  } // for k
1370 
1371  for (; k < arg_blk_count; ++k)
1372  {
1373  if (ar_->v_arg_and_blk[k] == FULL_BLOCK_REAL_ADDR)
1374  continue;
1375  digest = bm::bit_block_and(blk, ar_->v_arg_and_blk[k], digest);
1376  if (!digest) // all zero
1377  return digest;
1378  } // for k
1379  return digest;
1380 }
1381 
1382 // ------------------------------------------------------------------------
1383 
1384 template<typename BV>
1387  digest_type digest)
1388 {
1389  bm::word_t* blk = ar_->tb1;
1390  unsigned single_bit_idx;
1391  const word_t** args = &ar_->v_arg_or_blk[0];
1392  for (unsigned k = 0; k < arg_blk_count; ++k)
1393  {
1394  if (ar_->v_arg_or_blk[k] == FULL_BLOCK_REAL_ADDR) // golden block
1395  {
1396  digest = 0;
1397  break;
1398  }
1399  digest = bm::bit_block_sub(blk, args[k], digest);
1400  if (!digest) // all zero
1401  break;
1402 
1403  bool found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1404  if (found)
1405  {
1406  const unsigned mask = 1u << (single_bit_idx & bm::set_word_mask);
1407  unsigned nword = unsigned(single_bit_idx >> bm::set_word_shift);
1408  for (++k; k < arg_blk_count; ++k)
1409  {
1410  if (mask & args[k][nword])
1411  {
1412  blk[nword] = 0;
1413  return 0;
1414  }
1415  } // for k
1416  break;
1417  }
1418  } // for k
1419  return digest;
1420 }
1421 
1422 // ------------------------------------------------------------------------
1423 
1424 template<typename BV>
1426  const bvector_type_const_ptr* bv_src, unsigned src_size,
1427  bool init_clear)
1428 {
1429  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1430  if (init_clear)
1431  {
1432  if (bman_target.is_init())
1433  bman_target.deinit_tree();
1434  }
1435 
1436  unsigned top_blocks = bman_target.top_block_size();
1437  size_type size = bv_target.size();
1438  bool need_realloc = false;
1439 
1440  // pre-scan to do target size harmonization
1441  for (unsigned i = 0; i < src_size; ++i)
1442  {
1443  const bvector_type* bv = bv_src[i];
1444  BM_ASSERT(bv);
1445  const typename bvector_type::blocks_manager_type& bman_arg =
1446  bv->get_blocks_manager();
1447  unsigned arg_top_blocks = bman_arg.top_block_size();
1448  if (arg_top_blocks > top_blocks)
1449  {
1450  need_realloc = true;
1451  top_blocks = arg_top_blocks;
1452  }
1453  size_type arg_size = bv->size();
1454  if (arg_size > size)
1455  size = arg_size;
1456  } // for i
1457 
1458  if (need_realloc)
1459  {
1460  bman_target.reserve_top_blocks(top_blocks);
1461  }
1462  if (!bman_target.is_init())
1463  bman_target.init_tree();
1464  if (size > bv_target.size())
1465  bv_target.resize(size);
1466 
1467  return top_blocks;
1468 }
1469 
1470 // ------------------------------------------------------------------------
1471 
1472 template<typename BV>
1473 unsigned
1475 {
1476  unsigned top_blocks = 1;
1477 
1478  // pre-scan to do target size harmonization
1479  for (unsigned i = 0; i < src_size; ++i)
1480  {
1481  const bvector_type* bv = bv_src[i];
1482  BM_ASSERT(bv);
1483  const typename bvector_type::blocks_manager_type& bman_arg = bv->get_blocks_manager();
1484  unsigned arg_top_blocks = bman_arg.top_block_size();
1485  if (arg_top_blocks > top_blocks)
1486  top_blocks = arg_top_blocks;
1487  } // for i
1488  return top_blocks;
1489 }
1490 
1491 // ------------------------------------------------------------------------
1492 
1493 template<typename BV>
1495  unsigned src_size,
1496  unsigned i, unsigned j,
1497  unsigned* arg_blk_count,
1498  unsigned* arg_blk_gap_count)
1499 {
1500  bm::word_t* blk = 0;
1501  for (unsigned k = 0; k < src_size; ++k)
1502  {
1503  const bvector_type* bv = bv_src[k];
1504  BM_ASSERT(bv);
1505  const blocks_manager_type& bman_arg = bv->get_blocks_manager();
1506  const bm::word_t* arg_blk = bman_arg.get_block_ptr(i, j);
1507  if (!arg_blk)
1508  continue;
1509  if (BM_IS_GAP(arg_blk))
1510  {
1511  ar_->v_arg_or_blk_gap[*arg_blk_gap_count] = BMGAP_PTR(arg_blk);
1512  (*arg_blk_gap_count)++;
1513  }
1514  else // FULL or bit block
1515  {
1516  if (IS_FULL_BLOCK(arg_blk))
1517  {
1518  blk = FULL_BLOCK_FAKE_ADDR;
1519  *arg_blk_gap_count = *arg_blk_count = 0; // nothing to do
1520  break;
1521  }
1522  ar_->v_arg_or_blk[*arg_blk_count] = arg_blk;
1523  (*arg_blk_count)++;
1524  }
1525  } // for k
1526  return blk;
1527 }
1528 
1529 // ------------------------------------------------------------------------
1530 
1531 template<typename BV>
1533  unsigned src_size,
1534  unsigned i, unsigned j,
1535  unsigned* arg_blk_count,
1536  unsigned* arg_blk_gap_count)
1537 {
1538  unsigned full_blk_cnt = 0;
1540  for (unsigned k = 0; k < src_size; ++k)
1541  {
1542  const bvector_type* bv = bv_src[k];
1543  BM_ASSERT(bv);
1544  const blocks_manager_type& bman_arg = bv->get_blocks_manager();
1545  const bm::word_t* arg_blk = bman_arg.get_block_ptr(i, j);
1546  if (!arg_blk)
1547  {
1548  blk = 0;
1549  *arg_blk_gap_count = *arg_blk_count = 0; // nothing to do
1550  break;
1551  }
1552  if (BM_IS_GAP(arg_blk))
1553  {
1554  ar_->v_arg_and_blk_gap[*arg_blk_gap_count] = BMGAP_PTR(arg_blk);
1555  (*arg_blk_gap_count)++;
1556  }
1557  else // FULL or bit block
1558  {
1559  if (IS_FULL_BLOCK(arg_blk))
1560  {
1561  // add only first FULL encounter, others ignore
1562  if (!full_blk_cnt) // first 0xFFF....
1563  {
1564  ar_->v_arg_and_blk[*arg_blk_count] = FULL_BLOCK_REAL_ADDR;
1565  ++full_blk_cnt;
1566  (*arg_blk_count)++;
1567  }
1568  }
1569  else
1570  {
1571  ar_->v_arg_and_blk[*arg_blk_count] = arg_blk;
1572  (*arg_blk_count)++;
1573  }
1574  /*
1575  ar_->v_arg_and_blk[*arg_blk_count] =
1576  IS_FULL_BLOCK(arg_blk) ? FULL_BLOCK_REAL_ADDR: arg_blk;
1577  (*arg_blk_count)++; */
1578  }
1579  } // for k
1580  return blk;
1581 }
1582 
1583 // ------------------------------------------------------------------------
1584 
1585 template<typename BV>
1587  const bvector_type_const_ptr* bv_src, unsigned src_size)
1588 {
1589  BM_ASSERT(src_size);
1590  if (src_size == 0)
1591  {
1592  bv_target.clear();
1593  return;
1594  }
1595 
1596  const bvector_type* bv = bv_src[0];
1597  bv_target = *bv;
1598 
1599  for (unsigned i = 1; i < src_size; ++i)
1600  {
1601  bv = bv_src[i];
1602  BM_ASSERT(bv);
1603  bv_target.bit_or(*bv);
1604  }
1605 }
1606 
1607 // ------------------------------------------------------------------------
1608 
1609 template<typename BV>
1611  const bvector_type_const_ptr* bv_src, unsigned src_size)
1612 {
1613  BM_ASSERT(src_size);
1614 
1615  if (src_size == 0)
1616  {
1617  bv_target.clear();
1618  return;
1619  }
1620  const bvector_type* bv = bv_src[0];
1621  bv_target = *bv;
1622 
1623  for (unsigned i = 1; i < src_size; ++i)
1624  {
1625  bv = bv_src[i];
1626  BM_ASSERT(bv);
1627  bv_target.bit_and(*bv);
1628  }
1629 }
1630 
1631 // ------------------------------------------------------------------------
1632 
1633 template<typename BV>
1635  const bvector_type_const_ptr* bv_src_and,
1636  unsigned src_and_size,
1637  const bvector_type_const_ptr* bv_src_sub,
1638  unsigned src_sub_size)
1639 {
1640  BM_ASSERT(src_and_size);
1641 
1642  combine_and_horizontal(bv_target, bv_src_and, src_and_size);
1643 
1644  for (unsigned i = 0; i < src_sub_size; ++i)
1645  {
1646  const bvector_type* bv = bv_src_sub[i];
1647  BM_ASSERT(bv);
1648  bv_target -= *bv;
1649  }
1650 }
1651 
1652 // ------------------------------------------------------------------------
1653 
1654 template<typename BV>
1656  const bvector_type_const_ptr* bv_src,
1657  unsigned src_size)
1658 {
1659  top_block_size_ = resize_target(bv_target, bv_src, src_size);
1660 
1661  // set initial carry overs all to 0
1662  for (unsigned i = 0; i < src_size; ++i) // reset co flags
1663  ar_->carry_overs_[i] = 0;
1664 }
1665 
1666 // ------------------------------------------------------------------------
1667 
1668 template<typename BV>
1670  bvector_type& bv_target,
1671  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
1672  bool any)
1673 {
1674  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
1675  if (!src_and_size)
1676  {
1677  bv_target.clear();
1678  return false;
1679  }
1680  prepare_shift_right_and(bv_target, bv_src_and, src_and_size);
1681 
1682  for (unsigned i = 0; i < bm::set_top_array_size; ++i)
1683  {
1684  if (i > top_block_size_)
1685  {
1686  if (!this->any_carry_overs(src_and_size))
1687  break; // quit early if there is nothing to carry on
1688  }
1689 
1690  unsigned j = 0;
1691  do
1692  {
1693  bool found = combine_shift_right_and(i, j, bv_target, bv_src_and, src_and_size);
1694  if (found && any)
1695  return found;
1696  } while (++j < bm::set_sub_array_size);
1697 
1698  } // for i
1699 
1700  return bv_target.any();
1701 }
1702 
1703 // ------------------------------------------------------------------------
1704 
1705 template<typename BV>
1706 bool aggregator<BV>::combine_shift_right_and(unsigned i, unsigned j,
1707  bvector_type& bv_target,
1708  const bvector_type_const_ptr* bv_src,
1709  unsigned src_size)
1710 {
1711  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1712  bm::word_t* blk = temp_blk_ ? temp_blk_ : ar_->tb1;
1713  unsigned char* carry_overs = &(ar_->carry_overs_[0]);
1714 
1715  bm::id64_t digest = ~0ull; // start with a full content digest
1716 
1717  bool blk_zero = false;
1718  // first initial block is just copied over from the first AND
1719  {
1720  const blocks_manager_type& bman_arg = bv_src[0]->get_blocks_manager();
1721  BM_ASSERT(bman_arg.is_init());
1722  const bm::word_t* arg_blk = bman_arg.get_block(i, j);
1723  if (BM_IS_GAP(arg_blk))
1724  {
1725  bm::bit_block_set(blk, 0);
1726  bm::gap_add_to_bitset(blk, BMGAP_PTR(arg_blk));
1727  }
1728  else
1729  {
1730  if (arg_blk)
1731  {
1732  bm::bit_block_copy(blk, arg_blk);
1733  }
1734  else
1735  {
1736  blk_zero = true; // set flag for delayed block init
1737  digest = 0;
1738  }
1739  }
1740  carry_overs[0] = 0;
1741  }
1742 
1743  for (unsigned k = 1; k < src_size; ++k)
1744  {
1745  unsigned carry_over = carry_overs[k];
1746  if (!digest && !carry_over) // 0 into "00000" block >> 0
1747  continue;
1748  if (blk_zero) // delayed temp block 0-init requested
1749  {
1750  bm::bit_block_set(blk, 0);
1751  blk_zero = false;
1752  }
1753  const bm::word_t* arg_blk = get_arg_block(bv_src, k, i, j);
1754  carry_overs[k] = process_shift_right_and(arg_blk, digest, carry_over);
1755  } // for k
1756 
1757  // block now gets emitted into the target bit-vector
1758  if (digest)
1759  {
1761  bman_target.opt_copy_bit_block(i, j, blk,
1762  opt_mode_, ar_->tb_opt);
1763  return true;
1764  }
1765  return false;
1766 }
1767 
1768 // ------------------------------------------------------------------------
1769 
1770 template<typename BV>
1772  digest_type& digest,
1773  unsigned carry_over)
1774 {
1775  bm::word_t* blk = temp_blk_ ? temp_blk_ : ar_->tb1;
1776 
1777  if (BM_IS_GAP(arg_blk)) // GAP argument
1778  {
1779  if (digest)
1780  {
1781  carry_over =
1782  bm::bit_block_shift_r1_and_unr(blk, carry_over,
1783  FULL_BLOCK_REAL_ADDR, &digest);
1784  }
1785  else // digest == 0, but carry_over can change that
1786  {
1787  blk[0] = carry_over;
1788  carry_over = 0;
1789  digest = blk[0]; // NOTE: this does NOT account for AND (yet)
1790  }
1791  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
1792 
1793  bm::gap_and_to_bitset(blk, BMGAP_PTR(arg_blk), digest);
1794  digest = bm::update_block_digest0(blk, digest);
1795  }
1796  else // 2 bit-blocks
1797  {
1798  if (arg_blk) // use fast fused SHIFT-AND operation
1799  {
1800  if (digest)
1801  {
1802  carry_over =
1803  bm::bit_block_shift_r1_and_unr(blk, carry_over, arg_blk,
1804  &digest);
1805  }
1806  else // digest == 0
1807  {
1808  blk[0] = carry_over & arg_blk[0];
1809  carry_over = 0;
1810  digest = blk[0];
1811  }
1812  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
1813  }
1814  else // arg is zero - target block => zero
1815  {
1816  unsigned co = blk[bm::set_block_size-1] >> 31; // carry out
1817  if (digest)
1818  {
1819  bm::bit_block_set(blk, 0); // TODO: digest based set
1820  digest ^= digest;
1821  }
1822  carry_over = co;
1823  }
1824  }
1825  return carry_over;
1826 }
1827 
1828 // ------------------------------------------------------------------------
1829 
1830 template<typename BV>
1832  const bvector_type_const_ptr* bv_src,
1833  unsigned k, unsigned i, unsigned j)
1834 {
1835  const blocks_manager_type& bman_arg = bv_src[k]->get_blocks_manager();
1836  return bman_arg.get_block(i, j);
1837 }
1838 
1839 // ------------------------------------------------------------------------
1840 
1841 template<typename BV>
1842 bool aggregator<BV>::any_carry_overs(unsigned co_size) const
1843 {
1844  for (unsigned i = 0; i < co_size; ++i)
1845  if (ar_->carry_overs_[i])
1846  return true;
1847  return false;
1848 }
1849 
1850 // ------------------------------------------------------------------------
1851 
1852 template<typename BV>
1854 {
1855  bvector_type* bv_target = check_create_target(); // create target vector
1856  BM_ASSERT(bv_target);
1857 
1858  temp_blk_ = temp_block;
1859 
1860  switch (operation_)
1861  {
1862  case BM_NOT_DEFINED:
1863  break;
1864  case BM_SHIFT_R_AND:
1865  prepare_shift_right_and(*bv_target, ar_->arg_bv0, arg_group0_size);
1866  operation_status_ = op_prepared;
1867  break;
1868  default:
1869  BM_ASSERT(0);
1870  } // switch
1871 }
1872 
1873 // ------------------------------------------------------------------------
1874 
1875 template<typename BV>
1877 aggregator<BV>::run_step(unsigned i, unsigned j)
1878 {
1879  BM_ASSERT(operation_status_ == op_prepared || operation_status_ == op_in_progress);
1881 
1882  switch (operation_)
1883  {
1884  case BM_NOT_DEFINED:
1885  break;
1886 
1887  case BM_SHIFT_R_AND:
1888  {
1889  if (i > top_block_size_)
1890  {
1891  if (!this->any_carry_overs(arg_group0_size))
1892  {
1893  operation_status_ = op_done;
1894  return operation_status_;
1895  }
1896  }
1897  //bool found =
1898  this->combine_shift_right_and(i, j, *bv_target_,
1899  ar_->arg_bv0, arg_group0_size);
1900  operation_status_ = op_in_progress;
1901  }
1902  break;
1903  default:
1904  BM_ASSERT(0);
1905  break;
1906  } // switch
1907 
1908  return operation_status_;
1909 }
1910 
1911 
1912 // ------------------------------------------------------------------------
1913 
1914 
1915 } // bm
1916 
1917 #include "bmundef.h"
1918 
1919 #endif
BV::block_idx_type block_idx_type
Definition: bmaggregator.h:334
void bit_block_copy(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Bitblock copy operation.
Definition: bmfunc.h:5067
void aggregator_pipeline_execute(It first, It last)
Experimental method ro run multiple aggregators in sync.
Definition: bmaggregator.h:475
void gap_add_to_bitset(unsigned *dest, const T *pcurr, unsigned len)
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:3098
digest_type process_bit_blocks_sub(unsigned block_count, digest_type digest)
max_size
Maximum aggregation capacity in one pass.
Definition: bmaggregator.h:69
const unsigned set_block_size
Definition: bmconst.h:54
bool bit_block_or_5way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4)
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of sou...
Definition: bmfunc.h:6073
const unsigned set_word_shift
Definition: bmconst.h:70
void prepare_shift_right_and(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
const unsigned set_sub_array_size
Definition: bmconst.h:91
unsigned add(const bvector_type *bv, unsigned agr_group=0)
Attach source bit-vector to a argument group (0 or 1).
Definition: bmaggregator.h:569
void combine_or(bvector_type &bv_target)
Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg...
Definition: bmaggregator.h:601
const unsigned set_array_shift
Definition: bmconst.h:92
const unsigned set_top_array_size
Definition: bmconst.h:106
unsigned long long int id64_t
Definition: bmconst.h:34
void combine_and(bvector_type &bv_target)
Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of ar...
Definition: bmaggregator.h:609
bvector_type * check_create_target()
Definition: bmaggregator.h:556
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:401
bool combine_and_sub(bvector_type &bv_target)
Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit r...
Definition: bmaggregator.h:617
Definition: bm.h:76
bool bit_block_or_3way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of s...
Definition: bmfunc.h:6032
bvector_type::blocks_manager_type blocks_manager_type
Definition: bmaggregator.h:333
pre-processor un-defines to avoid global space pollution (internal)
void combine_shift_right_and(bvector_type &bv_target)
Aggregate added group of vectors using SHIFT-RIGHT and logical AND Operation does NOT perform an expl...
Definition: bmaggregator.h:647
bool bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:5915
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1148
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
const unsigned id_max
Definition: bmconst.h:105
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
bool process_bit_blocks_or(blocks_manager_type &bman_target, unsigned i, unsigned j, unsigned block_count)
void reset()
Reset aggregate groups, forget all attached vectors.
Definition: bmaggregator.h:536
void aligned_free(void *ptr)
Aligned free.
Definition: bmalloc.h:429
void gap_and_to_bitset(unsigned *dest, const T *pcurr)
ANDs GAP block to bitblock.
Definition: bmfunc.h:3146
static unsigned resize_target(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size, bool init_clear=true)
bool any_carry_overs(unsigned co_size) const
unsigned int word_t
Definition: bmconst.h:38
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:140
bm::id64_t digest_type
Definition: bmaggregator.h:64
Algorithms for bvector<>
const bm::word_t * get_arg_block(const bvector_type_const_ptr *bv_src, unsigned k, unsigned i, unsigned j)
void set_optimization(typename bvector_type::optmode opt=bvector_type::opt_compress)
set on-the-fly bit-block compression By default aggregator does not try to optimize result...
Definition: bmaggregator.h:105
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start)
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:1012
const bvector_type * get_target() const
Definition: bmaggregator.h:326
Bit manipulation primitives (internal)
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1256
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value)
Bitblock memset operation.
Definition: bmfunc.h:3492
bm::id64_t update_block_digest0(const bm::word_t *const block, bm::id64_t digest)
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) ...
Definition: bmfunc.h:743
operation
Codes for aggregation operations which can be pipelined for efficient execution.
Definition: bmaggregator.h:76
const unsigned set_array_mask
Definition: bmconst.h:93
unsigned short gap_word_t
Definition: bmconst.h:76
digest_type process_bit_blocks_and(unsigned block_count, digest_type digest)
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:112
void process_gap_blocks_or(unsigned block_count)
void gap_sub_to_bitset(unsigned *dest, const T *pcurr)
SUB (AND NOT) GAP block to bitblock.
Definition: bmfunc.h:2985
BV::size_type size_type
Definition: bmaggregator.h:62
void block_init_digest0(bm::word_t *const block, bm::id64_t digest)
Init block with 000111000 pattren based on digest.
Definition: bmfunc.h:672
operation_status run_step(unsigned i, unsigned j)
Run a step of current arrgegation operation.
void set_operation(int op_code)
Set operation code for the aggregator.
Definition: bmaggregator.h:311
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:111
bool test_gap_blocks_and(unsigned block_count, unsigned bit_idx)
digest_type process_gap_blocks_and(unsigned block_count, digest_type digest)
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:135
Definitions(internal)
#define BM_ASSERT_THROW(x, xerrcode)
Definition: bmdef.h:388
bm::word_t * sort_input_blocks_and(const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count)
Algorithms for fast aggregation of a group of bit-vectors.
Definition: bmaggregator.h:58
void stage(bm::word_t *temp_block)
Prepare operation, create internal resources, analyse dependencies.
void combine_and_sub_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size)
Horizontal AND-SUB aggregation (potentially slower) method.
bm::id64_t bit_block_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
Definition: bmfunc.h:6182
void combine_and_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
Horizontal AND aggregation (potentially slower) method.
bool test_gap_blocks_sub(unsigned block_count, unsigned bit_idx)
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmaggregator.h:66
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1433
#define BM_IS_GAP(ptr)
Definition: bmdef.h:168
BMFORCEINLINE bm::id64_t digest_mask(unsigned from, unsigned to)
Compute digest mask for [from..to] positions.
Definition: bmfunc.h:634
static unsigned find_effective_sub_block_size(unsigned i, const bvector_type_const_ptr *bv_src, unsigned src_size, bool top_null_as_zero)
Definition: bmaggregator.h:893
void combine_or_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
Horizontal OR aggregation (potentially slower) method.
const unsigned set_block_mask
Definition: bmconst.h:56
unsigned bit_find_first(const bm::word_t *block, unsigned *first)
BIT block find the first set bit.
Definition: bmfunc.h:6711
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
Definition: bm.h:129
bool bit_block_shift_r1_and_unr(bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest)
Right bit-shift bitblock by 1 bit (reference) + AND.
Definition: bmfunc.h:4648
#define BMGAP_PTR(ptr)
Definition: bmdef.h:166
const unsigned set_word_mask
Definition: bmconst.h:71
bm::word_t * get_temp_block()
Definition: bmaggregator.h:328
operation_status get_operation_status() const
Definition: bmaggregator.h:324
const unsigned max_size
Definition: xsample01.cpp:56
bm::id64_t bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:5107
void set_range_hint(size_type from, size_type to)
Set search hint for the range, where results needs to be searched (experimental for internal use)...
Definition: bmaggregator.h:547
int get_operation() const
Get current operation code.
Definition: bmaggregator.h:308
#define BM_ASSERT
Definition: bmdef.h:117
bm::word_t * sort_input_blocks_or(const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count)
id64_t wordop_t
Definition: bmconst.h:125
bm::bvector bvector_type
bm::id64_t calc_block_digest0(const bm::word_t *const block)
Compute digest for 64 non-zero areas.
Definition: bmfunc.h:702
bool bit_find_first_if_1(const bm::word_t *block, unsigned *first, bm::id64_t digest)
BIT block find the first set bit if only 1 bit is set.
Definition: bmfunc.h:6781
static unsigned max_top_blocks(const bvector_type_const_ptr *bv_src, unsigned src_size)
bool is_bits_one(const bm::wordop_t *start)
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:4760
const unsigned set_block_shift
Definition: bmconst.h:55
bm::id_t block_to_global_index(unsigned i, unsigned j, unsigned block_idx)
calculate bvector<> global bit-index from block-local coords
Definition: bmfunc.h:7867
bm::id64_t bit_block_and_2way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest)
digest based bit-block AND
Definition: bmfunc.h:5267
const bvector_type * bvector_type_const_ptr
Definition: bmaggregator.h:63
digest_type process_gap_blocks_sub(unsigned block_count, digest_type digest)
bool find_first_and_sub(size_type &idx)
Definition: bmaggregator.h:637
bm::id64_t bit_block_and_5way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest)
digest based bit-block AND 5-way
Definition: bmfunc.h:5200
bool process_shift_right_and(const bm::word_t *arg_blk, digest_type &digest, unsigned carry_over)
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:136