bm::xor_scanner< BV > Class Template Reference

XOR scanner to search for complement-similarities in collections of bit-vectors. More...

`#include <bmxor.h>`

## Public Types

typedef bm::bv_ref_vector< BV > | bv_ref_vector_type
typedef BV | bvector_type
typedef bvector_type::allocator_type | bv_allocator_type
typedef bvector_type::size_type | size_type
typedef bm::heap_vector< bm::block_xor_match_descr, bv_allocator_type, true > | xor_matches_vector_type
typedef bm::heap_vector< bm::match_pair, bv_allocator_type, true > | match_pairs_vector_type
typedef bv_ref_vector_type::matrix_chain_type | matrix_chain_type
typedef bm::heap_vector< bm::word_t *, bv_allocator_type, true > | bv_blocks_vector_type
typedef bm::heap_vector< unsigned, bv_allocator_type, true > | bv_bcgc_vector_type
typedef bm::heap_vector< bm::block_waves_xor_descr, bv_allocator_type, true > | bv_xdescr_vector_type

## Public Member Functions

| xor_scanner ()
| ~xor_scanner ()
void | set_ref_vector (const bv_ref_vector_type *ref_vect) BMNOEXCEPT
const bv_ref_vector_type & | get_ref_vector () const BMNOEXCEPT
void | get_s_block_stats (size_type ri) BMNOEXCEPT
| Get statistics for the r-(or s-) block.
void | compute_s_block_stats (const bm::word_t *block) BMNOEXCEPT
| Compute statistics for the r-(or s-) block.
bm::xor_complement_match | search_best_xor_mask (const bm::word_t *s_block, size_type ri, size_type ridx_from, size_type ridx_to, unsigned i, unsigned j, bm::word_t *tx_block, const bm::xor_sim_params &params)
| Scan for all candidate bit-blocks to find mask or match.
size_type | refine_match_chain ()
| Run a search to add possible XOR match chain additions.
void | apply_xor_match_vector (bm::word_t *target_xor_block, const bm::word_t *s_block, size_type s_ri, const match_pairs_vector_type &pm_vect, unsigned i, unsigned j) const BMNOEXCEPT
| XOR all match blocks to target using their digest masks.
bool | compute_sim_model (xor_sim_model< BV > &sim_model, const bv_ref_vector_type &ref_vect, const bm::xor_sim_params &params)
| Calculate matrix of best XOR match metrics per block for the attached collection of bit-vectors.
bool | compute_sim_model (xor_sim_model< BV > &sim_model, const bm::xor_sim_params &params)
| Calculate matrix of best XOR match metrics per block for the attached collection of bit-vectors.
void | compute_sim_model (typename xor_sim_model< BV >::matrix_chain_type &sim_model_matr, size_type nb, size_type nb_rank, const bm::xor_sim_params &params)
| Compute similarity model for block.
void | compute_xor_complexity_descr (const bm::word_t *BMRESTRICT block, bm::id64_t block_d64, const bm::word_t *BMRESTRICT xor_block, bm::block_waves_xor_descr &BMRESTRICT x_descr, bm::block_xor_match_descr &BMRESTRICT xmd) const BMNOEXCEPT
| Compute reference complexity descriptor based on XOR vector.
bool | validate_xor (const bm::word_t *xor_block) const BMNOEXCEPT
| Check if XOR transform simplified block enough for compressibility objective.
size_type | found_ridx () const BMNOEXCEPT
bm::xor_complement_match | get_best_match_type () const BMNOEXCEPT
| Return best match type of a found block.
const bm::word_t * | get_found_block () const BMNOEXCEPT
unsigned | get_x_best_metric () const BMNOEXCEPT
bm::id64_t | get_xor_digest () const BMNOEXCEPT
unsigned | get_s_bc () const BMNOEXCEPT
unsigned | get_s_gc () const BMNOEXCEPT
unsigned | get_s_block_best () const BMNOEXCEPT
bm::block_waves_xor_descr & | get_descr () BMNOEXCEPT
xor_matches_vector_type & | get_match_vector () BMNOEXCEPT
match_pairs_vector_type & | get_match_pairs () BMNOEXCEPT
const bm::word_t * | get_ref_block (size_type ri, unsigned i, unsigned j) const BMNOEXCEPT
| Return block from the reference vector [vect_idx, block_i, block_j].
void | sync_nb_vect ()
| Sync TEMP vector size.

