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_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

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ bv_allocator_type

◆ bv_bcgc_vector_type

◆ bv_blocks_vector_type

◆ bv_ref_vector_type

◆ bv_xdescr_vector_type

◆ bvector_type

◆ match_pairs_vector_type

◆ matrix_chain_type

◆ size_type

◆ xor_matches_vector_type

Constructor & Destructor Documentation

◆ xor_scanner()

◆ ~xor_scanner()

Member Function Documentation

◆ apply_xor_match_vector()

◆ best_metric()

◆ compute_s_block_stats()

◆ compute_sim_model() [1/3]

◆ compute_sim_model() [2/3]

◆ compute_sim_model() [3/3]

◆ compute_xor_complexity_descr()

◆ deoptimize_gap_blocks()

◆ found_ridx()

◆ free_blocks()

◆ get_best_match_type()

◆ get_descr()

◆ get_found_block()

◆ get_match_pairs()

◆ get_match_vector()

◆ get_ref_block()

◆ get_ref_vector()

◆ get_s_bc()

◆ get_s_block_best()

◆ get_s_block_stats()

◆ get_s_gc()

◆ get_x_best_metric()

◆ get_xor_digest()

◆ refine_match_chain()

◆ search_best_xor_mask()

◆ set_ref_vector()

◆ sync_nb_vect()

◆ validate_xor()