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 ()
	More...

void	set_ref_vector (const bv_ref_vector_type *ref_vect) BMNOEXCEPT
	More...

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. More...

void	compute_s_block_stats (const bm::word_t *block) BMNOEXCEPT
	Compute statistics for the r-(or s-) block. More...

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. More...

size_type	refine_match_chain ()
	Run a search to add possible XOR match chain additions. More...

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. More...

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. More...

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. More...

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. More...

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. More...

bool	validate_xor (const bm::word_t *xor_block) const BMNOEXCEPT
	Check if XOR transform simplified block enough for compressibility objective. More...

size_type	found_ridx () const BMNOEXCEPT
	More...

bm::xor_complement_match	get_best_match_type () const BMNOEXCEPT
	Return best match type of a found block. More...

const bm::word_t *	get_found_block () const BMNOEXCEPT

unsigned	get_x_best_metric () const BMNOEXCEPT

bm::id64_t	get_xor_digest () const BMNOEXCEPT
	More...

unsigned	get_s_bc () const BMNOEXCEPT

unsigned	get_s_gc () const BMNOEXCEPT

unsigned	get_s_block_best () const BMNOEXCEPT
	More...

bm::block_waves_xor_descr &	get_descr () BMNOEXCEPT

xor_matches_vector_type &	get_match_vector () BMNOEXCEPT

match_pairs_vector_type &	get_match_pairs () BMNOEXCEPT
	More...

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]. More...

void	sync_nb_vect ()
	Sync TEMP vector size. More...

Static Public Member Functions
static bm::xor_complement_match	best_metric (unsigned bc, unsigned gc, unsigned *best_metric) BMNOEXCEPT
	More...

Protected Member Functions
void	deoptimize_gap_blocks (size_type nb, const xor_sim_params &params)
	Deoptimize vertical slice of GAP blocks. More...

void	free_blocks () BMNOEXCEPT
	Free the collection of temp blocks. More...

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 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, bm::xor_scanner< BV >::get_ref_block(), bm::match_pair::ref_idx, and bm::match_pair::xor_d64.

Referenced by bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::best_metric(), BM_ASSERT, bm::e_xor_match_BC, bm::e_xor_match_GC, bm::e_xor_match_iBC, and bm::gap_max_bits.

Referenced by bm::xor_scanner< BV >::best_metric(), bm::xor_scanner< BV >::compute_s_block_stats(), bm::xor_scanner< BV >::compute_sim_model(), bm::xor_scanner< BV >::compute_xor_complexity_descr(), bm::xor_scanner< BV >::get_s_block_stats(), and bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::best_metric(), BM_ASSERT, BM_IS_GAP, 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 bm::xor_scanner< BV >::apply_xor_match_vector(), bm::xor_scanner< BV >::best_metric(), bm::bit_block_change_bc(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::block_match_chain< BLOCK_IDX >::chain_size, bm::xor_scanner< BV >::deoptimize_gap_blocks(), bm::e_no_xor_match, bm::e_xor_match_EQ, bm::xor_scanner< BV >::found_ridx(), bm::gap_length(), bm::gap_max_bits, bm::get_block_coord(), bm::xor_scanner< BV >::get_match_pairs(), bm::xor_scanner< BV >::get_ref_block(), bm::xor_scanner< BV >::get_s_block_best(), bm::xor_scanner< BV >::get_s_block_stats(), bm::xor_scanner< BV >::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::match_pair::ref_idx, bm::block_match_chain< BLOCK_IDX >::ref_idx, bm::xor_scanner< BV >::refine_match_chain(), bm::xor_scanner< BV >::search_best_xor_mask(), bm::bv_ref_vector< BV >::size(), bm::match_pair::xor_d64, and bm::block_match_chain< BLOCK_IDX >::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::bv_ref_vector< BV >::build_nb_digest_and_xor_matrix(), bm::xor_sim_model< BV >::bv_blocks, bm::xor_scanner< BV >::compute_sim_model(), bm::xor_sim_model< BV >::matr, bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::compute_sim_model().

Referenced by bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::best_metric(), bm::bit_block_xor_change(), bm::block_waves, BM_ASSERT, 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 bm::xor_scanner< BV >::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(), bm::xor_scanner< BV >::get_ref_block(), IS_VALID_ADDR, bm::xor_sim_params::min_gaps, and bm::bv_ref_vector< BV >::size().

Referenced by bm::xor_scanner< BV >::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.

Referenced by bm::xor_scanner< BV >::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.

Referenced by bm::xor_scanner< BV >::sync_nb_vect(), and bm::xor_scanner< BV >::~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.

Referenced by bm::xor_scanner< BV >::refine_match_chain().

◆ 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.

Referenced by bm::xor_scanner< BV >::compute_sim_model().

◆ 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 bm::bv_ref_vector< BV >::get_bv().

Referenced by bm::xor_scanner< BV >::apply_xor_match_vector(), bm::xor_scanner< BV >::compute_sim_model(), bm::xor_scanner< BV >::deoptimize_gap_blocks(), and bm::xor_scanner< BV >::search_best_xor_mask().

◆ 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.

Referenced by bm::xor_scanner< BV >::compute_sim_model(), and bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::best_metric().

Referenced by bm::xor_scanner< BV >::compute_sim_model().

◆ 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.

Referenced by bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::get_best_match_type(), and bm::greedy_refine_match_vector().

Referenced by bm::xor_scanner< BV >::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 bm::xor_scanner< BV >::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(), bm::xor_scanner< BV >::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, bm::xor_scanner< BV >::get_ref_block(), bm::xor_scanner< BV >::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::bv_ref_vector< BV >::size(), 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 bm::xor_scanner< BV >::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.

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 bm::xor_scanner< BV >::free_blocks(), and bm::bv_ref_vector< BV >::size().

Referenced by bm::xor_scanner< BV >::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.

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 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_match_pairs()

◆ get_ref_block()

◆ get_s_block_best()

◆ get_s_block_stats()

◆ get_xor_digest()

◆ refine_match_chain()

◆ search_best_xor_mask()

◆ set_ref_vector()

◆ sync_nb_vect()

◆ validate_xor()