## Static Public Member Functions

static bm::xor_complement_match | best_metric (unsigned bc, unsigned gc, unsigned *best_metric) BMNOEXCEPT

## Protected Member Functions

void | deoptimize_gap_blocks (size_type nb, const xor_sim_params &params)
| Deoptimize vertical slice of GAP blocks.
void | free_blocks () BMNOEXCEPT
| Free the collection of temp blocks.

## Detailed Description

template<typename BV>
class bm::xor_scanner< BV >

XOR scanner to search for complement-similarities in collections of bit-vectors.

Definition at line 819 of file bmxor.h.

## Member Typedef Documentation

## bv_allocator_type

template<typename BV>

typedef bvector_type::allocator_type bm::xor_scanner< BV >::bv_allocator_type

Definition at line 824 of file bmxor.h.

## bv_bcgc_vector_type

template<typename BV>

typedef bm::heap_vector<unsigned, bv_allocator_type, true> bm::xor_scanner< BV >::bv_bcgc_vector_type

Definition at line 836 of file bmxor.h.

## bv_blocks_vector_type

template<typename BV>

typedef bm::heap_vector<bm::word_t*, bv_allocator_type, true> bm::xor_scanner< BV >::bv_blocks_vector_type

Definition at line 834 of file bmxor.h.

## bv_ref_vector_type

template<typename BV>

typedef bm::bv_ref_vector<BV> bm::xor_scanner< BV >::bv_ref_vector_type

Definition at line 822 of file bmxor.h.

## bv_xdescr_vector_type

template<typename BV>

typedef bm::heap_vector<bm::block_waves_xor_descr, bv_allocator_type, true> bm::xor_scanner< BV >::bv_xdescr_vector_type

Definition at line 839 of file bmxor.h.

## bvector_type

template<typename BV>

typedef BV bm::xor_scanner< BV >::bvector_type

Definition at line 823 of file bmxor.h.

## match_pairs_vector_type

template<typename BV>

typedef bm::heap_vector<bm::match_pair, bv_allocator_type, true> bm::xor_scanner< BV >::match_pairs_vector_type

Definition at line 830 of file bmxor.h.

## matrix_chain_type

template<typename BV>

typedef bv_ref_vector_type::matrix_chain_type bm::xor_scanner< BV >::matrix_chain_type

Definition at line 832 of file bmxor.h.

## size_type

template<typename BV>

typedef bvector_type::size_type bm::xor_scanner< BV >::size_type

Definition at line 825 of file bmxor.h.

## xor_matches_vector_type

template<typename BV>

typedef bm::heap_vector<bm::block_xor_match_descr, bv_allocator_type, true> bm::xor_scanner< BV >::xor_matches_vector_type

Definition at line 828 of file bmxor.h.

## Constructor & Destructor Documentation

## xor_scanner()

template<typename BV>

bm::xor_scanner< BV >::xor_scanner | ( |  | ) |

inline

Definition at line 843 of file bmxor.h.

Referenced by get_s_block_stats().

## ~xor_scanner()

template<typename BV>

bm::xor_scanner< BV >::~xor_scanner | ( |  | ) |

inline

Definition at line 844 of file bmxor.h.

References free_blocks().

## Member Function Documentation

## apply_xor_match_vector()

template<typename BV>

void bm::xor_scanner< BV >::apply_xor_match_vector | ( | bm::word_t * | target_xor_block,
|  | const bm::word_t * | s_block,
|  | size_type | s_ri,
|  | const match_pairs_vector_type & | pm_vect,
|  | unsigned | i,
|  | unsigned | j ) const

XOR all match blocks to target using their digest masks.

Definition at line 1607 of file bmxor.h.

References bm::bit_block_xor(), BM_ASSERT, BM_IS_GAP, BMNOEXCEPT, get_ref_block(), bm::match_pair::ref_idx, and bm::match_pair::xor_d64.

