BitMagic-C++
bmxor.h
Go to the documentation of this file.
1 #ifndef BMXORFUNC__H__INCLUDED__
2 #define BMXORFUNC__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2019 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 bmxor.h
22  \brief Functions and utilities for XOR filters (internal)
23 */
24 
25 #include "bmdef.h"
26 #include "bmutil.h"
27 
28 
29 namespace bm
30 {
31 
32 /*!
33  Function calculates number of times when bit value changed
34  @internal
35 */
36 inline
38  const bm::word_t* BMRESTRICT xor_block,
39  unsigned size) BMNOEXCEPT
40 {
41  unsigned gap_count = 1;
42 
43  bm::word_t w, w0, w_prev, w_l;
44  w = w0 = *block ^ *xor_block;
45 
46  const int w_shift = int(sizeof(w) * 8 - 1);
47  w ^= (w >> 1);
48  BM_INCWORD_BITCOUNT(gap_count, w);
49  gap_count -= (w_prev = (w0 >> w_shift)); // negative value correction
50 
51  const bm::word_t* block_end = block + size; // bm::set_block_size;
52  for (++block, ++xor_block; block < block_end; ++block, ++xor_block)
53  {
54  w = w0 = *block ^ *xor_block;
55  ++gap_count;
56  if (!w)
57  {
58  gap_count -= !w_prev;
59  w_prev = 0;
60  }
61  else
62  {
63  w ^= (w >> 1);
64  BM_INCWORD_BITCOUNT(gap_count, w);
65 
66  w_l = w0 & 1;
67  gap_count -= (w0 >> w_shift); // negative value correction
68  gap_count -= !(w_prev ^ w_l); // word border correction
69 
70  w_prev = (w0 >> w_shift);
71  }
72  } // for
73  return gap_count;
74 }
75 
76 /*!
77  Function calculates number of times when bit value changed
78  @internal
79 */
80 inline
82  const bm::word_t* BMRESTRICT xor_block,
83  unsigned size) BMNOEXCEPT
84 {
85 #ifdef VECT_BLOCK_XOR_CHANGE
86  return VECT_BLOCK_XOR_CHANGE(block, xor_block, size);
87 #else
88  return bit_block_xor_change32(block, xor_block, size);
89 #endif
90 }
91 
92 /**
93  Structure to compute XOR gap-count profile by sub-block waves
94 
95  @ingroup bitfunc
96  @internal
97 */
99 {
100  unsigned short sb_change[bm::block_waves];
102 };
103 
104 /**
105  Compute reference (non-XOR) 64-dim complexity descriptor for the
106  target block.
107 
108  Phase 1 of the XOR filtering process
109 
110  @internal
111 */
112 inline
114  const bm::word_t* BMRESTRICT block,
116 {
117  for (unsigned i = 0; i < bm::block_waves; ++i)
118  {
119  unsigned off = (i * bm::set_block_digest_wave_size);
120  const bm::word_t* sub_block = block + off;
121  #if defined(VECT_BLOCK_CHANGE)
122  unsigned change VECT_BLOCK_CHANGE(sub_block,
124  #else
125  unsigned change = bm::bit_block_change32(sub_block,
127  #endif
128  x_descr.sb_change[i] = (unsigned short) change;
129  } // for i
130 }
131 
132 
133 /**
134  Compute reference complexity descriptor based on XOR vector.
135  Returns the digest of sub-blocks where XOR filtering improved the metric
136  (function needs reference to estimate the improvement).
137 
138  part of Phase 2 of the XOR filtering process
139 
140  @sa compute_sub_block_complexity_descr
141 
142  @internal
143 */
144 inline
146  const bm::word_t* BMRESTRICT block,
147  const bm::word_t* BMRESTRICT xor_block,
149  unsigned& BMRESTRICT block_gain) BMNOEXCEPT
150 {
151  block_gain = 0; // approximate block gain (sum of sub-waves)
152  bm::id64_t digest = 0;
153  for (unsigned i = 0; i < bm::block_waves; ++i)
154  {
155  unsigned off = (i * bm::set_block_digest_wave_size);
156  const bm::word_t* sub_block = block + off;
157  const bm::word_t* xor_sub_block = xor_block + off;
158 
159  unsigned xor_change =
160  bm::bit_block_xor_change(sub_block, xor_sub_block,
162 
163  x_descr.sb_xor_change[i] = (unsigned short)xor_change;
164  if (xor_change <= 1)
165  {
166  digest |= (1ull << i);
167  block_gain += x_descr.sb_change[i];
168  }
169  else
170  {
171  if (xor_change < x_descr.sb_change[i]) // detected improvement
172  {
173  digest |= (1ull << i);
174  block_gain += (x_descr.sb_change[i] - xor_change);
175  }
176  }
177  } // for i
178  return digest;
179 }
180 
181 /**
182  Build partial XOR product of 2 bit-blocks using digest mask
183 
184  @param target_block - target := block ^ xor_block
185  @param block - arg1
186  @param xor_block - arg2
187  @param digest - mask for each block wave to XOR (1) or just copy (0)
188 
189  @internal
190 */
191 inline
192 void bit_block_xor(bm::word_t* target_block,
193  const bm::word_t* block, const bm::word_t* xor_block,
194  bm::id64_t digest) BMNOEXCEPT
195 {
196  BM_ASSERT(target_block);
197  BM_ASSERT(block);
198  BM_ASSERT(xor_block);
199  BM_ASSERT(digest);
200 
201 #ifdef VECT_BIT_BLOCK_XOR
202  VECT_BIT_BLOCK_XOR(target_block, block, xor_block, digest);
203 #else
204  for (unsigned i = 0; i < bm::block_waves; ++i)
205  {
206  const bm::id64_t mask = (1ull << i);
207 
208  unsigned off = (i * bm::set_block_digest_wave_size);
209  const bm::word_t* sub_block = block + off;
210  bm::word_t* t_sub_block = target_block + off;
211 
212  const bm::word_t* sub_block_end = sub_block + bm::set_block_digest_wave_size;
213 
214  if (digest & mask) // XOR filtered sub-block
215  {
216  const bm::word_t* xor_sub_block = xor_block + off;
217  for (; sub_block < sub_block_end; )
218  *t_sub_block++ = *sub_block++ ^ *xor_sub_block++;
219  }
220  else // just copy source
221  {
222  for (; sub_block < sub_block_end;)
223  *t_sub_block++ = *sub_block++;
224  }
225  } // for i
226 #endif
227 }
228 
229 
230 /**
231  List of reference bit-vectors with their true index associations
232 
233  Each referece vector would have two alternative indexes:
234  - index(position) in the reference list
235  - index(row) in the external bit-matrix (plain index)
236 
237  @internal
238 */
239 template<typename BV>
241 {
242 public:
243  typedef BV bvector_type;
248 public:
249 
250  /// reset the collection (resize(0))
251  void reset()
252  {
253  ref_bvects_.resize(0);
254  ref_bvects_rows_.resize(0);
255  }
256 
257  /**
258  Add reference vector
259  @param bv - bvector pointer
260  @param ref_idx - reference (row) index
261  */
262  void add(const bvector_type* bv, size_type ref_idx)
263  {
264  BM_ASSERT(bv);
265  ref_bvects_.push_back(bv);
266  ref_bvects_rows_.push_back(ref_idx);
267  }
268 
269  /// Get reference list size
270  size_type size() const BMNOEXCEPT { return (size_type)ref_bvects_.size(); }
271 
272  /// Get reference vector by the index in this ref-vector
274  { return ref_bvects_[idx]; }
275 
276  /// Get reference row index by the index in this ref-vector
278  { return (size_type)ref_bvects_rows_[idx]; }
279 
280  /// not-found value for find methods
281  static
283 
284  /// Find vector index by the reference index
285  /// @return ~0 if not found
286  size_type find(std::size_t ref_idx) const BMNOEXCEPT
287  {
288  size_type sz = size();
289  for (size_type i = 0; i < sz; ++i)
290  if (ref_idx == ref_bvects_rows_[i])
291  return i;
292  return not_found();
293  }
294 
295  /// build vector of references from a basic bit-matrix
296  /// all NULL rows are skipped, not added to the ref.vector
297  template<class BMATR>
298  void build(const BMATR& bmatr)
299  {
300  reset();
301  size_type rows = bmatr.rows();
302  for (size_type r = 0; r < rows; ++r)
303  {
304  bvector_type_const_ptr bv = bmatr.get_row(r);
305  if (bv)
306  add(bv, r);
307  } // for r
308  }
309 
310 protected:
311  typedef bm::heap_vector<bvector_type_const_ptr, bv_allocator_type, true> bvptr_vector_type;
312  typedef bm::heap_vector<std::size_t, bv_allocator_type, true> bv_plain_vector_type;
313 
314 protected:
315  bvptr_vector_type ref_bvects_; ///< reference vector pointers
316  bv_plain_vector_type ref_bvects_rows_; ///< reference vector row idxs
317 };
318 
319 // --------------------------------------------------------------------------
320 //
321 // --------------------------------------------------------------------------
322 
323 /**
324  XOR scanner to search for complement-similarities in
325  collections of bit-vectors
326 
327  @internal
328 */
329 template<typename BV>
331 {
332 public:
334  typedef BV bvector_type;
336 
337 public:
339  { ref_vect_ = ref_vect; }
340 
342  { return *ref_vect_; }
343 
344  /** Compute statistics for the anchor search vector
345  @param block - bit-block target
346  */
347  void compute_x_block_stats(const bm::word_t* block) BMNOEXCEPT;
348 
349  /** Scan for all candidate bit-blocks to find mask or match
350  @return true if XOR complement or matching vector found
351  */
352  bool search_best_xor_mask(const bm::word_t* block,
353  size_type ridx_from,
354  size_type ridx_to,
355  unsigned i, unsigned j,
356  bm::word_t* tb);
357 
358  /** Scan all candidate gap-blocks to find best XOR match
359  */
360  bool search_best_xor_gap(const bm::word_t* block,
361  size_type ridx_from,
362  size_type ridx_to,
363  unsigned i, unsigned j);
364 
365  /**
366  Validate serialization target
367  */
368  bool validate_found(bm::word_t* xor_block,
369  const bm::word_t* block) const BMNOEXCEPT;
370 
371  size_type found_ridx() const BMNOEXCEPT { return found_ridx_; }
373  { return found_block_xor_; }
374  unsigned get_x_best_metric() const BMNOEXCEPT { return x_best_metric_; }
375  bm::id64_t get_xor_digest() const BMNOEXCEPT { return x_d64_; }
376 
377  /// true if completely identical vector found
378  bool is_eq_found() const BMNOEXCEPT { return !x_best_metric_; }
379 
380 
381  unsigned get_x_bc() const BMNOEXCEPT { return x_bc_; }
382  unsigned get_x_gc() const BMNOEXCEPT { return x_gc_; }
383  unsigned get_x_block_best() const BMNOEXCEPT
384  { return x_block_best_metric_; }
385 
386 
388 
389 private:
390  const bv_ref_vector_type* ref_vect_ = 0; ///< ref.vect for XOR filter
391 
392  // target x-block related statistics
393  //
394  bm::block_waves_xor_descr x_descr_; ///< XOR desriptor
395  unsigned x_bc_; ///< bitcount
396  unsigned x_gc_; ///< gap count
397  unsigned x_best_metric_; /// dynamic min(gc, bc)
398  unsigned x_block_best_metric_; ///< min(gc, bc) initial
399 
400  // scan related metrics
401  bm::id64_t x_d64_; ///< search digest
402  size_type found_ridx_; ///< match vector (in references)
403  const bm::word_t* found_block_xor_;
404 };
405 
406 // --------------------------------------------------------------------------
407 //
408 // --------------------------------------------------------------------------
409 
410 template<typename BV>
412 {
413  BM_ASSERT(IS_VALID_ADDR(block));
414  BM_ASSERT(!BM_IS_GAP(block));
415  BM_ASSERT(ref_vect_->size() > 0);
416 
417  bm::compute_complexity_descr(block, x_descr_);
418  bm::bit_block_change_bc(block, &x_gc_, &x_bc_);
419  x_block_best_metric_ = x_best_metric_ = x_gc_ < x_bc_ ? x_gc_ : x_bc_;
420 }
421 
422 // --------------------------------------------------------------------------
423 
424 template<typename BV>
426  size_type ridx_from,
427  size_type ridx_to,
428  unsigned i, unsigned j,
429  bm::word_t* tb)
430 {
431  BM_ASSERT(ridx_from <= ridx_to);
432  BM_ASSERT(IS_VALID_ADDR(block));
433  BM_ASSERT(!BM_IS_GAP(block));
434  BM_ASSERT(tb);
435 
436  if (ridx_to > ref_vect_->size())
437  ridx_to = ref_vect_->size();
438 
439  bool kb_found = false;
440  bm::id64_t d64 = 0;
441  found_block_xor_ = 0;
442 
443  unsigned best_block_gain = 0;
444  int best_ri = -1;
445 
446  for (size_type ri = ridx_from; ri < ridx_to; ++ri)
447  {
448  const bvector_type* bv = ref_vect_->get_bv(ri);
449  BM_ASSERT(bv);
450  const typename bvector_type::blocks_manager_type& bman =
451  bv->get_blocks_manager();
452  const bm::word_t* block_xor = bman.get_block_ptr(i, j);
453  if (!IS_VALID_ADDR(block_xor) || BM_IS_GAP(block_xor))
454  continue;
455 
456  BM_ASSERT(block != block_xor);
457 
458  unsigned block_gain = 0;
459 
460  bm::id64_t xor_d64 =
461  bm::compute_xor_complexity_descr(block, block_xor, x_descr_, block_gain);
462  if (xor_d64) // candidate XOR block
463  {
464  if (block_gain > best_block_gain)
465  {
466  best_block_gain = block_gain;
467  best_ri = int(ri);
468  d64 = xor_d64;
469  }
470  }
471  } // for ri
472 
473  if (best_ri != -1) // found some gain
474  {
475  unsigned xor_bc, xor_gc;
476  const bvector_type* bv = ref_vect_->get_bv(size_type(best_ri));
477  const typename bvector_type::blocks_manager_type& bman = bv->get_blocks_manager();
478  const bm::word_t* block_xor = bman.get_block_ptr(i, j);
479 
480  bm::bit_block_xor(tb, block, block_xor, d64);
481  bm::bit_block_change_bc(tb, &xor_gc, &xor_bc);
482 
483  if (xor_gc < x_best_metric_ && xor_gc < bm::bie_cut_off)
484  {
485  x_best_metric_ = xor_gc;
486  kb_found = true;
487  found_ridx_ = size_type(best_ri);
488  found_block_xor_ = block_xor;
489  }
490  if (xor_bc < x_best_metric_ && xor_bc < bm::bie_cut_off)
491  {
492  x_best_metric_ = xor_bc;
493  kb_found = true;
494  found_ridx_ = size_type(best_ri);
495  found_block_xor_ = block_xor;
496  if (!xor_bc) // completely identical block?
497  {
498  unsigned pos;
499  bool f = bm::bit_find_first_diff(block, block_xor, &pos);
500  x_best_metric_ += f;
501  }
502  }
503  }
504 
505  x_d64_ = d64;
506  return kb_found;
507 }
508 
509 // --------------------------------------------------------------------------
510 
511 template<typename BV>
513  size_type ridx_from,
514  size_type ridx_to,
515  unsigned i, unsigned j)
516 {
517  BM_ASSERT(ridx_from <= ridx_to);
518  BM_ASSERT(BM_IS_GAP(block));
519 
520  if (ridx_to > ref_vect_->size())
521  ridx_to = ref_vect_->size();
522 
523  const bm::gap_word_t* gap_block = BMGAP_PTR(block);
524  unsigned gap_len = bm::gap_length(gap_block);
525  if (gap_len <= 3)
526  return false;
527  unsigned best_gap_len = gap_len;
528  bool kb_found = false;
529 
530  for (size_type ri = ridx_from; ri < ridx_to; ++ri)
531  {
532  const bvector_type* bv = ref_vect_->get_bv(ri);
533  BM_ASSERT(bv);
534  const typename bvector_type::blocks_manager_type& bman = bv->get_blocks_manager();
535  const bm::word_t* block_xor = bman.get_block_ptr(i, j);
536  if (!IS_VALID_ADDR(block_xor))
537  continue;
538  if (!BM_IS_GAP(block_xor))
539  continue;
540 
541  const bm::gap_word_t* gap_xor_block = BMGAP_PTR(block_xor);
542  unsigned gap_xor_len = bm::gap_length(gap_block);
543  if (gap_xor_len <= 3)
544  continue;
545 
546  BM_ASSERT(block != block_xor);
547 
548  unsigned res_len;
549  bool f = bm::gap_operation_dry_xor(gap_block, gap_xor_block, res_len, best_gap_len);
550  if (f && (res_len < best_gap_len))
551  {
552  best_gap_len = res_len;
553  kb_found = true;
554  found_ridx_ = ri;
555  found_block_xor_ = (const bm::word_t*)gap_xor_block;
556  }
557 
558  } // for ri
559 
560  return kb_found;
561 }
562 
563 // --------------------------------------------------------------------------
564 
565 template<typename BV>
567  const bm::word_t* block) const BMNOEXCEPT
568 {
569  bm::id64_t d64 = get_xor_digest();
570  BM_ASSERT(d64);
571  const bm::word_t* key_block = get_found_block();
572  bm::bit_block_xor(xor_block, block, key_block, d64);
573 
574  unsigned bc, gc;
575  bm::bit_block_change_bc(xor_block, &gc, &bc);
576  unsigned xor_best_metric = gc < bc ? gc : bc;
577  if (xor_best_metric < get_x_block_best())
578  {
579  unsigned gain = get_x_block_best() - xor_best_metric;
580  gain *= 4; // take 4 as bit estimate for BIC
581  // gain should be greater than overhead for storing
582  // reference data: xor token, digest-64, block idx
583  unsigned gain_min = unsigned (sizeof(char) + sizeof(bm::id64_t) + sizeof(unsigned));
584  gain_min *= 8; // in bits
585  if (gain > gain_min)
586  {
587  BM_ASSERT(xor_best_metric < bm::bie_cut_off);
588  return true;
589  }
590  }
591  return false;
592 }
593 
594 // --------------------------------------------------------------------------
595 
596 } // namespace bm
597 
598 #endif
bm::bv_ref_vector::size_type
bvector_type::size_type size_type
Definition: bmxor.h:244
bm::bit_block_xor_change
unsigned bit_block_xor_change(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size) BMNOEXCEPT
Definition: bmxor.h:81
bm::bit_block_change_bc
void bit_block_change_bc(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
Definition: bmfunc.h:4581
BM_IS_GAP
#define BM_IS_GAP(ptr)
Definition: bmdef.h:181
VECT_BIT_BLOCK_XOR
#define VECT_BIT_BLOCK_XOR(t, src, src_xor, d)
Definition: bmsse4.h:1832
bm::xor_scanner::get_x_block_best
unsigned get_x_block_best() const BMNOEXCEPT
Definition: bmxor.h:383
bm::bit_block_change32
unsigned bit_block_change32(const bm::word_t *block, unsigned size) BMNOEXCEPT
Definition: bmfunc.h:4533
bm::xor_scanner::search_best_xor_mask
bool search_best_xor_mask(const bm::word_t *block, size_type ridx_from, size_type ridx_to, unsigned i, unsigned j, bm::word_t *tb)
Scan for all candidate bit-blocks to find mask or match.
Definition: bmxor.h:425
BMGAP_PTR
#define BMGAP_PTR(ptr)
Definition: bmdef.h:179
BM_INCWORD_BITCOUNT
#define BM_INCWORD_BITCOUNT(cnt, w)
Definition: bmdef.h:386
VECT_BLOCK_XOR_CHANGE
#define VECT_BLOCK_XOR_CHANGE(block, xor_block, size)
Definition: bmsse4.h:1818
bm::id64_t
unsigned long long int id64_t
Definition: bmconst.h:34
bm::xor_scanner::get_x_gc
unsigned get_x_gc() const BMNOEXCEPT
Definition: bmxor.h:382
bm::bv_ref_vector::ref_bvects_
bvptr_vector_type ref_bvects_
reference vector pointers
Definition: bmxor.h:315
bm::bv_ref_vector::find
size_type find(std::size_t ref_idx) const BMNOEXCEPT
Find vector index by the reference index.
Definition: bmxor.h:286
bm::bvector::allocator_type
Alloc allocator_type
Definition: bm.h:110
bm::xor_scanner::get_ref_vector
const bv_ref_vector_type & get_ref_vector() const BMNOEXCEPT
Definition: bmxor.h:341
bm::xor_scanner::set_ref_vector
void set_ref_vector(const bv_ref_vector_type *ref_vect) BMNOEXCEPT
Definition: bmxor.h:338
bm::block_waves_xor_descr
Structure to compute XOR gap-count profile by sub-block waves.
Definition: bmxor.h:98
bm::bv_ref_vector::bvector_type_const_ptr
const typedef bvector_type * bvector_type_const_ptr
Definition: bmxor.h:246
bm::bv_ref_vector::not_found
static size_type not_found() BMNOEXCEPT
not-found value for find methods
Definition: bmxor.h:282
bm::bv_ref_vector::get_bv
const bvector_type * get_bv(size_type idx) const BMNOEXCEPT
Get reference vector by the index in this ref-vector.
Definition: bmxor.h:273
bm::xor_scanner::get_x_bc
unsigned get_x_bc() const BMNOEXCEPT
Definition: bmxor.h:381
bm::xor_scanner::bv_ref_vector_type
bm::bv_ref_vector< BV > bv_ref_vector_type
Definition: bmxor.h:333
bm::gap_operation_dry_xor
bool gap_operation_dry_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, unsigned &dsize, unsigned limit) BMNOEXCEPT
Definition: bmfunc.h:5725
bm::xor_scanner::compute_x_block_stats
void compute_x_block_stats(const bm::word_t *block) BMNOEXCEPT
Compute statistics for the anchor search vector.
Definition: bmxor.h:411
bm::bv_ref_vector::add
void add(const bvector_type *bv, size_type ref_idx)
Add reference vector.
Definition: bmxor.h:262
bm::xor_scanner
XOR scanner to search for complement-similarities in collections of bit-vectors.
Definition: bmxor.h:330
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
bm::set_block_digest_wave_size
const unsigned set_block_digest_wave_size
Definition: bmconst.h:66
bm::xor_scanner::found_ridx
size_type found_ridx() const BMNOEXCEPT
Definition: bmxor.h:371
bm::gap_word_t
unsigned short gap_word_t
Definition: bmconst.h:77
bm::block_waves
const unsigned block_waves
Definition: bmconst.h:65
bm::bv_ref_vector::build
void build(const BMATR &bmatr)
build vector of references from a basic bit-matrix all NULL rows are skipped, not added to the ref....
Definition: bmxor.h:298
bm::block_waves_xor_descr::sb_xor_change
unsigned short sb_xor_change[bm::block_waves]
Definition: bmxor.h:101
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::bie_cut_off
const unsigned bie_cut_off
Definition: bmconst.h:87
bm::bv_ref_vector::size
size_type size() const BMNOEXCEPT
Get reference list size.
Definition: bmxor.h:270
bmdef.h
Definitions(internal)
bm::xor_scanner::validate_found
bool validate_found(bm::word_t *xor_block, const bm::word_t *block) const BMNOEXCEPT
Validate serialization target.
Definition: bmxor.h:566
VECT_BLOCK_CHANGE
#define VECT_BLOCK_CHANGE(block, size)
Definition: bmsse4.h:1815
IS_VALID_ADDR
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:152
bm::compute_complexity_descr
void compute_complexity_descr(const bm::word_t *BMRESTRICT block, block_waves_xor_descr &BMRESTRICT x_descr) BMNOEXCEPT
Compute reference (non-XOR) 64-dim complexity descriptor for the target block.
Definition: bmxor.h:113
bm::xor_scanner::get_descr
bm::block_waves_xor_descr & get_descr() BMNOEXCEPT
Definition: bmxor.h:387
bmutil.h
Bit manipulation primitives (internal)
bm::bv_ref_vector::bvector_type
BV bvector_type
Definition: bmxor.h:243
bm::xor_scanner::size_type
bvector_type::size_type size_type
Definition: bmxor.h:335
bm::bv_ref_vector::bv_plain_vector_type
bm::heap_vector< std::size_t, bv_allocator_type, true > bv_plain_vector_type
Definition: bmxor.h:312
bm::bit_block_xor_change32
unsigned bit_block_xor_change32(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size) BMNOEXCEPT
Definition: bmxor.h:37
bm
Definition: bm.h:76
bm::bv_ref_vector::bv_allocator_type
bvector_type::allocator_type bv_allocator_type
Definition: bmxor.h:247
bm::xor_scanner::get_x_best_metric
unsigned get_x_best_metric() const BMNOEXCEPT
Definition: bmxor.h:374
bm::bit_find_first_diff
bool bit_find_first_diff(const bm::word_t *BMRESTRICT blk1, const bm::word_t *BMRESTRICT blk2, unsigned *BMRESTRICT pos) BMNOEXCEPT
Find first bit which is different between two bit-blocks.
Definition: bmfunc.h:4106
bm::compute_xor_complexity_descr
bm::id64_t compute_xor_complexity_descr(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, block_waves_xor_descr &BMRESTRICT x_descr, unsigned &BMRESTRICT block_gain) BMNOEXCEPT
Compute reference complexity descriptor based on XOR vector.
Definition: bmxor.h:145
bm::xor_scanner::get_xor_digest
bm::id64_t get_xor_digest() const BMNOEXCEPT
Definition: bmxor.h:375
bm::bv_ref_vector::get_row_idx
size_type get_row_idx(size_type idx) const BMNOEXCEPT
Get reference row index by the index in this ref-vector.
Definition: bmxor.h:277
bm::bit_block_xor
bm::id64_t bit_block_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:7240
bm::bv_ref_vector::ref_bvects_rows_
bv_plain_vector_type ref_bvects_rows_
reference vector row idxs
Definition: bmxor.h:316
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
bm::bvector::blocks_manager_type
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:112
BMRESTRICT
#define BMRESTRICT
Definition: bmdef.h:193
bm::gap_length
BMFORCEINLINE bm::gap_word_t gap_length(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Returs GAP block length.
Definition: bmfunc.h:1098
bm::bvector::size_type
bm::id_t size_type
Definition: bm.h:117
bm::xor_scanner::get_found_block
const bm::word_t * get_found_block() const BMNOEXCEPT
Definition: bmxor.h:372
bm::bv_ref_vector::reset
void reset()
reset the collection (resize(0))
Definition: bmxor.h:251
bm::xor_scanner::bvector_type
BV bvector_type
Definition: bmxor.h:334
bm::bv_ref_vector::bvector_type_ptr
bvector_type * bvector_type_ptr
Definition: bmxor.h:245
bm::xor_scanner::search_best_xor_gap
bool search_best_xor_gap(const bm::word_t *block, size_type ridx_from, size_type ridx_to, unsigned i, unsigned j)
Scan all candidate gap-blocks to find best XOR match.
Definition: bmxor.h:512
bm::xor_scanner::is_eq_found
bool is_eq_found() const BMNOEXCEPT
true if completely identical vector found
Definition: bmxor.h:378
bm::block_waves_xor_descr::sb_change
unsigned short sb_change[bm::block_waves]
Definition: bmxor.h:100
bm::bv_ref_vector::bvptr_vector_type
bm::heap_vector< bvector_type_const_ptr, bv_allocator_type, true > bvptr_vector_type
Definition: bmxor.h:311
bm::bv_ref_vector
List of reference bit-vectors with their true index associations.
Definition: bmxor.h:240