1#ifndef BMXORFUNC__H__INCLUDED__
2#define BMXORFUNC__H__INCLUDED__
41 unsigned gap_count = 1;
44 w = w0 = *block ^ *xor_block;
46 const int w_shift = int(
sizeof(w) * 8 - 1);
49 gap_count -= (w_prev = (w0 >> w_shift));
52 for (++block, ++xor_block; block < block_end; ++block, ++xor_block)
54 w = w0 = *block ^ *xor_block;
67 gap_count -= (w0 >> w_shift);
68 gap_count -= !(w_prev ^ w_l);
70 w_prev = (w0 >> w_shift);
85#ifdef VECT_BLOCK_XOR_CHANGE
121 #if defined(VECT_BLOCK_CHANGE)
128 x_descr.sb_change[i] = (
unsigned short) change;
157 const bm::word_t* xor_sub_block = xor_block + off;
159 unsigned xor_change =
163 x_descr.sb_xor_change[i] = (
unsigned short)xor_change;
166 digest |= (1ull << i);
167 block_gain += x_descr.sb_change[i];
171 if (xor_change < x_descr.sb_change[i])
173 digest |= (1ull << i);
174 block_gain += (x_descr.sb_change[i] - xor_change);
201#ifdef VECT_BIT_BLOCK_XOR
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++;
222 for (; sub_block < sub_block_end;)
223 *t_sub_block++ = *sub_block++;
297 template<
class BMATR>
339 { ref_vect_ = ref_vect; }
342 {
return *ref_vect_; }
355 unsigned i,
unsigned j,
363 unsigned i,
unsigned j);
373 {
return found_block_xor_; }
384 {
return x_block_best_metric_; }
397 unsigned x_best_metric_;
398 unsigned x_block_best_metric_;
419 x_block_best_metric_ = x_best_metric_ = x_gc_ < x_bc_ ? x_gc_ : x_bc_;
428 unsigned i,
unsigned j,
436 if (ridx_to > ref_vect_->size())
437 ridx_to = ref_vect_->size();
439 bool kb_found =
false;
441 found_block_xor_ = 0;
443 unsigned best_block_gain = 0;
446 for (
size_type ri = ridx_from; ri < ridx_to; ++ri)
451 bv->get_blocks_manager();
452 const bm::word_t* block_xor = bman.get_block_ptr(i, j);
458 unsigned block_gain = 0;
464 if (block_gain > best_block_gain)
466 best_block_gain = block_gain;
475 unsigned xor_bc, xor_gc;
478 const bm::word_t* block_xor = bman.get_block_ptr(i, j);
485 x_best_metric_ = xor_gc;
488 found_block_xor_ = block_xor;
492 x_best_metric_ = xor_bc;
495 found_block_xor_ = block_xor;
515 unsigned i,
unsigned j)
520 if (ridx_to > ref_vect_->size())
521 ridx_to = ref_vect_->size();
527 unsigned best_gap_len = gap_len;
528 bool kb_found =
false;
530 for (
size_type ri = ridx_from; ri < ridx_to; ++ri)
535 const bm::word_t* block_xor = bman.get_block_ptr(i, j);
543 if (gap_xor_len <= 3)
550 if (f && (res_len < best_gap_len))
552 best_gap_len = res_len;
555 found_block_xor_ = (
const bm::word_t*)gap_xor_block;
571 const bm::word_t* key_block = get_found_block();
576 unsigned xor_best_metric = gc < bc ? gc : bc;
577 if (xor_best_metric < get_x_block_best())
579 unsigned gain = get_x_block_best() - xor_best_metric;
583 unsigned gain_min = unsigned (
sizeof(
char) +
sizeof(
bm::id64_t) +
sizeof(
unsigned));
#define IS_VALID_ADDR(addr)
#define VECT_BIT_BLOCK_XOR(t, src, src_xor, d)
#define VECT_BLOCK_CHANGE(block, size)
#define VECT_BLOCK_XOR_CHANGE(block, xor_block, size)
Bit manipulation primitives (internal)
List of reference bit-vectors with their true index associations.
bvector_type::size_type size_type
bm::heap_vector< std::size_t, bv_allocator_type, true > bv_plain_vector_type
size_type size() const BMNOEXCEPT
Get reference list size.
static size_type not_found() BMNOEXCEPT
not-found value for find methods
bvector_type * bvector_type_ptr
const bvector_type * bvector_type_const_ptr
void add(const bvector_type *bv, size_type ref_idx)
Add reference vector.
bv_plain_vector_type ref_bvects_rows_
reference vector row idxs
const bvector_type * get_bv(size_type idx) const BMNOEXCEPT
Get reference vector by the index in this ref-vector.
size_type get_row_idx(size_type idx) const BMNOEXCEPT
Get reference row index by the index in this ref-vector.
void reset()
reset the collection (resize(0))
void build(const BMATR &bmatr)
build vector of references from a basic bit-matrix all NULL rows are skipped, not added to the ref....
size_type find(std::size_t ref_idx) const BMNOEXCEPT
Find vector index by the reference index.
bm::heap_vector< bvector_type_const_ptr, bv_allocator_type, true > bvptr_vector_type
bvector_type::allocator_type bv_allocator_type
bvptr_vector_type ref_bvects_
reference vector pointers
blocks_manager< Alloc > blocks_manager_type
XOR scanner to search for complement-similarities in collections of bit-vectors.
bm::bv_ref_vector< BV > bv_ref_vector_type
bvector_type::size_type size_type
bool validate_found(bm::word_t *xor_block, const bm::word_t *block) const BMNOEXCEPT
Validate serialization target.
unsigned get_x_block_best() const BMNOEXCEPT
unsigned get_x_best_metric() const BMNOEXCEPT
unsigned get_x_gc() const BMNOEXCEPT
bool is_eq_found() const BMNOEXCEPT
true if completely identical vector found
bm::id64_t get_xor_digest() const BMNOEXCEPT
unsigned get_x_bc() const BMNOEXCEPT
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.
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.
const bm::word_t * get_found_block() const BMNOEXCEPT
size_type found_ridx() const BMNOEXCEPT
void set_ref_vector(const bv_ref_vector_type *ref_vect) BMNOEXCEPT
bm::block_waves_xor_descr & get_descr() BMNOEXCEPT
const bv_ref_vector_type & get_ref_vector() const BMNOEXCEPT
void compute_x_block_stats(const bm::word_t *block) BMNOEXCEPT
Compute statistics for the anchor search vector.
#define BM_INCWORD_BITCOUNT(cnt, w)
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.
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...
bool gap_operation_dry_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, unsigned &dsize, unsigned limit) BMNOEXCEPT
BMFORCEINLINE bm::gap_word_t gap_length(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Returs GAP block length.
const unsigned set_block_digest_wave_size
void bit_block_change_bc(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
unsigned bit_block_xor_change(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size) BMNOEXCEPT
unsigned bit_block_change32(const bm::word_t *block, unsigned size) BMNOEXCEPT
const unsigned bie_cut_off
unsigned bit_block_xor_change32(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size) BMNOEXCEPT
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.
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.
unsigned long long int id64_t
const unsigned block_waves
unsigned short gap_word_t
Structure to compute XOR gap-count profile by sub-block waves.
unsigned short sb_change[bm::block_waves]
unsigned short sb_xor_change[bm::block_waves]