Referenced by compute_sim_model().

## best_metric()

template<typename BV>

bm::xor_complement_match bm::xor_scanner< BV >::best_metric | ( | unsigned | bc,
|  | unsigned | gc,
|  | unsigned * | best_metric )

static

Definition at line 1641 of file bmxor.h.

References best_metric(), BM_ASSERT, BMNOEXCEPT, bm::e_xor_match_BC, bm::e_xor_match_GC, bm::e_xor_match_iBC, and bm::gap_max_bits.

Referenced by best_metric(), compute_s_block_stats(), compute_sim_model(), compute_xor_complexity_descr(), get_s_block_stats(), and search_best_xor_mask().

## compute_s_block_stats()

template<typename BV>

void bm::xor_scanner< BV >::compute_s_block_stats | ( | const bm::word_t * | block | ) |

Compute statistics for the r-(or s-) block.

Parameters

  block | - bit-block target

Definition at line 1057 of file bmxor.h.

References best_metric(), BM_ASSERT, BM_IS_GAP, BMNOEXCEPT, bm::compute_s_block_descr(), and IS_VALID_ADDR.

## compute_sim_model() [1/3]

template<typename BV>

void bm::xor_scanner< BV >::compute_sim_model | ( | typename xor_sim_model< BV >::matrix_chain_type & | sim_model_matr,
|  | size_type | nb,
|  | size_type | nb_rank,
|  | const bm::xor_sim_params & | params )

Compute similarity model for block.

Definition at line 1479 of file bmxor.h.

References apply_xor_match_vector(), best_metric(), bm::bit_block_change_bc(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::block_match_chain< BLOCK_IDX >::chain_size, deoptimize_gap_blocks(), bm::e_no_xor_match, bm::e_xor_match_EQ, found_ridx(), bm::gap_length(), bm::gap_max_bits, bm::get_block_coord(), get_match_pairs(), get_ref_block(), get_s_block_best(), get_s_block_stats(), get_xor_digest(), IS_VALID_ADDR, bm::block_match_chain< BLOCK_IDX >::match, bm::xor_sim_params::min_gaps, bm::block_match_chain< BLOCK_IDX >::nb, bm::block_match_chain< BLOCK_IDX >::ref_idx, bm::match_pair::ref_idx, refine_match_chain(), search_best_xor_mask(), bm::block_match_chain< BLOCK_IDX >::xor_d64, and bm::match_pair::xor_d64.

## compute_sim_model() [2/3]

template<typename BV>

bool bm::xor_scanner< BV >::compute_sim_model | ( | bm::xor_sim_model< BV > & | sim_model,
|  | const bm::xor_sim_params & | params )

Calculate matrix of best XOR match metrics per block for the attached collection of bit-vectors.

Returns
  true if computed successfully

Definition at line 1454 of file bmxor.h.

References BM_ASSERT, bm::xor_sim_model< BV >::bv_blocks, compute_sim_model(), bm::xor_sim_model< BV >::matr, sync_nb_vect(), and bm::bvector< Alloc >::iterator_base::valid().

## compute_sim_model() [3/3]

template<typename BV>

bool bm::xor_scanner< BV >::compute_sim_model | ( | xor_sim_model< BV > & | sim_model,
|  | const bv_ref_vector_type & | ref_vect,
|  | const bm::xor_sim_params & | params )

Calculate matrix of best XOR match metrics per block for the attached collection of bit-vectors.

Returns
  true if computed successfully

Definition at line 1440 of file bmxor.h.

References compute_sim_model().

Referenced by bm::compute_sim_matrix_plan_builder< BV >::build_plan(), compute_sim_model(), and compute_sim_model().

## compute_xor_complexity_descr()

template<typename BV>

void bm::xor_scanner< BV >::compute_xor_complexity_descr | ( | const bm::word_t *BMRESTRICT | block,
|  | bm::id64_t | block_d64,
|  | const bm::word_t *BMRESTRICT | xor_block,
|  | bm::block_waves_xor_descr &BMRESTRICT | x_descr,
|  | bm::block_xor_match_descr &BMRESTRICT | xmd ) const

Compute reference complexity descriptor based on XOR vector.

Returns the digest of sub-blocks where XOR filtering improved the metric (function needs reference to estimate the improvement).

part of Phase 2 of the XOR filtering process

See also
  compute_sub_block_complexity_descr

Definition at line 1070 of file bmxor.h.

References best_metric(), bm::bit_block_xor_change(), bm::block_waves, BM_ASSERT, BMNOEXCEPT, BMRESTRICT, bm::calc_block_digest0(), bm::e_no_xor_match, bm::e_xor_match_BC, bm::e_xor_match_GC, bm::e_xor_match_iBC, bm::gap_max_bits, and bm::set_block_digest_wave_size.

Referenced by search_best_xor_mask().

## deoptimize_gap_blocks()

template<typename BV>

void bm::xor_scanner< BV >::deoptimize_gap_blocks | ( | size_type | nb,
|  | const xor_sim_params & | params )

protected

Deoptimize vertical slice of GAP blocks.

Parameters

  nb | - block number

Definition at line 1690 of file bmxor.h.

References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::compute_s_block_descr(), bm::gap_convert_to_bitset(), bm::gap_length(), bm::get_block_coord(), get_ref_block(), IS_VALID_ADDR, and bm::xor_sim_params::min_gaps.

Referenced by compute_sim_model().

## found_ridx()

template<typename BV>

size_type bm::xor_scanner< BV >::found_ridx | ( |  | ) | const

inline

Definition at line 942 of file bmxor.h.

References BMNOEXCEPT.

Referenced by compute_sim_model().

## free_blocks()

template<typename BV>

void bm::xor_scanner< BV >::free_blocks | ( |  | ) |

protected

Free the collection of temp blocks.

Definition at line 1675 of file bmxor.h.

References BMNOEXCEPT.

Referenced by sync_nb_vect(), and ~xor_scanner().

## get_best_match_type()

template<typename BV>

bm::xor_complement_match bm::xor_scanner< BV >::get_best_match_type | ( |  | ) | const

inline

Return best match type of a found block.

Definition at line 946 of file bmxor.h.

References BMNOEXCEPT.

Referenced by refine_match_chain().

## get_descr()

template<typename BV>

bm::block_waves_xor_descr & bm::xor_scanner< BV >::get_descr | ( |  | ) |

inline

Definition at line 960 of file bmxor.h.

References BMNOEXCEPT.

## get_found_block()

template<typename BV>

const bm::word_t * bm::xor_scanner< BV >::get_found_block | ( |  | ) | const

inline

Definition at line 949 of file bmxor.h.

References BMNOEXCEPT.

## get_match_pairs()

template<typename BV>

match_pairs_vector_type & bm::xor_scanner< BV >::get_match_pairs | ( |  | ) |

inline

Definition at line 969 of file bmxor.h.

References BMNOEXCEPT.

Referenced by compute_sim_model().

## get_match_vector()

template<typename BV>

xor_matches_vector_type & bm::xor_scanner< BV >::get_match_vector | ( |  | ) |

inline

Definition at line 966 of file bmxor.h.

References BMNOEXCEPT.

## get_ref_block()

template<typename BV>

const bm::word_t * bm::xor_scanner< BV >::get_ref_block | ( | size_type | ri,
|  | unsigned | i,
|  | unsigned | j ) const

inline

Return block from the reference vector [vect_idx, block_i, block_j].

Definition at line 974 of file bmxor.h.

References BMNOEXCEPT.

Referenced by apply_xor_match_vector(), compute_sim_model(), deoptimize_gap_blocks(), and search_best_xor_mask().

## get_ref_vector()

template<typename BV>

const bv_ref_vector_type & bm::xor_scanner< BV >::get_ref_vector | ( |  | ) | const

inline

Definition at line 853 of file bmxor.h.

References BMNOEXCEPT.

## get_s_bc()

template<typename BV>

unsigned bm::xor_scanner< BV >::get_s_bc | ( |  | ) | const

inline

Definition at line 954 of file bmxor.h.

References BMNOEXCEPT.

## get_s_block_best()

template<typename BV>

unsigned bm::xor_scanner< BV >::get_s_block_best | ( |  | ) | const

inline

Definition at line 956 of file bmxor.h.

References BMNOEXCEPT.

Referenced by compute_sim_model(), and search_best_xor_mask().

## get_s_block_stats()

template<typename BV>

void bm::xor_scanner< BV >::get_s_block_stats | ( | size_type | ri | ) |

Get statistics for the r-(or s-) block.

Parameters

  ri | - nb cache index

Definition at line 1045 of file bmxor.h.

References best_metric(), BMNOEXCEPT, get_s_block_stats(), and xor_scanner().

Referenced by compute_sim_model(), and get_s_block_stats().

## get_s_gc()

template<typename BV>

unsigned bm::xor_scanner< BV >::get_s_gc | ( |  | ) | const

inline

Definition at line 955 of file bmxor.h.

References BMNOEXCEPT.

## get_x_best_metric()

template<typename BV>

unsigned bm::xor_scanner< BV >::get_x_best_metric | ( |  | ) | const

inline

Definition at line 951 of file bmxor.h.

References BMNOEXCEPT.

## get_xor_digest()

template<typename BV>

bm::id64_t bm::xor_scanner< BV >::get_xor_digest | ( |  | ) | const

inline

Definition at line 952 of file bmxor.h.

References BMNOEXCEPT.

Referenced by compute_sim_model().

## refine_match_chain()

template<typename BV>

xor_scanner< BV >::size_type bm::xor_scanner< BV >::refine_match_chain | ( |  | ) |

Run a search to add possible XOR match chain additions.

Definition at line 1425 of file bmxor.h.

References get_best_match_type(), and bm::greedy_refine_match_vector().

Referenced by compute_sim_model().

## search_best_xor_mask()

template<typename BV>

bm::xor_complement_match bm::xor_scanner< BV >::search_best_xor_mask | ( | const bm::word_t * | s_block,
|  | size_type | ri,
|  | size_type | ridx_from,
|  | size_type | ridx_to,
|  | unsigned | i,
|  | unsigned | j,
|  | bm::word_t * | tx_block,
|  | const bm::xor_sim_params & | params )

Scan for all candidate bit-blocks to find mask or match.

Returns
  XOR referenece match type

Definition at line 1246 of file bmxor.h.

References best_metric(), bm::bit_block_change_bc(), bm::bit_block_xor(), bm::block_find_first_diff(), bm::block_xor_match_descr::block_gain, BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::calc_block_digest0(), compute_xor_complexity_descr(), bm::e_no_xor_match, bm::e_xor_match_BC, bm::e_xor_match_EQ, bm::gap_length(), bm::gap_max_bits, get_ref_block(), get_s_block_best(), IS_VALID_ADDR, bm::block_xor_match_descr::match_type, bm::xor_sim_params::max_lookup_depth, bm::xor_sim_params::min_lookup_depth, bm::block_xor_match_descr::ref_idx, bm::xor_sim_params::stop_gain, bm::xor_sim_params::target_gain_ratio, bm::block_xor_match_descr::xor_bc, bm::block_xor_match_descr::xor_d64, and bm::block_xor_match_descr::xor_gc.

Referenced by compute_sim_model().

## set_ref_vector()

template<typename BV>

void bm::xor_scanner< BV >::set_ref_vector | ( | const bv_ref_vector_type * | ref_vect | ) |

inline

Definition at line 850 of file bmxor.h.

References BMNOEXCEPT.

Referenced by bm::compute_sim_matrix_plan_builder< BV >::build_plan().

## sync_nb_vect()

template<typename BV>

void bm::xor_scanner< BV >::sync_nb_vect | ( |  | ) |

Sync TEMP vector size.

Definition at line 1732 of file bmxor.h.

References free_blocks().

Referenced by bm::compute_sim_matrix_plan_builder< BV >::build_plan(), and compute_sim_model().

## validate_xor()

template<typename BV>

bool bm::xor_scanner< BV >::validate_xor | ( | const bm::word_t * | xor_block | ) | const

Check if XOR transform simplified block enough for compressibility objective.

References BMNOEXCEPT.

The documentation for this class was generated from the following file:

- bmxor.h